1 cananian 1.1.2.1 // DeadCode2.java, created Thu Oct 8 03:11:37 1998 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1
5 cananian 1.1.2.1 package harpoon.Analysis.Quads;
6 cananian 1.1.2.1
7 cananian 1.1.2.4 import harpoon.Analysis.AllocationInformationMap;
8 cananian 1.1.2.4 import harpoon.Analysis.Maps.AllocationInformation;
9 cananian 1.1.2.3 import harpoon.ClassFile.HClass;
10 cananian 1.1.2.3 import harpoon.ClassFile.HCode;
11 salcianu 1.6 import harpoon.IR.Quads.Code;
12 salcianu 1.6 import harpoon.IR.Quads.QuadSSI;
13 cananian 1.1.2.3 import harpoon.IR.Quads.Quad;
14 cananian 1.1.2.3 import harpoon.IR.Quads.QuadVisitor;
15 cananian 1.1.2.3 import harpoon.IR.Quads.Edge;
16 cananian 1.1.2.3 import harpoon.IR.Quads.AGET;
17 cananian 1.1.2.3 import harpoon.IR.Quads.ALENGTH;
18 cananian 1.1.2.3 import harpoon.IR.Quads.ANEW;
19 cananian 1.1.2.3 import harpoon.IR.Quads.ARRAYINIT;
20 cananian 1.1.2.3 import harpoon.IR.Quads.ASET;
21 cananian 1.1.2.3 import harpoon.IR.Quads.CALL;
22 cananian 1.1.2.3 import harpoon.IR.Quads.CJMP;
23 cananian 1.1.2.3 import harpoon.IR.Quads.COMPONENTOF;
24 cananian 1.1.2.3 import harpoon.IR.Quads.CONST;
25 cananian 1.1.2.3 import harpoon.IR.Quads.FOOTER;
26 cananian 1.1.2.3 import harpoon.IR.Quads.GET;
27 cananian 1.1.2.3 import harpoon.IR.Quads.HANDLER;
28 cananian 1.1.2.3 import harpoon.IR.Quads.HEADER;
29 cananian 1.1.2.3 import harpoon.IR.Quads.INSTANCEOF;
30 cananian 1.1.2.3 import harpoon.IR.Quads.METHOD;
31 cananian 1.1.2.3 import harpoon.IR.Quads.MONITORENTER;
32 cananian 1.1.2.3 import harpoon.IR.Quads.MONITOREXIT;
33 cananian 1.1.2.3 import harpoon.IR.Quads.MOVE;
34 cananian 1.1.2.3 import harpoon.IR.Quads.NEW;
35 cananian 1.1.2.3 import harpoon.IR.Quads.NOP;
36 cananian 1.1.2.3 import harpoon.IR.Quads.OPER;
37 cananian 1.1.2.3 import harpoon.IR.Quads.PHI;
38 cananian 1.1.2.3 import harpoon.IR.Quads.RETURN;
39 cananian 1.1.2.3 import harpoon.IR.Quads.SET;
40 cananian 1.1.2.3 import harpoon.IR.Quads.SIGMA;
41 cananian 1.1.2.3 import harpoon.IR.Quads.SWITCH;
42 cananian 1.1.2.3 import harpoon.IR.Quads.THROW;
43 cananian 1.1.2.7 import harpoon.IR.Quads.TYPESWITCH;
44 cananian 1.1.2.3 import harpoon.IR.LowQuad.LowQuadVisitor;
45 cananian 1.1.2.3 import harpoon.IR.LowQuad.PCALL;
46 cananian 1.1.2.3 import harpoon.IR.LowQuad.PSET;
47 cananian 1.1.2.1 import harpoon.Temp.Temp;
48 cananian 1.1.2.1 import harpoon.Temp.TempMap;
49 cananian 1.8 import net.cscott.jutil.GenericInvertibleMultiMap;
50 cananian 1.8 import net.cscott.jutil.InvertibleMultiMap;
51 cananian 1.8 import net.cscott.jutil.MultiMap;
52 cananian 1.8 import net.cscott.jutil.Default;
53 cananian 1.1.2.9 import harpoon.Util.Collections.WorkSet;
54 cananian 1.1.2.1 import harpoon.Util.Worklist;
55 cananian 1.1.2.1 import harpoon.Util.Util;
56 cananian 1.1.2.1
57 cananian 1.1.2.1 import java.util.Comparator;
58 cananian 1.1.2.1 import java.util.Enumeration;
59 cananian 1.1.2.1 import java.util.HashMap;
60 cananian 1.1.2.1 import java.util.HashSet;
61 cananian 1.1.2.8 import java.util.Iterator;
62 cananian 1.1.2.1 import java.util.Map;
63 cananian 1.1.2.1 import java.util.Set;
64 cananian 1.1.2.1 import java.util.SortedMap;
65 cananian 1.1.2.1 import java.util.TreeMap;
66 cananian 1.1.2.1 /**
67 cananian 1.1.2.1 * <code>DeadCode</code> removes dead code
68 cananian 1.1.2.1 * (unused definitions/useless jmps/one-argument phi functions/all moves) from
69 cananian 1.1.2.1 * a method. The analysis is optimistic; that is, it assumes that all code is
70 cananian 1.1.2.1 * unused and seeks to prove otherwise. Also works on LowQuads.
71 cananian 1.1.2.1 *
72 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
73 cananian 1.8 * @version $Id: DeadCode.java,v 1.8 2004/02/08 01:53:14 cananian Exp $
74 cananian 1.1.2.1 */
75 cananian 1.1.2.1
76 cananian 1.1.2.1 public abstract class DeadCode {
77 cananian 1.1.2.1
78 cananian 1.1.2.4 public static void optimize(harpoon.IR.Quads.Code hc,
79 cananian 1.1.2.4 AllocationInformationMap aim) {
80 cananian 1.1.2.4 AllocationInformation oldaim = hc.getAllocationInformation();
81 cananian 1.1.2.1 // Assume everything's useless.
82 cananian 1.1.2.1 Set useful = new HashSet(); // empty set.
83 cananian 1.1.2.1 // make a renaming table
84 cananian 1.1.2.1 NameMap nm = new NameMap();
85 cananian 1.1.2.1 // keep track of defs.
86 cananian 1.1.2.1 Map defMap = new HashMap();
87 cananian 1.1.2.8 // keep track of PHI/SIGMAs which use certain temps.
88 cananian 1.5 InvertibleMultiMap useMap = new GenericInvertibleMultiMap();
89 cananian 1.1.2.1 // we'll have a coupla visitors
90 cananian 1.1.2.3 LowQuadVisitor v;
91 cananian 1.1.2.1
92 cananian 1.1.2.1 // make a worklist (which everything's on, at the beginning)
93 cananian 1.1.2.8 WorkSet W = new WorkSet();
94 cananian 1.1.2.1 Quad[] ql = (Quad[]) hc.getElements();
95 cananian 1.1.2.1 for (int i=0; i<ql.length; i++) {
96 cananian 1.1.2.1 W.push(ql[i]);
97 cananian 1.1.2.1 // build our defMap while we're at it.
98 cananian 1.1.2.1 Temp d[] = ql[i].def();
99 cananian 1.1.2.1 for (int j=0; j<d.length; j++)
100 cananian 1.1.2.1 defMap.put(d[j], ql[i]);
101 cananian 1.1.2.8 // and keep track of phis/sigmas which use certain temps.
102 cananian 1.1.2.8 if (ql[i] instanceof PHI || ql[i] instanceof SIGMA)
103 cananian 1.1.2.8 for (Iterator it=ql[i].useC().iterator(); it.hasNext(); )
104 cananian 1.1.2.8 useMap.add((Temp)it.next(), ql[i]);
105 cananian 1.1.2.1 }
106 cananian 1.1.2.1 // ...and a visitor
107 cananian 1.1.2.1 v = new UsefulVisitor(W, useful, defMap, nm);
108 cananian 1.1.2.1 // look for useful stuff.
109 cananian 1.1.2.1 while (!W.isEmpty()) {
110 cananian 1.1.2.1 Quad q = (Quad) W.pull();
111 cananian 1.1.2.2 q.accept(v);
112 cananian 1.1.2.1 }
113 cananian 1.1.2.1
114 cananian 1.1.2.1 // remove the useless stuff, including useless cjmps/phis
115 cananian 1.1.2.1 for (int i=0; i<ql.length; i++)
116 salcianu 1.6 W.push(ql[i]);
117 cananian 1.1.2.8 v = new EraserVisitor(W, useful, useMap, nm);
118 cananian 1.1.2.1 while (!W.isEmpty()) {
119 cananian 1.1.2.1 Quad q = (Quad) W.pull();
120 cananian 1.1.2.2 q.accept(v);
121 cananian 1.1.2.1 }
122 cananian 1.1.2.1
123 cananian 1.1.2.1 // Finally, do all the necessary renaming
124 cananian 1.1.2.3 ql = (Quad[]) hc.getElements(); // put them all in an array.
125 cananian 1.1.2.1 // evil: can't replace the header node. [ack]
126 cananian 1.1.2.3 for (int i=0; i<ql.length; i++)
127 cananian 1.1.2.3 if (!(ql[i] instanceof HEADER))
128 cananian 1.1.2.4 replace(ql[i], ql[i].rename(nm, nm), oldaim, aim, nm);
129 cananian 1.1.2.1
130 cananian 1.1.2.1 } // end OPTIMIZE METHOD.
131 cananian 1.1.2.4 static void replace(Quad oldquad, Quad newquad,
132 cananian 1.1.2.4 AllocationInformation oldaim,
133 cananian 1.1.2.4 AllocationInformationMap newaim, TempMap tm) {
134 salcianu 1.7 oldquad.getFactory().getParent().notifyReplace(oldquad, newquad, tm);
135 cananian 1.1.2.4 Quad.replace(oldquad, newquad);
136 cananian 1.1.2.4 // update allocation properties, too.
137 cananian 1.1.2.4 if (newaim!=null && (oldquad instanceof ANEW||oldquad instanceof NEW))
138 cananian 1.1.2.4 newaim.transfer(newquad, oldquad, tm, oldaim);
139 cananian 1.1.2.4 }
140 cananian 1.1.2.1
141 cananian 1.1.2.1 static class EraserVisitor extends LowQuadVisitor {
142 cananian 1.1.2.8 WorkSet W;
143 cananian 1.1.2.1 Set useful;
144 cananian 1.5 InvertibleMultiMap useMap;
145 cananian 1.1.2.1 NameMap nm;
146 cananian 1.5 EraserVisitor(WorkSet W, Set useful, InvertibleMultiMap useMap, NameMap nm) {
147 cananian 1.1.2.6 super(false/*non-strict*/);
148 cananian 1.1.2.8 this.W= W; this.useful= useful; this.useMap= useMap; this.nm= nm;
149 cananian 1.1.2.1 }
150 cananian 1.1.2.1 void unlink(Quad q) {
151 cananian 1.1.2.1 Edge before = q.prevEdge(0);
152 cananian 1.1.2.1 Edge after = q.nextEdge(0);
153 cananian 1.1.2.1 Quad.addEdge((Quad)before.from(), before.which_succ(),
154 cananian 1.1.2.1 (Quad)after.to(), after.which_pred() );
155 cananian 1.5 useMap.invert().remove(q);
156 cananian 1.1.2.1 }
157 cananian 1.1.2.1
158 cananian 1.1.2.1 public void visit(Quad q) {
159 cananian 1.1.2.1 // generally, remove it if it's worthless.
160 cananian 1.1.2.1 if (useful.contains(q)) return; // safe.
161 cananian 1.1.2.1 // removing this statement could make its predecessor useless.
162 cananian 1.1.2.1 if (q.prev(0) instanceof CJMP) W.push(q.prev(0));
163 cananian 1.1.2.1 // unlink with vigor.
164 cananian 1.3.2.1 assert q.next().length==1 && q.prev().length==1;
165 cananian 1.1.2.1 unlink(q);
166 cananian 1.1.2.1 }
167 cananian 1.1.2.1 public void visit(PHI q) {
168 cananian 1.1.2.1 // arity-1 phis are useless.
169 cananian 1.1.2.1 if (q.prev().length == 1) {
170 cananian 1.1.2.1 // make a pseudo-MOVE for every useful function in this useless phi.
171 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++)
172 cananian 1.1.2.1 if (useful.contains(q.dst(i)))
173 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++)
174 cananian 1.1.2.1 nm.map(q.dst(i), q.src(i,j));
175 cananian 1.1.2.1 // could make a CJMP useless.
176 cananian 1.1.2.1 if (q.prev(0) instanceof CJMP) W.push(q.prev(0));
177 cananian 1.1.2.1 // unlink it. (fun for the whole family)
178 cananian 1.1.2.1 unlink(q);
179 cananian 1.1.2.1 } else {
180 cananian 1.1.2.1 // check for unused functions in the phi.
181 cananian 1.1.2.1 for (int i=0; i < q.numPhis(); i++) {
182 cananian 1.1.2.1 if (useful.contains(q.dst(i))) continue;
183 cananian 1.1.2.1 // shrink the phi! (secret headhunter's ritual)
184 cananian 1.1.2.1 q.removePhi(i);
185 cananian 1.1.2.1 // decrement i so we're at the right place still;
186 cananian 1.1.2.1 i--;
187 cananian 1.1.2.1 }
188 cananian 1.1.2.1 // check for phis whose sources are identical
189 cananian 1.1.2.1 // and coalesce them.
190 cananian 1.1.2.1 phidup.clear();
191 cananian 1.1.2.1 for (int i=0; i < q.numPhis(); i++) {
192 cananian 1.1.2.1 Temp[] src = q.src(i);
193 cananian 1.1.2.1 if (phidup.containsKey(src)) { // delete it!
194 cananian 1.1.2.1 int prev = ((Integer) phidup.get(src)).intValue();
195 cananian 1.1.2.1 nm.map(q.dst(i), q.dst(prev));
196 cananian 1.1.2.1 q.removePhi(i--);
197 cananian 1.1.2.8 // this could enable more merging in PHI/SIGMAs that
198 cananian 1.1.2.8 // use q.dst(i) or q.dst(prev)
199 cananian 1.1.2.8 W.addAll(useMap.getValues(q.dst(i)));
200 cananian 1.1.2.8 W.addAll(useMap.getValues(q.dst(prev)));
201 cananian 1.1.2.1 } else phidup.put(src, new Integer(i));
202 cananian 1.1.2.1 }
203 cananian 1.1.2.1 }
204 cananian 1.1.2.1 }
205 cananian 1.1.2.1 private final SortedMap phidup = new TreeMap(new Comparator() {
206 cananian 1.1.2.1 public int compare(Object o1, Object o2) {
207 cananian 1.1.2.1 Temp[] ta1 = (Temp[])o1, ta2 = (Temp[])o2;
208 cananian 1.1.2.1 if (ta1.length!=ta2.length) return ta1.length-ta2.length;
209 cananian 1.1.2.1 for (int i=0; i<ta1.length; i++) {
210 cananian 1.1.2.1 int c = Default.comparator.compare(nm.tempMap(ta1[i]),
211 cananian 1.1.2.1 nm.tempMap(ta2[i]));
212 cananian 1.1.2.1 if (c!=0) return c;
213 cananian 1.1.2.1 }
214 cananian 1.1.2.1 return 0;
215 cananian 1.1.2.1 }
216 cananian 1.1.2.1 });
217 cananian 1.1.2.1
218 cananian 1.1.2.1 public void visit(SIGMA q) {
219 cananian 1.1.2.1 // check for unused function in the sigma
220 cananian 1.1.2.1 L1:
221 cananian 1.1.2.1 for (int i=0; i < q.numSigmas(); i++) {
222 cananian 1.1.2.1 // if any dst is used, skip.
223 cananian 1.1.2.1 for (int j=0; j < q.arity(); j++)
224 cananian 1.1.2.1 if (useful.contains(q.dst(i,j))) continue L1;
225 cananian 1.1.2.1 // safe to delete. ERASER MAN appears.
226 cananian 1.1.2.1 // shrink the sigma function in our secret laboratory.
227 cananian 1.1.2.1 q.removeSigma(i);
228 cananian 1.1.2.1 // decrement index to keep us steady.
229 cananian 1.1.2.1 i--;
230 cananian 1.1.2.1 }
231 cananian 1.1.2.1 // find SIGMAs whose sources are identical, and coalesce them.
232 cananian 1.1.2.1 sigdup.clear();
233 cananian 1.1.2.1 for (int i=0; i < q.numSigmas(); i++) {
234 cananian 1.1.2.1 Temp src = nm.tempMap(q.src(i));
235 cananian 1.1.2.1 if (sigdup.containsKey(src)) { // delete it!
236 cananian 1.1.2.1 int prev = ((Integer) sigdup.get(src)).intValue();
237 cananian 1.1.2.8 for (int j=0; j<q.arity(); j++) {
238 cananian 1.1.2.1 nm.map(q.dst(i,j), q.dst(prev,j));
239 cananian 1.1.2.8 // this could enable more merging in PHI/SIGMAs that
240 cananian 1.1.2.8 // use q.dst(i,j) or q.dst(prev,j)
241 cananian 1.1.2.8 W.addAll(useMap.getValues(q.dst(i,j)));
242 cananian 1.1.2.8 W.addAll(useMap.getValues(q.dst(prev,j)));
243 cananian 1.1.2.8 }
244 cananian 1.1.2.1 q.removeSigma(i--);
245 cananian 1.1.2.1 } else sigdup.put(src, new Integer(i));
246 cananian 1.1.2.1 }
247 cananian 1.1.2.1 }
248 cananian 1.1.2.1 private final SortedMap sigdup = new TreeMap(new Comparator() {
249 cananian 1.1.2.1 public int compare(Object o1, Object o2) {
250 cananian 1.1.2.1 Temp t1 = (Temp)o1, t2 = (Temp)o2;
251 cananian 1.1.2.1 return Default.comparator.compare(nm.tempMap(t1),
252 cananian 1.1.2.1 nm.tempMap(t2));
253 cananian 1.1.2.1 }
254 cananian 1.1.2.1 });
255 cananian 1.1.2.1
256 cananian 1.1.2.1 public void visit(CJMP q) {
257 cananian 1.1.2.1 if (q.next(0)==q.next(1) && !matchPS(q, (PHI)q.next(0))) {
258 cananian 1.1.2.1 // Mu-ha-ha-ha! KILL THE CJMP!
259 cananian 1.1.2.1 // make a pseudo-MOVE for every useful function in this useless sigma.
260 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++)
261 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++)
262 cananian 1.1.2.1 if (useful.contains(q.dst(i,j)))
263 cananian 1.1.2.1 nm.map(q.dst(i,j), q.src(i));
264 cananian 1.1.2.1 // removing this might make a preceding CJMP useless.
265 cananian 1.1.2.1 if (q.prev(0) instanceof CJMP) W.push(q.prev(0));
266 cananian 1.1.2.1 // shrink the phi (and put it on the worklist)
267 cananian 1.1.2.1 ((PHI)q.next(0)).removePred(q.nextEdge(1).which_pred());
268 cananian 1.1.2.1 W.push(q.next(0));
269 cananian 1.1.2.1 // link out the CJMP
270 cananian 1.1.2.1 Quad.addEdge(q.prev(0), q.prevEdge(0).which_succ(),
271 cananian 1.1.2.1 q.next(0), q.nextEdge(0).which_pred());
272 cananian 1.5 useMap.invert().remove(q);
273 cananian 1.1.2.1 } else {
274 cananian 1.1.2.1 // just shrink the functions.
275 cananian 1.1.2.1 visit((SIGMA)q);
276 cananian 1.1.2.1 }
277 cananian 1.1.2.1 }
278 cananian 1.1.2.1 // Determine if (useful) cjmp and phi args match.
279 cananian 1.1.2.1 boolean matchPS(CJMP cj, PHI ph) {
280 cananian 1.1.2.1 // a hashtable makes this easier.
281 cananian 1.1.2.1 PSdup.clear();
282 cananian 1.1.2.1 for (int i=0; i<cj.numSigmas(); i++)
283 cananian 1.1.2.1 for (int j=0; j<cj.arity(); j++)
284 cananian 1.1.2.1 PSdup.put(nm.tempMap(cj.dst(i,j)),
285 cananian 1.1.2.1 nm.tempMap(cj.src(i)));
286 cananian 1.1.2.1
287 cananian 1.1.2.1 int which_pred0 = cj.nextEdge(0).which_pred();
288 cananian 1.1.2.1 int which_pred1 = cj.nextEdge(1).which_pred();
289 cananian 1.1.2.1 for (int i=0; i<ph.numPhis(); i++) {
290 cananian 1.1.2.1 if (!useful.contains(nm.tempMap(ph.dst(i))))
291 cananian 1.1.2.1 continue; // not useful, skip.
292 cananian 1.1.2.1 if (PSdup.get(nm.tempMap(ph.src(i,which_pred0))) !=
293 cananian 1.1.2.1 PSdup.get(nm.tempMap(ph.src(i,which_pred1))) )
294 cananian 1.1.2.1 return true; // cjmp matters, either in sig or phi.
295 cananian 1.1.2.1 }
296 cananian 1.1.2.1 return false; // not useful!
297 cananian 1.1.2.1 }
298 cananian 1.1.2.1 private final Map PSdup = new HashMap();
299 cananian 1.1.2.1 }
300 cananian 1.1.2.1
301 cananian 1.1.2.1 static class NameMap implements TempMap {
302 cananian 1.1.2.1 Map h = new HashMap();
303 cananian 1.1.2.1 public Temp tempMap(Temp t) {
304 cananian 1.1.2.1 while (h.containsKey(t))
305 cananian 1.1.2.1 t = (Temp) h.get(t);
306 cananian 1.1.2.1 return t;
307 cananian 1.1.2.1 }
308 cananian 1.1.2.1 public void map(Temp Told, Temp Tnew) { h.put(Told, Tnew); }
309 cananian 1.1.2.1 public String toString() { return h.toString(); }
310 cananian 1.1.2.1 }
311 cananian 1.1.2.1
312 cananian 1.1.2.1 static class UsefulVisitor extends LowQuadVisitor {
313 cananian 1.1.2.1 Worklist W;
314 cananian 1.1.2.1 Set useful;
315 cananian 1.1.2.1 Map defMap;
316 cananian 1.1.2.1 NameMap nm;
317 cananian 1.1.2.1 // maps cjmp targets past useless cjmps/phis
318 cananian 1.1.2.1 Map jmpMap = new HashMap();
319 cananian 1.1.2.1 // maps phi sources past useless cjmps/phis
320 cananian 1.1.2.1 Map phiMap = new HashMap();
321 cananian 1.1.2.1
322 cananian 1.1.2.1 UsefulVisitor(Worklist W, Set useful, Map defMap, NameMap nm) {
323 cananian 1.1.2.6 super(false/*non-strict*/);
324 cananian 1.1.2.1 this.W = W;
325 cananian 1.1.2.1 this.useful = useful;
326 cananian 1.1.2.1 this.defMap = defMap;
327 cananian 1.1.2.1 this.nm = nm;
328 cananian 1.1.2.1 }
329 cananian 1.1.2.1 void markUseful(Quad q) {
330 cananian 1.1.2.1 if (useful.contains(q)) return; // no change.
331 cananian 1.1.2.1 useful.add(q);
332 cananian 1.1.2.1 // all variables used by a useful quad are useful.
333 cananian 1.1.2.1 Temp u[] = q.use();
334 cananian 1.1.2.1 for (int i=0; i<u.length; i++)
335 cananian 1.1.2.1 markUseful(u[i]);
336 cananian 1.1.2.1 }
337 cananian 1.1.2.1 void markUseful(Temp t) {
338 cananian 1.1.2.1 if (useful.contains(t)) return; // no change.
339 cananian 1.1.2.1 useful.add(t);
340 cananian 1.1.2.1 // the quad defining this temp is now useful, too.
341 cananian 1.1.2.1 if (defMap.containsKey(t)) // undefined vars possible.
342 cananian 1.1.2.1 W.push(defMap.get(t));
343 cananian 1.1.2.1 }
344 cananian 1.1.2.1 public void visit(Quad q) {
345 cananian 1.1.2.1 boolean usefound = false;
346 cananian 1.1.2.1 // by default, a quad is useful iff what it defines is useful.
347 cananian 1.1.2.1 Temp d[] = q.def();
348 cananian 1.1.2.1 for (int i=0; i<d.length; i++)
349 cananian 1.1.2.1 if (useful.contains(d[i]))
350 cananian 1.1.2.1 usefound = true;
351 cananian 1.1.2.1 // statements that define no variables are safe, however.
352 cananian 1.1.2.1 if (d.length==0) usefound = true;
353 cananian 1.1.2.1 // if it's useful, mark it.
354 cananian 1.1.2.1 if (usefound)
355 cananian 1.1.2.1 markUseful(q);
356 cananian 1.1.2.1 }
357 cananian 1.1.2.1
358 cananian 1.1.2.1 public void visit(ARRAYINIT q) { // always useful.
359 cananian 1.1.2.1 markUseful(q);
360 cananian 1.1.2.1 }
361 cananian 1.1.2.1
362 cananian 1.1.2.1 public void visit(PSET q) {
363 cananian 1.1.2.1 // Pointer writes may be useful
364 cananian 1.1.2.1 markUseful(q);
365 cananian 1.1.2.1 }
366 cananian 1.1.2.1
367 cananian 1.1.2.3 public void visit(PCALL q) {
368 cananian 1.1.2.3 // all PCALLs are useful (may have side-effects)
369 cananian 1.1.2.3 useful.add(q);
370 cananian 1.1.2.3 // any variables used are useful.
371 cananian 1.1.2.3 for (int i=0; i<q.paramsLength(); i++)
372 cananian 1.1.2.3 markUseful(q.params(i));
373 cananian 1.1.2.3 markUseful(q.retex());
374 bdemsky 1.1.2.5 markUseful(q.ptr());
375 cananian 1.1.2.3 if (q.retval()!=null) markUseful(q.retval());
376 cananian 1.1.2.3 // process sigmas normally
377 cananian 1.1.2.3 visit((SIGMA)q);
378 cananian 1.1.2.3 }
379 cananian 1.1.2.3 public void visit(CALL q) {
380 cananian 1.1.2.3 // all CALLs are useful (may have side-effects)
381 cananian 1.1.2.3 useful.add(q);
382 cananian 1.1.2.3 // any variables used are useful.
383 cananian 1.1.2.3 for (int i=0; i<q.paramsLength(); i++)
384 cananian 1.1.2.3 markUseful(q.params(i));
385 cananian 1.1.2.3 markUseful(q.retex());
386 cananian 1.1.2.3 if (q.retval()!=null) markUseful(q.retval());
387 cananian 1.1.2.3 // process sigmas normally
388 cananian 1.1.2.3 visit((SIGMA)q);
389 cananian 1.1.2.3 }
390 cananian 1.1.2.1 public void visit(CJMP q) {
391 cananian 1.1.2.1 // assume all CJMPs are useful (we'll remove useless ones later)
392 cananian 1.1.2.1 useful.add(q);
393 cananian 1.1.2.1 // if this is useful, the condition is useful
394 cananian 1.1.2.1 markUseful(q.test());
395 cananian 1.1.2.1 // process sigmas normally.
396 cananian 1.1.2.1 visit((SIGMA)q);
397 cananian 1.1.2.1 }
398 cananian 1.1.2.1 public void visit(FOOTER q) { // always useful.
399 cananian 1.1.2.1 markUseful(q);
400 cananian 1.1.2.1 }
401 cananian 1.1.2.1 public void visit(HANDLER q) { // ACK! never should find.
402 cananian 1.3.2.1 assert false : "DeadCode doesn't work with HANDLERs.";
403 cananian 1.1.2.1 }
404 cananian 1.1.2.1 public void visit(HEADER q) { // always useful.
405 cananian 1.1.2.1 markUseful(q);
406 cananian 1.1.2.1 }
407 cananian 1.1.2.1 public void visit(METHOD q) { // always useful.
408 cananian 1.1.2.1 markUseful(q);
409 cananian 1.1.2.1 }
410 cananian 1.1.2.1 public void visit(MONITORENTER q) { // always useful.
411 cananian 1.1.2.1 markUseful(q);
412 cananian 1.1.2.1 }
413 cananian 1.1.2.1 public void visit(MONITOREXIT q) { // always useful.
414 cananian 1.1.2.1 markUseful(q);
415 cananian 1.1.2.1 }
416 cananian 1.1.2.1 public void visit(MOVE q) { // moves are never useful (add to rename map)
417 cananian 1.1.2.1 if (useful.contains(q.dst())) {
418 cananian 1.1.2.1 markUseful(q.src());
419 cananian 1.1.2.1 nm.map(q.dst(), q.src());
420 cananian 1.1.2.1 }
421 cananian 1.1.2.1 }
422 cananian 1.1.2.1 public void visit(NOP q) { // never useful.
423 cananian 1.1.2.1 }
424 cananian 1.1.2.1 public void visit(PHI q) {
425 cananian 1.1.2.1 // Assume all phis are useful (will remove arity-1 phis later)
426 cananian 1.1.2.1 useful.add(q);
427 cananian 1.1.2.1 // check the individual phi functions for usefulness.
428 cananian 1.1.2.1 for (int i=0; i < q.numPhis(); i++)
429 cananian 1.1.2.1 if (useful.contains(q.dst(i)))
430 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++)
431 cananian 1.1.2.1 markUseful(q.src(i,j));
432 cananian 1.1.2.1 }
433 cananian 1.1.2.1 public void visit(RETURN q) { // always useful.
434 cananian 1.1.2.1 markUseful(q);
435 cananian 1.1.2.1 }
436 cananian 1.1.2.1 public void visit(SET q) { // always useful.
437 cananian 1.1.2.1 markUseful(q);
438 cananian 1.1.2.1 }
439 cananian 1.1.2.1 public void visit(SIGMA q) {
440 cananian 1.1.2.1 // Sigmas are useful iff one of the definitions is useful.
441 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++) {
442 cananian 1.1.2.1 if (useful.contains(q.src(i))) continue; //skip already useful sigs.
443 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++)
444 cananian 1.1.2.1 if (useful.contains(q.dst(i,j))) // this one's (newly) useful.
445 cananian 1.1.2.1 markUseful(q.src(i));
446 cananian 1.1.2.1 }
447 cananian 1.1.2.1 }
448 cananian 1.1.2.1 public void visit(SWITCH q) {
449 cananian 1.1.2.1 // I'm too lazy to see if the switch actually does anything, so assume
450 cananian 1.1.2.7 // it's always useful.
451 cananian 1.1.2.7 useful.add(q);
452 cananian 1.1.2.7 markUseful(q.index());
453 cananian 1.1.2.7 visit((SIGMA)q);
454 cananian 1.1.2.7 }
455 cananian 1.1.2.7 public void visit(TYPESWITCH q) {
456 cananian 1.1.2.7 // I'm too lazy to see if the typeswitch actually does anything, so assume
457 cananian 1.1.2.1 // it's always useful.
458 cananian 1.1.2.1 useful.add(q);
459 cananian 1.1.2.1 markUseful(q.index());
460 cananian 1.1.2.1 visit((SIGMA)q);
461 cananian 1.1.2.1 }
462 cananian 1.1.2.1 public void visit(THROW q) { // always useful.
463 cananian 1.1.2.1 markUseful(q);
464 cananian 1.1.2.1 }
465 cananian 1.1.2.1 }
466 cananian 1.2 }