1
2
3
4 package joeq.Compiler.Analysis.IPA;
5
6 import java.io.PrintStream;
7 import java.util.Arrays;
8 import java.util.Collection;
9 import java.util.Collections;
10 import java.util.Iterator;
11 import java.util.LinkedList;
12 import java.util.Map;
13 import java.util.Set;
14 import joeq.Class.jq_Class;
15 import joeq.Class.jq_FakeInstanceMethod;
16 import joeq.Class.jq_FakeStaticMethod;
17 import joeq.Class.jq_Field;
18 import joeq.Class.jq_Initializer;
19 import joeq.Class.jq_Method;
20 import joeq.Class.jq_MethodVisitor;
21 import joeq.Class.jq_Reference;
22 import joeq.Class.jq_Type;
23 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
24 import joeq.Compiler.Analysis.FlowInsensitive.ReflectionInformationProvider;
25 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.CheckCastNode;
26 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ConcreteObjectNode;
27 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ConcreteTypeNode;
28 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.GlobalNode;
29 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.Node;
30 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.UnknownTypeNode;
31 import joeq.Compiler.Quad.CodeCache;
32 import joeq.Compiler.Quad.LoadedCallGraph;
33 import joeq.Compiler.Quad.Operand;
34 import joeq.Compiler.Quad.Operator;
35 import joeq.Compiler.Quad.Quad;
36 import joeq.Main.HostedVM;
37 import jwutil.collections.Pair;
38 import jwutil.util.Assert;
39 import net.sf.javabdd.BDD;
40
41 /***
42 * @author jwhaley
43 * @version $Id: PAMethodSummary.java 2465 2006-06-07 23:03:17Z joewhaley $
44 */
45 public class PAMethodSummary extends jq_MethodVisitor.EmptyVisitor {
46
47 boolean TRACE = false;
48 boolean TRACE_RELATIONS = false;
49 PrintStream out = System.out;
50
51 PA pa;
52
53 jq_Method m;
54
55 BDD vP;
56 BDD L;
57 BDD S;
58 BDD IE;
59
60 public PAMethodSummary(PA pa, jq_Method m) {
61 this.pa = pa;
62 this.TRACE = pa.TRACE;
63 this.TRACE_RELATIONS = pa.TRACE_RELATIONS;
64 this.m = m;
65 vP = pa.bdd.zero();
66 L = pa.bdd.zero();
67 S = pa.bdd.zero();
68 IE = pa.bdd.zero();
69 visitMethod(m);
70 }
71
72 public void registerRelations(BDD V1V2context, BDD V1H1context) {
73 if (TRACE) out.println("Adding "+m+" with context");
74 BDD b;
75 if (V1H1context != null) {
76 b = vP.and(V1H1context);
77 if (PA.VerifyAssertions) {
78 if (!b.exist(pa.V1cH1cset).equals(vP)) {
79 System.out.println("m = "+m);
80 System.out.println("vP = "+vP.toStringWithDomains(pa.TS));
81 System.out.println("V1H1context = "+V1H1context.toStringWithDomains());
82 System.out.println("b = "+b.toStringWithDomains());
83 Assert.UNREACHABLE();
84 }
85 }
86 } else {
87 if (PA.VerifyAssertions) {
88 if ((pa.OBJECT_SENSITIVE || pa.CONTEXT_SENSITIVE) && !vP.isZero()) {
89 System.out.println("m = "+m);
90 System.out.println("vP = "+vP.toStringWithDomains(pa.TS));
91 Assert.UNREACHABLE();
92 }
93 }
94 b = vP.id();
95 }
96 pa.vP.orWith(b);
97 if (V1V2context != null) {
98 if (L.isZero()) L.andWith(pa.V1.domain().and(pa.V2.domain()).and(pa.F.domain()));
99 b = L.and(V1V2context);
100 if (PA.VerifyAssertions) {
101 Assert._assert(b.exist(pa.V1cV2cset).equals(L));
102 }
103 } else {
104 b = L.id();
105 }
106 pa.L.orWith(b);
107 if (V1V2context != null) {
108 if (S.isZero()) S.andWith(pa.V1.domain().and(pa.V2.domain()).and(pa.F.domain()));
109 b = S.and(V1V2context);
110 if (PA.VerifyAssertions) {
111 Assert._assert(b.exist(pa.V1cV2cset).equals(S));
112 }
113 } else {
114 b = S.id();
115 }
116 pa.S.orWith(b);
117 }
118
119 public void free() {
120 if (TRACE) out.println("Freeing "+this.m);
121 vP.free(); vP = null;
122 L.free(); L = null;
123 S.free(); S = null;
124 }
125
126 void addToVP(BDD V_bdd, Node h) {
127 int H_i = pa.Hmap.get(h);
128 BDD bdd1 = pa.H1.ithVar(H_i);
129 bdd1.andWith(V_bdd.id());
130 if (TRACE_RELATIONS) out.println("Adding to vP: "+bdd1.toStringWithDomains(pa.TS));
131 vP.orWith(bdd1);
132 }
133
134 void addToS(BDD V_bdd, jq_Field f, Collection c) {
135 int F_i = pa.Fmap.get(f);
136 BDD F_bdd = pa.F.ithVar(F_i);
137
138 for (Iterator k = c.iterator(); k.hasNext(); ) {
139 Node node2 = (Node) k.next();
140 if (pa.FILTER_NULL && pa.isNullConstant(node2))
141 continue;
142
143 int V2_i = pa.Vmap.get(node2);
144 BDD bdd1 = pa.V2.ithVar(V2_i);
145 bdd1.andWith(F_bdd.id());
146 bdd1.andWith(V_bdd.id());
147 if (TRACE_RELATIONS) out.println("Adding to S: "+bdd1.toStringWithDomains(pa.TS));
148 S.orWith(bdd1);
149 }
150 F_bdd.free();
151 }
152
153 void addToL(BDD V_bdd, jq_Field f, Collection c) {
154 int F_i = pa.Fmap.get(f);
155 BDD F_bdd = pa.F.ithVar(F_i);
156 for (Iterator k = c.iterator(); k.hasNext(); ) {
157 Node node2 = (Node) k.next();
158 int V2_i = pa.Vmap.get(node2);
159 BDD bdd1 = pa.V2.ithVar(V2_i);
160 bdd1.andWith(F_bdd.id());
161 bdd1.andWith(V_bdd.id());
162 if (TRACE_RELATIONS) out.println("Adding to L: "+bdd1.toStringWithDomains(pa.TS));
163 L.orWith(bdd1);
164 }
165 F_bdd.free();
166 }
167
168 public void visitMethod(jq_Method m) {
169 Assert._assert(m != null);
170 Assert._assert(m.getDeclaringClass() != null);
171 if (PA.VerifyAssertions)
172 Assert._assert(!pa.newMethodSummaries.containsKey(m));
173 pa.newMethodSummaries.put(m, this);
174
175 if (TRACE) out.println("Visiting method "+m);
176 m.getDeclaringClass().prepare();
177
178 int M_i = pa.Mmap.get(m);
179 BDD M_bdd = pa.M.ithVar(M_i);
180 pa.addToVisited(M_bdd);
181
182 MethodSummary ms = MethodSummary.getSummary(m);
183
184 if (m.getBytecode() == null && ms == null) {
185
186
187 if(!(m instanceof jq_FakeInstanceMethod || m instanceof jq_FakeStaticMethod)) {
188 jq_Type retType = m.getReturnType();
189 if (retType instanceof jq_Reference) {
190 Node node = UnknownTypeNode.get((jq_Reference) retType);
191 pa.addToMret(M_bdd, node);
192 visitNode(node);
193 }
194 M_bdd.free();
195 } else {
196
197 }
198 return;
199 }
200
201 if (TRACE)
202 out.println("Visiting method summary "+ms);
203
204 if (m.isSynchronized() && !m.isStatic()) {
205 pa.addToSync(ms.getParamNode(0));
206 }
207
208 addToMethodToClass(m);
209 pa.addClassInitializer(ms.getMethod().getDeclaringClass());
210
211
212 int offset;
213 Node thisparam;
214 if (ms.getMethod().isStatic()) {
215 thisparam = GlobalNode.GLOBAL;
216 offset = 0;
217 } else {
218 thisparam = ms.getParamNode(0);
219 offset = 1;
220 }
221 pa.addToFormal(M_bdd, 0, thisparam);
222 int nParams = ms.getNumOfParams();
223 for (int i = offset; i < nParams; ++i) {
224 Node node = ms.getParamNode(i);
225 if (node == null) continue;
226 pa.addToFormal(M_bdd, i+1-offset, node);
227 }
228
229 for (Iterator i = ms.getSyncedVars().iterator(); i.hasNext(); ) {
230 Node node = (Node) i.next();
231 if (TRACE) out.println("Sync on: "+node);
232 pa.addToSync(node);
233 }
234
235 if (m.isSynchronized() && !m.isStatic()) {
236 pa.addToMSync(m);
237 }
238
239
240 for (Iterator i = ms.getCalls().iterator(); i.hasNext(); ) {
241 ProgramLocation mc = (ProgramLocation) i.next();
242 Quad q = ( (ProgramLocation.QuadProgramLocation) mc).getQuad();
243 Operand.MethodOperand methodOp = Operator.Invoke.getMethod(q);
244 if (TRACE) out.println("Visiting call site "+mc);
245 int I_i = pa.Imap.get(LoadedCallGraph.mapCall(mc));
246 BDD I_bdd = pa.I.ithVar(I_i);
247 jq_Method target = mc.getTargetMethod();
248
249 jq_Method replacement = null;
250 if(pa.USE_BOGUS_SUMMARIES) {
251 Operand.ParamListOperand listOp = Operator.Invoke.getParamList(q);
252 jq_Type type = listOp.length() > 0 ? listOp.get(0).getType() : null;
253 replacement = PA.getBogusSummaryProvider().getReplacementMethod(target, type);
254 if(replacement != null) {
255 if(pa.TRACE_BOGUS){
256 System.out.println("Replacing a call to " + target +
257 " with a call to "+ replacement);
258 }
259 jq_Method oldTarget = target;
260 target = replacement;
261
262
263 if(!PA.getBogusSummaryProvider().hasStaticReplacement(replacement)){
264
265
266
267
268
269
270
271
272
273 Assert._assert(methodOp.getMethod() == oldTarget);
274 methodOp.setMethod(replacement);
275
276 if(!replacement.isStatic()){
277 if(listOp.get(0).getType() == oldTarget.getDeclaringClass()){
278 listOp.get(0).setType(replacement.getDeclaringClass());
279 }
280 }
281
282
283
284
285
286
287
288
289
290 }else{
291
292 }
293 }
294 }
295 if (target.isStatic()){
296 pa.addClassInitializer(target.getDeclaringClass());
297 }
298
299 Set thisptr;
300 if( (replacement != null) && PA.getBogusSummaryProvider().hasStaticReplacement(replacement)) {
301 thisptr = Collections.singleton(GlobalNode.GLOBAL);
302 pa.addToActual(I_bdd, 0, thisptr);
303
304
305 offset = 0;
306 } else {
307 if (target.isStatic()) {
308 thisptr = Collections.singleton(GlobalNode.GLOBAL);
309 offset = 0;
310 } else {
311 thisptr = ms.getNodesThatCall(mc, 0);
312 offset = 1;
313 }
314 pa.addToActual(I_bdd, 0, thisptr);
315 }
316
317
318
319 Collection
320 if(pa.USE_REFLECTION_PROVIDER && ReflectionInformationProvider.isNewInstance(target)){
321 targets = PA.getReflectionProvider().getNewInstanceTargets(m);
322 if(targets != null){
323 if(PA.TRACE_REFLECTION) {
324 System.out.println("Replacing a call to " + target + " with " + targets);
325 }
326
327 for(Iterator iter = targets.iterator(); iter.hasNext();){
328 jq_Method newTarget = (jq_Method) iter.next();
329
330 if(newTarget instanceof jq_Initializer){
331 jq_Initializer constructor = (jq_Initializer) newTarget;
332 jq_Type type = constructor.getDeclaringClass();
333
334 Node node = ms.getRVN(mc);
335 if (node != null) {
336 MethodSummary.ConcreteTypeNode h = ConcreteTypeNode.get((jq_Reference) type);
337 int H_i = pa.Hmap.get(h);
338 int V_i = pa.Vmap.get(node);
339 BDD V_arg = pa.V1.ithVar(V_i);
340
341 pa.addToVP(V_arg, h);
342 }
343 }
344
345 if(PA.TRACE_REFLECTION) {
346 System.out.println("Adding a refective call to " + newTarget);
347 }
348 pa.addToMI(M_bdd, I_bdd, newTarget);
349 pa.addToIE(I_bdd, newTarget);
350 }
351 }
352 }
353
354 if ( mc.isSingleTarget() ||
355 (replacement != null && !PA.getBogusSummaryProvider().hasStaticReplacement(replacement)) )
356 {
357 if (target != pa.javaLangObject_clone) {
358
359 addSingleTargetCall(thisptr, mc, I_bdd, target);
360 pa.addToMI(M_bdd, I_bdd, null);
361 } else {
362
363 pa.addToMI(M_bdd, I_bdd, pa.javaLangObject_fakeclone);
364 }
365 } else {
366
367 pa.addToMI(M_bdd, I_bdd, target);
368 boolean isSingleTarget = mc.isSingleTarget();
369 }
370
371 jq_Type[] params = mc.getParamTypes();
372 int k = offset;
373 for ( ; k < params.length; ++k) {
374 if (!params[k].isReferenceType() && k+1-offset < pa.MAX_PARAMS) {
375 pa.addEmptyActual(I_bdd, k+1-offset);
376 continue;
377 }
378 Set s = ms.getNodesThatCall(mc, k);
379 pa.addToActual(I_bdd, k+1-offset, s);
380 }
381 for ( ; k+1-offset < pa.MAX_PARAMS; ++k) {
382 pa.addEmptyActual(I_bdd, k+1-offset);
383 }
384 Node node = ms.getRVN(mc);
385 if (node != null) {
386 pa.addToIret(I_bdd, node);
387
388 } else {
389
390
391
392
393
394
395 }
396 node = ms.getTEN(mc);
397 if (!pa.IGNORE_EXCEPTIONS && node != null) {
398 pa.addToIthr(I_bdd, node);
399 }
400 I_bdd.free();
401 }
402
403 if(pa.RESOLVE_REFLECTION){
404 for (Iterator i = ms.getCalls().iterator(); i.hasNext(); ) {
405 ProgramLocation mc = (ProgramLocation) i.next();
406 if (TRACE) out.println("Visiting call site "+mc);
407 int I_i = pa.Imap.get(LoadedCallGraph.mapCall(mc));
408 BDD I_bdd = pa.I.ithVar(I_i);
409 jq_Method target = mc.getTargetMethod();
410
411 if(ReflectionInformationProvider.isForName(target)){
412 ConcreteTypeNode h = ConcreteTypeNode.get(
413 pa.class_class,
414
415 new Integer(++pa.opn));
416 pa.addToForNameMap(h, I_bdd);
417 if(PA.TRACE_REFLECTION && pa.TRACE){
418 System.out.println("Processing a call to forName: " + mc.getEmacsName());
419 }
420 int H_i = pa.Hmap.get(h);
421 pa.addToVP(ms.getRVN(mc), H_i);
422
423
424 }
425 }
426 }
427
428
429 for (Iterator i = ms.nodeIterator(); i.hasNext(); ) {
430 Node node = (Node) i.next();
431
432 if (pa.FILTER_NULL && pa.isNullConstant(node))
433 continue;
434
435 int V_i = pa.Vmap.get(node);
436 BDD V_bdd = pa.V1.ithVar(V_i);
437 pa.addToMV(M_bdd, V_bdd);
438
439 if (ms.getReturned().contains(node)) {
440 pa.addToMret(M_bdd, V_i);
441 }
442
443 if (!pa.IGNORE_EXCEPTIONS && ms.getThrown().contains(node)) {
444 pa.addToMthr(M_bdd, V_i);
445 }
446
447 visitNode(node);
448 }
449
450 for (Iterator i = ms.getCastMap().entrySet().iterator(); i.hasNext(); ) {
451 Map.Entry e = (Map.Entry)i.next();
452 Node from = (Node)((Pair)e.getKey()).left;
453 CheckCastNode to = (CheckCastNode)e.getValue();
454 int V_i = pa.Vmap.get(to);
455 BDD V_bdd = pa.V1.ithVar(V_i);
456 pa.addToA(V_bdd, pa.Vmap.get(from));
457 }
458 }
459
460 void addToMethodToClass(jq_Method m) {
461 int m_i = pa.Mmap.get(m);
462 BDD m_bdd = pa.M.ithVar(m_i);
463
464 jq_Class c = m.getDeclaringClass();
465 int c_i = pa.Cmap.get(c);
466 BDD c_bdd = pa.C.ithVar(c_i);
467
468
469 BDD t = m_bdd.andWith(c_bdd);
470 pa.mC.orWith(t);
471 }
472
473 void addSingleTargetCall(Set thisptr, ProgramLocation mc, BDD I_bdd, jq_Method target) {
474 if (pa.DUMP_FLY) {
475 BDD bdd1 = I_bdd.id();
476 int M2_i = pa.Mmap.get(target);
477 bdd1.andWith(pa.M2.ithVar(M2_i));
478 IE.orWith(bdd1);
479 } else {
480 pa.addToIE(I_bdd, target);
481 }
482 if (pa.OBJECT_SENSITIVE || pa.CARTESIAN_PRODUCT) {
483 BDD bdd1 = pa.bdd.zero();
484 for (Iterator j = thisptr.iterator(); j.hasNext(); ) {
485 int V_i = pa.Vmap.get(j.next());
486 bdd1.orWith(pa.V1.ithVar(V_i));
487 }
488 bdd1.andWith(I_bdd.id());
489 int M_i = pa.Mmap.get(target);
490 bdd1.andWith(pa.M.ithVar(M_i));
491 if (TRACE_RELATIONS) out.println("Adding single-target call: "+bdd1.toStringWithDomains());
492 pa.staticCalls.orWith(bdd1);
493 }
494 }
495
496 public void visitNode(Node node) {
497 if (TRACE)
498 out.println("Visiting node "+node);
499
500 if (pa.FILTER_NULL && pa.isNullConstant(node))
501 return;
502
503 int V_i = pa.Vmap.get(node);
504 BDD V_bdd = pa.V1.ithVar(V_i);
505
506 if (node instanceof ConcreteTypeNode) {
507 addToVP(V_bdd, node);
508 } else if (node instanceof ConcreteObjectNode ||
509 node instanceof UnknownTypeNode ||
510 node == GlobalNode.GLOBAL)
511 {
512 pa.addToVP(V_bdd, node);
513 } else if (node instanceof GlobalNode) {
514 int V2_i = pa.Vmap.get(GlobalNode.GLOBAL);
515 pa.addToA(V_bdd, V2_i);
516 pa.addToA(V2_i, V_i);
517 }
518
519 for (Iterator j = node.getAllEdges().iterator(); j.hasNext(); ) {
520 Map.Entry e = (Map.Entry) j.next();
521 jq_Field f = (jq_Field) e.getKey();
522 Collection c;
523 if (e.getValue() instanceof Collection)
524 c = (Collection) e.getValue();
525 else
526 c = Collections.singleton(e.getValue());
527 addToS(V_bdd, f, c);
528 }
529
530 for (Iterator j = node.getAccessPathEdges().iterator(); j.hasNext(); ) {
531 Map.Entry e = (Map.Entry) j.next();
532 jq_Field f = (jq_Field) e.getKey();
533 Collection c;
534 if (e.getValue() instanceof Collection)
535 c = (Collection) e.getValue();
536 else
537 c = Collections.singleton(e.getValue());
538 addToL(V_bdd, f, c);
539 if (node instanceof GlobalNode)
540 pa.addClassInitializer(f.getDeclaringClass());
541 }
542 }
543
544 public String toString() {
545 StringBuffer sb = new StringBuffer();
546 sb.append("Method "+m+":");
547 sb.append("\nL = ");
548 sb.append(L.toStringWithDomains(pa.TS));
549 sb.append("\nS = ");
550 sb.append(S.toStringWithDomains(pa.TS));
551 sb.append("\nvP = ");
552 sb.append(vP.toStringWithDomains(pa.TS));
553 sb.append('\n');
554 return sb.toString();
555 }
556
557 public static void main(String[] args) {
558 HostedVM.initialize();
559 CodeCache.AlwaysMap = true;
560 jq_Class c = (jq_Class) jq_Type.parseType(args[0]);
561 c.load();
562 String name = null, desc = null;
563 if (args.length > 1) {
564 name = args[1];
565 if (args.length > 2) {
566 desc = args[2];
567 }
568 }
569 Collection methods;
570 if (name != null) {
571 jq_Method m;
572 if (desc != null) {
573 m = (jq_Method) c.getDeclaredMember(name, desc);
574 } else {
575 m = c.getDeclaredMethod(name);
576 }
577 methods = Collections.singleton(m);
578 } else {
579 methods = new LinkedList();
580 methods.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
581 methods.addAll(Arrays.asList(c.getDeclaredInstanceMethods()));
582 }
583
584 PA pa = new PA();
585 pa.initializeBDD(null);
586 pa.initializeMaps();
587 for (Iterator i = methods.iterator(); i.hasNext(); ) {
588 jq_Method m = (jq_Method) i.next();
589 if (m.getBytecode() == null) continue;
590 PAMethodSummary s = new PAMethodSummary(pa, m);
591 System.out.println(s);
592 }
593 }
594
595 }