1 kkz 1.1.2.1 // MRAFactory.java, created Sat Oct 13 19:47:53 2001 by kkz
2 kkz 1.1.2.1 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.mit.edu>
3 kkz 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1.2.1 package harpoon.Analysis.PreciseGC;
5 kkz 1.1.2.1
6 kkz 1.1.2.1 import harpoon.Analysis.BasicBlock;
7 kkz 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
8 kkz 1.7 import harpoon.Analysis.Quads.CachingCallGraph;
9 kkz 1.1.2.4 import harpoon.Analysis.Quads.CallGraph;
10 kkz 1.1.2.4 import harpoon.Analysis.Quads.CallGraphImpl;
11 kkz 1.1.2.1 import harpoon.ClassFile.CachingCodeFactory;
12 kkz 1.1.2.1 import harpoon.ClassFile.HCode;
13 kkz 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
14 kkz 1.1.2.1 import harpoon.ClassFile.HMethod;
15 kkz 1.1.2.2 import harpoon.ClassFile.Linker;
16 kkz 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
17 kkz 1.1.2.1 import harpoon.IR.Properties.UseDefer;
18 kkz 1.1.2.1 import harpoon.IR.Quads.AGET;
19 kkz 1.1.2.1 import harpoon.IR.Quads.ANEW;
20 kkz 1.1.2.1 import harpoon.IR.Quads.ARRAYINIT;
21 kkz 1.1.2.1 import harpoon.IR.Quads.ASET;
22 kkz 1.1.2.1 import harpoon.IR.Quads.CALL;
23 kkz 1.1.2.1 import harpoon.IR.Quads.CJMP;
24 kkz 1.1.2.1 import harpoon.IR.Quads.CONST;
25 kkz 1.1.2.1 import harpoon.IR.Quads.Code;
26 kkz 1.1.2.1 import harpoon.IR.Quads.Edge;
27 kkz 1.1.2.1 import harpoon.IR.Quads.FOOTER;
28 kkz 1.1.2.1 import harpoon.IR.Quads.GET;
29 kkz 1.1.2.1 import harpoon.IR.Quads.HEADER;
30 kkz 1.1.2.1 import harpoon.IR.Quads.INSTANCEOF;
31 kkz 1.1.2.1 import harpoon.IR.Quads.METHOD;
32 kkz 1.1.2.1 import harpoon.IR.Quads.MONITORENTER;
33 kkz 1.1.2.1 import harpoon.IR.Quads.MONITOREXIT;
34 kkz 1.1.2.1 import harpoon.IR.Quads.MOVE;
35 kkz 1.1.2.1 import harpoon.IR.Quads.NEW;
36 kkz 1.1.2.1 import harpoon.IR.Quads.NOP;
37 kkz 1.1.2.1 import harpoon.IR.Quads.OPER;
38 kkz 1.1.2.1 import harpoon.IR.Quads.PHI;
39 kkz 1.1.2.1 import harpoon.IR.Quads.Qop;
40 kkz 1.1.2.1 import harpoon.IR.Quads.Quad;
41 kkz 1.1.2.1 import harpoon.IR.Quads.QuadKind;
42 kkz 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
43 kkz 1.1.2.1 import harpoon.IR.Quads.QuadFactory;
44 kkz 1.1.2.1 import harpoon.IR.Quads.RETURN;
45 kkz 1.1.2.1 import harpoon.IR.Quads.SET;
46 kkz 1.1.2.1 import harpoon.IR.Quads.SIGMA;
47 kkz 1.1.2.1 import harpoon.IR.Quads.THROW;
48 kkz 1.1.2.1 import harpoon.IR.Quads.TYPESWITCH;
49 kkz 1.1.2.1 import harpoon.Temp.Temp;
50 kkz 1.7 import harpoon.Util.Collections.WorkSet;
51 cananian 1.8 import net.cscott.jutil.Default;
52 kkz 1.1.2.2 import harpoon.Util.ParseUtil;
53 kkz 1.1.2.4 import harpoon.Util.Tuple;
54 kkz 1.1.2.1 import harpoon.Util.Util;
55 kkz 1.1.2.1 import harpoon.Util.Worklist;
56 kkz 1.1.2.1
57 kkz 1.1.2.1 import java.util.Collections;
58 kkz 1.1.2.1 import java.util.HashMap;
59 kkz 1.1.2.1 import java.util.HashSet;
60 kkz 1.1.2.1 import java.util.Iterator;
61 kkz 1.1.2.1 import java.util.List;
62 kkz 1.1.2.1 import java.util.Map;
63 kkz 1.1.2.1 import java.util.Set;
64 kkz 1.1.2.1
65 kkz 1.1.2.1 /**
66 kkz 1.1.2.1 * <code>MRAFactory</code> generates <code>MRA</code>s.
67 kkz 1.1.2.1 *
68 kkz 1.1.2.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
69 cananian 1.9 * @version $Id: MRAFactory.java,v 1.9 2004/02/08 03:20:07 cananian Exp $
70 kkz 1.1.2.1 */
71 kkz 1.1.2.1 public class MRAFactory {
72 kkz 1.1.2.1
73 kkz 1.7 //private static int iterations = 0;
74 kkz 1.7 //private static long time = 0;
75 kkz 1.7
76 kkz 1.1.2.1 private final ClassHierarchy ch;
77 kkz 1.7 private CallGraph cg;
78 kkz 1.1.2.4 private final HCodeFactory hcf;
79 kkz 1.1.2.5 private final Map method2types;
80 kkz 1.1.2.5 private Set safeMethods;
81 kkz 1.1.2.1 private final CFGrapher cfger;
82 kkz 1.1.2.1 private final UseDefer ud;
83 kkz 1.1.2.1 private final Map cache;
84 kkz 1.1.2.1
85 kkz 1.7 /** Creates an <code>MRAFactory</code>. Requires a
86 kkz 1.7 * quad-ssa or quad-ssi codefactory. If the code is
87 kkz 1.1.2.1 * modified, a new <code>MRAFactory</code> is needed.
88 kkz 1.1.2.4 * For efficiency reasons, <code>hcf</code> should be
89 kkz 1.1.2.4 * a <code>CachingCodeFactory</code>.
90 kkz 1.1.2.1 */
91 kkz 1.1.2.2 public MRAFactory(ClassHierarchy ch, HCodeFactory hcf, Linker l,
92 kkz 1.1.2.5 String rName, int optLevel) {
93 kkz 1.7 // check that the codefactory produces the right type of code
94 kkz 1.7 /*
95 kkz 1.7 assert
96 kkz 1.7 hcf.getCodeName().equals("quad-ssi") ||
97 kkz 1.7 hcf.getCodeName().equals("quad-ssa") :
98 kkz 1.7 "MRAFactory requires quad-ssi or quad-ssa";
99 kkz 1.7 */
100 kkz 1.1.2.1 this.ch = ch;
101 kkz 1.1.2.4 this.hcf = hcf;
102 kkz 1.7 this.cg = new CachingCallGraph(new CallGraphImpl(ch, hcf));
103 kkz 1.1.2.1 this.cfger = CFGrapher.DEFAULT;
104 kkz 1.1.2.1 this.ud = UseDefer.DEFAULT;
105 kkz 1.1.2.1 this.cache = new HashMap();
106 kkz 1.7 /*
107 kkz 1.7 System.out.print("\nMethod->Types timing: ");
108 kkz 1.7 long start_time = System.currentTimeMillis();
109 kkz 1.7 */
110 kkz 1.1.2.5 this.method2types =
111 kkz 1.1.2.5 (optLevel == 2 || optLevel == 3)? dynamicDispatchM2TMap(l, rName):
112 kkz 1.5 (optLevel == 4 || optLevel == 5)? createMethod2TypesMap(l, rName):
113 kkz 1.7 Default.EMPTY_MAP;
114 kkz 1.7 /*
115 kkz 1.7 System.out.println(System.currentTimeMillis() - start_time);
116 kkz 1.7 System.out.print("Safe methods timing: ");
117 kkz 1.7 start_time = System.currentTimeMillis();
118 kkz 1.7 */
119 kkz 1.5 if (optLevel == 2 || optLevel == 4 || optLevel == 6)
120 kkz 1.1.2.5 findSafeMethods();
121 kkz 1.1.2.5 else
122 kkz 1.1.2.5 safeMethods = Collections.EMPTY_SET;
123 kkz 1.7 /*
124 kkz 1.7 System.out.println(System.currentTimeMillis() - start_time + " ms");
125 kkz 1.7 System.out.println(MRAFactory.iterations + " iterations");
126 kkz 1.7 System.out.print("Analysis timing: ");
127 kkz 1.7 int numMethods = 0;
128 kkz 1.7 start_time = System.currentTimeMillis();
129 kkz 1.7 */
130 kkz 1.7 // for timing reasons, force analysis to run
131 kkz 1.7 for(Iterator it = ch.callableMethods().iterator(); it.hasNext(); )
132 kkz 1.7 {
133 kkz 1.7 Code c = (Code) hcf.convert((HMethod)it.next());
134 kkz 1.7 if (c != null) {
135 kkz 1.7 mra(c);
136 kkz 1.7 //numMethods++;
137 kkz 1.7 }
138 kkz 1.7 }
139 kkz 1.7 /*
140 kkz 1.7 System.out.println(System.currentTimeMillis() - start_time + " ms");
141 kkz 1.7 System.out.println(MRAFactory.iterations + " iterations");
142 kkz 1.7 System.out.println(numMethods + " methods");
143 kkz 1.7 System.out.println("getPre outer loop: " + MRAFactory.time + " ms");
144 kkz 1.7 */
145 kkz 1.7 this.cg = null; /* allow GC */
146 kkz 1.1.2.1 }
147 kkz 1.1.2.1
148 kkz 1.1.2.1 /** Returns an <code>MRA</code>. */
149 kkz 1.1.2.1 public MRA mra(Code c) {
150 kkz 1.1.2.1 // check cache first
151 kkz 1.1.2.1 HMethod hm = c.getMethod();
152 kkz 1.1.2.1 MRA mra = (MRA) cache.get(c);
153 kkz 1.1.2.1 if (mra == null) {
154 kkz 1.1.2.1 mra = new MRAImpl(c);
155 kkz 1.1.2.1 cache.put(c, mra);
156 kkz 1.1.2.1 }
157 kkz 1.1.2.1 return mra;
158 kkz 1.1.2.1 }
159 kkz 1.1.2.1
160 kkz 1.1.2.4 /**
161 kkz 1.1.2.4 * Removes representation of <code>Code</code>
162 kkz 1.1.2.4 * <code>c</code> from this factory.
163 kkz 1.1.2.4 */
164 kkz 1.1.2.4 public void clear(Code c) {
165 kkz 1.1.2.4 Object o = cache.remove(c);
166 cananian 1.3.2.1 assert (o != null) : "Failed to remove "+c.getMethod();
167 kkz 1.1.2.4 }
168 kkz 1.1.2.4
169 kkz 1.1.2.5 /** Checks whether a method is "safe" (i.e. whether all
170 kkz 1.1.2.5 * calls to a method occurs when the receiver object is
171 kkz 1.1.2.5 * the most recently allocated object.)
172 kkz 1.1.2.2 */
173 kkz 1.1.2.5 public boolean isSafeMethod(HMethod hm) {
174 kkz 1.1.2.5 return safeMethods.contains(hm);
175 kkz 1.1.2.2 }
176 kkz 1.1.2.2
177 kkz 1.1.2.5 /** Checks whether the types that the <code>HMethod</code>
178 kkz 1.1.2.5 * may allocate are known.
179 kkz 1.1.2.4 */
180 kkz 1.1.2.5 public boolean allocatedTypesKnown(HMethod hm) {
181 kkz 1.1.2.5 return method2types.containsKey(hm);
182 kkz 1.1.2.4 }
183 kkz 1.1.2.4
184 kkz 1.1.2.4 /** Returns an unmodifiable <code>Set</code> of
185 kkz 1.1.2.4 * <code>HClass</code>es. The presence of an
186 kkz 1.1.2.4 * <code>HClass</code> in the <code>Set</code> indicates
187 kkz 1.1.2.4 * that the given <code>HMethod</code> may allocate,
188 kkz 1.1.2.4 * either directly or through calls, objects of that type.
189 kkz 1.1.2.4 */
190 kkz 1.1.2.5 public Set getAllocatedTypes(HMethod hm) {
191 kkz 1.1.2.5 return (Set) method2types.get(hm);
192 kkz 1.1.2.1 }
193 kkz 1.1.2.1
194 kkz 1.7 private Map tryDDMethod2TypesMap(Linker linker, String resourceName) {
195 kkz 1.7 // start w/ an empty map
196 kkz 1.7 Map safe = new HashMap();
197 kkz 1.7 // add known native methods
198 kkz 1.7 for (Iterator it = parseResource(linker, resourceName).iterator();
199 kkz 1.7 it.hasNext(); )
200 kkz 1.7 safe.put((HMethod)it.next(), Collections.EMPTY_SET);
201 kkz 1.7 // add leaves of call graph
202 kkz 1.7 QuadVisitor qv = new QuadVisitor() {
203 kkz 1.7 Set types = new HashSet();
204 kkz 1.7
205 kkz 1.7 public void visit(ANEW q) { types.add(q.hclass()); }
206 kkz 1.7 public void visit(NEW q) { types.add(q.hclass()); }
207 kkz 1.7 public void visit(MONITORENTER q) { assert false:
208 kkz 1.7 "should not contain " + q; }
209 kkz 1.7 public void visit(Quad q) { /* do nothing */ }
210 kkz 1.7 };
211 kkz 1.7 return safe;
212 kkz 1.7 }
213 kkz 1.7
214 kkz 1.1.2.2 /** Creates a <code>Map</code> of <code>HMethod</code>s
215 kkz 1.1.2.2 * to the <code>Set</code> of <code>Classes</code>
216 kkz 1.1.2.2 * whose objects may be allocated by the method either
217 kkz 1.1.2.2 * directly or indirectly through calling other methods.
218 kkz 1.1.2.5 * Handles dynamically-dispatched calls by conservative
219 kkz 1.1.2.5 * approximation.
220 kkz 1.1.2.5 */
221 kkz 1.1.2.5 private Map dynamicDispatchM2TMap(Linker linker, String resourceName) {
222 kkz 1.1.2.5 // start with an empty map
223 kkz 1.1.2.5 Map safe = new HashMap();
224 kkz 1.1.2.5 // add methods unless we have no information about them
225 cananian 1.9 for (Object hmO : ch.callableMethods()) {
226 cananian 1.9 HMethod hm = (HMethod) hmO;
227 kkz 1.1.2.5 Code c = (Code) hcf.convert(hm);
228 kkz 1.1.2.5 if (c != null) {
229 kkz 1.1.2.5 Set cls = new HashSet();
230 kkz 1.1.2.5 safe.put(hm, cls);
231 kkz 1.1.2.5 for (Iterator stms = c.getElementsI(); stms.hasNext(); ) {
232 kkz 1.1.2.5 Quad q = (Quad) stms.next();
233 kkz 1.1.2.5 int kind = q.kind();
234 kkz 1.1.2.5 if (kind == QuadKind.ANEW) {
235 kkz 1.1.2.5 cls.add(((ANEW)q).hclass());
236 kkz 1.1.2.5 } else if (kind == QuadKind.NEW) {
237 kkz 1.1.2.5 cls.add(((NEW)q).hclass());
238 kkz 1.5 } else if (kind == QuadKind.MONITORENTER) {
239 kkz 1.5 // for race-free multi-threaded programs
240 kkz 1.5 safe.remove(hm);
241 kkz 1.5 break;
242 kkz 1.1.2.5 }
243 kkz 1.1.2.5 }
244 kkz 1.1.2.5 }
245 kkz 1.1.2.5 }
246 kkz 1.1.2.5 // add known native methods
247 kkz 1.1.2.5 for (Iterator it = parseResource(linker, resourceName).iterator();
248 kkz 1.1.2.5 it.hasNext(); ) {
249 kkz 1.1.2.5 safe.put((HMethod)it.next(), Collections.EMPTY_SET);
250 kkz 1.1.2.5 }
251 kkz 1.1.2.5 // save results
252 kkz 1.1.2.5 safe = Collections.unmodifiableMap(safe);
253 kkz 1.1.2.5 // start with the map so far
254 kkz 1.1.2.5 Map safer = new HashMap(safe);
255 kkz 1.1.2.5 // iterate until fixed point to remove any that
256 kkz 1.1.2.5 // are unsafe by calling unsafe methods
257 kkz 1.1.2.5 while(true) {
258 kkz 1.1.2.5 boolean changed = false;
259 kkz 1.1.2.5 boolean done = false;
260 cananian 1.9 for (Object hmO : safe.keySet()) {
261 cananian 1.9 HMethod hm = (HMethod) hmO;
262 kkz 1.1.2.5 // get all the call sites in hm
263 kkz 1.1.2.5 CALL[] calls = cg.getCallSites(hm);
264 kkz 1.1.2.5 for (int i = 0; i < calls.length; i++) {
265 kkz 1.1.2.5 // there are multiple possible callees here
266 kkz 1.1.2.5 HMethod[] callees = cg.calls(hm, calls[i]);
267 kkz 1.1.2.5 for(int j = 0; j < callees.length && !done; j++) {
268 kkz 1.1.2.5 HMethod callee = callees[j];
269 kkz 1.1.2.5 if (!safe.containsKey(callee)) {
270 kkz 1.1.2.5 // if the method being called isn't in the
271 kkz 1.1.2.5 // safe set, then the caller is also unsafe
272 kkz 1.1.2.5 safer.remove(hm);
273 kkz 1.1.2.5 changed = true;
274 kkz 1.1.2.5 done = true; // done with this method
275 kkz 1.1.2.5 break;
276 kkz 1.1.2.5 } else {
277 kkz 1.1.2.5 // if the method being called is safe, then
278 kkz 1.1.2.5 // add its classes to the set of known classes
279 kkz 1.1.2.5 // being allocated
280 kkz 1.1.2.5 if (((Set)safer.get(hm)).addAll
281 kkz 1.1.2.5 ((Set)safe.get(callee)))
282 kkz 1.1.2.5 changed = true;
283 kkz 1.1.2.5 }
284 kkz 1.1.2.5 }
285 kkz 1.1.2.5 }
286 kkz 1.1.2.5 }
287 kkz 1.1.2.5 if (changed) {
288 kkz 1.1.2.5 // should be monotonic
289 cananian 1.3.2.1 assert safer.size() <= safe.size();
290 kkz 1.1.2.5 safe = Collections.unmodifiableMap(safer);
291 kkz 1.1.2.5 safer = new HashMap(safe);
292 kkz 1.1.2.5 } else {
293 kkz 1.1.2.5 // reached fix point
294 cananian 1.3.2.1 assert safer.size() == safe.size();
295 kkz 1.1.2.5 break;
296 kkz 1.1.2.5 }
297 kkz 1.1.2.5 }
298 kkz 1.1.2.5 // get a safe view of the keys
299 kkz 1.1.2.5 Set keys = Collections.unmodifiableSet(new HashSet(safer.keySet()));
300 kkz 1.1.2.5 // save results
301 cananian 1.9 for (Object hmO : keys) {
302 cananian 1.9 HMethod hm = (HMethod) hmO;
303 kkz 1.1.2.5 safer.put(hm, Collections.unmodifiableSet((Set)safer.get(hm)));
304 kkz 1.1.2.5 }
305 kkz 1.1.2.5 return Collections.unmodifiableMap(safer);
306 kkz 1.1.2.5 }
307 kkz 1.1.2.5
308 kkz 1.1.2.5 /** Creates a <code>Map</code> of <code>HMethod</code>s
309 kkz 1.1.2.5 * to the <code>Set</code> of <code>Classes</code>
310 kkz 1.1.2.5 * whose objects may be allocated by the method either
311 kkz 1.1.2.5 * directly or indirectly through calling other methods.
312 kkz 1.1.2.2 * <code>HMethods</code> that do not allocate any
313 kkz 1.1.2.2 * objects map to the empty set, while
314 kkz 1.1.2.2 * <code>HMethod</code>s that are entirely unsafe due
315 kkz 1.1.2.2 * to the presence of virtually-dispatched calls will
316 kkz 1.1.2.2 * be absent from the map (i.e. map to null).
317 kkz 1.1.2.1 */
318 kkz 1.1.2.5 private Map createMethod2TypesMap(Linker linker, String resourceName) {
319 kkz 1.1.2.4 // start with an empty map
320 kkz 1.1.2.4 Map safe = new HashMap();
321 kkz 1.1.2.4 // add methods unless we know they are unsafe because of
322 kkz 1.1.2.4 // dynamic dispatch or if we have no information because
323 kkz 1.1.2.4 // it is native or abstract
324 cananian 1.9 for (Object hmO : ch.callableMethods()) {
325 cananian 1.9 HMethod hm = (HMethod) hmO;
326 kkz 1.1.2.4 Code c = (Code) hcf.convert(hm);
327 kkz 1.1.2.2 if (c != null) {
328 kkz 1.1.2.4 Set cls = new HashSet();
329 kkz 1.1.2.4 safe.put(hm, cls);
330 kkz 1.1.2.2 for (Iterator stms = c.getElementsI(); stms.hasNext(); ) {
331 kkz 1.1.2.2 Quad q = (Quad) stms.next();
332 kkz 1.1.2.4 int kind = q.kind();
333 kkz 1.5 if ((kind == QuadKind.CALL && ((CALL)q).isVirtual()) ||
334 kkz 1.5 kind == QuadKind.MONITORENTER) {
335 kkz 1.5 // remove if unsafe due to dynamic dispatch or
336 kkz 1.5 // if unsafe due to interthread interactions
337 kkz 1.1.2.4 safe.remove(hm);
338 kkz 1.1.2.2 break;
339 kkz 1.1.2.4 } else if (kind == QuadKind.ANEW) {
340 kkz 1.1.2.4 cls.add(((ANEW)q).hclass());
341 kkz 1.1.2.4 } else if (kind == QuadKind.NEW) {
342 kkz 1.1.2.4 cls.add(((NEW)q).hclass());
343 kkz 1.1.2.2 }
344 kkz 1.1.2.1 }
345 kkz 1.1.2.1 }
346 kkz 1.1.2.1 }
347 kkz 1.1.2.4 // add known native methods
348 kkz 1.1.2.4 for (Iterator it = parseResource(linker, resourceName).iterator();
349 kkz 1.1.2.4 it.hasNext(); ) {
350 kkz 1.1.2.4 safe.put((HMethod)it.next(), Collections.EMPTY_SET);
351 kkz 1.1.2.4 }
352 kkz 1.1.2.4 // save results
353 kkz 1.1.2.4 safe = Collections.unmodifiableMap(safe);
354 kkz 1.1.2.4 // start with the map so far
355 kkz 1.1.2.4 Map safer = new HashMap(safe);
356 kkz 1.1.2.4 // iterate until fixed point to remove any that
357 kkz 1.1.2.4 // are unsafe by calling unsafe methods
358 kkz 1.1.2.4 while(true) {
359 kkz 1.1.2.4 boolean changed = false;
360 cananian 1.9 for (Object hmO : safe.keySet()) {
361 cananian 1.9 HMethod hm = (HMethod) hmO;
362 kkz 1.1.2.4 CALL[] calls = cg.getCallSites(hm);
363 kkz 1.1.2.4 for (int i = 0; i < calls.length; i++) {
364 kkz 1.1.2.4 HMethod callee = calls[i].method();
365 kkz 1.1.2.4 if (!safe.containsKey(callee)) {
366 kkz 1.1.2.4 // if the method being called isn't in the safe set,
367 kkz 1.1.2.4 // then the caller is also unsafe
368 kkz 1.1.2.4 safer.remove(hm);
369 kkz 1.1.2.4 changed = true;
370 kkz 1.1.2.4 break;
371 kkz 1.1.2.4 } else {
372 kkz 1.1.2.4 // if the method being called is safe, then add its
373 kkz 1.1.2.4 // classes to the set of known classes being allocated
374 kkz 1.1.2.4 if (((Set)safer.get(hm)).addAll((Set)safe.get(callee)))
375 kkz 1.1.2.4 changed = true;
376 kkz 1.1.2.4 }
377 kkz 1.1.2.4 }
378 kkz 1.1.2.4 }
379 kkz 1.1.2.4 if (changed) {
380 kkz 1.1.2.4 // should be monotonic
381 cananian 1.3.2.1 assert safer.size() < safe.size();
382 kkz 1.1.2.4 safe = Collections.unmodifiableMap(safer);
383 kkz 1.1.2.4 safer = new HashMap(safe);
384 kkz 1.1.2.4 } else {
385 kkz 1.1.2.4 // reached fix point
386 cananian 1.3.2.1 assert safer.size() == safe.size();
387 kkz 1.1.2.4 break;
388 kkz 1.1.2.4 }
389 kkz 1.1.2.4 }
390 kkz 1.1.2.4 // get a safe view of the keys
391 kkz 1.1.2.4 Set keys = Collections.unmodifiableSet(new HashSet(safer.keySet()));
392 kkz 1.1.2.4 // save results
393 cananian 1.9 for (Object hmO : keys) {
394 cananian 1.9 HMethod hm = (HMethod) hmO;
395 kkz 1.1.2.4 safer.put(hm, Collections.unmodifiableSet((Set)safer.get(hm)));
396 kkz 1.1.2.4 }
397 kkz 1.1.2.4 return Collections.unmodifiableMap(safer);
398 kkz 1.1.2.4 }
399 kkz 1.1.2.4
400 kkz 1.1.2.5 /** Calculates the <code>Set</code> of safe methods;
401 kkz 1.1.2.5 * a safe method is one where the receiver object
402 kkz 1.1.2.5 * is the most recently allocated object for all
403 kkz 1.1.2.5 * calls of that method in the program.
404 kkz 1.1.2.4 */
405 kkz 1.1.2.5 private void findSafeMethods() {
406 kkz 1.1.2.5 // start with the set of all analyzable methods
407 kkz 1.1.2.5 Set methods = new HashSet();
408 cananian 1.9 for (Object hmO : ch.callableMethods()) {
409 cananian 1.9 HMethod hm = (HMethod) hmO;
410 kkz 1.1.2.4 if (!hm.isStatic() && !hm.isInterfaceMethod()) {
411 kkz 1.1.2.4 Code c = (Code) hcf.convert(hm);
412 kkz 1.1.2.4 if (c != null)
413 kkz 1.1.2.5 methods.add(hm);
414 kkz 1.1.2.4 }
415 kkz 1.1.2.4 }
416 kkz 1.1.2.5 // assume that they are all safe
417 kkz 1.1.2.5 safeMethods = Collections.unmodifiableSet(methods);
418 kkz 1.1.2.4 // Start with the set of initializers and remove
419 kkz 1.1.2.4 // any that get called when the receiver is not
420 kkz 1.1.2.4 // mra. Iterate until a fixed-point is reached.
421 kkz 1.1.2.1 while (true) {
422 kkz 1.1.2.5 Set safe = new HashSet(safeMethods);
423 cananian 1.9 for (Object hmO : ch.callableMethods()) {
424 cananian 1.9 HMethod hm = (HMethod) hmO;
425 kkz 1.1.2.4 Code c = (Code) hcf.convert(hm);
426 kkz 1.1.2.4 if (c != null) {
427 kkz 1.1.2.4 MRA mra = mra(c);
428 kkz 1.1.2.4 CALL[] calls = cg.getCallSites(hm);
429 kkz 1.1.2.4 for(int i = 0; i < calls.length; i++) {
430 kkz 1.1.2.4 CALL call = calls[i];
431 kkz 1.1.2.4 // consider only initializers that
432 kkz 1.1.2.4 // have not been eliminated
433 kkz 1.1.2.4 if (safe.contains(call.method())) {
434 kkz 1.1.2.4 Tuple mra_before = mra.mra_before(call);
435 kkz 1.1.2.4 Map m = (Map) mra_before.proj(0);
436 kkz 1.1.2.4 Set s = (Set) mra_before.proj(1);
437 kkz 1.1.2.4 if (!m.containsKey(call.params(0)) ||
438 kkz 1.1.2.5 !s.isEmpty()) {
439 kkz 1.1.2.5 // if the receiver is not the MRA
440 kkz 1.1.2.5 // object, or if there are exceptions,
441 kkz 1.1.2.5 // then the called method is not safe
442 kkz 1.1.2.5 if (call.isVirtual()) {
443 kkz 1.1.2.5 // if the call is virtual, none
444 kkz 1.1.2.5 // of the other methods callable
445 kkz 1.1.2.5 // at this site are safe, either
446 kkz 1.1.2.5 HMethod[] cms = cg.calls(hm, call);
447 kkz 1.1.2.5 for(int j = 0; j < cms.length; j++)
448 kkz 1.1.2.5 safe.remove(cms[j]);
449 kkz 1.1.2.5 } else {
450 kkz 1.1.2.5 // if the call is not virtual, the
451 kkz 1.1.2.5 // exact called method is removed
452 kkz 1.1.2.5 safe.remove(call.method());
453 kkz 1.1.2.5 }
454 kkz 1.1.2.1 }
455 kkz 1.1.2.1 }
456 kkz 1.1.2.1 }
457 kkz 1.1.2.1 }
458 kkz 1.1.2.4 }
459 kkz 1.1.2.4 // save results
460 kkz 1.1.2.4 safe = Collections.unmodifiableSet(safe);
461 kkz 1.1.2.5 // newly-removed safe initializers must be re-analyzed
462 cananian 1.9 for (Object hmO : safeMethods) {
463 cananian 1.9 HMethod hm = (HMethod) hmO;
464 kkz 1.1.2.5 if (!safe.contains(hm)) {
465 kkz 1.1.2.4 Code c = (Code) hcf.convert(hm);
466 cananian 1.3.2.1 assert c != null;
467 kkz 1.1.2.4 clear(c);
468 kkz 1.1.2.1 }
469 kkz 1.1.2.1 }
470 kkz 1.1.2.5 if (safeMethods.size() == safe.size()) {
471 kkz 1.1.2.4 // reached fix-point
472 kkz 1.1.2.5 safeMethods = safe;
473 kkz 1.1.2.4 break;
474 kkz 1.1.2.1 } else {
475 kkz 1.1.2.5 // continue, size of set must be decreasing
476 cananian 1.3.2.1 assert safeMethods.size() > safe.size();
477 kkz 1.1.2.5 safeMethods = safe;
478 kkz 1.1.2.1 }
479 kkz 1.1.2.1 }
480 kkz 1.1.2.1 }
481 kkz 1.1.2.1
482 kkz 1.1.2.1 /** Implementation of <code>MRA</code> analysis. */
483 kkz 1.1.2.2 private class MRAImpl extends MRA {
484 kkz 1.1.2.1
485 kkz 1.1.2.1 private boolean DEBUG = false;
486 kkz 1.1.2.1 private final Code code;
487 kkz 1.1.2.5 private final boolean isSafeMethod;
488 kkz 1.1.2.1 private final BasicBlock.Factory bbf;
489 kkz 1.1.2.1 private final Map bb2pre;
490 kkz 1.1.2.1 private Map bb2post;
491 kkz 1.1.2.1
492 kkz 1.1.2.1 /** Creates a new <code>MRA</code>. Performs analysis.
493 kkz 1.1.2.1 * If the code is modified, then a new MRA needs to be
494 kkz 1.1.2.1 * created.
495 kkz 1.1.2.1 */
496 kkz 1.1.2.1 private MRAImpl(Code c) {
497 kkz 1.1.2.1 this.code = c;
498 kkz 1.1.2.5 this.isSafeMethod = isSafeMethod(code.getMethod());
499 kkz 1.1.2.1 this.bbf = new BasicBlock.Factory(code, cfger);
500 kkz 1.1.2.1 this.bb2pre = new HashMap();
501 kkz 1.1.2.1 this.bb2post = new HashMap();
502 kkz 1.1.2.1 analyze();
503 kkz 1.1.2.1 // after analysis, we can get rid of the post map
504 kkz 1.1.2.1 this.bb2post = null;
505 kkz 1.1.2.1 }
506 kkz 1.1.2.1
507 kkz 1.1.2.4 private Map results = new HashMap();
508 kkz 1.1.2.4
509 kkz 1.1.2.4 /** Returns a <code>Tuple</code> that characterizes
510 kkz 1.1.2.4 * the state before the given <code>Quad</code>.
511 kkz 1.1.2.1 */
512 kkz 1.1.2.4 public Tuple mra_before(Quad q) {
513 kkz 1.1.2.4 // first, check our cache
514 kkz 1.1.2.4 Tuple t = (Tuple) results.get(q);
515 kkz 1.1.2.4 if (t != null) return t;
516 kkz 1.1.2.4 // if not in cache, then calculate
517 kkz 1.1.2.1 BasicBlock bb = bbf.getBlock(q);
518 cananian 1.3.2.1 assert bb != null;
519 kkz 1.1.2.4 Tuple pre = (Tuple) bb2pre.get(bb);
520 cananian 1.3.2.1 assert pre != null;
521 kkz 1.1.2.4 Tuple post = new Tuple(new Object[]
522 kkz 1.1.2.4 { new HashMap((Map)pre.proj(0)),
523 kkz 1.1.2.4 new HashSet((Set)pre.proj(1)),
524 kkz 1.1.2.4 (Quad)pre.proj(2),
525 kkz 1.1.2.4 new HashSet((Set)pre.proj(3)) });
526 cananian 1.9 for(Object currO : bb.statements()) {
527 cananian 1.9 Quad curr = (Quad) currO;
528 kkz 1.1.2.1 if (q.equals(curr))
529 kkz 1.1.2.1 break;
530 kkz 1.1.2.1 // PHIs and LABELs (which are also PHIs) are
531 kkz 1.1.2.1 // handled specially. so are CJMPs, SWITCHs and
532 kkz 1.1.2.1 // TYPESWITCHs, which are actually SIGMAs.
533 kkz 1.1.2.1 // CALLs are SIGMAs, but the "call" part is
534 kkz 1.1.2.1 // handled separately from the "sigma" part
535 kkz 1.1.2.1 if (curr.kind() != QuadKind.PHI &&
536 kkz 1.1.2.1 curr.kind() != QuadKind.LABEL &&
537 kkz 1.1.2.1 curr.kind() != QuadKind.CJMP &&
538 kkz 1.1.2.1 curr.kind() != QuadKind.SWITCH &&
539 kkz 1.1.2.1 curr.kind() != QuadKind.TYPESWITCH)
540 kkz 1.1.2.4 post = transfer(curr, post);
541 kkz 1.1.2.1 else if (DEBUG)
542 kkz 1.1.2.1 System.out.println(q);
543 kkz 1.1.2.1 }
544 kkz 1.1.2.4 t = new Tuple
545 kkz 1.1.2.4 (new Object[]
546 kkz 1.1.2.4 { Collections.unmodifiableMap((Map)post.proj(0)),
547 kkz 1.1.2.4 Collections.unmodifiableSet((Set)post.proj(1)),
548 kkz 1.1.2.4 (Quad)post.proj(2),
549 kkz 1.1.2.4 Collections.unmodifiableSet((Set)post.proj(3)) });
550 kkz 1.1.2.4 results.put(q, t);
551 kkz 1.1.2.4 return t;
552 kkz 1.1.2.1 }
553 kkz 1.1.2.1
554 kkz 1.1.2.1
555 kkz 1.1.2.4 /** Performs analysis. This may take a while.
556 kkz 1.1.2.4 */
557 kkz 1.1.2.1 private void analyze() {
558 kkz 1.1.2.1 // create universe
559 kkz 1.1.2.4 Set temps = new HashSet();
560 kkz 1.1.2.1 for(Iterator it = code.getElementsI(); it.hasNext(); ) {
561 kkz 1.1.2.1 Quad q = (Quad) it.next();
562 kkz 1.1.2.4 temps.addAll(ud.useC(q));
563 kkz 1.1.2.4 temps.addAll(ud.defC(q));
564 kkz 1.1.2.4 }
565 kkz 1.7 // save results
566 kkz 1.1.2.4 temps = Collections.unmodifiableSet(temps);
567 kkz 1.1.2.4 // maps Temps to an array of 2 booleans
568 kkz 1.1.2.4 // the first boolean is true iff
569 kkz 1.1.2.4 // the method is an initializer and
570 kkz 1.1.2.4 // the given Temp points to the
571 kkz 1.1.2.4 // receiver object
572 kkz 1.1.2.4 // the second boolean is true iff
573 kkz 1.1.2.4 // the given Temp succeeded the receiver
574 kkz 1.1.2.4 // as the most-recently-allocated object
575 kkz 1.1.2.4 Map universe = new HashMap();
576 kkz 1.1.2.4 for(Iterator it = temps.iterator(); it.hasNext(); ) {
577 kkz 1.1.2.4 universe.put((Temp)it.next(), MRA.MRAToken.TOP);
578 kkz 1.1.2.1 }
579 kkz 1.1.2.4 universe = Collections.unmodifiableMap(universe);
580 kkz 1.1.2.1 // initialize the maps
581 kkz 1.1.2.1 for(Iterator it = bbf.blocksIterator(); it.hasNext(); )
582 kkz 1.1.2.2 bb2post.put((BasicBlock)it.next(),
583 kkz 1.1.2.4 new Tuple(new Object[] { universe,
584 kkz 1.1.2.4 Collections.EMPTY_SET,
585 kkz 1.1.2.4 null,
586 kkz 1.1.2.4 temps }));
587 kkz 1.1.2.1 // initialize worklist
588 kkz 1.1.2.1 Worklist toprocess = new WorkSet();
589 kkz 1.1.2.1 toprocess.push((BasicBlock)bbf.getRoot());
590 kkz 1.1.2.1 // keep going until we reached a fixed point
591 kkz 1.1.2.1 while(!toprocess.isEmpty()) {
592 kkz 1.7 //MRAFactory.iterations++;
593 kkz 1.1.2.1 BasicBlock bb = (BasicBlock)toprocess.pull();
594 kkz 1.1.2.1 // construct the pre-Set
595 kkz 1.1.2.4 Tuple pre = getPre(bb);
596 kkz 1.1.2.1 // add the unmodifiable original to the map
597 kkz 1.1.2.1 bb2pre.put(bb, pre);
598 kkz 1.1.2.4 // make a copy to modify
599 kkz 1.1.2.4 Tuple tup = new Tuple
600 kkz 1.1.2.4 (new Object[] { new HashMap((Map)pre.proj(0)),
601 kkz 1.1.2.4 new HashSet((Set)pre.proj(1)),
602 kkz 1.1.2.4 (Quad)pre.proj(2),
603 kkz 1.1.2.4 new HashSet((Set)pre.proj(3)) });
604 cananian 1.9 for(Object qO : bb.statements()) {
605 cananian 1.9 Quad q = (Quad) qO;
606 kkz 1.1.2.4 // PHIs (which include LABELs) are handled implicitly
607 kkz 1.1.2.4 // in the call to getPre(). SIGMAs (which include
608 kkz 1.1.2.4 // CALLs, CJMPs, SWITCHes and TYPESWITCHes) are also
609 kkz 1.1.2.4 // handled implicitly in the call to getPre(), which
610 kkz 1.1.2.4 // calls getPost(). CALLs are handled twice because
611 kkz 1.1.2.4 // they have non-SIGMA defs.
612 kkz 1.1.2.4 int kind = q.kind();
613 kkz 1.1.2.4 if (kind != QuadKind.PHI && kind != QuadKind.LABEL &&
614 kkz 1.1.2.4 kind != QuadKind.CJMP && kind != QuadKind.SWITCH &&
615 kkz 1.1.2.4 kind != QuadKind.TYPESWITCH)
616 kkz 1.1.2.4 tup = transfer(q, tup);
617 kkz 1.1.2.1 else if (DEBUG)
618 kkz 1.1.2.1 System.out.println(q);
619 kkz 1.1.2.1 }
620 kkz 1.1.2.4 Tuple post = (Tuple) bb2post.get(bb);
621 kkz 1.1.2.4 // check for convergence:
622 kkz 1.1.2.4 Set except = (Set) tup.proj(1);
623 kkz 1.1.2.4 if (((Set)tup.proj(1)).size() == ((Set)post.proj(1)).size()) {
624 kkz 1.1.2.4 // exception sets converged, check next:
625 kkz 1.1.2.4 if (((Map)tup.proj(0)).equals((Map)post.proj(0))) {
626 kkz 1.1.2.4 // mra maps converged, check next:
627 kkz 1.1.2.4 Quad q1 = (Quad)tup.proj(2);
628 kkz 1.1.2.4 Quad q2 = (Quad)post.proj(2);
629 kkz 1.1.2.4 if ((q1 == null && q2 == null) ||
630 kkz 1.1.2.4 (q1 != null && q1.equals(q2))) {
631 kkz 1.1.2.4 // all converged, go to next in worklist
632 kkz 1.1.2.4 continue;
633 kkz 1.1.2.4 }
634 kkz 1.1.2.4 }
635 kkz 1.1.2.4 } else {
636 cananian 1.3.2.1 assert ((Set)tup.proj(1)).size() >
637 cananian 1.3.2.1 ((Set)post.proj(1)).size();
638 kkz 1.1.2.1 }
639 kkz 1.1.2.4 // not converged, update map with new values,
640 kkz 1.1.2.4 // and add successors to worklist
641 kkz 1.1.2.4 bb2post.put(bb, new Tuple
642 kkz 1.1.2.4 (new Object[]
643 kkz 1.1.2.4 { Collections.unmodifiableMap((Map)tup.proj(0)),
644 kkz 1.1.2.4 Collections.unmodifiableSet((Set)tup.proj(1)),
645 kkz 1.1.2.4 (Quad)tup.proj(2),
646 kkz 1.1.2.4 Collections.unmodifiableSet((Set)tup.proj(3)) }));
647 kkz 1.1.2.4 for(Iterator it = bb.nextSet().iterator(); it.hasNext(); )
648 kkz 1.1.2.4 toprocess.push((BasicBlock)it.next());
649 kkz 1.1.2.1 }
650 kkz 1.1.2.1 }
651 kkz 1.1.2.1
652 kkz 1.1.2.4 /** Returns a <code>Tuple</code> containing an unmodifiable
653 kkz 1.1.2.4 * <code>Map</code>, an unmodifiable <code>Set</code>, and a
654 kkz 1.1.2.4 * <code>Quad</code> characterizing the state of the
655 kkz 1.1.2.4 * analysis prior to the given <code>Quad</code>.
656 kkz 1.1.2.4 *
657 kkz 1.1.2.4 * Handles complications that arise due to
658 kkz 1.1.2.4 * <code>SIGMA</code>s and <code>PHI</code>s.
659 kkz 1.1.2.4 */
660 kkz 1.1.2.4 private Tuple getPre(BasicBlock bb) {
661 kkz 1.1.2.4 // start from empty maps and sets
662 kkz 1.1.2.4 Map mra = new HashMap();
663 kkz 1.1.2.2 Set except = new HashSet();
664 kkz 1.1.2.4 Set allocs = new HashSet();
665 kkz 1.1.2.4 Set receiver = new HashSet();
666 kkz 1.1.2.4 // look at the first Quad of the BasicBlock
667 kkz 1.1.2.1 Quad q = (Quad) bb.statements().get(0);
668 kkz 1.1.2.1 // PHIs are special
669 kkz 1.1.2.1 if (q.kind() == QuadKind.LABEL ||
670 kkz 1.1.2.1 q.kind() == QuadKind.PHI) {
671 kkz 1.1.2.1 PHI phi = (PHI) q;
672 kkz 1.1.2.1 Quad[] prev = phi.prev();
673 kkz 1.1.2.1 // need to cycle through predecessors
674 kkz 1.1.2.1 for (int i = 0; i < phi.arity(); i++) {
675 kkz 1.1.2.4 Tuple post = getPost(bbf.getBlock(prev[i]), bb);
676 kkz 1.1.2.4 // create a new map since we need to modify it
677 kkz 1.1.2.4 Map pmra = new HashMap((Map) post.proj(0));
678 kkz 1.1.2.4 // create a new set since we need to modify it
679 kkz 1.1.2.4 Set preceiver = new HashSet((Set) post.proj(3));
680 kkz 1.1.2.1 for (int j = 0; j < phi.numPhis(); j++) {
681 kkz 1.1.2.1 Temp src = phi.src(j, i);
682 kkz 1.1.2.1 // substitute srcs for dsts
683 kkz 1.1.2.4 if (pmra.containsKey(src)) {
684 kkz 1.1.2.4 MRA.MRAToken tok = (MRA.MRAToken) pmra.remove(src);
685 cananian 1.3.2.1 assert tok != null;
686 kkz 1.1.2.4 pmra.put(phi.dst(j), tok);
687 kkz 1.1.2.4 }
688 kkz 1.1.2.4 if (preceiver.remove(src)) {
689 kkz 1.1.2.4 preceiver.add(phi.dst(j));
690 kkz 1.1.2.4 }
691 kkz 1.1.2.1 }
692 kkz 1.7 //long start_time = System.currentTimeMillis();
693 kkz 1.7
694 kkz 1.1.2.1 // perform intersection
695 kkz 1.1.2.4 if (i == 0) {
696 kkz 1.1.2.4 mra.putAll(pmra);
697 kkz 1.1.2.4 receiver.addAll(preceiver);
698 kkz 1.1.2.4 } else {
699 kkz 1.7 //long start_time = System.currentTimeMillis();
700 kkz 1.7
701 kkz 1.1.2.4 intersect(mra, pmra);
702 kkz 1.7
703 kkz 1.7 /*
704 kkz 1.7 MRAFactory.time +=
705 kkz 1.7 (System.currentTimeMillis() - start_time);
706 kkz 1.7 */
707 kkz 1.1.2.4 receiver.retainAll(preceiver);
708 kkz 1.1.2.4 }
709 kkz 1.1.2.2 // exceptions are just unioned
710 kkz 1.1.2.4 except.addAll((Set) post.proj(1));
711 kkz 1.1.2.4 // collect all allocations sites
712 kkz 1.1.2.4 allocs.add((Quad) post.proj(2));
713 kkz 1.7
714 kkz 1.7 //MRAFactory.time +=
715 kkz 1.7 // (System.currentTimeMillis() - start_time);
716 kkz 1.1.2.1 }
717 kkz 1.1.2.1 } else {
718 kkz 1.1.2.4 // we may have joins that are not
719 kkz 1.1.2.4 // PHIs or LABELs (FOOTERs), so
720 kkz 1.1.2.4 // perform intersection for mra,
721 kkz 1.1.2.4 // union for exceptions
722 kkz 1.1.2.1 Iterator it = bb.prevSet().iterator();
723 kkz 1.1.2.2 if (it.hasNext()) {
724 kkz 1.1.2.4 Tuple post = getPost((BasicBlock)it.next(), bb);
725 kkz 1.1.2.4 mra.putAll((Map) post.proj(0));
726 kkz 1.1.2.4 except.addAll((Set) post.proj(1));
727 kkz 1.1.2.4 allocs.add((Quad) post.proj(2));
728 kkz 1.1.2.4 receiver.addAll((Set) post.proj(3));
729 kkz 1.1.2.2 }
730 kkz 1.1.2.2 while (it.hasNext()) {
731 kkz 1.1.2.4 Tuple post = getPost((BasicBlock)it.next(), bb);
732 kkz 1.1.2.4 Map pmra = (Map) post.proj(0);
733 kkz 1.1.2.4 intersect(mra, pmra);
734 kkz 1.1.2.4 except.addAll((Set) post.proj(1));
735 kkz 1.1.2.4 allocs.add((Quad) post.proj(2));
736 kkz 1.1.2.4 receiver.retainAll((Set) post.proj(3));
737 kkz 1.1.2.4 }
738 kkz 1.1.2.4 }
739 kkz 1.1.2.4 Quad alloc = null;
740 kkz 1.1.2.4 if (allocs.size() == 1) {
741 kkz 1.1.2.4 alloc = (Quad) allocs.iterator().next();
742 kkz 1.1.2.4 }
743 kkz 1.1.2.4 return new Tuple(new Object[]
744 kkz 1.1.2.4 { Collections.unmodifiableMap(mra),
745 kkz 1.1.2.4 Collections.unmodifiableSet(except),
746 kkz 1.1.2.4 alloc,
747 kkz 1.1.2.4 Collections.unmodifiableSet(receiver) });
748 kkz 1.1.2.1 }
749 kkz 1.1.2.1
750 kkz 1.1.2.2 // Handles the complicated post-Sets that
751 kkz 1.1.2.2 // occur when we have SIGMAs and PHIs.
752 kkz 1.1.2.2 // The successor is needed when bb has
753 kkz 1.1.2.2 // multiple sucessors, because its post-Sets
754 kkz 1.1.2.2 // are different for each successor
755 kkz 1.1.2.2 // returns an array of unmodifiable sets
756 kkz 1.1.2.4 private Tuple getPost(BasicBlock bb, BasicBlock succ) {
757 kkz 1.1.2.1 List stms = bb.statements();
758 kkz 1.1.2.1 Quad q = (Quad) stms.get(stms.size()-1);
759 kkz 1.1.2.1 // SIGMAs are special, but abstract
760 kkz 1.1.2.1 if (q.kind() == QuadKind.CALL ||
761 kkz 1.1.2.1 q.kind() == QuadKind.CJMP ||
762 kkz 1.1.2.1 q.kind() == QuadKind.SWITCH ||
763 kkz 1.1.2.1 q.kind() == QuadKind.TYPESWITCH) {
764 kkz 1.1.2.1 // find our arity
765 kkz 1.1.2.1 SIGMA sigma = (SIGMA) q;
766 kkz 1.1.2.1 int arity = 0;
767 kkz 1.1.2.1 Quad match = (Quad) succ.statements().get(0);
768 kkz 1.1.2.1 Quad[] next = sigma.next();
769 kkz 1.1.2.1 for ( ; arity < sigma.arity(); arity++) {
770 kkz 1.1.2.1 if (match.equals(next[arity])) {
771 kkz 1.1.2.1 // found arity
772 kkz 1.1.2.4 Tuple t = (Tuple) bb2post.get(bb);
773 kkz 1.1.2.4 Map mra = new HashMap((Map)t.proj(0));
774 kkz 1.1.2.4 Set receiver = new HashSet((Set)t.proj(3));
775 kkz 1.1.2.1 for (int i = 0; i < sigma.numSigmas(); i++) {
776 kkz 1.1.2.4 Temp src = sigma.src(i);
777 kkz 1.1.2.4 // exchange dst for src in mra
778 kkz 1.1.2.4 if (mra.containsKey(src)) {
779 kkz 1.1.2.4 MRA.MRAToken tok = (MRA.MRAToken) mra.remove(src);
780 cananian 1.3.2.1 assert tok != null;
781 kkz 1.1.2.4 mra.put(sigma.dst(i, arity), tok);
782 kkz 1.1.2.4 }
783 kkz 1.1.2.4 if (receiver.remove(src)) {
784 kkz 1.1.2.4 receiver.add(sigma.dst(i, arity));
785 kkz 1.1.2.4 }
786 kkz 1.1.2.1 }
787 kkz 1.1.2.1 // make unmodifiable
788 kkz 1.1.2.4 return new Tuple(new Object[]
789 kkz 1.1.2.4 { Collections.unmodifiableMap(mra),
790 kkz 1.1.2.4 (Set)t.proj(1),
791 kkz 1.1.2.4 (Quad)t.proj(2),
792 kkz 1.1.2.4 Collections.unmodifiableSet(receiver) });
793 kkz 1.1.2.1 }
794 kkz 1.1.2.1 }
795 kkz 1.1.2.1 // should never get here
796 kkz 1.1.2.1 throw new Error("Cannot find arity of "+succ+" w.r.t. "+bb);
797 kkz 1.1.2.1 }
798 kkz 1.1.2.1 // otherwise...
799 kkz 1.1.2.4 return (Tuple) bb2post.get(bb);
800 kkz 1.1.2.1 }
801 kkz 1.1.2.1
802 kkz 1.1.2.4 /** Transfer function for the analysis. Returns
803 kkz 1.1.2.4 * a <code>Tuple</code> characterizing the
804 kkz 1.1.2.4 * state after the <code>Quad</code> <code>q</code>.
805 kkz 1.1.2.4 */
806 kkz 1.1.2.4 private Tuple transfer(Quad q, Tuple pre) {
807 kkz 1.1.2.1 if (DEBUG) {
808 kkz 1.1.2.1 System.out.println(q);
809 kkz 1.1.2.4 System.out.print(" "+pre.proj(0));
810 kkz 1.1.2.4 System.out.print(" except for "+pre.proj(1));
811 kkz 1.1.2.4 System.out.print(" allocated at "+pre.proj(2));
812 kkz 1.1.2.1 }
813 kkz 1.1.2.1 int kind = q.kind();
814 kkz 1.1.2.4 Map mra = (Map) pre.proj(0);
815 kkz 1.1.2.4 Set except = (Set) pre.proj(1);
816 kkz 1.1.2.4 Set receiver = (Set) pre.proj(3);
817 kkz 1.1.2.4 if (kind == QuadKind.ANEW ||
818 kkz 1.1.2.4 kind == QuadKind.NEW) {
819 kkz 1.1.2.4 boolean succeeding = false;
820 kkz 1.1.2.5 if (isSafeMethod) {
821 kkz 1.1.2.4 // check if the Temp we def is succeeding the
822 kkz 1.1.2.4 // receiver as the most recently allocated object
823 kkz 1.1.2.4 succeeding = true;
824 kkz 1.1.2.4 for(Iterator it = mra.values().iterator();
825 kkz 1.1.2.4 it.hasNext(); ) {
826 kkz 1.1.2.4 if (((MRA.MRAToken)it.next()) != MRA.MRAToken.RCVR)
827 kkz 1.1.2.4 succeeding = false;
828 kkz 1.1.2.4 }
829 kkz 1.1.2.4 }
830 kkz 1.1.2.4 // the Temp we def is now the mra
831 kkz 1.1.2.2 mra.clear();
832 kkz 1.1.2.4 mra.put(q.def()[0], (succeeding ?
833 kkz 1.1.2.4 MRA.MRAToken.SUCC : MRA.MRAToken.BOTTOM));
834 kkz 1.1.2.4 // there should only be one
835 cananian 1.3.2.1 assert ud.defC(q).size() == 1;
836 kkz 1.1.2.4 // clear exceptions after an allocation
837 kkz 1.1.2.2 except.clear();
838 kkz 1.1.2.4 // remove dst from receiver
839 kkz 1.1.2.4 receiver.remove(q.def()[0]);
840 kkz 1.1.2.4 // make new Tuple, because we are changing the allocation site
841 kkz 1.1.2.4 pre = new Tuple(new Object[] { mra, except, q, receiver });
842 kkz 1.1.2.1 } else if (kind == QuadKind.CALL) {
843 kkz 1.1.2.1 // after a call, we can no longer be
844 kkz 1.1.2.1 // certain of the most recently allocated
845 kkz 1.1.2.1 // object, unless that method has been
846 kkz 1.1.2.1 // pre-approved, in which case only the
847 kkz 1.1.2.1 // return value and exception are toast
848 kkz 1.1.2.1 // the "sigma" part of the call is
849 kkz 1.1.2.1 // handled as part of the control flow
850 kkz 1.1.2.1 CALL call = (CALL) q;
851 kkz 1.1.2.5 if (allocatedTypesKnown(call.method())) {
852 kkz 1.1.2.5 Set exceptions = (Set) getAllocatedTypes(call.method());
853 cananian 1.3.2.1 assert exceptions != null;
854 kkz 1.1.2.2 // need to add exceptions
855 kkz 1.1.2.4 except.addAll(exceptions);
856 kkz 1.1.2.2 // note our defs
857 kkz 1.1.2.2 Temp retval = call.retval();
858 kkz 1.1.2.4 if (retval != null) {
859 kkz 1.1.2.2 mra.remove(retval);
860 kkz 1.1.2.4 receiver.remove(retval);
861 kkz 1.1.2.4 }
862 kkz 1.1.2.2 Temp retex = call.retex();
863 kkz 1.1.2.4 if (retex != null) {
864 kkz 1.1.2.2 mra.remove(retex);
865 kkz 1.1.2.4 receiver.remove(retval);
866 kkz 1.1.2.4 }
867 kkz 1.1.2.1 } else {
868 kkz 1.1.2.2 // not safe, just clear
869 kkz 1.1.2.2 mra.clear();
870 kkz 1.1.2.1 }
871 kkz 1.1.2.1 } else if (kind == QuadKind.MOVE) {
872 kkz 1.1.2.4 // if the src is an mra, then the dst should
873 kkz 1.1.2.4 // be added to the map as a clone of the src
874 kkz 1.1.2.1 MOVE move = (MOVE)q;
875 kkz 1.1.2.4 if (mra.containsKey(move.src())) {
876 kkz 1.1.2.4 MRA.MRAToken token = (MRA.MRAToken) mra.get(move.src());
877 cananian 1.3.2.1 assert token != null;
878 kkz 1.1.2.4 mra.put(move.dst(), token);
879 kkz 1.1.2.4 } else {
880 kkz 1.1.2.2 mra.remove(move.dst());
881 kkz 1.1.2.4 }
882 kkz 1.1.2.4 // keep receiver set updated
883 kkz 1.1.2.4 if (receiver.contains(move.src())) {
884 kkz 1.1.2.4 receiver.add(move.dst());
885 kkz 1.1.2.4 } else {
886 kkz 1.1.2.4 receiver.remove(move.dst());
887 kkz 1.1.2.4 }
888 kkz 1.1.2.1 } else if (kind == QuadKind.METHOD) {
889 cananian 1.3.2.1 assert mra.isEmpty();
890 kkz 1.1.2.5 if (isSafeMethod) {
891 kkz 1.1.2.4 Temp rcvr = ((METHOD) q).params(0);
892 kkz 1.1.2.4 mra.put(rcvr, MRA.MRAToken.RCVR);
893 kkz 1.1.2.4 receiver.add(rcvr);
894 kkz 1.1.2.4 }
895 kkz 1.1.2.1 } else if (kind == QuadKind.AGET ||
896 kkz 1.1.2.1 kind == QuadKind.ALENGTH ||
897 kkz 1.1.2.1 kind == QuadKind.COMPONENTOF ||
898 kkz 1.1.2.1 kind == QuadKind.CONST ||
899 kkz 1.1.2.1 kind == QuadKind.GET ||
900 kkz 1.1.2.1 kind == QuadKind.HANDLER ||
901 kkz 1.1.2.1 kind == QuadKind.INSTANCEOF ||
902 kkz 1.1.2.1 kind == QuadKind.OPER) {
903 kkz 1.1.2.4 // defs of a Temp revoke its mra status
904 kkz 1.1.2.4 mra.remove(q.def()[0]);
905 kkz 1.1.2.4 receiver.remove(q.def()[0]);
906 kkz 1.1.2.4 // should only be one for these Quads
907 cananian 1.3.2.1 assert ud.defC(q).size() == 1;
908 kkz 1.5 } else if (kind == QuadKind.MONITORENTER) {
909 kkz 1.5 // for race-free multi-threaded code
910 kkz 1.5 mra.clear();
911 kkz 1.5 except.clear();
912 kkz 1.1.2.1 } else if (kind == QuadKind.ARRAYINIT ||
913 kkz 1.1.2.1 kind == QuadKind.ASET ||
914 kkz 1.1.2.1 kind == QuadKind.DEBUG ||
915 kkz 1.1.2.1 kind == QuadKind.FOOTER ||
916 kkz 1.1.2.1 kind == QuadKind.HEADER ||
917 kkz 1.1.2.1 kind == QuadKind.MONITOREXIT ||
918 kkz 1.1.2.1 kind == QuadKind.NOP ||
919 kkz 1.1.2.1 kind == QuadKind.RETURN ||
920 kkz 1.1.2.1 kind == QuadKind.SET ||
921 kkz 1.1.2.1 kind == QuadKind.THROW ||
922 kkz 1.1.2.1 kind == QuadKind.TYPECAST) {
923 kkz 1.1.2.1 // Quads with no defs have no effect
924 cananian 1.3.2.1 assert ud.defC(q).size() == 0;
925 kkz 1.1.2.1 } else {
926 kkz 1.1.2.1 // LABELs, PHIs, SIGMAs, SWITCHs, TYPESWITCHs and XIs
927 kkz 1.1.2.1 // are not handled, but there should not be any
928 kkz 1.1.2.1 throw new Error("Unknown QuadKind: "+q.kind()+" for "+q);
929 kkz 1.1.2.1 }
930 kkz 1.1.2.2 if (DEBUG) {
931 kkz 1.1.2.2 System.out.print(" -> ");
932 kkz 1.1.2.4 System.out.println(pre.proj(0)+" except for "+pre.proj(1));
933 kkz 1.1.2.4 }
934 kkz 1.1.2.4 return pre;
935 kkz 1.1.2.4 }
936 kkz 1.1.2.4 }
937 kkz 1.1.2.4
938 kkz 1.1.2.4 /** Requires that m1 and m2 map <code>Temp</code>s to
939 kkz 1.1.2.4 * <code>MRA.MRAToken</code>s.
940 kkz 1.1.2.4 * Modifies m1 such that it is an intersection of m1
941 kkz 1.1.2.4 * and m2 according to the following rules:
942 kkz 1.1.2.4 *
943 kkz 1.1.2.4 * 1. m1 will contain a mapping for a key k iff m1
944 kkz 1.1.2.4 * originally contained a mapping for k and if m2
945 kkz 1.1.2.4 * contains a mapping for k.
946 kkz 1.1.2.4 * 2. The value to which k maps in m1 will be the
947 kkz 1.1.2.4 * join of the value to which k originally mapped
948 kkz 1.1.2.4 * in m1 and the value to which k maps in m2.
949 kkz 1.1.2.4 */
950 kkz 1.1.2.4 private static void intersect(Map m1, Map m2) {
951 kkz 1.1.2.4 // make a copy of the keys before modifying the map
952 kkz 1.1.2.4 Set keySet = new HashSet(m1.keySet());
953 cananian 1.9 for(Object tO : keySet) {
954 cananian 1.9 Temp t = (Temp) tO;
955 kkz 1.1.2.4 if (m2.containsKey(t)) {
956 kkz 1.1.2.4 // both m1 and m2 contain a mapping for t
957 kkz 1.1.2.4 // compute join and put new mapping in m1
958 kkz 1.1.2.4 MRA.MRAToken t1 = (MRA.MRAToken) m1.get(t);
959 kkz 1.1.2.4 MRA.MRAToken t2 = (MRA.MRAToken) m2.get(t);
960 cananian 1.3.2.1 assert t1 != null && t2 != null;
961 kkz 1.1.2.4 m1.put(t, t1.join(t2));
962 kkz 1.1.2.4 } else {
963 kkz 1.1.2.4 // m2 does not contain a mapping for t
964 kkz 1.1.2.4 // therefore, remove mapping from m1
965 kkz 1.7 m1.remove(t);
966 kkz 1.1.2.2 }
967 kkz 1.1.2.2 }
968 kkz 1.1.2.2 }
969 kkz 1.1.2.2
970 kkz 1.1.2.2 private static Set parseResource(final Linker l, String resourceName) {
971 kkz 1.1.2.2 final Set result = new HashSet();
972 kkz 1.1.2.2 try {
973 kkz 1.1.2.2 ParseUtil.readResource(resourceName, new ParseUtil.StringParser() {
974 kkz 1.1.2.2 public void parseString(String s)
975 kkz 1.1.2.2 throws ParseUtil.BadLineException {
976 kkz 1.1.2.2 result.add(ParseUtil.parseMethod(l, s));
977 kkz 1.1.2.2 }
978 kkz 1.1.2.2 });
979 kkz 1.1.2.2 } catch (java.io.IOException ex) {
980 kkz 1.1.2.2 System.err.println("ERROR READING SAFE SET, SKIPPING REST.");
981 kkz 1.1.2.2 System.err.println(ex.toString());
982 kkz 1.1.2.1 }
983 kkz 1.1.2.2 // done.
984 kkz 1.1.2.2 return result;
985 kkz 1.1.2.1 }
986 cananian 1.2 }