diff options
Diffstat (limited to 'lib/hipe/ssa/hipe_ssa.inc')
| -rw-r--r-- | lib/hipe/ssa/hipe_ssa.inc | 978 |
1 files changed, 978 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}. + |