diff options
Diffstat (limited to 'lib/hipe/ssa')
| -rw-r--r-- | lib/hipe/ssa/hipe_ssa.inc | 978 | ||||
| -rw-r--r-- | lib/hipe/ssa/hipe_ssa_const_prop.inc | 522 | ||||
| -rw-r--r-- | lib/hipe/ssa/hipe_ssa_copy_prop.inc | 198 | ||||
| -rw-r--r-- | lib/hipe/ssa/hipe_ssa_liveness.inc | 328 |
4 files changed, 2026 insertions, 0 deletions
diff --git a/lib/hipe/ssa/hipe_ssa.inc b/lib/hipe/ssa/hipe_ssa.inc new file mode 100644 index 0000000000..d15b5ddd56 --- /dev/null +++ b/lib/hipe/ssa/hipe_ssa.inc @@ -0,0 +1,978 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2002-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_ssa.inc +%% Authors : Christoffer Vikstr�m, Daniel Deogun, and Jesper Bengtsson +%% Created : March 2002 +%% Purpose : Provides code which converts the code of a CFG into SSA +%% (Static Single Assignment) form and back. +%% A routine to check for SSA-ness is also provided. +%% +%% Major Modifications: +%% * Feb 2003: Per Gustafsson - added SSA checker. +%% * Aug 2003: Per Gustafsson - added removal of dead code. +%% * Feb 2004: Kostis Sagonas - made it work on RTL level too. +%% * Feb 2004: Tobias Lindahl - re-wrote the unconvert/1 function. +%%---------------------------------------------------------------------- + +-export([convert/1, check/1, unconvert/1, remove_dead_code/1]). + +-include("../main/hipe.hrl"). +-include("../flow/cfg.hrl"). %% needed for the specs +-include("../ssa/hipe_ssa_liveness.inc"). %% needed for dead code removal + +%%---------------------------------------------------------------------- +%% +%% NOTE! When the phi-instructions are placed, it is important that +%% the internal order is preserved. Otherwise the (correct) order: +%% +%% v1 := phi({1, v2}, {2, v11}) +%% v2 := phi({1, v11}, {2, v12}) +%% +%% can become (the incorrect) +%% +%% v2 := phi({1, v11}, {2, v12}) +%% v1 := phi({1, v2}, {2, v11}) +%% +%% that will set v1 to the _new_ value of v2 instead of the old value. +%% +%%---------------------------------------------------------------------- + +-spec convert(#cfg{}) -> #cfg{}. + +convert(CFG) -> + CFG1 = insertNewStartNode(CFG), + + ?opt_start_timer("Dominator Tree construction"), + DomTree = hipe_dominators:domTree_create(CFG1), + ?opt_stop_timer("Dominator Tree construction done"), + + ?opt_start_timer("Dominance Frontier"), + DomFrontier = hipe_dominators:domFrontier_create(CFG1, DomTree), + ?opt_stop_timer("Dominance Frontier done"), + + ?opt_start_timer("placement of Phi-nodes"), + CFG2 = place_phi(CFG1, DomFrontier), + ?opt_stop_timer("placement of Phi-nodes done"), + + ?opt_start_timer("Rename"), + CFG3 = rename(CFG2, DomTree), + ?opt_stop_timer("Rename done"), + + CFG3. + +%%---------------------------------------------------------------------- + +insertNewStartNode(CFG) -> + StartLabel = ?CFG:start_label(CFG), + NewStartLabel = ?CODE:label_name(?CODE:mk_new_label()), + BB = hipe_bb:mk_bb([?CODE:mk_goto(StartLabel)]), + CFG2 = ?CFG:bb_add(CFG, NewStartLabel, BB), + ?CFG:start_label_update(CFG2, NewStartLabel). + + +%%====================================================================== +%% PlacePhi Algorithm +%%====================================================================== + +%%---------------------------------------------------------------------- +%% Procedure : place_phi/2 +%% Purpose : Places phi nodes at appropriate places in the CFG. +%% Arguments : CFG - Control Flow Graph. +%% DF - Dominance Frontier. +%% Returns : CFG with phi functions. +%%---------------------------------------------------------------------- + +place_phi(CFG, DF) -> + AssMap = insertParams(CFG), + AssMap2 = preProcess(CFG, AssMap), + VarList = gb_trees:to_list(AssMap2), + Liveness = ?LIVENESS:analyze(CFG), + variableTraverse(CFG, DF, gb_trees:empty(), gb_trees:empty(), + 0, AssMap2, Liveness, VarList). + +%%---------------------------------------------------------------------- +%% Procedure : insertParams/1 +%% Purpose : Inserts the parameters of the CFG into the AssMap. +%% Arguments : CFG - Control Flow Graph +%% Returns : AssMap - Assignment map. +%%---------------------------------------------------------------------- + +insertParams(CFG) -> + StartLabel = ?CFG:start_label(CFG), + Params = ?CFG:params(CFG), + insertParams(Params, StartLabel, gb_trees:empty()). + +insertParams([Param|T], StartLabel, AssMap) -> + insertParams(T, StartLabel, gb_trees:insert(Param, [StartLabel], AssMap)); +insertParams([], _, AssMap) -> AssMap. + +%%---------------------------------------------------------------------- +%% Procedure : preProcessg/2 +%% Purpose : Creates the assignment map. +%% Arguments : CFG - Control Flow Graph +%% AssMap - Assignment map +%% Returns : AssMap. +%%---------------------------------------------------------------------- + +preProcess(CFG, AssMap) -> + traverseLabels(CFG, ?CFG:labels(CFG), AssMap). + +%%---------------------------------------------------------------------- +%% Procedure : traverseLabels/3 +%% Purpose : Traverses all labels and adds all assignments in the basic +%% block to the assignment map. +%% Arguments : CFG - Control Flow Graph +%% AssMap - Assignment Map +%% Label - A label for a node +%% Returns : AssMap. +%%---------------------------------------------------------------------- + +traverseLabels(CFG, [Label|T], AssMap) -> + Code = get_code_from_label(CFG, Label), + NewVarList = getAssignments(Code), + traverseLabels(CFG, T, updateAssMap(NewVarList, Label, AssMap)); +traverseLabels(_, [], AssMap) -> AssMap. + +%%---------------------------------------------------------------------- +%% Procedure : getAssignments/1 +%% Purpose : Retrieves all assigned variables in a basic block. +%% Arguments : InstrLst - A list of instructions from a basic block. +%% VarList - A list of variables. +%% Returns : VarList. +%% Notes : This function may return a list containing duplicates. +%%---------------------------------------------------------------------- + +getAssignments(InstrList) -> getAssignments(InstrList, []). + +getAssignments([Instr|T], VarList) -> + getAssignments(T, defs_to_rename(Instr) ++ VarList); +getAssignments([], VarList) -> VarList. + +%%---------------------------------------------------------------------- +%% Procedure : updateAssMap/3 +%% Purpose : Updates the assignment map with. Each variable in the AssVar +%% list is inserted with the value Label. +%% Arguments : Label - a label of a node +%% AssVar - a variable that is assigned at Label +%% AssMap - Assignment map. +%% Returns : AssMap. +%%---------------------------------------------------------------------- + +updateAssMap([AssVar|T], Label, AssMap) -> + Lst = getAssMap(AssVar, AssMap), + updateAssMap(T, Label, gb_trees:enter(AssVar, [Label|Lst], AssMap)); +updateAssMap([], _, AssMap) -> AssMap. + +getAssMap(AssVar, AssMap) -> + case gb_trees:lookup(AssVar, AssMap) of + {value, L} -> L; + none -> [] + end. + +%%---------------------------------------------------------------------- +%% Procedure : variableTraverse/7 +%% Purpose : This function traverses all variables and adds phi functions +%% at appropriate nodes. +%% Arguments : CFG - Control Flow Graph +%% DFMap - Dominance Frontier Map +%% HasAlready - A map of nodes which already have phi functions +%% Work - +%% IterCount - Counter of how many iterations have been done +%% AssMap - Assignment map +%% VarLst - Variable list that is traversed +%% Returns : CFG. +%%---------------------------------------------------------------------- + +variableTraverse(CFG, DFMap, HasAlready, Work, + IterCount, AssMap, Liveness, [{Var,_}|VarLst]) -> + IterCount2 = IterCount + 1, + DefLst = getAssMap(Var, AssMap), + {Work2, WorkLst2} = workListBuilder(DefLst, Work, [], IterCount2), + {CFG2, HasAlready2, Work3} = doWork(CFG, DFMap, HasAlready, + Work2, IterCount2, WorkLst2, + Var, Liveness), + variableTraverse(CFG2, DFMap, HasAlready2, Work3, + IterCount2, AssMap, Liveness, VarLst); +variableTraverse(CFG, _, _, _, _, _, _, []) -> CFG. + +%%---------------------------------------------------------------------- +%% Procedure : workListBuilder/4 +%% Purpose : Builds the worklist that the algorithm is working on. +%% Arguments : Work - +%% WorkLst - The worklist that is worked through +%% IterCount - Counter of how many itterations that has been done +%% Node - A node in the CFG +%% Returns : +%%---------------------------------------------------------------------- + +workListBuilder([Node|T], Work, WorkLst, IterCount) -> + case getCount(Node, Work) of + 0 -> + Work2 = gb_trees:enter(Node, IterCount, Work), + workListBuilder(T, Work2, [Node|WorkLst], IterCount); + _ -> + Work2 = gb_trees:enter(Node, IterCount, Work), + workListBuilder(T, Work2, [Node|WorkLst], IterCount) + end; +workListBuilder([], Work, WorkLst, _IterCount) -> + {Work, WorkLst}. + +getCount(Key, Dict) -> + case gb_trees:lookup(Key, Dict) of + {value, V} -> V; + none -> 0 + end. + +%%---------------------------------------------------------------------- +%% Procedure : doWork/7 +%% Purpose : This procedure works itself through the worklist and checks +%% if a node needs any phi functions. +%% Arguments : CFG - Control Flow Graph +%% DFMap - Dominance Frontier Map +%% HasAlready - A map of nodes that already have phi functions +%% Work - +%% IterCount - Counter of how many iterations have taken place +%% WorkLst - The worklist that is worked through +%% Var - Variable +%% Returns : {CFG, HasAlready, Work} +%%---------------------------------------------------------------------- + +doWork(CFG, DFMap, HasAlready, Work, IterCount, + [Node|WorkLst], Var, Liveness) -> + DFofX = hipe_dominators:domFrontier_get(Node, DFMap), + {CFG2, HasAlready2, Work2, WorkLst2} = + checkPhiNeeds(CFG, DFofX, HasAlready, Work, + IterCount, WorkLst, Var, Liveness), + doWork(CFG2, DFMap, HasAlready2, Work2, + IterCount, WorkLst2, Var, Liveness); +doWork(CFG, _, HasAlready, Work, _, [], _, _) -> + {CFG, HasAlready, Work}. + +%%---------------------------------------------------------------------- +%% Procedure : checkPhiNeeds/7 +%% Purpose : This function checks if a node needs a phi function and adds +%% one if its needed. +%% Arguments : CFG - Control Flow Graph +%% DFofX - Dominance Frontier of a node +%% HasAlready - A map of nodes that already have phi functions +%% Work - +%% IterCount - Counter of how many iterations have taken place +%% WorkLst - The worklist that is worked through +%% Var - Variable +%% Returns : {CFG, HasAlready, Work, WorkLst} +%%---------------------------------------------------------------------- + +checkPhiNeeds(CFG, [Node|DFofX], HasAlready, Work, + IterCount, WorkLst, Var, Liveness) -> + case getCount(Node, HasAlready) < IterCount of + true -> + LiveIn = ?LIVENESS:livein(Liveness, Node), + case lists:member(Var, LiveIn) of + true -> + CFG2 = insertPhiCode(CFG, Node, Var), + HasAlready2 = gb_trees:enter(Node, IterCount, HasAlready), + case getCount(Node, Work) < IterCount of + true -> + Work2 = gb_trees:enter(Node, IterCount, Work), + WorkLst2 = [Node|WorkLst], + checkPhiNeeds(CFG2, DFofX, HasAlready2, Work2, + IterCount, WorkLst2, Var, Liveness); + false -> + checkPhiNeeds(CFG2, DFofX, HasAlready2, Work, + IterCount, WorkLst, Var, Liveness) + end; + false -> + checkPhiNeeds(CFG, DFofX, HasAlready, Work, IterCount, + WorkLst, Var, Liveness) + end; + false -> + checkPhiNeeds(CFG, DFofX, HasAlready, Work, IterCount, + WorkLst, Var, Liveness) + end; +checkPhiNeeds(CFG, [], HasAlready, Work, _, WorkLst, _, _) -> + {CFG, HasAlready, Work, WorkLst}. + +%%---------------------------------------------------------------------- +%% Procedure : insertPhiCode/3 +%% Purpose : +%% Arguments : CFG - Control Flow Graph +%% Node - A node +%% Var - A variable +%% Returns : CFG +%%---------------------------------------------------------------------- + +insertPhiCode(CFG, Node, Var) -> + BB = ?CFG:bb(CFG, Node), + Phi = ?CODE:mk_phi(Var), + Code = [Phi | hipe_bb:code(BB)], + ?CFG:bb_add(CFG, Node, hipe_bb:code_update(BB, Code)). + + +%%====================================================================== +%% SSA Renaming pass +%%====================================================================== + +%%---------------------------------------------------------------------- +%% Procedure : rename/2 +%% Purpose : Renames all the variables in the CFG according to the SSA +%% conversion algorithm. +%% Arguments : CFG - The CFG being translated. +%% DomTree - The dominator tree of the CFG. +%% Returns : A CFG where all variables are renamed. +%%---------------------------------------------------------------------- + +rename(CFG, DomTree) -> + %% Reset the appropriate variable index so that we start from low + %% variable numbers again + reset_var_indx(), + {CFG2,Current} = insertRenamedParams(CFG), + rename(CFG2, ?CFG:start_label(CFG2), DomTree, Current). + +rename(CFG, Node, DomTree, Current) -> + BB = ?CFG:bb(CFG, Node), + Statements = hipe_bb:code(BB), + {Statements2,Current2} = renameVars(Statements, Current), + CFG1 = ?CFG:bb_add(CFG, Node, hipe_bb:code_update(BB, Statements2)), + Succ = ?CFG:succ(CFG1, Node), + CFG2 = updateSuccPhi(Succ, Node, CFG1, Current2), + Children = hipe_dominators:domTree_getChildren(Node, DomTree), + childrenRename(Children, CFG2, DomTree, Current2). + +%%---------------------------------------------------------------------- +%% Procedure : childrenRename/5 +%% Purpose : Renames all the nodes in a list according to the SSA +%% conversion algorithm. +%% Arguments : ChildList - the list of nodes being renamed +%% CFG - the CFG that the children are a part of +%% DomTree - The dominator tree for the CFG +%% Current - the current index of all variables encountered +%% Returns : CFG +%%---------------------------------------------------------------------- + +childrenRename([Child|Children], CFG, DomTree, Current) -> + CFG2 = rename(CFG, Child, DomTree, Current), + childrenRename(Children, CFG2, DomTree, Current); +childrenRename([], CFG, _, _) -> + CFG. + +%%---------------------------------------------------------------------- +%% Procedure : renameVars/3 +%% Purpose : Renames the variables in basic block +%% Arguments : Statements - the basic block +%% Current - the current index of all variables encountered +%% Returns : {Statements,Current} +%%---------------------------------------------------------------------- + +renameVars(Statements, Current) -> + renameVars(Statements, Current, []). + +renameVars([Statement|Statements], Current, Result) -> + Statement2 = renameUses(Statement, Current), + {Statement3,Current2} = renameDefs(Statement2, Current), + renameVars(Statements, Current2, [Statement3|Result]); +renameVars([], Current, Result) -> + {lists:reverse(Result),Current}. + +%%---------------------------------------------------------------------- +%% Procedure : renameUses/2 +%% Purpose : Renames all the uses of a variable in a statement. +%% Arguments : Statement - the statement being renamed. +%% Current - the current index of all variables encountered. +%% Returns : Statement +%%---------------------------------------------------------------------- + +renameUses(Statement, Current) -> + case ?CODE:is_phi(Statement) of + true -> Statement; + false -> VarList = uses_to_rename(Statement), + updateStatementUses(VarList, Statement, Current) + end. + +%%---------------------------------------------------------------------- +%% Procedure : updateStatementUses/3 +%% Purpose : Traverses the variable list and renames all the instances +%% of a variable in the Statement uses to its current value. +%% Arguments : VarList - the list of variables being updated. +%% Statement - the statement being updated. +%% Current - the current index of all variables encountered. +%% Returns : An updated statement. +%%---------------------------------------------------------------------- + +updateStatementUses(Vars, Statement, Current) -> + Substs = [{Var,gb_trees:get(Var, Current)} || Var <- Vars], + ?CODE:subst_uses(Substs, Statement). + +%%---------------------------------------------------------------------- +%% Procedure : renameDefs/3 +%% Purpose : Renames all the definitons in Statement. +%% Arguments : Statement - the statement where the definitions are being +%% renamed. +%% Current - the current index of all variables encountered. +%% Returns : Statement +%%---------------------------------------------------------------------- + +renameDefs(Statement, Current) -> + VarList = defs_to_rename(Statement), + updateStatementDefs(VarList, Statement, Current). + +%%---------------------------------------------------------------------- +%% Procedure : updateStatementDefs/4 +%% Purpose : traverses a variable list and exchanges all instances of +%% the variable in the statements definitions by its current +%% value. +%% Arguments : VariableList - the list of varibles being renamed +%% Statement - the statement whos definitions are being changed +%% Current - the current index of all variables encountered +%% Returns : {Statement, Current} +%% Notes : Per Gustafsson: +%% I changed this function to update the statement only when +%% all substitutions are found. +%%---------------------------------------------------------------------- + +updateStatementDefs(Vars, Statement, Current) -> + updateStatementDefs(Vars, Statement, Current, []). + +updateStatementDefs([Var|Vars], Statement, Current, Acc) -> + {NewVar,Current2} = updateIndices(Current, Var), + updateStatementDefs(Vars, Statement, Current2, [{Var,NewVar}|Acc]); +updateStatementDefs([], Statement, Current, Acc) -> + Statement2 = ?CODE:subst_defines(Acc, Statement), + {Statement2,Current}. + +%%---------------------------------------------------------------------- +%% Procedure : updateIndices/3 +%% Purpose : This function is used for updating the Current hash table +%% and for getting a new variable/fp variable/register. +%% Arguments : Current - Hash table containg the current index for a +%% particular variable. +%% Variable - The variable that is used as key in the hash table. +%% Returns : A two-tuple containing the new variable and Current. +%%---------------------------------------------------------------------- + +updateIndices(Current, Variable) -> + case ?CODE:is_var(Variable) of + true -> + NewVar = ?CODE:mk_new_var(), + {NewVar,gb_trees:enter(Variable, NewVar, Current)}; + false -> + case is_fp_temp(Variable) of + true -> + NewFVar = mk_new_fp_temp(), + {NewFVar,gb_trees:enter(Variable, NewFVar, Current)}; + false -> + NewReg = ?CODE:mk_new_reg(), + {NewReg,gb_trees:enter(Variable, NewReg, Current)} + end + end. + +%%---------------------------------------------------------------------- +%% Procedure : updateSuccPhi/4 +%% Purpose : This function is used for updating phi functions in a +%% particular node's successors. That is, the function +%% traverses the successor list of a node and updates the +%% arguments in the phi function calls. +%% Arguments : Succ - A successor to the node Parent. +%% T - The remainder of the successor list +%% Parent - The parent of the node Succ +%% CFG - Control Flow Graph +%% Current - Hash table containg the current index for a +%% particular variable +%% Returns : An updated version of the CFG +%%---------------------------------------------------------------------- + +updateSuccPhi([Succ|T], Parent, CFG, Current) -> + CFG2 = updatePhi(Succ, Parent, CFG, Current), + updateSuccPhi(T, Parent, CFG2, Current); +updateSuccPhi([], _, CFG, _) -> + CFG. + +%%---------------------------------------------------------------------- +%% Procedure : updatePhi/4 +%% Purpose : This function prepares for an update of a phi function call. +%% That is, if a statement contains a phi function call +%% then the number of predecessors are computed and the index +%% of the parent in the predecessor list is used for computing +%% which variable in the argument list of the phi function call +%% that need to be updated. +%% Arguments : Node - A node in the CFG +%% Parent - The parent of the node Node in the dominator tree +%% CFG - Control Flow Graph +%% Current - Hash table containg the current index for a +%% particular variable +%% Returns : An updated version of the CFG +%%---------------------------------------------------------------------- + +updatePhi(Node, Parent, CFG, Current) -> + BB = ?CFG:bb(CFG, Node), + case hipe_bb:code(BB) of + [Code|_] = Statements -> + case ?CODE:is_phi(Code) of + true -> + Code2 = updateCode(Statements, Parent, Current), + ?CFG:bb_add(CFG, Node, hipe_bb:code_update(BB, Code2)); + _ -> + CFG + end; + _ -> + CFG + end. + +%%---------------------------------------------------------------------- +%% Procedure : updateCode/3 +%% Purpose : This function updates a statement that contains a phi +%% function, i.e. it changes the arguments in the phi +%% function to their correct names. +%% Arguments : Code - A list of code +%% Pred - A predecessor of the node containing the +%% phi-function +%% Current - Hash table containing the current index for a +%% particular variable +%% Returns : A list of Code +%%---------------------------------------------------------------------- + +updateCode(Code, Pred, Current) -> + updateCode(Code, Pred, Current, []). + +updateCode([Stat|Stats] = Statements, Pred, Current, Result) -> + case ?CODE:is_phi(Stat) of + true -> + Var = ?CODE:phi_id(Stat), + Result2 = case gb_trees:lookup(Var, Current) of + none -> + [Stat|Result]; + {value,Var2} -> + Stat2 = ?CODE:phi_enter_pred(Stat, Pred, Var2), + [Stat2|Result] + end, + updateCode(Stats, Pred, Current, Result2); + _ -> + Result ++ Statements + end. + +%%---------------------------------------------------------------------- +%% Procedure : insertRenamedParams/1 +%% Purpose : Inserts the parameters of the CFG into the working hashmaps. +%% Arguments : CFG - the target control flow graph. +%% Returns : {CFG,Current} +%%---------------------------------------------------------------------- + +insertRenamedParams(CFG) -> + Params = ?CFG:params(CFG), + %% Current - the current variable we are working on. + {Current,Params2} = insertRenamedParams(Params, gb_trees:empty(), []), + CFG2 = ?CFG:params_update(CFG, Params2), + {CFG2,Current}. + +insertRenamedParams([Param|Params], Current, Result) -> + {Var,Current2} = updateIndices(Current, Param), + insertRenamedParams(Params, Current2, [Var|Result]); +insertRenamedParams([], Current, Result) -> + {Current,lists:reverse(Result)}. + + +%%====================================================================== +%% SSA Checker +%%====================================================================== + +%% +%% @doc Checks the control flow graph CFG of a function for SSA-ness. +%% More specifically, it checks that all variables in the CFG are only +%% defined once and that all uses of each variable in the function are +%% dominated by a define. If a variable does not abide by these rules, +%% a warning message will be printed on stdout. +%% +-spec check(#cfg{}) -> 'ok'. + +check(CFG) -> + Labels = ?CFG:labels(CFG), + VarTree = traverse_labels(Labels, CFG), + DomTree = hipe_dominators:domTree_create(CFG), + test_uses(Labels, VarTree, DomTree, CFG). + +%% +%% @doc Traverses all the labels in a CFG. +%% +traverse_labels(Labels, CFG) -> + VarTree = add_args(?CFG:params(CFG)), + traverse_labels(Labels, VarTree, CFG). + +traverse_labels([Label|Rest], VarTree, CFG) -> + Code = get_code_from_label(CFG, Label), + NewVarTree = traverse_code(Code, VarTree, Label), + traverse_labels(Rest, NewVarTree, CFG); +traverse_labels([], VarTree, _CFG) -> + VarTree. + +%% +%% @doc Traverses the code in a basic block. +%% +traverse_code([Instr|Rest], VarTree, Label) -> + Defined = defs_to_rename(Instr), + NewVarTree = add_to_var_tree(Defined, VarTree, Instr, Label), + traverse_code(Rest, NewVarTree, Label); +traverse_code([], VarTree, _) -> + VarTree. + +%% +%% @doc +%% Adds a variable to the variable tree if the variable is defined. +%% The entry in the variable tree will have the variable as key and a +%% two tuple consisting of a list of Instructions and a list of labels +%% where the variable is defined. If a variable is defined a second +%% time a warning message to this effect is printed on stdout. +%% +add_to_var_tree([Var|Rest], VarTree, Instr, Label) -> + NewVarTree = + case gb_trees:lookup(Var, VarTree) of + {value,{OldInstr,OldLabel}} -> + ?WARNING_MSG("Variable: ~w defined a second time\n"++ + "in Instr: ~w\n"++ + "at Label: ~w\n"++ + "variable was first defined at Label(s) ~w\n"++ + "in Instr(s): ~w\n -> non SSA form\n", + [Var,Instr,Label,OldLabel,OldInstr]), + gb_trees:update(Var, {[Instr|OldInstr],[Label|OldLabel]}, VarTree); + none -> + gb_trees:insert(Var, {[Instr],[Label]}, VarTree) + end, + add_to_var_tree(Rest, NewVarTree, Instr, Label); +add_to_var_tree([], VarTree, _, _) -> + VarTree. + +%% +%% @doc Adds the argument of a function to the VarTree. +%% They are defined at Label 0. +%% +add_args(Args) -> + add_args(Args, gb_trees:empty()). + +add_args([Arg|Rest], VarTree) -> + add_args(Rest, gb_trees:insert(Arg, {[argument_variable],[0]}, VarTree)); +add_args([], VarTree) -> + VarTree. + +%% +%% The functions below test that a use is dominated by a corresponding def. +%% + +%% +%% This function is analogous to traverse_labels. +%% +test_uses([Label|Rest], VarTree, DomTree,CFG) -> + Code = get_code_from_label(CFG, Label), + test_code(Code, VarTree, Label, DomTree, CFG, []), + test_uses(Rest, VarTree, DomTree, CFG); +test_uses([], _VarTree, _DomTree, _CFG) -> + ok. + +%% +%% This function is analogous to traverse_code. +%% +test_code([Instr|Instrs], VarTree, Label, DomTree, CFG, Old) -> + case ?CODE:is_phi(Instr) of + true -> + ArgList = ?CODE:phi_arglist(Instr), + case ArgList of + [_Arg] -> + ?WARNING_MSG("Phi with only one source at BB with label ~w:\n", + [Label]), + %% case ?CODE of + %% hipe_rtl -> ?CODE:pp_block(get_code_from_label(CFG, Label)); + %% _ -> ok + %% end, + ok; + [_|_] -> ok + end, + lists:foreach(fun ({Pred,Var}) -> + def_doms_use([Var], VarTree, Pred, DomTree, + get_code_from_label(CFG,Pred)) + end, ArgList); + false -> + Uses = uses_to_rename(Instr), + def_doms_use(Uses, VarTree, Label, DomTree, Old) + end, + test_code(Instrs, VarTree, Label, DomTree, CFG, [Instr|Old]); +test_code([], _VarTree, _Label, _DomTree, _CFG, _Old) -> + ok. + +get_code_from_label(CFG, Label) -> + case ?CFG:bb(CFG,Label) of + not_found -> + ?error_msg("Basic block with label ~w was not found\n", [Label]); + %% ?EXIT('Detected serious problem in SSA form'); + BB -> + hipe_bb:code(BB) + end. + +%% +%% This function checks whether a use is dominated by a def. +%% There are five different cases: +%% 1. A use of an argument register. This use is dominated by the def. +%% 2. Use and Def in same basic block if Use comes first this will +%% lead to a warning message, otherwise it is ok. +%% 3. The deinition is in a basic block that dominates the basic block +%% of the use. This is ok. +%% 4. The definition is in a basic block that does not dominate the use. +%% This will result in a warning message being printed. +%% 5. A use without any definition. This will result in a warning message +%% being printed. +%% +def_doms_use([Var|Vars], VarTree, Label, DomTree, Old) -> + case gb_trees:lookup(Var, VarTree) of + {value,{_,[DefLabel|_]}} -> + case DefLabel of + 0 -> + ok; + Label -> + Fun = fun(X) -> Defs = defs_to_rename(X), + lists:any(fun(Y) -> Var == Y end, Defs) + end, + case lists:any(Fun, Old) of + true -> + ok; + false -> + ?WARNING_MSG("Variable : ~w used before definition in bb: ~w\n", + [Var,Label]) + end; + _ -> + case hipe_dominators:domTree_dominates(DefLabel, Label, DomTree) of + true -> + ok; + false -> + ?WARNING_MSG("Definition does not dominate use for variable: ~w "++ + "at label: ~w (definition label: ~w)\n", + [Var, Label, DefLabel]) + end + end; + none -> + ?WARNING_MSG("Use with no definition of variable: ~w at label: ~w\n", + [Var, Label]) + end, + def_doms_use(Vars, VarTree, Label, DomTree, Old); +def_doms_use([], _VarTree, _Label, _DomTree, _Old) -> + ok. + + +%%====================================================================== +%% SSA Un-Converter +%%====================================================================== + +%%---------------------------------------------------------------------- +%% Procedure : unconvert/2 +%% Purpose : Removes all phi functions and propagates all +%% assignments up to the appropriate predecessors. +%% Arguments : CFG - Control Flow Graph +%% Node - A node in the CFG +%% Returns : CFG +%% Note : The call to remove_trivial_bbs is needed so that moves, +%% which are introduced in new basic blocks as part of the +%% un-conversion, are merged with the basic blocks of their +%% predecessors, if possible. +%%---------------------------------------------------------------------- + +-spec unconvert(#cfg{}) -> #cfg{}. + +unconvert(CFG) -> + ?CFG:remove_trivial_bbs(unconvert(?CFG:reverse_postorder(CFG), CFG)). + +unconvert([Node|Nodes], CFG) -> + BB = ?CFG:bb(CFG, Node), + Code = hipe_bb:code(BB), + {Phis,Code2} = getPhiFuncts(Code, []), + case Phis of + [] -> + unconvert(Nodes, CFG); + _ -> + BB2 = hipe_bb:code_update(BB, Code2), + CFG2 = ?CFG:bb_add(CFG, Node, BB2), + Pred = ?CFG:pred(CFG2, Node), + PredMoveMap = get_moves(Pred, Phis), + CFG3 = insert_move_bbs(PredMoveMap, Node, CFG2), + unconvert(Nodes, CFG3) + end; +unconvert([], CFG) -> + CFG. + +%%---------------------------------------------------------------------- +%% Procedure : get_moves/2 and /3 +%% Purpose : Find the moves that corresponds to phi-instructions of +%% a block. Try to merge incoming edges to avoid duplicate +%% blocks. +%% Arguments : Preds - The predecessors to this block. +%% Phis - The phi instructions that used to start this block. +%% Returns : [{ListOfMoves, [Preds]}] +%%---------------------------------------------------------------------- + +get_moves(Preds, Phis) -> + get_moves(Preds, Phis, gb_trees:empty()). + +get_moves([Pred|Left], Phis, Map)-> + Moves = get_moves_from_phis(Pred, Phis, []), + NewMap = + case gb_trees:lookup(Moves, Map) of + none -> gb_trees:insert(Moves, [Pred], Map); + {value,List} -> gb_trees:update(Moves, [Pred|List], Map) + end, + get_moves(Left, Phis, NewMap); +get_moves([], _Phis, Map) -> + gb_trees:to_list(Map). + +%%---------------------------------------------------------------------- +%% Procedure : get_moves_from_phis/3 +%% Purpose : Find all the moves that should be done in the edge +%% coming in from Pred. +%% Arguments : Pred - The predecessor +%% Phis - Reverse list of phi instructions. +%% Returns : [{Dst,Src}] representing the move instructions; +%% ORDERING IS SIGNIFICANT! +%%---------------------------------------------------------------------- + +get_moves_from_phis(Pred, [Phi|Left], Acc) -> + Dst = ?CODE:phi_dst(Phi), + Src = ?CODE:phi_arg(Phi, Pred), + NewAcc = [{Dst, Src}|Acc], + get_moves_from_phis(Pred, Left, NewAcc); +get_moves_from_phis(_Pred, [], Acc) -> + Acc. + +%%---------------------------------------------------------------------- +%% Procedure : insert_move_bbs/3 +%% Purpose : Create the bbs that contains the moves. +%% Arguments : Ordset - The move instruction tuples {Dst, Src} +%% Preds - The predecessors that needs the moves in Ordset +%% Label - The original label that contained the phis. +%% Cfg - The current cfg +%% Returns : The new Cfg. +%%---------------------------------------------------------------------- + +insert_move_bbs([{Ordset,Preds}|Left], Label, Cfg) -> + Code = create_moves(Ordset, []) ++ [?CODE:mk_goto(Label)], + BB = hipe_bb:mk_bb(Code), + NewLabel = ?CODE:label_name(?CODE:mk_new_label()), + NewCfg1 = ?CFG:bb_add(Cfg, NewLabel, BB), + NewCfg2 = lists:foldl(fun(X, Acc) -> + ?CFG:redirect(Acc, X, Label, NewLabel) + end, + NewCfg1, Preds), + insert_move_bbs(Left, Label, NewCfg2); +insert_move_bbs([], _Label, Cfg) -> + Cfg. + +create_moves([{X,X}|Left], Acc) -> + create_moves(Left, Acc); +create_moves([{Dst,Src}|Left], Acc) -> + create_moves(Left, [makePhiMove(Dst, Src)|Acc]); +create_moves([], Acc) -> + %% NOTE: ORDERING IS SIGNIFICANT! + lists:reverse(Acc). + +%%---------------------------------------------------------------------- +%% Procedure : getPhiFuncts/2 +%% Purpose : This function returns the list of phi-functions from a +%% list of intermediate code instructions. +%% Arguments : +%% List - A list of Code +%% Result - Accumulative parameter to store the result +%% Returns : Reverse list of the phi instructions. ORDERING IS SIGNIFICANT! +%%---------------------------------------------------------------------- + +getPhiFuncts([I|T] = List, Result) -> + case ?CODE:is_phi(I) of + true -> + getPhiFuncts(T, [I|Result]); + false -> + {Result,List} + end; +getPhiFuncts([], Result) -> + {Result,[]}. + + +%%====================================================================== +%% Dead Code Elimination on SSA form +%%====================================================================== + +-spec remove_dead_code(#cfg{}) -> #cfg{}. + +remove_dead_code(CFG) -> + Lbls = ?CFG:reverse_postorder(CFG), + Liveness = ssa_liveness__analyze(CFG), + case do_lbls(Lbls, CFG, Liveness, false) of + {CFG1,true} -> + remove_dead_code(CFG1); + {CFG1,false} -> + CFG1 + end. + +do_lbls([Lbl|Rest], CFG, Liveness, Changed) -> + LiveOut = gb_sets:from_list(ssa_liveness__liveout(Liveness, Lbl)), + BB = ?CFG:bb(CFG, Lbl), + Code = hipe_bb:code(BB), + {NewCode,NewChanged} = do_code(lists:reverse(Code), LiveOut, Changed, []), + NewBB = hipe_bb:code_update(BB, NewCode), + NewCFG = ?CFG:bb_add(CFG, Lbl, NewBB), + do_lbls(Rest, NewCFG, Liveness, NewChanged); +do_lbls([], CFG, _Liveness, Changed) -> + {CFG,Changed}. + +do_code([Instr|Instrs], LiveOut, Changed, Acc) -> + Def = ?CODE:defines(Instr), + Use = ?CODE:uses(Instr), + DefSet = gb_sets:from_list(Def), + UseSet = gb_sets:from_list(Use), + LiveIn = gb_sets:union(gb_sets:difference(LiveOut, DefSet), UseSet), + case gb_sets:is_empty(gb_sets:intersection(DefSet, LiveOut)) of + false -> + do_code(Instrs, LiveIn, Changed, [Instr|Acc]); + true -> + case ?CODE:is_safe(Instr) of + true -> + case ?CODE:is_call(Instr) of + true -> + case ?CODE:call_continuation(Instr) of + [] -> + do_code(Instrs, LiveOut, true, Acc); + SuccLblName -> + NewInstr = ?CODE:mk_goto(SuccLblName), + do_code(Instrs, LiveOut, true, [NewInstr|Acc]) + end; + false -> + do_code(Instrs, LiveOut, true, Acc) + end; + false -> %% not a safe instruction - cannot be removed + case ?CODE:is_call(Instr) of + true -> + case ?CODE:call_dstlist(Instr) of + [] -> %% result was not used anyway; no change + do_code(Instrs, LiveIn, Changed, [Instr|Acc]); + [_Dst] -> %% remove the unused assignment to call's destination + NewInstr = ?CODE:call_dstlist_update(Instr, []), + do_code(Instrs, LiveIn, true, [NewInstr|Acc]); + [_|_] -> %% calls with multiple dests are left untouched + do_code(Instrs, LiveIn, Changed, [Instr|Acc]) + end; + false -> + do_code(Instrs, LiveIn, Changed, [Instr|Acc]) + end + end + end; +do_code([], _LiveOut, Changed, Acc) -> + {Acc,Changed}. + diff --git a/lib/hipe/ssa/hipe_ssa_const_prop.inc b/lib/hipe/ssa/hipe_ssa_const_prop.inc new file mode 100644 index 0000000000..2fce384197 --- /dev/null +++ b/lib/hipe/ssa/hipe_ssa_const_prop.inc @@ -0,0 +1,522 @@ +%% -*- Erlang -*- +%% -*- 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_ssa_const_prop.inc +%% Author : Kostis Sagonas <[email protected]> +%% Description : Supporting routines for sparse conditional constant +%% propagation on SSA form. +%% +%% Created : 21 June 2004 by Kostis Sagonas <[email protected]> +%%----------------------------------------------------------------------------- + +%%----------------------------------------------------------------------------- +%% Procedure : propagate/1 +%% Purpose : Perform sparse conditional constant propagation on a +%% control flow graph +%% Arguments : CFG - The cfg to work on +%% Returns : A new cfg. +%%----------------------------------------------------------------------------- + +-spec propagate(#cfg{}) -> #cfg{}. + +propagate(CFG) -> + Environment = create_env(CFG), + StartEdge = {?CFG:start_label(CFG), ?CFG:start_label(CFG)}, + NewEnvironment = scc([StartEdge], [], Environment), + NewCFG = update_cfg(NewEnvironment), + NewCFG. + +%%----------------------------------------------------------------------------- +%% Procedure : visit_expressions/2 & visit_expressions/4 +%% Purpose : visit each instruction in a list of instructions. +%% Arguments : Instructions - the list of instructions to visit +%% Environment - have a guess. +%% FlowWork - list of destination part of flowgraph edges +%% from the visited instructions +%% SSAWork - resulting ssa-edges from visited instrs. +%% Returns : {FlowWorkList, SSAWorkList, Environment} +%%----------------------------------------------------------------------------- + +visit_expressions(Instructions, Environment) -> + visit_expressions(Instructions, Environment, [], []). + +visit_expressions([], Environment, FlowWork, SSAWork) -> + {FlowWork, SSAWork, Environment}; +visit_expressions([Inst | Insts], Environment, FlowWork, SSAWork) -> + {MoreFlowWork, MoreSSAWork, Environment1} + = visit_expression(Inst, Environment), + FlowWork1 = MoreFlowWork ++ FlowWork, + SSAWork1 = MoreSSAWork ++ SSAWork, + visit_expressions(Insts, Environment1, FlowWork1, SSAWork1). + +%%----------------------------------------------------------------------------- +%% The environment record: Shared between incarnations of SCCP. +%%----------------------------------------------------------------------------- + +-record(env, {cfg :: #cfg{}, + executable_flags = gb_sets:empty() :: gb_set(), + handled_blocks = gb_sets:empty() :: gb_set(), + lattice_values = gb_trees:empty() :: gb_tree(), + ssa_edges = gb_trees:empty() :: gb_tree() + }). + +create_env(CFG) -> + #env{cfg = CFG, + executable_flags = gb_sets:empty(), + handled_blocks = gb_sets:empty(), + lattice_values = initialize_lattice(CFG), + ssa_edges = initialize_ssa_edges(CFG) + }. + +env__cfg(#env{cfg=CFG}) -> CFG. +env__executable_flags(#env{executable_flags=Flags}) -> Flags. +env__lattice_values(#env{lattice_values=Values}) -> Values. +env__ssa_edges(#env{ssa_edges=Edges}) -> Edges. + +%%----------------------------------------------------------------------------- +%% Procedure : initialize_lattice/1 +%% Purpose : Compute the initial value-lattice for the CFG +%% Arguments : CFG a control flow graph +%% Returns : a value-latice (gb_tree) +%%----------------------------------------------------------------------------- + +initialize_lattice(CFG) -> + Lattice = gb_trees:empty(), + Parameters = ?CFG:params(CFG), + Inserter = fun(Parameter, Tree) -> + gb_trees:insert(Parameter, bottom, Tree) + end, + lists:foldl(Inserter, Lattice, Parameters). + +%%----------------------------------------------------------------------------- +%% Procedure : initialize_ssa_edges/1 +%% Purpose : Compute the SSA edges in the CFG. SSA edges are used to map +%% the definition of a value to its uses. +%% Arguments : CFG - the cfg +%% Returns : A gb_tree of values (variables & registers) to +%% lists of {Node, Instruction} pairs. +%%----------------------------------------------------------------------------- + +initialize_ssa_edges(CFG) -> + IterateNodes = + fun(Node, Tree1) -> + IterateInstructions = + fun(Instruction, Tree2) -> + IterateArguments = + fun(Argument, Tree3) -> + Data = gb_trees:lookup(Argument, Tree3), + NewEdge = {Node, Instruction}, + case Data of + none -> + %% insert assumes key is not present + gb_trees:insert(Argument, [NewEdge], Tree3); + {value, EdgeList} -> + %% update assumes key is present + gb_trees:update(Argument, [NewEdge|EdgeList], Tree3) + end + end, + Arguments = ?CODE:uses(Instruction), + lists:foldl(IterateArguments, Tree2, Arguments) + end, + Instructions = hipe_bb:code(?CFG:bb(CFG, Node)), + lists:foldl(IterateInstructions, Tree1, Instructions) + end, + NodeList = ?CFG:labels(CFG), + lists:foldl(IterateNodes, gb_trees:empty(), NodeList). + +%%----------------------------------------------------------------------------- +%% Procedure : scc/3 +%% Purpose : Do the symbolic execution of a cfg and compute the resulting +%% value-lattice, and reachability information (Environment). +%% This is the main loop that does a fixpoint computation of the +%% lattice-values for each variable and register. +%% Arguments : FlowWorkList - work list of control-flow edges +%% SSAWorkList - work list of ssa-edges +%% Environment - the environment that have been computed so far. +%% Returns : The environment after execution +%%----------------------------------------------------------------------------- + +scc([], [], Environment) -> + Environment; +%% Take an element from the FlowWorkList and process it +scc([{Source,Destination} | FlowWorkList], SSAWorkList, Environment) -> + case executable({Source, Destination}, Environment) of + true -> + scc(FlowWorkList, SSAWorkList, Environment); + false -> + Environment1 = mark_as_executable({Source,Destination}, Environment), + Code = extract_code(Destination, Environment), + {Environment2, Code1, ExtraSSA} = + visit_phi_nodes(Code, Destination, Environment1, []), + case handled(Destination, Environment2) of + true -> + scc(FlowWorkList, ExtraSSA ++ SSAWorkList, Environment2); + false -> + {MoreFlowDests, MoreSSAWork, Environment3} = + visit_expressions(Code1, Environment2), + MoreFlowWork = [{Destination, Node} || Node <- MoreFlowDests], + FlowWorkList1 = MoreFlowWork ++ FlowWorkList, + SSAWorkList1 = ExtraSSA ++ MoreSSAWork ++ SSAWorkList, + Environment4 = mark_as_handled(Destination, Environment3), + scc(FlowWorkList1, SSAWorkList1, Environment4) + end + end; +%% Take an element from the SSAWorkList and process it +scc([], [{Node, Instruction} | SSAWorkList], Environment) -> + case reachable(Node, Environment) of + true -> + case ?CODE:is_phi(Instruction) of + true -> + {Environment1, MoreSSA} = visit_phi(Instruction, Node, Environment), + scc([], MoreSSA ++ SSAWorkList, Environment1); + false -> + {MoreFlowDests, MoreSSAWork, Environment1} = + visit_expression(Instruction, Environment), + SSAWorkList1 = MoreSSAWork ++ SSAWorkList, + MoreFlowWork = [{Node, Destination} || Destination<-MoreFlowDests], + scc(MoreFlowWork, SSAWorkList1, Environment1) + end; + false -> + scc([], SSAWorkList, Environment) + end. + +%%----------------------------------------------------------------------------- +%% Procedure : update_cfg/1 +%% Purpose : Transforms the cfg into something more pleasant. +%% Here the mapping of variables & registers to lattice-values is +%% used to actually change the code. +%% Arguments : Environment - in which everything happens. +%% Returns : A new CFG. +%%----------------------------------------------------------------------------- + +update_cfg(Environment) -> + NodeList = get_nodelist(Environment), + CFG1 = update_nodes(NodeList, Environment), + %% why not hipe_???_ssa:remove_dead_code ? + CFG2 = ?CFG:remove_unreachable_code(CFG1), + CFG2. + +%%----------------------------------------------------------------------------- +%% Procedure : update_nodes/2 +%% Purpose : loop over all nodes in a list of nodes, ignoring any +%% non-reachable node. +%% Arguments : NodeList - the list of nodes. +%% Environment - in which everything happens. +%% Returns : a new cfg. +%%----------------------------------------------------------------------------- + +update_nodes([], Environment) -> + env__cfg(Environment); +update_nodes([Node | NodeList], Environment) -> + NewEnvironment = + case reachable(Node, Environment) of + true -> + Instructions = extract_code(Node, Environment), + Updater = fun(Instruction) -> + update_instruction(Instruction, Environment) + end, + NewInstructions = lists:flatmap(Updater, Instructions), + update_code(Node, NewInstructions, Environment); + false -> + Environment + end, + update_nodes(NodeList, NewEnvironment). + +%%----------------------------------------------------------------------------- +%% Procedure : update_code/3 +%% Purpose : Insert a list of new instructions into the cfg in the +%% environment +%% Arguments : Node - name of the bb whose instructions we replace. +%% NewInstructions - The list of new instructions +%% Env - The environment +%% Returns : A new environment +%%----------------------------------------------------------------------------- + +update_code(Node, NewInstructions, Environment) -> + CFG = env__cfg(Environment), + BB = ?CFG:bb(CFG, Node), + OrderedInstructions = put_phi_nodes_first(NewInstructions), + NewBB = hipe_bb:code_update(BB, OrderedInstructions), + NewCFG = ?CFG:bb_add(CFG, Node, NewBB), + Environment#env{cfg = NewCFG}. + +%%----------------------------------------------------------------------------- +%% Procedure : put_phi_nodes_first/1 +%% Purpose : Move all phi-instructions to the beginning of the basic block. +%% Arguments : Instructions - The list of instructions +%% Returns : A list of instructions where the phi-nodes are first. +%%----------------------------------------------------------------------------- + +put_phi_nodes_first(Instructions) -> + {PhiInstructions, OtherInstructions} = + partition(fun(X) -> ?CODE:is_phi(X) end, Instructions), + PhiInstructions ++ OtherInstructions. + +%%----------------------------------------------------------------------------- + +partition(Function, List) -> + partition(Function, List, [], []). + +partition(_Function, [], True, False) -> + {lists:reverse(True), lists:reverse(False)}; + +partition(Function, [Hd | Tail], True, False) -> + case Function(Hd) of + true -> + partition(Function, Tail, [Hd | True], False); + false -> + partition(Function, Tail, True, [Hd | False]) + end. + +%%----------------------------------------------------------------------------- +%% Procedure : visit_phi_nodes/4 +%% Purpose : visit all the phi-nodes in a bb and return the list of +%% remaining instructions, new ssa-edges and a new environment. +%% Arguments : [Inst|Insts] - The list of instructions in the bb +%% Node - Name of the current node. +%% Environment - the environment +%% SSAWork - the ssawork found so far. +%% Returns : {Environment, Instruction list, SSAWorkList} +%%----------------------------------------------------------------------------- + +visit_phi_nodes([], CurrentNode, _Environment, _SSAWork) -> + ?EXIT({"~w: visit_phi_nodes/4 Basic block contains no code", + ?MODULE, CurrentNode}); +visit_phi_nodes(Is = [Inst | Insts], Node, Environment, SSAWork) -> + case ?CODE:is_phi(Inst) of + true -> + {Environment1, NewSSA} = visit_phi(Inst, Node, Environment), + visit_phi_nodes(Insts, Node, Environment1, NewSSA ++ SSAWork); + false -> + {Environment, Is, SSAWork} + end. + +%%----------------------------------------------------------------------------- +%% Procedure : visit_phi/3 +%% Purpose : visit a phi-node +%% Arguments : PhiInstruction- The instruction +%% CurrentNode - Name of the current node. +%% Environment - the environment +%% Returns : {NewEnvironment, SSAWork} +%%----------------------------------------------------------------------------- + +visit_phi(PhiInstruction, CurrentNode, Environment) -> + ArgumentList = ?CODE:phi_arglist(PhiInstruction), + Value = get_phi_value(ArgumentList, CurrentNode, Environment, top), + Name = ?CODE:phi_dst(PhiInstruction), + {Environment1, SSAWork} = update_lattice_value({Name, Value}, Environment), + {Environment1, SSAWork}. + +%%----------------------------------------------------------------------------- +%% Procedure : get_phi_value/4 +%% Purpose : compute the result of a phi-function, taking care to ignore +%% edges that are not yet executable. +%% Arguments : ArgList - the list of arguments {Node, Value pair} +%% CurrentNode - the current node +%% Environment - well... +%% CurrentValue - the meet of the relevant already processed values +%% Returns : Integer, top or bottom +%%----------------------------------------------------------------------------- + +%% the arglist contains {predecessor, variable} elements. Remember +%% to be optimistic in this part, hopefully, topvalues will fall down +%% to become constants. Hence topvalues are more or less ignored here. +get_phi_value([], _CurrentNode, _Environment, CurrentValue) -> + CurrentValue; +get_phi_value([{PredecessorNode, Variable}| ArgList], + CurrentNode, + Environment, + CurrentValue) -> + case executable({PredecessorNode, CurrentNode}, Environment) of + true -> + NewValue = lookup_lattice_value(Variable, Environment), + case NewValue of + bottom -> + bottom; + top -> + get_phi_value(ArgList, CurrentNode, Environment, CurrentValue); + _ -> + case CurrentValue of + top -> + get_phi_value(ArgList, CurrentNode, Environment, NewValue); + _ -> + case (NewValue =:= CurrentValue) of + true -> + get_phi_value(ArgList, CurrentNode, Environment, NewValue); + false -> %% two different constants. + bottom + end + end + end; + false -> %% non-executable transitions don't affect the value. + get_phi_value(ArgList, CurrentNode, Environment, CurrentValue) + end. + +%%------------------------------ environment ---------------------------------- + +reachable(Node, Environment) -> + Predecessors = predecessors(Node, Environment), + Executable = fun(Pred) -> executable({Pred, Node}, Environment) end, + lists:any(Executable, Predecessors). + +%%----------------------------------------------------------------------------- + +mark_as_executable(Edge, Environment) -> + ExecutableFlags = env__executable_flags(Environment), + ExecutableFlags1 = gb_sets:add(Edge, ExecutableFlags), + Environment#env{executable_flags = ExecutableFlags1}. + +%%----------------------------------------------------------------------------- + +mark_as_handled(Node, Environment = #env{handled_blocks=Handled}) -> + NewHandled = gb_sets:add_element(Node, Handled), + Environment#env{handled_blocks=NewHandled}. + +handled(Node, #env{handled_blocks=Handled}) -> + gb_sets:is_element(Node, Handled). + +%%----------------------------------------------------------------------------- + +extract_code(Node, Environment) -> + CFG = env__cfg(Environment), + case ?CFG:bb(CFG, Node) of + not_found -> ?WARNING_MSG("Could not find label ~w.\n", [Node]), + []; + BB -> hipe_bb:code(BB) + end. + +%%----------------------------------------------------------------------------- + +predecessors(Node, Environment) -> + CFG = env__cfg(Environment), + ?CFG:pred(CFG, Node). + +%%----------------------------------------------------------------------------- + +executable(Edge, Environment) -> + ExecutableFlags = env__executable_flags(Environment), + gb_sets:is_member(Edge, ExecutableFlags). + +%%----------------------------------------------------------------------------- + +update_lattice_value({[], _NewValue}, Environment) -> + {Environment, []}; +update_lattice_value({Names, NewValue}, Environment) when is_list(Names) -> + Update = + fun(Dst, {Env, SSA}) -> + {NewEnv, NewSSA} = + update_lattice_value({Dst, NewValue}, Env), + {NewEnv, SSA ++ NewSSA} + end, + lists:foldl(Update, {Environment, []}, Names); +%% update_lattice_value({Name, {Res, N, Z, C, V} }, _) -> +%% ?EXIT({"inserting dumt grejs", {Name, {Res, N, Z, C, V} } }); +update_lattice_value({Name, NewValue}, Environment) -> + LatticeValues = env__lattice_values(Environment), + {LatticeValues1, SSAWork} = + case gb_trees:lookup(Name, LatticeValues) of + none -> + {gb_trees:insert(Name, NewValue, LatticeValues), + lookup_ssa_edges(Name, Environment)}; + {value, NewValue} -> + {LatticeValues, []}; + {value, _} -> + {gb_trees:update(Name, NewValue, LatticeValues), + lookup_ssa_edges(Name, Environment)} + end, + {Environment#env{lattice_values = LatticeValues1}, SSAWork}. + +%%----------------------------------------------------------------------------- + +lookup_ssa_edges(Variable, Environment) -> + SSAEdges = env__ssa_edges(Environment), + case gb_trees:lookup(Variable, SSAEdges) of + {value, X} -> + X; + _ -> % Unused variable + [] + end. + +%%----------------------------------------------------------------------------- + +get_nodelist(Environment) -> + CFG = env__cfg(Environment), + ?CFG:labels(CFG). + +%%----------------------------------------------------------------------------- + +-ifdef(DEBUG). + +%%----------------------------------------------------------------------------- +%%---------------------------------- DEBUG ------------------------------------ + +error(Text) -> + error(Text, []). + +error(Text, Data) -> + io:format("Internal compiler error in ~w\n",[?MODULE]), + io:format(Text, Data), + io:format("\n\n"), + halt(). + +%%----------------------------------------------------------------------------- + +print_environment(Environment) -> + io:format("============================================================\n"), + io:format("Executable flags: "), + print_executable_flags(env__executable_flags(Environment)), + io:format("Lattice values --->\n"), + print_lattice_values(env__lattice_values(Environment)), + io:format("SSA edges --->\n"), + print_ssa_edges(env__ssa_edges(Environment)), + io:format("============================================================\n"). + +%%----------------------------------------------------------------------------- + +print_executable_flags(ExecutableFlags) -> + ListOfFlags = gb_sets:to_list(ExecutableFlags), + Printer = fun ({Source, Destination}) -> + io:format("(~w, ~w), ", [Source, Destination]) end, + lists:foreach(Printer, ListOfFlags), + io:format("()\n"). + +%%----------------------------------------------------------------------------- + +print_lattice_values(LatticeValues) -> + ListOfLatticeValues = gb_trees:to_list(LatticeValues), + Printer = fun ({Key, Value}) -> + io:format("~w = ~w\n", [Key, Value]) end, + lists:foreach(Printer, ListOfLatticeValues). + +%%----------------------------------------------------------------------------- + +print_ssa_edges(SSAEdges) -> + ListOfSSAEdges = gb_trees:to_list(SSAEdges), + Printer = fun ({Key, Value}) -> + io:format("~w: ~w\n", [Key, Value]) end, + lists:foreach(Printer, ListOfSSAEdges). + +%%----------------------------------------------------------------------------- + +-endif. %% DEBUG + +%%----------------------------------------------------------------------------- + diff --git a/lib/hipe/ssa/hipe_ssa_copy_prop.inc b/lib/hipe/ssa/hipe_ssa_copy_prop.inc new file mode 100644 index 0000000000..311940a1fc --- /dev/null +++ b/lib/hipe/ssa/hipe_ssa_copy_prop.inc @@ -0,0 +1,198 @@ +%%% -*- Erlang -*- +%%% -*- erlang-indent-level: 2 -*- +%%% +%%% %CopyrightBegin% +%%% +%%% Copyright Ericsson AB 2003-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_ssa_copy_prop.inc +%%% Author : Tobias Lindahl <[email protected]> +%%% Description : Copy propagation on SSA form. +%%% +%%% Created : 4 Apr 2003 by Tobias Lindahl <[email protected]> +%%%------------------------------------------------------------------- + +-export([cfg/1]). + +%%-------------------------------------------------------------------- +%% Two passes through the code visiting the blocks in reverse +%% postorder. The first pass binds all destinations of copying moves +%% to the sources, and the second propagates the copies and removes +%% the copying moves. +%% +%% Problem: +%% Since phi-nodes are implemented as instructions they are not +%% atomic. If we are not careful we can get the situation (after propagation): +%% +%% v0 = phi(v0, v2) +%% v1 = phi(v0, v3) +%% ^^ +%% where the underlined v0 really corresponds to the v0 before the first +%% phi-instruction. +%% +%% Solution: +%% * Find all dependencies between the uses of a phi-instruction to +%% the destination of any earlier phi-instruction in the same phi-node; +%% * Keep the copying move that defines the variable used in the +%% latter phi-instruction; and +%% * Do not propagate the copy into the phi-instruction +%% +%%-------------------------------------------------------------------- + +-spec cfg(#cfg{}) -> #cfg{}. + +cfg(Cfg) -> + Labels = ?cfg:reverse_postorder(Cfg), + {Info,PhiDep} = analyse(Labels, Cfg, gb_trees:empty(), gb_trees:empty()), + rewrite(Labels, Cfg, Info, PhiDep). + +analyse([Label|Left], Cfg, Info, PhiDep) -> + BB = ?cfg:bb(Cfg, Label), + Code = hipe_bb:code(BB), + NewPhiDep = get_phi_dep(Code, gb_sets:empty(), PhiDep), + NewInfo = analyse_code(Code, Info), + analyse(Left, Cfg, NewInfo, NewPhiDep); +analyse([], _Cfg, Info, PhiDep) -> + {Info,PhiDep}. + +get_phi_dep([I|Left], Defined, Dep) -> + case ?code:is_phi(I) of + true -> + Use = ?code:uses(I), + [Def] = ?code:defines(I), + NewDep = add_dep(Use, Defined, Dep), + get_phi_dep(Left, gb_sets:insert(Def, Defined), NewDep); + false -> + Dep + end; +get_phi_dep([], _Defined, Dep) -> + Dep. + +add_dep([Use|Left], Defined, Dep) -> + case gb_trees:lookup(Use, Dep) of + none -> + add_dep(Left, Defined, gb_trees:insert(Use, Defined, Dep)); + {value, Set} -> + NewSet = gb_sets:union(Defined, Set), + add_dep(Left, Defined, gb_trees:enter(Use, NewSet, Dep)) + end; +add_dep([], _Defined, Dep) -> + Dep. + +has_dep(Use, Def, Dep) -> + case gb_trees:lookup(Use, Dep) of + none -> + false; + {value, Set} -> + gb_sets:is_member(Def, Set) + end. + +analyse_code([I|Left], Info) -> + case ?code:is_move(I) of + true -> + NewInfo = get_info_move(I, Info), + analyse_code(Left, NewInfo); + false -> + analyse_code(Left, Info) + end; +analyse_code([], Info) -> + Info. + +get_info_move(I, Info) -> + case ?code:uses(I) of + [] -> %% Constant. + Info; + [Src] -> + add_binding(?code:defines(I), Src, Info) + end. + +rewrite([Label|Left], Cfg, Info, PhiDep) -> + BB = ?cfg:bb(Cfg, Label), + Code = hipe_bb:code(BB), + NewCode = rewrite_code(Code, Info, PhiDep, []), + NewBB = hipe_bb:code_update(BB, NewCode), + rewrite(Left, ?cfg:bb_add(Cfg, Label, NewBB), Info, PhiDep); +rewrite([], Cfg, _Info, _PhiDep) -> + Cfg. + +rewrite_code([I|Left], Info, PhiDep, Acc) -> + case ?code:is_move(I) of + true -> + Fun = fun(X, Y) -> ?code:mk_move(X, Y) end, + NewI = rewrite_move(I, Fun, Info, PhiDep), + rewrite_code(Left, Info, PhiDep, NewI++Acc); + false -> + NewI = rewrite_instr(I, Info, PhiDep), + rewrite_code(Left, Info, PhiDep, [NewI|Acc]) + end; +rewrite_code([], _Info, _PhiDep, Acc) -> + lists:reverse(Acc). + +rewrite_move(I, Fun, Info, PhiDep) -> + case ?code:uses(I) of + [] ->%% Constant move. Keep it! + [I]; + _ -> + Dst = hd(?code:defines(I)), + case gb_trees:lookup(Dst, Info) of + {value, Root} -> + case has_dep(Dst, Root, PhiDep) of + true -> %% Must keep the copying move! + [Fun(Dst, Root)]; + false -> + [] + end; + none -> + [] + end + end. + +rewrite_instr(I, Info, PhiDep) -> + rewrite_instr0(I, ?code:uses(I), Info, PhiDep, []). + +rewrite_instr0(I, [Key|Left], Info, PhiDep, UpdateInfo) -> + case gb_trees:lookup(Key, Info) of + none -> + rewrite_instr0(I, Left, Info, PhiDep, UpdateInfo); + {value, Root} -> + case gb_trees:lookup(Key, Info) of + {value, Root} -> + case has_dep(Key, Root, PhiDep) of + true -> %% Must keep Key! + rewrite_instr0(I, Left, Info, PhiDep, UpdateInfo); + false -> + rewrite_instr0(I, Left, Info, PhiDep, [{Key, Root}|UpdateInfo]) + end; + _ -> + rewrite_instr0(I, Left, Info, PhiDep, UpdateInfo) + end + end; +rewrite_instr0(I, [], _Info, _PhiDep, UpdateInfo) -> + ?code:subst(UpdateInfo, I). + +add_binding([Key|Left], Val, Info) -> + %% Make sure the key is bound to the end of any copy-chains. + NewInfo = + case gb_trees:lookup(Val, Info) of + {value, NewVal} -> + gb_trees:insert(Key, NewVal, Info); + none -> + gb_trees:insert(Key, Val, Info) + end, + add_binding(Left, Val, NewInfo); +add_binding([], _, Info) -> + Info. diff --git a/lib/hipe/ssa/hipe_ssa_liveness.inc b/lib/hipe/ssa/hipe_ssa_liveness.inc new file mode 100644 index 0000000000..05c8a88059 --- /dev/null +++ b/lib/hipe/ssa/hipe_ssa_liveness.inc @@ -0,0 +1,328 @@ +%% -*- Erlang -*- +%% -*- 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% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% GENERIC MODULE TO PERFORM LIVENESS ANALYSIS ON SSA FORM +%% +%% Exports: +%% ~~~~~~~ +%% analyze(CFG) - returns a liveness analysis of CFG. +%% liveout(Liveness, Label) - returns the list of variables that are +%% live at exit from basic block named Label. +%% livein(Liveness, Label) - returns the list of variables that are +%% live on entry to the basic block named Label. +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%% Uncomment the following if this is ever needed as an independent module +%% +-ifdef(LIVENESS_NEEDED). +-export([ssa_liveness__analyze/1, + ssa_liveness__livein/2]). +%% ssa_liveness__livein/3], +%% ssa_liveness__liveout/2]). +-endif. +%% -ifdef(DEBUG_LIVENESS). +%% -export([pp_liveness/1]). +%% -endif. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Interface functions that MUST be implemented in the supporting files +%% +%% In the CFG file: +%% ---------------- +%% - bb(CFG, L) -> BasicBlock, extract a basic block from a cfg. +%% - postorder(CFG) -> [Labels], the labels of the cfg in postorder +%% - succ(CFG, L) -> [Labels], +%% - function(CFG) -> {M,F,A} +%% +%% In the CODE file: +%% ----------------- +%% - uses(Instr) -> +%% - defines(Instr) -> +%% - is_phi(Instr) -> Boolean +%% - phi_arglist(Instr) -> [{Pred, Var}] + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The generic liveness analysis on SSA form +%% +ssa_liveness__analyze(CFG) -> + PO = ?CFG:postorder(CFG), + InitLiveness = liveness_init(init(PO, CFG)), + merry_go_around(PO, InitLiveness). + +%% +%% The fixpoint iteration +%% + +merry_go_around(Labels, Liveness) -> + case doit_once(Labels, Liveness) of + {fixpoint, NewLiveness} -> + NewLiveness; + {value, NewLiveness} -> + merry_go_around(Labels, NewLiveness) + end. + +%% +%% One iteration +%% + +doit_once(Labels, Liveness) -> + doit_once(Labels, Liveness, true). + +doit_once([], Liveness, FixPoint) -> + if FixPoint -> {fixpoint, Liveness}; + true -> {value, Liveness} + end; +doit_once([L|Ls], Liveness, FixPoint) -> + LiveOut = join_livein(Liveness, L), + NewLiveness = update_liveout(L, LiveOut, Liveness), + Kill = set_subtract(LiveOut, kill(L, NewLiveness)), + LiveIn = set_union(Kill, gen(L, NewLiveness)), + case update_livein(L, LiveIn, NewLiveness) of + fixpoint -> doit_once(Ls, NewLiveness, FixPoint); + {value, NewLiveness1} -> doit_once(Ls, NewLiveness1, false) + end. + +%% +%% updates liveness for a basic block +%% + +update_livein(Label, NewLiveIn, Liveness) -> + {GKD, LiveIn, LiveOut, Succ} = liveness_lookup(Label, Liveness), + case LiveIn of + NewLiveIn -> + fixpoint; + _ -> + {value, liveness_update(Label, {GKD,NewLiveIn,LiveOut,Succ}, Liveness)} + end. + +update_liveout(Label, NewLiveOut, Liveness) -> + {GKD, LiveIn, _LiveOut, Succ} = liveness_lookup(Label, Liveness), + liveness_update(Label, {GKD,LiveIn,NewLiveOut,Succ}, Liveness). + +%% +%% Join live in to get the new live out. +%% + +join_livein(Liveness, L) -> + Succ = successors(L, Liveness), + case Succ of + [] -> % special case if no successors + gb_sets:from_list(liveout_no_succ()); + _ -> + join_livein1(L, Succ, Liveness) + end. + +join_livein1(Pred, Labels, Liveness) -> + join_livein1(Pred, Labels, Liveness, new_set()). + +join_livein1(_Pred, [], _Liveness, Live) -> + Live; +join_livein1(Pred, [L|Ls], Liveness, Live) -> + OldLivein = livein_set(Liveness, L, Pred), + NewLive = set_union(OldLivein, Live), + join_livein1(Pred, Ls, Liveness, NewLive). + + +ssa_liveness__liveout(Liveness, L) -> + {_GKD, _LiveIn, LiveOut, Successors} = liveness_lookup(L, Liveness), + case Successors of + [] -> % special case if no successors + liveout_no_succ(); + _ -> + set_to_list(LiveOut) + end. + +-ifdef(LIVENESS_NEEDED). +ssa_liveness__livein(Liveness, L) -> + set_to_list(livein_set(Liveness, L)). + +%% ssa_liveness__livein(Liveness, L, Pred) -> +%% set_to_list(livein_set(Liveness, L, Pred)). + +livein_set(Liveness, L) -> + {{_Gen,_Kill,{TotalDirGen, _DirGen}}, LiveIn, _LiveOut, _Successors} = + liveness_lookup(L, Liveness), + set_union(TotalDirGen, LiveIn). +-endif. + +livein_set(Liveness, L, Pred) -> + {{_Gen,_Kill,{_TotalDirGen, DirGen}}, LiveIn, _LiveOut, _Successors} = + liveness_lookup(L, Liveness), + case gb_trees:lookup(Pred, DirGen) of + none -> + LiveIn; + {value, LiveInFromPred} -> + set_union(LiveInFromPred, LiveIn) + end. + +successors(L, Liveness) -> + {_GKD, _LiveIn, _LiveOut, Successors} = liveness_lookup(L, Liveness), + Successors. + +kill(L, Liveness) -> + {{_Gen,Kill,_DirGen},_LiveIn,_LiveOut,_Successors} = + liveness_lookup(L, Liveness), + Kill. + +gen(L, Liveness) -> + {{Gen,_Kill,_DirGen},_LiveIn,_LiveOut,_Successors} = + liveness_lookup(L, Liveness), + Gen. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% init returns a list of: {Label, {{Gen, Kill}, LiveIn, Successors}} +%% - Label is the name of the basic block. +%% - Gen is the set of varables that are used by this block. +%% - Kill is the set of varables that are defined by this block. +%% - LiveIn is the set of variables that are alive at entry to the +%% block (initially empty). +%% - Successors is a list of the successors to the block. + +init([], _) -> + []; +init([L|Ls], CFG) -> + BB = ?CFG:bb(CFG, L), + Code = hipe_bb:code(BB), + Succ = ?CFG:succ(CFG, L), + {Gen, Kill} = make_bb_transfer(Code, Succ), + DirectedGen = get_directed_gen(Code), + [{L, {{Gen, Kill, DirectedGen}, new_set(), new_set(), Succ}} + | init(Ls, CFG)]. + +make_bb_transfer([], _Succ) -> + {new_set(), new_set()}; % {Gen, Kill} +make_bb_transfer([I|Is], Succ) -> + {Gen, Kill} = make_bb_transfer(Is, Succ), + case ?CODE:is_phi(I) of + true -> + InstrKill = set_from_list(?CODE:defines(I)), + Gen1 = set_subtract(Gen, InstrKill), + Kill1 = set_union(Kill, InstrKill), + {Gen1, Kill1}; + false -> + InstrGen = set_from_list(?CODE:uses(I)), + InstrKill = set_from_list(?CODE:defines(I)), + Gen1 = set_subtract(Gen, InstrKill), + Gen2 = set_union(Gen1, InstrGen), + Kill1 = set_union(Kill, InstrKill), + Kill2 = set_subtract(Kill1, InstrGen), + {Gen2, Kill2} + end. + +get_directed_gen(Code) -> + Map = get_directed_gen_1(Code), + TotalGen = lists:foldl(fun({_Pred, Gen}, Acc) -> + set_union(Gen, Acc) + end, new_set(), gb_trees:to_list(Map)), + {TotalGen, Map}. + +get_directed_gen_1([I|Left])-> + case ?CODE:is_phi(I) of + false -> + gb_trees:empty(); + true -> + Map = get_directed_gen_1(Left), + ArgList = ?CODE:phi_arglist(I), + lists:foldl(fun update_directed_gen/2, Map, ArgList) + end. + +update_directed_gen({Pred, Var}, Map)-> + case gb_trees:lookup(Pred, Map) of + none -> gb_trees:insert(Pred, set_from_list([Var]), Map); + {value, Set} -> gb_trees:update(Pred, set_add(Var, Set), Map) + end. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% liveness +%% + +liveness_init(List) -> + liveness_init1(List, gb_trees:empty()). + +liveness_init1([{Label, Info}|Left], Map) -> + liveness_init1(Left, gb_trees:insert(Label, Info, Map)); +liveness_init1([], Map) -> + Map. + +liveness_lookup(Label, Map) -> + {value, Info} = gb_trees:lookup(Label, Map), + Info. + +liveness_update(Label, NewInfo, Map) -> + gb_trees:update(Label, NewInfo, Map). + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Sets +%% + +new_set() -> + gb_sets:empty(). + +set_union(S1, S2) -> + gb_sets:union(S1, S2). + +set_subtract(S1, S2) -> + gb_sets:subtract(S1, S2). + +set_from_list(List) -> + gb_sets:from_list(List). + +set_to_list(Set) -> + gb_sets:to_list(Set). + +set_add(Var, Set) -> + gb_sets:add(Var, Set). + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Pretty printer +%% + +-ifdef(DEBUG_LIVENESS). + +pp_liveness(CFG) -> + io:format("Liveness for ~p:\n", [?CFG:function(CGF)]), + Liveness = analyze(CFG), + RevPostorder = lists:reverse(?CFG:postorder(CFG)), + Edges = [{X, Y} || X <- RevPostorder, Y <- ?CFG:succ(CFG, X)], + pp_liveness_edges(Edges, Liveness). + +pp_liveness_edges([{From, To}|Left], Liveness)-> + LiveIn = livein(Liveness, To, From), + io:format("Label ~w -> Label ~w: ~p\n", [From, To, LiveIn]), + LiveOut = liveout(Liveness, From), + io:format("Total live out from Label ~w: ~p\n", [From, LiveOut]), + pp_liveness_edges(Left, Liveness); +pp_liveness_edges([], _Liveness) -> + ok. + +-endif. |