diff options
Diffstat (limited to 'lib/hipe/icode/hipe_icode_range.erl')
| -rw-r--r-- | lib/hipe/icode/hipe_icode_range.erl | 1966 |
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. |