← Back to branch summary

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

« back to all changes in this revision

Viewing changes to lib/hipe/opt/hipe_dead_code.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/opt/hipe_dead_code.erl
1
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2
 
%%
3
 
%%                      DEAD CODE ELIMINATION
4
 
%%
5
 
%% Runs one pass of dead code elimination. Note that we should iterate
6
 
%% this to eliminate all dead code.
7
 
%%
8
 
%% Another approach is to employ use-def chains + marking, which is
9
 
%% probably a lot faster. Still, this is simple enough and might come
10
 
%% in useful. If we can save a lot of time, rewrite it to the use-def
11
 
%% algorithm.
12
 
 
13
 
-module(hipe_dead_code).
14
 
-export([eliminate/1]).
15
 
 
16
 
-define(cfg,hipe_icode_cfg).
17
 
-define(liveness,hipe_icode_liveness).
18
 
-define(code,hipe_icode).
19
 
 
20
 
eliminate(CFG) ->
21
 
    dce_blocks(?cfg:labels(CFG),?liveness:analyze(CFG),CFG).
22
 
 
23
 
dce_blocks([],_Live,CFG) -> CFG;
24
 
dce_blocks([L|Ls],Live,CFG) ->
25
 
    dce_blocks(Ls,Live,
26
 
               dce_block(L,?cfg:bb(CFG,L),?liveness:liveout(Live,L),CFG)).
27
 
 
28
 
dce_block(L,BB,LiveOut,CFG) ->
29
 
    {NewXs,_} = dce_instrs(hipe_bb:code(BB),LiveOut),
30
 
    ?cfg:bb_update(CFG,L,hipe_bb:mk_bb(NewXs)).
31
 
 
32
 
dce_instrs([],LiveOut) -> {[],LiveOut};
33
 
dce_instrs([X|Xs],LiveOut) ->
34
 
    {NewXs,Live} = dce_instrs(Xs,LiveOut),
35
 
    case {eliminable(X), dead(X,Live)} of
36
 
       {true, true} ->
37
 
          {NewXs,Live};
38
 
       _ ->
39
 
          {[X|NewXs],live_vars(X,Live)}
40
 
    end.
41
 
 
42
 
live_vars(X,Live) ->
43
 
    {D,U} = def_use(X),
44
 
    union(U,diff(Live,D)).
45
 
 
46
 
dead(X,Live) ->
47
 
    {D,_} = def_use(X),
48
 
    case intersect(D,Live) of
49
 
        [] ->
50
 
            true;
51
 
        [_|_] ->
52
 
            false
53
 
    end.
54
 
 
55
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
56
 
%%
57
 
%% Here, we would like to use real sets.
58
 
%% - convert liveness to use set-module
59
 
%% - convert def_use to return sets
60
 
 
61
 
union([],Ys) -> Ys;
62
 
union([X|Xs],Ys) ->
63
 
    case member(X,Ys) of 
64
 
       true ->
65
 
          union(Xs,Ys);
66
 
       false ->
67
 
          [X|union(Xs,Ys)]
68
 
    end.
69
 
 
70
 
diff([],_) -> [];
71
 
diff([X|Xs],Ys) ->
72
 
    case member(X,Ys) of
73
 
       true ->
74
 
          diff(Xs,Ys);
75
 
       false ->
76
 
          [X|diff(Xs,Ys)]
77
 
    end.
78
 
 
79
 
intersect([],_) -> [];
80
 
intersect([X|Xs],Ys) ->
81
 
   case member(X,Ys) of 
82
 
      true ->
83
 
         [X|intersect(Xs,Ys)];
84
 
      false ->
85
 
         intersect(Xs,Ys)
86
 
   end.
87
 
 
88
 
member(_,[]) -> false;
89
 
member(X,[X|_]) -> true;
90
 
member(X,[_|Xs]) -> member(X,Xs).
91
 
 
92
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
93
 
%%
94
 
%% *** PORTING ***
95
 
 
96
 
def_use(X) ->
97
 
    { ?code:defines(X), ?code:uses(X) }.
98
 
 
99
 
eliminable(X) ->
100
 
  case hipe_icode:type(X) of
101
 
    mov ->
102
 
      true;
103
 
    _ -> false
104
 
  end.