1 ovy 1.1 package harpoon.Analysis.MemOpt;
2 ovy 1.1
3 ovy 1.1
4 ovy 1.8 import harpoon.ClassFile.HClass;
5 ovy 1.8 import harpoon.ClassFile.HMethod;
6 ovy 1.8 import harpoon.ClassFile.HCode;
7 ovy 1.8 import harpoon.ClassFile.HCodeElement;
8 ovy 1.8 import harpoon.ClassFile.HCodeFactory;
9 salcianu 1.14 import harpoon.ClassFile.Linker;
10 salcianu 1.14
11 salcianu 1.14 import harpoon.Backend.Generic.Frame;
12 salcianu 1.14 import harpoon.Backend.Generic.Runtime;
13 ovy 1.8
14 cananian 1.20 import harpoon.IR.Quads.ASET;
15 cananian 1.20 import harpoon.IR.Quads.CALL;
16 cananian 1.20 import harpoon.IR.Quads.Edge;
17 cananian 1.20 import harpoon.IR.Quads.METHOD;
18 cananian 1.20 import harpoon.IR.Quads.MOVE;
19 cananian 1.20 import harpoon.IR.Quads.NEW;
20 cananian 1.20 import harpoon.IR.Quads.PHI;
21 cananian 1.20 import harpoon.IR.Quads.Quad;
22 cananian 1.20 import harpoon.IR.Quads.QuadKind;
23 cananian 1.20 import harpoon.IR.Quads.QuadSSI;
24 cananian 1.20 import harpoon.IR.Quads.RETURN;
25 cananian 1.20 import harpoon.IR.Quads.SET;
26 cananian 1.20 import harpoon.IR.Quads.SIGMA;
27 cananian 1.20 import harpoon.IR.Quads.THROW;
28 cananian 1.20 import harpoon.IR.Quads.TYPESWITCH;
29 ovy 1.8
30 ovy 1.1 import harpoon.Analysis.Quads.CallGraph;
31 ovy 1.1
32 ovy 1.8 import harpoon.Temp.Temp;
33 ovy 1.1
34 cananian 1.21 import net.cscott.jutil.AggregateSetFactory;
35 cananian 1.21 import net.cscott.jutil.GenericMultiMap;
36 cananian 1.21 import net.cscott.jutil.LinearSet;
37 cananian 1.21 import net.cscott.jutil.MultiMap;
38 cananian 1.21 import net.cscott.jutil.WorkSet;
39 ovy 1.8 import harpoon.Util.Timer;
40 salcianu 1.16 import harpoon.Util.Util;
41 ovy 1.1
42 cananian 1.20 import java.util.ArrayList;
43 cananian 1.20 import java.util.Arrays;
44 cananian 1.20 import java.util.Collection;
45 cananian 1.20 import java.util.Collections;
46 cananian 1.20 import java.util.Comparator;
47 cananian 1.20 import java.util.HashSet;
48 cananian 1.20 import java.util.HashMap;
49 cananian 1.20 import java.util.Iterator;
50 cananian 1.20 import java.util.LinkedList;
51 cananian 1.20 import java.util.List;
52 cananian 1.20 import java.util.Map;
53 cananian 1.20 import java.util.Set;
54 ovy 1.1
55 ovy 1.8 /**
56 ovy 1.8 * Describe class <code>IncompatibilityAnalysis</code> here.
57 ovy 1.8 *
58 salcianu 1.17 * @author <a href="mailto:Ovidiu Gheorghioiu <ovy@mit.edu>">Ovidiu Gheorghioiu</a>
59 ovy 1.8 * @version 1.0
60 ovy 1.8 */
61 ovy 1.1 public class IncompatibilityAnalysis {
62 ovy 1.1
63 ovy 1.8 /**
64 ovy 1.8 * If true, the analysis will not descend into classes other than
65 ovy 1.8 * the class of the entry method. Useful for debugging.
66 salcianu 1.13 * */
67 ovy 1.1 public static final boolean STAY_IN_DECLARING_CLASS = false;
68 ovy 1.8
69 ovy 1.8 /**
70 salcianu 1.13 * If true, the analysis will show progress dots and other
71 salcianu 1.13 * progress indicators.
72 salcianu 1.13 * */
73 salcianu 1.13 public static final boolean SHOW_PROGRESS = false;
74 ovy 1.1
75 ovy 1.8
76 ovy 1.8 /**
77 salcianu 1.14 * If true, and <code>SHOW_STATISTICS</code> is also true,
78 salcianu 1.14 * printStatistics will show A LOT OF statistics when it finishes.
79 salcianu 1.13 * */
80 salcianu 1.13 public static final boolean VERBOSE_STATISTICS = true;
81 ovy 1.8
82 ovy 1.8 /**
83 ovy 1.8 * If true, the analysis will show timings for all of its stages.
84 salcianu 1.13 * */
85 ovy 1.8 public static final boolean SHOW_TIMINGS = true;
86 ovy 1.8
87 salcianu 1.14 /** If true, compute the sizes of the classes in bytes, otherwise,
88 salcianu 1.14 compute them in fields (an approximation). Default is
89 salcianu 1.14 true. */
90 salcianu 1.14 public static boolean SIZE_IN_BYTES = true;
91 salcianu 1.14
92 salcianu 1.14 // add this many fields as estimated overhead.
93 ovy 1.8 private static final int ADD_FIELDS = 2;
94 ovy 1.1
95 ovy 1.1
96 ovy 1.1 private Map mdCache; // cache of method data objects
97 ovy 1.1
98 ovy 1.1 private MultiMap callees;
99 ovy 1.1
100 ovy 1.1 private HMethod entry;
101 ovy 1.1 private HCodeFactory codeFactory;
102 ovy 1.1 private CallGraph callGraph;
103 ovy 1.1
104 ovy 1.8 private LinkedList allMethods;
105 ovy 1.1
106 ovy 1.1 // globally maps temps to the allocations defining them
107 ovy 1.1 private Map globalAllocMap;
108 ovy 1.1
109 ovy 1.1 // fake variables
110 ovy 1.1 private static Object RETVAL = new String("RETVAL");
111 ovy 1.1 private static Object RETEX = new String("RETEX");
112 ovy 1.1 private static Object ESCAPE = new String("ESCAPE");
113 ovy 1.1
114 ovy 1.1 // a set of all the above
115 ovy 1.1 private static Set RETURNS = new LinearSet();
116 ovy 1.1 static {
117 ovy 1.1 RETURNS.add(RETVAL);
118 ovy 1.1 RETURNS.add(RETEX);
119 ovy 1.1 RETURNS.add(ESCAPE);
120 ovy 1.1 }
121 ovy 1.1
122 ovy 1.1 // our targets
123 ovy 1.1 private MultiMap I;
124 ovy 1.1 private Collection classes;
125 ovy 1.8 private Set selfIncompatible, selfCompatible;
126 ovy 1.8
127 ovy 1.8 private boolean callGraphNeedsSSA;
128 ovy 1.2
129 ovy 1.2 // interface to the outside world
130 ovy 1.1
131 ovy 1.8 /**
132 ovy 1.8 * Convenience form for the other constructor, calls it with
133 ovy 1.8 * <code>callGraphNeedsSSA</code> set to true.
134 ovy 1.8 */
135 salcianu 1.3 public IncompatibilityAnalysis(HMethod entry, HCodeFactory codeFactory,
136 salcianu 1.14 CallGraph callGraph, Linker linker) {
137 salcianu 1.14 this(entry, codeFactory, callGraph, linker, true);
138 ovy 1.8 }
139 ovy 1.1
140 ovy 1.8 /**
141 ovy 1.8 * Creates a new <code>IncompatibilityAnalysis</code> instance.
142 ovy 1.8 *
143 ovy 1.8 * @param entry the entry method
144 ovy 1.8 * @param codeFactory a <code>HCodeFactory</code>. This needs to be caching
145 ovy 1.8 * and in SSI form.
146 ovy 1.8 * @param callGraph the <code>CallGraph</code> the analysis should use.
147 ovy 1.8 * @param callGraphNeedsSSA hack that enables us to use Alex's
148 ovy 1.8 * <code>SmartCallGraph</code>, which only operates on NoSSA form. If
149 ovy 1.8 * you set to true, make sure you have set
150 ovy 1.8 * <code>QuadSSI.KEEP_QUAD_MAP_HACK</code> to true. This is sucky, I
151 ovy 1.8 * know, but there is no fast remedy.
152 ovy 1.8 *
153 ovy 1.8 */
154 ovy 1.8 public IncompatibilityAnalysis(HMethod entry, HCodeFactory codeFactory,
155 salcianu 1.14 CallGraph callGraph, Linker linker,
156 ovy 1.8 boolean callGraphNeedsSSA) {
157 ovy 1.1 // init
158 ovy 1.1 this.entry = entry;
159 ovy 1.1 this.codeFactory = codeFactory;
160 ovy 1.1 this.callGraph = callGraph;
161 ovy 1.8 this.callGraphNeedsSSA = callGraphNeedsSSA;
162 ovy 1.1
163 ovy 1.1 globalAllocMap = new HashMap();
164 ovy 1.1
165 ovy 1.8 Timer timer, big_timer;
166 ovy 1.8
167 ovy 1.8 if (SHOW_TIMINGS) {
168 ovy 1.8 big_timer = new Timer();
169 ovy 1.8 big_timer.start();
170 ovy 1.8 }
171 ovy 1.8
172 ovy 1.1 // stage 0: static analysis of methods for internal liveness & rest
173 ovy 1.8 if (SHOW_TIMINGS) {
174 ovy 1.8 timer = new Timer();
175 ovy 1.8 timer.start();
176 ovy 1.8 }
177 ovy 1.8
178 ovy 1.1 intraproceduralAnalysis();
179 ovy 1.1
180 ovy 1.8 if (SHOW_TIMINGS) {
181 ovy 1.8 timer.stop();
182 ovy 1.11 System.out.println("IA intraproc: " + timer);
183 ovy 1.8 }
184 ovy 1.8
185 ovy 1.1 // stage 1: compute An, Ae, Rn, Re, Esc
186 ovy 1.8 if (SHOW_TIMINGS) {
187 ovy 1.8 timer = new Timer();
188 ovy 1.8 timer.start();
189 ovy 1.8 }
190 ovy 1.8
191 ovy 1.1 computeInitialSets();
192 ovy 1.8
193 ovy 1.8 if (SHOW_TIMINGS) {
194 ovy 1.8 timer.stop();
195 ovy 1.8 System.out.println("IA points-to: " + timer);
196 ovy 1.8 }
197 ovy 1.1
198 ovy 1.1 // stage 2: compute I
199 ovy 1.8 if (SHOW_TIMINGS) {
200 ovy 1.8 timer = new Timer();
201 ovy 1.8 timer.start();
202 ovy 1.8 }
203 ovy 1.8
204 ovy 1.1 computeI();
205 ovy 1.8
206 ovy 1.8 if (SHOW_TIMINGS) {
207 ovy 1.8 timer.stop();
208 ovy 1.8 System.out.println("IA incompat: " + timer);
209 ovy 1.8 }
210 ovy 1.1
211 ovy 1.1 // stage 3: do compatible classes
212 ovy 1.8 if (SHOW_TIMINGS) {
213 ovy 1.8 timer = new Timer();
214 ovy 1.8 timer.start();
215 ovy 1.8 }
216 ovy 1.8
217 ovy 1.1 computeClasses();
218 ovy 1.2
219 ovy 1.8 if (SHOW_TIMINGS) {
220 ovy 1.8 timer.stop();
221 ovy 1.8 System.out.println("IA classes: " + timer);
222 salcianu 1.14 }
223 ovy 1.8
224 salcianu 1.14 if (SHOW_TIMINGS) {
225 ovy 1.8 big_timer.stop();
226 ovy 1.8 System.out.println("IA total: "+ big_timer);
227 ovy 1.8 }
228 ovy 1.2 }
229 ovy 1.2
230 ovy 1.8
231 ovy 1.8 /**
232 ovy 1.8 * Returns all allocation sites encountered by this analysis.
233 ovy 1.8 *
234 ovy 1.8 * @return a <code>Collection</code> of all the <code>NEW</code> quads processed.
235 ovy 1.8 */
236 ovy 1.8 public Collection allAllocationSites() {
237 ovy 1.8 return Collections.unmodifiableCollection(globalAllocMap.values());
238 ovy 1.8 }
239 ovy 1.8
240 ovy 1.8 /**
241 ovy 1.8 * Returns all the methods encountered by this analysis
242 ovy 1.8 *
243 ovy 1.8 * @return a <code>List</code> of all methods processed (as
244 ovy 1.8 * <code>HMethod</code>s.)
245 ovy 1.8 */
246 ovy 1.8 public List allMethods() {
247 ovy 1.8 return Collections.unmodifiableList(allMethods);
248 ovy 1.8 }
249 ovy 1.8
250 ovy 1.8 /**
251 ovy 1.8 * Returns true if the given site shound be dynamic
252 ovy 1.8 * to the best of our knowledge, i.e. if we haven't seen this site
253 ovy 1.8 * for some reason (e.g. it's not reachable from the entry method), or
254 ovy 1.8 * if we have been unable to prove it can be allocated statically.
255 ovy 1.8 * Requires that the site is a <code>NEW</code> quad in SSI form.
256 ovy 1.8 * This takes the more general
257 ovy 1.8 *
258 ovy 1.8 * @param e the allocation site. Right now, it must be a
259 ovy 1.8 * <code>NEW</code> quad in SSI form. This parameter has the more general
260 ovy 1.8 * <code>HCodeElement</code> because in the future we might want to support
261 ovy 1.8 * other forms and/or <code>ANEW</code> quads.
262 ovy 1.8 * @return true if the allocation site should not be made static.
263 ovy 1.8 */
264 ovy 1.2 public boolean isSelfIncompatible(HCodeElement e) {
265 ovy 1.2 assert e instanceof NEW : "allocations are NEW quads";
266 ovy 1.2
267 ovy 1.2 NEW qNew = (NEW) e;
268 ovy 1.2 Temp alloc = qNew.dst();
269 ovy 1.2
270 salcianu 1.4 return I.contains(alloc, alloc) || !globalAllocMap.containsKey(alloc);
271 ovy 1.2 }
272 ovy 1.2
273 ovy 1.8 /**
274 ovy 1.8 * Returns true if the given allocation sites cannot use the same
275 ovy 1.8 * memory to the best of our knowledge, i.e. we have not encountered
276 ovy 1.8 * one or both of them, or we have unable to prove thay can safely use
277 ovy 1.8 * the same memory. You should also call
278 ovy 1.8 * <code>isSelfIncompatible()</code> to check whether the sites can be
279 ovy 1.8 * allocated statically at all.
280 ovy 1.8 *
281 ovy 1.8 * @param e1,e2 the allocation sites. Right now, they must be
282 ovy 1.8 * <code>NEW</code> quads in SSI-form.
283 ovy 1.8 * @return true if the sites should not use the same memory.
284 ovy 1.8 */
285 ovy 1.2 public boolean isIncompatible(HCodeElement e1, HCodeElement e2) {
286 ovy 1.2 assert e1 instanceof NEW && e2 instanceof NEW :
287 ovy 1.2 "allocations are NEW quads";
288 ovy 1.2
289 ovy 1.2 NEW qNew1 = (NEW) e1; NEW qNew2 = (NEW) e2;
290 ovy 1.2 Temp alloc1 = qNew1.dst(); Temp alloc2 = qNew2.dst();
291 ovy 1.2
292 ovy 1.2 return I.contains(alloc1, alloc2);
293 ovy 1.1 }
294 ovy 1.2
295 ovy 1.8 /**
296 ovy 1.8 * Returns a <code>Collection</code> whose members are disjunct
297 ovy 1.8 * <code>Collection</code> of mutually compatible allocation sites
298 salcianu 1.10 * (<code>NEW</code> quads in SSI form). Every allocation site we
299 salcianu 1.10 * have encountered that can be made static is in one of these
300 salcianu 1.10 * classes.
301 ovy 1.8 *
302 ovy 1.8 * @return a <code>Collection</code> of compatible static allocation
303 salcianu 1.10 * classes. */
304 ovy 1.2 public Collection getCompatibleClasses() {
305 ovy 1.2 LinkedList allocClasses = new LinkedList();
306 cananian 1.22 for (Object thisClassO : classes) {
307 cananian 1.22 Collection thisClass = (Collection) thisClassO;
308 ovy 1.2 Collection newClass = new LinkedList();
309 ovy 1.2
310 ovy 1.2 for (Iterator it2 = thisClass.iterator(); it2.hasNext(); ) {
311 ovy 1.2 newClass.add(globalAllocMap.get(it2.next()));
312 ovy 1.2 }
313 ovy 1.2
314 ovy 1.2 allocClasses.add(newClass);
315 ovy 1.2 }
316 ovy 1.2
317 ovy 1.2 return allocClasses;
318 ovy 1.2 }
319 ovy 1.2
320 ovy 1.8 /**
321 ovy 1.8 * Similar to the above, except it operates on a specified set of
322 ovy 1.8 * allocation sites.
323 ovy 1.8 *
324 ovy 1.8 * @param allocs a <code>Collection</code> of allocation sites to be
325 ovy 1.8 * divided into compatible classes.
326 ovy 1.8 * @return a <code>Collection</code> of compatible classes. Every
327 ovy 1.8 * allocation site in <code>alloc</code> that can be safely made static
328 salcianu 1.10 * is in one of these classes. */
329 ovy 1.8 public Collection getCompatibleClasses(Collection allocs) {
330 ovy 1.8 Set allocVars = new HashSet();
331 ovy 1.8
332 cananian 1.22 for (Object qO : allocs) {
333 cananian 1.22 Quad q = (Quad) qO;
334 ovy 1.8 if (!(q instanceof NEW)) continue;
335 ovy 1.8
336 ovy 1.8 Temp temp = ((NEW) q).dst();
337 ovy 1.8 if (globalAllocMap.containsKey(temp)) {
338 ovy 1.8 allocVars.add(temp);
339 ovy 1.8 }
340 ovy 1.8 }
341 ovy 1.8
342 ovy 1.8 allocVars.removeAll(selfIncompatible);
343 ovy 1.8
344 ovy 1.8 Collection classes = MyGraphColorer.colorGraph(allocVars, I);
345 ovy 1.8
346 ovy 1.8 LinkedList allocClasses = new LinkedList();
347 cananian 1.22 for (Object thisClassO : classes) {
348 cananian 1.22 Collection thisClass = (Collection) thisClassO;
349 ovy 1.8 Collection newClass = new LinkedList();
350 ovy 1.8
351 ovy 1.8 for (Iterator it2 = thisClass.iterator(); it2.hasNext(); ) {
352 ovy 1.8 newClass.add(globalAllocMap.get(it2.next()));
353 ovy 1.8 }
354 ovy 1.8
355 ovy 1.8 allocClasses.add(newClass);
356 ovy 1.8 }
357 ovy 1.8
358 ovy 1.8 return allocClasses;
359 ovy 1.8
360 ovy 1.8 }
361 ovy 1.8
362 ovy 1.8 /**
363 salcianu 1.10 * Takes a Quad in NoSSA form, and returns the corresponding quad
364 salcianu 1.10 * in SSI form, generated by the <code>HCodeFactory</code> used to
365 salcianu 1.10 * create this <code>IncompatibilityAnalysis</code> instance. For
366 salcianu 1.10 * this to work correctly, our SSI factory *must* be a caching SSI
367 salcianu 1.10 * view of a caching SSA view. I wish I had any other way to do
368 salcianu 1.10 * this kind of "bridging", but there apparently is none.
369 ovy 1.8 *
370 salcianu 1.10 * @param q a <code>Quad</code> in NoSSA form/ @return the
371 salcianu 1.10 * corresponding <code>Quad</code> in SSI form, or null if we
372 salcianu 1.10 * couldn't find one (check the caching-SSI-of-caching-SSA
373 salcianu 1.10 * requirement) */
374 ovy 1.2 public Quad getSSIQuad(Quad q) {
375 ovy 1.2 HMethod method = q.getFactory().getMethod();
376 ovy 1.2 QuadSSI quadssi = (QuadSSI) codeFactory.convert(method);
377 ovy 1.2
378 salcianu 1.12 Quad retval = (Quad) quadssi.getQuadMapNoSSA2SSI().get(q);
379 ovy 1.2
380 ovy 1.2 return retval;
381 ovy 1.2 }
382 ovy 1.2
383 ovy 1.8 // implementation
384 ovy 1.8
385 ovy 1.8 // **** Step 0: analyze each method and gather everything we need for
386 ovy 1.8 // the analysis. This is the only pass that analyzes each element.
387 ovy 1.1
388 ovy 1.8 // iterate through all of the methods and analyze them.
389 ovy 1.1 private void intraproceduralAnalysis() {
390 ovy 1.1 WorkSet workset = new WorkSet();
391 ovy 1.1 mdCache = new HashMap();
392 ovy 1.1
393 ovy 1.1 allMethods = new LinkedList();
394 ovy 1.1
395 ovy 1.1 callees = new GenericMultiMap(new AggregateSetFactory());
396 ovy 1.1
397 ovy 1.1 workset.add(entry);
398 ovy 1.1
399 ovy 1.1 while (!workset.isEmpty()) {
400 ovy 1.1 HMethod method = (HMethod) workset.removeFirst();
401 ovy 1.1
402 ovy 1.1
403 ovy 1.1 // do the work
404 ovy 1.1 MethodData md = createInitialMethodData(method);
405 ovy 1.1
406 ovy 1.1 mdCache.put(method, md);
407 ovy 1.1 if (md.isNative) continue;
408 ovy 1.1
409 ovy 1.1 allMethods.addFirst(method);
410 ovy 1.1
411 cananian 1.22 for (Object qCallO : md.calls.keySet()) {
412 cananian 1.22 CALL qCall = (CALL) qCallO;
413 ovy 1.1 Collection possibleCalls = md.calls.getValues(qCall);
414 ovy 1.1
415 cananian 1.22 for (Object calledO : possibleCalls) {
416 cananian 1.22 HMethod called = (HMethod) calledO;
417 ovy 1.1
418 ovy 1.1 if (STAY_IN_DECLARING_CLASS &&
419 ovy 1.1 !(called.getDeclaringClass().equals(entry.getDeclaringClass())))
420 ovy 1.1 continue;
421 ovy 1.1
422 ovy 1.1 callees.add(called, method);
423 ovy 1.1
424 ovy 1.1 if (!mdCache.containsKey(called)) {
425 ovy 1.1 workset.addLast(called);
426 ovy 1.1 }
427 ovy 1.1 }
428 ovy 1.1 }
429 ovy 1.1 }
430 ovy 1.1 }
431 ovy 1.1
432 ovy 1.1 private MethodData createInitialMethodData(HMethod method) {
433 ovy 1.8 if (SHOW_PROGRESS) System.out.println("Analyzing " + method);
434 ovy 1.1
435 ovy 1.1 // what we need
436 ovy 1.1 HCode hcode = codeFactory.convert(method);
437 ovy 1.8 if (hcode == null) {
438 ovy 1.8 if (SHOW_PROGRESS) System.out.println(" native... ignoring");
439 ovy 1.1 MethodData md = new MethodData();
440 ovy 1.1 // return fake md
441 ovy 1.1 md.isNative = true;
442 ovy 1.1 return md;
443 ovy 1.1 }
444 ovy 1.1
445 salcianu 1.12 // get ssi2nossa quadmap if needed
446 salcianu 1.12 Map quadSSI2NoSSA =
447 salcianu 1.12 callGraphNeedsSSA ? ((QuadSSI) hcode).getQuadMapSSI2NoSSA() : null;
448 ovy 1.1
449 ovy 1.1 // ExactTypeMap typeMap = new SCCAnalysis(hcode);
450 ovy 1.1 // ReachingDefs rd= new SSxReachingDefsImpl(hcode);
451 ovy 1.1
452 ovy 1.8 // We can probably do with less objects, but dev time is the constraint
453 ovy 1.8 // now.
454 ovy 1.1 Collection allocations = new ArrayList();
455 ovy 1.1 Collection allocationSites = new ArrayList();
456 ovy 1.1 Collection escapeSites = new ArrayList();
457 ovy 1.1
458 ovy 1.1 Collection retNormal = new ArrayList();
459 ovy 1.1 Collection retNormalSites = new ArrayList();
460 ovy 1.1 Collection retEx = new ArrayList(1);
461 ovy 1.1 Collection retExSites = new ArrayList(1);
462 ovy 1.1
463 ovy 1.1 Collection callParams = new ArrayList();
464 ovy 1.1 Collection callReturns = new ArrayList();
465 ovy 1.1
466 ovy 1.1 Map conditions = new HashMap();
467 ovy 1.1
468 ovy 1.1 Collection escapes = new ArrayList();
469 ovy 1.1
470 ovy 1.1 MultiMap param2calls = new GenericMultiMap(new AggregateSetFactory());
471 ovy 1.1
472 ovy 1.1 METHOD header = null;
473 ovy 1.1
474 ovy 1.1 MultiMap calls = new GenericMultiMap(new AggregateSetFactory());
475 ovy 1.1 MultiMap liveness = new GenericMultiMap(new AggregateSetFactory());
476 ovy 1.1
477 ovy 1.1 // helpers for liveness
478 salcianu 1.3 // edges for which we are interested in liveness & reachability
479 salcianu 1.3 Set interestingEdges = new HashSet();
480 ovy 1.1
481 ovy 1.1 // direct assignments: which temps get assigned to this temp
482 ovy 1.1 MultiMap assignMap = new GenericMultiMap(new AggregateSetFactory());
483 ovy 1.1
484 ovy 1.8 // traverse the graph. Reimplement this using a Visitor if it threatens
485 ovy 1.8 // to become unmaintainable.
486 ovy 1.8 // The thing is, IMHO, code that uses visitors is pretty ugly too.
487 ovy 1.1 for (Iterator it = hcode.getElementsI(); it.hasNext(); ) {
488 ovy 1.1 Quad q = (Quad) it.next();
489 ovy 1.1
490 ovy 1.1 // allocation?
491 ovy 1.1 if (q.kind() == QuadKind.NEW) {
492 ovy 1.1 NEW qNew = (NEW) q;
493 ovy 1.1 Temp temp = qNew.dst();
494 ovy 1.1
495 ovy 1.1 allocations.add(temp);
496 ovy 1.1 allocationSites.add(qNew);
497 ovy 1.1 globalAllocMap.put(temp, qNew);
498 ovy 1.1
499 salcianu 1.3 assert qNew.nextLength() == 1 :
500 salcianu 1.3 "NEW should only have one incoming edge";
501 salcianu 1.3
502 ovy 1.1 interestingEdges.add(qNew.prevEdge(0));
503 ovy 1.1 interestingEdges.add(qNew.nextEdge(0));
504 salcianu 1.3 }
505 ovy 1.1 // call site?
506 ovy 1.1 else if (q.kind() == QuadKind.CALL) {
507 ovy 1.1 CALL qCall = (CALL) q;
508 ovy 1.8 CALL qCallToPass = qCall;
509 ovy 1.1
510 ovy 1.8 if (callGraphNeedsSSA) {
511 ovy 1.8 qCallToPass = (CALL) quadSSI2NoSSA.get(qCall);
512 ovy 1.8 assert qCallToPass != null : "SSI->SSA mapping failed";
513 ovy 1.8 }
514 ovy 1.8
515 ovy 1.8 HMethod[] calledMethods = callGraph.calls(method, qCallToPass);
516 ovy 1.1
517 ovy 1.8 // FIXME: figure out how important this is
518 ovy 1.8 // and upgrade to assertion / downgrade to DEBUG stmnt
519 ovy 1.1 if (calledMethods.length == 0) {
520 ovy 1.1 System.out.println("*** Warning: no methods found for: "
521 salcianu 1.16 + Util.code2str(qCall));
522 ovy 1.1 }
523 ovy 1.1
524 ovy 1.8 for (int i = 0; i<calledMethods.length; i++ ) {
525 ovy 1.8 HMethod called = calledMethods[i];
526 ovy 1.8 calls.add(qCall, called);
527 ovy 1.8 }
528 ovy 1.1
529 ovy 1.1 callParams.addAll(Arrays.asList(qCall.params()));
530 ovy 1.1
531 ovy 1.1 if (qCall.retval() != null) callReturns.add(qCall.retval());
532 ovy 1.1 callReturns.add(qCall.retex());
533 ovy 1.1
534 ovy 1.1 interestingEdges.add(qCall.prevEdge(0));
535 ovy 1.1 interestingEdges.add(qCall.nextEdge(0));
536 ovy 1.1 interestingEdges.add(qCall.nextEdge(1));
537 ovy 1.1
538 ovy 1.1 for (int i = 0; i<qCall.paramsLength(); i++) {
539 ovy 1.1 param2calls.add(qCall.params(i), qCall);
540 ovy 1.1 }
541 ovy 1.1 }
542 ovy 1.1 // direct assignment? (MOVE, PHI, SIGMA)
543 ovy 1.1 // MOVE?
544 ovy 1.1 else if (q.kind() == QuadKind.MOVE) {
545 ovy 1.1 MOVE qMove = (MOVE) q;
546 ovy 1.1 assignMap.add(qMove.src(), qMove.dst());
547 ovy 1.1 }
548 ovy 1.1 // PHI?
549 ovy 1.1 else if (q instanceof PHI) {
550 ovy 1.1 PHI qPhi = (PHI) q;
551 ovy 1.1
552 ovy 1.1 for (int i = 0; i<qPhi.numPhis(); i++) {
553 ovy 1.1 for (int j = 0; j<qPhi.arity(); j++) {
554 ovy 1.1 assignMap.add(qPhi.src(i, j), qPhi.dst(i));
555 ovy 1.1 }
556 ovy 1.1 }
557 ovy 1.1 }
558 ovy 1.1 // RETURN?
559 ovy 1.1 else if (q.kind() == QuadKind.RETURN) {
560 ovy 1.1 RETURN qRet = (RETURN) q;
561 ovy 1.1 if (qRet.retval() != null) retNormal.add(qRet.retval());
562 ovy 1.1 retNormalSites.add(qRet);
563 ovy 1.1 }
564 ovy 1.1 // THROW?
565 ovy 1.1 else if (q.kind() == QuadKind.THROW) {
566 ovy 1.1 THROW qThrow = (THROW) q;
567 ovy 1.1 retEx.add(qThrow.throwable());
568 ovy 1.1 retExSites.add(qThrow);
569 ovy 1.1 }
570 ovy 1.1 // METHOD?
571 ovy 1.1 else if (q.kind() == QuadKind.METHOD) {
572 ovy 1.1 assert header == null : "Only one METHOD quad";
573 ovy 1.1 header = (METHOD) q;
574 ovy 1.1 }
575 ovy 1.1 // SET?
576 ovy 1.1 else if (q.kind() == QuadKind.SET) {
577 ovy 1.1 SET qSet = (SET) q;
578 ovy 1.1 escapes.add(qSet.src());
579 ovy 1.1 escapeSites.add(qSet);
580 ovy 1.1 }
581 ovy 1.1 // ASET?
582 ovy 1.1 else if (q.kind() == QuadKind.ASET) {
583 ovy 1.1 ASET qASet = (ASET) q;
584 ovy 1.1 escapes.add(qASet.src());
585 ovy 1.1 escapeSites.add(qASet);
586 ovy 1.1 }
587 ovy 1.1
588 ovy 1.8 // SIGMA stuff. Note that this might overlap w/above
589 ovy 1.1 // handle typeswitch sigmas differently
590 ovy 1.1 if (q instanceof SIGMA) {
591 ovy 1.1 SIGMA qSigma = (SIGMA) q;
592 ovy 1.1 for (int i = 0; i<qSigma.numSigmas(); i++) {
593 ovy 1.1 for (int j = 0; j<qSigma.arity(); j++) {
594 ovy 1.1 assignMap.add(qSigma.src(i), qSigma.dst(i, j));
595 ovy 1.1 if (q instanceof TYPESWITCH &&
596 ovy 1.1 qSigma.src(i).equals(((TYPESWITCH) q).index())) {
597 ovy 1.1 conditions.put(qSigma.dst(i, j),
598 ovy 1.1 new TypeSwitchCondition((TYPESWITCH) q, j));
599 ovy 1.1 }
600 ovy 1.1
601 ovy 1.1 }
602 ovy 1.1 }
603 ovy 1.1 }
604 ovy 1.1 }
605 ovy 1.1
606 ovy 1.1 // interesting temps
607 ovy 1.1 Set externals = new HashSet(allocations);
608 ovy 1.1 externals.addAll(Arrays.asList(header.params()));
609 ovy 1.1 Set internals = new HashSet(callParams);
610 ovy 1.1 internals.addAll(callReturns);
611 ovy 1.1 internals.addAll(conditions.keySet());
612 ovy 1.1 internals.addAll(escapes);
613 ovy 1.1
614 ovy 1.1 // add fake temps
615 ovy 1.1 MultiMapUtils.multiMapAddAll(assignMap, retNormal, RETVAL);
616 ovy 1.1 MultiMapUtils.multiMapAddAll(assignMap, retEx, RETEX);
617 ovy 1.1 MultiMapUtils.multiMapAddAll(assignMap, escapes, ESCAPE);
618 ovy 1.1 internals.add(RETVAL);
619 ovy 1.1 internals.add(RETEX);
620 ovy 1.1 internals.add(ESCAPE);
621 ovy 1.1
622 ovy 1.1 // form interestingTemps collection. We don't need a fast contains()
623 ovy 1.8 // here, so use ArrayList.
624 ovy 1.1 Collection interestingTemps = new ArrayList(externals.size()
625 ovy 1.1 + internals.size());
626 ovy 1.1 interestingTemps.addAll(internals);
627 ovy 1.1 interestingTemps.addAll(externals);
628 ovy 1.1
629 ovy 1.1 // we are only interested in variables that get assigned the above,
630 ovy 1.8 // minus call params and escapes (e.g. a call param is not
631 ovy 1.8 // inherently interesting, only if it can hold an object)
632 ovy 1.1 Set interestingRoots = new HashSet(allocations);
633 ovy 1.1 interestingRoots.addAll(Arrays.asList(header.params()));
634 ovy 1.1 interestingRoots.addAll(callReturns);
635 ovy 1.1 interestingRoots.addAll(conditions.keySet());
636 ovy 1.1
637 ovy 1.1
638 ovy 1.1 // we are only interested in assignments between interesting temps
639 ovy 1.1
640 ovy 1.1 // close assignMap as per the interesting roots
641 ovy 1.1 // but: do *NOT* allow propagation over conditionals
642 ovy 1.1 // *THAT* propagation is assigned-object-dependent
643 ovy 1.1
644 ovy 1.1 assignMap = MultiMapUtils.multiMapClosure(assignMap, interestingRoots,
645 ovy 1.1 conditions.keySet());
646 ovy 1.1
647 ovy 1.1 // compute reverse mapping of vars to possible values
648 ovy 1.8 MultiMap valuesMap = MultiMapUtils.multiMapInvert(assignMap,
649 ovy 1.8 interestingRoots);
650 ovy 1.8
651 ovy 1.8 // we don't need assignMap anymore, free it
652 ovy 1.8 assignMap = null;
653 ovy 1.1
654 ovy 1.1 SSILiveness ssiLiveness = new SSILiveness(hcode);
655 ovy 1.1
656 ovy 1.1 // retain the liveness info we need
657 ovy 1.1 // i.e., for interestingTemps and interestingEdges, via valuesMap
658 cananian 1.22 for (Object edgeO : interestingEdges) {
659 cananian 1.22 Edge edge = (Edge) edgeO;
660 ovy 1.1
661 ovy 1.1 Set lvOn = ssiLiveness.getLiveOn(edge);
662 ovy 1.1
663 cananian 1.22 for (Object tempO : lvOn) {
664 cananian 1.22 Temp temp = (Temp) tempO;
665 ovy 1.1
666 ovy 1.1 liveness.addAll(edge, valuesMap.getValues(temp));
667 ovy 1.1 if (interestingRoots.contains(temp)) {
668 ovy 1.1 liveness.add(edge, temp);
669 ovy 1.1 }
670 ovy 1.1 }
671 ovy 1.1 }
672 ovy 1.1
673 ovy 1.1 // that's it, construct and return methodData
674 ovy 1.1 MethodData md = new MethodData();
675 ovy 1.1
676 ovy 1.1 // static values
677 ovy 1.1 md.liveness = liveness;
678 ovy 1.1 md.calls = calls;
679 ovy 1.1 md.header = header;
680 ovy 1.1 md.param2calls = param2calls;
681 ovy 1.1
682 ovy 1.1 md.conditions = conditions;
683 ovy 1.1 md.externals = externals;
684 ovy 1.1 md.internals = internals;
685 ovy 1.1
686 ovy 1.1 md.allocationSites = allocationSites;
687 ovy 1.1 md.escapeSites = escapeSites;
688 ovy 1.1
689 ovy 1.1 Set reachNormal = canReach(retNormalSites, true);
690 ovy 1.1 Set reachEx = canReach(retExSites, true);
691 ovy 1.1
692 ovy 1.8 // Only keep reachability info for interesting nodes, ie, nodes
693 ovy 1.8 // after calls.
694 ovy 1.1 md.reachNormal = new HashSet();
695 ovy 1.1 md.reachEx = new HashSet();
696 ovy 1.1
697 cananian 1.22 for (Object edgeO : interestingEdges) {
698 cananian 1.22 Edge edge = (Edge) edgeO;
699 cananian 1.19 Quad q = edge.to();
700 ovy 1.1
701 ovy 1.1 if (reachNormal.contains(q)) md.reachNormal.add(q);
702 ovy 1.1 if (reachEx.contains(q)) md.reachEx.add(q);
703 ovy 1.1 }
704 ovy 1.1
705 ovy 1.1 // initial values of dynamic sets
706 ovy 1.8
707 ovy 1.8 // aliases: only keep between interesting temps
708 ovy 1.8 MultiMap aliasedValues =
709 ovy 1.8 MultiMapUtils.multiMapFilter(valuesMap,
710 ovy 1.8 interestingTemps,
711 ovy 1.8 interestingTemps);
712 ovy 1.1
713 ovy 1.1 md.aliasedValues = aliasedValues;
714 ovy 1.8 md.aliasedAssigns =
715 ovy 1.8 MultiMapUtils.multiMapInvert(aliasedValues, interestingTemps);
716 ovy 1.1
717 ovy 1.1 // sanity check. take this out when sure the code works right
718 ovy 1.8 // (and put it back when it doesn't :)
719 ovy 1.1 // assert MultiMapUtils.intersect(md.aliasedValues.keySet(,
720 ovy 1.1 // externals) == null);
721 ovy 1.1
722 ovy 1.8 // An, Ae: use reachability on allocs in this method
723 ovy 1.1 md.An = new HashSet();
724 ovy 1.8 md.Ae = new HashSet();
725 ovy 1.1
726 cananian 1.22 for (Object qNewO : allocationSites) {
727 cananian 1.22 NEW qNew = (NEW) qNewO;
728 ovy 1.1
729 ovy 1.1 if (reachNormal.contains(qNew)) md.An.add(qNew.dst());
730 ovy 1.1 if (reachEx.contains(qNew)) md.Ae.add(qNew.dst());
731 ovy 1.1 }
732 ovy 1.1
733 ovy 1.1 // simulate pointsTo info from what we have
734 ovy 1.1 MultiMap pointsTo = new GenericMultiMap(new AggregateSetFactory());
735 cananian 1.22 for (Object tempO : externals) {
736 cananian 1.22 Temp temp = (Temp) tempO;
737 ovy 1.1 pointsTo.add(temp, temp);
738 ovy 1.1 }
739 ovy 1.1
740 ovy 1.1 // propagate pointsTo by simulating deltas
741 ovy 1.1 propagateExternalDeltas(md, pointsTo);
742 ovy 1.8
743 ovy 1.8 // initial values of Rn, Re, E: use fake variables
744 ovy 1.1 md.Rn = new HashSet(pointsTo.getValues(RETVAL));
745 ovy 1.1 md.Re = new HashSet(pointsTo.getValues(RETEX));
746 ovy 1.1 md.E = new HashSet(pointsTo.getValues(ESCAPE));
747 ovy 1.1
748 ovy 1.1 // done, hopefully
749 ovy 1.1 return md;
750 ovy 1.1 }
751 ovy 1.1
752 ovy 1.1
753 ovy 1.1 // computes all quads from which the given sites are reachable
754 ovy 1.1 // takes O(Nacc), where Nacc is the number of edges that can reach "sites"
755 ovy 1.1 private Set canReach(Collection sites, boolean addInitial) {
756 ovy 1.1 Set canreach = addInitial? new HashSet(sites) : new HashSet();
757 ovy 1.1 WorkSet workset = new WorkSet(sites);
758 ovy 1.1
759 ovy 1.1 while (!workset.isEmpty()) {
760 ovy 1.1 Quad q = (Quad) workset.removeFirst();
761 ovy 1.1
762 ovy 1.1 for (int i = 0; i<q.prevLength(); i++) {
763 cananian 1.19 Quad prev = q.prevEdge(i).from();
764 ovy 1.1
765 ovy 1.1 if (canreach.add(prev)) {
766 ovy 1.1 workset.add(prev);
767 ovy 1.1 }
768 ovy 1.1 }
769 ovy 1.1 }
770 ovy 1.1
771 ovy 1.1 return canreach;
772 ovy 1.1 }
773 ovy 1.1
774 ovy 1.8 // **** Stage 1: Fixed-point set computation for the 5 sets we need
775 ovy 1.8 // (An, Ae, Rn, Re, E)
776 ovy 1.8
777 ovy 1.8 // Fixed point lodic
778 ovy 1.1 private void computeInitialSets() {
779 ovy 1.8 if (SHOW_PROGRESS) System.out.print("Fixed point set (Ax, Rx, E)");
780 ovy 1.8
781 ovy 1.1 WorkSet workset = new WorkSet();
782 ovy 1.1
783 ovy 1.1 workset.addAll(allMethods);
784 ovy 1.1
785 ovy 1.1 while (!workset.isEmpty()) {
786 ovy 1.1 HMethod method = (HMethod) workset.removeFirst();
787 ovy 1.1
788 ovy 1.1 if (recomputeInitialSets(method)) {
789 cananian 1.22 for (Object calleeO : callees.getValues(method)) {
790 cananian 1.22 HMethod callee = (HMethod) calleeO;
791 ovy 1.1 workset.addLast(callee);
792 ovy 1.1 }
793 ovy 1.1 }
794 ovy 1.1 }
795 ovy 1.8
796 ovy 1.8 if (SHOW_PROGRESS) System.out.println();
797 ovy 1.1 }
798 ovy 1.1
799 ovy 1.8 // Do the actual work for each method
800 ovy 1.1 private boolean recomputeInitialSets(HMethod method) {
801 ovy 1.8 if (SHOW_PROGRESS) System.out.print(".");
802 ovy 1.8
803 ovy 1.1 MethodData md = (MethodData) mdCache.get(method);
804 ovy 1.1 assert !md.isNative;
805 ovy 1.1
806 ovy 1.1 int anSize = md.An.size(); int aeSize = md.Ae.size();
807 ovy 1.1 int rnSize = md.Rn.size(); int reSize = md.Re.size();
808 ovy 1.1 int eSize = md.E.size();
809 ovy 1.1
810 ovy 1.1 // This is terribly, terribly inefficient
811 ovy 1.1 // Should really be using deltas...
812 cananian 1.22 for (Object qCallO : md.calls.keySet()) {
813 cananian 1.22 CALL qCall = (CALL) qCallO;
814 ovy 1.1 boolean reachNN = md.reachNormal.contains(qCall.nextEdge(0).to());
815 ovy 1.1 boolean reachNE = md.reachEx.contains(qCall.nextEdge(0).to());
816 ovy 1.1 boolean reachEN = md.reachNormal.contains(qCall.nextEdge(1).to());
817 ovy 1.1 boolean reachEE = md.reachEx.contains(qCall.nextEdge(1).to());
818 ovy 1.1
819 ovy 1.1 // sanity check
820 ovy 1.1 assert (reachNN || reachNE) && (reachEN || reachEE) :
821 ovy 1.8 "Must have a way of getting out of the method (at "
822 salcianu 1.16 + Util.code2str(qCall)+")";
823 ovy 1.1
824 ovy 1.1
825 cananian 1.22 for (Object calledO : md.calls.getValues(qCall)) {
826 cananian 1.22 HMethod called = (HMethod) calledO;
827 ovy 1.1 MethodData mdCalled = (MethodData) mdCache.get(called);
828 ovy 1.1
829 ovy 1.1 if (mdCalled == null || mdCalled.isNative) continue;
830 ovy 1.1
831 ovy 1.1 // do An, Ae changes
832 ovy 1.1 if (reachNN) md.An.addAll(mdCalled.An);
833 ovy 1.1 if (reachNE) md.Ae.addAll(mdCalled.An);
834 ovy 1.1 if (reachEN) md.An.addAll(mdCalled.Ae);
835 ovy 1.1 if (reachEE) md.Ae.addAll(mdCalled.Ae);
836 ovy 1.1
837 ovy 1.1 }
838 ovy 1.1 }
839 ovy 1.1
840 ovy 1.1 // Rn, Re, E computation
841 ovy 1.1
842 ovy 1.1 // for now, we don't compute deltas, just full pointsTo information
843 ovy 1.1 // this has to change if we wanna be efficient
844 ovy 1.1 MultiMap externalPointsTo = new GenericMultiMap();
845 ovy 1.1 MultiMap internalPointsTo = new GenericMultiMap();
846 ovy 1.1
847 ovy 1.1 computePointsTo(md, externalPointsTo, internalPointsTo);
848 ovy 1.1
849 ovy 1.1 // non-optimized since we don't expect this to happen a lot
850 ovy 1.1 if (md.aliasedValues.addAll(internalPointsTo)) {
851 ovy 1.1 // i don't think we need redo transitivity...
852 ovy 1.1 // FIXME: maybe reconsider
853 ovy 1.1
854 ovy 1.1 md.aliasedAssigns.addAll(MultiMapUtils.multiMapInvert(internalPointsTo, null));
855 ovy 1.1
856 ovy 1.8 // if we implement deltas, we should re-computePointsTo here,
857 ovy 1.8 // or use just deltas if aliases haven't changed; but we do
858 ovy 1.8 // pointsTo anyway (for now; inefficient)
859 ovy 1.8
860 ovy 1.8 // the "o" indicates an alias recomputation is needed
861 ovy 1.8 if (SHOW_PROGRESS) System.out.print("o");
862 ovy 1.1 }
863 ovy 1.1
864 ovy 1.1 propagateExternalDeltas(md, externalPointsTo);
865 ovy 1.1
866 ovy 1.1
867 ovy 1.1
868 ovy 1.1 // finally, add any deltas to final variables to the final sets
869 ovy 1.1 md.Rn.addAll(externalPointsTo.getValues(RETVAL));
870 ovy 1.1 md.Re.addAll(externalPointsTo.getValues(RETEX));
871 ovy 1.1 md.E.addAll(externalPointsTo.getValues(ESCAPE));
872 ovy 1.8
873 ovy 1.1 return anSize != md.An.size() || aeSize != md.Ae.size()
874 ovy 1.1 || rnSize != md.Rn.size() || reSize != md.Re.size()
875 ovy 1.1 || eSize != md.E.size();
876 ovy 1.1
877 ovy 1.1 }
878 ovy 1.1
879 ovy 1.1
880 ovy 1.1
881 ovy 1.1 // this recomputes pointsTo information from params, allocs & calls
882 ovy 1.1 // separating it into external and internal
883 ovy 1.1 // Note: only assignments between call values and call params will be
884 ovy 1.1 // written to internalPointsTo. The rest of the info should come
885 ovy 1.1 // from aliasedValues & friends. The info in internalPointsTo is
886 ovy 1.1 // meant to be added to aliases. internalPointsTo can be null if we
887 ovy 1.1 // are not interested in them.
888 ovy 1.1
889 ovy 1.1 // this does NOT do transitivity. it must be handled externally, for good
890 ovy 1.1 // reasons.
891 ovy 1.1 private void computePointsTo(MethodData md,
892 ovy 1.1 MultiMap externalPointsTo,
893 ovy 1.1 MultiMap internalPointsTo) {
894 ovy 1.1
895 ovy 1.1 // add allocs & params
896 cananian 1.22 for (Object tempO : md.externals) {
897 cananian 1.22 Temp temp = (Temp) tempO;
898 ovy 1.1 externalPointsTo.add(temp, temp);
899 ovy 1.1 }
900 ovy 1.1
901 cananian 1.22 for (Object qCallO : md.calls.keySet()) {
902 cananian 1.22 CALL qCall = (CALL) qCallO;
903 ovy 1.1 Temp [] actParams = qCall.params();
904 cananian 1.22 for (Object calledO : md.calls.getValues(qCall)) {
905 cananian 1.22 HMethod called = (HMethod) calledO;
906 ovy 1.1 MethodData mdCalled = (MethodData) mdCache.get(called);
907 ovy 1.1
908 ovy 1.1 if (mdCalled == null || mdCalled.isNative) continue;
909 ovy 1.1 Temp [] declParams = mdCalled.header.params();
910 ovy 1.1
911 ovy 1.1 if (qCall.retval() != null)
912 ovy 1.1 addCallDeltas(md,
913 ovy 1.1 qCall.retval(),
914 ovy 1.1 mdCalled.Rn,
915 ovy 1.1 actParams,
916 ovy 1.1 declParams,
917 ovy 1.1 externalPointsTo,
918 ovy 1.1 internalPointsTo);
919 ovy 1.1
920 ovy 1.1 addCallDeltas(md,
921 ovy 1.1 qCall.retex(),
922 ovy 1.1 mdCalled.Re,
923 ovy 1.1 actParams,
924 ovy 1.1 declParams,
925 ovy 1.1 externalPointsTo,
926 ovy 1.1 internalPointsTo);
927 ovy 1.1
928 ovy 1.1 addCallDeltas(md,
929 ovy 1.1 ESCAPE,
930 ovy 1.1 mdCalled.E,
931 ovy 1.1 actParams,
932 ovy 1.1 declParams,
933 ovy 1.1 externalPointsTo,
934 ovy 1.1 internalPointsTo);
935 ovy 1.1
936 ovy 1.1 }
937 ovy 1.1
938 ovy 1.1 }
939 ovy 1.1
940 ovy 1.1 }
941 ovy 1.1
942 ovy 1.1
943 ovy 1.1 // what a mouthful
944 ovy 1.1 private void addCallDeltas(MethodData md,
945 ovy 1.1 Object var,
946 ovy 1.1 Set delta,
947 ovy 1.1 Temp[] actParams,
948 ovy 1.1 Temp[] declParams,
949 ovy 1.1 MultiMap externalDeltas,
950 ovy 1.1 MultiMap internalDeltas ) {
951 ovy 1.1
952 ovy 1.1 assert actParams.length == declParams.length;
953 ovy 1.1
954 ovy 1.1 // assume params in rets is actually a rare case
955 ovy 1.1 externalDeltas.addAll(var, delta);
956 ovy 1.1
957 ovy 1.1 for (int i = 0; i<actParams.length; i++) {
958 ovy 1.1 if (delta.contains(declParams[i])) {
959 ovy 1.1
960 ovy 1.1 externalDeltas.remove(var, declParams[i]);
961 ovy 1.1
962 ovy 1.1 if (md.externals.contains(actParams[i])) {
963 ovy 1.1 externalDeltas.add(var, actParams[i]);
964 ovy 1.1 }
965 ovy 1.1
966 ovy 1.1 if (internalDeltas != null)
967 ovy 1.1 internalDeltas.add(var, actParams[i]);
968 ovy 1.1
969 ovy 1.1 }
970 ovy 1.1 }
971 ovy 1.1 }
972 ovy 1.1
973 ovy 1.1
974 ovy 1.1 // propagates deltas through aliases
975 ovy 1.1 private void propagateExternalDeltas(MethodData md, MultiMap deltas) {
976 ovy 1.1 WorkSet workset = new WorkSet();
977 ovy 1.1
978 ovy 1.1 workset.addAll(deltas.keySet());
979 ovy 1.1
980 ovy 1.1 while (!workset.isEmpty()) {
981 ovy 1.1 Object var = workset.removeFirst();
982 ovy 1.1 Collection thisDelta = deltas.getValues(var);
983 ovy 1.1
984 ovy 1.1 // var has a delta, ie new possible values
985 ovy 1.8
986 ovy 1.1 // for all variables that get assigned var
987 ovy 1.1 for (Iterator it = md.aliasedAssigns.getValues(var).iterator();
988 ovy 1.1 it.hasNext(); ) {
989 ovy 1.1 Object assign = it.next();
990 ovy 1.1
991 ovy 1.1 boolean changed = false;
992 ovy 1.1
993 ovy 1.1 // if this variable has a condition associated with it...
994 ovy 1.1 if (md.conditions.containsKey(assign)) {
995 ovy 1.8 Condition condition =
996 ovy 1.8 (Condition) md.conditions.get(assign);
997 ovy 1.1
998 ovy 1.1 // filter deltas through the condition
999 cananian 1.22 for (Object tempO : thisDelta) {
1000 ovy 1.8
1001 cananian 1.22 Temp temp = (Temp) tempO;
1002 ovy 1.8 if (condition.isSatisfiedFor(temp))
1003 ovy 1.1 changed = deltas.add(assign, temp) || changed;
1004 ovy 1.8 else ; // print some debug stuff if you needto
1005 ovy 1.1 }
1006 ovy 1.1 } else {
1007 ovy 1.1 // otherwise, add the whole delta
1008 ovy 1.1 changed = deltas.addAll(assign, thisDelta) || changed;
1009 ovy 1.1 }
1010 ovy 1.1
1011 ovy 1.1 if (changed) workset.addLast(assign);
1012 ovy 1.1 }
1013 ovy 1.1 }
1014 ovy 1.1 }
1015 ovy 1.1
1016 ovy 1.8 // **** Stage 2: Compute incompatibilities
1017 ovy 1.8
1018 ovy 1.8 // Fixed-point logic
1019 ovy 1.1 private void computeI() {
1020 ovy 1.1
1021 ovy 1.1 I = new GenericMultiMap();
1022 ovy 1.5
1023 salcianu 1.13 if(SHOW_PROGRESS)
1024 salcianu 1.13 System.out.print("Computing initial Is");
1025 ovy 1.1
1026 cananian 1.22 for (Object methodO : allMethods) {
1027 cananian 1.22 HMethod method = (HMethod) methodO;
1028 ovy 1.1
1029 ovy 1.1 computeInitialI(method);
1030 ovy 1.1 }
1031 ovy 1.1
1032 ovy 1.1 // fixed point set analysis for I
1033 ovy 1.1 // this is strinkingly similar to the one in stage 1
1034 ovy 1.1 // we should really have a common interface of sorts
1035 ovy 1.1 WorkSet workset = new WorkSet();
1036 ovy 1.1
1037 ovy 1.1 workset.addAll(allMethods);
1038 ovy 1.1
1039 ovy 1.8 if (SHOW_PROGRESS) System.out.print("\nFixed point set (I)");
1040 ovy 1.5
1041 ovy 1.1 while (!workset.isEmpty()) {
1042 ovy 1.1 HMethod method = (HMethod) workset.removeFirst();
1043 ovy 1.1
1044 ovy 1.1 if (recomputeI(method)) {
1045 cananian 1.22 for (Object calleeO : callees.getValues(method)) {
1046 cananian 1.22 HMethod callee = (HMethod) calleeO;
1047 ovy 1.1 workset.addLast(callee);
1048 ovy 1.1 }
1049 ovy 1.1 }
1050 ovy 1.1 }
1051 ovy 1.1
1052 ovy 1.1 // finally, make sure I is symmetric
1053 ovy 1.1 MultiMapUtils.ensureSymmetric(I);
1054 ovy 1.8 if (SHOW_PROGRESS) System.out.println();
1055 ovy 1.1 }
1056 ovy 1.1
1057 ovy 1.1 private void computeInitialI(HMethod method) {
1058 salcianu 1.13 if(SHOW_PROGRESS) System.out.print(".");
1059 ovy 1.1 MethodData md = (MethodData) mdCache.get(method);
1060 ovy 1.1 if (md == null || md.isNative) return;
1061 ovy 1.1
1062 ovy 1.1 Collection params = Arrays.asList(md.header.params());
1063 ovy 1.1
1064 ovy 1.1
1065 ovy 1.11 // System.out.println("> i enter: " + method);
1066 ovy 1.1 // init Ip
1067 ovy 1.1 md.Ip = new GenericMultiMap(new AggregateSetFactory());
1068 ovy 1.1
1069 ovy 1.1 // compute pointsTo information
1070 ovy 1.1 MultiMap pointsTo = new GenericMultiMap();
1071 ovy 1.1 computePointsTo(md, pointsTo, null);
1072 ovy 1.11 // System.out.println("pointsto...");
1073 ovy 1.1 propagateExternalDeltas(md, pointsTo);
1074 ovy 1.11 // System.out.println("extdeltas...");
1075 ovy 1.11
1076 ovy 1.1
1077 ovy 1.8 // compute "meta allocation nodes", i.e. nodes that directly or
1078 ovy 1.8 // indirectly cause allocations
1079 ovy 1.8 Collection interestingNodes =
1080 ovy 1.8 new ArrayList(md.allocationSites.size() + md.calls.keySet().size());
1081 ovy 1.1 interestingNodes.addAll(md.allocationSites);
1082 ovy 1.1 interestingNodes.addAll(md.calls.keySet());
1083 ovy 1.11 // System.out.println("Interestingnodes: " + interestingNodes.size());
1084 ovy 1.1
1085 ovy 1.1 // compute mappings from escape sites to things that escape there
1086 ovy 1.8
1087 ovy 1.8 // first, simple escapes
1088 ovy 1.11 // System.out.println("Simple escapes...");
1089 ovy 1.1 MultiMap escapes = new GenericMultiMap();
1090 cananian 1.22 for (Object qO : md.escapeSites) {
1091 cananian 1.22 Quad q = (Quad) qO;
1092 ovy 1.1 if (q.kind() == QuadKind.SET) {
1093 ovy 1.1 SET qSet = (SET) q;
1094 ovy 1.1 escapes.addAll(qSet, pointsTo.getValues(qSet.src()));
1095 ovy 1.1 } else if (q.kind() == QuadKind.ASET) {
1096 ovy 1.1 ASET qASet = (ASET) q;
1097 ovy 1.1 escapes.addAll(qASet, pointsTo.getValues(qASet.src()));
1098 ovy 1.1 }
1099 ovy 1.1 }
1100 ovy 1.1
1101 ovy 1.11 // System.out.println("Escapes from calls...");
1102 ovy 1.8 // escapes from calls
1103 cananian 1.22 for (Object qCallO : md.calls.keySet()) {
1104 cananian 1.22 CALL qCall = (CALL) qCallO;
1105 ovy 1.1 Temp[] actParams = qCall.params();
1106 ovy 1.1
1107 cananian 1.22 for (Object calledO : md.calls.getValues(qCall)) {
1108 cananian 1.22 HMethod called = (HMethod) calledO;
1109 ovy 1.1 MethodData mdCalled = (MethodData) mdCache.get(called);
1110 ovy 1.1
1111 ovy 1.1 if (mdCalled == null || mdCalled.isNative) continue;
1112 ovy 1.1
1113 ovy 1.8
1114 ovy 1.1 Temp[] declParams = mdCalled.header.params();
1115 ovy 1.8
1116 ovy 1.1 escapes.addAll(qCall, mdCalled.E);
1117 ovy 1.1
1118 ovy 1.1 // do param replacement; add pointsTo for params
1119 ovy 1.1 for (int i = 0; i<actParams.length; i++) {
1120 ovy 1.1 if (escapes.contains(qCall, declParams[i])) {
1121 ovy 1.1 escapes.remove(qCall, declParams[i]);
1122 ovy 1.1 escapes.addAll(qCall, pointsTo.getValues(actParams[i]));
1123 ovy 1.1 }
1124 ovy 1.1 }
1125 ovy 1.1
1126 ovy 1.1 }
1127 ovy 1.1 }
1128 ovy 1.1
1129 ovy 1.11 // System.out.println("Total escapes: " + escapes.size());
1130 ovy 1.11
1131 ovy 1.11 Set escKeySet = new HashSet(escapes.keySet());
1132 ovy 1.11
1133 ovy 1.11 // System.out.println("Per meta alloc node...");
1134 ovy 1.8 // for each meta alloc node
1135 cananian 1.22 for (Object qO : interestingNodes) {
1136 cananian 1.22 Quad q = (Quad) qO;
1137 ovy 1.1
1138 ovy 1.1 Set allocs;
1139 ovy 1.1
1140 ovy 1.1 // allocs for outgoing edges
1141 ovy 1.1 Set[] edgeAllocs = new Set[q.nextLength()];
1142 salcianu 1.18 // outgoing dest vars
1143 salcianu 1.18 Temp[] edgeDst = new Temp[q.nextLength()];
1144 ovy 1.11
1145 salcianu 1.16 // System.out.println(" Per node: " + Util.code2str(q));
1146 ovy 1.1 if (q.kind() == QuadKind.NEW) {
1147 ovy 1.1 allocs = edgeAllocs[0] = Collections.singleton( ((NEW) q).dst());
1148 salcianu 1.18
1149 salcianu 1.18 edgeDst[0] = ((NEW) q).dst();
1150 ovy 1.1 } else {
1151 ovy 1.1 assert q.kind() == QuadKind.CALL;
1152 ovy 1.1
1153 ovy 1.1 edgeAllocs[0]= new HashSet();
1154 ovy 1.1 edgeAllocs[1] = new HashSet();
1155 ovy 1.1
1156 cananian 1.22 for (Object calledO : md.calls.getValues(q)) {
1157 cananian 1.22 HMethod called = (HMethod) calledO;
1158 ovy 1.1 MethodData mdCalled = (MethodData) mdCache.get(called);
1159 ovy 1.1
1160 ovy 1.1 if (mdCalled == null || mdCalled.isNative) continue;
1161 ovy 1.1
1162 ovy 1.1 edgeAllocs[0].addAll(mdCalled.An);
1163 ovy 1.1 edgeAllocs[1].addAll(mdCalled.Ae);
1164 ovy 1.1 }
1165 ovy 1.1
1166 ovy 1.1 allocs = new HashSet(edgeAllocs[0].size()
1167 ovy 1.1 + edgeAllocs[1].size());
1168 ovy 1.1 allocs.addAll(edgeAllocs[0]);
1169 ovy 1.1 allocs.addAll(edgeAllocs[1]);
1170 salcianu 1.18
1171 salcianu 1.18 edgeDst[0] = ((CALL) q).retval();
1172 salcianu 1.18 edgeDst[1] = ((CALL) q).retex();
1173 ovy 1.1 }
1174 ovy 1.1
1175 ovy 1.1 // add incompatibilities from escapes
1176 ovy 1.1 // compute reachability of this node (there are more efficient
1177 ovy 1.1 // ways though...)
1178 ovy 1.1
1179 ovy 1.11 // System.out.println(" # allocs: " + allocs.size());
1180 ovy 1.1 Set canReachQ = canReach(Collections.singleton(q), false);
1181 ovy 1.1
1182 ovy 1.11 // System.out.println(" escapes x allocs... ");
1183 ovy 1.1
1184 ovy 1.11 Set escCanReachQ = MultiMapUtils.multiMapUnion(escapes,
1185 ovy 1.11 canReachQ);
1186 ovy 1.11 /// System.out.println(" # escCanReachQ: " + escCanReachQ.size());
1187 ovy 1.11
1188 cananian 1.22 for (Object escapedO : escCanReachQ) {
1189 cananian 1.22 Temp escaped = (Temp) escapedO;
1190 ovy 1.11 if (params.contains(escaped)) {
1191 ovy 1.11 md.Ip.addAll(escaped, allocs);
1192 ovy 1.11 } else {
1193 ovy 1.11 assert globalAllocMap.containsKey(escaped);
1194 ovy 1.11 I.addAll(escaped, allocs);
1195 ovy 1.1 }
1196 ovy 1.1 }
1197 ovy 1.11
1198 ovy 1.11 // System.out.println(" # escCanReachQ: " + escCanReachQ);
1199 ovy 1.1
1200 ovy 1.11 // System.out.println(" # live-in objects: " + liveInObjects.size());
1201 ovy 1.1
1202 ovy 1.1 // add incompatibilities from liveness
1203 ovy 1.1 // for each outgoing edge
1204 ovy 1.1 for (int i = 0; i<q.nextLength(); i++) {
1205 ovy 1.1 // edgeAllocs empty? no point going on
1206 ovy 1.1 if (edgeAllocs[i].isEmpty()) continue;
1207 ovy 1.1
1208 ovy 1.1 Edge edge = q.nextEdge(i);
1209 ovy 1.1
1210 ovy 1.1 Collection liveInternal = md.liveness.getValues(edge);
1211 ovy 1.1
1212 salcianu 1.18 liveInternal.remove(edgeDst[i]);
1213 salcianu 1.18
1214 salcianu 1.18 Set liveOverObjects =
1215 salcianu 1.18 MultiMapUtils.multiMapUnion(pointsTo, liveInternal);
1216 ovy 1.1
1217 ovy 1.1 // all live objects become incompatible with allocs here
1218 ovy 1.1 // again, a good ol' cartesian product
1219 cananian 1.22 for (Object liveO : liveOverObjects) {
1220 cananian 1.22 Temp live = (Temp) liveO;
1221 ovy 1.1
1222 ovy 1.1 if (params.contains(live)) {
1223 ovy 1.1 md.Ip.addAll(live, edgeAllocs[i]);
1224 ovy 1.1 } else {
1225 ovy 1.1 assert globalAllocMap.containsKey(live);
1226 ovy 1.1
1227 ovy 1.1 I.addAll(live, edgeAllocs[i]);
1228 ovy 1.1 }
1229 ovy 1.1 }
1230 ovy 1.1 }
1231 ovy 1.11
1232 ovy 1.1 }
1233 ovy 1.11
1234 ovy 1.11 // System.out.println("< i exit");
1235 ovy 1.6
1236 ovy 1.1 }
1237 ovy 1.1
1238 ovy 1.1
1239 ovy 1.8 private boolean recomputeI(HMethod method) {
1240 ovy 1.8 if (SHOW_PROGRESS) System.out.print(".");
1241 ovy 1.1 MethodData md = (MethodData) mdCache.get(method);
1242 ovy 1.1 assert !md.isNative;
1243 ovy 1.1
1244 ovy 1.1 int ipSize = md.Ip.size();
1245 ovy 1.1
1246 ovy 1.1
1247 ovy 1.1 // This is terribly, terribly inefficient
1248 ovy 1.1 // Should really be using deltas...
1249 ovy 1.1 // (yes, here too :)
1250 ovy 1.1
1251 ovy 1.1 MultiMap pointsTo = new GenericMultiMap();
1252 ovy 1.1 computePointsTo(md, pointsTo, null);
1253 ovy 1.1 propagateExternalDeltas(md, pointsTo);
1254 ovy 1.1
1255 ovy 1.1 Collection params = Arrays.asList(md.header.params());
1256 ovy 1.1
1257 cananian 1.22 for (Object qCallO : md.calls.keySet()) {
1258 cananian 1.22 CALL qCall = (CALL) qCallO;
1259 ovy 1.1 Temp[] actParams = qCall.params();
1260 ovy 1.1
1261 ovy 1.1
1262 cananian 1.22 for (Object calledO : md.calls.getValues(qCall)) {
1263 cananian 1.22 HMethod called = (HMethod) calledO;
1264 ovy 1.1 MethodData mdCalled = (MethodData) mdCache.get(called);
1265 ovy 1.1
1266 ovy 1.1 if (mdCalled == null || mdCalled.isNative) continue;
1267 ovy 1.1 Temp [] declParams = mdCalled.header.params();
1268 ovy 1.1
1269 ovy 1.1 // replace params
1270 ovy 1.1 for (int i = 0; i<actParams.length; i++) {
1271 ovy 1.1 if (mdCalled.Ip.containsKey(declParams[i])) {
1272 cananian 1.22 for (Object tempO : pointsTo.getValues(actParams[i])) {
1273 cananian 1.22 Temp temp = (Temp) tempO;
1274 ovy 1.1
1275 ovy 1.1 if (params.contains(temp)) {
1276 ovy 1.1 md.Ip.addAll(temp,
1277 ovy 1.1 mdCalled.Ip.getValues(declParams[i]));
1278 ovy 1.1 }
1279 ovy 1.1 else {
1280 ovy 1.1 I.addAll(temp,
1281 ovy 1.1 mdCalled.Ip.getValues(declParams[i]));
1282 ovy 1.1 }
1283 ovy 1.1
1284 ovy 1.1 }
1285 ovy 1.1 }
1286 ovy 1.1 }
1287 ovy 1.1 }
1288 ovy 1.1
1289 ovy 1.1 }
1290 ovy 1.1
1291 ovy 1.1 return ipSize != md.Ip.size();
1292 ovy 1.1 }
1293 ovy 1.1
1294 ovy 1.8 // **** Stage 3: classes computation
1295 ovy 1.1
1296 ovy 1.8 // FIXME: try alternate heuristics that take sizes into account
1297 ovy 1.1 private void computeClasses() {
1298 ovy 1.8 selfCompatible = new HashSet();
1299 ovy 1.1 selfIncompatible = new HashSet();
1300 ovy 1.1
1301 ovy 1.1 // compute self-compatibles and self-incompatibles
1302 cananian 1.22 for (Object allocO : globalAllocMap.keySet()) {
1303 cananian 1.22 Temp alloc = (Temp) allocO;
1304 ovy 1.1
1305 ovy 1.1 if (I.contains(alloc, alloc)) {
1306 ovy 1.1 selfIncompatible.add(alloc);
1307 ovy 1.1 } else {
1308 ovy 1.1 selfCompatible.add(alloc);
1309 ovy 1.1 }
1310 ovy 1.1
1311 ovy 1.1 }
1312 ovy 1.1
1313 ovy 1.8 classes = MyGraphColorer.colorGraph(selfCompatible, I);
1314 ovy 1.1
1315 ovy 1.8 }
1316 ovy 1.1
1317 ovy 1.1
1318 ovy 1.8
1319 ovy 1.8 // *** Lots and lots of debugging code
1320 ovy 1.8
1321 ovy 1.8 // This prints the statistics. Comment in/out what you want
1322 salcianu 1.14 public void printStatistics(Frame frame, Linker linker) {
1323 ovy 1.1
1324 salcianu 1.13 if(VERBOSE_STATISTICS) {
1325 salcianu 1.13 // show off some end-results
1326 salcianu 1.13 MethodData md = (MethodData) mdCache.get(entry);
1327 salcianu 1.13
1328 salcianu 1.13 // System.out.println("An for entry: " + md.An);
1329 salcianu 1.13 // System.out.println("Ae for entry: " + md.Ae);
1330 salcianu 1.13
1331 salcianu 1.13 HashSet allocs = new HashSet(md.An);
1332 salcianu 1.13 allocs.add(md.Ae);
1333 salcianu 1.13
1334 salcianu 1.13 // System.out.println("Rn for entry: " + md.Rn);
1335 salcianu 1.13 // System.out.println("Re for entry: " + md.Re);
1336 salcianu 1.13
1337 salcianu 1.13 // System.out.println("E for entry: " + md.E);
1338 salcianu 1.13
1339 salcianu 1.13 // System.out.println("Liveness for entry: " + md.liveness);
1340 salcianu 1.13 // System.out.println("aliases for entry: " + md.aliasedValues);
1341 salcianu 1.13
1342 salcianu 1.13 // System.out.println("Incompatibility: " + I);
1343 salcianu 1.13
1344 salcianu 1.13
1345 salcianu 1.13 // System.out.println("Classes: ");
1346 salcianu 1.13 // System.out.println(classes);
1347 salcianu 1.13
1348 salcianu 1.13 // System.out.println("selfIncompatible: " + selfIncompatible);
1349 salcianu 1.13
1350 salcianu 1.13 // System.out.println("Legend: ");
1351 salcianu 1.13 // printTempCollection(I.keySet());
1352 salcianu 1.13
1353 salcianu 1.13 System.out.println("escape detail: ");
1354 salcianu 1.13 printTempCollection(md.E);
1355 salcianu 1.13
1356 salcianu 1.13 System.out.println("Self-incompatible detail: ");
1357 salcianu 1.13 printTempCollection(selfIncompatible);
1358 salcianu 1.13
1359 salcianu 1.13
1360 salcianu 1.13 System.out.println("Global type statistics: ");
1361 salcianu 1.13 printTypeStatistics(globalAllocMap.keySet());
1362 salcianu 1.13
1363 salcianu 1.13 System.out.println("Totally compatible type statistics: ");
1364 salcianu 1.13 Collection totally = new HashSet(globalAllocMap.keySet());
1365 salcianu 1.13 totally.removeAll(I.keySet());
1366 salcianu 1.13 printTypeStatistics(totally);
1367 salcianu 1.13
1368 salcianu 1.13 System.out.println("Class type statistics: ");
1369 salcianu 1.13 int nclass = 0;
1370 cananian 1.22 for (Object thisClassO : classes) {
1371 cananian 1.22 Collection thisClass = (Collection) thisClassO;
1372 salcianu 1.13 nclass++;
1373 salcianu 1.13
1374 salcianu 1.13 System.out.println(" *Class " + nclass);
1375 salcianu 1.13
1376 salcianu 1.13 assert MultiMapUtils.intersect(thisClass,
1377 salcianu 1.13 selfIncompatible).isEmpty();
1378 ovy 1.1
1379 salcianu 1.13 printTypeStatistics(thisClass);
1380 salcianu 1.13 }
1381 ovy 1.1
1382 ovy 1.1
1383 salcianu 1.13 System.out.println("Self-incompatible type statistics: ");
1384 salcianu 1.13 printTypeStatistics(selfIncompatible, globalAllocMap.keySet());
1385 salcianu 1.13
1386 salcianu 1.13 System.out.println("Statics type statics: ");
1387 salcianu 1.13 printTypeStatistics(selfCompatible, globalAllocMap.keySet());
1388 salcianu 1.13 }
1389 ovy 1.1
1390 salcianu 1.13
1391 salcianu 1.13 System.out.println("Statistics: ");
1392 salcianu 1.17 System.out.println
1393 salcianu 1.17 (" " + allMethods.size() + " methods analyzed;\t" +
1394 salcianu 1.17 sizeStatistics(allMethods, codeFactory) + " SSI;\t" +
1395 salcianu 1.17 sizeStatistics(allMethods,
1396 salcianu 1.17 harpoon.IR.Bytecode.Code.codeFactory()) +
1397 salcianu 1.17 " bytecodes");
1398 ovy 1.1 System.out.println(" " + globalAllocMap.keySet().size() + " allocations");
1399 ovy 1.1 System.out.println(" " + I.size() + " incompatible pairs");
1400 ovy 1.1 System.out.println(" " + classes.size() + " classes ("
1401 ovy 1.1 + (100 - (classes.size()*100/(globalAllocMap.keySet().size() - selfIncompatible.size()))) +"% reduction)");
1402 ovy 1.1 System.out.println(" " + selfIncompatible.size() + " self-incompatible vars ("+(selfIncompatible.size()*100/globalAllocMap.keySet().size())+"%)");
1403 ovy 1.8
1404 ovy 1.8
1405 salcianu 1.14 // compute the pre-allocated memory size
1406 salcianu 1.14 long psize = 0L; // size of preallocated memory (with packing)
1407 salcianu 1.14 long usize = 0L; // size of preallocated memory (no packing)
1408 ovy 1.8
1409 ovy 1.8 Collection allocClasses = getCompatibleClasses();
1410 ovy 1.8
1411 cananian 1.22 for (Object thisClassO : allocClasses) {
1412 cananian 1.22 Collection thisClass = (Collection) thisClassO;
1413 salcianu 1.14 long max = 0L;
1414 salcianu 1.14 for(Iterator itc = thisClass.iterator(); itc.hasNext(); ) {
1415 salcianu 1.14 HClass allocatedClass = ((NEW) itc.next()).hclass();
1416 salcianu 1.14 int size = SIZE_IN_BYTES ?
1417 salcianu 1.15 PreallocOpt.sizeForClass(frame.getRuntime(),
1418 salcianu 1.15 allocatedClass) :
1419 salcianu 1.14 fieldsForClass(allocatedClass);
1420 salcianu 1.14 usize += size;
1421 salcianu 1.14 max = Math.max(max, size);
1422 salcianu 1.14 }
1423 salcianu 1.14 psize += max;
1424 ovy 1.8 }
1425 ovy 1.8
1426 salcianu 1.14 System.out.println
1427 salcianu 1.14 ("Preallocated memory size " +
1428 salcianu 1.14 (SIZE_IN_BYTES ? "(bytes): " : "(fields): ") +
1429 salcianu 1.14 usize + " (normal) / " +
1430 salcianu 1.14 psize + " (sharing);\treduction = " +
1431 salcianu 1.16 Util.doubleRep
1432 salcianu 1.14 ( (100 * ((double) usize - psize)) / ((double) usize), 5, 2) +
1433 salcianu 1.14 "%");
1434 salcianu 1.14
1435 salcianu 1.14 printSubTypeStatistics("Exceptions",
1436 salcianu 1.14 linker.forName("java.lang.Throwable"));
1437 salcianu 1.14 printSubTypeStatistics("StringBuffers",
1438 salcianu 1.14 linker.forName("java.lang.StringBuffer"));
1439 salcianu 1.14 printSubTypeStatistics("Iterators",
1440 salcianu 1.14 linker.forName("java.util.Iterator"));
1441 ovy 1.8 }
1442 ovy 1.8
1443 salcianu 1.14 private void printSubTypeStatistics(String label, HClass hclass) {
1444 ovy 1.8 int total = countTempIsA(globalAllocMap.keySet(), hclass);
1445 salcianu 1.14 int stat = countTempIsA(selfCompatible, hclass);
1446 ovy 1.8
1447 salcianu 1.14 System.out.println(label + "\t" + stat + "\tof " + total +
1448 salcianu 1.14 "\t" + (stat*100/Math.max(total, 1)) + "%");
1449 ovy 1.8 }
1450 ovy 1.8
1451 ovy 1.8 private int countTempIsA(Collection temps, HClass hclass) {
1452 ovy 1.8 int count = 0;
1453 ovy 1.8
1454 cananian 1.22 for (Object tempO : temps) {
1455 cananian 1.22 Temp temp = (Temp) tempO;
1456 ovy 1.8
1457 ovy 1.8 if (tempIsA(temp, hclass)) count ++;
1458 ovy 1.8 }
1459 ovy 1.8
1460 ovy 1.8 return count;
1461 ovy 1.8 }
1462 ovy 1.8
1463 salcianu 1.14
1464 salcianu 1.14 private static int fieldsForClass(HClass hclass) {
1465 salcianu 1.14 return hclass.getFields().length + ADD_FIELDS;
1466 salcianu 1.4 }
1467 salcianu 1.14
1468 salcianu 1.4
1469 salcianu 1.4 private void printmap(Map map) {
1470 cananian 1.22 for (Object entryO : map.entrySet()) {
1471 cananian 1.22 Map.Entry entry = (Map.Entry) entryO;
1472 salcianu 1.4 Quad from = (Quad) entry.getKey();
1473 salcianu 1.4 Quad to = (Quad) entry.getValue();
1474 salcianu 1.4
1475 salcianu 1.4 if (from instanceof NEW) {
1476 salcianu 1.16 System.out.println(" " +Util.code2str(from) + " | " +
1477 salcianu 1.4 from.hashCode() + " -> ");
1478 salcianu 1.16 System.out.println(" " +Util.code2str(to) + " | " +
1479 salcianu 1.4 to.hashCode());
1480 salcianu 1.4 }
1481 salcianu 1.4 }
1482 ovy 1.1 }
1483 ovy 1.8
1484 ovy 1.1
1485 ovy 1.8 private Map getTypeCountMap(Collection temps) {
1486 ovy 1.8 Map count = new HashMap();
1487 ovy 1.1
1488 cananian 1.22 for (Object tempO : temps) {
1489 cananian 1.22 Temp temp = (Temp) tempO;
1490 ovy 1.1 HClass type = ((NEW) globalAllocMap.get(temp)).hclass();
1491 ovy 1.1 if (count.containsKey(type)) {
1492 ovy 1.1 Integer inMap = (Integer) count.get(type);
1493 ovy 1.1 count.put(type, new Integer(inMap.intValue() + 1));
1494 ovy 1.1 }
1495 ovy 1.1 else {
1496 ovy 1.1 count.put(type, new Integer(1));
1497 ovy 1.1 }
1498 ovy 1.1 }
1499 ovy 1.1
1500 ovy 1.8 return count;
1501 ovy 1.8 }
1502 ovy 1.8
1503 ovy 1.8 private void printTypeStatistics(Collection temps) {
1504 ovy 1.8 printTypeStatistics(temps, null);
1505 ovy 1.8 }
1506 ovy 1.1
1507 ovy 1.8 private void printTypeStatistics(Collection temps, Collection correl) {
1508 ovy 1.8 final Map count = getTypeCountMap(temps);
1509 ovy 1.8 Map count_correl = correl != null ?
1510 ovy 1.8 getTypeCountMap(correl) : null;
1511 ovy 1.8
1512 ovy 1.1 // sort
1513 ovy 1.1 Object[] types = count.keySet().toArray();
1514 ovy 1.1
1515 ovy 1.1 Arrays.sort(types, new Comparator() {
1516 ovy 1.1 public int compare(Object a, Object b) {
1517 ovy 1.1 Integer ac = (Integer) count.get(a);
1518 ovy 1.1 Integer bc = (Integer) count.get(b);
1519 ovy 1.1 return ac.compareTo(bc);
1520 ovy 1.1 };
1521 ovy 1.1 });
1522 ovy 1.1
1523 ovy 1.1 int total = 0;
1524 ovy 1.1 for (int i = 0; i<types.length; i++) {
1525 ovy 1.8 int c_this = ((Integer) count.get(types[i])).intValue();
1526 ovy 1.8 System.out.print(" " + types[i] + ": " + c_this);
1527 ovy 1.8
1528 ovy 1.8 if (correl != null) {
1529 ovy 1.8 int c_correl =
1530 ovy 1.8 ((Integer) count_correl.get(types[i])).intValue();
1531 ovy 1.8 System.out.println(" (of " + c_correl + ", " +
1532 ovy 1.8 c_this*100/c_correl + "%)");
1533 ovy 1.8 } else System.out.println();
1534 ovy 1.8
1535 ovy 1.8 total+= c_this;
1536 ovy 1.1 }
1537 ovy 1.1 System.out.println(" total: " + total);
1538 ovy 1.1
1539 ovy 1.1 }
1540 ovy 1.1
1541 ovy 1.11 public static long sizeStatistics(Collection methods, HCodeFactory factory) {
1542 ovy 1.8 long nElements = 0;
1543 cananian 1.22 for (Object methodO : methods) {
1544 cananian 1.22 HMethod method = (HMethod) methodO;
1545 ovy 1.8 HCode hc = factory.convert(method);
1546 ovy 1.8
1547 ovy 1.8 if (hc!=null)
1548 ovy 1.8 nElements+= hc.getElementsL().size();
1549 ovy 1.8 }
1550 ovy 1.8
1551 ovy 1.8 return nElements;
1552 ovy 1.8 }
1553 ovy 1.8
1554 ovy 1.1 // some helper methods for debugging
1555 ovy 1.1
1556 ovy 1.8 private boolean tempIsA(Object temp, HClass hclass) {
1557 ovy 1.1 if (globalAllocMap.containsKey(temp)) {
1558 ovy 1.8 return isA(((NEW) globalAllocMap.get(temp)).hclass(), hclass);
1559 ovy 1.1 } else return false;
1560 ovy 1.1 }
1561 ovy 1.1
1562 ovy 1.8 // i would think hclass would have something like this...
1563 ovy 1.8 private static boolean isA(HClass hclass, HClass what) {
1564 ovy 1.8 if (what == null) return false;
1565 ovy 1.8
1566 ovy 1.8 if (what.isInterface())
1567 ovy 1.8 return what.isSuperinterfaceOf(hclass);
1568 ovy 1.8 else
1569 ovy 1.8 return what.isSuperclassOf(hclass);
1570 ovy 1.8 }
1571 ovy 1.8
1572 ovy 1.8
1573 ovy 1.8
1574 ovy 1.1 private void printTempCollection(Collection temps) {
1575 cananian 1.22 for (Object allocO : temps) {
1576 cananian 1.22 Temp alloc = (Temp) allocO;
1577 ovy 1.1
1578 ovy 1.1 if (I.getValues(alloc).isEmpty()) continue;
1579 ovy 1.1
1580 ovy 1.1 System.out.println(" " + alloc + ": "
1581 salcianu 1.16 + Util.code2str((NEW) globalAllocMap.get(alloc)));
1582 ovy 1.1 }
1583 ovy 1.1 }
1584 ovy 1.1
1585 ovy 1.1 private NEW allocQuad(Temp temp) {
1586 ovy 1.1 if (globalAllocMap.containsKey(temp)) {
1587 ovy 1.1 return (NEW) globalAllocMap.get(temp);
1588 ovy 1.1 } else return null;
1589 ovy 1.1 }
1590 ovy 1.1
1591 ovy 1.1
1592 ovy 1.1 private class TypeSwitchCondition implements Condition {
1593 ovy 1.1 TYPESWITCH typeswitch;
1594 ovy 1.1 int branch;
1595 ovy 1.1
1596 ovy 1.1 TypeSwitchCondition(TYPESWITCH typeswitch, int branch) {
1597 ovy 1.1 this.typeswitch = typeswitch;
1598 ovy 1.1 this.branch = branch;
1599 ovy 1.1 }
1600 ovy 1.1
1601 ovy 1.1 public boolean isSatisfiedFor(Object object) {
1602 ovy 1.1 if (!(object instanceof Temp)) return false;
1603 ovy 1.1
1604 ovy 1.1 Object alloc = globalAllocMap.get(object);
1605 ovy 1.1
1606 ovy 1.1 // if not allocated, satisfies
1607 ovy 1.1 if (alloc == null) return true;
1608 ovy 1.1
1609 ovy 1.1 HClass hclass = ((NEW) alloc).hclass();
1610 ovy 1.1
1611 ovy 1.1 // default?
1612 ovy 1.1 // asume default branch is the last, as is apparently the case now
1613 ovy 1.1 if (typeswitch.hasDefault() &&
1614 ovy 1.1 branch == typeswitch.keysLength()) {
1615 ovy 1.1 // yes...
1616 ovy 1.1 // then hclass must not extend any of the keys
1617 ovy 1.1
1618 ovy 1.1 for (int i = 0; i<typeswitch.keysLength(); i++)
1619 ovy 1.1 if (isA(hclass, typeswitch.keys(i)))
1620 ovy 1.1 return false;
1621 ovy 1.1
1622 ovy 1.1 return true;
1623 ovy 1.1 } else {
1624 ovy 1.1 // no...
1625 ovy 1.1 // then hclass must extend the corresponding key
1626 ovy 1.1 return isA(hclass, typeswitch.keys(branch));
1627 ovy 1.1 }
1628 ovy 1.1
1629 ovy 1.1 }
1630 ovy 1.1
1631 ovy 1.1 public String toString() {
1632 ovy 1.1 return "{branch " + branch + " of " + typeswitch + "}";
1633 ovy 1.1 }
1634 ovy 1.1 }
1635 ovy 1.1
1636 ovy 1.1 }
1637 ovy 1.1
1638 ovy 1.1 class MethodData {
1639 ovy 1.1 // This is the data we keep for each method
1640 ovy 1.1
1641 ovy 1.8 // **** initial (static) data
1642 ovy 1.1
1643 ovy 1.1 // if this is set, everything else should be ignored
1644 ovy 1.1 boolean isNative = false;
1645 ovy 1.1
1646 ovy 1.1 // maps edges to sets of live allocations
1647 ovy 1.1 MultiMap liveness;
1648 ovy 1.1
1649 ovy 1.1 // Interesting nodes that can reach normal / exceptional returns
1650 ovy 1.1 Set reachNormal;
1651 ovy 1.1 Set reachEx;
1652 ovy 1.1
1653 ovy 1.1 // maps call sites to possibly called methods, for ease of use
1654 ovy 1.1 MultiMap calls;
1655 ovy 1.1
1656 ovy 1.1 // these are vars that are internal and should not appear in returns
1657 ovy 1.8 Set internals;
1658 ovy 1.8 // guess what these are
1659 ovy 1.1 Set externals;
1660 ovy 1.1
1661 ovy 1.1 // maps internals to the condition, if any, under which an object
1662 ovy 1.1 // is assigned to an internal (think TYPESWITCH)
1663 ovy 1.1 Map conditions;
1664 ovy 1.1
1665 ovy 1.1 MultiMap param2calls;
1666 ovy 1.1
1667 ovy 1.1 Collection allocationSites;
1668 ovy 1.1 Collection escapeSites;
1669 ovy 1.1
1670 ovy 1.1 // the header of this method
1671 ovy 1.1 METHOD header;
1672 ovy 1.1
1673 ovy 1.8 // **** data that will be constructed through fixed-point
1674 ovy 1.1
1675 ovy 1.1 // helper information: pointsTo information for internals
1676 ovy 1.1 // maps internal variables to possible values
1677 ovy 1.1 MultiMap aliasedValues;
1678 ovy 1.1 // inverse of the above. has to be kept in sync
1679 ovy 1.1 MultiMap aliasedAssigns;
1680 ovy 1.1
1681 ovy 1.1 Set An, Ae, Rn, Re, E;
1682 ovy 1.1
1683 ovy 1.1 // parameter incompatibilities
1684 ovy 1.1 MultiMap Ip;
1685 ovy 1.1 }
1686 ovy 1.1
1687 ovy 1.1 // FIXME: move this outside
1688 ovy 1.8 // ... or maybe not. Does anybody else need it?
1689 ovy 1.1 interface Condition {
1690 ovy 1.1 public boolean isSatisfiedFor(Object object);
1691 ovy 1.1 }
1692 ovy 1.1
1693 ovy 1.1
1694 ovy 1.1
1695 ovy 1.1
1696 ovy 1.1
1697 ovy 1.1
1698 ovy 1.1
1699 ovy 1.1