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