← Back to branch summary

~ubuntu-branches/debian/squeeze/erlang/squeeze

« back to all changes in this revision

Viewing changes to lib/hipe/rtl/hipe_rtl_prop.erl

  • Committer: Bazaar Package Importer
  • Author(s): Erlang Packagers, Sergei Golovan
  • Date: 2006-12-03 17:07:44 UTC
  • mfrom: (2.1.11 feisty)
  • Revision ID: james.westby@ubuntu.com-20061203170744-rghjwupacqlzs6kv
Tags: 1:11.b.2-4
[ Sergei Golovan ]
Fixed erlang-base and erlang-base-hipe prerm scripts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/hipe/rtl/hipe_rtl_prop.erl
1
1
%% -*- erlang-indent-level: 2 -*-
2
2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3
3
%%
4
 
%% Semi-local copy propagation, constant propagation, constant folding
 
4
%% Semi-local copy propagation, constant propagation, constant folding,
5
5
%% and dead code removal.
6
6
%%
7
7
%% Works on extended basic blocks. No iteration is done at this point.
8
8
%%
9
 
%% The environment binds (rtl) variables to:
 
9
%% The environment binds (RTL) variables to:
10
10
%%    - constants
11
11
%%    - variables
12
12
%%
13
13
 
14
14
-module(hipe_rtl_prop).
15
 
-export([cfg/1, do/1]).
 
15
-export([do/1]).
 
16
 
16
17
-include("../main/hipe.hrl").
17
 
 
18
 
cfg(CFG) ->
19
 
  ?opt_start_timer("Rtl Prop"),
20
 
  ?opt_start_timer("EBBs"),
21
 
  EBBs = hipe_rtl_ebb:cfg(CFG),
22
 
  ?opt_stop_timer("EBBs"),
23
 
  ?opt_start_timer("Prop"),
24
 
  CFG0 = prop_ebbs(EBBs, CFG),
25
 
  ?opt_stop_timer("Prop"),
26
 
  ?opt_start_timer("Liveness"),
27
 
  Liveness = hipe_rtl_liveness:analyze(CFG0),
28
 
  ?opt_stop_timer("Liveness"),
29
 
  ?opt_start_timer("Dead code"),
30
 
  EBBs2 = hipe_rtl_ebb:cfg(CFG0),
31
 
  CFG1 = dead_code_ebbs(EBBs2, CFG0, Liveness),
32
 
  ?opt_stop_timer("Dead code"),
33
 
  ?opt_stop_timer("RtlProp"),
34
 
  CFG1.
35
 
 
36
 
 
37
 
%%
38
 
%% Iterate over the extended basic blocks of a cfg.
39
 
%%
40
 
 
41
 
prop_ebbs([], CFG) ->
42
 
  CFG;
43
 
prop_ebbs([Ebb|Ebbs], CFG) ->
44
 
  CFG0 = prop_ebb(Ebb, new_env(), CFG),
45
 
  prop_ebbs(Ebbs, CFG0).
46
 
 
47
 
 
48
 
%%
49
 
%% If Lbl is a member of the extended block Ebb. Then propagate info 
50
 
%% and continue with its successors.
51
 
%%
52
 
 
53
 
prop_ebb(Ebb, Env, CFG) ->
54
 
  case hipe_rtl_ebb:type(Ebb) of
55
 
    node ->
56
 
      Lbl = hipe_rtl_ebb:node_label(Ebb),
57
 
      BB = hipe_rtl_cfg:bb(CFG, Lbl),
58
 
      {NewCode, NewEnv} = prop_instrs(hipe_bb:code(BB), Env),
59
 
      NewBB = hipe_bb:code_update(BB, NewCode),
60
 
      NewCFG = hipe_rtl_cfg:bb_update(CFG, Lbl, NewBB),
61
 
      Succ = hipe_rtl_ebb:node_successors(Ebb),
62
 
      prop_succ(Succ, NewEnv, NewCFG);
63
 
    leaf ->
64
 
      CFG
65
 
  end.
66
 
 
67
 
 
68
 
prop_succ([], _Env, CFG) ->
69
 
  CFG;
70
 
prop_succ([EBB|EBBs], Env, CFG) ->
71
 
  NewCFG = prop_ebb(EBB, Env, CFG),
72
 
  prop_succ(EBBs, Env, NewCFG).
73
 
 
74
 
prop_instrs(Is, Env) ->
75
 
  {NewIs, NewEnv} = lists:mapfoldl(fun prop_instr/2, Env, Is),
76
 
  {lists:flatten(NewIs), NewEnv}.
77
 
 
78
 
 
79
 
%prop_instrs([], Env) ->
80
 
%  {[], Env};
81
 
%prop_instrs([I|Is], Env) ->
82
 
%  {NewI, Env0} = prop_instr(I, Env),
83
 
%  {NewIs, NewEnv} = prop_instrs(Is, Env0),
84
 
%  %% io:format("I ~w to ~w\n",[I,NewI]),
85
 
%  case NewI of
86
 
%    [_|_] -> {NewI++NewIs, NewEnv};    %% alub -> [move, goto]
87
 
%    _ -> {[NewI|NewIs], NewEnv}
88
 
%  end.
89
 
 
 
18
-include("hipe_rtl.hrl").
 
19
 
 
20
-record(aliased_var, {name}).
 
21
 
 
22
%%=====================================================================
 
23
 
 
24
do(CFG) ->
 
25
  %% io:format("%%------------- RTL code in beginning of rtl_prop -----------\n"),
 
26
  %% hipe_rtl_cfg:pp(CFG),
 
27
  CFG1 = prop(CFG),
 
28
  %% io:format("%%------------- After prop -----------\n"),
 
29
  %% hipe_rtl_cfg:pp(CFG1),
 
30
  CFG2 = hipe_rtl_cfg:remove_trivial_bbs(CFG1),
 
31
  %% io:format("%%------------- After remove_trivial_bbs -----------\n"),
 
32
  Liveness = hipe_rtl_liveness:analyze(CFG2),
 
33
  EBBs2 = hipe_rtl_ebb:cfg(CFG2),
 
34
  CFG3 = dead_code_ebbs(EBBs2, CFG2, Liveness),
 
35
  %% io:format("%%------------- After dead_code_ebbs -----------\n"),
 
36
  %% hipe_rtl_cfg:pp(CFG3),
 
37
  CFG4 = remove_loads(CFG3),
 
38
  %% io:format("%%------------- After remove_loads -----------\n"),
 
39
  %% hipe_rtl_cfg:pp(CFG4),
 
40
  CFG5 = hipe_rtl_cfg:remove_unreachable_code(CFG4),
 
41
  %% io:format("%%------------- After remove_unreachable_code -----------\n"),
 
42
  %% hipe_rtl_cfg:pp(CFG5),
 
43
  CFG6 = hipe_rtl_cfg:remove_trivial_bbs(CFG5),
 
44
  %% io:format("%%------------- After remove_trivial_bbs -----------\n"),
 
45
  %% hipe_rtl_cfg:pp(CFG6),
 
46
  CFG7 = remove_stores(CFG6),
 
47
  %% io:format("%%------------- After remove_stores -----------\n"),
 
48
  %% hipe_rtl_cfg:pp(CFG7),
 
49
  CFG7.
 
50
 
 
51
prop(CFG) ->
 
52
  Start = hipe_rtl_cfg:start_label(CFG),
 
53
  Tree = gb_trees:empty(),
 
54
  PredMap = hipe_rtl_cfg:pred_map(CFG),
 
55
  Info = fix_point([Start], CFG, PredMap, Tree),
 
56
  pass_through([Start], CFG, PredMap, Info, gb_sets:singleton(Start)).
90
57
 
91
58
%%
92
59
%% Propagate copies and constants for one instruction.
94
61
 
95
62
prop_instr(I, Env) ->
96
63
  NewEnv = unbind(hipe_rtl:defines(I), Env),
97
 
  case hipe_rtl:type(I) of
98
 
    move ->
 
64
  case I of
 
65
    #move{} ->
99
66
      Srcs = [hipe_rtl:move_src(I)],
100
67
      Dsts = [hipe_rtl:move_dst(I)],
101
68
      bind_all(Srcs, Dsts, I, NewEnv);
102
 
    multimove ->
103
 
      Srcs = hipe_rtl:multimove_src(I),
104
 
      Dsts = hipe_rtl:multimove_dst(I),
 
69
    #multimove{} ->
 
70
      Srcs = hipe_rtl:multimove_srclist(I),
 
71
      Dsts = hipe_rtl:multimove_dstlist(I),
105
72
      bind_all(Srcs, Dsts, I, NewEnv);
106
 
    fconv ->
 
73
    #fconv{} ->
107
74
      {I, Env};
108
75
    _ ->
109
76
      Uses = hipe_rtl:uses(I),
113
80
      eval(NewI, NewEnv)
114
81
  end.
115
82
 
116
 
 
117
83
map_all([], _Env) ->
118
84
  [];
119
85
map_all([V|Vs], Env) ->
120
86
  [{V, lookup(V, Env)} | map_all(Vs, Env)].
121
87
 
122
 
 
123
88
bind_all(Srcs, Dsts, I, Env) ->
124
89
  bind_all(Srcs, Dsts, I, Env, Env).
125
90
 
126
 
%%%
 
91
%%
127
92
%% We have two envs, Env where we do lookups and
128
93
%%                   NewEnv where the new bindings are entered.
129
94
bind_all([Src|Srcs], [Dst|Dsts], I, Env, NewEnv) ->
144
109
bind_all([], [], I, _, Env) ->
145
110
  {I, Env}.
146
111
 
147
 
 
148
112
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
149
113
%%
150
114
%% Evaluate an instruction. Returns {NewI, NewEnv}.
151
115
%%
152
116
 
153
117
eval(I, Env) ->
154
 
  case hipe_rtl:type(I) of
155
 
    alu ->
 
118
  case I of
 
119
    #alu{} ->
156
120
      Src1 = hipe_rtl:alu_src1(I),
157
121
      Src2 = hipe_rtl:alu_src2(I),
158
122
      case {hipe_rtl:is_imm(Src1), hipe_rtl:is_imm(Src2)} of
165
129
        _ ->
166
130
          {I, Env}
167
131
      end;
168
 
    alub ->
 
132
    #alub{} ->
169
133
      Src1 = hipe_rtl:alub_src1(I),
170
134
      Src2 = hipe_rtl:alub_src2(I),
171
135
      case {hipe_rtl:is_imm(Src1), hipe_rtl:is_imm(Src2)} of
174
138
          Val2 = hipe_rtl:imm_value(Src2),
175
139
          Op = hipe_rtl:alub_op(I),
176
140
          Cond = hipe_rtl:alub_cond(I),
177
 
          case hipe_rtl_arith:eval_alub(Op, Cond, Val1, Val2) of
 
141
          case hipe_rtl_arch:eval_alub(Op, Cond, Val1, Val2) of
178
142
            {Val3, Bool} ->
179
143
              Src3 = hipe_rtl:mk_imm(Val3),
180
144
              Label =
192
156
        _ ->
193
157
          {I, Env}
194
158
      end;
195
 
    branch ->
 
159
    #branch{} ->
196
160
      Src1 = hipe_rtl:branch_src1(I),
197
161
      Src2 = hipe_rtl:branch_src2(I),
198
162
      case {hipe_rtl:is_imm(Src1), hipe_rtl:is_imm(Src2)} of
199
163
        {true, true} ->
200
 
          case hipe_rtl_arith:eval_cond(hipe_rtl:branch_cond(I), 
201
 
                                        hipe_rtl:imm_value(Src1), 
202
 
                                        hipe_rtl:imm_value(Src2)) of
 
164
          case hipe_rtl_arch:eval_cond(hipe_rtl:branch_cond(I), 
 
165
                                       hipe_rtl:imm_value(Src1), 
 
166
                                       hipe_rtl:imm_value(Src2)) of
203
167
            true ->
204
168
              {hipe_rtl:mk_goto(hipe_rtl:branch_true_label(I)), Env};
205
169
            false ->
208
172
        _ ->
209
173
          {I, Env}
210
174
      end;
211
 
    enter ->
 
175
    #enter{} ->
212
176
      {I, new_env()};
213
 
    return ->
 
177
    #return{} ->
214
178
      {I, new_env()};
215
179
    _ ->
216
180
      {I, Env}
217
181
  end.
218
182
 
219
 
 
220
183
eval_constant_alu(Op, Arg1, Arg2) ->
221
 
  {Res,_N,_Z,_V,_C} = hipe_rtl_arith:eval_alu(Op,Arg1,Arg2),
 
184
  {Res,_N,_Z,_V,_C} = hipe_rtl_arch:eval_alu(Op, Arg1, Arg2),
222
185
  hipe_rtl:mk_imm(Res).
223
186
 
224
187
 
225
 
 
226
 
 
227
 
 
228
 
 
229
 
 
230
188
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
231
 
%%%
 
189
%%
232
190
%% Dead code elimination
233
 
%%%
 
191
%%
234
192
 
235
193
dead_code_ebbs([], CFG, _Live) ->
236
194
  CFG;
238
196
  {CFG0, _} = dead_code_ebb(EBB, CFG, Live),
239
197
  dead_code_ebbs(EBBs, CFG0, Live).
240
198
 
241
 
 
242
199
dead_code_ebb(EBB, CFG, Live) ->
243
200
  case hipe_rtl_ebb:type(EBB) of
244
201
    node ->
254
211
      BB = hipe_rtl_cfg:bb(CFG0, Lbl),
255
212
      {NewCode, LiveIn} = dead_code_instrs(hipe_bb:code(BB), LiveOut),
256
213
      NewBB = hipe_bb:code_update(BB, NewCode),
257
 
      NewCFG = hipe_rtl_cfg:bb_update(CFG0, Lbl, NewBB),
 
214
      NewCFG = hipe_rtl_cfg:bb_add(CFG0, Lbl, NewBB),
258
215
      {NewCFG, LiveIn};
259
216
    leaf ->
260
217
      Lbl = hipe_rtl_ebb:leaf_next(EBB),
261
 
 
262
218
      {CFG, gb_sets:from_list(hipe_rtl_liveness:livein(Live, Lbl))}
263
219
  end.
264
220
 
265
 
 
266
221
dead_code_succ([], CFG, _Live) ->
267
222
  {CFG, gb_sets:new()};
268
223
dead_code_succ([EBB|EBBs], CFG, Live) ->
270
225
  {NewCFG, LiveOut1} = dead_code_succ(EBBs, CFG0, Live),
271
226
  {NewCFG, gb_sets:union(LiveOut0, LiveOut1)}.
272
227
 
273
 
 
274
228
dead_code_instrs([], LiveOut) ->
275
229
  {[], LiveOut};
276
230
dead_code_instrs([I|Is], LiveOut) ->
277
231
  {NewIs, LiveOut0} = dead_code_instrs(Is, LiveOut),
278
232
  NewI = simplify_mm(I, LiveOut0),
279
233
  Def = gb_sets:from_list(hipe_rtl:defines(NewI)),
280
 
  Dead = gb_sets:size(gb_sets:intersection(LiveOut0, Def)) == 0,
281
 
  case {hipe_rtl:is_pure(NewI), Dead} of
 
234
  Dead = gb_sets:size(gb_sets:intersection(LiveOut0, Def)) =:= 0,
 
235
  case {hipe_rtl:is_safe(NewI), Dead} of
282
236
    {true, true} ->
283
237
      {NewIs, LiveOut0};
284
238
    _ ->
301
255
  (hipe_rtl:is_move(X) andalso
302
256
   (hipe_rtl:move_src(X) =:= hipe_rtl:move_dst(X))).
303
257
 
304
 
 
 
258
%%
305
259
%% Simplify multimoves
 
260
%%
306
261
simplify_mm(I, LiveOut) ->
307
 
  case hipe_rtl:type(I) of
308
 
    multimove ->
309
 
      {NewSource, NewDest} = simplify_mm(hipe_rtl:multimove_src(I),
310
 
                                         hipe_rtl:multimove_dst(I), LiveOut),
311
 
      Info = hipe_rtl:multimove_info(I),
312
 
      hipe_rtl:multimove_info_update(hipe_rtl:mk_multimove(NewDest, NewSource),
313
 
                                     Info);
 
262
  case I of
 
263
    #multimove{} ->
 
264
      {NewSourceList, NewDestList} =
 
265
         simplify_mm(hipe_rtl:multimove_srclist(I),
 
266
                     hipe_rtl:multimove_dstlist(I), LiveOut),
 
267
      hipe_rtl:mk_multimove(NewDestList, NewSourceList);
314
268
    _ ->
315
269
      I
316
270
  end.
318
272
simplify_mm(Ss, Ds, LiveOut) ->
319
273
  simplify_mm(Ss, Ds, [], [], LiveOut).
320
274
 
321
 
simplify_mm([S|Srcs],[S|Dsts], SAcc, DAcc, LiveOut) ->
 
275
simplify_mm([S|Srcs], [S|Dsts], SAcc, DAcc, LiveOut) ->
322
276
  simplify_mm(Srcs, Dsts, SAcc, DAcc, LiveOut);
323
 
simplify_mm([S|Srcs],[D|Dsts], SAcc, DAcc, LiveOut) ->
 
277
simplify_mm([S|Srcs], [D|Dsts], SAcc, DAcc, LiveOut) ->
324
278
  case gb_sets:is_element(D, LiveOut) of
325
279
    true -> %% The dest is live after the instruction.
326
 
      simplify_mm(Srcs, Dsts, [S|SAcc] , [D|DAcc],LiveOut);
 
280
      simplify_mm(Srcs, Dsts, [S|SAcc], [D|DAcc],LiveOut);
327
281
    false -> %% The dest is dead, move unnecessary.
328
282
      simplify_mm(Srcs, Dsts, SAcc, DAcc, LiveOut)
329
283
  end;
333
287
 
334
288
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
335
289
%%
336
 
%% the environment, Rewrite if we go global.
 
290
%% The environment. Rewrite if we go global.
337
291
%%
338
 
%% An environment has two mappings If x is bound to y then
339
 
%% map 1 contains {x,y} and map 2 contains {y,[x|_]}
 
292
%% An environment has two mappings:
 
293
%%   If x is bound to y then
 
294
%%   map 1 contains {x,y} and map 2 contains {y,[x|_]}
 
295
 
340
296
new_env() ->
341
297
  {gb_trees:empty(),gb_trees:empty()}.
342
298
 
343
 
 
344
 
%%
345
 
%% Find what X is bound to (as a last restort varaibles are bound 
346
 
%% to themselves).
347
 
%%
348
 
 
 
299
%%
 
300
%% Find what X is bound to (as a last restort variables are bound to
 
301
%% themselves).
 
302
%%
349
303
 
350
304
lookup(X,{Map,_}) ->
351
 
    case gb_trees:lookup(X,Map) of
352
 
        {value, Y} -> Y;
353
 
        none -> X
354
 
    end.
355
 
 
 
305
  case gb_trees:lookup(X,Map) of
 
306
    {value, Y} -> Y;
 
307
    none -> X
 
308
  end.
356
309
 
357
310
%%
358
311
%% Bind X to Y in Map
360
313
 
361
314
bind({Map1,Map2}, X, Y) -> 
362
315
  NewMap2 =
363
 
     case gb_trees:lookup(Y,Map2) of
364
 
       none -> gb_trees:enter(Y,[X],Map2);
365
 
       {value,Ys} ->
366
 
         gb_trees:enter(Y,[X|Ys],Map2)
 
316
    case gb_trees:lookup(Y,Map2) of
 
317
      none ->
 
318
        gb_trees:enter(Y,[X],Map2);
 
319
      {value,Ys} ->
 
320
        gb_trees:enter(Y,[X|Ys],Map2)
367
321
    end, 
368
 
    {gb_trees:enter(X,Y,Map1),
369
 
     NewMap2}.
370
 
 
371
 
 
 
322
  {gb_trees:enter(X,Y,Map1),NewMap2}.
372
323
 
373
324
%%
374
325
%% Kill bindings with references to X
375
326
%%
 
327
 
376
328
kill(X,M = {Map1,Map2}) ->
377
329
  %% First check if anyting is bound to X.
378
330
  M1 = {M11,M12} =
379
331
    case gb_trees:lookup(X,Map2) of
380
332
      none -> M;
381
333
      {value,Y1s} -> %% All Y1s bound to X
382
 
        {lists:foldl(
383
 
           fun (Y1,MapAcc) ->
384
 
               gb_trees:delete_any(Y1,MapAcc)
385
 
           end,Map1,Y1s),
 
334
        {lists:foldl(fun (Y1,MapAcc) ->
 
335
                         gb_trees:delete_any(Y1,MapAcc)
 
336
                     end,Map1,Y1s),
386
337
         gb_trees:delete(X,Map2)}
387
338
    end,
388
339
  %% Now check if X is bound to anything.
390
341
    {value,Y2} -> %% X bound to Y2
391
342
      {gb_trees:delete(X,M11),
392
343
       case gb_trees:lookup(Y2,M12) of
393
 
         none -> M12;
394
 
       {value,Y2s} ->
395
 
         gb_trees:enter(Y2,lists:delete(X,Y2s),M12)
396
 
       end}; 
 
344
         none ->
 
345
           M12;
 
346
         {value,Y2s} ->
 
347
           gb_trees:enter(Y2,lists:delete(X,Y2s),M12)
 
348
       end};
397
349
    none -> 
398
350
      M1
399
 
  end.       
400
 
 
 
351
  end.
401
352
 
402
353
unbind([], Map) ->
403
354
  Map;
404
355
unbind([V|Vs], Map) ->
405
356
  unbind(Vs, kill(V, Map)).
406
357
 
407
 
do(CFG) ->
408
 
  CFG1=prop(CFG),
409
 
  CFG2=hipe_rtl_cfg:remove_dead_code(CFG1),
410
 
  Liveness = hipe_rtl_liveness:analyze(CFG2),
411
 
  EBBs2 = hipe_rtl_ebb:cfg(CFG2),
412
 
  CFG3=dead_code_ebbs(EBBs2, CFG2, Liveness),
413
 
  remove_loads(CFG3).
414
 
 
415
 
 
416
 
prop(CFG) ->
417
 
  Start=hipe_rtl_cfg:start(CFG),
418
 
  Tree=gb_trees:empty(),
419
 
  PredMap = hipe_rtl_cfg:pred_map(CFG),
420
 
  Info = fix_point([Start], CFG, PredMap, Tree),
421
 
  pass_through([Start], CFG, PredMap, Info, gb_sets:singleton(Start)).
422
 
 
423
358
pass_through([Label|Labels], CFG, PredMap, Info, Passed) ->
424
 
  Pred=hipe_rtl_cfg:pred(PredMap,Label),
425
 
  InfoIn= join(Pred, Info),
 
359
  Pred = hipe_rtl_cfg:pred(PredMap,Label),
 
360
  InfoIn = join(Pred, Info),
426
361
  CurrentBB = hipe_rtl_cfg:bb(CFG, Label),
427
362
  OldCode = hipe_bb:code(CurrentBB),
428
363
  {NewCode, _NewInfoOut} = prop2_instrs(OldCode, InfoIn), 
429
364
  NewBB = hipe_bb:mk_bb(NewCode),
430
 
  NewCFG = hipe_rtl_cfg:bb_update(CFG, Label, NewBB),
 
365
  NewCFG = hipe_rtl_cfg:bb_add(CFG, Label, NewBB),
431
366
  NewSuccMap = hipe_rtl_cfg:succ_map(NewCFG),
432
367
  Succ = hipe_rtl_cfg:succ(NewSuccMap, Label),
433
368
  {NewLbls, NewPassed} = not_members_of_set(Succ, Passed),
434
369
  NewPredMap = hipe_rtl_cfg:pred_map(NewCFG),
435
370
  pass_through(Labels ++ NewLbls, NewCFG, NewPredMap, Info, NewPassed);
436
 
 
437
371
pass_through([], CFG, _PredMap, _Info, _Passed) ->
438
372
  CFG.
439
373
 
449
383
  end;
450
384
not_members_of_set([], Set, Acc) ->
451
385
  {Acc, Set}.
 
386
 
452
387
fix_point([Label|Labels], CFG, PredMap, Info) ->
453
 
  Pred=hipe_rtl_cfg:pred(PredMap,Label),
454
 
  InfoIn= join(Pred, Info),
 
388
  Pred = hipe_rtl_cfg:pred(PredMap,Label),
 
389
  InfoIn = join(Pred, Info),
455
390
  OldInfoOut = 
456
391
    case gb_trees:lookup(Label, Info) of
457
392
      {value, V} -> V;
464
399
      fix_point(Labels, CFG, PredMap, Info);
465
400
    {NewCode, NewInfoOut} ->
466
401
      NewBB = hipe_bb:mk_bb(NewCode),
467
 
      NewCFG = hipe_rtl_cfg:bb_update(CFG, Label, NewBB),
 
402
      NewCFG = hipe_rtl_cfg:bb_add(CFG, Label, NewBB),
468
403
      NewSuccMap = hipe_rtl_cfg:succ_map(NewCFG),
469
404
      Succ = hipe_rtl_cfg:succ(NewSuccMap, Label), 
470
405
      NewList = add_succ_to_list(Succ, Labels),
471
406
      NewInfo = add_info(Label, NewInfoOut, Info),
472
407
      fix_point(NewList, CFG, PredMap, NewInfo)
473
408
  end;
474
 
 
475
409
fix_point([], _CFG, _PredMap, Info) ->
476
410
  Info.
477
411
 
479
413
  prop2_instrs(Code, Env, []).
480
414
 
481
415
prop2_instrs([Instr|Rest], Env, Acc) -> 
482
 
  case  prop_instr(Instr, Env) of
 
416
  case prop_instr(Instr, Env) of
483
417
    {NewI, NewEnv} when is_list(NewI) ->
484
418
      prop2_instrs(Rest, NewEnv, Acc++NewI);
485
419
    {NewI, NewEnv} ->
499
433
  join(Preds, Info, [], []).
500
434
 
501
435
join([Pred|Rest], Info, Acc1, Acc2) ->
502
 
  case  gb_trees:lookup(Pred, Info) of
 
436
  case gb_trees:lookup(Pred, Info) of
503
437
    {value,{Tree1, Tree2}} ->
504
438
      {List1, List2} = {gb_trees:to_list(Tree1),gb_trees:to_list(Tree2)} ,
505
439
      {Set1, Set2} = {gb_sets:from_ordset(List1),gb_sets:from_ordset(List2)},
516
450
  {gb_trees:from_orddict(L1), gb_trees:from_orddict(L2)}.
517
451
 
518
452
 
519
 
 
520
453
add_succ_to_list([First|Rest], List) ->
521
454
  case add_element(List, First) of
522
455
    fail ->
543
476
  PredMap = hipe_rtl_cfg:pred_map(CFG),  
544
477
  SuccMap = hipe_rtl_cfg:succ_map(CFG),
545
478
  Info = gb_trees:empty(),  
546
 
  Start = hipe_rtl_cfg:start(CFG),  
 
479
  Start = hipe_rtl_cfg:start_label(CFG),  
547
480
  NewInfo=fix_remove([Start], CFG, PredMap, SuccMap, Info),
548
481
  Labels = hipe_rtl_cfg:reverse_postorder(CFG),
549
482
  update_cfg(Labels, CFG, PredMap, NewInfo).
550
483
 
551
484
update_cfg([Label|Labels], CFG, PredMap, Info) ->
552
 
  Pred=hipe_rtl_cfg:pred(PredMap,Label),
553
 
  InfoIn= join_load(Pred, Info),
 
485
  Pred = hipe_rtl_cfg:pred(PredMap,Label),
 
486
  InfoIn = join_load(Pred, Info),
554
487
  CurrentBB = hipe_rtl_cfg:bb(CFG, Label),
555
488
  OldCode = hipe_bb:code(CurrentBB),
556
489
  case spread_info(OldCode, InfoIn) of
557
490
    {OldCode, _} ->
558
491
      update_cfg(Labels, CFG, PredMap, Info);
559
492
    {NewCode, _} ->
560
 
      NewBB=hipe_bb:code_update(CurrentBB, NewCode),
561
 
      NewCFG=hipe_rtl_cfg:bb_update(CFG, Label, NewBB),
562
 
      NewPredMap=hipe_rtl_cfg:pred_map(NewCFG),
 
493
      NewBB = hipe_bb:code_update(CurrentBB, NewCode),
 
494
      NewCFG = hipe_rtl_cfg:bb_add(CFG, Label, NewBB),
 
495
      NewPredMap = hipe_rtl_cfg:pred_map(NewCFG),
563
496
      update_cfg(Labels, NewCFG, NewPredMap, Info)
564
497
  end;
565
498
update_cfg([], CFG, _PredMap, _Info) ->
566
499
  CFG.
567
500
    
568
501
fix_remove([Label|Labels], CFG, PredMap, SuccMap, Info) ->
569
 
  Pred=hipe_rtl_cfg:pred(PredMap,Label),
570
 
  InfoIn= join_load(Pred, Info),
 
502
  Pred = hipe_rtl_cfg:pred(PredMap,Label),
 
503
  InfoIn = join_load(Pred, Info),
571
504
  OldInfoOut = 
572
505
    case gb_trees:lookup(Label, Info) of
573
506
      {value, V} -> V;
576
509
  CurrentBB = hipe_rtl_cfg:bb(CFG, Label),
577
510
  OldCode = hipe_bb:code(CurrentBB),
578
511
  case spread_info(OldCode, InfoIn) of
579
 
    {_,OldInfoOut} ->
 
512
    {_, OldInfoOut} ->
580
513
      fix_remove(Labels, CFG, PredMap, SuccMap, Info);
581
 
    {_,NewInfoOut} ->
 
514
    {_, NewInfoOut} ->
582
515
      Succ = hipe_rtl_cfg:succ(SuccMap, Label), 
583
516
      NewList = add_succ_to_list(Succ, Labels),
584
517
      NewInfo = add_info(Label, NewInfoOut, Info),
585
518
      fix_remove(NewList, CFG, PredMap, SuccMap, NewInfo)
586
519
  end;
587
 
 
588
520
fix_remove([], _CFG, _PredMap, _SuccMap, Info) ->
589
521
  Info.
590
522
 
592
524
  lists:foldl(fun do_instr/2, {[],Info}, Code).
593
525
 
594
526
do_instr(Instr, {Acc,Info}) ->
595
 
  case hipe_rtl:type(Instr) of
596
 
    call ->
597
 
      {Acc++[Instr],new_load_env()};
598
 
    store ->  
599
 
      {Acc++[Instr],new_load_env()};
600
 
    load ->
 
527
  case Instr of
 
528
    #call{} ->
 
529
      {Acc++[Instr], new_load_env()};
 
530
    #store{} ->  
 
531
      {Acc++[Instr], new_load_env()};
 
532
    #load{} ->
601
533
      Dst = hipe_rtl:load_dst(Instr),
602
534
      LoadType = {Dst, hipe_rtl:load_src(Instr), hipe_rtl:load_offset(Instr), 
603
535
                  hipe_rtl:load_size(Instr), hipe_rtl:load_sign(Instr)},
604
536
      NewInstr = 
605
537
        case get_aliased_var(LoadType, Info) of
606
 
          {var, Var} ->
 
538
          #aliased_var{name=Var} ->
607
539
            hipe_rtl:mk_move(Dst, Var);
608
540
          none ->
609
541
            Instr
610
542
        end,
611
 
      Defs=hipe_rtl:defines(Instr),
 
543
      Defs = hipe_rtl:defines(Instr),
612
544
      CleanInfo = remove_loads(Defs, Info),
613
 
      {Acc++[NewInstr],gb_sets:add(LoadType, CleanInfo)};
 
545
      {Acc++[NewInstr], gb_sets:add(LoadType, CleanInfo)};
614
546
    _ ->
615
 
      Defs=hipe_rtl:defines(Instr),
616
 
      {Acc++[Instr],remove_loads(Defs, Info)}
 
547
      Defs = hipe_rtl:defines(Instr),
 
548
      {Acc++[Instr], remove_loads(Defs, Info)}
617
549
  end.
618
550
  
619
551
remove_loads([Def|Defs], Info) ->
620
 
  NewInfo=gb_sets:filter(fun(X) -> not_part(X, Def) end, Info),
 
552
  NewInfo = gb_sets:filter(fun(X) -> not_part(X, Def) end, Info),
621
553
  remove_loads(Defs, NewInfo);
622
554
remove_loads([], Info) ->
623
555
  Info.
624
556
 
 
557
remove_stores(CFG) ->
 
558
  Labels = hipe_rtl_cfg:labels(CFG),
 
559
  remove_stores(Labels, CFG).
 
560
 
 
561
remove_stores([Label|Labels], CFG) ->
 
562
  BB = hipe_rtl_cfg:bb(CFG, Label),
 
563
  OldCode = hipe_bb:code(BB),
 
564
  case remove_store_from_bb(OldCode) of
 
565
    OldCode ->
 
566
      remove_stores(Labels, CFG);
 
567
    NewCode ->
 
568
      NewBB = hipe_bb:code_update(BB, NewCode),
 
569
      NewCFG = hipe_rtl_cfg:bb_add(CFG, Label, NewBB),
 
570
      remove_stores(Labels, NewCFG)
 
571
  end;
 
572
remove_stores([], CFG) ->
 
573
  CFG.
 
574
 
 
575
remove_store_from_bb(Code) ->
 
576
  remove_store_from_bb(lists:reverse(Code), new_load_env(), []).
 
577
 
 
578
remove_store_from_bb([Instr|Instrs], Env, Acc) ->
 
579
  {NewAcc, NewEnv} =
 
580
    case Instr of
 
581
      #call{} ->
 
582
        {[Instr|Acc],new_load_env()};
 
583
      #store{} ->  
 
584
        Base = hipe_rtl:store_base(Instr),
 
585
        Offset = hipe_rtl:store_offset(Instr),
 
586
        Size = hipe_rtl:store_size(Instr),
 
587
        StoreType = {Base, Offset, Size},
 
588
        case store_already_done(StoreType, Env) of
 
589
          true ->
 
590
            {Acc, Env};
 
591
          false ->
 
592
            {[Instr|Acc], gb_sets:add(StoreType, Env)}
 
593
        end;
 
594
      #load{} ->
 
595
        {[Instr|Acc],new_load_env()};
 
596
      _ -> 
 
597
        Defs = hipe_rtl:defines(Instr),
 
598
        {[Instr|Acc], update_store_env(Defs, Env)}
 
599
    end,
 
600
  remove_store_from_bb(Instrs, NewEnv, NewAcc);
 
601
remove_store_from_bb([], _Env, Acc) ->
 
602
  Acc.
 
603
 
 
604
update_store_env([Def|Defs], Env) ->
 
605
  NewEnv = gb_sets:filter(fun(X) -> not_part_of_store(X, Def) end, Env),
 
606
  update_store_env(Defs, NewEnv);
 
607
update_store_env([], Env) ->
 
608
  Env.
 
609
 
 
610
store_already_done(StoreType, Env) ->
 
611
  Iterator = gb_sets:iterator(Env),
 
612
  check_store(StoreType, Iterator).
 
613
 
 
614
check_store(StoreType, Iterator) ->
 
615
  case gb_sets:next(Iterator) of
 
616
    none ->
 
617
      false;                                
 
618
    {StoreType, _} ->
 
619
      true;
 
620
    {_, Next} ->
 
621
      check_store(StoreType, Next)
 
622
  end.
 
623
 
 
624
not_part_of_store({Def,_,_}, Def) -> false;
 
625
not_part_of_store({_,Def,_}, Def) -> false;
 
626
not_part_of_store(_, _Def) -> true.
 
627
 
625
628
not_part({Def,_,_,_,_}, Def) -> 
626
629
  false;
627
630
not_part({_,Def,_,_,_}, Def) ->
632
635
  true.
633
636
 
634
637
get_aliased_var({_, Src, Offset, Size, Sign}, Info) -> 
635
 
  Iterator=gb_sets:iterator(Info),
 
638
  Iterator = gb_sets:iterator(Info),
636
639
  find_aliased_var({Src, Offset, Size, Sign}, Iterator).
637
640
 
638
641
find_aliased_var({Src, Offset, Size, Sign}, Iterator) ->
640
643
    none ->
641
644
      none;
642
645
    {{Var, Src, Offset, Size, Sign}, _}  ->
643
 
      {var, Var};
 
646
      #aliased_var{name=Var};
644
647
    {_,Next} ->
645
648
      find_aliased_var({Src, Offset, Size, Sign}, Next)
646
649
  end.