The R13B03 release.OTP_R13B03

1 files changed, 1679 insertions, 0 deletions

diff --git a/lib/hipe/rtl/hipe_rtl_ssapre.erl b/lib/hipe/rtl/hipe_rtl_ssapre.erl
new file mode 100644
index 0000000000..a9e92e5688
--- /dev/null
+++ b/lib/hipe/rtl/hipe_rtl_ssapre.erl
@@ -0,0 +1,1679 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%% 
+%% Copyright Ericsson AB 2005-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_ssapre.erl
+%% Author      : He Bingwen and Fr�d�ric Haziza
+%% Description : Performs Partial Redundancy Elimination on SSA form.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% @doc
+%%
+%% This module implements the <a href="http://cs.wheaton.edu/%7Etvandrun/writings/spessapre.pdf">Anticipation-SSAPRE algorithm</a>,
+%% with several modifications for Partial Redundancy Elimination on SSA form.
+%% We actually found problems in this algorithm, so
+%% we implement another version with several advantages:
+%% - No loop for Xsi insertions
+%% - No fix point iteration for the downsafety part
+%% - Less computations for Will Be Available part
+%% - Complexity of the overall algorithm is improved
+%%
+%% We were supposed to publish these results anyway :D
+%%
+%% @end
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-module(hipe_rtl_ssapre).
+
+-export([rtl_ssapre/2]).
+
+-include("../main/hipe.hrl").
+-include("hipe_rtl.hrl").
+
+%%-define(SSAPRE_DEBUG, true        ). %% When uncommented, produces debug printouts
+-define(        SETS, ordsets       ). %% Which set implementation module to use
+-define(         CFG, hipe_rtl_cfg  ).
+-define(         RTL, hipe_rtl      ).
+-define(          BB, hipe_bb       ).
+-define(        ARCH, hipe_rtl_arch ).
+-define(       GRAPH, digraph       ).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Debugging stuff
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-ifndef(SSAPRE_DEBUG).
+-define(pp_debug(_Str, _Args), ok).
+-else.
+-define(pp_debug(Str, Args), io:format(standard_io, Str, Args)).
+-endif.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Records / Structures
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-record(xsi_link, {num}). %% Number is the index of the temporary (a Key into the Xsi Tree)
+-record(temp, {key, var}).
+-record(bottom, {key, var}).
+-record(xsi, {inst,   %% Associated instruction
+              def,    %% Hypothetical temporary variable
+	              %% that stores the result of the computation
+              label,  %% Block Label where the xsi is inserted
+              opList, %% List of operands
+              cba,    %%
+              later,  %%
+              wba
+             }).
+
+-record(pre_candidate, {alu, def}).
+-record(xsi_op, {pred, op}).
+
+-record(mp, {xsis, maps, preds, defs, uses, ndsSet}).
+-record(block, {type, attributes}).
+
+-record(eop, {expr, var, stopped_by}).
+-record(insertion, {code, from}).
+
+-record(const_expr, {var, value}).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Main function
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+rtl_ssapre(RtlSSACfg, Options) ->
+  %% io:format("\n################ Original CFG ################\n"),
+  %% hipe_rtl_cfg:pp(RtlSSACfg),
+  %% io:format("\n\n############ SSA-Form CHECK ==> ~w\n",[hipe_rtl_ssa:check(RtlSSACfg)]),
+
+  {CFG2,XsiGraph,CFGGraph,MPs} = perform_Xsi_insertion(RtlSSACfg,Options),
+  %%?pp_debug("~n~n################ Xsi CFG ################\n",[]),pp_cfg(CFG2,XsiGraph),
+  XsiList = ?GRAPH:vertices(XsiGraph),
+  case XsiList of
+    [] ->
+      %% No Xsi
+      ?option_time(?pp_debug("~n~n################ No Xsi Inserted ################~n",[]),"RTL A-SSAPRE No Xsi inserted (skip Downsafety and Will Be Available)",Options),
+      ok;
+    _ ->
+      ?pp_debug("~n############ Downsafety ##########~n",[]),
+      ?option_time(perform_downsafety(MPs,CFGGraph,XsiGraph),"RTL A-SSAPRE Downsafety",Options),
+      ?pp_debug("~n~n################ CFG Graph ################~n",[]),pp_cfggraph(CFGGraph),
+      ?pp_debug("~n############ Will Be Available ##########~n",[]),
+      ?option_time(perform_will_be_available(XsiGraph,CFGGraph,Options),"RTL A-SSAPRE WillBeAvailable",Options)
+  end,
+  
+  ?pp_debug("~n############ No more need for the CFG Graph....Deleting...",[]),?GRAPH:delete(CFGGraph),
+  ?pp_debug("~n~n################ Xsi Graph ################~n",[]),pp_xsigraph(XsiGraph),
+  
+  ?pp_debug("~n############ Code Motion ##########~n",[]),
+  Labels = ?CFG:preorder(CFG2),
+
+  ?pp_debug("~n~n################ Xsi CFG ################~n",[]),pp_cfg(CFG2,XsiGraph),
+
+  init_redundancy_count(),
+  ?option_time(FinalCFG=perform_code_motion(Labels,CFG2,XsiGraph),"RTL A-SSAPRE Code Motion",Options),
+  
+  ?pp_debug("\n############ No more need for the Xsi Graph....Deleting...",[]),?GRAPH:delete(XsiGraph),
+
+  %% io:format("\n################ Final CFG ################\n"),
+  %% hipe_rtl_cfg:pp(FinalCFG),
+  %% io:format("\n\n############ SSA-Form CHECK ==> ~w\n",
+  %%           [hipe_rtl_ssa:check(FinalCFG)]),
+  ?pp_debug("\nSSAPRE : ~w redundancies were found\n",[get_redundancy_count()]),
+
+  FinalCFG.
+
+%% ##########################################################################
+%% ######################## XSI INSERTION ###################################
+%% ##########################################################################
+
+perform_Xsi_insertion(Cfg, Options) ->
+  init_counters(), %% Init counters for Bottoms and Temps
+  DigraphOpts = [cyclic, private],
+  XsiGraph = digraph:new(DigraphOpts),
+  %% Be carefull, the digraph component is NOT garbage collected,
+  %% so don't create 20 millions of instances!
+  %% finds the longest depth
+  %% Depth-first, preorder traversal over Basic Blocks.
+  %%Labels = ?CFG:reverse_postorder(Cfg), 
+  Labels = ?CFG:preorder(Cfg), 
+
+  ?pp_debug("~n~n############# Finding definitions for computation~n~n",[]),
+  ?option_time({Cfg2,XsiGraph} = find_definition_for_computations(Labels,Cfg,XsiGraph),"RTL A-SSAPRE Xsi Insertion, searching from instructions",Options),
+
+  %% Active List creation
+  GeneratorXsiList = lists:sort(?GRAPH:vertices(XsiGraph)),
+  ?pp_debug("~n~n############# Inserted Xsis ~w",[GeneratorXsiList]),
+  ?pp_debug("~n~n############# Finding operands~n",[]),
+  ?option_time({Cfg3,XsiGraph} = find_operands(Cfg2,XsiGraph,GeneratorXsiList,0),"RTL A-SSAPRE Xsi Insertion, finding operands",Options),
+
+  %% Creating the CFGGraph
+  ?pp_debug("~n~n############# Creating CFG Graph",[]),
+  ?pp_debug("~n############# Labels = ~w",[Labels]),
+  CFGGraph = digraph:new(DigraphOpts),
+  [StartLabel|Others] = Labels,   % adding the start label as a leaf
+  ?pp_debug("~nAdding a vertex for the start label: ~w",[StartLabel]),
+  ?GRAPH:add_vertex(CFGGraph, StartLabel, #block{type = top}),
+                                                % Doing the others
+  ?option_time(MPs=create_cfggraph(Others,Cfg3,CFGGraph,[],[],[],XsiGraph),"RTL A-SSAPRE Xsi Insertion, creating intermediate 'SSAPRE Graph'",Options),
+
+  %% Return the bloody collected information
+  {Cfg3,XsiGraph,CFGGraph,MPs}.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+find_definition_for_computations([], Cfg, XsiGraph) ->
+  {Cfg,XsiGraph}; %% No more block to inspect in the depth-first order
+find_definition_for_computations([Label|Rest], Cfg, XsiGraph) ->
+  Code = ?BB:code(?CFG:bb(Cfg,Label)),
+  {NewCfg,XsiGraph} = find_definition_for_computations_in_block(Label,Code,Cfg,[],XsiGraph),
+  find_definition_for_computations(Rest, NewCfg, XsiGraph).
+
+%%===========================================================================
+%% Searches from instruction for one block BlockLabel.
+%% We process forward over instructions.
+
+find_definition_for_computations_in_block(BlockLabel,[],Cfg,
+					  VisitedInstructions,XsiGraph)->
+  Code = lists:reverse(VisitedInstructions),
+  NewBB = ?BB:mk_bb(Code),
+  NewCfg = ?CFG:bb_add(Cfg,BlockLabel,NewBB),
+  {NewCfg,XsiGraph}; %% No more instructions to inspect in this block
+find_definition_for_computations_in_block(BlockLabel,[Inst|Rest],Cfg,
+					  VisitedInstructions,XsiGraph) ->
+  %%  ?pp_debug(" Inspecting instruction: ",[]),pp_instr(Inst,nil),
+  case Inst of
+    #alu{} ->
+      %% Is Inst interesting for SSAPRE?
+      %% i.e., is Inst an arithmetic operation which doesn't deal with precoloured?
+      %% Note that since we parse forward, we have no 'pre_candidate'-type so far.
+      case check_definition(Inst,VisitedInstructions,BlockLabel,Cfg,XsiGraph) of
+ 	{def_found,Def} ->
+ 	  %% Replacing Inst in Cfg
+ 	  NewInst = #pre_candidate{alu=Inst,def=Def},
+ 	  NewVisited = [NewInst|VisitedInstructions],
+ 	  %% Recurse forward over instructions, same CFG, same XsiGraph
+ 	  find_definition_for_computations_in_block(BlockLabel,Rest,Cfg,
+						    NewVisited,XsiGraph);
+ 	{merge_point,Xsi} ->
+          Def = Xsi#xsi.def,
+    	  Key = Def#temp.key,
+ 	  NewInst = #pre_candidate{alu=Inst,def=Def},
+          XsiLink = #xsi_link{num=Key},
+
+          %% Add a vertex to the Xsi Graph
+          ?GRAPH:add_vertex(XsiGraph,Key,Xsi),
+ 	  ?pp_debug(" Inserting Xsi: ",[]),pp_xsi(Xsi),
+
+          Label = Xsi#xsi.label,
+          case BlockLabel =:= Label of
+            false ->
+              %% Insert the Xsi in the appropriate block
+              Code = hipe_bb:code(?CFG:bb(Cfg,Label)),
+              {BeforeCode,AfterCode} = split_for_xsi(lists:reverse(Code),[]),
+              NewCode = BeforeCode++[XsiLink|AfterCode],
+              NewBB = hipe_bb:mk_bb(NewCode),
+              NewCfg = ?CFG:bb_add(Cfg,Label,NewBB),
+              NewVisited = [NewInst|VisitedInstructions];
+            _->
+              {BeforeCode,AfterCode} = split_for_xsi(VisitedInstructions,[]),
+              TempVisited = BeforeCode++[XsiLink|AfterCode],
+              TempVisited2 = lists:reverse(TempVisited),
+              NewVisited = [NewInst|TempVisited2],
+              NewCfg = Cfg
+          end,
+          find_definition_for_computations_in_block(BlockLabel, Rest, NewCfg,
+						    NewVisited, XsiGraph)
+      end;
+    _ ->
+      %%?pp_debug("~n [L~w] Not concerned with: ~w",[BlockLabel,Inst]),
+      %% If the instruction is not a SSAPRE candidate, we skip it and keep on
+      %% processing instructions
+      %% Prepend Inst, so that we have all in reverse order.
+      %% Easy to parse backwards
+      find_definition_for_computations_in_block(BlockLabel, Rest, Cfg,
+						[Inst|VisitedInstructions], XsiGraph)
+  end.
+
+%% ############################################################################
+%% We have E as an expression, I has an alu (arithmetic operation), and
+%% we inspect backwards the previous instructions to find a definition for E.
+%% Since we parse in forward order, we know that the previous SSAPRE 
+%% instruction will have a definition.
+
+check_definition(E,[],BlockLabel,Cfg,XsiGraph)->
+  %% No more instructions in that block
+  %% No definition found in that block
+  %% Search is previous blocks
+  Preds = ?CFG:pred(Cfg, BlockLabel),
+  %%  ?pp_debug("~n CHECKING DEFINITION  ####### Is L~w a merge block? It has ~w preds. So far E=",[BlockLabel,length(Preds)]),pp_expr(E),
+  case Preds of
+    [] ->
+      %% Entry Point
+      {def_found,bottom};
+    [P] ->
+      %% One predecessor only, we just keep looking for a definition in that block
+      VisitedInstructions = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))),
+      check_definition(E,VisitedInstructions,P,Cfg,XsiGraph);
+    _ ->
+      Temp = new_temp(),
+      %% It's a merge point
+      OpList = [#xsi_op{pred=X} || X<-Preds],
+      Xsi = #xsi{inst=E,def=Temp,label=BlockLabel,opList=OpList},
+      {merge_point,Xsi} 
+  end;
+check_definition(E,[CC|Rest],BlockLabel,Cfg,XsiGraph) ->
+  SRC1 = ?RTL:alu_src1(E),
+  SRC2 = ?RTL:alu_src2(E),
+  case CC of
+    #alu{} ->
+      exit({?MODULE,should_not_be_an_alu,
+	    {"Why the hell do we still have an alu???",CC}});
+    #pre_candidate{} ->
+      %% C is the previous instruction
+      C = CC#pre_candidate.alu,
+      DST = ?RTL:alu_dst(C),
+      case DST =:= SRC1 orelse DST =:= SRC2 of
+ 	false ->
+ 	  case check_match(E,C) of
+ 	    true -> %% It's a computation of E!
+ 	      %% Get the dst of the alu
+ 	      {def_found,DST};
+ 	    _->
+ 	      check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
+ 	  end;
+ 	true ->
+ 	  %% Get the definition of C, since C is PRE-candidate AND has been processed before
+ 	  DEF = CC#pre_candidate.def,
+ 	  case DEF of
+ 	    bottom -> 
+ 	      %% Def(E)=bottom, STOP
+ 	      {def_found,bottom};
+ 	    _ -> 
+ 	      %% Emend E with this def(C)
+ 	      %%?pp_debug("Parameters are E=~w, DST=~w, DEF=~w",[E,DST,DEF]),
+ 	      F = emend(E,DST,DEF),
+ 	      check_definition(F,Rest,BlockLabel,Cfg,XsiGraph) %% Continue the search
+ 	  end
+      end;
+    #move{} ->
+      %% It's a move, we emend E, and continue the definition search
+      DST = ?RTL:move_dst(CC),
+      F = case SRC1 =:= DST orelse SRC2 =:= DST of
+	    true ->
+	      SRC = ?RTL:move_src(CC),
+	      emend(E,DST,SRC);
+	    _ ->
+	      E
+	  end,
+      check_definition(F,Rest,BlockLabel,Cfg,XsiGraph); %% Continue the search
+    #xsi_link{} ->
+      {_K,Xsi} = ?GRAPH:vertex(XsiGraph,CC#xsi_link.num),
+      C = Xsi#xsi.inst,
+      case check_match(C,E) of
+ 	true -> %% There is a Xsi already with a computation of E!
+ 	  %% fetch definition of C, and give it to E
+ 	  {def_found,Xsi#xsi.def};
+ 	_->
+ 	  check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
+      end;
+    #phi{} -> 
+      %% skip them. NOTE: Important to separate this case from the next one
+      check_definition(E,Rest,BlockLabel,Cfg,XsiGraph);
+    _ ->
+      %% Note: the function calls or some other instructions can change the pre-coloured registers
+      %% which are able to be redefined. This breaks of course the SSA form.
+      %% If there is a redefinition we can give bottom to the computation, and no xsi will be inserted.
+      %% (In some sens, the result of the computation is new at that point.)
+      PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2),
+
+      %%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2),
+      RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)), %% That means we cannot reuse the result held in this register...
+
+      case PreColouredTest orelse RegisterTest of
+ 	true ->
+ 	  {def_found,bottom};
+ 	false ->
+          DC = ?RTL:defines(CC),
+          case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of
+            true ->
+              {def_found,bottom};
+            false ->
+              %% Orthogonal to E, we continue the search
+              check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
+          end
+      end
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+check_match(E, C) ->
+  OpE = ?RTL:alu_op(E),
+  OpC = ?RTL:alu_op(C),
+  case OpE =:= OpC of
+    false ->
+      false;
+    true ->
+      Src1E = ?RTL:alu_src1(E),
+      Src2E = ?RTL:alu_src2(E),
+      Src1C = ?RTL:alu_src1(C),
+      Src2C = ?RTL:alu_src2(C),
+      case Src1E =:= Src1C of
+ 	true ->
+ 	  Src2E =:= Src2C;
+ 	false ->
+ 	  Src1E =:= Src2C andalso Src2E =:= Src1C
+      end
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+expr_is_const(E) ->
+  ?RTL:is_imm(?RTL:alu_src1(E)) andalso ?RTL:is_imm(?RTL:alu_src2(E)).
+%%  is_number(?RTL:alu_src1(E)) andalso is_number(?RTL:alu_src2(E)).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Must be an arithmetic operation, i.e. #alu{}
+emend(Expr, S, Var) ->
+  SRC1 = ?RTL:alu_src1(Expr),
+  NewExpr = case SRC1 =:= S of
+	      true  -> ?RTL:alu_src1_update(Expr,Var);
+	      false -> Expr
+	    end,
+  SRC2 = ?RTL:alu_src2(NewExpr),
+  case SRC2 =:= S of
+    true  -> ?RTL:alu_src2_update(NewExpr,Var);
+    false -> NewExpr
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+split_for_xsi([], Acc) ->
+  {[], Acc};  %  no_xsi_no_phi_found;
+split_for_xsi([I|Is] = Code, Acc) -> %% [I|Is] in backward order, Acc in order
+  case I of
+    #xsi_link{} ->
+      {lists:reverse(Code), Acc};
+    #phi{} ->
+      {lists:reverse(Code), Acc};
+    _ ->
+      split_for_xsi(Is, [I|Acc])
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Phase 1.B : Search for operands
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+find_operands(Cfg,XsiGraph,[],_Count) ->
+  {Cfg,XsiGraph};
+find_operands(Cfg,XsiGraph,ActiveList,Count) ->
+  {NewCfg,TempActiveList} = find_operands_for_active_list(Cfg,XsiGraph,ActiveList,[]),
+  NewActiveList = lists:reverse(TempActiveList),
+  ?pp_debug("~n################ Finding operands (iteration ~w): ~w have been introduced. Now ~w in total~n",
+ 	   [Count+1, length(NewActiveList), length(?GRAPH:vertices(XsiGraph))]),
+  find_operands(NewCfg,XsiGraph,NewActiveList,Count+1).
+
+find_operands_for_active_list(Cfg,_XsiGraph,[],ActiveListAcc) ->
+  {Cfg,ActiveListAcc};
+find_operands_for_active_list(Cfg,XsiGraph,[K|Ks],ActiveListAcc) ->
+  {_Key,Xsi} = ?GRAPH:vertex(XsiGraph,K),
+  ?pp_debug("~n Inspecting operands of : ~n",[]),pp_xsi(Xsi),
+  Preds = ?CFG:pred(Cfg, Xsi#xsi.label),
+  {NewCfg,NewActiveListAcc}=determine_operands(Xsi,Preds,Cfg,K,XsiGraph,ActiveListAcc),
+  {_Key2,Xsi2} = ?GRAPH:vertex(XsiGraph,K),
+  ?pp_debug("~n ** Final Xsi: ~n",[]),pp_xsi(Xsi2),
+  ?pp_debug("~n #####################################################~n",[]),
+  find_operands_for_active_list(NewCfg,XsiGraph,Ks,NewActiveListAcc).
+
+determine_operands(_Xsi,[],Cfg,_K,_XsiGraph,ActiveAcc) ->
+  %% All operands have been determined.
+  %% The CFG is not updated, only the XsiGraph
+  {Cfg,ActiveAcc};
+determine_operands(Xsi,[P|Ps],Cfg,K,XsiGraph,ActiveAcc) ->
+  Label = Xsi#xsi.label,
+  ReverseCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,Label))),
+  VisitedInstructions = get_visited_instructions(Xsi,ReverseCode),
+  Res = determine_e_prime(Xsi#xsi.inst,VisitedInstructions,P,XsiGraph),
+  case Res of
+    operand_is_bottom ->
+      NewXsi = xsi_arg_update(Xsi,P,new_bottom()),
+      ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
+      determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
+    operand_is_const_expr ->
+      NewXsi = xsi_arg_update(Xsi,P,new_bottom()),
+      ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
+      determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
+    {sharing_operand,Op} ->
+      NewXsi = xsi_arg_update(Xsi,P,Op),
+      ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
+      determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);  
+    {revised_expression,E_prime} ->
+      ?pp_debug(" E' is determined : ",[]),pp_expr(E_prime),
+      ?pp_debug(" and going along the edge L~w~n",[P]),
+      %% Go along the edge P
+      RevCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))),
+      case check_one_operand(E_prime,RevCode,P,Cfg,K,XsiGraph) of
+ 	{def_found,Def} ->
+ 	  NewXsi = xsi_arg_update(Xsi,P,Def),
+          ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
+          determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
+
+ 	{expr_found,ChildExpr} ->
+ 	  NewXsi = xsi_arg_update(Xsi,P,ChildExpr),
+          ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
+          determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
+
+ 	{expr_is_const, Op} ->
+          %% We detected that the expression is of the form: 'N op M'
+          %% where N and M are constant.
+ 	  NewXsi = xsi_arg_update(Xsi,P,Op),
+          ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
+          determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
+
+ 	{merge_point,XsiChild} ->
+ 	  %% Update that Xsi, give its definition as Operand for the
+ 	  %% search, and go on
+          XsiChildDef = XsiChild#xsi.def,
+ 	  NewXsi = xsi_arg_update(Xsi,P,XsiChildDef),
+          ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
+
+ 	  KeyChild = XsiChildDef#temp.key,
+ 	  XsiChildLink = #xsi_link{num=KeyChild},
+          ?GRAPH:add_vertex(XsiGraph,KeyChild,XsiChild),
+
+ 	  %% Should not be the same block !!!!!!!
+ 	  RCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,XsiChild#xsi.label))),
+ 	  {BCode,ACode} = split_code_for_xsi(RCode,[]),
+
+ 	  NewCode = BCode++[XsiChildLink|ACode],
+ 	  NewBB = hipe_bb:mk_bb(NewCode),
+ 	  NewCfg = ?CFG:bb_add(Cfg, XsiChild#xsi.label, NewBB),
+
+ 	  ?pp_debug(" -- ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" causes insertion of: ~n",[]),pp_xsi(XsiChild),
+          ?pp_debug(" -- Adding an edge ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" -> ",[]),pp_arg(XsiChild#xsi.def),
+
+          %% Adding an edge...
+ 	  %%?GRAPH:add_edge(XsiGraph,K,KeyChild,"family"),
+          ?GRAPH:add_edge(XsiGraph,K,KeyChild),
+ 	  determine_operands(NewXsi,Ps,NewCfg,K,XsiGraph,[KeyChild|ActiveAcc])
+      end
+  end.
+
+determine_e_prime(Expr,VisitedInstructions,Pred,XsiGraph) ->
+  %% MUST FETCH FROM THE XSI TREE, since Xsis are not updated yet in the CFG
+  NewExpr = emend_with_phis(Expr,VisitedInstructions,Pred),
+  emend_with_processed_xsis(NewExpr,VisitedInstructions,Pred,XsiGraph).
+
+emend_with_phis(EmendedE, [], _) ->
+  EmendedE;
+emend_with_phis(E, [I|Rest], Pred) ->
+  case I of
+    #phi{} ->
+      Dst = ?RTL:phi_dst(I),
+      UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead?
+      case lists:member(Dst, UE) of
+  	false ->
+  	  emend_with_phis(E, Rest, Pred);
+  	true ->
+  	  NewE = emend(E, Dst, ?RTL:phi_arg(I,Pred)),
+  	  emend_with_phis(NewE, Rest, Pred)
+      end;
+    _ ->
+      emend_with_phis(E, Rest, Pred)
+  end.
+
+emend_with_processed_xsis(EmendedE, [], _, _) ->
+  {revised_expression,EmendedE};  
+emend_with_processed_xsis(E, [I|Rest], Pred, XsiGraph) ->
+  case I of
+    #xsi_link{} ->
+      Key = I#xsi_link.num,
+      {_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
+      Def = Xsi#xsi.def,
+      UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead?
+      case lists:member(Def,UE) of
+  	false ->
+ 	  CE = Xsi#xsi.inst,
+ 	  case check_match(E,CE) of
+ 	    true -> %% It's a computation of E!
+ 	      case xsi_arg(Xsi,Pred) of
+ 		undetermined_operand ->
+ 		  exit({?MODULE,check_operand_sharing,"######## �h Dear, we trusted Kostis !!!!!!!!! #############"});
+ 		XsiOp ->
+ 		  {sharing_operand,XsiOp} %% They share operands
+ 	      end;
+ 	    _->
+ 	      emend_with_processed_xsis(E,Rest,Pred,XsiGraph)
+ 	  end;
+  	true ->
+ 	  A = xsi_arg(Xsi,Pred),
+ 	  %% ?pp_debug(" ######### xsi_arg(I:~w,Pred:~w) = ~w~n",[I,Pred,A]),
+ 	  case A of
+ 	    #bottom{} ->
+ 	      operand_is_bottom;
+ 	    #const_expr{} ->
+ 	      operand_is_const_expr;
+            #eop{} ->
+              NewE = emend(E,Def,A#eop.var),
+  	      emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph);
+            undetermined_operand ->
+ 	      exit({?MODULE,emend_with_processed_xsis,"######## �h Dear, we trusted Kostis, again !!!!!!!!! #############"});
+ 	    XsiOp ->
+ 	      NewE = emend(E,Def,XsiOp),
+ 	      emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph)
+ 	  end
+      end;
+    _ ->
+      emend_with_processed_xsis(E,Rest,Pred,XsiGraph)
+  end.
+
+%% get_visited_instructions(Xsi,[]) ->
+%%   ?pp_debug("~nWe don't find this xsi with def ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" in L~w : ",[Xsi#xsi.label]),
+%%   exit({?MODULE,no_such_xsi_in_block,"We didn't find that Xsi in the block"});
+get_visited_instructions(Xsi, [I|Is]) ->
+  case I of
+    #xsi_link{} ->
+      XsiDef = Xsi#xsi.def,
+      Key = XsiDef#temp.key,
+      case I#xsi_link.num =:= Key of
+ 	true ->
+ 	  Is;
+ 	false ->
+ 	  get_visited_instructions(Xsi, Is)
+      end;
+    _ ->
+      get_visited_instructions(Xsi, Is)
+  end.
+
+split_code_for_xsi([], Acc) ->
+  {[],Acc};
+split_code_for_xsi([I|Is] = Code, Acc) ->
+  case I of
+    #xsi_link{} ->
+      {lists:reverse(Code), Acc};
+    #phi{} ->
+      {lists:reverse(Code), Acc};
+    _ ->
+      split_code_for_xsi(Is, [I|Acc])
+  end.
+
+check_one_operand(E, [], BlockLabel, Cfg, XsiKey, XsiGraph) ->
+  %% No more instructions in that block
+  %% No definition found in that block
+  %% Search is previous blocks
+  Preds = ?CFG:pred(Cfg, BlockLabel),
+  case Preds of
+    [] ->
+      %% Entry Point
+      {def_found,new_bottom()};
+    [P] ->
+      %% One predecessor only, we just keep looking for a definition in that block
+      case expr_is_const(E) of
+        true ->
+          ?pp_debug("\n\n############## Wow expr is constant: ~w",[E]),
+          Var = ?RTL:mk_new_var(),
+          Value = eval_expr(E),
+          Op = #const_expr{var = Var, value = Value},
+          {expr_is_const, Op};
+        false ->
+          VisitedInstructions = lists:reverse(?BB:code(?CFG:bb(Cfg,P))),
+          check_one_operand(E, VisitedInstructions, P, Cfg, XsiKey, XsiGraph)
+      end;
+    _ ->
+      %% It's a merge point
+      case expr_is_const(E) of
+        true ->
+          ?pp_debug("\n\n############## Wow expr is constant at merge point: ~w",[E]),
+          Var = ?RTL:mk_new_var(),
+          Value = eval_expr(E),
+          Op = #const_expr{var = Var, value = Value},
+          {expr_is_const, Op};
+        false ->
+          Temp = new_temp(),
+          OpList = [#xsi_op{pred = X} || X <- Preds],
+          Xsi = #xsi{inst = E, def = Temp, label = BlockLabel, opList = OpList},
+          {merge_point, Xsi}
+      end
+  end;
+check_one_operand(E, [CC|Rest], BlockLabel, Cfg, XsiKey, XsiGraph) ->
+  SRC1 = ?RTL:alu_src1(E),
+  SRC2 = ?RTL:alu_src2(E),
+  %% C is the previous instruction
+  case CC of
+    #alu{} ->
+      exit({?MODULE,should_not_be_an_alu,
+	    {"Why the hell do we still have an alu???",CC}});
+    #xsi{} ->
+      exit({?MODULE,should_not_be_a_xsi,
+	    {"Why the hell do we still have a xsi???",CC}});
+    #pre_candidate{} ->
+      C = CC#pre_candidate.alu,
+      DST = ?RTL:alu_dst(C),
+      case DST =:= SRC1 orelse DST =:= SRC2 of
+ 	true ->
+ 	  %% Get the definition of C, since C is PRE-candidate AND has
+ 	  %% been processed before
+ 	  DEF = CC#pre_candidate.def,
+ 	  case DEF of
+ 	    bottom -> 
+ 	      %% Def(E)=bottom, STOP
+              %% No update of the XsiGraph
+ 	      {def_found,new_bottom()};
+ 	    _->
+ 	      %% Simply emend
+ 	      F = emend(E,DST,DEF),
+ 	      ?pp_debug("~nEmendation : E= ",[]),pp_expr(E),?pp_debug(" ==> E'= ",[]),pp_expr(F),?pp_debug("~n",[]),
+ 	      check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
+ 	  end;
+ 	false ->
+ 	  case check_match(C,E) of
+ 	    true -> %% It's a computation of E!
+ 	      %% It should give DST and not Def
+              %% No update of the XsiGraph, cuz we use DST and not Def
+              %% The operand is therefore gonna be a real variable
+ 	      {def_found,DST};
+ 	    _->
+ 	      %% Nothing to do with E
+ 	      check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
+ 	  end
+      end;
+    #move{} ->
+      %% It's a move, we emend E, and continue the definition search
+      DST = ?RTL:move_dst(CC),
+      case SRC1 =:= DST orelse SRC2 =:= DST of
+ 	true ->
+ 	  SRC = ?RTL:move_src(CC),
+ 	  F = emend(E,DST,SRC),
+  	  check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); %% Continue the search
+  	_ ->
+ 	  check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) %% Continue the search
+      end;
+    #xsi_link{} ->
+      Key = CC#xsi_link.num,
+      %% Is Key a family member of XsiDef ?
+      {_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
+      C = Xsi#xsi.inst,
+      case check_match(E,C) of
+        true -> %% There is a Xsi already with a computation of E!
+          %% fetch definition of C, and give it to E
+          %% Must update an edge in the XsiGraph, and here, we know it's a Temp
+          %% Note: this can create a loop (= a cycle of length 1)
+          ?pp_debug(" -- Found a cycle with match: Adding an edge t~w -> t~w",[XsiKey,Key]),
+          ?GRAPH:add_edge(XsiGraph,XsiKey,Key),
+          {def_found,Xsi#xsi.def};
+        _ ->
+          case ?GRAPH:get_path(XsiGraph,Key,XsiKey) of 
+            false ->
+              %% Is it a loop back to itself???
+              case Key =:= XsiKey of 
+                false ->
+                  check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph);
+                _ ->
+                  {expr_found,#eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key}}
+              end;
+            _ ->
+              %% Returning the expression instead of looping
+              %% And in case of no match
+              ExprOp = #eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key},
+              {expr_found,ExprOp}
+          end
+      end;
+    #phi{} -> %% skip them
+      check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph);
+    _ ->
+      PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2),
+
+      %%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2),
+      RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)),
+      case PreColouredTest orelse RegisterTest of
+ 	true ->
+ 	  {def_found,new_bottom()};
+ 	_->
+ 	  DC = ?RTL:defines(CC),
+ 	  case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of
+ 	    true ->
+ 	      {def_found,new_bottom()};
+ 	    _ ->
+ 	      %% Orthogonal to E, we continue the search
+ 	      check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
+ 	  end
+      end
+  end.
+
+eval_expr(E) ->
+  ?pp_debug("~n Evaluating the result of ~w~n", [E]),
+  Op1 = ?RTL:alu_src1(E),
+  Op2 = ?RTL:alu_src2(E),
+  true = ?RTL:is_imm(Op1),
+  Val1 = ?RTL:imm_value(Op1),
+  true = ?RTL:is_imm(Op2),
+  Val2 = ?RTL:imm_value(Op2),    
+  {Result, _Sign, _Zero, _Overflow, _Carry} = ?ARCH:eval_alu(?RTL:alu_op(E), Val1, Val2),
+  ?pp_debug("~n Result is then ~w~n", [Result]),
+  ?RTL:mk_imm(Result).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%  CREATTING CFGGRAPH  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+create_cfggraph([],_Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,_XsiGraph) ->
+  ?pp_debug("~n~n ############# PostProcessing ~n~w~n",[LateEdges]),
+  post_process(LateEdges,CFGGraph),
+  ?pp_debug("~n~n ############# Factorizing ~n~w~n",[ToBeFactorizedAcc]),
+  factorize(ToBeFactorizedAcc,CFGGraph),
+  MPAcc;
+create_cfggraph([Label|Ls],Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph) ->
+  Preds = ?CFG:pred(Cfg, Label),
+  case Preds of
+    [] ->
+      exit({?MODULE,do_not_call_on_top,{"Why the hell do we call that function on the start label???",Label}});
+    [P] ->
+      Code = ?BB:code(?CFG:bb(Cfg, Label)),
+      Defs = get_defs_in_non_merge_block(Code, []),
+      ?pp_debug("~nAdding a vertex for ~w", [Label]),
+      Succs = ?CFG:succ(Cfg, Label),
+      case Succs of
+        [] -> %% Exit point
+          ?GRAPH:add_vertex(CFGGraph, Label, #block{type = exit}),
+          NewToBeFactorizedAcc = ToBeFactorizedAcc;
+        _ -> %% Split point
+          ?GRAPH:add_vertex(CFGGraph,Label,#block{type=not_mp,attributes={P,Succs}}),
+          NewToBeFactorizedAcc = [Label|ToBeFactorizedAcc]
+      end,
+      ?pp_debug("~nAdding an edge ~w -> ~w (~w)",[P,Label,Defs]),
+      case ?GRAPH:add_edge(CFGGraph,P,Label,Defs) of
+        {error,Reason} ->
+          exit({?MODULE,forget_that_for_christs_sake_bingwen_please,{"Bad edge",Reason}});
+        _ ->
+          ok
+      end,
+      create_cfggraph(Ls,Cfg,CFGGraph,NewToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph);
+    _ -> %% Merge point
+      Code = ?BB:code(?CFG:bb(Cfg,Label)),
+      {Defs,Xsis,Maps,Uses} = get_info_in_merge_block(Code,XsiGraph,[],[],gb_trees:empty(),gb_trees:empty()),
+      Attributes = #mp{preds=Preds,xsis=Xsis,defs=Defs,maps=Maps,uses=Uses},
+      MergeBlock = #block{type=mp,attributes=Attributes},
+      ?pp_debug("~nAdding a vertex for ~w with Defs= ~w",[Label,Defs]),
+      ?GRAPH:add_vertex(CFGGraph,Label,MergeBlock),
+      %% Add edges
+      NewLateEdges = add_edges_for_mp(Preds,Label,LateEdges),
+      create_cfggraph(Ls,Cfg,CFGGraph,ToBeFactorizedAcc,[Label|MPAcc],NewLateEdges,XsiGraph)
+  end.
+
+get_defs_in_non_merge_block([], Acc) ->
+  ?SETS:from_list(Acc);
+get_defs_in_non_merge_block([Inst|Rest], Acc) ->
+  case Inst of
+    #pre_candidate{} ->
+      Def = Inst#pre_candidate.def,
+      case Def of
+        #temp{} ->
+          %%        {temp,Key,_Var} ->
+          %%          get_defs_in_non_merge_block(Rest,[Key|Acc]);
+          get_defs_in_non_merge_block(Rest, [Def#temp.key|Acc]);
+ 	_-> %% Real variables or bottom
+ 	  get_defs_in_non_merge_block(Rest, Acc)
+      end;
+    _  ->
+      get_defs_in_non_merge_block(Rest, Acc)
+  end.
+
+get_info_in_merge_block([],_XsiGraph,Defs,Xsis,Maps,Uses) ->
+  {?SETS:from_list(Defs),Xsis,Maps,Uses}; %% Xsis are in backward order
+get_info_in_merge_block([Inst|Rest],XsiGraph,Defs,Xsis,Maps,Uses) ->
+  case Inst of
+    #pre_candidate{} ->
+      Def = Inst#pre_candidate.def,
+      case Def of
+        #temp{} ->
+          get_info_in_merge_block(Rest,XsiGraph,[Def#temp.key|Defs],Xsis,Maps,Uses);
+ 	_ ->
+          get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses)
+      end;
+    #xsi_link{} ->
+      Key = Inst#xsi_link.num,
+      {_Key,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
+      OpList = xsi_oplist(Xsi),
+      {NewMaps,NewUses} = add_map_and_uses(OpList,Key,Maps,Uses),
+      get_info_in_merge_block(Rest,XsiGraph,Defs,[Key|Xsis],NewMaps,NewUses);
+    _  ->
+      get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses)
+  end.
+
+add_edges_for_mp([], _Label, LateEdges) ->
+  LateEdges;
+add_edges_for_mp([P|Ps], Label, LateEdges) ->
+  add_edges_for_mp(Ps,Label,[{P,Label}|LateEdges]).
+
+%% Doesn't do anything so far
+add_map_and_uses([], _Key, Maps, Uses) ->
+  {Maps,Uses};
+add_map_and_uses([XsiOp|Ops], Key, Maps, Uses) ->
+  case XsiOp#xsi_op.op of
+    #bottom{} ->
+      Set = case gb_trees:lookup(XsiOp,Maps) of
+              {value, V} ->
+                ?SETS:add_element(Key,V);
+              none ->
+                ?SETS:from_list([Key])
+            end,
+      NewMaps = gb_trees:enter(XsiOp,Set,Maps),
+      NewUses = Uses;
+    #temp{} ->
+      Set = case gb_trees:lookup(XsiOp,Maps) of
+              {value, V} ->
+                ?SETS:add_element(Key,V);
+              none ->
+                ?SETS:from_list([Key])
+            end,
+      NewMaps = gb_trees:enter(XsiOp,Set,Maps),
+      Pred = XsiOp#xsi_op.pred,
+      OOP = XsiOp#xsi_op.op,
+      SSet = case gb_trees:lookup(Pred,Uses) of
+	       {value, VV} ->
+		 ?SETS:add_element(OOP#temp.key,VV);
+	       none ->
+		 ?SETS:from_list([OOP#temp.key])
+	     end,
+      NewUses = gb_trees:enter(Pred,SSet,Uses);
+    #eop{} ->
+      Set = case gb_trees:lookup(XsiOp,Maps) of
+              {value, V} ->
+                ?SETS:add_element(Key,V);
+              none ->
+                ?SETS:from_list([Key])
+            end,
+      NewMaps = gb_trees:enter(XsiOp,Set,Maps),
+      Pred = XsiOp#xsi_op.pred,
+      Op = XsiOp#xsi_op.op,
+      SSet = case gb_trees:lookup(Pred,Uses) of
+	       {value, VV} ->
+		 ?SETS:add_element(Op#eop.stopped_by,VV);
+	       none ->
+		 ?SETS:from_list([Op#eop.stopped_by])
+	     end,
+      NewUses = gb_trees:enter(Pred,SSet,Uses);
+    _->
+      NewMaps = Maps,
+      NewUses = Uses
+  end,
+  add_map_and_uses(Ops, Key, NewMaps, NewUses).
+
+post_process([], _CFGGraph) -> ok;
+post_process([E|Es], CFGGraph) ->
+  {Pred,Label} = E,
+  {_PP,Block} = ?GRAPH:vertex(CFGGraph,Label),
+  Att = Block#block.attributes,
+  Uses = Att#mp.uses,
+  SetToAdd = case gb_trees:lookup(Pred,Uses) of
+               {value, Set} ->
+                 Set;
+               none ->
+                 ?SETS:new()
+             end,
+  %% ?pp_debug("~nAdding an edge ~w -> ~w (~w)",[Pred,Label,SetToAdd]),
+  ?GRAPH:add_edge(CFGGraph, Pred, Label, SetToAdd),
+  post_process(Es, CFGGraph).
+
+factorize([], _CFGGraph) -> ok;
+factorize([P|Ps], CFGGraph) ->
+  [OE|OEs] = ?GRAPH:out_edges(CFGGraph,P),
+  %% ?pp_debug("~nIn_degrees ~w : ~w",[P,?GRAPH:in_degree(CFGGraph,P)]),
+  [InEdge] = ?GRAPH:in_edges(CFGGraph,P),
+  {E,V1,V2,Label} = ?GRAPH:edge(CFGGraph,InEdge),
+  {_OEE,_OEV1,_OEV2,LOE} = ?GRAPH:edge(CFGGraph,OE),
+  List = shoot_info_upwards(OEs,LOE,CFGGraph),
+  NewLabel = ?SETS:union(Label,List),
+  ?GRAPH:add_edge(CFGGraph,E,V1,V2,NewLabel),
+  factorize(Ps, CFGGraph).
+
+shoot_info_upwards([], Acc, _CFGGraph) -> Acc;
+shoot_info_upwards([E|Es], Acc, CFGGraph) ->
+  {_E,_V1,_V2,Set} = ?GRAPH:edge(CFGGraph,E),
+  NewAcc = ?SETS:intersection(Acc, Set),
+  case ?SETS:size(NewAcc) of
+    0 -> NewAcc;
+    _ -> shoot_info_upwards(Es,NewAcc,CFGGraph)
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  DOWNSAFETY   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+perform_downsafety([], _G, _XsiG) ->
+  ok;
+perform_downsafety([MP|MPs], G, XG) ->
+  {V,Block} = ?GRAPH:vertex(G, MP),
+  NDS = ?SETS:new(),
+  Att = Block#block.attributes,
+  Maps = Att#mp.maps,
+  Defs = Att#mp.defs,
+  OutEdges = ?GRAPH:out_edges(G, MP),
+  %% ?pp_debug("~n Inspection Maps : ~w",[Maps]),
+  NewNDS = parse_keys(gb_trees:keys(Maps),Maps,OutEdges,G,Defs,NDS,XG),
+  NewAtt = Att#mp{ndsSet = NewNDS},
+  ?GRAPH:add_vertex(G, V, Block#block{attributes = NewAtt}),
+  ?pp_debug("~n Not Downsafe at L~w: ~w", [V, NewNDS]),
+  %%io:format(standard_io,"~n Not Downsafe at L~w: ~w",[V,NewNDS]),
+  perform_downsafety(MPs, G, XG).
+
+parse_keys([], _Maps, _OutEdges, _G, _Defs, NDS, _XsiG) ->
+  NDS;
+parse_keys([M|Ms], Maps, OutEdges, G, Defs, NDS, XsiG) ->
+  KillerSet = gb_trees:get(M,Maps),
+  %% ?pp_debug("~n Inspection ~w -> ~w",[M,KillerSet]),
+  TempSet = ?SETS:intersection(KillerSet,Defs),
+  NewNDS = case ?SETS:size(TempSet) of
+	     0 -> getNDS(M,KillerSet,NDS,OutEdges,G,XsiG);
+	     _ ->
+	       %% One Xsi which has M as operand has killed it
+	       %% M is then Downsafe
+	       %% and is not added to the NotDownsafeSet (NDS)
+	       NDS
+	   end,
+  parse_keys(Ms, Maps, OutEdges, G, Defs, NewNDS, XsiG).
+
+getNDS(_M, _KillerSet, NDS, [], _G, _XsiG) ->
+  NDS;
+getNDS(M, KillerSet, NDS, [E|Es], G, XsiG) ->
+  {_EE,_V1,_V2,Label} = ?GRAPH:edge(G, E),
+  Set = ?SETS:intersection(KillerSet, Label),
+  %% ?pp_debug("~n ######## Intersection between KillerSet: ~w and Label: ~w",[KillerSet,Label]),
+  %% ?pp_debug("~n ######## ~w",[Set]),
+  case ?SETS:size(Set) of
+    0 ->
+      %% M is not downsafe
+      ?SETS:add_element(M, NDS);
+    _ ->
+      %% Try the other edges
+      getNDS(M, KillerSet, NDS, Es, G, XsiG)
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  WILL BE AVAILABLE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+perform_will_be_available(XsiGraph,CFGGraph,Options) ->
+  Keys = ?GRAPH:vertices(XsiGraph),
+  ?pp_debug("~n############ Can Be Available ##########~n",[]),
+  ?option_time(perform_can_be_available(Keys,XsiGraph,CFGGraph),"RTL A-SSAPRE WillBeAvailable - Compute CanBeAvailable",Options),
+  ?pp_debug("~n############ Later ##########~n",[]),
+  ?option_time(perform_later(Keys,XsiGraph),"RTL A-SSAPRE WillBeAvailable - Compute Later",Options).
+
+perform_can_be_available([],_XsiGraph,_CFGGraph) -> ok;
+perform_can_be_available([Key|Keys],XsiGraph,CFGGraph) ->
+  {V,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
+  case Xsi#xsi.cba of
+    undefined ->
+      {_VV,Block} = ?GRAPH:vertex(CFGGraph,Xsi#xsi.label),
+      Att = Block#block.attributes,
+      NDS = Att#mp.ndsSet,
+      OpList = ?SETS:from_list(xsi_oplist(Xsi)),
+      Set = ?SETS:intersection(NDS,OpList),
+      case ?SETS:size(Set) of
+        0 ->
+          ?GRAPH:add_vertex(XsiGraph, V, Xsi#xsi{cba = true}),
+          perform_can_be_available(Keys, XsiGraph, CFGGraph);
+        _ ->
+          LIST = [X || #temp{key=X} <- ?SETS:to_list(Set)],
+          case LIST of
+            [] ->
+              ?GRAPH:add_vertex(XsiGraph, V, Xsi#xsi{cba = false}),
+              ImmediateParents = ?GRAPH:in_neighbours(XsiGraph, Key),
+              propagate_cba(ImmediateParents,XsiGraph,Xsi#xsi.def,CFGGraph);
+            _ ->
+              ok
+          end,
+          perform_can_be_available(Keys, XsiGraph, CFGGraph)
+      end;
+    _ -> %% True or False => recurse
+      perform_can_be_available(Keys, XsiGraph, CFGGraph)
+  end.
+
+propagate_cba([],_XG,_Def,_CFGG) -> ok;
+propagate_cba([IPX|IPXs],XsiGraph,XsiDef,CFGGraph) ->
+  {V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX),
+  {_VV,Block} = ?GRAPH:vertex(CFGGraph,IPXsi#xsi.label),
+  Att = Block#block.attributes,
+  NDS = Att#mp.ndsSet,
+  List = ?SETS:to_list(?SETS:intersection(NDS,?SETS:from_list(xsi_oplist(IPXsi)))),
+  case IPXsi#xsi.cba of
+    false -> ok;
+    _ ->
+      case lists:keymember(XsiDef, #xsi_op.op, List) of
+        true ->
+          ?GRAPH:add_vertex(XsiGraph, V, IPXsi#xsi{cba = false}),
+          ImmediateParents = ?GRAPH:in_neighbours(XsiGraph, IPX),
+          propagate_cba(ImmediateParents,XsiGraph,IPXsi#xsi.def,CFGGraph);
+        _ ->
+          ok
+      end
+  end,
+  propagate_cba(IPXs,XsiGraph,XsiDef,CFGGraph).
+
+perform_later([], _XsiGraph) -> ok;
+perform_later([Key|Keys], XsiGraph) ->
+  {V, Xsi} = ?GRAPH:vertex(XsiGraph, Key),
+  %% ?pp_debug("~n DEBUG : inspecting later of ~w (~w)~n",[Key,Xsi#xsi.later]),
+  case Xsi#xsi.later of
+    undefined ->
+      OpList = xsi_oplist(Xsi),
+      case parse_ops(OpList,fangpi) of  %% It means "fart" in chinese :D
+        has_temp ->
+          perform_later(Keys,XsiGraph);
+        has_real ->
+          case Xsi#xsi.cba of
+            true ->
+              ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true});
+            undefined ->
+              ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true});
+            _ ->
+              ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=false})
+          end,
+          AllParents = digraph_utils:reaching([Key], XsiGraph),
+          ?pp_debug("~nPropagating to all parents of t~w: ~w",[Key,AllParents]),
+          propagate_later(AllParents,XsiGraph),
+          perform_later(Keys,XsiGraph);
+        _ -> %% Just contains bottoms and/or expressions
+          ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=true}),
+          perform_later(Keys,XsiGraph)
+      end;
+    _ -> %% True or False => recurse
+      perform_later(Keys,XsiGraph)
+  end.
+
+propagate_later([], _XG) -> ok;
+propagate_later([IPX|IPXs], XsiGraph) ->
+  {V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX),
+  case IPXsi#xsi.later of
+    false ->
+      ?pp_debug("~nThrough propagation, later of t~w is already reset",[IPX]),
+      propagate_later(IPXs,XsiGraph);
+    _ ->
+      ?pp_debug("~nThrough propagation, resetting later of t~w",[IPX]),
+      case IPXsi#xsi.cba of
+        true ->
+          ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true});
+        undefined ->
+          ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true});
+        _ ->
+          ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=false})
+      end,
+      propagate_later(IPXs,XsiGraph)
+  end.
+
+parse_ops([], Res) ->
+  Res;
+parse_ops([Op|Ops], Res) ->
+  case Op#xsi_op.op of
+    #temp{} ->
+      NewRes = has_temp,
+      parse_ops(Ops,NewRes);
+    #bottom{} ->
+      parse_ops(Ops,Res);
+    #eop{} ->
+      parse_ops(Ops,Res);
+    _ ->
+      has_real
+  end.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  CODE MOTION  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+perform_code_motion([], Cfg, _XsiG) ->
+  Cfg;
+perform_code_motion([L|Labels], Cfg, XsiG) ->
+  Code=?BB:code(?CFG:bb(Cfg,L)),
+  ?pp_debug("~n################  Code Motion in L~w~n",[L]),
+  ?pp_debug("~nCode to move ~n",[]),
+  pp_instrs(Code,XsiG),
+  NewCfg = code_motion_in_block(L,Code,Cfg,XsiG,[],gb_trees:empty()),
+  ?pp_debug("~n################  Code Motion successful in L~w~n",[L]),
+  perform_code_motion(Labels,NewCfg,XsiG).
+
+code_motion_in_block(Label,[],Cfg,_XsiG,Visited,InsertionsAcc) ->
+  InsertionsAlong = gb_trees:keys(InsertionsAcc),
+  Code = lists:reverse(Visited),
+  NewBB = ?BB:mk_bb(Code),
+  Cfg2 = ?CFG:bb_add(Cfg,Label,NewBB),
+  %% Must come after the bb_add, since redirect will update the Phis too...
+  Cfg3 = make_insertions(Label,InsertionsAlong,InsertionsAcc,Cfg2),
+  %% ?pp_debug("~nChecking the Code at L~w:~n~p",[Label,?BB:code(?CFG:bb(Cfg3,Label))]),
+  Cfg3;
+code_motion_in_block(L,[Inst|Insts],Cfg,XsiG,Visited,InsertionsAcc) ->
+  ?pp_debug("~nInspecting Inst : ~n",[]),pp_instr(Inst,XsiG),
+  case Inst of
+    #pre_candidate{} ->
+      Def = Inst#pre_candidate.def,
+      Alu = Inst#pre_candidate.alu,
+      case Def of
+        bottom ->
+          InstToAdd = Alu;
+        #temp{} ->
+          Key = Def#temp.key,
+          {_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
+          case Xsi#xsi.wba of
+            true ->
+              %% Turn into a move
+              Dst = ?RTL:alu_dst(Alu),
+              Move = ?RTL:mk_move(Dst,Def#temp.var),
+              pp_instr(Inst#pre_candidate.alu,nil), ?pp_debug(" ==> ",[]), pp_instr(Move,nil),
+              %% Counting redundancies
+              redundancy_add(),
+              InstToAdd = Move;
+            _ ->
+              InstToAdd = Alu
+          end;
+        _ -> %% Def is a real variable
+          %% Turn into a move
+          Dst = ?RTL:alu_dst(Alu),
+          Move = ?RTL:mk_move(Dst,Def),
+          pp_instr(Alu,nil), ?pp_debug(" ==> ",[]), pp_instr(Move,nil),
+          %% Counting redundancies
+          redundancy_add(),
+          InstToAdd = Move
+      end,
+      code_motion_in_block(L,Insts,Cfg,XsiG,[InstToAdd|Visited],InsertionsAcc);
+    #xsi_link{} ->
+      Key = Inst#xsi_link.num,
+      {_V,Xsi} = ?GRAPH:vertex(XsiG,Key),      
+      case Xsi#xsi.wba of
+        true ->
+          %% Xsi is a WBA, it might trigger insertions
+          OpList = xsi_oplist(Xsi),
+          ?pp_debug(" This Xsi is a 'Will be available'",[]),
+          %% Cleaning the instruction
+          Expr = prepare_inst(Xsi#xsi.inst),
+          {NewOpList,NewInsertionsAcc} = get_insertions(OpList,[],InsertionsAcc,Visited,Expr,XsiG),
+          %% Making Xsi a Phi with Oplist
+          PhiOpList = [{Pred,Var} || #xsi_op{pred=Pred,op=Var} <- NewOpList],
+          Def = Xsi#xsi.def,
+          Phi = ?RTL:phi_arglist_update(?RTL:mk_phi(Def#temp.var),PhiOpList),
+          ?pp_debug("~n Xsi is turned into Phi : ~w",[Phi]),
+          code_motion_in_block(L,Insts,Cfg,XsiG,[Phi|Visited],NewInsertionsAcc);
+        _ ->
+          ?pp_debug(" This Xsi is not a 'Will be available'",[]),
+          code_motion_in_block(L,Insts,Cfg,XsiG,Visited,InsertionsAcc)
+      end;
+%%     phi ->
+%%       code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc);
+    _ ->
+      %% Other instructions.... Phis too
+      code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc)
+  end.
+
+prepare_inst(Expr) ->
+  S1 = ?RTL:alu_src1(Expr),
+  S2 = ?RTL:alu_src2(Expr),
+  NewInst = case S1 of
+	      #temp{} -> ?RTL:alu_src1_update(Expr,S1#temp.var);
+	      _ -> Expr
+	    end,
+  case S2 of
+    #temp{} -> ?RTL:alu_src2_update(NewInst,S2#temp.var);
+    _ -> NewInst
+  end.
+
+get_insertions([],OpAcc,InsertionsAcc,_Visited,_Expr,_XsiG) ->
+  {OpAcc,InsertionsAcc};
+get_insertions([XsiOp|Ops],OpAcc,InsertionsAcc,Visited,Expr,XsiG) ->
+  Pred = XsiOp#xsi_op.pred,
+  Op = XsiOp#xsi_op.op,
+  case Op of
+    #bottom{} ->
+      case gb_trees:lookup(Pred,InsertionsAcc) of
+        {value,Insertion} ->
+          From = Insertion#insertion.from,
+          case lists:keyfind(Op, 1, From) of
+            false ->
+              ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
+              Dst = Op#bottom.var,
+              Expr2 = ?RTL:alu_dst_update(Expr,Dst),
+              Inst = manufacture_computation(Pred,Expr2,Visited),
+              Code = Insertion#insertion.code,
+              NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]},
+              NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc);
+            {_, Val} ->
+              ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
+              Dst = Val,
+              NewInsertionsAcc = InsertionsAcc
+          end;
+        none ->
+          ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
+          Dst = Op#bottom.var,
+          Expr2 = ?RTL:alu_dst_update(Expr,Dst),
+          Inst = manufacture_computation(Pred,Expr2,Visited),
+          NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]},
+          NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc)
+      end;
+    #const_expr{} ->
+      case gb_trees:lookup(Pred,InsertionsAcc) of
+        {value,Insertion} ->
+          From = Insertion#insertion.from,
+          case lists:keyfind(Op, 1, From) of
+            false ->
+              ?pp_debug("~nThere have been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
+              Dst = Op#const_expr.var,
+              Val = Op#const_expr.value,
+              Inst = ?RTL:mk_move(Dst,Val),
+              Code = Insertion#insertion.code,
+              NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]},
+              NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc);
+            {_, Val} ->
+              ?pp_debug("~nThere have been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
+              Dst = Val,
+              NewInsertionsAcc = InsertionsAcc
+          end;
+        none ->
+          ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
+          Dst = Op#const_expr.var,
+          Val = Op#const_expr.value,
+          Inst = ?RTL:mk_move(Dst,Val),
+          NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]},
+          NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc)
+      end;
+    #eop{} ->
+      %% We treat expressions like bottoms
+      %% The value must be recomputed, and therefore not available...
+      case gb_trees:lookup(Pred,InsertionsAcc) of
+        {value,Insertion} ->
+          From = Insertion#insertion.from,
+          case lists:keyfind(Op, 1, From) of
+            false ->
+              ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
+              Dst = Op#eop.var,
+              Expr2 = ?RTL:alu_dst_update(Expr,Dst),
+              Inst = manufacture_computation(Pred,Expr2,Visited),
+              Code = Insertion#insertion.code,
+              NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]},
+              NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc);
+            {_, Val} ->
+              ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
+              Dst = Val,
+              NewInsertionsAcc = InsertionsAcc
+          end;
+        none ->
+          ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
+          Dst = Op#eop.var,
+          Expr2 = ?RTL:alu_dst_update(Expr,Dst),
+          Inst = manufacture_computation(Pred,Expr2,Visited),
+          NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]},
+          NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc)
+      end;
+    #temp{} ->
+      case gb_trees:lookup(Pred,InsertionsAcc) of
+        {value,Insertion} ->
+          From = Insertion#insertion.from,
+          case lists:keyfind(Op, 1, From) of
+            false ->
+              ?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
+              Key = Op#temp.key,
+              {_V,Xsi} = ?GRAPH:vertex(XsiG,Key),      
+              case Xsi#xsi.wba of
+                true ->
+                  ?pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]),
+                  Dst = Op#temp.var,
+                  NewInsertionsAcc = InsertionsAcc;
+                _ ->
+                  ?pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]),
+                  Dst = ?RTL:mk_new_var(),
+                  Expr2 = ?RTL:alu_dst_update(Expr,Dst),
+                  Inst = manufacture_computation(Pred,Expr2,Visited),
+                  Code = Insertion#insertion.code,
+                  NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]},
+                  NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc)
+              end;
+            {_, Val} ->
+              ?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too (Op=~w)",[Pred,Op]),
+              ?pp_debug("~nThis means, this temp is a WBA Xsi's definition",[]),
+              Dst = Val,
+              NewInsertionsAcc = InsertionsAcc
+          end;
+        none ->
+          ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course | Op=",[Pred]),pp_arg(Op),
+          Key = Op#temp.key,
+          {_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
+          case Xsi#xsi.wba of
+            true ->
+              ?pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]),
+              Dst = Op#temp.var,
+              NewInsertionsAcc = InsertionsAcc;
+            _ ->
+              ?pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]),
+              Dst = ?RTL:mk_new_var(),
+              Expr2 = ?RTL:alu_dst_update(Expr,Dst),
+              Inst = manufacture_computation(Pred,Expr2,Visited),
+              NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]},
+              NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc)
+          end
+      end;
+    _ ->
+      ?pp_debug("~nThe operand (Op=",[]),pp_arg(Op),?pp_debug(") is a real variable, no need for insertion along L~w",[Pred]),
+      Dst = Op,
+      NewInsertionsAcc = InsertionsAcc
+  end,
+  NewXsiOp = XsiOp#xsi_op{op=Dst},
+  get_insertions(Ops, [NewXsiOp|OpAcc], NewInsertionsAcc, Visited, Expr, XsiG).
+
+manufacture_computation(_Pred, Expr, []) ->
+  ?pp_debug("~n Manufactured computation : ~w", [Expr]),
+  Expr;
+manufacture_computation(Pred, Expr, [I|Rest]) ->
+  %% ?pp_debug("~n Expr = ~w",[Expr]),
+  SRC1 = ?RTL:alu_src1(Expr),
+  SRC2 = ?RTL:alu_src2(Expr),
+  case I of
+    #xsi_link{} ->
+      exit({?MODULE,should_not_be_a_xsi_link,{"Why the hell do we still have a xsi link???",I}});
+    #xsi{} ->
+      exit({?MODULE,should_not_be_a_xsi,{"Why the hell do we still have a xsi ???",I}});
+    #phi{} ->
+      DST = ?RTL:phi_dst(I),
+      Arg = ?RTL:phi_arg(I,Pred),
+      NewInst = case DST =:= SRC1 of
+  	          true -> ?RTL:alu_src1_update(Expr,Arg);
+  	          false -> Expr
+                end,
+      NewExpr = case DST =:= SRC2 of
+                  true -> ?RTL:alu_src2_update(NewInst,Arg);
+                  false -> NewInst
+                end,
+      manufacture_computation(Pred,NewExpr,Rest)
+  end.
+
+make_insertions(_L, [], _ITree, Cfg) ->
+  Cfg; 
+make_insertions(L, [OldPred|Is], ITree, Cfg) ->
+  NewPred      = ?RTL:label_name(?RTL:mk_new_label()),
+  I            = gb_trees:get(OldPred, ITree),
+  CodeToInsert = lists:reverse([?RTL:mk_goto(L)|I#insertion.code]),
+  BBToInsert   = ?BB:mk_bb(CodeToInsert),
+  NewCfg       = ?CFG:bb_insert_between(Cfg, NewPred, BBToInsert, OldPred, L),
+  make_insertions(L, Is, ITree, NewCfg).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  XSI INTERFACE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+xsi_oplist(#xsi{opList=OpList}) ->
+  case OpList of undefined -> [] ; _ -> OpList end.
+xsi_arg(Xsi, Pred) ->
+  case lists:keyfind(Pred, #xsi_op.pred, xsi_oplist(Xsi)) of
+    false ->
+      undetermined_operand;
+    R ->
+      R#xsi_op.op
+  end.
+xsi_arg_update(Xsi, Pred, Op) ->
+  NewOpList = lists:keyreplace(Pred, #xsi_op.pred, xsi_oplist(Xsi), 
+			       #xsi_op{pred=Pred,op=Op}),
+  Xsi#xsi{opList=NewOpList}.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PRETTY-PRINTING %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+-ifndef(SSAPRE_DEBUG).
+
+%%pp_cfg(Cfg,_) -> ?CFG:pp(Cfg).
+pp_cfg(_,_) -> ok.
+pp_instr(_,_) -> ok.
+pp_instrs(_,_) -> ok.
+pp_expr(_) -> ok.
+pp_xsi(_) -> ok.
+pp_arg(_) -> ok.
+pp_xsigraph(_) -> ok.
+pp_cfggraph(_) -> ok.
+%% pp_xsigraph(G) ->
+%%   Vertices = lists:sort(?GRAPH:vertices(G)),
+%%   io:format(standard_io, "Size of the Xsi Graph: ~w", [length(Vertices)]).
+%% pp_cfggraph(G) ->
+%%   Vertices = lists:sort(?GRAPH:vertices(G)),
+%%   io:format(standard_io, "Size of the CFG Graph: ~w", [length(Vertices)]).
+
+-else.
+
+pp_cfg(Cfg, Graph) ->
+  Labels = ?CFG:preorder(Cfg),
+  pp_blocks(Labels, Cfg, Graph).
+
+pp_blocks([], _, _) ->
+  ok;
+pp_blocks([L|Ls], Cfg, Graph) ->
+  Code = hipe_bb:code(?CFG:bb(Cfg,L)),
+  io:format(standard_io,"~n########## Label L~w~n", [L]),
+  pp_instrs(Code, Graph),
+  pp_blocks(Ls, Cfg, Graph).
+
+pp_instrs([], _) ->
+  ok;
+pp_instrs([I|Is], Graph) ->
+  pp_instr(I, Graph),
+  pp_instrs(Is, Graph).
+
+pp_xsi_link(Key, Graph) ->
+  {_Key,Xsi} = ?GRAPH:vertex(Graph, Key),
+  pp_xsi(Xsi).
+
+pp_xsi(Xsi) ->
+  io:format(standard_io, "    [L~w] ", [Xsi#xsi.label]),
+  io:format(standard_io, "[", []), pp_expr(Xsi#xsi.inst),
+  io:format(standard_io, "] Xsi(", []), pp_xsi_args(xsi_oplist(Xsi)),
+  io:format(standard_io, ") (", []), pp_xsi_def(Xsi#xsi.def),
+  io:format(standard_io, ") cba=~w, later=~w | wba=~w~n", [Xsi#xsi.cba,Xsi#xsi.later,Xsi#xsi.wba]).
+
+pp_instr(I, Graph) ->
+  case I of
+    #alu{} ->
+      io:format(standard_io, "    ", []),
+      pp_arg(?RTL:alu_dst(I)),
+      io:format(standard_io, " <- ", []),
+      pp_expr(I),
+      io:format(standard_io, "~n", []);
+    _ ->
+      try ?RTL:pp_instr(standard_io, I)
+      catch _:_ ->
+ 	case I of
+ 	  #pre_candidate{} ->
+ 	    pp_pre(I);
+ 	  #xsi{} ->
+ 	    pp_xsi(I);
+ 	  #xsi_link{} ->
+ 	    pp_xsi_link(I#xsi_link.num, Graph);
+ 	  _->
+ 	    io:format(standard_io,"*** ~w ***~n", [I])
+ 	end
+      end
+  end.
+
+pp_pre(I) ->
+  A = I#pre_candidate.alu,
+  io:format(standard_io, "    ", []),
+  pp_arg(?RTL:alu_dst(A)),
+  io:format(standard_io, " <- ", []),pp_expr(A),
+  io:format(standard_io, " [ ", []),pp_arg(I#pre_candidate.def),
+  %%io:format(standard_io, "~w", [I#pre_candidate.def]),
+  io:format(standard_io, " ]~n",[]).
+
+pp_expr(I) ->
+  pp_arg(?RTL:alu_dst(I)),
+  io:format(standard_io, " <- ", []),
+  pp_arg(?RTL:alu_src1(I)),
+  io:format(standard_io, " ~w ", [?RTL:alu_op(I)]),
+  pp_arg(?RTL:alu_src2(I)).
+
+pp_arg(Arg) ->
+  case Arg of
+    bottom ->
+      io:format(standard_io, "_|_", []);
+    #bottom{} ->
+      io:format(standard_io, "_|_:~w (", [Arg#bottom.key]),pp_arg(Arg#bottom.var),io:format(standard_io,")",[]);
+    #temp{} ->
+      pp_xsi_def(Arg);
+    #eop{} ->
+      io:format(standard_io,"#",[]),pp_expr(Arg#eop.expr),io:format(standard_io,"(",[]),pp_arg(Arg#eop.var),io:format(standard_io,")#",[]);
+    #const_expr{} ->
+      io:format(standard_io,"*",[]),pp_arg(Arg#const_expr.var),io:format(standard_io," -> ",[]),pp_arg(Arg#const_expr.value),io:format(standard_io,"*",[]);
+    undefined ->
+      io:format(standard_io, "...", []); %%"undefined", []);
+    _->
+      case Arg of
+        #alu{} ->
+          pp_expr(Arg);      
+        _->
+          ?RTL:pp_arg(standard_io, Arg)
+      end
+  end.
+
+pp_args([]) ->
+  ok;
+pp_args(undefined) ->
+  io:format(standard_io, "...,...,...", []);
+pp_args([A]) ->
+  pp_arg(A);
+pp_args([A|As]) ->
+  pp_arg(A),
+  io:format(standard_io, ", ", []),
+  pp_args(As).
+
+pp_xsi_args([]) -> ok;
+pp_xsi_args([XsiOp]) ->
+  io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]),
+  pp_arg(XsiOp#xsi_op.op),
+  io:format(standard_io, "}", []);
+pp_xsi_args([XsiOp|Args]) ->
+  io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]),
+  pp_arg(XsiOp#xsi_op.op),
+  io:format(standard_io, "}, ", []),
+  pp_xsi_args(Args);
+pp_xsi_args(Args) ->
+  pp_args(Args).
+
+pp_xsi_def(Arg) ->
+  D = Arg#temp.key,
+  V = Arg#temp.var,
+  io:format(standard_io, "t~w (", [D]),pp_arg(V),io:format(standard_io,")",[]).
+
+pp_cfggraph(G) ->
+  Vertices = lists:sort(?GRAPH:vertices(G)),
+  io:format(standard_io, "Size of the CFG Graph: ~w ~n", [length(Vertices)]),
+  pp_cfgvertex(Vertices, G).
+
+pp_xsigraph(G) ->
+  Vertices = lists:sort(?GRAPH:vertices(G)),
+  io:format(standard_io, "Size of the Xsi Graph: ~w ~n", [length(Vertices)]),
+  pp_xsivertex(Vertices,G).
+
+pp_xsivertex([], _G) ->
+  ok;
+pp_xsivertex([Key|Keys], G) ->
+  {V,Xsi} = ?GRAPH:vertex(G, Key),
+  OutNeighbours = ?GRAPH:out_neighbours(G, V),
+  ?pp_debug(" ~w -> ~w", [V,OutNeighbours]), pp_xsi(Xsi),
+  pp_xsivertex(Keys, G).
+
+pp_cfgvertex([], _G) ->
+  ok;
+pp_cfgvertex([Key|Keys], G) ->
+  {V,Block} = ?GRAPH:vertex(G,Key),
+  case Block#block.type of
+    mp ->
+      ?pp_debug("~n Block ~w's attributes: ~n", [V]),
+      pp_attributes(Block),
+      ?pp_debug("~n Block ~w's edges: ~n", [V]),
+      pp_edges(G, ?GRAPH:in_edges(G,Key), ?GRAPH:out_edges(G,Key));
+    _->
+      ok
+  end,
+  pp_cfgvertex(Keys, G).
+
+pp_attributes(Block) ->
+  Att = Block#block.attributes,
+  case Att of
+    undefined ->
+      ok;
+    _ ->
+      ?pp_debug("        Maps: ~n",[]),pp_maps(gb_trees:keys(Att#mp.maps),Att#mp.maps),
+      ?pp_debug("        Uses: ~n",[]),pp_uses(gb_trees:keys(Att#mp.uses),Att#mp.uses),
+      ?pp_debug("        Defs: ~w~n",[Att#mp.defs]),
+      ?pp_debug("        Xsis: ~w~n",[Att#mp.xsis]),
+      ?pp_debug("        NDS : ",[]),pp_nds(?SETS:to_list(Att#mp.ndsSet))
+  end.
+
+pp_maps([], _Maps) -> ok;
+pp_maps([K|Ks], Maps) ->
+  ?pp_debug("              ",[]),pp_arg(K#xsi_op.op),?pp_debug("-> ~w~n",[?SETS:to_list(gb_trees:get(K,Maps))]),
+  pp_maps(Ks, Maps).
+
+pp_uses([], _Maps) -> ok;
+pp_uses([K|Ks], Maps) ->
+  ?pp_debug("              ~w -> ~w~n",[K,?SETS:to_list(gb_trees:get(K,Maps))]),
+  pp_uses(Ks, Maps).
+
+pp_nds([]) -> ?pp_debug("~n",[]);
+pp_nds(undefined) -> ?pp_debug("None",[]);
+pp_nds([K]) ->
+  pp_arg(K#xsi_op.op), ?pp_debug("~n",[]);
+pp_nds([K|Ks]) ->
+  pp_arg(K#xsi_op.op), ?pp_debug(", ",[]),
+  pp_nds(Ks).
+
+pp_edges(_G, [], []) -> ok;
+pp_edges(G, [], [OUT|OUTs]) ->
+  {_E,V1,V2,Label} = ?GRAPH:edge(G,OUT),
+  ?pp_debug(" Out edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]),
+  pp_edges(G, [], OUTs);
+pp_edges(G, [IN|INs], Outs) ->
+  {_E,V1,V2,Label} = ?GRAPH:edge(G,IN),
+  ?pp_debug("  In edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]),
+  pp_edges(G, INs, Outs).
+
+-endif.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+init_counters() ->
+  put({ssapre_temp,temp_count}, 0),
+  put({ssapre_index,index_count}, 0).
+
+new_bottom() ->
+  IndxCountPair = {ssapre_index, index_count},
+  V = get(IndxCountPair),
+  put(IndxCountPair, V+1),
+  #bottom{key = V, var = ?RTL:mk_new_var()}.
+
+new_temp() ->
+  TmpCountPair = {ssapre_temp, temp_count},
+  V = get(TmpCountPair),
+  put(TmpCountPair, V+1),
+  #temp{key = V, var = ?RTL:mk_new_var()}.
+
+init_redundancy_count() ->
+  put({ssapre_redundancy,redundancy_count}, 0).
+
+redundancy_add() ->
+  RedCountPair = {ssapre_redundancy, redundancy_count},
+  V = get(RedCountPair),
+  put(RedCountPair, V+1).
+
+-ifdef(SSAPRE_DEBUG).
+get_redundancy_count() ->
+  get({ssapre_redundancy,redundancy_count}).
+-endif.