diff options
Diffstat (limited to 'lib/hipe/icode')
| -rw-r--r-- | lib/hipe/icode/hipe_icode.erl | 17 | ||||
| -rw-r--r-- | lib/hipe/icode/hipe_icode_bincomp.erl | 28 | ||||
| -rw-r--r-- | lib/hipe/icode/hipe_icode_coordinator.erl | 29 | ||||
| -rw-r--r-- | lib/hipe/icode/hipe_icode_range.erl | 133 | ||||
| -rw-r--r-- | lib/hipe/icode/hipe_icode_ssa.erl | 9 | ||||
| -rw-r--r-- | lib/hipe/icode/hipe_icode_ssa_const_prop.erl | 43 | ||||
| -rw-r--r-- | lib/hipe/icode/hipe_icode_type.erl | 2 |
7 files changed, 167 insertions, 94 deletions
diff --git a/lib/hipe/icode/hipe_icode.erl b/lib/hipe/icode/hipe_icode.erl index 78508dff22..d2d08e0253 100644 --- a/lib/hipe/icode/hipe_icode.erl +++ b/lib/hipe/icode/hipe_icode.erl @@ -438,6 +438,7 @@ if_true_label/1, if_false_label/1, if_args/1, + if_args_update/2, if_pred/1, %% is_if/1, @@ -594,6 +595,7 @@ uses/1, defines/1, is_safe/1, + reduce_unused/1, strip_comments/1, subst/2, subst_uses/2, @@ -713,6 +715,9 @@ if_op_update(IF, NewOp) -> IF#icode_if{op=NewOp}. -spec if_args(#icode_if{}) -> [icode_term_arg()]. if_args(#icode_if{args=Args}) -> Args. +-spec if_args_update(#icode_if{}, [icode_term_arg()]) -> #icode_if{}. +if_args_update(IF, Args) -> IF#icode_if{args=Args}. + -spec if_true_label(#icode_if{}) -> icode_lbl(). if_true_label(#icode_if{true_label=TrueLbl}) -> TrueLbl. @@ -1765,6 +1770,18 @@ is_safe(Instr) -> #icode_end_try{} -> false end. +%% @doc Produces a simplified instruction sequence that is equivalent to [Instr] +%% under the assumption that all results of Instr are unused, or 'false' if +%% there is no such sequence (other than [Instr] itself). + +-spec reduce_unused(icode_instr()) -> false | [icode_instr()]. + +reduce_unused(Instr) -> + case is_safe(Instr) of + true -> []; + false -> false + end. + %%----------------------------------------------------------------------- -spec highest_var(icode_instrs()) -> non_neg_integer(). diff --git a/lib/hipe/icode/hipe_icode_bincomp.erl b/lib/hipe/icode/hipe_icode_bincomp.erl index 5a27519141..5ee6fe2c87 100644 --- a/lib/hipe/icode/hipe_icode_bincomp.erl +++ b/lib/hipe/icode/hipe_icode_bincomp.erl @@ -40,8 +40,8 @@ -spec cfg(cfg()) -> cfg(). cfg(Cfg1) -> - StartLbls = ordsets:from_list([hipe_icode_cfg:start_label(Cfg1)]), - find_bs_get_integer(StartLbls, Cfg1, StartLbls). + StartLbl = hipe_icode_cfg:start_label(Cfg1), + find_bs_get_integer([StartLbl], Cfg1, set_from_list([StartLbl])). find_bs_get_integer([Lbl|Rest], Cfg, Visited) -> BB = hipe_icode_cfg:bb(Cfg, Lbl), @@ -55,10 +55,10 @@ find_bs_get_integer([Lbl|Rest], Cfg, Visited) -> not_ok -> Cfg end, - Succs = ordsets:from_list(hipe_icode_cfg:succ(NewCfg, Lbl)), - NewSuccs = ordsets:subtract(Succs, Visited), - NewLbls = ordsets:union(NewSuccs, Rest), - NewVisited = ordsets:union(NewSuccs, Visited), + Succs = hipe_icode_cfg:succ(NewCfg, Lbl), + NewSuccs = not_visited(Succs, Visited), + NewLbls = NewSuccs ++ Rest, + NewVisited = set_union(set_from_list(NewSuccs), Visited), find_bs_get_integer(NewLbls, NewCfg, NewVisited); find_bs_get_integer([], Cfg, _) -> Cfg. @@ -177,3 +177,19 @@ make_butlast([{Res, Size}|Rest], Var) -> [Var, hipe_icode:mk_const((1 bsl Size)-1)]), hipe_icode:mk_primop([NewVar], 'bsr', [Var, hipe_icode:mk_const(Size)]) |make_butlast(Rest, NewVar)]. + +%%-------------------------------------------------------------------- +%% Sets + +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). diff --git a/lib/hipe/icode/hipe_icode_coordinator.erl b/lib/hipe/icode/hipe_icode_coordinator.erl index d2f8748535..b073954ce7 100644 --- a/lib/hipe/icode/hipe_icode_coordinator.erl +++ b/lib/hipe/icode/hipe_icode_coordinator.erl @@ -106,12 +106,29 @@ handle_no_change_done(MFA, {Queue, Busy}) -> {Queue, Busy -- [MFA]}. last_action(PM, ServerPid, Mod, All) -> - lists:foreach(fun (MFA) -> - gb_trees:get(MFA, PM) ! {done, final_funs(ServerPid, Mod)}, - receive - {done_rewrite, MFA} -> ok - end - end, All). + last_action(PM, ServerPid, Mod, All, []). + +last_action(_, _, _, [], []) -> ok; +last_action(PM, ServerPid, Mod, [], [MFA|Busy]) -> + receive + {done_rewrite, MFA} -> + last_action(PM, ServerPid, Mod, [], Busy) + end; +last_action(PM, ServerPid, Mod, All0, Busy) -> + receive + {done_rewrite, MFA} -> + last_action(PM, ServerPid, Mod, All0, Busy -- [MFA]) + after 0 -> + case ?MAX_CONCURRENT - length(Busy) of + X when is_integer(X), X > 0 -> + [MFA|All1] = All0, + gb_trees:get(MFA, PM) ! {done, final_funs(ServerPid, Mod)}, + last_action(PM, ServerPid, Mod, All1, [MFA|Busy]); + X when is_integer(X) -> + Busy1 = receive {done_rewrite, MFA} -> Busy -- [MFA] end, + last_action(PM, ServerPid, Mod, All0, Busy1) + end + end. restart_funs({Queue, Busy} = QB, PM, All, ServerPid) -> case ?MAX_CONCURRENT - length(Busy) of diff --git a/lib/hipe/icode/hipe_icode_range.erl b/lib/hipe/icode/hipe_icode_range.erl index 12ed796690..af160769a1 100644 --- a/lib/hipe/icode/hipe_icode_range.erl +++ b/lib/hipe/icode/hipe_icode_range.erl @@ -73,8 +73,8 @@ -type final_fun() :: fun((mfa(), [range()]) -> 'ok'). -type data() :: {mfa(), args_fun(), call_fun(), final_fun()}. -type label() :: non_neg_integer(). --type info() :: gb_trees:tree(). --type work_list() :: {[label()], [label()], sets:set()}. +-type info() :: map(). +-type work_list() :: {[label()], [label()], set(label())}. -type variable() :: #icode_variable{}. -type annotated_variable() :: #icode_variable{}. -type argument() :: #icode_const{} | variable(). @@ -82,10 +82,9 @@ -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:dict(), - cfg :: cfg(), - liveness = gb_trees:empty() :: gb_trees:tree(), +-record(state, {info_map = #{} :: info(), + cfg :: cfg(), + liveness :: hipe_icode_ssa:liveness(), ret_type :: range(), lookup_fun :: call_fun(), result_action :: final_fun()}). @@ -187,17 +186,16 @@ safe_analyse(CFG, Data={MFA,_,_,_}) -> rewrite_blocks(State) -> CFG = state__cfg(State), Start = hipe_icode_cfg:start_label(CFG), - rewrite_blocks([Start], State, [Start]). + rewrite_blocks([Start], State, set_from_list([Start])). --spec rewrite_blocks([label()], state(), [label()]) -> state(). +-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), - NewLabelsSet = ordsets:from_list(NewLabels), - RealNew = ordsets:subtract(NewLabelsSet, Visited), - NewVisited = ordsets:union([RealNew, Visited, [Next]]), - NewWork = ordsets:union([RealNew, Rest]), + 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. @@ -1661,8 +1659,8 @@ state__init(Cfg, {MFA, ArgsFun, CallFun, FinalFun}) -> 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()), + 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} @@ -1700,7 +1698,7 @@ state__info_in(S, Label) -> state__info(S, {Label, in}). state__info(#state{info_map=IM}, Key) -> - gb_trees:get(Key, IM). + maps:get(Key, IM). state__update_info(State, LabelInfo, Rewrite) -> update_info(LabelInfo, State, [], Rewrite). @@ -1721,60 +1719,58 @@ update_info([], State, LabelAcc, _Rewrite) -> state__info_in_update(S=#state{info_map=IM,liveness=Liveness}, Label, Info) -> LabelIn = {Label, in}, - case gb_trees:lookup(LabelIn, IM) of - none -> + 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 = gb_trees:empty(), + OldInfo = #{}, 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; + S#state{info_map=IM#{LabelIn => OldInfo}}; NewInfo -> - S#state{info_map=gb_trees:update(LabelIn, NewInfo, IM)} + S#state{info_map=IM#{LabelIn => NewInfo}} end end. join_info_in(Vars, OldInfo, NewInfo) -> - case join_info_in(Vars, OldInfo, NewInfo, gb_trees:empty(), false) of + case join_info_in(Vars, OldInfo, NewInfo, #{}, 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), + case {Info1, Info2} of + {#{Var := Val}, #{Var := Val}} -> + NewTree = Acc#{Var => Val}, 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}} -> - {NewChanged, NewVal} = + {#{Var := Val1}, #{Var := Val2}} -> + {NewChanged, NewVal} = case sup(Val1, Val2) of Val1 -> {Changed, Val1}; Val -> {true, Val} end, - NewTree = gb_trees:insert(Var, NewVal, Acc), - join_info_in(Left, Info1, Info2, NewTree, NewChanged) + 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}. @@ -1786,7 +1782,7 @@ 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); + Info#{hipe_icode:var_name(PossibleVar) => Range}; false -> Info end; @@ -1795,7 +1791,7 @@ enter_define(PossibleVar, Info) -> true -> case hipe_icode:variable_annotation(PossibleVar) of {range_anno, #ann{range=Range}, _} -> - gb_trees:enter(hipe_icode:var_name(PossibleVar), Range, Info); + Info#{hipe_icode:var_name(PossibleVar) => Range}; _ -> Info end; @@ -1810,11 +1806,10 @@ enter_vals(Ins, Info) -> 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 + PossibleVarName = hipe_icode:var_name(PossibleVar), + case Info of + #{PossibleVarName := Val} -> Val; + _ -> none_type() end; false -> none_type() @@ -1828,10 +1823,10 @@ lookup(PossibleVar, Info) -> 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)}. + {Labels, [], set_from_list(Labels)}. get_work({[Label|Left], List, Set}) -> - NewWork = {Left, List, sets:del_element(Label, Set)}, + NewWork = {Left, List, maps:remove(Label, Set)}, {Label, NewWork}; get_work({[], [], _Set}) -> fixpoint; @@ -1839,12 +1834,12 @@ 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 -> + case Set of + #{Label := _} -> add_work(Work, Left); - false -> + _ -> %% io:format("Adding work: ~w\n", [Label]), - add_work({List1, [Label|List2], sets:add_element(Label, Set)}, Left) + add_work({List1, [Label|List2], Set#{Label => []}}, Left) end; add_work(Work, []) -> Work. @@ -1959,3 +1954,21 @@ 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). diff --git a/lib/hipe/icode/hipe_icode_ssa.erl b/lib/hipe/icode/hipe_icode_ssa.erl index b222fbc7d2..aca13a2ff0 100644 --- a/lib/hipe/icode/hipe_icode_ssa.erl +++ b/lib/hipe/icode/hipe_icode_ssa.erl @@ -34,13 +34,16 @@ -define(LIVENESS, hipe_icode_liveness). -define(LIVENESS_NEEDED, true). +-export_type([liveness/0]). + -include("hipe_icode.hrl"). -include("../ssa/hipe_ssa.inc"). %% Declarations for exported functions which are Icode-specific. --spec ssa_liveness__analyze(#cfg{}) -> gb_trees:tree(). --spec ssa_liveness__livein(_, icode_lbl()) -> [#icode_variable{}]. -%% -spec ssa_liveness__livein(_, icode_lbl(), _) -> [#icode_var{}]. +-opaque liveness() :: liveness(icode_lbl(), #icode_variable{}). +-spec ssa_liveness__analyze(#cfg{}) -> liveness(). +-spec ssa_liveness__livein(liveness(), icode_lbl()) -> [#icode_variable{}]. +%% -spec ssa_liveness__livein(liveness(), icode_lbl(), _) -> [#icode_var{}]. %%---------------------------------------------------------------------- %% Auxiliary operations which seriously differ between Icode and RTL. diff --git a/lib/hipe/icode/hipe_icode_ssa_const_prop.erl b/lib/hipe/icode/hipe_icode_ssa_const_prop.erl index 4ab4d7e95d..5d3d5413bc 100644 --- a/lib/hipe/icode/hipe_icode_ssa_const_prop.erl +++ b/lib/hipe/icode/hipe_icode_ssa_const_prop.erl @@ -97,11 +97,13 @@ visit_expression(Instruction, Environment) -> visit_begin_handler (Instruction, EvaluatedArguments, Environment); #icode_begin_try{} -> visit_begin_try (Instruction, EvaluatedArguments, Environment); - #icode_fail{} -> + #icode_fail{} -> visit_fail (Instruction, EvaluatedArguments, Environment); - _ -> - %% label, end_try, comment, return, - {[], [], Environment} + #icode_comment{} -> {[], [], Environment}; + #icode_end_try{} -> {[], [], Environment}; + #icode_enter{} -> {[], [], Environment}; + #icode_label{} -> {[], [], Environment}; + #icode_return{} -> {[], [], Environment} end. %%----------------------------------------------------------------------------- @@ -463,11 +465,15 @@ update_instruction(Instruction, Environment) -> update_type(Instruction, Environment); #icode_switch_tuple_arity{} -> update_switch_tuple_arity(Instruction, Environment); - _ -> - %% goto, comment, label, return, begin_handler, end_try, - %% begin_try, fail - %% We could but don't handle: catch?, fail? - [Instruction] + %% We could but don't handle: catch?, fail? + #icode_begin_handler{} -> [Instruction]; + #icode_begin_try{} -> [Instruction]; + #icode_comment{} -> [Instruction]; + #icode_end_try{} -> [Instruction]; + #icode_fail{} -> [Instruction]; + #icode_goto{} -> [Instruction]; + #icode_label{} -> [Instruction]; + #icode_return{} -> [Instruction] end. %%----------------------------------------------------------------------------- @@ -502,14 +508,12 @@ update_call(Instruction, Environment) -> [Instruction, NewInstructions]), NewInstructions end; -%% %% [] -> %% No destination; we don't touch this -%% [] -> -%% NewArguments = update_arguments(hipe_icode:call_args(Instruction), -%% Environment), -%% [hipe_icode:call_args_update(Instruction, NewArguments)]; + %% [] -> %% No destination; we don't touch this %% List-> %% Means register allocation; not implemented at this point _ -> - [Instruction] + NewArguments = update_arguments(hipe_icode:call_args(Instruction), + Environment), + [hipe_icode:call_args_update(Instruction, NewArguments)] end. %%----------------------------------------------------------------------------- @@ -574,7 +578,9 @@ update_if(Instruction, Environment) -> %% Convert the if-test to a type test if possible. Op = hipe_icode:if_op(Instruction), case Op =:= '=:=' orelse Op =:= '=/=' of - false -> [Instruction]; + false -> + [hipe_icode:if_args_update( + Instruction, update_arguments(Args, Environment))]; true -> [Arg1, Arg2] = Args, case EvaluatedArguments of @@ -604,8 +610,9 @@ conv_if_to_type(I, Const, Arg) when is_atom(Const); NewI = hipe_icode:mk_type([Arg], Test, T, F), ?CONST_PROP_MSG("if: ~w ---> type ~w\n", [I, NewI]), [NewI]; -conv_if_to_type(I, _, _) -> - [I]. +conv_if_to_type(I, Const, Arg) -> + %% Note: we are potentially commuting the (equality) comparison here + [hipe_icode:if_args_update(I, [Arg, hipe_icode:mk_const(Const)])]. %%----------------------------------------------------------------------------- diff --git a/lib/hipe/icode/hipe_icode_type.erl b/lib/hipe/icode/hipe_icode_type.erl index 794c27ebcc..3f0e2998f1 100644 --- a/lib/hipe/icode/hipe_icode_type.erl +++ b/lib/hipe/icode/hipe_icode_type.erl @@ -100,7 +100,7 @@ -record(state, {info_map = gb_trees:empty() :: gb_trees:tree(), cfg :: cfg(), - liveness = gb_trees:empty() :: gb_trees:tree(), + liveness :: hipe_icode_ssa:liveness(), arg_types :: [erl_types:erl_type()], ret_type = [t_none()] :: [erl_types:erl_type()], lookupfun :: call_fun(), |