KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > polyglot > visit > DeadCodeEliminator


1 package polyglot.visit;
2
3 import polyglot.ast.*;
4 import polyglot.frontend.Job;
5 import polyglot.main.Report;
6 import polyglot.types.*;
7 import polyglot.util.InternalCompilerError;
8 import polyglot.util.Position;
9
10 import java.util.*;
11
12 /**
13  * Visitor which performs dead code elimination.
14  */

15 public class DeadCodeEliminator extends DataFlow {
16     public DeadCodeEliminator(Job job, TypeSystem ts, NodeFactory nf) {
17     super(job, ts, nf,
18           false /* backward analysis */,
19           true /* perform dataflow on entry to CodeDecls */);
20     }
21
22     protected static class DataFlowItem extends Item {
23     // Set of LocalInstances of live variables.
24
private Set liveVars;
25
26     // Set of LocalInstances of live declarations. A LocalDecl is live if
27
// the declared local is ever live.
28
private Set liveDecls;
29
30     /**
31      * Constructor for creating an empty set.
32      */

33     protected DataFlowItem() {
34         this.liveVars = new HashSet();
35         this.liveDecls = new HashSet();
36     }
37
38     /**
39      * Deep copy constructor.
40      */

41     protected DataFlowItem(DataFlowItem dfi) {
42         liveVars = new HashSet(dfi.liveVars);
43         liveDecls = new HashSet(dfi.liveDecls);
44     }
45
46     public void add(LocalInstance li) {
47         liveVars.add(li);
48         liveDecls.add(li);
49     }
50
51     public void addAll(Set lis) {
52         liveVars.addAll(lis);
53         liveDecls.addAll(lis);
54     }
55
56     public void remove(LocalInstance li) {
57         liveVars.remove(li);
58     }
59
60     public void removeAll(Set lis) {
61         liveVars.removeAll(lis);
62     }
63
64     public void removeDecl(LocalInstance li) {
65         liveVars.remove(li);
66         liveDecls.remove(li);
67     }
68
69     public void union(DataFlowItem dfi) {
70         liveVars.addAll(dfi.liveVars);
71         liveDecls.addAll(dfi.liveDecls);
72     }
73
74     protected boolean needDecl(LocalInstance li) {
75         return liveDecls.contains(li);
76     }
77
78     protected boolean needDef(LocalInstance li) {
79         return liveVars.contains(li);
80     }
81
82     public int hashCode() {
83         int result = 0;
84         for (Iterator it = liveVars.iterator(); it.hasNext(); ) {
85         result = 31*result + it.next().hashCode();
86         }
87
88         for (Iterator it = liveDecls.iterator(); it.hasNext(); ) {
89         result = 31*result + it.next().hashCode();
90         }
91
92         return result;
93     }
94
95     public boolean equals(Object JavaDoc o) {
96         if (!(o instanceof DataFlowItem)) return false;
97
98         DataFlowItem dfi = (DataFlowItem)o;
99         return liveVars.equals(dfi.liveVars)
100         && liveDecls.equals(dfi.liveDecls);
101     }
102
103     public String JavaDoc toString() {
104         return "<vars=" + liveVars + " ; decls=" + liveDecls + ">";
105     }
106     }
107
108     public Item createInitialItem(FlowGraph graph, Term node) {
109     return new DataFlowItem();
110     }
111
112     public Item confluence(List inItems, Term node, FlowGraph graph) {
113     DataFlowItem result = null;
114     for (Iterator it = inItems.iterator(); it.hasNext(); ) {
115         DataFlowItem inItem = (DataFlowItem)it.next();
116         if (result == null) {
117         result = new DataFlowItem(inItem);
118         } else {
119         result.union(inItem);
120         }
121     }
122
123     return result;
124     }
125
126     public Map flow(Item in, FlowGraph graph, Term t, Set succEdgeKeys) {
127     return itemToMap(flow(in, graph, t), succEdgeKeys);
128     }
129
130     protected DataFlowItem flow(Item in, FlowGraph graph, Term t) {
131     DataFlowItem result = new DataFlowItem((DataFlowItem)in);
132
133     Set[] du = null;
134
135     if (t instanceof LocalDecl) {
136         LocalDecl n = (LocalDecl)t;
137
138         LocalInstance to = n.localInstance();
139         result.removeDecl(to);
140
141         du = getDefUse(n.init());
142     } else if (t instanceof Stmt && !(t instanceof CompoundStmt)) {
143         du = getDefUse((Stmt)t);
144     } else if (t instanceof CompoundStmt) {
145         if (t instanceof If) {
146         du = getDefUse(((If)t).cond());
147         } else if (t instanceof Switch) {
148         du = getDefUse(((Switch)t).expr());
149         } else if (t instanceof Do) {
150         du = getDefUse(((Do)t).cond());
151         } else if (t instanceof For) {
152         du = getDefUse(((For)t).cond());
153         } else if (t instanceof While) {
154         du = getDefUse(((While)t).cond());
155         }
156     }
157
158     if (du != null) {
159         result.removeAll(du[0]);
160         result.addAll(du[1]);
161     }
162
163     return result;
164     }
165
166     public void post(FlowGraph graph, Term root) throws SemanticException {
167     // No need to do any checking.
168
if (Report.should_report(Report.cfg, 2)) {
169         dumpFlowGraph(graph, root);
170     }
171     }
172
173     public void check(FlowGraph graph, Term n, Item inItem, Map outItems)
174     throws SemanticException {
175
176     throw new InternalCompilerError("DeadCodeEliminator.check should "
177         + "never be called.");
178     }
179
180     private DataFlowItem getItem(Term n) {
181     FlowGraph g = currentFlowGraph();
182     if (g == null) return null;
183
184     Collection peers = g.peers(n);
185     if (peers == null || peers.isEmpty()) return null;
186
187     List items = new ArrayList();
188     for (Iterator it = peers.iterator(); it.hasNext(); ) {
189         FlowGraph.Peer p = (FlowGraph.Peer)it.next();
190         if (p.inItem() != null) items.add(p.inItem());
191     }
192
193     return (DataFlowItem)confluence(items, n, g);
194     }
195
196     public Node leaveCall(Node old, Node n, NodeVisitor v)
197     throws SemanticException {
198
199     if (n instanceof LocalDecl) {
200         LocalDecl ld = (LocalDecl)n;
201         DataFlowItem in = getItem(ld);
202         if (in == null || in.needDecl(ld.localInstance())) return n;
203         return getEffects(ld.init());
204     }
205
206     if (n instanceof Eval) {
207         Eval eval = (Eval)n;
208         Expr expr = eval.expr();
209         Local local;
210         Expr right = null;
211
212         if (expr instanceof Assign) {
213         Assign assign = (Assign)expr;
214         Expr left = assign.left();
215         right = assign.right();
216
217         if (!(left instanceof Local)) return n;
218         local = (Local)left;
219         } else if (expr instanceof Unary) {
220         Unary unary = (Unary)expr;
221         expr = unary.expr();
222         if (!(expr instanceof Local)) return n;
223         local = (Local)expr;
224         } else {
225         return n;
226         }
227
228         DataFlowItem in = getItem(eval);
229         if (in == null || in.needDef(local.localInstance())) return n;
230
231         if (right != null) {
232         return getEffects(right);
233         }
234
235         return nf.Empty(Position.COMPILER_GENERATED);
236     }
237
238     if (n instanceof Block) {
239         // Get rid of empty statements.
240
Block b = (Block)n;
241         List stmts = new ArrayList(b.statements());
242         for (Iterator it = stmts.iterator(); it.hasNext(); ) {
243         if (it.next() instanceof Empty) it.remove();
244         }
245
246         return b.statements(stmts);
247     }
248
249     return n;
250     }
251
252     /**
253      * Returns array of sets of local instances.
254      * Element 0 is the set of local instances DEFined by the node.
255      * Element 1 is the set of local instances USEd by the node.
256      */

257     protected Set[] getDefUse(Node n) {
258     final Set def = new HashSet();
259     final Set use = new HashSet();
260
261     if (n != null) {
262         n.visit(createDefUseFinder(def, use));
263     }
264
265     return new Set[] {def, use};
266     }
267
268     protected NodeVisitor createDefUseFinder(Set def, Set use) {
269     return new DefUseFinder(def, use);
270     }
271
272     protected static class DefUseFinder extends HaltingVisitor {
273     protected Set def;
274     protected Set use;
275
276     public DefUseFinder(Set def, Set use) {
277         this.def = def;
278         this.use = use;
279     }
280
281     public NodeVisitor enter(Node n) {
282         if (n instanceof LocalAssign) {
283         return bypass(((Assign)n).left());
284         }
285
286         return super.enter(n);
287     }
288
289     public Node leave(Node old, Node n, NodeVisitor v) {
290         if (n instanceof Local) {
291         use.add(((Local)n).localInstance());
292         } else if (n instanceof Assign) {
293         Expr left = ((Assign)n).left();
294         if (left instanceof Local) {
295             def.add(((Local)left).localInstance());
296         }
297         }
298
299         return n;
300     }
301     }
302
303     /**
304      * Returns a statement that is side-effect-equivalent to the given
305      * expression.
306      */

307     protected Stmt getEffects(Expr expr) {
308     Stmt empty = nf.Empty(Position.COMPILER_GENERATED);
309     if (expr == null) return empty;
310
311     final List result = new LinkedList();
312     final Position pos = Position.COMPILER_GENERATED;
313
314     NodeVisitor v = new HaltingVisitor() {
315         public NodeVisitor enter(Node n) {
316         if (n instanceof Assign || n instanceof ProcedureCall) {
317             return bypassChildren(n);
318         }
319
320         // XXX Cast
321

322         if (n instanceof Unary) {
323             Unary.Operator op = ((Unary)n).operator();
324             if (op == Unary.POST_INC || op == Unary.POST_DEC
325             || op == Unary.PRE_INC || op == Unary.PRE_INC) {
326
327             return bypassChildren(n);
328             }
329         }
330
331         return this;
332         }
333
334         public Node leave(Node old, Node n, NodeVisitor v) {
335         if (n instanceof Assign || n instanceof ProcedureCall) {
336             result.add(nf.Eval(pos, (Expr)n));
337         } else if (n instanceof Unary) {
338             Unary.Operator op = ((Unary)n).operator();
339             if (op == Unary.POST_INC || op == Unary.POST_DEC
340             || op == Unary.PRE_INC || op == Unary.PRE_INC) {
341
342             result.add(nf.Eval(pos, (Expr)n));
343             }
344         }
345
346         // XXX Cast
347

348         return n;
349         }
350     };
351
352     expr.visit(v);
353
354     if (result.isEmpty()) return empty;
355     if (result.size() == 1) return (Stmt)result.get(0);
356     return nf.Block(Position.COMPILER_GENERATED, result);
357     }
358 }
359
360
Popular Tags