View Javadoc

1   // LiveRefAnalysis.java, created Fri Jan 11 16:49:00 2002 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.BytecodeAnalysis;
5   
6   import java.util.Set;
7   import joeq.Class.PrimordialClassLoader;
8   import joeq.Class.jq_Array;
9   import joeq.Class.jq_InstanceField;
10  import joeq.Class.jq_Method;
11  import joeq.Class.jq_Primitive;
12  import joeq.Class.jq_StaticField;
13  import joeq.Class.jq_Type;
14  import joeq.Runtime.TypeCheck;
15  import jwutil.collections.LinearSet;
16  import jwutil.math.BitString;
17  import jwutil.math.BitString.BitStringIterator;
18  import jwutil.strings.Strings;
19  import jwutil.util.Assert;
20  
21  /***
22   * A combination liveness and type analysis for Java bytecode.
23   * 
24   * @author  John Whaley <jwhaley@alum.mit.edu>
25   * @version $Id: LiveRefAnalysis.java 2282 2005-05-28 11:14:27Z joewhaley $
26   */
27  public class LiveRefAnalysis {
28  
29      private jq_Method method;
30      private ExactState[] start_states;
31      private ExactState[] end_states;
32      
33      /*** Creates new LiveRefAnalysis */
34      public LiveRefAnalysis(jq_Method method) {
35          this.method = method;
36      }
37  
38      public ExactState getState(BasicBlock bb) {
39          return start_states[bb.id];
40      }
41      
42      public static final byte NOT_LIVE = 0;
43      public static final byte LIVE_INT = 1;
44      public static final byte LIVE_FLOAT = 2;
45      public static final byte LIVE_LONG1 = 3;
46      public static final byte LIVE_LONG2 = 4;
47      public static final byte LIVE_DOUBLE1 = 5;
48      public static final byte LIVE_DOUBLE2 = 6;
49      public static final byte LIVE_REF = 7;
50      public static final byte LIVE_DERIVED_REF = 8;
51      public static final byte LIVE_RETADDR = 9;
52      public static final String[] TYPE_NAMES = {
53          "NOT_LIVE", "LIVE_INT", "LIVE_FLOAT", "LIVE_LONG1", "LIVE_LONG2",
54          "LIVE_DOUBLE1", "LIVE_DOUBLE2", "LIVE_REF", "LIVE_DERIVED_REF", "LIVE_RETADDR" };
55      public static final byte SET_TO_INT = 33;        // for JSR subroutines
56      public static final byte SET_TO_FLOAT = 34;
57      public static final byte SET_TO_LONG1 = 35;
58      public static final byte SET_TO_LONG2 = 36;
59      public static final byte SET_TO_DOUBLE1 = 37;
60      public static final byte SET_TO_DOUBLE2 = 38;
61      public static final byte SET_TO_REF = 39;
62      public static final byte SET_TO_DERIVED_REF = 40;
63      public static final byte SET_TO_RETADDR = 41;
64      
65      public void compute() {
66          ControlFlowGraph bc_cfg = ControlFlowGraph.computeCFG(method);
67          compute(bc_cfg);
68      }
69      
70      public void compute(ControlFlowGraph bc_cfg) {
71          
72          // Pass 1 (forward): Compute bytecode boundaries and initial sets, and identify
73          // bytecodes that manipulate heap addresses.
74          FirstPassVisitor fpv = new FirstPassVisitor(method, bc_cfg);
75          // traverse reverse post-order over basic blocks
76          this.start_states = new ExactState[bc_cfg.getNumberOfBasicBlocks()];
77          this.end_states = new ExactState[bc_cfg.getNumberOfBasicBlocks()];
78          this.start_states[2] = ExactState.allocateInitialState(method);
79          for (;;) {
80              fpv.go_again = false;
81              joeq.Compiler.BytecodeAnalysis.ControlFlowGraph.RPOBasicBlockIterator rpo = bc_cfg.reversePostOrderIterator();
82              BasicBlock first_bb = rpo.nextBB();
83              Assert._assert(first_bb == bc_cfg.getEntry());
84              // initialize start states
85              while (rpo.hasNext()) {
86                  if (ALWAYS_TRACE)
87                      System.out.println("Iteration : "+rpo.toString());
88                  BasicBlock bc_bb = rpo.nextBB();
89                  if (ALWAYS_TRACE)
90                      System.out.println(bc_bb+" : start state "+this.start_states[bc_bb.id]);
91                  fpv.traverseBB(bc_bb);
92                  if (ALWAYS_TRACE)
93                      System.out.println(bc_bb+" : end state "+this.end_states[bc_bb.id]);
94              }
95              if (!fpv.go_again) break;
96          }
97          
98          // Pass 1.5: Search for blocks that are unreachable by a backward traversal
99          // (caused by infinite loops) and add fake backedges to make them reachable.
100         
101         // Pass 2 (backward): Perform live variable analysis
102         SecondPassVisitor spv = new SecondPassVisitor(method, fpv.getBytecodeStart());
103         // traverse post-order over basic blocks
104         for (;;) {
105             spv.go_again = false;
106             joeq.Compiler.BytecodeAnalysis.ControlFlowGraph.RPOBasicBlockIterator rpo = bc_cfg.reversePostOrderIterator();
107             rpo.jumpToEnd();
108             while (rpo.hasPrevious()) {
109                 if (ALWAYS_TRACE)
110                     System.out.println("Iteration : "+rpo.toString());
111                 BasicBlock bc_bb = rpo.previousBB();
112                 if (ALWAYS_TRACE)
113                     System.out.println(bc_bb+" : end state "+this.end_states[bc_bb.id]);
114                 spv.traverseBB(bc_bb);
115                 if (ALWAYS_TRACE)
116                     System.out.println(bc_bb+" : start state "+this.start_states[bc_bb.id]);
117             }
118             if (!spv.go_again) break;
119         }
120     }
121 
122     public void dump() {
123         for(int i=0; i<start_states.length; ++i) {
124             if (start_states[i] != null) {
125                 System.out.println("BB"+i+" start: "+start_states[i].toString());
126             }
127             if (end_states[i] != null) {
128                 System.out.println("BB"+i+" end: "+end_states[i].toString());
129             }
130         }
131         System.out.println();
132     }
133     
134     /*
135     public static class State {
136         private int stackDepth;
137         private byte[] stack; private byte[] locals;
138         public static State allocateEmptyState(jq_Method m) {
139             return new State(m.getMaxStack(), m.getMaxLocals());
140         }
141         public static State allocateInitialState(jq_Method m) {
142             State s = new State(m.getMaxStack(), m.getMaxLocals());
143             jq_Type[] paramTypes = m.getParamTypes();
144             for (int i=0,j=0; i<paramTypes.length; ++i, ++j) {
145                 if (paramTypes[i].isReferenceType()) {
146                     s.locals[j] = LIVE_REF;
147                 } else if (paramTypes[i].isIntLike()) {
148                     s.locals[j] = LIVE_INT;
149                 } else if (paramTypes[i] == jq_Primitive.FLOAT) {
150                     s.locals[j] = LIVE_FLOAT;
151                 } else if (paramTypes[i] == jq_Primitive.LONG) {
152                     s.locals[j] = LIVE_LONG1;
153                     s.locals[++j] = LIVE_LONG2;
154                 } else if (paramTypes[i] == jq_Primitive.DOUBLE) {
155                     s.locals[j] = LIVE_DOUBLE1;
156                     s.locals[++j] = LIVE_DOUBLE2;
157                 } else {
158                     jq.UNREACHABLE();
159                 }
160             }
161             return s;
162         }
163         State(int stacksize, int localsize) {
164             stack = new byte[stacksize]; locals = new byte[localsize];
165             stackDepth = 0;
166         }
167         public State copy() {
168             State that = new State(this.stack.length, this.locals.length);
169             System.arraycopy(this.stack, 0, that.stack, 0, this.stackDepth);
170             System.arraycopy(this.locals, 0, that.locals, 0, this.locals.length);
171             that.stackDepth = this.stackDepth;
172             return that;
173         }
174         public boolean merge(State that) {
175             jq.Assert(this.stackDepth == that.stackDepth);
176             boolean change = false;
177             for (int i=0; i<this.stackDepth; ++i) {
178                 if (this.stack[i] != that.stack[i]) { this.stack[i] = NOT_LIVE; change = true; }
179             }
180             for (int i=0; i<this.locals.length; ++i) {
181                 if (this.locals[i] != that.locals[i]) { this.locals[i] = NOT_LIVE; change = true; }
182             }
183             return change;
184         }
185         public void overwriteWith(State that) {
186             jq.Assert(this.stack.length == that.stack.length);
187             jq.Assert(this.locals.length == that.locals.length);
188             System.arraycopy(that.stack, 0, this.stack, 0, that.stackDepth);
189             System.arraycopy(that.locals, 0, this.locals, 0, that.locals.length);
190             this.stackDepth = that.stackDepth;
191         }
192         void push_I() { stack[stackDepth++] = LIVE_INT; }
193         void push_F() { stack[stackDepth++] = LIVE_FLOAT; }
194         void push_L() { stack[stackDepth++] = LIVE_LONG1; stack[stackDepth++] = LIVE_LONG2; }
195         void push_D() { stack[stackDepth++] = LIVE_DOUBLE1; stack[stackDepth++] = LIVE_DOUBLE2; }
196         void push_A() { stack[stackDepth++] = LIVE_REF; }
197         void push_R() { stack[stackDepth++] = LIVE_DERIVED_REF; }
198         void push_RetAddr() { stack[stackDepth++] = LIVE_RETADDR; }
199         void pop_I() { --stackDepth; jq.Assert(stack[stackDepth] == LIVE_INT); }
200         void pop_F() { --stackDepth; jq.Assert(stack[stackDepth] == LIVE_FLOAT); }
201         void pop_L() { stackDepth-=2; jq.Assert(stack[stackDepth] == LIVE_LONG1); jq.Assert(stack[stackDepth+1] == LIVE_LONG2); }
202         void pop_D() { stackDepth-=2; jq.Assert(stack[stackDepth] == LIVE_DOUBLE1); jq.Assert(stack[stackDepth+1] == LIVE_DOUBLE2); }
203         void pop_A() { --stackDepth; jq.Assert(stack[stackDepth] == LIVE_REF); }
204         void pop_R() { --stackDepth; jq.Assert(stack[stackDepth] == LIVE_DERIVED_REF); }
205         byte pop() { return stack[--stackDepth]; }
206         void push(byte t) { stack[stackDepth++] = t; }
207         void pop(jq_Type t) {
208             if (t.isReferenceType()) pop_A();
209             else if (t.isIntLike()) {
210                 byte t2 = pop();
211                 if (t2 != LIVE_DERIVED_REF)
212                     System.err.println("WARNING: method takes derived ref as an argument");
213             }
214             else if (t == jq_Primitive.FLOAT) pop_F();
215             else if (t == jq_Primitive.LONG) pop_L();
216             else if (t == jq_Primitive.DOUBLE) pop_D();
217             else jq.UNREACHABLE();
218         }
219         public int getStackDepth() { return stackDepth; }
220         public byte getStack(int i) { return stack[i]; }
221 
222         //static boolean isLiveIntType(byte type) {
223         //    return type == LIVE_INT || type == LIVE_DERIVED_REF;
224         //}
225         
226         void setLocal_I(int i) { locals[i] = LIVE_INT; }
227         void setLocal_F(int i) { locals[i] = LIVE_FLOAT; }
228         void setLocal_L(int i) { locals[i] = LIVE_LONG1; locals[i+1] = LIVE_LONG2; }
229         void setLocal_D(int i) { locals[i] = LIVE_DOUBLE1; locals[i+1] = LIVE_DOUBLE2; }
230         void setLocal_A(int i) { locals[i] = LIVE_REF; }
231         void setLocal_RetAddr(int i) { locals[i] = LIVE_RETADDR; }
232         void setLocal(int i, byte t) { locals[i] = t; }
233         public byte getLocal(int i) { return locals[i]; }
234         public int getNumberOfLocals() { return locals.length; }
235         
236         public String toString() {
237             StringBuffer sb = new StringBuffer("Locals: { ");
238             for (int i=0; i<locals.length; ++i) {
239                 if (locals[i] == NOT_LIVE) continue;
240                 sb.append(i);
241                 sb.append('=');
242                 sb.append(TYPE_NAMES[locals[i]]);
243                 if (i < locals.length-1) sb.append(',');
244             }
245             sb.append(" }");
246             if (stackDepth > 0) {
247                 sb.append(Strings.lineSep+"Stack: {");
248                 for (int i=0; i<stackDepth; ++i) {
249                     sb.append(i);
250                     sb.append('=');
251                     sb.append(stack[i]==null?"null":stack[i].toString());
252                     if (i < stackDepth-1) sb.append(',');
253                 }
254                 sb.append(" }");
255             }
256             return sb.toString();
257         }
258     }
259     */
260 
261     public abstract static class Type {
262         public abstract Type findCommonSuperclass(Type that);
263         public abstract boolean isReferenceType();
264         public Type getElementType() { return NullConstant.INSTANCE; }
265     }
266     
267     public static class SystemType extends Type {
268         private final jq_Type type;
269         SystemType(jq_Type jq_t) {
270             if (jq_t.isIntLike()) jq_t = jq_Primitive.INT;
271             this.type = jq_t;
272         }
273         public jq_Type getType() { return type; }
274         public Type findCommonSuperclass(Type that) {
275             if (that instanceof SystemType) {
276                 SystemType t = (SystemType)that;
277                 jq_Type jq_t = TypeCheck.findCommonSuperclass(this.type, t.type, true);
278                 if (jq_t == null) return null;
279                 if (jq_t == this.type) return this;
280                 if (jq_t == t.type) return t;
281                 if (ALWAYS_TRACE) System.out.println("Superclass of "+this+" and "+that+" is "+jq_t);
282                 return new SystemType(jq_t);
283             }
284             if (that instanceof NullConstant) {
285                 if (this.type.isReferenceType()) return this;
286             }
287             return null;
288         }
289         public Type getElementType() {
290             jq_Array a = (jq_Array)type;
291             if (a.getElementType().isAddressType()) return DerivedRef.INSTANCE;
292             return new SystemType(a.getElementType());
293         }
294         public boolean equals(SystemType that) {
295             return this.type == that.type;
296         }
297         public boolean equals(Object that) {
298             return equals((SystemType)that);
299         }
300         public int hashCode() { return type.hashCode(); }
301         public boolean isReferenceType() { return type.isReferenceType(); }
302         public String toString() { return type.toString(); }
303         public static final SystemType INT    = new SystemType(jq_Primitive.INT);
304         public static final SystemType FLOAT  = new SystemType(jq_Primitive.FLOAT);
305         public static final SystemType LONG   = new SystemType(jq_Primitive.LONG);
306         public static final SystemType DOUBLE = new SystemType(jq_Primitive.DOUBLE);
307         public static final SystemType OBJECT = new SystemType(PrimordialClassLoader.getJavaLangObject());
308     }
309     
310     public static class DerivedRef extends Type {
311         public Type findCommonSuperclass(Type that) {
312             if (that instanceof DerivedRef) return this;
313             return null;
314         }
315         public boolean isReferenceType() { return false; }
316         public String toString() { return "DerivedRef"; }
317         public static final DerivedRef INSTANCE = new DerivedRef();
318     }
319     
320     public static class NullConstant extends Type {
321         
322         public Type findCommonSuperclass(Type that) {
323             if (that.isReferenceType()) return that;
324             return null;
325         }
326         public boolean isReferenceType() { return true; }
327         public String toString() { return "NULL"; }
328         public static final NullConstant INSTANCE = new NullConstant();
329     }
330 
331     public static class HalfOfNumber extends Type {
332         public Type findCommonSuperclass(Type that) {
333             if (that instanceof HalfOfNumber) return that;
334             return null;
335         }
336         public boolean isReferenceType() { return false; }
337         public String toString() { return "HALF"; }
338         public static final HalfOfNumber INSTANCE = new HalfOfNumber();
339     }
340     
341     public static class Retaddr extends Type {
342         int location;
343         Retaddr(int l) { this.location = l; }
344         public Type findCommonSuperclass(Type that) {
345             if (that instanceof Retaddr) {
346                 if (this.equals((Retaddr)that)) return this;
347             }
348             return null;
349         }
350         public boolean equals(Retaddr that) {
351             return this.location == that.location;
352         }
353         public boolean equals(Object that) {
354             return equals((Retaddr)that);
355         }
356         public int hashCode() { return location; }
357         public boolean isReferenceType() { return false; }
358         public String toString() { return "RetAddr:"+location; }
359     }
360 
361     public static class ExactJSRState extends ExactState {
362         protected boolean[] mayChangeLocals;
363         protected boolean[] mustChangeLocals;
364         ExactJSRState(int stacksize, int localsize) {
365             super(stacksize, localsize);
366             mayChangeLocals = new boolean[localsize];
367             mustChangeLocals = new boolean[localsize];
368         }
369         public ExactState copy() {
370             ExactJSRState that = new ExactJSRState(this.stack.length, this.locals.length);
371             System.arraycopy(this.stack, 0, that.stack, 0, this.stackDepth);
372             System.arraycopy(this.locals, 0, that.locals, 0, this.locals.length);
373             System.arraycopy(this.mayChangeLocals, 0, that.mayChangeLocals, 0, this.mayChangeLocals.length);
374             System.arraycopy(this.mustChangeLocals, 0, that.mustChangeLocals, 0, this.mustChangeLocals.length);
375             that.stackDepth = this.stackDepth;
376             return that;
377         }
378         public ExactJSRState copyAsJSR() {
379             // nested jsr's!
380             if (ALWAYS_TRACE) System.out.println("nested jsr's! adding nesting level");
381             // we need a fresh may/mustChangeLocals array for the nested jsr
382             return super.copyAsJSR();
383         }
384         public ExactState copyJSR(ExactJSRState jsr_state) {
385             // nested jsr's!
386             if (ALWAYS_TRACE) System.out.println("nested jsr's! removing nesting level");
387             ExactJSRState that = new ExactJSRState(this.stack.length, this.locals.length);
388             System.arraycopy(jsr_state.stack, 0, that.stack, 0, jsr_state.stackDepth);
389             System.arraycopy(this.locals, 0, that.locals, 0, this.locals.length);
390             that.stackDepth = jsr_state.stackDepth;
391             for (int i=0; i<this.locals.length; ++i) {
392                 if (jsr_state.mayChangeLocals[i]) {
393                     if (ALWAYS_TRACE) System.out.println("nested jsr may change local "+i);
394                     this.locals[i] = jsr_state.locals[i];
395                     this.mayChangeLocals[i] = true;
396                     if (jsr_state.mustChangeLocals[i]) {
397                         this.mustChangeLocals[i] = true;
398                     }
399                 }
400             }
401             return that;
402         }
403         public ExactState copyHandler(jq_Type t) {
404             ExactJSRState that = new ExactJSRState(this.stack.length, this.locals.length);
405             System.arraycopy(this.locals, 0, that.locals, 0, this.locals.length);
406             System.arraycopy(this.mayChangeLocals, 0, that.mayChangeLocals, 0, this.mayChangeLocals.length);
407             System.arraycopy(this.mustChangeLocals, 0, that.mustChangeLocals, 0, this.mustChangeLocals.length);
408             that.stackDepth = 1; that.stack[0] = new SystemType(t);
409             return that;
410         }
411         public boolean mergeBeforeJSR(ExactState that) {
412             // don't merge changedLocals from 'that'
413             return super.merge(that);
414         }
415         public boolean merge(ExactState that) {
416             Assert._assert(this.stackDepth == that.stackDepth);
417             boolean change = false;
418             for (int i=0; i<this.stackDepth; ++i) {
419                 if (this.stack[i] == null) continue;
420                 if (that.stack[i] == null) { this.stack[i] = null; change = true; continue; }
421                 Type t = this.stack[i].findCommonSuperclass(that.stack[i]);
422                 if (t != this.stack[i]) change = true;
423                 this.stack[i] = t;
424             }
425             for (int i=0; i<this.locals.length; ++i) {
426                 if (this.locals[i] == null) continue;
427                 if (that.locals[i] == null) { this.locals[i] = null; change = true; continue; }
428                 Type t = this.locals[i].findCommonSuperclass(that.locals[i]);
429                 if (t != this.locals[i]) change = true;
430                 this.locals[i] = t;
431             }
432             if (that instanceof ExactJSRState) {
433                 ExactJSRState that2 = (ExactJSRState)that;
434                 for (int i=0; i<this.mayChangeLocals.length; ++i) {
435                     if (that2.mayChangeLocals[i]) {
436                         if (!this.mayChangeLocals[i]) {
437                             if (ALWAYS_TRACE) System.out.println("updated: may change local "+i+" during merge");
438                             this.mayChangeLocals[i] = true;
439                             change = true;
440                         }
441                     }
442                     if (!that2.mustChangeLocals[i]) {
443                         if (this.mustChangeLocals[i]) {
444                             this.mustChangeLocals[i] = false;
445                             change = true;
446                         }
447                     }
448                 }
449             }
450             return change;
451         }
452         public boolean mergeWithHandler(ExactState that) {
453             Assert._assert(this.stackDepth == 1);
454             boolean change = false;
455             for (int i=0; i<this.locals.length; ++i) {
456                 if (this.locals[i] == null) continue;
457                 if (that.locals[i] == null) { this.locals[i] = null; change = true; continue; }
458                 Type t = this.locals[i].findCommonSuperclass(that.locals[i]);
459                 if (t != this.locals[i]) change = true;
460                 this.locals[i] = t;
461             }
462             if (that instanceof ExactJSRState) {
463                 ExactJSRState that2 = (ExactJSRState)that;
464                 for (int i=0; i<this.mayChangeLocals.length; ++i) {
465                     if (that2.mayChangeLocals[i]) {
466                         if (!this.mayChangeLocals[i]) {
467                             if (ALWAYS_TRACE) System.out.println("updated: may change local "+i+" during exception handler merge");
468                             this.mayChangeLocals[i] = true;
469                             change = true;
470                         }
471                     }
472                     if (!that2.mustChangeLocals[i]) {
473                         if (this.mustChangeLocals[i]) {
474                             this.mustChangeLocals[i] = false;
475                             change = true;
476                         }
477                     }
478                 }
479             }
480             return change;
481         }
482         
483         void setLocal_I(int i) { super.setLocal_I(i); this.mayChangeLocals[i] = this.mustChangeLocals[i] = true; }
484         void setLocal_F(int i) { super.setLocal_F(i); this.mayChangeLocals[i] = this.mustChangeLocals[i] = true; }
485         void setLocal_L(int i) { super.setLocal_L(i); this.mayChangeLocals[i] = this.mustChangeLocals[i] = true; this.mayChangeLocals[i+1] = this.mustChangeLocals[i+1] = true; }
486         void setLocal_D(int i) { super.setLocal_D(i); this.mayChangeLocals[i] = this.mustChangeLocals[i] = true; this.mayChangeLocals[i+1] = this.mustChangeLocals[i+1] = true; }
487         void setLocal(int i, Type t) { super.setLocal(i, t); this.mayChangeLocals[i] = this.mustChangeLocals[i] = true; }
488         
489         public String toString_live() {
490             StringBuffer sb = new StringBuffer("Live Locals: { ");
491             for (int i=0; i<locals.length; ++i) {
492                 if (getLocal(i) == null) continue;
493                 sb.append(i);
494                 sb.append('=');
495                 sb.append(locals[i].toString());
496                 if (mayChangeLocals[i]) sb.append('*');
497                 if (mustChangeLocals[i]) sb.append('&');
498                 if (i < locals.length-1) sb.append(',');
499             }
500             sb.append(" }");
501             if (stackDepth > 0) {
502                 sb.append(Strings.lineSep);
503                 sb.append("Stack: {");
504                 for (int i=0; i<stackDepth; ++i) {
505                     sb.append(i);
506                     sb.append('=');
507                     sb.append(stack[i]==null?"null":stack[i].toString());
508                     if (i < stackDepth-1) sb.append(',');
509                 }
510                 sb.append(" }");
511             }
512             return sb.toString();
513         }
514         public String toString() {
515             if (liveness != null) return toString_live();
516             StringBuffer sb = new StringBuffer("Locals: { ");
517             for (int i=0; i<locals.length; ++i) {
518                 if (locals[i] == null) continue;
519                 sb.append(i);
520                 sb.append('=');
521                 sb.append(locals[i].toString());
522                 if (mayChangeLocals[i]) sb.append('*');
523                 if (mustChangeLocals[i]) sb.append('&');
524                 if (i < locals.length-1) sb.append(',');
525             }
526             sb.append(" }");
527             if (stackDepth > 0) {
528                 sb.append(Strings.lineSep);
529                 sb.append("Stack: {");
530                 for (int i=0; i<stackDepth; ++i) {
531                     sb.append(i);
532                     sb.append('=');
533                     sb.append(stack[i]==null?"null":stack[i].toString());
534                     if (i < stackDepth-1) sb.append(',');
535                 }
536                 sb.append(" }");
537             }
538             return sb.toString();
539         }
540     }
541     
542     public static class ExactState {
543         protected int stackDepth;
544         protected Type[] stack; protected Type[] locals;
545         protected boolean[] liveness;
546         protected Set last_uses;
547         public static ExactState allocateEmptyState(jq_Method m) {
548             return new ExactState(m.getMaxStack(), m.getMaxLocals());
549         }
550         public static ExactState allocateInitialState(jq_Method m) {
551             ExactState s = new ExactState(m.getMaxStack(), m.getMaxLocals());
552             jq_Type[] paramTypes = m.getParamTypes();
553             for (int i=0, j=0; i<paramTypes.length; ++i, ++j) {
554                 s.locals[j] = new SystemType(paramTypes[i]);
555                 if (paramTypes[i].getReferenceSize() == 8) {
556                     s.locals[++j] = HalfOfNumber.INSTANCE;
557                 }
558             }
559             return s;
560         }
561         ExactState(int stacksize, int localsize) {
562             stack = new Type[stacksize]; locals = new Type[localsize];
563             stackDepth = 0;
564         }
565         public void allocateLiveness() {
566             if (liveness == null)
567                 liveness = new boolean[locals.length];
568         }
569         public void initializeLastUses() {
570             last_uses = new LinearSet();
571         }
572         public boolean compareLiveness(ExactState that) {
573             if (that.liveness == null) return true;
574             for (int i=0; i<this.liveness.length; ++i) {
575                 if (this.liveness[i] != that.liveness[i]) return true;
576             }
577             return false;
578         }
579         public ExactState copy() {
580             ExactState that = new ExactState(this.stack.length, this.locals.length);
581             System.arraycopy(this.stack, 0, that.stack, 0, this.stackDepth);
582             System.arraycopy(this.locals, 0, that.locals, 0, this.locals.length);
583             if (this.liveness != null) {
584                 that.liveness = new boolean[this.liveness.length];
585                 System.arraycopy(this.liveness, 0, that.liveness, 0, this.liveness.length);
586             }
587             that.stackDepth = this.stackDepth;
588             return that;
589         }
590         public ExactJSRState copyAsJSR() {
591             ExactJSRState that = new ExactJSRState(this.stack.length, this.locals.length);
592             System.arraycopy(this.stack, 0, that.stack, 0, this.stackDepth);
593             System.arraycopy(this.locals, 0, that.locals, 0, this.locals.length);
594             that.stackDepth = this.stackDepth;
595             return that;
596         }
597         public ExactState copyJSR(ExactJSRState jsr_state) {
598             ExactState that = new ExactState(this.stack.length, this.locals.length);
599             System.arraycopy(jsr_state.stack, 0, that.stack, 0, jsr_state.stackDepth);
600             System.arraycopy(this.locals, 0, that.locals, 0, this.locals.length);
601             that.stackDepth = jsr_state.stackDepth;
602             for (int i=0; i<this.locals.length; ++i) {
603                 if (jsr_state.mayChangeLocals[i]) {
604                     this.locals[i] = jsr_state.locals[i];
605                 }
606             }
607             return that;
608         }
609         public ExactState copyHandler(jq_Type t) {
610             ExactState that = new ExactState(this.stack.length, this.locals.length);
611             System.arraycopy(this.locals, 0, that.locals, 0, this.locals.length);
612             that.stackDepth = 1; that.stack[0] = new SystemType(t);
613             return that;
614         }
615         public boolean mergeLiveness(ExactState that) {
616             if (that.liveness == null) return false;
617             if (this.liveness == null) {
618                 this.liveness = new boolean[this.locals.length];
619                 System.arraycopy(that.liveness, 0, this.liveness, 0, this.liveness.length);
620                 return true;
621             }
622             boolean change = false;
623             for (int i=0; i<this.liveness.length; ++i) {
624                 if (this.liveness[i]) continue;
625                 if (that.liveness[i]) {
626                     this.liveness[i] = true;
627                     change = true;
628                     continue;
629                 }
630             }
631             return change;
632         }
633         // Conservative approximation!  we union the two live sets
634         // this == at JSR call, that == after JSR call
635         /*
636         public boolean mergeLivenessJSR(ExactState that, ExactJSRState jsr_start) {
637             if (that.liveness == null) return false;
638             if (jsr_state.liveness == null) return false;
639             if (this.liveness == null) {
640                 this.liveness = new boolean[this.locals.length];
641             }
642             boolean change = false;
643             for (int i=0; i<this.liveness.length; ++i) {
644                 if (this.liveness[i]) continue;
645                 if (jsr_start.liveness[i] || that.liveness[i]) {
646                     this.liveness[i] = true;
647                     change = true;
648                     continue;
649                 }
650             }
651             return change;
652         }
653         */
654 
655         public boolean merge(ExactState that) {
656             Assert._assert(this.stackDepth == that.stackDepth);
657             boolean change = false;
658             for (int i=0; i<this.stackDepth; ++i) {
659                 if (this.stack[i] == null) continue;
660                 if (that.stack[i] == null) { this.stack[i] = null; change = true; continue; }
661                 Type t = this.stack[i].findCommonSuperclass(that.stack[i]);
662                 if (t != this.stack[i]) change = true;
663                 this.stack[i] = t;
664             }
665             for (int i=0; i<this.locals.length; ++i) {
666                 if (this.locals[i] == null) {
667                     continue;
668                 }
669                 if (that.locals[i] == null) {
670                     this.locals[i] = null;
671                     change = true;
672                     continue;
673                 }
674                 Type t = this.locals[i].findCommonSuperclass(that.locals[i]);
675                 if (t != this.locals[i]) change = true;
676                 this.locals[i] = t;
677             }
678             return change;
679         }
680         // this == after JSR call, that == before JSR call, jsr_state == end of JSR body
681         public boolean mergeJSR(ExactState that, ExactJSRState jsr_state) {
682             Assert._assert(this.stackDepth == jsr_state.stackDepth);
683             boolean change = false;
684             for (int i=0; i<this.stackDepth; ++i) {
685                 if (this.stack[i] == null) continue;
686                 if (jsr_state.stack[i] == null) { this.stack[i] = null; change = true; continue; }
687                 Type t = this.stack[i].findCommonSuperclass(jsr_state.stack[i]);
688                 if (t != this.stack[i]) change = true;
689                 this.stack[i] = t;
690             }
691             for (int i=0; i<this.locals.length; ++i) {
692                 if (this.locals[i] == null) {
693                     continue;
694                 }
695                 Type that_type;
696                 if (jsr_state.mayChangeLocals[i]) {
697                     that_type = jsr_state.locals[i];
698                 } else {
699                     that_type = that.locals[i];
700                 }
701                 if (that_type == null) {
702                     this.locals[i] = null;
703                     change = true;
704                     continue;
705                 }
706                 Type t = this.locals[i].findCommonSuperclass(that_type);
707                 if (t != this.locals[i]) change = true;
708                 this.locals[i] = t;
709             }
710             return change;
711         }
712         public boolean mergeWithHandler(ExactState that) {
713             Assert._assert(this.stackDepth == 1);
714             boolean change = false;
715             for (int i=0; i<this.locals.length; ++i) {
716                 if (this.locals[i] == null) {
717                     continue;
718                 }
719                 if (that.locals[i] == null) {
720                     this.locals[i] = null;
721                     change = true;
722                     continue;
723                 }
724                 Type t = this.locals[i].findCommonSuperclass(that.locals[i]);
725                 if (t != this.locals[i]) change = true;
726                 this.locals[i] = t;
727             }
728             return change;
729         }
730 
731         void push_I() { stack[stackDepth++] = SystemType.INT; }
732         void push_F() { stack[stackDepth++] = SystemType.FLOAT; }
733         void push_L() { stack[stackDepth++] = SystemType.LONG; stack[stackDepth++] = HalfOfNumber.INSTANCE; }
734         void push_D() { stack[stackDepth++] = SystemType.DOUBLE; stack[stackDepth++] = HalfOfNumber.INSTANCE; }
735         void push_R() { stack[stackDepth++] = DerivedRef.INSTANCE; }
736         void push_RetAddr(int target) { stack[stackDepth++] = new Retaddr(target); }
737         void pop_I() { --stackDepth; Assert._assert(stack[stackDepth].equals(SystemType.INT)); }
738         void pop_F() { --stackDepth; Assert._assert(stack[stackDepth].equals(SystemType.FLOAT)); }
739         void pop_L() { stackDepth-=2; Assert._assert(stack[stackDepth].equals(SystemType.LONG)); Assert._assert(stack[stackDepth+1] == HalfOfNumber.INSTANCE); }
740         void pop_D() { stackDepth-=2; Assert._assert(stack[stackDepth].equals(SystemType.DOUBLE)); Assert._assert(stack[stackDepth+1] == HalfOfNumber.INSTANCE); }
741         void pop_A() { --stackDepth; Assert._assert(stack[stackDepth].isReferenceType()); }
742         void pop_R() { --stackDepth; Assert._assert(stack[stackDepth] == DerivedRef.INSTANCE); }
743         Type pop() { return stack[--stackDepth]; }
744         void push(Type t) {
745             stack[stackDepth++] = t;
746             //if (t.equals(SystemType.LONG) || t.equals(SystemType.DOUBLE)) stack[stackDepth++] = HalfOfNumber.INSTANCE;
747         }
748         void pop(jq_Type t) {
749             if (t.isAddressType()) pop_R();
750             else if (t.isReferenceType()) pop_A();
751             else if (t.isIntLike()) pop_I();
752             else if (t == jq_Primitive.FLOAT) pop_F();
753             else if (t == jq_Primitive.LONG) pop_L();
754             else if (t == jq_Primitive.DOUBLE) pop_D();
755             else Assert.UNREACHABLE();
756         }
757         public int getStackDepth() { return stackDepth; }
758         public Type getStack(int i) { return stack[i]; }
759 
760         //static boolean isLiveIntType(byte type) {
761         //    return type == LIVE_INT || type == LIVE_DERIVED_REF;
762         //}
763         
764         void setLocal_I(int i) { locals[i] = SystemType.INT; }
765         void setLocal_F(int i) { locals[i] = SystemType.FLOAT; }
766         void setLocal_L(int i) { locals[i] = SystemType.LONG; locals[i+1] = HalfOfNumber.INSTANCE; }
767         void setLocal_D(int i) { locals[i] = SystemType.DOUBLE; locals[i+1] = HalfOfNumber.INSTANCE; }
768         void setLocal_R(int i) { locals[i] = DerivedRef.INSTANCE; }
769         void setLocal(int i, Type t) { locals[i] = t; }
770         public Type getLocal(int i) { return locals[i]; }
771 
772         public Type getLiveLocal(int i) {
773             if (liveness[i]) return locals[i];
774             else return null;
775         }
776         void liveLocal_I(int bci, int i) {
777             checkLastUse(bci, i); liveness[i] = true;
778         }
779         void liveLocal_F(int bci, int i) {
780             checkLastUse(bci, i); liveness[i] = true;
781         }
782         void liveLocal_L(int bci, int i) {
783             checkLastUse(bci, i); liveness[i] = true;
784             checkLastUse(bci, i+1); liveness[i+1] = true;
785         }
786         void liveLocal_D(int bci, int i) {
787             checkLastUse(bci, i); liveness[i] = true;
788             checkLastUse(bci, i+1); liveness[i+1] = true;
789         }
790         void liveLocal_A(int bci, int i) {
791             checkLastUse(bci, i); liveness[i] = true;
792         }
793         void deadLocal_I(int i) { liveness[i] = false; }
794         void deadLocal_F(int i) { liveness[i] = false; }
795         void deadLocal_L(int i) { liveness[i] = false; liveness[i+1] = false; }
796         void deadLocal_D(int i) { liveness[i] = false; liveness[i+1] = false; }
797         void deadLocal_A(int i) { liveness[i] = false; }
798 
799         void checkLastUse(int bci, int i) {
800             if (liveness[i] == false) {
801                 if (ALWAYS_TRACE)
802                     System.out.println(bci+": Last use of local "+i);
803                 last_uses.add(new LastUse(bci, i));
804             }
805         }
806 
807         static class LastUse {
808             int bci, i;
809             LastUse(int bci, int i) { this.bci = bci; this.i = i; }
810         }
811 
812         public int getNumberOfLocals() { return locals.length; }
813         
814         public String toString_live() {
815             StringBuffer sb = new StringBuffer("Live Locals: { ");
816             for (int i=0; i<locals.length; ++i) {
817                 if (getLiveLocal(i) == null) continue;
818                 sb.append(i);
819                 sb.append('=');
820                 sb.append(getLiveLocal(i).toString());
821                 if (i < locals.length-1) sb.append(',');
822             }
823             sb.append(" }");
824             if (stackDepth > 0) {
825                 sb.append(Strings.lineSep);
826                 sb.append("Stack: {");
827                 for (int i=0; i<stackDepth; ++i) {
828                     sb.append(i);
829                     sb.append('=');
830                     sb.append(stack[i]==null?"null":stack[i].toString());
831                     if (i < stackDepth-1) sb.append(',');
832                 }
833                 sb.append(" }");
834             }
835             return sb.toString();
836         }
837         public String toString() {
838             if (liveness != null) return toString_live();
839             StringBuffer sb = new StringBuffer("Locals: { ");
840             for (int i=0; i<locals.length; ++i) {
841                 if (getLocal(i) == null) continue;
842                 sb.append(i);
843                 sb.append('=');
844                 sb.append(getLocal(i).toString());
845                 if (i < locals.length-1) sb.append(',');
846             }
847             sb.append(" }");
848             if (stackDepth > 0) {
849                 sb.append(Strings.lineSep);
850                 sb.append("Stack: {");
851                 for (int i=0; i<stackDepth; ++i) {
852                     sb.append(i);
853                     sb.append('=');
854                     sb.append(stack[i]==null?"null":stack[i].toString());
855                     if (i < stackDepth-1) sb.append(',');
856                 }
857                 sb.append(" }");
858             }
859             return sb.toString();
860         }
861     }
862     
863     public static boolean ALWAYS_TRACE = false;
864     
865     public class FirstPassVisitor extends BytecodeVisitor {
866         private BitString bytecode_start;
867         private ExactState current_state;
868         private BasicBlock current_bb;
869         private ControlFlowGraph cfg;
870 
871         FirstPassVisitor(jq_Method method, ControlFlowGraph cfg) {
872             super(method);
873             this.bytecode_start = new BitString(bcs.length);
874             this.current_state = ExactState.allocateEmptyState(method);
875             this.cfg = cfg;
876             this.TRACE = ALWAYS_TRACE;
877         }
878         
879         public String toString() { return "LR1/"+this.method.getName(); }
880         
881         boolean isEndOfBB(BasicBlock bb) { return i_start > bb.getEnd(); }
882         
883         boolean go_again = false;
884         boolean endsWithJSR = false, endsWithRET = false;
885 
886         public BitString getBytecodeStart() { return bytecode_start; }
887 
888         public void traverseBB(joeq.Compiler.BytecodeAnalysis.BasicBlock bb) {
889             if (start_states[bb.id] == null) {
890                 // unreachable block!
891                 if (TRACE) out.println("Basic block "+bb+" is unreachable!");
892                 return;
893             }
894             if (bb.getStart() == -1) {
895                 return; // entry or exit
896             }
897             if (TRACE) out.println("Visiting "+bb);
898             current_state = start_states[bb.id].copy();
899             //current_state.overwriteWith(start_states[bb.id]);
900             current_bb = bb;
901             endsWithJSR = false; endsWithRET = false;
902             for (i_end=bb.getStart()-1; ; ) {
903                 i_start = i_end+1;
904                 if (isEndOfBB(bb)) break;
905                 bytecode_start.set(i_start);
906                 try {
907                     this.visitBytecode();
908                 } catch (RuntimeException x) {
909                     System.err.println("EXCEPTION OCCURRED while analyzing "+this.method+" bc "+(int)i_start);
910                     throw x;
911                 }
912             }
913             //end_states[bb.id] = copyStateInto(end_states[bb.id], current_state);
914             end_states[bb.id] = current_state;
915             if (endsWithRET) {
916                 for (int i=0; i<bb.getNumberOfSuccessors(); ++i) {
917                     BasicBlock jsr_caller = cfg.getBasicBlock(bb.getSuccessor(i).id-1);
918                     if (TRACE) out.println("Merging with jsr successor "+bb.getSuccessor(i)+" from jsr call at "+jsr_caller);
919                     if (start_states[jsr_caller.id] != null) {
920                         if (this.mergeJSRStateWith(jsr_caller, bb.getSuccessor(i))) go_again = true;
921                     } else {
922                         if (TRACE) out.println("jsr "+jsr_caller+" is not yet reached (or is unreachable");
923                     }
924                 }
925             } else {
926                 for (int i=0; i<bb.getNumberOfSuccessors(); ++i) {
927                     if (bb.getSuccessor(i).id == 1) continue;
928                     if (TRACE) out.println("Merging with successor "+bb.getSuccessor(i));
929                     if (this.mergeStateWith(bb.getSuccessor(i), endsWithJSR)) go_again = true;
930                 }
931             }
932         }
933         
934         private boolean mergeWithExceptionHandlers() {
935             boolean change = false;
936             ExceptionHandlerIterator ehi = current_bb.getExceptionHandlers();
937             while (ehi.hasNext()) {
938                 ExceptionHandler eh = ehi.nextEH();
939                 BasicBlock bb2 = eh.getEntry();
940                 jq_Type t = eh.getExceptionType();
941                 if (t == null) t = PrimordialClassLoader.getJavaLangThrowable();
942                 if (TRACE) out.println("Merging with handler "+bb2+" type "+t);
943                 if (start_states[bb2.id] == null) {
944                     change = true;
945                     start_states[bb2.id] = current_state.copyHandler(t);
946                 } else {
947                     if (start_states[bb2.id].mergeWithHandler(current_state)) change = true;
948                 }
949             }
950             if (change) go_again = true;
951             return change;
952         }
953         
954         private boolean mergeStateWith(BasicBlock bb2, boolean jsr) {
955             if (start_states[bb2.id] == null) {
956                 if (jsr)
957                     start_states[bb2.id] = current_state.copyAsJSR();
958                 else
959                     start_states[bb2.id] = current_state.copy();
960                 return true;
961             } else {
962                 if (jsr) {
963                     Assert._assert(start_states[bb2.id] instanceof ExactJSRState);
964                     return ((ExactJSRState)start_states[bb2.id]).mergeBeforeJSR(current_state);
965                 } else {
966                     return start_states[bb2.id].merge(current_state);
967                 }
968             }
969         }
970         
971         private boolean mergeJSRStateWith(BasicBlock before, BasicBlock after) {
972             Assert._assert(current_state instanceof ExactJSRState);
973             if (end_states[before.id] == null) {
974                 System.err.println(this.method+" ::: Warning! Successor of JSR block "+before+" has not yet been visited.");
975                 return false;
976             }
977             ExactJSRState jsr_state = (ExactJSRState)current_state;
978             if (start_states[after.id] == null) {
979                 start_states[after.id] = end_states[before.id].copyJSR(jsr_state);
980                 return true;
981             } else return start_states[after.id].mergeJSR(end_states[before.id], jsr_state);
982         }
983         
984         /*
985         private ExactState copyStateInto(ExactState s1, ExactState s2) {
986             if (s1 == null) return s2.copy();
987             s1.overwriteWith(s2); return s1;
988         }
989          */
990         
991         public void visitNOP() {
992             super.visitNOP();
993         }
994         public void visitACONST(Object s) {
995             super.visitACONST(s);
996             current_state.push(NullConstant.INSTANCE);
997         }
998         public void visitICONST(int c) {
999             super.visitICONST(c);
1000             current_state.push_I();
1001         }
1002         public void visitLCONST(long c) {
1003             super.visitLCONST(c);
1004             current_state.push_L();
1005         }
1006         public void visitFCONST(float c) {
1007             super.visitFCONST(c);
1008             current_state.push_F();
1009         }
1010         public void visitDCONST(double c) {
1011             super.visitDCONST(c);
1012             current_state.push_D();
1013         }
1014         public void visitILOAD(int i) {
1015             super.visitILOAD(i);
1016             current_state.push_I();
1017         }
1018         public void visitLLOAD(int i) {
1019             super.visitLLOAD(i);
1020             current_state.push_L();
1021         }
1022         public void visitFLOAD(int i) {
1023             super.visitFLOAD(i);
1024             current_state.push_F();
1025         }
1026         public void visitDLOAD(int i) {
1027             super.visitDLOAD(i);
1028             current_state.push_D();
1029         }
1030         public void visitALOAD(int i) {
1031             super.visitALOAD(i);
1032             current_state.push(current_state.getLocal(i));
1033         }
1034         public void visitISTORE(int i) {
1035             super.visitISTORE(i);
1036             current_state.pop_I(); current_state.setLocal_I(i);
1037         }
1038         public void visitLSTORE(int i) {
1039             super.visitLSTORE(i);
1040             current_state.pop_L(); current_state.setLocal_L(i);
1041         }
1042         public void visitFSTORE(int i) {
1043             super.visitFSTORE(i);
1044             current_state.pop_F(); current_state.setLocal_F(i);
1045         }
1046         public void visitDSTORE(int i) {
1047             super.visitDSTORE(i);
1048             current_state.pop_D(); current_state.setLocal_D(i);
1049         }
1050         public void visitASTORE(int i) {
1051             super.visitASTORE(i);
1052             current_state.setLocal(i, current_state.pop());
1053         }
1054         public void visitIALOAD() {
1055             super.visitIALOAD();
1056             current_state.pop_I(); current_state.pop_A(); current_state.push_I();
1057             mergeWithExceptionHandlers();
1058         }
1059         public void visitLALOAD() {
1060             super.visitLALOAD();
1061             current_state.pop_I(); current_state.pop_A(); current_state.push_L();
1062             mergeWithExceptionHandlers();
1063         }
1064         public void visitFALOAD() {
1065             super.visitFALOAD();
1066             current_state.pop_I(); current_state.pop_A(); current_state.push_F();
1067             mergeWithExceptionHandlers();
1068         }
1069         public void visitDALOAD() {
1070             super.visitDALOAD();
1071             current_state.pop_I(); current_state.pop_A(); current_state.push_D();
1072             mergeWithExceptionHandlers();
1073         }
1074         public void visitAALOAD() {
1075             super.visitAALOAD();
1076             current_state.pop_I();
1077             Type t = current_state.pop();
1078             Type t2 = t.getElementType();
1079             current_state.push(t2);
1080             mergeWithExceptionHandlers();
1081         }
1082         public void visitBALOAD() {
1083             super.visitBALOAD();
1084             current_state.pop_I(); current_state.pop_A(); current_state.push_I();
1085             mergeWithExceptionHandlers();
1086         }
1087         public void visitCALOAD() {
1088             super.visitCALOAD();
1089             current_state.pop_I(); current_state.pop_A(); current_state.push_I();
1090             mergeWithExceptionHandlers();
1091         }
1092         public void visitSALOAD() {
1093             super.visitSALOAD();
1094             current_state.pop_I(); current_state.pop_A(); current_state.push_I();
1095             mergeWithExceptionHandlers();
1096         }
1097         public void visitIASTORE() {
1098             super.visitIASTORE();
1099             current_state.pop_I(); current_state.pop_I(); current_state.pop_A();
1100             mergeWithExceptionHandlers();
1101         }
1102         public void visitLASTORE() {
1103             super.visitLASTORE();
1104             current_state.pop_L(); current_state.pop_I(); current_state.pop_A();
1105             mergeWithExceptionHandlers();
1106         }
1107         public void visitFASTORE() {
1108             super.visitFASTORE();
1109             current_state.pop_F(); current_state.pop_I(); current_state.pop_A();
1110             mergeWithExceptionHandlers();
1111         }
1112         public void visitDASTORE() {
1113             super.visitDASTORE();
1114             current_state.pop_D(); current_state.pop_I(); current_state.pop_A();
1115             mergeWithExceptionHandlers();
1116         }
1117         public void visitAASTORE() {
1118             super.visitAASTORE();
1119             Type t = current_state.pop(); // may be storing derived ref
1120             current_state.pop_I();
1121             Type t2 = current_state.pop();
1122             if (t instanceof DerivedRef)
1123                 Assert._assert(t2.getElementType() instanceof DerivedRef);
1124             mergeWithExceptionHandlers();
1125         }
1126         public void visitBASTORE() {
1127             super.visitBASTORE();
1128             current_state.pop_I(); current_state.pop_I(); current_state.pop_A();
1129             mergeWithExceptionHandlers();
1130         }
1131         public void visitCASTORE() {
1132             super.visitCASTORE();
1133             current_state.pop_I(); current_state.pop_I(); current_state.pop_A();
1134             mergeWithExceptionHandlers();
1135         }
1136         public void visitSASTORE() {
1137             super.visitSASTORE();
1138             current_state.pop_I(); current_state.pop_I(); current_state.pop_A();
1139             mergeWithExceptionHandlers();
1140         }
1141         public void visitPOP() {
1142             super.visitPOP();
1143             current_state.pop();
1144         }
1145         public void visitPOP2() {
1146             super.visitPOP2();
1147             current_state.pop(); current_state.pop();
1148         }
1149         public void visitDUP() {
1150             super.visitDUP();
1151             Type t = current_state.pop(); current_state.push(t); current_state.push(t);
1152         }
1153         public void visitDUP_x1() {
1154             super.visitDUP_x1();
1155             Type t1 = current_state.pop(); Type t2 = current_state.pop();
1156             current_state.push(t1); current_state.push(t2); current_state.push(t1);
1157         }
1158         public void visitDUP_x2() {
1159             super.visitDUP_x2();
1160             Type t1 = current_state.pop(); Type t2 = current_state.pop(); Type t3 = current_state.pop();
1161             current_state.push(t1); current_state.push(t3); current_state.push(t2); current_state.push(t1);
1162         }
1163         public void visitDUP2() {
1164             super.visitDUP2();
1165             Type t1 = current_state.pop(); Type t2 = current_state.pop();
1166             current_state.push(t2); current_state.push(t1); current_state.push(t2); current_state.push(t1);
1167         }
1168         public void visitDUP2_x1() {
1169             super.visitDUP2_x1();
1170             Type t1 = current_state.pop(); Type t2 = current_state.pop(); Type t3 = current_state.pop();
1171             current_state.push(t2); current_state.push(t1); current_state.push(t3); current_state.push(t2); current_state.push(t1);
1172         }
1173         public void visitDUP2_x2() {
1174             super.visitDUP2_x2();
1175             Type t1 = current_state.pop(); Type t2 = current_state.pop(); Type t3 = current_state.pop(); Type t4 = current_state.pop();
1176             current_state.push(t2); current_state.push(t1); current_state.push(t4); current_state.push(t3); current_state.push(t2); current_state.push(t1);
1177         }
1178         public void visitSWAP() {
1179             super.visitSWAP();
1180             Type t1 = current_state.pop(); Type t2 = current_state.pop();
1181             current_state.push(t1); current_state.push(t2);
1182         }
1183         public void visitIBINOP(byte op) {
1184             super.visitIBINOP(op);
1185             current_state.pop_I();
1186         }
1187         public void visitLBINOP(byte op) {
1188             super.visitLBINOP(op);
1189             current_state.pop_L();
1190         }
1191         public void visitFBINOP(byte op) {
1192             super.visitFBINOP(op);
1193             current_state.pop_F();
1194         }
1195         public void visitDBINOP(byte op) {
1196             super.visitDBINOP(op);
1197             current_state.pop_D();
1198         }
1199         public void visitIUNOP(byte op) {
1200             super.visitIUNOP(op);
1201         }
1202         public void visitLUNOP(byte op) {
1203             super.visitLUNOP(op);
1204         }
1205         public void visitFUNOP(byte op) {
1206             super.visitFUNOP(op);
1207         }
1208         public void visitDUNOP(byte op) {
1209             super.visitDUNOP(op);
1210         }
1211         public void visitISHIFT(byte op) {
1212             super.visitISHIFT(op);
1213             current_state.pop_I();
1214         }
1215         public void visitLSHIFT(byte op) {
1216             super.visitLSHIFT(op);
1217             current_state.pop_I();
1218         }
1219         public void visitIINC(int i, int v) {
1220             super.visitIINC(i, v);
1221         }
1222         public void visitI2L() {
1223             super.visitI2L();
1224             current_state.pop_I(); current_state.push_L();
1225         }
1226         public void visitI2F() {
1227             super.visitI2F();
1228             current_state.pop_I(); current_state.push_F();
1229         }
1230         public void visitI2D() {
1231             super.visitI2D();
1232             current_state.pop_I(); current_state.push_D();
1233         }
1234         public void visitL2I() {
1235             super.visitL2I();
1236             current_state.pop_L(); current_state.push_I();
1237         }
1238         public void visitL2F() {
1239             super.visitL2F();
1240             current_state.pop_L(); current_state.push_F();
1241         }
1242         public void visitL2D() {
1243             super.visitL2D();
1244             current_state.pop_L(); current_state.push_D();
1245         }
1246         public void visitF2I() {
1247             super.visitF2I();
1248             current_state.pop_F(); current_state.push_I();
1249         }
1250         public void visitF2L() {
1251             super.visitF2L();
1252             current_state.pop_F(); current_state.push_L();
1253         }
1254         public void visitF2D() {
1255             super.visitF2D();
1256             current_state.pop_F(); current_state.push_D();
1257         }
1258         public void visitD2I() {
1259             super.visitD2I();
1260             current_state.pop_D(); current_state.push_I();
1261         }
1262         public void visitD2L() {
1263             super.visitD2L();
1264             current_state.pop_D(); current_state.push_L();
1265         }
1266         public void visitD2F() {
1267             super.visitD2F();
1268             current_state.pop_D(); current_state.push_F();
1269         }
1270         public void visitI2B() {
1271             super.visitI2B();
1272         }
1273         public void visitI2C() {
1274             super.visitI2C();
1275         }
1276         public void visitI2S() {
1277             super.visitI2S();
1278         }
1279         public void visitLCMP2() {
1280             super.visitLCMP2();
1281             current_state.pop_L(); current_state.pop_L(); current_state.push_I();
1282         }
1283         public void visitFCMP2(byte op) {
1284             super.visitFCMP2(op);
1285             current_state.pop_F(); current_state.pop_F(); current_state.push_I();
1286         }
1287         public void visitDCMP2(byte op) {
1288             super.visitDCMP2(op);
1289             current_state.pop_D(); current_state.pop_D(); current_state.push_I();
1290         }
1291         public void visitIF(byte op, int target) {
1292             super.visitIF(op, target);
1293             current_state.pop_I();
1294         }
1295         public void visitIFREF(byte op, int target) {
1296             super.visitIFREF(op, target);
1297             current_state.pop_A();
1298         }
1299         public void visitIFCMP(byte op, int target) {
1300             super.visitIFCMP(op, target);
1301             current_state.pop_I(); current_state.pop_I();
1302         }
1303         public void visitIFREFCMP(byte op, int target) {
1304             super.visitIFREFCMP(op, target);
1305             current_state.pop_A(); current_state.pop_A();
1306         }
1307         public void visitGOTO(int target) {
1308             super.visitGOTO(target);
1309         }
1310         public void visitJSR(int target) {
1311             super.visitJSR(target);
1312             endsWithJSR = true;
1313             current_state.push_RetAddr(target);
1314         }
1315         public void visitRET(int i) {
1316             super.visitRET(i);
1317             Retaddr r = (Retaddr)current_state.getLocal(i);
1318             endsWithRET = true;
1319             // add JSR edges, if they don't already exist.
1320             BasicBlock jsub_bb = cfg.getBasicBlockByBytecodeIndex(r.location);
1321             if (current_bb.getNumberOfSuccessors() == 0) {
1322                 if (TRACE) out.println("Adding jsr subroutine edges to "+current_bb);
1323                 current_bb.setSubroutineRet(cfg, jsub_bb);
1324                 if (TRACE) {
1325                     out.println("Number of jsr subroutine edges: "+current_bb.getNumberOfSuccessors());
1326                     for (int j=0; j<current_bb.getNumberOfSuccessors(); ++j) {
1327                         out.println("Successor "+j+": "+current_bb.getSuccessor(j));
1328                     }
1329                 }
1330             }
1331             cfg.addJSRInfo(jsub_bb, current_bb, ((ExactJSRState)current_state).mayChangeLocals);
1332         }
1333         public void visitTABLESWITCH(int default_target, int low, int high, int[] targets) {
1334             super.visitTABLESWITCH(default_target, low, high, targets);
1335             current_state.pop_I();
1336         }
1337         public void visitLOOKUPSWITCH(int default_target, int[] values, int[] targets) {
1338             super.visitLOOKUPSWITCH(default_target, values, targets);
1339             current_state.pop_I();
1340         }
1341         public void visitIRETURN() {
1342             super.visitIRETURN();
1343         }
1344         public void visitLRETURN() {
1345             super.visitLRETURN();
1346         }
1347         public void visitFRETURN() {
1348             super.visitFRETURN();
1349         }
1350         public void visitDRETURN() {
1351             super.visitDRETURN();
1352         }
1353         public void visitARETURN() {
1354             super.visitARETURN();
1355         }
1356         public void visitVRETURN() {
1357             super.visitVRETURN();
1358         }
1359         public void visitIGETSTATIC(jq_StaticField f) {
1360             super.visitIGETSTATIC(f);
1361             current_state.push_I();
1362         }
1363         public void visitLGETSTATIC(jq_StaticField f) {
1364             super.visitLGETSTATIC(f);
1365             current_state.push_L();
1366         }
1367         public void visitFGETSTATIC(jq_StaticField f) {
1368             super.visitFGETSTATIC(f);
1369             current_state.push_F();
1370         }
1371         public void visitDGETSTATIC(jq_StaticField f) {
1372             super.visitDGETSTATIC(f);
1373             current_state.push_D();
1374         }
1375         public void visitAGETSTATIC(jq_StaticField f) {
1376             super.visitAGETSTATIC(f);
1377             Type t;
1378             if (f.getType().isAddressType()) t = DerivedRef.INSTANCE;
1379             else t = new SystemType(f.getType());
1380             current_state.push(t);
1381         }
1382         public void visitZGETSTATIC(jq_StaticField f) {
1383             super.visitZGETSTATIC(f);
1384             current_state.push_I();
1385         }
1386         public void visitBGETSTATIC(jq_StaticField f) {
1387             super.visitBGETSTATIC(f);
1388             current_state.push_I();
1389         }
1390         public void visitCGETSTATIC(jq_StaticField f) {
1391             super.visitCGETSTATIC(f);
1392             current_state.push_I();
1393         }
1394         public void visitSGETSTATIC(jq_StaticField f) {
1395             super.visitSGETSTATIC(f);
1396             current_state.push_I();
1397         }
1398         public void visitIPUTSTATIC(jq_StaticField f) {
1399             super.visitIPUTSTATIC(f);
1400             current_state.pop_I();
1401         }
1402         public void visitLPUTSTATIC(jq_StaticField f) {
1403             super.visitLPUTSTATIC(f);
1404             current_state.pop_L();
1405         }
1406         public void visitFPUTSTATIC(jq_StaticField f) {
1407             super.visitFPUTSTATIC(f);
1408             current_state.pop_F();
1409         }
1410         public void visitDPUTSTATIC(jq_StaticField f) {
1411             super.visitDPUTSTATIC(f);
1412             current_state.pop_D();
1413         }
1414         public void visitAPUTSTATIC(jq_StaticField f) {
1415             super.visitAPUTSTATIC(f);
1416             if (f.getType().isAddressType()) current_state.pop_R();
1417             else current_state.pop_A();
1418         }
1419         public void visitZPUTSTATIC(jq_StaticField f) {
1420             super.visitZPUTSTATIC(f);
1421             current_state.pop_I();
1422         }
1423         public void visitBPUTSTATIC(jq_StaticField f) {
1424             super.visitBPUTSTATIC(f);
1425             current_state.pop_I();
1426         }
1427         public void visitCPUTSTATIC(jq_StaticField f) {
1428             super.visitCPUTSTATIC(f);
1429             current_state.pop_I();
1430         }
1431         public void visitSPUTSTATIC(jq_StaticField f) {
1432             super.visitSPUTSTATIC(f);
1433             current_state.pop_I();
1434         }
1435         public void visitIGETFIELD(jq_InstanceField f) {
1436             super.visitIGETFIELD(f);
1437             current_state.pop_A(); current_state.push_I();
1438             mergeWithExceptionHandlers();
1439         }
1440         public void visitLGETFIELD(jq_InstanceField f) {
1441             super.visitLGETFIELD(f);
1442             current_state.pop_A(); current_state.push_L();
1443             mergeWithExceptionHandlers();
1444         }
1445         public void visitFGETFIELD(jq_InstanceField f) {
1446             super.visitFGETFIELD(f);
1447             current_state.pop_A(); current_state.push_F();
1448             mergeWithExceptionHandlers();
1449         }
1450         public void visitDGETFIELD(jq_InstanceField f) {
1451             super.visitDGETFIELD(f);
1452             current_state.pop_A(); current_state.push_D();
1453             mergeWithExceptionHandlers();
1454         }
1455         public void visitAGETFIELD(jq_InstanceField f) {
1456             super.visitAGETFIELD(f);
1457             current_state.pop_A();
1458             Type t;
1459             if (f.getType().isAddressType()) t = DerivedRef.INSTANCE;
1460             else t = new SystemType(f.getType());
1461             current_state.push(t);
1462             mergeWithExceptionHandlers();
1463         }
1464         public void visitBGETFIELD(jq_InstanceField f) {
1465             super.visitBGETFIELD(f);
1466             current_state.pop_A(); current_state.push_I();
1467             mergeWithExceptionHandlers();
1468         }
1469         public void visitCGETFIELD(jq_InstanceField f) {
1470             super.visitCGETFIELD(f);
1471             current_state.pop_A(); current_state.push_I();
1472             mergeWithExceptionHandlers();
1473         }
1474         public void visitSGETFIELD(jq_InstanceField f) {
1475             super.visitSGETFIELD(f);
1476             current_state.pop_A(); current_state.push_I();
1477             mergeWithExceptionHandlers();
1478         }
1479         public void visitZGETFIELD(jq_InstanceField f) {
1480             super.visitZGETFIELD(f);
1481             current_state.pop_A(); current_state.push_I();
1482             mergeWithExceptionHandlers();
1483         }
1484         public void visitIPUTFIELD(jq_InstanceField f) {
1485             super.visitIPUTFIELD(f);
1486             current_state.pop_I(); current_state.pop_A();
1487             mergeWithExceptionHandlers();
1488         }
1489         public void visitLPUTFIELD(jq_InstanceField f) {
1490             super.visitLPUTFIELD(f);
1491             current_state.pop_L(); current_state.pop_A();
1492             mergeWithExceptionHandlers();
1493         }
1494         public void visitFPUTFIELD(jq_InstanceField f) {
1495             super.visitFPUTFIELD(f);
1496             current_state.pop_F(); current_state.pop_A();
1497             mergeWithExceptionHandlers();
1498         }
1499         public void visitDPUTFIELD(jq_InstanceField f) {
1500             super.visitDPUTFIELD(f);
1501             current_state.pop_D(); current_state.pop_A();
1502             mergeWithExceptionHandlers();
1503         }
1504         public void visitAPUTFIELD(jq_InstanceField f) {
1505             super.visitAPUTFIELD(f);
1506             if (f.getType().isAddressType()) current_state.pop_R();
1507             else current_state.pop_A();
1508             current_state.pop_A();
1509             mergeWithExceptionHandlers();
1510         }
1511         public void visitBPUTFIELD(jq_InstanceField f) {
1512             super.visitBPUTFIELD(f);
1513             current_state.pop_I(); current_state.pop_A();
1514             mergeWithExceptionHandlers();
1515         }
1516         public void visitCPUTFIELD(jq_InstanceField f) {
1517             super.visitCPUTFIELD(f);
1518             current_state.pop_I(); current_state.pop_A();
1519             mergeWithExceptionHandlers();
1520         }
1521         public void visitSPUTFIELD(jq_InstanceField f) {
1522             super.visitSPUTFIELD(f);
1523             current_state.pop_I(); current_state.pop_A();
1524             mergeWithExceptionHandlers();
1525         }
1526         public void visitZPUTFIELD(jq_InstanceField f) {
1527             super.visitZPUTFIELD(f);
1528             current_state.pop_I(); current_state.pop_A();
1529             mergeWithExceptionHandlers();
1530         }
1531         private void INVOKEhelper(jq_Method f) {
1532             jq_Type[] paramTypes = f.getParamTypes();
1533             for (int i=paramTypes.length-1; i>=0; --i) {
1534                 current_state.pop(paramTypes[i]);
1535             }
1536             mergeWithExceptionHandlers();
1537         }
1538         public void visitIINVOKE(byte op, jq_Method f) {
1539             super.visitIINVOKE(op, f);
1540             INVOKEhelper(f); current_state.push_I();
1541         }
1542         public void visitLINVOKE(byte op, jq_Method f) {
1543             super.visitLINVOKE(op, f);
1544             INVOKEhelper(f); current_state.push_L();
1545         }
1546         public void visitFINVOKE(byte op, jq_Method f) {
1547             super.visitFINVOKE(op, f);
1548             INVOKEhelper(f); current_state.push_F();
1549         }
1550         public void visitDINVOKE(byte op, jq_Method f) {
1551             super.visitDINVOKE(op, f);
1552             INVOKEhelper(f); current_state.push_D();
1553         }
1554         public void visitAINVOKE(byte op, jq_Method f) {
1555             super.visitAINVOKE(op, f);
1556             INVOKEhelper(f);
1557             Type t;
1558             if (f.getReturnType().isAddressType()) t = DerivedRef.INSTANCE;
1559             else t = new SystemType(f.getReturnType());
1560             current_state.push(t);
1561         }
1562         public void visitVINVOKE(byte op, jq_Method f) {
1563             super.visitVINVOKE(op, f);
1564             INVOKEhelper(f);
1565         }
1566         public void visitNEW(jq_Type f) {
1567             super.visitNEW(f);
1568             current_state.push(new SystemType(f));
1569             mergeWithExceptionHandlers();
1570         }
1571         public void visitNEWARRAY(jq_Array f) {
1572             super.visitNEWARRAY(f);
1573             current_state.pop_I();
1574             current_state.push(new SystemType(f));
1575             mergeWithExceptionHandlers();
1576         }
1577         public void visitCHECKCAST(jq_Type f) {
1578             super.visitCHECKCAST(f);
1579             current_state.pop_A();
1580             current_state.push(new SystemType(f));
1581             mergeWithExceptionHandlers();
1582         }
1583         public void visitINSTANCEOF(jq_Type f) {
1584             super.visitINSTANCEOF(f);
1585             current_state.pop_A(); current_state.push_I();
1586         }
1587         public void visitARRAYLENGTH() {
1588             super.visitARRAYLENGTH();
1589             current_state.pop_A(); current_state.push_I();
1590             mergeWithExceptionHandlers();
1591         }
1592         public void visitATHROW() {
1593             super.visitATHROW();
1594             mergeWithExceptionHandlers();
1595         }
1596         public void visitMONITOR(byte op) {
1597             super.visitMONITOR(op);
1598             current_state.pop_A();
1599             mergeWithExceptionHandlers();
1600         }
1601         public void visitMULTINEWARRAY(jq_Type f, char dim) {
1602             super.visitMULTINEWARRAY(f, dim);
1603             for (int i=0; i<dim; ++i) current_state.pop_I();
1604             current_state.push(new SystemType(f));
1605             mergeWithExceptionHandlers();
1606         }
1607     }
1608     
1609     public class SecondPassVisitor extends BytecodeVisitor {
1610         private BitString bytecode_start;
1611         private BasicBlock current_bb;
1612         private ExactState current_state;
1613 
1614         boolean go_again = false;
1615 
1616         SecondPassVisitor(jq_Method method, BitString bytecode_start) {
1617             super(method);
1618             this.bytecode_start = bytecode_start;
1619             this.current_state = ExactState.allocateEmptyState(method);
1620             this.TRACE = ALWAYS_TRACE;
1621         }
1622         
1623         public String toString() { return "LR2/"+this.method.getName(); }
1624         
1625         public void traverseBB(joeq.Compiler.BytecodeAnalysis.BasicBlock bb) {
1626             if ((end_states[bb.id] == null) || (start_states[bb.id] == null)) {
1627                 // unreachable block!
1628                 if (TRACE) out.println("Basic block "+bb+" is unreachable!");
1629                 return;
1630             }
1631             if (bb.getStart() == -1) {
1632                 return;
1633             }
1634             if (TRACE) out.println("Visiting "+bb);
1635             current_state = end_states[bb.id].copy();
1636             current_state.allocateLiveness();
1637             current_state.initializeLastUses();
1638             current_bb = bb;
1639             i_end = bb.getEnd();
1640             BitStringIterator it = bytecode_start.backwardsIterator(i_end);
1641             while (it.hasNext()) {
1642                 i_start = it.nextIndex(); i_end = i_start-1;
1643                 this.visitBytecode();
1644                 if (i_start <= bb.getStart()) break;
1645             }
1646             if (current_state.compareLiveness(start_states[bb.id]))
1647                 go_again = true;
1648             start_states[bb.id] = current_state;
1649             for (int i=0; i<bb.getNumberOfPredecessors(); ++i) {
1650                 this.mergeStateWith(bb.getPredecessor(i));
1651             }
1652         }
1653         
1654         private boolean mergeStateWith(BasicBlock bb2) {
1655             if (end_states[bb2.id] == null) {
1656                 end_states[bb2.id] = current_state.copy();
1657                 return true;
1658             } else return end_states[bb2.id].mergeLiveness(current_state);
1659         }
1660         
1661         public void visitPEI() {
1662             ExceptionHandlerIterator ehi = current_bb.getExceptionHandlers();
1663             while (ehi.hasNext()) {
1664                 ExceptionHandler eh = ehi.nextEH();
1665                 BasicBlock bb2 = eh.getEntry();
1666                 if (start_states[bb2.id] == null) {
1667                     if (TRACE) out.println("No live var info for handler "+bb2+" yet");
1668                     continue;
1669                 }
1670                 if (TRACE) out.println("Merging current state "+current_state+" with live var info from handler "+bb2+": "+start_states[bb2.id]);
1671                 // merge call is the same as the normal one
1672                 if (current_state.mergeLiveness(start_states[bb2.id])) {
1673                     if (TRACE) out.println("Change in current state: "+current_state);
1674                 }
1675             }
1676         }
1677 
1678         public void visitILOAD(int i) {
1679             super.visitILOAD(i);
1680             current_state.liveLocal_I(i_start, i);
1681         }
1682         public void visitLLOAD(int i) {
1683             super.visitLLOAD(i);
1684             current_state.liveLocal_L(i_start, i);
1685         }
1686         public void visitFLOAD(int i) {
1687             super.visitFLOAD(i);
1688             current_state.liveLocal_F(i_start, i);
1689         }
1690         public void visitDLOAD(int i) {
1691             super.visitDLOAD(i);
1692             current_state.liveLocal_D(i_start, i);
1693         }
1694         public void visitALOAD(int i) {
1695             super.visitALOAD(i);
1696             current_state.liveLocal_A(i_start, i);
1697         }
1698         public void visitISTORE(int i) {
1699             super.visitISTORE(i);
1700             current_state.deadLocal_I(i);
1701         }
1702         public void visitLSTORE(int i) {
1703             super.visitLSTORE(i);
1704             current_state.deadLocal_L(i);
1705         }
1706         public void visitFSTORE(int i) {
1707             super.visitFSTORE(i);
1708             current_state.deadLocal_F(i);
1709         }
1710         public void visitDSTORE(int i) {
1711             super.visitDSTORE(i);
1712             current_state.deadLocal_D(i);
1713         }
1714         public void visitASTORE(int i) {
1715             super.visitASTORE(i);
1716             current_state.deadLocal_A(i);
1717         }
1718         
1719     }
1720 
1721 }