%% -*- erlang-indent-level: 2 -*-
%%
%% %CopyrightBegin%
%% 
%% Copyright Ericsson AB 2004-2011. 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 compatibility 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, 
					    IdMap, 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, IdMap, [Label|Labels]) ->
  Code = hipe_bb:code(hipe_rtl_cfg:bb(CFG, Label)),
  KilledExprs = calc_killed_expr_bb(Code, UseMap, AllExpr, IdMap, ?SETS:new()),
  NewNodeInfo = set_killed_expr(NodeInfo, Label, KilledExprs),
  calc_killed_expr(CFG, NewNodeInfo, UseMap, AllExpr, IdMap, Labels).

%%=============================================================================
%% Calculates the killed expressions set for one basic block.
calc_killed_expr_bb([], _UseMap, _AllExpr, _IdMap, KilledExprs) ->
  KilledExprs;
calc_killed_expr_bb([Instr|Instrs], UseMap, AllExpr, IdMap, 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(ExprId, Fexprs) ->
			     Expr = expr_id_map_get_expr(IdMap, ExprId),
			 [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, IdMap, KilledExprs);
	[Define|_] ->
	  NewKilledExprs = use_map_get_expr_uses(UseMap, Define),
	  calc_killed_expr_bb(Instrs, UseMap, AllExpr, IdMap,
			      ?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).