The R13B03 release.OTP_R13B03

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.