1
2
3
4 package joeq.Compiler.Analysis.FlowInsensitive;
5
6 import java.io.BufferedWriter;
7 import java.io.FileOutputStream;
8 import java.io.IOException;
9 import java.io.OutputStreamWriter;
10 import java.io.PrintStream;
11 import java.util.ArrayList;
12 import java.util.Arrays;
13 import java.util.Collection;
14 import java.util.Collections;
15 import java.util.HashMap;
16 import java.util.HashSet;
17 import java.util.Iterator;
18 import java.util.LinkedHashMap;
19 import java.util.LinkedHashSet;
20 import java.util.LinkedList;
21 import java.util.List;
22 import java.util.Map;
23 import java.util.Set;
24 import java.util.StringTokenizer;
25 import joeq.Class.PrimordialClassLoader;
26 import joeq.Class.jq_Array;
27 import joeq.Class.jq_Class;
28 import joeq.Class.jq_FakeInstanceMethod;
29 import joeq.Class.jq_FakeStaticMethod;
30 import joeq.Class.jq_Field;
31 import joeq.Class.jq_InstanceField;
32 import joeq.Class.jq_Member;
33 import joeq.Class.jq_Method;
34 import joeq.Class.jq_Reference;
35 import joeq.Class.jq_StaticField;
36 import joeq.Class.jq_Type;
37 import joeq.Class.jq_Reference.jq_NullType;
38 import joeq.Compiler.Analysis.IPA.LoopAnalysis;
39 import joeq.Compiler.Analysis.IPA.ProgramLocation;
40 import joeq.Compiler.Analysis.IPA.ProgramLocation.FakeProgramLocation;
41 import joeq.Compiler.Analysis.IPA.ProgramLocation.QuadProgramLocation;
42 import joeq.Compiler.Quad.BasicBlock;
43 import joeq.Compiler.Quad.CodeCache;
44 import joeq.Compiler.Quad.ControlFlowGraph;
45 import joeq.Compiler.Quad.ControlFlowGraphVisitor;
46 import joeq.Compiler.Quad.ExceptionHandler;
47 import joeq.Compiler.Quad.JSRInfo;
48 import joeq.Compiler.Quad.Operand;
49 import joeq.Compiler.Quad.Operator;
50 import joeq.Compiler.Quad.Quad;
51 import joeq.Compiler.Quad.QuadVisitor;
52 import joeq.Compiler.Quad.RegisterFactory;
53 import joeq.Compiler.Quad.BytecodeToQuad.jq_ReturnAddressType;
54 import joeq.Compiler.Quad.Operand.AConstOperand;
55 import joeq.Compiler.Quad.Operand.Const4Operand;
56 import joeq.Compiler.Quad.Operand.PConstOperand;
57 import joeq.Compiler.Quad.Operand.ParamListOperand;
58 import joeq.Compiler.Quad.Operand.RegisterOperand;
59 import joeq.Compiler.Quad.Operator.ALoad;
60 import joeq.Compiler.Quad.Operator.AStore;
61 import joeq.Compiler.Quad.Operator.Binary;
62 import joeq.Compiler.Quad.Operator.CheckCast;
63 import joeq.Compiler.Quad.Operator.Getfield;
64 import joeq.Compiler.Quad.Operator.Getstatic;
65 import joeq.Compiler.Quad.Operator.Invoke;
66 import joeq.Compiler.Quad.Operator.Jsr;
67 import joeq.Compiler.Quad.Operator.Monitor;
68 import joeq.Compiler.Quad.Operator.Move;
69 import joeq.Compiler.Quad.Operator.New;
70 import joeq.Compiler.Quad.Operator.NewArray;
71 import joeq.Compiler.Quad.Operator.Phi;
72 import joeq.Compiler.Quad.Operator.Putfield;
73 import joeq.Compiler.Quad.Operator.Putstatic;
74 import joeq.Compiler.Quad.Operator.Return;
75 import joeq.Compiler.Quad.Operator.Special;
76 import joeq.Compiler.Quad.Operator.Unary;
77 import joeq.Compiler.Quad.RegisterFactory.Register;
78 import joeq.Compiler.Quad.SSA.EnterSSA;
79 import joeq.Main.HostedVM;
80 import joeq.Memory.Address;
81 import joeq.Memory.StackAddress;
82 import joeq.Runtime.Reflection;
83 import joeq.Runtime.TypeCheck;
84 import jwutil.collections.CollectionTestWrapper;
85 import jwutil.collections.Filter;
86 import jwutil.collections.FilterIterator;
87 import jwutil.collections.FlattenedCollection;
88 import jwutil.collections.HashCodeComparator;
89 import jwutil.collections.IdentityHashCodeWrapper;
90 import jwutil.collections.IndexMap;
91 import jwutil.collections.InstrumentedSetWrapper;
92 import jwutil.collections.MultiMap;
93 import jwutil.collections.Pair;
94 import jwutil.collections.SetFactory;
95 import jwutil.collections.SortedArraySet;
96 import jwutil.collections.Triple;
97 import jwutil.graphs.Navigator;
98 import jwutil.io.Textualizable;
99 import jwutil.io.Textualizer;
100 import jwutil.strings.Strings;
101 import jwutil.util.Assert;
102
103 /***
104 * MethodSummary
105 *
106 * @author John Whaley
107 * @version $Id: MethodSummary.java 2465 2006-06-07 23:03:17Z joewhaley $
108 */
109 public class MethodSummary {
110
111 public static PrintStream out = System.out;
112 public static
113 public static
114 public static
115 public static
116 public static final boolean IGNORE_INSTANCE_FIELDS = false;
117 public static final boolean IGNORE_STATIC_FIELDS = false;
118 public static final boolean VERIFY_ASSERTIONS = false;
119
120 public static boolean SSA = System.getProperty("ssa") != null;
121
122 public static final boolean USE_IDENTITY_HASHCODE = false;
123 public static final boolean DETERMINISTIC = !USE_IDENTITY_HASHCODE && true;
124
125 public static final boolean SPLIT_THREADS = true;
126
127 public static Set ssaEntered = new HashSet();
128 public static Map stringNodes2Values = new HashMap();
129
130 /***
131 * Helper class to output method summary in dot graph format.
132 * @author jwhaley
133 */
134 public static final class MethodSummaryBuilder implements ControlFlowGraphVisitor {
135 public void visitCFG(ControlFlowGraph cfg) {
136 MethodSummary s = getSummary(cfg);
137
138 try {
139 BufferedWriter dos = new BufferedWriter(new OutputStreamWriter(System.out));
140 s.dotGraph(dos);
141 } catch (IOException x) {
142 x.printStackTrace();
143 }
144 }
145 }
146
147 /***
148 * Holds the cache of method summary graphs.
149 */
150 public static HashMap summary_cache = new HashMap();
151
152 /***
153 * Get the method summary for the given CFG. Builds and caches it if it doesn't
154 * already exist.
155 *
156 * @param cfg
157 * @return summary for the given CFG
158 */
159 public static MethodSummary getSummary(ControlFlowGraph cfg) {
160 MethodSummary s = (MethodSummary) summary_cache.get(cfg);
161 if (s == null) {
162 if (TRACE_INTER) out.println("vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv");
163 if (TRACE_INTER) out.println("Building summary for "+cfg.getMethod());
164 try {
165 BuildMethodSummary b = new BuildMethodSummary(cfg);
166 s = b.getSummary();
167 } catch (RuntimeException t) {
168 System.err.println("Runtime exception when getting method summary for "+cfg.getMethod());
169 throw t;
170 } catch (Error t) {
171 System.err.println("Error when getting method summary for "+cfg.getMethod());
172 throw t;
173 }
174 summary_cache.put(cfg, s);
175 if (TRACE_INTER) out.println("Summary for "+cfg.getMethod()+":");
176 if (TRACE_INTER) out.println(s);
177 if (TRACE_INTER) out.println("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^");
178 if (TRACE_DOT) {
179 try {
180 BufferedWriter dos = new BufferedWriter(new OutputStreamWriter(
181 new FileOutputStream("out.txt", true)));
182 dos.write("Method summary for " + s.getMethod() + "\n");
183 s.dotGraph(dos);
184 dos.flush();
185 dos.close();
186 } catch (IOException x) {
187 x.printStackTrace();
188 }
189 }
190 }
191
192 return s;
193 }
194
195 /***
196 * Get the method summary for the given method.
197 * If we know how to fake a method summary, do so.
198 *
199 * @return null if method has no bytecode and we do not know how to fake it
200 */
201 public static MethodSummary getSummary(jq_Method m) {
202 if(m instanceof jq_FakeStaticMethod || m instanceof jq_FakeInstanceMethod) {
203 return null;
204 }
205 MethodSummary hasFake = fakeMethodSummary(m);
206 if (hasFake != null)
207 return hasFake;
208
209 if (m.getBytecode() == null) {
210 return null;
211 }
212
213
214
215
216
217
218
219
220
221 ControlFlowGraph cfg = CodeCache.getCode(m);
222 if (SSA & !ssaEntered.contains(cfg)) {
223
224
225 if (SSA) new EnterSSA().visitCFG(cfg);
226
227
228 ssaEntered.add(cfg);
229 }
230 return getSummary(cfg);
231 }
232
233 /***
234 * Clear the method summary graph.
235 */
236 public static void clearSummaryCache() {
237 summary_cache.clear();
238 ConcreteTypeNode.FACTORY.clear();
239 ConcreteTypeNode.FACTORY2.clear();
240 ConcreteObjectNode.FACTORY.clear();
241 UnknownTypeNode.FACTORY.clear();
242 ReturnValueNode.FACTORY.clear();
243 ThrownExceptionNode.FACTORY.clear();
244 FieldNode.FACTORY.clear();
245 GlobalNode.FACTORY.clear();
246 GlobalNode.GLOBAL = GlobalNode.get((jq_Method) null);
247 }
248
249 /*** Cache of cloned method summaries. */
250 public static HashMap clone_cache;
251
252 /*** Get the (context-sensitive) method summary for the given control flow graph
253 * when called from the given call site. If clone_cache is null, falls back to
254 * the context-insensitive version.
255 *
256 * @param cfg
257 * @param cs
258 * @return summary for the given CFG and context
259 */
260 public static MethodSummary getSummary(ControlFlowGraph cfg, CallSite cs) {
261 if (clone_cache != null) {
262
263 MethodSummary ms = (MethodSummary) clone_cache.get(new Pair(cfg, cs));
264 if (ms != null) {
265
266 return ms;
267 }
268 }
269 return getSummary(cfg);
270 }
271
272 /*** Visitor class to build an intramethod summary. */
273 public static final class BuildMethodSummary extends QuadVisitor.EmptyVisitor {
274
275 /*** The method that we are building a summary for. */
276 protected final jq_Method method;
277 /*** The register factory. */
278 protected final RegisterFactory rf;
279 /*** The parameter nodes. */
280 protected final ParamNode[] param_nodes;
281 /*** The global node. */
282 protected final GlobalNode my_global;
283 /*** The start states of the iteration. */
284 protected final State[] start_states;
285 /*** The set of returned and thrown nodes. */
286 protected final Set returned, thrown;
287 /*** The set of method calls made. */
288 protected final Set methodCalls;
289 /*** Map from a method call to its ReturnValueNode. */
290 protected final HashMap callToRVN;
291 /*** Map from a method call to its ThrownExceptionNode. */
292 protected final HashMap callToTEN;
293 /*** Map from a (Node,Quad) pair to the node it's cast to. */
294 protected final LinkedHashMap castMap;
295 /*** Set of nodes that lead to a cast. */
296 protected final LinkedHashSet castPredecessors;
297 /*** The set of nodes that were ever passed as a parameter, or returned/thrown from a call site. */
298 protected final Set passedAsParameter;
299 /*** The current basic block. */
300 protected BasicBlock bb;
301 /*** The current state. */
302 protected State s;
303 /*** Change bit for worklist iteration. */
304 protected boolean change;
305
306 boolean include_sync_ops = true;
307 boolean include_cast_ops = System.getProperty("ms.withcasts", "yes").equals("yes");
308
309 /*** Map from sync ops to their nodes. */
310 protected final Map sync_ops;
311
312 /*** Factory for nodes. */
313 protected final HashMap nodeCache;
314
315 BuildMethodSummary(BuildMethodSummary that) {
316 this.method = that.method;
317 this.rf = that.rf;
318 this.param_nodes = that.param_nodes;
319 this.my_global = that.my_global;
320 this.start_states = that.start_states;
321 this.returned = that.returned;
322 this.thrown = that.thrown;
323 this.methodCalls = that.methodCalls;
324 this.callToRVN = that.callToRVN;
325 this.callToTEN = that.callToTEN;
326 this.castMap = that.castMap;
327 this.castPredecessors = that.castPredecessors;
328 this.passedAsParameter = that.passedAsParameter;
329 this.bb = that.bb;
330 this.s = that.s;
331 this.change = that.change;
332 this.sync_ops = that.sync_ops;
333 this.nodeCache = that.nodeCache;
334 }
335
336 /*** Returns the summary. Call this after iteration has completed. */
337 public MethodSummary getSummary() {
338 MethodSummary s = new MethodSummary(this,
339 method,
340 param_nodes,
341 my_global,
342 methodCalls,
343 callToRVN,
344 callToTEN,
345 castMap,
346 castPredecessors,
347 returned,
348 thrown,
349 passedAsParameter,
350 sync_ops);
351 return s;
352 }
353
354 /*** Set the given local in the current state to point to the given node. */
355 protected void setLocal(int i, Node n) { s.registers[i] = n; }
356 /*** Set the given register in the current state to point to the given node. */
357 protected void setRegister(Register r, Node n) {
358 int i = r.getNumber();
359 s.registers[i] = n;
360 if (TRACE_INTRA) out.println("Setting register "+r+" to "+n);
361 }
362 /*** Set the given register in the current state to point to the given node or set of nodes. */
363 protected void setRegister(Register r, Object n) {
364 int i = r.getNumber();
365 if (n instanceof Collection) n = NodeSet.FACTORY.makeSet((Collection)n);
366 else if (n != null) Assert._assert(n instanceof Node);
367 s.registers[i] = n;
368 if (TRACE_INTRA) out.println("Setting register "+r+" to "+n);
369 }
370 /*** Get the node or set of nodes in the given register in the current state. */
371 public Object getRegister(Register r) {
372 int i = r.getNumber();
373 if (s.registers[i] == null) {
374
375
376 }
377 return s.registers[i];
378 }
379
380 /*** Calculate the register set up to a given point. */
381 public void updateLocation(BasicBlock bb, Quad q) {
382 this.bb = bb;
383 this.s = start_states[bb.getID()];
384 this.s = this.s.copy();
385 for (joeq.Util.Templates.ListIterator.Quad i = bb.iterator(); i.hasNext(); ) {
386 Quad q2 = i.nextQuad();
387 q2.accept(this);
388 if (q2 == q) break;
389 }
390 }
391
392 /*** Build a summary for the given method. */
393 public BuildMethodSummary(ControlFlowGraph cfg) {
394 this.rf = cfg.getRegisterFactory();
395 this.method = cfg.getMethod();
396 this.start_states = new State[cfg.getNumberOfBasicBlocks()];
397 this.methodCalls = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
398 this.callToRVN = new HashMap();
399 this.callToTEN = new HashMap();
400 this.passedAsParameter = NodeSet.FACTORY.makeSet();
401 this.nodeCache = new HashMap();
402 this.s = this.start_states[0] = new State(rf.size());
403 jq_Type[] params = this.method.getParamTypes();
404 this.param_nodes = new ParamNode[params.length];
405 for (int i=0, j=0; i<params.length; ++i, ++j) {
406 if (params[i].isReferenceType()
407
408 ) {
409 setLocal(j, param_nodes[i] = ParamNode.get(method, i, (jq_Reference)params[i]));
410 } else if (params[i].getReferenceSize() == 8) {
411
412 }
413 }
414 this.my_global = GlobalNode.get(this.method);
415 this.sync_ops = new HashMap();
416 this.castMap = new LinkedHashMap();
417 this.castPredecessors = new LinkedHashSet();
418 this.returned = NodeSet.FACTORY.makeSet(); this.thrown = NodeSet.FACTORY.makeSet();
419
420 if (TRACE_INTRA) out.println("Building summary for "+this.method);
421
422
423 joeq.Util.Templates.List.BasicBlock rpo_list = cfg.reversePostOrder(cfg.entry());
424 for (;;) {
425 joeq.Util.Templates.ListIterator.BasicBlock rpo = rpo_list.basicBlockIterator();
426 this.change = false;
427 while (rpo.hasNext()) {
428 this.bb = rpo.nextBasicBlock();
429 this.s = start_states[bb.getID()];
430 if (this.s == null) {
431 continue;
432 }
433 this.s = this.s.copy();
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453 if (TRACE_INTRA) {
454 out.println("State at beginning of "+this.bb+":");
455 this.s.dump(out);
456 }
457 this.bb.visitQuads(this);
458 joeq.Util.Templates.ListIterator.BasicBlock succs = this.bb.getSuccessors().basicBlockIterator();
459 while (succs.hasNext()) {
460 BasicBlock succ = succs.nextBasicBlock();
461 if (this.bb.endsInRet()) {
462 if (jsr_states != null) {
463 State s2 = (State) jsr_states.get(succ);
464 if (s2 != null) {
465 JSRInfo info = cfg.getJSRInfo(this.bb);
466 boolean[] changedLocals = info.changedLocals;
467 mergeWithJSR(succ, s2, changedLocals);
468 } else {
469 if (TRACE_INTRA) out.println("jsr before "+succ+" not yet visited!");
470 }
471 } else {
472 if (TRACE_INTRA) out.println("no jsr's visited yet! was looking for jsr successor "+succ);
473 }
474 } else {
475 mergeWith(succ);
476 }
477 }
478 }
479 if (!this.change) break;
480 }
481 }
482
483 /*** Merge the current state into the start state for the given basic block.
484 * If that start state is uninitialized, it is initialized with a copy of
485 * the current state. This updates the change flag if anything is changed. */
486 protected void mergeWith(BasicBlock succ) {
487 if (this.start_states[succ.getID()] == null) {
488 if (TRACE_INTRA) out.println(succ+" not yet visited.");
489 this.start_states[succ.getID()] = this.s.copy();
490 this.change = true;
491 } else {
492
493 if (TRACE_INTRA) out.println("merging out set of "+bb+" into in set of "+succ);
494 if (this.start_states[succ.getID()].merge(this.s)) {
495 if (TRACE_INTRA) out.println(succ+" in set changed");
496 this.change = true;
497 }
498 }
499 }
500
501 protected void mergeWithJSR(BasicBlock succ, State s2, boolean[] changedLocals) {
502 State state = this.start_states[succ.getID()];
503 if (state == null) {
504 if (TRACE_INTRA) out.println(succ+" not yet visited.");
505 this.start_states[succ.getID()] = state = this.s.copy();
506 this.change = true;
507 }
508
509 if (TRACE_INTRA) out.println("merging out set of jsr "+bb+" into in set of "+succ);
510 for (int i=0; i<changedLocals.length; ++i) {
511 if (changedLocals[i]) {
512 if (state.merge(i, this.s.registers[i])) {
513 if (TRACE_INTRA) out.println(succ+" in set changed by register "+i+" in jsr subroutine");
514 this.change = true;
515 }
516 } else {
517 if (state.merge(i, s2.registers[i])) {
518 if (TRACE_INTRA) out.println(succ+" in set changed by register "+i+" before jsr subroutine");
519 this.change = true;
520 }
521 }
522 }
523 }
524
525 /*** Merge the current state into the start state for the given basic block.
526 * If that start state is uninitialized, it is initialized with a copy of
527 * the current state. This updates the change flag if anything is changed. */
528 protected void mergeWith(ExceptionHandler eh) {
529 BasicBlock succ = eh.getEntry();
530 if (this.start_states[succ.getID()] == null) {
531 if (TRACE_INTRA) out.println(succ+" not yet visited.");
532 this.start_states[succ.getID()] = this.s.copy();
533 for (Iterator i = rf.iterator(); i.hasNext(); ) {
534 Register r = (Register) i.next();
535 if (r.isTemp())
536 this.start_states[succ.getID()].registers[r.getNumber()] = null;
537 }
538 this.change = true;
539 } else {
540
541 if (TRACE_INTRA) out.println("merging out set of "+bb+" into in set of ex handler "+succ);
542 for (Iterator i = rf.iterator(); i.hasNext(); ) {
543 Register r = (Register) i.next();
544 if (r.isTemp()) continue;
545 if (this.start_states[succ.getID()].merge(r.getNumber(), this.s.registers[r.getNumber()]))
546 this.change = true;
547 }
548 if (TRACE_INTRA && this.change) out.println(succ+" in set changed");
549 }
550 }
551
552 public static final boolean INSIDE_EDGES = false;
553
554 /*** Abstractly perform a heap load operation on the given base and field
555 * with the given field node, putting the result in the given set. */
556 protected void heapLoad(Set result, Node base, jq_Field f, FieldNode fn) {
557
558 result.add(fn);
559 if (INSIDE_EDGES)
560 base.getAllEdges(f, result);
561 }
562 /*** Abstractly perform a heap load operation corresponding to quad 'obj'
563 * with the given destination register, bases and field. The destination
564 * register in the current state is changed to the result. */
565 protected void heapLoad(ProgramLocation obj, Register dest_r, Set base_s, jq_Field f) {
566 Set result = NodeSet.FACTORY.makeSet();
567 for (Iterator i=base_s.iterator(); i.hasNext(); ) {
568 Node base = (Node)i.next();
569 FieldNode fn = FieldNode.get(base, f, obj);
570 heapLoad(result, base, f, fn);
571 }
572 setRegister(dest_r, result);
573 }
574 /*** Abstractly perform a heap load operation corresponding to quad 'obj'
575 * with the given destination register, base and field. The destination
576 * register in the current state is changed to the result. */
577 protected void heapLoad(ProgramLocation obj, Register dest_r, Node base_n, jq_Field f) {
578 FieldNode fn = FieldNode.get(base_n, f, obj);
579 Set result = NodeSet.FACTORY.makeSet();
580 heapLoad(result, base_n, f, fn);
581 setRegister(dest_r, result);
582 }
583 /*** Abstractly perform a heap load operation corresponding to quad 'obj'
584 * with the given destination register, base register and field. The
585 * destination register in the current state is changed to the result. */
586 protected void heapLoad(ProgramLocation obj, Register dest_r, Register base_r, jq_Field f) {
587 Object o = getRegister(base_r);
588 if (o instanceof Set) {
589 heapLoad(obj, dest_r, (Set)o, f);
590 } else {
591 heapLoad(obj, dest_r, (Node)o, f);
592 }
593 }
594
595 /*** Abstractly perform a heap store operation of the given source node on
596 * the given base node and field. */
597 protected void heapStore(Node base, Node src, jq_Field f) {
598 base.addEdge(f, src);
599 }
600 /*** Abstractly perform a heap store operation of the given source nodes on
601 * the given base node and field. */
602 protected void heapStore(Node base, Set src, jq_Field f) {
603 base.addEdges(f, NodeSet.FACTORY.makeSet(src));
604 }
605 protected void heapStore(Node base, Object src, jq_Field f) {
606 if (src instanceof Node) {
607 heapStore(base, (Node) src, f);
608 } else {
609 heapStore(base, (Set) src, f);
610 }
611 }
612 /*** Abstractly perform a heap store operation of the given source node on
613 * the nodes in the given register in the current state and the given field. */
614 protected void heapStore(Object base, Object src, jq_Field f) {
615 if (base instanceof Node) {
616 if (src instanceof Node) {
617 heapStore((Node) base, (Node) src, f);
618 } else {
619 heapStore((Node) base, (Set) src, f);
620 }
621 } else {
622 Set s = (Set) base;
623 if (src instanceof Node) {
624 for (Iterator i = s.iterator(); i.hasNext(); ) {
625 heapStore((Node)i.next(), (Node) src, f);
626 }
627 } else {
628 for (Iterator i = s.iterator(); i.hasNext(); ) {
629 heapStore((Node)i.next(), (Set) src, f);
630 }
631 }
632 }
633 }
634
635 protected void monitorOp(Quad q, Register r) {
636 Object src = getRegister(r);
637 if (src instanceof Node) {
638 monitorOp(q, Collections.singleton(src));
639 } else {
640 monitorOp(q, (Set) src);
641 }
642 }
643
644 protected void monitorOp(Quad q, Set s) {
645 Set old = (Set) sync_ops.get(q);
646 if (old != null) {
647 Assert._assert(s.containsAll(old));
648 }
649 sync_ops.put(q, s);
650 }
651
652 /*** Record that the nodes in the given register were passed to the given
653 * method call as the given parameter. */
654 void passParameter(Register r, ProgramLocation m, int p) {
655 Object v = getRegister(r);
656 if (TRACE_INTRA) out.println("Passing "+r+" to "+m+" param "+p+": "+v);
657 if (v instanceof Set) {
658 for (Iterator i = ((Set)v).iterator(); i.hasNext(); ) {
659 Node n = (Node)i.next();
660 n.recordPassedParameter(m, p);
661 passedAsParameter.add(n);
662 }
663 } else {
664 Node n = (Node)v;
665 n.recordPassedParameter(m, p);
666 passedAsParameter.add(n);
667 }
668 }
669
670
671 static final boolean GLOBAL_OBJECT_CONSTANTS = false;
672
673 static final boolean GLOBAL_TYPE_CONSTANTS = false;
674
675 static final boolean MERGE_LOCAL_CONSTANTS = false;
676 public static boolean PATCH_UP_FAKE = false;
677 Node handleConst(Const4Operand op, ProgramLocation pl) {
678 return handleConst(op, pl, 0);
679 }
680 Node handleConst(Const4Operand op, ProgramLocation pl, int opn) {
681 Node n;
682 if (op instanceof AConstOperand) {
683 AConstOperand aop = (AConstOperand) op;
684 if (GLOBAL_OBJECT_CONSTANTS) {
685 n = ConcreteObjectNode.get(aop, (ProgramLocation)null);
686 } else if (GLOBAL_TYPE_CONSTANTS) {
687 n = ConcreteTypeNode.get(aop.getType());
688 } else {
689 if (MERGE_LOCAL_CONSTANTS) {
690 n = ConcreteObjectNode.get(aop, pl);
691 } else {
692 n = ConcreteTypeNode.get(aop.getType(), pl, new Integer(opn));
693 if(aop.getValue() instanceof String){
694 String value = (String) aop.getValue();
695
696 stringNodes2Values.put(n, value);
697
698 }
699 }
700 }
701 } else {
702 jq_Reference type = ((PConstOperand)op).getType();
703 n = UnknownTypeNode.get(type);
704 }
705 return n;
706 }
707
708 /*** Visit an array load instruction. */
709 public void visitALoad(Quad obj) {
710 if (obj.getOperator() instanceof Operator.ALoad.ALOAD_A
711 || obj.getOperator() instanceof Operator.ALoad.ALOAD_P
712 ) {
713 if (TRACE_INTRA) out.println("Visiting: "+obj);
714 Register r = ALoad.getDest(obj).getRegister();
715 Operand o = ALoad.getBase(obj);
716 ProgramLocation pl = new QuadProgramLocation(method, obj);
717 if (o instanceof RegisterOperand) {
718 Register b = ((RegisterOperand)o).getRegister();
719 heapLoad(pl, r, b, null);
720 } else {
721
722 Node n = handleConst((AConstOperand) o, pl);
723 heapLoad(pl, r, n, null);
724 }
725 }
726 }
727 /*** Visit an array store instruction. */
728 public void visitAStore(Quad obj) {
729 if (obj.getOperator() instanceof Operator.AStore.ASTORE_A
730 || obj.getOperator() instanceof Operator.AStore.ASTORE_P
731 ) {
732 if (TRACE_INTRA) out.println("Visiting: "+obj);
733 Operand val_op = AStore.getValue(obj);
734 Operand base_op = AStore.getBase(obj);
735 Object val, base;
736 if (base_op instanceof RegisterOperand) {
737 Register base_r = ((RegisterOperand)base_op).getRegister();
738 base = getRegister(base_r);
739 } else {
740
741 base = handleConst((AConstOperand) base_op, new QuadProgramLocation(method, obj), 0);
742 }
743 if (val_op instanceof RegisterOperand) {
744 Register src_r = ((RegisterOperand)val_op).getRegister();
745 val = getRegister(src_r);
746 } else {
747 val = handleConst((Const4Operand) val_op, new QuadProgramLocation(method, obj), 1);
748 }
749 heapStore(base, val, null);
750 }
751 }
752 public void visitBinary(Quad obj) {
753 if (obj.getOperator() == Binary.ADD_P.INSTANCE) {
754 if (TRACE_INTRA) out.println("Visiting: "+obj);
755 Register dest_r = Binary.getDest(obj).getRegister();
756 Operand src = Binary.getSrc1(obj);
757 if (src instanceof RegisterOperand) {
758 RegisterOperand rop = ((RegisterOperand)src);
759 Register src_r = rop.getRegister();
760 setRegister(dest_r, getRegister(src_r));
761 } else {
762 Node n = handleConst((Const4Operand) src, new QuadProgramLocation(method, obj));
763 setRegister(dest_r, n);
764 }
765 }
766 }
767 /*** Visit a type cast check instruction. */
768 public void visitCheckCast(Quad obj) {
769 if (TRACE_INTRA) out.println("Visiting: "+obj);
770 Register dest_r = CheckCast.getDest(obj).getRegister();
771 Operand src = CheckCast.getSrc(obj);
772 if (src instanceof RegisterOperand) {
773 Register src_r = ((RegisterOperand)src).getRegister();
774 Object s = getRegister(src_r);
775 if (!include_cast_ops) {
776 setRegister(dest_r, s);
777 return;
778 }
779 CheckCastNode n = (CheckCastNode)nodeCache.get(obj);
780 if (n == null) {
781 n = CheckCastNode.get((jq_Reference)CheckCast.getType(obj).getType(),
782 new QuadProgramLocation(method, obj));
783 nodeCache.put(obj, n);
784 }
785 Collection from = (s instanceof Collection) ? (Collection)s : Collections.singleton(s);
786 Iterator i = from.iterator();
787 while (i.hasNext()) {
788 Node fn = (Node)i.next();
789 Pair key = new Pair(fn, obj);
790 if (castMap.put(key, n) == null)
791 castPredecessors.add(fn);
792 }
793 setRegister(dest_r, n);
794 } else {
795 Node n = handleConst((Const4Operand) src, new QuadProgramLocation(method, obj));
796 setRegister(dest_r, n);
797 }
798 }
799 /*** Visit a get instance field instruction. */
800 public void visitGetfield(Quad obj) {
801 if (obj.getOperator() instanceof Operator.Getfield.GETFIELD_A
802 || obj.getOperator() instanceof Operator.Getfield.GETFIELD_P
803 ) {
804 if (TRACE_INTRA) out.println("Visiting: "+obj);
805 Register r = Getfield.getDest(obj).getRegister();
806 Operand o = Getfield.getBase(obj);
807 Getfield.getField(obj).resolve();
808 jq_Field f = Getfield.getField(obj).getField();
809 if (IGNORE_INSTANCE_FIELDS) f = null;
810 ProgramLocation pl = new QuadProgramLocation(method, obj);
811 if (o instanceof RegisterOperand) {
812 Register b = ((RegisterOperand)o).getRegister();
813 heapLoad(pl, r, b, f);
814 } else {
815
816 Node n = handleConst((Const4Operand) o, pl);
817 heapLoad(pl, r, n, f);
818 }
819 }
820 }
821 /*** Visit a get static field instruction. */
822 public void visitGetstatic(Quad obj) {
823 if (obj.getOperator() instanceof Operator.Getstatic.GETSTATIC_A
824 || obj.getOperator() instanceof Operator.Getstatic.GETSTATIC_P
825 ) {
826 if (TRACE_INTRA) out.println("Visiting: "+obj);
827 Register r = Getstatic.getDest(obj).getRegister();
828 Getstatic.getField(obj).resolve();
829 jq_Field f = Getstatic.getField(obj).getField();
830 if (IGNORE_STATIC_FIELDS) f = null;
831 ProgramLocation pl = new QuadProgramLocation(method, obj);
832 heapLoad(pl, r, my_global, f);
833 }
834 }
835 /*** Visit a type instance of instruction. */
836 public void visitInstanceOf(Quad obj) {
837
838 }
839 /*** Visit an invoke instruction. */
840 public void visitInvoke(Quad obj) {
841 if (TRACE_INTRA) out.println("Visiting: "+obj);
842 Invoke.getMethod(obj).resolve();
843 jq_Method m = Invoke.getMethod(obj).getMethod();
844 ProgramLocation mc = new ProgramLocation.QuadProgramLocation(method, obj);
845 if (m == joeq.Runtime.Arrays._multinewarray) {
846
847 RegisterOperand dest = Invoke.getDest(obj);
848 if (dest != null) {
849 Register dest_r = dest.getRegister();
850
851 jq_Reference type = PrimordialClassLoader.getJavaLangObject().getArrayTypeForElementType();
852 Node n = ConcreteTypeNode.get(type, new QuadProgramLocation(method, obj));
853 setRegister(dest_r, n);
854 }
855 return;
856 }
857
858 this.methodCalls.add(mc);
859 jq_Type[] params = m.getParamTypes();
860 ParamListOperand plo = Invoke.getParamList(obj);
861 Assert._assert(m == joeq.Runtime.Arrays._multinewarray || params.length == plo.length(),
862 obj + " calling " + m + ": params.length: " + params.length + ", plo: " + plo);
863
864 for (int i=0; i<params.length; ++i) {
865 if (!params[i].isReferenceType()
866
867 ) continue;
868 Assert._assert(plo.get(i) != null, "Element " + i + " of plo " + plo + " is bogus");
869 Register r = plo.get(i).getRegister();
870 passParameter(r, mc, i);
871 }
872 if (m.getReturnType().isReferenceType()
873
874 )
875 {
876 if(false
877
878 RegisterOperand dest = Invoke.getDest(obj);
879 if (dest != null) {
880 Register dest_r = dest.getRegister();
881
882 Node n = ConcreteTypeNode.get((jq_Reference) m.getReturnType(), new QuadProgramLocation(method, obj));
883 setRegister(dest_r, n);
884 }
885 } else {
886 RegisterOperand dest = Invoke.getDest(obj);
887 if (dest != null) {
888 Register dest_r = dest.getRegister();
889 ReturnValueNode n = (ReturnValueNode)callToRVN.get(mc);
890 if (n == null) {
891 callToRVN.put(mc, n = new ReturnValueNode(mc));
892 passedAsParameter.add(n);
893 }
894 setRegister(dest_r, n);
895 }
896 }
897 }
898
899 }
900
901 /***
902 * Holds the current state at each jsr call.
903 */
904 HashMap jsr_states;
905 /***
906 * @see joeq.Compiler.Quad.QuadVisitor#visitJsr(joeq.Compiler.Quad.Quad)
907 */
908 public void visitJsr(Quad obj) {
909 if (TRACE_INTRA) out.println("Visiting: "+obj);
910 if (jsr_states == null) jsr_states = new HashMap();
911 BasicBlock succ = Jsr.getSuccessor(obj).getTarget();
912 jsr_states.put(succ, this.s);
913 }
914
915 /*** Visit a register move instruction. */
916 public void visitMonitor(Quad obj) {
917 if (!include_sync_ops) return;
918 if (TRACE_INTRA) out.println("Visiting: "+obj);
919 Operand src = Monitor.getSrc(obj);
920 if (src instanceof RegisterOperand) {
921 RegisterOperand rop = ((RegisterOperand)src);
922 Register src_r = rop.getRegister();
923 monitorOp(obj, src_r);
924 } else {
925 Node n = handleConst((Const4Operand) src, new QuadProgramLocation(method, obj));
926 monitorOp(obj, Collections.singleton(n));
927 }
928 }
929
930 /*** Visit a register move instruction. */
931 public void visitMove(Quad obj) {
932 if (obj.getOperator() instanceof Operator.Move.MOVE_A
933 || obj.getOperator() instanceof Operator.Move.MOVE_P
934 ) {
935 if (TRACE_INTRA) out.println("Visiting: "+obj);
936 Register dest_r = Move.getDest(obj).getRegister();
937 Operand src = Move.getSrc(obj);
938 if (src instanceof RegisterOperand) {
939 RegisterOperand rop = ((RegisterOperand)src);
940 if (rop.getType() instanceof jq_ReturnAddressType) return;
941 Register src_r = rop.getRegister();
942 setRegister(dest_r, getRegister(src_r));
943 } else {
944 Node n = handleConst((Const4Operand) src, new QuadProgramLocation(method, obj));
945 setRegister(dest_r, n);
946 }
947 }
948 }
949
950 public void visitPhi(Quad obj) {
951 if (TRACE_INTRA) out.println("Visiting: "+obj);
952 Set set = NodeSet.FACTORY.makeSet();
953 ParamListOperand plo = Phi.getSrcs(obj);
954 for (int i=0; i<plo.length(); ++i) {
955 RegisterOperand rop = plo.get(i);
956 if (rop == null) continue;
957 Register r = rop.getRegister();
958 Object foo = s.registers[r.getNumber()];
959 if (foo instanceof Collection)
960 set.addAll((Collection) foo);
961 else if (foo != null)
962 set.add(foo);
963 else {
964
965 }
966 }
967 s.registers[Phi.getDest(obj).getRegister().getNumber()] = set;
968 }
969
970 LoopAnalysis la;
971 /*** Visit an object allocation instruction. */
972 public void visitNew(Quad obj) {
973 if (TRACE_INTRA) out.println("Visiting: "+obj);
974 Register dest_r = New.getDest(obj).getRegister();
975 jq_Reference type = (jq_Reference)New.getType(obj).getType();
976 if (SPLIT_THREADS && type != null) {
977 type.prepare();
978 jq_Class jlt = PrimordialClassLoader.getJavaLangThread();
979 jq_Class jlr = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("Ljava/lang/Runnable;");
980 jlt.prepare(); jlr.prepare();
981 if (type.isSubtypeOf(jlt) ||
982 type.isSubtypeOf(jlr)) {
983 if (la == null) la = new LoopAnalysis();
984 if (la.isInLoop(method, bb)) {
985 Object key = obj;
986 Pair p = (Pair) nodeCache.get(key);
987 if (p == null) {
988 System.out.println("Found thread creation in loop: "+obj);
989 p = new Pair(ConcreteTypeNode.get(type, new QuadProgramLocation(method, obj)),
990 ConcreteTypeNode.get(type, new QuadProgramLocation(method, obj)));
991 nodeCache.put(key, p);
992 }
993 setRegister(dest_r, p);
994 return;
995 }
996 }
997 }
998
999
1000 Node n = ConcreteTypeNode.get(type, new QuadProgramLocation(method, obj));
1001 setRegister(dest_r, n);
1002 }
1003
1004 /*** Visit an array allocation instruction. */
1005 public void visitNewArray(Quad obj) {
1006 if (TRACE_INTRA) out.println("Visiting: "+obj);
1007 Register dest_r = NewArray.getDest(obj).getRegister();
1008 jq_Reference type = (jq_Reference)NewArray.getType(obj).getType();
1009 Node n = ConcreteTypeNode.get(type, new QuadProgramLocation(method, obj));
1010 setRegister(dest_r, n);
1011 }
1012
1013 /*** Visit a put instance field instruction. */
1014 public void visitPutfield(Quad obj) {
1015 if (obj.getOperator() instanceof Operator.Putfield.PUTFIELD_A
1016 || obj.getOperator() instanceof Operator.Putfield.PUTFIELD_P
1017 ) {
1018 if (TRACE_INTRA) out.println("Visiting: "+obj);
1019 Operand base_op = Putfield.getBase(obj);
1020 Operand val_op = Putfield.getSrc(obj);
1021 Putfield.getField(obj).resolve();
1022 jq_Field f = Putfield.getField(obj).getField();
1023 if (IGNORE_INSTANCE_FIELDS) f = null;
1024 Object base, val;
1025 if (val_op instanceof RegisterOperand) {
1026 Register src_r = ((RegisterOperand)val_op).getRegister();
1027 val = getRegister(src_r);
1028 } else {
1029 val = handleConst((Const4Operand) val_op, new QuadProgramLocation(method, obj), 0);
1030 }
1031 if (base_op instanceof RegisterOperand) {
1032 Register base_r = ((RegisterOperand)base_op).getRegister();
1033 base = getRegister(base_r);
1034 } else {
1035 base = handleConst((Const4Operand) base_op, new QuadProgramLocation(method, obj), 1);
1036 }
1037 heapStore(base, val, f);
1038 }
1039 }
1040 /*** Visit a put static field instruction. */
1041 public void visitPutstatic(Quad obj) {
1042 if (obj.getOperator() instanceof Operator.Putstatic.PUTSTATIC_A
1043 || obj.getOperator() instanceof Operator.Putstatic.PUTSTATIC_P
1044 ) {
1045 if (TRACE_INTRA) out.println("Visiting: "+obj);
1046 Operand val = Putstatic.getSrc(obj);
1047 Putstatic.getField(obj).resolve();
1048 jq_Field f = Putstatic.getField(obj).getField();
1049 if (IGNORE_STATIC_FIELDS) f = null;
1050 if (val instanceof RegisterOperand) {
1051 Register src_r = ((RegisterOperand)val).getRegister();
1052 heapStore(my_global, getRegister(src_r), f);
1053 } else {
1054 Node n = handleConst((Const4Operand) val, new QuadProgramLocation(method, obj));
1055 heapStore(my_global, n, f);
1056 }
1057 }
1058 }
1059
1060 static void addToSet(Set s, Object o) {
1061 if (o instanceof Set) s.addAll((Set)o);
1062 else if (o != null) s.add(o);
1063 }
1064
1065 /*** Visit a return/throw instruction. */
1066 public void visitReturn(Quad obj) {
1067 Operand src = Return.getSrc(obj);
1068 Set r;
1069 if (obj.getOperator() == Return.RETURN_A.INSTANCE
1070 || obj.getOperator() == Return.RETURN_P.INSTANCE
1071 ) r = returned;
1072 else if (obj.getOperator() == Return.THROW_A.INSTANCE) r = thrown;
1073 else return;
1074 if (TRACE_INTRA) out.println("Visiting: "+obj);
1075 if (src instanceof RegisterOperand) {
1076 Register src_r = ((RegisterOperand)src).getRegister();
1077 addToSet(r, getRegister(src_r));
1078 } else {
1079 Node n = handleConst((Const4Operand) src, new QuadProgramLocation(method, obj));
1080 r.add(n);
1081 }
1082 }
1083
1084 static void setAsEscapes(Object o) {
1085 if (o instanceof Set) {
1086 for (Iterator i=((Set)o).iterator(); i.hasNext(); ) {
1087 ((Node)i.next()).escapes = true;
1088 }
1089 } else {
1090 ((Node)o).escapes = true;
1091 }
1092 }
1093
1094 public void visitSpecial(Quad obj) {
1095 if (obj.getOperator() == Special.GET_THREAD_BLOCK.INSTANCE) {
1096 if (TRACE_INTRA) out.println("Visiting: "+obj);
1097 Register dest_r = ((RegisterOperand)Special.getOp1(obj)).getRegister();
1098 jq_Reference type = (jq_Reference) PrimordialClassLoader.loader.getOrCreateBSType("Ljoeq/Scheduler/jq_Thread;");
1099 Node n = ConcreteTypeNode.get(type, new QuadProgramLocation(method, obj));
1100 n.setEscapes();
1101 setRegister(dest_r, n);
1102 } else if (obj.getOperator() == Special.SET_THREAD_BLOCK.INSTANCE) {
1103 if (TRACE_INTRA) out.println("Visiting: "+obj);
1104 Register src_r = ((RegisterOperand)Special.getOp2(obj)).getRegister();
1105 setAsEscapes(getRegister(src_r));
1106 } else if (obj.getOperator() == Special.GET_STACK_POINTER.INSTANCE ||
1107 obj.getOperator() == Special.GET_BASE_POINTER.INSTANCE ||
1108 obj.getOperator() == Special.ALLOCA.INSTANCE ) {
1109 if (TRACE_INTRA) out.println("Visiting: "+obj);
1110 Register dest_r = ((RegisterOperand)Special.getOp1(obj)).getRegister();
1111 jq_Reference type = StackAddress._class;
1112 Node n = ConcreteTypeNode.get(type, new QuadProgramLocation(method, obj));
1113
1114 setRegister(dest_r, n);
1115
1116
1117
1118
1119
1120
1121
1122
1123 }
1124 }
1125 public void visitUnary(Quad obj) {
1126 if (obj.getOperator() == Unary.OBJECT_2ADDRESS.INSTANCE ||
1127 obj.getOperator() == Unary.ADDRESS_2OBJECT.INSTANCE) {
1128 if (TRACE_INTRA) out.println("Visiting: "+obj);
1129 Register dest_r = Unary.getDest(obj).getRegister();
1130 Operand src = Unary.getSrc(obj);
1131 if (src instanceof RegisterOperand) {
1132 RegisterOperand rop = ((RegisterOperand)src);
1133 Register src_r = rop.getRegister();
1134 setRegister(dest_r, getRegister(src_r));
1135 } else {
1136 Node n = handleConst((Const4Operand) src, new QuadProgramLocation(method, obj));
1137 setRegister(dest_r, n);
1138 }
1139 } else if (obj.getOperator() == Unary.INT_2ADDRESS.INSTANCE) {
1140 Register dest_r = Unary.getDest(obj).getRegister();
1141 jq_Reference type = Address._class;
1142 UnknownTypeNode n = UnknownTypeNode.get(type);
1143 setRegister(dest_r, n);
1144 }
1145 }
1146 public void visitExceptionThrower(Quad obj) {
1147 if (TRACE_INTRA) out.println("Visiting: "+obj);
1148
1149 if (obj.getOperator() instanceof Invoke) {
1150 Invoke.getMethod(obj).resolve();
1151
1152 ProgramLocation mc = new ProgramLocation.QuadProgramLocation(method, obj);
1153 ThrownExceptionNode n = (ThrownExceptionNode) callToTEN.get(mc);
1154 if (n == null) {
1155 callToTEN.put(mc, n = ThrownExceptionNode.get(mc));
1156 passedAsParameter.add(n);
1157 }
1158 joeq.Util.Templates.ListIterator.ExceptionHandler eh = bb.getExceptionHandlers().exceptionHandlerIterator();
1159 while (eh.hasNext()) {
1160 ExceptionHandler h = eh.nextExceptionHandler();
1161 this.mergeWith(h);
1162 Register r = null;
1163 if (h.getEntry().size() > 0) {
1164 for (Iterator ge = h.getEntry().iterator(); ge.hasNext();) {
1165 Quad q = (Quad) ge.next();
1166 if (q.getOperator() instanceof Special.GET_EXCEPTION) {
1167 r = ((RegisterOperand) Special.getOp1(q)).getRegister();
1168 break;
1169 }
1170 }
1171 }
1172 if (r == null) {
1173
1174
1175
1176 Assert._assert(!SSA);
1177 r = rf.getOrCreateStack(0, PrimordialClassLoader.getJavaLangObject());
1178 }
1179 this.start_states[h.getEntry().getID()].merge(r.getNumber(), n);
1180 if (h.mustCatch(PrimordialClassLoader.getJavaLangThrowable()))
1181 return;
1182 }
1183 this.thrown.add(n);
1184 return;
1185 }
1186 joeq.Util.Templates.ListIterator.jq_Class xs = obj.getThrownExceptions().classIterator();
1187 while (xs.hasNext()) {
1188 jq_Class x = xs.nextClass();
1189 UnknownTypeNode n = UnknownTypeNode.get(x);
1190 joeq.Util.Templates.ListIterator.ExceptionHandler eh = bb.getExceptionHandlers().exceptionHandlerIterator();
1191 boolean caught = false;
1192 while (eh.hasNext()) {
1193 ExceptionHandler h = eh.nextExceptionHandler();
1194 if (h.mayCatch(x)) {
1195 this.mergeWith(h);
1196 Register r = null;
1197 if (h.getEntry().size() > 0) {
1198 for (Iterator ge = h.getEntry().iterator(); ge.hasNext();) {
1199 Quad q = (Quad) ge.next();
1200 if (q.getOperator() instanceof Special.GET_EXCEPTION) {
1201 r = ((RegisterOperand) Special.getOp1(q)).getRegister();
1202 break;
1203 }
1204 }
1205 }
1206 if (r == null) {
1207
1208
1209
1210 Assert._assert(!SSA);
1211 r = rf.getOrCreateStack(0, PrimordialClassLoader.getJavaLangObject());
1212 }
1213 this.start_states[h.getEntry().getID()].merge(r.getNumber(), n);
1214 }
1215 if (h.mustCatch(x)) {
1216 caught = true;
1217 break;
1218 }
1219 }
1220 if (!caught) this.thrown.add(n);
1221 }
1222 }
1223
1224 }
1225
1226 /*** Represents a particular parameter passed to a particular method call. */
1227 public static class PassedParameter implements Textualizable {
1228 final ProgramLocation m; final int paramNum;
1229 public PassedParameter(ProgramLocation m, int paramNum) {
1230 this.m = m; this.paramNum = paramNum;
1231 }
1232 public ProgramLocation getCall() { return m; }
1233 public int getParamNum() { return paramNum; }
1234 public int hashCode() {
1235 return m.hashCode() ^ paramNum;
1236 }
1237 public boolean equals(PassedParameter that) { return this.m.equals(that.m) && this.paramNum == that.paramNum; }
1238 public boolean equals(Object o) { if (o instanceof PassedParameter) return equals((PassedParameter)o); return false; }
1239 public String toString() { return "Param "+paramNum+" for "+m; }
1240 public void write(Textualizer t) throws IOException {
1241 m.write(t);
1242 t.writeString(" "+paramNum);
1243 }
1244 public void writeEdges(Textualizer t) throws IOException { }
1245 public void addEdge(String edgeName, Textualizable t) { }
1246 public static PassedParameter read(StringTokenizer st) {
1247 ProgramLocation l = ProgramLocation.read(st);
1248 int k = Integer.parseInt(st.nextToken());
1249 return new PassedParameter(l, k);
1250 }
1251 }
1252
1253 /*** Represents a particular call site in a method. */
1254 public static class CallSite {
1255 final MethodSummary caller; final ProgramLocation m;
1256 public CallSite(MethodSummary caller, ProgramLocation m) {
1257 this.caller = caller; this.m = m;
1258 }
1259 public MethodSummary getCaller() { return caller; }
1260 public ProgramLocation getLocation() { return m; }
1261 public int hashCode() { return (caller == null?0x0:caller.hashCode()) ^ m.hashCode(); }
1262 public boolean equals(CallSite that) { return this.m.equals(that.m) && this.caller == that.caller; }
1263 public boolean equals(Object o) { if (o instanceof CallSite) return equals((CallSite)o); return false; }
1264 public String toString() { return (caller!=null?caller.getMethod():null)+" "+m.getID()+" "+(m.getTargetMethod()!=null?m.getTargetMethod().getName():null); }
1265 }
1266
1267 /*** Represents a field edge between two nodes. */
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307 public static class InsideEdgeNavigator implements Navigator {
1308
1309
1310
1311
1312 public Collection next(Object node) {
1313 Node n = (Node) node;
1314 return n.getNonEscapingEdgeTargets();
1315 }
1316
1317
1318
1319
1320 public Collection prev(Object node) {
1321 Node n = (Node) node;
1322 return n.getPredecessorTargets();
1323 }
1324
1325 }
1326
1327 public static interface Variable {}
1328 public static interface HeapObject {
1329 ProgramLocation getLocation();
1330 jq_Reference getDeclaredType();
1331 }
1332
1333 public abstract static class Node implements Textualizable, Comparable, Variable {
1334 /*** Map from fields to sets of predecessors on that field.
1335 * This only includes inside edges; outside edge predecessors are in FieldNode. */
1336 protected Map predecessors;
1337 /*** Set of passed parameters for this node. */
1338 protected Set passedParameters;
1339 /*** Map from fields to sets of inside edges from this node on that field. */
1340 protected Map addedEdges;
1341 /*** Map from fields to sets of outside edges from this node on that field. */
1342 protected Map accessPathEdges;
1343 /*** Unique id number. */
1344 public final int id;
1345 /*** Whether or not this node escapes into some unanalyzable code. */
1346 private boolean escapes;
1347
1348 public static boolean TRACK_REASONS = false;
1349
1350 /*** Maps added edges to the quads that they come from.
1351 Only used if TRACK_REASONS is true. */
1352
1353
1354 public static int numberOfNodes() { return current_id; }
1355 private static int current_id = 0;
1356
1357 protected Node() { this.id = ++current_id; }
1358 protected Node(Node that) {
1359 this.predecessors = that.predecessors;
1360 this.passedParameters = that.passedParameters;
1361 this.addedEdges = that.addedEdges;
1362 this.accessPathEdges = that.accessPathEdges;
1363 this.id = ++current_id;
1364 this.escapes = that.escapes;
1365
1366 }
1367
1368 public int hashCode() {
1369 if (USE_IDENTITY_HASHCODE)
1370 return System.identityHashCode(this);
1371 else
1372 return id;
1373 }
1374
1375 public final int compareTo(Node that) {
1376 if (this.id > that.id) return 1;
1377 else if (this.id == that.id) return 0;
1378 else return -1;
1379 }
1380 public final int compareTo(Object o) {
1381 return compareTo((Node)o);
1382 }
1383
1384 public boolean isPassedAsParameter() {
1385 return passedParameters != null;
1386 }
1387 public Set getPassedParameters() {
1388 return passedParameters;
1389 }
1390
1391 /*** Replace this node by the given set of nodes. All inside and outside
1392 * edges to and from this node are replaced by sets of edges to and from
1393 * the nodes in the set. The passed parameter set of this node is also
1394 * added to every node in the given set. */
1395 public void replaceBy(Set set, boolean removeSelf) {
1396 if (TRACE_INTRA) out.println("Replacing "+this+" with "+set+(removeSelf?", and removing self":""));
1397 if (set.contains(this)) {
1398 if (TRACE_INTRA) out.println("Replacing a node with itself, turning off remove self.");
1399 set.remove(this);
1400 if (set.isEmpty()) {
1401 if (TRACE_INTRA) out.println("Replacing a node with only itself! Nothing to do.");
1402 return;
1403 }
1404 removeSelf = false;
1405 }
1406 if (VERIFY_ASSERTIONS) Assert._assert(!set.contains(this));
1407 if (this.predecessors != null) {
1408 for (Iterator i=this.predecessors.entrySet().iterator(); i.hasNext(); ) {
1409 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
1410 jq_Field f = (jq_Field)e.getKey();
1411 Object o = e.getValue();
1412 if (removeSelf)
1413 i.remove();
1414 if (TRACE_INTRA) out.println("Looking at predecessor on field "+f+": "+o);
1415 if (o == null) continue;
1416 if (o instanceof Node) {
1417 Node that = (Node)o;
1418
1419
1420
1421 if (removeSelf)
1422 that._removeEdge(f, this);
1423 if (that == this) {
1424
1425 if (TRACE_INTRA) out.println("Adding self-cycles on field "+f);
1426 for (Iterator j=set.iterator(); j.hasNext(); ) {
1427 Node k = (Node)j.next();
1428 k.addEdge(f, k);
1429 }
1430 } else {
1431 for (Iterator j=set.iterator(); j.hasNext(); ) {
1432 that.addEdge(f, (Node)j.next());
1433 }
1434 }
1435 } else {
1436 for (Iterator k=((Set)o).iterator(); k.hasNext(); ) {
1437 Node that = (Node)k.next();
1438 if (removeSelf) {
1439 k.remove();
1440 that._removeEdge(f, this);
1441 }
1442
1443
1444
1445 if (that == this) {
1446
1447 if (TRACE_INTRA) out.println("Adding self-cycles on field "+f);
1448 for (Iterator j=set.iterator(); j.hasNext(); ) {
1449 Node k2 = (Node)j.next();
1450 k2.addEdge(f, k2);
1451 }
1452 } else {
1453 for (Iterator j=set.iterator(); j.hasNext(); ) {
1454 that.addEdge(f, (Node)j.next());
1455 }
1456 }
1457 }
1458 }
1459 }
1460 }
1461 if (this.addedEdges != null) {
1462 for (Iterator i=this.addedEdges.entrySet().iterator(); i.hasNext(); ) {
1463 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
1464 jq_Field f = (jq_Field)e.getKey();
1465 Object o = e.getValue();
1466 if (removeSelf)
1467 i.remove();
1468 if (o == null) continue;
1469 if (TRACE_INTRA) out.println("Looking at successor on field "+f+": "+o);
1470 if (o instanceof Node) {
1471 Node that = (Node)o;
1472 if (that == this) continue;
1473
1474 if (removeSelf) {
1475 boolean b = that.removePredecessor(f, this);
1476 if (TRACE_INTRA) out.println("Removed "+this+" from predecessor set of "+that+"."+f);
1477 Assert._assert(b);
1478 }
1479 for (Iterator j=set.iterator(); j.hasNext(); ) {
1480 Node node2 = (Node)j.next();
1481 node2.addEdge(f, that);
1482 }
1483 } else {
1484 for (Iterator k=((Set)o).iterator(); k.hasNext(); ) {
1485 Node that = (Node)k.next();
1486 if (removeSelf)
1487 k.remove();
1488 if (that == this) continue;
1489
1490 if (removeSelf) {
1491 boolean b = that.removePredecessor(f, this);
1492 if (TRACE_INTRA) out.println("Removed "+this+" from predecessor set of "+that+"."+f);
1493 Assert._assert(b);
1494 }
1495 for (Iterator j=set.iterator(); j.hasNext(); ) {
1496 Node node2 = (Node)j.next();
1497 node2.addEdge(f, that);
1498 }
1499 }
1500 }
1501 }
1502 }
1503 if (this.accessPathEdges != null) {
1504 for (Iterator i=this.accessPathEdges.entrySet().iterator(); i.hasNext(); ) {
1505 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
1506 jq_Field f = (jq_Field)e.getKey();
1507 Object o = e.getValue();
1508 if (removeSelf)
1509 i.remove();
1510 if (o == null) continue;
1511 if (TRACE_INTRA) out.println("Looking at access path successor on field "+f+": "+o);
1512 if (o instanceof FieldNode) {
1513 FieldNode that = (FieldNode)o;
1514 if (that == this) continue;
1515 if (removeSelf) {
1516 that.field_predecessors.remove(this);
1517 if (TRACE_INTRA) out.println("Removed "+this+" from access path predecessor set of "+that);
1518 }
1519 for (Iterator j=set.iterator(); j.hasNext(); ) {
1520 Node node2 = (Node)j.next();
1521 if (TRACE_INTRA) out.println("Adding access path edge "+node2+"->"+that);
1522 node2.addAccessPathEdge(f, that);
1523 }
1524 } else {
1525 for (Iterator k=((Set)o).iterator(); k.hasNext(); ) {
1526 FieldNode that = (FieldNode)k.next();
1527 if (removeSelf)
1528 k.remove();
1529 if (that == this) continue;
1530 if (removeSelf)
1531 that.field_predecessors.remove(this);
1532 for (Iterator j=set.iterator(); j.hasNext(); ) {
1533 Node node2 = (Node)j.next();
1534 node2.addAccessPathEdge(f, that);
1535 }
1536 }
1537 }
1538 }
1539 }
1540 if (this.passedParameters != null) {
1541 if (TRACE_INTRA) out.println("Node "+this+" is passed as parameters: "+this.passedParameters+", adding those parameters to "+set);
1542 for (Iterator i=this.passedParameters.iterator(); i.hasNext(); ) {
1543 PassedParameter pp = (PassedParameter)i.next();
1544 for (Iterator j=set.iterator(); j.hasNext(); ) {
1545 ((Node)j.next()).recordPassedParameter(pp);
1546 }
1547 }
1548 }
1549 }
1550
1551 /*** Helper function to update map m given an update map um. */
1552 static void updateMap(Map um, Iterator i, Map m) {
1553 while (i.hasNext()) {
1554 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
1555 Object f = e.getKey();
1556 Object o = e.getValue();
1557 if (o == null) continue;
1558 if (o instanceof Node) {
1559 Object q = um.get(o);
1560 if (o instanceof UnknownTypeNode) q = o;
1561 if (o == GlobalNode.GLOBAL) q = o;
1562 if (VERIFY_ASSERTIONS) Assert._assert(q != null, o+" is missing from map");
1563 if (TRACE_INTRA) out.println("Updated edge "+f+" "+o+" to "+q);
1564 m.put(f, q);
1565 } else {
1566 Set lhs = NodeSet.FACTORY.makeSet();
1567 m.put(f, lhs);
1568 for (Iterator j=((Set)o).iterator(); j.hasNext(); ) {
1569 Object r = j.next();
1570 Assert._assert(r != null);
1571 Object q = um.get(r);
1572 if (r instanceof UnknownTypeNode) q = r;
1573 if (r == GlobalNode.GLOBAL) q = o;
1574 if (VERIFY_ASSERTIONS) Assert._assert(q != null, r+" is missing from map");
1575 if (TRACE_INTRA) out.println("Updated edge "+f+" "+r+" to "+q);
1576 lhs.add(q);
1577 }
1578 }
1579 }
1580 }
1581
1582 static void addGlobalEdges(Node n) {
1583 if (n.predecessors != null) {
1584 for (Iterator i=n.predecessors.entrySet().iterator(); i.hasNext(); ) {
1585 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
1586 jq_Field f = (jq_Field)e.getKey();
1587 Object o = e.getValue();
1588 if (o == GlobalNode.GLOBAL) {
1589 GlobalNode.GLOBAL.addEdge(f, n);
1590 } else if (o instanceof UnknownTypeNode) {
1591 ((UnknownTypeNode)o).addEdge(f, n);
1592 } else if (o instanceof Set) {
1593 for (Iterator j=((Set)o).iterator(); j.hasNext(); ) {
1594 Object r = j.next();
1595 if (r == GlobalNode.GLOBAL) {
1596 GlobalNode.GLOBAL.addEdge(f, n);
1597 } else if (r instanceof UnknownTypeNode) {
1598 ((UnknownTypeNode)r).addEdge(f, n);
1599 }
1600 }
1601 }
1602 }
1603 }
1604 if (n.addedEdges != null) {
1605 for (Iterator i=n.addedEdges.entrySet().iterator(); i.hasNext(); ) {
1606 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
1607 jq_Field f = (jq_Field)e.getKey();
1608 Object o = e.getValue();
1609 if (o instanceof UnknownTypeNode) {
1610 n.addEdge(f, (UnknownTypeNode)o);
1611 } else if (o instanceof Set) {
1612 for (Iterator j=((Set)o).iterator(); j.hasNext(); ) {
1613 Object r = j.next();
1614 if (r instanceof UnknownTypeNode) {
1615 n.addEdge(f, (UnknownTypeNode)r);
1616 }
1617 }
1618 }
1619 }
1620 }
1621 }
1622
1623 static void updateMap_unknown(Map um, Iterator i, Map m) {
1624 while (i.hasNext()) {
1625 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
1626 jq_Field f = (jq_Field)e.getKey();
1627 Object o = e.getValue();
1628 if (o == null) continue;
1629 if (o instanceof Node) {
1630 Object q = um.get(o);
1631 if (q == null) q = o;
1632 else if (TRACE_INTRA) out.println("Updated edge "+f+" "+o+" to "+q);
1633 m.put(f, q);
1634 } else {
1635 Set lhs = NodeSet.FACTORY.makeSet();
1636 m.put(f, lhs);
1637 for (Iterator j=((Set)o).iterator(); j.hasNext(); ) {
1638 Object r = j.next();
1639 Assert._assert(r != null);
1640 Object q = um.get(r);
1641 if (q == null) q = r;
1642 else if (TRACE_INTRA) out.println("Updated edge "+f+" "+r+" to "+q);
1643 lhs.add(q);
1644 }
1645 }
1646 }
1647 }
1648
1649 /*** Update all predecessor and successor nodes with the given update map.
1650 * Also clones the passed parameter set.
1651 */
1652 public void update(HashMap um) {
1653 if (TRACE_INTRA) out.println("Updating edges for node "+this.toString_long());
1654 Map m = this.predecessors;
1655 if (m != null) {
1656 this.predecessors = new LinkedHashMap();
1657 updateMap(um, m.entrySet().iterator(), this.predecessors);
1658 }
1659 m = this.addedEdges;
1660 if (m != null) {
1661 this.addedEdges = new LinkedHashMap();
1662 updateMap(um, m.entrySet().iterator(), this.addedEdges);
1663 }
1664 m = this.accessPathEdges;
1665 if (m != null) {
1666 this.accessPathEdges = new LinkedHashMap();
1667 updateMap(um, m.entrySet().iterator(), this.accessPathEdges);
1668 }
1669 if (this.passedParameters != null) {
1670 Set pp = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
1671 pp.addAll(this.passedParameters);
1672 this.passedParameters = pp;
1673 }
1674 addGlobalEdges(this);
1675 }
1676
1677 /*** Return the declared type of this node. */
1678 public abstract jq_Reference getDeclaredType();
1679
1680 /*** Return the method that this node is defined in, null if it
1681 * doesn't come from a method.
1682 */
1683 public abstract jq_Method getDefiningMethod();
1684
1685 /*** Return a shallow copy of this node. */
1686 public abstract Node copy();
1687
1688 public boolean hasPredecessor(jq_Field f, Node n) {
1689 Object o = this.predecessors.get(f);
1690 if (o instanceof Node) {
1691 if (n != o) {
1692 Assert.UNREACHABLE("predecessor of "+this+" should be "+n+", but is "+o);
1693 return false;
1694 }
1695 } else if (o == null) {
1696 Assert.UNREACHABLE("predecessor of "+this+" should be "+n+", but is missing");
1697 return false;
1698 } else {
1699 Set s = (Set) o;
1700 if (!s.contains(n)) {
1701 Assert.UNREACHABLE("predecessor of "+this+" should be "+n);
1702 return false;
1703 }
1704 }
1705 return true;
1706 }
1707
1708 /*** Remove the given predecessor node on the given field from the predecessor set.
1709 * Returns true if that predecessor existed, false otherwise. */
1710 public boolean removePredecessor(jq_Field m, Node n) {
1711 if (predecessors == null) return false;
1712 Object o = predecessors.get(m);
1713 if (o instanceof Set) return ((Set)o).remove(n);
1714 else if (o == n) { predecessors.remove(m); return true; }
1715 else return false;
1716 }
1717 /*** Add the given predecessor node on the given field to the predecessor set.
1718 * Returns true if that predecessor didn't already exist, false otherwise. */
1719 public boolean addPredecessor(jq_Field m, Node n) {
1720 if (predecessors == null) predecessors = new LinkedHashMap();
1721 Object o = predecessors.get(m);
1722 if (o == null) {
1723 predecessors.put(m, n);
1724 return true;
1725 }
1726 if (o instanceof Set) return ((Set)o).add(n);
1727 if (o == n) return false;
1728 Set s = NodeSet.FACTORY.makeSet(); s.add(o); s.add(n);
1729 predecessors.put(m, s);
1730 return true;
1731 }
1732
1733 /*** Return a set of Map.Entry objects corresponding to the incoming inside edges
1734 * of this node. */
1735 public Set getPredecessors() {
1736 if (predecessors == null) return Collections.EMPTY_SET;
1737 return predecessors.entrySet();
1738 }
1739
1740 public Collection getPredecessorTargets() {
1741 if (predecessors == null) return Collections.EMPTY_SET;
1742 return new FlattenedCollection(predecessors.values());
1743 }
1744
1745 /*** Record the given passed parameter in the set for this node.
1746 * Returns true if that passed parameter didn't already exist, false otherwise. */
1747 public boolean recordPassedParameter(PassedParameter cm) {
1748 if (passedParameters == null) passedParameters = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
1749 return passedParameters.add(cm);
1750 }
1751 /*** Record the passed parameter of the given method call and argument number in
1752 * the set for this node.
1753 * Returns true if that passed parameter didn't already exist, false otherwise. */
1754 public boolean recordPassedParameter(ProgramLocation m, int paramNum) {
1755 if (passedParameters == null) passedParameters = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
1756 PassedParameter cm = new PassedParameter(m, paramNum);
1757 return passedParameters.add(cm);
1758 }
1759 private boolean _removeEdge(jq_Field m, Node n) {
1760 Object o = addedEdges.get(m);
1761 if (o instanceof Set) return ((Set)o).remove(n);
1762 else if (o == n) { addedEdges.remove(m); return true; }
1763 else return false;
1764 }
1765 /*** Remove the given successor node on the given field from the inside edge set.
1766 * Also removes the predecessor link from the successor node to this node.
1767 * Returns true if that edge existed, false otherwise. */
1768 public boolean removeEdge(jq_Field m, Node n) {
1769 if (addedEdges == null) return false;
1770 n.removePredecessor(m, this);
1771 return _removeEdge(m, n);
1772 }
1773 public boolean hasNonEscapingEdge(jq_Field m, Node n) {
1774 if (addedEdges == null) return false;
1775 Object o = addedEdges.get(m);
1776 if (o == n) return true;
1777 if (o instanceof Set) {
1778 return ((Set)o).contains(n);
1779 }
1780 return false;
1781 }
1782 /*** Add the given successor node on the given field to the inside edge set.
1783 * Also adds a predecessor link from the successor node to this node.
1784 * Returns true if that edge didn't already exist, false otherwise. */
1785 public boolean addEdge(jq_Field m, Node n) {
1786
1787
1788
1789
1790
1791 n.addPredecessor(m, this);
1792 if (addedEdges == null) addedEdges = new LinkedHashMap();
1793 Object o = addedEdges.get(m);
1794 if (o == null) {
1795 addedEdges.put(m, n);
1796 return true;
1797 }
1798 if (o instanceof Set) {
1799 return ((Set)o).add(n);
1800 }
1801 if (o == n) {
1802 return false;
1803 }
1804 Set s = NodeSet.FACTORY.makeSet(); s.add(o); s.add(n);
1805 addedEdges.put(m, s);
1806 return true;
1807 }
1808 /*** Add the given set of successor nodes on the given field to the inside edge set.
1809 * The given set is consumed.
1810 * Also adds predecessor links from the successor nodes to this node.
1811 * Returns true if the inside edge set changed, false otherwise. */
1812 public boolean addEdges(jq_Field m, Set s) {
1813
1814
1815
1816 for (Iterator i=s.iterator(); i.hasNext(); ) {
1817 Node n = (Node)i.next();
1818
1819
1820
1821
1822 n.addPredecessor(m, this);
1823 }
1824 if (addedEdges == null) addedEdges = new LinkedHashMap();
1825 Object o = addedEdges.get(m);
1826 if (o == null) {
1827 addedEdges.put(m, s);
1828 return true;
1829 }
1830 if (o instanceof Set) {
1831 return ((Set)o).addAll(s);
1832 }
1833 addedEdges.put(m, s); return s.add(o);
1834 }
1835 /*** Add the given successor node on the given field to the inside edge set
1836 * of all of the given set of nodes.
1837 * Also adds predecessor links from the successor node to the given nodes.
1838 * Returns true if anything was changed, false otherwise. */
1839 public static boolean addEdges(Set s, jq_Field f, Node n) {
1840 boolean b = false;
1841 for (Iterator i=s.iterator(); i.hasNext(); ) {
1842 Node a = (Node)i.next();
1843 if (a.addEdge(f, n))
1844 b = true;
1845 }
1846 return b;
1847 }
1848
1849 private boolean _removeAccessPathEdge(jq_Field m, FieldNode n) {
1850 Object o = accessPathEdges.get(m);
1851 if (o instanceof Set) return ((Set)o).remove(n);
1852 else if (o == n) { accessPathEdges.remove(m); return true; }
1853 else return false;
1854 }
1855 /*** Remove the given successor node on the given field from the outside edge set.
1856 * Also removes the predecessor link from the successor node to this node.
1857 * Returns true if that edge existed, false otherwise. */
1858 public boolean removeAccessPathEdge(jq_Field m, FieldNode n) {
1859 if (accessPathEdges == null) return false;
1860 if (n.field_predecessors != null) n.field_predecessors.remove(this);
1861 return _removeAccessPathEdge(m, n);
1862 }
1863 public boolean hasAccessPathEdge(jq_Field m, Node n) {
1864 if (accessPathEdges == null) return false;
1865 Object o = accessPathEdges.get(m);
1866 if (o == n) return true;
1867 if (o instanceof Set) {
1868 return ((Set)o).contains(n);
1869 }
1870 return false;
1871 }
1872 /*** Add the given successor node on the given field to the outside edge set.
1873 * Also adds a predecessor link from the successor node to this node.
1874 * Returns true if that edge didn't already exist, false otherwise. */
1875 public boolean addAccessPathEdge(jq_Field m, FieldNode n) {
1876 if (n.field_predecessors == null) n.field_predecessors = NodeSet.FACTORY.makeSet();
1877 n.field_predecessors.add(this);
1878 if (accessPathEdges == null) accessPathEdges = new LinkedHashMap();
1879 Object o = accessPathEdges.get(m);
1880 if (o == null) {
1881 accessPathEdges.put(m, n);
1882 return true;
1883 }
1884 if (o instanceof Set) return ((Set)o).add(n);
1885 if (o == n) return false;
1886 Set s = NodeSet.FACTORY.makeSet(); s.add(o); s.add(n);
1887 accessPathEdges.put(m, s);
1888 return true;
1889 }
1890 /*** Add the given set of successor nodes on the given field to the outside edge set.
1891 * The given set is consumed.
1892 * Also adds predecessor links from the successor nodes to this node.
1893 * Returns true if the inside edge set changed, false otherwise. */
1894 public boolean addAccessPathEdges(jq_Field m, Set s) {
1895 for (Iterator i=s.iterator(); i.hasNext(); ) {
1896 FieldNode n = (FieldNode)i.next();
1897 if (n.field_predecessors == null) n.field_predecessors = NodeSet.FACTORY.makeSet();
1898 n.field_predecessors.add(this);
1899 }
1900 if (accessPathEdges == null) accessPathEdges = new LinkedHashMap();
1901 Object o = accessPathEdges.get(m);
1902 if (o == null) {
1903 accessPathEdges.put(m, s);
1904 return true;
1905 }
1906 if (o instanceof Set) return ((Set)o).addAll(s);
1907 accessPathEdges.put(m, s); return s.add(o);
1908 }
1909
1910 /*** Add the nodes that are targets of inside edges on the given field
1911 * to the given result set. */
1912 public final void getAllEdges(jq_Field m, Set result) {
1913 if (addedEdges != null) {
1914 Object o = addedEdges.get(m);
1915 if (o != null) {
1916 if (o instanceof Set) {
1917 result.addAll((Set)o);
1918 } else {
1919 result.add(o);
1920 }
1921 }
1922 }
1923 if (this.escapes)
1924 getEdges_escaped(m, result);
1925 }
1926
1927 public final Set getAllEdges(jq_Field m) {
1928 if (addedEdges != null) {
1929 Object o = addedEdges.get(m);
1930 if (o != null) {
1931 if (o instanceof Set) {
1932 Set s = NodeSet.FACTORY.makeSet((Set)o);
1933 if (this.escapes)
1934 getEdges_escaped(m, s);
1935 return s;
1936 } else {
1937 if (this.escapes) {
1938 Set s = NodeSet.FACTORY.makeSet(2);
1939 s.add(o);
1940 getEdges_escaped(m, s);
1941 return s;
1942 }
1943 return Collections.singleton(o);
1944 }
1945 }
1946 }
1947 if (this.escapes) {
1948 Set s = NodeSet.FACTORY.makeSet(1);
1949 getEdges_escaped(m, s);
1950 return s;
1951 }
1952 return Collections.EMPTY_SET;
1953 }
1954
1955 public final Set getAllEdges() {
1956 if (this.escapes) {
1957 jq_Reference type = getDeclaredType();
1958 Set result = new LinkedHashSet();
1959 if (type instanceof jq_Class) {
1960 jq_Class c = (jq_Class) type;
1961 c.prepare();
1962 for (Iterator i = Arrays.asList(c.getInstanceFields()).iterator();
1963 i.hasNext(); ) {
1964 final jq_InstanceField f = (jq_InstanceField) i.next();
1965 if (!f.getType().isReferenceType()) continue;
1966 final Set r = NodeSet.FACTORY.makeSet();
1967 getEdges_escaped(f, r);
1968 result.add(new Map.Entry() {
1969 public Object getKey() {
1970 return f;
1971 }
1972 public Object getValue() {
1973 return r;
1974 }
1975 public Object setValue(Object value) {
1976 throw new UnsupportedOperationException();
1977 }
1978 });
1979 }
1980 }
1981 if (addedEdges != null) {
1982 result.addAll(addedEdges.entrySet());
1983 }
1984 return result;
1985 }
1986 if (addedEdges != null) {
1987 return addedEdges.entrySet();
1988 }
1989 return Collections.EMPTY_SET;
1990 }
1991
1992 public final Set getNonEscapingEdges(jq_Field m) {
1993 if (addedEdges == null) return Collections.EMPTY_SET;
1994 Object o = addedEdges.get(m);
1995 if (o == null) return Collections.EMPTY_SET;
1996 if (o instanceof Set) {
1997 return (Set)o;
1998 } else {
1999 return Collections.singleton(o);
2000 }
2001 }
2002
2003 /*** Add the nodes that are targets of inside edges on the given field
2004 * to the given result set. */
2005 public void getEdges_escaped(jq_Field m, Set result) {
2006 if (TRACE_INTER) out.println("Getting escaped edges "+this+"."+m);
2007 jq_Reference type = this.getDeclaredType();
2008 if (m == null) {
2009 if (type != null && (type.isArrayType() || type == PrimordialClassLoader.getJavaLangObject()))
2010 result.add(UnknownTypeNode.get(PrimordialClassLoader.getJavaLangObject()));
2011 return;
2012 }
2013 if (type != null) {
2014 type.prepare();
2015 m.getDeclaringClass().prepare();
2016 if (TypeCheck.isAssignable((jq_Type)type, (jq_Type)m.getDeclaringClass()) ||
2017 TypeCheck.isAssignable((jq_Type)m.getDeclaringClass(), (jq_Type)type)) {
2018 jq_Reference r = (jq_Reference)m.getType();
2019 result.add(UnknownTypeNode.get(r));
2020 } else {
2021 if (TRACE_INTER) out.println("Object of type "+type+" cannot possibly have field "+m);
2022 }
2023 }
2024 if (TRACE_INTER) out.println("New result: "+result);
2025 }
2026
2027 /*** Return a set of Map.Entry objects corresponding to the inside edges
2028 * of this node. */
2029 public Set getNonEscapingEdges() {
2030 if (addedEdges == null) return Collections.EMPTY_SET;
2031 return addedEdges.entrySet();
2032 }
2033
2034 /*** Return the set of fields that this node has inside edges with. */
2035 public Set getNonEscapingEdgeFields() {
2036 if (addedEdges == null) return Collections.EMPTY_SET;
2037 return addedEdges.keySet();
2038 }
2039
2040 /*** Return the collection of target nodes that this node has inside
2041 * edges with. */
2042 public Collection getNonEscapingEdgeTargets() {
2043 if (addedEdges == null) return Collections.EMPTY_SET;
2044 return new FlattenedCollection(addedEdges.values());
2045 }
2046
2047 /*** Returns true if this node has any added inside edges. */
2048 public boolean hasNonEscapingEdges() {
2049 return addedEdges != null;
2050 }
2051
2052 /*** Returns true if this node has any added outside edges. */
2053 public boolean hasAccessPathEdges() {
2054 return accessPathEdges != null;
2055 }
2056
2057 public final Set getAccessPathEdges(jq_Field m) {
2058 if (accessPathEdges == null) return Collections.EMPTY_SET;
2059 Object o = accessPathEdges.get(m);
2060 if (o == null) return Collections.EMPTY_SET;
2061 if (o instanceof Set) {
2062 return (Set)o;
2063 } else {
2064 return Collections.singleton(o);
2065 }
2066 }
2067
2068 /*** Add the nodes that are targets of outside edges on the given field
2069 * to the given result set. */
2070 public void getAccessPathEdges(jq_Field m, Set result) {
2071 if (accessPathEdges == null) return;
2072 Object o = accessPathEdges.get(m);
2073 if (o == null) return;
2074 if (o instanceof Set) {
2075 result.addAll((Set)o);
2076 } else {
2077 result.add(o);
2078 }
2079 }
2080
2081 /*** Return a set of Map.Entry objects corresponding to the outside edges
2082 * of this node. */
2083 public Set getAccessPathEdges() {
2084 if (accessPathEdges == null) return Collections.EMPTY_SET;
2085 return accessPathEdges.entrySet();
2086 }
2087
2088 /*** Return the set of fields that this node has outside edges with. */
2089 public Set getAccessPathEdgeFields() {
2090 if (accessPathEdges == null) return Collections.EMPTY_SET;
2091 return accessPathEdges.keySet();
2092 }
2093
2094 /*** Return the collection of target nodes that this node has inside
2095 * edges with. */
2096 public Collection getAccessPathEdgeTargets() {
2097 if (accessPathEdges == null) return Collections.EMPTY_SET;
2098 return new FlattenedCollection(accessPathEdges.values());
2099 }
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109 public void setEscapes() { this.escapes = true; }
2110 public boolean getEscapes() { return this.escapes; }
2111
2112 /*** Return a string representation of the node in short form. */
2113 public abstract String toString_short();
2114 public String toString() {
2115 return toString_short() + (this.escapes?"*":"");
2116 }
2117 /*** Return a string representation of the node in long form.
2118 * Includes inside and outside edges and passed parameters. */
2119 public String toString_long() {
2120 StringBuffer sb = new StringBuffer();
2121 if (addedEdges != null) {
2122 sb.append(" writes: ");
2123 for (Iterator i=addedEdges.entrySet().iterator(); i.hasNext(); ) {
2124 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
2125 jq_Field f = (jq_Field)e.getKey();
2126 Object o = e.getValue();
2127 if (o == null) continue;
2128 sb.append(f);
2129 sb.append("={");
2130 if (o instanceof Node)
2131 sb.append(((Node)o).toString_short());
2132 else {
2133 for (Iterator j=((Set)o).iterator(); j.hasNext(); ) {
2134 sb.append(((Node)j.next()).toString_short());
2135 if (j.hasNext()) sb.append(", ");
2136 }
2137 }
2138 sb.append("} ");
2139 }
2140 }
2141 if (accessPathEdges != null) {
2142 sb.append(" reads: ");
2143 sb.append(accessPathEdges);
2144 }
2145 if (passedParameters != null) {
2146 sb.append(" called: ");
2147 sb.append(passedParameters);
2148 }
2149 return sb.toString();
2150 }
2151
2152 public void write(Textualizer t) throws IOException {
2153 if (addedEdges != null) {
2154 for (Iterator i = this.getNonEscapingEdges().iterator(); i.hasNext(); ) {
2155 Map.Entry e = (Map.Entry) i.next();
2156 jq_Field f = (jq_Field) e.getKey();
2157 Collection c;
2158 if (e.getValue() instanceof Collection)
2159 c = (Collection) e.getValue();
2160 else
2161 c = Collections.singleton(e.getValue());
2162 for (Iterator j = c.iterator(); j.hasNext(); ) {
2163 Node n = (Node) j.next();
2164 if (!t.contains(n)) continue;
2165 t.writeString(" succ ");
2166 t.writeObject(f);
2167 t.writeString(" ");
2168 t.writeReference(n);
2169 }
2170 }
2171 }
2172 if (predecessors != null) {
2173 for (Iterator i = this.getPredecessors().iterator(); i.hasNext(); ) {
2174 Map.Entry e = (Map.Entry) i.next();
2175 jq_Field f = (jq_Field) e.getKey();
2176 Collection c;
2177 if (e.getValue() instanceof Collection)
2178 c = (Collection) e.getValue();
2179 else
2180 c = Collections.singleton(e.getValue());
2181 for (Iterator j = c.iterator(); j.hasNext(); ) {
2182 Node n = (Node) j.next();
2183 if (!t.contains(n)) continue;
2184 t.writeString(" pred ");
2185 t.writeObject(f);
2186 t.writeString(" ");
2187 t.writeReference(n);
2188 }
2189 }
2190 }
2191 if (accessPathEdges != null) {
2192 for (Iterator i = this.getAccessPathEdgeTargets().iterator(); i.hasNext(); ) {
2193 Node n = (Node) i.next();
2194 if (!t.contains(n)) continue;
2195 t.writeEdge("fsucc", n);
2196 }
2197 }
2198 }
2199
2200 public void readEdges(IndexMap map, StringTokenizer st) {
2201 while (st.hasMoreElements()) {
2202 String edgeName = st.nextToken();
2203 if (edgeName.equals("succ")) {
2204 jq_Field f = (jq_Field) jq_Member.read(st);
2205 int index = Integer.parseInt(st.nextToken());
2206 if (index < map.size()) {
2207 addEdge(f, (Node) map.get(index));
2208 }
2209 } else if (edgeName.equals("pred")) {
2210 jq_Field f = (jq_Field) jq_Member.read(st);
2211 int index = Integer.parseInt(st.nextToken());
2212 if (index < map.size()) {
2213 Node that = (Node) map.get(index);
2214 that.addEdge(f, this);
2215 }
2216 } else if (edgeName.equals("fsucc")) {
2217 int index = Integer.parseInt(st.nextToken());
2218 if (index < map.size()) {
2219 FieldNode fn = (FieldNode) map.get(index);
2220 addAccessPathEdge(fn.getField(), fn);
2221 }
2222 } else if (edgeName.equals("fpred")) {
2223 int index = Integer.parseInt(st.nextToken());
2224 if (index < map.size()) {
2225 Node n = (Node) map.get(index);
2226 FieldNode fn = (FieldNode) this;
2227 n.addAccessPathEdge(fn.getField(), fn);
2228 }
2229 } else {
2230 Assert.UNREACHABLE(edgeName);
2231 }
2232 }
2233 }
2234
2235
2236
2237
2238 public void addEdge(String edge, Textualizable t) { }
2239
2240
2241
2242
2243 public void writeEdges(Textualizer t) throws IOException { }
2244
2245 }
2246
2247 /*** A CheckCastNode refers to the result of a CheckCast instruction
2248 */
2249 public static final class CheckCastNode extends Node {
2250 jq_Reference dstType;
2251 final ProgramLocation q;
2252
2253 public String toString_short() {
2254 return q.getEmacsName() + " Cast to (" + dstType.shortName() + ") @ "+(q==null?-1:q.getID());
2255 }
2256 private CheckCastNode(jq_Reference dstType, ProgramLocation q) {
2257 this.dstType = dstType;
2258 this.q = q;
2259 }
2260 private static HashMap
2261 public static CheckCastNode get(jq_Reference dstType, ProgramLocation q) {
2262 Pair key = new Pair(dstType, q);
2263 CheckCastNode n = (CheckCastNode)FACTORY.get(key);
2264 if (n == null) {
2265 FACTORY.put(key, n = new CheckCastNode(dstType, q));
2266 }
2267 return n;
2268 }
2269 public CheckCastNode(CheckCastNode that) {
2270 super(that);
2271 this.dstType = that.dstType;
2272 this.q = that.q;
2273 }
2274 public Node copy() { return new CheckCastNode(this); }
2275 public jq_Reference getDeclaredType() { return dstType; }
2276 public jq_Method getDefiningMethod() { return q.getMethod(); }
2277 public ProgramLocation getLocation() { return q; }
2278
2279 public void write(Textualizer t) throws IOException {
2280 dstType.write(t);
2281 t.writeString(" ");
2282 q.write(t);
2283 super.write(t);
2284 }
2285
2286 public static Node read(StringTokenizer st) {
2287 jq_Reference type = (jq_Reference) jq_Type.read(st);
2288 ProgramLocation q = ProgramLocation.read(st);
2289 CheckCastNode n = CheckCastNode.get(type, q);
2290
2291 return n;
2292 }
2293 }
2294
2295 /*** A ConcreteTypeNode refers to an object with a concrete type.
2296 * This is the result of a 'new' operation or a constant object.
2297 * It is tied to the quad that created it, so nodes of the same type but
2298 * from different quads are not equal.
2299 */
2300 public static final class ConcreteTypeNode extends Node implements HeapObject {
2301 final jq_Reference type;
2302 final ProgramLocation q;
2303 final Integer opn;
2304
2305 static final HashMap FACTORY = new HashMap();
2306 public static ConcreteTypeNode get(jq_Reference type) {
2307 ConcreteTypeNode n = (ConcreteTypeNode)FACTORY.get(type);
2308 if (n == null) {
2309 FACTORY.put(type, n = new ConcreteTypeNode(type));
2310 }
2311 return n;
2312 }
2313
2314 public final Node copy() { return new ConcreteTypeNode(this); }
2315
2316 private ConcreteTypeNode(jq_Reference type) {
2317 this.type = type; this.q = null; this.opn = null;
2318 }
2319 static final HashMap FACTORY2 = new HashMap();
2320 public static ConcreteTypeNode get(jq_Reference type, ProgramLocation q) {
2321 return get(type, q, new Integer(0));
2322 }
2323 public static ConcreteTypeNode get(jq_Reference type, ProgramLocation q, Integer opn) {
2324 Triple key = new Triple(type, q, opn);
2325 ConcreteTypeNode n = (ConcreteTypeNode)FACTORY2.get(key);
2326 if (n == null) {
2327 FACTORY2.put(key, n = new ConcreteTypeNode(type, q, opn));
2328 }
2329 return n;
2330 }
2331
2332 private ConcreteTypeNode(jq_Reference type, ProgramLocation q, Integer opn) {
2333 this.type = type; this.q = q; this.opn = opn;
2334 }
2335
2336 private ConcreteTypeNode(ConcreteTypeNode that) {
2337 super(that);
2338 this.type = that.type; this.q = that.q; this.opn = that.opn;
2339 }
2340
2341 public ProgramLocation getLocation() { return q; }
2342
2343 public jq_Method getDefiningMethod() {
2344 if (q == null) return null;
2345 return q.getMethod();
2346 }
2347
2348 public jq_Reference getDeclaredType() { return type; }
2349
2350 public String toString_long() {
2351 return Integer.toHexString(this.hashCode())+": "+toString_short()+super.toString_long();
2352 }
2353 public String toString_short() {
2354 return (q==null?"":q.getEmacsName())+" Concrete: "+(type==null?"null":type.shortName())+" @ "+(q==null?-1:q.getID());
2355 }
2356
2357 public void write(Textualizer t) throws IOException {
2358 if (type == null) t.writeString("null ");
2359 else {
2360 type.write(t);
2361 t.writeString(" ");
2362 }
2363 if (opn == null) t.writeString("null ");
2364 else t.writeString(opn.toString()+" ");
2365 t.writeObject(q);
2366 super.write(t);
2367 }
2368
2369 public static ConcreteTypeNode read(StringTokenizer st) {
2370 jq_Reference type = (jq_Reference) jq_Type.read(st);
2371 String opns = st.nextToken();
2372 Integer opn = opns.equals("null") ? null : Integer.decode(opns);
2373 ProgramLocation pl = ProgramLocation.read(st);
2374 ConcreteTypeNode n = ConcreteTypeNode.get(type, pl, opn);
2375
2376 return n;
2377 }
2378 }
2379
2380 /*** A ConcreteObjectNode refers to an object that we discovered through reflection.
2381 * It includes a reference to the actual object instance.
2382 */
2383 public static final class ConcreteObjectNode extends Node implements HeapObject {
2384 Object object;
2385 final Object key;
2386 final ProgramLocation q;
2387
2388 public static Collection getAll() {
2389 return FACTORY.values();
2390 }
2391
2392 public static final boolean ADD_EDGES = true;
2393 static final HashMap FACTORY = new HashMap();
2394 public static ConcreteObjectNode get(AConstOperand op, ProgramLocation q) {
2395 Object key = q;
2396 if (!Operand.Util.isNullConstant(op)) {
2397 key = q.getContainingClass().findStringConstant((String)op.getValue());
2398 Assert._assert(key != null);
2399 jq_Method meth = q.getMethod();
2400 key = new Pair(key, meth);
2401 }
2402 ConcreteObjectNode n = get(key, op.getValue(), q);
2403 return n;
2404 }
2405 private static ConcreteObjectNode get(Object key, Object o, ProgramLocation q) {
2406 ConcreteObjectNode n = (ConcreteObjectNode) FACTORY.get(key);
2407 if (n == null) {
2408 FACTORY.put(key, n = new ConcreteObjectNode(key, o, q));
2409 }
2410 return n;
2411 }
2412 public static ConcreteObjectNode get(jq_Field f, Object o) {
2413 List path = new ArrayList();
2414 path.add(f);
2415 return explore(path, o);
2416 }
2417 static HashSet explored = new HashSet();
2418 private static ConcreteObjectNode explore(List
2419 ConcreteObjectNode n = get(
2420 n.object = o;
2421 if (o != null) {
2422 if (ADD_EDGES && !explored.contains(o)) {
2423 explored.add(o);
2424
2425 jq_Reference type = jq_Reference.getTypeOf(o);
2426 if (type.isClassType()) {
2427 jq_Class c = (jq_Class) type;
2428 c.prepare();
2429 jq_InstanceField[] ifs = c.getInstanceFields();
2430 for (int i=0; i<ifs.length; ++i) {
2431 if (ifs[i].getType().isPrimitiveType()) continue;
2432 Object p = Reflection.getfield_A(o, ifs[i]);
2433 ArrayList np = new ArrayList(path);
2434 np.add(ifs[i]);
2435 n.addEdge(ifs[i], explore(np, p));
2436 }
2437 } else {
2438 Assert._assert(type.isArrayType());
2439 jq_Array a = (jq_Array) type;
2440 if (a.getElementType().isReferenceType()) {
2441 Object[] oa = (Object[]) o;
2442 for (int i=0; i<oa.length; ++i) {
2443 ArrayList np = new ArrayList(path);
2444 np.add((jq_Field) null);
2445 n.addEdge((jq_Field) null, explore(np, oa[i]));
2446 }
2447 }
2448 }
2449 }
2450 }
2451 return n;
2452 }
2453
2454 public ProgramLocation getLocation() { return q; }
2455
2456 public final Node copy() { return new ConcreteObjectNode(this); }
2457
2458 private ConcreteObjectNode(Object key, Object o, ProgramLocation q) {
2459 this.key = key; this.object = o; this.q = q;
2460 }
2461
2462 private ConcreteObjectNode(ConcreteObjectNode that) {
2463 super(that);
2464 this.object = that.object;
2465 this.key = that.key;
2466 this.q = that.q;
2467 }
2468
2469 public jq_Method getDefiningMethod() { return null; }
2470
2471 public jq_Reference getDeclaredType() {
2472 if (object == null) return null;
2473 return jq_Reference.getTypeOf(object);
2474 }
2475
2476 public String toString_long() { return Integer.toHexString(this.hashCode())+": "+toString_short()+super.toString_long(); }
2477 public String toString_short() {
2478 return (q==null?"":q.getEmacsName())+" Object: "+(getDeclaredType()==null?"null":getDeclaredType().shortName())+" @ "+(q==null?-1:q.getID());
2479 }
2480
2481
2482
2483
2484 public Set getNonEscapingEdgeFields() {
2485 if (ADD_EDGES)
2486 return super.getNonEscapingEdgeFields();
2487 if (object == null) return Collections.EMPTY_SET;
2488 jq_Reference type = jq_Reference.getTypeOf(object);
2489 HashSet ll = new HashSet();
2490 if (type.isClassType()) {
2491 jq_Class c = (jq_Class) type;
2492 c.prepare();
2493 jq_InstanceField[] ifs = c.getInstanceFields();
2494 for (int i=0; i<ifs.length; ++i) {
2495 if (ifs[i].getType().isPrimitiveType()) continue;
2496 ll.add(ifs[i]);
2497 }
2498 } else {
2499 Assert._assert(type.isArrayType());
2500 jq_Array a = (jq_Array) type;
2501 if (a.getElementType().isReferenceType()) {
2502 ll.add(null);
2503 }
2504 }
2505 ll.addAll(super.getNonEscapingEdgeFields());
2506 return ll;
2507 }
2508
2509
2510
2511
2512 public Set getEdges() {
2513 if (ADD_EDGES)
2514 return super.getNonEscapingEdges();
2515 if (object == null) return Collections.EMPTY_SET;
2516 jq_Reference type = jq_Reference.getTypeOf(object);
2517 HashMap ll = new HashMap();
2518 if (type.isClassType()) {
2519 jq_Class c = (jq_Class) type;
2520 c.prepare();
2521 jq_InstanceField[] ifs = c.getInstanceFields();
2522 for (int i=0; i<ifs.length; ++i) {
2523 if (ifs[i].getType().isPrimitiveType()) continue;
2524 ll.put(ifs[i], get(ifs[i], Reflection.getfield_A(object, ifs[i])));
2525 }
2526 } else {
2527 Assert._assert(type.isArrayType());
2528 jq_Array a = (jq_Array) type;
2529 if (a.getElementType().isReferenceType()) {
2530 Object[] oa = (Object[]) object;
2531 for (int i=0; i<oa.length; ++i) {
2532 ll.put(null, get((jq_Field)null, oa[i]));
2533 }
2534 }
2535 }
2536 if (addedEdges != null)
2537 ll.putAll(addedEdges);
2538 return ll.entrySet();
2539 }
2540
2541 public boolean hasNonEscapingEdge(jq_Field m, Node n) {
2542 if (ADD_EDGES)
2543 return super.hasNonEscapingEdge(m, n);
2544 if (object == null)
2545 return false;
2546 if (!(n instanceof ConcreteObjectNode))
2547 return super.hasNonEscapingEdge(m, n);
2548 Object other = ((ConcreteObjectNode) n).object;
2549 jq_Reference type = jq_Reference.getTypeOf(object);
2550 if (type.isClassType()) {
2551 jq_Class c = (jq_Class) type;
2552 c.prepare();
2553 jq_InstanceField[] ifs = c.getInstanceFields();
2554 if (!Arrays.asList(ifs).contains(m)) return false;
2555 Object p = Reflection.getfield_A(object, (jq_InstanceField) m);
2556 if (p == other) return true;
2557 } else {
2558 Assert._assert(type.isArrayType());
2559 if (m != null) return false;
2560 jq_Array a = (jq_Array) type;
2561 if (!a.getElementType().isReferenceType()) return false;
2562 Object[] oa = (Object[]) object;
2563 for (int i=0; i<oa.length; ++i) {
2564 if (other == oa[i]) return true;
2565 }
2566 }
2567 return super.hasNonEscapingEdge(m, n);
2568 }
2569
2570
2571
2572
2573 public boolean hasEdges() {
2574 if (ADD_EDGES)
2575 return super.hasNonEscapingEdges();
2576 return object != null;
2577 }
2578
2579 public boolean removeEdge(jq_Field m, Node n) {
2580 Assert._assert(!(n instanceof ConcreteObjectNode));
2581 return super.removeEdge(m, n);
2582 }
2583
2584 public void write(Textualizer t) throws IOException {
2585 if (object == null && q instanceof ProgramLocation) t.writeString("nullconstant");
2586 else if (key instanceof Pair) {
2587 t.writeString("stringconstant ");
2588 Pair p = (Pair)key;
2589 ((jq_Class.StringConstant)p.left).write(t);
2590 t.writeString(" ");
2591 t.writeObject((jq_Method)p.right);
2592 } else {
2593 t.writeString("object");
2594 List l = (List)key;
2595 t.writeString(" " + l.size());
2596 for (int i = 0; i < l.size(); i++) {
2597 t.writeString(" ");
2598 jq_Field f = ((jq_Field)l.get(i));
2599 t.writeObject(f);
2600 }
2601 }
2602
2603 t.writeString(" ");
2604 t.writeObject(q);
2605 super.write(t);
2606 }
2607
2608 public static Node read(StringTokenizer st) {
2609 String what = st.nextToken();
2610 Object key, o;
2611 ProgramLocation pl;
2612 if (what.equals("nullconstant")) {
2613 o = null;
2614 key = pl = ProgramLocation.read(st);
2615 } else if (what.equals("stringconstant")) {
2616 jq_Class.StringConstant sc = jq_Class.readStringConstant(st);
2617 jq_Method m = (jq_Method)jq_Member.read(st);
2618 key = new Pair(sc, m);
2619 o = sc.getString();
2620 pl = ProgramLocation.read(st);
2621 } else if (what.equals("object")) {
2622 int n = Integer.parseInt(st.nextToken());
2623 ArrayList al = new ArrayList(n);
2624 for (int i = 0; i < n; i++) {
2625 al.add(jq_Member.read(st));
2626 }
2627 key = al;
2628 pl = ProgramLocation.read(st);
2629 o = null;
2630
2631 } else
2632 throw new InternalError("bad tag " + what);
2633
2634 return ConcreteObjectNode.get(key, o, pl);
2635 }
2636 }
2637
2638 /*** A UnknownTypeNode refers to an object with an unknown type. All that is
2639 * known is that the object is the same or a subtype of some given type.
2640 * Nodes with the same "type" are considered to be equal.
2641 * This class includes a factory to get UnknownTypeNode's.
2642 */
2643 public static final class UnknownTypeNode extends Node implements HeapObject {
2644 public static final boolean ADD_DUMMY_EDGES = false;
2645
2646 static final HashMap FACTORY = new HashMap();
2647 public static UnknownTypeNode get(jq_Reference type) {
2648 UnknownTypeNode n = (UnknownTypeNode)FACTORY.get(type);
2649 if (n == null) {
2650 FACTORY.put(type, n = new UnknownTypeNode(type));
2651 if (ADD_DUMMY_EDGES) n.addDummyEdges();
2652 }
2653 return n;
2654 }
2655
2656 public static Collection getAll() {
2657 return FACTORY.values();
2658 }
2659
2660 final jq_Reference type;
2661
2662 private UnknownTypeNode(jq_Reference type) {
2663 this.type = type;
2664 this.setEscapes();
2665 }
2666
2667 private void addDummyEdges() {
2668 if (type instanceof jq_Class) {
2669 jq_Class klass = (jq_Class)type;
2670 klass.prepare();
2671 jq_InstanceField[] fields = klass.getInstanceFields();
2672 for (int i=0; i<fields.length; ++i) {
2673 jq_InstanceField f = fields[i];
2674 if (f.getType() instanceof jq_Reference) {
2675 UnknownTypeNode n = get((jq_Reference)f.getType());
2676 this.addEdge(f, n);
2677 }
2678 }
2679 } else {
2680 jq_Array array = (jq_Array)type;
2681 if (array.getElementType() instanceof jq_Reference) {
2682 UnknownTypeNode n = get((jq_Reference)array.getElementType());
2683 this.addEdge((jq_Field) null, n);
2684 }
2685 }
2686 }
2687
2688 /*** Update all predecessor and successor nodes with the given update map.
2689 * Also clones the passed parameter set.
2690 */
2691 public void update(HashMap um) {
2692 if (false) {
2693 if (TRACE_INTRA) out.println("Updating edges for node "+this.toString_long());
2694 Map m = this.predecessors;
2695 if (m != null) {
2696 this.predecessors = new LinkedHashMap();
2697 updateMap_unknown(um, m.entrySet().iterator(), this.predecessors);
2698 }
2699 m = this.addedEdges;
2700 if (m != null) {
2701 this.addedEdges = new LinkedHashMap();
2702 updateMap_unknown(um, m.entrySet().iterator(), this.addedEdges);
2703 }
2704 m = this.accessPathEdges;
2705 if (m != null) {
2706 this.accessPathEdges = new LinkedHashMap();
2707 updateMap_unknown(um, m.entrySet().iterator(), this.accessPathEdges);
2708 }
2709 if (this.passedParameters != null) {
2710 Set pp = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
2711 pp.addAll(this.passedParameters);
2712 this.passedParameters = pp;
2713 }
2714 addGlobalEdges(this);
2715 }
2716 }
2717
2718 public ProgramLocation getLocation() { return null; }
2719
2720 public jq_Method getDefiningMethod() { return null; }
2721
2722 public jq_Reference getDeclaredType() { return type; }
2723
2724 public final Node copy() { return this; }
2725
2726 public String toString_long() { return Integer.toHexString(this.hashCode())+": "+toString_short()+super.toString_long(); }
2727 public String toString_short() {
2728 return "Unknown: "+type;
2729 }
2730
2731 public void write(Textualizer t) throws IOException {
2732 getDeclaredType().write(t);
2733 super.write(t);
2734 }
2735 public static UnknownTypeNode read(StringTokenizer st) {
2736 jq_Reference type = (jq_Reference) jq_Type.read(st);
2737
2738 return new UnknownTypeNode(type);
2739 }
2740 }
2741
2742 /*** A PlaceholderNode is used to signify an object that is out-of-scope.
2743 */
2744 public static final class PlaceholderNode extends OutsideNode implements HeapObject {
2745 public static final boolean ADD_DUMMY_EDGES = false;
2746
2747 static final HashMap FACTORY = new HashMap();
2748 public static PlaceholderNode get(jq_Method m, int k) {
2749 jq_Reference type = (jq_Reference) m.getParamTypes()[k];
2750 return get(m, ""+k, type);
2751 }
2752 public static PlaceholderNode get(jq_StaticField f) {
2753 jq_Reference type = (jq_Reference) f.getType();
2754 return get(f, "field", type);
2755 }
2756 public static PlaceholderNode get(jq_Method m, String s) {
2757 jq_Reference type;
2758 if (s.equals("return")) type = (jq_Reference) m.getReturnType();
2759 else if (s.equals("throw")) type = PrimordialClassLoader.getJavaLangThrowable();
2760 else type = (jq_Reference) m.getParamTypes()[Integer.parseInt(s)];
2761 return get(m, s, type);
2762 }
2763 public static PlaceholderNode get(jq_Member m, String s, jq_Reference type) {
2764 Object key = new Pair(m, s);
2765 PlaceholderNode n = (PlaceholderNode)FACTORY.get(key);
2766 if (n == null) {
2767 FACTORY.put(key, n = new PlaceholderNode(m, s, type));
2768 }
2769 return n;
2770 }
2771
2772 public static Collection getAll() {
2773 return FACTORY.values();
2774 }
2775
2776 final jq_Member member;
2777 final String s;
2778 final jq_Reference type;
2779
2780 private PlaceholderNode(jq_Member m, String s, jq_Reference type) {
2781 this.member = m;
2782 this.s = s;
2783 this.type = type;
2784 this.setEscapes();
2785 }
2786
2787 /*** Update all predecessor and successor nodes with the given update map.
2788 * Also clones the passed parameter set.
2789 */
2790 public void update(HashMap um) {
2791 if (false) {
2792 if (TRACE_INTRA) out.println("Updating edges for node "+this.toString_long());
2793 Map m = this.predecessors;
2794 if (m != null) {
2795 this.predecessors = new LinkedHashMap();
2796 updateMap_unknown(um, m.entrySet().iterator(), this.predecessors);
2797 }
2798 m = this.addedEdges;
2799 if (m != null) {
2800 this.addedEdges = new LinkedHashMap();
2801 updateMap_unknown(um, m.entrySet().iterator(), this.addedEdges);
2802 }
2803 m = this.accessPathEdges;
2804 if (m != null) {
2805 this.accessPathEdges = new LinkedHashMap();
2806 updateMap_unknown(um, m.entrySet().iterator(), this.accessPathEdges);
2807 }
2808 if (this.passedParameters != null) {
2809 Set pp = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
2810 pp.addAll(this.passedParameters);
2811 this.passedParameters = pp;
2812 }
2813 addGlobalEdges(this);
2814 }
2815 }
2816
2817 public ProgramLocation getLocation() { return null; }
2818
2819 public jq_Method getDefiningMethod() { return null; }
2820
2821 public jq_Reference getDeclaredType() { return type; }
2822
2823 public final Node copy() { return this; }
2824
2825 public String toString_long() { return Integer.toHexString(this.hashCode())+": "+toString_short()+super.toString_long(); }
2826 public String toString_short() {
2827 return "Placeholder: "+member+" "+s+" type "+type;
2828 }
2829
2830 public void write(Textualizer t) throws IOException {
2831 member.write(t);
2832 t.writeString(s);
2833 super.write(t);
2834 }
2835 public static PlaceholderNode read(StringTokenizer st) {
2836 jq_Member m = (jq_Member) jq_Member.read(st);
2837 String s = st.nextToken();
2838
2839 jq_Reference type;
2840 if (m instanceof jq_Method) {
2841 jq_Method m2 = (jq_Method) m;
2842 if (s.equals("return")) type = (jq_Reference) m2.getReturnType();
2843 else if (s.equals("throw")) type = PrimordialClassLoader.getJavaLangThrowable();
2844 else type = (jq_Reference) m2.getParamTypes()[Integer.parseInt(s)];
2845 } else {
2846 type = (jq_Reference) ((jq_Field) m).getType();
2847 }
2848 return new PlaceholderNode(m, s, type);
2849 }
2850 }
2851
2852 /*** An outside node is some node that can be mapped to other nodes.
2853 * This is just a marker for some of the other node classes below.
2854 */
2855 public abstract static class OutsideNode extends Node {
2856 OutsideNode() {}
2857 OutsideNode(Node n) { super(n); }
2858
2859 public abstract jq_Reference getDeclaredType();
2860
2861 public OutsideNode skip;
2862 public boolean visited;
2863
2864 }
2865
2866 /*** A GlobalNode stores references to the static variables.
2867 * It has no predecessors, and there is a global copy stored in GLOBAL.
2868 */
2869 public static final class GlobalNode extends OutsideNode {
2870 jq_Method method;
2871 static final HashMap FACTORY = new HashMap();
2872 public static GlobalNode get(jq_Method m) {
2873 GlobalNode n = (GlobalNode)FACTORY.get(m);
2874 if (n == null) {
2875 FACTORY.put(m, n = new GlobalNode(m));
2876 }
2877 return n;
2878 }
2879 private GlobalNode(jq_Method m) {
2880 this.method = m;
2881 if (TRACE_INTRA) out.println("Created "+this.toString_long());
2882 }
2883 private GlobalNode(GlobalNode that) {
2884 super(that);
2885 this.method = that.method;
2886 }
2887 public jq_Reference getDeclaredType() { return null; }
2888 public jq_Method getDefiningMethod() { return method; }
2889 public final Node copy() {
2890 Assert._assert(this != GLOBAL);
2891 return new GlobalNode(this);
2892 }
2893 public String toString_long() { return Integer.toHexString(this.hashCode())+": "+toString_short()+super.toString_long(); }
2894 public String toString_short() {
2895 return "global("+(method==null?"null":method.toString())+")";
2896 }
2897 public static GlobalNode GLOBAL = GlobalNode.get((jq_Method) null);
2898
2899 public void addDefaultStatics() {
2900 jq_Class c;
2901 jq_StaticField f;
2902 Node n;
2903
2904 c = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("Ljava/lang/System;");
2905 c.load();
2906 f = (jq_StaticField) c.getDeclaredMember("in", "Ljava/io/InputStream;");
2907 Assert._assert(f != null);
2908 n = ConcreteObjectNode.get(f, System.in);
2909 addEdge(f, n);
2910 f = (jq_StaticField) c.getDeclaredMember("out", "Ljava/io/PrintStream;");
2911 Assert._assert(f != null);
2912 n = ConcreteObjectNode.get(f, System.out);
2913 addEdge(f, n);
2914 f = (jq_StaticField) c.getDeclaredMember("err", "Ljava/io/PrintStream;");
2915 Assert._assert(f != null);
2916 n = ConcreteObjectNode.get(f, System.err);
2917 addEdge(f, n);
2918
2919
2920 }
2921
2922 public void write(Textualizer t) throws IOException {
2923 t.writeObject(method);
2924 super.write(t);
2925 }
2926 public static GlobalNode read(StringTokenizer st) {
2927 jq_Method m = (jq_Method) jq_Member.read(st);
2928
2929 return GlobalNode.get(m);
2930 }
2931
2932 }
2933
2934 /*** A ReturnedNode represents a return value or thrown exception from a method call. */
2935 public abstract static class ReturnedNode extends OutsideNode {
2936 final ProgramLocation m;
2937 public ReturnedNode(ProgramLocation m) { this.m = m; }
2938 public ReturnedNode(ReturnedNode that) {
2939 super(that); this.m = that.m;
2940 }
2941 public jq_Method getDefiningMethod() {
2942 return m.getMethod();
2943 }
2944 public final ProgramLocation getLocation() { return m; }
2945 }
2946
2947 /*** A ReturnValueNode represents the return value of a method call.
2948 */
2949 public static final class ReturnValueNode extends ReturnedNode {
2950 static final HashMap FACTORY = new HashMap();
2951 public static ReturnValueNode get(ProgramLocation m) {
2952 ReturnValueNode n = (ReturnValueNode)FACTORY.get(m);
2953 if (n == null) {
2954 FACTORY.put(m, n = new ReturnValueNode(m));
2955 }
2956 return n;
2957 }
2958 private ReturnValueNode(ProgramLocation m) { super(m); }
2959 private ReturnValueNode(ReturnValueNode that) { super(that); }
2960
2961 public jq_Reference getDeclaredType() {
2962 return (jq_Reference) m.getTargetMethod().getReturnType();
2963 }
2964
2965 public final Node copy() { return new ReturnValueNode(this); }
2966
2967 public String toString_long() {
2968 return Integer.toHexString(this.hashCode())+": "+toString_short()+super.toString_long();
2969 }
2970 public String toString_short() {
2971 return m.getEmacsName()+" Return value of "+m;
2972 }
2973
2974 public void write(Textualizer t) throws IOException {
2975 m.write(t);
2976 super.write(t);
2977 }
2978 public static ReturnValueNode read(StringTokenizer st) {
2979 ProgramLocation m = ProgramLocation.read(st);
2980
2981 return ReturnValueNode.get(m);
2982 }
2983 }
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011 /*** A ThrownExceptionNode represents the thrown exception of a method call.
3012 */
3013 public static final class ThrownExceptionNode extends ReturnedNode {
3014 static final HashMap FACTORY = new HashMap();
3015 public static ThrownExceptionNode get(ProgramLocation m) {
3016 ThrownExceptionNode n = (ThrownExceptionNode)FACTORY.get(m);
3017 if (n == null) {
3018 FACTORY.put(m, n = new ThrownExceptionNode(m));
3019 }
3020 return n;
3021 }
3022 private ThrownExceptionNode(ProgramLocation m) { super(m); }
3023 private ThrownExceptionNode(ThrownExceptionNode that) { super(that); }
3024
3025 public jq_Reference getDeclaredType() { return PrimordialClassLoader.getJavaLangObject(); }
3026
3027 public final Node copy() { return new ThrownExceptionNode(this); }
3028
3029 public String toString_long() {
3030 return Integer.toHexString(this.hashCode())+": "+toString_short()+super.toString_long();
3031 }
3032 public String toString_short() {
3033 return m.getEmacsName()+" Thrown exception of "+m;
3034 }
3035
3036
3037
3038
3039 public void write(Textualizer t) throws IOException {
3040 m.write(t);
3041 super.write(t);
3042 }
3043 public static ThrownExceptionNode read(StringTokenizer st) {
3044 ProgramLocation m = ProgramLocation.read(st);
3045
3046 return ThrownExceptionNode.get(m);
3047 }
3048 }
3049
3050 /*** A ParamNode represents an incoming parameter.
3051 */
3052 public static class ParamNode extends OutsideNode {
3053 final jq_Method m; final int n; final jq_Reference declaredType;
3054 static HashMap
3055
3056 private ParamNode(jq_Method m, int n, jq_Reference declaredType) { this.m = m; this.n = n; this.declaredType = declaredType; }
3057 public static ParamNode get(jq_Method m, int n, jq_Reference declaredType) {
3058 Triple key = new Triple(m, new Integer(n), declaredType);
3059 ParamNode pnode = (ParamNode)FACTORY.get(key);
3060 if (pnode == null) {
3061 FACTORY.put(key, pnode = new ParamNode(m, n, declaredType));
3062 }
3063 return pnode;
3064 }
3065 private ParamNode(ParamNode that) {
3066 this.m = that.m; this.n = that.n; this.declaredType = that.declaredType;
3067 }
3068 public jq_Reference getDeclaredType() { return declaredType; }
3069 public jq_Method getDefiningMethod() { return m; }
3070
3071 public jq_Method getMethod() { return m; }
3072 public int getIndex() { return n; }
3073
3074 public Node copy() { return new ParamNode(this); }
3075
3076 public String toString_long() {
3077 return Integer.toHexString(this.hashCode())+": "+this.toString_short()+super.toString_long();
3078 }
3079 public String toString_short() {
3080 return "Param#"+n+" method "+m;
3081 }
3082
3083
3084
3085
3086 public void write(Textualizer t) throws IOException {
3087 m.write(t);
3088 t.writeString(" "+n);
3089 super.write(t);
3090 }
3091 public static ParamNode read(StringTokenizer st) {
3092 jq_Method m = (jq_Method) jq_Member.read(st);
3093 int k = Integer.parseInt(st.nextToken());
3094 jq_Reference type = (jq_Reference) m.getParamTypes()[k];
3095
3096 return get(m, k, type);
3097 }
3098 }
3099
3100
3101 public static final class FakeParamNode extends ParamNode {
3102 static final HashMap FACTORY = new HashMap();
3103 public static FakeParamNode getFake(jq_Method m, int n, jq_Reference declaredType) {
3104 Triple key = new Triple(m, new Integer(n), declaredType);
3105 FakeParamNode fn = (FakeParamNode)FACTORY.get(key);
3106 if (fn == null) {
3107 FACTORY.put(key, fn = new FakeParamNode(m, n, declaredType));
3108 }
3109 return fn;
3110 }
3111 private FakeParamNode(jq_Method m, int n, jq_Reference declaredType) {
3112 super(m, n, declaredType);
3113 }
3114 private FakeParamNode(FakeParamNode that) {
3115 super(that);
3116 }
3117 public final Node copy() { return new FakeParamNode(this); }
3118
3119 public static ParamNode read(StringTokenizer st) {
3120 jq_Method m = (jq_Method) jq_FakeInstanceMethod.read(st);
3121 int k = Integer.parseInt(st.nextToken());
3122 jq_Reference type = (jq_Reference) m.getParamTypes()[k];
3123
3124 return FakeParamNode.get(m, k, type);
3125 }
3126 }
3127
3128 /*** A FieldNode represents the result of a 'load' instruction.
3129 * There are outside edge links from the nodes that can be the base object
3130 * of the load to this node.
3131 * Two nodes are equal if the fields match and they are from the same instruction.
3132 */
3133 public static final class FieldNode extends OutsideNode {
3134 final jq_Field f; final Set locs;
3135 Set field_predecessors;
3136
3137 private static FieldNode findPredecessor(FieldNode base, ProgramLocation obj) {
3138 if (TRACE_INTRA) out.println("Checking "+base+" for predecessor "+obj.getID());
3139 if (base.locs.contains(obj)) {
3140 if (TRACE_INTRA) out.println("Success!");
3141 return base;
3142 }
3143 if (base.visited) {
3144 if (TRACE_INTRA) out.println(base+" already visited");
3145 return null;
3146 }
3147 base.visited = true;
3148 if (base.field_predecessors != null) {
3149 for (Iterator i=base.field_predecessors.iterator(); i.hasNext(); ) {
3150 Object o = i.next();
3151 if (o instanceof FieldNode) {
3152 FieldNode fn = (FieldNode)o;
3153 FieldNode fn2 = findPredecessor(fn, obj);
3154 if (fn2 != null) {
3155 base.visited = false;
3156 return fn2;
3157 }
3158 }
3159 }
3160 }
3161 base.visited = false;
3162 return null;
3163 }
3164
3165 public static FieldNode get(Node base, jq_Field f, ProgramLocation obj) {
3166 if (TRACE_INTRA) out.println("Getting field node for "+base+(f==null?"[]":("."+f.getName()))+" loc "+(obj==null?-1:obj.getID()));
3167 Set s = null;
3168 if (base.accessPathEdges != null) {
3169 Object o = base.accessPathEdges.get(f);
3170 if (o instanceof FieldNode) {
3171 if (TRACE_INTRA) out.println("Field node for "+base+" already exists, reusing: "+o);
3172 return (FieldNode)o;
3173 } else if (o != null) {
3174 s = (Set)o;
3175 if (!s.isEmpty()) {
3176 if (TRACE_INTRA) out.println("Field node for "+base+" already exists, reusing: "+o);
3177 return (FieldNode)s.iterator().next();
3178 }
3179 }
3180 } else {
3181 base.accessPathEdges = new LinkedHashMap();
3182 }
3183 FieldNode fn;
3184 if (base instanceof FieldNode) fn = findPredecessor((FieldNode)base, obj);
3185 else fn = null;
3186 if (fn == null) {
3187 fn = FieldNode.get(f, obj);
3188 if (TRACE_INTRA) out.println("Created field node: "+fn.toString_long());
3189 } else {
3190 if (TRACE_INTRA) out.println("Using existing field node: "+fn.toString_long());
3191 }
3192 if (fn.field_predecessors == null) fn.field_predecessors = NodeSet.FACTORY.makeSet();
3193 fn.field_predecessors.add(base);
3194 if (s != null) {
3195 if (VERIFY_ASSERTIONS) Assert._assert(base.accessPathEdges.get(f) == s);
3196 s.add(fn);
3197 } else {
3198 base.accessPathEdges.put(f, fn);
3199 }
3200 if (TRACE_INTRA) out.println("Final field node: "+fn.toString_long());
3201 return fn;
3202 }
3203
3204 static final HashMap FACTORY = new HashMap();
3205 private static FieldNode get(jq_Field f, ProgramLocation q) {
3206 Set locs = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
3207 locs.add(q);
3208 return get(f, locs);
3209 }
3210 private static FieldNode get(jq_Field f, Set s) {
3211 Pair key = new Pair(f, s);
3212 FieldNode n = (FieldNode)FACTORY.get(key);
3213 if (n == null) {
3214 FACTORY.put(key, n = new FieldNode(f, s));
3215 }
3216 return n;
3217 }
3218 private FieldNode(jq_Field f, Set s) {
3219 this.f = f;
3220 this.locs = s;
3221 }
3222
3223 private FieldNode(FieldNode that) {
3224 this.f = that.f;
3225 this.locs = SortedArraySet.FACTORY.makeSet(that.locs);
3226 this.field_predecessors = that.field_predecessors;
3227 }
3228
3229 /*** Returns a new FieldNode that is the unification of the given set of FieldNodes.
3230 * In essence, all of the given nodes are replaced by a new, returned node.
3231 * The given field nodes must be on the given field.
3232 */
3233 public static FieldNode unify(jq_Field f, Set s) {
3234 if (TRACE_INTRA) out.println("Unifying the set of field nodes: "+s);
3235 Set dislocs = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
3236
3237 for (Iterator i=s.iterator(); i.hasNext(); ) {
3238 FieldNode dat = (FieldNode)i.next();
3239 Assert._assert(f == dat.f);
3240 dislocs.addAll(dat.locs);
3241 }
3242 FieldNode dis = FieldNode.get(f, dislocs);
3243
3244 for (Iterator i=s.iterator(); i.hasNext(); ) {
3245 FieldNode dat = (FieldNode)i.next();
3246 Set s2 = Collections.singleton(dis);
3247 dat.replaceBy(s2, true);
3248 }
3249 if (TRACE_INTRA) out.println("Resulting field node: "+dis.toString_long());
3250 return dis;
3251 }
3252
3253 public void replaceBy(Set set, boolean removeSelf) {
3254 if (TRACE_INTRA) out.println("Replacing "+this+" with "+set+(removeSelf?", and removing self":""));
3255 if (set.contains(this)) {
3256 if (TRACE_INTRA) out.println("Replacing a node with itself, turning off remove self.");
3257 set.remove(this);
3258 if (set.isEmpty()) {
3259 if (TRACE_INTRA) out.println("Replacing a node with only itself! Nothing to do.");
3260 return;
3261 }
3262 removeSelf = false;
3263 }
3264 if (VERIFY_ASSERTIONS) Assert._assert(!set.contains(this));
3265 if (this.field_predecessors != null) {
3266 for (Iterator i=this.field_predecessors.iterator(); i.hasNext(); ) {
3267 Node that = (Node)i.next();
3268 Assert._assert(that != null);
3269 if (removeSelf) {
3270 i.remove();
3271 that._removeAccessPathEdge(f, this);
3272 }
3273 if (that == this) {
3274
3275 if (TRACE_INTRA) out.println("Found self-cycle on outside edge of "+that);
3276 for (Iterator j=set.iterator(); j.hasNext(); ) {
3277 FieldNode k = (FieldNode)j.next();
3278 k.addAccessPathEdge(f, k);
3279 }
3280 } else {
3281 for (Iterator j=set.iterator(); j.hasNext(); ) {
3282 that.addAccessPathEdge(f, (FieldNode)j.next());
3283 }
3284 }
3285 }
3286 }
3287 super.replaceBy(set, removeSelf);
3288 }
3289
3290 static void addGlobalAccessPathEdges(FieldNode n) {
3291 if (n.field_predecessors == null) return;
3292 jq_Field f = n.f;
3293 for (Iterator i=n.field_predecessors.iterator(); i.hasNext(); ) {
3294 Object o = i.next();
3295 if (o == GlobalNode.GLOBAL) {
3296 GlobalNode.GLOBAL.addAccessPathEdge(f, n);
3297 } else if (o instanceof UnknownTypeNode) {
3298 ((UnknownTypeNode)o).addAccessPathEdge(f, n);
3299 }
3300 }
3301 }
3302
3303 public void update(HashMap um) {
3304 super.update(um);
3305 Set m = this.field_predecessors;
3306 if (m != null) {
3307 this.field_predecessors = NodeSet.FACTORY.makeSet();
3308 for (Iterator j=m.iterator(); j.hasNext(); ) {
3309 Object p = j.next();
3310 Assert._assert(p != null);
3311 Object o = um.get(p);
3312 if (p instanceof UnknownTypeNode) o = p;
3313 if (p == GlobalNode.GLOBAL) o = p;
3314 if (VERIFY_ASSERTIONS) Assert._assert(o != null, ((Node)p).toString_long()+" (field predecessor of "+this.toString_long()+")");
3315 this.field_predecessors.add(o);
3316 }
3317 addGlobalAccessPathEdges(this);
3318 }
3319 }
3320
3321 /*** Return the set of outside edge predecessors of this node. */
3322 public Set getAccessPathPredecessors() {
3323 if (field_predecessors == null) return Collections.EMPTY_SET;
3324 return field_predecessors;
3325 }
3326
3327 public jq_Field getField() { return f; }
3328
3329 public jq_Method getDefiningMethod() {
3330 Iterator i = locs.iterator();
3331 if (!i.hasNext()) return null;
3332 return ((ProgramLocation) i.next()).getMethod();
3333 }
3334
3335 public Set getLocations() { return locs; }
3336
3337 public String fieldName() {
3338 if (f != null) return f.getName().toString();
3339 return getDeclaredType()+"[]";
3340 }
3341
3342 public final Node copy() {
3343 return new FieldNode(this);
3344 }
3345
3346 public jq_Reference getDeclaredType() {
3347 if (f != null) {
3348 return (jq_Reference)f.getType();
3349 }
3350 if (locs.isEmpty()) return PrimordialClassLoader.getJavaLangObject();
3351 return (jq_Reference) ((ProgramLocation) locs.iterator().next()).getResultType();
3352 }
3353
3354 public String toString_long() {
3355 StringBuffer sb = new StringBuffer();
3356
3357
3358 sb.append(this.toString_short());
3359 sb.append(super.toString_long());
3360 if (field_predecessors != null) {
3361 sb.append(" field pred:");
3362 sb.append(field_predecessors);
3363 }
3364 return sb.toString();
3365 }
3366 public String toString_short() {
3367 StringBuffer sb = new StringBuffer();
3368 Iterator i=locs.iterator();
3369 while (i.hasNext()) {
3370 ProgramLocation pl = (ProgramLocation) i.next();
3371 sb.append(pl.getEmacsName());
3372 sb.append(' ');
3373 }
3374 sb.append("FieldLoad ");
3375 sb.append(fieldName());
3376 i=locs.iterator();
3377 if (i.hasNext()) {
3378 int id = ((ProgramLocation)i.next()).getID();
3379 if (!i.hasNext()) {
3380 sb.append(" loc ");
3381 sb.append(id);
3382 } else {
3383 sb.append(" locs {");
3384 sb.append(id);
3385 while (i.hasNext()) {
3386 sb.append(',');
3387 sb.append(((ProgramLocation)i.next()).getID());
3388 }
3389 sb.append('}');
3390 }
3391 }
3392 return sb.toString();
3393 }
3394
3395
3396
3397
3398 public void write(Textualizer t) throws IOException {
3399 t.writeObject(f);
3400 t.writeString(" "+locs.size());
3401 for (Iterator i = locs.iterator(); i.hasNext(); ) {
3402 t.writeString(" ");
3403 ProgramLocation pl = (ProgramLocation) i.next();
3404 pl.write(t);
3405 }
3406 for (Iterator i = this.field_predecessors.iterator(); i.hasNext(); ) {
3407 Node n = (Node) i.next();
3408 if (!t.contains(n)) continue;
3409 t.writeEdge("fpred", n);
3410 }
3411 super.write(t);
3412 }
3413 public static FieldNode read(StringTokenizer st) {
3414 jq_Field f = (jq_Field) jq_Member.read(st);
3415 int k = Integer.parseInt(st.nextToken());
3416 Set locs = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
3417 for (int i = 0; i < k; ++i) {
3418 ProgramLocation pl = ProgramLocation.read(st);
3419 locs.add(pl);
3420 }
3421
3422 return FieldNode.get(f, locs);
3423 }
3424 }
3425
3426 /*** Records the state of the intramethod analysis at some point in the method. */
3427 public static final class State implements Cloneable {
3428 final Object[] registers;
3429 /*** Return a new state with the given number of registers. */
3430 public State(int nRegisters) {
3431 this.registers = new Object[nRegisters];
3432 }
3433 /*** Return a shallow copy of this state.
3434 * Sets of nodes are copied, but the individual nodes are not. */
3435 public State copy() {
3436 State that = new State(this.registers.length);
3437 for (int i=0; i<this.registers.length; ++i) {
3438 Object a = this.registers[i];
3439 if (a == null) continue;
3440 if (a instanceof Node)
3441 that.registers[i] = a;
3442 else
3443 that.registers[i] = NodeSet.FACTORY.makeSet((Set)a);
3444 }
3445 return that;
3446 }
3447 /*** Merge two states. Mutates this state, the other is unchanged. */
3448 public boolean merge(State that) {
3449 boolean change = false;
3450 for (int i=0; i<this.registers.length; ++i) {
3451 if (merge(i, that.registers[i])) change = true;
3452 }
3453 return change;
3454 }
3455 /*** Merge the given node or set of nodes into the given register. */
3456 public boolean merge(int i, Object b) {
3457 if (b == null) return false;
3458 Object a = this.registers[i];
3459 if (b.equals(a)) return false;
3460 Set q;
3461 if (!(a instanceof Set)) {
3462 this.registers[i] = q = NodeSet.FACTORY.makeSet();
3463 if (a != null) q.add(a);
3464 } else {
3465 q = (Set)a;
3466 }
3467 if (b instanceof Set) {
3468 if (q.addAll((Set)b)) {
3469 if (TRACE_INTRA) out.println("change in register "+i+" from adding set");
3470 return true;
3471 }
3472 } else {
3473 if (q.add(b)) {
3474 if (TRACE_INTRA) out.println("change in register "+i+" from adding "+b);
3475 return true;
3476 }
3477 }
3478 return false;
3479 }
3480 /*** Dump a textual representation of the state to the given print stream. */
3481 public void dump(java.io.PrintStream out) {
3482 for (int i=0; i<registers.length; ++i) {
3483 if (registers[i] == null) continue;
3484 out.print(i+": "+registers[i]+" ");
3485 }
3486 out.println();
3487 }
3488 }
3489
3490 public static final class NodeSet implements Set, Cloneable {
3491
3492 private Node elementData[];
3493 private int size;
3494
3495 public NodeSet(int initialCapacity) {
3496 super();
3497 if (initialCapacity < 0)
3498 throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
3499 this.elementData = new Node[initialCapacity];
3500 this.size = 0;
3501 }
3502
3503 public NodeSet() {
3504 this(10);
3505 }
3506
3507 public NodeSet(Collection c) {
3508 this((int) Math.min((c.size()*110L)/100, Integer.MAX_VALUE));
3509 this.addAll(c);
3510 }
3511
3512 public int size() {
3513
3514 return this.size;
3515 }
3516
3517 private static final int compare(Node n1, Node n2) {
3518 int n1i = n1.id, n2i = n2.id;
3519 if (n1i > n2i) return 1;
3520 if (n1i < n2i) return -1;
3521 return 0;
3522 }
3523
3524 private int whereDoesItGo(Node o) {
3525 int lo = 0;
3526 int hi = this.size-1;
3527 if (hi < 0)
3528 return 0;
3529 int mid = hi >> 1;
3530 for (;;) {
3531 Node o2 = this.elementData[mid];
3532 int r = compare(o, o2);
3533 if (r < 0) {
3534 hi = mid - 1;
3535 if (lo > hi) return mid;
3536 } else if (r > 0) {
3537 lo = mid + 1;
3538 if (lo > hi) return lo;
3539 } else {
3540 return mid;
3541 }
3542 mid = ((hi - lo) >> 1) + lo;
3543 }
3544 }
3545
3546 public boolean add(Object arg0) { return this.add((Node)arg0); }
3547 public boolean add(Node arg0) {
3548 int i = whereDoesItGo(arg0);
3549 int s = this.size;
3550 if (i != s && elementData[i].equals(arg0)) {
3551 return false;
3552 }
3553 ensureCapacity(s+1);
3554 System.arraycopy(this.elementData, i, this.elementData, i + 1, s - i);
3555 elementData[i] = arg0;
3556 this.size++;
3557 return true;
3558 }
3559
3560 public void ensureCapacity(int minCapacity) {
3561 int oldCapacity = elementData.length;
3562 if (minCapacity > oldCapacity) {
3563 Object oldData[] = elementData;
3564 int newCapacity = ((oldCapacity * 3) >> 1) + 1;
3565 if (newCapacity < minCapacity)
3566 newCapacity = minCapacity;
3567 this.elementData = new Node[newCapacity];
3568 System.arraycopy(oldData, 0, this.elementData, 0, this.size);
3569 }
3570 }
3571
3572
3573 public static final boolean REDUCE_ALLOCATIONS = false;
3574
3575 public boolean addAll(java.util.Collection that) {
3576 if (that instanceof NodeSet) {
3577 boolean result = addAll((NodeSet) that);
3578 return result;
3579 } else {
3580 boolean change = false;
3581 for (Iterator i=that.iterator(); i.hasNext(); )
3582 if (this.add((Node)i.next())) change = true;
3583 return change;
3584 }
3585 }
3586
3587 public boolean addAll(NodeSet that) {
3588 if (this == that) {
3589 return false;
3590 }
3591 int s2 = that.size();
3592 if (s2 == 0) {
3593 return false;
3594 }
3595 int s1 = this.size;
3596 Node[] e1 = this.elementData, e2 = that.elementData;
3597 int newSize = Math.max(e1.length, s1 + s2);
3598 int i1, new_i1=0, i2=0;
3599 Node[] new_e1;
3600 if (REDUCE_ALLOCATIONS && newSize <= e1.length) {
3601 System.arraycopy(e1, 0, e1, s2, s1);
3602 new_e1 = e1;
3603 i1 = s2; s1 += s2;
3604 } else {
3605 new_e1 = new Node[newSize];
3606 this.elementData = new_e1;
3607 i1 = 0;
3608 }
3609 boolean change = false;
3610 for (;;) {
3611 if (i2 == s2) {
3612 int size2 = s1-i1;
3613 if (size2 > 0)
3614 System.arraycopy(e1, i1, new_e1, new_i1, size2);
3615 this.size = new_i1 + size2;
3616 return change;
3617 }
3618 Node o2 = e2[i2++];
3619 for (;;) {
3620 if (i1 == s1) {
3621 new_e1[new_i1++] = o2;
3622 int size2 = s2-i2;
3623 System.arraycopy(e2, i2, new_e1, new_i1, size2);
3624 this.size = new_i1 + size2;
3625 return true;
3626 }
3627 Node o1 = e1[i1];
3628 int r = compare(o1, o2);
3629 if (r <= 0) {
3630 new_e1[new_i1++] = o1;
3631 if (REDUCE_ALLOCATIONS && new_e1 == e1) e1[i1] = null;
3632 i1++;
3633 if (r == 0) break;
3634 } else {
3635 new_e1[new_i1++] = o2;
3636 change = true;
3637 break;
3638 }
3639 }
3640 }
3641 }
3642 public int indexOf(Node arg0) {
3643 int i = whereDoesItGo(arg0);
3644 if (i == size || arg0.id != elementData[i].id) return -1;
3645 return i;
3646 }
3647 public boolean contains(Object arg0) { return contains((Node)arg0); }
3648 public boolean contains(Node arg0) {
3649 boolean result = this.indexOf(arg0) != -1;
3650 return result;
3651 }
3652 public boolean remove(Object arg0) { return remove((Node)arg0); }
3653 public boolean remove(Node arg0) {
3654 int i = whereDoesItGo(arg0);
3655 if (i == size) {
3656 return false;
3657 }
3658 Object oldValue = elementData[i];
3659 if (arg0 != oldValue) {
3660 return false;
3661 }
3662 int numMoved = this.size - i - 1;
3663 if (numMoved > 0)
3664 System.arraycopy(elementData, i+1, elementData, i, numMoved);
3665 elementData[--this.size] = null;
3666 return true;
3667 }
3668 public Object clone() {
3669 try {
3670 NodeSet s = (NodeSet) super.clone();
3671 int initialCapacity = this.elementData.length;
3672 s.elementData = new Node[initialCapacity];
3673 s.size = this.size;
3674 System.arraycopy(this.elementData, 0, s.elementData, 0, this.size);
3675 return s;
3676 } catch (CloneNotSupportedException _) { return null; }
3677 }
3678
3679 public boolean equals(Object o) {
3680 if (o instanceof NodeSet) {
3681 boolean result = equals((NodeSet)o);
3682 return result;
3683 } else if (o instanceof Collection) {
3684 Collection that = (Collection) o;
3685 if (this.size() != that.size()) return false;
3686 for (Iterator i=that.iterator(); i.hasNext(); ) {
3687 if (!this.contains(i.next())) return false;
3688 }
3689 return true;
3690 } else {
3691 return false;
3692 }
3693 }
3694 public boolean equals(NodeSet that) {
3695 if (this.size != that.size) {
3696 return false;
3697 }
3698 Node[] e1 = this.elementData; Node[] e2 = that.elementData;
3699 for (int i=0; i<this.size; ++i) {
3700 if (e1[i] != e2[i]) {
3701 return false;
3702 }
3703 }
3704 return true;
3705 }
3706
3707 public int hashCode() {
3708 int hash = 0;
3709 for (int i=0; i<this.size; ++i) {
3710 if (USE_IDENTITY_HASHCODE)
3711 hash += System.identityHashCode(this.elementData[i]);
3712 else
3713 hash += this.elementData[i].hashCode();
3714 }
3715 return hash;
3716 }
3717
3718 public String toString() {
3719 StringBuffer sb = new StringBuffer();
3720 if (false) {
3721 sb.append(Integer.toHexString(System.identityHashCode(this)));
3722 sb.append(':');
3723 }
3724 sb.append('{');
3725 for (int i=0; i<size; ++i) {
3726 sb.append(elementData[i]);
3727 if (i+1 < size) sb.append(',');
3728 }
3729 sb.append('}');
3730 return sb.toString();
3731 }
3732
3733 public void clear() { this.size = 0; }
3734 public boolean containsAll(Collection arg0) {
3735 if (arg0 instanceof NodeSet) return containsAll((NodeSet)arg0);
3736 else {
3737 for (Iterator i=arg0.iterator(); i.hasNext(); )
3738 if (!this.contains((Node)i.next())) return false;
3739 return true;
3740 }
3741 }
3742 public boolean containsAll(NodeSet that) {
3743 if (this == that) {
3744 return true;
3745 }
3746 int s1 = this.size;
3747 int s2 = that.size;
3748 if (s2 > s1) {
3749 return false;
3750 }
3751 Node[] e1 = this.elementData, e2 = that.elementData;
3752 for (int i1 = 0, i2 = 0; i2 < s2; ++i2) {
3753 Node o2 = e2[i2];
3754 for (;;) {
3755 Node o1 = e1[i1++];
3756 if (o1 == o2) break;
3757 if (o1.id > o2.id) {
3758 return false;
3759 }
3760 }
3761 }
3762 return true;
3763 }
3764 public boolean isEmpty() { return this.size == 0; }
3765 public Iterator iterator() {
3766 final Node[] e = this.elementData;
3767 final int s = this.size;
3768 return new Iterator() {
3769 int n = s;
3770 int i = 0;
3771 public Object next() {
3772 return e[i++];
3773 }
3774 public boolean hasNext() {
3775 return i < n;
3776 }
3777 public void remove() {
3778 int numMoved = s - i;
3779 if (numMoved > 0)
3780 System.arraycopy(e, i, e, i-1, numMoved);
3781 elementData[--size] = null;
3782 --i; --n;
3783 }
3784 };
3785 }
3786 public boolean removeAll(Collection arg0) {
3787 if (arg0 instanceof NodeSet)
3788 return removeAll((NodeSet)arg0);
3789 else {
3790 boolean change = false;
3791 for (Iterator i=arg0.iterator(); i.hasNext(); )
3792 if (this.remove((Node)i.next())) change = true;
3793 return change;
3794 }
3795 }
3796 public boolean removeAll(NodeSet that) {
3797 if (this.isEmpty()) return false;
3798 if (this == that) {
3799 this.clear(); return true;
3800 }
3801 int s1 = this.size;
3802 int s2 = that.size;
3803 Node[] e1 = this.elementData, e2 = that.elementData;
3804 int i1 = 0, i2 = 0, i3 = 0;
3805 Node o1 = e1[i1++];
3806 Node o2 = e2[i2++];
3807 outer:
3808 for (;;) {
3809 while (o1.id < o2.id) {
3810 e1[i3++] = o1;
3811 if (i1 == s1) break outer;
3812 o1 = e1[i1++];
3813 }
3814 while (o1.id > o2.id) {
3815 if (i2 == s2) break outer;
3816 o2 = e2[i2++];
3817 }
3818 while (o1 == o2) {
3819 if (i1 == s1) break outer;
3820 o1 = e1[i1++];
3821 if (i2 == s2) {
3822 System.arraycopy(e1, i1, e1, i3, s1-i1);
3823 i3 += s1-i1;
3824 break outer;
3825 }
3826 o2 = e2[i2++];
3827 }
3828 }
3829 this.size = i3;
3830 return true;
3831 }
3832
3833 public boolean retainAll(Collection arg0) {
3834 if (arg0 instanceof NodeSet)
3835 return retainAll((NodeSet)arg0);
3836 else {
3837 boolean change = false;
3838 for (Iterator i=this.iterator(); i.hasNext(); )
3839 if (!arg0.contains(i.next())) {
3840 i.remove();
3841 change = true;
3842 }
3843 return change;
3844 }
3845 }
3846 public boolean retainAll(NodeSet that) {
3847 if (this == that) return false;
3848 int s1 = this.size;
3849 int s2 = that.size;
3850 Node[] e1 = this.elementData, e2 = that.elementData;
3851 int i1 = 0, i2 = 0, i3 = 0;
3852 Node o1 = e1[i1++];
3853 Node o2 = e2[i2++];
3854 outer:
3855 for (;;) {
3856 while (o1.id < o2.id) {
3857 if (i1 == s1) break outer;
3858 o1 = e1[i1++];
3859 }
3860 while (o1.id > o2.id) {
3861 if (i2 == s2) break outer;
3862 o2 = e2[i2++];
3863 }
3864 while (o1 == o2) {
3865 e1[i3++] = o1;
3866 if (i1 == s1) break outer;
3867 o1 = e1[i1++];
3868 if (i2 == s2) break outer;
3869 o2 = e2[i2++];
3870 }
3871 }
3872 this.size = i3;
3873 return true;
3874 }
3875 public Object[] toArray() {
3876 Node[] n = new Node[this.size];
3877 System.arraycopy(this.elementData, 0, n, 0, this.size);
3878 return n;
3879 }
3880 public Object[] toArray(Object[] arg0) {
3881 return this.toArray();
3882 }
3883
3884 public static final boolean TEST = false;
3885 public static final boolean PROFILE = false;
3886
3887 public static final SetFactory FACTORY = new SetFactory() {
3888 /***
3889 * Version ID for serialization.
3890 */
3891 private static final long serialVersionUID = 3257845485078459956L;
3892
3893 public final Set makeSet(Collection c) {
3894 if (TEST)
3895 return new CollectionTestWrapper(new LinkedHashSet(c), new NodeSet(c));
3896 if (PROFILE)
3897 return new InstrumentedSetWrapper(new NodeSet(c));
3898 return new NodeSet(c);
3899 }
3900 };
3901
3902 }
3903
3904
3905 /*** Encodes an access path.
3906 * An access path is an NFA, where transitions are field names.
3907 * Each node in the NFA is represented by an AccessPath object.
3908 * We try to share AccessPath objects as much as possible.
3909 */
3910 public static class AccessPath {
3911 /*** All incoming transitions have this field. */
3912 jq_Field _field;
3913 /*** The incoming transitions are associated with this AccessPath object. */
3914 Node _n;
3915 /*** Whether this is a valid end state. */
3916 boolean _last;
3917
3918 /*** The set of (wrapped) successor AccessPath objects. */
3919 Set succ;
3920
3921 /*** Adds the set of (wrapped) AccessPath objects that are reachable from this
3922 * AccessPath object to the given set. */
3923 private void reachable(Set s) {
3924 for (Iterator i = this.succ.iterator(); i.hasNext(); ) {
3925 IdentityHashCodeWrapper ap = (IdentityHashCodeWrapper)i.next();
3926 if (!s.contains(ap)) {
3927 s.add(ap);
3928 ((AccessPath)ap.getObject()).reachable(s);
3929 }
3930 }
3931 }
3932 /*** Return an iteration of the AccessPath objects that are reachable from
3933 * this AccessPath. */
3934 public Iterator reachable() {
3935 Set s = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
3936 s.add(IdentityHashCodeWrapper.create(this));
3937 this.reachable(s);
3938 return new FilterIterator(s.iterator(), filter);
3939 }
3940
3941 /*** Add the given AccessPath object as a successor to this AccessPath object. */
3942 private void addSuccessor(AccessPath ap) {
3943 succ.add(IdentityHashCodeWrapper.create(ap));
3944 }
3945
3946 /*** Return an access path that is equivalent to the given access path prepended
3947 * with a transition on the given field and node. The given access path can
3948 * be null (empty). */
3949 public static AccessPath create(jq_Field f, Node n, AccessPath p) {
3950 if (p == null) return new AccessPath(f, n, true);
3951 AccessPath that = p.findNode(n);
3952 if (that == null) {
3953 that = new AccessPath(f, n);
3954 } else {
3955 p = p.copy();
3956 that = p.findNode(n);
3957 }
3958 that.addSuccessor(p);
3959 return that;
3960 }
3961
3962 /*** Return an access path that is equivalent to the given access path appended
3963 * with a transition on the given field and node. The given access path can
3964 * be null (empty). */
3965 public static AccessPath create(AccessPath p, jq_Field f, Node n) {
3966 if (p == null) return new AccessPath(f, n, true);
3967 p = p.copy();
3968 AccessPath that = p.findNode(n);
3969 if (that == null) {
3970 that = new AccessPath(f, n);
3971 }
3972 that.setLast();
3973 for (Iterator i = p.findLast(); i.hasNext(); ) {
3974 AccessPath last = (AccessPath)i.next();
3975 last.unsetLast();
3976 last.addSuccessor(that);
3977 }
3978 return p;
3979 }
3980
3981 /*** Helper function for findLast(), below. */
3982 private void findLast(HashSet s, Set last) {
3983 for (Iterator i = this.succ.iterator(); i.hasNext(); ) {
3984 IdentityHashCodeWrapper ap = (IdentityHashCodeWrapper)i.next();
3985 if (!s.contains(ap)) {
3986 s.add(ap);
3987 AccessPath that = (AccessPath)ap.getObject();
3988 if (that._last) last.add(ap);
3989 that.findLast(s, last);
3990 }
3991 }
3992 }
3993
3994 /*** Return an iteration of the AccessPath nodes that correspond to end states. */
3995 public Iterator findLast() {
3996 HashSet visited = new HashSet();
3997 Set last = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
3998 IdentityHashCodeWrapper ap = IdentityHashCodeWrapper.create(this);
3999 visited.add(ap);
4000 if (this._last) last.add(ap);
4001 this.findLast(visited, last);
4002 return new FilterIterator(last.iterator(), filter);
4003 }
4004
4005 /*** Helper function for findNode(Node n), below. */
4006 private AccessPath findNode(Node n, HashSet s) {
4007 for (Iterator i = this.succ.iterator(); i.hasNext(); ) {
4008 IdentityHashCodeWrapper ap = (IdentityHashCodeWrapper)i.next();
4009 if (!s.contains(ap)) {
4010 AccessPath p = (AccessPath)ap.getObject();
4011 if (n == p._n) return p;
4012 s.add(ap);
4013 AccessPath q = p.findNode(n, s);
4014 if (q != null) return q;
4015 }
4016 }
4017 return null;
4018 }
4019
4020 /*** Find the AccessPath object that corresponds to the given node. */
4021 public AccessPath findNode(Node n) {
4022 if (n == this._n) return this;
4023 HashSet visited = new HashSet();
4024 IdentityHashCodeWrapper ap = IdentityHashCodeWrapper.create(this);
4025 visited.add(ap);
4026 return findNode(n, visited);
4027 }
4028
4029 /*** Set this transition as a valid end transition. */
4030 private void setLast() { this._last = true; }
4031 /*** Unset this transition as a valid end transition. */
4032 private void unsetLast() { this._last = false; }
4033
4034 /*** Helper function for copy(), below. */
4035 private void copy(HashMap m, AccessPath that) {
4036 for (Iterator i = this.succ.iterator(); i.hasNext(); ) {
4037 IdentityHashCodeWrapper ap = (IdentityHashCodeWrapper)i.next();
4038 AccessPath p = (AccessPath)m.get(ap);
4039 if (p == null) {
4040 AccessPath that2 = (AccessPath)ap.getObject();
4041 p = new AccessPath(that2._field, that2._n, that2._last);
4042 m.put(ap, p);
4043 that2.copy(m, p);
4044 }
4045 that.addSuccessor(p);
4046 }
4047 }
4048
4049 /*** Return a copy of this (complete) access path. */
4050 public AccessPath copy() {
4051 HashMap m = new HashMap();
4052 IdentityHashCodeWrapper ap = IdentityHashCodeWrapper.create(this);
4053 AccessPath p = new AccessPath(this._field, this._n, this._last);
4054 m.put(ap, p);
4055 this.copy(m, p);
4056 return p;
4057 }
4058
4059 /*** Helper function for toString(), below. */
4060 private void toString(StringBuffer sb, HashSet set) {
4061 if (this._field == null) sb.append("[]");
4062 else sb.append(this._field.getName());
4063 if (this._last) sb.append("<e>");
4064 sb.append("->(");
4065 for (Iterator i = this.succ.iterator(); i.hasNext(); ) {
4066 IdentityHashCodeWrapper ap = (IdentityHashCodeWrapper)i.next();
4067 if (set.contains(ap)) {
4068 sb.append("<backedge>");
4069 } else {
4070 set.add(ap);
4071 ((AccessPath)ap.getObject()).toString(sb, set);
4072 }
4073 }
4074 sb.append(')');
4075 }
4076 /*** Returns a string representation of this (complete) access path. */
4077 public String toString() {
4078 StringBuffer sb = new StringBuffer();
4079 HashSet visited = new HashSet();
4080 IdentityHashCodeWrapper ap = IdentityHashCodeWrapper.create(this);
4081 visited.add(ap);
4082 toString(sb, visited);
4083 return sb.toString();
4084 }
4085
4086 /*** Private constructor. Use the create() methods above. */
4087 private AccessPath(jq_Field f, Node n, boolean last) {
4088 this._field = f; this._n = n; this._last = last;
4089 this.succ = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
4090 }
4091 /*** Private constructor. Use the create() methods above. */
4092 private AccessPath(jq_Field f, Node n) {
4093 this(f, n, false);
4094 }
4095
4096 /*** Helper function for equals(AccessPath), below. */
4097 private boolean oneEquals(AccessPath that) {
4098
4099 if (this._field != that._field) return false;
4100 if (this._last != that._last) return false;
4101 if (this.succ.size() != that.succ.size()) return false;
4102 return true;
4103 }
4104 /*** Helper function for equals(AccessPath), below. */
4105 private boolean equals(AccessPath that, HashSet s) {
4106
4107
4108 for (Iterator i = this.succ.iterator(), j = that.succ.iterator(); i.hasNext(); ) {
4109 IdentityHashCodeWrapper a = (IdentityHashCodeWrapper)i.next();
4110 IdentityHashCodeWrapper b = (IdentityHashCodeWrapper)j.next();
4111 AccessPath p = (AccessPath)a.getObject();
4112 AccessPath q = (AccessPath)b.getObject();
4113 if (!p.oneEquals(q)) return false;
4114 if (s.contains(a)) continue;
4115 s.add(a);
4116 if (!p.equals(q, s)) return false;
4117 }
4118 return true;
4119 }
4120 /*** Returns true if this access path is equal to the given access path. */
4121 public boolean equals(AccessPath that) {
4122 HashSet s = new HashSet();
4123 if (!oneEquals(that)) return false;
4124 s.add(IdentityHashCodeWrapper.create(this));
4125 return this.equals(that, s);
4126 }
4127 public boolean equals(Object o) {
4128 if (o instanceof AccessPath) return equals((AccessPath)o);
4129 return false;
4130 }
4131 /*** Returns the hashcode for this access path. */
4132 public int hashCode() {
4133 int x = this.local_hashCode();
4134 for (Iterator i = this.succ.iterator(); i.hasNext(); ) {
4135 IdentityHashCodeWrapper a = (IdentityHashCodeWrapper)i.next();
4136 x ^= (((AccessPath)a.getObject()).local_hashCode() << 1);
4137 }
4138 return x;
4139 }
4140 /*** Returns the hashcode for this individual AccessPath object. */
4141 private int local_hashCode() {
4142 return _field != null ? _field.hashCode() : 0x31337;
4143 }
4144 /*** Returns the first field of this access path. */
4145 public jq_Field first() { return _field; }
4146 /*** Returns an iteration of the next AccessPath objects. */
4147 public Iterator next() {
4148 return new FilterIterator(succ.iterator(), filter);
4149 }
4150 /*** A filter to unwrap objects from their IdentityHashCodeWrapper. */
4151 public static final Filter filter = new Filter() {
4152 public Object map(Object o) { return ((IdentityHashCodeWrapper)o).getObject(); }
4153 };
4154 }
4155
4156 /*** vvvvv Actual MethodSummary stuff is below. vvvvv */
4157
4158 /*** The method that this is a summary for. */
4159 final jq_Method method;
4160 /*** The parameter nodes. */
4161 final ParamNode[] params;
4162 /*** All nodes in the summary graph. */
4163 final Map nodes;
4164 /*** The returned nodes. */
4165 final Set returned;
4166 /*** The thrown nodes. */
4167 final Set thrown;
4168 /*** The global node. */
4169
4170 /*** The method calls that this method makes. */
4171 final Set calls;
4172 /*** Map from a method call that this method makes, and its ReturnValueNode. */
4173 final Map callToRVN;
4174 /*** Map from a method call that this method makes, and its ThrownExceptionNode. */
4175 final Map callToTEN;
4176 /*** Map from a (node,castquad) pair to its cast node. */
4177 final Map castMap;
4178 /*** Set of nodes being casts. */
4179 final Set castPredecessors;
4180 /*** Map from a sync op to the nodes it operates on. */
4181 final Map sync_ops;
4182
4183 BuildMethodSummary builder;
4184
4185 public static final boolean USE_PARAMETER_MAP = true;
4186 final Map passedParamToNodes;
4187
4188 public MethodSummary(ParamNode[] param_nodes) {
4189 this.method = null;
4190 this.params = param_nodes;
4191 this.calls = Collections.EMPTY_SET;
4192 this.callToRVN = Collections.EMPTY_MAP;
4193 this.callToTEN = Collections.EMPTY_MAP;
4194 this.nodes = Collections.EMPTY_MAP;
4195 this.returned = Collections.EMPTY_SET;
4196 this.thrown = Collections.EMPTY_SET;
4197 this.castMap = Collections.EMPTY_MAP;
4198 this.castPredecessors = Collections.EMPTY_SET;
4199 this.passedParamToNodes = Collections.EMPTY_MAP;
4200 this.sync_ops = Collections.EMPTY_MAP;
4201 }
4202
4203 public static boolean CACHE_BUILDER = true;
4204
4205 public MethodSummary(BuildMethodSummary builder,
4206 jq_Method method,
4207 ParamNode[] param_nodes,
4208 GlobalNode my_global,
4209 Set methodCalls,
4210 Map callToRVN,
4211 Map callToTEN,
4212 Map castMap,
4213 Set castPredecessors,
4214 Set returned,
4215 Set thrown,
4216 Set passedAsParameters,
4217 Map sync_ops) {
4218 this.method = method;
4219 this.params = param_nodes;
4220 this.calls = methodCalls;
4221 this.callToRVN = callToRVN;
4222 this.callToTEN = callToTEN;
4223 this.passedParamToNodes = USE_PARAMETER_MAP?new HashMap():null;
4224 this.sync_ops = sync_ops;
4225 this.castMap = castMap;
4226 this.castPredecessors = castPredecessors;
4227 this.returned = returned;
4228 this.thrown = thrown;
4229 this.global = my_global;
4230 if (CACHE_BUILDER)
4231 this.builder = builder;
4232 this.nodes = new LinkedHashMap();
4233
4234
4235 this.nodes.put(my_global, my_global);
4236 for (int i=0; i<params.length; ++i) {
4237 if (params[i] == null) continue;
4238 this.nodes.put(params[i], params[i]);
4239 }
4240 for (Iterator i=returned.iterator(); i.hasNext(); ) {
4241 Node n = (Node) i.next();
4242 if (n instanceof UnknownTypeNode) continue;
4243 this.nodes.put(n, n);
4244 }
4245 for (Iterator i=thrown.iterator(); i.hasNext(); ) {
4246 Node n = (Node) i.next();
4247 if (n instanceof UnknownTypeNode) continue;
4248 this.nodes.put(n, n);
4249 }
4250 for (Iterator i=passedAsParameters.iterator(); i.hasNext(); ) {
4251 Node n = (Node) i.next();
4252 if (n instanceof UnknownTypeNode) continue;
4253 this.nodes.put(n, n);
4254 if (USE_PARAMETER_MAP) {
4255 if (n.passedParameters != null) {
4256 for (Iterator j=n.passedParameters.iterator(); j.hasNext(); ) {
4257 PassedParameter pp = (PassedParameter)j.next();
4258 Set s2 = (Set)this.passedParamToNodes.get(pp);
4259 if (s2 == null) this.passedParamToNodes.put(pp, s2 = NodeSet.FACTORY.makeSet());
4260 s2.add(n);
4261 }
4262 }
4263 }
4264 }
4265
4266 HashSet visited = new HashSet();
4267 HashSet path = new HashSet();
4268 addAsUseful(visited, path, my_global);
4269 for (int i=0; i<params.length; ++i) {
4270 if (params[i] == null) continue;
4271 addAsUseful(visited, path, params[i]);
4272 }
4273 for (Iterator i=returned.iterator(); i.hasNext(); ) {
4274 addAsUseful(visited, path, (Node)i.next());
4275 }
4276 for (Iterator i=thrown.iterator(); i.hasNext(); ) {
4277 addAsUseful(visited, path, (Node)i.next());
4278 }
4279 for (Iterator i=passedAsParameters.iterator(); i.hasNext(); ) {
4280 addAsUseful(visited, path, (Node)i.next());
4281 }
4282
4283 castPredecessors = null;
4284
4285 if (UNIFY_ACCESS_PATHS) {
4286 HashSet roots = new HashSet();
4287 for (int i=0; i<params.length; ++i) {
4288 if (params[i] == null) continue;
4289 roots.add(params[i]);
4290 }
4291 roots.addAll(returned); roots.addAll(thrown); roots.addAll(passedAsParameters);
4292 unifyAccessPaths(roots);
4293 }
4294
4295 if (VERIFY_ASSERTIONS) {
4296 this.verify();
4297 for (Iterator i=returned.iterator(); i.hasNext(); ) {
4298 Object o = i.next();
4299 if (o instanceof UnknownTypeNode) continue;
4300 if (!nodes.containsKey(o)) {
4301 Assert.UNREACHABLE("Returned node "+o+" not in set.");
4302 }
4303 }
4304 for (Iterator i=thrown.iterator(); i.hasNext(); ) {
4305 Object o = i.next();
4306 if (o instanceof UnknownTypeNode) continue;
4307 if (!nodes.containsKey(o)) {
4308 Assert.UNREACHABLE("Returned node "+o+" not in set.");
4309 }
4310 }
4311 for (Iterator i=nodes.keySet().iterator(); i.hasNext(); ) {
4312 Node nod = (Node)i.next();
4313 if (nod.predecessors == null) continue;
4314 for (Iterator j=nod.predecessors.values().iterator(); j.hasNext(); ) {
4315 Object o = j.next();
4316 if (o instanceof Node) {
4317 if (o instanceof UnknownTypeNode) continue;
4318 if (!nodes.containsKey(o)) {
4319 Assert.UNREACHABLE("Predecessor node "+o+" of "+nod+" not in set.");
4320 }
4321 } else {
4322 for (Iterator k=((Set)o).iterator(); k.hasNext(); ) {
4323 Node q = (Node)k.next();
4324 if (q instanceof UnknownTypeNode) continue;
4325 if (!nodes.containsKey(q)) {
4326 Assert.UNREACHABLE("Predecessor node "+q+" of "+nod+" not in set.");
4327 }
4328 }
4329 }
4330 }
4331 }
4332
4333 }
4334 }
4335
4336 public static final boolean UNIFY_ACCESS_PATHS = false;
4337
4338 private MethodSummary(BuildMethodSummary builder,
4339 jq_Method method,
4340 ParamNode[] params,
4341 Set methodCalls,
4342 Map callToRVN,
4343 Map callToTEN,
4344 Map castMap,
4345 Set castPredecessors,
4346 Map passedParamToNodes,
4347 Map sync_ops,
4348 Set returned,
4349 Set thrown,
4350 Map nodes) {
4351 this.method = method;
4352 this.params = params;
4353 this.calls = methodCalls;
4354 this.callToRVN = callToRVN;
4355 this.callToTEN = callToTEN;
4356 this.castMap = castMap;
4357 this.castPredecessors = castPredecessors;
4358 this.passedParamToNodes = passedParamToNodes;
4359 this.sync_ops = sync_ops;
4360 this.returned = returned;
4361 this.thrown = thrown;
4362 this.nodes = nodes;
4363 this.builder = builder;
4364 }
4365
4366 /*** Get the global node for this method. */
4367 public GlobalNode getGlobal() { return global; }
4368
4369 /*** Get the ith parameter node. */
4370 public ParamNode getParamNode(int i) { return params[i]; }
4371
4372 /*** Get the number of parameters passed into this method. */
4373 public int getNumOfParams() { return params.length; }
4374
4375 /*** Get the set of method calls made by this method. */
4376 public Set getCalls() { return calls; }
4377
4378 /*** Add all nodes that are passed as the given passed parameter to the given result set. */
4379 public void getNodesThatCall(PassedParameter pp, Set result) {
4380 if (USE_PARAMETER_MAP) {
4381 Set s = (Set)passedParamToNodes.get(pp);
4382 if (s == null) return;
4383 result.addAll(s);
4384 return;
4385 }
4386 for (Iterator i = this.nodeIterator(); i.hasNext(); ) {
4387 Node n = (Node)i.next();
4388 if ((n.passedParameters != null) && n.passedParameters.contains(pp))
4389 result.add(n);
4390 }
4391 }
4392
4393 public Set getNodesThatCall(ProgramLocation mc, int k) {
4394 return getNodesThatCall(new PassedParameter(mc, k));
4395 }
4396
4397 /*** Return the set of nodes that are passed as the given parameter. */
4398 public Set getNodesThatCall(PassedParameter pp) {
4399 if (USE_PARAMETER_MAP) {
4400 Set s = (Set)passedParamToNodes.get(pp);
4401 if (s == null) return Collections.EMPTY_SET;
4402 return s;
4403 }
4404 Set s = NodeSet.FACTORY.makeSet();
4405 getNodesThatCall(pp, s);
4406 return s;
4407 }
4408
4409 /*** Merge the global node for this method summary with the main global node. */
4410 public void mergeGlobal() {
4411 if (global == null) return;
4412
4413 Set set = Collections.singleton(GlobalNode.GLOBAL);
4414 global.replaceBy(set, true);
4415 nodes.remove(global);
4416 unifyAccessPaths(new LinkedHashSet(set));
4417 if (VERIFY_ASSERTIONS) {
4418 verifyNoReferences(global);
4419 }
4420 global = null;
4421 }
4422
4423 /*** Utility function to add to a multi map. */
4424 public static boolean addToMultiMap(HashMap mm, Object from, Object to) {
4425 Set s = (Set) mm.get(from);
4426 if (s == null) {
4427 mm.put(from, s = NodeSet.FACTORY.makeSet());
4428 }
4429 return s.add(to);
4430 }
4431
4432 /*** Utility function to add to a multi map. */
4433 public static boolean addToMultiMap(HashMap mm, Object from, Set to) {
4434 Set s = (Set) mm.get(from);
4435 if (s == null) {
4436 mm.put(from, s = NodeSet.FACTORY.makeSet());
4437 }
4438 return s.addAll(to);
4439 }
4440
4441 /*** Utility function to get the mapping for a callee node. */
4442 static Set get_mapping(HashMap callee_to_caller, Node callee_n) {
4443 Set s = (Set)callee_to_caller.get(callee_n);
4444 if (s != null) return s;
4445 s = NodeSet.FACTORY.makeSet(); s.add(callee_n);
4446 return s;
4447 }
4448
4449 /*** Return a deep copy of this analysis summary.
4450 * Nodes, edges, everything is copied.
4451 */
4452 public MethodSummary copy() {
4453 if (TRACE_INTRA) out.println("Copying summary: "+this);
4454 if (VERIFY_ASSERTIONS) this.verify();
4455 HashMap m = new HashMap();
4456
4457 for (Iterator i=nodeIterator(); i.hasNext(); ) {
4458 Node a = (Node)i.next();
4459 Node b = a.copy();
4460 m.put(a, b);
4461 }
4462 for (Iterator i=nodeIterator(); i.hasNext(); ) {
4463 Node a = (Node)i.next();
4464 Node b = (Node)m.get(a);
4465 b.update(m);
4466 }
4467 Set calls = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
4468 calls.addAll(this.calls);
4469 Set returned = NodeSet.FACTORY.makeSet();
4470 for (Iterator i=this.returned.iterator(); i.hasNext(); ) {
4471 Node a = (Node)i.next();
4472 Node b = (Node)m.get(a);
4473 if (a instanceof UnknownTypeNode) b = a;
4474 Assert._assert(b != null);
4475 returned.add(b);
4476 }
4477 Set thrown = NodeSet.FACTORY.makeSet();
4478 for (Iterator i=this.thrown.iterator(); i.hasNext(); ) {
4479 Node a = (Node)i.next();
4480 Node b = (Node)m.get(a);
4481 if (a instanceof UnknownTypeNode) b = a;
4482 Assert._assert(b != null);
4483 thrown.add(b);
4484 }
4485 ParamNode[] params = new ParamNode[this.params.length];
4486 for (int i=0; i<params.length; ++i) {
4487 if (this.params[i] == null) continue;
4488 params[i] = (ParamNode)m.get(this.params[i]);
4489 }
4490 HashMap callToRVN = new HashMap();
4491 for (Iterator i=this.callToRVN.entrySet().iterator(); i.hasNext(); ) {
4492 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
4493 ProgramLocation mc = (ProgramLocation) e.getKey();
4494 Object o = e.getValue();
4495 if (o != null) {
4496 o = m.get(o);
4497 Assert._assert(o != null, e.toString());
4498 }
4499 callToRVN.put(mc, o);
4500 }
4501 HashMap callToTEN = new HashMap();
4502 for (Iterator i=this.callToTEN.entrySet().iterator(); i.hasNext(); ) {
4503 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
4504 ProgramLocation mc = (ProgramLocation) e.getKey();
4505 Object o = e.getValue();
4506 if (o != null) {
4507 o = m.get(o);
4508 Assert._assert(o != null, e.toString());
4509 }
4510 callToTEN.put(mc, o);
4511 }
4512 LinkedHashMap nodes = new LinkedHashMap();
4513 for (Iterator i=m.entrySet().iterator(); i.hasNext(); ) {
4514 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
4515 Assert._assert(e.getValue() != GlobalNode.GLOBAL);
4516 Assert._assert(!(e.getValue() instanceof UnknownTypeNode));
4517 nodes.put(e.getValue(), e.getValue());
4518 }
4519 Map passedParamToNodes = null;
4520 if (USE_PARAMETER_MAP) {
4521 passedParamToNodes = new HashMap(this.passedParamToNodes);
4522 Node.updateMap(m, passedParamToNodes.entrySet().iterator(), passedParamToNodes);
4523 }
4524 MethodSummary that = new MethodSummary(builder, method, params, calls, callToRVN, callToTEN, castMap, castPredecessors, passedParamToNodes, sync_ops, returned, thrown, nodes);
4525 if (VERIFY_ASSERTIONS) that.verify();
4526 return that;
4527 }
4528
4529 /*** Unify similar access paths from the given roots.
4530 * The given set is consumed.
4531 */
4532 public void unifyAccessPaths(Set roots) {
4533 LinkedList worklist = new LinkedList();
4534 for (Iterator i = roots.iterator(); i.hasNext(); ) {
4535 worklist.add(i.next());
4536 }
4537 while (!worklist.isEmpty()) {
4538 Node n = (Node) worklist.removeFirst();
4539 if (n instanceof UnknownTypeNode) continue;
4540 unifyAccessPathEdges(n);
4541 for (Iterator i = n.getAccessPathEdges().iterator(); i.hasNext(); ) {
4542 Map.Entry e = (Map.Entry) i.next();
4543 FieldNode n2 = (FieldNode) e.getValue();
4544 Assert._assert(n2 != null);
4545 if (roots.contains(n2)) continue;
4546 worklist.add(n2); roots.add(n2);
4547 }
4548 for (Iterator i=n.getNonEscapingEdges().iterator(); i.hasNext(); ) {
4549 Map.Entry e = (Map.Entry) i.next();
4550 Object o = e.getValue();
4551 if (o instanceof Node) {
4552 Node n2 = (Node)o;
4553 Assert._assert(n2 != null);
4554 if (roots.contains(n2)) continue;
4555 worklist.add(n2); roots.add(n2);
4556 } else {
4557 Set s = NodeSet.FACTORY.makeSet((Set) o);
4558 for (Iterator j = s.iterator(); j.hasNext(); ) {
4559 Object p = j.next();
4560 Assert._assert(p != null);
4561 if (roots.contains(p)) j.remove();
4562 }
4563 if (!s.isEmpty()) {
4564 worklist.addAll(s); roots.addAll(s);
4565 }
4566 }
4567 }
4568 }
4569 }
4570
4571 /*** Unify similar access path edges from the given node.
4572 */
4573 public void unifyAccessPathEdges(Node n) {
4574 if (n instanceof UnknownTypeNode) return;
4575 if (TRACE_INTRA) out.println("Unifying access path edges from: "+n);
4576 if (n.accessPathEdges != null) {
4577 for (Iterator i = n.accessPathEdges.entrySet().iterator(); i.hasNext(); ) {
4578 Map.Entry e = (Map.Entry)i.next();
4579 jq_Field f = (jq_Field)e.getKey();
4580 Object o = e.getValue();
4581 Assert._assert(o != null);
4582 FieldNode n2;
4583 if (o instanceof FieldNode) {
4584 n2 = (FieldNode) o;
4585 } else {
4586 Set s = (Set) NodeSet.FACTORY.makeSet((Set) o);
4587 if (s.size() == 0) {
4588 i.remove();
4589 continue;
4590 }
4591 if (s.size() == 1) {
4592 n2 = (FieldNode) s.iterator().next();
4593 e.setValue(n2);
4594 continue;
4595 }
4596 if (TRACE_INTRA) out.println("Node "+n+" has duplicate access path edges on field "+f+": "+s);
4597 n2 = FieldNode.unify(f, s);
4598 for (Iterator j = s.iterator(); j.hasNext(); ) {
4599 FieldNode n3 = (FieldNode)j.next();
4600 if (returned.contains(n3)) {
4601 returned.remove(n3); returned.add(n2);
4602 }
4603 if (thrown.contains(n3)) {
4604 thrown.remove(n3); thrown.add(n2);
4605 }
4606 nodes.remove(n3);
4607 if (VERIFY_ASSERTIONS)
4608 this.verifyNoReferences(n3);
4609 }
4610 nodes.put(n2, n2);
4611 e.setValue(n2);
4612 }
4613 }
4614 }
4615 }
4616
4617 /*** Instantiate a copy of the callee summary into the caller. */
4618 public static void instantiate(MethodSummary caller, ProgramLocation mc, MethodSummary callee, boolean removeCall) {
4619 callee = callee.copy();
4620 if (TRACE_INST) out.println("Instantiating "+callee+" into "+caller+", mc="+mc+" remove call="+removeCall);
4621 if (VERIFY_ASSERTIONS) {
4622 callee.verify();
4623 caller.verify();
4624 }
4625 Assert._assert(caller.calls.contains(mc));
4626 HashMap callee_to_caller = new HashMap();
4627 if (TRACE_INST) out.println("Adding global node to map: "+GlobalNode.GLOBAL.toString_long());
4628 callee_to_caller.put(GlobalNode.GLOBAL, GlobalNode.GLOBAL);
4629 if (TRACE_INST) out.println("Initializing map with "+callee.params.length+" parameters");
4630
4631 for (int i=0; i<callee.params.length; ++i) {
4632 ParamNode pn = callee.params[i];
4633 if (pn == null) continue;
4634 PassedParameter pp = new PassedParameter(mc, i);
4635 Set s = caller.getNodesThatCall(pp);
4636 if (TRACE_INST) out.println("Adding param node to map: "+pn.toString_long()+" maps to "+s);
4637 callee_to_caller.put(pn, s);
4638 if (removeCall) {
4639 if (TRACE_INST) out.println("Removing "+pn+" from nodes "+s);
4640 for (Iterator jj=s.iterator(); jj.hasNext(); ) {
4641 Node n = (Node)jj.next();
4642 n.passedParameters.remove(pp);
4643 }
4644 if (USE_PARAMETER_MAP) caller.passedParamToNodes.remove(pp);
4645 }
4646 }
4647
4648 if (TRACE_INST) out.println("Adding all callee calls: "+callee.calls);
4649 caller.calls.addAll(callee.calls);
4650 for (Iterator i=callee.callToRVN.entrySet().iterator(); i.hasNext(); ) {
4651 java.util.Map.Entry e = (java.util.Map.Entry) i.next();
4652 ProgramLocation mc2 = (ProgramLocation) e.getKey();
4653 if (VERIFY_ASSERTIONS) {
4654 Assert._assert(caller.calls.contains(mc2));
4655 Assert._assert(!mc.equals(mc2));
4656 }
4657 Object rvn2 = e.getValue();
4658 if (TRACE_INST) out.println("Adding rvn for callee call: "+rvn2);
4659 Object o2 = caller.callToRVN.get(mc2);
4660 Assert._assert(o2 == null);
4661 caller.callToRVN.put(mc2, rvn2);
4662 }
4663 for (Iterator i=callee.callToTEN.entrySet().iterator(); i.hasNext(); ) {
4664 java.util.Map.Entry e = (java.util.Map.Entry) i.next();
4665 ProgramLocation mc2 = (ProgramLocation) e.getKey();
4666 if (VERIFY_ASSERTIONS) {
4667 Assert._assert(caller.calls.contains(mc2));
4668 Assert._assert(!mc.equals(mc2));
4669 }
4670 Object ten2 = e.getValue();
4671 if (TRACE_INST) out.println("Adding ten for callee call: "+ten2);
4672 Object o2 = caller.callToTEN.get(mc2);
4673 Assert._assert(o2 == null);
4674 caller.callToTEN.put(mc2, ten2);
4675 }
4676
4677 if (TRACE_INST) out.println("Replacing formal parameters with actuals");
4678 for (int ii=0; ii<callee.params.length; ++ii) {
4679 ParamNode pn = callee.params[ii];
4680 if (pn == null) continue;
4681 Set s = (Set)callee_to_caller.get(pn);
4682 if (TRACE_INST) out.println("Replacing "+pn+" by "+s);
4683 pn.replaceBy(s, removeCall);
4684 if (callee.returned.contains(pn)) {
4685 if (TRACE_INST) out.println(pn+" is returned, updating callee returned set");
4686 if (removeCall) {
4687 callee.returned.remove(pn);
4688 }
4689 callee.returned.addAll(s);
4690 }
4691 if (callee.thrown.contains(pn)) {
4692 if (TRACE_INST) out.println(pn+" is thrown, updating callee thrown set");
4693 if (removeCall) {
4694 callee.thrown.remove(pn);
4695 }
4696 callee.thrown.addAll(s);
4697 }
4698 if (removeCall) {
4699 callee.nodes.remove(pn);
4700 if (VERIFY_ASSERTIONS) callee.verifyNoReferences(pn);
4701 }
4702 }
4703
4704 ReturnValueNode rvn = caller.getRVN(mc);
4705 if (rvn != null) {
4706 if (TRACE_INST) out.println("Replacing return value "+rvn+" by "+callee.returned);
4707 rvn.replaceBy(callee.returned, removeCall);
4708 if (caller.returned.contains(rvn)) {
4709 if (TRACE_INST) out.println(rvn+" is returned, updating returned set");
4710 if (removeCall) caller.returned.remove(rvn);
4711 caller.returned.addAll(callee.returned);
4712 }
4713 if (caller.thrown.contains(rvn)) {
4714 if (TRACE_INST) out.println(rvn+" is thrown, updating thrown set");
4715 if (removeCall) caller.thrown.remove(rvn);
4716 caller.thrown.addAll(callee.returned);
4717 }
4718 if (removeCall) {
4719 if (TRACE_INST) out.println("Removing old return value node "+rvn+" from nodes list");
4720 caller.nodes.remove(rvn);
4721 }
4722 if (VERIFY_ASSERTIONS && removeCall) caller.verifyNoReferences(rvn);
4723 }
4724
4725 ThrownExceptionNode ten = caller.getTEN(mc);
4726 if (ten != null) {
4727 if (TRACE_INST) out.println("Replacing thrown exception "+ten+" by "+callee.thrown);
4728 ten.replaceBy(callee.thrown, removeCall);
4729 if (caller.returned.contains(ten)) {
4730 if (TRACE_INST) out.println(ten+" is returned, updating caller returned set");
4731 if (removeCall) caller.returned.remove(ten);
4732 caller.returned.addAll(callee.thrown);
4733 }
4734 if (caller.thrown.contains(ten)) {
4735 if (TRACE_INST) out.println(ten+" is thrown, updating caller thrown set");
4736 if (removeCall) caller.thrown.remove(ten);
4737 caller.thrown.addAll(callee.thrown);
4738 }
4739 if (removeCall) {
4740 if (TRACE_INST) out.println("Removing old thrown exception node "+ten+" from nodes list");
4741 caller.nodes.remove(ten);
4742 }
4743 if (VERIFY_ASSERTIONS && removeCall) caller.verifyNoReferences(ten);
4744 }
4745
4746 if (TRACE_INST) out.println("Adding all callee nodes: "+callee.nodes);
4747 caller.nodes.putAll(callee.nodes);
4748
4749 if (TRACE_INST) out.println("Building a root set for access path unification");
4750 Set s = NodeSet.FACTORY.makeSet();
4751 s.addAll(callee.returned);
4752 s.addAll(callee.thrown);
4753 for (int ii=0; ii<callee.params.length; ++ii) {
4754 ParamNode pn = callee.params[ii];
4755 if (pn == null) continue;
4756 Set t = (Set)callee_to_caller.get(pn);
4757 s.addAll(t);
4758 }
4759 if (TRACE_INST) out.println("Root set: "+s);
4760 caller.unifyAccessPaths(s);
4761 if (removeCall) {
4762 if (TRACE_INST) out.println("Removing instantiated call: "+mc);
4763 caller.calls.remove(mc);
4764 caller.callToRVN.remove(mc);
4765 caller.callToTEN.remove(mc);
4766 }
4767
4768 if (VERIFY_ASSERTIONS) {
4769 caller.verify();
4770
4771 }
4772 }
4773
4774 public jq_Method getMethod() { return method; }
4775
4776 public int hashCode() {
4777 if (DETERMINISTIC)
4778 return method.hashCode();
4779 else
4780 return System.identityHashCode(this);
4781 }
4782
4783 /*** Return a string representation of this summary. */
4784 public String toString() {
4785 StringBuffer sb = new StringBuffer();
4786 sb.append("Summary for ");
4787 sb.append(method.toString());
4788 sb.append(':');
4789 sb.append(Strings.lineSep);
4790 for (Iterator i=nodes.keySet().iterator(); i.hasNext(); ) {
4791 Node n = (Node)i.next();
4792 sb.append(n.toString_long());
4793 sb.append(Strings.lineSep);
4794 }
4795 if (returned != null && !returned.isEmpty()) {
4796 sb.append("Returned: ");
4797 sb.append(returned);
4798 sb.append(Strings.lineSep);
4799 }
4800 if (thrown != null && !thrown.isEmpty()) {
4801 sb.append("Thrown: ");
4802 sb.append(thrown);
4803 sb.append(Strings.lineSep);
4804 }
4805 if (calls != null && !calls.isEmpty()) {
4806 sb.append("Calls: ");
4807 sb.append(calls);
4808 sb.append(Strings.lineSep);
4809 }
4810 return sb.toString();
4811 }
4812
4813 /*** Utility function to add the given node to the node set if it is useful,
4814 * and transitively for other nodes. */
4815 private boolean addIfUseful(HashSet visited, HashSet path, Node n) {
4816 if (path.contains(n)) return true;
4817 path.add(n);
4818 if (visited.contains(n)) return nodes.containsKey(n);
4819 visited.add(n);
4820 boolean useful = false;
4821 if (nodes.containsKey(n)) {
4822 if (TRACE_INTER) out.println("Useful: "+n);
4823 useful = true;
4824 }
4825 if (n instanceof UnknownTypeNode) {
4826 path.remove(n);
4827 return true;
4828 }
4829 if (n.addedEdges != null) {
4830 if (TRACE_INTER) out.println("Useful because of added edge: "+n);
4831 useful = true;
4832 for (Iterator i = n.getNonEscapingEdgeTargets().iterator(); i.hasNext(); ) {
4833 addAsUseful(visited, path, (Node) i.next());
4834 }
4835 }
4836 if (n.accessPathEdges != null) {
4837 for (Iterator i = n.accessPathEdges.entrySet().iterator(); i.hasNext(); ) {
4838 java.util.Map.Entry e = (java.util.Map.Entry)i.next();
4839
4840 Object o = e.getValue();
4841 if (o instanceof Node) {
4842 if (addIfUseful(visited, path, (Node)o)) {
4843 if (TRACE_INTER && !useful) out.println("Useful because outside edge: "+n+"->"+o);
4844 useful = true;
4845 } else {
4846 if (n != o) i.remove();
4847 }
4848 } else {
4849 for (Iterator j=((Set)o).iterator(); j.hasNext(); ) {
4850 Node n2 = (Node)j.next();
4851 if (addIfUseful(visited, path, n2)) {
4852 if (TRACE_INTER && !useful) out.println("Useful because outside edge: "+n+"->"+n2);
4853 useful = true;
4854 } else {
4855 if (n != n2) j.remove();
4856 }
4857 }
4858 if (!useful) i.remove();
4859 }
4860 }
4861 }
4862 if (castPredecessors.contains(n)) {
4863 for (Iterator i = castMap.entrySet().iterator(); i.hasNext(); ) {
4864 Map.Entry e = (Map.Entry)i.next();
4865 Node goestocast = (Node)((Pair)e.getKey()).left;
4866 CheckCastNode castsucc = (CheckCastNode)e.getValue();
4867
4868 if (n == goestocast && addIfUseful(visited, path, castsucc))
4869 useful = true;
4870 }
4871 }
4872 if (n instanceof ReturnedNode) {
4873 if (TRACE_INTER && !useful) out.println("Useful because ReturnedNode: "+n);
4874 useful = true;
4875 }
4876 if (n.predecessors != null) {
4877 useful = true;
4878 if (TRACE_INTER && !useful) out.println("Useful because target of added edge: "+n);
4879 for (Iterator i = n.getPredecessorTargets().iterator(); i.hasNext(); ) {
4880 addAsUseful(visited, path, (Node) i.next());
4881 }
4882 }
4883 if (useful) {
4884 this.nodes.put(n, n);
4885 if (n instanceof FieldNode) {
4886 FieldNode fn = (FieldNode)n;
4887 for (Iterator i = fn.getAccessPathPredecessors().iterator(); i.hasNext(); ) {
4888 addAsUseful(visited, path, (Node)i.next());
4889 }
4890 }
4891 if (n instanceof CheckCastNode) {
4892
4893
4894 Quad thiscast = ((QuadProgramLocation)((CheckCastNode)n).getLocation()).getQuad();
4895 for (Iterator i = castPredecessors.iterator(); i.hasNext(); ) {
4896 Node goestocast = (Node)i.next();
4897 CheckCastNode castsucc = (CheckCastNode)castMap.get(new Pair(goestocast, thiscast));
4898 if (castsucc != null)
4899 addAsUseful(visited, path, goestocast);
4900 }
4901 }
4902 }
4903 if (TRACE_INTER && !useful) out.println("Not useful: "+n);
4904 path.remove(n);
4905 return useful;
4906 }
4907
4908 /*** Utility function to add the given node to the node set as useful,
4909 * and transitively for other nodes. */
4910 private void addAsUseful(HashSet visited, HashSet path, Node n) {
4911 if (path.contains(n)) {
4912 return;
4913 }
4914 path.add(n);
4915 if (visited.contains(n)) {
4916 if (VERIFY_ASSERTIONS) Assert._assert(nodes.containsKey(n), n.toString());
4917 return;
4918 }
4919 if (n instanceof UnknownTypeNode) {
4920 path.remove(n);
4921 return;
4922 }
4923 visited.add(n); this.nodes.put(n, n);
4924 if (TRACE_INTER) out.println("Useful: "+n);
4925 for (Iterator i = n.getNonEscapingEdgeTargets().iterator(); i.hasNext(); ) {
4926 addAsUseful(visited, path, (Node) i.next());
4927 }
4928 if (n.accessPathEdges != null) {
4929 for (Iterator i=n.accessPathEdges.entrySet().iterator(); i.hasNext(); ) {
4930 Map.Entry e = (Map.Entry) i.next();
4931 Object o = e.getValue();
4932 if (o instanceof Node) {
4933 if (!addIfUseful(visited, path, (Node)o)) {
4934 i.remove();
4935 }
4936 } else {
4937 boolean any = false;
4938 for (Iterator j=((Set)o).iterator(); j.hasNext(); ) {
4939 Node j_n = (Node)j.next();
4940 if (!addIfUseful(visited, path, j_n)) {
4941 j.remove();
4942 } else {
4943 any = true;
4944 }
4945 }
4946 if (!any) i.remove();
4947 }
4948 }
4949 }
4950 for (Iterator i = n.getPredecessorTargets().iterator(); i.hasNext(); ) {
4951 addAsUseful(visited, path, (Node) i.next());
4952 }
4953 if (n instanceof FieldNode) {
4954 FieldNode fn = (FieldNode) n;
4955 for (Iterator i = fn.getAccessPathPredecessors().iterator(); i.hasNext(); ) {
4956 addAsUseful(visited, path, (Node)i.next());
4957 }
4958 }
4959
4960 if (castPredecessors.contains(n)) {
4961 for (Iterator i = castMap.entrySet().iterator(); i.hasNext(); ) {
4962 Map.Entry e = (Map.Entry)i.next();
4963 Node goestocast = (Node)((Pair)e.getKey()).left;
4964 CheckCastNode castsucc = (CheckCastNode)e.getValue();
4965 if (n == goestocast)
4966 addIfUseful(visited, path, castsucc);
4967 }
4968 }
4969
4970
4971 if (n instanceof CheckCastNode) {
4972 Quad thiscast = ((QuadProgramLocation)((CheckCastNode)n).getLocation()).getQuad();
4973 for (Iterator i = castPredecessors.iterator(); i.hasNext(); ) {
4974 Node goestocast = (Node)i.next();
4975 CheckCastNode castsucc = (CheckCastNode)castMap.get(new Pair(goestocast, thiscast));
4976 if (castsucc != null)
4977 addAsUseful(visited, path, goestocast);
4978 }
4979 }
4980 path.remove(n);
4981 }
4982
4983 /*** Returns an iteration of all nodes in this summary. */
4984 public Iterator nodeIterator() { return nodes.keySet().iterator(); }
4985
4986 /*** Get the set of returned nodes. */
4987 public Set getReturned() {
4988 return returned;
4989 }
4990
4991 /*** Get the set of thrown nodes. */
4992 public Set getThrown() {
4993 return thrown;
4994 }
4995
4996 /*** Get the map of casts. */
4997 public Map getCastMap() {
4998 return castMap;
4999 }
5000
5001 /*** Get the return value node corresponding to the given method call. */
5002 public ReturnValueNode getRVN(ProgramLocation mc) {
5003 return (ReturnValueNode) callToRVN.get(mc);
5004 }
5005
5006 /*** Get the thrown exception node corresponding to the given method call. */
5007 public ThrownExceptionNode getTEN(ProgramLocation mc) {
5008 return (ThrownExceptionNode) callToTEN.get(mc);
5009 }
5010
5011 /*** Verify the integrity of the method summary data structure. */
5012 void verify() {
5013 for (int i=0; i<this.params.length; ++i) {
5014 if (this.params[i] == null) continue;
5015 if (!nodes.containsKey(this.params[i])) {
5016 Assert.UNREACHABLE(this.params[i].toString_long());
5017 }
5018 }
5019 for (Iterator i=returned.iterator(); i.hasNext(); ) {
5020 Node n = (Node) i.next();
5021 if (n instanceof UnknownTypeNode) continue;
5022 if (!nodes.containsKey(n)) {
5023 Assert.UNREACHABLE(n.toString_long());
5024 }
5025 }
5026 for (Iterator i=thrown.iterator(); i.hasNext(); ) {
5027 Node n = (Node) i.next();
5028 if (n instanceof UnknownTypeNode) continue;
5029 if (!nodes.containsKey(n)) {
5030 Assert.UNREACHABLE(n.toString_long());
5031 }
5032 }
5033 for (Iterator i=callToRVN.entrySet().iterator(); i.hasNext(); ) {
5034 Map.Entry e = (Map.Entry) i.next();
5035 if (!calls.contains(e.getKey())) {
5036 Assert.UNREACHABLE(e.toString());
5037 }
5038 Object o = e.getValue();
5039 if (o != null) {
5040 if (!nodes.containsKey(o)) {
5041 Assert.UNREACHABLE(e.toString());
5042 }
5043 }
5044 }
5045 for (Iterator i=callToTEN.entrySet().iterator(); i.hasNext(); ) {
5046 Map.Entry e = (Map.Entry) i.next();
5047 if (!calls.contains(e.getKey())) {
5048 Assert.UNREACHABLE(e.toString());
5049 }
5050 Object o = e.getValue();
5051 if (o instanceof Set) {
5052 for (Iterator j=((Set) o).iterator(); j.hasNext(); ) {
5053 Object o2 = j.next();
5054 if (!nodes.containsKey(o2)) {
5055 Assert.UNREACHABLE(e.toString());
5056 }
5057 }
5058 } else if (o != null) {
5059 if (!nodes.containsKey(o)) {
5060 Assert.UNREACHABLE(e.toString());
5061 }
5062 }
5063 }
5064 for (Iterator i=nodeIterator(); i.hasNext(); ) {
5065 Node n = (Node) i.next();
5066 if (n instanceof UnknownTypeNode) {
5067 Assert.UNREACHABLE(n.toString_long());
5068 }
5069 if (n.addedEdges != null) {
5070 for (Iterator j=n.addedEdges.entrySet().iterator(); j.hasNext(); ) {
5071 Map.Entry e = (Map.Entry) j.next();
5072 jq_Field f = (jq_Field) e.getKey();
5073 Object o = e.getValue();
5074 if (o instanceof Node) {
5075 Node n2 = (Node) o;
5076 if (!(n2 instanceof UnknownTypeNode) && !nodes.containsKey(n2)) {
5077 Assert.UNREACHABLE(n2.toString_long());
5078 }
5079 if (!n2.hasPredecessor(f, n)) {
5080 Assert.UNREACHABLE(n2.toString_long()+" has no predecessor "+n.toString_long());
5081 }
5082 } else if (o == null) {
5083
5084 } else {
5085 Set s = (Set) o;
5086 for (Iterator k=s.iterator(); k.hasNext(); ) {
5087 Node n2 = (Node) k.next();
5088 if (!(n2 instanceof UnknownTypeNode) && !nodes.containsKey(n2)) {
5089 Assert.UNREACHABLE(n2.toString_long());
5090 }
5091 if (!n2.hasPredecessor(f, n)) {
5092 Assert.UNREACHABLE(n2.toString_long()+" has no predecessor "+n.toString_long());
5093 }
5094 }
5095 }
5096 }
5097 }
5098 if (n.predecessors != null) {
5099 for (Iterator j=n.predecessors.entrySet().iterator(); j.hasNext(); ) {
5100 Map.Entry e = (Map.Entry) j.next();
5101 jq_Field f = (jq_Field) e.getKey();
5102 Object o = e.getValue();
5103 if (o instanceof Node) {
5104 Node n2 = (Node) o;
5105 if (n2 != GlobalNode.GLOBAL && !(n2 instanceof UnknownTypeNode) && !nodes.containsKey(n2)) {
5106 Assert.UNREACHABLE(this.toString()+" ::: "+n2);
5107 }
5108 if (!n2.hasNonEscapingEdge(f, n)) {
5109 Assert.UNREACHABLE(this.toString()+" ::: "+n2+" -> "+n);
5110 }
5111 } else if (o == null) {
5112
5113 } else {
5114 Set s = (Set) o;
5115 for (Iterator k=s.iterator(); k.hasNext(); ) {
5116 Node n2 = (Node) k.next();
5117 if (n2 != GlobalNode.GLOBAL && !(n2 instanceof UnknownTypeNode) && !nodes.containsKey(n2)) {
5118 Assert.UNREACHABLE(n2.toString_long());
5119 }
5120 if (!n2.hasNonEscapingEdge(f, n)) {
5121 Assert.UNREACHABLE(n2.toString_long()+" has no edge "+n.toString_long());
5122 }
5123 }
5124 }
5125 }
5126 }
5127 if (n.accessPathEdges != null) {
5128 for (Iterator j = n.accessPathEdges.entrySet().iterator(); j.hasNext(); ) {
5129 Map.Entry e = (Map.Entry) j.next();
5130
5131 Object o = e.getValue();
5132 if (o instanceof FieldNode) {
5133 FieldNode n2 = (FieldNode) o;
5134 if (!nodes.containsKey(n2)) {
5135 Assert.UNREACHABLE(n2.toString_long());
5136 }
5137 if (!n2.field_predecessors.contains(n)) {
5138 Assert.UNREACHABLE(n2.toString_long()+" has no field pred "+n.toString_long());
5139 }
5140 } else if (o == null) {
5141
5142 } else {
5143 Set s = (Set) o;
5144 for (Iterator k=s.iterator(); k.hasNext(); ) {
5145 FieldNode n2 = (FieldNode) k.next();
5146 if (!nodes.containsKey(n2)) {
5147 Assert.UNREACHABLE(n2.toString_long());
5148 }
5149 if (!n2.field_predecessors.contains(n)) {
5150 Assert.UNREACHABLE(n2.toString_long()+" has no field pred "+n.toString_long());
5151 }
5152 }
5153 }
5154 }
5155 }
5156 if (n instanceof FieldNode) {
5157 FieldNode fn = (FieldNode) n;
5158 if (fn.field_predecessors != null) {
5159 jq_Field f = (jq_Field) fn.f;
5160 for (Iterator j=fn.field_predecessors.iterator(); j.hasNext(); ) {
5161 Node n2 = (Node) j.next();
5162 if (n2 != GlobalNode.GLOBAL && !(n2 instanceof UnknownTypeNode) && !nodes.containsKey(n2)) {
5163 Assert.UNREACHABLE(this.toString()+" ::: "+n2.toString_long());
5164 }
5165 if (!n2.hasAccessPathEdge(f, fn)) {
5166 Assert.UNREACHABLE(this.toString()+" ::: "+n2.toString_long()+" => "+fn.toString_long());
5167 }
5168 }
5169 }
5170 }
5171 if (n instanceof ReturnValueNode) {
5172 if (!callToRVN.containsValue(n)) {
5173 Assert.UNREACHABLE(n.toString_long());
5174 }
5175 }
5176 if (n instanceof ThrownExceptionNode) {
5177 if (!callToTEN.containsValue(n)) {
5178 System.out.println(callToTEN);
5179 Assert.UNREACHABLE(this.toString()+" ::: "+n.toString_long());
5180 }
5181 }
5182 }
5183 }
5184
5185 /*** Helper function for multiset contains relation. */
5186 static boolean multiset_contains(Map m, Object o) {
5187 if (m == null) return false;
5188 for (Iterator i = m.values().iterator(); i.hasNext(); ) {
5189 Object p = i.next();
5190 if (p == o) return true;
5191 if (p instanceof Collection)
5192 if (((Collection) p).contains(o)) return true;
5193 }
5194 return false;
5195 }
5196
5197 public Collection getSyncedVars() {
5198 return new FlattenedCollection(this.sync_ops.values());
5199 }
5200
5201 /*** Verify that there are no references to the given node in this method summary. */
5202 void verifyNoReferences(Node n) {
5203 if (returned.contains(n))
5204 Assert.UNREACHABLE("ERROR: returned set contains "+n);
5205 if (thrown.contains(n))
5206 Assert.UNREACHABLE("ERROR: thrown set contains "+n);
5207 if (false) {
5208 for (int i=0; i<this.params.length; ++i) {
5209 if (this.params[i] == n)
5210 Assert.UNREACHABLE("ERROR: param #"+i+" "+n);
5211 }
5212 }
5213 for (Iterator i = nodeIterator(); i.hasNext(); ) {
5214 Node n2 = (Node) i.next();
5215 if (n2 instanceof UnknownTypeNode) continue;
5216 if (multiset_contains(n2.addedEdges, n)) {
5217 Assert.UNREACHABLE("ERROR: "+n2+" contains an edge to "+n);
5218 }
5219 if (multiset_contains(n2.predecessors, n)) {
5220 Assert.UNREACHABLE("ERROR: "+n2+" contains predecessor "+n);
5221 }
5222 if (multiset_contains(n2.accessPathEdges, n)) {
5223 Assert.UNREACHABLE("ERROR: "+n2+" contains access path edge to "+n);
5224 }
5225 if (n2 instanceof FieldNode) {
5226 FieldNode fn = (FieldNode) n2;
5227 if (fn.field_predecessors != null &&
5228 fn.field_predecessors.contains(n)) {
5229 Assert.UNREACHABLE("ERROR: "+fn+" contains a field predecessor "+n);
5230 }
5231 }
5232 }
5233 }
5234
5235 /*** Dumps this method summary as a dot graph. */
5236 public void dotGraph(BufferedWriter out) throws IOException {
5237 out.write("digraph \""+this.method+"\" {\n");
5238 IndexMap m = new IndexMap("MethodCallMap");
5239 for (Iterator i=nodeIterator(); i.hasNext(); ) {
5240 Node n = (Node) i.next();
5241 out.write("n"+n.id+" [label=\""+n.toString_short()+"\"];\n");
5242 }
5243 for (Iterator i=getCalls().iterator(); i.hasNext(); ) {
5244 ProgramLocation mc = (ProgramLocation) i.next();
5245 int k = m.get(mc);
5246 out.write("mc"+k+" [label=\""+mc+"\"];\n");
5247 }
5248 for (Iterator i=nodeIterator(); i.hasNext(); ) {
5249 Node n = (Node) i.next();
5250 for (Iterator j=n.getNonEscapingEdges().iterator(); j.hasNext(); ) {
5251 Map.Entry e = (Map.Entry) j.next();
5252 String fieldName = ""+e.getKey();
5253 Iterator k;
5254 if (e.getValue() instanceof Set) k = ((Set)e.getValue()).iterator();
5255 else k = Collections.singleton(e.getValue()).iterator();
5256 while (k.hasNext()) {
5257 Node n2 = (Node) k.next();
5258 out.write("n"+n.id+" -> n"+n2.id+" [label=\""+fieldName+"\"];\n");
5259 }
5260 }
5261 for (Iterator j=n.getAccessPathEdges().iterator(); j.hasNext(); ) {
5262 Map.Entry e = (Map.Entry) j.next();
5263 String fieldName = ""+e.getKey();
5264 Iterator k;
5265 if (e.getValue() instanceof Set) k = ((Set)e.getValue()).iterator();
5266 else k = Collections.singleton(e.getValue()).iterator();
5267 while (k.hasNext()) {
5268 Node n2 = (Node) k.next();
5269 out.write("n"+n.id+" -> n"+n2.id+" [label=\""+fieldName+"\",style=dashed];\n");
5270 }
5271 }
5272 if (n.getPassedParameters() != null) {
5273 for (Iterator j=n.getPassedParameters().iterator(); j.hasNext(); ) {
5274 PassedParameter pp = (PassedParameter) j.next();
5275 int k = m.get(pp.m);
5276 out.write("n"+n.id+" -> mc"+k+" [label=\"p"+pp.paramNum+"\",style=dotted];\n");
5277 }
5278 }
5279 if (n instanceof ReturnedNode) {
5280 ReturnedNode rn = (ReturnedNode) n;
5281 int k = m.get(rn.m);
5282 out.write("mc"+k+" -> n"+n.id+" [label=\"r\",style=dotted];\n");
5283 }
5284 }
5285 for (Iterator i=castMap.entrySet().iterator(); i.hasNext(); ) {
5286 Map.Entry e = (Map.Entry) i.next();
5287 Node n = (Node)((Pair)e.getKey()).left;
5288 Node n2 = (Node)e.getValue();
5289 if (nodes.containsKey(n2))
5290 out.write("n"+n.id+" -> n"+n2.id+" [label=\"(cast)\"];\n");
5291 }
5292 out.write("}\n");
5293 }
5294
5295 public static final boolean DUMP_DOTGRAPH = System.getProperty("ms.dotgraph") != null;
5296
5297 public static void main(String[] args) throws IOException {
5298 HostedVM.initialize();
5299 joeq.ClassLib.ClassLibInterface.useJoeqClasslib(true);
5300 jq_Class c = (jq_Class) jq_Type.parseType(args[0]);
5301 c.load();
5302 String name = null, desc = null;
5303 if (args.length > 1) {
5304 name = args[1];
5305
5306 if (name.equals(fakeCloneName)) {
5307 MethodSummary ms = fakeCloneMethodSummary((jq_FakeInstanceMethod)jq_FakeInstanceMethod.fakeMethod(c,
5308 fakeCloneName, "()"+c.getName()));
5309 if (DUMP_DOTGRAPH) ms.dotGraph(new BufferedWriter(new OutputStreamWriter(System.out)));
5310 else System.out.println(ms);
5311 return;
5312 }
5313
5314 if (args.length > 2) {
5315 desc = args[2];
5316 }
5317 }
5318 Collection methods;
5319 if (name != null) {
5320 jq_Method m;
5321 if (desc != null) {
5322 m = (jq_Method) c.getDeclaredMember(name, desc);
5323 } else {
5324 m = c.getDeclaredMethod(name);
5325 }
5326 methods = Collections.singleton(m);
5327 } else {
5328 methods = new LinkedList();
5329 methods.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
5330 methods.addAll(Arrays.asList(c.getDeclaredInstanceMethods()));
5331 }
5332
5333 for (Iterator i = methods.iterator(); i.hasNext(); ) {
5334 jq_Method m = (jq_Method) i.next();
5335 if (m.getBytecode() == null) continue;
5336 ControlFlowGraph cfg = CodeCache.getCode(m);
5337
5338
5339 if (SSA) new EnterSSA().visitCFG(cfg);
5340
5341
5342 MethodSummary ms = getSummary(cfg);
5343 if (DUMP_DOTGRAPH) ms.dotGraph(new BufferedWriter(new OutputStreamWriter(System.out)));
5344 else System.out.println(ms);
5345 }
5346 }
5347
5348 public Collection getRegisterAtLocation(BasicBlock bb, Quad q, Register r) {
5349 builder.updateLocation(bb, q);
5350 Object o = builder.getRegister(r);
5351 if (o instanceof Node) return Collections.singleton(o);
5352 else return ((Collection) o);
5353 }
5354
5355 /***
5356 * fake method summaries for fake methods.
5357 */
5358 private static HashMap fakeCache = new HashMap();
5359 public static MethodSummary fakeMethodSummary(jq_Method method) {
5360 MethodSummary ms = (MethodSummary)fakeCache.get(method);
5361 if (ms != null)
5362 return ms;
5363
5364 boolean mustfake = method instanceof jq_FakeInstanceMethod;
5365 if (mustfake && method.getName().toString().equals(fakeCloneName)) {
5366 ms = fakeCloneMethodSummary((jq_FakeInstanceMethod)method);
5367 } else if (identityMethods.contains(method)) {
5368 ms = fakeIdentityMethodSummary(method);
5369 } else {
5370 if (!mustfake)
5371 return null;
5372 throw new Error("don't know how to fake " + method);
5373 }
5374 fakeCache.put(method, ms);
5375 return ms;
5376 }
5377
5378 private static HashSet
5379 {
5380 jq_Class throwable_class = PrimordialClassLoader.getJavaLangThrowable();
5381 identityMethods.add(throwable_class.getDeclaredMember("fillInStackTrace", "()Ljava/lang/Throwable;"));
5382 }
5383
5384 /***
5385 * fake a method summary that simulates the effect of '{ return this; }'
5386 */
5387 static MethodSummary fakeIdentityMethodSummary(jq_Method method) {
5388 jq_Class clazz = method.getDeclaringClass();
5389 ParamNode []params = new ParamNode[] { FakeParamNode.getFake(method, 0, clazz) };
5390
5391 return new MethodSummary((BuildMethodSummary)null,
5392 method,
5393 params,
5394 GlobalNode.get(method),
5395
5396
5397
5398
5399
5400
5401
5402
5403
5404 }
5405
5406 /***
5407 * fake a method summary that simulates the effect of the inherited default clone().
5408 */
5409 public static String fakeCloneName = "fake$clone";
5410 public static MethodSummary fakeCloneMethodSummary(jq_FakeInstanceMethod method) {
5411 jq_Class clazz = method.getDeclaringClass();
5412 ParamNode []params = new ParamNode[] { FakeParamNode.getFake(method, 0, clazz) };
5413 ConcreteTypeNode clone = ConcreteTypeNode.get(clazz, new FakeProgramLocation(method, "fakedclone"));
5414
5415 clazz.prepare();
5416 jq_InstanceField [] f = clazz.getInstanceFields();
5417 for (int i = 0; i < f.length; i++) {
5418 if (f[i].getType().isReferenceType())
5419 clone.addEdge(f[i], FieldNode.get(params[0], f[i], new FakeProgramLocation(method, "field="+f[i].getName())));
5420 }
5421
5422 return new MethodSummary((BuildMethodSummary)null,
5423 method,
5424 params,
5425 GlobalNode.get(method),
5426
5427
5428
5429
5430
5431
5432
5433
5434
5435 }
5436
5437 public static class OperandToNodeMap {
5438
5439 MultiMap operandToNode;
5440
5441 public static void write(Textualizer t) throws IOException {
5442 for (Iterator i = MethodSummary.summary_cache.entrySet().iterator(); i.hasNext(); ) {
5443 Map.Entry e = (Map.Entry) i.next();
5444 jq_Method m = (jq_Method) e.getKey();
5445 if (m.getBytecode() == null) continue;
5446 MethodSummary s = (MethodSummary) e.getValue();
5447 ControlFlowGraph cfg = CodeCache.getCode(m);
5448 m.write(t);
5449 for (Iterator j = cfg.reversePostOrderIterator(); j.hasNext(); ) {
5450 BasicBlock bb = (BasicBlock) j.next();
5451 s.builder.bb = bb;
5452 State state = s.builder.start_states[bb.getID()];
5453 s.builder.s = state.copy();
5454 for (Iterator k = bb.iterator(); k.hasNext(); ) {
5455 Quad q = (Quad) k.next();
5456 t.writeString("quad "+q.getID()+" ");
5457 for (Iterator l = q.getUsedRegisters().iterator(); l.hasNext(); ) {
5458 RegisterOperand op = (RegisterOperand) l.next();
5459 t.writeString("op ");
5460 Register r = ((RegisterOperand) op).getRegister();
5461 Object o = s.builder.getRegister(r);
5462 Set set;
5463 if (o instanceof Set) {
5464 set = (Set) o;
5465 } else {
5466 set = Collections.singleton(o);
5467 }
5468 for (Iterator n = set.iterator(); n.hasNext(); ) {
5469
5470 }
5471 }
5472 }
5473 }
5474 }
5475 }
5476 }
5477
5478 public static boolean isNullConstant(Node node) {
5479 if (node instanceof ConcreteTypeNode || node instanceof ConcreteObjectNode) {
5480 jq_Reference type = node.getDeclaredType();
5481 if (type == null || type == jq_NullType.NULL_TYPE) {
5482 return true;
5483 }
5484 }
5485 return false;
5486 }
5487 }