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