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