aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/icode/hipe_icode_range.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/icode/hipe_icode_range.erl')
-rw-r--r--lib/hipe/icode/hipe_icode_range.erl1966
1 files changed, 1966 insertions, 0 deletions
diff --git a/lib/hipe/icode/hipe_icode_range.erl b/lib/hipe/icode/hipe_icode_range.erl
new file mode 100644
index 0000000000..bcc857acf4
--- /dev/null
+++ b/lib/hipe/icode/hipe_icode_range.erl
@@ -0,0 +1,1966 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2007-2009. All Rights Reserved.
+%%
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%%
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%%
+%% %CopyrightEnd%
+%%
+%%%-------------------------------------------------------------------
+%%% File : hipe_icode_range.erl
+%%% Author : Per Gustafsson <[email protected]>
+%%% Description :
+%%%
+%%% Created : 12 Mar 2007 by Per Gustafsson <[email protected]>
+%%%-------------------------------------------------------------------
+-module(hipe_icode_range).
+
+-export([cfg/4]).
+
+%%=====================================================================
+%% Icode Coordinator Behaviour Callbacks
+%%=====================================================================
+
+-export([replace_nones/1,
+ update__info/2, new__info/1, return__info/1,
+ return_none/0, return_none_args/2, return_any_args/2]).
+
+%%=====================================================================
+
+-import(erl_types, [t_any/0,
+ t_from_range_unsafe/2,
+ t_inf/2, t_integer/0,
+ t_to_string/1, t_to_tlist/1,
+ t_limit/2, t_none/0,
+ number_min/1, number_max/1]).
+
+-include("hipe_icode.hrl").
+-include("hipe_icode_primops.hrl").
+-include("../main/hipe.hrl").
+-include("../flow/cfg.hrl").
+-include("../flow/hipe_bb.hrl").
+-include("hipe_icode_type.hrl").
+
+-type range_tuple() :: {'neg_inf' | integer(), 'pos_inf' | integer()}.
+-type range_rep() :: range_tuple() | 'empty'.
+-type fun_name() :: atom() | tuple().
+-type inf_integer() :: 'neg_inf' | 'pos_inf' | integer().
+
+-record(range, {range :: range_rep(),
+ other :: boolean()}).
+
+-record(ann, {range :: #range{},
+ type :: erl_types:erl_type(),
+ count :: integer()}).
+
+-type range_anno() :: {range_anno, #ann{}, fun((#ann{}) -> string())}.
+-type args_fun() :: fun((mfa(),cfg()) -> [#range{}]).
+-type call_fun() :: fun((mfa(),[#range{}]) -> #range{}).
+-type final_fun() :: fun((mfa(),[#range{}]) -> ok).
+-type data() :: {mfa(), args_fun(), call_fun(), final_fun()}.
+-type label() :: non_neg_integer().
+-type info() :: gb_tree().
+-type work_list() :: {[label()], [label()], set()}.
+-type variable() :: #icode_variable{}.
+-type annotated_variable() :: #icode_variable{}.
+-type argument() :: #icode_const{} | variable().
+-type three_range_fun() :: fun((#range{},#range{},#range{}) -> #range{}).
+-type instr_split_info() :: {icode_instr(), [{label(),info()}]}.
+-type last_instr_return() :: {instr_split_info(), #range{}}.
+
+-record(state, {info_map = gb_trees:empty() :: info(),
+ counter = dict:new() :: dict(),
+ cfg :: cfg(),
+ liveness = gb_trees:empty() :: gb_tree(),
+ ret_type :: #range{},
+ lookup_fun :: call_fun(),
+ result_action :: final_fun()}).
+
+-define(WIDEN, 1).
+
+-define(TAG_IMMED1_SIZE, 4).
+
+-define(BITS, 64).
+
+%%---------------------------------------------------------------------
+
+-spec cfg(cfg(), mfa(), comp_options(), #comp_servers{}) -> cfg().
+
+cfg(Cfg, MFA, Options, Servers) ->
+ case proplists:get_bool(concurrent_comp, Options) of
+ true ->
+ concurrent_cfg(Cfg, MFA, Servers#comp_servers.range);
+ false ->
+ ordinary_cfg(Cfg, MFA)
+ end.
+
+-spec concurrent_cfg(cfg(), mfa(), pid()) -> cfg().
+
+concurrent_cfg(Cfg, MFA, CompServer) ->
+ CompServer ! {ready, {MFA,self()}},
+ {ArgsFun,CallFun,FinalFun} = do_analysis(Cfg, MFA),
+ Ans = do_rewrite(Cfg, MFA, ArgsFun, CallFun, FinalFun),
+ CompServer ! {done_rewrite, MFA},
+ Ans.
+
+-spec do_analysis(cfg(), mfa()) -> {args_fun(), call_fun(), final_fun()}.
+
+do_analysis(Cfg, MFA) ->
+ receive
+ {analyse, {ArgsFun, CallFun, FinalFun}} ->
+ analyse(Cfg, {MFA, ArgsFun, CallFun, FinalFun}),
+ do_analysis(Cfg, MFA);
+ {done, {_NewArgsFun, _NewCallFun, _NewFinalFun} = T} ->
+ T
+ end.
+
+-spec do_rewrite(cfg(), mfa(), args_fun(), call_fun(), final_fun()) -> cfg().
+
+do_rewrite(Cfg, MFA, ArgsFun, CallFun, FinalFun) ->
+ common_rewrite(Cfg, {MFA, ArgsFun, CallFun, FinalFun}).
+
+-spec ordinary_cfg(cfg(), mfa()) -> cfg().
+
+ordinary_cfg(Cfg, MFA) ->
+ Data = make_data(Cfg,MFA),
+ common_rewrite(Cfg, Data).
+
+-spec common_rewrite(cfg(), data()) -> cfg().
+
+common_rewrite(Cfg, Data) ->
+ State = safe_analyse(Cfg, Data),
+ State2 = rewrite_blocks(State),
+ Cfg1 = state__cfg(State2),
+ Cfg2 = hipe_icode_cfg:remove_unreachable_code(Cfg1),
+ Cfg3 = convert_cfg_to_types(Cfg2),
+ hipe_icode_type:specialize(Cfg3).
+
+-spec make_data(cfg(), mfa()) -> data().
+
+make_data(Cfg, {_M,_F,A}=MFA) ->
+ NoArgs =
+ case hipe_icode_cfg:is_closure(Cfg) of
+ true -> hipe_icode_cfg:closure_arity(Cfg)+1;
+ false -> A
+ end,
+ Args = lists:duplicate(NoArgs, any_type()),
+ ArgsFun = fun(_,_) -> Args end,
+ CallFun = fun(_,_) -> any_type() end,
+ FinalFun = fun(_,_) -> ok end,
+ {MFA, ArgsFun, CallFun, FinalFun}.
+
+-spec analyse(cfg(), data()) -> 'ok'.
+
+analyse(Cfg, Data) ->
+ try
+ #state{} = safe_analyse(Cfg, Data),
+ ok
+ catch throw:no_input -> ok
+ end.
+
+-spec safe_analyse(cfg(), data()) -> #state{}.
+
+safe_analyse(CFG, Data={MFA,_,_,_}) ->
+ State = state__init(CFG, Data),
+ Work = init_work(State),
+ NewState = analyse_blocks(State, Work),
+ (state__result_action(NewState))(MFA, [state__ret_type(NewState)]),
+ NewState.
+
+-spec rewrite_blocks(#state{}) -> #state{}.
+
+rewrite_blocks(State) ->
+ CFG = state__cfg(State),
+ Start = hipe_icode_cfg:start_label(CFG),
+ rewrite_blocks([Start], State, [Start]).
+
+-spec rewrite_blocks([label()], #state{}, [label()]) -> #state{}.
+
+rewrite_blocks([Next|Rest], State, Visited) ->
+ Info = state__info_in(State, Next),
+ {NewState, NewLabels} = analyse_block(Next, Info, State, true),
+ NewLabelsSet = ordsets:from_list(NewLabels),
+ RealNew = ordsets:subtract(NewLabelsSet, Visited),
+ NewVisited = ordsets:union([RealNew, Visited, [Next]]),
+ NewWork = ordsets:union([RealNew, Rest]),
+ rewrite_blocks(NewWork, NewState, NewVisited);
+rewrite_blocks([], State, _) ->
+ State.
+
+-spec analyse_blocks(#state{}, work_list()) -> #state{}.
+
+analyse_blocks(State, Work) ->
+ case get_work(Work) of
+ fixpoint ->
+ State;
+ {Label, NewWork} ->
+ Info = state__info_in(State, Label),
+ {NewState, NewLabels} =
+ try analyse_block(Label, Info, State, false)
+ catch throw:none_range ->
+ {State, []}
+ end,
+ NewWork2 = add_work(NewWork, NewLabels),
+ analyse_blocks(NewState, NewWork2)
+ end.
+
+-spec analyse_block(label(), info(), #state{}, boolean()) -> {#state{}, [label()]}.
+
+analyse_block(Label, Info, State, Rewrite) ->
+ BB = state__bb(State, Label),
+ Code = hipe_bb:code(BB),
+ {NewCode, InfoList, RetType} =
+ analyse_BB(Code, Info, [], Rewrite, state__lookup_fun(State)),
+ State1 = state__bb_add(State, Label, hipe_bb:mk_bb(NewCode)),
+ State2 = state__ret_type_update(State1, RetType),
+ state__update_info(State2, InfoList, Rewrite).
+
+-spec analyse_BB([icode_instr()], info(), [icode_instr()], boolean(), call_fun()) ->
+ {[icode_instr()], [{label(),info()}], #range{}}.
+
+analyse_BB([Last], Info, Code, Rewrite, LookupFun) ->
+ {{NewI, LabelInfoList}, RetType} =
+ analyse_last_insn(Last, Info, Rewrite, LookupFun),
+ {lists:reverse([NewI|Code]), LabelInfoList, RetType};
+analyse_BB([Insn|InsnList], Info, Code, Rewrite, LookupFun) ->
+ {NewInfo, NewI} = analyse_insn(Insn, Info, LookupFun),
+ analyse_BB(InsnList, NewInfo, [NewI|Code], Rewrite, LookupFun).
+
+-spec analyse_insn(icode_instr(), info(), call_fun()) -> {info(), icode_instr()}.
+
+analyse_insn(I, Info, LookupFun) ->
+ %% io:format("~w Info: ~p~n", [I, Info]),
+ NewI = handle_args(I,Info),
+ FinalI =
+ case NewI of
+ #icode_call{} -> analyse_call(NewI, LookupFun);
+ #icode_move{} -> analyse_move(NewI);
+ #icode_phi{} -> analyse_phi(NewI);
+ #icode_begin_handler{} -> analyse_begin_handler(NewI);
+ #icode_comment{} -> NewI
+ end,
+ {enter_vals(FinalI, Info), FinalI}.
+
+-spec handle_args(icode_instr(), info()) -> icode_instr().
+
+handle_args(I, Info) ->
+ WidenFun = fun update_three/3,
+ handle_args(I, Info, WidenFun).
+
+-spec handle_args(icode_instr(), info(), three_range_fun()) -> icode_instr().
+
+handle_args(I, Info, WidenFun) ->
+ Uses = hipe_icode:uses(I),
+ PresentRanges = [lookup(V, Info) || V <- Uses],
+ %% io:format("Uses: ~p~nRanges: ~p~n", [Uses, PresentRanges]),
+ JoinFun = fun(Var, Range) -> update_info(Var, Range, WidenFun) end,
+ NewUses = lists:zipwith(JoinFun, Uses, PresentRanges),
+ hipe_icode:subst_uses(lists:zip(Uses, NewUses),I).
+
+-spec join_info(#ann{}, #range{}, three_range_fun()) -> #ann{}.
+
+join_info(Ann = #ann{range = R1, type = Type, count = ?WIDEN}, R2, Fun) ->
+ Ann#ann{range = Fun(R1, R2, range_from_simple_type(Type))};
+join_info(Ann = #ann{range = R1, type = Type, count = C}, R2, _Fun) when C < ?WIDEN ->
+ case join_three(R1, R2, range_from_simple_type(Type)) of
+ R1 -> Ann;
+ NewR -> Ann#ann{range = NewR, count = C+1}
+ end.
+
+-spec join_three(#range{}, #range{}, #range{}) -> #range{}.
+
+join_three(R1, R2, R3) ->
+ inf(sup(R1, R2), R3).
+
+-spec update_info(variable(), #range{}) -> annotated_variable().
+
+update_info(Var, Range) ->
+ update_info(Var, Range, fun update_three/3).
+
+-spec update_info(variable(), #range{}, three_range_fun()) -> annotated_variable().
+
+update_info(Arg, R, Fun) ->
+ case hipe_icode:is_annotated_variable(Arg) of
+ true ->
+ Ann = hipe_icode:variable_annotation(Arg),
+ hipe_icode:annotate_variable(Arg, update_info1(Ann, R, Fun));
+ false ->
+ Arg
+ end.
+
+-spec update_info1(any(), #range{}, three_range_fun()) -> range_anno().
+
+update_info1({range_anno, Ann, _}, R2, Fun) ->
+ make_range_anno(update_ann(Ann,R2,Fun));
+update_info1({type_anno, Type, _}, R2, Fun) ->
+ make_range_anno(update_ann(type_to_ann(Type), R2, Fun)).
+
+update_ann(Ann = #ann{range = R1, type = Type, count = ?WIDEN}, R2, Fun) ->
+ Ann#ann{range = Fun(R1,R2,range_from_simple_type(Type))};
+update_ann(Ann = #ann{range = R1, type = Type, count = C}, R2, _Fun) ->
+ case update_three(R1, R2, range_from_simple_type(Type)) of
+ R1 -> Ann;
+ NewR -> Ann#ann{range = NewR, count = C+1}
+ end.
+
+-spec type_to_ann(erl_types:erl_type()) -> #ann{}.
+
+type_to_ann(Type) ->
+ #ann{range = range_from_simple_type(Type), type = t_limit(Type,1), count=1}.
+
+-spec make_range_anno(#ann{}) -> range_anno().
+
+make_range_anno(Ann) ->
+ {range_anno, Ann, fun pp_ann/1}.
+
+-spec update_three(#range{}, #range{}, #range{}) -> #range{}.
+
+update_three(_R1, R2, R3) ->
+ inf(R2, R3).
+
+-spec safe_widen(#range{}, #range{}, #range{}) -> #range{}.
+
+safe_widen(#range{range=Old}, #range{range=New}, T = #range{range=Wide}) ->
+ ResRange =
+ case {Old,New,Wide} of
+ {{Min,Max1},{Min,Max2},{_,Max}} ->
+ case inf_geq(OMax = next_up_limit(inf_max([Max1,Max2])),Max) of
+ true -> {Min,Max};
+ false -> {Min,OMax}
+ end;
+ {{Min1,Max},{Min2,Max},{Min,_}} ->
+ case inf_geq(Min, OMin = next_down_limit(inf_min([Min1,Min2]))) of
+ true -> {Min,Max};
+ false -> {OMin,Max}
+ end;
+ {{Min1,Max1},{Min2,Max2},{Min,Max}} ->
+ RealMax =
+ case inf_geq(OMax = next_up_limit(inf_max([Max1,Max2])),Max) of
+ true -> Max;
+ false -> OMax
+ end,
+ RealMin =
+ case inf_geq(Min, OMin = next_down_limit(inf_min([Min1,Min2]))) of
+ true -> Min;
+ false -> OMin
+ end,
+ {RealMin,RealMax};
+ _ ->
+ Wide
+ end,
+ T#range{range=ResRange}.
+
+-spec widen(#range{}, #range{}, #range{}) -> #range{}.
+
+widen(#range{range=Old}, #range{range=New}, T = #range{range=Wide}) ->
+ ResRange =
+ case {Old,New,Wide} of
+ {{Min,_},{Min,Max2},{_,Max}} ->
+ case inf_geq(OMax = next_up_limit(Max2),Max) of
+ true -> {Min,Max};
+ false -> {Min,OMax}
+ end;
+ {{_,Max},{Min2,Max},{Min,_}} ->
+ case inf_geq(Min, OMin = next_down_limit(Min2)) of
+ true -> {Min,Max};
+ false -> {OMin,Max}
+ end;
+ {_,{Min2,Max2},{Min,Max}} ->
+ RealMax =
+ case inf_geq(OMax = next_up_limit(Max2),Max) of
+ true -> Max;
+ false -> OMax
+ end,
+ RealMin =
+ case inf_geq(Min, OMin = next_down_limit(Min2)) of
+ true -> Min;
+ false -> OMin
+ end,
+ {RealMin,RealMax};
+ _ ->
+ Wide
+ end,
+ T#range{range=ResRange}.
+
+-spec analyse_call(#icode_call{}, call_fun()) -> #icode_call{}.
+
+analyse_call(Call, LookupFun) ->
+ case hipe_icode:call_dstlist(Call) of
+ [] ->
+ Call;
+ Dsts ->
+ Args = hipe_icode:args(Call),
+ Fun = hipe_icode:call_fun(Call),
+ Type = hipe_icode:call_type(Call),
+ DstRanges = analyse_call_or_enter_fun(Fun, Args, Type, LookupFun),
+ NewDefs = [update_info(Var, R) || {Var,R} <- lists:zip(Dsts, DstRanges)],
+ hipe_icode:subst_defines(lists:zip(Dsts, NewDefs), Call)
+ end.
+
+-spec analyse_move(#icode_move{}) -> #icode_move{}.
+
+analyse_move(Move) ->
+ Src = hipe_icode:move_src(Move),
+ Dst = hipe_icode:move_dst(Move),
+ Range = get_range_from_arg(Src),
+ NewDst = update_info(Dst, Range),
+ hipe_icode:subst_defines([{Dst,NewDst}], Move).
+
+-spec analyse_begin_handler(#icode_begin_handler{}) -> #icode_begin_handler{}.
+
+analyse_begin_handler(Handler) ->
+ SubstList =
+ [{Dst,update_info(Dst,any_type())} ||
+ Dst <- hipe_icode:begin_handler_dstlist(Handler)],
+ hipe_icode:subst_defines(SubstList, Handler).
+
+-spec analyse_phi(#icode_phi{}) -> #icode_phi{}.
+
+analyse_phi(Phi) ->
+ {_, Args} = lists:unzip(hipe_icode:phi_arglist(Phi)),
+ Dst = hipe_icode:phi_dst(Phi),
+ ArgRanges = get_range_from_args(Args),
+ %% io:format("Phi-Arg_ranges: ~p ~n", [Arg_ranges]),
+ DstRange = sup(ArgRanges),
+ NewDst = update_info(Dst, DstRange, fun widen/3),
+ hipe_icode:subst_defines([{Dst, NewDst}], Phi).
+
+-spec analyse_last_insn(icode_instr(), info(), boolean(), call_fun()) ->
+ last_instr_return().
+
+analyse_last_insn(I, Info, Rewrite, LookupFun) ->
+ %% io:format("~w Info: ~p~n",[I,Info]),
+ NewI = handle_args(I, Info),
+ %% io:format("~w -> ~w~n",[NewI,I]),
+ case NewI of
+ #icode_return{} -> analyse_return(NewI, Info);
+ #icode_enter{} -> analyse_enter(NewI, Info, LookupFun);
+ #icode_switch_val{} ->
+ {analyse_switch_val(NewI, Info, Rewrite), none_type()};
+ #icode_if{} -> {analyse_if(NewI, Info, Rewrite), none_type()};
+ #icode_goto{} -> {analyse_goto(NewI, Info), none_type()};
+ #icode_type{} -> {analyse_type(NewI, Info, Rewrite), none_type()};
+ #icode_fail{} -> {analyse_fail(NewI, Info), none_type()};
+ #icode_call{} -> {analyse_last_call(NewI, Info, LookupFun), none_type()};
+ #icode_switch_tuple_arity{} ->
+ {analyse_switch_tuple_arity(NewI, Info), none_type()};
+ #icode_begin_try{} -> {analyse_begin_try(NewI, Info), none_type()}
+ end.
+
+-spec analyse_return(#icode_return{}, info()) -> last_instr_return().
+
+analyse_return(Insn, _Info) ->
+ [RetRange] = get_range_from_args(hipe_icode:return_vars(Insn)),
+ {{Insn,[]}, RetRange}.
+
+-spec analyse_enter(#icode_enter{}, info(), call_fun()) -> last_instr_return().
+
+analyse_enter(Insn, _Info, LookupFun) ->
+ Args = hipe_icode:args(Insn),
+ Fun = hipe_icode:enter_fun(Insn),
+ CallType = hipe_icode:enter_type(Insn),
+ [RetRange] = analyse_call_or_enter_fun(Fun, Args, CallType, LookupFun),
+ {{Insn,[]}, RetRange}.
+
+-spec analyse_switch_val(#icode_switch_val{}, info(), boolean()) -> instr_split_info().
+
+analyse_switch_val(Switch, Info, Rewrite) ->
+ Var = hipe_icode:switch_val_term(Switch),
+ SwitchRange = get_range_from_arg(Var),
+ Cases = hipe_icode:switch_val_cases(Switch),
+ {FailRange, LabelRangeList} = get_range_label_list(Cases, SwitchRange, []),
+ case range__is_none(FailRange) of
+ true ->
+ InfoList = update_infos(Var, Info, LabelRangeList),
+ if Rewrite -> {update_switch(Switch, LabelRangeList, false), InfoList};
+ true -> {Switch, InfoList}
+ end;
+ false ->
+ FailLabel = hipe_icode:switch_val_fail_label(Switch),
+ InfoList = update_infos(Var, Info, [{FailRange, FailLabel}|LabelRangeList]),
+ if Rewrite -> {update_switch(Switch, LabelRangeList, true), InfoList};
+ true -> {Switch, InfoList}
+ end
+ end.
+
+-spec update_infos(argument(), info(), [{#range{},label()}]) -> [{label(),info()}].
+
+update_infos(Arg, Info, [{Range, Label}|Rest]) ->
+ [{Label,enter_define({Arg,Range},Info)} | update_infos(Arg,Info,Rest)];
+update_infos(_, _, []) -> [].
+
+-spec get_range_label_list([{argument(),label()}], #range{}, [{#range{},label()}]) ->
+ {#range{},[{#range{},label()}]}.
+
+get_range_label_list([{Val,Label}|Cases], SRange, Acc) ->
+ VRange = get_range_from_arg(Val),
+ None = none_type(),
+ case inf(SRange, VRange) of
+ None ->
+ get_range_label_list(Cases, SRange, Acc);
+ ResRange ->
+ get_range_label_list(Cases, SRange, [{ResRange,Label}|Acc])
+ end;
+get_range_label_list([], SRange, Acc) ->
+ {PointTypes, _} = lists:unzip(Acc),
+ {remove_point_types(SRange, PointTypes), Acc}.
+
+-spec update_switch(#icode_switch_val{}, [{#range{},label()}], boolean()) ->
+ #icode_switch_val{}.
+
+update_switch(Switch, LabelRangeList, KeepFail) ->
+ S2 =
+ case label_range_list_to_cases(LabelRangeList, []) of
+ no_update ->
+ Switch;
+ Cases ->
+ hipe_icode:switch_val_cases_update(Switch, Cases)
+ end,
+ if KeepFail -> S2;
+ true -> S2
+ end.
+
+-spec label_range_list_to_cases([{#range{},label()}], [{#icode_const{},label()}]) ->
+ 'no_update' | [{#icode_const{},label()}].
+
+label_range_list_to_cases([{#range{range={C,C},other=false},Label}|Rest],
+ Acc) when is_integer(C) ->
+ label_range_list_to_cases(Rest, [{hipe_icode:mk_const(C),Label}|Acc]);
+label_range_list_to_cases([{_NotAConstantRange,_Label}|_Rest], _Acc) ->
+ no_update;
+label_range_list_to_cases([], Acc) ->
+ lists:reverse(Acc).
+
+-spec analyse_switch_tuple_arity(#icode_switch_tuple_arity{}, info()) ->
+ {#icode_switch_tuple_arity{}, [{label(),info()}]}.
+
+analyse_switch_tuple_arity(Switch, Info) ->
+ Var = hipe_icode:switch_tuple_arity_term(Switch),
+ NewInfo = enter_define({Var, get_range_from_arg(Var)}, Info),
+ Cases = hipe_icode:switch_tuple_arity_cases(Switch),
+ Fail = hipe_icode:switch_tuple_arity_fail_label(Switch),
+ {_, Case_labels} = lists:unzip(Cases),
+ Labels = [Fail|Case_labels],
+ {Switch, [{Label,NewInfo} || Label <- Labels]}.
+
+-spec analyse_goto(#icode_goto{}, info()) -> {#icode_goto{}, [{label(),info()},...]}.
+
+analyse_goto(Insn, Info) ->
+ GotoLabel = hipe_icode:goto_label(Insn),
+ {Insn, [{GotoLabel,Info}]}.
+
+-spec analyse_fail(#icode_fail{}, info()) -> {#icode_fail{}, [{label(),info()}]}.
+
+analyse_fail(Fail, Info) ->
+ case hipe_icode:fail_label(Fail) of
+ [] -> {Fail, []};
+ Label -> {Fail, [{Label,Info}]}
+ end.
+
+-spec analyse_begin_try(#icode_begin_try{}, info()) ->
+ {#icode_begin_try{}, [{label(),info()},...]}.
+
+analyse_begin_try(Insn, Info) ->
+ Label = hipe_icode:begin_try_label(Insn),
+ Successor = hipe_icode:begin_try_successor(Insn),
+ {Insn, [{Label,Info},{Successor,Info}]}.
+
+-spec analyse_last_call(#icode_call{}, info(), call_fun()) ->
+ {#icode_call{}, [{label(),info()},...]}.
+
+analyse_last_call(Call, Info, LookupFun) ->
+ %% hipe_icode_pp:pp_block([Insn]),
+ NewI = analyse_call(Call, LookupFun),
+ Continuation = hipe_icode:call_continuation(Call),
+ NewInfo = enter_vals(NewI, Info),
+ case hipe_icode:call_fail_label(Call) of
+ [] ->
+ {NewI, [{Continuation,NewInfo}]};
+ Fail ->
+ {NewI, [{Continuation,NewInfo}, {Fail,Info}]}
+ end.
+
+-spec analyse_if(#icode_if{}, info(), boolean()) ->
+ {#icode_goto{} | #icode_if{}, [{label(),info()}]}.
+
+analyse_if(If, Info, Rewrite) ->
+ case hipe_icode:if_args(If) of
+ Args = [_,_] ->
+ analyse_sane_if(If, Info, Args, get_range_from_args(Args), Rewrite);
+ _ ->
+ TrueLabel = hipe_icode:if_true_label(If),
+ FalseLabel = hipe_icode:if_false_label(If),
+ {If, [{TrueLabel,Info},{FalseLabel,Info}]}
+ end.
+
+-spec analyse_sane_if(#icode_if{}, info(), [argument(),...],
+ [#range{},...], boolean()) ->
+ {#icode_goto{} | #icode_if{}, [{label(), info()}]}.
+
+analyse_sane_if(If, Info, [Arg1, Arg2], [Range1, Range2], Rewrite) ->
+ case normalize_name(hipe_icode:if_op(If)) of
+ '>' ->
+ {TrueRange2, TrueRange1, FalseRange2, FalseRange1} =
+ range_inequality_propagation(Range2, Range1);
+ '==' ->
+ {TempTrueRange1, TempTrueRange2, FalseRange1, FalseRange2}=
+ range_equality_propagation(Range1, Range2),
+ TrueRange1 = set_other(TempTrueRange1,other(Range1)),
+ TrueRange2 = set_other(TempTrueRange2,other(Range2));
+ '<' ->
+ {TrueRange1, TrueRange2, FalseRange1, FalseRange2} =
+ range_inequality_propagation(Range1, Range2);
+ '>=' ->
+ {FalseRange1, FalseRange2, TrueRange1, TrueRange2} =
+ range_inequality_propagation(Range1, Range2);
+ '=<' ->
+ {FalseRange2, FalseRange1, TrueRange2, TrueRange1} =
+ range_inequality_propagation(Range2, Range1);
+ '=:=' ->
+ {TrueRange1, TrueRange2, FalseRange1, FalseRange2}=
+ range_equality_propagation(Range1, Range2);
+ '=/=' ->
+ {FalseRange1, FalseRange2, TrueRange1, TrueRange2} =
+ range_equality_propagation(Range1, Range2);
+ '/=' ->
+ {TempFalseRange1, TempFalseRange2, TrueRange1, TrueRange2}=
+ range_equality_propagation(Range1, Range2),
+ FalseRange1 = set_other(TempFalseRange1,other(Range1)),
+ FalseRange2 = set_other(TempFalseRange2,other(Range2))
+ end,
+ TrueLabel = hipe_icode:if_true_label(If),
+ FalseLabel = hipe_icode:if_false_label(If),
+ TrueInfo =
+ enter_defines([{Arg1,TrueRange1}, {Arg2,TrueRange2}],Info),
+ FalseInfo =
+ enter_defines([{Arg1,FalseRange1}, {Arg2,FalseRange2}],Info),
+ True =
+ case lists:any(fun range__is_none/1,[TrueRange1,TrueRange2]) of
+ true -> [];
+ false -> [{TrueLabel,TrueInfo}]
+ end,
+ False =
+ case lists:any(fun range__is_none/1, [FalseRange1,FalseRange2]) of
+ true -> [];
+ false -> [{FalseLabel,FalseInfo}]
+ end,
+ UpdateInfo = True++False,
+ NewIF =
+ if Rewrite ->
+ %%io:format("~w~n~w~n", [{Arg1,FalseRange1},{Arg2,FalseRange2}]),
+ %%io:format("Any none: ~w~n", [lists:any(fun range__is_none/1,[FalseRange1,FalseRange2])]),
+ case UpdateInfo of
+ [] -> %%This is weird
+ If;
+ [{Label,_Info}] ->
+ hipe_icode:mk_goto(Label);
+ [_,_] ->
+ If
+ end;
+ true ->
+ If
+ end,
+ {NewIF, UpdateInfo}.
+
+-spec normalize_name(atom()) -> atom().
+
+normalize_name(Name) ->
+ case Name of
+ 'fixnum_eq' -> '=:=';
+ 'fixnum_neq' -> '=/=';
+ 'fixnum_gt' -> '>';
+ 'fixnum_lt' -> '<';
+ 'fixnum_ge' -> '>=';
+ 'fixnum_le' -> '=<';
+ Name -> Name
+ end.
+
+-spec range_equality_propagation(#range{}, #range{}) ->
+ {#range{}, #range{}, #range{}, #range{}}.
+
+range_equality_propagation(Range_1, Range_2) ->
+ True_range = inf(Range_1, Range_2),
+ case {range(Range_1), range(Range_2)} of
+ {{N,N},{ N,N}} ->
+ False_range_1 = none_range(),
+ False_range_2 = none_range();
+ {{N1,N1}, {N2,N2}} ->
+ False_range_1 = Range_1,
+ False_range_2 = Range_2;
+ {{N,N}, _} ->
+ False_range_1 = Range_1,
+ {_,False_range_2} = compare_with_integer(N, Range_2);
+ {_, {N,N}} ->
+ False_range_2 = Range_2,
+ {_,False_range_1} = compare_with_integer(N, Range_1);
+ {_, _} ->
+ False_range_1 = Range_1,
+ False_range_2 = Range_2
+ end,
+ {True_range, True_range, False_range_1, False_range_2}.
+
+-spec range_inequality_propagation(#range{}, #range{}) ->
+ {#range{}, #range{}, #range{}, #range{}}.
+
+%% Range1 < Range2
+range_inequality_propagation(Range1, Range2) ->
+ R1_other = other(Range1),
+ R2_other = other(Range2),
+ {R1_true_range, R1_false_range, R2_true_range, R2_false_range} =
+ case {range(Range1), range(Range2)} of
+ {{N1,N1}, {N2,N2}} ->
+ case inf_geq(N2,inf_add(N1,1)) of
+ true ->
+ {{N1,N1},empty,{N2,N2},empty};
+ false ->
+ {empty,{N1,N1},empty,{N2,N2}}
+ end;
+ {{N1,N1}, {Min2,Max2}} ->
+ case inf_geq(Min2,inf_add(N1,1)) of
+ true ->
+ {{N1,N1},empty,{inf_add(N1,1),Max2},empty};
+ false ->
+ case inf_geq(N1,Max2) of
+ true ->
+ {empty,{N1,N1},empty,{Min2,N1}};
+ false ->
+ {{N1,N1},{N1,N1},{inf_add(N1,1),Max2},{Min2,N1}}
+ end
+ end;
+ {{Min1,Max1}, {N2,N2}} ->
+ case inf_geq(N2,inf_add(Max1,1)) of
+ true ->
+ {{Min1,inf_add(N2,-1)},empty,{N2,N2},empty};
+ false ->
+ case inf_geq(Min1,N2) of
+ true ->
+ {empty,{N2,Max1},empty,{N2,N2}};
+ false ->
+ {{Min1,inf_add(N2,-1)},{N2,Max1},{N2,N2},{N2,N2}}
+ end
+ end;
+ {empty, {Min2,Max2}} ->
+ {empty,empty,{Min2,Max2},{Min2,Max2}};
+ {{Min1,Max1}, empty} ->
+ {{Min1,Max1},{Min1,Max1},empty,empty};
+ {empty, empty} ->
+ {empty,empty,empty,empty};
+ {{Min1,Max1}, {Min2,Max2}} ->
+ {{Min1,inf_min([Max1,inf_add(Max2,-1)])},
+ {inf_max([Min1,Min2]),Max1},
+ {inf_max([inf_add(Min1,1),Min2]),Max2},
+ {Min2,inf_min([Max1,Max2])}}
+ end,
+ {range_init(R1_true_range, R1_other),
+ range_init(R2_true_range, R2_other),
+ range_init(R1_false_range, R1_other),
+ range_init(R2_false_range, R2_other)}.
+
+-spec analyse_type(#icode_type{}, info(), boolean()) ->
+ {#icode_goto{} | #icode_type{}, [{label(),info()}]}.
+
+analyse_type(Type, Info, Rewrite) ->
+ TypeTest = hipe_icode:type_test(Type),
+ [Arg|_] = hipe_icode:type_args(Type),
+ OldVarRange = get_range_from_arg(Arg),
+ case TypeTest of
+ {integer, N} ->
+ {TrueRange,FalseRange} = compare_with_integer(N,OldVarRange);
+ integer ->
+ TrueRange = inf(any_range(), OldVarRange),
+ FalseRange = inf(none_range(), OldVarRange);
+ _ ->
+ TrueRange = inf(none_range(),OldVarRange),
+ FalseRange = OldVarRange
+ end,
+ TrueLabel = hipe_icode:type_true_label(Type),
+ FalseLabel = hipe_icode:type_false_label(Type),
+ TrueInfo =
+ enter_define({Arg,TrueRange},Info),
+ FalseInfo =
+ enter_define({Arg,FalseRange},Info),
+ True =
+ case range__is_none(TrueRange) of
+ true -> [];
+ false -> [{TrueLabel,TrueInfo}]
+ end,
+ False =
+ case range__is_none(FalseRange) of
+ true -> [];
+ false -> [{FalseLabel,FalseInfo}]
+ end,
+ UpdateInfo = True++False,
+ NewType =
+ if Rewrite ->
+ case UpdateInfo of
+ [] -> %% This is weird
+ Type;
+ [{Label,_Info}] ->
+ hipe_icode:mk_goto(Label);
+ [_,_] ->
+ Type
+ end;
+ true ->
+ Type
+ end,
+ {NewType,True ++ False}.
+
+-spec compare_with_integer(integer(), #range{}) -> {#range{}, #range{}}.
+
+compare_with_integer(N, OldVarRange) ->
+ TestRange = range_init({N, N}, false),
+ TrueRange = inf(TestRange, OldVarRange),
+ %% False range
+ TempFalseRange = range__remove_constant(OldVarRange, TestRange),
+ BetterRange =
+ case range(TempFalseRange) of
+ {Min, Max} = MM ->
+ New_small = inf_geq(Min, N),
+ New_large = inf_geq(N, Max),
+ if New_small and not New_large ->
+ {N + 1, Max};
+ New_large and not New_small ->
+ {Min, N - 1};
+ true ->
+ MM
+ end;
+ Not_tuple ->
+ Not_tuple
+ end,
+ FalseRange = range_init(BetterRange, other(TempFalseRange)),
+ {TrueRange, FalseRange}.
+
+%%== Ranges ==================================================================
+
+-spec pp_ann(#ann{} | erl_types:erl_type()) -> [string()].
+
+pp_ann(#ann{range=#range{range=R, other=false}}) ->
+ pp_range(R);
+pp_ann(#ann{range=#range{range=empty, other=true}, type=Type}) ->
+ t_to_string(Type);
+pp_ann(#ann{range=#range{range=R, other=true}, type=Type}) ->
+ pp_range(R) ++ " | " ++ t_to_string(Type);
+pp_ann(Type) ->
+ t_to_string(Type).
+
+-spec pp_range(range_rep()) -> nonempty_string().
+
+pp_range(empty) ->
+ "none";
+pp_range({Min, Max}) ->
+ val_to_string(Min) ++ ".." ++ val_to_string(Max).
+
+-spec val_to_string('pos_inf' | 'neg_inf' | integer()) -> string().
+
+val_to_string(pos_inf) -> "inf";
+val_to_string(neg_inf) -> "-inf";
+val_to_string(X) when is_integer(X) -> integer_to_list(X).
+
+-spec range_from_type(erl_types:erl_type()) -> [#range{}].
+
+range_from_type(Type) ->
+ [range_from_simple_type(T) || T <- t_to_tlist(Type)].
+
+-spec range_from_simple_type(erl_types:erl_type()) -> #range{}.
+
+range_from_simple_type(Type) ->
+ None = t_none(),
+ case t_inf(t_integer(), Type) of
+ None ->
+ #range{range = empty, other = true};
+ Type ->
+ Range = {number_min(Type), number_max(Type)},
+ #range{range = Range, other = false};
+ NewType ->
+ Range = {number_min(NewType), number_max(NewType)},
+ #range{range = Range, other = true}
+ end.
+
+-spec range_init(range_rep(), boolean()) -> #range{}.
+
+range_init({Min, Max} = Range, Other) ->
+ case inf_geq(Max, Min) of
+ true ->
+ #range{range = Range, other = Other};
+ false ->
+ #range{range = empty, other = Other}
+ end;
+range_init(empty, Other) ->
+ #range{range = empty, other = Other}.
+
+-spec range(#range{}) -> range_rep().
+
+range(#range{range = R}) -> R.
+
+-spec other(#range{}) -> boolean().
+
+other(#range{other = O}) -> O.
+
+-spec set_other(#range{}, boolean()) -> #range{}.
+
+set_other(R, O) -> R#range{other = O}.
+
+-spec range__min(#range{}) -> 'empty' | 'neg_inf' | integer().
+
+range__min(#range{range=empty}) -> empty;
+range__min(#range{range={Min,_}}) -> Min.
+
+-spec range__max(#range{}) -> 'empty' | 'pos_inf' | integer().
+
+range__max(#range{range=empty}) -> empty;
+range__max(#range{range={_,Max}}) -> Max.
+
+-spec range__is_none(#range{}) -> boolean().
+
+range__is_none(#range{range=empty, other=false}) -> true;
+range__is_none(#range{}) -> false.
+
+-spec range__is_empty(#range{}) -> boolean().
+
+range__is_empty(#range{range=empty}) -> true;
+range__is_empty(#range{range={_,_}}) -> false.
+
+-spec remove_point_types(#range{}, [#range{}]) -> #range{}.
+
+remove_point_types(Range, Ranges) ->
+ Sorted = lists:sort(Ranges),
+ FoldFun = fun (R, Acc) -> range__remove_constant(Acc,R) end,
+ Range1 = lists:foldl(FoldFun, Range, Sorted),
+ lists:foldl(FoldFun, Range1, lists:reverse(Sorted)).
+
+-spec range__remove_constant(#range{}, #range{}) -> #range{}.
+
+range__remove_constant(R = #range{range={C,C}}, #range{range={C,C}}) ->
+ R#range{range=empty};
+range__remove_constant(R = #range{range={C,H}}, #range{range={C,C}}) ->
+ R#range{range={C+1,H}};
+range__remove_constant(R = #range{range={L,C}}, #range{range={C,C}}) ->
+ R#range{range={L,C-1}};
+range__remove_constant(R = #range{}, #range{range={C,C}}) ->
+ R;
+range__remove_constant(R = #range{}, _) ->
+ R.
+
+-spec any_type() -> #range{}.
+
+any_type() ->
+ #range{range=any_r(), other=true}.
+
+-spec any_range() -> #range{}.
+
+any_range() ->
+ #range{range=any_r(), other=false}.
+
+-spec none_range() -> #range{}.
+
+none_range() ->
+ #range{range=empty, other=true}.
+
+-spec none_type() -> #range{}.
+
+none_type() ->
+ #range{range = empty, other = false}.
+
+-spec any_r() -> {'neg_inf','pos_inf'}.
+
+any_r() -> {neg_inf, pos_inf}.
+
+-spec get_range_from_args([argument()]) -> [#range{}].
+
+get_range_from_args(Args) ->
+ [get_range_from_arg(Arg) || Arg <- Args].
+
+-spec get_range_from_arg(argument()) -> #range{}.
+
+get_range_from_arg(Arg) ->
+ case hipe_icode:is_const(Arg) of
+ true ->
+ Value = hipe_icode:const_value(Arg),
+ case is_integer(Value) of
+ true ->
+ #range{range={Value,Value}, other=false};
+ false ->
+ #range{range=empty, other=true}
+ end;
+ false ->
+ case hipe_icode:is_annotated_variable(Arg) of
+ true ->
+ case hipe_icode:variable_annotation(Arg) of
+ {range_anno, #ann{range=Range}, _} ->
+ Range;
+ {type_anno, Type, _} ->
+ range_from_simple_type(Type)
+ end;
+ false ->
+ any_type()
+ end
+ end.
+
+%% inf([R]) ->
+%% R;
+%% inf([R1,R2|Rest]) ->
+%% inf([inf(R1,R2)|Rest]).
+
+-spec inf(#range{}, #range{}) -> #range{}.
+
+inf(#range{range=R1, other=O1}, #range{range=R2, other=O2}) ->
+ #range{range=range_inf(R1,R2), other=other_inf(O1,O2)}.
+
+-spec range_inf(range_rep(), range_rep()) -> range_rep().
+
+range_inf(empty, _) -> empty;
+range_inf(_, empty) -> empty;
+range_inf({Min1,Max1}, {Min2,Max2}) ->
+ NewMin = inf_max([Min1,Min2]),
+ NewMax = inf_min([Max1,Max2]),
+ case inf_geq(NewMax, NewMin) of
+ true ->
+ {NewMin, NewMax};
+ false ->
+ empty
+ end.
+
+-spec other_inf(boolean(), boolean()) -> boolean().
+
+other_inf(O1, O2) -> O1 and O2.
+
+-spec sup([#range{},...]) -> #range{}.
+
+sup([R]) ->
+ R;
+sup([R1,R2|Rest]) ->
+ sup([sup(R1, R2)|Rest]).
+
+-spec sup(#range{}, #range{}) -> #range{}.
+
+sup(#range{range=R1,other=O1}, #range{range=R2,other=O2}) ->
+ #range{range=range_sup(R1,R2), other=other_sup(O1,O2)}.
+
+-spec range_sup(range_rep(), range_rep()) -> range_rep().
+
+range_sup(empty, R) -> R;
+range_sup(R, empty) -> R;
+range_sup({Min1,Max1}, {Min2,Max2}) ->
+ NewMin = inf_min([Min1,Min2]),
+ NewMax = inf_max([Max1,Max2]),
+ {NewMin,NewMax}.
+
+-spec other_sup(boolean(), boolean()) -> boolean().
+
+other_sup(O1, O2) -> O1 or O2.
+
+%%== Call Support =============================================================
+
+-spec analyse_call_or_enter_fun(fun_name(), [argument()],
+ icode_call_type(), call_fun()) -> [#range{}].
+
+analyse_call_or_enter_fun(Fun, Args, CallType, LookupFun) ->
+ %%io:format("Fun: ~p~n Args: ~p~n CT: ~p~n LF: ~p~n", [Fun, Args, CallType, LookupFun]),
+ case basic_type(Fun) of
+ {bin, Operation} ->
+ [Arg_range1,Arg_range2] = get_range_from_args(Args),
+ A1_is_empty = range__is_empty(Arg_range1),
+ A2_is_empty = range__is_empty(Arg_range2),
+ case A1_is_empty orelse A2_is_empty of
+ true ->
+ [none_type()];
+ false ->
+ [Operation(Arg_range1, Arg_range2)]
+ end;
+ {unary, Operation} ->
+ [Arg_range] = get_range_from_args(Args),
+ case range__is_empty(Arg_range) of
+ true ->
+ [none_type()];
+ false ->
+ [Operation(Arg_range)]
+ end;
+ {fcall, MFA} ->
+ case CallType of
+ local ->
+ Range = LookupFun(MFA, get_range_from_args(Args)),
+ case range__is_none(Range) of
+ true ->
+ throw(none_range);
+ false ->
+ [Range]
+ end;
+ remote ->
+ [any_type()]
+ end;
+ not_int ->
+ [any_type()];
+ not_analysed ->
+ [any_type()];
+ {hipe_bs_primop, {bs_get_integer, Size, Flags}} ->
+ {Min, Max} = analyse_bs_get_integer(Size, Flags, length(Args) =:= 1),
+ [#range{range={Min, Max}, other=false}, any_type()];
+ {hipe_bs_primop, _} = Primop ->
+ Type = hipe_icode_primops:type(Primop),
+ range_from_type(Type)
+ end.
+
+-type bin_operation() :: fun((#range{},#range{}) -> #range{}).
+-type unary_operation() :: fun((#range{}) -> #range{}).
+
+-spec basic_type(fun_name()) -> 'not_int' | 'not_analysed'
+ | {bin, bin_operation()}
+ | {unary, unary_operation()}
+ | {fcall, mfa()} | {hipe_bs_primop, _}.
+
+%% Arithmetic operations
+basic_type('+') -> {bin, fun(R1, R2) -> range_add(R1, R2) end};
+basic_type('-') -> {bin, fun(R1, R2) -> range_sub(R1, R2) end};
+basic_type('*') -> {bin, fun(R1, R2) -> range_mult(R1, R2) end};
+basic_type('/') -> not_int;
+basic_type('div') -> {bin, fun(R1, R2) -> range_div(R1, R2) end};
+basic_type('rem') -> {bin, fun(R1, R2) -> range_rem(R1, R2) end};
+basic_type('bor') -> {bin, fun(R1, R2) -> range_bor(R1, R2) end};
+basic_type('band') -> {bin, fun(R1, R2) -> range_band(R1, R2) end};
+basic_type('bxor') -> {bin, fun(R1, R2) -> range_bxor(R1, R2) end};
+basic_type('bnot') -> {unary, fun(R1) -> range_bnot(R1) end};
+basic_type('bsl') -> {bin, fun(R1, R2) -> range_bsl(R1, R2) end};
+basic_type('bsr') -> {bin, fun(R1, R2) -> range_bsr(R1, R2) end};
+%% unsafe_*
+basic_type('unsafe_bor') ->
+ {bin, fun(R1, R2) -> range_bor(R1, R2) end};
+basic_type('unsafe_band') ->
+ {bin, fun(R1, R2) -> range_band(R1, R2) end};
+basic_type('unsafe_bxor') ->
+ {bin, fun(R1, R2) -> range_bxor(R1, R2) end};
+basic_type('unsafe_bnot') ->
+ {unary, fun(R1) -> range_bnot(R1) end};
+basic_type('unsafe_bsl') ->
+ {bin, fun(R1, R2) -> range_bsl(R1, R2) end};
+basic_type('unsafe_bsr') ->
+ {bin, fun(R1, R2) -> range_bsr(R1, R2) end};
+basic_type('unsafe_add') ->
+ {bin, fun(R1, R2) -> range_add(R1, R2) end};
+basic_type('unsafe_sub') ->
+ {bin, fun(R1, R2) -> range_sub(R1, R2) end};
+basic_type('extra_unsafe_add') ->
+ {bin, fun(R1, R2) -> range_add(R1, R2) end};
+basic_type('extra_unsafe_sub') ->
+ {bin, fun(R1, R2) -> range_sub(R1, R2) end};
+%% Binaries
+basic_type({hipe_bs_primop, _} = Primop) -> Primop;
+%% Unknown, other
+basic_type(call_fun) -> not_analysed;
+basic_type(clear_timeout) -> not_analysed;
+basic_type(redtest) -> not_analysed;
+basic_type(set_timeout) -> not_analysed;
+basic_type(#apply_N{}) -> not_analysed;
+basic_type(#closure_element{}) -> not_analysed;
+basic_type(#gc_test{}) -> not_analysed;
+%% Message handling
+basic_type(check_get_msg) -> not_analysed;
+basic_type(next_msg) -> not_analysed;
+basic_type(select_msg) -> not_analysed;
+basic_type(suspend_msg) -> not_analysed;
+%% Functions
+basic_type(enter_fun) -> not_analysed;
+basic_type(#mkfun{}) -> not_int;
+basic_type({_M,_F,_A} = MFA) -> {fcall, MFA};
+%% Floats
+basic_type(conv_to_float) -> not_int;
+basic_type(fclearerror) -> not_analysed;
+basic_type(fcheckerror) -> not_analysed;
+basic_type(fnegate) -> not_int;
+basic_type(fp_add) -> not_int;
+basic_type(fp_div) -> not_int;
+basic_type(fp_mul) -> not_int;
+basic_type(fp_sub) -> not_int;
+basic_type(unsafe_tag_float) -> not_int;
+basic_type(unsafe_untag_float) -> not_int;
+%% Lists, tuples, records
+basic_type(cons) -> not_int;
+basic_type(mktuple) -> not_int;
+basic_type(unsafe_hd) -> not_analysed;
+basic_type(unsafe_tl) -> not_int;
+basic_type(#element{}) -> not_analysed;
+basic_type(#unsafe_element{}) -> not_analysed;
+basic_type(#unsafe_update_element{}) -> not_analysed.
+
+-spec analyse_bs_get_integer(integer(), integer(), boolean()) -> range_tuple().
+
+analyse_bs_get_integer(Size, Flags, true) ->
+ Signed = Flags band 4,
+ if Signed =:= 0 ->
+ Max = 1 bsl Size - 1,
+ Min = 0;
+ true ->
+ Max = 1 bsl (Size-1) - 1,
+ Min = -(1 bsl (Size-1))
+ end,
+ {Min, Max};
+analyse_bs_get_integer(Size, Flags, false) when is_integer(Size),
+ is_integer(Flags) ->
+ any_r().
+
+%%---------------------------------------------------------------------------
+%% Range operations
+%%---------------------------------------------------------------------------
+
+%% Arithmetic
+
+-spec range_add(#range{}, #range{}) -> #range{}.
+
+range_add(Range1, Range2) ->
+ NewMin = inf_add(range__min(Range1), range__min(Range2)),
+ NewMax = inf_add(range__max(Range1), range__max(Range2)),
+ Other = other(Range1) orelse other(Range2),
+ range_init({NewMin, NewMax}, Other).
+
+-spec range_sub(#range{}, #range{}) -> #range{}.
+
+range_sub(Range1, Range2) ->
+ Min_sub = inf_min([inf_inv(range__max(Range2)),
+ inf_inv(range__min(Range2))]),
+ Max_sub = inf_max([inf_inv(range__max(Range2)),
+ inf_inv(range__min(Range2))]),
+ NewMin = inf_add(range__min(Range1), Min_sub),
+ NewMax = inf_add(range__max(Range1), Max_sub),
+ Other = other(Range1) orelse other(Range2),
+ range_init({NewMin, NewMax}, Other).
+
+-spec range_mult(#range{}, #range{}) -> #range{}.
+
+range_mult(#range{range=empty, other=true}, _Range2) ->
+ range_init(empty, true);
+range_mult(_Range1, #range{range=empty, other=true}) ->
+ range_init(empty, true);
+range_mult(Range1, Range2) ->
+ Min1 = range__min(Range1),
+ Min2 = range__min(Range2),
+ Max1 = range__max(Range1),
+ Max2 = range__max(Range2),
+ GreaterMin1 = inf_greater_zero(Min1),
+ GreaterMin2 = inf_greater_zero(Min2),
+ GreaterMax1 = inf_greater_zero(Max1),
+ GreaterMax2 = inf_greater_zero(Max2),
+ Range =
+ if GreaterMin1 ->
+ if GreaterMin2 -> {inf_mult(Min1, Min2), inf_mult(Max1, Max2)};
+ GreaterMax2 -> {inf_mult(Min2, Max1), inf_mult(Max2, Max1)};
+ true -> {inf_mult(Min2, Max1), inf_mult(Max2, Min1)}
+ end;
+ %% Column 1 or 2
+ GreaterMin2 -> % Column 1 or 2 row 3
+ range(range_mult(Range2, Range1));
+ GreaterMax1 -> % Column 2 Row 1 or 2
+ if GreaterMax2 -> % Column 2 Row 2
+ NewMin = inf_min([inf_mult(Min2, Max1), inf_mult(Max2, Min1)]),
+ NewMax = inf_max([inf_mult(Min2, Min1), inf_mult(Max2, Max1)]),
+ {NewMin, NewMax};
+ true -> % Column 2 Row 1
+ {inf_mult(Min2, Max1), inf_mult(Min2, Min1)}
+ end;
+ GreaterMax2 -> % Column 1 Row 2
+ range(range_mult(Range2, Range1));
+ true -> % Column 1 Row 1
+ {inf_mult(Max1, Max2), inf_mult(Min2, Min1)}
+ end,
+ Other = other(Range1) orelse other(Range2),
+ range_init(Range, Other).
+
+-spec extreme_divisors(#range{}) -> range_tuple().
+
+extreme_divisors(#range{range={0,0}}) -> {0,0};
+extreme_divisors(#range{range={0,Max}}) -> {1,Max};
+extreme_divisors(#range{range={Min,0}}) -> {Min,-1};
+extreme_divisors(#range{range={Min,Max}}) ->
+ case inf_geq(Min, 0) of
+ true -> {Min, Max};
+ false -> % Min < 0
+ case inf_geq(0, Max) of
+ true -> {Min,Max}; % Max < 0
+ false -> {-1,1} % Max > 0
+ end
+ end.
+
+-spec range_div(#range{}, #range{}) -> #range{}.
+
+%% this is div, not /.
+range_div(_, #range{range={0,0}}) ->
+ range_init(empty, false);
+range_div(#range{range=empty}, _) ->
+ range_init(empty, false);
+range_div(_, #range{range=empty}) ->
+ range_init(empty, false);
+range_div(Range1, Den) ->
+ Min1 = range__min(Range1),
+ Max1 = range__max(Range1),
+ {Min2, Max2} = extreme_divisors(Den),
+ Min_max_list = [inf_div(Min1, Min2), inf_div(Min1, Max2),
+ inf_div(Max1, Min2), inf_div(Max1, Max2)],
+ range_init({inf_min(Min_max_list), inf_max(Min_max_list)}, false).
+
+-spec range_rem(#range{}, #range{}) -> #range{}.
+
+range_rem(Range1, Range2) ->
+ %% Range1 desides the sign of the answer.
+ Min1 = range__min(Range1),
+ Max1 = range__max(Range1),
+ Min2 = range__min(Range2),
+ Max2 = range__max(Range2),
+ Min1_geq_zero = inf_geq(Min1, 0),
+ Max1_leq_zero = inf_geq(0, Max1),
+ Max_range2 = inf_max([inf_abs(Min2), inf_abs(Max2)]),
+ Max_range2_leq_zero = inf_geq(0, Max_range2),
+ New_min =
+ if Min1_geq_zero -> 0;
+ Max_range2_leq_zero -> Max_range2;
+ true -> inf_inv(Max_range2)
+ end,
+ New_max =
+ if Max1_leq_zero -> 0;
+ Max_range2_leq_zero -> inf_inv(Max_range2);
+ true -> Max_range2
+ end,
+ range_init({New_min, New_max}, false).
+
+%%--- Bit operations ----------------------------
+
+-spec range_bsr(#range{}, #range{}) -> #range{}.
+
+range_bsr(Range1, Range2=#range{range={Min, Max}}) ->
+ New_Range2 = range_init({inf_inv(Max), inf_inv(Min)}, other(Range2)),
+ Ans = range_bsl(Range1, New_Range2),
+ %% io:format("bsr res:~w~nInput:= ~w~n", [Ans, {Range1,Range2}]),
+ Ans.
+
+-spec range_bsl(#range{}, #range{}) -> #range{}.
+
+range_bsl(Range1, Range2) ->
+ Min1 = range__min(Range1),
+ Min2 = range__min(Range2),
+ Max1 = range__max(Range1),
+ Max2 = range__max(Range2),
+ Min1Geq0 = inf_geq(Min1, 0),
+ Max1Less0 = not inf_geq(Max1, 0),
+ MinMax =
+ if Min1Geq0 ->
+ {inf_bsl(Min1, Min2), inf_bsl(Max1, Max2)};
+ true ->
+ if Max1Less0 -> {inf_bsl(Min1, Max2), inf_bsl(Max1, Min2)};
+ true -> {inf_bsl(Min1, Max2), inf_bsl(Max1, Max2)}
+ end
+ end,
+ range_init(MinMax, false).
+
+-spec range_bnot(#range{}) -> #range{}.
+
+range_bnot(Range) ->
+ Minus_one = range_init({-1,-1}, false),
+ range_add(range_mult(Range, Minus_one), Minus_one).
+
+-spec width(range_rep() | integer()) -> 'pos_inf' | non_neg_integer().
+
+width({Min, Max}) -> inf_max([width(Min), width(Max)]);
+width(pos_inf) -> pos_inf;
+width(neg_inf) -> pos_inf;
+width(X) when is_integer(X), X >= 0 -> poswidth(X, 0);
+width(X) when is_integer(X), X < 0 -> negwidth(X, 0).
+
+-spec poswidth(non_neg_integer(), non_neg_integer()) -> non_neg_integer().
+
+poswidth(X, N) ->
+ case X < (1 bsl N) of
+ true -> N;
+ false -> poswidth(X, N+1)
+ end.
+
+-spec negwidth(neg_integer(), non_neg_integer()) -> non_neg_integer().
+
+negwidth(X, N) ->
+ case X > (-1 bsl N) of
+ true -> N;
+ false -> negwidth(X, N+1)
+ end.
+
+-spec range_band(#range{}, #range{}) -> #range{}.
+
+range_band(R1, R2) ->
+ {_Min1, Max1} = MM1 = range(R1),
+ {_Min2, Max2} = MM2 = range(R2),
+ Width1 = width(MM1),
+ Width2 = width(MM2),
+ Range =
+ case {classify_range(R1), classify_range(R2)} of
+ {minus_minus, minus_minus} ->
+ Width = inf_max([Width1, Width2]),
+ {inf_bsl(-1, Width), -1};
+ {minus_minus, minus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {inf_bsl(-1, Width), Max2};
+ {minus_minus, plus_plus} ->
+ {0, Max2};
+ {minus_plus, minus_minus} ->
+ Width = inf_max([Width1, Width2]),
+ {inf_bsl(-1, Width), Max1};
+ {minus_plus, minus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {inf_bsl(-1, Width), inf_max([Max1, Max2])};
+ {minus_plus, plus_plus} ->
+ {0, Max2};
+ {plus_plus, minus_minus} ->
+ {0, Max1};
+ {plus_plus, minus_plus} ->
+ {0, Max1};
+ {plus_plus, plus_plus} ->
+ {0, inf_min([Max1, Max2])}
+ end,
+ range_init(Range, false).
+
+-spec range_bor(#range{}, #range{}) -> #range{}.
+
+range_bor(R1, R2) ->
+ {Min1, _Max1} = MM1 = range(R1),
+ {Min2, _Max2} = MM2 = range(R2),
+ Width1 = width(MM1),
+ Width2 = width(MM2),
+ Range =
+ case {classify_range(R1), classify_range(R2)} of
+ {minus_minus, minus_minus} ->
+ {inf_max([Min1, Min2]), -1};
+ {minus_minus, minus_plus} ->
+ {Min1, -1};
+ {minus_minus, plus_plus} ->
+ {Min1, -1};
+ {minus_plus, minus_minus} ->
+ {Min2, -1};
+ {minus_plus, minus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {inf_min([Min1, Min2]), inf_add(-1, inf_bsl(1, Width))};
+ {minus_plus, plus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {Min1, inf_add(-1, inf_bsl(1, Width))};
+ {plus_plus, minus_minus} ->
+ {Min2, -1};
+ {plus_plus, minus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {Min2, inf_add(-1, inf_bsl(1, Width))};
+ {plus_plus, plus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {0, inf_add(-1, inf_bsl(1, Width))}
+ end,
+ range_init(Range, false).
+
+-spec classify_range(#range{}) -> 'minus_minus' | 'minus_plus' | 'plus_plus'.
+
+classify_range(Range) ->
+ case range(Range) of
+ {neg_inf, Number} when is_integer(Number), Number < 0 -> minus_minus;
+ {neg_inf, Number} when is_integer(Number), Number >= 0 -> minus_plus;
+ {Number, pos_inf} when is_integer(Number), Number < 0 -> minus_plus;
+ {Number, pos_inf} when is_integer(Number), Number >= 0 -> plus_plus;
+ {neg_inf, pos_inf} -> minus_plus;
+ {Number1,Number2} when is_integer(Number1), is_integer(Number2) ->
+ classify_int_range(Number1, Number2)
+ end.
+
+-spec classify_int_range(integer(), integer()) ->
+ 'minus_minus' | 'minus_plus' | 'plus_plus'.
+
+classify_int_range(Number1, _Number2) when Number1 >= 0 ->
+ plus_plus;
+classify_int_range(_Number1, Number2) when Number2 < 0 ->
+ minus_minus;
+classify_int_range(_Number1, _Number2) ->
+ minus_plus.
+
+-spec range_bxor(#range{}, #range{}) -> #range{}.
+
+range_bxor(R1, R2) ->
+ {Min1, Max1} = MM1 = range(R1),
+ {Min2, Max2} = MM2 = range(R2),
+ Width1 = width(MM1),
+ Width2 = width(MM2),
+ Range =
+ case {classify_range(R1), classify_range(R2)} of
+ {minus_minus, minus_minus} ->
+ Width = inf_max([Width1, Width2]),
+ {0, inf_add(-1, inf_bsl(1, Width))};
+ {minus_minus, minus_plus} ->
+ MinWidth = inf_max([Width1, width({0,Max2})]),
+ MaxWidth = inf_max([Width1, width({Min2,-1})]),
+ {inf_bsl(-1, MinWidth), inf_add(-1, inf_bsl(1, MaxWidth))};
+ {minus_minus, plus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {inf_bsl(-1, Width), -1};
+ {minus_plus, minus_minus} ->
+ MinWidth = inf_max([Width2,width({0,Max1})]),
+ MaxWidth = inf_max([Width2,width({Min1,-1})]),
+ {inf_bsl(-1, MinWidth), inf_add(-1, inf_bsl(1, MaxWidth))};
+ {minus_plus, minus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {inf_bsl(-1, Width), inf_add(-1, inf_bsl(1, Width))};
+ {minus_plus, plus_plus} ->
+ MinWidth = inf_max([Width2,width({Min1,-1})]),
+ MaxWidth = inf_max([Width2,width({0,Max1})]),
+ {inf_bsl(-1, MinWidth), inf_add(-1, inf_bsl(1, MaxWidth))};
+ {plus_plus, minus_minus} ->
+ Width = inf_max([Width1, Width2]),
+ {inf_bsl(-1, Width), -1};
+ {plus_plus, minus_plus} ->
+ MinWidth = inf_max([Width1,width({Min2,-1})]),
+ MaxWidth = inf_max([Width1,width({0,Max2})]),
+ {inf_bsl(-1, MinWidth), inf_add(-1, inf_bsl(1, MaxWidth))};
+ {plus_plus, plus_plus} ->
+ Width = inf_max([Width1, Width2]),
+ {0, inf_add(-1, inf_bsl(1, Width))}
+ end,
+ range_init(Range, false).
+
+%%---------------------------------------------------------------------------
+%% Inf operations
+%%---------------------------------------------------------------------------
+
+-spec inf_max([inf_integer(),...]) -> inf_integer().
+
+inf_max([H|T]) ->
+ lists:foldl(fun (Elem, Max) ->
+ case inf_geq(Elem, Max) of
+ false -> Max;
+ true -> Elem
+ end
+ end, H, T).
+
+-spec inf_min([inf_integer(),...]) -> inf_integer().
+
+inf_min([H|T]) ->
+ lists:foldl(fun (Elem, Min) ->
+ case inf_geq(Elem, Min) of
+ true -> Min;
+ false -> Elem
+ end
+ end, H, T).
+
+-spec inf_abs(inf_integer()) -> 'pos_inf' | integer().
+
+inf_abs(pos_inf) -> pos_inf;
+inf_abs(neg_inf) -> pos_inf;
+inf_abs(Number) when is_integer(Number), (Number < 0) -> - Number;
+inf_abs(Number) when is_integer(Number) -> Number.
+
+-spec inf_add(inf_integer(), inf_integer()) -> inf_integer().
+
+inf_add(pos_inf, _Number) -> pos_inf;
+inf_add(neg_inf, _Number) -> neg_inf;
+inf_add(_Number, pos_inf) -> pos_inf;
+inf_add(_Number, neg_inf) -> neg_inf;
+inf_add(Number1, Number2) when is_integer(Number1), is_integer(Number2) ->
+ Number1 + Number2.
+
+-spec inf_inv(inf_integer()) -> inf_integer().
+
+inf_inv(pos_inf) -> neg_inf;
+inf_inv(neg_inf) -> pos_inf;
+inf_inv(Number) -> -Number.
+
+-spec inf_geq(inf_integer(), inf_integer()) -> boolean().
+
+inf_geq(pos_inf, _) -> true;
+inf_geq(_, pos_inf) -> false;
+inf_geq(_, neg_inf) -> true;
+inf_geq(neg_inf, _) -> false;
+inf_geq(A, B) -> A >= B.
+
+-spec inf_greater_zero(inf_integer()) -> boolean().
+
+inf_greater_zero(pos_inf) -> true;
+inf_greater_zero(neg_inf) -> false;
+inf_greater_zero(Number) when is_integer(Number), Number >= 0 -> true;
+inf_greater_zero(Number) when is_integer(Number), Number < 0 -> false.
+
+-spec inf_div(inf_integer(), inf_integer()) -> inf_integer().
+
+inf_div(Number, 0) ->
+ Greater = inf_greater_zero(Number),
+ if Greater -> pos_inf;
+ true -> neg_inf
+ end;
+inf_div(pos_inf, Number) ->
+ Greater = inf_greater_zero(Number),
+ if Greater -> pos_inf;
+ true -> neg_inf
+ end;
+inf_div(neg_inf, Number) ->
+ Greater = inf_greater_zero(Number),
+ if Greater -> neg_inf;
+ true -> pos_inf
+ end;
+inf_div(Number, pos_inf) ->
+ Greater = inf_greater_zero(Number),
+ if Greater -> pos_inf;
+ true -> neg_inf
+ end;
+inf_div(Number, neg_inf) ->
+ Greater = inf_greater_zero(Number),
+ if Greater -> neg_inf;
+ true -> pos_inf
+ end;
+inf_div(Number1, Number2) -> Number1 div Number2.
+
+-spec inf_mult(inf_integer(), inf_integer()) -> inf_integer().
+
+inf_mult(neg_inf, Number) ->
+ Greater = inf_greater_zero(Number),
+ if Greater -> neg_inf;
+ true -> pos_inf
+ end;
+inf_mult(pos_inf, Number) ->
+ Greater = inf_greater_zero(Number),
+ if Greater -> pos_inf;
+ true -> neg_inf
+ end;
+inf_mult(Number, pos_inf) -> inf_mult(pos_inf, Number);
+inf_mult(Number, neg_inf) -> inf_mult(neg_inf, Number);
+inf_mult(Number1, Number2) -> Number1 * Number2.
+
+-spec inf_bsl(inf_integer(), inf_integer()) -> inf_integer().
+
+inf_bsl(pos_inf, _) -> pos_inf;
+inf_bsl(neg_inf, _) -> neg_inf;
+inf_bsl(Number, pos_inf) when is_integer(Number), Number >= 0 -> pos_inf;
+inf_bsl(_, pos_inf) -> neg_inf;
+inf_bsl(Number, neg_inf) when is_integer(Number), Number >= 0 -> 0;
+inf_bsl(_Number, neg_inf) -> -1;
+inf_bsl(Number1, Number2) when is_integer(Number1), is_integer(Number2) ->
+ %% We can not shift left with a number which is not a fixnum. We
+ %% don't have enough memory.
+ Bits = ?BITS,
+ if Number2 > (Bits bsl 1) -> inf_bsl(Number1, pos_inf);
+ Number2 < (-Bits bsl 1) -> inf_bsl(Number1, neg_inf);
+ true -> Number1 bsl Number2
+ end.
+
+%% State
+
+-spec state__init(cfg(), data()) -> #state{}.
+
+state__init(Cfg, {MFA, ArgsFun, CallFun, FinalFun}) ->
+ Start = hipe_icode_cfg:start_label(Cfg),
+ Params = hipe_icode_cfg:params(Cfg),
+ Ranges = ArgsFun(MFA, Cfg),
+ %% io:format("MFA: ~w~nRanges: ~w~n", [MFA, Ranges]),
+ Liveness =
+ hipe_icode_ssa:ssa_liveness__analyze(hipe_icode_type:unannotate_cfg(Cfg)),
+ case lists:any(fun range__is_none/1, Ranges) of
+ true ->
+ FinalFun(MFA, [none_type()]),
+ throw(no_input);
+ false ->
+ NewParams = lists:zipwith(fun update_info/2, Params, Ranges),
+ NewCfg = hipe_icode_cfg:params_update(Cfg, NewParams),
+ Info = enter_defines(NewParams, gb_trees:empty()),
+ InfoMap = gb_trees:insert({Start, in}, Info, gb_trees:empty()),
+ #state{info_map=InfoMap, cfg=NewCfg, liveness=Liveness,
+ ret_type=none_type(),
+ lookup_fun=CallFun, result_action=FinalFun}
+ end.
+
+-spec state__cfg(#state{}) -> cfg().
+
+state__cfg(#state{cfg=Cfg}) ->
+ Cfg.
+
+-spec state__bb(#state{}, label()) -> bb().
+
+state__bb(#state{cfg=Cfg}, Label) ->
+ BB = hipe_icode_cfg:bb(Cfg, Label),
+ true = hipe_bb:is_bb(BB), % Just an assert
+ BB.
+
+-spec state__bb_add(#state{}, label(), bb()) -> #state{}.
+
+state__bb_add(S=#state{cfg=Cfg}, Label, BB) ->
+ NewCfg = hipe_icode_cfg:bb_add(Cfg, Label, BB),
+ S#state{cfg=NewCfg}.
+
+state__lookup_fun(#state{lookup_fun=LF}) -> LF.
+
+state__result_action(#state{result_action=RA}) -> RA.
+
+state__ret_type(#state{ret_type=RT}) -> RT.
+
+state__ret_type_update(#state{ret_type=RT} = State, NewType) ->
+ TotType = sup(RT, NewType),
+ State#state{ret_type=TotType}.
+
+state__info_in(S, Label) ->
+ state__info(S, {Label, in}).
+
+state__info(#state{info_map=IM}, Key) ->
+ gb_trees:get(Key, IM).
+
+state__update_info(State, LabelInfo, Rewrite) ->
+ update_info(LabelInfo, State, [], Rewrite).
+
+update_info([{Label,InfoIn}|Rest], State, LabelAcc, Rewrite) ->
+ case state__info_in_update(State, Label, InfoIn) of
+ fixpoint ->
+ if Rewrite ->
+ update_info(Rest, State, [Label|LabelAcc], Rewrite);
+ true ->
+ update_info(Rest, State, LabelAcc, Rewrite)
+ end;
+ NewState ->
+ update_info(Rest, NewState, [Label|LabelAcc], Rewrite)
+ end;
+update_info([], State, LabelAcc, _Rewrite) ->
+ {State, LabelAcc}.
+
+state__info_in_update(S=#state{info_map=IM,liveness=Liveness}, Label, Info) ->
+ LabelIn = {Label, in},
+ case gb_trees:lookup(LabelIn, IM) of
+ none ->
+ LiveIn = hipe_icode_ssa:ssa_liveness__livein(Liveness, Label),
+ NamesLiveIn = [hipe_icode:var_name(Var) || Var <- LiveIn,
+ hipe_icode:is_var(Var)],
+ OldInfo = gb_trees:empty(),
+ case join_info_in(NamesLiveIn, OldInfo, Info) of
+ fixpoint ->
+ S#state{info_map=gb_trees:insert(LabelIn, OldInfo, IM)};
+ NewInfo ->
+ S#state{info_map=gb_trees:enter(LabelIn, NewInfo, IM)}
+ end;
+ {value, OldInfo} ->
+ OldVars = gb_trees:keys(OldInfo),
+ case join_info_in(OldVars, OldInfo, Info) of
+ fixpoint ->
+ fixpoint;
+ NewInfo ->
+ S#state{info_map=gb_trees:update(LabelIn, NewInfo, IM)}
+ end
+ end.
+
+join_info_in(Vars, OldInfo, NewInfo) ->
+ case join_info_in(Vars, OldInfo, NewInfo, gb_trees:empty(), false) of
+ {Res, true} -> Res;
+ {_, false} -> fixpoint
+ end.
+
+join_info_in([Var|Left], Info1, Info2, Acc, Changed) ->
+ Type1 = gb_trees:lookup(Var, Info1),
+ Type2 = gb_trees:lookup(Var, Info2),
+ case {Type1, Type2} of
+ {none, none} ->
+ NewTree = gb_trees:insert(Var, none_type(), Acc),
+ join_info_in(Left, Info1, Info2, NewTree, true);
+ {none, {value, Val}} ->
+ NewTree = gb_trees:insert(Var, Val, Acc),
+ join_info_in(Left, Info1, Info2, NewTree, true);
+ {{value, Val}, none} ->
+ NewTree = gb_trees:insert(Var, Val, Acc),
+ join_info_in(Left, Info1, Info2, NewTree, Changed);
+ {{value, Val}, {value, Val}} ->
+ NewTree = gb_trees:insert(Var, Val, Acc),
+ join_info_in(Left, Info1, Info2, NewTree, Changed);
+ {{value, Val1}, {value, Val2}} ->
+ NewVal =
+ case sup(Val1, Val2) of
+ Val1 ->
+ NewChanged = Changed,
+ Val1;
+ Val ->
+ NewChanged = true,
+ Val
+ end,
+ NewTree = gb_trees:insert(Var, NewVal, Acc),
+ join_info_in(Left, Info1, Info2, NewTree, NewChanged)
+ end;
+join_info_in([], _Info1, _Info2, Acc, NewChanged) ->
+ {Acc, NewChanged}.
+
+enter_defines([Def|Rest], Info) ->
+ enter_defines(Rest, enter_define(Def, Info));
+enter_defines([], Info) -> Info.
+
+enter_define({PossibleVar, Range = #range{}}, Info) ->
+ case hipe_icode:is_var(PossibleVar) of
+ true ->
+ gb_trees:enter(hipe_icode:var_name(PossibleVar), Range, Info);
+ false ->
+ Info
+ end;
+enter_define(PossibleVar, Info) ->
+ case hipe_icode:is_var(PossibleVar) of
+ true ->
+ case hipe_icode:variable_annotation(PossibleVar) of
+ {range_anno, #ann{range=Range}, _} ->
+ gb_trees:enter(hipe_icode:var_name(PossibleVar), Range, Info);
+ _ ->
+ Info
+ end;
+ false ->
+ Info
+ end.
+
+enter_vals(Ins, Info) ->
+ NewInfo = enter_defines(hipe_icode:args(Ins), Info),
+ enter_defines(hipe_icode:defines(Ins), NewInfo).
+
+lookup(PossibleVar, Info) ->
+ case hipe_icode:is_var(PossibleVar) of
+ true ->
+ case gb_trees:lookup(hipe_icode:var_name(PossibleVar), Info) of
+ none ->
+ none_type();
+ {value, Val} ->
+ Val
+ end;
+ false ->
+ none_type()
+ end.
+
+%% _________________________________________________________________
+%%
+%% The worklist.
+%%
+
+init_work(State) ->
+ %% Labels = hipe_icode_cfg:reverse_postorder(state__cfg(State)),
+ Labels = [hipe_icode_cfg:start_label(state__cfg(State))],
+ {Labels, [], sets:from_list(Labels)}.
+
+get_work({[Label|Left], List, Set}) ->
+ NewWork = {Left, List, sets:del_element(Label, Set)},
+ {Label, NewWork};
+get_work({[], [], _Set}) ->
+ fixpoint;
+get_work({[], List, Set}) ->
+ get_work({lists:reverse(List), [], Set}).
+
+add_work(Work = {List1, List2, Set}, [Label|Left]) ->
+ case sets:is_element(Label, Set) of
+ true ->
+ add_work(Work, Left);
+ false ->
+ %% io:format("Adding work: ~w\n", [Label]),
+ add_work({List1, [Label|List2], sets:add_element(Label, Set)}, Left)
+ end;
+add_work(Work, []) ->
+ Work.
+
+convert_cfg_to_types(Cfg) ->
+ Lbls = hipe_icode_cfg:reverse_postorder(Cfg),
+ lists:foldl(fun convert_lbl_to_type/2, Cfg, Lbls).
+
+convert_lbl_to_type(Lbl, Cfg) ->
+ BB = hipe_icode_cfg:bb(Cfg, Lbl),
+ Code = hipe_bb:code(BB),
+ NewCode = [convert_instr_to_type(I) || I <- Code],
+ hipe_icode_cfg:bb_add(Cfg, Lbl, hipe_bb:mk_bb(NewCode)).
+
+convert_instr_to_type(I) ->
+ Uses = hipe_icode:uses(I),
+ UseSubstList = [{Use, convert_to_types(Use)} ||
+ Use <- Uses, hipe_icode:is_annotated_variable(Use)],
+ NewI = hipe_icode:subst_uses(UseSubstList, I),
+ Defs = hipe_icode:defines(NewI),
+ DefSubstList = [{Def, convert_to_types(Def)} ||
+ Def <- Defs, hipe_icode:is_annotated_variable(Def)],
+ hipe_icode:subst_defines(DefSubstList, NewI).
+
+convert_to_types(VarOrReg) ->
+ Annotation =
+ case hipe_icode:variable_annotation(VarOrReg) of
+ {range_anno, Ann, _} ->
+ {type_anno, convert_ann_to_types(Ann), fun erl_types:t_to_string/1};
+ {type_anno, _, _} = TypeAnn ->
+ TypeAnn
+ end,
+ hipe_icode:annotate_variable(VarOrReg, Annotation).
+
+convert_ann_to_types(#ann{range=#range{range={Min,Max}, other=false}}) ->
+ t_from_range_unsafe(Min, Max);
+convert_ann_to_types(#ann{range=#range{range=empty, other=false}}) ->
+ t_none();
+convert_ann_to_types(#ann{range=#range{other=true}, type=Type}) ->
+ Type.
+
+%%=====================================================================
+%% Icode Coordinator Callbacks
+%%=====================================================================
+
+-spec replace_nones([#range{}]) -> [#range{}].
+replace_nones(Args) ->
+ [replace_none(Arg) || Arg <- Args].
+
+replace_none(Arg) ->
+ case range__is_none(Arg) of
+ true -> any_type();
+ false -> Arg
+ end.
+
+-spec update__info([#range{}], [#range{}]) -> {boolean(), [#ann{}]}.
+update__info(NewRanges, OldRanges) ->
+ SupFun = fun (Ann, Range) ->
+ join_info(Ann, Range, fun safe_widen/3)
+ end,
+ EqFun = fun (X, Y) -> X =:= Y end,
+ ResRanges = lists:zipwith(SupFun, OldRanges, NewRanges),
+ Change = lists:zipwith(EqFun, ResRanges, OldRanges),
+ {lists:all(fun (X) -> X end, Change), ResRanges}.
+
+-spec new__info/1 :: ([#range{}]) -> [#ann{}].
+new__info(NewRanges) ->
+ [#ann{range=Range,count=1,type=t_any()} || Range <- NewRanges].
+
+-spec return__info/1 :: ([#ann{}]) -> [#range{}].
+return__info(Ranges) ->
+ [Range || #ann{range=Range} <- Ranges].
+
+-spec return_none/0 :: () -> [#range{},...].
+return_none() ->
+ [none_type()].
+
+-spec return_none_args/2 :: (#cfg{}, mfa()) -> [#range{}].
+return_none_args(Cfg, {_M,_F,A}) ->
+ NoArgs =
+ case hipe_icode_cfg:is_closure(Cfg) of
+ true -> hipe_icode_cfg:closure_arity(Cfg) + 1;
+ false -> A
+ end,
+ lists:duplicate(NoArgs, none_type()).
+
+-spec return_any_args/2 :: (#cfg{}, mfa()) -> [#range{}].
+return_any_args(Cfg, {_M,_F,A}) ->
+ NoArgs =
+ case hipe_icode_cfg:is_closure(Cfg) of
+ true -> hipe_icode_cfg:closure_arity(Cfg) + 1;
+ false -> A
+ end,
+ lists:duplicate(NoArgs, any_type()).
+
+%%=====================================================================
+
+next_up_limit(X) when is_integer(X), X < 0 -> 0;
+next_up_limit(X) when is_integer(X), X < 255 -> 255;
+next_up_limit(X) when is_integer(X), X < 16#10ffff -> 16#10ffff;
+next_up_limit(X) when is_integer(X), X < 16#7ffffff -> 16#7ffffff;
+next_up_limit(X) when is_integer(X), X < 16#7fffffff -> 16#7fffffff;
+next_up_limit(X) when is_integer(X), X < 16#ffffffff -> 16#ffffffff;
+next_up_limit(X) when is_integer(X), X < 16#fffffffffff -> 16#fffffffffff;
+next_up_limit(X) when is_integer(X), X < 16#7fffffffffffffff -> 16#7fffffffffffffff;
+next_up_limit(_X) -> pos_inf.
+
+next_down_limit(X) when is_integer(X), X > 0 -> 0;
+next_down_limit(X) when is_integer(X), X > -256 -> -256;
+next_down_limit(X) when is_integer(X), X > -16#10ffff -> -16#10ffff;
+next_down_limit(X) when is_integer(X), X > -16#8000000 -> -16#8000000;
+next_down_limit(X) when is_integer(X), X > -16#80000000 -> -16#80000000;
+next_down_limit(X) when is_integer(X), X > -16#800000000000000 -> -16#800000000000000;
+next_down_limit(_X) -> neg_inf.