%% -*- erlang-indent-level: 2 -*-
%%
%% Licensed under the Apache License, Version 2.0 (the "License");
%% you may not use this file except in compliance with the License.
%% You may obtain a copy of the License at
%%
%% http://www.apache.org/licenses/LICENSE-2.0
%%
%% Unless required by applicable law or agreed to in writing, software
%% distributed under the License is distributed on an "AS IS" BASIS,
%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
%% See the License for the specific language governing permissions and
%% limitations under the License.
%%
%%%-------------------------------------------------------------------
%%% 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()}).
-type range() :: #range{}.
-record(ann, {range :: range(),
type :: erl_types:erl_type(),
count :: integer()}).
-type ann() :: #ann{}.
-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() :: map().
-type work_list() :: {[label()], [label()], set(label())}.
-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 = #{} :: info(),
cfg :: cfg(),
liveness :: hipe_icode_ssa:liveness(),
ret_type :: range(),
lookup_fun :: call_fun(),
result_action :: final_fun()}).
-type state() :: #state{}.
-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, set_from_list([Start])).
-spec rewrite_blocks([label()], state(), set(label())) -> state().
rewrite_blocks([Next|Rest], State, Visited) ->
Info = state__info_in(State, Next),
{NewState, NewLabels} = analyse_block(Next, Info, State, true),
RealNew = not_visited(NewLabels, Visited),
NewVisited = set_union(set_from_list(RealNew), Visited),
NewWork = 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) ->
Args = hipe_icode:args(Call),
Fun = hipe_icode:call_fun(Call),
Type = hipe_icode:call_type(Call),
%% This call has side-effects (it might call LookupFun which sends messages to
%% hipe_icode_coordinator to update the argument ranges of Fun), and must thus
%% not be moved into the case statement.
DstRanges = analyse_call_or_enter_fun(Fun, Args, Type, LookupFun),
case hipe_icode:call_dstlist(Call) of
[] ->
Call;
Dsts ->
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) ->
{TrueRange1, TrueRange2, FalseRange1, FalseRange2} =
case normalize_name(hipe_icode:if_op(If)) of
'>' ->
{TR2, TR1, FR2, FR1} = range_inequality_propagation(Range2, Range1),
{TR1, TR2, FR1, FR2};
'<' ->
range_inequality_propagation(Range1, Range2);
'>=' ->
{FR1, FR2, TR1, TR2} = range_inequality_propagation(Range1, Range2),
{TR1, TR2, FR1, FR2};
'=<' ->
{FR2, FR1, TR2, TR1} = range_inequality_propagation(Range2, Range1),
{TR1, TR2, FR1, FR2};
'=:=' ->
{TR1, TR2, FR1, FR2} = range_equality_propagation(Range1, Range2),
{TR1, TR2, FR1, FR2};
'=/=' ->
{FR1, FR2, TR1, TR2} = range_equality_propagation(Range1, Range2),
{TR1, TR2, FR1, FR2};
'==' ->
{TR1, TR2, FR1, FR2} = range_equality_propagation(Range1, Range2),
{set_other(TR1,other(Range1)), set_other(TR2,other(Range2)), FR1, FR2};
'/=' ->
{FR1, FR2, TR1, TR2} = range_equality_propagation(Range1, Range2),
{TR1, TR2, set_other(FR1,other(Range1)), set_other(FR2,other(Range2))}
end,
%% io:format("TR1 = ~w\nTR2 = ~w\n", [TrueRange1, TrueRange2]),
True =
case lists:all(fun range__is_none/1, [TrueRange1, TrueRange2]) of
true -> [];
false ->
TrueLabel = hipe_icode:if_true_label(If),
TrueArgRanges = [{Arg1, TrueRange1}, {Arg2, TrueRange2}],
TrueInfo = enter_defines(TrueArgRanges, Info),
[{TrueLabel, TrueInfo}]
end,
%% io:format("FR1 = ~w\nFR2 = ~w\n", [FalseRange1, FalseRange2]),
False =
case lists:all(fun range__is_none/1, [FalseRange1, FalseRange2]) of
true -> [];
false ->
FalseLabel = hipe_icode:if_false_label(If),
FalseArgRanges = [{Arg1, FalseRange1}, {Arg2, FalseRange2}],
FalseInfo = enter_defines(FalseArgRanges, Info),
[{FalseLabel, FalseInfo}]
end,
UpdateInfo = True ++ False,
NewIF =
if Rewrite ->
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(Range1, Range2) ->
TrueRange = inf(Range1, Range2),
{FalseRange1, FalseRange2} =
case {range(Range1), range(Range2)} of
{{N,N}, {N,N}} ->
{none_range(), none_range()};
{{N1,N1}, {N2,N2}} ->
{Range1, Range2};
{{N,N}, _} ->
{_,FR2} = compare_with_integer(N, Range2),
{Range1, FR2};
{_, {N,N}} ->
{_,FR1} = compare_with_integer(N, Range1),
{FR1, Range2};
{_, _} ->
{Range1, Range2}
end,
{TrueRange, TrueRange, FalseRange1, FalseRange2}.
-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),
{TrueRange, FalseRange} =
case TypeTest of
{integer, N} ->
compare_with_integer(N, OldVarRange);
integer ->
{inf(any_range(), OldVarRange), inf(none_range(), OldVarRange)};
number ->
{OldVarRange, OldVarRange};
_ ->
{inf(none_range(), OldVarRange), 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(#range{range = {C, C}} = R, #range{range = {C, C}}) ->
R#range{range = empty};
range__remove_constant(#range{range = {C, H}} = R, #range{range = {C, C}}) ->
R#range{range = {C+1, H}};
range__remove_constant(#range{range = {L, C}} = R, #range{range = {C, C}}) ->
R#range{range = {L, C-1}};
range__remove_constant(#range{} = R, #range{range = {C,C}}) ->
R;
range__remove_constant(#range{} = R, _) ->
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,
case Signed =:= 0 of
true ->
{0, inf_add(inf_bsl(1, Size), -1)}; % return {Min, Max}
false ->
{inf_inv(inf_bsl(1, Size-1)), inf_add(inf_bsl(1, Size-1), -1)}
end;
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)]),
New_min =
if Min1_geq_zero -> 0;
Max_range2 =:= 0 -> 0;
true -> inf_add(inf_inv(Max_range2), 1)
end,
New_max =
if Max1_leq_zero -> 0;
Max_range2 =:= 0 -> 0;
true -> inf_add(Max_range2, -1)
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() | inf_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, #{}),
InfoMap = #{{Start, in} => Info},
#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) ->
maps: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 IM of
#{LabelIn := OldInfo} ->
OldVars = maps:keys(OldInfo),
case join_info_in(OldVars, OldInfo, Info) of
fixpoint ->
fixpoint;
NewInfo ->
S#state{info_map=IM#{LabelIn := NewInfo}}
end;
_ ->
LiveIn = hipe_icode_ssa:ssa_liveness__livein(Liveness, Label),
NamesLiveIn = [hipe_icode:var_name(Var) || Var <- LiveIn,
hipe_icode:is_var(Var)],
OldInfo = #{},
case join_info_in(NamesLiveIn, OldInfo, Info) of
fixpoint ->
S#state{info_map=IM#{LabelIn => OldInfo}};
NewInfo ->
S#state{info_map=IM#{LabelIn => NewInfo}}
end
end.
join_info_in(Vars, OldInfo, NewInfo) ->
case join_info_in(Vars, OldInfo, NewInfo, #{}, false) of
{Res, true} -> Res;
{_, false} -> fixpoint
end.
join_info_in([Var|Left], Info1, Info2, Acc, Changed) ->
case {Info1, Info2} of
{#{Var := Val}, #{Var := Val}} ->
NewTree = Acc#{Var => Val},
join_info_in(Left, Info1, Info2, NewTree, Changed);
{#{Var := Val1}, #{Var := Val2}} ->
{NewChanged, NewVal} =
case sup(Val1, Val2) of
Val1 ->
{Changed, Val1};
Val ->
{true, Val}
end,
NewTree = Acc#{Var => NewVal},
join_info_in(Left, Info1, Info2, NewTree, NewChanged);
{_, #{Var := Val}} ->
NewTree = Acc#{Var => Val},
join_info_in(Left, Info1, Info2, NewTree, true);
{#{Var := Val}, _} ->
NewTree = Acc#{Var => Val},
join_info_in(Left, Info1, Info2, NewTree, Changed);
{_, _} ->
NewTree = Acc#{Var => none_type()},
join_info_in(Left, Info1, Info2, NewTree, true)
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 ->
Info#{hipe_icode:var_name(PossibleVar) => Range};
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}, _} ->
Info#{hipe_icode:var_name(PossibleVar) => Range};
_ ->
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 ->
PossibleVarName = hipe_icode:var_name(PossibleVar),
case Info of
#{PossibleVarName := Val} -> Val;
_ -> none_type()
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, [], set_from_list(Labels)}.
get_work({[Label|Left], List, Set}) ->
NewWork = {Left, List, maps:remove(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 Set of
#{Label := _} ->
add_work(Work, Left);
_ ->
%% io:format("Adding work: ~w\n", [Label]),
add_work({List1, [Label|List2], Set#{Label => []}}, 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([range()]) -> [ann()].
new__info(NewRanges) ->
[#ann{range=Range,count=1,type=t_any()} || Range <- NewRanges].
-spec return__info([ann()]) -> [range()].
return__info(Ranges) ->
[Range || #ann{range=Range} <- Ranges].
-spec return_none() -> [range(),...].
return_none() ->
[none_type()].
-spec return_none_args(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(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.
%%--------------------------------------------------------------------
%% Sets
-type set(E) :: #{E => []}.
set_from_list([]) -> #{};
set_from_list(L) ->
maps:from_list([{E, []} || E <- L]).
not_visited([], _) -> [];
not_visited([E|T], M) ->
case M of
#{E := []} -> not_visited(T, M);
_ -> [E|not_visited(T, M)]
end.
set_union(A, B) -> maps:merge(A, B).
