src/org/ibex/classgen/JSSA.java

   1 package org.ibex.classgen;
   2 import java.io.*;
   3 import java.util.*;
   4
   5 /**
   6  *  a highly streamlined SSA-form intermediate representation of a
   7  *  sequence of JVM instructions; all stack manipulation is factored
   8  *  out.
   9  */
  10 public class JSSA extends MethodGen implements CGConst {
  11
  12     // Constructor //////////////////////////////////////////////////////////////////////////////
  13
  14     public JSSA(Type.Class c, DataInput in, ConstantPool cp) throws IOException {
  15         super(c, in, cp);
  16         local = new Expr[maxLocals];
  17         stack = new Expr[maxStack];
  18         int n=0;
  19         if (!isStatic())
  20             local[n++] = new Argument("this",method.getDeclaringClass());
  21         for(int i=0;i<this.method.getNumArgs(); i++)
  22             local[n++] = new Argument("arg"+i, this.method.getArgType(i));
  23         for(int i=0; i<size(); i++) {
  24             int    op  = get(i);
  25             Object arg = getArg(i);
  26             try {
  27                 Object o = addOp(op, arg);
  28                 if (o != null) {
  29                     ops[numOps] = o;
  30                     ofs[numOps++] = i;
  31                 }
  32             } catch(RuntimeException e) {
  33                 System.err.println("Had a problem at PC: " + i + " of " + method);
  34                 e.printStackTrace();
  35                 throw new IOException("invalid class file");
  36             }
  37         }
  38     }
  39
  40     private Object[] ops = new Object[65535];
  41     private int[] ofs = new int[65535];
  42     private int numOps = 0;
  43
  44     // Instance Data; used ONLY during constructor; then thrown away /////////////////////////////////////////////////
  45
  46     /** this models the JVM locals; it is only used for unwinding stack-ops into an SSA-tree, then thrown away */
  47     private final Expr[] local;
  48
  49     /** this models the JVM stack; it is only used for unwinding stack-ops into an SSA-tree, then thrown away */
  50     private final Expr[] stack;
  51
  52     /** JVM stack pointer */
  53     private int sp = 0;
  54
  55     private Expr push(Expr e) {
  56         if(sp == stack.length) {
  57             for(int i=0;i<stack.length;i++) System.err.println("Stack " + i + ": " + stack[i]);
  58             throw new IllegalStateException("stack overflow (" + stack.length + ")");
  59         }
  60         if(e.getType() == Type.VOID) throw new IllegalArgumentException("can't push a void");
  61         return stack[sp++] = e;
  62     }
  63     private Expr pop() {
  64         if(sp == 0) throw new IllegalStateException("stack underflow");
  65         return stack[--sp];
  66     }
  67
  68     private Op seqPush(Expr e) {
  69         push(e);
  70         return new Seq(e);
  71     }
  72
  73
  74     // SSA-node classes /////////////////////////////////////////////////////////////////////////////////////////
  75
  76     public final Expr VOID_EXPR = new Expr() {
  77         public Type getType() { return Type.VOID; }
  78     };
  79
  80     /** an purely imperative operation which does not generate data */
  81     public abstract class Op {
  82         //public abstract Op[] predecessors();  // not implemented yet
  83         //public abstract Op[] successors();    // not implemented yet
  84         public String toString() { return name(); }
  85         String name() {
  86             String name = this.getClass().getName();
  87             if (name.indexOf('$') != -1) name = name.substring(name.lastIndexOf('$')+1);
  88             if (name.indexOf('.') != -1) name = name.substring(name.lastIndexOf('.')+1);
  89             return name;
  90         }
  91     }
  92
  93     /** A sequence point. expr is evaluated for side effects at this point, this does not generate data
  94         Expressions that haven't been evaluated with Seq are evaluated when they are first encountered
  95       */
  96     public class Seq extends Op {
  97         private final Expr expr;
  98         public String toString() { return expr.toString(); }
  99         public Seq(Expr expr) { this.expr = expr; }
 100     }
 101
 102     /** an operation which generates data */
 103     public abstract class Expr extends Op {
 104         //public abstract Expr[] contributors();  // not implemented yet
 105         //public abstract Expr[] dependents();    // not implemented yet
 106
 107         /** every JSSA.Expr either remembers its type _OR_ knows how to figure it out (the latter is preferred to eliminate
 108          *  redundant information that could possibly "disagree" with itself -- this happened a LOT in Soot) */
 109         public abstract Type getType();
 110
 111         public final String toString() { return exprToString(this); }
 112         public String _toString() { return super.toString(); } // Adam is going to hate me for this
 113     }
 114
 115     /**
 116      *  A "nondeterministic merge" -- for example when the first instruction in a loop reads from a local which could have been
 117      *  written to either by some instruction at the end of the previous iteration of the loop or by some instruction before
 118      *  the loop (on the first iteration).
 119      */
 120     public class Phi extends Expr {
 121         private final Expr[] inputs;
 122         public Phi(Expr[] inputs) {
 123             this.inputs = new Expr[inputs.length];
 124             System.arraycopy(inputs, 0, this.inputs, 0, inputs.length);
 125         }
 126         public Type getType() {
 127             // sanity check
 128             Type t = inputs[0].getType();
 129
 130             // FIXME: actually this should check type-unifiability... fe, the "type of null" unifies with any Type.Ref
 131             for(int i=1; i<inputs.length; i++)
 132                 if (inputs[i].getType() != t)
 133                     throw new Error("Phi node with disagreeing types!  Crisis!");
 134             return t;
 135         }
 136     }
 137
 138     public class Argument extends Expr {
 139         public final String name;
 140         public final Type t;
 141         public Argument(String name, Type t) { this.name = name; this.t = t; }
 142         public String _toString() { return name; }
 143         public Type getType() { return t; }
 144     }
 145
 146     // Unary Operations
 147     public class Not extends Expr {
 148         public final Expr e;
 149         public Not(Expr e) {
 150             if(e.getType() != Type.BOOLEAN) throw new IllegalArgumentException("not needs a boolean expression");
 151             this.e = e;
 152         }
 153         public Type getType() { return Type.BOOLEAN; }
 154         public String _toString() { return "!(" + e + ")"; }
 155     }
 156
 157     public class Neg extends Expr {
 158         public final Expr e;
 159         public Neg(Expr e) {
 160             if(!e.getType().isPrimitive()) throw new IllegalArgumentException("can only negate a primitive");
 161             this.e = e;
 162         }
 163         public Type getType() { return e.getType(); }
 164         public String _toString() { return "- (" + e + ")"; }
 165     }
 166
 167     // Binary Operations //////////////////////////////////////////////////////////////////////////////
 168
 169     public abstract class BinExpr extends Expr {
 170         public final Expr e1;
 171         public final Expr e2;
 172         private final String show;
 173         public BinExpr(Expr e1, Expr e2, String show) { this.e1 = e1; this.e2 = e2; this.show = show; }
 174         public String _toString() {
 175             // FEATURE: should we be doing some precedence stuff here? probably no worth it for debugging output
 176             return "(" + e1 + show + e2 + ")";
 177         }
 178     }
 179
 180     public class Comparison extends BinExpr {
 181         public Comparison(Expr e1, Expr e2, String show) { super(e1, e2, show); }
 182         public Type getType() { return Type.BOOLEAN; }
 183     }
 184
 185     public class Eq extends Comparison {
 186         public Eq(Expr e1, Expr e2) {
 187             super(e1, e2, "==");
 188             if(e1.getType().isPrimitive() != e2.getType().isPrimitive())
 189                 throw new IllegalArgumentException("type mismatch");
 190             if(e1.getType().isPrimitive() && e1.getType() != e2.getType())
 191                 throw new IllegalArgumentException("type mismatch");
 192             // FEATURE: Check if we can compare these classes
 193         }
 194     }
 195
 196
 197     public class PrimitiveComparison extends Comparison {
 198         public PrimitiveComparison(Expr e1, Expr e2, String show) {
 199             super(e1, e2, show);
 200             if(!e1.getType().isPrimitive() || e1.getType() != e2.getType()) throw new IllegalArgumentException("type mismatch");
 201         }
 202     }
 203
 204     public class Gt extends PrimitiveComparison { public Gt(Expr e1, Expr e2) { super(e1, e2, ">"); } }
 205     public class Lt extends PrimitiveComparison { public Lt(Expr e1, Expr e2) { super(e1, e2, "<"); } }
 206     public class Ge extends PrimitiveComparison { public Ge(Expr e1, Expr e2) { super(e1, e2, ">="); } }
 207     public class Le extends PrimitiveComparison { public Le(Expr e1, Expr e2) { super(e1, e2, "<="); } }
 208
 209     // Math Operations //////////////////////////////////////////////////////////////////////////////
 210
 211     public class BinMath extends BinExpr {
 212         public BinMath(Expr e1, Expr e2, String show) {
 213             super(e2, e1, show);
 214             if(e1.getType() != e2.getType()) throw new IllegalArgumentException("types disagree");
 215         }
 216         public Type getType() { return e1.getType(); }
 217     }
 218
 219     public class Add  extends BinMath { public  Add(Expr e, Expr e2) { super(e, e2, "+"); } }
 220     public class Sub  extends BinMath { public  Sub(Expr e, Expr e2) { super(e, e2, "-"); } }
 221     public class Mul  extends BinMath { public  Mul(Expr e, Expr e2) { super(e, e2, "*"); } }
 222     public class Rem  extends BinMath { public  Rem(Expr e, Expr e2) { super(e, e2, "%"); } }
 223     public class Div  extends BinMath { public  Div(Expr e, Expr e2) { super(e, e2, "/"); } }
 224     public class And  extends BinMath { public  And(Expr e, Expr e2) { super(e, e2, "&"); } }
 225     public class Or   extends BinMath { public   Or(Expr e, Expr e2) { super(e, e2, "|"); } }
 226     public class Xor  extends BinMath { public  Xor(Expr e, Expr e2) { super(e, e2, "^"); } }
 227
 228     public class BitShiftExpr extends BinExpr {
 229         public BitShiftExpr(Expr e1, Expr e2, String show) {
 230             super(e1,e2,show);
 231             Type t = e1.getType();
 232             if(t != Type.INT && t != Type.LONG) throw new IllegalArgumentException("type mismatch");
 233             if(e2.getType() != Type.INT) throw new IllegalArgumentException("type mismatch");
 234         }
 235         public Type getType() { return e1.getType(); }
 236     }
 237     public class Shl  extends BitShiftExpr { public  Shl(Expr e, Expr e2) { super(e, e2, "<<"); } }
 238     public class Shr  extends BitShiftExpr { public  Shr(Expr e, Expr e2) { super(e, e2, ">>"); } }
 239     public class Ushr extends BitShiftExpr { public Ushr(Expr e, Expr e2) { super(e, e2, ">>>"); } }
 240
 241     // Other operations //////////////////////////////////////////////////////////////////////////////
 242
 243     public class Cast extends Expr {
 244         final Expr e;
 245         final Type t;
 246         public Cast(Expr e, Type t) {
 247             if(e.getType().isRef() != t.isRef()) throw new IllegalArgumentException("invalid cast");
 248             // FEATURE: Check that one is a subclass of the other if it is a ref
 249             this.e = e;
 250             this.t = t;
 251         }
 252         public Type getType() { return t; }
 253     }
 254
 255     public class InstanceOf extends Expr {
 256         final Expr e;
 257         final Type.Ref t;
 258         public InstanceOf(Expr e, Type.Ref t) {
 259             if(!e.getType().isRef()) throw new IllegalArgumentException("can't do an instanceof check on a non-ref");
 260             this.e = e;
 261             this.t = t;
 262         }
 263         public Type getType() { return Type.BOOLEAN; }
 264     }
 265
 266     public class Throw extends Op {
 267         public final Expr e;
 268         public Throw(Expr e) {
 269             if(!e.getType().isRef()) throw new IllegalArgumentException("can't throw a non ref");
 270             // FEATURE: CHeck that it is a subclass of Throwable
 271             this.e = e;
 272         }
 273     }
 274
 275     public class Branch extends Op {
 276         public Branch(Expr condition, Object destination) { }
 277         public Branch(Label destination) { }
 278         public Branch(MethodGen.Switch s) { }
 279         public Branch() { }
 280     }
 281     public class Goto extends Branch { }
 282     public class RET extends Branch { }
 283     public class JSR extends Branch { public JSR(Label l) { super(l); } }
 284     public class If extends Branch { }
 285
 286     /** represents a "returnaddr" pushed onto the stack */
 287     public class Label extends Expr {
 288         public final Op op;
 289         public Type getType() { throw new Error("attempted to call getType() on a Label"); }
 290         public Label(Op op) { this.op = op; }
 291         public Label(int i) { this.op = null; /* FIXME */ }
 292     }
 293
 294     public class New extends Expr {
 295         public final Type.Class t;
 296         public Type getType() { return t; }
 297         public New(Type.Class t) { this.t = t; }
 298         public String _toString() { return "new " + t + "()"; }
 299     }
 300
 301     public class NewArray extends Expr {
 302         public final Type.Array t;
 303         public final Expr[] dims;
 304         public NewArray(Type.Array t, Expr[] dims) { this.t = t; this.dims = dims; }
 305         public NewArray(Type.Array t, Expr dim) { this(t,new Expr[]{dim}); }
 306         public Type getType() { return t; }
 307         public String _toString() {
 308             Type base = t;
 309             int totalDims = 0;
 310             while(base.isArray()) {
 311                 totalDims++;
 312                 base = base.asArray().getElementType();
 313             }
 314             StringBuffer sb = new StringBuffer("new " + base);
 315             for(int i=0;i<totalDims;i++)
 316                 sb.append("[" + (i < dims.length ? dims[i].toString() : "") + "]");
 317             return sb.toString();
 318         }
 319     }
 320
 321     public class Return extends Op {
 322         final Expr e;
 323         public Return() { this(VOID_EXPR); }
 324         public Return(Expr e) {
 325             this.e = e;
 326             if(Type.unify(method.getReturnType(),e.getType()) != method.getReturnType())
 327                throw new IllegalArgumentException("type mismatch");
 328         }
 329         public String toString() { return e.getType() == Type.VOID ? "return" : ("return "+e.toString()); }
 330     }
 331
 332     /** GETFIELD and GETSTATIC */
 333     public class Get extends Expr {
 334         final Type.Class.Field f;
 335         final Expr e;
 336         public Type getType() { return f.getType(); }
 337         public Get(Type.Class.Field f) { this(f, null); }
 338         public Get(Type.Class.Field f, Expr e) { this.f = f; this.e = e; }
 339         public String _toString() {
 340             return
 341                 (e!=null
 342                  ? e+"."+f.name
 343                  : f.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
 344                  ? f.name
 345                  : f.toString());
 346         }
 347     }
 348
 349     /** PUTFIELD and PUTSTATIC */
 350     public class Put extends Op {
 351         final Type.Class.Field f;
 352         final Expr v;
 353         final Expr e;
 354         public Put(Type.Class.Field f, Expr v) { this(f, v, null); }
 355         public Put(Type.Class.Field f, Expr v, Expr e) { this.f = f; this.v = v; this.e = e; }
 356         public String toString() {
 357             return
 358                 (e!=null
 359                  ? e+"."+f.name
 360                  : f.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
 361                  ? f.name
 362                  : f.toString()) + " = " + v;
 363         }
 364     }
 365
 366     public class ArrayPut extends Op {
 367         final Expr e, i, v;
 368         public ArrayPut(Expr v, Expr i, Expr e) { this.e = e; this.i = i; this.v = v; }
 369         public String toString() { return e + "[" + i + "] := " + v; }
 370     }
 371
 372     public class ArrayGet extends Expr {
 373         final Expr e, i;
 374         public ArrayGet(Expr i, Expr e) { this.e = e; this.i = i; }
 375         public Type getType() { return e.getType().asArray().getElementType(); }
 376         public String _toString() { return e + "[" + i + "]"; }
 377     }
 378
 379     public class ArrayLength extends Expr {
 380         final Expr e;
 381         public ArrayLength(Expr e) { this.e = e; }
 382         public Type getType() { return Type.INT; }
 383     }
 384
 385     public abstract class Invoke extends Expr {
 386         public final Expr[] arguments;
 387         public final Type.Class.Method method;
 388         protected Invoke(Type.Class.Method m, Expr[] a) { this.arguments = a; this.method = m; }
 389
 390         public Type getType() { return method.getReturnType(); }
 391         protected void args(StringBuffer sb) {
 392             sb.append("(");
 393             for(int i=0; i<arguments.length; i++) {
 394                 if (i>0) sb.append(", ");
 395                 sb.append(arguments[i]+"");
 396             }
 397             sb.append(")");
 398         }
 399
 400         public String _toString() {
 401             StringBuffer sb = new StringBuffer();
 402             sb.append(method.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
 403                       ? method.name
 404                       : (method.getDeclaringClass() + "." + method.name));
 405             args(sb);
 406             return sb.toString();
 407         }
 408     }
 409     public class InvokeStatic    extends Invoke  { public InvokeStatic(Type.Class.Method m, Expr[] a) { super(m,a); } }
 410     public class InvokeSpecial   extends InvokeVirtual {
 411         public InvokeSpecial(Type.Class.Method m, Expr[] a, Expr e) { super(m,a,e); }
 412         public String _toString() { return _toString(method.name.equals("<init>") ? method.getDeclaringClass().getName() : method.name); }
 413     }
 414     public class InvokeInterface extends InvokeVirtual{public InvokeInterface(Type.Class.Method m, Expr[] a, Expr e){super(m,a,e);}}
 415     public class InvokeVirtual   extends Invoke  {
 416         public final Expr instance;
 417         public InvokeVirtual(Type.Class.Method m, Expr[] a, Expr e) { super(m, a); instance = e; }
 418         public String _toString() { return _toString(method.name); }
 419         protected String _toString(String name) {
 420             StringBuffer sb = new StringBuffer();
 421             sb.append(instance+".");
 422             sb.append(name);
 423             args(sb);
 424             return sb.toString();
 425         }
 426     }
 427
 428     public class Constant extends Expr {
 429         private final Object o;
 430         public Constant(int i) { this(new Integer(i)); }
 431         public Constant(Object o) { this.o = o; }
 432         public String _toString() { return o == null ? "null" : o instanceof String ? "\"" + o + "\"" : o.toString(); }
 433         public Type getType() {
 434             if (o == null) return Type.NULL;
 435             if (o instanceof Byte) return Type.BYTE;
 436             if (o instanceof Short) return Type.SHORT;
 437             if (o instanceof Character) return Type.CHAR;
 438             if (o instanceof Boolean) return Type.BOOLEAN;
 439             if (o instanceof Long) return Type.LONG;
 440             if (o instanceof Double) return Type.DOUBLE;
 441             if (o instanceof Float) return Type.FLOAT;
 442             if (o instanceof Integer) return Type.INT;
 443             if (o instanceof String) return Type.STRING;
 444             throw new IllegalStateException("unknown constant type");
 445         }
 446     }
 447
 448
 449     // Implementation //////////////////////////////////////////////////////////////////////////////
 450
 451     private Object addOp(int op, Object arg) {
 452         int i1 = 0;
 453         int i2 = 0;
 454         if (op==WIDE) {
 455             MethodGen.Wide w = (MethodGen.Wide)arg;
 456             op = w.op;
 457             arg = null;
 458             i1 = w.varNum;
 459             i2 = w.n;
 460         }
 461         if (op==IINC) {
 462             MethodGen.Pair p = (MethodGen.Pair)arg;
 463             arg = null;
 464             i1 = p.i1;
 465             i2 = p.i2;
 466         }
 467         switch(op) {
 468
 469             case NOP: return null;
 470
 471                 // Stack manipulations //////////////////////////////////////////////////////////////////////////////
 472
 473             case ACONST_NULL:                                                      push(new Constant(null)); return null;
 474             case ICONST_M1:                                                        push(new Constant(-1)); return null;
 475             case ICONST_0: case LCONST_0: case FCONST_0: case DCONST_0:            push(new Constant(0)); return null;
 476             case ICONST_1: case LCONST_1: case FCONST_1: case DCONST_1:            push(new Constant(1)); return null;
 477             case ICONST_2: case FCONST_2:                                          push(new Constant(2)); return null;
 478             case ICONST_3:                                                         push(new Constant(3)); return null;
 479             case ICONST_4:                                                         push(new Constant(4)); return null;
 480             case ICONST_5:                                                         push(new Constant(5)); return null;
 481             case ILOAD:    case LLOAD:    case FLOAD:    case DLOAD:    case ALOAD:    push(local[i1]); return null;
 482             case ILOAD_0:  case LLOAD_0:  case FLOAD_0:  case DLOAD_0:  case ALOAD_0:  push(local[0]); return null;
 483             case ILOAD_1:  case LLOAD_1:  case FLOAD_1:  case DLOAD_1:  case ALOAD_1:  push(local[1]); return null;
 484             case ALOAD_2:  case DLOAD_2:  case FLOAD_2:  case LLOAD_2:  case ILOAD_2:  push(local[2]); return null;
 485             case ILOAD_3:  case LLOAD_3:  case FLOAD_3:  case DLOAD_3:  case ALOAD_3:  push(local[3]); return null;
 486             case ISTORE:   case LSTORE:   case FSTORE:   case DSTORE:   case ASTORE:   local[i1] = pop(); return null;
 487             case ISTORE_0: case LSTORE_0: case FSTORE_0: case DSTORE_0: case ASTORE_0: local[0]  = pop(); return null;
 488             case ISTORE_1: case LSTORE_1: case FSTORE_1: case DSTORE_1: case ASTORE_1: local[1]  = pop(); return null;
 489             case ASTORE_2: case DSTORE_2: case FSTORE_2: case LSTORE_2: case ISTORE_2: local[2]  = pop(); return null;
 490             case ISTORE_3: case LSTORE_3: case FSTORE_3: case DSTORE_3: case ASTORE_3: local[3]  = pop(); return null;
 491             case POP:      pop(); return null;
 492             case POP2:     pop(); pop(); return null;
 493             case DUP:      push(stack[sp-1]); return null;
 494             case DUP2:     push(stack[sp-2]); push(stack[sp-2]); return null;
 495
 496                 // Conversions //////////////////////////////////////////////////////////////////////////////
 497
 498                 // coercions are added as-needed when converting from JSSA back to bytecode, so we can
 499                 // simply discard them here (assuming the bytecode we're reading in was valid in the first place)
 500
 501             case I2L: case F2L: case D2L:               push(new Cast(pop(), Type.LONG)); return null;
 502             case I2F: case L2F: case D2F:               push(new Cast(pop(), Type.FLOAT)); return null;
 503             case I2D: case L2D: case F2D:               push(new Cast(pop(), Type.DOUBLE)); return null;
 504             case L2I: case F2I: case D2I:               push(new Cast(pop(), Type.INT)); return null;
 505             case I2B:                                   push(new Cast(pop(), Type.BYTE)); return null;
 506             case I2C:                                   push(new Cast(pop(), Type.CHAR)); return null;
 507             case I2S:                                   push(new Cast(pop(), Type.SHORT)); return null;
 508             case SWAP:                                  { Expr e1 = pop(), e2 = pop(); push(e2);  push(e1); return null; }
 509
 510                 // Math //////////////////////////////////////////////////////////////////////////////
 511
 512             case IADD: case LADD: case FADD: case DADD: push(new Add(pop(), pop())); return null;
 513             case ISUB: case LSUB: case FSUB: case DSUB: push(new Sub(pop(), pop())); return null;
 514             case IMUL: case LMUL: case FMUL: case DMUL: push(new Mul(pop(), pop())); return null;
 515             case IREM: case LREM: case FREM: case DREM: push(new Rem(pop(), pop())); return null;
 516                 //case INEG: case LNEG: case FNEG: case DNEG: push(new Neg(pop())); return null;
 517             case IDIV: case LDIV: case FDIV: case DDIV: push(new Div(pop(), pop())); return null;
 518             case ISHL: case LSHL:                       push(new Shl(pop(), pop())); return null;
 519             case ISHR: case LSHR:                       push(new Shr(pop(), pop())); return null;
 520             case IUSHR: case LUSHR:                     push(new Ushr(pop(), pop())); return null;
 521             case IAND: case LAND:                       push(new And(pop(), pop())); return null;
 522             case IOR:  case LOR:                        push(new Or(pop(), pop())); return null;
 523             case IXOR: case LXOR:                       push(new Xor(pop(), pop())); return null;
 524             case IINC:                                  return local[i1] = new Add(local[i1], new Constant(i2));
 525
 526                 // Control and branching //////////////////////////////////////////////////////////////////////////////
 527
 528             case IFNULL:                                return new Branch(new Eq(pop(), new Constant(null)), new Label(i1));
 529             case IFNONNULL:                             return new Branch(new Not(new Eq(pop(),new Constant(null))),new Label(i1));
 530             case IFEQ:                                  return new Branch(    new Eq(new Constant(0), pop()),  arg);
 531             case IFNE:                                  return new Branch(new Not(new Eq(new Constant(0), pop())), arg);
 532             case IFLT:                                  return new Branch(    new Lt(new Constant(0), pop()),  arg);
 533             case IFGE:                                  return new Branch(new Not(new Lt(new Constant(0), pop())), arg);
 534             case IFGT:                                  return new Branch(    new Gt(new Constant(0), pop()),  arg);
 535             case IFLE:                                  return new Branch(new Not(new Gt(new Constant(0), pop())), arg);
 536             case IF_ICMPEQ:                             return new Branch(    new Eq(pop(), pop()),  arg);
 537             case IF_ICMPNE:                             return new Branch(new Not(new Eq(pop(), pop())), arg);
 538             case IF_ICMPLT:                             return new Branch(    new Lt(pop(), pop()),  arg);
 539             case IF_ICMPGE:                             return new Branch(new Not(new Lt(pop(), pop())), arg);
 540             case IF_ICMPGT:                             return new Branch(    new Gt(pop(), pop()),  arg);
 541             case IF_ICMPLE:                             return new Branch(new Not(new Gt(pop(), pop())), arg);
 542             case IF_ACMPEQ:                             return new Branch(    new Eq(pop(), pop()),  arg);
 543             case IF_ACMPNE:                             return new Branch(new Not(new Eq(pop(), pop())), arg);
 544             case ATHROW:                                return new Throw(pop());
 545             case GOTO:                                  return new Branch(new Label(i1));
 546             case JSR:                                   return new JSR(new Label(i1));
 547             case RET:                                   return new RET();
 548             case RETURN:                                return new Return();
 549             case IRETURN: case LRETURN: case FRETURN: case DRETURN: case ARETURN:
 550                 return new Return(pop());
 551
 552                 // Array manipulations //////////////////////////////////////////////////////////////////////////////
 553
 554             case IALOAD:  case LALOAD:  case FALOAD:  case DALOAD:  case AALOAD:
 555             case BALOAD:  case CALOAD:  case SALOAD:
 556                 return seqPush(new ArrayGet(pop(), pop()));
 557             case IASTORE: case LASTORE: case FASTORE: case DASTORE: case AASTORE:
 558             case BASTORE: case CASTORE: case SASTORE:
 559                 return new ArrayPut(pop(), pop(), pop());
 560
 561                 // Invocation //////////////////////////////////////////////////////////////////////////////
 562
 563             case INVOKEVIRTUAL: case INVOKESPECIAL: case INVOKESTATIC: case INVOKEINTERFACE: {
 564                 Type.Class.Method method = (Type.Class.Method)arg;
 565                 Expr args[] = new Expr[method.getNumArgs()];
 566                 for(int i=0; i<args.length; i++) args[args.length-i-1] = pop();
 567                 Expr ret;
 568                 switch(op) {
 569                     case INVOKEVIRTUAL:   ret = new InvokeVirtual(method, args, pop()); break;
 570                     case INVOKEINTERFACE: ret = new InvokeInterface(method, args, pop()); break;
 571                     case INVOKESPECIAL:   ret = new InvokeSpecial(method, args, pop()); break;
 572                     case INVOKESTATIC:    ret = new InvokeStatic(method, args); break;
 573                     default: throw new Error("should never happen");
 574                 }
 575                 if(ret.getType() != Type.VOID) push(ret);
 576                 return new Seq(ret);
 577             }
 578
 579                 // Field Access //////////////////////////////////////////////////////////////////////////////
 580
 581             case GETSTATIC:         return seqPush(new Get((Type.Class.Field)arg, null));
 582             case PUTSTATIC:         return new Put((Type.Class.Field)arg, pop(), null);
 583             case GETFIELD:          return seqPush(new Get((Type.Class.Field)arg, pop()));
 584             case PUTFIELD:          return new Put((Type.Class.Field)arg, pop(), pop());
 585
 586                 // Allocation //////////////////////////////////////////////////////////////////////////////
 587
 588             case NEW:               push(new New((Type.Class)arg)); return null;
 589             case NEWARRAY: {
 590                 Type base;
 591                 switch(((Integer)arg).intValue()) {
 592                     case 4: base = Type.BOOLEAN; break;
 593                     case 5: base = Type.CHAR; break;
 594                     case 6: base = Type.FLOAT; break;
 595                     case 7: base = Type.DOUBLE; break;
 596                     case 8: base = Type.BYTE; break;
 597                     case 9: base = Type.SHORT; break;
 598                     case 10: base = Type.INT; break;
 599                     case 11: base = Type.LONG; break;
 600                     default: throw new IllegalStateException("invalid array type");
 601                 }
 602                 return seqPush(new NewArray(base.makeArray(),pop()));
 603             }
 604             case ANEWARRAY:         push(new NewArray(((Type.Ref)arg).makeArray(), pop())); return null;
 605             case MULTIANEWARRAY: {
 606                 MethodGen.MultiANewArray mana = (MethodGen.MultiANewArray) arg;
 607                 Expr[] dims = new Expr[mana.dims];
 608                 for(int i=0;i<dims.length;i++) dims[i] = pop();
 609                 return seqPush(new NewArray(mana.type, dims));
 610             }
 611             case ARRAYLENGTH:       return seqPush(new ArrayLength(pop()));
 612
 613                 // Runtime Type information //////////////////////////////////////////////////////////////////////////////
 614
 615             case CHECKCAST:         return seqPush(new Cast(pop(), (Type.Ref)arg));
 616             case INSTANCEOF:        push(new InstanceOf(pop(), (Type.Ref)arg)); return null;
 617
 618             case LDC: case LDC_W: case LDC2_W: push(new Constant(arg)); return null;
 619
 620             case BIPUSH:    push(new Constant((Integer)arg)); return null;
 621             case SIPUSH:    push(new Constant((Integer)arg)); return null;
 622
 623             case TABLESWITCH:    return new Branch((MethodGen.Switch)arg);
 624             case LOOKUPSWITCH:   return new Branch((MethodGen.Switch)arg);
 625
 626                 /*
 627             case MONITORENTER:   Op.monitorEnter(pop());
 628             case MONITOREXIT:    Op.monitorExit(pop());
 629                 */
 630
 631             case DUP_X1:         throw new Error("unimplemented");
 632             case DUP_X2:         throw new Error("unimplemented");
 633             case DUP2_X1:         throw new Error("unimplemented");
 634             case DUP2_X2:         throw new Error("unimplemented");
 635             case LCMP:         throw new Error("unimplemented");
 636             case FCMPL:         throw new Error("unimplemented");
 637             case FCMPG:         throw new Error("unimplemented");
 638             case DCMPL:         throw new Error("unimplemented");
 639             case DCMPG:         throw new Error("unimplemented");
 640             case GOTO_W:         throw new Error("unimplemented");
 641             case JSR_W:         throw new Error("unimplemented");
 642             default:          throw new Error("unhandled");
 643         }
 644     }
 645
 646
 647     public void debugBodyToString(StringBuffer sb) {
 648         StringBuffer sb0 = new StringBuffer();
 649         super.debugBodyToString(sb0);
 650         StringTokenizer st = new StringTokenizer(sb0.toString(), "\n");
 651         String[] lines = new String[st.countTokens()];
 652         for(int i=0; i<lines.length; i++) lines[i] = st.nextToken();
 653         for(int j=0; j<ofs[0]; j++) {
 654             String s = "    /* " + lines[j].trim();
 655              while(s.length() < 50) s += " ";
 656              s += " */";
 657              sb.append(s);
 658              sb.append("\n");
 659         }
 660
 661         bindingMap = new IdentityHashMap();
 662         nextVar = 0;
 663
 664         for(int i=0; i<numOps; i++) {
 665             String s = "    /* " + lines[ofs[i]].trim();
 666              while(s.length() < 50) s += " ";
 667              s += " */  ";
 668              s += ops[i].toString();
 669              sb.append(s);
 670              sb.append(";\n");
 671              for(int j=ofs[i]+1; j<(i==numOps-1?size():ofs[i+1]); j++) {
 672                  s = "    /* " + lines[j].trim();
 673                   while(s.length() < 50) s += " ";
 674                   s += " */";
 675                   sb.append(s);
 676                   sb.append("\n");
 677              }
 678         }
 679     }
 680
 681     private Map bindingMap;
 682     private int nextVar;
 683     String exprToString(Expr e) {
 684         if(e instanceof Constant) return e._toString();
 685         String s = (String)bindingMap.get(e);
 686         if(s != null) return s;
 687         String prefix;
 688         if(e.getType() == Type.VOID) return e._toString();
 689         else if(e.getType() == Type.DOUBLE || e.getType() == Type.FLOAT) prefix = "f";
 690         else if(e.getType().isPrimitive()) prefix = "i";
 691         else if(e.getType().isArray()) prefix = "a";
 692         else prefix = "o";
 693         s = prefix + (nextVar++);
 694         bindingMap.put(e,s);
 695         return "(" + s + " = " + e._toString() + ")";
 696     }
 697
 698     public static void main(String[] args) throws Exception {
 699         InputStream is = Class.forName(args[0]).getClassLoader().getResourceAsStream(args[0].replace('.', '/')+".class");
 700         System.out.println(new ClassFile(new DataInputStream(is), true).toString());
 701     }
 702 }