1
2
3
4 package joeq.Compiler.Analysis.FlowInsensitive;
5
6 import java.util.Arrays;
7 import java.util.Collection;
8 import java.util.Collections;
9 import java.util.HashMap;
10 import java.util.HashSet;
11 import java.util.Iterator;
12 import java.util.LinkedList;
13 import java.util.Map;
14 import java.util.Set;
15 import java.io.BufferedWriter;
16 import java.io.File;
17 import java.io.FileWriter;
18 import java.io.IOException;
19 import java.io.PrintStream;
20 import java.lang.reflect.Field;
21 import java.math.BigInteger;
22 import joeq.Class.PrimordialClassLoader;
23 import joeq.Class.jq_Class;
24 import joeq.Class.jq_ClassInitializer;
25 import joeq.Class.jq_FakeInstanceMethod;
26 import joeq.Class.jq_Field;
27 import joeq.Class.jq_Member;
28 import joeq.Class.jq_Method;
29 import joeq.Class.jq_NameAndDesc;
30 import joeq.Class.jq_Reference;
31 import joeq.Class.jq_Type;
32 import joeq.Class.jq_Reference.jq_NullType;
33 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.CheckCastNode;
34 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ConcreteObjectNode;
35 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ConcreteTypeNode;
36 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.GlobalNode;
37 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.Node;
38 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.UnknownTypeNode;
39 import joeq.Compiler.Analysis.IPA.ProgramLocation;
40 import joeq.Compiler.Quad.CodeCache;
41 import joeq.Compiler.Quad.LoadedCallGraph;
42 import joeq.Main.HostedVM;
43 import jwutil.collections.IndexMap;
44 import jwutil.collections.Pair;
45 import jwutil.collections.Tuples;
46 import jwutil.collections.TuplesArray;
47 import jwutil.util.Assert;
48
49 /***
50 * SummaryToTuples
51 *
52
53 Definition of domains:
54
55 V: Variables.
56 Corresponds to variable nodes in the program. There are variable nodes
57 for each formal parameter, result of a object creation (new/newarray/etc.),
58 result of a getfield/arrayload, return value at a call site, and thrown
59 exception at a call site. There is also a special type of 'global'
60 variable node that is used when loading or storing to static fields.
61 Primitive type variables are skipped.
62
63 H: Heap.
64 Corresponds to a location on the heap. There is a heap node for each
65 object creation site.
66
67 T: Type.
68 Corresponds to a Java type (class or interface). There is one for every
69 class or interface used in the program.
70
71 F: Field.
72 Corresponds to a field. There is one for each dereferenced field in the
73 program. There is also a special 'array' field for array accesses.
74
75 I: Invocation.
76 Corresponds to a method invocation. There is one for each method
77 invocation in the program. Note that object creation is not a method
78 invocation, but object initialization (a call to the "<init>" method)
79 is an invocation.
80
81 Z: Integer.
82 Corresponds to an integer number. Used for numbering parameters.
83
84 N: Method name.
85 Corresponds to a method name and descriptor used for virtual method
86 dispatch. There is one for every method name and descriptor used in
87 a virtual method call. There is also a special 'null' method name that
88 is used for non-virtual calls.
89
90 M: Methods.
91 Corresponds to a method in the program. This differs from the N domain
92 in that this contains actual methods, whereas N simply contains names
93 that are used for virtual method lookup, and can therefore contain
94 abstract methods.
95
96 VC: Variable context.
97 Path number used for context sensitivity.
98
99 Files dumped by SummaryToTuples:
100
101 fielddomains.pa :
102 contains the domain definitions, sizes, and map file names.
103
104 m_formal.tuples : (M,Z,V)
105 Contains formal method parameters.
106 A tuple (m,z,v) means that parameter #z of method m is represented by
107 variable v. In static methods, parameter #0 is the special 'global'
108 variable. For instance methods, parameter #0 is the 'this' pointer for
109 the method. Primitive type parameters do not have variable nodes and
110 therefore are not in m_formal.
111
112 m_global.tuples : (M,V)
113 Contains the 'global variable node' for each method.
114 Each method has a 'global variable node' that it uses when accessing
115 static fields. A tuple (m,v) means that method m has global variable
116 node v.
117
118 m_vP.tuples : (M,V,H)
119 Contains object creation sites within the method.
120 A tuple (m,v,h) means that method m contains an object creation site
121 that makes variable v point to new heap location h.
122
123 m_A.tuples : (M,V,V)
124 Contains assignments within a method.
125 A tuple (m,v1,v2) means that method m contains an assignment "v1=v2;".
126 Note that because assignments are factored away, the only remaining
127 assignments will be caused by casts. This is because variables can
128 only have one type, so we need to use different variables to record
129 the different types.
130
131 m_L.tuples : (M,V,F,V)
132 Contains load instructions within a method.
133 A tuple (m,v1,f,v2) means that method m contains a load instruction
134 "v2=v1.f;", or if f is the special 'array' field, then m contains an
135 instruction of the form "v2=v1[_];". Loads from static fields
136 are specified with v1 equal to the 'global variable node' for the method.
137 Loads from fields with primitive types are skipped.
138
139 m_S.tuples : (M,V,F,V)
140 Contains store instructions within a method.
141 A tuple (m,v1,f,v2) means that method m contains a store instruction
142 "v1.f=v2;", or if f is the special 'array' field, then m contains an
143 instruction of the form "v1[_]=v2;". Stores into static fields
144 are specified with v1 equal to the 'global variable node' for the method.
145 Stores to fields with primitive types are skipped.
146
147 m_calls.tuples : (M,I,N)
148 Contains the method invocations within a method.
149 A tuple (m,i,n) means that a method m contains an invocation site i
150 on method name n. If the invocation is a non-virtual invocation or can
151 be completely statically resolved, the method name is a special null
152 method name, otherwise the method name is the virtual method to do the
153 lookup upon. Non-virtual calls will also appear in "m_sc" with their
154 real targets.
155
156 m_actual.tuples : (M,I,Z,V)
157 Contains the parameters for method invocations.
158 A tuple (m,i,z,v) means that a method m contains an invocation site i
159 with variable v passed in as parameter #z. Static calls have the
160 special 'global' variable as their 0th parameter; instance calls have
161 the base object as their 0th parameter. Primitive-typed parameters
162 are skipped.
163
164 m_Iret.tuples : (M,I,V)
165 Contains the return values for method invocations.
166 A tuple (m,i,v) means that a method m contains an invocation site i
167 with return value v. Invocations that do not use the return value or
168 that have a primitive return value are skipped.
169
170 m_Ithr.tuples : (M,I,V)
171 Contains the thrown exceptions for method invocations.
172 A tuple (m,i,v) means that a method m contains an invocation site i
173 with thrown exception v.
174
175 m_sync.tuples : (M,V)
176 Contains the variables that are synchronized in a method.
177 A tuple (m,v) means that method m synchronizes on variable v.
178
179 m_vars.tuples : (M,V)
180 Contains the set of all variables in a method.
181 A tuple (m,v) means that method m contains variable v.
182
183 m_ret.tuples : (M,V)
184 Contains the set of variables that are returned from a method.
185 A tuple (m,v) means that method m returns variable v.
186
187 m_thr.tuples : (M,V)
188 Contains the set of variables that are thrown from a method.
189 A tuple (m,v) means that method m throws variable v.
190
191 m_sc.tuples : (M,I,M)
192 Contains the statically-bound calls in a method.
193 A tuple (m1,i,m2) means that m1 contains an invocation site i that
194 is statically bound to call m2.
195
196 vT.tuples : (V,T)
197 Contains the declared type (class or interface) of each variable.
198
199 hT.tuples : (H,T)
200 Contains the type (class) of each object creation site.
201
202 aT.tuples : (T,T)
203 Contains which types are assignable from one to another.
204 A tuple (t1,t2) means that you can assign an object of type t2 to
205 a variable of type t1 (i.e., t1 is a supertype of t2).
206
207 cha.tuples : (T,N,M)
208 Contains the virtual method dispatch information.
209 A tuple (t,n,m) means that doing a virtual method call with name n
210 on an object of type t leads to target method m.
211
212 methods.tuples : (T,M)
213 Contains the methods that each class defines.
214 A tuple (t,m) means that class t defines method m.
215
216 fields.tuples : (T,F)
217 Contains the fields that each class defines.
218 A tuple (t,f) means that class t defines field f.
219
220 clinit.tuples : (T,M)
221 Contains the class initializers.
222 A tuple (t,m) means that class t has class initializer method m.
223
224 m_access.tuples : (M,Z)
225 Contains the access modifiers for each of the methods.
226 0 = public, 1 = private, 2 = protected, 3 = package-protected
227
228 f_access.tuples : (F,Z)
229 Contains the access modifiers for each of the fields.
230 0 = public, 1 = private, 2 = protected, 3 = package-protected
231
232 *
233 * @author jwhaley
234 * @version $Id: SummaryToTuples.java 2289 2005-07-15 00:45:14Z joewhaley $
235 */
236 public class SummaryToTuples {
237
238 public static boolean TRACE = !System.getProperty("pa.trace", "no").equals("no");
239 public static PrintStream out = System.out;
240
241 boolean SKIP_NULL = !System.getProperty("pa.skipnull", "yes").equals("no");
242 boolean SKIP_EXCEPTIONS = !System.getProperty("pa.skipexceptions", "yes").equals("no");
243 boolean ADD_SUPERTYPES = !System.getProperty("pa.addsupertypes", "yes").equals("no");
244
245 IndexMap
246 IndexMap
247 IndexMap
248 IndexMap
249 IndexMap
250 IndexMap
251 IndexMap
252
253 jq_Class object_class = PrimordialClassLoader.getJavaLangObject();
254 jq_Method javaLangObject_clone;
255 {
256 object_class.prepare();
257 javaLangObject_clone = object_class.getDeclaredInstanceMethod(new jq_NameAndDesc("clone", "()Ljava/lang/Object;"));
258 }
259 jq_Class cloneable_class = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("Ljava/lang/Cloneable;");
260 jq_Class throwable_class = (jq_Class) PrimordialClassLoader.getJavaLangThrowable();
261 jq_Method javaLangObject_fakeclone = jq_FakeInstanceMethod.fakeMethod(object_class,
262 MethodSummary.fakeCloneName, "()Ljava/lang/Object;");
263
264 Tuples.S2 vT;
265 Tuples.S2 hT;
266 Tuples.S2 aT;
267 Tuples.S3 cha;
268 Tuples.S2 methods;
269 Tuples.S2 fields;
270 Tuples.S2 clinit;
271 Tuples.S2 m_access;
272 Tuples.S2 f_access;
273
274 int last_V, last_H, last_T, last_N, last_F, last_M;
275
276 public static boolean USE_HMAP = false;
277
278 public SummaryToTuples() {
279 Vmap = new IndexMap("var");
280 Imap = new IndexMap("invoke");
281 if (USE_HMAP)
282 Hmap = new IndexMap("heap");
283 else
284 Hmap = Vmap;
285 Fmap = new IndexMap("field");
286 Tmap = new IndexMap("type");
287 Nmap = new IndexMap("name");
288 Mmap = new IndexMap("method");
289
290
291 Vmap.get(GlobalNode.GLOBAL);
292 Hmap.get(GlobalNode.GLOBAL);
293 Fmap.get(null);
294 Tmap.get(null);
295 }
296
297 Map cache = new HashMap();
298
299 public TupleSummary getSummary(jq_Method m) {
300 TupleSummary s = (TupleSummary) cache.get(m);
301 if (s == null) cache.put(m, s = new TupleSummary(m));
302 return s;
303 }
304
305 void calcTypes() {
306 vT = new TuplesArray.S2(16384);
307 hT = new TuplesArray.S2(8192);
308 aT = new TuplesArray.S2(8192);
309 cha = new TuplesArray.S3(8192);
310 methods = new TuplesArray.S2(4096);
311 fields = new TuplesArray.S2(4096);
312 clinit = new TuplesArray.S2(4096);
313 m_access = new TuplesArray.S2(4096);
314 f_access = new TuplesArray.S2(4096);
315 last_V = 0; last_H = 0; last_T = 0; last_N = 0; last_F = 0; last_M = 0;
316 calcTypes_inc();
317 }
318
319 void calcTypes_inc() {
320
321 int Vsize = Vmap.size();
322 for (int V_i = last_V; V_i < Vsize; ++V_i) {
323 Node n = (Node) Vmap.get(V_i);
324 jq_Reference type = n.getDeclaredType();
325 if (type != null) type.prepare();
326 vT.add(V_i, Tmap.get(type));
327 }
328
329
330 int Hsize = Hmap.size();
331 for (int H_i = last_H; H_i < Hsize; ++H_i) {
332 Node n = (Node) Hmap.get(H_i);
333 if (!USE_HMAP) {
334 if (n instanceof MethodSummary.FieldNode ||
335 n instanceof MethodSummary.ParamNode ||
336 n instanceof MethodSummary.CheckCastNode ||
337 n instanceof MethodSummary.ReturnValueNode ||
338 n instanceof MethodSummary.ThrownExceptionNode
339 ) continue;
340 }
341 jq_Reference type = n.getDeclaredType();
342 if (type != null) type.prepare();
343 hT.add(H_i, Tmap.get(type));
344 }
345
346 if (ADD_SUPERTYPES) {
347
348 for (int T_i = 0; T_i < Tmap.size(); ++T_i) {
349 jq_Reference t1 = (jq_Reference) Tmap.get(T_i);
350 if (t1 == null || t1 instanceof jq_NullType) continue;
351 t1.prepare();
352 jq_Reference t2 = t1.getDirectPrimarySupertype();
353 if (t2 != null) {
354 t2.prepare();
355 Tmap.get(t2);
356 }
357 jq_Class[] c = t1.getInterfaces();
358 for (int i = 0; i < c.length; ++i) {
359 Tmap.get(c[i]);
360 }
361 }
362 }
363
364 int Tsize = Tmap.size();
365
366 for (int T1_i = 0; T1_i < Tsize; ++T1_i) {
367 jq_Reference t1 = (jq_Reference) Tmap.get(T1_i);
368 int start = (T1_i < last_T)?last_T:0;
369 for (int T2_i = start; T2_i < Tsize; ++T2_i) {
370 jq_Reference t2 = (jq_Reference) Tmap.get(T2_i);
371 if (t2 == null || (t1 != null && t2.isSubtypeOf(t1))) {
372 aT.add(T1_i, T2_i);
373 }
374 }
375 }
376
377
378 int Nsize = Nmap.size();
379 for (int T_i = 0; T_i < Tsize; ++T_i) {
380 jq_Reference t = (jq_Reference) Tmap.get(T_i);
381 int start = (T_i < last_T)?last_N:0;
382 for (int N_i = start; N_i < Nsize; ++N_i) {
383 jq_Method n = (jq_Method) Nmap.get(N_i);
384 if (n == null) continue;
385 n.getDeclaringClass().prepare();
386 jq_Method m;
387 if (n.isStatic()) {
388 if (t != null) continue;
389 m = n;
390 } else {
391 if (t == null ||
392 t == jq_NullType.NULL_TYPE ||
393 !t.isSubtypeOf(n.getDeclaringClass())) continue;
394 m = t.getVirtualMethod(n.getNameAndDesc());
395 }
396 if ((m == javaLangObject_clone && t != object_class) || n == javaLangObject_fakeclone) {
397 m = fakeCloneIfNeeded(t);
398 cha.add(T_i, Nmap.get(javaLangObject_fakeclone), Mmap.get(m));
399 }
400 if (m == null) continue;
401 cha.add(T_i, N_i, Mmap.get(m));
402 }
403 }
404
405 int Fsize = Fmap.size();
406 for (int F_i = last_F; F_i < Fsize; ++F_i) {
407 jq_Member f = (jq_Member) Fmap.get(F_i);
408 int a;
409 if (f == null || f.isPublic()) a = 0;
410 else if (f.isPrivate()) a = 1;
411 else if (f.isProtected()) a = 2;
412 else a = 3;
413 f_access.add(F_i, a);
414 if (f != null)
415 fields.add(Tmap.get(f.getDeclaringClass()), F_i);
416 }
417
418 int Msize = Mmap.size();
419 for (int M_i = last_M; M_i < Msize; ++M_i) {
420 jq_Member f = (jq_Member) Mmap.get(M_i);
421 int a;
422 if (f.isPublic()) a = 0;
423 else if (f.isPrivate()) a = 1;
424 else if (f.isProtected()) a = 2;
425 else a = 3;
426 m_access.add(M_i, a);
427 methods.add(Tmap.get(f.getDeclaringClass()), M_i);
428 if (f instanceof jq_ClassInitializer)
429 clinit.add(Tmap.get(f.getDeclaringClass()), M_i);
430 }
431
432 last_V = Vsize;
433 last_H = Hsize;
434 last_T = Tsize;
435 last_N = Nsize;
436 last_F = Fsize;
437 last_M = Msize;
438 if (Vsize != Vmap.size() ||
439 Hsize != Hmap.size() ||
440 Tsize != Tmap.size() ||
441 Nsize != Nmap.size() ||
442 Fsize != Fmap.size() ||
443 Msize != Mmap.size()) {
444 if (TRACE) out.println("Elements added, recalculating types...");
445 calcTypes_inc();
446 }
447 }
448
449 private jq_Method fakeCloneIfNeeded(jq_Type t) {
450 jq_Method m = javaLangObject_clone;
451 if (t instanceof jq_Class) {
452 jq_Class c = (jq_Class) t;
453 if (!c.isInterface() && c.implementsInterface(cloneable_class)) {
454 m = jq_FakeInstanceMethod.fakeMethod(c, MethodSummary.fakeCloneName, "()"+t.getDesc());
455 }
456 }
457
458 return m;
459 }
460
461 public class TupleSummary {
462 jq_Method m;
463 MethodSummary ms;
464
465 int[] formal;
466 int global;
467
468 Tuples.S2 vP;
469 Tuples.S2 A;
470 Tuples.S3 L;
471 Tuples.S3 S;
472 Tuples.S2 calls;
473 Tuples.S3 actual;
474 Tuples.S2 Iret;
475 Tuples.S2 Ithr;
476 Tuples.S1 sync;
477 Tuples.S1 vars;
478 Tuples.S1 ret;
479 Tuples.S1 thr;
480 Tuples.S2 sc;
481
482 public TupleSummary(jq_Method m) {
483 visitMethod(m);
484 }
485
486 public TupleSummary(MethodSummary ms) {
487 this.m = ms.getMethod();
488 visitMethodSummary(ms);
489 }
490
491 void visitMethod(jq_Method m) {
492 Assert._assert(m != null);
493 Assert._assert(m.getDeclaringClass() != null);
494
495 if (TRACE) out.println("Visiting method "+m);
496 m.getDeclaringClass().prepare();
497 this.m = m;
498 this.ms = MethodSummary.getSummary(m);
499 Mmap.get(m);
500
501 if (m.getBytecode() == null && ms == null) {
502
503 init();
504
505
506 handleFormalParams();
507
508
509 jq_Type retType = m.getReturnType();
510 if (retType instanceof jq_Reference) {
511 Node node = UnknownTypeNode.get((jq_Reference) retType);
512 int V_i = Vmap.get(node);
513 vars.add(V_i);
514 ret.add(V_i);
515 visitNode(node);
516 }
517 if (!SKIP_EXCEPTIONS) {
518 Node node = UnknownTypeNode.get(PrimordialClassLoader.getJavaLangThrowable());
519 int V_i = Vmap.get(node);
520 vars.add(V_i);
521 thr.add(V_i);
522 visitNode(node);
523 }
524 return;
525 }
526
527 visitMethodSummary(ms);
528 }
529
530 boolean skipNode(Node node) {
531 if (SKIP_NULL && MethodSummary.isNullConstant(node))
532 return true;
533 if (SKIP_EXCEPTIONS && node instanceof MethodSummary.ThrownExceptionNode)
534 return true;
535 return false;
536 }
537
538 private void init() {
539 vP = new TuplesArray.S2(2);
540 A = new TuplesArray.S2(2);
541 L = new TuplesArray.S3(2);
542 S = new TuplesArray.S3(2);
543 calls = new TuplesArray.S2(2);
544 actual = new TuplesArray.S3(2);
545 Iret = new TuplesArray.S2(2);
546 Ithr = new TuplesArray.S2(2);
547 sync = new TuplesArray.S1(2);
548 vars = new TuplesArray.S1(2);
549 ret = new TuplesArray.S1(2);
550 thr = new TuplesArray.S1(2);
551 sc = new TuplesArray.S2(2);
552 }
553
554 void handleFormalParams() {
555 int offset;
556 Node thisparam;
557 if (m.isStatic()) {
558 thisparam = GlobalNode.GLOBAL;
559 offset = 0;
560 } else {
561 if (ms != null)
562 thisparam = ms.getParamNode(0);
563 else
564 thisparam = MethodSummary.ParamNode.get(m, 0, m.getDeclaringClass());
565 offset = 1;
566 }
567 int nParams;
568 if (ms != null) nParams = ms.getNumOfParams();
569 else nParams = m.getParamTypes().length;
570 formal = new int[nParams+1-offset];
571 formal[0] = Vmap.get(thisparam);
572 for (int i = offset; i < nParams; ++i) {
573 Node node;
574 if (ms != null) {
575 node = ms.getParamNode(i);
576 } else {
577 jq_Type t = m.getParamTypes()[i];
578 if (!t.isReferenceType()) continue;
579 node = MethodSummary.ParamNode.get(m, i, (jq_Reference) t);
580 }
581 formal[i+1-offset] = node==null?-1:Vmap.get(node);
582 }
583
584 if (m.isSynchronized()) {
585 if (TRACE) out.println("Synchronized method, sync on: "+thisparam);
586 sync.add(formal[0]);
587
588 }
589
590 if (ms != null) {
591 global = Vmap.get(ms.getGlobal());
592 } else {
593 global = Vmap.get(GlobalNode.GLOBAL);
594 }
595 }
596
597 void visitMethodSummary(MethodSummary ms) {
598
599 if (TRACE) out.println("Visiting method summary "+ms);
600
601 if (vP == null) {
602 int nNodes = ms.nodes.size();
603 int nCalls = ms.calls.size();
604 vP = new TuplesArray.S2(nNodes/2+1);
605 A = new TuplesArray.S2(nNodes/4+1);
606 L = new TuplesArray.S3(nNodes/2+1);
607 S = new TuplesArray.S3(nNodes/4+1);
608 calls = new TuplesArray.S2(nCalls+1);
609 actual = new TuplesArray.S3(nCalls*3+1);
610 Iret = new TuplesArray.S2(nCalls+1);
611 Ithr = new TuplesArray.S2(nCalls+1);
612 sync = new TuplesArray.S1(2);
613 vars = new TuplesArray.S1(nNodes+1);
614 ret = new TuplesArray.S1(8);
615 thr = new TuplesArray.S1(8);
616 sc = new TuplesArray.S2(nCalls+1);
617 }
618
619
620 handleFormalParams();
621
622
623 for (Iterator i = ms.getSyncedVars().iterator(); i.hasNext(); ) {
624 Node node = (Node) i.next();
625 if (skipNode(node)) continue;
626 if (TRACE) out.println("Sync on: "+node);
627 sync.add(Vmap.get(node));
628 }
629
630
631 for (Iterator i = ms.getCalls().iterator(); i.hasNext(); ) {
632 ProgramLocation mc = (ProgramLocation) i.next();
633 if (TRACE) out.println("Visiting call site "+mc);
634 int I_i = Imap.get(LoadedCallGraph.mapCall(mc));
635 jq_Method target = mc.getTargetMethod();
636
637 Set thisptr;
638 int offset;
639 if (target.isStatic()) {
640 thisptr = Collections.singleton(GlobalNode.GLOBAL);
641 offset = 0;
642 } else {
643 thisptr = ms.getNodesThatCall(mc, 0);
644 offset = 1;
645 }
646 for (Iterator j = thisptr.iterator(); j.hasNext(); ) {
647 Node n = (Node) j.next();
648 if (!skipNode(n)) {
649 actual.add(I_i, 0, Vmap.get(n));
650 }
651 }
652
653 if (mc.isSingleTarget()) {
654 if (target != javaLangObject_clone) {
655
656 calls.add(I_i, Nmap.get(null));
657 sc.add(I_i, Mmap.get(target));
658 } else {
659
660 calls.add(I_i, Nmap.get(javaLangObject_fakeclone));
661 }
662 } else {
663
664 calls.add(I_i, Nmap.get(target));
665 }
666
667 jq_Type[] params = mc.getParamTypes();
668 int k = offset;
669 for ( ; k < params.length; ++k) {
670 if (!params[k].isReferenceType()) {
671 continue;
672 }
673 Set s = ms.getNodesThatCall(mc, k);
674 for (Iterator j = s.iterator(); j.hasNext(); ) {
675 Node n = (Node) j.next();
676 if (skipNode(n)) continue;
677 actual.add(I_i, k+1-offset, Vmap.get(n));
678 }
679 }
680 Node node = ms.getRVN(mc);
681 if (node != null && !skipNode(node)) {
682 Iret.add(I_i, Vmap.get(node));
683 }
684 if (!SKIP_EXCEPTIONS) {
685 node = ms.getTEN(mc);
686 if (node != null && !skipNode(node)) {
687 Ithr.add(I_i, Vmap.get(node));
688 }
689 }
690 }
691
692
693 for (Iterator i = ms.nodeIterator(); i.hasNext(); ) {
694 Node node = (Node) i.next();
695 if (skipNode(node)) continue;
696
697 int V_i = Vmap.get(node);
698 vars.add(V_i);
699
700 if (ms.getReturned().contains(node)) {
701 ret.add(V_i);
702 }
703
704 if (!SKIP_EXCEPTIONS && ms.getThrown().contains(node)) {
705 thr.add(V_i);
706 }
707
708 visitNode(node);
709 }
710
711
712 for (Iterator i = ms.getCastMap().entrySet().iterator(); i.hasNext(); ) {
713 Map.Entry e = (Map.Entry)i.next();
714 Node from = (Node)((Pair)e.getKey()).left;
715 if (skipNode(from)) continue;
716 CheckCastNode to = (CheckCastNode)e.getValue();
717 int V_i = Vmap.get(to);
718 A.add(V_i, Vmap.get(from));
719 }
720 }
721
722 void visitNode(Node node) {
723 if (TRACE)
724 out.println("Visiting node "+node);
725
726 Assert._assert(!skipNode(node));
727
728 int V_i = Vmap.get(node);
729
730 if (node instanceof ConcreteTypeNode ||
731 node instanceof ConcreteObjectNode ||
732 node instanceof UnknownTypeNode ||
733 node == GlobalNode.GLOBAL) {
734 int H_i = Hmap.get(node);
735 vP.add(V_i, H_i);
736 }
737
738 for (Iterator j = node.getAllEdges().iterator(); j.hasNext(); ) {
739 Map.Entry e = (Map.Entry) j.next();
740 jq_Field f = (jq_Field) e.getKey();
741 Collection c;
742 if (e.getValue() instanceof Collection)
743 c = (Collection) e.getValue();
744 else
745 c = Collections.singleton(e.getValue());
746 int F_i = Fmap.get(f);
747 for (Iterator k = c.iterator(); k.hasNext(); ) {
748 Node node2 = (Node) k.next();
749 if (skipNode(node2)) continue;
750 int V2_i = Vmap.get(node2);
751 S.add(V_i, F_i, V2_i);
752 }
753 }
754
755 for (Iterator j = node.getAccessPathEdges().iterator(); j.hasNext(); ) {
756 Map.Entry e = (Map.Entry) j.next();
757 jq_Field f = (jq_Field) e.getKey();
758 Collection c;
759 if (e.getValue() instanceof Collection)
760 c = (Collection) e.getValue();
761 else
762 c = Collections.singleton(e.getValue());
763 int F_i = Fmap.get(f);
764 for (Iterator k = c.iterator(); k.hasNext(); ) {
765 Node node2 = (Node) k.next();
766 int V2_i = Vmap.get(node2);
767 L.add(V_i, F_i, V2_i);
768 }
769 }
770 }
771
772 public String toString() {
773 StringBuffer sb = new StringBuffer();
774 sb.append(m);
775 sb.append('\n');
776 sb.append("Params: ");
777 for (int i = 0; i < formal.length; ++i) {
778 if (i > 0) sb.append(',');
779 sb.append(formal[i]);
780 }
781 sb.append("\nGlobal: ");
782 sb.append(global);
783 if (!vP.isEmpty()) {
784 sb.append("\nvP: ");
785 sb.append(vP);
786 }
787 if (!A.isEmpty()) {
788 sb.append("\nA: ");
789 sb.append(A);
790 }
791 if (!L.isEmpty()) {
792 sb.append("\nL: ");
793 sb.append(L);
794 }
795 if (!S.isEmpty()) {
796 sb.append("\nS: ");
797 sb.append(S);
798 }
799 if (!calls.isEmpty()) {
800 sb.append("\ncalls: ");
801 sb.append(calls);
802 }
803 if (!actual.isEmpty()) {
804 sb.append("\nactual: ");
805 sb.append(actual);
806 }
807 if (!Iret.isEmpty()) {
808 sb.append("\nIret: ");
809 sb.append(Iret);
810 }
811 if (!Ithr.isEmpty()) {
812 sb.append("\nIthr: ");
813 sb.append(Ithr);
814 }
815 if (!sync.isEmpty()) {
816 sb.append("\nsync: ");
817 sb.append(sync);
818 }
819 if (!vars.isEmpty()) {
820 sb.append("\nvars: ");
821 sb.append(vars);
822 }
823 if (!ret.isEmpty()) {
824 sb.append("\nret: ");
825 sb.append(ret);
826 }
827 if (!thr.isEmpty()) {
828 sb.append("\nthr: ");
829 sb.append(thr);
830 }
831 if (!sc.isEmpty()) {
832 sb.append("\nsc: ");
833 sb.append(sc);
834 }
835 sb.append('\n');
836 return sb.toString();
837 }
838 }
839
840 String mungeMethodName(jq_Method m) {
841 if (m == null) return "null";
842 return m.toString();
843 }
844 String mungeFieldName(jq_Field m) {
845 if (m == null) return "null";
846 return m.toString();
847 }
848 String mungeTypeName2(jq_Type m) {
849 if (m == null) return "null";
850 return m.toString();
851 }
852
853 public void dump() throws IOException {
854 String dumpPath = System.getProperty("pa.dumppath", "");
855 if (dumpPath.length() > 0) {
856 File f = new File(dumpPath);
857 if (!f.exists()) f.mkdirs();
858 String sep = System.getProperty("file.separator", "/");
859 if (!dumpPath.endsWith(sep))
860 dumpPath += sep;
861 }
862 dump(dumpPath);
863 }
864
865 public void dump(String dumpPath) throws IOException {
866 System.out.println("Dumping to path "+dumpPath);
867
868 int V_BITS = BigInteger.valueOf(Vmap.size()).bitLength();
869 int H_BITS = BigInteger.valueOf(Hmap.size()).bitLength();
870 int T_BITS = BigInteger.valueOf(Tmap.size()).bitLength();
871 int F_BITS = BigInteger.valueOf(Fmap.size()).bitLength();
872 int I_BITS = BigInteger.valueOf(Imap.size()).bitLength();
873 int Z_BITS = 6;
874 int N_BITS = BigInteger.valueOf(Nmap.size()).bitLength();
875 int M_BITS = BigInteger.valueOf(Mmap.size()).bitLength();
876 int VC_BITS = 62;
877
878 BufferedWriter dos = null;
879 try {
880 dos = new BufferedWriter(new FileWriter(dumpPath+"fielddomains.pa"));
881 dos.write("V "+(1L<<V_BITS)+" var.map\n");
882 dos.write("H "+(1L<<H_BITS)+" heap.map\n");
883 dos.write("T "+(1L<<T_BITS)+" type.map\n");
884 dos.write("F "+(1L<<F_BITS)+" field.map\n");
885 dos.write("I "+(1L<<I_BITS)+" invoke.map\n");
886 dos.write("Z "+(1L<<Z_BITS)+"\n");
887 dos.write("N "+(1L<<N_BITS)+" name.map\n");
888 dos.write("M "+(1L<<M_BITS)+" method.map\n");
889 dos.write("VC "+(1L<<VC_BITS)+"\n");
890 } finally {
891 if (dos != null) dos.close();
892 }
893
894 int tuples = 0;
895 dos = null;
896 try {
897 dos = new BufferedWriter(new FileWriter(dumpPath+"m_formal.tuples"));
898 dos.write("# M0:"+M_BITS+" Z0:"+Z_BITS+" V0:"+V_BITS+"\n");
899 for (Iterator i = cache.values().iterator(); i.hasNext(); ) {
900 TupleSummary s = (TupleSummary) i.next();
901 String prefix = Mmap.get(s.m)+" ";
902 for (int j = 0; j < s.formal.length; ++j) {
903 if (s.formal[j] == -1) continue;
904 dos.write(prefix+j+" "+s.formal[j]+"\n");
905 ++tuples;
906 }
907 }
908 System.out.println("Wrote formal.tuples"+": "+tuples+" elements");
909 } finally {
910 if (dos != null) dos.close();
911 }
912
913 tuples = 0;
914 dos = null;
915 try {
916 dos = new BufferedWriter(new FileWriter(dumpPath+"m_global.tuples"));
917 dos.write("# M0:"+M_BITS+" V0:"+V_BITS+"\n");
918 for (Iterator i = cache.values().iterator(); i.hasNext(); ) {
919 TupleSummary s = (TupleSummary) i.next();
920 if (s.global == -1) continue;
921 dos.write(Mmap.get(s.m)+" "+s.global+"\n");
922 ++tuples;
923 }
924 System.out.println("Wrote global.tuples"+": "+tuples+" elements");
925 } finally {
926 if (dos != null) dos.close();
927 }
928
929 Field[] fs = TupleSummary.class.getDeclaredFields();
930 for (int k = 0; k < fs.length; ++k) {
931 if (!Tuples.Interface.class.isAssignableFrom(fs[k].getType())) {
932 continue;
933 }
934 tuples = 0;
935 dos = null;
936 try {
937 dos = new BufferedWriter(new FileWriter(dumpPath+"m_"+fs[k].getName()+".tuples"));
938 for (Iterator i = cache.values().iterator(); i.hasNext(); ) {
939 TupleSummary s = (TupleSummary) i.next();
940 String prefix = Mmap.get(s.m)+" ";
941 Tuples.Interface t;
942 try {
943 t = (Tuples.Interface) fs[k].get(s);
944 t.dump(prefix, dos);
945 tuples += t.size();
946 } catch (IllegalArgumentException e) {
947 e.printStackTrace();
948 } catch (IllegalAccessException e) {
949 e.printStackTrace();
950 }
951 }
952 System.out.println("Wrote "+fs[k].getName()+".tuples"+": "+tuples+" elements");
953 } finally {
954 if (dos != null) dos.close();
955 }
956 }
957
958 fs = SummaryToTuples.class.getDeclaredFields();
959 for (int k = 0; k < fs.length; ++k) {
960 if (!Tuples.Interface.class.isAssignableFrom(fs[k].getType())) {
961 continue;
962 }
963 dos = null;
964 try {
965 dos = new BufferedWriter(new FileWriter(dumpPath+fs[k].getName()+".tuples"));
966 Tuples.Interface t;
967 try {
968 t = (Tuples.Interface) fs[k].get(this);
969 t.dump(dos);
970 System.out.println("Wrote "+fs[k].getName()+".tuples: "+t.size()+" elements");
971 } catch (IllegalArgumentException e) {
972 e.printStackTrace();
973 } catch (IllegalAccessException e) {
974 e.printStackTrace();
975 }
976 } finally {
977 if (dos != null) dos.close();
978 }
979 }
980
981 dos = null;
982 try {
983 dos = new BufferedWriter(new FileWriter(dumpPath+"var.map"));
984 for (int j = 0; j < Vmap.size(); ++j) {
985 Node o = (Node)Vmap.get(j);
986 dos.write(o.id+": "+o+"\n");
987 }
988 } finally {
989 if (dos != null) dos.close();
990 }
991
992 if (USE_HMAP) {
993 dos = null;
994 try {
995 dos = new BufferedWriter(new FileWriter(dumpPath+"heap.map"));
996 for (int j = 0; j < Hmap.size(); ++j) {
997 Node o = (Node) Hmap.get(j);
998 dos.write(o.id+": "+o+"\n");
999 }
1000 } finally {
1001 if (dos != null) dos.close();
1002 }
1003 }
1004
1005 dos = null;
1006 try {
1007 dos = new BufferedWriter(new FileWriter(dumpPath+"type.map"));
1008 for (int j = 0; j < Tmap.size(); ++j) {
1009 jq_Type o = (jq_Type) Tmap.get(j);
1010 dos.write(mungeTypeName2(o)+"\n");
1011 }
1012 } finally {
1013 if (dos != null) dos.close();
1014 }
1015
1016 dos = null;
1017 try {
1018 dos = new BufferedWriter(new FileWriter(dumpPath+"field.map"));
1019 for (int j = 0; j < Fmap.size(); ++j) {
1020 jq_Field o = (jq_Field) Fmap.get(j);
1021 dos.write(mungeFieldName(o)+"\n");
1022 }
1023 } finally {
1024 if (dos != null) dos.close();
1025 }
1026
1027 dos = null;
1028 try {
1029 dos = new BufferedWriter(new FileWriter(dumpPath+"invoke.map"));
1030 for (int j = 0; j < Imap.size(); ++j) {
1031 ProgramLocation o = (ProgramLocation)Imap.get(j);
1032 dos.write(o.hashCode()+": "+o+"\n");
1033 }
1034 } finally {
1035 if (dos != null) dos.close();
1036 }
1037
1038 dos = null;
1039 try {
1040 dos = new BufferedWriter(new FileWriter(dumpPath+"name.map"));
1041 for (int j = 0; j < Nmap.size(); ++j) {
1042 jq_Method o = (jq_Method) Nmap.get(j);
1043 dos.write(mungeMethodName(o)+"\n");
1044 }
1045 } finally {
1046 if (dos != null) dos.close();
1047 }
1048
1049 dos = null;
1050 try {
1051 dos = new BufferedWriter(new FileWriter(dumpPath+"method.map"));
1052 for (int j = 0; j < Mmap.size(); ++j) {
1053 Object o = Mmap.get(j);
1054 jq_Method m = (jq_Method) o;
1055 dos.write(mungeMethodName(m)+"\n");
1056 }
1057 } finally {
1058 if (dos != null) dos.close();
1059 }
1060
1061 }
1062
1063 public static Collection
1064 jq_Class c = (jq_Class) jq_Type.parseType(args[0]);
1065 c.load();
1066 String name = null, desc = null;
1067 if (args.length > 1) {
1068 name = args[1];
1069 if (args.length > 2) {
1070 desc = args[2];
1071 }
1072 }
1073 Collection methods;
1074 if (name != null) {
1075 jq_Method m;
1076 if (desc != null) {
1077 m = (jq_Method) c.getDeclaredMember(name, desc);
1078 } else {
1079 m = c.getDeclaredMethod(name);
1080 }
1081 methods = Collections.singleton(m);
1082 } else {
1083 methods = new LinkedList();
1084 methods.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
1085 methods.addAll(Arrays.asList(c.getDeclaredInstanceMethods()));
1086 }
1087 return methods;
1088 }
1089
1090 public static String canonicalizeClassName(String s) {
1091 if (s.endsWith(".class")) s = s.substring(0, s.length() - 6);
1092 s = s.replace('.', '/');
1093 String desc = "L" + s + ";";
1094 return desc;
1095 }
1096
1097 private static Collection getClassesInPackage(String pkgName, boolean recursive) {
1098 String canonicalPackageName = pkgName.replace('.', '/');
1099 if (!canonicalPackageName.endsWith("/")) canonicalPackageName += '/';
1100 Iterator i = PrimordialClassLoader.loader.listPackage(canonicalPackageName, recursive);
1101 if (!i.hasNext()) {
1102 System.err.println("Package " + canonicalPackageName + " not found.");
1103 }
1104
1105
1106 Collection result = new LinkedList();
1107 HashSet loaded = new HashSet();
1108 while (i.hasNext()) {
1109 String canonicalClassName = canonicalizeClassName((String) i.next());
1110 if (loaded.contains(canonicalClassName))
1111 continue;
1112 loaded.add(canonicalClassName);
1113 try {
1114
1115 jq_Class c = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType(canonicalClassName);
1116 c.load();
1117 result.add(c);
1118 } catch (SecurityException x) {
1119 System.err.println("Security exception occurred while loading class (" + canonicalClassName + "):");
1120 } catch (NoClassDefFoundError x) {
1121 System.err.println("Package " + pkgName + ": Class not found (canonical name " + canonicalClassName + ").");
1122 } catch (LinkageError le) {
1123 System.err.println("Linkage error occurred while loading class (" + canonicalClassName + "):");
1124 le.printStackTrace(System.err);
1125 }
1126 }
1127 return result;
1128 }
1129
1130 public static Collection
1131 Collection classes;
1132 if (arg.endsWith(".**")) {
1133 String packageName = arg.substring(0, arg.length()-3);
1134 classes = getClassesInPackage(packageName, true);
1135 } else if (arg.endsWith(".*")) {
1136 String packageName = arg.substring(0, arg.length()-2);
1137 classes = getClassesInPackage(packageName, false);
1138 } else {
1139 String canonicalClassName = canonicalizeClassName(arg);
1140 jq_Class c = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType(canonicalClassName);
1141 c.load();
1142 classes = Collections.singleton(c);
1143 }
1144 Collection methods = new LinkedList();
1145 for (Iterator i = classes.iterator(); i.hasNext(); ) {
1146 jq_Class c = (jq_Class) i.next();
1147 methods.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
1148 methods.addAll(Arrays.asList(c.getDeclaredInstanceMethods()));
1149 }
1150 return methods;
1151 }
1152
1153 public static void main(String[] args) throws IOException {
1154 HostedVM.initialize();
1155 CodeCache.AlwaysMap = true;
1156
1157 Collection methods = new LinkedList();
1158 for (int i = 0; i < args.length; ++i) {
1159 Collection methods2 = parseClass(args[i]);
1160 methods.addAll(methods2);
1161 }
1162 System.out.println("Processing "+methods.size()+" methods...");
1163 SummaryToTuples dis = new SummaryToTuples();
1164 for (Iterator i = methods.iterator(); i.hasNext(); ) {
1165 jq_Method m = (jq_Method) i.next();
1166 if (m.getBytecode() == null) continue;
1167 TupleSummary s = dis.getSummary(m);
1168
1169 }
1170 dis.calcTypes();
1171 dis.dump();
1172 }
1173
1174 }