aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/ssa
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hipe/ssa')
-rw-r--r--lib/hipe/ssa/hipe_ssa.inc978
-rw-r--r--lib/hipe/ssa/hipe_ssa_const_prop.inc522
-rw-r--r--lib/hipe/ssa/hipe_ssa_copy_prop.inc198
-rw-r--r--lib/hipe/ssa/hipe_ssa_liveness.inc328
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.