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