The R13B03 release.OTP_R13B03

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}.
+