The R13B03 release.OTP_R13B03

9 files changed, 2549 insertions, 0 deletions

diff --git a/lib/hipe/flow/Makefile b/lib/hipe/flow/Makefile
new file mode 100644
index 0000000000..5b9d0b7582
--- /dev/null
+++ b/lib/hipe/flow/Makefile
@@ -0,0 +1,105 @@
+#
+# %CopyrightBegin%
+# 
+# Copyright Ericsson AB 2001-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%
+#
+
+ifndef EBIN
+EBIN = ../ebin
+endif
+
+ifndef DOCS
+DOCS = ../doc
+endif
+
+include $(ERL_TOP)/make/target.mk
+include $(ERL_TOP)/make/$(TARGET)/otp.mk
+
+# ----------------------------------------------------
+# Application version
+# ----------------------------------------------------
+include ../vsn.mk
+VSN=$(HIPE_VSN)
+
+# ----------------------------------------------------
+# Release directory specification
+# ----------------------------------------------------
+RELSYSDIR = $(RELEASE_PATH)/lib/hipe-$(VSN)
+
+# ----------------------------------------------------
+# Target Specs
+# ----------------------------------------------------
+MODULES = hipe_bb hipe_dominators hipe_gen_cfg
+
+
+HRL_FILES=
+INC_FILES= cfg.inc ebb.inc liveness.inc
+ERL_FILES= $(MODULES:%=%.erl)
+TARGET_FILES= $(MODULES:%=$(EBIN)/%.$(EMULATOR))
+DOC_FILES= $(MODULES:%=$(DOCS)/%.html)
+
+# APP_FILE= 
+# APP_SRC= $(APP_FILE).src
+# APP_TARGET= $(EBIN)/$(APP_FILE)
+#
+# APPUP_FILE= 
+# APPUP_SRC= $(APPUP_FILE).src
+# APPUP_TARGET= $(EBIN)/$(APPUP_FILE)
+
+# ----------------------------------------------------
+# FLAGS
+# ----------------------------------------------------
+
+include ../native.mk
+
+ERL_COMPILE_FLAGS += +warn_exported_vars +warn_missing_spec +warn_untyped_record
+
+# ----------------------------------------------------
+# Targets
+# ----------------------------------------------------
+
+debug opt: $(TARGET_FILES) 
+
+docs: $(DOC_FILES)
+
+clean:
+	rm -f $(TARGET_FILES)
+	rm -f core
+
+$(DOCS)/%.html:%.erl
+	erl -noshell -run edoc_run file '"$<"' '[{dir, "$(DOCS)"}]' -s init stop
+
+# ----------------------------------------------------
+# Special Build Targets
+# ----------------------------------------------------
+
+
+
+# ----------------------------------------------------
+# Release Target
+# ---------------------------------------------------- 
+include $(ERL_TOP)/make/otp_release_targets.mk
+
+release_spec: opt
+	$(INSTALL_DIR) $(RELSYSDIR)/flow
+	$(INSTALL_DATA) $(ERL_FILES) $(HRL_FILES) $(INC_FILES) $(RELSYSDIR)/flow
+	$(INSTALL_DIR) $(RELSYSDIR)/ebin
+	$(INSTALL_DATA) $(TARGET_FILES) $(RELSYSDIR)/ebin
+
+release_docs_spec:
+
+$(EBIN)/hipe_bb.beam: hipe_bb.hrl
+$(EBIN)/hipe_gen_cfg.beam: cfg.hrl cfg.inc ../main/hipe.hrl
diff --git a/lib/hipe/flow/cfg.hrl b/lib/hipe/flow/cfg.hrl
new file mode 100644
index 0000000000..62f47a707a
--- /dev/null
+++ b/lib/hipe/flow/cfg.hrl
@@ -0,0 +1,53 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2007-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    : cfg.hrl
+%% Author  : Kostis Sagonas <[email protected]>
+%% Purpose : Contains typed record declarations for the CFG data structures
+%%
+%% $Id$
+%%============================================================================
+
+-type cfg_lbl() :: non_neg_integer().
+
+%%
+%% This is supposed to be local but appears here for the time being
+%% just so that it is used below
+%%
+-record(cfg_info, {'fun'         :: mfa(),
+                   start_label   :: cfg_lbl(),
+                   is_closure    :: boolean(),
+                   closure_arity :: arity(),
+                   is_leaf       :: boolean(),
+                   params,     % :: list()
+                   info = []}).  %% this field seems not needed; take out??
+
+%%
+%% Data is a triple with a dict of constants, a list of labels and an integer
+%%
+-type cfg_data() :: {dict(), [cfg_lbl()], non_neg_integer()}.
+
+%%
+%% The following is to be used by other modules
+%%
+-record(cfg, {table = gb_trees:empty() :: gb_tree(),
+              info                     :: #cfg_info{},
+              data                     :: cfg_data()}).
+-type cfg() :: #cfg{}.
diff --git a/lib/hipe/flow/cfg.inc b/lib/hipe/flow/cfg.inc
new file mode 100644
index 0000000000..62f399a81c
--- /dev/null
+++ b/lib/hipe/flow/cfg.inc
@@ -0,0 +1,949 @@
+%% -*- Erlang -*-
+%% -*- erlang-indent-level: 2 -*-
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-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%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%%			 CONTROL FLOW GRAPHS
+%%
+%% Construct and manipulate the control flow graph of a function (program?).
+%%
+%% Exports:
+%% ~~~~~~~~
+%%  init(Code) - makes a CFG out of code.
+%%  bb(CFG, Label) - returns the basic block named 'Label' from the CFG.
+%%  bb_add(CFG, Label, NewBB) - makes NewBB the basic block associated
+%%       with Label.
+%%  succ(Map, Label) - returns a list of successors of basic block 'Label'.
+%%  pred(Map, Label) - returns the predecessors of basic block 'Label'.
+%%  fallthrough(CFG, Label) - returns fall-through successor of basic 
+%%       block 'Label' (or 'none').
+%%  conditional(CFG, Label) - returns conditional successor (or 'none')
+%%  start_label(CFG) - returns the label of the entry basic block.
+%%  params(CFG) - returns the list of parameters to the CFG.
+%%  labels(CFG) - returns a list of labels of all basic blocks in the CFG.
+%%  postorder(CFG) - returns a list of labels in postorder.
+%%  reverse_postorder(CFG) - returns a list of labels in reverse postorder.
+%%  cfg_to_linear(CFG) - converts CFG to linearized code.
+%%  remove_trivial_bbs(CFG) - removes empty BBs or BBs with only a goto.
+%%  remove_unreachable_code(CFG) - removes unreachable BBs.
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% TODO:
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%=====================================================================
+%% The following are ugly as hell, but what else can I do???
+%%=====================================================================
+
+-ifdef(GEN_CFG).
+-define(PRED_NEEDED,true).
+-endif.
+
+-ifdef(ICODE_CFG).
+-define(CLOSURE_ARITY_NEEDED,true).
+-define(INFO_NEEDED,true).
+-define(PARAMS_NEEDED,true).
+-define(PARAMS_UPDATE_NEEDED,true).
+-define(PRED_NEEDED,true).
+-define(REMOVE_TRIVIAL_BBS_NEEDED,true).
+-define(REMOVE_UNREACHABLE_CODE,true).
+-define(START_LABEL_UPDATE_NEEDED,true).
+-define(CFG_CAN_HAVE_PHI_NODES,true).
+-endif.
+
+-ifdef(RTL_CFG).
+-define(PREORDER,true).
+-define(FIND_NEW_LABEL_NEEDED,true).
+-define(INFO_NEEDED,true).
+-define(PARAMS_NEEDED,true).
+-define(PARAMS_UPDATE_NEEDED,true).
+-define(PRED_NEEDED,true).
+-define(REMOVE_TRIVIAL_BBS_NEEDED,true).
+-define(REMOVE_UNREACHABLE_CODE,true).
+-define(START_LABEL_UPDATE_NEEDED,true).
+-define(CFG_CAN_HAVE_PHI_NODES,true).
+-endif.
+
+-ifdef(SPARC_CFG).
+-define(BREADTH_ORDER,true). % for linear scan
+-define(PARAMS_NEEDED,true).
+-define(START_LABEL_UPDATE_NEEDED,true).
+-endif.
+
+%%=====================================================================
+
+-ifdef(START_LABEL_UPDATE_NEEDED).
+-export([start_label_update/2]).
+-endif.
+
+-ifdef(BREADTH_ORDER).
+-export([breadthorder/1]).
+-endif.
+
+-compile(inline).
+
+%%=====================================================================
+%%
+%% Interface functions that MUST be implemented in the including file:
+%%
+%% linear_to_cfg(LinearCode) -> CFG, constructs the cfg.
+%% is_label(Instr) -> boolean(), true if instruction is a label.
+%% label_name(Instr) -> term(), the name of a label.
+%% branch_successors(Instr) -> [term()], the successors of a branch.
+%% fails_to(Instr) -> [term()], the fail-successors of an instruction.
+%% is_branch(Instr) -> boolean(), true if instruction is a branch.
+%% is_comment(Instr) -> boolean(),
+%%       true if instruction is a comment, used by remove dead code.
+%% is_goto(Instr) -> boolean(),
+%%       true if instruction is a pure goto, used by remove dead code.
+%% redirect_jmp(Jmp, ToOld, ToNew) -> NewJmp, 
+%% redirect_ops(Labels, CFG, Map) -> CFG.
+%%       Rewrite instructions with labels in operands to use
+%%       the new label as given by map.
+%%       Use find_new_label(OldLab,Map) to get the new label.
+%%       (See hipe_sparc_cfg for example)
+%% pp(CFG) -> ok, do some nifty output.
+%% cfg_to_linear(CFG) -> LinearCode, linearizes the code of CFG
+%% mk_goto(Label) -> instruction
+%% is_phi(Instr) -> boolean(), true if the instruction is a phi-instruction.
+%% phi_remove_pred(PhiInstr, Pred) -> NewPhi, 
+%%       Removes the predecessor Pred from the phi instruction.
+%% highest_var(Code) -> term(),
+%%       Returns the highest variable used or defined in the code.
+%%
+%%=====================================================================
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Primitives (not all of these are exported)
+%%
+
+-spec start_label(cfg()) -> cfg_lbl().
+start_label(CFG) -> (CFG#cfg.info)#cfg_info.start_label.
+
+-ifndef(GEN_CFG).
+-spec start_label_update(cfg(), cfg_lbl()) -> cfg().
+start_label_update(CFG, NewStartLabel) ->
+  Info = CFG#cfg.info,
+  CFG#cfg{info = Info#cfg_info{start_label = NewStartLabel}}.
+
+-spec function(cfg()) -> mfa().
+function(CFG) -> (CFG#cfg.info)#cfg_info.'fun'.
+
+-spec is_closure(cfg()) -> boolean().
+is_closure(CFG) -> (CFG#cfg.info)#cfg_info.is_closure.
+
+-spec is_leaf(cfg()) -> boolean().
+is_leaf(CFG) -> (CFG#cfg.info)#cfg_info.is_leaf.
+
+mk_empty_cfg(Fun, StartLbl, Data, Closure, Leaf, Params) ->
+  Info = #cfg_info{'fun' = Fun,
+		   start_label = StartLbl,
+		   is_closure = Closure,
+		   is_leaf = Leaf,
+		   params = Params},
+  #cfg{table = gb_trees:empty(), data = Data, info = Info}.
+
+data(CFG) -> CFG#cfg.data.
+-endif.	% GEN_CFG
+
+-ifdef(REMOVE_TRIVIAL_BBS_NEEDED).
+-spec update_data(cfg(), cfg_data()) -> cfg().
+update_data(CFG, D) ->
+  CFG#cfg{data = D}.
+-endif.
+
+-ifdef(PARAMS_NEEDED).
+params(CFG) -> (CFG#cfg.info)#cfg_info.params.
+-endif.
+
+-ifdef(PARAMS_UPDATE_NEEDED).
+params_update(CFG, NewParams) ->
+  Info = CFG#cfg.info,
+  CFG#cfg{info = Info#cfg_info{params = NewParams}}.
+-endif.
+
+-ifdef(CLOSURE_ARITY_NEEDED).
+-spec closure_arity(cfg()) -> arity().
+closure_arity(CFG) ->
+  Info = CFG#cfg.info,
+  Info#cfg_info.closure_arity.
+
+-spec closure_arity_update(cfg(), arity()) -> cfg().
+closure_arity_update(CFG, Arity) ->
+  Info = CFG#cfg.info,
+  CFG#cfg{info = Info#cfg_info{closure_arity = Arity}}.
+-endif.
+
+%% %% Don't forget to do a start_label_update if necessary.
+%% update_code(CFG, NewCode) ->
+%%   take_bbs(NewCode, CFG).
+
+-ifdef(INFO_NEEDED).
+info(CFG) -> (CFG#cfg.info)#cfg_info.info.
+%% info_add(CFG, A) ->
+%%    As = info(CFG),
+%%    Info = CFG#cfg.info,
+%%    CFG#cfg{info = Info#cfg_info{info = [A|As]}}.
+info_update(CFG, I) ->
+  Info = CFG#cfg.info,
+  CFG#cfg{info = Info#cfg_info{info = I}}.
+-endif.
+
+%%=====================================================================
+-ifndef(GEN_CFG).
+
+-spec other_entrypoints(cfg()) -> [cfg_lbl()].
+%% @doc Returns a list of labels that are refered to from the data section.
+
+other_entrypoints(CFG) ->
+  hipe_consttab:referred_labels(data(CFG)).
+
+%% is_entry(Lbl, CFG) ->
+%%   Lbl =:= start_label(CFG) orelse
+%% 	lists:member(Lbl, other_entrypoints(CFG)).
+
+%% @spec bb(CFG::cfg(), Label::cfg_lbl()) -> basic_block()
+%% @doc  Returns the basic block of the CFG which begins at the Label.
+bb(CFG, Label) ->
+  HT = CFG#cfg.table,
+  case gb_trees:lookup(Label, HT) of
+    {value, {Block,_Succ,_Pred}} ->
+      Block;
+    none ->
+      not_found
+  end.
+
+%% Remove duplicates from a list. The first instance (in left-to-right
+%% order) of an element is kept, remaining instances are removed.
+-spec remove_duplicates([cfg_lbl()]) -> [cfg_lbl()].
+remove_duplicates(List) ->
+  remove_duplicates(List, []).
+
+-spec remove_duplicates([cfg_lbl()], [cfg_lbl()]) -> [cfg_lbl()].
+remove_duplicates([H|T], Acc) ->
+  NewAcc =
+    case lists:member(H, Acc) of
+      false -> [H|Acc];
+      true -> Acc
+    end,
+  remove_duplicates(T, NewAcc);
+remove_duplicates([], Acc) ->
+  lists:reverse(Acc).
+
+
+-ifdef(RTL_CFG).	%% this could be CFG_CAN_HAVE_PHI_NODES
+			%% if Icode also starts using this function
+
+%% @spec bb_insert_between(CFG::cfg(),
+%%                         Label::cfg_lbl(), NewBB::basic_block(),
+%%                         Pred::cfg_lbl(), Succ::cfg_lbl()) -> cfg() 
+%%
+%% @doc Insert the new basic block with label Label in the edge from
+%%      Pred to Succ
+
+bb_insert_between(CFG, Label, NewBB, Pred, Succ) ->
+  Last = hipe_bb:last(NewBB),
+  %% Asserts that NewBB ends in a label
+  true = is_branch(Last),
+  %% Asserts that the only Successor of NewBB is Succ
+  [Succ] = remove_duplicates(branch_successors(Last)),
+  HT = CFG#cfg.table,
+  %% Asserts that Label does not exist in the CFG
+  none = gb_trees:lookup(Label, HT),
+  %% Updates the predecessor of NewBB
+  {value, {PBB, PSucc, PPred}} = gb_trees:lookup(Pred, HT),
+  NewPSucc = [Label|lists:delete(Succ, PSucc)],
+  PLast = hipe_bb:last(PBB),
+  PButLast = hipe_bb:butlast(PBB),
+  NewPBB = hipe_bb:code_update(PBB, PButLast++[redirect_jmp(PLast, Succ, Label)]),
+  HT1 = gb_trees:update(Pred, {NewPBB,NewPSucc,PPred}, HT),
+  %% Updates the successor of NewBB
+  {value, {SBB, SSucc, SPred}} = gb_trees:lookup(Succ, HT1),
+  NewSPred = [Label|lists:delete(Pred, SPred)],
+  SCode = hipe_bb:code(SBB),
+  NewSCode = redirect_phis(SCode, Pred, Label, []),
+  NewSBB = hipe_bb:code_update(SBB, NewSCode),
+  HT2 = gb_trees:update(Succ, {NewSBB,SSucc,NewSPred}, HT1),
+  %% Enters NewBB into the CFG
+  HT3 = gb_trees:insert(Label, {NewBB,[Succ],[Pred]}, HT2), 
+  CFG#cfg{table = HT3}.
+
+redirect_phis([], _OldPred, _NewPred, Acc) ->
+  lists:reverse(Acc);
+redirect_phis([I|Rest], OldPred, NewPred, Acc) ->
+  case is_phi(I) of
+    true ->
+      Phi = phi_redirect_pred(I, OldPred, NewPred),
+      redirect_phis(Rest, OldPred, NewPred, [Phi|Acc]);
+    false ->
+      redirect_phis(Rest, OldPred, NewPred, [I|Acc])
+  end.
+
+-endif.
+
+%% @spec bb_add(CFG::cfg(), Label::cfg_lbl(), NewBB::basic_block()) -> cfg()
+%% @doc  Adds a new basic block to a CFG (or updates an existing block).
+bb_add(CFG, Label, NewBB) ->
+  %% Asserting that the NewBB is a legal basic block
+  Last = hipe_bb:last(NewBB),
+  case is_branch(Last) of
+    true  -> ok;
+    false -> throw({?MODULE, {"Basic block ends without branch", Last}})
+  end,
+  %% The order of the elements from branch_successors/1 is
+  %% significant. It determines the basic block order when the CFG is
+  %% converted to linear form. That order may have been tuned for
+  %% branch prediction purposes.
+  Succ = remove_duplicates(branch_successors(Last)),
+  HT = CFG#cfg.table,
+  {OldSucc, OldPred} = case gb_trees:lookup(Label, HT) of
+			 {value, {_Block, OSucc, OPred}} ->
+			   {OSucc, OPred};
+			 none ->
+		           {[], []}
+		       end,
+  %% Change this block to contain new BB and new successors, but keep
+  %% the old predecessors which will be updated in the following steps
+  HT1 = gb_trees:enter(Label, {NewBB, Succ, OldPred}, HT),
+  %% Add this block as predecessor to its new successors
+  HT2 = lists:foldl(fun (P, HTAcc) ->
+		      add_pred(HTAcc, P, Label)
+		    end,
+		    HT1, Succ -- OldSucc),
+  %% Remove this block as predecessor of its former successors
+  HT3 = lists:foldl(fun (S, HTAcc) ->
+		      remove_pred(HTAcc, S, Label)
+		    end,
+		    HT2, OldSucc -- Succ),
+  CFG#cfg{table = HT3}.
+
+remove_pred(HT, FromL, PredL) ->
+  case gb_trees:lookup(FromL, HT) of
+    {value, {Block, Succ, Preds}} ->
+      Code = hipe_bb:code(Block),
+      NewCode = remove_pred_from_phis(Code, PredL, []),
+      NewBlock = hipe_bb:code_update(Block, NewCode),      
+      gb_trees:update(FromL, {NewBlock,Succ,lists:delete(PredL,Preds)}, HT);
+    none ->
+      HT
+  end.
+
+add_pred(HT, ToL, PredL) ->
+  case gb_trees:lookup(ToL, HT) of
+    {value,{Block,Succ,Preds}} ->
+      gb_trees:update(ToL, {Block,Succ,[PredL|lists:delete(PredL,Preds)]}, HT);
+    none ->
+      gb_trees:insert(ToL, {[],[],[PredL]}, HT)
+  end.
+
+%% find_highest_label(CFG) ->
+%%   Labels = labels(CFG),
+%%   lists:foldl(fun(X, Acc) -> erlang:max(X, Acc) end, 0, Labels).
+%% 
+%% find_highest_var(CFG) ->
+%%   Labels = labels(CFG),
+%%   Fun = fun(X, Max) ->
+%% 	    Code = hipe_bb:code(bb(CFG, X)),
+%% 	    NewMax = highest_var(Code),
+%% 	    erlang:max(Max, NewMax)
+%% 	end,
+%%   lists:foldl(Fun, 0, Labels).
+
+-ifdef(CFG_CAN_HAVE_PHI_NODES).
+%% phi-instructions in a removed block's successors must be aware of
+%% the change.
+remove_pred_from_phis(List = [I|Left], Label, Acc) ->
+  case is_phi(I) of
+    true -> 
+      NewAcc = [phi_remove_pred(I, Label)|Acc],
+      remove_pred_from_phis(Left, Label, NewAcc);
+    false ->
+      lists:reverse(Acc) ++ List
+  end;
+remove_pred_from_phis([], _Label, Acc) ->
+  lists:reverse(Acc).
+-else.
+%% this is used for code representations like those of back-ends which
+%% do not have phi-nodes.
+remove_pred_from_phis(Code, _Label, _Acc) ->
+  Code.
+-endif.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Constructs a CFG from a list of instructions.
+%%
+
+take_bbs([], CFG) ->
+  CFG;
+take_bbs(Xs, CFG) ->
+  Lbl = hd(Xs),
+  case is_label(Lbl) of
+    true ->
+      case take_bb(tl(Xs), []) of
+	{Code, Rest} ->
+	  NewCFG = bb_add(CFG, label_name(Lbl), hipe_bb:mk_bb(Code)),
+	  take_bbs(Rest, NewCFG)
+      end;
+    false ->
+      erlang:error({?MODULE,"basic block doesn't start with a label",Xs})
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Take_bb returns:
+%%   - {Code, Rest}.
+%%      * Code is a list of all the instructions.
+%%      * Rest is the remainder of the instructions
+
+take_bb([], Code) ->
+  {lists:reverse(Code), []};
+take_bb([X, Y|Xs], Code) ->
+  case is_label(X) of
+    true -> %% Empty block fallthrough
+      {[mk_goto(label_name(X))], [X,Y|Xs]};
+    false ->
+      case is_branch(X) of
+	true ->
+	  case is_label(Y) of
+	    true ->
+	      {lists:reverse([X|Code]), [Y|Xs]};
+	    false ->
+	      %% This should not happen...
+	      %% move the problem to the next BB.
+	      {lists:reverse([X|Code]), [Y|Xs]}
+	  end;
+	false -> %% X not branch
+	  case is_label(Y) of
+	    true ->
+	      {lists:reverse([mk_goto(label_name(Y)),X|Code]), [Y|Xs]};
+	    false ->
+	      take_bb([Y|Xs], [X|Code])
+	  end
+      end
+  end;
+take_bb([X], []) ->
+  case is_label(X) of 
+    true -> 
+      %% We don't want the CFG to just end with a label...
+      %% We loop forever instead...
+      {[X,mk_goto(label_name(X))],[]};
+    false ->
+      {[X],[]}
+  end;
+take_bb([X], Code) ->
+  case is_label(X) of 
+    true -> 
+      %% We don't want the CFG to just end with a label...
+      %% We loop for ever instead...
+      {lists:reverse(Code),[X,mk_goto(label_name(X))]};
+    false ->
+      {lists:reverse([X|Code]),[]}
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Functions for extracting the names of the basic blocks in various
+%% orders.
+%%
+
+labels(CFG) ->
+  HT = CFG#cfg.table,
+  gb_trees:keys(HT).
+
+postorder(CFG) ->
+  lists:reverse(reverse_postorder(CFG)).
+
+reverse_postorder(CFG) ->
+  Start = start_label(CFG),
+  {Ordering, _Visited} =
+    depth_search([Start|other_entrypoints(CFG)], none_visited(), CFG, []),
+  Ordering.
+
+depth_search([N|Ns], Visited, CFG, Acc) ->
+  case is_visited(N, Visited) of 
+    true ->
+      depth_search(Ns, Visited, CFG, Acc);
+    false ->
+      {Order, Vis} = depth_search(succ(CFG, N), visit(N, Visited), CFG, Acc),
+      depth_search(Ns, Vis, CFG, [N|Order])
+  end;
+depth_search([], Visited, _, Ordering) ->
+  {Ordering, Visited}.
+
+-ifdef(PREORDER).
+preorder(CFG) ->
+  Start = start_label(CFG),
+  {Ordering, _Visited} =
+    preorder_search([Start|other_entrypoints(CFG)], none_visited(), CFG, []),
+  lists:reverse(Ordering).
+
+preorder_search([N|Ns], Visited, CFG, Acc) ->
+  case is_visited(N, Visited) of 
+    true ->
+      preorder_search(Ns, Visited, CFG, Acc);
+    false ->
+      {Order, Vis} = 
+	preorder_search(succ(CFG, N), visit(N, Visited), CFG, [N|Acc]),
+      preorder_search(Ns, Vis, CFG, Order)
+  end;
+preorder_search([], Visited, _, Ordering) ->
+  {Ordering,Visited}.
+-endif.	% PREORDER
+
+-ifdef(BREADTH_ORDER).
+breadthorder(CFG) ->
+  lists:reverse(reverse_breadthorder(CFG)).
+
+reverse_breadthorder(CFG) ->
+  Start = start_label(CFG),
+  {Vis, RBO1} = breadth_list([Start], none_visited(), CFG, []),
+  {_Vis1, RBO2} = breadth_list(other_entrypoints(CFG), Vis, CFG, RBO1),
+  RBO2.
+
+breadth_list([X|Xs], Vis, CFG, BO) ->
+  case is_visited(X, Vis) of
+    true ->
+      breadth_list(Xs, Vis, CFG, BO);
+    false ->
+      breadth_list(Xs ++ succ(CFG, X), visit(X, Vis), CFG, [X|BO])
+  end;  
+breadth_list([], Vis, _CFG, BO) -> 
+  {Vis, BO}.
+-endif.
+
+-spec none_visited() -> gb_set().
+none_visited() -> 
+  gb_sets:empty().
+
+visit(X, Vis) -> 
+  gb_sets:add(X, Vis).
+
+is_visited(X, Vis) ->
+  gb_sets:is_member(X, Vis).
+
+-endif.	% GEN_CFG
+
+%%---------------------------------------------------------------------
+
+succ(SuccMap, Label) ->
+  HT = SuccMap#cfg.table,
+  case gb_trees:lookup(Label, HT) of
+    {value, {_Block,Succ,_Pred}} ->
+      Succ;
+    none ->
+      erlang:error({"successor not found", Label, SuccMap})
+  end.
+
+-ifdef(PRED_NEEDED).
+pred(Map, Label) ->
+  HT = Map#cfg.table,
+  case gb_trees:lookup(Label, HT) of
+    {value, {_Block,_Succ,Pred}} ->
+      Pred;
+    none ->
+      erlang:error({"predecessor not found", Label, Map})
+  end.
+-endif.	% PRED_NEEDED
+
+-ifndef(GEN_CFG).
+fallthrough(CFG, Label) ->
+  HT = CFG#cfg.table,
+  case gb_trees:lookup(Label, HT) of
+    {value, {_Block, Succ, _}} ->
+       case Succ of
+	 [X|_] -> X;
+	 _ -> none
+       end;
+     none ->
+       erlang:error({"fallthrough label not found", Label})
+  end.
+
+conditional(CFG, Label) ->
+  HT = CFG#cfg.table,
+  {value,{_Block,Succ,_}} = gb_trees:lookup(Label, HT),
+  case Succ of
+    [] -> none;
+    [_] -> none;
+    [_|Labels] -> Labels
+  end.
+-endif.	% GEN_CFG
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Linearize the code in a CFG. Returns a list of instructions.
+%%
+
+-ifdef(GEN_CFG).
+-else.
+linearize_cfg(CFG) ->
+  Start = start_label(CFG),
+  Vis = none_visited(),
+  {Vis0, NestedCode} = lin_succ(Start, CFG, Vis),
+  BlocksInData = hipe_consttab:referred_labels(data(CFG)),
+  AllCode = lin_other_entries(NestedCode, CFG, BlocksInData, Vis0),
+  lists:flatten(AllCode).
+
+lin_succ(none, _CFG, Vis) ->
+  {Vis, []};
+lin_succ([Label|Labels], CFG, Vis) ->
+  {Vis1, Code1} = lin_succ(Label, CFG, Vis),
+  {Vis2, Code2} = lin_succ(Labels, CFG, Vis1),
+  {Vis2, [Code1,Code2]};
+lin_succ([], _CFG, Vis) ->
+  {Vis, []};
+lin_succ(Label, CFG, Vis) ->
+  case is_visited(Label, Vis) of
+    true ->
+      {Vis, []};      % already visited
+    false ->
+      Vis0 = visit(Label, Vis),
+      case bb(CFG, Label) of
+	not_found ->
+	  erlang:error({?MODULE, "No basic block with label", Label});
+        BB ->
+	  Fallthrough = fallthrough(CFG, Label),
+	  Cond = conditional(CFG, Label),
+	  LblInstr = mk_label(Label),
+	  {Vis1, Code1} = lin_succ(Fallthrough, CFG, Vis0),
+	  {Vis2, Code2} = lin_succ(Cond, CFG, Vis1),
+	  {Vis2, [[LblInstr|hipe_bb:code(BB)], Code1, Code2]}
+      end
+  end.
+
+lin_other_entries(Code, _CFG, [], _Vis) ->
+  Code;
+lin_other_entries(Code, CFG, [E|Es], Vis) ->
+  {Vis0, MoreCode} = lin_succ(E, CFG, Vis),
+  lin_other_entries([Code, MoreCode], CFG, Es, Vis0).
+-endif.
+
+-ifdef(FIND_NEW_LABEL_NEEDED).
+find_new_label(Old, Map) ->
+  forward(Old, Map).
+-endif.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Remove empty BBs.
+%% 
+%% Removes basic blocks containing only a goto to another BB.
+%% Branches to removed blocks are updated to the successor of the
+%% removed block.
+%% Loads (or other operations) on the label of the BB are also
+%% updated. So are any references from the data section.
+%%
+
+-ifdef(REMOVE_TRIVIAL_BBS_NEEDED).
+
+-spec remove_trivial_bbs(cfg()) -> cfg().
+remove_trivial_bbs(CFG) ->
+  ?opt_start_timer("Merge BBs"),
+  CFG0 = merge_bbs(rewrite_trivial_branches(CFG)),
+  ?opt_stop_timer("Merge BBs"),
+  %% pp(CFG0),
+  ?opt_start_timer("FindDead"),
+  {NewMap, CFG1} = remap(labels(CFG0), rd_map_new(), CFG0),
+  ?opt_stop_timer("FindDead"),
+  ?opt_start_timer("Labels"),
+  Labels = labels(CFG1),
+  ?opt_stop_timer("Labels"),
+  ?opt_start_timer("RedirectBranches"),
+  CFG2 = redirect_branches(NewMap, CFG1),
+  ?opt_stop_timer("RedirectBranches"),
+  ?opt_start_timer("RedirectOps"),
+  CFG3 = redirect_ops(Labels, CFG2, NewMap),
+  ?opt_stop_timer("RedirectOps"),
+  ?opt_start_timer("RedirectData"),
+  CFG4 = redirect_data(CFG3, NewMap),
+  ?opt_stop_timer("RedirectData"),
+  ?opt_start_timer("RedirectStart"),
+  CFG5 = redirect_start(CFG4, NewMap),
+  ?opt_stop_timer("RedirectStart"),
+  %% pp(CFG5),
+  CFG5.
+
+redirect_start(CFG, Map) ->
+  Start = start_label(CFG),
+  case forward(Start, Map) of
+    Start -> CFG;
+    NewStart ->
+      start_label_update(CFG, NewStart)
+  end.
+
+redirect_data(CFG, Map) ->
+  Data = data(CFG),
+  NewData = hipe_consttab:update_referred_labels(Data, rd_succs(Map)),
+  update_data(CFG, NewData).
+
+redirect_branches(Map, CFG) ->
+  lists:foldl(fun ({From,{newsuccs,Redirects}}, CFGAcc) ->
+		  lists:foldl(
+		    fun({ToOld,ToNew}, CFG1) ->
+			case bb(CFG1, From) of
+			  not_found -> 
+			    CFG1;
+			  _ ->
+			    To = forward(ToNew, Map),
+			    redirect(CFG1, From, ToOld, To)
+			end
+		    end,
+		    CFGAcc,
+		    Redirects);
+		  (_, CFGAcc) -> CFGAcc
+	      end,
+	      CFG,
+	      gb_trees:to_list(Map)).
+
+redirect(CFG, From, ToOld, ToNew) ->
+  BB = bb(CFG, From),
+  LastInstr = hipe_bb:last(BB),
+  NewLastInstr = redirect_jmp(LastInstr, ToOld, ToNew),
+  NewBB = hipe_bb:mk_bb(hipe_bb:butlast(BB) ++ [NewLastInstr]),
+  bb_add(CFG, From, NewBB).
+
+bb_remove(CFG, Label) ->
+  HT = CFG#cfg.table,
+  case gb_trees:lookup(Label, HT) of
+    {value, {_Block, Succ, _Preds}} ->
+      %% Remove this block as a pred from all successors.
+      HT1 = lists:foldl(fun (S,HTAcc) ->
+			    remove_pred(HTAcc, S, Label)
+			end,
+			HT, Succ),
+      CFG#cfg{table = gb_trees:delete(Label, HT1)};
+    none -> 
+      CFG
+  end.
+
+remap([L|Rest], Map, CFG) ->
+  case is_empty(bb(CFG, L)) of
+    true ->
+      case succ(CFG, L) of
+	[L] -> %% This is an empty (infinite) self loop. Leave it.
+	  remap(Rest, Map, CFG);
+	[SuccL] ->
+	  CFG1 = bb_remove(CFG, L), 
+	  NewMap = remap_to_succ(L, SuccL, Map, CFG),
+	  remap(Rest, NewMap, CFG1)
+      end;
+    false ->
+      remap(Rest, Map, CFG)
+  end;
+remap([], Map, CFG) ->
+  {Map, CFG}.
+
+remap_to_succ(L, SuccL, Map, PredMap) ->
+  insert_remap(L, forward(SuccL,Map), pred(PredMap,L), Map).
+
+%% Find the proxy for a BB
+forward(L, Map) ->
+  case gb_trees:lookup(L, Map) of
+    {value, {dead, To}} ->
+      forward(To, Map); %% Hope this terminates.
+    _ -> L
+  end.
+
+%% A redirection map contains mappings from labels to
+%%  none -> this BB is not affected by the remapping.
+%%  {dead,To} -> this BB is dead, To is the new proxy.
+%%  {newsuccs,[{X,Y}|...]} -> The successor X is redirected to Y. 
+
+rd_map_new() -> gb_trees:empty().
+
+rd_succs(M) ->
+  lists:foldl(fun ({From,{dead,To}}, Acc) -> [{From,forward(To,M)}|Acc];
+		  (_, Acc) -> Acc
+	      end,
+	      [],
+	      gb_trees:to_list(M)).
+
+add_redirectedto(L, From, To, Map) ->
+  case gb_trees:lookup(L, Map) of
+    {value, {newsuccs, NS}} ->
+      gb_trees:update(L,{newsuccs,[{From,To}|lists:keydelete(From,1,NS)]},Map);
+    {value, {dead, _}} -> Map;
+    none ->
+      gb_trees:insert(L, {newsuccs, [{From, To}]}, Map)
+  end.
+
+insert_remap(L, ToL, Preds, Map) ->
+  Map2 = gb_trees:enter(L, {dead, ToL}, Map),
+  lists:foldl(fun (Pred, AccMap) ->
+		   add_redirectedto(Pred, L, ToL, AccMap)
+	      end,
+	      Map2,
+	      Preds).
+
+is_empty(BB) ->
+  is_empty_bb(hipe_bb:code(BB)).
+
+is_empty_bb([I]) ->
+  is_goto(I); %% A BB with just a 'goto' is empty.
+is_empty_bb([I|Is]) ->
+  case is_comment(I) of 
+    true ->
+      is_empty_bb(Is);
+    false ->
+      false
+  end;
+is_empty_bb([]) ->
+  true.
+
+
+%% Rewrite all pure branches with one successor to goto:s
+
+-spec rewrite_trivial_branches(cfg()) -> cfg().
+rewrite_trivial_branches(CFG) ->
+  rewrite_trivial_branches(postorder(CFG), CFG).
+
+rewrite_trivial_branches([L|Left], CFG) ->
+  BB = bb(CFG, L),
+  Last = hipe_bb:last(BB),
+  case is_goto(Last) of
+    true ->
+      rewrite_trivial_branches(Left, CFG);
+    false ->
+      case is_pure_branch(Last) of
+	false ->
+	  rewrite_trivial_branches(Left, CFG);
+	true ->
+	  case succ(CFG, L) of
+	    [Successor] ->
+	      Head = hipe_bb:butlast(BB),
+	      NewBB = hipe_bb:mk_bb(Head ++ [mk_goto(Successor)]),
+	      NewCFG = bb_add(CFG, L, NewBB),
+	      rewrite_trivial_branches(Left, NewCFG);
+	    _ ->
+	      rewrite_trivial_branches(Left, CFG)
+	  end
+      end
+  end;
+rewrite_trivial_branches([], CFG) ->
+  CFG.
+
+
+%% Go through the CFG and find pairs of BBs that can be merged to one BB.
+%% They are of the form:
+%%
+%%      L
+%%      |
+%%   Successor
+%%
+%% That is, the block L has only one successor (Successor) and that
+%% successor has no other predecessors than L.
+%%
+%% Note: calls might end a basic block 
+
+merge_bbs(CFG) ->
+  lists:foldl(fun merge_successor/2, CFG, postorder(CFG)).
+
+%% If L fulfills the requirements, merge it with its successor.
+merge_successor(L, CFG) ->
+  %% Get the BB L (If it still exists).
+  case bb(CFG, L) of
+    not_found -> CFG;
+    BB ->
+      StartLabel = start_label(CFG),
+      Last = hipe_bb:last(BB),
+      %% Note: Cannot use succ/2 since the instruction can have more than
+      %% one successor that are the same label.
+      case {branch_successors(Last), fails_to(Last)} of
+	{[Successor],[Successor]} ->
+	  %% The single successor is the fail-label; don't merge.
+	  CFG;
+	{[Successor],_} when Successor =/= StartLabel ->
+	  %% Make sure the succesor only have this block as predecessor.
+	  case [L] =:= pred(CFG, Successor) of
+	    true ->
+	      %% Remove the goto or remap fall-through in BB and merge the BBs
+	      NewCode = merge(BB, bb(CFG, Successor), Successor),
+	      NewBB = hipe_bb:mk_bb(NewCode),
+	      bb_add(bb_remove(CFG, Successor), L, NewBB);
+	    false ->
+	      CFG
+	  end;
+	_ -> 
+	  %% Not exactly one successor or tried to merge with the 
+	  %% entry point
+	  CFG
+      end
+  end.
+
+%% Merge BB and BB2
+merge(BB, BB2, BB2_Label) ->
+  Head = hipe_bb:butlast(BB),
+  Last = hipe_bb:last(BB),
+  Tail = hipe_bb:code(BB2),
+  case is_goto(Last) of
+    true ->
+      %% Just ignore the goto.
+      Head ++ Tail;
+    false -> 
+      %% The last instr is not a goto,
+      %%  e.g. a call with only fall-through
+      %% Remove the fall-through with the []-label. 
+      Head ++ [redirect_jmp(Last, BB2_Label, [])|Tail]
+  end.
+
+-endif.	% REMOVE_TRIVIAL_BBS_NEEDED
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Remove unreachable BBs.
+%% 
+%% A BB is unreachable if it cannot be reached by any path from the
+%% start label of the function.
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-ifdef(REMOVE_UNREACHABLE_CODE).
+
+-spec remove_unreachable_code(cfg()) -> cfg().
+
+remove_unreachable_code(CFG) ->
+  Start = start_label(CFG),
+  Reachable = find_reachable([Start], CFG, gb_sets:from_list([Start])),
+  %% Reachable is an ordset: it comes from gb_sets:to_list/1.
+  %% So use ordset:subtract instead of '--' below.
+  Labels = ordsets:from_list(labels(CFG)),
+  case ordsets:subtract(Labels, Reachable) of
+    [] ->
+      CFG;
+    Remove ->
+      NewCFG = lists:foldl(fun(X, Acc) -> bb_remove(Acc, X) end, CFG, Remove),
+      remove_unreachable_code(NewCFG)
+  end.
+
+find_reachable([Label|Left], CFG, Acc) ->
+  NewAcc = gb_sets:add(Label, Acc),
+  Succ = succ(CFG, Label),
+  find_reachable([X || X <- Succ, not gb_sets:is_member(X, Acc)] ++ Left,
+		 CFG, NewAcc);
+find_reachable([], _CFG, Acc) ->
+  gb_sets:to_list(Acc).
+
+-endif.
diff --git a/lib/hipe/flow/ebb.inc b/lib/hipe/flow/ebb.inc
new file mode 100644
index 0000000000..42d7ff3793
--- /dev/null
+++ b/lib/hipe/flow/ebb.inc
@@ -0,0 +1,247 @@
+%% -*- Erlang -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-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%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% IDENTIFIES THE EXTENDED BASIC BLOCKS OF A CFG
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-export([cfg/1,
+	 %% dag/2,
+	 type/1,
+	 node_label/1,
+	 node_successors/1
+	]).
+-ifdef(DEBUG_EBB).
+-export([pp/1]).
+-endif.
+
+-define(cfg, ?CFG).
+
+%%--------------------------------------------------------------------
+%% The extended basic block datatype
+%%
+%% An EBB is identified with the label of the root node. 
+%% It's a tree
+%%
+%% EBB :=  {ebb_node, Label, [EBB]}
+%%      |  {ebb_leaf, SuccesorLabel}
+%%--------------------------------------------------------------------
+
+%% XXX: Cheating big time! no recursive types
+-type ebb() :: {ebb_node, icode_lbl(), _}
+             | {ebb_leaf, icode_lbl()}.
+
+-record(ebb_node, {label :: icode_lbl(), successors :: [ebb()]}).
+-record(ebb_leaf, {successor :: icode_lbl()}).
+
+%%--------------------------------------------------------------------
+%% Returns a list of extended basic blocks.
+%%--------------------------------------------------------------------
+
+-spec cfg(cfg()) -> [ebb()].
+
+cfg(CFG) ->
+  Start = ?cfg:start_label(CFG),
+  Labels = ?cfg:reverse_postorder(CFG),
+  Roots = [Start],
+  Blocks = Labels -- Roots,
+  Visited = new_visited(),
+  build_all_ebb(Roots, Blocks, Visited, CFG).
+
+new_visited() ->
+  gb_sets:empty().
+visited(L, Visited) ->
+  gb_sets:is_member(L, Visited).
+visit(L, Visited) ->
+  gb_sets:add(L, Visited).
+
+build_all_ebb(Roots, Blocks, Visited, CFG) ->
+  build_all_ebb(Roots, Blocks, Visited, CFG, []).
+
+build_all_ebb([], [], _, _CFG, Ebbs) ->
+  lists:reverse(Ebbs);
+build_all_ebb([], [BlockLeft|BlocksLeft], Visited, CFG, Ebbs) ->
+  case visited(BlockLeft, Visited) of
+    true -> 
+      build_all_ebb([], BlocksLeft, Visited, CFG, Ebbs);
+    false ->
+      build_all_ebb([BlockLeft], BlocksLeft, Visited, CFG, Ebbs)
+  end;
+build_all_ebb([Root|Roots], Blocks, Visited, CFG, Ebbs) ->
+  {Ebb, NewVisited} = build_ebb(Root, Visited, CFG),
+  build_all_ebb(Roots, Blocks, NewVisited, CFG, [Ebb|Ebbs]).
+
+%%
+%% Build the extended basic block with Lbl as its root.
+%%
+
+build_ebb(Lbl, Visited, CFG) ->
+  build_ebb(Lbl, Visited, 
+	    fun (NodeL, NewVisited) -> {NodeL, NewVisited} end,
+	    [], CFG).
+
+build_ebb(Lbl, Visited, MkFun, EBBs, CFG) ->
+  Succ = ?cfg:succ(CFG, Lbl),
+  add_succ(Succ, visit(Lbl, Visited), Lbl, MkFun, EBBs, CFG).
+
+add_succ([], Visited, Node, MkFun, EBBs, _CFG) ->
+  MkFun(mk_node(Node, lists:reverse(EBBs)), Visited);
+add_succ([Lbl|Lbls], Visited, Node, MkFun, EBBs, CFG) ->
+  case [visited(Lbl, Visited)|?cfg:pred(CFG, Lbl)] of
+    [false,_] ->
+      build_ebb(Lbl, Visited, 
+		fun (NewEbb, Visited0) ->
+		    add_succ(Lbls, Visited0, Node, MkFun, [NewEbb|EBBs], CFG)
+		end, [], CFG);
+    _ ->
+      add_succ(Lbls, Visited, Node, MkFun, [mk_leaf(Lbl)|EBBs], CFG)
+   end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Generate a list of dags.
+%%
+
+%% dag(EBBs, CFG) ->
+%%   Start = ?cfg:start_label(CFG),
+%%   Roots = [Start],
+%%   Edges = all_adges(EBBs, Roots),
+%%   start_dag(Roots, Edges, []).
+%% 
+%% start_dag([], _Edges, _Visit) ->
+%%   [];
+%% start_dag([Root|Roots], Edges, Visit) ->
+%%   case lists:member(Root, Visit) of
+%%     true ->
+%%       start_dag(Roots, Edges, Visit);
+%%     false ->
+%%       {Dag, Roots0, Visit0} =
+%% 	fill_dag(Root, [Root], Edges, Roots, [Root|Visit]),
+%%       [lists:reverse(Dag) | start_dag(Roots0, Edges, Visit0)]
+%%   end.
+%% 
+%% fill_dag(Lbl, Dag, Edges, Roots, Visit) ->
+%%   Succ = find_succ(Lbl, Edges),
+%%   add_dag_succ(Succ, Dag, Edges, Roots, Visit).
+%% 
+%% add_dag_succ([], Dag, _Edges, Roots, Visit) ->
+%%   {Dag, Roots, Visit};
+%% add_dag_succ([S|Ss], Dag, Edges, Roots, Visit) ->
+%%   {Dag0, Roots0, Visit0} = add_dag_succ(Ss, Dag, Edges, Roots, Visit),
+%%   Pred = find_pred(S, Edges),
+%%   case all_in(Pred, Dag0) of
+%%     true ->
+%%       fill_dag(S, [S|Dag0], Edges, Roots0, [S|Visit0]);
+%%     false ->
+%%       {Dag0, [S|Roots], Visit0}
+%%   end.
+%% 
+%% find_succ(_Lbl, []) ->
+%%   [];
+%% find_succ(Lbl, [{Lbl, Succ}|Edges]) ->
+%%   [Succ | find_succ(Lbl, Edges)];
+%% find_succ(Lbl, [_|Edges]) ->
+%%   find_succ(Lbl, Edges).
+%% 
+%% find_pred(_Lbl, []) ->
+%%   [];
+%% find_pred(Lbl, [{Pred, Lbl}|Edges]) ->
+%%   [Pred | find_pred(Lbl, Edges)];
+%% find_pred(Lbl, [_|Edges]) ->
+%%   find_pred(Lbl, Edges).
+%% 
+%% all_edges([], _Roots) ->
+%%   [];
+%% all_edges([EBB|EBBs], Roots) ->
+%%   succ_edges(node_label(EBB), ebb_successors(EBB), EBBs, Roots).
+%% 
+%% succ_edges(Lbl, [], EBBs, Roots) ->
+%%   case lists:member(Lbl, Roots) of
+%%     true ->
+%%       [{start, Lbl} | all_edges(EBBs, Roots)];
+%%     false ->
+%%       all_edges(EBBs, Roots)
+%%   end;
+%% succ_edges(Lbl, [S|Ss], EBBs, Roots) ->
+%%   [{Lbl, S} | succ_edges(Lbl, Ss, EBBs, Roots)].
+%% 
+%% all_in([], _List) ->
+%%   true;
+%% all_in([X|Xs], List) ->
+%%   lists:member(X, List) andalso all_in(Xs, List).
+%% 
+%% find_ebb(Lbl, [EBB|EBBs]) ->
+%%   case node_label(EBB) of
+%%      Lbl ->
+%%	 EBB;
+%%      _ ->
+%%	 find_ebb(Lbl, EBBs)
+%%   end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-spec mk_node(icode_lbl(), [ebb()]) -> #ebb_node{}.
+mk_node(Label, Successors) -> #ebb_node{label=Label, successors=Successors}.
+
+-spec node_label(#ebb_node{}) -> icode_lbl().
+node_label(#ebb_node{label=Label}) -> Label.
+
+-spec node_successors(#ebb_node{}) -> [ebb()].
+node_successors(#ebb_node{successors=Successors}) -> Successors.
+
+-spec mk_leaf(icode_lbl()) -> #ebb_leaf{}.
+mk_leaf(NextEbb) -> #ebb_leaf{successor=NextEbb}.
+%% leaf_next(Leaf) -> Leaf#ebb_leaf.successor.
+
+-spec type(#ebb_node{}) -> 'node' ; (#ebb_leaf{}) -> 'leaf'.
+type(#ebb_node{}) -> node;
+type(#ebb_leaf{}) -> leaf.
+
+%% ebb_successors(EBB) ->
+%%   ordsets:from_list(ebb_successors0(EBB)).
+%% 
+%% ebb_successors0(#ebb_leaf{successor=NextEBB}) ->
+%%   [NextEBB];
+%% ebb_successors0(#ebb_node{successors=SuccessorNodes}) ->
+%%   lists:append(lists:map(fun ebb_successors0/1, SuccessorNodes)).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Prettyprint a list of extended basic blocks
+%%
+
+-ifdef(DEBUG_EBB).
+
+pp(EBBs) ->
+  lists:map(fun(E) -> pp(E, 0) end, EBBs).
+
+pp(EBB, Indent) ->
+  io:format([$~]++integer_to_list(Indent)++[$c],[$ ]),
+  case type(EBB) of
+    node ->
+      io:format("~w~n", [node_label(EBB)]),
+      lists:map(fun(E) -> pp(E, Indent+3) end, node_successors(EBB));
+    leaf ->
+      io:format("* -> ~w~n", [leaf_next(EBB)])
+  end.
+
+-endif.
diff --git a/lib/hipe/flow/hipe_bb.erl b/lib/hipe/flow/hipe_bb.erl
new file mode 100644
index 0000000000..16730f1dce
--- /dev/null
+++ b/lib/hipe/flow/hipe_bb.erl
@@ -0,0 +1,81 @@
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-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%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Basic Block Module
+%%
+%% Exports:
+%% ~~~~~~~~
+%% mk_bb(Code) - construct a basic block.
+%% code(BB) - returns the code.
+%% code_update(BB, NewCode) - replace the code in a basic block.
+%% last(BB) - returns the last instruction.
+%% butlast(BB) - returns the code with the last instruction removed.
+%%
+
+-module(hipe_bb).
+
+-export([mk_bb/1,
+	 code/1,
+	 code_update/2,
+	 is_bb/1,
+	 last/1,
+	 butlast/1]).
+
+-include("hipe_bb.hrl").
+
+%%
+%% Constructs a basic block.
+%% Returns a basic block: {bb, Code}
+%%   * Code is a list of instructions
+
+-spec mk_bb([_]) -> bb().
+
+mk_bb(Code) ->
+    #bb{code=Code}.
+
+-spec is_bb(_) -> boolean().
+
+is_bb(#bb{}) -> true;
+is_bb(_) -> false.
+
+-spec code_update(bb(), [_]) -> bb().
+
+code_update(BB, Code) ->
+    BB#bb{code = Code}.
+
+-spec code(bb()) -> [_].
+
+code(#bb{code = Code}) -> 
+    Code.
+
+-spec last(bb()) -> _.
+
+last(#bb{code = Code}) -> 
+    lists:last(Code).
+
+-spec butlast(bb()) -> [_].
+
+butlast(#bb{code = Code}) ->
+    butlast_1(Code).
+
+butlast_1([X|Xs]) -> butlast_1(Xs,X).
+
+butlast_1([X|Xs],Y) -> [Y|butlast_1(Xs,X)];
+butlast_1([],_) -> [].
diff --git a/lib/hipe/flow/hipe_bb.hrl b/lib/hipe/flow/hipe_bb.hrl
new file mode 100644
index 0000000000..f4d426dad1
--- /dev/null
+++ b/lib/hipe/flow/hipe_bb.hrl
@@ -0,0 +1,30 @@
+%%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2007-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    : bb.hrl
+%%% Author  : Per Gustafsson <[email protected]>
+%%% Description : Typed record declaration for basic blocks 
+%%%
+%%% Created : 20 Dec 2007 by Per Gustafsson <[email protected]>
+%%%-------------------------------------------------------------------
+
+-record(bb, {code=[] :: [_]}).
+
+-type bb() :: #bb{}.
diff --git a/lib/hipe/flow/hipe_dominators.erl b/lib/hipe/flow/hipe_dominators.erl
new file mode 100644
index 0000000000..3bfa6d43c4
--- /dev/null
+++ b/lib/hipe/flow/hipe_dominators.erl
@@ -0,0 +1,715 @@
+%% -*- 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_dominators.erl
+%% Author  : Christoffer Vikstr�m <[email protected]>
+%%           Daniel Deogun        <[email protected]>
+%%           Jesper Bengtsson     <[email protected]>
+%% Created : 18 Mar 2002
+%%
+%% @doc
+%%   Contains utilities for creating and manipulating dominator trees
+%%   and dominance frontiers from a CFG.
+%% @end
+%%------------------------------------------------------------------------ 
+-module(hipe_dominators).
+
+-export([domTree_create/1,
+	 domTree_getChildren/2,
+	 domTree_dominates/3,
+	 domFrontier_create/2,
+	 domFrontier_get/2]).
+
+-include("cfg.hrl").
+
+%%========================================================================
+%%
+%% CODE FOR CREATING AND MANIPULATING DOMINATOR TREES.
+%%
+%%========================================================================
+
+-record(workDataCell, {dfnum = 0       :: non_neg_integer(),
+		       dfparent = none :: 'none' | cfg_lbl(),
+		       semi = none     :: 'none' | cfg_lbl(),
+		       ancestor = none :: 'none' | cfg_lbl(),
+		       best = none     :: 'none' | cfg_lbl(),
+		       samedom = none  :: 'none' | cfg_lbl(), 
+		       bucket = []     :: [cfg_lbl()]}).
+
+-record(domTree, {root                     :: cfg_lbl(),
+		  size  = 0		   :: non_neg_integer(),
+		  nodes = gb_trees:empty() :: gb_tree()}).
+-type domTree() :: #domTree{}.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_create/1
+%% Purpose   : Creates a complete dominator tree given a CFG.
+%% Arguments : CFG - a Control Flow Graph representation
+%% Returns   : A dominator tree
+%%>----------------------------------------------------------------------<
+
+-spec domTree_create(cfg()) -> domTree().
+
+domTree_create(CFG) ->
+  {WorkData, DFS, N} = dfs(CFG),
+  DomTree = domTree_empty(hipe_gen_cfg:start_label(CFG)),
+  {DomData, WorkData2} = getIdoms(CFG, DomTree, WorkData, N, DFS),
+  finalize(WorkData2, DomData, 1, N, DFS).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_empty/0
+%% Purpose   : Creates an empty dominator tree.
+%% Arguments : The root node
+%% Returns   : A dominator tree
+%%>----------------------------------------------------------------------<
+
+domTree_empty(Node) ->
+  #domTree{root = Node}.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_createNode/2
+%% Purpose   : Creates a new node and inserts it into the dominator tree. 
+%% Arguments : Node    - The new node
+%%             DomTree - The target dominator tree
+%% Returns   : A dominator tree
+%%>----------------------------------------------------------------------<
+
+domTree_createNode(Node, DomTree) ->
+  DomTree2 = domTree_setNodes(DomTree,
+			      gb_trees:enter(Node, {none,[]},
+					     domTree_getNodes(DomTree))),
+  domTree_incSize(DomTree2).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_getNode/2
+%% Purpose   : Returns a specific node in the dominator tree.
+%% Arguments : Node - The new node
+%%             DomTree - The target dominator tree
+%% Returns   : Node
+%%>----------------------------------------------------------------------<
+
+domTree_getNode(Node, DomTree) ->
+  gb_trees:lookup(Node, domTree_getNodes(DomTree)).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_getNodes/1
+%% Purpose   : Retrieves the nodes from a dominator tree.
+%% Arguments : DomTree - The target dominator tree
+%% Returns   : A map containing the nodes of the dominator tree.
+%%>----------------------------------------------------------------------<
+
+domTree_getNodes(#domTree{nodes=Nodes}) -> Nodes.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_setNodes/2
+%% Purpose   : Replaces the set of nodes in a dominator tree with a 
+%%             new set of nodes.
+%% Arguments : Nodes   - The new set of nodes
+%%             DomTree - The target dominator tree
+%% Returns   : DomTree
+%%>----------------------------------------------------------------------<
+
+domTree_setNodes(DomTree, Nodes) -> DomTree#domTree{nodes = Nodes}.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_setSize/2
+%% Purpose   : Sets the size of the dominator tree, i.e. the number of 
+%%             nodes in it.
+%% Arguments : Size    - The new size of the target dominator tree
+%%             DomTree - The target dominator tree
+%% Returns   : A dominator tree
+%%>----------------------------------------------------------------------<
+
+domTree_setSize(DomTree, Size) -> DomTree#domTree{size = Size}.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_incSize/1
+%% Purpose   : Increases the size of the dominator tree with one.
+%% Arguments : DomTree - The target dominator tree
+%% Returns   : DomTree
+%%>----------------------------------------------------------------------<
+
+domTree_incSize(DomTree) ->
+  Size = domTree_getSize(DomTree),
+  domTree_setSize(DomTree, Size + 1).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : get IDom/2
+%% Purpose   : Retrieves the immediate dominators of a node in the 
+%%             dominator tree.
+%% Arguments : Node    - The new node
+%%             DomTree - The target dominator tree
+%% Returns   : The immediate dominator
+%%>----------------------------------------------------------------------<
+
+domTree_getIDom(Node, DomTree) ->
+  case domTree_getNode(Node, DomTree) of
+    {value, {IDom, _}} ->
+      IDom;
+    none ->
+      []
+  end.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : getChildren/2
+%% Purpose   : Retrieves the children of a node in the dominator tree.
+%% Arguments : Node    - The new node
+%%             DomTree - The target dominator tree
+%% Returns   : [children]
+%%>----------------------------------------------------------------------<
+
+-spec domTree_getChildren(cfg_lbl(), domTree()) -> [cfg_lbl()].
+
+domTree_getChildren(Node, DomTree) ->
+  case domTree_getNode(Node, DomTree) of
+    {value, {_, Children}} ->
+      Children;
+    none ->
+      []
+  end.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_getSize/1
+%% Purpose   : Retrieves the size of a dominator tree.
+%% Arguments : DomTree - The target dominator tree
+%% Returns   : A number denoting the size of the dominator tree
+%%>----------------------------------------------------------------------<
+
+domTree_getSize(#domTree{size=Size}) -> Size.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_getRoot/2
+%% Purpose   : Retrieves the number of the root node in the dominator tree.
+%% Arguments : DomTree - The target dominator tree
+%% Returns   : Number
+%%>----------------------------------------------------------------------<
+
+domTree_getRoot(#domTree{root=Root}) -> Root.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_addChild/3
+%% Purpose   : Inserts a new node as a child to another node in the
+%%             dominator tree.
+%% Arguments : Node    - The old node that should get a new child
+%%             Child   - The new child node
+%%             DomTree - The target dominator tree
+%% Returns   : DomTree
+%%>----------------------------------------------------------------------<
+
+domTree_addChild(Node, Child, DomTree) ->
+  {IDom, Children} = case domTree_getNode(Node, DomTree) of
+		       {value, Tuple} ->
+			 Tuple;
+		       none ->
+			 {none, []}
+		     end,
+  Nodes = case lists:member(Child, Children) of 
+	    true ->
+	      domTree_getNodes(DomTree);
+	    false ->
+	      gb_trees:enter(Node, {IDom, [Child|Children]},
+			     domTree_getNodes(DomTree))
+	  end,
+  domTree_setNodes(DomTree, Nodes).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : setIDom/3
+%% Purpose   : Sets the immediate domminator of a node in the domminator tree.
+%% Arguments : Node    - The node whose immediate domminator we are seting
+%%             IDom    - The immediate domminator
+%%             DomTree - The target dominator tree
+%% Returns   : DomTree
+%% Notes     : Is used to build the dominator tree.
+%%>----------------------------------------------------------------------<
+
+setIDom(Node, IDom, DomTree) ->
+  DomTree1 = case domTree_getNode(Node, DomTree) of
+	       none ->
+		 domTree_createNode(Node, DomTree);
+	       _ ->
+		 DomTree
+	     end,
+  DomTree2 = domTree_addChild(IDom, Node, DomTree1),
+  {value, {_, Children}} = domTree_getNode(Node, DomTree2),
+  domTree_setNodes(DomTree2,
+		   gb_trees:enter(Node, {IDom, Children},
+				  domTree_getNodes(DomTree2))).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : lookup
+%% Purpose   : This function is used as a wrapper for the lookup function.
+%%             The function retrieves a particular element (defined by
+%%             Field) stored in a workDataCell in the table (defined by
+%%             Table).
+%% Arguments : Field - Value defined in the workDataCell record
+%%             Key   - Value used as a key in the table
+%%             Table - Table storing workDataCells
+%% Returns   : A value defined in the workDataCell record
+%%>----------------------------------------------------------------------<
+
+lookup({Field, Key}, Table) when is_integer(Key) ->
+  WD = lookup_table(Key, Table),
+  case Field of
+    ancestor -> WD#workDataCell.ancestor;
+    best     -> WD#workDataCell.best;
+    bucket   -> WD#workDataCell.bucket;
+    dfnum    -> WD#workDataCell.dfnum; 
+    dfparent -> WD#workDataCell.dfparent; 
+    samedom  -> WD#workDataCell.samedom;
+    semi     -> WD#workDataCell.semi    
+  end.
+
+lookup_table(Key, Table) when is_integer(Key) ->
+  case gb_trees:lookup(Key, Table) of
+    {value, Data} ->
+      Data;
+    none ->
+      #workDataCell{}
+  end.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : update
+%% Purpose   : This function is used as a wrapper for the update function 
+%%             The main purpose of the update function is therefore
+%%             change a particular cell in the table (Table) to the
+%%             value given as an argument (Value).
+%% Arguments : Key   - Value used as a key in the table
+%%             Field - Value defined in the workDataCell record.
+%%             Value - The new value that should replace the old in the table
+%%             Table - Table storing workDataCells
+%% Returns   : NewTable               
+%%>----------------------------------------------------------------------<
+
+update(Key, {Field, Value}, Table) ->
+  gb_trees:enter(Key, updateCell(Value, Field, lookup_table(Key, Table)), Table);
+update(Key, List, Table) ->
+  gb_trees:enter(Key, update(List, lookup_table(Key, Table)), Table).
+
+update([{Field, Value} | T], WD) -> 
+  update(T, updateCell(Value, Field, WD));
+update([], WD) -> WD.
+
+updateCell(Value, Field, WD) ->
+  case Field of
+    dfnum    -> WD#workDataCell{dfnum   = Value}; 
+    dfparent -> WD#workDataCell{dfparent= Value}; 
+    semi     -> WD#workDataCell{semi    = Value}; 
+    ancestor -> WD#workDataCell{ancestor= Value}; 
+    best     -> WD#workDataCell{best    = Value}; 
+    samedom  -> WD#workDataCell{samedom = Value}; 
+    bucket   -> WD#workDataCell{bucket  = Value}
+  end.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : dfs/1
+%% Purpose   : The main purpose of this function is to traverse the CFG in
+%%             a depth first order. It is aslo used to initialize certain 
+%%             elements defined in a workDataCell.
+%% Arguments : CFG - a Control Flow Graph representation
+%% Returns   : A table (WorkData) and the total number of elements in
+%%             the CFG.
+%%>----------------------------------------------------------------------<
+
+dfs(CFG) ->
+  {WorkData, DFS, N} = dfs(CFG, hipe_gen_cfg:start_label(CFG), 
+			   none, 1, gb_trees:empty(), gb_trees:empty()),
+  {WorkData, DFS, N-1}.
+
+dfs(CFG, Node, Parent, N, WorkData, DFS) ->
+  case lookup({dfnum, Node}, WorkData) of
+    0 -> 	  
+      WorkData2 = update(Node, [{dfnum, N}, {dfparent, Parent}, 
+				{semi, Node}, {best, Node}], WorkData),
+      DFS2 = gb_trees:enter(N, Node, DFS),
+      dfsTraverse(hipe_gen_cfg:succ(CFG, Node), CFG, Node, 
+		  N + 1, WorkData2, DFS2);
+    _ -> {WorkData, DFS, N}
+  end.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : dfsTraverse/6
+%% Purpose   : This function acts as a help function for the dfs algorithm
+%%             in the sence that it traverses a list of nodes given by the 
+%%             CFG. 
+%% Arguments : Node     - The first element in the node list
+%%             SuccLst  - The remainder of the node list
+%%             CFG      - Control Flow Graph representation
+%%             Parent   - Node representing the parent of the Node defined
+%%                        above.
+%%             N        - The total number of processed nodes.
+%%             WorkData - Table consisting of workDataCells
+%% Returns   : An updated version of the table (WorkData) and the 
+%%             total number of nodes processed.
+%%>----------------------------------------------------------------------<
+
+dfsTraverse([Node|T], CFG, Parent, N, WorkData, DFS) ->
+  {WorkData2, DFS2, N2} = dfs(CFG, Node, Parent, N, WorkData, DFS),
+  dfsTraverse(T, CFG, Parent, N2, WorkData2, DFS2);
+dfsTraverse([], _, _, N, WorkData, DFS) -> {WorkData, DFS, N}.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : getIdoms/6
+%% Purpose   : The purpose of this function is to compute the immediate
+%%             dominators. This is accomplished by traversing the CFG nodes
+%%             by their depth first number in a bottom up manner. That is, 
+%%             the nodes are processed in a backward order (highest to 
+%%             lowest number).
+%% Arguments : CFG      - Control Flow Graph representation
+%%             DomData  - Table consisting of domTree cells
+%%             WorkData - Table consisting of workDataCells
+%%             Index    - The index used for retrieving the node to be 
+%%                        processed
+%% Returns   : An updated version of the tables DomData and WorkData
+%%>----------------------------------------------------------------------<
+
+getIdoms(CFG, DomData, WorkData, Index, DFS)
+     when is_integer(Index), Index > 1 ->
+  Node = lookup_table(Index, DFS),
+  PredLst = hipe_gen_cfg:pred(CFG, Node),
+  Par = lookup({dfparent, Node}, WorkData),
+  DfNumN = lookup({dfnum, Node}, WorkData),
+  {S, WorkData2} = getSemiDominator(PredLst, DfNumN, Par, WorkData),
+  WorkData3 = update(Node, {semi, S}, WorkData2),
+  OldBucket = lookup({bucket, S}, WorkData3),
+  WorkData4 = update(S, {bucket, [Node | OldBucket]}, WorkData3),
+  WorkData5 = linkTrees(Par, Node, WorkData4),
+  {WorkData6, DomData2} = filterBucket(lookup({bucket, Par}, WorkData5), 
+				       Par, WorkData5, DomData),
+  WorkData7 = update(Par, {bucket, []}, WorkData6),
+  getIdoms(CFG, DomData2, WorkData7, Index - 1, DFS);
+getIdoms(_, DomData, WorkData, 1, _) ->
+  {DomData, WorkData}.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : getSemiDominator/4
+%% Purpose   : The main purpose of this algorithm is to compute the semi 
+%%             dominator of the node Node based on the Semidominator Theorem
+%% Arguments : Preds    - The list of predecessors of the node Node
+%%             Node     - Node in the CFG
+%%             S        - Parent of node Node (depth first parent)
+%%             WorkData - Table consisting of workDataCells
+%% Returns   : A tuple containing the semidominator and an updated version
+%%             of the table WorkData.
+%%>----------------------------------------------------------------------<
+
+getSemiDominator([Pred|Preds], DfNumChild, S, WorkData) ->
+  {Sp, WorkData3} = 
+    case lookup({dfnum, Pred}, WorkData) =< DfNumChild of
+      true  -> 
+	{Pred, WorkData};
+      false ->  
+	{AncLowSemi, WorkData2} = getAncestorWithLowestSemi(Pred, WorkData),	
+	{lookup({semi, AncLowSemi}, WorkData2), WorkData2}
+    end,
+  S2 = case lookup({dfnum, Sp}, WorkData3) < lookup({dfnum, S}, WorkData3) of
+	 true  -> Sp;
+	 false -> S
+       end,
+  getSemiDominator(Preds, DfNumChild, S2, WorkData3);
+getSemiDominator([], _, S, WorkData) ->
+  {S, WorkData}.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : getAncestorWithLowestSemi/2
+%% Purpose   : The main purpose of this function is to retrieve the ancestor 
+%%             of a node with the lowest depth first number (semi). The
+%%             function is also using path compression, i.e. it remembers the
+%%             best node (the one with the lowest semi number) and hence the
+%%             algorithm is only processing the minimal number of nodes.
+%% Arguments : Node     - Node in the tree
+%%             WorkData - Table consisting of workDataCells
+%% Returns   : A node (the one with the lowest semi) and an updated version
+%%             of the table WorkData.
+%%>----------------------------------------------------------------------<
+
+getAncestorWithLowestSemi(Node, WorkData) ->
+  Best = lookup({best, Node}, WorkData),
+  case lookup({ancestor, Node}, WorkData) of
+    none -> {Best, WorkData};
+    A -> 
+      case lookup({ancestor, A}, WorkData) of
+	none -> 
+	  {Best, WorkData};
+	_ -> 
+	  {B, WorkData2} = getAncestorWithLowestSemi(A, WorkData),
+	  AncA = lookup({ancestor, A}, WorkData2),
+	  WorkData3 = update(Node, {ancestor, AncA}, WorkData2),
+	  DfSemiB = lookup({dfnum, lookup({semi, B}, WorkData3)}, WorkData3),
+	  BestN = lookup({best, Node}, WorkData3),
+	  SemiB = lookup({semi, BestN}, WorkData3),
+	  DfSemiBestN = lookup({dfnum, SemiB}, WorkData3),
+	  case DfSemiB < DfSemiBestN of
+	    true  ->
+	      {B, update(Node, {best, B}, WorkData3)};
+	    false -> 
+	      {BestN, WorkData3}
+	  end
+      end
+  end.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : linkTrees/3
+%% Purpose   : The main purpose of this function is to combine two trees
+%%             into one (accomplished by setting the ancestor for node 
+%%             Node to Parent). The algorithm is also updating the best field
+%%             in the workDataCell for node Node to the value of itself.
+%% Arguments : Parent   - The parent of the node Node.
+%%             Node     - The node to process
+%%             WorkData - Table consisting of workDataCells
+%% Returns   : An updated version of table WorkData
+%%>----------------------------------------------------------------------<
+
+linkTrees(Parent, Node, WorkData) ->
+  update(Node, [{ancestor, Parent}, {best, Node}], WorkData).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : filterBucket/4 
+%% Purpose   : The purpose of this algorith is to compute the dominator of
+%%             the node Node by utilizing the first clause of the Dominator
+%%             Theorem. If the first clause of the theorem doesn't apply 
+%%             then the computation of that particular node is deferred to
+%%             a later stage (see finalize).
+%% Arguments : Nodes    - The list of CFG nodes that need to be computed.
+%%             Parent   - The parent of the nodes in the list Nodes
+%%             WorkData - Table consisting of workDataCells
+%%             DomData  - Table consisting of domTree cells.
+%% Returns   : An updated version of the tables WorkData and DomData
+%%>----------------------------------------------------------------------<
+
+filterBucket([Node|Nodes], Parent, WorkData, DomData) ->
+  {Y, WorkData2} = getAncestorWithLowestSemi(Node, WorkData),
+  {WorkData3, DomData2} = 
+    case lookup({semi, Y}, WorkData2) =:= lookup({semi, Node}, WorkData2) of
+      true  -> {WorkData2, setIDom(Node, Parent, DomData)};
+      false -> {update(Node, {samedom, Y}, WorkData2), DomData}
+    end,
+  filterBucket(Nodes, Parent, WorkData3, DomData2);
+filterBucket([], _, WorkData, DomData) ->
+  {WorkData, DomData}.	     
+
+%%>----------------------------------------------------------------------<
+%% Procedure : finalize/5
+%% Purpose   : This algorithm finishes up the second clause of the Dominator
+%%             Theorem. Hence, the main purpose of this function is therefore
+%%             to update the dominator tree with the nodes that were deferred
+%%             in the filterBucket algorithm.
+%% Arguments : WorkData - Table consisting of workDataCells
+%%             DomData  - Table consisting of domTree cells
+%%             N        - The index used for retrieving the node to be 
+%%                        processed
+%%             Max      - Maximum node index
+%% Returns   : An updated version of the table DomData
+%%>----------------------------------------------------------------------<
+
+finalize(WorkData, DomData, N, Max, DFS) when N =< Max ->
+  Node = lookup_table(N, DFS),
+  case lookup({samedom, Node}, WorkData) of
+    none ->
+      finalize(WorkData, DomData, N + 1, Max, DFS);
+    SameDomN -> 
+      case domTree_getIDom(SameDomN, DomData) of
+	IdomSameDomN when is_integer(IdomSameDomN) ->
+	  DomData2 = setIDom(Node, IdomSameDomN, DomData),
+	  finalize(WorkData, DomData2, N + 1, Max, DFS)
+      end
+  end;
+finalize(_, DomData, _, _, _) ->
+  DomData.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domTree_dominates/3
+%% Purpose   : checks wheter Node1 dominates Node2 with respect to the
+%%             dominator tree DomTree
+%% Arguments : Node1 the possible dominator, Node2 which might be dominated 
+%%             and DomTree  - the target dominator tree.
+%% Notes     : Relies on lists:any to return false when the a list is empty
+%%>----------------------------------------------------------------------<     
+
+-spec domTree_dominates(cfg_lbl(), cfg_lbl(), domTree()) -> boolean().
+
+domTree_dominates(Node1, Node1, _DomTree) ->
+  true;
+domTree_dominates(Node1, Node2, DomTree) ->
+  Children = domTree_getChildren(Node1, DomTree),
+  lists:any(fun(X) -> domTree_dominates(X, Node2, DomTree) end, Children).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : pp/1
+%% Purpose   : Pretty Printing a dominator tree.
+%% Arguments : DomTree  - the target dominator tree.
+%% Notes     : Uses pp/2 and pp_children to perform its task.
+%%>----------------------------------------------------------------------<     
+
+-ifdef(DEBUG).
+
+domTree_pp(DomTree) ->
+  io:format("Domtree:\nRoot: ~w\nSize: ~w\n", [domTree_getRoot(DomTree),
+					       domTree_getSize(DomTree)]),
+  domTree_pp(domTree_getRoot(DomTree), DomTree).
+
+domTree_pp(N, DomTree) ->
+  case domTree_getNode(N, DomTree) of
+    {value, {IDom, Children}} ->
+      io:format("Node: ~w\n\tIDom: ~w\n\tChildren: ~w\n\n",
+		[N, IDom, Children]),
+      domTree_pp_children(Children, DomTree);
+    none ->
+      failed
+  end.
+
+domTree_pp_children([Child|T], DomTree) ->
+  domTree_pp(Child, DomTree),
+  domTree_pp_children(T, DomTree);
+domTree_pp_children([], _) ->
+  ok.
+
+-endif.	%% DEBUG
+
+%%========================================================================
+%%
+%% CODE FOR CREATING AND MANIPULATING DOMINANCE FRONTIERS.
+%%
+%%========================================================================
+
+-type domFrontier() :: gb_tree().
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domFrontier_create
+%% Purpose   : This function calculates the Dominance Frontiers given
+%%             a CFG and a Dominator Tree.
+%% Arguments : SuccMap - The successor map of the CFG we are working with.
+%%             DomTree - The dominance tree of the CFG.
+%% Notes     : DomTree must actually be the dominance tree of the CFG.
+%%>----------------------------------------------------------------------<
+
+-spec domFrontier_create(cfg(), domTree()) -> domFrontier().
+
+domFrontier_create(SuccMap, DomTree) ->
+  df_create(domTree_getRoot(DomTree), SuccMap, DomTree, df__empty()).
+
+df_create(Node, SuccMap, DomTree, DF) ->
+  Children = domTree_getChildren(Node, DomTree),
+  Succ = hipe_gen_cfg:succ(SuccMap, Node),
+  DF1 = checkIDomList(Succ, Node, DomTree, DF),
+  makeDFChildren(Children, Node, SuccMap, DomTree, DF1).
+
+%%>----------------------------------------------------------------------<
+%% Procedure : domFrontier_get
+%% Purpose   : This function returns the Dominance Frontier for Node.
+%% Arguments : Node - The node whose Dominance Frontier we request
+%%             DF   - The Dominance Frontier structure
+%% Returns   : 
+%%>----------------------------------------------------------------------<
+
+-spec domFrontier_get(cfg_lbl(), domFrontier()) -> [cfg_lbl()].
+
+domFrontier_get(Node, DF) ->
+  case gb_trees:lookup(Node, DF) of
+    {value, List} -> List;
+    none -> []
+  end.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : df__empty
+%% Purpose   : This function creates an empty instance of the Dominance
+%%             Frontiers (DF) structure.
+%%>----------------------------------------------------------------------<
+
+df__empty() ->
+  gb_trees:empty().
+
+%%>----------------------------------------------------------------------<
+%% Procedure : df__add
+%% Purpose   : This function adds Node to N in DF.
+%% Arguments : N    - The value being inserted
+%%             Node - The node getting the value
+%%             DF   - The Dominance Frontiers
+%% Returns   : DF
+%% Notes     : If Node already exists at position N, it is not added again.
+%%>----------------------------------------------------------------------<
+
+df__add_to_node(N, Node, DF) ->
+  case gb_trees:lookup(N, DF) of
+    {value, DFList} ->
+      case lists:member(Node, DFList) of
+	true ->
+	  DF;
+	false ->
+	  gb_trees:update(N, [Node|DFList], DF)
+      end;
+    none ->
+      gb_trees:insert(N, [Node], DF)
+  end.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : makeDFChildren
+%% Purpose   : This function calculates the dominance frontiers of the
+%%             children of the parent and adds the nodes in these
+%%             dominance frontiers who are not immediate dominantors of
+%%             the parent to parents dominance frontier.
+%% Arguments : ChildList - The list of children that the function traverses
+%%             Parent - The parent of the children
+%%             SuccMap - The successor map of the CFG
+%%             DomTree - The dominantor tree of the CFG
+%%             DF - The dominance frontiers so far
+%%>----------------------------------------------------------------------<
+
+makeDFChildren([Child|T], Parent, SuccMap, DomTree, DF) ->
+  DF1 = df_create(Child, SuccMap, DomTree, DF),
+  DF2 = checkIDomList(domFrontier_get(Child, DF1), Parent, DomTree, DF1),
+  makeDFChildren(T, Parent, SuccMap, DomTree, DF2);
+makeDFChildren([], _, _, _, DF) ->
+  DF.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : checIDomList
+%% Purpose   : Adds all the nodes in the list to the parents dominance
+%%             frontier who do not have parent as immediate dominator.
+%% Arguments : NodeList - The list of nodes that the function traverses
+%%             Parent - The parent of the nodes
+%%             DomTree - Our dominator tree
+%%             DF - The dominance frontiers so far
+%%>----------------------------------------------------------------------<
+
+checkIDomList([Node|T], Parent, DomTree, DF) ->
+  DF1 = checkIDom(Node, Parent, DomTree, DF),
+  checkIDomList(T, Parent, DomTree, DF1);
+checkIDomList([], _, _, DF) ->
+  DF.
+
+%%>----------------------------------------------------------------------<
+%% Procedure : checkIdom
+%% Purpose   : Adds Node1 to Node2's dominance frontier if Node2 is not
+%%             Node1's immediate dominator.
+%% Arguments : Node1 - a node
+%%             Node2 - another node
+%%             DomTree - the dominator tree
+%%             DF - the dominance frontier so far
+%%>----------------------------------------------------------------------<
+
+checkIDom(Node1, Node2, DomTree, DF) ->
+  case domTree_getIDom(Node1, DomTree) of
+    Node2 ->
+      DF;
+    none ->
+      DF;
+    _ ->
+      df__add_to_node(Node2, Node1, DF)
+  end.
diff --git a/lib/hipe/flow/hipe_gen_cfg.erl b/lib/hipe/flow/hipe_gen_cfg.erl
new file mode 100644
index 0000000000..f9fb1f70c8
--- /dev/null
+++ b/lib/hipe/flow/hipe_gen_cfg.erl
@@ -0,0 +1,37 @@
+%%
+%% %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%
+%%
+
+-module(hipe_gen_cfg).
+
+-export([start_label/1,
+	 succ/2,
+         pred/2
+	]).
+
+%%-define(DO_ASSERT, true).
+-define(GEN_CFG, true).	    % needed for cfg.inc
+
+-include("../main/hipe.hrl").
+-include("cfg.hrl").
+
+-spec succ(cfg(), cfg_lbl()) -> [cfg_lbl()].
+-spec pred(cfg(), cfg_lbl()) -> [cfg_lbl()].
+
+-include("cfg.inc").
+
diff --git a/lib/hipe/flow/liveness.inc b/lib/hipe/flow/liveness.inc
new file mode 100644
index 0000000000..9c5eaf3e68
--- /dev/null
+++ b/lib/hipe/flow/liveness.inc
@@ -0,0 +1,332 @@
+%% -*- Erlang -*-
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2001-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%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% LIVENESS ANALYSIS
+%%
+%% Exports:
+%% ~~~~~~~
+%% analyze(CFG) - returns a liveness analysis of CFG.
+%% liveout(Liveness, Label) - returns a set of variables that are live at
+%%      exit from basic block named Label.
+%% livein(Liveness, Label) - returns a set of variables that are live at
+%%      entry to the basic block named Label.
+%% livein_from_liveout(Instructions, LiveOut) - Given a list of instructions 
+%%      and a liveout-set, returns a set of variables live at the 
+%%      first instruction.
+%%
+
+-export([analyze/1,
+	 livein/2]).
+-ifdef(LIVEOUT_NEEDED).
+-export([liveout/2]).
+-endif.
+-ifdef(PRETTY_PRINT).
+-export([pp/1]).
+-endif.
+%%-export([livein_from_liveout/2]).
+-ifdef(DEBUG_LIVENESS).
+-export([annotate_liveness/2]).
+-endif.
+
+-include("../flow/cfg.hrl").
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Interface functions that MUST be implemented in the including file
+%%
+%% cfg_bb(CFG, L) -> BasicBlock, extract a basic block from a cfg.
+%% cfg_postorder(CFG) -> [Labels], the labels of the cfg in postorder
+%% cfg_succ(CFG, L) -> [Labels], 
+%% uses(Instr) ->
+%% defines(Instr) ->
+%%
+%% Plus the following, if basic block annotations are needed
+%%
+%% cfg_labels(CFG) ->
+%% cfg_bb_add(CFG, L, NewBB) ->
+%% mk_comment(Text) ->
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% The generic liveness analysis
+%%
+
+-spec analyze(cfg()) -> gb_tree().
+
+-ifdef(HIPE_LIVENESS_CALC_LARGEST_LIVESET).
+analyze(CFG) ->
+  PO = cfg_postorder(CFG),
+  InitLiveness = liveness_init(init(cfg_labels(CFG), CFG)),
+  _Max = case get(hipe_largest_liveset) of
+	   undefined ->
+	     put(hipe_largest_liveset, 0),
+	     0;
+	   LL -> LL
+	 end,
+  Res = merry_go_around(PO, InitLiveness,0),
+  case get(hipe_largest_liveset) > _Max of 
+    true ->
+      io:format("Largest liveset: ~w \n", [get(hipe_largest_liveset)]);
+    _ -> ok
+  end,
+  Res.
+
+-else.
+
+analyze(CFG) ->
+  PO = cfg_postorder(CFG),
+  InitLiveness = liveness_init(init(PO, CFG)),
+  Res = merry_go_around(PO, InitLiveness, 0),
+  Res.
+-endif.
+
+%%
+%% The fixpoint iteration
+%%
+
+merry_go_around(Labels, Liveness, Count) ->
+  case doit_once(Labels, Liveness, 0) of
+    {NewLiveness, 0} -> 
+       %% io:format("Iterations ~w~n", [Count]),
+       NewLiveness;
+    {NewLiveness, _Changed} ->
+       merry_go_around(Labels, NewLiveness, Count+1)
+  end.
+
+%%
+%% One iteration
+%%
+
+-ifdef(HIPE_LIVENESS_CALC_LARGEST_LIVESET).
+doit_once([], Liveness, Changed) ->
+  {Liveness, Changed};
+doit_once([L|Ls], Liveness, Changed) ->
+  LiveOut = liveout(Liveness, L),
+  Kill = ordsets:subtract(LiveOut, kill(L, Liveness)),
+  LiveIn = ordsets:union(Kill, gen(L,Liveness)),
+  {NewLiveness, ChangedP} = update_livein(L, LiveIn, Liveness),
+  Le = length(LiveIn),
+  Max = get(hipe_largest_liveset),
+  if Le > Max -> put(hipe_largest_liveset, Le);
+     true -> true
+  end,
+  doit_once(Ls, NewLiveness, Changed+ChangedP).
+
+-else.
+
+doit_once([], Liveness, Changed) ->
+  {Liveness, Changed};
+doit_once([L|Ls], Liveness, Changed) ->
+  LiveOut = liveout(Liveness, L),
+  Kill = ordsets:subtract(LiveOut, kill(L, Liveness)),
+  LiveIn = ordsets:union(Kill, gen(L,Liveness)),
+  {NewLiveness, ChangedP} = update_livein(L, LiveIn, Liveness),
+  doit_once(Ls, NewLiveness, Changed+ChangedP).
+-endif.
+
+%% %%
+%% %% Given a list of instructions and liveout, calculates livein
+%% %%
+%% livein_from_liveout(List, LiveOut) when is_list(List) ->
+%%   livein_from_liveout_1(lists:reverse(List), gb_sets:from_list(LiveOut));
+%% livein_from_liveout(Instr, LiveOut) ->
+%%   livein_from_liveout_1([Instr], gb_sets:from_list(LiveOut)).
+%% 
+%% livein_from_liveout_1([], LiveOut) ->
+%%   gb_sets:to_list(LiveOut);
+%% livein_from_liveout_1([I|Is], LiveOut) ->
+%%   Def = defines(I),
+%%   Use = uses(I),
+%%   DefSet = gb_sets:from_list(Def),
+%%   UseSet = gb_sets:from_list(Use),
+%%   LiveIn = gb_sets:union(gb_sets:difference(LiveOut, DefSet), UseSet),
+%%   Le = gb_sets:size(LiveIn),
+%%   Max = get(hipe_largest_liveset),
+%%   if Le > Max -> put(hipe_largest_liveset, Le);
+%%      true -> true
+%%   end,
+%%   livein_from_liveout_1(Is, LiveIn).
+
+%%
+%% updates liveness for a basic block
+%%    - returns: {NewLiveness, ChangedP} 
+%%    - ChangedP is 0 if the new LiveIn is equal to the old one
+%%      otherwise it's 1.
+%%
+
+update_livein(Label, NewLiveIn, Liveness) ->
+  {GK, LiveIn, Successors} = liveness_lookup(Label, Liveness),
+  NewLiveness = liveness_update(Label, {GK, NewLiveIn, Successors}, Liveness),
+  if LiveIn =:= NewLiveIn ->
+      {NewLiveness, 0};
+  true ->
+      {NewLiveness, 1}
+  end.
+
+
+%%
+%% LiveOut for a block is the union of the successors LiveIn
+%%
+
+liveout(Liveness, L) ->
+  Succ = successors(L, Liveness),
+  case Succ of
+    [] ->    % special case if no successors
+      liveout_no_succ();
+    _ ->
+      liveout1(Succ, Liveness)
+  end.
+
+liveout1(Labels, Liveness) ->
+  liveout1(Labels, Liveness, ordsets:new()).
+
+liveout1([], _Liveness, Live) ->
+  Live;
+liveout1([L|Ls], Liveness,Live) ->
+  liveout1(Ls, Liveness, ordsets:union(livein(Liveness, L), Live)).
+
+successors(L, Liveness) ->
+  {_GK, _LiveIn, Successors} = liveness_lookup(L, Liveness),
+  Successors.
+
+-spec livein(gb_tree(), _) -> [_].
+
+livein(Liveness, L) ->
+  {_GK, LiveIn, _Successors} = liveness_lookup(L, Liveness),
+  LiveIn.
+
+kill(L, Liveness) ->
+  {{_Gen, Kill}, _LiveIn, _Successors} = liveness_lookup(L, Liveness),
+  Kill.
+
+gen(L, Liveness) ->
+  {{Gen, _Kill}, _LiveIn, _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),
+  Transfer = make_bb_transfer(Code, Succ),
+  [{L, {Transfer, ordsets:new(), Succ}} | init(Ls, CFG)].
+
+
+make_bb_transfer([], _Succ) ->
+  {ordsets:new(), ordsets:new()};   % {Gen, Kill}
+make_bb_transfer([I|Is], Succ) ->
+  {Gen, Kill} = make_bb_transfer(Is, Succ),
+  InstrGen = ordsets:from_list(uses(I)),
+  InstrKill = ordsets:from_list(defines(I)),
+  Gen1 = ordsets:subtract(Gen, InstrKill),
+  Gen2 = ordsets:union(Gen1, InstrGen),
+  Kill1 = ordsets:union(Kill, InstrKill),
+  Kill2 = ordsets:subtract(Kill1, InstrGen),
+  {Gen2, Kill2}.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% Annotate each basic block with liveness info
+%%
+
+-ifdef(DEBUG_LIVENESS).
+
+annotate_liveness(CFG, Liveness) ->
+  Labels = cfg_labels(CFG),
+  annotate_liveness_bb(Labels, CFG, Liveness).
+
+annotate_liveness_bb([], CFG, _Liveness) ->
+  CFG;
+annotate_liveness_bb([L|Ls], CFG, Liveness) ->
+  BB = cfg_bb(CFG, L),
+  Code0 = hipe_bb:code(BB), 
+  LiveIn = strip(livein(Liveness, L)),
+  LiveOut = strip(liveout(Liveness, L)),
+  Code = [mk_comment({live_in, LiveIn}),
+	  mk_comment({live_out, LiveOut})
+          | Code0],
+  NewBB = hipe_bb:code_update(BB, Code),
+  NewCFG = cfg_bb_add(CFG, L, NewBB),
+  annotate_liveness_bb(Ls, NewCFG, Liveness).
+
+strip([]) ->
+   [];
+strip([{_,Y}|Xs]) ->
+   [Y|strip(Xs)].
+
+-endif.	% DEBUG_LIVENESS
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+liveness_init(List) ->
+  liveness_init(List, gb_trees:empty()).
+
+liveness_init([{Lbl, Data}|Left], Acc) ->
+  liveness_init(Left, gb_trees:insert(Lbl, Data, Acc));
+liveness_init([], Acc) ->
+  Acc.
+  
+liveness_lookup(Label, Liveness) ->
+  gb_trees:get(Label, Liveness).
+liveness_update(Label, Val, Liveness) ->
+  gb_trees:update(Label, Val, Liveness).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%
+%% pp/1 pretty prints liveness information for a CFG
+%%
+
+-ifdef(PRETTY_PRINT).
+
+-spec pp(cfg()) -> 'ok'.
+pp(Cfg) ->
+  Liveness = analyze(Cfg),
+  Labels = cfg_labels(Cfg),
+  ok = print_blocks(Labels, Liveness, Cfg).
+
+print_blocks([Lbl|Rest], Liveness, Cfg) ->
+  io:format("~nLivein:", []),
+  pp_liveness_info(livein(Liveness, Lbl)),
+  io:format("Label ~w:~n" , [Lbl]),
+  pp_block(Lbl, Cfg),
+  io:format("Liveout:", []),
+  pp_liveness_info(liveout(Liveness, Lbl)),
+  print_blocks(Rest, Liveness, Cfg);
+print_blocks([], _Liveness, _Cfg) ->
+  ok.
+
+-endif. % PRETTY_PRINT