1
%% -*- erlang-indent-level: 2 -*-
2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3
%% File : hipe_rtl_ssapre.erl
4
%% Author : He Bingwen and Fr�d�ric Haziza
5
%% Description : Performs Partial Redundancy Elimination on SSA form.
6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11
%% This module implements the <a href="http://cs.wheaton.edu/%7Etvandrun/writings/spessapre.pdf">Anticipation-SSAPRE algorithm</a>,
12
%% with several modifications for Partial Redundancy Elimination on SSA form.
13
%% We actually found problems in this algorithm, so
14
%% we implement another version with several advantages:
15
%% - No loop for Xsi insertions
16
%% - No fix point iteration for the downsafety part
17
%% - Less computations for Will Be Available part
18
%% - Complexity of the overall algorithm is improved
20
%% We were supposed to publish these results anyway :D
23
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
25
-module(hipe_rtl_ssapre).
27
-export([rtl_ssapre/2]).
29
-include("../main/hipe.hrl").
30
-include("hipe_rtl.hrl").
32
%%-define(SSAPRE_DEBUG, true ). %% When uncommented, produces debug printouts
33
-define( SETS, ordsets ). %% Which set implementation module to use
34
-define( CFG, hipe_rtl_cfg ).
35
-define( RTL, hipe_rtl ).
36
-define( BB, hipe_bb ).
37
-define( ARCH, hipe_rtl_arch ).
38
-define( GRAPH, digraph ).
40
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
41
%% Records / Structures
42
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
44
-record(xsi_link,{number}). %% Number is the index of the temporary (a Key into the Xsi Tree)
45
-record(temp,{key,var}).
46
-record(bottom,{key,var}).
47
-record(xsi, { inst, %% Associated instruction
48
def, %% Hypothetical temporary variable
49
%% that stores the result of the computation
50
label, %% Block Label where the xsi is inserted
51
opList,%% List of operands
57
-record(pre_candidate, {alu,def}).
58
-record(xsi_op, {pred,op}).
60
-record(mp, {xsis,maps,preds,defs,uses,ndsSet}).
61
-record(block, {type,attributes}).
63
-record(eop, {expr,var,stopped_by}).
64
-record(insertion, {code,from}).
66
-record(const_expr, {var,value}).
68
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
70
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
72
rtl_ssapre(RtlSSACfg, Options) ->
73
%% io:format("\n################ Original CFG ################\n"),
74
%% hipe_rtl_cfg:pp(RtlSSACfg),
75
%% io:format("\n\n############ SSA-Form CHECK ==> ~w\n",[hipe_rtl_ssa:check(RtlSSACfg)]),
77
{CFG2,XsiGraph,CFGGraph,MPs} = perform_Xsi_insertion(RtlSSACfg,Options),
78
%%pp_debug("~n~n################ Xsi CFG ################\n",[]),pp_cfg(CFG2,XsiGraph),
79
XsiList = ?GRAPH:vertices(XsiGraph),
83
?option_time(pp_debug("~n~n################ No Xsi Inserted ################~n",[]),"RTL A-SSAPRE No Xsi inserted (skip Downsafety and Will Be Available)",Options),
86
pp_debug("~n############ Downsafety ##########~n",[]),
87
?option_time(perform_downsafety(MPs,CFGGraph,XsiGraph),"RTL A-SSAPRE Downsafety",Options),
88
pp_debug("~n~n################ CFG Graph ################~n",[]),pp_cfggraph(CFGGraph),
89
pp_debug("~n############ Will Be Available ##########~n",[]),
90
?option_time(perform_will_be_available(XsiGraph,CFGGraph,Options),"RTL A-SSAPRE WillBeAvailable",Options)
93
pp_debug("~n############ No more need for the CFG Graph....Deleting...",[]),?GRAPH:delete(CFGGraph),
94
pp_debug("~n~n################ Xsi Graph ################~n",[]),pp_xsigraph(XsiGraph),
96
pp_debug("~n############ Code Motion ##########~n",[]),
97
Labels = ?CFG:preorder(CFG2),
99
pp_debug("~n~n################ Xsi CFG ################~n",[]),pp_cfg(CFG2,XsiGraph),
101
init_redundancy_count(),
102
?option_time(FinalCFG=perform_code_motion(Labels,CFG2,XsiGraph),"RTL A-SSAPRE Code Motion",Options),
104
pp_debug("\n############ No more need for the Xsi Graph....Deleting...",[]),?GRAPH:delete(XsiGraph),
106
%% io:format("\n################ Final CFG ################\n"),
107
%% hipe_rtl_cfg:pp(FinalCFG),
108
%% io:format("\n\n############ SSA-Form CHECK ==> ~w\n",
109
%% [hipe_rtl_ssa:check(FinalCFG)]),
110
pp_debug("\nSSAPRE : ~w redundancies were found\n",[get_redundancy_count()]),
114
%% ##########################################################################
115
%% ######################## XSI INSERTION ###################################
116
%% ##########################################################################
118
perform_Xsi_insertion(Cfg, Options)->
119
init_counters(), %% Init counters for Bottoms and Temps
120
XsiGraph = digraph:new([cyclic,private]),
121
%% Be carefull, the digraph component is NOT garbage collected,
122
%% so don't create 20 millions of instances!
123
%% finds the longest depth
124
%% Depth-first, preorder traversal over Basic Blocks.
125
%%Labels = ?CFG:reverse_postorder(Cfg),
126
Labels = ?CFG:preorder(Cfg),
128
pp_debug("~n~n############# Finding definitions for computation~n~n",[]),
129
?option_time({Cfg2,XsiGraph} = find_definition_for_computations(Labels,Cfg,XsiGraph),"RTL A-SSAPRE Xsi Insertion, searching from instructions",Options),
131
%% Active List creation
132
GeneratorXsiList = lists:sort(?GRAPH:vertices(XsiGraph)),
133
pp_debug("~n~n############# Inserted Xsis ~w",[GeneratorXsiList]),
134
pp_debug("~n~n############# Finding operands~n",[]),
135
?option_time({Cfg3,XsiGraph} = find_operands(Cfg2,XsiGraph,GeneratorXsiList,0),"RTL A-SSAPRE Xsi Insertion, finding operands",Options),
137
%% Creating the CFGGraph
138
pp_debug("~n~n############# Creating CFG Graph",[]),
139
pp_debug("~n############# Labels = ~w",[Labels]),
140
CFGGraph = digraph:new([cyclic,private]),
141
[StartLabel|Others] = Labels, % adding the start label as a leaf
142
pp_debug("~nAdding a vertex for the start label: ~w",[StartLabel]),
143
?GRAPH:add_vertex(CFGGraph,StartLabel,#block{type=top}),
145
?option_time(MPs=create_cfggraph(Others,Cfg3,CFGGraph,[],[],[],XsiGraph),"RTL A-SSAPRE Xsi Insertion, creating intermediate 'SSAPRE Graph'",Options),
147
%% Return the bloody collected information
148
{Cfg3,XsiGraph,CFGGraph,MPs}.
150
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
152
find_definition_for_computations([], Cfg, XsiGraph) ->
153
{Cfg,XsiGraph}; %% No more block to inspect in the depth-first order
154
find_definition_for_computations([Label|Rest], Cfg, XsiGraph) ->
155
Code = ?BB:code(?CFG:bb(Cfg,Label)),
156
{NewCfg,XsiGraph} = find_definition_for_computations_in_block(Label,Code,Cfg,[],XsiGraph),
157
find_definition_for_computations(Rest, NewCfg, XsiGraph).
159
%%===========================================================================
160
%% Searches from instruction for one block BlockLabel.
161
%% We process forward over instructions.
163
find_definition_for_computations_in_block(BlockLabel,[],Cfg,
164
VisitedInstructions,XsiGraph)->
165
Code = lists:reverse(VisitedInstructions),
166
NewBB = ?BB:mk_bb(Code),
167
NewCfg = ?CFG:bb_add(Cfg,BlockLabel,NewBB),
168
{NewCfg,XsiGraph}; %% No more instructions to inspect in this block
169
find_definition_for_computations_in_block(BlockLabel,[Inst|Rest],Cfg,
170
VisitedInstructions,XsiGraph) ->
171
%% pp_debug(" Inspecting instruction: ",[]),pp_instr(Inst,nil),
174
%% Is Inst interesting for SSAPRE?
175
%% i.e., is Inst an arithmetic operation which doesn't deal with precoloured?
176
%% Note that since we parse forward, we have no 'pre_candidate'-type so far.
177
case check_definition(Inst,VisitedInstructions,BlockLabel,Cfg,XsiGraph) of
179
%% Replacing Inst in Cfg
180
NewInst = #pre_candidate{alu=Inst,def=Def},
181
NewVisited = [NewInst|VisitedInstructions],
182
%% Recurse forward over instructions, same CFG, same XsiGraph
183
find_definition_for_computations_in_block(BlockLabel,Rest,Cfg,
184
NewVisited,XsiGraph);
188
NewInst = #pre_candidate{alu=Inst,def=Def},
189
XsiLink = #xsi_link{number=Key},
191
%% Add a vertex to the Xsi Graph
192
?GRAPH:add_vertex(XsiGraph,Key,Xsi),
193
pp_debug(" Inserting Xsi: ",[]),pp_xsi(Xsi),
195
Label = Xsi#xsi.label,
196
case BlockLabel == Label of
198
%% Insert the Xsi in the appropriate block
199
Code = hipe_bb:code(?CFG:bb(Cfg,Label)),
200
{BeforeCode,AfterCode} = split_for_xsi(lists:reverse(Code),[]),
201
NewCode = BeforeCode++[XsiLink|AfterCode],
202
NewBB = hipe_bb:mk_bb(NewCode),
203
NewCfg = ?CFG:bb_add(Cfg,Label,NewBB),
204
NewVisited = [NewInst|VisitedInstructions];
206
{BeforeCode,AfterCode} = split_for_xsi(VisitedInstructions,[]),
207
TempVisited = BeforeCode++[XsiLink|AfterCode],
208
TempVisited2 = lists:reverse(TempVisited),
209
NewVisited = [NewInst|TempVisited2],
212
find_definition_for_computations_in_block(BlockLabel, Rest, NewCfg,
213
NewVisited, XsiGraph)
216
%%pp_debug("~n [L~w] Not concerned with: ~w",[BlockLabel,Inst]),
217
%% If the instruction is not a SSAPRE candidate, we skip it and keep on
218
%% processing instructions
219
%% Prepend Inst, so that we have all in reverse order.
220
%% Easy to parse backwards
221
find_definition_for_computations_in_block(BlockLabel, Rest, Cfg,
222
[Inst|VisitedInstructions], XsiGraph)
225
%% ############################################################################
226
%% We have E as an expression, I has an alu (arithmetic operation), and
227
%% we inspect backwards the previous instructions to find a definition for E.
228
%% Since we parse in forward order, we know that the previous SSAPRE
229
%% instruction will have a definition.
231
check_definition(E,[],BlockLabel,Cfg,XsiGraph)->
232
%% No more instructions in that block
233
%% No definition found in that block
234
%% Search is previous blocks
235
Preds = ?CFG:pred(?CFG:pred_map(Cfg),BlockLabel),
236
%% pp_debug("~n CHECKING DEFINITION ####### Is L~w a merge block? It has ~w preds. So far E=",[BlockLabel,length(Preds)]),pp_expr(E),
242
%% One predecessor only, we just keep looking for a definition in that block
243
VisitedInstructions = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))),
244
check_definition(E,VisitedInstructions,P,Cfg,XsiGraph);
247
%% It's a merge point
248
OpList = [#xsi_op{pred=X} || X<-Preds],
249
Xsi = #xsi{inst=E,def=Temp,label=BlockLabel,opList=OpList},
252
check_definition(E,[CC|Rest],BlockLabel,Cfg,XsiGraph) ->
253
SRC1 = ?RTL:alu_src1(E),
254
SRC2 = ?RTL:alu_src2(E),
257
exit({?MODULE,should_not_be_an_alu,
258
{"Why the hell do we still have an alu???",CC}});
260
%% C is the previous instruction
261
C = CC#pre_candidate.alu,
262
DST = ?RTL:alu_dst(C),
263
case DST==SRC1 orelse DST==SRC2 of
265
case check_match(E,C) of
266
true -> %% It's a computation of E!
267
%% Get the dst of the alu
270
check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
273
%% Get the definition of C, since C is PRE-candidate AND has been processed before
274
DEF = CC#pre_candidate.def,
277
%% Def(E)=bottom, STOP
280
%% Emend E with this def(C)
281
%%pp_debug("Parameters are E=~w, DST=~w, DEF=~w",[E,DST,DEF]),
283
check_definition(F,Rest,BlockLabel,Cfg,XsiGraph) %% Continue the search
287
%% It's a move, we emend E, and continue the definition search
288
DST = ?RTL:move_dst(CC),
289
F = case SRC1==DST orelse SRC2==DST of
291
SRC = ?RTL:move_src(CC),
296
check_definition(F,Rest,BlockLabel,Cfg,XsiGraph); %% Continue the search
298
{_K,Xsi} = ?GRAPH:vertex(XsiGraph,CC#xsi_link.number),
300
case check_match(C,E) of
301
true -> %% There is a Xsi already with a computation of E!
302
%% fetch definition of C, and give it to E
303
{def_found,Xsi#xsi.def};
305
check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
308
%% skip them. NOTE: Important to separate this case from the next one
309
check_definition(E,Rest,BlockLabel,Cfg,XsiGraph);
311
%% Note: the function calls or some other instructions can change the pre-coloured registers
312
%% which are able to be redefined. This breaks of course the SSA form.
313
%% If there is a redefinition we can give bottom to the computation, and no xsi will be inserted.
314
%% (In some sens, the result of the computation is new at that point.)
315
PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2),
317
%%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2),
318
RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)), %% That means we cannot reuse the result held in this register...
320
case PreColouredTest orelse RegisterTest of
324
DC = ?RTL:defines(CC),
325
case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of
329
%% Orthogonal to E, we continue the search
330
check_definition(E,Rest,BlockLabel,Cfg,XsiGraph)
335
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
338
OpE = ?RTL:alu_op(E),
339
OpC = ?RTL:alu_op(C),
344
Src1E = ?RTL:alu_src1(E),
345
Src2E = ?RTL:alu_src2(E),
346
Src1C = ?RTL:alu_src1(C),
347
Src2C = ?RTL:alu_src2(C),
348
case Src1E == Src1C of
352
case Src1E == Src2C of
361
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
363
expr_is_constant(E) ->
364
?RTL:is_imm(?RTL:alu_src1(E)) andalso ?RTL:is_imm(?RTL:alu_src2(E)).
365
%% is_number(?RTL:alu_src1(E)) andalso is_number(?RTL:alu_src2(E)).
367
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
368
%% Must be an arithmetic operation, i.e. #alu{}
369
emend(Expr, S, Var) ->
370
SRC1 = ?RTL:alu_src1(Expr),
371
NewExpr = case SRC1 == S of
372
true -> ?RTL:alu_src1_update(Expr,Var);
375
SRC2 = ?RTL:alu_src2(NewExpr),
376
NewExpr2 = case SRC2 == S of
377
true -> ?RTL:alu_src2_update(NewExpr,Var);
382
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
384
split_for_xsi([], Acc) ->
385
{[],Acc}; % no_xsi_no_phi_found;
386
split_for_xsi([I|Rest], Acc) -> %% [I|Rest] in backward order, Acc in order
389
BeforeCode = [I|Rest],
390
{lists:reverse(BeforeCode), Acc};
392
BeforeCode = [I|Rest],
393
{lists:reverse(BeforeCode), Acc};
395
split_for_xsi(Rest,[I|Acc])
398
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
399
%% Phase 1.B : Search for operands
400
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
402
find_operands(Cfg,XsiGraph,[],_Count) ->
404
find_operands(Cfg,XsiGraph,ActiveList,Count) ->
405
{NewCfg,TempActiveList} = find_operands_for_active_list(Cfg,XsiGraph,ActiveList,[]),
406
NewActiveList = lists:reverse(TempActiveList),
407
pp_debug("~n################ Finding operands (iteration ~w): ~w have been introduced. Now ~w in total~n",
408
[Count+1, length(NewActiveList), length(?GRAPH:vertices(XsiGraph))]),
409
find_operands(NewCfg,XsiGraph,NewActiveList,Count+1).
411
find_operands_for_active_list(Cfg,_XsiGraph,[],ActiveListAcc) ->
413
find_operands_for_active_list(Cfg,XsiGraph,[K|Ks],ActiveListAcc) ->
414
{_Key,Xsi} = ?GRAPH:vertex(XsiGraph,K),
415
pp_debug("~n Inspecting operands of : ~n",[]),pp_xsi(Xsi),
416
Preds = ?CFG:pred(?CFG:pred_map(Cfg),Xsi#xsi.label),
417
{NewCfg,NewActiveListAcc}=determine_operands(Xsi,Preds,Cfg,K,XsiGraph,ActiveListAcc),
418
{_Key2,Xsi2} = ?GRAPH:vertex(XsiGraph,K),
419
pp_debug("~n ** Final Xsi: ~n",[]),pp_xsi(Xsi2),
420
pp_debug("~n #####################################################~n",[]),
421
find_operands_for_active_list(NewCfg,XsiGraph,Ks,NewActiveListAcc).
423
determine_operands(_Xsi,[],Cfg,_K,_XsiGraph,ActiveAcc) ->
424
%% All operands have been determined.
425
%% The CFG is not updated, only the XsiGraph
427
determine_operands(Xsi,[P|Ps],Cfg,K,XsiGraph,ActiveAcc) ->
428
Label = Xsi#xsi.label,
429
ReverseCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,Label))),
430
VisitedInstructions = get_visited_instructions(Xsi,ReverseCode),
431
Res = determine_e_prime(Xsi#xsi.inst,VisitedInstructions,P,XsiGraph),
435
NewXsi = xsi_arg_update(Xsi,P,new_bottom()),
436
?GRAPH:add_vertex(XsiGraph,K,NewXsi),
437
determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
438
operand_is_const_expr ->
439
NewXsi = xsi_arg_update(Xsi,P,new_bottom()),
440
?GRAPH:add_vertex(XsiGraph,K,NewXsi),
441
determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
442
{sharing_operand,Op} ->
443
NewXsi = xsi_arg_update(Xsi,P,Op),
444
?GRAPH:add_vertex(XsiGraph,K,NewXsi),
445
determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
446
{revised_expression,E_prime} ->
447
pp_debug(" E' is determined : ",[]),pp_expr(E_prime),
448
pp_debug(" and going along the edge L~w~n",[P]),
449
%% Go along the edge P
450
RevCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,P))),
451
case check_one_operand(E_prime,RevCode,P,Cfg,K,XsiGraph) of
453
NewXsi = xsi_arg_update(Xsi,P,Def),
454
?GRAPH:add_vertex(XsiGraph,K,NewXsi),
455
determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
457
{expr_found,ChildExpr}->
458
NewXsi = xsi_arg_update(Xsi,P,ChildExpr),
459
?GRAPH:add_vertex(XsiGraph,K,NewXsi),
460
determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
462
{expr_is_constant,Op}->
463
%% We detected that the expression is of the form: 'N op M'
464
%% where N and M are constant.
465
NewXsi = xsi_arg_update(Xsi,P,Op),
466
?GRAPH:add_vertex(XsiGraph,K,NewXsi),
467
determine_operands(NewXsi,Ps,Cfg,K,XsiGraph,ActiveAcc);
469
{merge_point,XsiChild}->
470
%% Update that Xsi, give its definition as Operand for the
472
XsiChildDef = XsiChild#xsi.def,
473
NewXsi = xsi_arg_update(Xsi,P,XsiChildDef),
474
?GRAPH:add_vertex(XsiGraph,K,NewXsi),
476
KeyChild = XsiChildDef#temp.key,
477
XsiChildLink = #xsi_link{number=KeyChild},
478
?GRAPH:add_vertex(XsiGraph,KeyChild,XsiChild),
480
%% Should not be the same block !!!!!!!
481
RCode = lists:reverse(hipe_bb:code(?CFG:bb(Cfg,XsiChild#xsi.label))),
482
{BCode,ACode}=split_code_for_xsi(RCode,[]),
484
NewCode = BCode++[XsiChildLink|ACode],
485
NewBB = hipe_bb:mk_bb(NewCode),
486
NewCfg = ?CFG:bb_add(Cfg, XsiChild#xsi.label, NewBB),
488
pp_debug(" -- ",[]),pp_arg(Xsi#xsi.def),pp_debug(" causes insertion of: ~n",[]),pp_xsi(XsiChild),
489
pp_debug(" -- Adding an edge ",[]),pp_arg(Xsi#xsi.def),pp_debug(" -> ",[]),pp_arg(XsiChild#xsi.def),
492
%%?GRAPH:add_edge(XsiGraph,K,KeyChild,"family"),
493
?GRAPH:add_edge(XsiGraph,K,KeyChild),
494
determine_operands(NewXsi,Ps,NewCfg,K,XsiGraph,[KeyChild|ActiveAcc])
498
determine_e_prime(Expr,VisitedInstructions,Pred,XsiGraph) ->
499
%% MUST FETCH FROM THE XSI TREE, since Xsis are not updated yet in the CFG
500
NewExpr=emend_with_phis(Expr,VisitedInstructions,Pred),
501
emend_with_processed_xsis(NewExpr,VisitedInstructions,Pred,XsiGraph).
503
emend_with_phis(EmendedE, [], _) ->
505
emend_with_phis(E, [I|Rest], Pred) ->
508
Dst = ?RTL:phi_dst(I),
509
UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead?
510
case lists:member(Dst, UE) of
512
emend_with_phis(E, Rest, Pred);
514
NewE = emend(E, Dst, ?RTL:phi_arg(I,Pred)),
515
emend_with_phis(NewE, Rest, Pred)
518
emend_with_phis(E, Rest, Pred)
521
emend_with_processed_xsis(EmendedE, [], _, _) ->
522
{revised_expression,EmendedE};
523
emend_with_processed_xsis(E, [I|Rest], Pred, XsiGraph) ->
526
Key = I#xsi_link.number,
527
{_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
529
UE = ?RTL:uses(E), %% Should we get SRC1 and SRC2 instead?
530
case lists:member(Def,UE) of
533
case check_match(E,CE) of
534
true -> %% It's a computation of E!
535
case xsi_arg(Xsi,Pred) of
536
undetermined_operand ->
537
exit({?MODULE,check_operand_sharing,"######## �h Dear, we trusted Kostis !!!!!!!!! #############"});
539
{sharing_operand,XsiOp} %% They share operands
542
emend_with_processed_xsis(E,Rest,Pred,XsiGraph)
546
%%pp_debug(" ######### xsi_arg(I:~w,Pred:~w) = ~w~n",[I,Pred,A]),
551
operand_is_const_expr;
553
NewE = emend(E,Def,A#eop.var),
554
emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph);
555
undetermined_operand ->
556
exit({?MODULE,emend_with_processed_xsis,"######## �h Dear, we trusted Kostis, again !!!!!!!!! #############"});
558
NewE = emend(E,Def,XsiOp),
559
emend_with_processed_xsis(NewE,Rest,Pred,XsiGraph)
563
emend_with_processed_xsis(E,Rest,Pred,XsiGraph)
566
%% get_visited_instructions(Xsi,[]) ->
567
%% pp_debug("~nWe don't find this xsi with def ",[]),pp_arg(Xsi#xsi.def),pp_debug(" in L~w : ",[Xsi#xsi.label]),
568
%% exit({?MODULE,no_such_xsi_in_block,"We didn't find that Xsi in the block"});
569
get_visited_instructions(Xsi,[I|Rest]) ->
572
XsiDef = Xsi#xsi.def,
573
Key = XsiDef#temp.key,
574
case I#xsi_link.number == Key of
578
get_visited_instructions(Xsi,Rest)
581
get_visited_instructions(Xsi,Rest)
584
split_code_for_xsi([], Acc) ->
586
split_code_for_xsi([I|Rest], Acc) ->
589
{lists:reverse([I|Rest]),Acc};
591
{lists:reverse([I|Rest]),Acc};
593
split_code_for_xsi(Rest,[I|Acc])
596
check_one_operand(E, [], BlockLabel, Cfg, XsiKey, XsiGraph) ->
597
%% No more instructions in that block
598
%% No definition found in that block
599
%% Search is previous blocks
600
Preds = ?CFG:pred(?CFG:pred_map(Cfg), BlockLabel),
604
{def_found,new_bottom()};
606
%% One predecessor only, we just keep looking for a definition in that block
607
case expr_is_constant(E) of
609
pp_debug("\n\n############## Wow expr is constant: ~w",[E]),
610
Var = ?RTL:mk_new_var(),
611
Value = eval_expr(E),
612
Op = #const_expr{var=Var,value=Value},
613
{expr_is_constant,Op};
615
VisitedInstructions = lists:reverse(?BB:code(?CFG:bb(Cfg,P))),
616
check_one_operand(E,VisitedInstructions,P,Cfg,XsiKey,XsiGraph)
619
%% It's a merge point
620
case expr_is_constant(E) of
622
pp_debug("\n\n############## Wow expr is constant at merge point: ~w",[E]),
623
Var = ?RTL:mk_new_var(),
624
Value = eval_expr(E),
625
Op = #const_expr{var=Var,value=Value},
626
{expr_is_constant,Op};
629
OpList = [#xsi_op{pred=X} || X <- Preds],
630
Xsi = #xsi{inst=E,def=Temp,label=BlockLabel,opList=OpList},
634
check_one_operand(E,[CC|Rest],BlockLabel,Cfg,XsiKey,XsiGraph) ->
635
SRC1 = ?RTL:alu_src1(E),
636
SRC2 = ?RTL:alu_src2(E),
637
%% C is the previous instruction
640
exit({?MODULE,should_not_be_an_alu,
641
{"Why the hell do we still have an alu???",CC}});
643
exit({?MODULE,should_not_be_a_xsi,
644
{"Why the hell do we still have a xsi???",CC}});
646
C = CC#pre_candidate.alu,
647
DST = ?RTL:alu_dst(C),
648
case DST==SRC1 orelse DST==SRC2 of
650
%% Get the definition of C, since C is PRE-candidate AND has
651
%% been processed before
652
DEF = CC#pre_candidate.def,
655
%% Def(E)=bottom, STOP
656
%% No update of the XsiGraph
657
{def_found,new_bottom()};
660
F = emend(E,DST,DEF),
661
pp_debug("~nEmendation : E= ",[]),pp_expr(E),pp_debug(" ==> E'= ",[]),pp_expr(F),pp_debug("~n",[]),
662
check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
665
case check_match(C,E) of
666
true -> %% It's a computation of E!
667
%% It should give DST and not Def
668
%% No update of the XsiGraph, cuz we use DST and not Def
669
%% The operand is therefore gonna be a real variable
672
%% Nothing to do with E
673
check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
677
%% It's a move, we emend E, and continue the definition search
678
DST = ?RTL:move_dst(CC),
679
case SRC1==DST orelse SRC2==DST of
681
SRC = ?RTL:move_src(CC),
682
F = emend(E,DST,SRC),
683
check_one_operand(F,Rest,BlockLabel,Cfg,XsiKey,XsiGraph); %% Continue the search
685
check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph) %% Continue the search
688
Key = CC#xsi_link.number,
689
%% Is Key a family member of XsiDef ?
690
{_KK,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
692
case check_match(E,C) of
693
true -> %% There is a Xsi already with a computation of E!
694
%% fetch definition of C, and give it to E
695
%% Must update an edge in the XsiGraph, and here, we know it's a Temp
696
%% Note: this can create a loop (= a cycle of length 1)
697
pp_debug(" -- Found a cycle with match: Adding an edge t~w -> t~w",[XsiKey,Key]),
698
?GRAPH:add_edge(XsiGraph,XsiKey,Key),
699
{def_found,Xsi#xsi.def};
701
case ?GRAPH:get_path(XsiGraph,Key,XsiKey) of
703
%% Is it a loop back to itself???
706
check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph);
708
{expr_found,#eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key}}
711
%% Returning the expression instead of looping
712
%% And in case of no match
713
ExprOp = #eop{expr=E,var=?RTL:mk_new_var(),stopped_by=Key},
717
#phi{} -> %% skip them
718
check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph);
720
PreColouredTest = ?ARCH:is_precoloured(SRC1) orelse ?ARCH:is_precoloured(SRC2),
722
%%RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)) orelse ?RTL:is_reg(SRC1) orelse ?RTL:is_reg(SRC2),
723
RegisterTest = ?RTL:is_reg(?RTL:alu_dst(E)),
725
case PreColouredTest orelse RegisterTest of
727
{def_found,new_bottom()};
729
DC = ?RTL:defines(CC),
730
case lists:member(SRC1,DC) orelse lists:member(SRC2,DC) of
732
{def_found,new_bottom()};
734
%% Orthogonal to E, we continue the search
735
check_one_operand(E,Rest,BlockLabel,Cfg,XsiKey,XsiGraph)
741
pp_debug("~n Evaluating the result of ~w~n", [E]),
742
Op1 = ?RTL:alu_src1(E),
743
Op2 = ?RTL:alu_src2(E),
744
Val1 = case ?RTL:is_imm(Op1) of
745
true -> ?RTL:imm_value(Op1)
747
Val2 = case ?RTL:is_imm(Op2) of
748
true -> ?RTL:imm_value(Op2)
750
{Result, _Sign, _Zero, _Overflow, _Carry} = ?ARCH:eval_alu(?RTL:alu_op(E), Val1, Val2),
751
pp_debug("~n Result is then ~w~n", [Result]),
754
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
755
%%%%%%%%%%%%%%%%%%%%%%%%%% CREATTING CFGGRAPH %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
756
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
758
create_cfggraph([],_Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,_XsiGraph) ->
759
pp_debug("~n~n ############# PostProcessing ~n~w~n",[LateEdges]),
760
post_process(LateEdges,CFGGraph),
761
pp_debug("~n~n ############# Factorizing ~n~w~n",[ToBeFactorizedAcc]),
762
factorize(ToBeFactorizedAcc,CFGGraph),
764
create_cfggraph([Label|Ls],Cfg,CFGGraph,ToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph) ->
765
Preds = ?CFG:pred(?CFG:pred_map(Cfg),Label),
768
exit({?MODULE,do_not_call_on_top,{"Why the hell do we call that function on the start label???",Label}});
770
Code = ?BB:code(?CFG:bb(Cfg,Label)),
771
Defs = get_defs_in_non_merge_block(Code,[]),
772
pp_debug("~nAdding a vertex for ~w",[Label]),
773
Succs = ?CFG:succ(?CFG:succ_map(Cfg),Label),
776
?GRAPH:add_vertex(CFGGraph,Label,#block{type=exit}),
777
NewToBeFactorizedAcc=ToBeFactorizedAcc;
779
?GRAPH:add_vertex(CFGGraph,Label,#block{type=not_mp,attributes={P,Succs}}),
780
NewToBeFactorizedAcc=[Label|ToBeFactorizedAcc]
782
pp_debug("~nAdding an edge ~w -> ~w (~w)",[P,Label,Defs]),
783
case ?GRAPH:add_edge(CFGGraph,P,Label,Defs) of
785
exit({?MODULE,forget_that_for_christs_sake_bingwen_please,{"Bad edge",Reason}});
789
create_cfggraph(Ls,Cfg,CFGGraph,NewToBeFactorizedAcc,MPAcc,LateEdges,XsiGraph);
791
Code = ?BB:code(?CFG:bb(Cfg,Label)),
792
{Defs,Xsis,Maps,Uses} = get_info_in_merge_block(Code,XsiGraph,[],[],gb_trees:empty(),gb_trees:empty()),
793
Attributes = #mp{preds=Preds,xsis=Xsis,defs=Defs,maps=Maps,uses=Uses},
794
MergeBlock = #block{type=mp,attributes=Attributes},
795
pp_debug("~nAdding a vertex for ~w with Defs= ~w",[Label,Defs]),
796
?GRAPH:add_vertex(CFGGraph,Label,MergeBlock),
798
NewLateEdges = add_edges_for_mp(Preds,Label,LateEdges),
799
create_cfggraph(Ls,Cfg,CFGGraph,ToBeFactorizedAcc,[Label|MPAcc],NewLateEdges,XsiGraph)
802
get_defs_in_non_merge_block([], Acc) ->
803
?SETS:from_list(Acc);
804
get_defs_in_non_merge_block([Inst|Rest], Acc) ->
807
Def = Inst#pre_candidate.def,
811
%% get_defs_in_non_merge_block(Rest,[Key|Acc]);
812
get_defs_in_non_merge_block(Rest,[Def#temp.key|Acc]);
813
_-> %% Real variables or bottom
814
get_defs_in_non_merge_block(Rest,Acc)
817
get_defs_in_non_merge_block(Rest,Acc)
820
get_info_in_merge_block([],_XsiGraph,Defs,Xsis,Maps,Uses) ->
821
{?SETS:from_list(Defs),Xsis,Maps,Uses}; %% Xsis are in backward order
822
get_info_in_merge_block([Inst|Rest],XsiGraph,Defs,Xsis,Maps,Uses) ->
825
Def = Inst#pre_candidate.def,
828
get_info_in_merge_block(Rest,XsiGraph,[Def#temp.key|Defs],Xsis,Maps,Uses);
830
get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses)
833
Key = Inst#xsi_link.number,
834
{_Key,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
835
OpList = xsi_oplist(Xsi),
836
{NewMaps,NewUses} = add_map_and_uses(OpList,Key,Maps,Uses),
837
get_info_in_merge_block(Rest,XsiGraph,Defs,[Key|Xsis],NewMaps,NewUses);
839
get_info_in_merge_block(Rest,XsiGraph,Defs,Xsis,Maps,Uses)
842
add_edges_for_mp([], _Label, LateEdges) ->
844
add_edges_for_mp([P|Ps], Label, LateEdges) ->
845
add_edges_for_mp(Ps,Label,[{P,Label}|LateEdges]).
847
%% Doesn't do anything so far
848
add_map_and_uses([], _Key, Maps, Uses) ->
850
add_map_and_uses([XsiOp|Ops], Key, Maps, Uses) ->
851
case XsiOp#xsi_op.op of
853
Set = case gb_trees:lookup(XsiOp,Maps) of
855
?SETS:add_element(Key,V);
857
?SETS:from_list([Key])
859
NewMaps = gb_trees:enter(XsiOp,Set,Maps),
862
Set = case gb_trees:lookup(XsiOp,Maps) of
864
?SETS:add_element(Key,V);
866
?SETS:from_list([Key])
868
NewMaps = gb_trees:enter(XsiOp,Set,Maps),
869
Pred = XsiOp#xsi_op.pred,
870
OOP = XsiOp#xsi_op.op,
871
SSet = case gb_trees:lookup(Pred,Uses) of
873
?SETS:add_element(OOP#temp.key,VV);
875
?SETS:from_list([OOP#temp.key])
877
NewUses = gb_trees:enter(Pred,SSet,Uses);
879
Set = case gb_trees:lookup(XsiOp,Maps) of
881
?SETS:add_element(Key,V);
883
?SETS:from_list([Key])
885
NewMaps = gb_trees:enter(XsiOp,Set,Maps),
886
Pred = XsiOp#xsi_op.pred,
887
Op = XsiOp#xsi_op.op,
888
SSet = case gb_trees:lookup(Pred,Uses) of
890
?SETS:add_element(Op#eop.stopped_by,VV);
892
?SETS:from_list([Op#eop.stopped_by])
894
NewUses = gb_trees:enter(Pred,SSet,Uses);
899
add_map_and_uses(Ops, Key, NewMaps, NewUses).
901
post_process([], _CFGGraph) -> ok;
902
post_process([E|Es], CFGGraph) ->
904
{_PP,Block} = ?GRAPH:vertex(CFGGraph,Label),
905
Att = Block#block.attributes,
907
SetToAdd = case gb_trees:lookup(Pred,Uses) of
913
%%pp_debug("~nAdding an edge ~w -> ~w (~w)",[Pred,Label,SetToAdd]),
914
?GRAPH:add_edge(CFGGraph, Pred, Label, SetToAdd),
915
post_process(Es, CFGGraph).
917
factorize([], _CFGGraph) -> ok;
918
factorize([P|Ps], CFGGraph) ->
919
[OE|OEs] = ?GRAPH:out_edges(CFGGraph,P),
920
%%pp_debug("~nIn_degrees ~w : ~w",[P,?GRAPH:in_degree(CFGGraph,P)]),
921
[InEdge] = ?GRAPH:in_edges(CFGGraph,P),
922
{E,V1,V2,Label} = ?GRAPH:edge(CFGGraph,InEdge),
923
{_OEE,_OEV1,_OEV2,LOE} = ?GRAPH:edge(CFGGraph,OE),
924
List = shoot_info_upwards(OEs,LOE,CFGGraph),
925
NewLabel = ?SETS:union(Label,List),
926
?GRAPH:add_edge(CFGGraph,E,V1,V2,NewLabel),
927
factorize(Ps, CFGGraph).
929
shoot_info_upwards([], Acc, _CFGGraph) -> Acc;
930
shoot_info_upwards([E|Es], Acc, CFGGraph) ->
931
{_E,_V1,_V2,Set} = ?GRAPH:edge(CFGGraph,E),
932
NewAcc = ?SETS:intersection(Acc, Set),
933
case ?SETS:size(NewAcc) of
935
_ -> shoot_info_upwards(Es,NewAcc,CFGGraph)
938
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
939
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DOWNSAFETY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
940
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
942
perform_downsafety([],_G,_XsiG) ->
944
perform_downsafety([MP|MPs],G,XG) ->
945
{V,Block} = ?GRAPH:vertex(G,MP),
947
Att = Block#block.attributes,
950
OutEdges = ?GRAPH:out_edges(G,MP),
951
%%pp_debug("~n Inspection Maps : ~w",[Maps]),
952
NewNDS = parse_keys(gb_trees:keys(Maps),Maps,OutEdges,G,Defs,NDS,XG),
953
NewAtt = Att#mp{ndsSet=NewNDS},
954
?GRAPH:add_vertex(G,V,Block#block{attributes=NewAtt}),
955
pp_debug("~n Not Downsafe at L~w: ~w",[V,NewNDS]),
956
%%io:format(standard_io,"~n Not Downsafe at L~w: ~w",[V,NewNDS]),
957
perform_downsafety(MPs,G,XG).
959
parse_keys([], _Maps, _OutEdges, _G, _Defs, NDS, _XsiG) ->
961
parse_keys([M|Ms], Maps, OutEdges, G, Defs, NDS, XsiG) ->
962
KillerSet = gb_trees:get(M,Maps),
963
%%pp_debug("~n Inspection ~w -> ~w",[M,KillerSet]),
964
TempSet = ?SETS:intersection(KillerSet,Defs),
965
NewNDS = case ?SETS:size(TempSet) of
966
0 -> getNDS(M,KillerSet,NDS,OutEdges,G,XsiG);
968
%% One Xsi which has M as operand has killed it
969
%% M is then Downsafe
970
%% and is not added to the NotDownsafeSet (NDS)
973
parse_keys(Ms, Maps, OutEdges, G, Defs, NewNDS, XsiG).
975
getNDS(_M,_KillerSet,NDS,[],_G,_XsiG) ->
977
getNDS(M,KillerSet,NDS,[E|Es],G,XsiG) ->
978
{_EE,_V1,_V2,Label} = ?GRAPH:edge(G,E),
979
Set = ?SETS:intersection(KillerSet,Label),
980
%% pp_debug("~n ######## Intersection between KillerSet: ~w and Label: ~w",[KillerSet,Label]),
981
%% pp_debug("~n ######## ~w",[Set]),
982
case ?SETS:size(Set) of
985
?SETS:add_element(M,NDS);
987
%% Try the other edges
988
getNDS(M,KillerSet,NDS,Es,G,XsiG)
991
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
992
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% WILL BE AVAILABLE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
993
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
995
perform_will_be_available(XsiGraph,CFGGraph,Options) ->
996
Keys = ?GRAPH:vertices(XsiGraph),
997
pp_debug("~n############ Can Be Available ##########~n",[]),
998
?option_time(perform_can_be_available(Keys,XsiGraph,CFGGraph),"RTL A-SSAPRE WillBeAvailable - Compute CanBeAvailable",Options),
999
pp_debug("~n############ Later ##########~n",[]),
1000
?option_time(perform_later(Keys,XsiGraph),"RTL A-SSAPRE WillBeAvailable - Compute Later",Options).
1002
perform_can_be_available([],_XsiGraph,_CFGGraph) -> ok;
1003
perform_can_be_available([Key|Keys],XsiGraph,CFGGraph) ->
1004
{V,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
1007
{_VV,Block} = ?GRAPH:vertex(CFGGraph,Xsi#xsi.label),
1008
Att = Block#block.attributes,
1009
NDS = Att#mp.ndsSet,
1010
OpList = ?SETS:from_list(xsi_oplist(Xsi)),
1011
Set = ?SETS:intersection(NDS,OpList),
1012
case ?SETS:size(Set) of
1014
?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{cba=true}),
1015
perform_can_be_available(Keys,XsiGraph,CFGGraph);
1017
LIST = [X || #temp{key=X} <- ?SETS:to_list(Set)],
1020
?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{cba=false}),
1021
ImmediateParents = ?GRAPH:in_neighbours(XsiGraph,Key),
1022
propagate_cba(ImmediateParents,XsiGraph,Xsi#xsi.def,CFGGraph);
1026
perform_can_be_available(Keys,XsiGraph,CFGGraph)
1028
_ -> %% True or False => recurse
1029
perform_can_be_available(Keys,XsiGraph,CFGGraph)
1032
propagate_cba([],_XG,_Def,_CFGG) -> ok;
1033
propagate_cba([IPX|IPXs],XsiGraph,XsiDef,CFGGraph) ->
1034
{V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX),
1035
{_VV,Block} = ?GRAPH:vertex(CFGGraph,IPXsi#xsi.label),
1036
Att = Block#block.attributes,
1037
NDS = Att#mp.ndsSet,
1038
List = ?SETS:to_list(?SETS:intersection(NDS,?SETS:from_list(xsi_oplist(IPXsi)))),
1039
case IPXsi#xsi.cba of
1042
case lists:keymember(XsiDef,#xsi_op.op,List) of
1044
?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{cba=false}),
1045
ImmediateParents = ?GRAPH:in_neighbours(XsiGraph,IPX),
1046
propagate_cba(ImmediateParents,XsiGraph,IPXsi#xsi.def,CFGGraph);
1051
propagate_cba(IPXs,XsiGraph,XsiDef,CFGGraph).
1053
perform_later([], _XsiGraph) -> ok;
1054
perform_later([Key|Keys], XsiGraph) ->
1055
{V,Xsi} = ?GRAPH:vertex(XsiGraph,Key),
1056
%% pp_debug("~n DEBUG : inspecting later of ~w (~w)~n",[Key,Xsi#xsi.later]),
1057
case Xsi#xsi.later of
1059
OpList = xsi_oplist(Xsi),
1060
case parse_ops(OpList,fangpi) of %% It means "fart" in chinese :D
1062
perform_later(Keys,XsiGraph);
1066
?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true});
1068
?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=true});
1070
?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=false,wba=false})
1072
AllParents = digraph_utils:reaching([Key],XsiGraph),
1073
pp_debug("~nPropagating to all parents of t~w: ~w",[Key,AllParents]),
1074
propagate_later(AllParents,XsiGraph),
1075
perform_later(Keys,XsiGraph);
1076
_ -> %% Just contains bottoms and/or expressions
1077
?GRAPH:add_vertex(XsiGraph,V,Xsi#xsi{later=true}),
1078
perform_later(Keys,XsiGraph)
1080
_ -> %% True or False => recurse
1081
perform_later(Keys,XsiGraph)
1084
propagate_later([], _XG) -> ok;
1085
propagate_later([IPX|IPXs], XsiGraph) ->
1086
{V,IPXsi} = ?GRAPH:vertex(XsiGraph,IPX),
1087
case IPXsi#xsi.later of
1089
pp_debug("~nThrough propagation, later of t~w is already reset",[IPX]),
1090
propagate_later(IPXs,XsiGraph);
1092
pp_debug("~nThrough propagation, resetting later of t~w",[IPX]),
1093
case IPXsi#xsi.cba of
1095
?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true});
1097
?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=true});
1099
?GRAPH:add_vertex(XsiGraph,V,IPXsi#xsi{later=false,wba=false})
1101
propagate_later(IPXs,XsiGraph)
1104
parse_ops([], Res) ->
1106
parse_ops([Op|Ops], Res) ->
1107
case Op#xsi_op.op of
1110
parse_ops(Ops,NewRes);
1119
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1120
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CODE MOTION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1121
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1123
perform_code_motion([], Cfg, _XsiG) ->
1125
perform_code_motion([L|Labels], Cfg, XsiG) ->
1126
Code=?BB:code(?CFG:bb(Cfg,L)),
1127
pp_debug("~n################ Code Motion in L~w~n",[L]),
1128
pp_debug("~nCode to move ~n",[]),
1129
pp_instrs(Code,XsiG),
1130
NewCfg = code_motion_in_block(L,Code,Cfg,XsiG,[],gb_trees:empty()),
1131
pp_debug("~n################ Code Motion successful in L~w~n",[L]),
1132
perform_code_motion(Labels,NewCfg,XsiG).
1134
code_motion_in_block(Label,[],Cfg,_XsiG,Visited,InsertionsAcc) ->
1135
InsertionsAlong = gb_trees:keys(InsertionsAcc),
1136
Code = lists:reverse(Visited),
1137
NewBB = ?BB:mk_bb(Code),
1138
Cfg2 = ?CFG:bb_add(Cfg,Label,NewBB),
1139
%% Must come after the bb_add, since redirect will update the Phis too...
1140
Cfg3 = make_insertions(Label,InsertionsAlong,InsertionsAcc,Cfg2),
1141
%%pp_debug("~nChecking the Code at L~w:~n~p",[Label,?BB:code(?CFG:bb(Cfg3,Label))]),
1143
code_motion_in_block(L,[Inst|Insts],Cfg,XsiG,Visited,InsertionsAcc) ->
1144
pp_debug("~nInspecting Inst : ~n",[]),pp_instr(Inst,XsiG),
1147
Def = Inst#pre_candidate.def,
1148
Alu = Inst#pre_candidate.alu,
1154
{_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
1158
Dst = ?RTL:alu_dst(Alu),
1159
Move = ?RTL:mk_move(Dst,Def#temp.var),
1160
pp_instr(Inst#pre_candidate.alu,nil),pp_debug(" ==> ",[]),pp_instr(Move,nil),
1161
%% Counting redundancies
1167
_ -> %% Def is a real variable
1169
Dst = ?RTL:alu_dst(Alu),
1170
Move = ?RTL:mk_move(Dst,Def),
1171
pp_instr(Alu,nil), pp_debug(" ==> ",[]),pp_instr(Move,nil),
1172
%% Counting redundancies
1176
code_motion_in_block(L,Insts,Cfg,XsiG,[InstToAdd|Visited],InsertionsAcc);
1178
Key = Inst#xsi_link.number,
1179
{_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
1182
%% Xsi is a WBA, it might trigger insertions
1183
OpList = xsi_oplist(Xsi),
1184
pp_debug(" This Xsi is a 'Will be available'",[]),
1185
%% Cleaning the instruction
1186
Expr = prepare_inst(Xsi#xsi.inst),
1187
{NewOpList,NewInsertionsAcc} = get_insertions(OpList,[],InsertionsAcc,Visited,Expr,XsiG),
1188
%% Making Xsi a Phi with Oplist
1189
PhiOpList = [{Pred,Var} || #xsi_op{pred=Pred,op=Var} <- NewOpList],
1191
Phi = ?RTL:phi_arglist_update(?RTL:mk_phi(Def#temp.var),PhiOpList),
1192
pp_debug("~n Xsi is turned into Phi : ~w",[Phi]),
1193
code_motion_in_block(L,Insts,Cfg,XsiG,[Phi|Visited],NewInsertionsAcc);
1195
pp_debug(" This Xsi is not a 'Will be available'",[]),
1196
code_motion_in_block(L,Insts,Cfg,XsiG,Visited,InsertionsAcc)
1199
%% code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc);
1201
%% Other instructions.... Phis too
1202
code_motion_in_block(L,Insts,Cfg,XsiG,[Inst|Visited],InsertionsAcc)
1205
prepare_inst(Expr) ->
1206
S1 = ?RTL:alu_src1(Expr),
1207
S2 = ?RTL:alu_src2(Expr),
1208
NewInst = case S1 of
1209
#temp{} -> ?RTL:alu_src1_update(Expr,S1#temp.var);
1212
NewExpr = case S2 of
1213
#temp{} -> ?RTL:alu_src2_update(NewInst,S2#temp.var);
1218
get_insertions([],OpAcc,InsertionsAcc,_Visited,_Expr,_XsiG) ->
1219
{OpAcc,InsertionsAcc};
1220
get_insertions([XsiOp|Ops],OpAcc,InsertionsAcc,Visited,Expr,XsiG) ->
1221
Pred = XsiOp#xsi_op.pred,
1222
Op = XsiOp#xsi_op.op,
1225
case gb_trees:lookup(Pred,InsertionsAcc) of
1226
{value,Insertion} ->
1227
From = Insertion#insertion.from,
1228
case lists:keysearch(Op,1,From) of
1230
pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
1231
Dst = Op#bottom.var,
1232
Expr2 = ?RTL:alu_dst_update(Expr,Dst),
1233
Inst = manufacture_computation(Pred,Expr2,Visited),
1234
Code = Insertion#insertion.code,
1235
NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]},
1236
NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc);
1238
pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
1240
NewInsertionsAcc = InsertionsAcc
1243
pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
1244
Dst = Op#bottom.var,
1245
Expr2 = ?RTL:alu_dst_update(Expr,Dst),
1246
Inst = manufacture_computation(Pred,Expr2,Visited),
1247
NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]},
1248
NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc)
1251
case gb_trees:lookup(Pred,InsertionsAcc) of
1252
{value,Insertion} ->
1253
From = Insertion#insertion.from,
1254
case lists:keysearch(Op,1,From) of
1256
pp_debug("~nThere have been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
1257
Dst = Op#const_expr.var,
1258
Val = Op#const_expr.value,
1259
Inst = ?RTL:mk_move(Dst,Val),
1260
Code = Insertion#insertion.code,
1261
NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]},
1262
NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc);
1264
pp_debug("~nThere have been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
1266
NewInsertionsAcc = InsertionsAcc
1269
pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
1270
Dst = Op#const_expr.var,
1271
Val = Op#const_expr.value,
1272
Inst = ?RTL:mk_move(Dst,Val),
1273
NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]},
1274
NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc)
1277
%% We treat expressions like bottoms
1278
%% The value must be recomputed, and therefore not available...
1279
case gb_trees:lookup(Pred,InsertionsAcc) of
1280
{value,Insertion} ->
1281
From = Insertion#insertion.from,
1282
case lists:keysearch(Op,1,From) of
1284
pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
1286
Expr2 = ?RTL:alu_dst_update(Expr,Dst),
1287
Inst = manufacture_computation(Pred,Expr2,Visited),
1288
Code = Insertion#insertion.code,
1289
NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]},
1290
NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc);
1292
pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too | Op=",[Pred]),pp_arg(Op),
1294
NewInsertionsAcc = InsertionsAcc
1297
pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course)| Op=",[Pred]),pp_arg(Op),
1299
Expr2 = ?RTL:alu_dst_update(Expr,Dst),
1300
Inst = manufacture_computation(Pred,Expr2,Visited),
1301
NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]},
1302
NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc)
1305
case gb_trees:lookup(Pred,InsertionsAcc) of
1306
{value,Insertion} ->
1307
From = Insertion#insertion.from,
1308
case lists:keysearch(Op,1,From) of
1310
pp_debug("~nThere has been insertions along the edge L~w already, but not for that operand | Op=",[Pred]),pp_arg(Op),
1312
{_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
1315
pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]),
1317
NewInsertionsAcc = InsertionsAcc;
1319
pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]),
1320
Dst = ?RTL:mk_new_var(),
1321
Expr2 = ?RTL:alu_dst_update(Expr,Dst),
1322
Inst = manufacture_computation(Pred,Expr2,Visited),
1323
Code = Insertion#insertion.code,
1324
NewInsertion = Insertion#insertion{from=[{Op,Dst}|From],code=[Inst|Code]},
1325
NewInsertionsAcc = gb_trees:update(Pred,NewInsertion,InsertionsAcc)
1328
pp_debug("~nThere has been insertions along the edge L~w already, and for that operand too (Op=~w)",[Pred,Op]),
1329
pp_debug("~nThis means, this temp is a WBA Xsi's definition",[]),
1331
NewInsertionsAcc = InsertionsAcc
1334
pp_debug("~nThere has been no insertion along the edge L~w, (and not for that operand, of course | Op=",[Pred]),pp_arg(Op),
1336
{_V,Xsi} = ?GRAPH:vertex(XsiG,Key),
1339
pp_debug("~nBut the operand is a WBA Xsi: no need for insertion",[]),
1341
NewInsertionsAcc = InsertionsAcc;
1343
pp_debug("~nBut the operand is a NOT WBA Xsi: we must make an insertion",[]),
1344
Dst = ?RTL:mk_new_var(),
1345
Expr2 = ?RTL:alu_dst_update(Expr,Dst),
1346
Inst = manufacture_computation(Pred,Expr2,Visited),
1347
NewInsertion = #insertion{from=[{Op,Dst}],code=[Inst]},
1348
NewInsertionsAcc = gb_trees:insert(Pred,NewInsertion,InsertionsAcc)
1352
pp_debug("~nThe operand (Op=",[]),pp_arg(Op),pp_debug(") is a real variable, no need for insertion along L~w",[Pred]),
1354
NewInsertionsAcc = InsertionsAcc
1356
NewXsiOp = XsiOp#xsi_op{op=Dst},
1357
get_insertions(Ops, [NewXsiOp|OpAcc], NewInsertionsAcc, Visited, Expr, XsiG).
1359
manufacture_computation(_Pred, Expr, []) ->
1360
pp_debug("~n Manufactured computation : ~w", [Expr]),
1362
manufacture_computation(Pred, Expr, [I|Rest]) ->
1363
%%pp_debug("~n Expr = ~w",[Expr]),
1364
SRC1 = ?RTL:alu_src1(Expr),
1365
SRC2 = ?RTL:alu_src2(Expr),
1368
exit({?MODULE,should_not_be_a_xsi_link,{"Why the hell do we still have a xsi link???",I}});
1370
exit({?MODULE,should_not_be_a_xsi,{"Why the hell do we still have a xsi ???",I}});
1372
DST = ?RTL:phi_dst(I),
1373
Arg = ?RTL:phi_arg(I,Pred),
1374
NewInst = case DST==SRC1 of
1375
true -> ?RTL:alu_src1_update(Expr,Arg);
1378
NewExpr = case DST==SRC2 of
1379
true -> ?RTL:alu_src2_update(NewInst,Arg);
1382
manufacture_computation(Pred,NewExpr,Rest)
1385
make_insertions(_L, [], _ITree, Cfg) ->
1387
make_insertions(L, [OldPred|Is], ITree, Cfg) ->
1388
NewPred = ?RTL:label_name(?RTL:mk_new_label()),
1389
I = gb_trees:get(OldPred, ITree),
1390
CodeToInsert = lists:reverse([?RTL:mk_goto(L)|I#insertion.code]),
1391
BBToInsert = ?BB:mk_bb(CodeToInsert),
1392
NewCfg = ?CFG:bb_insert_between(Cfg, NewPred, BBToInsert, OldPred, L),
1393
make_insertions(L, Is, ITree, NewCfg).
1395
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1396
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% XSI INTERFACE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1397
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1399
xsi_oplist(#xsi{opList=OpList}) ->
1400
case OpList of undefined -> [] ; _ -> OpList end.
1401
xsi_arg(Xsi, Pred) ->
1402
case lists:keysearch(Pred, #xsi_op.pred ,xsi_oplist(Xsi)) of
1404
undetermined_operand;
1408
xsi_arg_update(Xsi, Pred, Op) ->
1409
NewOpList = lists:keyreplace(Pred, #xsi_op.pred, xsi_oplist(Xsi),
1410
#xsi_op{pred=Pred,op=Op}),
1411
Xsi#xsi{opList=NewOpList}.
1413
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1414
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PRETTY-PRINTING %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1415
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1417
-ifndef(SSAPRE_DEBUG).
1419
pp_debug(_,_) -> ok.
1420
%%pp_cfg(Cfg,_) -> ?CFG:pp(Cfg).
1422
pp_instr(_,_) -> ok.
1423
pp_instrs(_,_) -> ok.
1427
pp_xsigraph(_) -> ok.
1428
pp_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)]).
1438
pp_debug(Str, Args) ->
1439
io:format(standard_io, Str, Args).
1441
pp_cfg(Cfg, Graph) ->
1442
Labels = ?CFG:preorder(Cfg),
1443
pp_blocks(Labels, Cfg, Graph).
1445
pp_blocks([], _, _) ->
1447
pp_blocks([L|Ls], Cfg, Graph) ->
1448
Code = hipe_bb:code(?CFG:bb(Cfg,L)),
1449
io:format(standard_io,"~n########## Label L~w~n", [L]),
1450
pp_instrs(Code, Graph),
1451
pp_blocks(Ls, Cfg, Graph).
1455
pp_instrs([I|Is], Graph) ->
1457
pp_instrs(Is, Graph).
1459
pp_xsi_link(Key, Graph) ->
1460
{_Key,Xsi} = ?GRAPH:vertex(Graph, Key),
1464
io:format(standard_io, " [L~w] ", [Xsi#xsi.label]),
1465
io:format(standard_io, "[", []), pp_expr(Xsi#xsi.inst),
1466
io:format(standard_io, "] Xsi(", []), pp_xsi_args(xsi_oplist(Xsi)),
1467
io:format(standard_io, ") (", []), pp_xsi_def(Xsi#xsi.def),
1468
io:format(standard_io, ") cba=~w, later=~w | wba=~w~n", [Xsi#xsi.cba,Xsi#xsi.later,Xsi#xsi.wba]).
1470
pp_instr(I,Graph) ->
1473
io:format(standard_io, " ", []),
1474
pp_arg(?RTL:alu_dst(I)),
1475
io:format(standard_io, " <- ", []),
1477
io:format(standard_io, "~n", []);
1479
case catch ?RTL:pp_instr(standard_io, I) of
1487
pp_xsi_link(I#xsi_link.number,Graph);
1489
io:format(standard_io,"*** ~w ***~n", [I])
1497
A = I#pre_candidate.alu,
1498
io:format(standard_io, " ", []),
1499
pp_arg(?RTL:alu_dst(A)),
1500
io:format(standard_io, " <- ", []),pp_expr(A),
1501
io:format(standard_io, " [ ", []),pp_arg(I#pre_candidate.def),
1502
%%io:format(standard_io, "~w", [I#pre_candidate.def]),
1503
io:format(standard_io, " ]~n",[]).
1506
pp_arg(?RTL:alu_dst(I)),
1507
io:format(standard_io, " <- ", []),
1508
pp_arg(?RTL:alu_src1(I)),
1509
io:format(standard_io, " ~w ", [?RTL:alu_op(I)]),
1510
pp_arg(?RTL:alu_src2(I)).
1515
io:format(standard_io, "_|_", []);
1517
io:format(standard_io, "_|_:~w (", [Arg#bottom.key]),pp_arg(Arg#bottom.var),io:format(standard_io,")",[]);
1521
io:format(standard_io,"#",[]),pp_expr(Arg#eop.expr),io:format(standard_io,"(",[]),pp_arg(Arg#eop.var),io:format(standard_io,")#",[]);
1523
io:format(standard_io,"*",[]),pp_arg(Arg#const_expr.var),io:format(standard_io," -> ",[]),pp_arg(Arg#const_expr.value),io:format(standard_io,"*",[]);
1525
io:format(standard_io, "...", []); %%"undefined", []);
1531
?RTL:pp_arg(standard_io, Arg)
1537
pp_args(undefined) ->
1538
io:format(standard_io, "...,...,...", []);
1543
io:format(standard_io, ", ", []),
1546
pp_xsi_args([]) -> ok;
1547
pp_xsi_args([XsiOp]) ->
1548
io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]),
1549
pp_arg(XsiOp#xsi_op.op),
1550
io:format(standard_io, "}", []);
1551
pp_xsi_args([XsiOp|Args]) ->
1552
io:format(standard_io, "{~w| ", [XsiOp#xsi_op.pred]),
1553
pp_arg(XsiOp#xsi_op.op),
1554
io:format(standard_io, "}, ", []),
1556
pp_xsi_args(Args) ->
1562
io:format(standard_io, "t~w (", [D]),pp_arg(V),io:format(standard_io,")",[]).
1565
Vertices = lists:sort(?GRAPH:vertices(G)),
1566
io:format(standard_io, "Size of the CFG Graph: ~w ~n", [length(Vertices)]),
1567
pp_cfgvertex(Vertices, G).
1570
Vertices = lists:sort(?GRAPH:vertices(G)),
1571
io:format(standard_io, "Size of the Xsi Graph: ~w ~n", [length(Vertices)]),
1572
pp_xsivertex(Vertices,G).
1574
pp_xsivertex([], _G) ->
1576
pp_xsivertex([Key|Keys], G) ->
1577
{V,Xsi} = ?GRAPH:vertex(G, Key),
1578
OutNeighbours = ?GRAPH:out_neighbours(G, V),
1579
pp_debug(" ~w -> ~w", [V,OutNeighbours]), pp_xsi(Xsi),
1580
pp_xsivertex(Keys, G).
1582
pp_cfgvertex([], _G) ->
1584
pp_cfgvertex([Key|Keys], G) ->
1585
{V,Block} = ?GRAPH:vertex(G,Key),
1586
case Block#block.type of
1588
pp_debug("~n Block ~w's attributes: ~n", [V]),
1589
pp_attributes(Block),
1590
pp_debug("~n Block ~w's edges: ~n", [V]),
1591
pp_edges(G, ?GRAPH:in_edges(G,Key), ?GRAPH:out_edges(G,Key));
1595
pp_cfgvertex(Keys, G).
1597
pp_attributes(Block) ->
1598
Att = Block#block.attributes,
1603
pp_debug(" Maps: ~n",[]),pp_maps(gb_trees:keys(Att#mp.maps),Att#mp.maps),
1604
pp_debug(" Uses: ~n",[]),pp_uses(gb_trees:keys(Att#mp.uses),Att#mp.uses),
1605
pp_debug(" Defs: ~w~n",[Att#mp.defs]),
1606
pp_debug(" Xsis: ~w~n",[Att#mp.xsis]),
1607
pp_debug(" NDS : ",[]),pp_nds(?SETS:to_list(Att#mp.ndsSet))
1610
pp_maps([], _Maps) -> ok;
1611
pp_maps([K|Ks], Maps) ->
1612
pp_debug(" ",[]),pp_arg(K#xsi_op.op),pp_debug("-> ~w~n",[?SETS:to_list(gb_trees:get(K,Maps))]),
1615
pp_uses([], _Maps) -> ok;
1616
pp_uses([K|Ks], Maps) ->
1617
pp_debug(" ~w -> ~w~n",[K,?SETS:to_list(gb_trees:get(K,Maps))]),
1620
pp_nds([]) -> pp_debug("~n",[]);
1621
pp_nds(undefined) -> pp_debug("None",[]);
1623
pp_arg(K#xsi_op.op), pp_debug("~n",[]);
1625
pp_arg(K#xsi_op.op), pp_debug(", ",[]),
1628
pp_edges(_G, [], []) -> ok;
1629
pp_edges(G, [], [OUT|OUTs]) ->
1630
{_E,V1,V2,Label} = ?GRAPH:edge(G,OUT),
1631
pp_debug(" Out edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]),
1632
pp_edges(G, [], OUTs);
1633
pp_edges(G, [IN|INs], Outs) ->
1634
{_E,V1,V2,Label} = ?GRAPH:edge(G,IN),
1635
pp_debug(" In edge ~w -> ~w (~w)~n", [V1,V2,?SETS:to_list(Label)]),
1636
pp_edges(G, INs, Outs).
1640
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1641
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1642
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1645
put({ssapre_temp,temp_count}, 0),
1646
put({ssapre_index,index_count}, 0).
1649
V = get({ssapre_index,index_count}),
1650
put({ssapre_index,index_count}, V+1),
1651
#bottom{key=V,var=?RTL:mk_new_var()}.
1654
V = get({ssapre_temp,temp_count}),
1655
put({ssapre_temp,temp_count}, V+1),
1656
#temp{key=V,var=?RTL:mk_new_var()}.
1658
init_redundancy_count() ->
1659
put({ssapre_redundancy,redundancy_count}, 0).
1662
V = get({ssapre_redundancy,redundancy_count}),
1663
put({ssapre_redundancy,redundancy_count}, V+1).
1665
get_redundancy_count() ->
1666
get({ssapre_redundancy,redundancy_count}).
1668
%% //////////////////
1669
%% // End of the file
added
removed
lib/hipe/rtl/hipe_rtl_ssapre.erl
