The R13B03 release.OTP_R13B03

1 files changed, 1696 insertions, 0 deletions

diff --git a/lib/hipe/rtl/hipe_rtl_lcm.erl b/lib/hipe/rtl/hipe_rtl_lcm.erl
new file mode 100644
index 0000000000..5d65389d48
--- /dev/null
+++ b/lib/hipe/rtl/hipe_rtl_lcm.erl
@@ -0,0 +1,1696 @@
+%% -*- 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_rtl_lcm.erl
+%% Author      : Henrik Nyman and Erik Cedheim
+%% Description : Performs Lazy Code Motion on RTL
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% @doc
+%%
+%% This module implements Lazy Code Motion on RTL.
+%%
+%% @end
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-module(hipe_rtl_lcm).
+
+-export([rtl_lcm/2]).
+
+-define(SETS, ordsets).   %% Which set implementation module to use
+                          %% We have tried gb_sets, sets and ordsets and
+                          %% ordsets seems to be a lot faster according to 
+                          %% our test runs.
+
+-include("../main/hipe.hrl").
+-include("hipe_rtl.hrl").
+-include("../flow/cfg.hrl").
+
+%%-define(LCM_DEBUG, true). %% When defined and true, produces debug printouts
+
+%%=============================================================================
+
+%%
+%% @doc Performs Lazy Code Motion on RTL.
+%%
+
+-spec rtl_lcm(cfg(), comp_options()) -> cfg().
+
+rtl_lcm(CFG, Options) ->
+  %% Perform pre-calculation of the data sets.
+  ?opt_start_timer("RTL LCM precalc"),
+  {NodeInfo, EdgeInfo, AllExpr, ExprMap, IdMap, Labels} = lcm_precalc(CFG, Options),
+  ?opt_stop_timer("RTL LCM precalc"),
+  %% {NodeInfo, EdgeInfo, AllExpr, ExprMap, Labels} = 
+  %%   ?option_time(lcm_precalc(CFG, Options), "RTL LCM precalc", Options),
+  
+  pp_debug("-------------------------------------------------~n",[]),
+  %% pp_debug( "~w~n", [MFA]),
+  
+  %% A check if we should pretty print the result.
+  case proplists:get_bool(pp_rtl_lcm, Options) of
+    true->
+      pp_debug("-------------------------------------------------~n",[]),
+      %% pp_debug("AllExpr:  ~w~n", [AllExpr]),
+      pp_debug("AllExpr:~n", []),
+      pp_exprs(ExprMap, IdMap, ?SETS:to_list(AllExpr)),
+      %% pp_sets(ExprMap, NodeInfo, EdgeInfo, AllExpr, CFG2<-ERROR!, Labels); 
+      pp_sets(ExprMap, IdMap, NodeInfo, EdgeInfo, AllExpr, CFG, Labels);
+    _ ->
+      ok
+  end,
+  
+  pp_debug("-------------------------------------------------~n",[]),
+  ?option_time({CFG1, MoveSet} = perform_lcm(CFG, NodeInfo, EdgeInfo, ExprMap, 
+					     IdMap, AllExpr, mk_edge_bb_map(), 
+					     ?SETS:new(), Labels),
+	       "RTL LCM perform_lcm", Options),
+
+  %% Scan through list of moved expressions and replace their 
+  %% assignments with the new temporary created for that expression
+  MoveList = ?SETS:to_list(MoveSet),
+  ?option_time(CFG2 = moved_expr_replace_assignments(CFG1, ExprMap, IdMap, 
+						     MoveList),
+	       "RTL LCM moved_expr_replace_assignments", Options),
+  pp_debug("-------------------------------------------------~n~n",[]),
+  
+  CFG2.
+
+%%=============================================================================
+%% Performs lazy code motion given the pre-calculated data sets.
+perform_lcm(CFG, _, _, _, _, _, _, MoveSet, []) ->
+  {CFG, MoveSet};
+perform_lcm(CFG0, NodeInfo, EdgeInfo, ExprMap, IdMap, AllExp, BetweenMap, 
+	    MoveSet0, [Label|Labels]) ->
+  Code0 = hipe_bb:code(hipe_rtl_cfg:bb(CFG0, Label)),
+  DeleteSet = delete(NodeInfo, Label),
+  
+  %% Check if something should be deleted from this block.
+  {CFG1, MoveSet1} = 
+    case ?SETS:size(DeleteSet) > 0 of
+      true ->
+        pp_debug("Label ~w: Expressions Deleted: ~n", [Label]),
+        Code1 = delete_exprs(Code0, ExprMap, IdMap, ?SETS:to_list(DeleteSet)),
+        BB = hipe_bb:mk_bb(Code1),
+        {hipe_rtl_cfg:bb_add(CFG0, Label, BB), 
+         ?SETS:union(MoveSet0, DeleteSet)};
+      false ->
+        {CFG0, MoveSet0}
+    end,
+  
+  Succs = hipe_rtl_cfg:succ(CFG1, Label),  
+  
+  %% Go through the list of successors and insert expression where needed.
+  %% Also collect a list of expressions that are inserted somewhere
+  {CFG2, NewBetweenMap, MoveSet2} = 
+    lists:foldl(fun(Succ, {CFG, BtwMap, MoveSet}) ->
+		    InsertSet = calc_insert_edge(NodeInfo, EdgeInfo, 
+						 Label, Succ),
+		    %% Check if something should be inserted on this edge.
+		    case ?SETS:size(InsertSet) > 0 of
+		      true ->
+			pp_debug("Label ~w: Expressions Inserted for Successor: ~w~n", [Label, Succ]),
+			InsertList = ?SETS:to_list(InsertSet),
+			{NewCFG, NewBtwMap} =
+			  insert_exprs(CFG, Label, Succ, ExprMap, IdMap, 
+				       BtwMap, InsertList),
+			{NewCFG, NewBtwMap, ?SETS:union(MoveSet, InsertSet)};
+		      false ->
+			{CFG, BtwMap, MoveSet}
+		    end
+		end, 
+		{CFG1, BetweenMap, MoveSet1}, Succs),
+  
+  perform_lcm(CFG2, NodeInfo, EdgeInfo, ExprMap, IdMap, AllExp, NewBetweenMap, 
+	      MoveSet2, Labels).
+
+%%=============================================================================
+%% Scan through list of moved expressions and replace their 
+%% assignments with the new temporary created for that expression.
+moved_expr_replace_assignments(CFG, _, _, []) ->
+  CFG;
+moved_expr_replace_assignments(CFG0, ExprMap, IdMap, [ExprId|Exprs]) ->
+  Expr = expr_id_map_get_expr(IdMap, ExprId),
+  case expr_map_lookup(ExprMap, Expr) of
+    {value, {_, ReplaceList, NewReg}} -> 
+      CFG1 = lists:foldl(fun({Label, Reg}, CFG) ->
+                      %% Find and replace expression in block
+		      pp_debug("Label ~w: Expressions Replaced:~n", [Label]),
+		      Code0 = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)),
+                      Code1 = 
+                        moved_expr_do_replacement(expr_set_dst(Expr, Reg), 
+                                                  Reg, NewReg, Code0),
+                      hipe_rtl_cfg:bb_add(CFG, Label, hipe_bb:mk_bb(Code1))
+                  end, CFG0, ReplaceList),
+      moved_expr_replace_assignments(CFG1, ExprMap, IdMap, Exprs);
+    none ->
+      moved_expr_replace_assignments(CFG0, ExprMap, IdMap, Exprs)
+  end.
+
+moved_expr_do_replacement(_, _, _, []) ->
+  [];
+moved_expr_do_replacement(Expr, Reg, NewReg, [Expr|Instrs]) ->
+  NewExpr = expr_set_dst(Expr, NewReg),
+  Move = mk_expr_move_instr(Reg, NewReg),
+  pp_debug("  Replacing:~n", []),
+  pp_debug_instr(Expr),
+  pp_debug("  With:~n", []),
+  pp_debug_instr(NewExpr),
+  pp_debug_instr(Move),
+  [NewExpr, Move | moved_expr_do_replacement(Expr, Reg, NewReg, Instrs)];
+moved_expr_do_replacement(Expr, Reg, NewReg, [Instr|Instrs]) ->
+  [Instr | moved_expr_do_replacement(Expr, Reg, NewReg, Instrs)].
+
+%%=============================================================================
+%% Goes through the given list of expressions and deletes them from the code.
+%% NOTE We do not actually delete an expression, but instead we replace it 
+%%      with an assignment from the new temporary containing the result of the 
+%%      expressions which is guaranteed to have been calculated earlier in 
+%%      the code.
+delete_exprs(Code, _, _, []) ->
+  Code;
+delete_exprs(Code, ExprMap, IdMap, [ExprId|Exprs]) ->
+  Expr = expr_id_map_get_expr(IdMap, ExprId),
+  %% Perform a foldl that goes through the code and deletes all
+  %% occurences of the expression.
+  NewCode =
+    lists:reverse
+      (lists:foldl(fun(CodeExpr, Acc) ->
+                     case is_expr(CodeExpr) of
+                       true ->
+                         case expr_clear_dst(CodeExpr) =:= Expr of
+                           true ->
+                             pp_debug("  Deleting:         ", []),
+                             pp_debug_instr(CodeExpr),
+                             %% Lookup expression entry.
+                             Defines = 
+                               case expr_map_lookup(ExprMap, Expr) of
+                                 {value, {_, _, Defs}} -> 
+				   Defs;
+                                 none -> 
+                                   exit({?MODULE, expr_map_lookup,
+                                         "expression missing"})
+                               end,
+                             MoveCode = 
+                               mk_expr_move_instr(hipe_rtl:defines(CodeExpr),
+						  Defines),
+                             pp_debug("    Replacing with: ", []),
+                             pp_debug_instr(MoveCode),
+                             [MoveCode|Acc];
+                           false ->
+                             [CodeExpr|Acc]
+                         end;
+		       false ->
+                             [CodeExpr|Acc]
+                     end
+                   end, 
+		   [], Code)),
+  delete_exprs(NewCode, ExprMap, IdMap, Exprs).
+
+%%=============================================================================
+%% Goes through the given list of expressions and inserts them at 
+%% appropriate places in the code.
+insert_exprs(CFG, _, _, _, _, BetweenMap, []) ->
+  {CFG, BetweenMap};
+insert_exprs(CFG, Pred, Succ, ExprMap, IdMap, BetweenMap, [ExprId|Exprs]) ->
+  Expr = expr_id_map_get_expr(IdMap, ExprId),
+  Instr = expr_map_get_instr(ExprMap, Expr),
+  case hipe_rtl_cfg:succ(CFG, Pred) of
+    [_] ->
+      pp_debug("  Inserted last: ", []),
+      pp_debug_instr(Instr),
+      NewCFG = insert_expr_last(CFG, Pred, Instr),
+      insert_exprs(NewCFG, Pred, Succ, ExprMap, IdMap, BetweenMap, Exprs);
+    _ ->
+      case hipe_rtl_cfg:pred(CFG, Succ) of
+        [_] ->
+	  pp_debug("  Inserted first: ", []),
+	  pp_debug_instr(Instr),
+          NewCFG = insert_expr_first(CFG, Succ, Instr),
+          insert_exprs(NewCFG, Pred, Succ, ExprMap, IdMap, BetweenMap, Exprs);
+        _ ->
+	  pp_debug("  Inserted between: ", []),
+	  pp_debug_instr(Instr),
+          {NewCFG, NewBetweenMap} = 
+	    insert_expr_between(CFG, BetweenMap, Pred, Succ, Instr),
+          insert_exprs(NewCFG, Pred, Succ, ExprMap, IdMap, NewBetweenMap, Exprs)
+      end 
+  end.
+
+%%=============================================================================
+%% Recursively goes through the code in a block and returns a new block
+%% with the new code inserted second to last (assuming the last expression
+%% is a branch operation).
+insert_expr_last(CFG0, Label, Instr) ->
+  Code0 = hipe_bb:code(hipe_rtl_cfg:bb(CFG0, Label)),
+  %% FIXME: Use hipe_bb:butlast() instead?
+  Code1 = insert_expr_last_work(Label, Instr, Code0),
+  hipe_rtl_cfg:bb_add(CFG0, Label, hipe_bb:mk_bb(Code1)).
+
+%%=============================================================================
+%% Recursively goes through the code in a block and returns a new block
+%% with the new code inserted second to last (assuming the last expression
+%% is a branch operation).
+insert_expr_last_work(_, Instr, []) ->
+  %% This case should not happen since this means that block was completely 
+  %% empty when the function was called. For compability we insert it last.
+  [Instr];
+insert_expr_last_work(_, Instr, [Code1]) ->
+  %% We insert the code next to last.
+  [Instr, Code1];
+insert_expr_last_work(Label, Instr, [Code|Codes]) ->
+  [Code|insert_expr_last_work(Label, Instr, Codes)].
+
+%%=============================================================================
+%% Inserts expression first in the block for the given label.
+insert_expr_first(CFG0, Label, Instr) ->
+  %% The first instruction is always a label
+  [Lbl|Code0] = hipe_bb:code(hipe_rtl_cfg:bb(CFG0, Label)),
+  Code1 = [Lbl, Instr | Code0],
+  hipe_rtl_cfg:bb_add(CFG0, Label, hipe_bb:mk_bb(Code1)).
+
+%%=============================================================================
+%% Inserts an expression on and edge between two existing blocks.
+%% It creates a new basic block to hold the expression. 
+%% Created bbs are inserted into BetweenMap to be able to reuse them for 
+%% multiple inserts on the same edge.
+%% NOTE Currently creates multiple blocks for identical expression with the
+%%      same successor. Since the new bb usually contains very few instructions
+%%      this should not be a problem.
+insert_expr_between(CFG0, BetweenMap, Pred, Succ, Instr) ->
+  PredSucc = {Pred, Succ},
+  case edge_bb_map_lookup(BetweenMap, PredSucc) of
+    none ->
+      NewLabel = hipe_rtl:mk_new_label(),
+      NewLabelName = hipe_rtl:label_name(NewLabel),
+      pp_debug("    Creating new bb ~w~n", [NewLabel]),
+      Code = [Instr, hipe_rtl:mk_goto(Succ)],
+      CFG1 = hipe_rtl_cfg:bb_add(CFG0, NewLabelName, hipe_bb:mk_bb(Code)),
+      CFG2 = hipe_rtl_cfg:redirect(CFG1, Pred, Succ, NewLabelName),
+      NewBetweenMap = edge_bb_map_insert(BetweenMap, PredSucc, NewLabelName),
+      pp_debug("    Mapping edge (~w,~w) to label ~w~n", 
+	       [Pred, Succ, NewLabelName]),
+      {CFG2, NewBetweenMap};
+    {value, Label} ->
+      pp_debug("    Using existing new bb for edge (~w,~w) with label ~w~n", 
+	       [Pred, Succ, Label]),
+      {insert_expr_last(CFG0, Label, Instr), BetweenMap}
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%% GENERAL UTILITY FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%=============================================================================
+%% Returns true if the list of registers only contains virtual registers and
+%% no machine registers. 
+no_machine_regs([]) ->
+  true;
+no_machine_regs([Reg|Regs]) ->
+  case hipe_rtl:is_reg(Reg) of
+    true ->
+      N = hipe_rtl:reg_index(Reg),
+      (N >= hipe_rtl_arch:first_virtual_reg()) andalso no_machine_regs(Regs);
+    _ ->
+      case hipe_rtl:is_fpreg(Reg) of
+	true ->
+	  N = hipe_rtl:fpreg_index(Reg),
+	  (N >= hipe_rtl_arch:first_virtual_reg()) andalso no_machine_regs(Regs);
+	_ ->
+	  no_machine_regs(Regs)
+      end
+  end.
+
+%%=============================================================================
+%% Returns true if an RTL instruction is an expression.
+%%
+is_expr(I) ->
+  Defines = hipe_rtl:defines(I),
+  Uses = hipe_rtl:uses(I),
+  
+  %% We don't cosider something that doesn't define anything as an expression.
+  %% Also we don't consider machine registers to be expressions.
+  case length(Defines) > 0 andalso no_machine_regs(Defines)
+    andalso no_machine_regs(Uses) of 
+    true ->
+      case I of
+        #alu{} -> true;
+%%   	#alu{} ->
+%%    	  Dst = hipe_rtl:alu_dst(I),
+%%    	  Src1 = hipe_rtl:alu_src1(I),
+%%    	  Src2 = hipe_rtl:alu_src2(I),
+
+   	  %% Check if dst updates src
+%%    	  case Dst =:= Src1 orelse Dst =:= Src2 of
+%%    	    true ->
+%%    	      false;
+%%    	    false ->
+%%    	      true
+%%    	  end;
+
+	  %% Check if alu expression is untagging of boxed (rX <- vX sub 2)
+%% 	  case hipe_rtl:is_reg(Dst) andalso hipe_rtl:is_var(Src1) andalso 
+%% 	    (hipe_rtl:alu_op(I) =:= sub) andalso hipe_rtl:is_imm(Src2) of
+%% 	    true ->
+%% 	      case hipe_rtl:imm_value(Src2) of
+%% 		2 -> false; %% Tag for boxed. TODO: Should not be hardcoded...
+%% 		_ -> true
+%% 	      end;
+%% 	    false ->
+%% 	      true
+%% 	  end;
+	       
+        #alub{} -> false; %% TODO: Split instruction to consider alu expression?
+        #branch{} -> false;
+        #call{} -> false; %% We cannot prove that a call has no side-effects
+        #comment{} -> false;
+        #enter{} -> false;
+        %% #fail_to{} -> false; %% Deprecated?
+        #fconv{} -> true;
+        #fixnumop{} -> true;
+        #fload{} -> true;
+        #fmove{} -> false;
+        #fp{} -> true;
+        #fp_unop{} -> true;
+        #fstore{} -> false;
+        #goto{} -> false;
+        #goto_index{} -> false;
+        #gctest{} -> false;
+        #label{} -> false;
+        #load{} -> true;
+        #load_address{} ->
+	  case hipe_rtl:load_address_type(I) of
+	    c_const -> false;
+	    closure -> false;	%% not sure whether safe to move; 
+	                        %% also probably not worth it
+	    constant -> true
+	  end;
+        #load_atom{} -> true;
+        #load_word_index{} -> true;
+        #move{} -> false;
+        #multimove{} -> false;
+        #phi{} -> false;
+        #return{} -> false;
+        #store{} -> false;
+        #switch{} -> false
+      end;
+    false ->
+      false
+  end.
+
+%%=============================================================================
+%% Replaces destination of RTL expression with empty list.
+%% 
+expr_set_dst(I, [Dst|_Dsts] = DstList) ->
+  case I of
+    #alu{} -> hipe_rtl:alu_dst_update(I, Dst);
+    #call{} -> hipe_rtl:call_dstlist_update(I, DstList);
+    #fconv{} -> hipe_rtl:fconv_dst_update(I, Dst);
+    #fixnumop{} -> hipe_rtl:fixnumop_dst_update(I, Dst);
+    #fload{} -> hipe_rtl:fload_dst_update(I, Dst);
+    %% #fmove{} -> hipe_rtl:fmove_dst_update(I, Dst);
+    #fp{} -> hipe_rtl:fp_dst_update(I, Dst);
+    #fp_unop{} -> hipe_rtl:fp_unop_dst_update(I, Dst);
+    #load{} -> hipe_rtl:load_dst_update(I, Dst);
+    #load_address{} -> hipe_rtl:load_address_dst_update(I, Dst);
+    #load_atom{} -> hipe_rtl:load_atom_dst_update(I, Dst);
+    #load_word_index{} -> hipe_rtl:load_word_index_dst_update(I, Dst);
+    %% #move{} -> hipe_rtl:move_dst_update(I, Dst);
+    _ -> exit({?MODULE, expr_set_dst, "bad expression"})
+  end.
+
+%%=============================================================================
+%% Replaces destination of RTL expression with empty list.
+%% 
+expr_clear_dst(I) ->
+  case I of
+    #alu{} -> hipe_rtl:alu_dst_update(I, nil);
+    #call{} -> hipe_rtl:call_dstlist_update(I, nil);
+    #fconv{} -> hipe_rtl:fconv_dst_update(I, nil);
+    #fixnumop{} -> hipe_rtl:fixnumop_dst_update(I, nil);
+    #fload{} -> hipe_rtl:fload_dst_update(I, nil);
+    %% #fmove{} -> hipe_rtl:fmove_dst_update(I, nil);
+    #fp{} -> hipe_rtl:fp_dst_update(I, nil);
+    #fp_unop{} -> hipe_rtl:fp_unop_dst_update(I, nil);
+    #load{} -> hipe_rtl:load_dst_update(I, nil);
+    #load_address{} -> hipe_rtl:load_address_dst_update(I, nil);
+    #load_atom{} -> hipe_rtl:load_atom_dst_update(I, nil);
+    #load_word_index{} -> hipe_rtl:load_word_index_dst_update(I, nil);
+    %% #move{} -> hipe_rtl:move_dst_update(I, nil);
+    _ -> exit({?MODULE, expr_clear_dst, "bad expression"})
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%% PRECALC FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%=============================================================================
+%% Pre-calculates the flow analysis and puts the calculated sets in maps for 
+%% easy access later.
+lcm_precalc(CFG, Options) ->
+  %% Calculate use map and expression map.
+  ?option_time({ExprMap, IdMap} = mk_expr_map(CFG), 
+	       "RTL LCM mk_expr_map", Options),
+  ?option_time(UseMap = mk_use_map(CFG, ExprMap), 
+	       "RTL LCM mk_use_map", Options),
+  %% Labels = hipe_rtl_cfg:reverse_postorder(CFG),
+  Labels = hipe_rtl_cfg:labels(CFG),
+  %% StartLabel = hipe_rtl_cfg:start_label(CFG),
+  %% AllExpr = all_exprs(CFG, Labels),
+  AllExpr = ?SETS:from_list(gb_trees:keys(IdMap)),
+
+  %% Calculate the data sets.
+  ?option_time(NodeInfo0 = mk_node_info(Labels), "RTL LCM mk_node_info", 
+	       Options),
+  %% ?option_time(EdgeInfo0 = mk_edge_info(), "RTL LCM mk_edge_info", 
+  %%  	          Options),
+  EdgeInfo0 = mk_edge_info(),
+  ?option_time(NodeInfo1 = calc_up_exp(CFG, ExprMap, NodeInfo0, Labels), 
+	       "RTL LCM calc_up_exp", Options),
+  ?option_time(NodeInfo2 = calc_down_exp(CFG, ExprMap, NodeInfo1, Labels), 
+	       "RTL LCM calc_down_exp", Options),
+  ?option_time(NodeInfo3 = calc_killed_expr(CFG, NodeInfo2, UseMap, AllExpr, 
+					   Labels), 
+	       "RTL LCM calc_killed_exp", Options),
+  ?option_time(NodeInfo4 = calc_avail(CFG, NodeInfo3), 
+	       "RTL LCM calc_avail", Options),
+  ?option_time(NodeInfo5 = calc_antic(CFG, NodeInfo4, AllExpr), 
+	       "RTL LCM calc_antic", Options),
+  ?option_time(EdgeInfo1 = calc_earliest(CFG, NodeInfo5, EdgeInfo0, Labels), 
+  	       "RTL LCM calc_earliest", Options),
+  ?option_time({NodeInfo6, EdgeInfo2} = calc_later(CFG, NodeInfo5, EdgeInfo1),
+	       "RTL LCM calc_later", Options),
+  ?option_time(NodeInfo7 = calc_delete(CFG, NodeInfo6, Labels), 
+	       "RTL LCM calc_delete", Options),
+  {NodeInfo7, EdgeInfo2, AllExpr, ExprMap, IdMap, Labels}.
+
+%%%%%%%%%%%%%%%%%%% AVAILABLE IN/OUT FLOW ANALYSIS %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Fixpoint calculation of anticipated in/out sets.
+%% Uses a worklist algorithm.
+%% Performs the avail in/out flow analysis.
+
+%%=============================================================================
+%% Calculates the available in/out sets, and returns an updated NodeInfo.
+
+calc_avail(CFG, NodeInfo) ->
+  StartLabel = hipe_rtl_cfg:start_label(CFG),
+  Work = init_work([StartLabel]),
+  %% Initialize start node
+  NewNodeInfo = set_avail_in(NodeInfo, StartLabel, ?SETS:new()),
+  calc_avail_fixpoint(Work, CFG, NewNodeInfo).
+
+calc_avail_fixpoint(Work, CFG, NodeInfo) ->
+  case get_work(Work) of
+    fixpoint ->
+      NodeInfo;
+    {Label, NewWork} ->
+      {NewNodeInfo, NewLabels} = calc_avail_node(Label, CFG, NodeInfo),
+      NewWork2 = add_work(NewWork, NewLabels),
+      calc_avail_fixpoint(NewWork2, CFG, NewNodeInfo)
+  end.
+
+calc_avail_node(Label, CFG, NodeInfo) ->
+  %% Get avail in
+  AvailIn = avail_in(NodeInfo, Label),
+
+  %% Calculate avail out
+  AvailOut = ?SETS:union(down_exp(NodeInfo, Label),
+			 ?SETS:subtract(AvailIn,
+					killed_expr(NodeInfo, Label))),
+  
+  {Changed, NodeInfo2} = 
+    case avail_out(NodeInfo, Label) of
+      none ->
+	%% If there weren't any old avail out we use this one.
+	{true, set_avail_out(NodeInfo, Label, AvailOut)};
+      OldAvailOut ->
+	%% Check if the avail outs are equal.
+	case AvailOut =:= OldAvailOut of
+	  true ->
+	    {false, NodeInfo};
+	  false ->
+	    {true, set_avail_out(NodeInfo, Label, AvailOut)}
+	end
+    end,
+
+  case Changed of
+    true ->
+      %% Update AvailIn-sets of successors and add them to worklist
+      Succs = hipe_rtl_cfg:succ(CFG, Label),
+      NodeInfo3 =
+	lists:foldl
+	  (fun(Succ, NewNodeInfo) ->
+	       case avail_in(NewNodeInfo, Succ) of
+		 none ->
+		   %% Initialize avail in to all expressions
+		   set_avail_in(NewNodeInfo, Succ, AvailOut);
+		 OldAvailIn ->
+		   set_avail_in(NewNodeInfo, Succ, 
+				?SETS:intersection(OldAvailIn, AvailOut))
+	       end
+	   end,
+	   NodeInfo2, Succs),
+      {NodeInfo3, Succs};
+    false ->
+      {NodeInfo2, []}
+  end.
+
+%%%%%%%%%%%%%%%%%% ANTICIPATED IN/OUT FLOW ANALYSIS  %%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Fixpoint calculation of anticipated in/out sets.
+%% Uses a worklist algorithm.
+
+%%=============================================================================
+%% Calculates the anicipated in/out sets, and returns an updated NodeInfo.
+calc_antic(CFG, NodeInfo, AllExpr) ->
+  %% Initialize worklist with all nodes in postorder
+  Labels = hipe_rtl_cfg:postorder(CFG),
+  Work = init_work(Labels),
+  calc_antic_fixpoint(Work, CFG, NodeInfo, AllExpr).
+
+calc_antic_fixpoint(Work, CFG, NodeInfo, AllExpr) ->
+  case get_work(Work) of
+    fixpoint ->
+      NodeInfo;
+    {Label, NewWork} ->
+      {NewNodeInfo, NewLabels} = calc_antic_node(Label, CFG, NodeInfo, AllExpr),
+      NewWork2 = add_work(NewWork, NewLabels),
+      calc_antic_fixpoint(NewWork2, CFG, NewNodeInfo, AllExpr)
+  end.
+
+calc_antic_node(Label, CFG, NodeInfo, AllExpr) ->
+  %% Get antic out
+  AnticOut = 
+    case antic_out(NodeInfo, Label) of
+      none -> 
+	case is_exit_label(CFG, Label) of 
+	  true ->
+	    ?SETS:new();
+	  false ->
+	    AllExpr
+	end;
+      
+      AnticOutTemp -> AnticOutTemp
+    end,
+
+  %% Calculate antic in
+  AnticIn = ?SETS:union(up_exp(NodeInfo, Label),
+			?SETS:subtract(AnticOut,
+				       killed_expr(NodeInfo, Label))),
+  {Changed, NodeInfo2} = 
+    case antic_in(NodeInfo, Label) of
+      %% If there weren't any old antic in we use this one.
+      none ->
+	{true, set_antic_in(NodeInfo, Label, AnticIn)};
+
+      OldAnticIn ->
+	%% Check if the antic in:s are equal.
+	case AnticIn =:= OldAnticIn of
+	  true ->
+	    {false, NodeInfo};
+	  false ->
+	    {true, 
+	     set_antic_in(NodeInfo, Label, AnticIn)}
+	end
+    end,
+
+  case Changed of
+    true ->
+      %% Update AnticOut-sets of predecessors and add them to worklist
+      Preds = hipe_rtl_cfg:pred(CFG, Label),
+      NodeInfo3 =
+	lists:foldl
+	  (fun(Pred, NewNodeInfo) ->
+	       case antic_out(NewNodeInfo, Pred) of
+		 none ->
+		   %% Initialize antic out to all expressions
+		   set_antic_out(NewNodeInfo, Pred, AnticIn);
+		 OldAnticOut ->
+		   set_antic_out(NewNodeInfo, Pred, 
+				 ?SETS:intersection(OldAnticOut, AnticIn))
+	       end
+	   end,
+	   NodeInfo2, Preds),
+      {NodeInfo3, Preds};
+    false ->
+      {NodeInfo2, []}
+  end.
+
+%%%%%%%%%%%%%%%%%%%%% LATER / LATER IN FLOW ANALYSIS %%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Fixpoint calculations of Later and LaterIn sets. 
+%% Uses a worklist algorithm.
+%% Note that the Later set is calculated on edges.
+
+%%=============================================================================
+%% Calculates the Later and LaterIn sets, and returns updates of both 
+%% NodeInfo (with LaterIn sets) and EdgeInfo (with Later sets).
+
+calc_later(CFG, NodeInfo, EdgeInfo) ->
+  StartLabel = hipe_rtl_cfg:start_label(CFG),
+  Work = init_work([{node, StartLabel}]),
+  %% Initialize start node
+  NewNodeInfo = set_later_in(NodeInfo, StartLabel, ?SETS:new()),
+  calc_later_fixpoint(Work, CFG, NewNodeInfo, EdgeInfo).
+
+calc_later_fixpoint(Work, CFG, NodeInfo, EdgeInfo) ->
+  case get_work(Work) of
+    {{edge, From, To}, Work2} ->
+      {NewNodeInfo, NewEdgeInfo, AddWork} = 
+	calc_later_edge(From, To, CFG, NodeInfo, EdgeInfo),
+      Work3 = add_work(Work2, AddWork),
+      calc_later_fixpoint(Work3, CFG, NewNodeInfo, NewEdgeInfo);
+    {{node, Label}, Work2} ->
+      AddWork = calc_later_node(Label, CFG),
+      Work3 = add_work(Work2, AddWork),
+      calc_later_fixpoint(Work3, CFG, NodeInfo, EdgeInfo);
+    fixpoint ->
+      {NodeInfo, EdgeInfo}
+  end.
+
+calc_later_node(Label, CFG) ->
+  Succs = hipe_rtl_cfg:succ(CFG, Label),
+  [{edge, Label, Succ} || Succ <- Succs].
+
+calc_later_edge(From, To, _CFG, NodeInfo, EdgeInfo) ->
+  FromTo = {From, To},
+  Earliest = earliest(EdgeInfo, FromTo),
+  LaterIn = later_in(NodeInfo, From),
+  UpExp = up_exp(NodeInfo, From),
+  Later = ?SETS:union(Earliest, ?SETS:subtract(LaterIn, UpExp)),
+  {Changed, EdgeInfo2} =
+    case lookup_later(EdgeInfo, FromTo) of
+      none ->  {true, set_later(EdgeInfo, FromTo, Later)};
+      Later -> {false, EdgeInfo};
+      _Old ->  {true, set_later(EdgeInfo, FromTo, Later)}
+    end,
+  case Changed of 
+    true ->
+      %% Update later in set of To-node
+      case lookup_later_in(NodeInfo, To) of
+	%% If the data isn't set initialize to all expressions
+	none ->
+ 	  {set_later_in(NodeInfo, To, Later), EdgeInfo2, [{node, To}]};
+	OldLaterIn ->
+	  NewLaterIn = ?SETS:intersection(OldLaterIn, Later),
+	  %% Check if something changed
+	  %% FIXME: Implement faster equality test?
+	  case NewLaterIn =:= OldLaterIn of 
+	    true ->
+	      {NodeInfo, EdgeInfo2, []};
+	    false ->
+	      {set_later_in(NodeInfo, To, NewLaterIn),
+	       EdgeInfo2, [{node, To}]}
+	  end
+      end;
+    false ->
+      {NodeInfo, EdgeInfo2, []}
+  end.
+
+%%%%%%%%%%%%%%%%%% UPWARDS/DOWNWARDS EXPOSED EXPRESSIONS %%%%%%%%%%%%%%%%%%%%%%
+%% Calculates upwards and downwards exposed expressions.
+
+%%=============================================================================
+%% Calculates the downwards exposed expression sets for the given labels in
+%% the CFG.
+calc_down_exp(_, _, NodeInfo, []) ->
+  NodeInfo;
+calc_down_exp(CFG, ExprMap, NodeInfo, [Label|Labels]) ->
+  Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)),
+  %% Data = ?SETS:from_list(lists:map(fun expr_clear_dst/1, exp_work(Code))),
+  Data = ?SETS:from_list(get_expr_ids(ExprMap, exp_work(Code))),
+  NewNodeInfo = set_down_exp(NodeInfo, Label, Data),
+  calc_down_exp(CFG, ExprMap, NewNodeInfo, Labels).
+  
+%%=============================================================================
+%% Calculates the upwards exposed expressions sets for the given labels in 
+%% the CFG.
+calc_up_exp(_, _, NodeInfo, []) ->
+  NodeInfo;
+calc_up_exp(CFG, ExprMap, NodeInfo, [Label|Labels]) ->
+  BB = hipe_rtl_cfg:bb(CFG, Label),
+  RevCode = lists:reverse(hipe_bb:code(BB)),
+  Data = ?SETS:from_list(get_expr_ids(ExprMap, exp_work(RevCode))),
+  NewNodeInfo = set_up_exp(NodeInfo, Label, Data),
+  calc_up_exp(CFG, ExprMap, NewNodeInfo, Labels).
+
+%%=============================================================================
+%% Given a list of expression instructions, gets a list of expression ids
+%% from an expression map.
+get_expr_ids(ExprMap, Instrs) ->
+  [expr_map_get_id(ExprMap, expr_clear_dst(I)) || I <- Instrs].
+
+%%=============================================================================
+%% Does the work of the calc_*_exp functions.
+exp_work(Code) ->
+  exp_work([], Code).
+
+exp_work([], [Instr|Instrs]) ->
+  case is_expr(Instr) of
+    true  ->
+      exp_work([Instr], Instrs);
+    false ->
+      exp_work([], Instrs)
+  end;
+exp_work(Exprs, []) ->
+  Exprs;
+exp_work(Exprs, [Instr|Instrs]) ->
+  NewExprs = case is_expr(Instr) of
+	       true ->
+		 exp_kill_expr(Instr, [Instr|Exprs]);
+	       false ->
+		 exp_kill_expr(Instr, Exprs)
+	     end,
+  exp_work(NewExprs, Instrs).
+
+%%=============================================================================
+%% Checks if the given instruction redefines any operands of 
+%% instructions in the instruction list. 
+%% It returns the list of expressions with those instructions that has
+%% operands redefined removed.
+exp_kill_expr(_Instr, []) ->
+  [];
+exp_kill_expr(Instr, [CheckedExpr|Exprs]) ->
+  %% Calls, gctests and stores potentially clobber everything
+  case Instr of
+    #call{} -> [];
+    #gctest{} -> [];
+    #store{} -> [];     %% FIXME: Only regs and vars clobbered, not fregs...
+    #fstore{} -> 
+      %% fstore potentially clobber float expressions
+      [ExprDefine|_] = hipe_rtl:defines(CheckedExpr),
+      case hipe_rtl:is_fpreg(ExprDefine) of
+	true ->
+	  exp_kill_expr(Instr, Exprs);
+	false ->
+	  [CheckedExpr | exp_kill_expr(Instr, Exprs)]
+      end;
+    _ ->
+      InstrDefines = hipe_rtl:defines(Instr),
+      ExprUses     = hipe_rtl:uses(CheckedExpr),
+      Diff         = ExprUses -- InstrDefines,
+      case length(Diff) < length(ExprUses) of  
+	true ->
+	  exp_kill_expr(Instr, Exprs);
+	false ->
+	  [CheckedExpr | exp_kill_expr(Instr, Exprs)]
+      end
+  end.
+     
+%%%%%%%%%%%%%%%%%%%%%%%% KILLED EXPRESSIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%=============================================================================
+%% Calculates the killed expression sets for all given labels.
+calc_killed_expr(_, NodeInfo, _, _, []) ->
+  NodeInfo;
+calc_killed_expr(CFG, NodeInfo, UseMap, AllExpr, [Label|Labels]) ->
+  Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)),
+  KilledExprs = calc_killed_expr_bb(Code, UseMap, AllExpr, ?SETS:new()),
+  NewNodeInfo = set_killed_expr(NodeInfo, Label, KilledExprs),
+  calc_killed_expr(CFG, NewNodeInfo, UseMap, AllExpr, Labels).
+
+%%=============================================================================
+%% Calculates the killed expressions set for one basic block.
+calc_killed_expr_bb([], _UseMap, _AllExpr, KilledExprs) ->
+  KilledExprs;
+calc_killed_expr_bb([Instr|Instrs], UseMap, AllExpr, KilledExprs) ->
+  %% Calls, gctests and stores potentially clobber everything
+  case Instr of
+    #call{} -> AllExpr;
+    #gctest{} -> AllExpr;
+    #store{} -> AllExpr;   %% FIXME: Only regs and vars clobbered, not fregs...
+    #fstore{} -> 
+      %% Kill all float expressions
+      %% FIXME: Make separate function is_fp_expr
+      ?SETS:from_list
+	(lists:foldl(fun(Expr, Fexprs) ->
+			 [Define|_] = hipe_rtl:defines(Expr),
+			 case hipe_rtl:is_fpreg(Define) of
+			   true ->
+			     [Expr|Fexprs];
+			   false ->
+			     Fexprs
+			 end
+		     end, [], ?SETS:to_list(AllExpr)));
+    _ ->
+      case hipe_rtl:defines(Instr) of
+	[] ->
+	  calc_killed_expr_bb(Instrs, UseMap, AllExpr, KilledExprs);
+	[Define|_] ->
+	  NewKilledExprs = use_map_get_expr_uses(UseMap, Define),
+	  calc_killed_expr_bb(Instrs, UseMap, AllExpr,
+			      ?SETS:union(NewKilledExprs, KilledExprs))
+      end
+  end.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%% EARLIEST %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%=============================================================================
+%% Calculates the earliest set for all edges in the CFG.
+
+calc_earliest(_, _, EdgeInfo, []) ->
+  EdgeInfo;
+calc_earliest(CFG, NodeInfo, EdgeInfo, [To|Labels]) ->
+  EmptySet = ?SETS:new(),
+  Preds = hipe_rtl_cfg:pred(CFG, To),
+  NewEdgeInfo =
+    case EmptySet =:= antic_in(NodeInfo, To) of
+      true ->
+	%% Earliest is empty for all edges into this block.
+	lists:foldl(fun(From, EdgeInfoAcc) ->
+			set_earliest(EdgeInfoAcc, {From, To}, EmptySet)
+		    end, EdgeInfo, Preds);
+      false ->
+	lists:foldl(fun(From, EdgeInfoAcc) ->
+			IsStartLabel = (From =:= hipe_rtl_cfg:start_label(CFG)),
+			Earliest = 
+			  calc_earliest_edge(NodeInfo, IsStartLabel, From, To),
+			set_earliest(EdgeInfoAcc, {From, To}, Earliest)
+		    end, EdgeInfo, Preds)
+    end,
+  calc_earliest(CFG, NodeInfo, NewEdgeInfo, Labels).
+  
+%%=============================================================================
+%% Calculates the earliest set for one edge.
+
+calc_earliest_edge(NodeInfo, IsStartLabel, From, To) ->
+  AnticIn = antic_in(NodeInfo, To),
+  AvailOut = avail_out(NodeInfo, From),
+  
+  case IsStartLabel of
+    true ->
+      ?SETS:subtract(AnticIn, AvailOut);
+    false ->
+      AnticOut = antic_out(NodeInfo, From),
+      ExprKill = killed_expr(NodeInfo, From),
+      ?SETS:subtract(?SETS:subtract(AnticIn, AvailOut),
+		     ?SETS:subtract(AnticOut, ExprKill))
+  end.
+%% The above used to be:
+%%
+%% ?SETS:intersection(?SETS:subtract(AnticIn, AvailOut),
+%%                    ?SETS:union(ExprKill, ?SETS:subtract(AllExpr, AnticOut)))
+%%
+%% But it is costly to use the AllExpr, so let's do some tricky set algebra.
+%%
+%% Let A = AnticIn, B = AvailOut, C = ExprKill, D = AnticOut, U = AllExpr
+%% Let n = intersection, u = union, ' = inverse
+%%
+%% Then
+%%    (A - B) n (C u (U - D)) =       <Remove D unless it is in C>
+%%  = (A - B) n ((C u U) - (D - C)) = <But U is the whole universe>
+%%  = (A - B) n (U - (D - C)) =       <We are really meaning the complement>
+%%  = (A - B) n (D - C)' =            <Intersection w complement is subtraction>
+%%  = (A - B) - (D - C)               <Simple enough, let's stop>
+%%
+%% or in other words
+%%   ?SETS:subtract(?SETS:subtract(AnticIn, AvailOut),
+%%                  ?SETS:subtract(AnticOut, ExprKill))
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%% INSERT / DELETE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%=============================================================================
+%% Calculates the insert set for one edge and returns the resulting set.
+%% NOTE This does not modify the EdgeInfo set, since the resulting set is 
+%%      returned and used immediately, instead of being pre-calculated as are 
+%%      the other sets.
+calc_insert_edge(NodeInfo, EdgeInfo, From, To) ->
+  Later = later(EdgeInfo, {From, To}),
+  LaterIn = later_in(NodeInfo, To),	      
+  ?SETS:subtract(Later, LaterIn).
+
+%%=============================================================================
+%% Calculates the delete set for all given labels in a CFG.
+calc_delete(_, NodeInfo, []) ->
+  NodeInfo;
+calc_delete(CFG, NodeInfo, [Label|Labels]) ->
+  case Label =:= hipe_rtl_cfg:start_label(CFG) of
+    true -> 
+      NewNodeInfo = set_delete(NodeInfo, Label, ?SETS:new());
+    false ->
+      UpExp = up_exp(NodeInfo, Label),
+      LaterIn = later_in(NodeInfo, Label),
+      Delete = ?SETS:subtract(UpExp, LaterIn),
+      NewNodeInfo = set_delete(NodeInfo, Label, Delete)
+  end,
+  calc_delete(CFG, NewNodeInfo, Labels).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%% FIXPOINT FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%=============================================================================
+%% Worklist used by the fixpoint calculations.
+%% 
+%% We use gb_sets here, which is optimized for continuous inserts and
+%% membership tests.
+
+init_work(Labels) ->
+  {Labels, [], gb_sets:from_list(Labels)}.
+
+get_work({[Label|Left], List, Set}) ->
+  NewWork = {Left, List, gb_sets:delete(Label, Set)},
+  {Label, NewWork};
+get_work({[], [], _Set}) ->
+  fixpoint;
+get_work({[], List, Set}) ->
+  get_work({lists:reverse(List), [], Set}).
+
+add_work(Work = {List1, List2, Set}, [Label|Labels]) ->
+  case gb_sets:is_member(Label, Set) of
+    true ->
+      add_work(Work, Labels);
+    false ->
+      %%io:format("Adding work: ~w\n", [Label]),
+      add_work({List1, [Label|List2], gb_sets:insert(Label, Set)}, Labels)
+  end;
+add_work(Work, []) ->
+  Work.
+
+%%=============================================================================
+%% Calculates the labels that are the exit labels.
+%% FIXME We do not detect dead-end loops spanning more than one block.
+%%       This could potentially cause a bug in the future...
+%% exit_labels(CFG) ->
+%%   Labels = hipe_rtl_cfg:labels(CFG),
+%%   lists:foldl(fun(Label, ExitLabels) ->
+%%                   Succs = hipe_rtl_cfg:succ(CFG, Label),
+%%                   case Succs of
+%% 		    [] ->
+%%                       [Label|ExitLabels];
+%% 		    [Label] -> %% Count single bb dead-end loops as exit labels
+%%                       [Label|ExitLabels];		      
+%%                     _ ->
+%%                       ExitLabels
+%%                   end
+%%               end, [], Labels ).
+
+%%=============================================================================
+%% Return true if label is an exit label,
+%% i.e. its bb has no successors or itself as only successor.
+is_exit_label(CFG, Label) ->
+  case hipe_rtl_cfg:succ(CFG, Label) of
+    [] -> true;
+    [Label] -> true;
+    _ -> false
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%% DATASET FUNCTIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% The dataset is a collection of data about the CFG. 
+%% It is divided into two parts, NodeInfo and EdgeInfo.
+%% The pre-calculation step stores the calculated sets here.
+
+-record(node_data, {up_exp      = none,
+		    down_exp    = none,
+		    killed_expr = none,
+		    avail_in    = none,
+		    avail_out   = none,
+		    antic_in    = none,
+		    antic_out   = none,
+		    later_in    = none,
+		    delete      = none}).
+
+-record(edge_data, {earliest    = none,
+		    later       = none,
+		    insert      = none}).
+
+%%=============================================================================
+%% Creates a node info from a CFG (one entry for each Label).
+mk_node_info(Labels) ->
+  lists:foldl(fun(Label, DataTree) ->
+		  gb_trees:insert(Label, #node_data{}, DataTree)
+		  %%gb_trees:enter(Label, #node_data{}, DataTree)
+	      end, 
+	      gb_trees:empty(), Labels).
+
+%%mk_edge_info(Labels) ->
+%%  FIXME Should we traverse cfg and initialize edges?
+mk_edge_info() ->
+  gb_trees:empty().
+
+%%=============================================================================
+%% Get methods
+up_exp(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.up_exp.
+
+down_exp(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.down_exp.
+
+killed_expr(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.killed_expr.
+
+avail_in(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.avail_in.
+
+avail_out(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.avail_out.
+
+antic_in(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.antic_in.
+
+antic_out(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.antic_out.
+
+later_in(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.later_in.
+
+lookup_later_in(NodeInfo, Label) ->
+  case gb_trees:lookup(Label, NodeInfo) of
+    none -> 
+      none;
+    {value, #node_data{later_in = Data}} ->
+      Data
+  end.
+
+delete(NodeInfo, Label) ->
+  Data = gb_trees:get(Label, NodeInfo),
+  Data#node_data.delete.
+
+earliest(EdgeInfo, Edge) ->
+  Data = gb_trees:get(Edge, EdgeInfo),
+  Data#edge_data.earliest.
+
+-ifdef(LOOKUP_EARLIEST_NEEDED).
+lookup_earliest(EdgeInfo, Edge) ->
+  case gb_trees:lookup(Edge, EdgeInfo) of
+    none -> 
+      none;
+    {value, #edge_data{earliest = Data}} ->
+      Data
+  end.
+-endif.
+
+later(EdgeInfo, Edge) ->
+  Data = gb_trees:get(Edge, EdgeInfo),
+  Data#edge_data.later.
+
+lookup_later(EdgeInfo, Edge) ->
+  case gb_trees:lookup(Edge, EdgeInfo) of
+    none -> 
+      none;
+    {value, #edge_data{later = Data}} ->
+      Data
+  end.
+
+%% insert(EdgeInfo, Edge) ->
+%%   case gb_trees:lookup(Edge, EdgeInfo) of
+%%     none -> 
+%%       exit({?MODULE, insert, "edge info not found"}),
+%%       none;
+%%     {value, #edge_data{insert = Data}} ->
+%%       Data
+%%   end.
+
+%%=============================================================================
+%% Set methods
+set_up_exp(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{up_exp = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{up_exp = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_down_exp(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{down_exp = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{down_exp = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_killed_expr(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{killed_expr = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{killed_expr = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_avail_in(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{avail_in = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{avail_in = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_avail_out(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{avail_out = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{avail_out = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_antic_in(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{antic_in = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{antic_in = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_antic_out(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{antic_out = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{antic_out = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_later_in(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{later_in = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{later_in = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_delete(NodeInfo, Label, Data) ->
+  NodeData =
+    case gb_trees:lookup(Label, NodeInfo) of
+      none -> 
+	#node_data{delete = Data};
+      {value, OldNodeData} ->
+	OldNodeData#node_data{delete = Data}
+    end,
+  gb_trees:enter(Label, NodeData, NodeInfo).
+
+set_earliest(EdgeInfo, Edge, Data) ->
+  EdgeData =
+    case gb_trees:lookup(Edge, EdgeInfo) of
+      none -> 
+	#edge_data{earliest = Data};
+      {value, OldEdgeData} ->
+	OldEdgeData#edge_data{earliest = Data}
+    end,
+  gb_trees:enter(Edge, EdgeData, EdgeInfo).
+
+set_later(EdgeInfo, Edge, Data) ->
+  EdgeData =
+    case gb_trees:lookup(Edge, EdgeInfo) of
+      none -> 
+	#edge_data{later = Data};
+      {value, OldEdgeData} ->
+	OldEdgeData#edge_data{later = Data}
+    end,
+  gb_trees:enter(Edge, EdgeData, EdgeInfo).
+
+%% set_insert(EdgeInfo, Edge, Data) ->
+%%   EdgeData =
+%%     case gb_trees:lookup(Edge, EdgeInfo) of
+%%       none -> 
+%% 	#edge_data{insert = Data};
+%%       {value, OldEdgeData} ->
+%% 	OldEdgeData#edge_data{insert = Data}
+%%     end,
+%%   gb_trees:enter(Edge, EdgeData, EdgeInfo).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%% USE MAP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% The use map is a mapping from "use" (which is an rtl register/variable) 
+%% to a set of expressions (IDs) where that register/variable is used.
+%% It is used by calc_killed_expr to know what expressions are affected by
+%% a definition.
+
+%%=============================================================================
+%% Creates and calculates the use map for a CFG.
+%% It uses ExprMap to lookup the expression IDs.
+mk_use_map(CFG, ExprMap) ->
+  Labels = hipe_rtl_cfg:reverse_postorder(CFG),
+  NewMap = mk_use_map(gb_trees:empty(), CFG, ExprMap, Labels),
+  gb_trees:balance(NewMap).
+
+mk_use_map(Map, _, _, []) ->
+  Map;
+mk_use_map(Map, CFG, ExprMap, [Label|Labels]) ->
+  Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)),
+  NewMap = mk_use_map_bb(Map, ExprMap, Code),
+  mk_use_map(NewMap, CFG, ExprMap, Labels).
+
+mk_use_map_bb(UseMap, _, []) ->
+  UseMap;
+mk_use_map_bb(UseMap, ExprMap, [Instr|Instrs]) ->
+  case is_expr(Instr) of
+    true ->
+      Uses = hipe_rtl:uses(Instr),
+      ExprId = expr_map_get_id(ExprMap, expr_clear_dst(Instr)),
+      NewUseMap = mk_use_map_insert_uses(UseMap, ExprId, Uses),
+      mk_use_map_bb(NewUseMap, ExprMap, Instrs);
+    false ->
+      mk_use_map_bb(UseMap, ExprMap, Instrs)
+  end.
+
+%%=============================================================================
+%% Worker function for mk_use_map that inserts the expression id for every 
+%% rtl register the expression uses in a use map.
+mk_use_map_insert_uses(Map, _, []) ->
+  Map;
+mk_use_map_insert_uses(Map, Expr, [Use|Uses]) ->
+  case gb_trees:lookup(Use, Map) of
+    {value, UseSet} ->
+      NewUseSet = ?SETS:add_element(Expr, UseSet),
+      mk_use_map_insert_uses(gb_trees:update(Use, NewUseSet, Map), Expr, Uses);
+    none ->
+      UseSet = ?SETS:new(),
+      NewUseSet = ?SETS:add_element(Expr, UseSet),
+      mk_use_map_insert_uses(gb_trees:insert(Use, NewUseSet, Map), Expr, Uses)
+  end.
+
+%%=============================================================================
+%% Gets a set of expressions where the given rtl register is used.
+use_map_get_expr_uses(Map, Reg) ->
+  case gb_trees:lookup(Reg, Map) of
+    {value, UseSet} ->
+      UseSet;
+    none ->
+      ?SETS:new()
+  end. 
+
+%%%%%%%%%%%%%%%%%%%%%% EXPRESSION MAP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% The expression map is a mapping from expression to 
+%% (1) Expression Id (Integer used to speed up set operations)
+%% (2) List of definitions (labels where the expression is defined and the 
+%%     list of registers or variables defined by an instruction in that label,
+%%     represented as a tuple {Label, Defines})
+%% (3) The list of replacement registers created for the expression
+
+%%=============================================================================
+%% Creates and calculates the expression map for a CFG.
+mk_expr_map(CFG) ->
+  init_expr_id(),
+  Labels = hipe_rtl_cfg:reverse_postorder(CFG),
+  {ExprMap, IdMap} = mk_expr_map(gb_trees:empty(), gb_trees:empty(), 
+				 CFG, Labels),
+  {gb_trees:balance(ExprMap), gb_trees:balance(IdMap)}.
+
+mk_expr_map(ExprMap, IdMap, _, []) ->
+  {ExprMap, IdMap};
+mk_expr_map(ExprMap, IdMap, CFG, [Label|Labels]) ->
+  Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)),
+  {NewExprMap, NewIdMap} = mk_expr_map_bb(ExprMap, IdMap, Label, Code),
+  mk_expr_map(NewExprMap, NewIdMap, CFG, Labels).
+
+mk_expr_map_bb(ExprMap, IdMap, _, []) ->
+  {ExprMap, IdMap};
+mk_expr_map_bb(ExprMap, IdMap, Label, [Instr|Instrs]) ->
+  case is_expr(Instr) of
+    true ->
+      Expr = expr_clear_dst(Instr),
+      Defines = hipe_rtl:defines(Instr),
+      case gb_trees:lookup(Expr, ExprMap) of
+        {value, {ExprId, DefinesList, ReplRegs}} ->
+          NewExprMap = gb_trees:update(Expr, {ExprId, 
+					      [{Label, Defines}|DefinesList], 
+					      ReplRegs}, ExprMap),
+	  mk_expr_map_bb(NewExprMap, IdMap, Label, Instrs);
+        none ->
+	  NewExprId = new_expr_id(),
+          NewReplRegs = mk_replacement_regs(Defines),
+          NewExprMap = gb_trees:insert(Expr, {NewExprId, 
+					      [{Label, Defines}], 
+					      NewReplRegs}, ExprMap),
+          NewIdMap = gb_trees:insert(NewExprId, Expr, IdMap),
+	  mk_expr_map_bb(NewExprMap, NewIdMap, Label, Instrs)
+      end;
+    false ->
+      mk_expr_map_bb(ExprMap, IdMap, Label, Instrs)
+  end.
+
+%%=============================================================================
+%% Creates new temporaries to replace defines in moved expressions.
+mk_replacement_regs([]) ->
+  [];
+mk_replacement_regs(Defines) ->
+  mk_replacement_regs(Defines, []).
+
+mk_replacement_regs([], NewRegs) ->
+  lists:reverse(NewRegs);
+mk_replacement_regs([Define|Defines], NewRegs) ->
+  case hipe_rtl:is_reg(Define) of
+    true ->
+      NewReg =
+	case hipe_rtl:reg_is_gcsafe(Define) of
+	  true -> hipe_rtl:mk_new_reg_gcsafe();
+	  false -> hipe_rtl:mk_new_reg()
+	end,
+      mk_replacement_regs(Defines, [NewReg|NewRegs]);
+    false ->
+      case hipe_rtl:is_var(Define) of
+	true ->
+	  mk_replacement_regs(Defines, [hipe_rtl:mk_new_var()|NewRegs]);
+	false ->
+	  true = hipe_rtl:is_fpreg(Define),
+	  mk_replacement_regs(Defines, [hipe_rtl:mk_new_fpreg()|NewRegs])
+      end
+  end.
+  
+%%=============================================================================
+%% Performs a lookup, which returns a tuple
+%% {expression ID, list of definitions, list of replacement registers}
+expr_map_lookup(Map, Expr) ->
+  gb_trees:lookup(Expr, Map).
+
+%%=============================================================================
+%% Gets the actual RTL instruction to be generated for insertions of an 
+%% expression.
+expr_map_get_instr(Map, Expr) ->
+  case gb_trees:lookup(Expr, Map) of
+    {value, {_, _, Regs}} ->
+      expr_set_dst(Expr, Regs);
+    none ->
+      exit({?MODULE, expr_map_get_instr, "expression missing"})
+  end.
+
+%%=============================================================================
+%% Gets expression id.
+expr_map_get_id(Map, Expr) ->
+  case gb_trees:lookup(Expr, Map) of
+    {value, {ExprId, _, _}} ->
+      ExprId;
+    none ->
+      exit({?MODULE, expr_map_get_instr, "expression missing"})
+  end.
+
+%%=============================================================================
+%% Creates an rtl instruction that moves a value
+mk_expr_move_instr([Reg], [Define]) ->
+  case hipe_rtl:is_fpreg(Reg) of
+    true ->
+      hipe_rtl:mk_fmove(Reg, Define);
+    false ->
+      %% FIXME Check is_var() orelse is_reg() ?
+      hipe_rtl:mk_move(Reg, Define)
+  end;
+mk_expr_move_instr([_Reg|_Regs] = RegList, Defines) ->
+  %% FIXME Does this really work? What about floats...
+  %% (Multiple defines does not seem to be used by any of the 
+  %%  instructions considered by rtl_lcm at the moment so this is pretty much
+  %%  untested/unused.)
+  hipe_rtl:mk_multimove(RegList, Defines);
+mk_expr_move_instr(_, []) ->
+  exit({?MODULE, mk_expr_move_instr, "bad match"}).
+
+%%=============================================================================
+%% Returns a set of all expressions in the code.
+%% all_exprs(_CFG, []) ->
+%%   ?SETS:new();
+%% all_exprs(CFG, [Label|Labels]) ->
+%%   BB = hipe_rtl_cfg:bb(CFG, Label),
+%%   Code = hipe_bb:code(BB),
+%%   ?SETS:union(all_exprs_bb(Code),
+%% 	      all_exprs(CFG, Labels)).
+
+%%=============================================================================
+%% Returns a set of expressions in a basic block.
+%% all_exprs_bb([]) ->
+%%   ?SETS:new();
+%% all_exprs_bb([Instr|Instrs]) ->
+%%   case is_expr(Instr) of
+%%     true ->
+%%       Expr = expr_clear_dst(Instr),
+%%       ExprSet = all_exprs_bb(Instrs),
+%%       ?SETS:add_element(Expr, ExprSet);
+%%     false ->
+%%       all_exprs_bb(Instrs)
+%%   end.
+
+%%%%%%%%%%%%%%%%%% EXPRESSION ID -> EXPRESSION MAP %%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Map from expression IDs to expressions.
+%%=============================================================================
+%% mk_expr_id_map() ->
+%%   gb_trees:empty().
+
+%% expr_id_map_insert(Map, ExprId, Expr) ->
+%%   gb_trees:insert(ExprId, Expr, Map).
+
+%% expr_id_map_lookup(Map, ExprId) ->
+%%   gb_trees:lookup(ExprId, Map).
+
+%%=============================================================================
+%% Given expression id, gets expression.
+expr_id_map_get_expr(Map, ExprId) ->
+  case gb_trees:lookup(ExprId, Map) of
+    {value, Expr} ->
+      Expr;
+    none ->
+      exit({?MODULE, expr_id_map_get_expr, "expression id missing"})
+  end.
+
+%%=============================================================================
+%% Expression ID counter
+init_expr_id() ->
+  put({rtl_lcm,expr_id_count}, 0),
+  ok.
+
+-spec new_expr_id() -> non_neg_integer().
+new_expr_id() ->
+  Obj = {rtl_lcm, expr_id_count},
+  V = get(Obj),
+  put(Obj, V+1),
+  V.
+
+%%%%%%%%%%%%%%%%%% EDGE BB (INSERT BETWEEN) MAP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Map from edges to labels.
+%% This is used by insert_expr_between to remember what new bbs it has created
+%% for insertions on edges, and thus for multiple insertions on the same edge
+%% to end up in the same bb.
+%%=============================================================================
+mk_edge_bb_map() ->
+  gb_trees:empty().
+
+edge_bb_map_insert(Map, Edge, Label) ->
+  gb_trees:enter(Edge, Label, Map).
+
+edge_bb_map_lookup(Map, Edge) ->
+  gb_trees:lookup(Edge, Map).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PRETTY-PRINTING %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%=============================================================================
+%% Prints debug messages.
+-ifdef(LCM_DEBUG).
+
+pp_debug(Str, Args) ->
+  case ?LCM_DEBUG of
+    true ->
+      io:format(standard_io, Str, Args);
+    false ->
+      ok
+  end.
+
+pp_debug_instr(Instr) ->
+  case ?LCM_DEBUG of
+    true ->
+      hipe_rtl:pp_instr(standard_io, Instr);
+    false ->
+      ok
+  end.
+
+-else.
+
+pp_debug(_, _) ->  
+  ok.
+
+pp_debug_instr(_) ->  
+  ok.
+
+-endif.	%% DEBUG
+
+%%=============================================================================
+%% Pretty-prints the calculated sets for the lazy code motion.
+pp_sets(_, _, _, _, _, _, []) ->
+  ok; 
+pp_sets(ExprMap, IdMap, NodeInfo, EdgeInfo, AllExpr, CFG, [Label|Labels]) ->
+  Preds = hipe_rtl_cfg:pred(CFG, Label),
+  Succs = hipe_rtl_cfg:succ(CFG, Label),
+
+  io:format(standard_io, "Label ~w~n", [Label]),
+  io:format(standard_io, "  Preds:    ~w~n", [Preds]),
+  io:format(standard_io, "  Succs:    ~w~n", [Succs]),
+
+  case up_exp(NodeInfo, Label) of
+    none -> ok;
+    UpExp -> 
+      case ?SETS:size(UpExp) =:= 0 of
+	false ->
+	  io:format(standard_io, "  UEExpr: ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(UpExp));
+	true -> ok
+      end
+  end,
+  case down_exp(NodeInfo, Label) of
+    none -> ok;
+    DownExp -> 
+      case ?SETS:size(DownExp) =:= 0 of
+	false ->
+	  io:format(standard_io, "  DEExpr: ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(DownExp));
+	true -> ok
+      end
+  end,
+  case killed_expr(NodeInfo, Label) of
+    none -> ok;
+    KilledExpr -> 
+      case ?SETS:size(KilledExpr) =:= 0 of
+	false ->
+	  io:format(standard_io, "  ExprKill: ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(KilledExpr));
+	true -> ok
+      end
+  end,
+  case avail_in(NodeInfo, Label) of
+    none -> ok;
+    AvailIn ->
+      case ?SETS:size(AvailIn) =:= 0 of
+	false ->
+	  io:format(standard_io, "  AvailIn:  ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(AvailIn));
+	true -> ok
+      end
+  end,
+  case avail_out(NodeInfo, Label) of
+    none -> ok;
+    AvailOut ->
+      case ?SETS:size(AvailOut) =:= 0 of
+	false ->
+	  io:format(standard_io, "  AvailOut: ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(AvailOut));
+	true -> ok
+      end
+  end,
+  case antic_in(NodeInfo, Label) of
+    none -> ok;
+    AnticIn ->
+      case ?SETS:size(AnticIn) =:= 0 of
+	false ->
+	  io:format(standard_io, "  AnticIn:  ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(AnticIn));
+	true -> ok
+      end
+  end,
+  case antic_out(NodeInfo, Label) of
+    none -> ok;
+    AnticOut ->
+      case ?SETS:size(AnticOut) =:= 0 of
+	false ->
+	  io:format(standard_io, "  AnticOut: ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(AnticOut));
+	true -> ok
+      end
+  end,
+  case later_in(NodeInfo, Label) of
+    none -> ok;
+    LaterIn ->
+      case ?SETS:size(LaterIn) =:= 0 of
+	false ->
+	  io:format(standard_io, "  LaterIn:  ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(LaterIn));
+	true -> ok
+      end
+  end,  
+
+  pp_earliest(ExprMap, IdMap, EdgeInfo, Label, Succs),
+  pp_later(ExprMap, IdMap, EdgeInfo, Label, Succs),
+
+  case delete(NodeInfo, Label) of
+    none -> ok;
+    Delete ->
+      case ?SETS:size(Delete) =:= 0 of
+	false ->
+	  io:format(standard_io, "  Delete:   ~n", []),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(Delete));
+	true -> ok
+      end
+  end,
+  pp_sets(ExprMap, IdMap, NodeInfo, EdgeInfo, AllExpr, CFG, Labels).
+
+%%=============================================================================
+%% Pretty-prints the later set.
+pp_later(_, _, _, _, []) ->
+  ok;
+pp_later(ExprMap, IdMap, EdgeInfo, Pred, [Succ|Succs]) ->
+  case later(EdgeInfo, {Pred, Succ}) of
+    none -> ok;
+    Later ->
+      case ?SETS:size(Later) =:= 0 of
+	false ->
+	  io:format(standard_io, "  Later(~w->~w): ~n", [Pred,Succ]),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(Later));
+	true -> ok
+      end
+  end,
+  pp_later(ExprMap, IdMap, EdgeInfo, Pred, Succs).
+
+%%=============================================================================
+%% Pretty-prints the earliest set.
+pp_earliest(_, _, _, _, []) ->
+  ok;
+pp_earliest(ExprMap, IdMap, EdgeInfo, Pred, [Succ|Succs]) ->
+  case earliest(EdgeInfo, {Pred, Succ}) of
+    none -> ok;
+    Earliest ->
+      case ?SETS:size(Earliest) =:= 0 of
+	false ->
+	  io:format(standard_io, "  Earliest(~w->~w): ~n", [Pred,Succ]),
+	  pp_exprs(ExprMap, IdMap, ?SETS:to_list(Earliest));
+	true -> ok
+      end
+  end,
+  pp_earliest(ExprMap, IdMap, EdgeInfo, Pred, Succs).
+
+%%=============================================================================
+%% Pretty-prints an expression
+pp_expr(ExprMap, IdMap, ExprId) ->
+  Expr = expr_id_map_get_expr(IdMap, ExprId),
+  hipe_rtl:pp_instr(standard_io, expr_map_get_instr(ExprMap, Expr)).
+
+pp_exprs(_, _, []) ->
+  ok;
+pp_exprs(ExprMap, IdMap, [E|Es]) ->
+  pp_expr(ExprMap, IdMap, E),
+  pp_exprs(ExprMap, IdMap, Es).