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