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) { this.e = e; }
 325         public String toString() { return e.getType() == Type.VOID ? "return" : ("return "+e.toString()); }
 326     }
 327
 328     /** GETFIELD and GETSTATIC */
 329     public class Get extends Expr {
 330         final Type.Class.Field f;
 331         final Expr e;
 332         public Type getType() { return f.getType(); }
 333         public Get(Type.Class.Field f) { this(f, null); }
 334         public Get(Type.Class.Field f, Expr e) { this.f = f; this.e = e; }
 335         public String _toString() {
 336             return
 337                 (e!=null
 338                  ? e+"."+f.name
 339                  : f.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
 340                  ? f.name
 341                  : f.toString());
 342         }
 343     }
 344
 345     /** PUTFIELD and PUTSTATIC */
 346     public class Put extends Op {
 347         final Type.Class.Field f;
 348         final Expr v;
 349         final Expr e;
 350         public Put(Type.Class.Field f, Expr v) { this(f, v, null); }
 351         public Put(Type.Class.Field f, Expr v, Expr e) { this.f = f; this.v = v; this.e = e; }
 352         public String toString() {
 353             return
 354                 (e!=null
 355                  ? e+"."+f.name
 356                  : f.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
 357                  ? f.name
 358                  : f.toString()) + " = " + v;
 359         }
 360     }
 361
 362     public class ArrayPut extends Op {
 363         final Expr e, i, v;
 364         public ArrayPut(Expr v, Expr i, Expr e) { this.e = e; this.i = i; this.v = v; }
 365         public String toString() { return e + "[" + i + "] := " + v; }
 366     }
 367
 368     public class ArrayGet extends Expr {
 369         final Expr e, i;
 370         public ArrayGet(Expr i, Expr e) { this.e = e; this.i = i; }
 371         public Type getType() { return e.getType().asArray().getElementType(); }
 372         public String _toString() { return e + "[" + i + "]"; }
 373     }
 374
 375     public class ArrayLength extends Expr {
 376         final Expr e;
 377         public ArrayLength(Expr e) { this.e = e; }
 378         public Type getType() { return Type.INT; }
 379     }
 380
 381     public abstract class Invoke extends Expr {
 382         public final Expr[] arguments;
 383         public final Type.Class.Method method;
 384         protected Invoke(Type.Class.Method m, Expr[] a) { this.arguments = a; this.method = m; }
 385
 386         public Type getType() { return method.getReturnType(); }
 387         protected void args(StringBuffer sb) {
 388             sb.append("(");
 389             for(int i=0; i<arguments.length; i++) {
 390                 if (i>0) sb.append(", ");
 391                 sb.append(arguments[i]+"");
 392             }
 393             sb.append(")");
 394         }
 395
 396         public String _toString() {
 397             StringBuffer sb = new StringBuffer();
 398             sb.append(method.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
 399                       ? method.name
 400                       : (method.getDeclaringClass() + "." + method.name));
 401             args(sb);
 402             return sb.toString();
 403         }
 404     }
 405     public class InvokeStatic    extends Invoke  { public InvokeStatic(Type.Class.Method m, Expr[] a) { super(m,a); } }
 406     public class InvokeSpecial   extends InvokeVirtual {
 407         public InvokeSpecial(Type.Class.Method m, Expr[] a, Expr e) { super(m,a,e); }
 408         public String _toString() { return _toString(method.name.equals("<init>") ? method.getDeclaringClass().getName() : method.name); }
 409     }
 410     public class InvokeInterface extends InvokeVirtual{public InvokeInterface(Type.Class.Method m, Expr[] a, Expr e){super(m,a,e);}}
 411     public class InvokeVirtual   extends Invoke  {
 412         public final Expr instance;
 413         public InvokeVirtual(Type.Class.Method m, Expr[] a, Expr e) { super(m, a); instance = e; }
 414         public String _toString() { return _toString(method.name); }
 415         protected String _toString(String name) {
 416             StringBuffer sb = new StringBuffer();
 417             sb.append(instance+".");
 418             sb.append(name);
 419             args(sb);
 420             return sb.toString();
 421         }
 422     }
 423
 424     public class Constant extends Expr {
 425         private final Object o;
 426         public Constant(int i) { this(new Integer(i)); }
 427         public Constant(Object o) { this.o = o; }
 428         public String _toString() { return o instanceof String ? "\"" + o + "\"" : o.toString(); }
 429         public Type getType() {
 430             if (o instanceof Byte) return Type.BYTE;
 431             if (o instanceof Short) return Type.SHORT;
 432             if (o instanceof Character) return Type.CHAR;
 433             if (o instanceof Boolean) return Type.BOOLEAN;
 434             if (o instanceof Long) return Type.LONG;
 435             if (o instanceof Double) return Type.DOUBLE;
 436             if (o instanceof Float) return Type.FLOAT;
 437             if (o instanceof Integer) return Type.INT;
 438             if (o instanceof String) return Type.STRING;
 439             throw new IllegalStateException("unknown constant type");
 440         }
 441     }
 442
 443
 444     // Implementation //////////////////////////////////////////////////////////////////////////////
 445
 446     private Object addOp(int op, Object arg) {
 447         int i1 = 0;
 448         int i2 = 0;
 449         if (op==WIDE) {
 450             MethodGen.Wide w = (MethodGen.Wide)arg;
 451             op = w.op;
 452             arg = null;
 453             i1 = w.varNum;
 454             i2 = w.n;
 455         }
 456         if (op==IINC) {
 457             MethodGen.Pair p = (MethodGen.Pair)arg;
 458             arg = null;
 459             i1 = p.i1;
 460             i2 = p.i2;
 461         }
 462         switch(op) {
 463
 464             case NOP: return null;
 465
 466                 // Stack manipulations //////////////////////////////////////////////////////////////////////////////
 467
 468             case ACONST_NULL:                                                      return stack[sp++] = new Constant(null);
 469             case ICONST_M1:                                                        return stack[sp++] = new Constant(-1);
 470             case ICONST_0: case LCONST_0: case FCONST_0: case DCONST_0:            push(new Constant(0)); return null;
 471             case ICONST_1: case LCONST_1: case FCONST_1: case DCONST_1:            push(new Constant(1)); return null;
 472             case ICONST_2: case FCONST_2:                                          push(new Constant(2)); return null;
 473             case ICONST_3:                                                         push(new Constant(3)); return null;
 474             case ICONST_4:                                                         push(new Constant(4)); return null;
 475             case ICONST_5:                                                         push(new Constant(5)); return null;
 476             case ILOAD:    case LLOAD:    case FLOAD:    case DLOAD:    case ALOAD:    push(local[i1]); return null;
 477             case ILOAD_0:  case LLOAD_0:  case FLOAD_0:  case DLOAD_0:  case ALOAD_0:  push(local[0]); return null;
 478             case ILOAD_1:  case LLOAD_1:  case FLOAD_1:  case DLOAD_1:  case ALOAD_1:  push(local[1]); return null;
 479             case ALOAD_2:  case DLOAD_2:  case FLOAD_2:  case LLOAD_2:  case ILOAD_2:  push(local[2]); return null;
 480             case ILOAD_3:  case LLOAD_3:  case FLOAD_3:  case DLOAD_3:  case ALOAD_3:  push(local[3]); return null;
 481             case ISTORE:   case LSTORE:   case FSTORE:   case DSTORE:   case ASTORE:   local[i1] = pop(); return null;
 482             case ISTORE_0: case LSTORE_0: case FSTORE_0: case DSTORE_0: case ASTORE_0: local[0]  = pop(); return null;
 483             case ISTORE_1: case LSTORE_1: case FSTORE_1: case DSTORE_1: case ASTORE_1: local[1]  = pop(); return null;
 484             case ASTORE_2: case DSTORE_2: case FSTORE_2: case LSTORE_2: case ISTORE_2: local[2]  = pop(); return null;
 485             case ISTORE_3: case LSTORE_3: case FSTORE_3: case DSTORE_3: case ASTORE_3: local[3]  = pop(); return null;
 486             case POP:      pop(); return null;
 487             case POP2:     pop(); pop(); return null;
 488             case DUP:      push(stack[sp-1]); return null;
 489             case DUP2:     push(stack[sp-2]); push(stack[sp-2]); return null;
 490
 491                 // Conversions //////////////////////////////////////////////////////////////////////////////
 492
 493                 // coercions are added as-needed when converting from JSSA back to bytecode, so we can
 494                 // simply discard them here (assuming the bytecode we're reading in was valid in the first place)
 495
 496             case I2L: case F2L: case D2L:               push(new Cast(pop(), Type.LONG)); return null;
 497             case I2F: case L2F: case D2F:               push(new Cast(pop(), Type.FLOAT)); return null;
 498             case I2D: case L2D: case F2D:               push(new Cast(pop(), Type.DOUBLE)); return null;
 499             case L2I: case F2I: case D2I:               push(new Cast(pop(), Type.INT)); return null;
 500             case I2B:                                   push(new Cast(pop(), Type.BYTE)); return null;
 501             case I2C:                                   push(new Cast(pop(), Type.CHAR)); return null;
 502             case I2S:                                   push(new Cast(pop(), Type.SHORT)); return null;
 503             case SWAP:                                  { Expr e1 = pop(), e2 = pop(); push(e2);  push(e1); return null; }
 504
 505                 // Math //////////////////////////////////////////////////////////////////////////////
 506
 507             case IADD: case LADD: case FADD: case DADD: push(new Add(pop(), pop())); return null;
 508             case ISUB: case LSUB: case FSUB: case DSUB: push(new Sub(pop(), pop())); return null;
 509             case IMUL: case LMUL: case FMUL: case DMUL: push(new Mul(pop(), pop())); return null;
 510             case IREM: case LREM: case FREM: case DREM: push(new Rem(pop(), pop())); return null;
 511                 //case INEG: case LNEG: case FNEG: case DNEG: push(new Neg(pop())); return null;
 512             case IDIV: case LDIV: case FDIV: case DDIV: push(new Div(pop(), pop())); return null;
 513             case ISHL: case LSHL:                       push(new Shl(pop(), pop())); return null;
 514             case ISHR: case LSHR:                       push(new Shr(pop(), pop())); return null;
 515             case IUSHR: case LUSHR:                     push(new Ushr(pop(), pop())); return null;
 516             case IAND: case LAND:                       push(new And(pop(), pop())); return null;
 517             case IOR:  case LOR:                        push(new Or(pop(), pop())); return null;
 518             case IXOR: case LXOR:                       push(new Xor(pop(), pop())); return null;
 519             case IINC:                                  return local[i1] = new Add(local[i1], new Constant(i2));
 520
 521                 // Control and branching //////////////////////////////////////////////////////////////////////////////
 522
 523             case IFNULL:                                return new Branch(new Eq(pop(), new Constant(null)), new Label(i1));
 524             case IFNONNULL:                             return new Branch(new Not(new Eq(pop(),new Constant(null))),new Label(i1));
 525             case IFEQ:                                  return new Branch(    new Eq(new Constant(0), pop()),  arg);
 526             case IFNE:                                  return new Branch(new Not(new Eq(new Constant(0), pop())), arg);
 527             case IFLT:                                  return new Branch(    new Lt(new Constant(0), pop()),  arg);
 528             case IFGE:                                  return new Branch(new Not(new Lt(new Constant(0), pop())), arg);
 529             case IFGT:                                  return new Branch(    new Gt(new Constant(0), pop()),  arg);
 530             case IFLE:                                  return new Branch(new Not(new Gt(new Constant(0), pop())), arg);
 531             case IF_ICMPEQ:                             return new Branch(    new Eq(pop(), pop()),  arg);
 532             case IF_ICMPNE:                             return new Branch(new Not(new Eq(pop(), pop())), arg);
 533             case IF_ICMPLT:                             return new Branch(    new Lt(pop(), pop()),  arg);
 534             case IF_ICMPGE:                             return new Branch(new Not(new Lt(pop(), pop())), arg);
 535             case IF_ICMPGT:                             return new Branch(    new Gt(pop(), pop()),  arg);
 536             case IF_ICMPLE:                             return new Branch(new Not(new Gt(pop(), pop())), arg);
 537             case IF_ACMPEQ:                             return new Branch(    new Eq(pop(), pop()),  arg);
 538             case IF_ACMPNE:                             return new Branch(new Not(new Eq(pop(), pop())), arg);
 539             case ATHROW:                                return new Throw(pop());
 540             case GOTO:                                  return new Branch(new Label(i1));
 541             case JSR:                                   return new JSR(new Label(i1));
 542             case RET:                                   return new RET();
 543             case RETURN:                                return new Return();
 544             case IRETURN: case LRETURN: case FRETURN: case DRETURN: case ARETURN:
 545                 return new Return(pop());
 546
 547                 // Array manipulations //////////////////////////////////////////////////////////////////////////////
 548
 549             case IALOAD:  case LALOAD:  case FALOAD:  case DALOAD:  case AALOAD:
 550             case BALOAD:  case CALOAD:  case SALOAD:
 551                 return seqPush(new ArrayGet(pop(), pop()));
 552             case IASTORE: case LASTORE: case FASTORE: case DASTORE: case AASTORE:
 553             case BASTORE: case CASTORE: case SASTORE:
 554                 return new ArrayPut(pop(), pop(), pop());
 555
 556                 // Invocation //////////////////////////////////////////////////////////////////////////////
 557
 558             case INVOKEVIRTUAL: case INVOKESPECIAL: case INVOKESTATIC: case INVOKEINTERFACE: {
 559                 Type.Class.Method method = (Type.Class.Method)arg;
 560                 Expr args[] = new Expr[method.getNumArgs()];
 561                 for(int i=0; i<args.length; i++) args[args.length-i-1] = pop();
 562                 Expr ret;
 563                 switch(op) {
 564                     case INVOKEVIRTUAL:   ret = new InvokeVirtual(method, args, pop()); break;
 565                     case INVOKEINTERFACE: ret = new InvokeInterface(method, args, pop()); break;
 566                     case INVOKESPECIAL:   ret = new InvokeSpecial(method, args, pop()); break;
 567                     case INVOKESTATIC:    ret = new InvokeStatic(method, args); break;
 568                     default: throw new Error("should never happen");
 569                 }
 570                 if(ret.getType() != Type.VOID) push(ret);
 571                 return new Seq(ret);
 572             }
 573
 574                 // Field Access //////////////////////////////////////////////////////////////////////////////
 575
 576             case GETSTATIC:         return seqPush(new Get((Type.Class.Field)arg, null));
 577             case PUTSTATIC:         return new Put((Type.Class.Field)arg, pop(), null);
 578             case GETFIELD:          return seqPush(new Get((Type.Class.Field)arg, pop()));
 579             case PUTFIELD:          return new Put((Type.Class.Field)arg, pop(), pop());
 580
 581                 // Allocation //////////////////////////////////////////////////////////////////////////////
 582
 583             case NEW:               push(new New((Type.Class)arg)); return null;
 584             case NEWARRAY: {
 585                 Type base;
 586                 switch(((Integer)arg).intValue()) {
 587                     case 4: base = Type.BOOLEAN; break;
 588                     case 5: base = Type.CHAR; break;
 589                     case 6: base = Type.FLOAT; break;
 590                     case 7: base = Type.DOUBLE; break;
 591                     case 8: base = Type.BYTE; break;
 592                     case 9: base = Type.SHORT; break;
 593                     case 10: base = Type.INT; break;
 594                     case 11: base = Type.LONG; break;
 595                     default: throw new IllegalStateException("invalid array type");
 596                 }
 597                 return seqPush(new NewArray(base.makeArray(),pop()));
 598             }
 599             case ANEWARRAY:         push(new NewArray(((Type.Ref)arg).makeArray(), pop())); return null;
 600             case MULTIANEWARRAY: {
 601                 MethodGen.MultiANewArray mana = (MethodGen.MultiANewArray) arg;
 602                 Expr[] dims = new Expr[mana.dims];
 603                 for(int i=0;i<dims.length;i++) dims[i] = pop();
 604                 return seqPush(new NewArray(mana.type, dims));
 605             }
 606             case ARRAYLENGTH:       return seqPush(new ArrayLength(pop()));
 607
 608                 // Runtime Type information //////////////////////////////////////////////////////////////////////////////
 609
 610             case CHECKCAST:         return seqPush(new Cast(pop(), (Type.Ref)arg));
 611             case INSTANCEOF:        push(new InstanceOf(pop(), (Type.Ref)arg)); return null;
 612
 613             case LDC: case LDC_W: case LDC2_W: push(new Constant(arg)); return null;
 614
 615             case BIPUSH:    push(new Constant((Integer)arg)); return null;
 616             case SIPUSH:    push(new Constant((Integer)arg)); return null;
 617
 618             case TABLESWITCH:    return new Branch((MethodGen.Switch)arg);
 619             case LOOKUPSWITCH:   return new Branch((MethodGen.Switch)arg);
 620
 621                 /*
 622             case MONITORENTER:   Op.monitorEnter(pop());
 623             case MONITOREXIT:    Op.monitorExit(pop());
 624                 */
 625
 626             case DUP_X1:         throw new Error("unimplemented");
 627             case DUP_X2:         throw new Error("unimplemented");
 628             case DUP2_X1:         throw new Error("unimplemented");
 629             case DUP2_X2:         throw new Error("unimplemented");
 630             case LCMP:         throw new Error("unimplemented");
 631             case FCMPL:         throw new Error("unimplemented");
 632             case FCMPG:         throw new Error("unimplemented");
 633             case DCMPL:         throw new Error("unimplemented");
 634             case DCMPG:         throw new Error("unimplemented");
 635             case GOTO_W:         throw new Error("unimplemented");
 636             case JSR_W:         throw new Error("unimplemented");
 637             default:          throw new Error("unhandled");
 638         }
 639     }
 640
 641
 642     public void debugBodyToString(StringBuffer sb) {
 643         StringBuffer sb0 = new StringBuffer();
 644         super.debugBodyToString(sb0);
 645         StringTokenizer st = new StringTokenizer(sb0.toString(), "\n");
 646         String[] lines = new String[st.countTokens()];
 647         for(int i=0; i<lines.length; i++) lines[i] = st.nextToken();
 648         for(int j=0; j<ofs[0]; j++) {
 649             String s = "    /* " + lines[j].trim();
 650              while(s.length() < 50) s += " ";
 651              s += " */";
 652              sb.append(s);
 653              sb.append("\n");
 654         }
 655
 656         bindingMap = new IdentityHashMap();
 657         nextVar = 0;
 658
 659         for(int i=0; i<numOps; i++) {
 660             String s = "    /* " + lines[ofs[i]].trim();
 661              while(s.length() < 50) s += " ";
 662              s += " */  ";
 663              s += ops[i].toString();
 664              sb.append(s);
 665              sb.append(";\n");
 666              for(int j=ofs[i]+1; j<(i==numOps-1?size():ofs[i+1]); j++) {
 667                  s = "    /* " + lines[j].trim();
 668                   while(s.length() < 50) s += " ";
 669                   s += " */";
 670                   sb.append(s);
 671                   sb.append("\n");
 672              }
 673         }
 674     }
 675
 676     private Map bindingMap;
 677     private int nextVar;
 678     String exprToString(Expr e) {
 679         if(e instanceof Constant) return e._toString();
 680         String s = (String)bindingMap.get(e);
 681         if(s != null) return s;
 682         String prefix;
 683         if(e.getType() == Type.VOID) return e._toString();
 684         else if(e.getType() == Type.DOUBLE || e.getType() == Type.FLOAT) prefix = "f";
 685         else if(e.getType().isPrimitive()) prefix = "i";
 686         else if(e.getType().isArray()) prefix = "a";
 687         else prefix = "o";
 688         s = prefix + (nextVar++);
 689         bindingMap.put(e,s);
 690         return "(" + s + " = " + e._toString() + ")";
 691     }
 692
 693     public static void main(String[] args) throws Exception {
 694         InputStream is = Class.forName(args[0]).getClassLoader().getResourceAsStream(args[0].replace('.', '/')+".class");
 695         System.out.println(new ClassFile(new DataInputStream(is), true).toString());
 696     }
 697 }