diff options
Diffstat (limited to 'lib/hipe/rtl/hipe_rtl_lcm.erl')
| -rw-r--r-- | lib/hipe/rtl/hipe_rtl_lcm.erl | 1696 |
1 files changed, 1696 insertions, 0 deletions
diff --git a/lib/hipe/rtl/hipe_rtl_lcm.erl b/lib/hipe/rtl/hipe_rtl_lcm.erl new file mode 100644 index 0000000000..5d65389d48 --- /dev/null +++ b/lib/hipe/rtl/hipe_rtl_lcm.erl @@ -0,0 +1,1696 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2004-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_rtl_lcm.erl +%% Author : Henrik Nyman and Erik Cedheim +%% Description : Performs Lazy Code Motion on RTL +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% @doc +%% +%% This module implements Lazy Code Motion on RTL. +%% +%% @end +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-module(hipe_rtl_lcm). + +-export([rtl_lcm/2]). + +-define(SETS, ordsets). %% Which set implementation module to use + %% We have tried gb_sets, sets and ordsets and + %% ordsets seems to be a lot faster according to + %% our test runs. + +-include("../main/hipe.hrl"). +-include("hipe_rtl.hrl"). +-include("../flow/cfg.hrl"). + +%%-define(LCM_DEBUG, true). %% When defined and true, produces debug printouts + +%%============================================================================= + +%% +%% @doc Performs Lazy Code Motion on RTL. +%% + +-spec rtl_lcm(cfg(), comp_options()) -> cfg(). + +rtl_lcm(CFG, Options) -> + %% Perform pre-calculation of the data sets. + ?opt_start_timer("RTL LCM precalc"), + {NodeInfo, EdgeInfo, AllExpr, ExprMap, IdMap, Labels} = lcm_precalc(CFG, Options), + ?opt_stop_timer("RTL LCM precalc"), + %% {NodeInfo, EdgeInfo, AllExpr, ExprMap, Labels} = + %% ?option_time(lcm_precalc(CFG, Options), "RTL LCM precalc", Options), + + pp_debug("-------------------------------------------------~n",[]), + %% pp_debug( "~w~n", [MFA]), + + %% A check if we should pretty print the result. + case proplists:get_bool(pp_rtl_lcm, Options) of + true-> + pp_debug("-------------------------------------------------~n",[]), + %% pp_debug("AllExpr: ~w~n", [AllExpr]), + pp_debug("AllExpr:~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(AllExpr)), + %% pp_sets(ExprMap, NodeInfo, EdgeInfo, AllExpr, CFG2<-ERROR!, Labels); + pp_sets(ExprMap, IdMap, NodeInfo, EdgeInfo, AllExpr, CFG, Labels); + _ -> + ok + end, + + pp_debug("-------------------------------------------------~n",[]), + ?option_time({CFG1, MoveSet} = perform_lcm(CFG, NodeInfo, EdgeInfo, ExprMap, + IdMap, AllExpr, mk_edge_bb_map(), + ?SETS:new(), Labels), + "RTL LCM perform_lcm", Options), + + %% Scan through list of moved expressions and replace their + %% assignments with the new temporary created for that expression + MoveList = ?SETS:to_list(MoveSet), + ?option_time(CFG2 = moved_expr_replace_assignments(CFG1, ExprMap, IdMap, + MoveList), + "RTL LCM moved_expr_replace_assignments", Options), + pp_debug("-------------------------------------------------~n~n",[]), + + CFG2. + +%%============================================================================= +%% Performs lazy code motion given the pre-calculated data sets. +perform_lcm(CFG, _, _, _, _, _, _, MoveSet, []) -> + {CFG, MoveSet}; +perform_lcm(CFG0, NodeInfo, EdgeInfo, ExprMap, IdMap, AllExp, BetweenMap, + MoveSet0, [Label|Labels]) -> + Code0 = hipe_bb:code(hipe_rtl_cfg:bb(CFG0, Label)), + DeleteSet = delete(NodeInfo, Label), + + %% Check if something should be deleted from this block. + {CFG1, MoveSet1} = + case ?SETS:size(DeleteSet) > 0 of + true -> + pp_debug("Label ~w: Expressions Deleted: ~n", [Label]), + Code1 = delete_exprs(Code0, ExprMap, IdMap, ?SETS:to_list(DeleteSet)), + BB = hipe_bb:mk_bb(Code1), + {hipe_rtl_cfg:bb_add(CFG0, Label, BB), + ?SETS:union(MoveSet0, DeleteSet)}; + false -> + {CFG0, MoveSet0} + end, + + Succs = hipe_rtl_cfg:succ(CFG1, Label), + + %% Go through the list of successors and insert expression where needed. + %% Also collect a list of expressions that are inserted somewhere + {CFG2, NewBetweenMap, MoveSet2} = + lists:foldl(fun(Succ, {CFG, BtwMap, MoveSet}) -> + InsertSet = calc_insert_edge(NodeInfo, EdgeInfo, + Label, Succ), + %% Check if something should be inserted on this edge. + case ?SETS:size(InsertSet) > 0 of + true -> + pp_debug("Label ~w: Expressions Inserted for Successor: ~w~n", [Label, Succ]), + InsertList = ?SETS:to_list(InsertSet), + {NewCFG, NewBtwMap} = + insert_exprs(CFG, Label, Succ, ExprMap, IdMap, + BtwMap, InsertList), + {NewCFG, NewBtwMap, ?SETS:union(MoveSet, InsertSet)}; + false -> + {CFG, BtwMap, MoveSet} + end + end, + {CFG1, BetweenMap, MoveSet1}, Succs), + + perform_lcm(CFG2, NodeInfo, EdgeInfo, ExprMap, IdMap, AllExp, NewBetweenMap, + MoveSet2, Labels). + +%%============================================================================= +%% Scan through list of moved expressions and replace their +%% assignments with the new temporary created for that expression. +moved_expr_replace_assignments(CFG, _, _, []) -> + CFG; +moved_expr_replace_assignments(CFG0, ExprMap, IdMap, [ExprId|Exprs]) -> + Expr = expr_id_map_get_expr(IdMap, ExprId), + case expr_map_lookup(ExprMap, Expr) of + {value, {_, ReplaceList, NewReg}} -> + CFG1 = lists:foldl(fun({Label, Reg}, CFG) -> + %% Find and replace expression in block + pp_debug("Label ~w: Expressions Replaced:~n", [Label]), + Code0 = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)), + Code1 = + moved_expr_do_replacement(expr_set_dst(Expr, Reg), + Reg, NewReg, Code0), + hipe_rtl_cfg:bb_add(CFG, Label, hipe_bb:mk_bb(Code1)) + end, CFG0, ReplaceList), + moved_expr_replace_assignments(CFG1, ExprMap, IdMap, Exprs); + none -> + moved_expr_replace_assignments(CFG0, ExprMap, IdMap, Exprs) + end. + +moved_expr_do_replacement(_, _, _, []) -> + []; +moved_expr_do_replacement(Expr, Reg, NewReg, [Expr|Instrs]) -> + NewExpr = expr_set_dst(Expr, NewReg), + Move = mk_expr_move_instr(Reg, NewReg), + pp_debug(" Replacing:~n", []), + pp_debug_instr(Expr), + pp_debug(" With:~n", []), + pp_debug_instr(NewExpr), + pp_debug_instr(Move), + [NewExpr, Move | moved_expr_do_replacement(Expr, Reg, NewReg, Instrs)]; +moved_expr_do_replacement(Expr, Reg, NewReg, [Instr|Instrs]) -> + [Instr | moved_expr_do_replacement(Expr, Reg, NewReg, Instrs)]. + +%%============================================================================= +%% Goes through the given list of expressions and deletes them from the code. +%% NOTE We do not actually delete an expression, but instead we replace it +%% with an assignment from the new temporary containing the result of the +%% expressions which is guaranteed to have been calculated earlier in +%% the code. +delete_exprs(Code, _, _, []) -> + Code; +delete_exprs(Code, ExprMap, IdMap, [ExprId|Exprs]) -> + Expr = expr_id_map_get_expr(IdMap, ExprId), + %% Perform a foldl that goes through the code and deletes all + %% occurences of the expression. + NewCode = + lists:reverse + (lists:foldl(fun(CodeExpr, Acc) -> + case is_expr(CodeExpr) of + true -> + case expr_clear_dst(CodeExpr) =:= Expr of + true -> + pp_debug(" Deleting: ", []), + pp_debug_instr(CodeExpr), + %% Lookup expression entry. + Defines = + case expr_map_lookup(ExprMap, Expr) of + {value, {_, _, Defs}} -> + Defs; + none -> + exit({?MODULE, expr_map_lookup, + "expression missing"}) + end, + MoveCode = + mk_expr_move_instr(hipe_rtl:defines(CodeExpr), + Defines), + pp_debug(" Replacing with: ", []), + pp_debug_instr(MoveCode), + [MoveCode|Acc]; + false -> + [CodeExpr|Acc] + end; + false -> + [CodeExpr|Acc] + end + end, + [], Code)), + delete_exprs(NewCode, ExprMap, IdMap, Exprs). + +%%============================================================================= +%% Goes through the given list of expressions and inserts them at +%% appropriate places in the code. +insert_exprs(CFG, _, _, _, _, BetweenMap, []) -> + {CFG, BetweenMap}; +insert_exprs(CFG, Pred, Succ, ExprMap, IdMap, BetweenMap, [ExprId|Exprs]) -> + Expr = expr_id_map_get_expr(IdMap, ExprId), + Instr = expr_map_get_instr(ExprMap, Expr), + case hipe_rtl_cfg:succ(CFG, Pred) of + [_] -> + pp_debug(" Inserted last: ", []), + pp_debug_instr(Instr), + NewCFG = insert_expr_last(CFG, Pred, Instr), + insert_exprs(NewCFG, Pred, Succ, ExprMap, IdMap, BetweenMap, Exprs); + _ -> + case hipe_rtl_cfg:pred(CFG, Succ) of + [_] -> + pp_debug(" Inserted first: ", []), + pp_debug_instr(Instr), + NewCFG = insert_expr_first(CFG, Succ, Instr), + insert_exprs(NewCFG, Pred, Succ, ExprMap, IdMap, BetweenMap, Exprs); + _ -> + pp_debug(" Inserted between: ", []), + pp_debug_instr(Instr), + {NewCFG, NewBetweenMap} = + insert_expr_between(CFG, BetweenMap, Pred, Succ, Instr), + insert_exprs(NewCFG, Pred, Succ, ExprMap, IdMap, NewBetweenMap, Exprs) + end + end. + +%%============================================================================= +%% Recursively goes through the code in a block and returns a new block +%% with the new code inserted second to last (assuming the last expression +%% is a branch operation). +insert_expr_last(CFG0, Label, Instr) -> + Code0 = hipe_bb:code(hipe_rtl_cfg:bb(CFG0, Label)), + %% FIXME: Use hipe_bb:butlast() instead? + Code1 = insert_expr_last_work(Label, Instr, Code0), + hipe_rtl_cfg:bb_add(CFG0, Label, hipe_bb:mk_bb(Code1)). + +%%============================================================================= +%% Recursively goes through the code in a block and returns a new block +%% with the new code inserted second to last (assuming the last expression +%% is a branch operation). +insert_expr_last_work(_, Instr, []) -> + %% This case should not happen since this means that block was completely + %% empty when the function was called. For compability we insert it last. + [Instr]; +insert_expr_last_work(_, Instr, [Code1]) -> + %% We insert the code next to last. + [Instr, Code1]; +insert_expr_last_work(Label, Instr, [Code|Codes]) -> + [Code|insert_expr_last_work(Label, Instr, Codes)]. + +%%============================================================================= +%% Inserts expression first in the block for the given label. +insert_expr_first(CFG0, Label, Instr) -> + %% The first instruction is always a label + [Lbl|Code0] = hipe_bb:code(hipe_rtl_cfg:bb(CFG0, Label)), + Code1 = [Lbl, Instr | Code0], + hipe_rtl_cfg:bb_add(CFG0, Label, hipe_bb:mk_bb(Code1)). + +%%============================================================================= +%% Inserts an expression on and edge between two existing blocks. +%% It creates a new basic block to hold the expression. +%% Created bbs are inserted into BetweenMap to be able to reuse them for +%% multiple inserts on the same edge. +%% NOTE Currently creates multiple blocks for identical expression with the +%% same successor. Since the new bb usually contains very few instructions +%% this should not be a problem. +insert_expr_between(CFG0, BetweenMap, Pred, Succ, Instr) -> + PredSucc = {Pred, Succ}, + case edge_bb_map_lookup(BetweenMap, PredSucc) of + none -> + NewLabel = hipe_rtl:mk_new_label(), + NewLabelName = hipe_rtl:label_name(NewLabel), + pp_debug(" Creating new bb ~w~n", [NewLabel]), + Code = [Instr, hipe_rtl:mk_goto(Succ)], + CFG1 = hipe_rtl_cfg:bb_add(CFG0, NewLabelName, hipe_bb:mk_bb(Code)), + CFG2 = hipe_rtl_cfg:redirect(CFG1, Pred, Succ, NewLabelName), + NewBetweenMap = edge_bb_map_insert(BetweenMap, PredSucc, NewLabelName), + pp_debug(" Mapping edge (~w,~w) to label ~w~n", + [Pred, Succ, NewLabelName]), + {CFG2, NewBetweenMap}; + {value, Label} -> + pp_debug(" Using existing new bb for edge (~w,~w) with label ~w~n", + [Pred, Succ, Label]), + {insert_expr_last(CFG0, Label, Instr), BetweenMap} + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%% GENERAL UTILITY FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%============================================================================= +%% Returns true if the list of registers only contains virtual registers and +%% no machine registers. +no_machine_regs([]) -> + true; +no_machine_regs([Reg|Regs]) -> + case hipe_rtl:is_reg(Reg) of + true -> + N = hipe_rtl:reg_index(Reg), + (N >= hipe_rtl_arch:first_virtual_reg()) andalso no_machine_regs(Regs); + _ -> + case hipe_rtl:is_fpreg(Reg) of + true -> + N = hipe_rtl:fpreg_index(Reg), + (N >= hipe_rtl_arch:first_virtual_reg()) andalso no_machine_regs(Regs); + _ -> + no_machine_regs(Regs) + end + end. + +%%============================================================================= +%% Returns true if an RTL instruction is an expression. +%% +is_expr(I) -> + Defines = hipe_rtl:defines(I), + Uses = hipe_rtl:uses(I), + + %% We don't cosider something that doesn't define anything as an expression. + %% Also we don't consider machine registers to be expressions. + case length(Defines) > 0 andalso no_machine_regs(Defines) + andalso no_machine_regs(Uses) of + true -> + case I of + #alu{} -> true; +%% #alu{} -> +%% Dst = hipe_rtl:alu_dst(I), +%% Src1 = hipe_rtl:alu_src1(I), +%% Src2 = hipe_rtl:alu_src2(I), + + %% Check if dst updates src +%% case Dst =:= Src1 orelse Dst =:= Src2 of +%% true -> +%% false; +%% false -> +%% true +%% end; + + %% Check if alu expression is untagging of boxed (rX <- vX sub 2) +%% case hipe_rtl:is_reg(Dst) andalso hipe_rtl:is_var(Src1) andalso +%% (hipe_rtl:alu_op(I) =:= sub) andalso hipe_rtl:is_imm(Src2) of +%% true -> +%% case hipe_rtl:imm_value(Src2) of +%% 2 -> false; %% Tag for boxed. TODO: Should not be hardcoded... +%% _ -> true +%% end; +%% false -> +%% true +%% end; + + #alub{} -> false; %% TODO: Split instruction to consider alu expression? + #branch{} -> false; + #call{} -> false; %% We cannot prove that a call has no side-effects + #comment{} -> false; + #enter{} -> false; + %% #fail_to{} -> false; %% Deprecated? + #fconv{} -> true; + #fixnumop{} -> true; + #fload{} -> true; + #fmove{} -> false; + #fp{} -> true; + #fp_unop{} -> true; + #fstore{} -> false; + #goto{} -> false; + #goto_index{} -> false; + #gctest{} -> false; + #label{} -> false; + #load{} -> true; + #load_address{} -> + case hipe_rtl:load_address_type(I) of + c_const -> false; + closure -> false; %% not sure whether safe to move; + %% also probably not worth it + constant -> true + end; + #load_atom{} -> true; + #load_word_index{} -> true; + #move{} -> false; + #multimove{} -> false; + #phi{} -> false; + #return{} -> false; + #store{} -> false; + #switch{} -> false + end; + false -> + false + end. + +%%============================================================================= +%% Replaces destination of RTL expression with empty list. +%% +expr_set_dst(I, [Dst|_Dsts] = DstList) -> + case I of + #alu{} -> hipe_rtl:alu_dst_update(I, Dst); + #call{} -> hipe_rtl:call_dstlist_update(I, DstList); + #fconv{} -> hipe_rtl:fconv_dst_update(I, Dst); + #fixnumop{} -> hipe_rtl:fixnumop_dst_update(I, Dst); + #fload{} -> hipe_rtl:fload_dst_update(I, Dst); + %% #fmove{} -> hipe_rtl:fmove_dst_update(I, Dst); + #fp{} -> hipe_rtl:fp_dst_update(I, Dst); + #fp_unop{} -> hipe_rtl:fp_unop_dst_update(I, Dst); + #load{} -> hipe_rtl:load_dst_update(I, Dst); + #load_address{} -> hipe_rtl:load_address_dst_update(I, Dst); + #load_atom{} -> hipe_rtl:load_atom_dst_update(I, Dst); + #load_word_index{} -> hipe_rtl:load_word_index_dst_update(I, Dst); + %% #move{} -> hipe_rtl:move_dst_update(I, Dst); + _ -> exit({?MODULE, expr_set_dst, "bad expression"}) + end. + +%%============================================================================= +%% Replaces destination of RTL expression with empty list. +%% +expr_clear_dst(I) -> + case I of + #alu{} -> hipe_rtl:alu_dst_update(I, nil); + #call{} -> hipe_rtl:call_dstlist_update(I, nil); + #fconv{} -> hipe_rtl:fconv_dst_update(I, nil); + #fixnumop{} -> hipe_rtl:fixnumop_dst_update(I, nil); + #fload{} -> hipe_rtl:fload_dst_update(I, nil); + %% #fmove{} -> hipe_rtl:fmove_dst_update(I, nil); + #fp{} -> hipe_rtl:fp_dst_update(I, nil); + #fp_unop{} -> hipe_rtl:fp_unop_dst_update(I, nil); + #load{} -> hipe_rtl:load_dst_update(I, nil); + #load_address{} -> hipe_rtl:load_address_dst_update(I, nil); + #load_atom{} -> hipe_rtl:load_atom_dst_update(I, nil); + #load_word_index{} -> hipe_rtl:load_word_index_dst_update(I, nil); + %% #move{} -> hipe_rtl:move_dst_update(I, nil); + _ -> exit({?MODULE, expr_clear_dst, "bad expression"}) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%% PRECALC FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%============================================================================= +%% Pre-calculates the flow analysis and puts the calculated sets in maps for +%% easy access later. +lcm_precalc(CFG, Options) -> + %% Calculate use map and expression map. + ?option_time({ExprMap, IdMap} = mk_expr_map(CFG), + "RTL LCM mk_expr_map", Options), + ?option_time(UseMap = mk_use_map(CFG, ExprMap), + "RTL LCM mk_use_map", Options), + %% Labels = hipe_rtl_cfg:reverse_postorder(CFG), + Labels = hipe_rtl_cfg:labels(CFG), + %% StartLabel = hipe_rtl_cfg:start_label(CFG), + %% AllExpr = all_exprs(CFG, Labels), + AllExpr = ?SETS:from_list(gb_trees:keys(IdMap)), + + %% Calculate the data sets. + ?option_time(NodeInfo0 = mk_node_info(Labels), "RTL LCM mk_node_info", + Options), + %% ?option_time(EdgeInfo0 = mk_edge_info(), "RTL LCM mk_edge_info", + %% Options), + EdgeInfo0 = mk_edge_info(), + ?option_time(NodeInfo1 = calc_up_exp(CFG, ExprMap, NodeInfo0, Labels), + "RTL LCM calc_up_exp", Options), + ?option_time(NodeInfo2 = calc_down_exp(CFG, ExprMap, NodeInfo1, Labels), + "RTL LCM calc_down_exp", Options), + ?option_time(NodeInfo3 = calc_killed_expr(CFG, NodeInfo2, UseMap, AllExpr, + Labels), + "RTL LCM calc_killed_exp", Options), + ?option_time(NodeInfo4 = calc_avail(CFG, NodeInfo3), + "RTL LCM calc_avail", Options), + ?option_time(NodeInfo5 = calc_antic(CFG, NodeInfo4, AllExpr), + "RTL LCM calc_antic", Options), + ?option_time(EdgeInfo1 = calc_earliest(CFG, NodeInfo5, EdgeInfo0, Labels), + "RTL LCM calc_earliest", Options), + ?option_time({NodeInfo6, EdgeInfo2} = calc_later(CFG, NodeInfo5, EdgeInfo1), + "RTL LCM calc_later", Options), + ?option_time(NodeInfo7 = calc_delete(CFG, NodeInfo6, Labels), + "RTL LCM calc_delete", Options), + {NodeInfo7, EdgeInfo2, AllExpr, ExprMap, IdMap, Labels}. + +%%%%%%%%%%%%%%%%%%% AVAILABLE IN/OUT FLOW ANALYSIS %%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Fixpoint calculation of anticipated in/out sets. +%% Uses a worklist algorithm. +%% Performs the avail in/out flow analysis. + +%%============================================================================= +%% Calculates the available in/out sets, and returns an updated NodeInfo. + +calc_avail(CFG, NodeInfo) -> + StartLabel = hipe_rtl_cfg:start_label(CFG), + Work = init_work([StartLabel]), + %% Initialize start node + NewNodeInfo = set_avail_in(NodeInfo, StartLabel, ?SETS:new()), + calc_avail_fixpoint(Work, CFG, NewNodeInfo). + +calc_avail_fixpoint(Work, CFG, NodeInfo) -> + case get_work(Work) of + fixpoint -> + NodeInfo; + {Label, NewWork} -> + {NewNodeInfo, NewLabels} = calc_avail_node(Label, CFG, NodeInfo), + NewWork2 = add_work(NewWork, NewLabels), + calc_avail_fixpoint(NewWork2, CFG, NewNodeInfo) + end. + +calc_avail_node(Label, CFG, NodeInfo) -> + %% Get avail in + AvailIn = avail_in(NodeInfo, Label), + + %% Calculate avail out + AvailOut = ?SETS:union(down_exp(NodeInfo, Label), + ?SETS:subtract(AvailIn, + killed_expr(NodeInfo, Label))), + + {Changed, NodeInfo2} = + case avail_out(NodeInfo, Label) of + none -> + %% If there weren't any old avail out we use this one. + {true, set_avail_out(NodeInfo, Label, AvailOut)}; + OldAvailOut -> + %% Check if the avail outs are equal. + case AvailOut =:= OldAvailOut of + true -> + {false, NodeInfo}; + false -> + {true, set_avail_out(NodeInfo, Label, AvailOut)} + end + end, + + case Changed of + true -> + %% Update AvailIn-sets of successors and add them to worklist + Succs = hipe_rtl_cfg:succ(CFG, Label), + NodeInfo3 = + lists:foldl + (fun(Succ, NewNodeInfo) -> + case avail_in(NewNodeInfo, Succ) of + none -> + %% Initialize avail in to all expressions + set_avail_in(NewNodeInfo, Succ, AvailOut); + OldAvailIn -> + set_avail_in(NewNodeInfo, Succ, + ?SETS:intersection(OldAvailIn, AvailOut)) + end + end, + NodeInfo2, Succs), + {NodeInfo3, Succs}; + false -> + {NodeInfo2, []} + end. + +%%%%%%%%%%%%%%%%%% ANTICIPATED IN/OUT FLOW ANALYSIS %%%%%%%%%%%%%%%%%%%%%%%%%% +%% Fixpoint calculation of anticipated in/out sets. +%% Uses a worklist algorithm. + +%%============================================================================= +%% Calculates the anicipated in/out sets, and returns an updated NodeInfo. +calc_antic(CFG, NodeInfo, AllExpr) -> + %% Initialize worklist with all nodes in postorder + Labels = hipe_rtl_cfg:postorder(CFG), + Work = init_work(Labels), + calc_antic_fixpoint(Work, CFG, NodeInfo, AllExpr). + +calc_antic_fixpoint(Work, CFG, NodeInfo, AllExpr) -> + case get_work(Work) of + fixpoint -> + NodeInfo; + {Label, NewWork} -> + {NewNodeInfo, NewLabels} = calc_antic_node(Label, CFG, NodeInfo, AllExpr), + NewWork2 = add_work(NewWork, NewLabels), + calc_antic_fixpoint(NewWork2, CFG, NewNodeInfo, AllExpr) + end. + +calc_antic_node(Label, CFG, NodeInfo, AllExpr) -> + %% Get antic out + AnticOut = + case antic_out(NodeInfo, Label) of + none -> + case is_exit_label(CFG, Label) of + true -> + ?SETS:new(); + false -> + AllExpr + end; + + AnticOutTemp -> AnticOutTemp + end, + + %% Calculate antic in + AnticIn = ?SETS:union(up_exp(NodeInfo, Label), + ?SETS:subtract(AnticOut, + killed_expr(NodeInfo, Label))), + {Changed, NodeInfo2} = + case antic_in(NodeInfo, Label) of + %% If there weren't any old antic in we use this one. + none -> + {true, set_antic_in(NodeInfo, Label, AnticIn)}; + + OldAnticIn -> + %% Check if the antic in:s are equal. + case AnticIn =:= OldAnticIn of + true -> + {false, NodeInfo}; + false -> + {true, + set_antic_in(NodeInfo, Label, AnticIn)} + end + end, + + case Changed of + true -> + %% Update AnticOut-sets of predecessors and add them to worklist + Preds = hipe_rtl_cfg:pred(CFG, Label), + NodeInfo3 = + lists:foldl + (fun(Pred, NewNodeInfo) -> + case antic_out(NewNodeInfo, Pred) of + none -> + %% Initialize antic out to all expressions + set_antic_out(NewNodeInfo, Pred, AnticIn); + OldAnticOut -> + set_antic_out(NewNodeInfo, Pred, + ?SETS:intersection(OldAnticOut, AnticIn)) + end + end, + NodeInfo2, Preds), + {NodeInfo3, Preds}; + false -> + {NodeInfo2, []} + end. + +%%%%%%%%%%%%%%%%%%%%% LATER / LATER IN FLOW ANALYSIS %%%%%%%%%%%%%%%%%%%%%%%%%% +%% Fixpoint calculations of Later and LaterIn sets. +%% Uses a worklist algorithm. +%% Note that the Later set is calculated on edges. + +%%============================================================================= +%% Calculates the Later and LaterIn sets, and returns updates of both +%% NodeInfo (with LaterIn sets) and EdgeInfo (with Later sets). + +calc_later(CFG, NodeInfo, EdgeInfo) -> + StartLabel = hipe_rtl_cfg:start_label(CFG), + Work = init_work([{node, StartLabel}]), + %% Initialize start node + NewNodeInfo = set_later_in(NodeInfo, StartLabel, ?SETS:new()), + calc_later_fixpoint(Work, CFG, NewNodeInfo, EdgeInfo). + +calc_later_fixpoint(Work, CFG, NodeInfo, EdgeInfo) -> + case get_work(Work) of + {{edge, From, To}, Work2} -> + {NewNodeInfo, NewEdgeInfo, AddWork} = + calc_later_edge(From, To, CFG, NodeInfo, EdgeInfo), + Work3 = add_work(Work2, AddWork), + calc_later_fixpoint(Work3, CFG, NewNodeInfo, NewEdgeInfo); + {{node, Label}, Work2} -> + AddWork = calc_later_node(Label, CFG), + Work3 = add_work(Work2, AddWork), + calc_later_fixpoint(Work3, CFG, NodeInfo, EdgeInfo); + fixpoint -> + {NodeInfo, EdgeInfo} + end. + +calc_later_node(Label, CFG) -> + Succs = hipe_rtl_cfg:succ(CFG, Label), + [{edge, Label, Succ} || Succ <- Succs]. + +calc_later_edge(From, To, _CFG, NodeInfo, EdgeInfo) -> + FromTo = {From, To}, + Earliest = earliest(EdgeInfo, FromTo), + LaterIn = later_in(NodeInfo, From), + UpExp = up_exp(NodeInfo, From), + Later = ?SETS:union(Earliest, ?SETS:subtract(LaterIn, UpExp)), + {Changed, EdgeInfo2} = + case lookup_later(EdgeInfo, FromTo) of + none -> {true, set_later(EdgeInfo, FromTo, Later)}; + Later -> {false, EdgeInfo}; + _Old -> {true, set_later(EdgeInfo, FromTo, Later)} + end, + case Changed of + true -> + %% Update later in set of To-node + case lookup_later_in(NodeInfo, To) of + %% If the data isn't set initialize to all expressions + none -> + {set_later_in(NodeInfo, To, Later), EdgeInfo2, [{node, To}]}; + OldLaterIn -> + NewLaterIn = ?SETS:intersection(OldLaterIn, Later), + %% Check if something changed + %% FIXME: Implement faster equality test? + case NewLaterIn =:= OldLaterIn of + true -> + {NodeInfo, EdgeInfo2, []}; + false -> + {set_later_in(NodeInfo, To, NewLaterIn), + EdgeInfo2, [{node, To}]} + end + end; + false -> + {NodeInfo, EdgeInfo2, []} + end. + +%%%%%%%%%%%%%%%%%% UPWARDS/DOWNWARDS EXPOSED EXPRESSIONS %%%%%%%%%%%%%%%%%%%%%% +%% Calculates upwards and downwards exposed expressions. + +%%============================================================================= +%% Calculates the downwards exposed expression sets for the given labels in +%% the CFG. +calc_down_exp(_, _, NodeInfo, []) -> + NodeInfo; +calc_down_exp(CFG, ExprMap, NodeInfo, [Label|Labels]) -> + Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)), + %% Data = ?SETS:from_list(lists:map(fun expr_clear_dst/1, exp_work(Code))), + Data = ?SETS:from_list(get_expr_ids(ExprMap, exp_work(Code))), + NewNodeInfo = set_down_exp(NodeInfo, Label, Data), + calc_down_exp(CFG, ExprMap, NewNodeInfo, Labels). + +%%============================================================================= +%% Calculates the upwards exposed expressions sets for the given labels in +%% the CFG. +calc_up_exp(_, _, NodeInfo, []) -> + NodeInfo; +calc_up_exp(CFG, ExprMap, NodeInfo, [Label|Labels]) -> + BB = hipe_rtl_cfg:bb(CFG, Label), + RevCode = lists:reverse(hipe_bb:code(BB)), + Data = ?SETS:from_list(get_expr_ids(ExprMap, exp_work(RevCode))), + NewNodeInfo = set_up_exp(NodeInfo, Label, Data), + calc_up_exp(CFG, ExprMap, NewNodeInfo, Labels). + +%%============================================================================= +%% Given a list of expression instructions, gets a list of expression ids +%% from an expression map. +get_expr_ids(ExprMap, Instrs) -> + [expr_map_get_id(ExprMap, expr_clear_dst(I)) || I <- Instrs]. + +%%============================================================================= +%% Does the work of the calc_*_exp functions. +exp_work(Code) -> + exp_work([], Code). + +exp_work([], [Instr|Instrs]) -> + case is_expr(Instr) of + true -> + exp_work([Instr], Instrs); + false -> + exp_work([], Instrs) + end; +exp_work(Exprs, []) -> + Exprs; +exp_work(Exprs, [Instr|Instrs]) -> + NewExprs = case is_expr(Instr) of + true -> + exp_kill_expr(Instr, [Instr|Exprs]); + false -> + exp_kill_expr(Instr, Exprs) + end, + exp_work(NewExprs, Instrs). + +%%============================================================================= +%% Checks if the given instruction redefines any operands of +%% instructions in the instruction list. +%% It returns the list of expressions with those instructions that has +%% operands redefined removed. +exp_kill_expr(_Instr, []) -> + []; +exp_kill_expr(Instr, [CheckedExpr|Exprs]) -> + %% Calls, gctests and stores potentially clobber everything + case Instr of + #call{} -> []; + #gctest{} -> []; + #store{} -> []; %% FIXME: Only regs and vars clobbered, not fregs... + #fstore{} -> + %% fstore potentially clobber float expressions + [ExprDefine|_] = hipe_rtl:defines(CheckedExpr), + case hipe_rtl:is_fpreg(ExprDefine) of + true -> + exp_kill_expr(Instr, Exprs); + false -> + [CheckedExpr | exp_kill_expr(Instr, Exprs)] + end; + _ -> + InstrDefines = hipe_rtl:defines(Instr), + ExprUses = hipe_rtl:uses(CheckedExpr), + Diff = ExprUses -- InstrDefines, + case length(Diff) < length(ExprUses) of + true -> + exp_kill_expr(Instr, Exprs); + false -> + [CheckedExpr | exp_kill_expr(Instr, Exprs)] + end + end. + +%%%%%%%%%%%%%%%%%%%%%%%% KILLED EXPRESSIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%============================================================================= +%% Calculates the killed expression sets for all given labels. +calc_killed_expr(_, NodeInfo, _, _, []) -> + NodeInfo; +calc_killed_expr(CFG, NodeInfo, UseMap, AllExpr, [Label|Labels]) -> + Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)), + KilledExprs = calc_killed_expr_bb(Code, UseMap, AllExpr, ?SETS:new()), + NewNodeInfo = set_killed_expr(NodeInfo, Label, KilledExprs), + calc_killed_expr(CFG, NewNodeInfo, UseMap, AllExpr, Labels). + +%%============================================================================= +%% Calculates the killed expressions set for one basic block. +calc_killed_expr_bb([], _UseMap, _AllExpr, KilledExprs) -> + KilledExprs; +calc_killed_expr_bb([Instr|Instrs], UseMap, AllExpr, KilledExprs) -> + %% Calls, gctests and stores potentially clobber everything + case Instr of + #call{} -> AllExpr; + #gctest{} -> AllExpr; + #store{} -> AllExpr; %% FIXME: Only regs and vars clobbered, not fregs... + #fstore{} -> + %% Kill all float expressions + %% FIXME: Make separate function is_fp_expr + ?SETS:from_list + (lists:foldl(fun(Expr, Fexprs) -> + [Define|_] = hipe_rtl:defines(Expr), + case hipe_rtl:is_fpreg(Define) of + true -> + [Expr|Fexprs]; + false -> + Fexprs + end + end, [], ?SETS:to_list(AllExpr))); + _ -> + case hipe_rtl:defines(Instr) of + [] -> + calc_killed_expr_bb(Instrs, UseMap, AllExpr, KilledExprs); + [Define|_] -> + NewKilledExprs = use_map_get_expr_uses(UseMap, Define), + calc_killed_expr_bb(Instrs, UseMap, AllExpr, + ?SETS:union(NewKilledExprs, KilledExprs)) + end + end. +%%%%%%%%%%%%%%%%%%%%%%%%%%%% EARLIEST %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%============================================================================= +%% Calculates the earliest set for all edges in the CFG. + +calc_earliest(_, _, EdgeInfo, []) -> + EdgeInfo; +calc_earliest(CFG, NodeInfo, EdgeInfo, [To|Labels]) -> + EmptySet = ?SETS:new(), + Preds = hipe_rtl_cfg:pred(CFG, To), + NewEdgeInfo = + case EmptySet =:= antic_in(NodeInfo, To) of + true -> + %% Earliest is empty for all edges into this block. + lists:foldl(fun(From, EdgeInfoAcc) -> + set_earliest(EdgeInfoAcc, {From, To}, EmptySet) + end, EdgeInfo, Preds); + false -> + lists:foldl(fun(From, EdgeInfoAcc) -> + IsStartLabel = (From =:= hipe_rtl_cfg:start_label(CFG)), + Earliest = + calc_earliest_edge(NodeInfo, IsStartLabel, From, To), + set_earliest(EdgeInfoAcc, {From, To}, Earliest) + end, EdgeInfo, Preds) + end, + calc_earliest(CFG, NodeInfo, NewEdgeInfo, Labels). + +%%============================================================================= +%% Calculates the earliest set for one edge. + +calc_earliest_edge(NodeInfo, IsStartLabel, From, To) -> + AnticIn = antic_in(NodeInfo, To), + AvailOut = avail_out(NodeInfo, From), + + case IsStartLabel of + true -> + ?SETS:subtract(AnticIn, AvailOut); + false -> + AnticOut = antic_out(NodeInfo, From), + ExprKill = killed_expr(NodeInfo, From), + ?SETS:subtract(?SETS:subtract(AnticIn, AvailOut), + ?SETS:subtract(AnticOut, ExprKill)) + end. +%% The above used to be: +%% +%% ?SETS:intersection(?SETS:subtract(AnticIn, AvailOut), +%% ?SETS:union(ExprKill, ?SETS:subtract(AllExpr, AnticOut))) +%% +%% But it is costly to use the AllExpr, so let's do some tricky set algebra. +%% +%% Let A = AnticIn, B = AvailOut, C = ExprKill, D = AnticOut, U = AllExpr +%% Let n = intersection, u = union, ' = inverse +%% +%% Then +%% (A - B) n (C u (U - D)) = <Remove D unless it is in C> +%% = (A - B) n ((C u U) - (D - C)) = <But U is the whole universe> +%% = (A - B) n (U - (D - C)) = <We are really meaning the complement> +%% = (A - B) n (D - C)' = <Intersection w complement is subtraction> +%% = (A - B) - (D - C) <Simple enough, let's stop> +%% +%% or in other words +%% ?SETS:subtract(?SETS:subtract(AnticIn, AvailOut), +%% ?SETS:subtract(AnticOut, ExprKill)) + + + +%%%%%%%%%%%%%%%%%%%%%%%% INSERT / DELETE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%============================================================================= +%% Calculates the insert set for one edge and returns the resulting set. +%% NOTE This does not modify the EdgeInfo set, since the resulting set is +%% returned and used immediately, instead of being pre-calculated as are +%% the other sets. +calc_insert_edge(NodeInfo, EdgeInfo, From, To) -> + Later = later(EdgeInfo, {From, To}), + LaterIn = later_in(NodeInfo, To), + ?SETS:subtract(Later, LaterIn). + +%%============================================================================= +%% Calculates the delete set for all given labels in a CFG. +calc_delete(_, NodeInfo, []) -> + NodeInfo; +calc_delete(CFG, NodeInfo, [Label|Labels]) -> + case Label =:= hipe_rtl_cfg:start_label(CFG) of + true -> + NewNodeInfo = set_delete(NodeInfo, Label, ?SETS:new()); + false -> + UpExp = up_exp(NodeInfo, Label), + LaterIn = later_in(NodeInfo, Label), + Delete = ?SETS:subtract(UpExp, LaterIn), + NewNodeInfo = set_delete(NodeInfo, Label, Delete) + end, + calc_delete(CFG, NewNodeInfo, Labels). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%% FIXPOINT FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%============================================================================= +%% Worklist used by the fixpoint calculations. +%% +%% We use gb_sets here, which is optimized for continuous inserts and +%% membership tests. + +init_work(Labels) -> + {Labels, [], gb_sets:from_list(Labels)}. + +get_work({[Label|Left], List, Set}) -> + NewWork = {Left, List, gb_sets:delete(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|Labels]) -> + case gb_sets:is_member(Label, Set) of + true -> + add_work(Work, Labels); + false -> + %%io:format("Adding work: ~w\n", [Label]), + add_work({List1, [Label|List2], gb_sets:insert(Label, Set)}, Labels) + end; +add_work(Work, []) -> + Work. + +%%============================================================================= +%% Calculates the labels that are the exit labels. +%% FIXME We do not detect dead-end loops spanning more than one block. +%% This could potentially cause a bug in the future... +%% exit_labels(CFG) -> +%% Labels = hipe_rtl_cfg:labels(CFG), +%% lists:foldl(fun(Label, ExitLabels) -> +%% Succs = hipe_rtl_cfg:succ(CFG, Label), +%% case Succs of +%% [] -> +%% [Label|ExitLabels]; +%% [Label] -> %% Count single bb dead-end loops as exit labels +%% [Label|ExitLabels]; +%% _ -> +%% ExitLabels +%% end +%% end, [], Labels ). + +%%============================================================================= +%% Return true if label is an exit label, +%% i.e. its bb has no successors or itself as only successor. +is_exit_label(CFG, Label) -> + case hipe_rtl_cfg:succ(CFG, Label) of + [] -> true; + [Label] -> true; + _ -> false + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%% DATASET FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The dataset is a collection of data about the CFG. +%% It is divided into two parts, NodeInfo and EdgeInfo. +%% The pre-calculation step stores the calculated sets here. + +-record(node_data, {up_exp = none, + down_exp = none, + killed_expr = none, + avail_in = none, + avail_out = none, + antic_in = none, + antic_out = none, + later_in = none, + delete = none}). + +-record(edge_data, {earliest = none, + later = none, + insert = none}). + +%%============================================================================= +%% Creates a node info from a CFG (one entry for each Label). +mk_node_info(Labels) -> + lists:foldl(fun(Label, DataTree) -> + gb_trees:insert(Label, #node_data{}, DataTree) + %%gb_trees:enter(Label, #node_data{}, DataTree) + end, + gb_trees:empty(), Labels). + +%%mk_edge_info(Labels) -> +%% FIXME Should we traverse cfg and initialize edges? +mk_edge_info() -> + gb_trees:empty(). + +%%============================================================================= +%% Get methods +up_exp(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.up_exp. + +down_exp(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.down_exp. + +killed_expr(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.killed_expr. + +avail_in(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.avail_in. + +avail_out(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.avail_out. + +antic_in(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.antic_in. + +antic_out(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.antic_out. + +later_in(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.later_in. + +lookup_later_in(NodeInfo, Label) -> + case gb_trees:lookup(Label, NodeInfo) of + none -> + none; + {value, #node_data{later_in = Data}} -> + Data + end. + +delete(NodeInfo, Label) -> + Data = gb_trees:get(Label, NodeInfo), + Data#node_data.delete. + +earliest(EdgeInfo, Edge) -> + Data = gb_trees:get(Edge, EdgeInfo), + Data#edge_data.earliest. + +-ifdef(LOOKUP_EARLIEST_NEEDED). +lookup_earliest(EdgeInfo, Edge) -> + case gb_trees:lookup(Edge, EdgeInfo) of + none -> + none; + {value, #edge_data{earliest = Data}} -> + Data + end. +-endif. + +later(EdgeInfo, Edge) -> + Data = gb_trees:get(Edge, EdgeInfo), + Data#edge_data.later. + +lookup_later(EdgeInfo, Edge) -> + case gb_trees:lookup(Edge, EdgeInfo) of + none -> + none; + {value, #edge_data{later = Data}} -> + Data + end. + +%% insert(EdgeInfo, Edge) -> +%% case gb_trees:lookup(Edge, EdgeInfo) of +%% none -> +%% exit({?MODULE, insert, "edge info not found"}), +%% none; +%% {value, #edge_data{insert = Data}} -> +%% Data +%% end. + +%%============================================================================= +%% Set methods +set_up_exp(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{up_exp = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{up_exp = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_down_exp(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{down_exp = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{down_exp = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_killed_expr(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{killed_expr = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{killed_expr = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_avail_in(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{avail_in = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{avail_in = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_avail_out(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{avail_out = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{avail_out = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_antic_in(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{antic_in = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{antic_in = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_antic_out(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{antic_out = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{antic_out = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_later_in(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{later_in = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{later_in = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_delete(NodeInfo, Label, Data) -> + NodeData = + case gb_trees:lookup(Label, NodeInfo) of + none -> + #node_data{delete = Data}; + {value, OldNodeData} -> + OldNodeData#node_data{delete = Data} + end, + gb_trees:enter(Label, NodeData, NodeInfo). + +set_earliest(EdgeInfo, Edge, Data) -> + EdgeData = + case gb_trees:lookup(Edge, EdgeInfo) of + none -> + #edge_data{earliest = Data}; + {value, OldEdgeData} -> + OldEdgeData#edge_data{earliest = Data} + end, + gb_trees:enter(Edge, EdgeData, EdgeInfo). + +set_later(EdgeInfo, Edge, Data) -> + EdgeData = + case gb_trees:lookup(Edge, EdgeInfo) of + none -> + #edge_data{later = Data}; + {value, OldEdgeData} -> + OldEdgeData#edge_data{later = Data} + end, + gb_trees:enter(Edge, EdgeData, EdgeInfo). + +%% set_insert(EdgeInfo, Edge, Data) -> +%% EdgeData = +%% case gb_trees:lookup(Edge, EdgeInfo) of +%% none -> +%% #edge_data{insert = Data}; +%% {value, OldEdgeData} -> +%% OldEdgeData#edge_data{insert = Data} +%% end, +%% gb_trees:enter(Edge, EdgeData, EdgeInfo). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%% USE MAP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The use map is a mapping from "use" (which is an rtl register/variable) +%% to a set of expressions (IDs) where that register/variable is used. +%% It is used by calc_killed_expr to know what expressions are affected by +%% a definition. + +%%============================================================================= +%% Creates and calculates the use map for a CFG. +%% It uses ExprMap to lookup the expression IDs. +mk_use_map(CFG, ExprMap) -> + Labels = hipe_rtl_cfg:reverse_postorder(CFG), + NewMap = mk_use_map(gb_trees:empty(), CFG, ExprMap, Labels), + gb_trees:balance(NewMap). + +mk_use_map(Map, _, _, []) -> + Map; +mk_use_map(Map, CFG, ExprMap, [Label|Labels]) -> + Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)), + NewMap = mk_use_map_bb(Map, ExprMap, Code), + mk_use_map(NewMap, CFG, ExprMap, Labels). + +mk_use_map_bb(UseMap, _, []) -> + UseMap; +mk_use_map_bb(UseMap, ExprMap, [Instr|Instrs]) -> + case is_expr(Instr) of + true -> + Uses = hipe_rtl:uses(Instr), + ExprId = expr_map_get_id(ExprMap, expr_clear_dst(Instr)), + NewUseMap = mk_use_map_insert_uses(UseMap, ExprId, Uses), + mk_use_map_bb(NewUseMap, ExprMap, Instrs); + false -> + mk_use_map_bb(UseMap, ExprMap, Instrs) + end. + +%%============================================================================= +%% Worker function for mk_use_map that inserts the expression id for every +%% rtl register the expression uses in a use map. +mk_use_map_insert_uses(Map, _, []) -> + Map; +mk_use_map_insert_uses(Map, Expr, [Use|Uses]) -> + case gb_trees:lookup(Use, Map) of + {value, UseSet} -> + NewUseSet = ?SETS:add_element(Expr, UseSet), + mk_use_map_insert_uses(gb_trees:update(Use, NewUseSet, Map), Expr, Uses); + none -> + UseSet = ?SETS:new(), + NewUseSet = ?SETS:add_element(Expr, UseSet), + mk_use_map_insert_uses(gb_trees:insert(Use, NewUseSet, Map), Expr, Uses) + end. + +%%============================================================================= +%% Gets a set of expressions where the given rtl register is used. +use_map_get_expr_uses(Map, Reg) -> + case gb_trees:lookup(Reg, Map) of + {value, UseSet} -> + UseSet; + none -> + ?SETS:new() + end. + +%%%%%%%%%%%%%%%%%%%%%% EXPRESSION MAP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The expression map is a mapping from expression to +%% (1) Expression Id (Integer used to speed up set operations) +%% (2) List of definitions (labels where the expression is defined and the +%% list of registers or variables defined by an instruction in that label, +%% represented as a tuple {Label, Defines}) +%% (3) The list of replacement registers created for the expression + +%%============================================================================= +%% Creates and calculates the expression map for a CFG. +mk_expr_map(CFG) -> + init_expr_id(), + Labels = hipe_rtl_cfg:reverse_postorder(CFG), + {ExprMap, IdMap} = mk_expr_map(gb_trees:empty(), gb_trees:empty(), + CFG, Labels), + {gb_trees:balance(ExprMap), gb_trees:balance(IdMap)}. + +mk_expr_map(ExprMap, IdMap, _, []) -> + {ExprMap, IdMap}; +mk_expr_map(ExprMap, IdMap, CFG, [Label|Labels]) -> + Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)), + {NewExprMap, NewIdMap} = mk_expr_map_bb(ExprMap, IdMap, Label, Code), + mk_expr_map(NewExprMap, NewIdMap, CFG, Labels). + +mk_expr_map_bb(ExprMap, IdMap, _, []) -> + {ExprMap, IdMap}; +mk_expr_map_bb(ExprMap, IdMap, Label, [Instr|Instrs]) -> + case is_expr(Instr) of + true -> + Expr = expr_clear_dst(Instr), + Defines = hipe_rtl:defines(Instr), + case gb_trees:lookup(Expr, ExprMap) of + {value, {ExprId, DefinesList, ReplRegs}} -> + NewExprMap = gb_trees:update(Expr, {ExprId, + [{Label, Defines}|DefinesList], + ReplRegs}, ExprMap), + mk_expr_map_bb(NewExprMap, IdMap, Label, Instrs); + none -> + NewExprId = new_expr_id(), + NewReplRegs = mk_replacement_regs(Defines), + NewExprMap = gb_trees:insert(Expr, {NewExprId, + [{Label, Defines}], + NewReplRegs}, ExprMap), + NewIdMap = gb_trees:insert(NewExprId, Expr, IdMap), + mk_expr_map_bb(NewExprMap, NewIdMap, Label, Instrs) + end; + false -> + mk_expr_map_bb(ExprMap, IdMap, Label, Instrs) + end. + +%%============================================================================= +%% Creates new temporaries to replace defines in moved expressions. +mk_replacement_regs([]) -> + []; +mk_replacement_regs(Defines) -> + mk_replacement_regs(Defines, []). + +mk_replacement_regs([], NewRegs) -> + lists:reverse(NewRegs); +mk_replacement_regs([Define|Defines], NewRegs) -> + case hipe_rtl:is_reg(Define) of + true -> + NewReg = + case hipe_rtl:reg_is_gcsafe(Define) of + true -> hipe_rtl:mk_new_reg_gcsafe(); + false -> hipe_rtl:mk_new_reg() + end, + mk_replacement_regs(Defines, [NewReg|NewRegs]); + false -> + case hipe_rtl:is_var(Define) of + true -> + mk_replacement_regs(Defines, [hipe_rtl:mk_new_var()|NewRegs]); + false -> + true = hipe_rtl:is_fpreg(Define), + mk_replacement_regs(Defines, [hipe_rtl:mk_new_fpreg()|NewRegs]) + end + end. + +%%============================================================================= +%% Performs a lookup, which returns a tuple +%% {expression ID, list of definitions, list of replacement registers} +expr_map_lookup(Map, Expr) -> + gb_trees:lookup(Expr, Map). + +%%============================================================================= +%% Gets the actual RTL instruction to be generated for insertions of an +%% expression. +expr_map_get_instr(Map, Expr) -> + case gb_trees:lookup(Expr, Map) of + {value, {_, _, Regs}} -> + expr_set_dst(Expr, Regs); + none -> + exit({?MODULE, expr_map_get_instr, "expression missing"}) + end. + +%%============================================================================= +%% Gets expression id. +expr_map_get_id(Map, Expr) -> + case gb_trees:lookup(Expr, Map) of + {value, {ExprId, _, _}} -> + ExprId; + none -> + exit({?MODULE, expr_map_get_instr, "expression missing"}) + end. + +%%============================================================================= +%% Creates an rtl instruction that moves a value +mk_expr_move_instr([Reg], [Define]) -> + case hipe_rtl:is_fpreg(Reg) of + true -> + hipe_rtl:mk_fmove(Reg, Define); + false -> + %% FIXME Check is_var() orelse is_reg() ? + hipe_rtl:mk_move(Reg, Define) + end; +mk_expr_move_instr([_Reg|_Regs] = RegList, Defines) -> + %% FIXME Does this really work? What about floats... + %% (Multiple defines does not seem to be used by any of the + %% instructions considered by rtl_lcm at the moment so this is pretty much + %% untested/unused.) + hipe_rtl:mk_multimove(RegList, Defines); +mk_expr_move_instr(_, []) -> + exit({?MODULE, mk_expr_move_instr, "bad match"}). + +%%============================================================================= +%% Returns a set of all expressions in the code. +%% all_exprs(_CFG, []) -> +%% ?SETS:new(); +%% all_exprs(CFG, [Label|Labels]) -> +%% BB = hipe_rtl_cfg:bb(CFG, Label), +%% Code = hipe_bb:code(BB), +%% ?SETS:union(all_exprs_bb(Code), +%% all_exprs(CFG, Labels)). + +%%============================================================================= +%% Returns a set of expressions in a basic block. +%% all_exprs_bb([]) -> +%% ?SETS:new(); +%% all_exprs_bb([Instr|Instrs]) -> +%% case is_expr(Instr) of +%% true -> +%% Expr = expr_clear_dst(Instr), +%% ExprSet = all_exprs_bb(Instrs), +%% ?SETS:add_element(Expr, ExprSet); +%% false -> +%% all_exprs_bb(Instrs) +%% end. + +%%%%%%%%%%%%%%%%%% EXPRESSION ID -> EXPRESSION MAP %%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Map from expression IDs to expressions. +%%============================================================================= +%% mk_expr_id_map() -> +%% gb_trees:empty(). + +%% expr_id_map_insert(Map, ExprId, Expr) -> +%% gb_trees:insert(ExprId, Expr, Map). + +%% expr_id_map_lookup(Map, ExprId) -> +%% gb_trees:lookup(ExprId, Map). + +%%============================================================================= +%% Given expression id, gets expression. +expr_id_map_get_expr(Map, ExprId) -> + case gb_trees:lookup(ExprId, Map) of + {value, Expr} -> + Expr; + none -> + exit({?MODULE, expr_id_map_get_expr, "expression id missing"}) + end. + +%%============================================================================= +%% Expression ID counter +init_expr_id() -> + put({rtl_lcm,expr_id_count}, 0), + ok. + +-spec new_expr_id() -> non_neg_integer(). +new_expr_id() -> + Obj = {rtl_lcm, expr_id_count}, + V = get(Obj), + put(Obj, V+1), + V. + +%%%%%%%%%%%%%%%%%% EDGE BB (INSERT BETWEEN) MAP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Map from edges to labels. +%% This is used by insert_expr_between to remember what new bbs it has created +%% for insertions on edges, and thus for multiple insertions on the same edge +%% to end up in the same bb. +%%============================================================================= +mk_edge_bb_map() -> + gb_trees:empty(). + +edge_bb_map_insert(Map, Edge, Label) -> + gb_trees:enter(Edge, Label, Map). + +edge_bb_map_lookup(Map, Edge) -> + gb_trees:lookup(Edge, Map). + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PRETTY-PRINTING %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%============================================================================= +%% Prints debug messages. +-ifdef(LCM_DEBUG). + +pp_debug(Str, Args) -> + case ?LCM_DEBUG of + true -> + io:format(standard_io, Str, Args); + false -> + ok + end. + +pp_debug_instr(Instr) -> + case ?LCM_DEBUG of + true -> + hipe_rtl:pp_instr(standard_io, Instr); + false -> + ok + end. + +-else. + +pp_debug(_, _) -> + ok. + +pp_debug_instr(_) -> + ok. + +-endif. %% DEBUG + +%%============================================================================= +%% Pretty-prints the calculated sets for the lazy code motion. +pp_sets(_, _, _, _, _, _, []) -> + ok; +pp_sets(ExprMap, IdMap, NodeInfo, EdgeInfo, AllExpr, CFG, [Label|Labels]) -> + Preds = hipe_rtl_cfg:pred(CFG, Label), + Succs = hipe_rtl_cfg:succ(CFG, Label), + + io:format(standard_io, "Label ~w~n", [Label]), + io:format(standard_io, " Preds: ~w~n", [Preds]), + io:format(standard_io, " Succs: ~w~n", [Succs]), + + case up_exp(NodeInfo, Label) of + none -> ok; + UpExp -> + case ?SETS:size(UpExp) =:= 0 of + false -> + io:format(standard_io, " UEExpr: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(UpExp)); + true -> ok + end + end, + case down_exp(NodeInfo, Label) of + none -> ok; + DownExp -> + case ?SETS:size(DownExp) =:= 0 of + false -> + io:format(standard_io, " DEExpr: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(DownExp)); + true -> ok + end + end, + case killed_expr(NodeInfo, Label) of + none -> ok; + KilledExpr -> + case ?SETS:size(KilledExpr) =:= 0 of + false -> + io:format(standard_io, " ExprKill: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(KilledExpr)); + true -> ok + end + end, + case avail_in(NodeInfo, Label) of + none -> ok; + AvailIn -> + case ?SETS:size(AvailIn) =:= 0 of + false -> + io:format(standard_io, " AvailIn: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(AvailIn)); + true -> ok + end + end, + case avail_out(NodeInfo, Label) of + none -> ok; + AvailOut -> + case ?SETS:size(AvailOut) =:= 0 of + false -> + io:format(standard_io, " AvailOut: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(AvailOut)); + true -> ok + end + end, + case antic_in(NodeInfo, Label) of + none -> ok; + AnticIn -> + case ?SETS:size(AnticIn) =:= 0 of + false -> + io:format(standard_io, " AnticIn: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(AnticIn)); + true -> ok + end + end, + case antic_out(NodeInfo, Label) of + none -> ok; + AnticOut -> + case ?SETS:size(AnticOut) =:= 0 of + false -> + io:format(standard_io, " AnticOut: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(AnticOut)); + true -> ok + end + end, + case later_in(NodeInfo, Label) of + none -> ok; + LaterIn -> + case ?SETS:size(LaterIn) =:= 0 of + false -> + io:format(standard_io, " LaterIn: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(LaterIn)); + true -> ok + end + end, + + pp_earliest(ExprMap, IdMap, EdgeInfo, Label, Succs), + pp_later(ExprMap, IdMap, EdgeInfo, Label, Succs), + + case delete(NodeInfo, Label) of + none -> ok; + Delete -> + case ?SETS:size(Delete) =:= 0 of + false -> + io:format(standard_io, " Delete: ~n", []), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(Delete)); + true -> ok + end + end, + pp_sets(ExprMap, IdMap, NodeInfo, EdgeInfo, AllExpr, CFG, Labels). + +%%============================================================================= +%% Pretty-prints the later set. +pp_later(_, _, _, _, []) -> + ok; +pp_later(ExprMap, IdMap, EdgeInfo, Pred, [Succ|Succs]) -> + case later(EdgeInfo, {Pred, Succ}) of + none -> ok; + Later -> + case ?SETS:size(Later) =:= 0 of + false -> + io:format(standard_io, " Later(~w->~w): ~n", [Pred,Succ]), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(Later)); + true -> ok + end + end, + pp_later(ExprMap, IdMap, EdgeInfo, Pred, Succs). + +%%============================================================================= +%% Pretty-prints the earliest set. +pp_earliest(_, _, _, _, []) -> + ok; +pp_earliest(ExprMap, IdMap, EdgeInfo, Pred, [Succ|Succs]) -> + case earliest(EdgeInfo, {Pred, Succ}) of + none -> ok; + Earliest -> + case ?SETS:size(Earliest) =:= 0 of + false -> + io:format(standard_io, " Earliest(~w->~w): ~n", [Pred,Succ]), + pp_exprs(ExprMap, IdMap, ?SETS:to_list(Earliest)); + true -> ok + end + end, + pp_earliest(ExprMap, IdMap, EdgeInfo, Pred, Succs). + +%%============================================================================= +%% Pretty-prints an expression +pp_expr(ExprMap, IdMap, ExprId) -> + Expr = expr_id_map_get_expr(IdMap, ExprId), + hipe_rtl:pp_instr(standard_io, expr_map_get_instr(ExprMap, Expr)). + +pp_exprs(_, _, []) -> + ok; +pp_exprs(ExprMap, IdMap, [E|Es]) -> + pp_expr(ExprMap, IdMap, E), + pp_exprs(ExprMap, IdMap, Es). |