1%% -*- erlang-indent-level: 2 -*-
2%%
3%% Licensed under the Apache License, Version 2.0 (the "License");
4%% you may not use this file except in compliance with the License.
5%% You may obtain a copy of the License at
6%%
7%%     http://www.apache.org/licenses/LICENSE-2.0
8%%
9%% Unless required by applicable law or agreed to in writing, software
10%% distributed under the License is distributed on an "AS IS" BASIS,
11%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12%% See the License for the specific language governing permissions and
13%% limitations under the License.
14%%
15%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16%% File        : hipe_rtl_ssapre.erl
17%% Author      : He Bingwen and Frédéric Haziza
18%% Description : Performs Partial Redundancy Elimination on SSA form.
19%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20%% @doc
21%%
22%% This module implements the <a href="http://cs.wheaton.edu/%7Etvandrun/writings/spessapre.pdf">Anticipation-SSAPRE algorithm</a>,
23%% with several modifications for Partial Redundancy Elimination on SSA form.
24%% We actually found problems in this algorithm, so
25%% we implement another version with several advantages:
26%% - No loop for Xsi insertions
27%% - No fix point iteration for the downsafety part
28%% - Less computations for Will Be Available part
29%% - Complexity of the overall algorithm is improved
30%%
31%% We were supposed to publish these results anyway :D
32%%
33%% @end
34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35
36-module(hipe_rtl_ssapre).
37
38-export([rtl_ssapre/2]).
39
40-include("../main/hipe.hrl").
41-include("hipe_rtl.hrl").
42
43%%-define(SSAPRE_DEBUG, true        ). %% When uncommented, produces debug printouts
44-define(        SETS, ordsets       ). %% Which set implementation module to use
45-define(         CFG, hipe_rtl_cfg  ).
46-define(         RTL, hipe_rtl      ).
47-define(          BB, hipe_bb       ).
48-define(        ARCH, hipe_rtl_arch ).
49-define(       GRAPH, digraph       ).
50
51%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
52%% Debugging stuff
53%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54
55-ifndef(SSAPRE_DEBUG).
56-define(pp_debug(_Str, _Args), ok).
57-else.
58-define(pp_debug(Str, Args), io:format(standard_io, Str, Args)).
59-endif.
60
61%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
62%% Records / Structures
63%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
64
65-record(xsi_link, {num}). %% Number is the index of the temporary (a Key into the Xsi Tree)
66-record(temp, {key, var}).
67-record(bottom, {key, var}).
68-record(xsi, {inst,   %% Associated instruction
69              def,    %% Hypothetical temporary variable
70	              %% that stores the result of the computation
71              label,  %% Block Label where the xsi is inserted
72              opList, %% List of operands
73              cba,    %%
74              later,  %%
75              wba
76             }).
77
78-record(pre_candidate, {alu, def}).
79-record(xsi_op, {pred, op}).
80
81-record(mp, {xsis, maps, preds, defs, uses, ndsSet}).
82-record(block, {type, attributes}).
83
84-record(eop, {expr, var, stopped_by}).
85-record(insertion, {code, from}).
86
87-record(const_expr, {var, value}).
88
89%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
90%% Main function
91%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92
93rtl_ssapre(RtlSSACfg, Options) ->
94  %% io:format("\n################ Original CFG ################\n"),
95  %% hipe_rtl_cfg:pp(RtlSSACfg),
96  %% io:format("\n\n############ SSA-Form CHECK ==> ~w\n",[hipe_rtl_ssa:check(RtlSSACfg)]),
97
98  {CFG2,XsiGraph,CFGGraph,MPs} = perform_Xsi_insertion(RtlSSACfg,Options),
99  %%?pp_debug("~n~n################ Xsi CFG ################\n",[]),pp_cfg(CFG2,XsiGraph),
100  XsiList = ?GRAPH:vertices(XsiGraph),
101  case XsiList of
102    [] ->
103      %% No Xsi
104      ?pp_debug("~n~n################ No Xsi Inserted ################~n",[]),
105      ok;
106    _ ->
107      ?pp_debug("~n############ Downsafety ##########~n",[]),
108      ?option_time(perform_downsafety(MPs,CFGGraph,XsiGraph),"RTL A-SSAPRE Downsafety",Options),
109      ?pp_debug("~n~n################ CFG Graph ################~n",[]),pp_cfggraph(CFGGraph),
110      ?pp_debug("~n############ Will Be Available ##########~n",[]),
111      ?option_time(perform_will_be_available(XsiGraph,CFGGraph,Options),"RTL A-SSAPRE WillBeAvailable",Options)
112  end,
113
114  ?pp_debug("~n############ No more need for the CFG Graph....Deleting...",[]),?GRAPH:delete(CFGGraph),
115  ?pp_debug("~n~n################ Xsi Graph ################~n",[]),pp_xsigraph(XsiGraph),
116
117  ?pp_debug("~n############ Code Motion ##########~n",[]),
118  Labels = ?CFG:preorder(CFG2),
119
120  ?pp_debug("~n~n################ Xsi CFG ################~n",[]),pp_cfg(CFG2,XsiGraph),
121
122  init_redundancy_count(),
123  FinalCFG = ?option_time(perform_code_motion(Labels,CFG2,XsiGraph),"RTL A-SSAPRE Code Motion",Options),
124
125  ?pp_debug("\n############ No more need for the Xsi Graph....Deleting...",[]),?GRAPH:delete(XsiGraph),
126
127  %% io:format("\n################ Final CFG ################\n"),
128  %% hipe_rtl_cfg:pp(FinalCFG),
129  %% io:format("\n\n############ SSA-Form CHECK ==> ~w\n",
130  %%           [hipe_rtl_ssa:check(FinalCFG)]),
131  ?pp_debug("\nSSAPRE : ~w redundancies were found\n",[get_redundancy_count()]),
132
133  FinalCFG.
134
135%% ##########################################################################
136%% ######################## XSI INSERTION ###################################
137%% ##########################################################################
138
139perform_Xsi_insertion(Cfg, Options) ->
140  init_counters(), %% Init counters for Bottoms and Temps
141  DigraphOpts = [cyclic, private],
142  XsiGraph = digraph:new(DigraphOpts),
143  %% Be careful, the digraph component is NOT garbage collected,
144  %% so don't create 20 millions of instances!
145  %% finds the longest depth
146  %% Depth-first, preorder traversal over Basic Blocks.
147  %%Labels = ?CFG:reverse_postorder(Cfg),
148  Labels = ?CFG:preorder(Cfg),
149
150  ?pp_debug("~n~n############# Finding definitions for computation~n~n",[]),
151  {Cfg2,XsiGraph} = ?option_time(find_definition_for_computations(Labels,Cfg,XsiGraph),"RTL A-SSAPRE Xsi Insertion, searching from instructions",Options),
152
153  %% Active List creation
154  GeneratorXsiList = lists:sort(?GRAPH:vertices(XsiGraph)),
155  ?pp_debug("~n~n############# Inserted Xsis ~w",[GeneratorXsiList]),
156  ?pp_debug("~n~n############# Finding operands~n",[]),
157  {Cfg3,XsiGraph} = ?option_time(find_operands(Cfg2,XsiGraph,GeneratorXsiList,0),"RTL A-SSAPRE Xsi Insertion, finding operands",Options),
158
159  %% Creating the CFGGraph
160  ?pp_debug("~n~n############# Creating CFG Graph",[]),
161  ?pp_debug("~n############# Labels = ~w",[Labels]),
162  CFGGraph = digraph:new(DigraphOpts),
163  [StartLabel|Others] = Labels,   % adding the start label as a leaf
164  ?pp_debug("~nAdding a vertex for the start label: ~w",[StartLabel]),
165  ?GRAPH:add_vertex(CFGGraph, StartLabel, #block{type = top}),
166                                                % Doing the others
167  MPs = ?option_time(create_cfggraph(Others,Cfg3,CFGGraph,[],[],[],XsiGraph),"RTL A-SSAPRE Xsi Insertion, creating intermediate 'SSAPRE Graph'",Options),
168
169  %% Return the collected information
170  {Cfg3,XsiGraph,CFGGraph,MPs}.
171
172%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
173
174find_definition_for_computations([], Cfg, XsiGraph) ->
175  {Cfg,XsiGraph}; %% No more block to inspect in the depth-first order
176find_definition_for_computations([Label|Rest], Cfg, XsiGraph) ->
177  Code = ?BB:code(?CFG:bb(Cfg,Label)),
178  {NewCfg,XsiGraph} = find_definition_for_computations_in_block(Label,Code,Cfg,[],XsiGraph),
179  find_definition_for_computations(Rest, NewCfg, XsiGraph).
180
181%%===========================================================================
182%% Searches from instruction for one block BlockLabel.
183%% We process forward over instructions.
184
185find_definition_for_computations_in_block(BlockLabel,[],Cfg,
186					  VisitedInstructions,XsiGraph)->
187  Code = lists:reverse(VisitedInstructions),
188  NewBB = ?BB:mk_bb(Code),
189  NewCfg = ?CFG:bb_add(Cfg,BlockLabel,NewBB),
190  {NewCfg,XsiGraph}; %% No more instructions to inspect in this block
191find_definition_for_computations_in_block(BlockLabel,[Inst|Rest],Cfg,
192					  VisitedInstructions,XsiGraph) ->
193  %%  ?pp_debug(" Inspecting instruction: ",[]),pp_instr(Inst,nil),
194  case Inst of
195    #alu{} ->
196      %% Is Inst interesting for SSAPRE?
197      %% i.e., is Inst an arithmetic operation which doesn't deal with precoloured?
198      %% Note that since we parse forward, we have no 'pre_candidate'-type so far.
199      case check_definition(Inst,VisitedInstructions,BlockLabel,Cfg,XsiGraph) of
200 	{def_found,Def} ->
201 	  %% Replacing Inst in Cfg
202 	  NewInst = #pre_candidate{alu=Inst,def=Def},
203 	  NewVisited = [NewInst|VisitedInstructions],
204 	  %% Recurse forward over instructions, same CFG, same XsiGraph
205 	  find_definition_for_computations_in_block(BlockLabel,Rest,Cfg,
206						    NewVisited,XsiGraph);
207 	{merge_point,Xsi} ->
208          Def = Xsi#xsi.def,
209    	  Key = Def#temp.key,
210 	  NewInst = #pre_candidate{alu=Inst,def=Def},
211          XsiLink = #xsi_link{num=Key},
212
213          %% Add a vertex to the Xsi Graph
214          ?GRAPH:add_vertex(XsiGraph,Key,Xsi),
215 	  ?pp_debug(" Inserting Xsi: ",[]),pp_xsi(Xsi),
216
217          Label = Xsi#xsi.label,
218	  {NewCfg, NewVisited} =
219	    case BlockLabel =:= Label of
220	      false ->
221		%% Insert the Xsi in the appropriate block
222		Code = hipe_bb:code(?CFG:bb(Cfg,Label)),
223		{BeforeCode,AfterCode} = split_for_xsi(lists:reverse(Code),[]),
224		NewCode = BeforeCode++[XsiLink|AfterCode],
225		NewBB = hipe_bb:mk_bb(NewCode),
226		{?CFG:bb_add(Cfg,Label,NewBB), [NewInst|VisitedInstructions]};
227	      _->
228		{BeforeCode,AfterCode} = split_for_xsi(VisitedInstructions,[]),
229		TempVisited = BeforeCode++[XsiLink|AfterCode],
230		TempVisited2 = lists:reverse(TempVisited),
231		{Cfg, [NewInst|TempVisited2]}
232	    end,
233          find_definition_for_computations_in_block(BlockLabel, Rest, NewCfg,
234						    NewVisited, XsiGraph)
235      end;
236    _ ->
237      %%?pp_debug("~n [L~w] Not concerned with: ~w",[BlockLabel,Inst]),
238      %% If the instruction is not a SSAPRE candidate, we skip it and keep on
239      %% processing instructions
240      %% Prepend Inst, so that we have all in reverse order.
241      %% Easy to parse backwards
242      find_definition_for_computations_in_block(BlockLabel, Rest, Cfg,
243						[Inst|VisitedInstructions], XsiGraph)
244  end.
245
246%% ############################################################################
247%% We have E as an expression, I has an alu (arithmetic operation), and
248%% we inspect backwards the previous instructions to find a definition for E.
249%% Since we parse in forward order, we know that the previous SSAPRE
250%% instruction will have a definition.
251
252check_definition(E,[],BlockLabel,Cfg,XsiGraph)->
253  %% No more instructions in that block
254  %% No definition found in that block
255  %% Search is previous blocks
256  Preds = ?CFG:pred(Cfg, BlockLabel),
257  %%  ?pp_debug("~n CHECKING DEFINITION  ####### Is L~w a merge block? It has ~w preds. So far E=",[BlockLabel,length(Preds)]),pp_expr(E),
258  case Preds of
259    [] ->
260      %% Entry Point
261      {def_found,bottom};
262    [P] ->
263      %% One predecessor only, we just keep looking for a definition in that block
264      VisitedInstructions = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))),
265      check_definition(E,VisitedInstructions,P,Cfg,XsiGraph);
266    _ ->
267      Temp = new_temp(),
268      %% It's a merge point
269      OpList = [#xsi_op{pred=X} || X<-Preds],
270      Xsi = #xsi{inst=E,def=Temp,label=BlockLabel,opList=OpList},
271      {merge_point,Xsi}
272  end;
273check_definition(E,[CC|Rest],BlockLabel,Cfg,XsiGraph) ->
274  SRC1 = ?RTL:alu_src1(E),
275  SRC2 = ?RTL:alu_src2(E),
276  case CC of
277    #alu{} ->
278      exit({?MODULE,should_not_be_an_alu,
279	    {"Why the hell do we still have an alu???",CC}});
280    #pre_candidate{} ->
281      %% C is the previous instruction
282      C = CC#pre_candidate.alu,
283      DST = ?RTL:alu_dst(C),
284      case DST =:= SRC1 orelse DST =:= SRC2 of
285 	false ->
286 	  case check_match(E,C) of
287 	    true -> %% It's a computation of E!
288 	      %% Get the dst of the alu
289 	      {def_found,DST};
290 	    _->
291 	      check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
292 	  end;
293 	true ->
294 	  %% Get the definition of C, since C is PRE-candidate AND has been processed before
295 	  DEF = CC#pre_candidate.def,
296 	  case DEF of
297 	    bottom ->
298 	      %% Def(E)=bottom, STOP
299 	      {def_found,bottom};
300 	    _ ->
301 	      %% Emend E with this def(C)
302 	      %%?pp_debug("Parameters are E=~w, DST=~w, DEF=~w",[E,DST,DEF]),
303 	      F = emend(E,DST,DEF),
304 	      check_definition(F,Rest,BlockLabel,Cfg,XsiGraph) %% Continue the search
305 	  end
306      end;
307    #move{} ->
308      %% It's a move, we emend E, and continue the definition search
309      DST = ?RTL:move_dst(CC),
310      F = case SRC1 =:= DST orelse SRC2 =:= DST of
311	    true ->
312	      SRC = ?RTL:move_src(CC),
313	      emend(E,DST,SRC);
314	    _ ->
315	      E
316	  end,
317      check_definition(F,Rest,BlockLabel,Cfg,XsiGraph); %% Continue the search
318    #xsi_link{} ->
319      {_K,Xsi} = ?GRAPH:vertex(XsiGraph,CC#xsi_link.num),
320      C = Xsi#xsi.inst,
321      case check_match(C,E) of
322 	true -> %% There is a Xsi already with a computation of E!
323 	  %% fetch definition of C, and give it to E
324 	  {def_found,Xsi#xsi.def};
325 	_->
326 	  check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
327      end;
328    #phi{} ->
329      %% skip them. NOTE: Important to separate this case from the next one
330      check_definition(E,Rest,BlockLabel,Cfg,XsiGraph);
331    _ ->
332      %% Note: the function calls or some other instructions can change the pre-coloured registers
333      %% which are able to be redefined. This breaks of course the SSA form.
334      %% If there is a redefinition we can give bottom to the computation, and no xsi will be inserted.
335      %% (In some sens, the result of the computation is new at that point.)
336      PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2),
337
338      %%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2),
339      RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)), %% That means we cannot reuse the result held in this register...
340
341      case PreColouredTest orelse RegisterTest of
342 	true ->
343 	  {def_found,bottom};
344 	false ->
345          DC = ?RTL:defines(CC),
346          case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of
347            true ->
348              {def_found,bottom};
349            false ->
350              %% Orthogonal to E, we continue the search
351              check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
352          end
353      end
354  end.
355
356%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
357
358check_match(E, C) ->
359  OpE = ?RTL:alu_op(E),
360  OpC = ?RTL:alu_op(C),
361  case OpE =:= OpC of
362    false ->
363      false;
364    true ->
365      Src1E = ?RTL:alu_src1(E),
366      Src2E = ?RTL:alu_src2(E),
367      Src1C = ?RTL:alu_src1(C),
368      Src2C = ?RTL:alu_src2(C),
369      case Src1E =:= Src1C of
370 	true ->
371 	  Src2E =:= Src2C;
372 	false ->
373 	  Src1E =:= Src2C andalso Src2E =:= Src1C
374      end
375  end.
376
377%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
378
379expr_is_const(E) ->
380  ?RTL:is_imm(?RTL:alu_src1(E)) andalso ?RTL:is_imm(?RTL:alu_src2(E)).
381%%  is_number(?RTL:alu_src1(E)) andalso is_number(?RTL:alu_src2(E)).
382
383%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
384%% Must be an arithmetic operation, i.e. #alu{}
385emend(Expr, S, Var) ->
386  SRC1 = ?RTL:alu_src1(Expr),
387  NewExpr = case SRC1 =:= S of
388	      true  -> ?RTL:alu_src1_update(Expr,Var);
389	      false -> Expr
390	    end,
391  SRC2 = ?RTL:alu_src2(NewExpr),
392  case SRC2 =:= S of
393    true  -> ?RTL:alu_src2_update(NewExpr,Var);
394    false -> NewExpr
395  end.
396
397%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
398
399split_for_xsi([], Acc) ->
400  {[], Acc};  %  no_xsi_no_phi_found;
401split_for_xsi([I|Is] = Code, Acc) -> %% [I|Is] in backward order, Acc in order
402  case I of
403    #xsi_link{} ->
404      {lists:reverse(Code), Acc};
405    #phi{} ->
406      {lists:reverse(Code), Acc};
407    _ ->
408      split_for_xsi(Is, [I|Acc])
409  end.
410
411%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
412%% Phase 1.B : Search for operands
413%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
414
415find_operands(Cfg,XsiGraph,[],_Count) ->
416  {Cfg,XsiGraph};
417find_operands(Cfg,XsiGraph,ActiveList,Count) ->
418  {NewCfg,TempActiveList} = find_operands_for_active_list(Cfg,XsiGraph,ActiveList,[]),
419  NewActiveList = lists:reverse(TempActiveList),
420  ?pp_debug("~n################ Finding operands (iteration ~w): ~w have been introduced. Now ~w in total~n",
421 	   [Count+1, length(NewActiveList), length(?GRAPH:vertices(XsiGraph))]),
422  find_operands(NewCfg,XsiGraph,NewActiveList,Count+1).
423
424find_operands_for_active_list(Cfg,_XsiGraph,[],ActiveListAcc) ->
425  {Cfg,ActiveListAcc};
426find_operands_for_active_list(Cfg,XsiGraph,[K|Ks],ActiveListAcc) ->
427  {_Key,Xsi} = ?GRAPH:vertex(XsiGraph,K),
428  ?pp_debug("~n Inspecting operands of : ~n",[]),pp_xsi(Xsi),
429  Preds = ?CFG:pred(Cfg, Xsi#xsi.label),
430  {NewCfg,NewActiveListAcc}=determine_operands(Xsi,Preds,Cfg,K,XsiGraph,ActiveListAcc),
431  {_Key2,Xsi2} = ?GRAPH:vertex(XsiGraph,K),
432  ?pp_debug("~n ** Final Xsi: ~n",[]),pp_xsi(Xsi2),
433  ?pp_debug("~n #####################################################~n",[]),
434  find_operands_for_active_list(NewCfg,XsiGraph,Ks,NewActiveListAcc).
435
436determine_operands(_Xsi,[],Cfg,_K,_XsiGraph,ActiveAcc) ->
437  %% All operands have been determined.
438  %% The CFG is not updated, only the XsiGraph
439  {Cfg,ActiveAcc};
440determine_operands(Xsi,[P|Ps],Cfg,K,XsiGraph,ActiveAcc) ->
441  Label = Xsi#xsi.label,
442  ReverseCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,Label))),
443  VisitedInstructions = get_visited_instructions(Xsi,ReverseCode),
444  Res = determine_e_prime(Xsi#xsi.inst,VisitedInstructions,P,XsiGraph),
445  case Res of
446    operand_is_bottom ->
447      NewXsi = xsi_arg_update(Xsi,P,new_bottom()),
448      ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
449      determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
450    operand_is_const_expr ->
451      NewXsi = xsi_arg_update(Xsi,P,new_bottom()),
452      ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
453      determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
454    {sharing_operand,Op} ->
455      NewXsi = xsi_arg_update(Xsi,P,Op),
456      ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
457      determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
458    {revised_expression,E_prime} ->
459      ?pp_debug(" E' is determined : ",[]),pp_expr(E_prime),
460      ?pp_debug(" and going along the edge L~w~n",[P]),
461      %% Go along the edge P
462      RevCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))),
463      case check_one_operand(E_prime,RevCode,P,Cfg,K,XsiGraph) of
464 	{def_found,Def} ->
465 	  NewXsi = xsi_arg_update(Xsi,P,Def),
466          ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
467          determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
468
469 	{expr_found,ChildExpr} ->
470 	  NewXsi = xsi_arg_update(Xsi,P,ChildExpr),
471          ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
472          determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
473
474 	{expr_is_const, Op} ->
475          %% We detected that the expression is of the form: 'N op M'
476          %% where N and M are constant.
477 	  NewXsi = xsi_arg_update(Xsi,P,Op),
478          ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
479          determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
480
481 	{merge_point,XsiChild} ->
482 	  %% Update that Xsi, give its definition as Operand for the
483 	  %% search, and go on
484          XsiChildDef = XsiChild#xsi.def,
485 	  NewXsi = xsi_arg_update(Xsi,P,XsiChildDef),
486          ?GRAPH:add_vertex(XsiGraph,K,NewXsi),
487
488 	  KeyChild = XsiChildDef#temp.key,
489 	  XsiChildLink = #xsi_link{num=KeyChild},
490          ?GRAPH:add_vertex(XsiGraph,KeyChild,XsiChild),
491
492 	  %% Should not be the same block !!!!!!!
493 	  RCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,XsiChild#xsi.label))),
494 	  {BCode,ACode} = split_code_for_xsi(RCode,[]),
495
496 	  NewCode = BCode++[XsiChildLink|ACode],
497 	  NewBB = hipe_bb:mk_bb(NewCode),
498 	  NewCfg = ?CFG:bb_add(Cfg, XsiChild#xsi.label, NewBB),
499
500 	  ?pp_debug(" -- ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" causes insertion of: ~n",[]),pp_xsi(XsiChild),
501          ?pp_debug(" -- Adding an edge ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" -> ",[]),pp_arg(XsiChild#xsi.def),
502
503          %% Adding an edge...
504 	  %%?GRAPH:add_edge(XsiGraph,K,KeyChild,"family"),
505          ?GRAPH:add_edge(XsiGraph,K,KeyChild),
506 	  determine_operands(NewXsi,Ps,NewCfg,K,XsiGraph,[KeyChild|ActiveAcc])
507      end
508  end.
509
510determine_e_prime(Expr,VisitedInstructions,Pred,XsiGraph) ->
511  %% MUST FETCH FROM THE XSI TREE, since Xsis are not updated yet in the CFG
512  NewExpr = emend_with_phis(Expr,VisitedInstructions,Pred),
513  emend_with_processed_xsis(NewExpr,VisitedInstructions,Pred,XsiGraph).
514
515emend_with_phis(EmendedE, [], _) ->
516  EmendedE;
517emend_with_phis(E, [I|Rest], Pred) ->
518  case I of
519    #phi{} ->
520      Dst = ?RTL:phi_dst(I),
521      UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead?
522      case lists:member(Dst, UE) of
523  	false ->
524  	  emend_with_phis(E, Rest, Pred);
525  	true ->
526  	  NewE = emend(E, Dst, ?RTL:phi_arg(I,Pred)),
527  	  emend_with_phis(NewE, Rest, Pred)
528      end;
529    _ ->
530      emend_with_phis(E, Rest, Pred)
531  end.
532
533emend_with_processed_xsis(EmendedE, [], _, _) ->
534  {revised_expression,EmendedE};
535emend_with_processed_xsis(E, [I|Rest], Pred, XsiGraph) ->
536  case I of
537    #xsi_link{} ->
538      Key = I#xsi_link.num,
539      {_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
540      Def = Xsi#xsi.def,
541      UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead?
542      case lists:member(Def,UE) of
543  	false ->
544 	  CE = Xsi#xsi.inst,
545 	  case check_match(E,CE) of
546 	    true -> %% It's a computation of E!
547 	      case xsi_arg(Xsi,Pred) of
548 		undetermined_operand ->
549                  exit({?MODULE,check_operand_sharing,"######## Ôh Dear, we trusted Kostis !!!!!!!!! #############"});
550 		XsiOp ->
551 		  {sharing_operand,XsiOp} %% They share operands
552 	      end;
553 	    _->
554 	      emend_with_processed_xsis(E,Rest,Pred,XsiGraph)
555 	  end;
556  	true ->
557 	  A = xsi_arg(Xsi,Pred),
558 	  %% ?pp_debug(" ######### xsi_arg(I:~w,Pred:~w) = ~w~n",[I,Pred,A]),
559 	  case A of
560 	    #bottom{} ->
561 	      operand_is_bottom;
562 	    #const_expr{} ->
563 	      operand_is_const_expr;
564            #eop{} ->
565              NewE = emend(E,Def,A#eop.var),
566  	      emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph);
567            undetermined_operand ->
568              exit({?MODULE,emend_with_processed_xsis,"######## Ôh Dear, we trusted Kostis, again !!!!!!!!! #############"});
569 	    XsiOp ->
570 	      NewE = emend(E,Def,XsiOp),
571 	      emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph)
572 	  end
573      end;
574    _ ->
575      emend_with_processed_xsis(E,Rest,Pred,XsiGraph)
576  end.
577
578%% get_visited_instructions(Xsi,[]) ->
579%%   ?pp_debug("~nWe don't find this xsi with def ",[]),pp_arg(Xsi#xsi.def),?pp_debug(" in L~w : ",[Xsi#xsi.label]),
580%%   exit({?MODULE,no_such_xsi_in_block,"We didn't find that Xsi in the block"});
581get_visited_instructions(Xsi, [I|Is]) ->
582  case I of
583    #xsi_link{} ->
584      XsiDef = Xsi#xsi.def,
585      Key = XsiDef#temp.key,
586      case I#xsi_link.num =:= Key of
587 	true ->
588 	  Is;
589 	false ->
590 	  get_visited_instructions(Xsi, Is)
591      end;
592    _ ->
593      get_visited_instructions(Xsi, Is)
594  end.
595
596split_code_for_xsi([], Acc) ->
597  {[],Acc};
598split_code_for_xsi([I|Is] = Code, Acc) ->
599  case I of
600    #xsi_link{} ->
601      {lists:reverse(Code), Acc};
602    #phi{} ->
603      {lists:reverse(Code), Acc};
604    _ ->
605      split_code_for_xsi(Is, [I|Acc])
606  end.
607
608check_one_operand(E, [], BlockLabel, Cfg, XsiKey, XsiGraph) ->
609  %% No more instructions in that block
610  %% No definition found in that block
611  %% Search is previous blocks
612  Preds = ?CFG:pred(Cfg, BlockLabel),
613  case Preds of
614    [] ->
615      %% Entry Point
616      {def_found,new_bottom()};
617    [P] ->
618      %% One predecessor only, we just keep looking for a definition in that block
619      case expr_is_const(E) of
620        true ->
621          ?pp_debug("\n\n############## Wow expr is constant: ~w",[E]),
622          Var = ?RTL:mk_new_var(),
623          Value = eval_expr(E),
624          Op = #const_expr{var = Var, value = Value},
625          {expr_is_const, Op};
626        false ->
627          VisitedInstructions = lists:reverse(?BB:code(?CFG:bb(Cfg,P))),
628          check_one_operand(E, VisitedInstructions, P, Cfg, XsiKey, XsiGraph)
629      end;
630    _ ->
631      %% It's a merge point
632      case expr_is_const(E) of
633        true ->
634          ?pp_debug("\n\n############## Wow expr is constant at merge point: ~w",[E]),
635          Var = ?RTL:mk_new_var(),
636          Value = eval_expr(E),
637          Op = #const_expr{var = Var, value = Value},
638          {expr_is_const, Op};
639        false ->
640          Temp = new_temp(),
641          OpList = [#xsi_op{pred = X} || X <- Preds],
642          Xsi = #xsi{inst = E, def = Temp, label = BlockLabel, opList = OpList},
643          {merge_point, Xsi}
644      end
645  end;
646check_one_operand(E, [CC|Rest], BlockLabel, Cfg, XsiKey, XsiGraph) ->
647  SRC1 = ?RTL:alu_src1(E),
648  SRC2 = ?RTL:alu_src2(E),
649  %% C is the previous instruction
650  case CC of
651    #alu{} ->
652      exit({?MODULE,should_not_be_an_alu,
653	    {"Why the hell do we still have an alu???",CC}});
654    #xsi{} ->
655      exit({?MODULE,should_not_be_a_xsi,
656	    {"Why the hell do we still have a xsi???",CC}});
657    #pre_candidate{} ->
658      C = CC#pre_candidate.alu,
659      DST = ?RTL:alu_dst(C),
660      case DST =:= SRC1 orelse DST =:= SRC2 of
661 	true ->
662 	  %% Get the definition of C, since C is PRE-candidate AND has
663 	  %% been processed before
664 	  DEF = CC#pre_candidate.def,
665 	  case DEF of
666 	    bottom ->
667 	      %% Def(E)=bottom, STOP
668              %% No update of the XsiGraph
669 	      {def_found,new_bottom()};
670 	    _->
671 	      %% Simply emend
672 	      F = emend(E,DST,DEF),
673 	      ?pp_debug("~nEmendation : E= ",[]),pp_expr(E),?pp_debug(" ==> E'= ",[]),pp_expr(F),?pp_debug("~n",[]),
674 	      check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
675 	  end;
676 	false ->
677 	  case check_match(C,E) of
678 	    true -> %% It's a computation of E!
679 	      %% It should give DST and not Def
680              %% No update of the XsiGraph, cuz we use DST and not Def
681              %% The operand is therefore gonna be a real variable
682 	      {def_found,DST};
683 	    _->
684 	      %% Nothing to do with E
685 	      check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
686 	  end
687      end;
688    #move{} ->
689      %% It's a move, we emend E, and continue the definition search
690      DST = ?RTL:move_dst(CC),
691      case SRC1 =:= DST orelse SRC2 =:= DST of
692 	true ->
693 	  SRC = ?RTL:move_src(CC),
694 	  F = emend(E,DST,SRC),
695  	  check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); %% Continue the search
696  	_ ->
697 	  check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) %% Continue the search
698      end;
699    #xsi_link{} ->
700      Key = CC#xsi_link.num,
701      %% Is Key a family member of XsiDef ?
702      {_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
703      C = Xsi#xsi.inst,
704      case check_match(E,C) of
705        true -> %% There is a Xsi already with a computation of E!
706          %% fetch definition of C, and give it to E
707          %% Must update an edge in the XsiGraph, and here, we know it's a Temp
708          %% Note: this can create a loop (= a cycle of length 1)
709          ?pp_debug(" -- Found a cycle with match: Adding an edge t~w -> t~w",[XsiKey,Key]),
710          ?GRAPH:add_edge(XsiGraph,XsiKey,Key),
711          {def_found,Xsi#xsi.def};
712        _ ->
713          case ?GRAPH:get_path(XsiGraph,Key,XsiKey) of
714            false ->
715              %% Is it a loop back to itself???
716              case Key =:= XsiKey of
717                false ->
718                  check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph);
719                _ ->
720                  {expr_found,#eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key}}
721              end;
722            _ ->
723              %% Returning the expression instead of looping
724              %% And in case of no match
725              ExprOp = #eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key},
726              {expr_found,ExprOp}
727          end
728      end;
729    #phi{} -> %% skip them
730      check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph);
731    _ ->
732      PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2),
733
734      %%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2),
735      RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)),
736      case PreColouredTest orelse RegisterTest of
737 	true ->
738 	  {def_found,new_bottom()};
739 	_->
740 	  DC = ?RTL:defines(CC),
741 	  case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of
742 	    true ->
743 	      {def_found,new_bottom()};
744 	    _ ->
745 	      %% Orthogonal to E, we continue the search
746 	      check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
747 	  end
748      end
749  end.
750
751eval_expr(E) ->
752  ?pp_debug("~n Evaluating the result of ~w~n", [E]),
753  Op1 = ?RTL:alu_src1(E),
754  Op2 = ?RTL:alu_src2(E),
755  true = ?RTL:is_imm(Op1),
756  Val1 = ?RTL:imm_value(Op1),
757  true = ?RTL:is_imm(Op2),
758  Val2 = ?RTL:imm_value(Op2),
759  {Result, _Sign, _Zero, _Overflow, _Carry} = ?ARCH:eval_alu(?RTL:alu_op(E), Val1, Val2),
760  ?pp_debug("~n Result is then ~w~n", [Result]),
761  ?RTL:mk_imm(Result).
762
763%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
764%%%%%%%%%%%%%%%%%%%%%%%%%%  CREATTING CFGGRAPH  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
765%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
766
767create_cfggraph([],_Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,_XsiGraph) ->
768  ?pp_debug("~n~n ############# PostProcessing ~n~w~n",[LateEdges]),
769  post_process(LateEdges,CFGGraph),
770  ?pp_debug("~n~n ############# Factorizing ~n~w~n",[ToBeFactorizedAcc]),
771  factorize(ToBeFactorizedAcc,CFGGraph),
772  MPAcc;
773create_cfggraph([Label|Ls],Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph) ->
774  Preds = ?CFG:pred(Cfg, Label),
775  case Preds of
776    [] ->
777      exit({?MODULE,do_not_call_on_top,{"Why the hell do we call that function on the start label???",Label}});
778    [P] ->
779      Code = ?BB:code(?CFG:bb(Cfg, Label)),
780      Defs = get_defs_in_non_merge_block(Code, []),
781      ?pp_debug("~nAdding a vertex for ~w", [Label]),
782      Succs = ?CFG:succ(Cfg, Label),
783      NewToBeFactorizedAcc =
784	case Succs of
785	  [] -> %% Exit point
786	    ?GRAPH:add_vertex(CFGGraph, Label, #block{type = exit}),
787	    ToBeFactorizedAcc;
788	  _ -> %% Split point
789	    ?GRAPH:add_vertex(CFGGraph,Label,#block{type=not_mp,attributes={P,Succs}}),
790	    [Label|ToBeFactorizedAcc]
791	end,
792      ?pp_debug("~nAdding an edge ~w -> ~w (~w)",[P,Label,Defs]),
793      case ?GRAPH:add_edge(CFGGraph,P,Label,Defs) of
794        {error,Reason} ->
795          exit({?MODULE,forget_that_for_christs_sake_bingwen_please,{"Bad edge",Reason}});
796        _ ->
797          ok
798      end,
799      create_cfggraph(Ls,Cfg,CFGGraph,NewToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph);
800    _ -> %% Merge point
801      Code = ?BB:code(?CFG:bb(Cfg,Label)),
802      {Defs,Xsis,Maps,Uses} = get_info_in_merge_block(Code,XsiGraph,[],[],gb_trees:empty(),gb_trees:empty()),
803      Attributes = #mp{preds=Preds,xsis=Xsis,defs=Defs,maps=Maps,uses=Uses},
804      MergeBlock = #block{type=mp,attributes=Attributes},
805      ?pp_debug("~nAdding a vertex for ~w with Defs= ~w",[Label,Defs]),
806      ?GRAPH:add_vertex(CFGGraph,Label,MergeBlock),
807      %% Add edges
808      NewLateEdges = add_edges_for_mp(Preds,Label,LateEdges),
809      create_cfggraph(Ls,Cfg,CFGGraph,ToBeFactorizedAcc,[Label|MPAcc],NewLateEdges,XsiGraph)
810  end.
811
812get_defs_in_non_merge_block([], Acc) ->
813  ?SETS:from_list(Acc);
814get_defs_in_non_merge_block([Inst|Rest], Acc) ->
815  case Inst of
816    #pre_candidate{} ->
817      Def = Inst#pre_candidate.def,
818      case Def of
819        #temp{} ->
820          %%        {temp,Key,_Var} ->
821          %%          get_defs_in_non_merge_block(Rest,[Key|Acc]);
822          get_defs_in_non_merge_block(Rest, [Def#temp.key|Acc]);
823 	_-> %% Real variables or bottom
824 	  get_defs_in_non_merge_block(Rest, Acc)
825      end;
826    _  ->
827      get_defs_in_non_merge_block(Rest, Acc)
828  end.
829
830get_info_in_merge_block([],_XsiGraph,Defs,Xsis,Maps,Uses) ->
831  {?SETS:from_list(Defs),Xsis,Maps,Uses}; %% Xsis are in backward order
832get_info_in_merge_block([Inst|Rest],XsiGraph,Defs,Xsis,Maps,Uses) ->
833  case Inst of
834    #pre_candidate{} ->
835      Def = Inst#pre_candidate.def,
836      case Def of
837        #temp{} ->
838          get_info_in_merge_block(Rest,XsiGraph,[Def#temp.key|Defs],Xsis,Maps,Uses);
839 	_ ->
840          get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses)
841      end;
842    #xsi_link{} ->
843      Key = Inst#xsi_link.num,
844      {_Key,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
845      OpList = xsi_oplist(Xsi),
846      {NewMaps,NewUses} = add_map_and_uses(OpList,Key,Maps,Uses),
847      get_info_in_merge_block(Rest,XsiGraph,Defs,[Key|Xsis],NewMaps,NewUses);
848    _  ->
849      get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses)
850  end.
851
852add_edges_for_mp([], _Label, LateEdges) ->
853  LateEdges;
854add_edges_for_mp([P|Ps], Label, LateEdges) ->
855  add_edges_for_mp(Ps,Label,[{P,Label}|LateEdges]).
856
857%% Doesn't do anything so far
858add_map_and_uses([], _Key, Maps, Uses) ->
859  {Maps, Uses};
860add_map_and_uses([XsiOp|Ops], Key, Maps, Uses) ->
861  {NewMaps, NewUses} =
862    case XsiOp#xsi_op.op of
863      #bottom{} ->
864	Set = case gb_trees:lookup(XsiOp, Maps) of
865		{value, V} ->
866		  ?SETS:add_element(Key, V);
867		none ->
868		  ?SETS:from_list([Key])
869	      end,
870	{gb_trees:enter(XsiOp, Set, Maps), Uses};
871      #temp{} ->
872	Set = case gb_trees:lookup(XsiOp, Maps) of
873		{value, V} ->
874		  ?SETS:add_element(Key, V);
875		none ->
876		  ?SETS:from_list([Key])
877	      end,
878	Pred = XsiOp#xsi_op.pred,
879	OOP = XsiOp#xsi_op.op,
880	SSet = case gb_trees:lookup(Pred, Uses) of
881		 {value, VV} ->
882		   ?SETS:add_element(OOP#temp.key, VV);
883		 none ->
884		   ?SETS:from_list([OOP#temp.key])
885	       end,
886	{gb_trees:enter(XsiOp, Set, Maps), gb_trees:enter(Pred, SSet, Uses)};
887      #eop{} ->
888	Set = case gb_trees:lookup(XsiOp, Maps) of
889		{value, V} ->
890		  ?SETS:add_element(Key, V);
891		none ->
892		  ?SETS:from_list([Key])
893	      end,
894	Pred = XsiOp#xsi_op.pred,
895	Op = XsiOp#xsi_op.op,
896	SSet = case gb_trees:lookup(Pred, Uses) of
897		 {value, VV} ->
898		   ?SETS:add_element(Op#eop.stopped_by, VV);
899		 none ->
900		   ?SETS:from_list([Op#eop.stopped_by])
901	       end,
902	{gb_trees:enter(XsiOp, Set, Maps), gb_trees:enter(Pred, SSet, Uses)};
903      _->
904	{Maps, Uses}
905    end,
906  add_map_and_uses(Ops, Key, NewMaps, NewUses).
907
908post_process([], _CFGGraph) -> ok;
909post_process([E|Es], CFGGraph) ->
910  {Pred,Label} = E,
911  {_PP,Block} = ?GRAPH:vertex(CFGGraph,Label),
912  Att = Block#block.attributes,
913  Uses = Att#mp.uses,
914  SetToAdd = case gb_trees:lookup(Pred,Uses) of
915               {value, Set} ->
916                 Set;
917               none ->
918                 ?SETS:new()
919             end,
920  %% ?pp_debug("~nAdding an edge ~w -> ~w (~w)",[Pred,Label,SetToAdd]),
921  ?GRAPH:add_edge(CFGGraph, Pred, Label, SetToAdd),
922  post_process(Es, CFGGraph).
923
924factorize([], _CFGGraph) -> ok;
925factorize([P|Ps], CFGGraph) ->
926  [OE|OEs] = ?GRAPH:out_edges(CFGGraph,P),
927  %% ?pp_debug("~nIn_degrees ~w : ~w",[P,?GRAPH:in_degree(CFGGraph,P)]),
928  [InEdge] = ?GRAPH:in_edges(CFGGraph,P),
929  {E,V1,V2,Label} = ?GRAPH:edge(CFGGraph,InEdge),
930  {_OEE,_OEV1,_OEV2,LOE} = ?GRAPH:edge(CFGGraph,OE),
931  List = shoot_info_upwards(OEs,LOE,CFGGraph),
932  NewLabel = ?SETS:union(Label,List),
933  ?GRAPH:add_edge(CFGGraph,E,V1,V2,NewLabel),
934  factorize(Ps, CFGGraph).
935
936shoot_info_upwards([], Acc, _CFGGraph) -> Acc;
937shoot_info_upwards([E|Es], Acc, CFGGraph) ->
938  {_E,_V1,_V2,Set} = ?GRAPH:edge(CFGGraph,E),
939  NewAcc = ?SETS:intersection(Acc, Set),
940  case ?SETS:size(NewAcc) of
941    0 -> NewAcc;
942    _ -> shoot_info_upwards(Es,NewAcc,CFGGraph)
943  end.
944
945%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
946%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  DOWNSAFETY   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
947%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
948
949perform_downsafety([], _G, _XsiG) ->
950  ok;
951perform_downsafety([MP|MPs], G, XG) ->
952  {V,Block} = ?GRAPH:vertex(G, MP),
953  NDS = ?SETS:new(),
954  Att = Block#block.attributes,
955  Maps = Att#mp.maps,
956  Defs = Att#mp.defs,
957  OutEdges = ?GRAPH:out_edges(G, MP),
958  %% ?pp_debug("~n Inspection Maps : ~w",[Maps]),
959  NewNDS = parse_keys(gb_trees:keys(Maps),Maps,OutEdges,G,Defs,NDS,XG),
960  NewAtt = Att#mp{ndsSet = NewNDS},
961  ?GRAPH:add_vertex(G, V, Block#block{attributes = NewAtt}),
962  ?pp_debug("~n Not Downsafe at L~w: ~w", [V, NewNDS]),
963  %%io:format(standard_io,"~n Not Downsafe at L~w: ~w",[V,NewNDS]),
964  perform_downsafety(MPs, G, XG).
965
966parse_keys([], _Maps, _OutEdges, _G, _Defs, NDS, _XsiG) ->
967  NDS;
968parse_keys([M|Ms], Maps, OutEdges, G, Defs, NDS, XsiG) ->
969  KillerSet = gb_trees:get(M,Maps),
970  %% ?pp_debug("~n Inspection ~w -> ~w",[M,KillerSet]),
971  TempSet = ?SETS:intersection(KillerSet,Defs),
972  NewNDS = case ?SETS:size(TempSet) of
973	     0 -> getNDS(M,KillerSet,NDS,OutEdges,G,XsiG);
974	     _ ->
975	       %% One Xsi which has M as operand has killed it
976	       %% M is then Downsafe
977	       %% and is not added to the NotDownsafeSet (NDS)
978	       NDS
979	   end,
980  parse_keys(Ms, Maps, OutEdges, G, Defs, NewNDS, XsiG).
981
982getNDS(_M, _KillerSet, NDS, [], _G, _XsiG) ->
983  NDS;
984getNDS(M, KillerSet, NDS, [E|Es], G, XsiG) ->
985  {_EE,_V1,_V2,Label} = ?GRAPH:edge(G, E),
986  Set = ?SETS:intersection(KillerSet, Label),
987  %% ?pp_debug("~n ######## Intersection between KillerSet: ~w and Label: ~w",[KillerSet,Label]),
988  %% ?pp_debug("~n ######## ~w",[Set]),
989  case ?SETS:size(Set) of
990    0 ->
991      %% M is not downsafe
992      ?SETS:add_element(M, NDS);
993    _ ->
994      %% Try the other edges
995      getNDS(M, KillerSet, NDS, Es, G, XsiG)
996  end.
997
998%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
999%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  WILL BE AVAILABLE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1000%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1001
1002perform_will_be_available(XsiGraph,CFGGraph,Options) ->
1003  Keys = ?GRAPH:vertices(XsiGraph),
1004  ?pp_debug("~n############ Can Be Available ##########~n",[]),
1005  ?option_time(perform_can_be_available(Keys,XsiGraph,CFGGraph),"RTL A-SSAPRE WillBeAvailable - Compute CanBeAvailable",Options),
1006  ?pp_debug("~n############ Later ##########~n",[]),
1007  ?option_time(perform_later(Keys,XsiGraph),"RTL A-SSAPRE WillBeAvailable - Compute Later",Options).
1008
1009perform_can_be_available([],_XsiGraph,_CFGGraph) -> ok;
1010perform_can_be_available([Key|Keys],XsiGraph,CFGGraph) ->
1011  {V,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
1012  case Xsi#xsi.cba of
1013    undefined ->
1014      {_VV,Block} = ?GRAPH:vertex(CFGGraph,Xsi#xsi.label),
1015      Att = Block#block.attributes,
1016      NDS = Att#mp.ndsSet,
1017      OpList = ?SETS:from_list(xsi_oplist(Xsi)),
1018      Set = ?SETS:intersection(NDS,OpList),
1019      case ?SETS:size(Set) of
1020        0 ->
1021          ?GRAPH:add_vertex(XsiGraph, V, Xsi#xsi{cba = true}),
1022          perform_can_be_available(Keys, XsiGraph, CFGGraph);
1023        _ ->
1024          LIST = [X || #temp{key=X} <- ?SETS:to_list(Set)],
1025          case LIST of
1026            [] ->
1027              ?GRAPH:add_vertex(XsiGraph, V, Xsi#xsi{cba = false}),
1028              ImmediateParents = ?GRAPH:in_neighbours(XsiGraph, Key),
1029              propagate_cba(ImmediateParents,XsiGraph,Xsi#xsi.def,CFGGraph);
1030            _ ->
1031              ok
1032          end,
1033          perform_can_be_available(Keys, XsiGraph, CFGGraph)
1034      end;
1035    _ -> %% True or False => recurse
1036      perform_can_be_available(Keys, XsiGraph, CFGGraph)
1037  end.
1038
1039propagate_cba([],_XG,_Def,_CFGG) -> ok;
1040propagate_cba([IPX|IPXs],XsiGraph,XsiDef,CFGGraph) ->
1041  {V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX),
1042  {_VV,Block} = ?GRAPH:vertex(CFGGraph,IPXsi#xsi.label),
1043  Att = Block#block.attributes,
1044  NDS = Att#mp.ndsSet,
1045  List = ?SETS:to_list(?SETS:intersection(NDS,?SETS:from_list(xsi_oplist(IPXsi)))),
1046  case IPXsi#xsi.cba of
1047    false -> ok;
1048    _ ->
1049      case lists:keymember(XsiDef, #xsi_op.op, List) of
1050        true ->
1051          ?GRAPH:add_vertex(XsiGraph, V, IPXsi#xsi{cba = false}),
1052          ImmediateParents = ?GRAPH:in_neighbours(XsiGraph, IPX),
1053          propagate_cba(ImmediateParents,XsiGraph,IPXsi#xsi.def,CFGGraph);
1054        _ ->
1055          ok
1056      end
1057  end,
1058  propagate_cba(IPXs,XsiGraph,XsiDef,CFGGraph).
1059
1060perform_later([], _XsiGraph) -> ok;
1061perform_later([Key|Keys], XsiGraph) ->
1062  {V, Xsi} = ?GRAPH:vertex(XsiGraph, Key),
1063  %% ?pp_debug("~n DEBUG : inspecting later of ~w (~w)~n",[Key,Xsi#xsi.later]),
1064  case Xsi#xsi.later of
1065    undefined ->
1066      OpList = xsi_oplist(Xsi),
1067      case parse_ops(OpList,fangpi) of  %% It means "fart" in chinese :D
1068        has_temp ->
1069          perform_later(Keys,XsiGraph);
1070        has_real ->
1071          case Xsi#xsi.cba of
1072            true ->
1073              ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true});
1074            undefined ->
1075              ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true});
1076            _ ->
1077              ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=false})
1078          end,
1079          AllParents = digraph_utils:reaching([Key], XsiGraph),
1080          ?pp_debug("~nPropagating to all parents of t~w: ~w",[Key,AllParents]),
1081          propagate_later(AllParents,XsiGraph),
1082          perform_later(Keys,XsiGraph);
1083        _ -> %% Just contains bottoms and/or expressions
1084          ?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=true}),
1085          perform_later(Keys,XsiGraph)
1086      end;
1087    _ -> %% True or False => recurse
1088      perform_later(Keys,XsiGraph)
1089  end.
1090
1091propagate_later([], _XG) -> ok;
1092propagate_later([IPX|IPXs], XsiGraph) ->
1093  {V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX),
1094  case IPXsi#xsi.later of
1095    false ->
1096      ?pp_debug("~nThrough propagation, later of t~w is already reset",[IPX]),
1097      propagate_later(IPXs,XsiGraph);
1098    _ ->
1099      ?pp_debug("~nThrough propagation, resetting later of t~w",[IPX]),
1100      case IPXsi#xsi.cba of
1101        true ->
1102          ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true});
1103        undefined ->
1104          ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true});
1105        _ ->
1106          ?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=false})
1107      end,
1108      propagate_later(IPXs,XsiGraph)
1109  end.
1110
1111parse_ops([], Res) ->
1112  Res;
1113parse_ops([Op|Ops], Res) ->
1114  case Op#xsi_op.op of
1115    #temp{} ->
1116      NewRes = has_temp,
1117      parse_ops(Ops,NewRes);
1118    #bottom{} ->
1119      parse_ops(Ops,Res);
1120    #eop{} ->
1121      parse_ops(Ops,Res);
1122    _ ->
1123      has_real
1124  end.
1125
1126%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1127%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  CODE MOTION  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1128%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1129
1130perform_code_motion([], Cfg, _XsiG) ->
1131  Cfg;
1132perform_code_motion([L|Labels], Cfg, XsiG) ->
1133  Code=?BB:code(?CFG:bb(Cfg,L)),
1134  ?pp_debug("~n################  Code Motion in L~w~n",[L]),
1135  ?pp_debug("~nCode to move ~n",[]),
1136  pp_instrs(Code,XsiG),
1137  NewCfg = code_motion_in_block(L,Code,Cfg,XsiG,[],gb_trees:empty()),
1138  ?pp_debug("~n################  Code Motion successful in L~w~n",[L]),
1139  perform_code_motion(Labels,NewCfg,XsiG).
1140
1141code_motion_in_block(Label,[],Cfg,_XsiG,Visited,InsertionsAcc) ->
1142  InsertionsAlong = gb_trees:keys(InsertionsAcc),
1143  Code = lists:reverse(Visited),
1144  NewBB = ?BB:mk_bb(Code),
1145  Cfg2 = ?CFG:bb_add(Cfg,Label,NewBB),
1146  %% Must come after the bb_add, since redirect will update the Phis too...
1147  Cfg3 = make_insertions(Label,InsertionsAlong,InsertionsAcc,Cfg2),
1148  %% ?pp_debug("~nChecking the Code at L~w:~n~p",[Label,?BB:code(?CFG:bb(Cfg3,Label))]),
1149  Cfg3;
1150code_motion_in_block(L,[Inst|Insts],Cfg,XsiG,Visited,InsertionsAcc) ->
1151  ?pp_debug("~nInspecting Inst : ~n",[]),pp_instr(Inst,XsiG),
1152  case Inst of
1153    #pre_candidate{} ->
1154      Def = Inst#pre_candidate.def,
1155      Alu = Inst#pre_candidate.alu,
1156      InstToAdd =
1157	case Def of
1158	  bottom ->
1159	    Alu;
1160	  #temp{} ->
1161	    Key = Def#temp.key,
1162	    {_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
1163	    case Xsi#xsi.wba of
1164	      true ->
1165		%% Turn into a move
1166		Dst = ?RTL:alu_dst(Alu),
1167		Move = ?RTL:mk_move(Dst,Def#temp.var),
1168		pp_instr(Inst#pre_candidate.alu,nil), ?pp_debug(" ==> ",[]), pp_instr(Move,nil),
1169		%% Counting redundancies
1170		redundancy_add(),
1171		Move;
1172	      _ ->
1173		Alu
1174	    end;
1175	  _ -> %% Def is a real variable
1176	    %% Turn into a move
1177	    Dst = ?RTL:alu_dst(Alu),
1178	    Move = ?RTL:mk_move(Dst,Def),
1179	    pp_instr(Alu,nil), ?pp_debug(" ==> ",[]), pp_instr(Move,nil),
1180	    %% Counting redundancies
1181	    redundancy_add(),
1182	    Move
1183	end,
1184      code_motion_in_block(L,Insts,Cfg,XsiG,[InstToAdd|Visited],InsertionsAcc);
1185    #xsi_link{} ->
1186      Key = Inst#xsi_link.num,
1187      {_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
1188      case Xsi#xsi.wba of
1189        true ->
1190          %% Xsi is a WBA, it might trigger insertions
1191          OpList = xsi_oplist(Xsi),
1192          ?pp_debug(" This Xsi is a 'Will be available'",[]),
1193          %% Cleaning the instruction
1194          Expr = prepare_inst(Xsi#xsi.inst),
1195          {NewOpList,NewInsertionsAcc} = get_insertions(OpList,[],InsertionsAcc,Visited,Expr,XsiG),
1196          %% Making Xsi a Phi with Oplist
1197          PhiOpList = [{Pred,Var} || #xsi_op{pred=Pred,op=Var} <- NewOpList],
1198          Def = Xsi#xsi.def,
1199          Phi = ?RTL:phi_arglist_update(?RTL:mk_phi(Def#temp.var),PhiOpList),
1200          ?pp_debug("~n Xsi is turned into Phi : ~w",[Phi]),
1201          code_motion_in_block(L,Insts,Cfg,XsiG,[Phi|Visited],NewInsertionsAcc);
1202        _ ->
1203          ?pp_debug(" This Xsi is not a 'Will be available'",[]),
1204          code_motion_in_block(L,Insts,Cfg,XsiG,Visited,InsertionsAcc)
1205      end;
1206%%     phi ->
1207%%       code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc);
1208    _ ->
1209      %% Other instructions.... Phis too
1210      code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc)
1211  end.
1212
1213prepare_inst(Expr) ->
1214  S1 = ?RTL:alu_src1(Expr),
1215  S2 = ?RTL:alu_src2(Expr),
1216  NewInst = case S1 of
1217	      #temp{} -> ?RTL:alu_src1_update(Expr,S1#temp.var);
1218	      _ -> Expr
1219	    end,
1220  case S2 of
1221    #temp{} -> ?RTL:alu_src2_update(NewInst,S2#temp.var);
1222    _ -> NewInst
1223  end.
1224
1225get_insertions([],OpAcc,InsertionsAcc,_Visited,_Expr,_XsiG) ->
1226  {OpAcc,InsertionsAcc};
1227get_insertions([XsiOp|Ops],OpAcc,InsertionsAcc,Visited,Expr,XsiG) ->
1228  Pred = XsiOp#xsi_op.pred,
1229  Op = XsiOp#xsi_op.op,
1230  {Dst, NewInsertionsAcc} =
1231    case Op of
1232      #bottom{} ->
1233	case gb_trees:lookup(Pred,InsertionsAcc) of
1234	  {value,Insertion} ->
1235	    From = Insertion#insertion.from,
1236	    case lists:keyfind(Op, 1, From) of
1237	      false ->
1238		?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
1239		D = Op#bottom.var,
1240		Expr2 = ?RTL:alu_dst_update(Expr,D),
1241		Inst = manufacture_computation(Pred,Expr2,Visited),
1242		Code = Insertion#insertion.code,
1243		NewInsertion = Insertion#insertion{from=[{Op,D}|From],code=[Inst|Code]},
1244		{D, gb_trees:update(Pred, NewInsertion, InsertionsAcc)};
1245	      {_, Val} ->
1246		?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
1247		{Val, InsertionsAcc}
1248	    end;
1249	  none ->
1250	    ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
1251	    D = Op#bottom.var,
1252	    Expr2 = ?RTL:alu_dst_update(Expr, D),
1253	    Inst = manufacture_computation(Pred,Expr2,Visited),
1254	    NewInsertion = #insertion{from=[{Op,D}],code=[Inst]},
1255	    {D, gb_trees:insert(Pred,NewInsertion, InsertionsAcc)}
1256	end;
1257      #const_expr{} ->
1258	case gb_trees:lookup(Pred,InsertionsAcc) of
1259	  {value,Insertion} ->
1260	    From = Insertion#insertion.from,
1261	    case lists:keyfind(Op, 1, From) of
1262	      false ->
1263		?pp_debug("~nThere have been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
1264		D = Op#const_expr.var,
1265		Val = Op#const_expr.value,
1266		Inst = ?RTL:mk_move(D, Val),
1267		Code = Insertion#insertion.code,
1268		NewInsertion = Insertion#insertion{from=[{Op,D}|From],code=[Inst|Code]},
1269		{D, gb_trees:update(Pred,NewInsertion,InsertionsAcc)};
1270	      {_, Val} ->
1271		?pp_debug("~nThere have been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
1272		{Val, InsertionsAcc}
1273	    end;
1274	  none ->
1275	    ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
1276	    D = Op#const_expr.var,
1277	    Val = Op#const_expr.value,
1278	    Inst = ?RTL:mk_move(D, Val),
1279	    NewInsertion = #insertion{from=[{Op,D}],code=[Inst]},
1280	    {D, gb_trees:insert(Pred,NewInsertion, InsertionsAcc)}
1281	end;
1282      #eop{} ->
1283	%% We treat expressions like bottoms
1284	%% The value must be recomputed, and therefore not available...
1285	case gb_trees:lookup(Pred,InsertionsAcc) of
1286	  {value,Insertion} ->
1287	    From = Insertion#insertion.from,
1288	    case lists:keyfind(Op, 1, From) of
1289	      false ->
1290		?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
1291		D = Op#eop.var,
1292		Expr2 = ?RTL:alu_dst_update(Expr, D),
1293		Inst = manufacture_computation(Pred,Expr2,Visited),
1294		Code = Insertion#insertion.code,
1295		NewInsertion = Insertion#insertion{from=[{Op,D}|From],code=[Inst|Code]},
1296		{D, gb_trees:update(Pred,NewInsertion, InsertionsAcc)};
1297	      {_, Val} ->
1298		?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
1299		{Val, InsertionsAcc}
1300	    end;
1301	  none ->
1302	    ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
1303	    D = Op#eop.var,
1304	    Expr2 = ?RTL:alu_dst_update(Expr, D),
1305	    Inst = manufacture_computation(Pred,Expr2,Visited),
1306	    NewInsertion = #insertion{from=[{Op,D}],code=[Inst]},
1307	    {D, gb_trees:insert(Pred, NewInsertion, InsertionsAcc)}
1308	end;
1309      #temp{} ->
1310	case gb_trees:lookup(Pred,InsertionsAcc) of
1311	  {value,Insertion} ->
1312	    From = Insertion#insertion.from,
1313	    case lists:keyfind(Op, 1, From) of
1314	      false ->
1315		?pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
1316		Key = Op#temp.key,
1317		{_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
1318		case Xsi#xsi.wba of
1319		  true ->
1320		    ?pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]),
1321		    {Op#temp.var, InsertionsAcc};
1322		  _ ->
1323		    ?pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]),
1324		    D = ?RTL:mk_new_var(),
1325		    Expr2 = ?RTL:alu_dst_update(Expr, D),
1326		    Inst = manufacture_computation(Pred,Expr2,Visited),
1327		    Code = Insertion#insertion.code,
1328		    NewInsertion = Insertion#insertion{from=[{Op,D}|From],code=[Inst|Code]},
1329		    {D, gb_trees:update(Pred, NewInsertion, InsertionsAcc)}
1330		end;
1331	      {_, Val} ->
1332		?pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too (Op=~w)",[Pred,Op]),
1333		?pp_debug("~nThis means, this temp is a WBA Xsi's definition",[]),
1334		{Val, InsertionsAcc}
1335	    end;
1336	  none ->
1337	    ?pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course | Op=",[Pred]),pp_arg(Op),
1338	    Key = Op#temp.key,
1339	    {_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
1340	    case Xsi#xsi.wba of
1341	      true ->
1342		?pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]),
1343		{Op#temp.var, InsertionsAcc};
1344	      _ ->
1345		?pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]),
1346		D = ?RTL:mk_new_var(),
1347		Expr2 = ?RTL:alu_dst_update(Expr, D),
1348		Inst = manufacture_computation(Pred,Expr2,Visited),
1349		NewInsertion = #insertion{from=[{Op,D}],code=[Inst]},
1350	        {D, gb_trees:insert(Pred, NewInsertion, InsertionsAcc)}
1351	    end
1352	end;
1353      _ ->
1354	?pp_debug("~nThe operand (Op=",[]),pp_arg(Op),?pp_debug(") is a real variable, no need for insertion along L~w",[Pred]),
1355	{Op, InsertionsAcc}
1356    end,
1357  NewXsiOp = XsiOp#xsi_op{op=Dst},
1358  get_insertions(Ops, [NewXsiOp|OpAcc], NewInsertionsAcc, Visited, Expr, XsiG).
1359
1360manufacture_computation(_Pred, Expr, []) ->
1361  ?pp_debug("~n Manufactured computation : ~w", [Expr]),
1362  Expr;
1363manufacture_computation(Pred, Expr, [I|Rest]) ->
1364  %% ?pp_debug("~n Expr = ~w",[Expr]),
1365  SRC1 = ?RTL:alu_src1(Expr),
1366  SRC2 = ?RTL:alu_src2(Expr),
1367  case I of
1368    #xsi_link{} ->
1369      exit({?MODULE,should_not_be_a_xsi_link,{"Why the hell do we still have a xsi link???",I}});
1370    #xsi{} ->
1371      exit({?MODULE,should_not_be_a_xsi,{"Why the hell do we still have a xsi ???",I}});
1372    #phi{} ->
1373      DST = ?RTL:phi_dst(I),
1374      Arg = ?RTL:phi_arg(I,Pred),
1375      NewInst = case DST =:= SRC1 of
1376  	          true -> ?RTL:alu_src1_update(Expr,Arg);
1377  	          false -> Expr
1378                end,
1379      NewExpr = case DST =:= SRC2 of
1380                  true -> ?RTL:alu_src2_update(NewInst,Arg);
1381                  false -> NewInst
1382                end,
1383      manufacture_computation(Pred,NewExpr,Rest)
1384  end.
1385
1386make_insertions(_L, [], _ITree, Cfg) ->
1387  Cfg;
1388make_insertions(L, [OldPred|Is], ITree, Cfg) ->
1389  NewPred      = ?RTL:label_name(?RTL:mk_new_label()),
1390  I            = gb_trees:get(OldPred, ITree),
1391  CodeToInsert = lists:reverse([?RTL:mk_goto(L)|I#insertion.code]),
1392  BBToInsert   = ?BB:mk_bb(CodeToInsert),
1393  NewCfg       = ?CFG:bb_insert_between(Cfg, NewPred, BBToInsert, OldPred, L),
1394  make_insertions(L, Is, ITree, NewCfg).
1395
1396%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1397%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  XSI INTERFACE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1398%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1399
1400xsi_oplist(#xsi{opList=OpList}) ->
1401  case OpList of undefined -> [] ; _ -> OpList end.
1402xsi_arg(Xsi, Pred) ->
1403  case lists:keyfind(Pred, #xsi_op.pred, xsi_oplist(Xsi)) of
1404    false ->
1405      undetermined_operand;
1406    R ->
1407      R#xsi_op.op
1408  end.
1409xsi_arg_update(Xsi, Pred, Op) ->
1410  NewOpList = lists:keyreplace(Pred, #xsi_op.pred, xsi_oplist(Xsi),
1411			       #xsi_op{pred=Pred,op=Op}),
1412  Xsi#xsi{opList=NewOpList}.
1413
1414%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1415%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PRETTY-PRINTING %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1416%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1417
1418-ifndef(SSAPRE_DEBUG).
1419
1420%%pp_cfg(Cfg,_) -> ?CFG:pp(Cfg).
1421pp_cfg(_,_) -> ok.
1422pp_instr(_,_) -> ok.
1423pp_instrs(_,_) -> ok.
1424pp_expr(_) -> ok.
1425pp_xsi(_) -> ok.
1426pp_arg(_) -> ok.
1427pp_xsigraph(_) -> ok.
1428pp_cfggraph(_) -> ok.
1429%% pp_xsigraph(G) ->
1430%%   Vertices = lists:sort(?GRAPH:vertices(G)),
1431%%   io:format(standard_io, "Size of the Xsi Graph: ~w", [length(Vertices)]).
1432%% pp_cfggraph(G) ->
1433%%   Vertices = lists:sort(?GRAPH:vertices(G)),
1434%%   io:format(standard_io, "Size of the CFG Graph: ~w", [length(Vertices)]).
1435
1436-else.
1437
1438pp_cfg(Cfg, Graph) ->
1439  Labels = ?CFG:preorder(Cfg),
1440  pp_blocks(Labels, Cfg, Graph).
1441
1442pp_blocks([], _, _) ->
1443  ok;
1444pp_blocks([L|Ls], Cfg, Graph) ->
1445  Code = hipe_bb:code(?CFG:bb(Cfg,L)),
1446  io:format(standard_io,"~n########## Label L~w~n", [L]),
1447  pp_instrs(Code, Graph),
1448  pp_blocks(Ls, Cfg, Graph).
1449
1450pp_instrs([], _) ->
1451  ok;
1452pp_instrs([I|Is], Graph) ->
1453  pp_instr(I, Graph),
1454  pp_instrs(Is, Graph).
1455
1456pp_xsi_link(Key, Graph) ->
1457  {_Key,Xsi} = ?GRAPH:vertex(Graph, Key),
1458  pp_xsi(Xsi).
1459
1460pp_xsi(Xsi) ->
1461  io:format(standard_io, "    [L~w] ", [Xsi#xsi.label]),
1462  io:format(standard_io, "[", []), pp_expr(Xsi#xsi.inst),
1463  io:format(standard_io, "] Xsi(", []), pp_xsi_args(xsi_oplist(Xsi)),
1464  io:format(standard_io, ") (", []), pp_xsi_def(Xsi#xsi.def),
1465  io:format(standard_io, ") cba=~w, later=~w | wba=~w~n", [Xsi#xsi.cba,Xsi#xsi.later,Xsi#xsi.wba]).
1466
1467pp_instr(I, Graph) ->
1468  case I of
1469    #alu{} ->
1470      io:format(standard_io, "    ", []),
1471      pp_arg(?RTL:alu_dst(I)),
1472      io:format(standard_io, " <- ", []),
1473      pp_expr(I),
1474      io:format(standard_io, "~n", []);
1475    _ ->
1476      try ?RTL:pp_instr(standard_io, I)
1477      catch _:_ ->
1478 	case I of
1479 	  #pre_candidate{} ->
1480 	    pp_pre(I);
1481 	  #xsi{} ->
1482 	    pp_xsi(I);
1483 	  #xsi_link{} ->
1484 	    pp_xsi_link(I#xsi_link.num, Graph);
1485 	  _->
1486 	    io:format(standard_io,"*** ~w ***~n", [I])
1487 	end
1488      end
1489  end.
1490
1491pp_pre(I) ->
1492  A = I#pre_candidate.alu,
1493  io:format(standard_io, "    ", []),
1494  pp_arg(?RTL:alu_dst(A)),
1495  io:format(standard_io, " <- ", []),pp_expr(A),
1496  io:format(standard_io, " [ ", []),pp_arg(I#pre_candidate.def),
1497  %%io:format(standard_io, "~w", [I#pre_candidate.def]),
1498  io:format(standard_io, " ]~n",[]).
1499
1500pp_expr(I) ->
1501  pp_arg(?RTL:alu_dst(I)),
1502  io:format(standard_io, " <- ", []),
1503  pp_arg(?RTL:alu_src1(I)),
1504  io:format(standard_io, " ~w ", [?RTL:alu_op(I)]),
1505  pp_arg(?RTL:alu_src2(I)).
1506
1507pp_arg(Arg) ->
1508  case Arg of
1509    bottom ->
1510      io:format(standard_io, "_|_", []);
1511    #bottom{} ->
1512      io:format(standard_io, "_|_:~w (", [Arg#bottom.key]),pp_arg(Arg#bottom.var),io:format(standard_io,")",[]);
1513    #temp{} ->
1514      pp_xsi_def(Arg);
1515    #eop{} ->
1516      io:format(standard_io,"#",[]),pp_expr(Arg#eop.expr),io:format(standard_io,"(",[]),pp_arg(Arg#eop.var),io:format(standard_io,")#",[]);
1517    #const_expr{} ->
1518      io:format(standard_io,"*",[]),pp_arg(Arg#const_expr.var),io:format(standard_io," -> ",[]),pp_arg(Arg#const_expr.value),io:format(standard_io,"*",[]);
1519    undefined ->
1520      io:format(standard_io, "...", []); %%"undefined", []);
1521    _->
1522      case Arg of
1523        #alu{} ->
1524          pp_expr(Arg);
1525        _->
1526          ?RTL:pp_arg(standard_io, Arg)
1527      end
1528  end.
1529
1530pp_args([]) ->
1531  ok;
1532pp_args(undefined) ->
1533  io:format(standard_io, "...,...,...", []);
1534pp_args([A]) ->
1535  pp_arg(A);
1536pp_args([A|As]) ->
1537  pp_arg(A),
1538  io:format(standard_io, ", ", []),
1539  pp_args(As).
1540
1541pp_xsi_args([]) -> ok;
1542pp_xsi_args([XsiOp]) ->
1543  io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]),
1544  pp_arg(XsiOp#xsi_op.op),
1545  io:format(standard_io, "}", []);
1546pp_xsi_args([XsiOp|Args]) ->
1547  io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]),
1548  pp_arg(XsiOp#xsi_op.op),
1549  io:format(standard_io, "}, ", []),
1550  pp_xsi_args(Args);
1551pp_xsi_args(Args) ->
1552  pp_args(Args).
1553
1554pp_xsi_def(Arg) ->
1555  D = Arg#temp.key,
1556  V = Arg#temp.var,
1557  io:format(standard_io, "t~w (", [D]),pp_arg(V),io:format(standard_io,")",[]).
1558
1559pp_cfggraph(G) ->
1560  Vertices = lists:sort(?GRAPH:vertices(G)),
1561  io:format(standard_io, "Size of the CFG Graph: ~w ~n", [length(Vertices)]),
1562  pp_cfgvertex(Vertices, G).
1563
1564pp_xsigraph(G) ->
1565  Vertices = lists:sort(?GRAPH:vertices(G)),
1566  io:format(standard_io, "Size of the Xsi Graph: ~w ~n", [length(Vertices)]),
1567  pp_xsivertex(Vertices,G).
1568
1569pp_xsivertex([], _G) ->
1570  ok;
1571pp_xsivertex([Key|Keys], G) ->
1572  {V,Xsi} = ?GRAPH:vertex(G, Key),
1573  OutNeighbours = ?GRAPH:out_neighbours(G, V),
1574  ?pp_debug(" ~w -> ~w", [V,OutNeighbours]), pp_xsi(Xsi),
1575  pp_xsivertex(Keys, G).
1576
1577pp_cfgvertex([], _G) ->
1578  ok;
1579pp_cfgvertex([Key|Keys], G) ->
1580  {V,Block} = ?GRAPH:vertex(G,Key),
1581  case Block#block.type of
1582    mp ->
1583      ?pp_debug("~n Block ~w's attributes: ~n", [V]),
1584      pp_attributes(Block),
1585      ?pp_debug("~n Block ~w's edges: ~n", [V]),
1586      pp_edges(G, ?GRAPH:in_edges(G,Key), ?GRAPH:out_edges(G,Key));
1587    _->
1588      ok
1589  end,
1590  pp_cfgvertex(Keys, G).
1591
1592pp_attributes(Block) ->
1593  Att = Block#block.attributes,
1594  case Att of
1595    undefined ->
1596      ok;
1597    _ ->
1598      ?pp_debug("        Maps: ~n",[]),pp_maps(gb_trees:keys(Att#mp.maps),Att#mp.maps),
1599      ?pp_debug("        Uses: ~n",[]),pp_uses(gb_trees:keys(Att#mp.uses),Att#mp.uses),
1600      ?pp_debug("        Defs: ~w~n",[Att#mp.defs]),
1601      ?pp_debug("        Xsis: ~w~n",[Att#mp.xsis]),
1602      ?pp_debug("        NDS : ",[]),pp_nds(?SETS:to_list(Att#mp.ndsSet))
1603  end.
1604
1605pp_maps([], _Maps) -> ok;
1606pp_maps([K|Ks], Maps) ->
1607  ?pp_debug("              ",[]),pp_arg(K#xsi_op.op),?pp_debug("-> ~w~n",[?SETS:to_list(gb_trees:get(K,Maps))]),
1608  pp_maps(Ks, Maps).
1609
1610pp_uses([], _Maps) -> ok;
1611pp_uses([K|Ks], Maps) ->
1612  ?pp_debug("              ~w -> ~w~n",[K,?SETS:to_list(gb_trees:get(K,Maps))]),
1613  pp_uses(Ks, Maps).
1614
1615pp_nds([]) -> ?pp_debug("~n",[]);
1616pp_nds(undefined) -> ?pp_debug("None",[]);
1617pp_nds([K]) ->
1618  pp_arg(K#xsi_op.op), ?pp_debug("~n",[]);
1619pp_nds([K|Ks]) ->
1620  pp_arg(K#xsi_op.op), ?pp_debug(", ",[]),
1621  pp_nds(Ks).
1622
1623pp_edges(_G, [], []) -> ok;
1624pp_edges(G, [], [OUT|OUTs]) ->
1625  {_E,V1,V2,Label} = ?GRAPH:edge(G,OUT),
1626  ?pp_debug(" Out edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]),
1627  pp_edges(G, [], OUTs);
1628pp_edges(G, [IN|INs], Outs) ->
1629  {_E,V1,V2,Label} = ?GRAPH:edge(G,IN),
1630  ?pp_debug("  In edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]),
1631  pp_edges(G, INs, Outs).
1632
1633-endif.
1634
1635%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1636%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1637%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1638
1639init_counters() ->
1640  put({ssapre_temp,temp_count}, 0),
1641  put({ssapre_index,index_count}, 0).
1642
1643new_bottom() ->
1644  IndxCountPair = {ssapre_index, index_count},
1645  V = get(IndxCountPair),
1646  put(IndxCountPair, V+1),
1647  #bottom{key = V, var = ?RTL:mk_new_var()}.
1648
1649new_temp() ->
1650  TmpCountPair = {ssapre_temp, temp_count},
1651  V = get(TmpCountPair),
1652  put(TmpCountPair, V+1),
1653  #temp{key = V, var = ?RTL:mk_new_var()}.
1654
1655init_redundancy_count() ->
1656  put({ssapre_redundancy,redundancy_count}, 0).
1657
1658redundancy_add() ->
1659  RedCountPair = {ssapre_redundancy, redundancy_count},
1660  V = get(RedCountPair),
1661  put(RedCountPair, V+1).
1662
1663-ifdef(SSAPRE_DEBUG).
1664get_redundancy_count() ->
1665  get({ssapre_redundancy,redundancy_count}).
1666-endif.
1667