1
2
3
4 package joeq.Compiler.Analysis.IPA;
5
6 import java.util.AbstractSet;
7 import java.util.ArrayList;
8 import java.util.Arrays;
9 import java.util.Collection;
10 import java.util.Collections;
11 import java.util.HashMap;
12 import java.util.HashSet;
13 import java.util.Iterator;
14 import java.util.LinkedList;
15 import java.util.List;
16 import java.util.Set;
17 import java.util.Stack;
18 import java.util.StringTokenizer;
19 import java.io.DataInput;
20 import java.io.DataInputStream;
21 import java.io.DataOutput;
22 import java.io.DataOutputStream;
23 import java.io.FileInputStream;
24 import java.io.FileOutputStream;
25 import java.io.IOException;
26 import java.io.PrintStream;
27 import java.lang.reflect.Field;
28 import java.lang.reflect.InvocationTargetException;
29 import java.lang.reflect.Method;
30 import java.math.BigInteger;
31 import java.net.URL;
32 import joeq.Class.PrimordialClassLoader;
33 import joeq.Class.jq_Class;
34 import joeq.Class.jq_Field;
35 import joeq.Class.jq_Method;
36 import joeq.Class.jq_NameAndDesc;
37 import joeq.Class.jq_Reference;
38 import joeq.Class.jq_Type;
39 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
40 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.Node;
41 import joeq.Compiler.Analysis.IPA.ProgramLocation.QuadProgramLocation;
42 import joeq.Compiler.Analysis.IPSSA.ContextSet;
43 import joeq.Compiler.Analysis.IPSSA.SSALocation;
44 import joeq.Compiler.Quad.BasicBlock;
45 import joeq.Compiler.Quad.CallGraph;
46 import joeq.Compiler.Quad.CodeCache;
47 import joeq.Compiler.Quad.LoadedCallGraph;
48 import joeq.Compiler.Quad.Operator;
49 import joeq.Compiler.Quad.Quad;
50 import joeq.Compiler.Quad.Operand.RegisterOperand;
51 import joeq.Compiler.Quad.RegisterFactory.Register;
52 import joeq.Main.Driver;
53 import joeq.Main.HostedVM;
54 import joeq.Util.IO.SourceLister;
55 import jwutil.collections.HashWorklist;
56 import jwutil.collections.IndexedMap;
57 import jwutil.collections.LinearSet;
58 import jwutil.collections.Pair;
59 import jwutil.collections.UnmodifiableIterator;
60 import jwutil.console.SimpleInterpreter;
61 import jwutil.graphs.Navigator;
62 import jwutil.graphs.PathNumbering;
63 import jwutil.graphs.SCCPathNumbering;
64 import jwutil.graphs.SCCTopSortedGraph;
65 import jwutil.graphs.SCComponent;
66 import jwutil.graphs.PathNumbering.Range;
67 import jwutil.graphs.SCCPathNumbering.Path;
68 import jwutil.strings.Strings;
69 import jwutil.util.Assert;
70 import net.sf.javabdd.BDD;
71 import net.sf.javabdd.BDDDomain;
72 import net.sf.javabdd.BDDFactory;
73 import net.sf.javabdd.BDDPairing;
74 import net.sf.javabdd.BDDVarSet;
75 import net.sf.javabdd.TypedBDDFactory.TypedBDD;
76 import net.sf.javabdd.TypedBDDFactory.TypedBDDVarSet;
77
78 /***
79 * Records results for pointer analysis. The results can be saved and reloaded.
80 * This class also provides methods to query the results.
81 *
82 * @author John Whaley
83 * @version $Id: PAResults.java 2470 2006-07-17 05:20:48Z joewhaley $
84 */
85 public class PAResults implements PointerAnalysisResults {
86 final PA r;
87
88 CallGraph cg;
89
90 public PAResults(PA pa) {
91 r = pa;
92 }
93
94 public PA getPAResults() {
95 return r;
96 }
97
98 public static void main(String[] args) throws IOException {
99 initialize(null);
100 PAResults r = loadResults(args, null);
101 if (System.getProperty("pa.stats") != null)
102 r.printStats();
103 else
104 r.interactive();
105 }
106
107 public static void initialize(String addToClasspath) {
108
109 CodeCache.AlwaysMap = true;
110 if (PA.USE_JOEQ_CLASSLIBS) {
111 System.setProperty("joeq.classlibinterface", "joeq.ClassLib.pa.Interface");
112 joeq.ClassLib.ClassLibInterface.useJoeqClasslib(true);
113 }
114 HostedVM.initialize();
115
116 if (addToClasspath != null)
117 PrimordialClassLoader.loader.addToClasspath(addToClasspath);
118 }
119
120 public static PAResults loadResults(String[] args, String addToClasspath) throws IOException {
121 String prefix;
122 if (args != null && args.length > 0) {
123 prefix = args[0];
124 String sep = System.getProperty("file.separator");
125 if (!prefix.endsWith(sep))
126 prefix += sep;
127 } else {
128 prefix = "";
129 }
130 String fileName = System.getProperty("pa.results", "pa");
131 String bddfactory = "typed";
132 PAResults r = loadResults(bddfactory, prefix, fileName);
133 return r;
134 }
135
136 public static PAResults loadResults(String bddfactory,
137 String prefix,
138 String fileName) throws IOException {
139 PA pa = PA.loadResults(bddfactory, prefix, fileName);
140 PAResults r = new PAResults(pa);
141 r.loadCallGraph(prefix+"callgraph");
142
143 if (pa.CONTEXT_SENSITIVE || pa.OBJECT_SENSITIVE) {
144 pa.addDefaults();
145 pa.numberPaths(r.cg, pa.ocg, false);
146 }
147 return r;
148 }
149
150 /*** Load call graph from the given file name.
151 */
152 public void loadCallGraph(String fn) throws IOException {
153 cg = new LoadedCallGraph(fn);
154 }
155
156 private HashMap
157 public void storeBDD(String name, TypedBDD bdd1) {
158 storedBDDs.put(name, bdd1);
159 System.out.println("Stored BDD under name `" + name + "'");
160 }
161 public void interactive() {
162 int i = 1;
163 List results = new ArrayList();
164 DataInput in = new DataInputStream(System.in);
165 SimpleInterpreter si = new SimpleInterpreter((URL[])null, storedBDDs);
166 Stack
167 for (;;) {
168 boolean increaseCount = true;
169 int listHowMany = DEFAULT_NUM_TO_PRINT;
170
171 try {
172 if (inputs.isEmpty())
173 System.out.print(i+"> ");
174 String s = in.readLine();
175 if (s == null) {
176 if (inputs.isEmpty())
177 return;
178 in = (DataInput)inputs.pop();
179 continue;
180 }
181 if (!inputs.isEmpty())
182 System.out.println(i+"> "+s);
183 StringTokenizer st = new StringTokenizer(s);
184 if (!st.hasMoreElements()) continue;
185 String command = st.nextToken();
186 if (command.equals("quit") || command.equals("exit")) {
187 break;
188 } else if (command.equals("include")) {
189 inputs.push(in);
190 in = new DataInputStream(new FileInputStream(st.nextToken()));
191 continue;
192 } else if (command.equals("relprod")) {
193 TypedBDD bdd1 = parseBDD(results, st.nextToken());
194 TypedBDD bdd2 = parseBDD(results, st.nextToken());
195 TypedBDDVarSet set = parseBDDset(results, st.nextToken());
196 TypedBDD r = (TypedBDD) bdd1.relprod(bdd2, set);
197 results.add(r);
198 } else if (command.equals("replace")) {
199 TypedBDD bdd = parseBDD(results, st.nextToken());
200 String ps = st.nextToken();
201 BDDPairing pair = parsePairing(ps);
202 if (pair != null) {
203 results.add(bdd.replace(pair));
204 } else {
205 System.out.println("No such pairing: " + ps);
206 increaseCount = false;
207 }
208 } else if (command.equals("restrict")) {
209 TypedBDD bdd1 = parseBDD(results, st.nextToken());
210 TypedBDD r = bdd1;
211 while (st.hasMoreTokens()) {
212 TypedBDD bdd2 = parseBDD(results, st.nextToken());
213 r = (TypedBDD) r.restrict(bdd2);
214 }
215 results.add(r);
216 } else if (command.equals("exist")) {
217 TypedBDD bdd1 = parseBDD(results, st.nextToken());
218 TypedBDD r = bdd1;
219 while (st.hasMoreTokens()) {
220 TypedBDDVarSet set = parseBDDset(results, st.nextToken());
221 r = (TypedBDD) r.exist(set);
222 }
223 results.add(r);
224 } else if (command.equals("diff")) {
225 TypedBDD bdd1 = parseBDD(results, st.nextToken());
226 TypedBDD bdd2 = parseBDD(results, st.nextToken());
227 TypedBDD r = (TypedBDD) bdd1.apply(bdd2, BDDFactory.diff);
228 results.add(r);
229 } else if (command.equals("and")) {
230 TypedBDD bdd1 = parseBDD(results, st.nextToken());
231 TypedBDD bdd2 = parseBDD(results, st.nextToken());
232 TypedBDD r = (TypedBDD) bdd1.and(bdd2);
233 results.add(r);
234 } else if (command.equals("cmp") || command.equals("equals")) {
235 TypedBDD bdd1 = parseBDD(results, st.nextToken());
236 TypedBDD bdd2 = parseBDD(results, st.nextToken());
237 System.out.println(command + " " + bdd1.equals(bdd2));
238 increaseCount = false;
239 } else if (command.equals("or")) {
240 TypedBDD bdd1 = parseBDD(results, st.nextToken());
241 TypedBDD bdd2 = parseBDD(results, st.nextToken());
242 TypedBDD r = (TypedBDD) bdd1.or(bdd2);
243 results.add(r);
244 } else if (command.equals("findpath")) {
245 int m1 = Integer.parseInt(st.nextToken());
246 int m2 = Integer.parseInt(st.nextToken());
247 Path trace = findPath(m1, m2);
248 if (trace != null) {
249 System.out.println(getMethod(m2));
250 printTrace(System.out, trace);
251 } else
252 System.out.println("there is no path from " + getMethod(m1) + " to " + getMethod(m2));
253 increaseCount = false;
254 } else if (command.equals("store")) {
255 String name = st.nextToken();
256 TypedBDD bdd1 = parseBDD(results, st.nextToken());
257 storeBDD(name, bdd1);
258 increaseCount = false;
259 } else if (command.equals("satcount")) {
260 TypedBDD r = parseBDDWithCheck(results, st.nextToken());
261 System.out.println("Domains: " + r.getDomainSet());
262 System.out.println("satCount: " + r.satCount(getDomains(r)));
263 increaseCount = false;
264 } else if (command.equals("showdomains")) {
265 TypedBDD r = parseBDDWithCheck(results, st.nextToken());
266 System.out.println("Domains: " + r.getDomainSet());
267 increaseCount = false;
268 } else if (command.equals("source")) {
269 TypedBDD r = parseBDDWithCheck(results, st.nextToken());
270 int before = st.hasMoreTokens() ? Integer.parseInt(st.nextToken()) : SourceLister.defaultLinesBefore;
271 int after = st.hasMoreTokens() ? Integer.parseInt(st.nextToken()) : SourceLister.defaultLinesAfter;
272 showSource(r, before, after);
273 increaseCount = false;
274 } else if (command.equals("list")) {
275 TypedBDD r = parseBDDWithCheck(results, st.nextToken());
276 results.add(r);
277 listHowMany = st.hasMoreTokens() ? Integer.parseInt(st.nextToken()) : -1;
278 System.out.println("Domains: " + r.getDomainSet());
279 } else if (command.equals("contextvar") || command.equals("stacktracevar")) {
280 int varNum = Integer.parseInt(st.nextToken());
281 Node n = getVariableNode(varNum);
282 if (n == null) {
283 System.out.println("No method for node "+n);
284 } else {
285 jq_Method m = n.getDefiningMethod();
286 Number c = new BigInteger(st.nextToken(), 10);
287 if (m == null) {
288 System.out.println("No method for node "+n);
289 } else {
290 Path trace = ((SCCPathNumbering)r.vCnumbering).getPath(m, c);
291 if (command.equals("stacktracevar")) {
292 System.out.println(m + " called in context #" + c);
293 printTrace(System.out, trace);
294 } else
295 System.out.println(m+" context "+c+":\n"+trace);
296
297 }
298 }
299 increaseCount = false;
300 } else if (command.equals("contextheap") || command.equals("stacktraceheap")) {
301 int varNum = Integer.parseInt(st.nextToken());
302 Node n = (Node) getHeapNode(varNum);
303 if (n == null) {
304 System.out.println("No method for node "+n);
305 } else {
306 jq_Method m = n.getDefiningMethod();
307 Number c = new BigInteger(st.nextToken(), 10);
308 if (m == null) {
309 System.out.println("No method for node "+n);
310 } else {
311 Path trace = ((SCCPathNumbering)r.hCnumbering).getPath(m, c);
312 if (command.equals("stacktraceheap")) {
313 System.out.println(m + " called in context #" + c);
314 printTrace(System.out, trace);
315 } else
316 System.out.println(m+" context "+c+": "+trace);
317 }
318 }
319 increaseCount = false;
320 } else if (command.equals("type")) {
321 jq_Class c = parseClassName(st.nextToken());
322 if (c == null || !c.isLoaded()) {
323 System.out.println("Cannot find class");
324 increaseCount = false;
325 } else {
326 System.out.println("Class: "+c);
327 int k = getTypeIndex(c);
328 results.add(r.T1.ithVar(k));
329 }
330 } else if (command.equals("comparecc")) {
331 jq_Class c = parseClassName(st.nextToken());
332 if (c == null || !c.isLoaded()) {
333 System.out.println("Cannot find class");
334 } else {
335 String methodname = st.nextToken();
336 jq_Method m;
337 if (st.hasMoreTokens()) m = (jq_Method) c.getDeclaredMember(methodname, st.nextToken());
338 else m = c.getDeclaredMethod(methodname);
339 if (m == null || !m.isLoaded()) {
340 System.out.println("Cannot find method");
341 increaseCount = false;
342 } else {
343 compareCallingContexts(m);
344 }
345 }
346 increaseCount = false;
347 } else if (command.equals("method") || command.equals("callsin") || command.equals("summary") || command.equals("params")) {
348 jq_Class c = parseClassName(st.nextToken());
349 if (c == null || !c.isLoaded()) {
350 System.out.println("Cannot find class");
351 increaseCount = false;
352 } else {
353 String methodname = st.nextToken();
354 jq_Method m;
355 if (st.hasMoreTokens()) m = (jq_Method) c.getDeclaredMember(methodname, st.nextToken());
356 else m = c.getDeclaredMethod(methodname);
357 if (m == null || !m.isLoaded()) {
358 System.out.println("Cannot find method");
359 increaseCount = false;
360 } else {
361 if (command.equals("method")) {
362 int k = getMethodIndex(m);
363 int n = getNameIndex(m);
364 System.out.println("Method: "+m+" N("+n+")");
365 if (r.vCnumbering instanceof SCCPathNumbering) {
366 SCComponent scc = ((SCCPathNumbering)r.vCnumbering).getSCC(m);
367 Range range = ((SCCPathNumbering)r.vCnumbering).getRange(m);
368 if (scc != null) {
369 System.out.println("is located in SCC #" + System.identityHashCode(scc)
370 + " of size " + scc.size() + "; context range is " + range);
371 }
372 }
373 results.add(r.M.ithVar(k));
374 } else {
375 MethodSummary ms = MethodSummary.getSummary(CodeCache.getCode(m));
376 if (command.equals("callsin")) {
377 TypedBDD rc = (TypedBDD)r.bdd.zero();
378 for (Iterator j=ms.getCalls().iterator(); j.hasNext(); ) {
379 ProgramLocation mc = (ProgramLocation) j.next();
380 int iidx = getInvokeIndex(mc);
381 if (iidx == -1)
382 System.out.println("callsite not in index: " + mc + " at " + mc.toStringLong());
383 else
384 rc.orWith(r.I.ithVar(iidx));
385 }
386 results.add(rc);
387 }
388 else if (command.equals("params")) {
389 for(int j = 0; j < ms.getNumOfParams(); j++) {
390 Node pn = ms.getParamNode(j);
391 System.out.println("\t" + pn);
392 }
393
394 increaseCount = false;
395 }
396 else {
397 System.out.println(ms);
398 increaseCount = false;
399 }
400 }
401 }
402 }
403 } else if (command.equals("field")) {
404 jq_Class c = parseClassName(st.nextToken());
405 if (c == null || !c.isLoaded()) {
406 System.out.println("Cannot find class");
407 increaseCount = false;
408 } else {
409 jq_Field m = c.getDeclaredField(st.nextToken());
410 if (m == null) {
411 System.out.println("Cannot find field");
412 increaseCount = false;
413 } else {
414 System.out.println("Field: "+m);
415 int k = getFieldIndex(m);
416 results.add(r.F.ithVar(k));
417 }
418 }
419 } else if (command.equals("thread")) {
420 int k = Integer.parseInt(st.nextToken());
421 jq_Method run = null;
422 Iterator j = PA.thread_runs.keySet().iterator();
423 while (--k >= 0) {
424 run = (jq_Method) j.next();
425 }
426 System.out.println(k+": "+run);
427 int x = getMethodIndex(run);
428 results.add(r.M.ithVar(x));
429 } else if (command.equals("threadlocal")) {
430 TypedBDD r = (TypedBDD) getThreadLocalObjects();
431 results.add(r);
432 } else if (command.equals("reachable")) {
433 TypedBDD bdd1 = parseBDD(results, st.nextToken());
434 TypedBDD r = (TypedBDD) getReachableVars(bdd1);
435 results.add(r);
436 } else if (command.equals("usedef")) {
437 TypedBDD bdd1 = parseBDD(results, st.nextToken());
438 BDD r = calculateUseDef(bdd1);
439 results.add(r);
440 } else if (command.equals("printusedef")) {
441 TypedBDD bdd1 = parseBDD(results, st.nextToken());
442 printUseDefChain(bdd1);
443 increaseCount = false;
444 } else if (command.equals("dumpusedef")) {
445 TypedBDD bdd1 = parseBDD(results, st.nextToken());
446 DataOutput out = new DataOutputStream(new FileOutputStream("usedef.dot"));
447 this.defUseGraph(bdd1, false, out);
448 increaseCount = false;
449 } else if (command.equals("defuse")) {
450 TypedBDD bdd1 = parseBDD(results, st.nextToken());
451 BDD r = calculateDefUse(bdd1);
452 results.add(r);
453 } else if (command.equals("dumpdefuse")) {
454 TypedBDD bdd1 = parseBDD(results, st.nextToken());
455 DataOutput out = new DataOutputStream(new FileOutputStream("defuse.dot"));
456 this.defUseGraph(bdd1, true, out);
457 increaseCount = false;
458 } else if (command.equals("encapsulation")) {
459 BDD r = getEncapsulatedHeapObjects();
460 results.add(r);
461 } else if (command.equals("indistinguishable")) {
462 BDD r = findIndistinguishablyTypedObjects();
463 results.add(r);
464 } else if (command.equals("showargs")) {
465 TypedBDD bdd1 = parseBDD(results, st.nextToken());
466 TypedBDD r = showArguments(bdd1);
467 results.add(r);
468 } else if (command.equals("gini")) {
469 computeGini(r.vCnumbering);
470 increaseCount = false;
471 } else if (command.equals("buildsummaries")) {
472 int before = Node.numberOfNodes();
473 for (Iterator ii = r.Mmap.iterator(); ii.hasNext(); ) {
474 jq_Method m = (jq_Method) ii.next();
475 MethodSummary ms = MethodSummary.getSummary(m);
476 }
477 int after = Node.numberOfNodes();
478 System.out.println("before: " + before + " nodes, after: " + after + " nodes.");
479 increaseCount = false;
480 } else if (command.equals("stats")) {
481 printStats();
482 increaseCount = false;
483 } else if (command.equals("help")) {
484 printHelp(results);
485 increaseCount = false;
486 } else {
487 increaseCount = false;
488 if (command.equals("driver"))
489 command = st.nextToken();
490 String []cmds = new String[st.countTokens()+1];
491 cmds[0] = command;
492 for (int j = 1; j < cmds.length; j++)
493 cmds[j] = st.nextToken();
494 si.getStore().put("$paproxy", new PAProxy(r));
495 si.getStore().put("$paresults", this);
496 for (int j = 0; j < cmds.length; j++)
497 j = Driver.processCommand(cmds, j, si);
498 }
499
500 if (increaseCount) {
501 TypedBDD r = (TypedBDD) results.get(i-1);
502 System.out.println(i+" -> "+toString(r, listHowMany));
503 Assert._assert(i == results.size());
504 ++i;
505 }
506 } catch (Exception e) {
507 System.err.println("Error: "+e);
508 e.printStackTrace();
509 increaseCount = false;
510 }
511 }
512 }
513
514 public void printHelp(List results) {
515 System.out.println("BDD manipulation:");
516 System.out.println("relprod b1 b2 bs: relational product of b1 and b2 w.r.t. set bs");
517 System.out.println("replace b1 pair: replace b1 according to pair");
518 System.out.println("restrict b1 b2 (bi)*: restrict b2 to bi in b1");
519 System.out.println("exist b1 bs1 (bsi)*: exist bs2 to bsi in b1");
520 System.out.println("(and|or|diff) b1 b2: compute b1 and|or|diff b2");
521 System.out.println("(equals|cmp) b1 b2: compare bdds b1 and b2");
522 System.out.println("list b1 [#n]: list #n (or all) elements of bdd b1");
523 System.out.println("showdomains b1: show domains of bdd b1");
524 System.out.println("satcount b1: print satcount (restricted by domain)");
525 System.out.println("store name b1: store BDD b1 under name");
526 System.out.println("\nAnalysis Results:");
527 System.out.println("dumpconnect # <fn>: dump heap connectivity graph for heap object # to file fn");
528 System.out.println("dumpallconnect <fn>: dump entire heap connectivity graph to file fn");
529 System.out.println("dumpdefuse b1: dump def/use graph to defuse.dot, bdd must be in V1xV1c");
530 System.out.println("dumpusedef b1: dump use/def graph to usedef.dot, bdd must be in V1xV1c");
531 System.out.println("threadlocal: run escape analysis");
532 System.out.println("stats: print general statistics");
533 System.out.println("contextvar #vidx #cidx: show path in vCnumbering for var #vidx in context #");
534 System.out.println("stacktracevar #vidx #cidx: like contextvar, except print as stacktrace");
535 System.out.println("contextheap #hidx #cidx: show path in hCnumbering for heap obj #hidx in context #");
536 System.out.println("stacktraceheap #hidx #cidx: like contextheap, except print as stacktrace");
537 System.out.println("findpath #from #to: find a path in callgraph from method #from to #to");
538 System.out.println("gini: compute unbiased Gini-coefficient for callgraph and show SCCs");
539 System.out.println("\nProgram Information:");
540 System.out.println("method class name [signature]: lookup method in class, shows M and N indices");
541 System.out.println("callsin class name [signature]: list all call sites in a given method");
542 System.out.println("summary class name [signature]: list method summary for a given method");
543 System.out.println("params class name [signature]: list method parameters for a given method");
544 System.out.println("source bdd [#before [#after]]: show source code surrounding items in bdd");
545 System.out.println("field class name: show information about field name in class");
546 System.out.println("\nHow to use this driver:");
547 System.out.println("include file: execute commands in file");
548 System.out.println("[driver] arg0 arg1 ...: pass args to Main.Driver for interpretation");
549
550 printAvailableBDDs(results);
551 }
552
553 public void printAvailableBDDs(List results) {
554 Collection allbdds = new ArrayList();
555 for (int i = 0; i < r.bdd.numberOfDomains(); ++i)
556 allbdds.add(r.bdd.getDomain(i));
557 Field []f = PA.class.getDeclaredFields();
558 for (int i = 0; i < f.length; i++) {
559 try {
560 if (f[i].getType() == BDD.class && f[i].get(r) != null) {
561 if(i % 12 == 0) {
562
563 allbdds.add("\n" + f[i].getName());
564 } else {
565 allbdds.add(f[i].getName());
566 }
567 }
568 } catch (IllegalAccessException _) { }
569 }
570 f = PAResults.class.getDeclaredFields();
571 for (int i = 0; i < f.length; i++) {
572 try {
573 if (f[i].getType() == BDD.class && f[i].get(this) != null)
574 allbdds.add(f[i].getName());
575 } catch (IllegalAccessException _) { }
576 }
577 if (storedBDDs.size() > 0)
578 allbdds.add("stored BDDs " + (storedBDDs.keySet()) + "\n");
579 if (results.size() >= 1)
580 allbdds.add("and previous results 1.." + (results.size()));
581 System.out.println("\ncurrently known BDDs are " + allbdds);
582 }
583
584 /*** Print a Path as if it were a stacktrace. */
585 public void printTrace(PrintStream out, Path trace) {
586 for (int i = trace.size() - 1; i >= 0; --i) {
587 Object o = trace.get(i);
588 if (o instanceof ProgramLocation) {
589 out.println(" at " + ((ProgramLocation)o).toStringLong());
590 }
591 }
592 }
593
594 /***
595 * Find a path from a method to another method in the callgraph.
596 */
597 Path findPath(int from, int to) {
598 jq_Method fm = getMethod(from);
599 jq_Method tm = getMethod(to);
600 if (fm == null || tm == null)
601 return null;
602
603
604 Navigator ng = cg.getCallSiteNavigator();
605 LinkedList queue = new LinkedList();
606 HashMap prev = new HashMap();
607
608 queue.addLast(fm);
609 prev.put(fm, null);
610 outer:
611 while (queue.size() != 0) {
612 Object f = queue.removeFirst();
613 Collection succ = ng.next(f);
614 Iterator it = succ.iterator();
615 while (it.hasNext()) {
616 Object t = it.next();
617 if (!prev.containsKey(t)) {
618 prev.put(t, f);
619 queue.addLast(t);
620 }
621 if (t == tm)
622 break outer;
623 }
624 }
625
626 if (!prev.containsKey(tm))
627 return null;
628
629 Path rc = new Path(tm);
630 Object f = prev.get(tm);
631 while (f != null) {
632 rc = new Path(f, rc);
633 f = prev.get(f);
634 }
635 return rc;
636 }
637
638 public jq_Class parseClassName(String className) {
639 jq_Class c = (jq_Class) jq_Type.parseType(className);
640 if (c != null) return c;
641 jq_Type[] types = PrimordialClassLoader.loader.getAllTypes();
642 for (int i = 0; i < PrimordialClassLoader.loader.getNumTypes(); ++i) {
643 jq_Type t = types[i];
644 if (t instanceof jq_Class) {
645 c = (jq_Class) t;
646 if (c.getJDKName().endsWith(className))
647 return c;
648 }
649 }
650 return null;
651 }
652
653 public Node getVariableNode(int v) {
654 if (v < 0 || v >= r.Vmap.size())
655 return null;
656 Node n = (Node) r.Vmap.get(v);
657 return n;
658 }
659
660 public int getVariableIndex(Node n) {
661 if (!r.Vmap.contains(n)) return -1;
662 int v = r.Vmap.get(n);
663 return v;
664 }
665
666 public ProgramLocation getInvoke(int v) {
667 if (v < 0 || v >= r.Imap.size())
668 return null;
669 ProgramLocation n = (ProgramLocation) r.Imap.get(v);
670 return n;
671 }
672
673 public int getInvokeIndex(ProgramLocation n) {
674 n = LoadedCallGraph.mapCall(n);
675 if (!r.Imap.contains(n)) return -1;
676 int v = r.Imap.get(n);
677 return v;
678 }
679
680 public Node getHeapNode(int v) {
681 if (v < 0 || v >= r.Hmap.size())
682 return null;
683 Node n = (Node) r.Hmap.get(v);
684 return n;
685 }
686
687 public int getHeapIndex(Node n) {
688 if (!r.Hmap.contains(n)) return -1;
689 int v = r.Hmap.get(n);
690 return v;
691 }
692
693 public jq_Field getField(int v) {
694 if (v < 0 || v >= r.Fmap.size())
695 return null;
696 jq_Field n = (jq_Field) r.Fmap.get(v);
697 return n;
698 }
699
700 public int getFieldIndex(jq_Field m) {
701 if (!r.Fmap.contains(m)) return -1;
702 int v = r.Fmap.get(m);
703 return v;
704 }
705
706 public jq_Reference getType(int v) {
707 if (v < 0 || v >= r.Tmap.size())
708 return null;
709 jq_Reference n = (jq_Reference) r.Tmap.get(v);
710 return n;
711 }
712
713 public int getTypeIndex(jq_Type m) {
714 if (!r.Tmap.contains(m)) return -1;
715 int v = r.Tmap.get(m);
716 return v;
717 }
718
719 public jq_Method getName(int v) {
720 if (v < 0 || v >= r.Nmap.size())
721 return null;
722 jq_Method n = (jq_Method) r.Nmap.get(v);
723 return n;
724 }
725
726 public int getNameIndex(jq_Method m) {
727 if (!r.Nmap.contains(m)) return -1;
728 int v = r.Nmap.get(m);
729 return v;
730 }
731
732 public jq_Method getMethod(int v) {
733 if (v < 0 || v >= r.Mmap.size())
734 return null;
735 jq_Method n = (jq_Method) r.Mmap.get(v);
736 return n;
737 }
738
739 public int getMethodIndex(jq_Method m) {
740 if (!r.Mmap.contains(m)) return -1;
741 int v = r.Mmap.get(m);
742 return v;
743 }
744
745 /*** For a given TypedBDD, return its domains.
746 * This duplicates TypedBDD.getDomains() which for unknown reasons is not public.
747 */
748 TypedBDDVarSet getDomains(TypedBDD b) {
749 TypedBDDVarSet dset = (TypedBDDVarSet) b.getFactory().emptySet();
750 Set domains = b.getDomainSet();
751 for (Iterator i = domains.iterator(); i.hasNext(); ) {
752 BDDDomain d = (BDDDomain) i.next();
753 dset.unionWith(d.set());
754 }
755 return dset;
756 }
757
758 BDDDomain parseDomain(String dom) {
759 for (int i = 0; i < r.bdd.numberOfDomains(); ++i) {
760 if (dom.equals(r.bdd.getDomain(i).getName()))
761 return r.bdd.getDomain(i);
762 }
763 return null;
764 }
765
766 TypedBDD parseBDDWithCheck(List results, String bddname) throws Exception {
767 TypedBDD r = parseBDD(results, bddname);
768 if (r == null) {
769 printAvailableBDDs(results);
770 throw new Exception("No such BDD: " + bddname);
771 }
772 return r;
773 }
774
775 BDDPairing parsePairing(String s) {
776 try {
777 Field f = PA.class.getDeclaredField(s);
778 if (f.getType() == BDDPairing.class) {
779 return (BDDPairing) f.get(r);
780 }
781 } catch (NoSuchFieldException e) {
782 } catch (IllegalArgumentException e) {
783 } catch (IllegalAccessException e) {
784 }
785 return null;
786 }
787
788 private TypedBDD lookupBDDField(String s, Class clazz, Object r) {
789 try {
790 Field f = clazz.getDeclaredField(s);
791 if (f.getType() == BDD.class) {
792 return (TypedBDD) f.get(r);
793 }
794 } catch (NoSuchFieldException e) {
795 } catch (IllegalArgumentException e) {
796 } catch (IllegalAccessException e) {
797 }
798 return null;
799 }
800
801 TypedBDD parseBDD(List a, String s) {
802 int paren_index = s.indexOf('(');
803 if (paren_index > 0) {
804 int close_index = s.indexOf(')');
805 if (close_index <= paren_index) return null;
806 String domainName = s.substring(0, paren_index);
807 BDDDomain dom = parseDomain(domainName);
808 if (dom == null) return null;
809 long index = Long.parseLong(s.substring(paren_index+1, close_index));
810 return (TypedBDD) dom.ithVar(index);
811 }
812 TypedBDD rc = lookupBDDField(s, PA.class, r);
813 if (rc != null)
814 return rc;
815 rc = lookupBDDField(s, PAResults.class, this);
816 if (rc != null)
817 return rc;
818 BDDDomain d = parseDomain(s);
819 if (d != null) {
820 return (TypedBDD) d.domain();
821 }
822 TypedBDD stored = (TypedBDD)storedBDDs.get(s);
823 if (stored != null)
824 return stored;
825 try {
826 int num = Integer.parseInt(s) - 1;
827 if (num >= 0 && num < a.size()) {
828 return (TypedBDD) a.get(num);
829 }
830 } catch (NumberFormatException e) { }
831 if (s.equals("$last"))
832 return (TypedBDD)a.get(a.size()-1);
833 if (s.equals("$one"))
834 return (TypedBDD)r.bdd.one();
835 if (s.equals("$zero"))
836 return (TypedBDD)r.bdd.zero();
837 return null;
838 }
839
840 TypedBDDVarSet parseBDDset(List a, String s) {
841 BDDDomain d = parseDomain(s);
842 if (d != null) {
843 return (TypedBDDVarSet) d.set();
844 }
845 return (TypedBDDVarSet) parseBDD(a, s).toVarSet();
846 }
847
848 public static final int DEFAULT_NUM_TO_PRINT = 10;
849
850 public String toString(TypedBDD b, int numToPrint) {
851 if (b == null) return "<you passed 'null' to PAResult.toString>";
852 if (b.isZero()) return "<empty>";
853 TypedBDDVarSet dset = (TypedBDDVarSet) b.getFactory().emptySet();
854 Set domains = b.getDomainSet();
855 for (Iterator i = domains.iterator(); i.hasNext(); ) {
856 BDDDomain d = (BDDDomain) i.next();
857 dset.unionWith(d.set());
858 }
859 StringBuffer sb = new StringBuffer();
860 int j = 0;
861 for (Iterator i = b.iterator(); i.hasNext(); ++j) {
862 if (numToPrint >= 0 && j > numToPrint - 1) {
863 sb.append("\tand "+((long)b.satCount(dset)-numToPrint)+" others.");
864 sb.append(Strings.lineSep);
865 break;
866 }
867 TypedBDD b1 = (TypedBDD) i.next();
868 sb.append("\t(");
869 sb.append(b1.toStringWithDomains(r.TS));
870 sb.append(')');
871 sb.append(Strings.lineSep);
872 }
873 return sb.toString();
874 }
875
876 /****** COOL OPERATIONS BELOW *****/
877
878 int heapConnectivityQueries;
879 int heapConnectivitySteps;
880 /*** Given a heap object (H1xH1c), calculate the set of heap objects (H1xH1c) that
881 * are reachable by following a chain of access paths.
882 */
883 public BDD calculateHeapConnectivity(BDD h1) {
884 BDD result = r.bdd.zero();
885 BDD h1h2 = r.hP.exist(r.Fset);
886 for (;;) {
887 BDD b = h1.relprod(h1h2, r.H1set);
888 b.replaceWith(r.H2toH1);
889 b.applyWith(result.id(), BDDFactory.diff);
890 result.orWith(b.id());
891 if (b.isZero()) break;
892 h1 = b;
893 ++heapConnectivitySteps;
894 }
895 h1h2.free();
896 ++heapConnectivityQueries;
897 return result;
898 }
899
900 /*** Given a set of types (T2), calculate the tightest common superclass (T2).
901 */
902 public BDD calculateCommonSupertype(BDD types) {
903 if (types.isZero()) return r.bdd.zero();
904 BDD bestTypes = r.T1.domain();
905
906 for (Iterator i = types.iterator(r.T2set); i.hasNext(); ) {
907 BDD b = (BDD) i.next();
908 BDD c = b.relprod(r.aT, r.T2set);
909 b.free();
910 bestTypes.andWith(c);
911 }
912 for (Iterator i = bestTypes.iterator(r.T1set); i.hasNext(); ) {
913 BDD b = (BDD) i.next();
914 BDD c = b.relprod(r.aT, r.T1set);
915 b.free();
916 c.replaceWith(r.T2toT1);
917 c.andWith(bestTypes.id());
918 if (c.satCount(r.T1set) == 1.0) {
919 return c;
920 }
921 }
922 System.out.println("No subtype matches! "+bestTypes.toStringWithDomains(r.TS));
923 return r.bdd.zero();
924 }
925
926 /*** Given a set of uses (V1xV1c), calculate the set of definitions (V1xV1c) that
927 * reach that set of uses. Only does one step at a time; you'll have to iterate
928 * to get the transitive closure.
929 */
930 public BDD calculateUseDef(BDD r_v1) {
931
932 BDD b = r.A.relprod(r_v1, r.V1set);
933 b.replaceWith(r.V2toV1);
934
935 BDD r_v2 = r_v1.replace(r.V1toV2);
936
937 BDD c = r.L.relprod(r_v2, r.V2set);
938 r_v2.free();
939 BDD d = r.vP.relprod(c, r.V1set);
940 c.free();
941 BDD e = r.hP.relprod(d, r.H1Fset);
942 d.free();
943 e.replaceWith(r.H2toH1);
944 BDD f = r.vP.relprod(e, r.H1set);
945
946 e.free();
947 f.orWith(b);
948 return f;
949 }
950
951 /*** Given a set of definitions (V1xV1c), calculate the set of uses (V1xV1c) that
952 * reach that set of definitions. Only does one step at a time; you'll have to
953 * iterate to get the transitive closure.
954 */
955 public BDD calculateDefUse(BDD r_v1) {
956 BDD r_v2 = r_v1.replace(r.V1toV2);
957
958 BDD b = r.A.relprod(r_v2, r.V2set);
959
960
961 BDD c = r.S.relprod(r_v2, r.V2set);
962 r_v2.free();
963 BDD d = r.vP.relprod(c, r.V1set);
964 c.free();
965 BDD e = r.vP.relprod(d, r.H1set);
966 d.free();
967
968 BDD f = r.L.relprod(e, r.V1Fset);
969 f.replaceWith(r.V2toV1);
970
971 f.orWith(b);
972 return f;
973 }
974
975 /*** Output def-use or use-def graph in dot format.
976 */
977 public void defUseGraph(BDD vPrelation, boolean direction, DataOutput out) throws IOException {
978 out.writeBytes("digraph \"");
979 if (direction) out.writeBytes("DefUse");
980 else out.writeBytes("UseDef");
981 out.writeBytes("\" {\n");
982 HashWorklist w = new HashWorklist(true);
983 BDD c = vPrelation.id();
984 int k = -1;
985 Node n = null;
986 for (;;) {
987 while (!c.isZero()) {
988 int k2 = c.scanVar(r.V1).intValue();
989 Node n2 = getVariableNode(k2);
990 if (w.add(n2)) {
991 String name = r.LONG_LOCATIONS ? r.findInMap(r.Vmap, k2) : n2.toString();
992 out.writeBytes("n"+k2+" [label=\""+name+"\"];\n");
993 }
994 if (n != null) {
995 if (direction) {
996 out.writeBytes("n"+k+
997 " -> n"+k2+";\n");
998 } else {
999 out.writeBytes("n"+k2+
1000 " -> n"+k+";\n");
1001 }
1002 }
1003 BDD q = r.V1.ithVar(k2);
1004 q.andWith(r.V1cdomain);
1005 c.applyWith(q, BDDFactory.diff);
1006 }
1007 if (w.isEmpty()) break;
1008 n = (Node) w.pull();
1009 k = getVariableIndex(n);
1010 BDD b = r.V1.ithVar(k);
1011 b.andWith(r.V1cdomain);
1012 c = direction?calculateDefUse(b):calculateUseDef(b);
1013 }
1014 out.writeBytes("}\n");
1015 }
1016
1017 /*** Prints out the chain of use-defs, starting from the given uses (V1xV1c).
1018 */
1019 public void printUseDefChain(BDD vPrelation) {
1020 BDD visited = r.bdd.zero();
1021 vPrelation = vPrelation.id();
1022 for (int k = 1; !vPrelation.isZero(); ++k) {
1023 System.out.println("Step "+k+":");
1024 System.out.println(vPrelation.toStringWithDomains(r.TS));
1025 visited.orWith(vPrelation.id());
1026
1027 BDD b = r.A.relprod(vPrelation, r.V1set);
1028
1029
1030 vPrelation.replaceWith(r.V1toV2);
1031 BDD c = r.L.relprod(vPrelation, r.V2set);
1032 vPrelation.free();
1033 BDD d = r.vP.relprod(c, r.V1set);
1034 c.free();
1035 BDD e = r.hP.relprod(d, r.H1Fset);
1036 d.free();
1037 e.replaceWith(r.H2toH1);
1038 BDD f = r.vP.relprod(e, r.H1set);
1039
1040 e.free();
1041 vPrelation = b;
1042 vPrelation.replaceWith(r.V2toV1);
1043 vPrelation.orWith(f);
1044 vPrelation.applyWith(visited.id(), BDDFactory.diff);
1045 }
1046 }
1047
1048 public void printDefUseChain(BDD vPrelation) {
1049 BDD visited = r.bdd.zero();
1050 vPrelation = vPrelation.id();
1051 for (int k = 1; !vPrelation.isZero(); ++k) {
1052 System.out.println("Step "+k+":");
1053 System.out.println(vPrelation.toStringWithDomains(r.TS));
1054 visited.orWith(vPrelation.id());
1055
1056 BDD b = r.A.relprod(vPrelation, r.V2set);
1057
1058
1059 vPrelation.replaceWith(r.V2toV1);
1060 BDD c = r.L.relprod(vPrelation, r.V1set);
1061 vPrelation.free();
1062 BDD d = r.vP.relprod(c, r.V2set);
1063 c.free();
1064 BDD e = r.hP.relprod(d, r.H2Fset);
1065 d.free();
1066 e.replaceWith(r.H1toH2);
1067 BDD f = r.vP.relprod(e, r.H2set);
1068
1069 e.free();
1070 vPrelation = b;
1071 vPrelation.replaceWith(r.V1toV2);
1072 vPrelation.orWith(f);
1073 vPrelation.applyWith(visited.id(), BDDFactory.diff);
1074 }
1075 }
1076
1077 /*** Starting from a method with a context (MxV1c), calculate the set of
1078 * transitively-reachable variables (V1xV1c).
1079 */
1080 public BDD getReachableVars(BDD method_plus_context0) {
1081
1082 BDD result = r.bdd.zero();
1083 BDD allInvokes = r.mI.exist(r.Nset);
1084 BDD new_m = method_plus_context0.id();
1085 BDDVarSet V2cIset = r.Iset.union(r.V2cset);
1086 BDD IEcs = (r.CONTEXT_SENSITIVE || r.OBJECT_SENSITIVE) ? r.IEcs : r.IE;
1087 for (int k=1; ; ++k) {
1088
1089 BDD vars = new_m.relprod(r.mV, r.Mset);
1090 result.orWith(vars);
1091
1092 BDD invokes = new_m.relprod(allInvokes, r.Mset);
1093 invokes.replaceWith(r.V1ctoV2c);
1094 BDD methods = invokes.relprod(IEcs, V2cIset);
1095 new_m.orWith(methods);
1096 new_m.applyWith(method_plus_context0.id(), BDDFactory.diff);
1097 if (new_m.isZero()) break;
1098 method_plus_context0.orWith(new_m.id());
1099 }
1100 return result;
1101 }
1102
1103 /*** Given a starting method and a context (MxV1c), calculate the transitive mod
1104 * set (H1xH1cxF). */
1105 public BDD getTransitiveModSet(BDD method_plus_context0) {
1106 BDD reachableVars = getReachableVars(method_plus_context0);
1107 BDD stores = r.S.relprod(reachableVars, r.V2set);
1108 BDD result = stores.relprod(r.vP, r.V1set);
1109 return result;
1110 }
1111
1112 /*** Given a starting method and a context (MxV1c), calculate the transitive ref
1113 * set (H1xH1cxF). */
1114 public BDD getTransitiveRefSet(BDD method_plus_context0) {
1115 BDD reachableVars = getReachableVars(method_plus_context0);
1116 BDD loads = r.L.relprod(reachableVars, r.V2set);
1117 BDD result = loads.relprod(r.vP, r.V1set);
1118 return result;
1119 }
1120
1121 /*** Return the set of thread-local objects (H1xH1c).
1122 */
1123 public BDD getThreadLocalObjects() {
1124 jq_NameAndDesc main_nd = new jq_NameAndDesc("main", "([Ljava/lang/String;)V");
1125 jq_Method main = null;
1126 for (Iterator i = r.Mmap.iterator(); i.hasNext(); ) {
1127 jq_Method m = (jq_Method) i.next();
1128 if (main_nd.equals(m.getNameAndDesc())) {
1129 main = m;
1130 System.out.println("Using main() method: "+main);
1131 break;
1132 }
1133 }
1134 BDD allObjects = r.bdd.zero();
1135 BDD sharedObjects = r.bdd.zero();
1136 if (main != null) {
1137 int M_i = r.Mmap.get(main);
1138 BDD m = r.M.ithVar(M_i);
1139 m.andWith(r.V1c[0].ithVar(0));
1140 System.out.println("Main: "+m.toStringWithDomains());
1141 BDD b = getReachableVars(m);
1142 m.free();
1143 System.out.println("Reachable vars: "+b.satCount(r.V1set));
1144 BDD b2 = b.relprod(r.vP, r.V1set);
1145 b.free();
1146 System.out.println("Reachable objects: "+b2.satCount(r.H1set));
1147 allObjects.orWith(b2);
1148 }
1149 for (Iterator i = PA.thread_runs.keySet().iterator(); i.hasNext(); ) {
1150 jq_Method run = (jq_Method) i.next();
1151 int M_i = r.Mmap.get(run);
1152 Set t_runs = (Set) PA.thread_runs.get(run);
1153 if (t_runs == null) {
1154 System.out.println("Unknown run() method: "+run);
1155 continue;
1156 }
1157 Iterator k = t_runs.iterator();
1158 for (int j = 0; k.hasNext(); ++j) {
1159 Node q = (Node) k.next();
1160 BDD m = r.M.ithVar(M_i);
1161 m.andWith(r.V1c[0].ithVar(j));
1162 System.out.println("Thread: "+m.toStringWithDomains()+" Object: "+q);
1163 BDD b = getReachableVars(m);
1164 m.free();
1165 System.out.println("Reachable vars: "+b.satCount(r.V1set));
1166 BDD b2 = b.relprod(r.vP, r.V1set);
1167 b.free();
1168 System.out.println("Reachable objects: "+b2.satCount(r.H1set));
1169 BDD b3 = allObjects.and(b2);
1170 System.out.println("Shared objects: "+b3.satCount(r.H1set));
1171 sharedObjects.orWith(b3);
1172 allObjects.orWith(b2);
1173 }
1174 }
1175
1176 System.out.println("All shared objects: "+sharedObjects.satCount(r.H1set));
1177 allObjects.applyWith(sharedObjects, BDDFactory.diff);
1178 System.out.println("All local objects: "+allObjects.satCount(r.H1set));
1179
1180 return allObjects;
1181 }
1182
1183 BDDDomain H3;
1184 BDDPairing H1toH3, H3toH1;
1185 BDDVarSet H3set;
1186
1187 public void initializeExtraDomains() {
1188 if (H3 == null) {
1189 H3 = r.makeDomain("H3", r.H_BITS);
1190 H1toH3 = r.bdd.makePair(r.H1, H3);
1191 H3toH1 = r.bdd.makePair(H3, r.H1);
1192 H3set = H3.set();
1193 }
1194 }
1195
1196 public BDD getHashcodeTakenVars() {
1197 jq_NameAndDesc nd = new jq_NameAndDesc("hashCode", "()I");
1198 jq_Method m = PrimordialClassLoader.getJavaLangObject().getDeclaredInstanceMethod(nd);
1199 BDD m_bdd = r.M.ithVar(r.Mmap.get(m));
1200 BDD invokes = r.IE.relprod(m_bdd, r.Mset);
1201 invokes.andWith(r.Z.ithVar(0));
1202 System.out.println("Invokes: "+invokes.toStringWithDomains());
1203 BDD bar = r.actual.relprod(invokes, r.Iset.union(r.Zset));
1204 System.out.println("Actual: "+bar.toStringWithDomains());
1205 bar.replaceWith(r.V2toV1);
1206
1207 nd = new jq_NameAndDesc("identityHashCode", "(Ljava/lang/Object;)I");
1208 m = PrimordialClassLoader.getJavaLangSystem().getDeclaredStaticMethod(nd);
1209 m_bdd = r.M.ithVar(r.Mmap.get(m));
1210 invokes = r.IE.relprod(m_bdd, r.Mset);
1211 invokes.andWith(r.Z.ithVar(1));
1212 System.out.println("Invokes: "+invokes.toStringWithDomains());
1213 BDD bar2 = r.actual.relprod(invokes, r.Iset.union(r.Zset));
1214 System.out.println("Actual: "+bar2.toStringWithDomains());
1215 bar2.replaceWith(r.V2toV1);
1216 bar.orWith(bar2);
1217
1218 if (r.CONTEXT_SENSITIVE || r.OBJECT_SENSITIVE) bar.andWith(r.V1c[0].domain());
1219 return bar;
1220 }
1221
1222 public BDD getEncapsulatedHeapObjects() {
1223 initializeExtraDomains();
1224
1225
1226 BDD hP_ci = r.hP.exist(r.H1cH2cset).exist(r.Fset);
1227 BDDVarSet set = r.H1.set().unionWith(r.H2.set());
1228
1229 BDD one_to_one = r.H1.buildEquals(H3).andWith(r.H2.domain());
1230 BDDVarSet my_set = r.H1.set().unionWith(H3.set());
1231
1232 BDD b = hP_ci.replace(H1toH3);
1233 b.andWith(hP_ci.id());
1234
1235 BDD a = b.applyAll(one_to_one, BDDFactory.imp, my_set);
1236 b.free(); one_to_one.free();
1237 a.andWith(hP_ci.id());
1238
1239 System.out.println("Number = "+a.satCount(set));
1240
1241 BDD result = r.bdd.zero();
1242 int count = 0;
1243 for (int i = 0; i < r.Hmap.size(); ++i) {
1244 BDD x = r.H2.ithVar(i);
1245 BDD y = hP_ci.restrict(x);
1246 if (y.satCount(r.H1.set()) == 1.0) {
1247 ++count;
1248 result.orWith(x.and(y));
1249 }
1250 x.free();
1251 y.free();
1252 }
1253
1254 System.out.println("Number = "+result.satCount(set));
1255
1256 if (!a.equals(result)) {
1257 System.out.println("a has extra: "+a.apply(result, BDDFactory.diff).toStringWithDomains());
1258 System.out.println("a is missing: "+result.apply(a, BDDFactory.diff).toStringWithDomains());
1259 }
1260
1261 return result;
1262 }
1263
1264 /*** Compute all types that override equals() */
1265 public TypedBDD typesThatOverrideEquals() {
1266 jq_NameAndDesc equals_nd = new jq_NameAndDesc("equals", "(Ljava/lang/Object;)Z");
1267 jq_Method equals_m = PrimordialClassLoader.getJavaLangObject().getDeclaredInstanceMethod(equals_nd);
1268 BDD n_bdd = r.N.ithVar(getNameIndex(equals_m));
1269 BDD t1 = r.cha.restrict(n_bdd);
1270 BDD t2 = t1.exist(r.Mset);
1271 t1.free();
1272 return (TypedBDD)t2;
1273 }
1274
1275
1276
1277 public BDD findIndistinguishablyTypedObjects() {
1278 initializeExtraDomains();
1279 BDD t = r.hT.replace(H1toH3);
1280 BDD sameType = t.relprod(r.hT, r.T2set);
1281 BDD stringType = r.T2.ithVar(r.Tmap.get(PrimordialClassLoader.getJavaLangString()));
1282 BDD strings = r.hT.restrict(stringType);
1283 BDD same = r.H1.buildEquals(H3);
1284 BDD relationsToCheck = sameType.id();
1285 for (;;) {
1286
1287 relationsToCheck.andWith(r.hP.exist(r.H2Fset));
1288
1289 relationsToCheck.andWith(strings.not());
1290
1291 relationsToCheck.andWith(same.not());
1292
1293 BDD recheck = r.bdd.zero();
1294 int outer = 0;
1295
1296 while (!relationsToCheck.isZero()) {
1297 System.out.print((long)relationsToCheck.satCount(r.H1set.union(H3set))+" relations remaining. \r");
1298 ++outer;
1299 BDD h_a = relationsToCheck.satOne(r.H1set, false);
1300 BDD h1 = h_a.exist(H3set); h_a.free();
1301
1302 BDD foo = relationsToCheck.restrict(h1);
1303 relationsToCheck.applyWith(h1.and(H3.domain()), BDDFactory.diff);
1304
1305 foo.replaceWith(H3toH1);
1306 BDD a1 = r.hP.relprod(h1, r.H1set);
1307 BDD a3 = r.hP.and(foo);
1308
1309 BDD ok = a3.relprod(a1, r.H2Fset);
1310
1311 foo.applyWith(ok, BDDFactory.diff);
1312
1313 if (!foo.isZero()) {
1314 BDD sameType23 = sameType.replace(r.H1toH2);
1315 BDD r1 = a1.relprod(sameType23, r.H2set);
1316 BDD r3 = a3.relprod(sameType23, r.H2set);
1317
1318 ok = r3.relprod(r1, r.Fset.union(H3set));
1319
1320 foo.applyWith(ok, BDDFactory.diff);
1321
1322 if (!foo.isZero()) {
1323
1324 BDD n = foo.replace(H1toH3).and(h1);
1325 n.orWith(h1.replace(H1toH3).and(foo));
1326 sameType.applyWith(n.id(), BDDFactory.diff);
1327 relationsToCheck.applyWith(n.id(), BDDFactory.diff);
1328
1329 recheck.orWith(h1.id());
1330 recheck.orWith(foo.id());
1331 }
1332 }
1333 }
1334
1335
1336 System.out.println("Recheck: "+(long)recheck.satCount(r.H1set)+" ");
1337 if (recheck.isZero()) break;
1338 recheck.replaceWith(r.H1toH2);
1339 BDD checkRelations = recheck.relprod(r.hP, r.H2Fset);
1340 checkRelations.andWith(sameType.id());
1341 relationsToCheck.orWith(checkRelations);
1342 }
1343
1344
1345 BDD iter = sameType.id();
1346 int i = 0;
1347 while (!iter.isZero()) {
1348 ++i;
1349 BDD foo = iter.satOne(r.H1set, false).exist(H3set);
1350 BDD set = sameType.restrict(foo);
1351 set.replaceWith(H3toH1);
1352 System.out.println("Equivalence class "+i+": "+set.toStringWithDomains(r.TS));
1353 iter.applyWith(set.andWith(H3.domain()), BDDFactory.diff);
1354 }
1355 int nObjects = (int) r.hT.exist(r.T2set).satCount(r.H1set);
1356 int nTypes = (int) r.hT.exist(r.H1set).satCount(r.T2set);
1357 System.out.println(nObjects+" objects (of "+nTypes+" different types) put into "+i+" equivalence classes.");
1358 return sameType;
1359 }
1360
1361
1362 public TypedBDD showArguments(TypedBDD isites) {
1363 return (TypedBDD)r.actual.and(isites).replaceWith(r.bdd.makePair(r.V2, r.V1)).and(r.vP);
1364 }
1365
1366 /****** STATISTICS *****/
1367
1368 public void printStats() throws IOException {
1369 System.out.println("Number of types="+r.Tmap.size());
1370 System.out.println("Number of methods="+r.Mmap.size());
1371 int bytecodes = 0;
1372 for (Iterator i = r.Mmap.iterator(); i.hasNext(); ) {
1373 jq_Method m = (jq_Method) i.next();
1374 if (m.getBytecode() != null)
1375 bytecodes += m.getBytecode().length;
1376 }
1377 System.out.println("Number of bytecodes="+bytecodes);
1378 System.out.println("Number of virtual call sites="+r.Imap.size());
1379 System.out.println("Number of virtual call names="+r.Nmap.size());
1380 System.out.println("Number of variables="+r.Vmap.size());
1381 System.out.println("Number of heap objects="+r.Hmap.size());
1382 System.out.println("Number of fields="+r.Fmap.size());
1383
1384
1385 System.out.println("Number of callgraph edges="+r.IE.satCount(r.Iset.union(r.Mset)));
1386
1387 BDD all_v1 = r.vP.exist(r.H1set);
1388 all_v1.orWith(r.A.exist(r.V2set));
1389 all_v1.orWith(r.A.exist(r.V1set).replaceWith(r.V2toV1));
1390 all_v1.orWith(r.L.exist(r.V2Fset));
1391 all_v1.orWith(r.L.exist(r.V1Fset).replaceWith(r.V2toV1));
1392
1393 double v1h1_count = r.vP.satCount(r.V1H1set);
1394
1395 double v1_count = all_v1.satCount(r.V1set);
1396 System.out.println("Points-to: "+v1h1_count+" / "+v1_count+" = "+(double)v1h1_count/v1_count);
1397
1398 BDD all_h1 = r.vP.exist(r.V1set);
1399
1400 double h1fh2_count = r.hP.satCount(r.H1FH2set);
1401 double h1f_count = r.hP.exist(r.H2set).satCount(r.H1Fset);
1402
1403 double h1_count = all_h1.satCount(r.H1set);
1404
1405 System.out.println("Heap object points to (all fields): "+h1fh2_count+" / "+h1_count+" = "+(double)h1fh2_count/h1_count);
1406
1407 {
1408 long heapConnectSum = 0L; int heapConnect = 0;
1409 long heapPointsToSum = 0L; long heapPointsTo = 0L;
1410 for (int i = 0; i < r.Hmap.size() && i < 4000; ++i) {
1411 BDD b = r.H1.ithVar(i);
1412 if (r.CONTEXT_SENSITIVE) b.andWith(r.H1cdomain);
1413 BDD c = calculateHeapConnectivity(b);
1414 heapConnectSum += c.satCount(r.H1set);
1415 ++heapConnect;
1416 c.free();
1417 BDD d = r.hP.relprod(b, r.H1set);
1418 heapPointsToSum += d.satCount(r.H2Fset);
1419 heapPointsTo += d.exist(r.H2set).satCount(r.Fset);
1420 b.free();
1421
1422 }
1423 System.out.println("Heap connectivity: "+heapConnectSum+" / "+heapConnect+" = "+(double)heapConnectSum/heapConnect+" ");
1424 System.out.println("Heap chain length: "+heapConnectivitySteps+" / "+heapConnectivityQueries+" = "+(double)heapConnectivitySteps/heapConnectivityQueries);
1425 System.out.println("Heap points-to, per field: "+heapPointsToSum+" / "+heapPointsTo+" = "+(double)heapPointsToSum/heapPointsTo);
1426 }
1427
1428 {
1429 BDD fh2 = r.hP.exist(r.H1set);
1430 int singleTypeFields = 0, singleObjectFields = 0, unusedFields = 0, refinedTypeFields = 0;
1431 Set polyClasses = new HashSet();
1432 for (int i = 0; i < r.Fmap.size(); ++i) {
1433 BDD b = r.F.ithVar(i);
1434 BDD c = fh2.restrict(b);
1435 if (c.isZero()) {
1436 ++unusedFields;
1437 continue;
1438 }
1439 c.replaceWith(r.H2toH1);
1440 if (c.satCount(r.H1set) == 1.0) {
1441 ++singleObjectFields;
1442 }
1443 BDD d = c.relprod(r.hT, r.H1set);
1444 jq_Field f = (jq_Field) r.Fmap.get(i);
1445 if (d.satCount(r.T2set) == 1.0) {
1446 ++singleTypeFields;
1447 } else {
1448 if (f != null && !f.isStatic()) {
1449 polyClasses.add(f.getDeclaringClass());
1450 }
1451 }
1452 BDD e = calculateCommonSupertype(d);
1453 if (f != null) {
1454 int T_i = r.Tmap.get(f.getType());
1455 BDD g = r.T1.ithVar(T_i);
1456 if (!e.equals(g)) {
1457 e.replaceWith(r.T1toT2);
1458 if (e.andWith(g).and(r.aT).isZero()) {
1459 System.out.println("Field "+f);
1460 System.out.println(" Declared: "+f.getType()+" Computed: "+e.toStringWithDomains(r.TS));
1461 } else {
1462 ++refinedTypeFields;
1463 }
1464 }
1465 g.free();
1466 }
1467 d.free();
1468 e.free();
1469 c.free();
1470 b.free();
1471 }
1472 System.out.println("Refined-type fields: "+refinedTypeFields+" / "+r.Fmap.size()+" = "+(double)refinedTypeFields/r.Fmap.size());
1473 System.out.println("Single-type fields: "+singleTypeFields+" / "+r.Fmap.size()+" = "+(double)singleTypeFields/r.Fmap.size());
1474 System.out.println("Single-object fields: "+singleObjectFields+" / "+r.Fmap.size()+" = "+(double)singleObjectFields/r.Fmap.size());
1475 System.out.println("Unused fields: "+unusedFields+" / "+r.Fmap.size()+" = "+(double)unusedFields/r.Fmap.size());
1476 System.out.println("Poly classes: "+polyClasses.size());
1477
1478 DataOutputStream out = null;
1479 try {
1480 out = new DataOutputStream(new FileOutputStream("polyclasses"));
1481 for (Iterator i = polyClasses.iterator(); i.hasNext(); ) {
1482 jq_Class c = (jq_Class) i.next();
1483 out.writeBytes(c.getJDKName()+"\n");
1484 }
1485 } finally {
1486 if (out != null) out.close();
1487 }
1488 }
1489
1490 if (r.CONTEXT_SENSITIVE) {
1491 System.out.println("Thread-local objects: "+countThreadLocalObjects());
1492 }
1493
1494 {
1495 BDD h1 = this.getHashcodeTakenVars();
1496 BDD h2 = h1.relprod(r.vP, r.V1set);
1497 System.out.println("Hashcode taken objects: "+h2.satCount(r.H1set));
1498 h2 = h2.exist(r.H1cset);
1499 System.out.println("Hashcode taken objects (no context): "+h2.satCount(r.H1.set()));
1500 System.out.println("Hashcode never taken objects (no context): "+(r.Hmap.size()-h2.satCount(r.H1.set())));
1501 }
1502
1503 {
1504 BDD h1 = r.sync;
1505 if (r.CONTEXT_SENSITIVE || r.OBJECT_SENSITIVE) h1.andWith(r.H1cdomain);
1506 BDD h2 = h1.relprod(r.vP, r.V1set);
1507 System.out.println("Locked objects: "+h2.satCount(r.H1set));
1508 h2 = h2.exist(r.H1cset);
1509 System.out.println("Locked objects (no context): "+h2.satCount(r.H1.set()));
1510 System.out.println("Never locked objects (no context): "+(r.Hmap.size()-h2.satCount(r.H1.set())));
1511 }
1512
1513 {
1514 BDD vCalls = r.mI.exist(r.Mset.union(r.Nset));
1515 double d = vCalls.satCount(r.Iset);
1516 System.out.println("Virtual call sites: "+d);
1517 double e = r.IE.satCount(r.IMset);
1518 System.out.println("Average vcall targets = "+e+" / "+d+" = "+e/d);
1519 }
1520
1521 if (false)
1522 {
1523 long sum = 0L; int n = 0;
1524 for (int i = 0; i < r.Vmap.size(); ++i) {
1525 BDD b = r.V1.ithVar(i);
1526 if (r.CONTEXT_SENSITIVE || r.OBJECT_SENSITIVE) b.andWith(r.V1cdomain);
1527 int result = countTransitiveReachingDefs(b);
1528 sum += result;
1529 ++n;
1530 System.out.print("Reaching defs: "+sum+" / "+n+" = "+(double)sum/n+"\r");
1531 }
1532 System.out.println("Reaching defs: "+sum+" / "+n+" = "+(double)sum/n);
1533 }
1534 }
1535
1536 public int countPointsTo(BDD v) {
1537 BDD p = r.vP.relprod(v, r.V1set);
1538 double result = p.satCount(r.H1.set());
1539 return (int) result;
1540 }
1541
1542 public int countTransitiveReachingDefs(BDD vPrelation) {
1543 BDD visited = r.bdd.zero();
1544 vPrelation = vPrelation.id();
1545 for (int k = 1; !vPrelation.isZero(); ++k) {
1546 visited.orWith(vPrelation.id());
1547
1548 BDD b = r.A.relprod(vPrelation, r.V1set);
1549
1550 vPrelation.replaceWith(r.V1toV2);
1551 BDD c = r.L.relprod(vPrelation, r.V2set);
1552 vPrelation.free();
1553 BDD d = r.vP.relprod(c, r.V1set);
1554 c.free();
1555 BDD e = r.hP.relprod(d, r.H1Fset);
1556 d.free();
1557 e.replaceWith(r.H2toH1);
1558 BDD f = r.vP.relprod(e, r.H1set);
1559 e.free();
1560 vPrelation = b;
1561 vPrelation.replaceWith(r.V2toV1);
1562 vPrelation.orWith(f);
1563 vPrelation.applyWith(visited.id(), BDDFactory.diff);
1564 }
1565 double result = visited.satCount(r.V1.set());
1566 return (int) result;
1567 }
1568
1569 public int countThreadLocalObjects() {
1570 BDD b = getThreadLocalObjects();
1571 double result = b.satCount(r.H1set);
1572 return (int) result;
1573 }
1574
1575 /***
1576 * Compute the set of results based on the BDD results.
1577 * */
1578 public Set getCallTargets(QuadProgramLocation invoke) {
1579
1580 ProgramLocation loc = LoadedCallGraph.mapCall(invoke); invoke = null;
1581
1582 if(loc.isSingleTarget()) {
1583 Set result = new LinearSet();
1584 result.add(loc.getTargetMethod());
1585
1586
1587 return result;
1588 }else
1589 if(!r.Imap.contains(loc)){
1590 System.err.println("No call information about " + loc.toString());
1591 return new LinearSet();
1592 }
1593
1594 BDD t1 = r.actual.restrict(r.Z.ithVar(0));
1595 t1.replaceWith(r.bdd.makePair(r.V2, r.V1));
1596 BDD t2 = r.mI.exist(r.Mset);
1597 BDD t3 = t1.and(t2);
1598 t1.free(); t2.free();
1599 BDD t4 = t3.relprod(r.vP, r.V1set);
1600 BDD t5 = t4.relprod(r.hT, r.H1set);
1601 t4.free();
1602 BDD t6 = t5.relprod(r.cha, r.T2Nset);
1603 t5.free();
1604
1605 r.IE.orWith(t6.id());
1606
1607 BDD t7;
1608 if ((r.CONTEXT_SENSITIVE || r.THREAD_SENSITIVE)) {
1609
1610 t6.andWith(r.IEfilter.id());
1611 r.IEcs.orWith(t6.id());
1612 t7 = t6.exist(r.V1cV2cset);
1613 t6.free();
1614 }else {
1615 t7 = t6;
1616 }
1617
1618
1619 int oldSize = r.Imap.size();
1620
1621 int I_idx = r.Imap.get(loc);
1622
1623 BDD isite = r.I.ithVar(I_idx);
1624
1625
1626 t7.restrictWith(isite);
1627
1628 System.err.println(((TypedBDD)t7).getDomainSet().toString() + ": " + t7.satCount());
1629
1630
1631
1632 return new PACallGraph.BDDSet(t7, r.M, r.Mmap);
1633 }
1634
1635 public Set getCallTargets2(ProgramLocation invoke) {
1636 Collection c = this.cg.getTargetMethods(invoke);
1637
1638 return new HashSet(c);
1639 }
1640
1641 public Set mod(QuadProgramLocation invoke, BasicBlock bb) {
1642 if (invoke.isCall()) {
1643 ProgramLocation loc = LoadedCallGraph.mapCall(invoke);
1644
1645 if(!r.Imap.contains(loc)){
1646
1647 return null;
1648 }
1649 int I_i = r.Imap.get(loc);
1650 BDD i = r.I.ithVar(I_i);
1651 BDD m_c = r.IEcs.relprod(i, r.V2cset.union(r.Iset));
1652
1653 BDD s = getTransitiveModSet(m_c);
1654 BDD q = s.exist(r.H1cset);
1655
1656 return new HeapLocationSet(q);
1657 } else {
1658
1659 jq_Method m = invoke.getMethod();
1660 Quad q = ((QuadProgramLocation) invoke).getQuad();
1661 Assert._assert(bb != null);
1662
1663 return mod(m, bb, q);
1664 }
1665 }
1666
1667 public Set ref(QuadProgramLocation invoke, BasicBlock bb) {
1668 if (invoke.isCall()) {
1669 ProgramLocation loc = LoadedCallGraph.mapCall(invoke);
1670
1671 if(!r.Imap.contains(loc)){
1672
1673 return null;
1674 }
1675 int I_i = r.Imap.get(invoke);
1676 BDD i = r.I.ithVar(I_i);
1677 BDD m_c = r.IEcs.relprod(i, r.V2cset.union(r.Iset));
1678 BDD s = getTransitiveRefSet(m_c);
1679 BDD q = s.exist(r.H1cset);
1680
1681 return new HeapLocationSet(q);
1682 }else {
1683
1684
1685
1686
1687
1688
1689
1690
1691 return null;
1692 }
1693 }
1694
1695 public Set mod(jq_Method m, BasicBlock bb, Quad quad) {
1696 MethodSummary ms = MethodSummary.getSummary(CodeCache.getCode(m));
1697 Register reg;
1698 jq_Field f;
1699 if (quad.getOperator() instanceof Operator.AStore) {
1700 reg = ((RegisterOperand) Operator.AStore.getBase(quad)).getRegister();
1701 f = null;
1702 } else {
1703 Assert._assert(quad.getOperator() instanceof Operator.Putfield);
1704 reg = ((RegisterOperand) Operator.Putfield.getBase(quad)).getRegister();
1705 f = Operator.Putfield.getField(quad).getField();
1706 }
1707 Collection c = ms.getRegisterAtLocation(bb, quad, reg);
1708 BDD b = r.bdd.zero();
1709 for (Iterator i = c.iterator(); i.hasNext(); ) {
1710 Node n = (Node) i.next();
1711 Assert._assert(r.Vmap.contains(n));
1712 int V_i = r.Vmap.get(n);
1713 b.orWith(r.V1.ithVar(V_i));
1714 }
1715 b.andWith(r.V1cdomain);
1716 BDD s = r.vP.relprod(b, r.V1set);
1717 BDD q = s.exist(r.H1cset);
1718 q.andWith(r.F.ithVar(r.Fmap.get(f)));
1719 return new HeapLocationSet(q);
1720 }
1721
1722 public boolean isAliased(SSALocation a, SSALocation b) {
1723
1724
1725 return a.equals(b);
1726 }
1727
1728
1729
1730
1731 public Set
1732 return Collections.EMPTY_SET;
1733 }
1734
1735
1736
1737
1738 public boolean hasAliases(jq_Method method, SSALocation loc, ContextSet contextSet) {
1739 return false;
1740 }
1741
1742
1743
1744
1745 public boolean hasAliases(jq_Method method, SSALocation loc) {
1746 return false;
1747 }
1748
1749 public class HeapLocationSet extends AbstractSet {
1750
1751 BDD heapLocations;
1752
1753 HeapLocationSet(BDD b) {
1754 this.heapLocations = b;
1755 }
1756
1757
1758
1759
1760 public int size() {
1761 return (int) heapLocations.satCount(r.H1.set().union(r.Fset));
1762 }
1763
1764
1765
1766
1767 public Iterator iterator() {
1768 final Iterator i = heapLocations.iterator(r.H1.set().union(r.Fset));
1769 return new UnmodifiableIterator() {
1770 public boolean hasNext() {
1771 return i.hasNext();
1772 }
1773 public Object next() {
1774 BDD b = (BDD) i.next();
1775 int h = b.scanVar(r.H1).intValue();
1776 int f = b.scanVar(r.F).intValue();
1777 Node hn = (Node) r.Hmap.get(h);
1778 jq_Field fn = (jq_Field) r.Fmap.get(f);
1779 return new HeapLocation(hn, fn);
1780 }
1781 };
1782 }
1783
1784 }
1785
1786 public static class HeapLocation implements SSALocation {
1787 Node n;
1788 jq_Field f;
1789
1790 public static class FACTORY {
1791 static HashMap _locationMap;
1792 HeapLocation createHeapLocation(Node n, jq_Field f){
1793 Pair pair = new Pair(n, f);
1794 HeapLocation loc = (HeapLocation) _locationMap.get(pair);
1795 if(loc == null){
1796 loc = new HeapLocation(n, f);
1797 _locationMap.put(pair, loc);
1798 }
1799 return loc;
1800 }
1801 }
1802
1803 private HeapLocation(Node n, jq_Field f) {
1804 this.n = n;
1805 this.f = f;
1806
1807 Assert._assert(n != null);
1808 }
1809
1810 public boolean equals(HeapLocation o) {
1811 return n.equals(o.n) && f == o.f;
1812 }
1813
1814 public boolean equals(Object o) {
1815 return equals((HeapLocation) o);
1816 }
1817
1818 public int hashCode() {
1819 int x = n.hashCode();
1820 if (f != null) x ^= f.hashCode();
1821 return x;
1822 }
1823
1824 public String toString() {
1825 String fname = (f == null) ? "[]" : "."+f.getName().toString();
1826 return n.toString_short()+fname;
1827 }
1828
1829 public String toString(PA r) {
1830 String fname = (f == null) ? "[]" : "."+f.getName().toString();
1831
1832
1833 return r.longForm(n) + fname;
1834 }
1835 }
1836
1837 /***
1838 * Given a typedbdd that contains variables, callsites, or heap objects,
1839 * display the source code for each item.
1840 *
1841 * Works for ProgramLocations (callsites), but only for those variable and heap
1842 * nodes that have implemented getLocation() methods.
1843 *
1844 * @see joeq.Util.IO.SourceLister
1845 */
1846 public void showSource(TypedBDD b, final int before, final int after) {
1847 final PA fr = r;
1848
1849 final SourceLister sourceLister = new SourceLister();
1850
1851 BDD.BDDToString ts = new BDD.BDDToString() {
1852 String findInMap(IndexedMap map, int i) {
1853 if (i >= map.size())
1854 return "not in map\n";
1855 Object o = map.get(i);
1856 if (o instanceof ProgramLocation)
1857 return sourceLister.list((ProgramLocation)o, true, before, after);
1858 else {
1859 Class c = o.getClass();
1860 try {
1861 Method m = c.getMethod("getLocation", new Class[] {});
1862 ProgramLocation pl = (ProgramLocation)m.invoke(o, null);
1863 if (pl != null)
1864 return sourceLister.list(pl,
1865 } catch (NoSuchMethodException _) {
1866 } catch (InvocationTargetException _) {
1867 } catch (IllegalAccessException _) {
1868 }
1869 }
1870 return "no source available for "+o+"\n";
1871 }
1872 public String elementName(int i, long j) {
1873 String n = j+"\n";
1874 switch (i) {
1875 case 0:
1876 case 1: return n+findInMap(fr.Vmap, (int)j);
1877 case 2: return n+findInMap(fr.Imap, (int)j);
1878 case 3:
1879 case 4: return n+findInMap(fr.Hmap, (int)j);
1880 default: return n+"does not implement map index#"+i+"\n";
1881 }
1882 }
1883 public String elementNames(int i, long j, long k) {
1884 return "big sets not implemented";
1885 }
1886 };
1887
1888 for (Iterator i = b.iterator(); i.hasNext(); ) {
1889 TypedBDD bb = (TypedBDD)i.next();
1890 System.out.println(bb.toStringWithDomains(ts));
1891 }
1892 }
1893
1894 /***
1895 * Compute coefficient of concentration of SCC-sizes for given path numbering.
1896 * 0 means there is no SCC of size greater than 1.
1897 * 1 mean all nodes are in one SCC.
1898 */
1899 public void computeGini(PathNumbering pn) {
1900 if (!(pn instanceof SCCPathNumbering)) {
1901 System.out.println(pn.getClass() + " is not using a SCC numbering");
1902 return;
1903 }
1904 SCCTopSortedGraph graph = ((SCCPathNumbering)pn).getSCCGraph();
1905 List sccs = graph.list();
1906 int []sccs_sizes = new int[sccs.size()];
1907 int n = 0;
1908 for (int i = 0; i < sccs.size(); i++) {
1909 SCComponent scc = (SCComponent)sccs.get(i);
1910 sccs_sizes[i] = scc.size();
1911 n += scc.size();
1912 }
1913 int x[] = new int[n];
1914 Arrays.sort(sccs_sizes);
1915 System.arraycopy(sccs_sizes, 0, x, n - sccs_sizes.length, sccs_sizes.length);
1916 double gini = 0.0;
1917
1918 for (int i = 0; i < n; i++) {
1919 gini += (2*(i+1)-n-1)*x[i];
1920 }
1921
1922 gini = gini / n / (n - 1);
1923
1924 System.out.println("Gini-Coefficient is " + gini);
1925 int PRINTMAX = 20;
1926 System.out.print(PRINTMAX + " largest SCCs are :");
1927 for (int i = sccs_sizes.length - 1; i>=0 && i>sccs_sizes.length-1-PRINTMAX; --i) {
1928 System.out.print(" " + sccs_sizes[i]);
1929 }
1930 System.out.println();
1931 }
1932
1933 public void compareCallingContexts(jq_Method m) {
1934
1935 int m_i = getMethodIndex(m);
1936 System.out.println("Calls to method "+m);
1937 BDD m_bdd = r.M.ithVar(m_i);
1938 BDD b = r.IEcs.restrict(m_bdd);
1939 BDD c = b.exist(r.V1cV2cset);
1940 for (Iterator i = c.iterator(r.Iset); i.hasNext(); ) {
1941 BDD i_bdd = (BDD) i.next();
1942 int i_i = i_bdd.scanVar(r.I).intValue();
1943 ProgramLocation invoke = getInvoke(i_i);
1944 System.out.println(" Call site "+i_i+": "+invoke);
1945 BDD d = b.exist(r.Iset);
1946 BDD e = d.exist(r.V2cset);
1947
1948 MethodSummary ms = MethodSummary.getSummary(m);
1949 for (int j = 0; j < ms.getNumOfParams(); ++j) {
1950 Node pn = ms.getParamNode(j);
1951 if (pn == null) continue;
1952 int p_i = getVariableIndex(pn);
1953 BDD f = r.V1.ithVar(p_i);
1954 f.andWith(e.id());
1955 BDD g = r.vP.relprod(f, r.V1set);
1956 BDD h = g.exist(r.H1cset);
1957 System.out.println(" Param "+j+": ");
1958 for (Iterator z = g.iterator(r.H1.set()); z.hasNext(); ) {
1959 BDD x = (BDD) z.next();
1960 int heap_i = x.scanVar(r.H1).intValue();
1961 Node heap = getHeapNode(heap_i);
1962 System.out.println(" "+heap);
1963 }
1964 }
1965 }
1966 }
1967
1968 /***
1969 * Generic z-statistic stuff.
1970 * Default p0. Set with set Compiler.Analysis.PAResults.p0 0.5
1971 */
1972 public static double p0 = 0.85;
1973
1974 public static double zcompute(double e1, double c1, double p_0) {
1975 double p_hat, q_0, n;
1976
1977 q_0 = 1. - p_0;
1978 n = e1 + c1;
1979 p_hat = e1 / n;
1980 return (p_hat - p_0) / Math.sqrt((p_0 * q_0) / n);
1981 }
1982
1983 public static double zcompute(double e1, double c1) {
1984 return zcompute(e1, c1, p0);
1985 }
1986
1987 public CallGraph getCallGraph() {
1988 return this.cg;
1989 }
1990 }