1 kkz 1.1 // DynamicWBQuadPass.java, created Wed May 29 12:05:56 2002 by kkz
2 kkz 1.1 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.mit.edu>
3 kkz 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1 package harpoon.Analysis.PreciseGC;
5 kkz 1.1
6 kkz 1.1 import harpoon.Analysis.AllocationInformationMap;
7 kkz 1.1 import harpoon.Analysis.AllocationInformationMap.AllocationPropertiesImpl;
8 kkz 1.1 import harpoon.Analysis.ClassHierarchy;
9 kkz 1.1 import harpoon.Analysis.DefaultAllocationInformation;
10 kkz 1.1 import harpoon.Analysis.Maps.AllocationInformation;
11 kkz 1.1 import harpoon.Analysis.Maps.AllocationInformation.AllocationProperties;
12 kkz 1.1 import harpoon.ClassFile.HClass;
13 kkz 1.1 import harpoon.ClassFile.HCode;
14 kkz 1.1 import harpoon.ClassFile.HCodeAndMaps;
15 kkz 1.1 import harpoon.ClassFile.HCodeFactory;
16 kkz 1.1 import harpoon.ClassFile.HConstructor;
17 kkz 1.1 import harpoon.ClassFile.HMethod;
18 kkz 1.1 import harpoon.ClassFile.Linker;
19 kkz 1.1 import harpoon.IR.Properties.CFGEdge;
20 kkz 1.1 import harpoon.IR.Quads.ANEW;
21 kkz 1.1 import harpoon.IR.Quads.ARRAYINIT;
22 kkz 1.1 import harpoon.IR.Quads.ASET;
23 kkz 1.1 import harpoon.IR.Quads.CALL;
24 kkz 1.1 import harpoon.IR.Quads.Code;
25 kkz 1.1 import harpoon.IR.Quads.Edge;
26 kkz 1.1 import harpoon.IR.Quads.FOOTER;
27 kkz 1.1 import harpoon.IR.Quads.HEADER;
28 kkz 1.1 import harpoon.IR.Quads.METHOD;
29 kkz 1.1 import harpoon.IR.Quads.MOVE;
30 kkz 1.1 import harpoon.IR.Quads.NEW;
31 kkz 1.1 import harpoon.IR.Quads.PHI;
32 kkz 1.1 import harpoon.IR.Quads.Quad;
33 kkz 1.1 import harpoon.IR.Quads.QuadFactory;
34 kkz 1.1 import harpoon.IR.Quads.RETURN;
35 kkz 1.1 import harpoon.IR.Quads.SET;
36 kkz 1.1 import harpoon.IR.Quads.SIGMA;
37 kkz 1.1 import harpoon.IR.Quads.THROW;
38 kkz 1.1 import harpoon.Temp.Temp;
39 kkz 1.1 import harpoon.Util.Worklist;
40 kkz 1.1 import harpoon.Util.Collections.WorkSet;
41 kkz 1.1
42 kkz 1.1 import java.util.Collections;
43 kkz 1.1 import java.util.HashMap;
44 kkz 1.1 import java.util.HashSet;
45 kkz 1.1 import java.util.Iterator;
46 kkz 1.1 import java.util.Map;
47 kkz 1.1 import java.util.Set;
48 kkz 1.1
49 kkz 1.1 /**
50 kkz 1.1 * <code>DynamicWBQuadPass</code> inserts dynamic write barriers, where
51 kkz 1.1 * possible and identifies <code>SET</code>s and <code>ASET</code>s for which
52 kkz 1.1 * static write barriers are unnecessary.
53 kkz 1.1 *
54 kkz 1.1 * Operates on <code>QuadSSA</code> and <code>QuadSSI</code>.
55 kkz 1.1 *
56 kkz 1.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
57 cananian 1.2 * @version $Id: DynamicWBQuadPass.java,v 1.2 2004/02/08 03:20:07 cananian Exp $
58 kkz 1.1 */
59 kkz 1.1 public class DynamicWBQuadPass
60 kkz 1.1 extends harpoon.Analysis.Transformation.MethodMutator
61 kkz 1.1 implements WriteBarrierInserter.WriteBarrierAnalysis {
62 kkz 1.1
63 kkz 1.1 final static boolean DEBUG1 = false;
64 kkz 1.1 final static boolean DEBUG2 = false;
65 kkz 1.1 final static boolean DEBUG3 = false;
66 kkz 1.1 final static boolean DEBUG4 = false;
67 kkz 1.1
68 kkz 1.1 private final HMethod clearBitHM;
69 kkz 1.1 private final Map ignoreMap = new HashMap(); /* maps Codes to Sets */
70 kkz 1.1
71 kkz 1.1 /** Creates a <code>DynamicWBQuadPass</code>. */
72 kkz 1.1 public DynamicWBQuadPass(HCodeFactory parent, Linker linker) {
73 kkz 1.1 super(parent);
74 kkz 1.1 clearBitHM = linker.forName
75 kkz 1.1 ("harpoon.Runtime.PreciseGC.WriteBarrier").getMethod
76 kkz 1.1 ("clearBit", new HClass[] {linker.forName("java.lang.Object")});
77 kkz 1.1 }
78 kkz 1.1
79 kkz 1.1 protected HCode mutateHCode(HCodeAndMaps input) {
80 kkz 1.1 Code hc = (Code) input.hcode();
81 kkz 1.1 //DEBUG4 = hc.getMethod().getName().equals("rehash");
82 kkz 1.1 /*
83 kkz 1.1 if (hc.getMethod().getName().equals("<init>") &&
84 kkz 1.1 hc.getMethod().getDeclaringClass().getName().equals("Branch")) {
85 kkz 1.1 hc.print(new java.io.PrintWriter(System.out), null);
86 kkz 1.1 System.exit(0);
87 kkz 1.1 } */
88 kkz 1.1 AllocationInformationMap aim =
89 kkz 1.1 (AllocationInformationMap) hc.getAllocationInformation();
90 kkz 1.1 // code may not have any associated allocation information
91 kkz 1.1 if (aim == null) {
92 kkz 1.1 aim = new AllocationInformationMap();
93 kkz 1.1 hc.setAllocationInformation(aim);
94 kkz 1.1 }
95 kkz 1.1 // first, collect allocations and Temps
96 kkz 1.1 InitVisitor iv = new InitVisitor();
97 kkz 1.1 for(Iterator it = hc.getElementsI(); it.hasNext(); ) {
98 kkz 1.1 Quad q = (Quad) it.next();
99 kkz 1.1 q.accept(iv);
100 kkz 1.1 }
101 kkz 1.1 FOOTER footer = ((HEADER) hc.getRootElement()).footer();
102 kkz 1.1 // handle object allocations that are not arrays
103 cananian 1.2 for (Object onewO : iv.NEWs) {
104 cananian 1.2 NEW onew = (NEW) onewO;
105 kkz 1.1 if (DEBUG2) System.out.println("\nSET @ \t" + onew);
106 kkz 1.1 associateAllocationProperties(onew, aim, true);
107 kkz 1.1 ObjectAnalysisVisitor oav =
108 kkz 1.1 new ObjectAnalysisVisitor(onew, iv.allTemps, hc);
109 kkz 1.1 // insert clear after CALL to constructor
110 cananian 1.2 for (Object callO : oav.CALLs) {
111 cananian 1.2 CALL call = (CALL) callO;
112 kkz 1.1 if (DEBUG2) System.out.println("\tCLEAR @ \t" + call);
113 kkz 1.1 Temp dst = call.params(0);
114 kkz 1.1 footer = insertClearAfter(call, dst, footer);
115 kkz 1.1 }
116 kkz 1.1 }
117 kkz 1.1 // set of Quads for this method for which write barriers
118 kkz 1.1 // are not required
119 kkz 1.1 Set ignore = new HashSet();
120 kkz 1.1 // handle Object array allocations
121 cananian 1.2 for (Object anewO : iv.ANEWs) {
122 cananian 1.2 ANEW anew = (ANEW) anewO;
123 kkz 1.1 ArrayAnalysisVisitor aav =
124 kkz 1.1 new ArrayAnalysisVisitor(anew, iv.allTemps, hc);
125 kkz 1.1 if (!aav.ARRAYINITs.isEmpty() || !aav.ASETs.isEmpty()) {
126 kkz 1.1 if (DEBUG3) {
127 kkz 1.1 System.out.println("ANEW: "+anew);
128 kkz 1.1 System.out.println("ARRAYINITs: ");
129 kkz 1.1 for(Iterator it2 = aav.ARRAYINITs.iterator();
130 kkz 1.1 it2.hasNext(); )
131 kkz 1.1 System.out.println("\t" + it2.next());
132 kkz 1.1 System.out.println("\nASETs: ");
133 kkz 1.1 for(Iterator it2 = aav.ASETs.iterator();
134 kkz 1.1 it2.hasNext(); )
135 kkz 1.1 System.out.println("\t" + it2.next());
136 kkz 1.1 System.out.println("\nneedClear: ");
137 cananian 1.2 for(Object keyO : aav.needClear.keySet()) {
138 cananian 1.2 Edge key = (Edge) keyO;
139 kkz 1.1 System.out.println("\t" + key.from() + " -> " +
140 kkz 1.1 key.to() + " (" +
141 kkz 1.1 aav.needClear.get(key) + ")");
142 kkz 1.1 }
143 kkz 1.1 System.out.println("\n");
144 kkz 1.1 }
145 cananian 1.2 for (Object keyO : aav.needClear.keySet()) {
146 cananian 1.2 Edge key = (Edge) keyO;
147 kkz 1.1 Temp dst = (Temp) aav.needClear.get(key);
148 kkz 1.1 footer = insertClear((Quad) key.to(), key, dst, footer);
149 kkz 1.1 }
150 kkz 1.1 //hc.print(new java.io.PrintWriter(System.out), null);
151 kkz 1.1 associateAllocationProperties(anew, aim, true);
152 kkz 1.1 } else {
153 kkz 1.1 associateAllocationProperties(anew, aim, false);
154 kkz 1.1 }
155 kkz 1.1 // compile ASETs that do not need write barriers
156 kkz 1.1 ignore.addAll(aav.ASETs);
157 kkz 1.1 }
158 kkz 1.1 // handle primitive array allocations
159 kkz 1.1 for (Iterator it = iv.primitiveANEWs.iterator(); it.hasNext(); ) {
160 kkz 1.1 associateAllocationProperties((ANEW) it.next(), aim, false);
161 kkz 1.1 }
162 kkz 1.1 // handle constructors--any assignments to receiver object
163 kkz 1.1 // should optimistically have write barriers removed
164 kkz 1.1 if (hc.getMethod() instanceof HConstructor) {
165 kkz 1.1 ConstructorVisitor cv = new ConstructorVisitor(iv.allTemps, hc);
166 kkz 1.1 ignore.addAll(cv.SETs);
167 kkz 1.1 }
168 kkz 1.1 // add results to map
169 kkz 1.1 ignoreMap.put(hc.getMethod(), ignore);
170 kkz 1.1 return hc;
171 kkz 1.1 }
172 kkz 1.1
173 kkz 1.1 /* returns an unmodifiable <code>Set</code> of the <code>Quad</code>s
174 kkz 1.1 * for which write barriers have been optimistically removed.
175 kkz 1.1 */
176 kkz 1.1 public Set getIgnoreSet(Code hc) {
177 kkz 1.1 return Collections.unmodifiableSet((Set)ignoreMap.get(hc.getMethod()));
178 kkz 1.1 }
179 kkz 1.1
180 kkz 1.1 // modify the given AllocationInformationMap so that the
181 kkz 1.1 // AllocationProperties associated with Quad q has its
182 kkz 1.1 // setDynamicWBFlag property set accordingly
183 kkz 1.1 private void associateAllocationProperties(Quad q,
184 kkz 1.1 AllocationInformationMap aim,
185 kkz 1.1 boolean setDynamicWBFlag) {
186 kkz 1.1 AllocationProperties ap = aim.query(q);
187 kkz 1.1 if (ap == null)
188 kkz 1.1 ap = DefaultAllocationInformation.SINGLETON.query(q);
189 kkz 1.1 aim.associate(q, new AllocationPropertiesImpl
190 kkz 1.1 (ap.hasInteriorPointers(),
191 kkz 1.1 ap.canBeStackAllocated(),
192 kkz 1.1 ap.canBeThreadAllocated(),
193 kkz 1.1 ap.makeHeap(),
194 kkz 1.1 ap.noSync(),
195 kkz 1.1 ap.allocationHeap(),
196 kkz 1.1 ap.actualClass(),
197 kkz 1.1 setDynamicWBFlag));
198 kkz 1.1 }
199 kkz 1.1
200 kkz 1.1 // insert a placeholder CALL after the given Quad to
201 kkz 1.1 // mark where we should clear the dynamic write
202 kkz 1.1 // barrier bit for the object to which t refers.
203 kkz 1.1 // requires: that t refer to the object on the
204 kkz 1.1 // outgoing edge of q unless q is a SIGMA,
205 kkz 1.1 // in which case t needs to refer to the
206 kkz 1.1 // object on the incoming edge of the
207 kkz 1.1 // SIGMA, since the object reference may be
208 kkz 1.1 // different for each outgoing edge of the
209 kkz 1.1 // SIGMA. remapping is done here.
210 kkz 1.1 private FOOTER insertClearAfter(Quad q, Temp t, FOOTER footer) {
211 kkz 1.1 // special handling for SIGMAs
212 kkz 1.1 if (q instanceof SIGMA) {
213 kkz 1.1 SIGMA sigma = (SIGMA) q;
214 kkz 1.1 for(int i = 0; i < sigma.nextLength(); i++) {
215 kkz 1.1 Temp renamed = null;
216 kkz 1.1 for(int j = 0; j < sigma.numSigmas(); j++) {
217 kkz 1.1 if (sigma.src(j).equals(t)) {
218 kkz 1.1 renamed = sigma.dst(j, i);
219 kkz 1.1 break;
220 kkz 1.1 }
221 kkz 1.1 }
222 kkz 1.1 if (renamed == null)
223 kkz 1.1 footer = insertClear(sigma, sigma.nextEdge(i), t, footer);
224 kkz 1.1 else
225 kkz 1.1 footer = insertClear
226 kkz 1.1 (sigma, sigma.nextEdge(i), renamed, footer);
227 kkz 1.1 }
228 kkz 1.1 } else {
229 kkz 1.1 for(int i = 0; i < q.nextLength(); i++)
230 kkz 1.1 footer = insertClear(q, q.nextEdge(i), t, footer);
231 kkz 1.1 }
232 kkz 1.1 return footer;
233 kkz 1.1 }
234 kkz 1.1
235 kkz 1.1 // helper function to insert placeholder CALL on given Edge
236 kkz 1.1 private FOOTER insertClear(Quad q, Edge e, Temp t, FOOTER f) {
237 kkz 1.1 QuadFactory qf = q.getFactory();
238 kkz 1.1 Temp clearexT = new Temp(qf.tempFactory(), "clearex");
239 kkz 1.1 Quad q1 = new CALL(qf, q, clearBitHM,
240 kkz 1.1 new Temp[] { t }, null, clearexT,
241 kkz 1.1 false, false, new Temp[0]);
242 kkz 1.1 Quad q2 = new THROW(qf, q, clearexT);
243 kkz 1.1 Quad.addEdge((Quad) e.from(), e.which_succ(), q1, 0);
244 kkz 1.1 Quad.addEdge(q1, 0, (Quad) e.to(), e.which_pred());
245 kkz 1.1 Quad.addEdge(q1, 1, q2, 0);
246 kkz 1.1 return f.attach(q2, 0);
247 kkz 1.1 }
248 kkz 1.1
249 kkz 1.1 private static class InitVisitor extends
250 kkz 1.1 harpoon.IR.Quads.QuadVisitor {
251 kkz 1.1
252 kkz 1.1 final Set allTemps = new HashSet();
253 kkz 1.1 final Set ANEWs = new HashSet();
254 kkz 1.1 final Set primitiveANEWs = new HashSet();
255 kkz 1.1 final Set NEWs = new HashSet();
256 kkz 1.1
257 kkz 1.1 public void visit(ANEW q) {
258 kkz 1.1 if (!q.hclass().getComponentType().isPrimitive())
259 kkz 1.1 ANEWs.add(q);
260 kkz 1.1 else
261 kkz 1.1 primitiveANEWs.add(q);
262 kkz 1.1 visit((Quad)q);
263 kkz 1.1 }
264 kkz 1.1
265 kkz 1.1 public void visit(NEW q) {
266 kkz 1.1 assert !q.hclass().isPrimitive();
267 kkz 1.1 NEWs.add(q);
268 kkz 1.1 visit((Quad)q);
269 kkz 1.1 }
270 kkz 1.1
271 kkz 1.1 public void visit(Quad q) {
272 kkz 1.1 allTemps.addAll(q.useC());
273 kkz 1.1 allTemps.addAll(q.defC());
274 kkz 1.1 }
275 kkz 1.1 }
276 kkz 1.1
277 kkz 1.1 private static class ConstructorVisitor extends AliasAnalysisVisitor {
278 kkz 1.1 final Set SETs = new HashSet();
279 kkz 1.1
280 kkz 1.1 ConstructorVisitor(Set allTemps, Code hc) {
281 kkz 1.1 super(allTemps);
282 kkz 1.1 HEADER header = (HEADER) hc.getRootElement();
283 kkz 1.1 METHOD method = (METHOD) header.next(1);
284 kkz 1.1 // initialize dataflow fact for METHOD
285 kkz 1.1 Set aliases = new HashSet();
286 kkz 1.1 aliases.add(method.params(0));
287 kkz 1.1 // perform analysis
288 kkz 1.1 analyze(method, aliases);
289 kkz 1.1 // find SETs of fields of the receiver object
290 kkz 1.1 for(Iterator it = hc.getElementsI(); it.hasNext(); ) {
291 kkz 1.1 Quad q = (Quad) it.next();
292 kkz 1.1 if (q instanceof SET) {
293 kkz 1.1 SET set = (SET) q;
294 kkz 1.1 Set aliases2 = get(q.prevEdge(0));
295 kkz 1.1 if (aliases2.contains(set.objectref())) {
296 kkz 1.1 SETs.add(set);
297 kkz 1.1 }
298 kkz 1.1 }
299 kkz 1.1 }
300 kkz 1.1 }
301 kkz 1.1 }
302 kkz 1.1
303 kkz 1.1 private static class ObjectAnalysisVisitor extends AliasAnalysisVisitor {
304 kkz 1.1 private final NEW alloc;
305 kkz 1.1 final Set CALLs = new HashSet();
306 kkz 1.1
307 kkz 1.1 ObjectAnalysisVisitor(NEW alloc, Set allTemps, Code hc) {
308 kkz 1.1 super(allTemps);
309 kkz 1.1 this.alloc = alloc;
310 kkz 1.1 // initialize dataflow fact for NEW
311 kkz 1.1 Set aliases = new HashSet();
312 kkz 1.1 aliases.add(alloc.dst());
313 kkz 1.1 // perform analysis
314 kkz 1.1 analyze(alloc, aliases);
315 kkz 1.1 // find CALLs to constructor for this object allocation site
316 kkz 1.1 for(Iterator it = hc.getElementsI(); it.hasNext(); ) {
317 kkz 1.1 Quad q = (Quad) it.next();
318 kkz 1.1 if (q instanceof CALL) {
319 kkz 1.1 CALL call = (CALL) q;
320 kkz 1.1 HMethod hm = (HMethod) call.method();
321 kkz 1.1 if (hm instanceof HConstructor &&
322 kkz 1.1 hm.getDeclaringClass().compareTo(alloc.hclass()) == 0) {
323 kkz 1.1 Set aliases2 = get(q.prevEdge(0));
324 kkz 1.1 if (aliases2.contains(call.params(0))) {
325 kkz 1.1 CALLs.add(call);
326 kkz 1.1 }
327 kkz 1.1 }
328 kkz 1.1 }
329 kkz 1.1 }
330 kkz 1.1 }
331 kkz 1.1
332 kkz 1.1 public void visit(NEW q) {
333 kkz 1.1 if (q == alloc) {
334 kkz 1.1 Set aliases = new HashSet(get(q.prevEdge(0)));
335 kkz 1.1 aliases.add(q.dst());
336 kkz 1.1 raiseValue(q.nextEdge(0), aliases);
337 kkz 1.1 } else {
338 kkz 1.1 visit((Quad)q);
339 kkz 1.1 }
340 kkz 1.1 }
341 kkz 1.1 }
342 kkz 1.1
343 kkz 1.1 private static class ArrayAnalysisVisitor extends AliasAnalysisVisitor {
344 kkz 1.1 private final ANEW alloc;
345 kkz 1.1 final Set ARRAYINITs = new HashSet();
346 kkz 1.1 final Set ASETs = new HashSet();
347 kkz 1.1 final Map needClear = new HashMap();
348 kkz 1.1
349 kkz 1.1 ArrayAnalysisVisitor(ANEW alloc, Set allTemps, Code hc) {
350 kkz 1.1 super(allTemps);
351 kkz 1.1 this.alloc = alloc;
352 kkz 1.1 // initialize dataflow fact for ANEW
353 kkz 1.1 Set aliases = new HashSet();
354 kkz 1.1 aliases.add(alloc.dst());
355 kkz 1.1 // begin analysis
356 kkz 1.1 analyze(alloc, aliases);
357 kkz 1.1 // find array assignments for this array
358 kkz 1.1 // allocation site using depth-first search
359 kkz 1.1 markQuads(alloc, null, get(alloc.prevEdge(0)), new HashSet());
360 kkz 1.1 }
361 kkz 1.1
362 kkz 1.1 // depth-first search algorithm for marking Quads
363 kkz 1.1 // that are SETs, ASETs, or require a clear
364 kkz 1.1 // requires: that lastQ be the most recent ASET or
365 kkz 1.1 // ARRAYINIT at which lastAlias referred
366 kkz 1.1 // to an alias of the object allocated at
367 kkz 1.1 // the given allocation site
368 kkz 1.1 private void markQuads(Quad q, Edge prevE, Set aliases, Set visited) {
369 kkz 1.1 if (DEBUG4) System.out.println(q);
370 kkz 1.1 // already working on this Quad
371 kkz 1.1 if (visited.contains(q)) return;
372 kkz 1.1 if (!(q instanceof PHI)) visited.add(q);
373 kkz 1.1 // find assignments for this allocation site
374 kkz 1.1 if (q instanceof ASET) {
375 kkz 1.1 Temp objectref = ((ASET) q).objectref();
376 kkz 1.1 if (aliases.contains(objectref))
377 kkz 1.1 ASETs.add(q);
378 kkz 1.1 } else if (q instanceof ARRAYINIT) {
379 kkz 1.1 Temp objectref = ((ARRAYINIT) q).objectref();
380 kkz 1.1 if (aliases.contains(objectref))
381 kkz 1.1 ARRAYINITs.add(q);
382 kkz 1.1 }
383 kkz 1.1 // find Quads where a clear is needed
384 kkz 1.1 if (q instanceof RETURN || q instanceof THROW) {
385 kkz 1.1 needClear.put(prevE, aliases.iterator().next());
386 kkz 1.1 } else {
387 kkz 1.1 for (int i = 0; i < q.nextLength(); i++) {
388 kkz 1.1 Edge nextE = q.nextEdge(i);
389 kkz 1.1 Set next = get(nextE);
390 kkz 1.1 if (next.isEmpty()) {
391 kkz 1.1 needClear.put(prevE, aliases.iterator().next());
392 kkz 1.1 } else {
393 kkz 1.1 markQuads(q.next(i), nextE, next, visited);
394 kkz 1.1 }
395 kkz 1.1 }
396 kkz 1.1 }
397 kkz 1.1 }
398 kkz 1.1
399 kkz 1.1 public void visit(ANEW q) {
400 kkz 1.1 if (q == alloc) {
401 kkz 1.1 Set aliases = new HashSet(get(q.prevEdge(0)));
402 kkz 1.1 aliases.add(q.dst());
403 kkz 1.1 raiseValue(q.nextEdge(0), aliases);
404 kkz 1.1 } else {
405 kkz 1.1 visit((Quad)q);
406 kkz 1.1 }
407 kkz 1.1 }
408 kkz 1.1 }
409 kkz 1.1
410 kkz 1.1 private static class AliasAnalysisVisitor extends
411 kkz 1.1 harpoon.IR.Quads.QuadVisitor {
412 kkz 1.1
413 kkz 1.1 protected final Set allTemps;
414 kkz 1.1 protected final Worklist toDo = new WorkSet();
415 kkz 1.1
416 kkz 1.1 // map of CFGEdges to aliases (Sets of Temps)
417 kkz 1.1 protected final Map EdgeToTemps = new HashMap();
418 kkz 1.1
419 kkz 1.1 AliasAnalysisVisitor(Set allTemps) {
420 kkz 1.1 this.allTemps = allTemps;
421 kkz 1.1 }
422 kkz 1.1
423 kkz 1.1 // requires: that start has outgoing arity of 1
424 kkz 1.1 protected void analyze(Quad start, Set aliases) {
425 kkz 1.1 assert start.nextLength() == 1;
426 kkz 1.1 // initialize dataflow facts
427 kkz 1.1 EdgeToTemps.put(start.nextEdge(0), aliases);
428 kkz 1.1 // initialize to-do list
429 kkz 1.1 toDo.push(start.next(0));
430 kkz 1.1 // go, gadget, go!
431 kkz 1.1 while(!toDo.isEmpty()) {
432 kkz 1.1 Quad q = (Quad) toDo.pull();
433 kkz 1.1 if (DEBUG1) System.out.println(q);
434 kkz 1.1 q.accept(this);
435 kkz 1.1 }
436 kkz 1.1 }
437 kkz 1.1
438 kkz 1.1 public void visit(CALL q) {
439 kkz 1.1 assert q.prevLength() == 1;
440 kkz 1.1 Set aliases = get(q.prevEdge(0));
441 kkz 1.1 // handle normal edge
442 kkz 1.1 Temp retval = q.retval();
443 kkz 1.1 if (retval != null)
444 kkz 1.1 aliases.remove(retval);
445 kkz 1.1 handleSIGMAEdge(q, new HashSet(aliases), 0);
446 kkz 1.1 // handle exception edge
447 kkz 1.1 Temp retex = q.retex();
448 kkz 1.1 if (retex != null) {
449 kkz 1.1 aliases.remove(retex);
450 kkz 1.1 // if retex == null, then the CALL has only
451 kkz 1.1 // one outgoing edge (only happens in quad-
452 kkz 1.1 // with-try), so only handle exception edge
453 kkz 1.1 // if retex != null
454 kkz 1.1 handleSIGMAEdge(q, new HashSet(aliases), 1);
455 kkz 1.1 }
456 kkz 1.1 }
457 kkz 1.1
458 kkz 1.1 public void visit(FOOTER q) { /* do nothing */ }
459 kkz 1.1
460 kkz 1.1 public void visit(MOVE q) {
461 kkz 1.1 assert q.prevLength() == 1 && q.nextLength() == 1;
462 kkz 1.1 Set aliases = new HashSet(get(q.prevEdge(0)));
463 kkz 1.1 if (aliases.contains(q.src()))
464 kkz 1.1 aliases.add(q.dst());
465 kkz 1.1 else
466 kkz 1.1 aliases.remove(q.dst());
467 kkz 1.1 raiseValue(q.nextEdge(0), aliases);
468 kkz 1.1 }
469 kkz 1.1
470 kkz 1.1 public void visit (PHI q) {
471 kkz 1.1 // start with edge 0
472 kkz 1.1 Set aliases = get(q.prevEdge(0));
473 kkz 1.1 Set renamed = new HashSet(aliases);
474 kkz 1.1 for (int j = 0; j < q.numPhis(); j++) {
475 kkz 1.1 // rename aliases as needed
476 kkz 1.1 Temp src = q.src(j, 0);
477 kkz 1.1 // perform check on original set
478 kkz 1.1 // in case an alias has multiple
479 kkz 1.1 // renames
480 kkz 1.1 if (aliases.contains(src)) {
481 kkz 1.1 renamed.remove(src);
482 kkz 1.1 renamed.add(q.dst(j));
483 kkz 1.1 }
484 kkz 1.1 }
485 kkz 1.1 // handle rest of edges (starting w/ edge 1)
486 kkz 1.1 for (int i = 1; i < q.arity(); i++) {
487 kkz 1.1 aliases = get(q.prevEdge(i));
488 kkz 1.1 Set renamed2 = new HashSet(aliases);
489 kkz 1.1 for(int j = 0; j < q.numPhis(); j++) {
490 kkz 1.1 // rename aliases as needed
491 kkz 1.1 Temp src = q.src(j, i);
492 kkz 1.1 // perform check on original set
493 kkz 1.1 // in case an alias has multiple
494 kkz 1.1 // renames
495 kkz 1.1 if (aliases.contains(src)) {
496 kkz 1.1 renamed2.remove(src);
497 kkz 1.1 renamed2.add(q.dst(j));
498 kkz 1.1 }
499 kkz 1.1 }
500 kkz 1.1 // since this is a must analysis,
501 kkz 1.1 // we use set intersection: keep
502 kkz 1.1 // only if present in both sets
503 kkz 1.1 renamed.retainAll(renamed2);
504 kkz 1.1 }
505 kkz 1.1 raiseValue(q.nextEdge(0), renamed);
506 kkz 1.1 }
507 kkz 1.1
508 kkz 1.1 public void visit(Quad q) {
509 kkz 1.1 assert q.prevLength() == 1 && q.nextLength() == 1;
510 kkz 1.1 Set aliases = new HashSet(get(q.prevEdge(0)));
511 kkz 1.1 // remove redefined aliases, if any
512 kkz 1.1 aliases.removeAll(q.defC());
513 kkz 1.1 raiseValue(q.nextEdge(0), aliases);
514 kkz 1.1 }
515 kkz 1.1
516 kkz 1.1 public void visit(SIGMA q) {
517 kkz 1.1 assert q.prevLength() == 1;
518 kkz 1.1 Set aliases = get(q.prevEdge(0));
519 kkz 1.1 // iterate over successor edges
520 kkz 1.1 for(int i = 0; i < q.nextLength(); i++)
521 kkz 1.1 handleSIGMAEdge(q, new HashSet(aliases), i);
522 kkz 1.1 }
523 kkz 1.1
524 kkz 1.1 // retreive dataflow fact for CFGEdge e
525 kkz 1.1 protected Set get(CFGEdge e) {
526 kkz 1.1 Set V = (Set) EdgeToTemps.get(e);
527 kkz 1.1 if (V == null) {
528 kkz 1.1 V = new HashSet(allTemps);
529 kkz 1.1 EdgeToTemps.put(e, V);
530 kkz 1.1 }
531 kkz 1.1 if (DEBUG1) {
532 kkz 1.1 System.out.print("\tget: ");
533 kkz 1.1 if (V.size() == allTemps.size()) {
534 kkz 1.1 System.out.println("*");
535 kkz 1.1 } else {
536 kkz 1.1 for(Iterator it = V.iterator(); it.hasNext(); ) {
537 kkz 1.1 System.out.print(it.next());
538 kkz 1.1 if (it.hasNext())
539 kkz 1.1 System.out.print(", ");
540 kkz 1.1 }
541 kkz 1.1 System.out.println("");
542 kkz 1.1 }
543 kkz 1.1 }
544 kkz 1.1 return V;
545 kkz 1.1 }
546 kkz 1.1
547 kkz 1.1 // update dataflow fact for CFGEdge e
548 kkz 1.1 protected void raiseValue(CFGEdge e, Set raised) {
549 kkz 1.1 if (DEBUG1) {
550 kkz 1.1 System.out.print("\traiseValue: ");
551 kkz 1.1 for(Iterator it = raised.iterator(); it.hasNext(); ) {
552 kkz 1.1 System.out.print(it.next());
553 kkz 1.1 if (it.hasNext())
554 kkz 1.1 System.out.print(", ");
555 kkz 1.1 }
556 kkz 1.1 System.out.println("");
557 kkz 1.1 }
558 kkz 1.1 // add successor to to-do list, if necessary
559 kkz 1.1 if (!raised.equals((Set) EdgeToTemps.get(e))) {
560 kkz 1.1 EdgeToTemps.put(e, raised);
561 kkz 1.1 toDo.push(e.to());
562 kkz 1.1 }
563 kkz 1.1 }
564 kkz 1.1
565 kkz 1.1 // handleSIGMAEdge handles the index'th outgoing edge of the
566 kkz 1.1 // SIGMA q, given the set of aliases on the incoming edge
567 kkz 1.1 // requires: aliases be a Set of Temps
568 kkz 1.1 // modifies: aliases
569 kkz 1.1 protected void handleSIGMAEdge(SIGMA q, Set aliases, int index) {
570 kkz 1.1 Set insert = new HashSet();
571 kkz 1.1 Set remove = new HashSet();
572 kkz 1.1 // iterate over sigma functions
573 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
574 kkz 1.1 Temp src = q.src(j);
575 kkz 1.1 if (aliases.contains(src)) {
576 kkz 1.1 insert.add(q.dst(j, index));
577 kkz 1.1 remove.add(src);
578 kkz 1.1 }
579 kkz 1.1 }
580 kkz 1.1 aliases.removeAll(remove);
581 kkz 1.1 aliases.addAll(insert);
582 kkz 1.1 raiseValue(q.nextEdge(index), aliases);
583 kkz 1.1 }
584 kkz 1.1 }
585 kkz 1.1 }