src/org/ibex/classgen/Code.java

   1 package org.ibex.classgen;
   2
   3 /**
   4  *  a highly streamlined SSA-form intermediate representation of a
   5  *  sequence of JVM instructions; all stack manipulation is factored
   6  *  out.
   7  */
   8 public class JSSA {
   9
  10     // Constructor //////////////////////////////////////////////////////////////////////////////
  11
  12     public JSSA(MethodGen mg) {
  13         Expr[] reg = new Expr[5];
  14         for(int i=0; i<mg.size(); i++) {
  15             int    op  = mg.get(i);
  16             Object arg = mg.getArg(i);
  17             addOp(mg, op, arg);
  18         }
  19     }
  20
  21     // Instance Data; used ONLY during constructor; then thrown away /////////////////////////////////////////////////
  22
  23     /** this models the JVM registers; it is only used for unwinding stack-ops into an SSA-tree, then thrown away */
  24     private Expr[] reg = new Expr[5];
  25
  26     /** this models the JVM stack; it is only used for unwinding stack-ops into an SSA-tree, then thrown away */
  27     private Expr[] stack = new Expr[65535];
  28
  29     /** JVM stack pointer */
  30     private int sp = 0;
  31
  32     private Expr push(Expr e) { return stack[sp++] = e; }
  33     private Expr pop()        { return stack[--sp]; }
  34
  35
  36     // SSA-node classes /////////////////////////////////////////////////////////////////////////////////////////
  37
  38     /** an purely imperative operation which does not generate data */
  39     public abstract class Op {
  40         //public abstract Op[] predecessors();  // not implemented yet
  41         //public abstract Op[] successors();    // not implemented yet
  42     }
  43
  44     /** an operation which generates data */
  45     public abstract class Expr extends Op {
  46         //public abstract Expr[] contributors();  // not implemented yet
  47         //public abstract Expr[] dependents();    // not implemented yet
  48
  49         /** every JSSA.Expr either remembers its type _OR_ knows how to figure it out (the latter is preferred to eliminate
  50          *  redundant information that could possibly "disagree" with itself -- this happened a LOT in Soot) */
  51         public abstract Type getType();
  52     }
  53
  54     /**
  55      *  A "nondeterministic merge" -- for example when the first instruction in a loop reads from a local which could have been
  56      *  written to either by some instruction at the end of the previous iteration of the loop or by some instruction before
  57      *  the loop (on the first iteration).
  58      */
  59     public class Phi extends Expr {
  60         private final Expr[] inputs;
  61         public Phi(Expr[] inputs) {
  62             this.inputs = new Expr[inputs.length];
  63             System.arraycopy(inputs, 0, this.inputs, 0, inputs.length);
  64         }
  65         public Type getType() {
  66             // sanity check
  67             Type t = inputs[0].getType();
  68
  69             // FIXME: actually this should check type-unifiability... fe, the "type of null" unifies with any Type.Ref
  70             for(int i=1; i<inputs.length; i++)
  71                 if (inputs[i].getType() != t)
  72                     throw new Error("Phi node with disagreeing types!  Crisis!");
  73         }
  74     }
  75
  76
  77 public class Cast extends Expr {
  78     final Expr e;
  79     final Type t;
  80     public Cast(Expr e, Type t) { this.e = e; this.t = t; }
  81     public Type getType() { return t; }
  82 }
  83
  84 public class InstanceOf extends Expr {
  85     final Expr e;
  86     final Type t;
  87     public InstanceOf(Expr e, Type t) { this.e = e; this.t = t; }
  88     public Type getType() { return Type.BOOLEAN; }
  89 }
  90
  91 public class Branch extends Op {
  92     public class Goto extends Branch { }
  93     public class GoSub extends Branch { }
  94     public class Ret extends Branch { }
  95     public class If extends Branch { }
  96 }
  97
  98 /** represents a "returnaddr" pushed onto the stack */
  99 public class Label extends Expr {
 100     public final Op op;
 101     public Type getType() { throw new Error("attempted to call getType() on a Label"); }
 102     public Label(Op op) { this.op = op; }
 103 }
 104
 105 public class Allocate extends Expr {
 106     public final Type t;
 107     public Type getType() { return t; }
 108     public Allocate(Type t) { this.t = t; }
 109 }
 110
 111 public class Return extends Op {
 112     final Expr e;
 113     public Return() { this(null); }
 114     public Return(Expr e) { this.e = e; }
 115 }
 116
 117 /** GETFIELD and GETSTATIC */
 118 public class Get extends Expr {
 119     final Type.Class.Field f;
 120     final Expr e;
 121     public Type getType() { return f.getType(); }
 122     public Get(Field f) { this(f, null); }
 123     public Get(Field f, Expr e) { this.f = f; this.e = e; }
 124 }
 125
 126 /** PUTFIELD and PUTSTATIC */
 127 public class Put extends Op {
 128     final Type.Class.Field f;
 129     final Expr v;
 130     final Expr e;
 131     public Put(Field f, Expr v) { this(f, v, null); }
 132     public Put(Field f, Expr v, Expr e) { this.f = f; this.v = v; this.e = e; }
 133 }
 134
 135 public class ArrayPut extends Op {
 136     final Expr e, i, v;
 137     public ArrayPut(Expr e, Expr i, Expr v) { this.e = e; this.i = i; this.v = v; }
 138 }
 139
 140 public class ArrayGet extends Expr {
 141     final Expr e, i;
 142     public ArrayGet(Expr e, Expr i) { this.e = e; this.i = i; this.v = v; }
 143     public Type getType() { return e.getType().asArray().elementType(); }
 144 }
 145
 146 public class ArrayLength extends Expr {
 147     final Expr e;
 148     public ArrayLength(Expr e) { this.e = e; }
 149     public Type getType() { return Type.INTEGER; }
 150 }
 151
 152 public abstract class Invoke extends Op {
 153     public final Expr[] arguments;
 154     public final Type.Class.Method method;
 155     protected Invoke(Type.Class.Method m, Expr[] a) { this.arguments = a; this.method m; }
 156
 157     public Type getType() { return method.getReturnType(); }
 158
 159     public class Static    extends Invoke { public Static(Type.Class.Method m, Expr[] a) { super(m,a); } }
 160     public class Special   extends Virtual { public Special(Type.Class.Method m, Expr[] a, Expr e) { super(m,a,e); } }
 161     public class Interface extends Virtual { public Virtual(Type.Class.Method m, Expr[] a, Expr e) { super(m,a,e); } }
 162     public class Virtual   extends Invoke {
 163         public final Expr instance;
 164         public Virtual(Type.Class.Method m, Expr[] a, Expr e) { super(m, a); instance = e; }
 165     }
 166 }
 167
 168 public static class Constant extends Expr {
 169     private final Object o;
 170     public Constant(Object o) { this.o = o; }
 171     public Type getType() {
 172         if (o instanceof Byte) return Type.BYTE;
 173         if (o instanceof Short) return Type.SHORT;
 174         if (o instanceof Char) return Type.CHAR;
 175         if (o instanceof Boolean) return Type.BOOLEAN;
 176         if (o instanceof Long) return Type.LONG;
 177         if (o instanceof Double) return Type.DOUBLE;
 178         if (o instanceof Float) return Type.FLOAT;
 179         if (o instanceof ConstantPool.Ent) throw new Error("unimplemented");
 180         throw new Error("this should not happen");
 181     }
 182 }
 183
 184     // Implementation //////////////////////////////////////////////////////////////////////////////
 185
 186     private void addOp(MethodGen mg, int op, Object arg) {
 187         Number number = null;
 188         int i1 = 0;
 189         int i2 = 0;
 190         if (op==WIDE) {
 191             Wide w = (Wide)arg;
 192             op = w.op;
 193             arg = null;
 194             i1 = w.varNum;
 195             i2 = w.n;
 196         }
 197         if (op==IINC) {
 198             Pair p = (Pair)arg;
 199             arg = null;
 200             i1 = p.i1;
 201             i2 = p.i2;
 202         }
 203         if (arg != null && arg instanceof Number) number = (Number)arg;
 204         switch(op) {
 205
 206             case NOP: return null;
 207
 208                 // Stack manipulations //////////////////////////////////////////////////////////////////////////////
 209
 210             case ACONST_NULL:                                                      return stack[sp++] = new Constant(null);
 211             case ICONST_M1:                                                        return stack[sp++] = new Constant(-1);
 212             case ICONST_0: case LCONST_0: case FCONST_0: case DCONST_0:            return reg[0] = new Constant(i1);
 213             case ICONST_1: case LCONST_1: case FCONST_1: case DCONST_1:            return reg[1] = new Constant(i1);
 214             case ICONST_2: case FCONST_2:                                          return reg[2] = new Constant(i1);
 215             case ICONST_3:                                                         return reg[3] = new Constant(i1);
 216             case ICONST_4:                                                         return reg[4] = new Constant(i1);
 217             case ICONST_5:                                                         return reg[5] = new Constant(i1);
 218             case ILOAD:    case LLOAD:    case FLOAD:    case DLOAD:    case ALOAD:    return stack[sp++] = reg[i1];
 219             case ILOAD_0:  case LLOAD_0:  case FLOAD_0:  case DLOAD_0:  case ALOAD_0:  return stack[sp++] = reg[0];
 220             case ILOAD_1:  case LLOAD_1:  case FLOAD_1:  case DLOAD_1:  case ALOAD_1:  return stack[sp++] = reg[1];
 221             case ALOAD_2:  case DLOAD_2:  case FLOAD_2:  case LLOAD_2:  case ILOAD_2:  return stack[sp++] = reg[2];
 222             case ILOAD_3:  case LLOAD_3:  case FLOAD_3:  case DLOAD_3:  case ALOAD_3:  return stack[sp++] = reg[3];
 223             case ISTORE:   case LSTORE:   case FSTORE:   case DSTORE:   case ASTORE:   return reg[i1] = stack[sp++];
 224             case ISTORE_0: case LSTORE_0: case FSTORE_0: case DSTORE_0: case ASTORE_0: return reg[0] = stack[sp++];
 225             case ISTORE_1: case LSTORE_1: case FSTORE_1: case DSTORE_1: case ASTORE_1: return reg[1] = stack[sp++];
 226             case ASTORE_2: case DSTORE_2: case FSTORE_2: case LSTORE_2: case ISTORE_2: return reg[2] = stack[sp++];
 227             case ISTORE_3: case LSTORE_3: case FSTORE_3: case DSTORE_3: case ASTORE_3: return reg[3] = stack[sp++];
 228             case POP:      stack[--sp] = null;
 229             case POP2:     stack[--sp] = null; stack[--sp] = null;   /** fixme: pops a WORD, not an item */
 230             case DUP:      stack[sp] = stack[sp-1]; sp++;
 231             case DUP2:     stack[sp] = stack[sp-2]; stack[sp+1] = stack[sp-1]; sp+=2;
 232
 233                 // Conversions //////////////////////////////////////////////////////////////////////////////
 234
 235                 // coercions are added as-needed when converting from JSSA back to bytecode, so we can
 236                 // simply discard them here (assuming the bytecode we're reading in was valid in the first place)
 237
 238             case I2L: case F2L: case D2L:               return push(new Cast(pop(), Type.LONG));
 239             case I2F: case L2F: case D2F:               return push(new Cast(pop(), Type.FLOAT));
 240             case I2D: case L2D: case F2D:               return push(new Cast(pop(), Type.DOUBLE));
 241             case L2I: case F2I: case D2I:               return push(new Cast(pop(), Type.INT));
 242             case I2B:                                   return push(new Cast(pop(), Type.BYTE));
 243             case I2C:                                   return push(new Cast(pop(), Type.CHAR));
 244             case I2S:                                   return push(new Cast(pop(), Type.SHORT));
 245             case SWAP:                                  { Expr e1 = pop(), e2 = pop(); return push(e2); return push(e1); }
 246
 247                 // Math //////////////////////////////////////////////////////////////////////////////
 248
 249             case IADD: case LADD: case FADD: case DADD: return push(new Add(pop(), pop()));
 250             case ISUB: case LSUB: case FSUB: case DSUB: return push(new Sub(pop(), pop()));
 251             case IMUL: case LMUL: case FMUL: case DMUL: return push(new Mul(pop(), pop()));
 252             case IREM: case LREM: case FREM: case DREM: return push(new Rem(pop(), pop()));
 253             case INEG: case LNEG: case FNEG: case DNEG: return push(new Neg(pop(), pop()));
 254             case IDIV: case LDIV: case FDIV: case DDIV: return push(new Div(pop(), pop()));
 255             case ISHL: case LSHL:                       return push(new Shl(pop(), pop()));
 256             case ISHR: case LSHR:                       return push(new Shr(pop(), pop()));
 257             case IUSHR: case LUSHR:                     return push(new Ushr(pop(), pop()));
 258             case IAND: case LAND:                       return push(new And(pop(), pop()));
 259             case IOR:  case LOR:                        return push(new Or(pop(), pop()));
 260             case IXOR: case LXOR:                       return push(new Xor(pop(), pop()));
 261             case IINC:                                  return reg[i1] = new Add(reg[i1], new Constant(i2));
 262
 263                 // Control and branching //////////////////////////////////////////////////////////////////////////////
 264
 265             case IFNULL:                                return new Branch(eq(pop(), new Constant(null)), new Label(arg));
 266             case IFNONNULL:                             return new Branch(not(eq(pop(), new Constant(null))), new Label(arg));
 267             case IFEQ:                                  return new Branch(    eq(new Constant(0), pop()),  arg);
 268             case IFNE:                                  return new Branch(not(eq(new Constant(0), pop())), arg);
 269             case IFLT:                                  return new Branch(    lt(new Constant(0), pop()),  arg);
 270             case IFGE:                                  return new Branch(not(lt(new Constant(0), pop())), arg);
 271             case IFGT:                                  return new Branch(    gt(new Constant(0), pop()),  arg);
 272             case IFLE:                                  return new Branch(not(gt(new Constant(0), pop())), arg);
 273             case IF_ICMPEQ:                             return new Branch(    eq(pop(), pop()),  arg);
 274             case IF_ICMPNE:                             return new Branch(not(eq(pop(), pop())), arg);
 275             case IF_ICMPLT:                             return new Branch(    lt(pop(), pop()),  arg);
 276             case IF_ICMPGE:                             return new Branch(not(lt(pop(), pop())), arg);
 277             case IF_ICMPGT:                             return new Branch(    gt(pop(), pop()),  arg);
 278             case IF_ICMPLE:                             return new Branch(not(gt(pop(), pop())), arg);
 279             case IF_ACMPEQ:                             return new Branch(    eq(pop(), pop()),  arg);
 280             case IF_ACMPNE:                             return new Branch(not(eq(pop(), pop())), arg);
 281             case ATHROW:                                return new Throw(pop());
 282             case GOTO:                                  return new Branch(new Label(arg));
 283             case JSR:                                   return new Branch.JSR(new Label(arg));
 284             case RET:                                   return new Branch.RET();
 285             case RETURN:                                return new Return();
 286             case IRETURN: case LRETURN: case FRETURN: case DRETURN: case ARETURN:
 287                 return new Return(pop());
 288
 289                 // Array manipulations //////////////////////////////////////////////////////////////////////////////
 290
 291             case IALOAD:  case LALOAD:  case FALOAD:  case DALOAD:  case AALOAD:
 292             case BALOAD:  case CALOAD:  case SALOAD:                                  return push(new ArrayGet(pop(), pop()));
 293             case IASTORE: case LASTORE: case FASTORE: case DASTORE: case AASTORE:
 294             case BASTORE: case CASTORE: case SASTORE:                                 return new ArrayPut(pop(), pop(), pop());
 295
 296                 // Invocation //////////////////////////////////////////////////////////////////////////////
 297
 298             case INVOKEVIRTUAL: case INVOKESPECIAL: case INVOKESTATIC: case INVOKEINTERFACE: {
 299                 Type.Class.Method method = (Type.Class.Method)arg;
 300                 Expr args[] = new Expr[method.getNumArgs()];
 301                 for(int i=0; i<args.length; i++) args[args.length-i] = pop();
 302                 switch(op) {
 303                     case INVOKEVIRTUAL:   return push(new Invoke.Virtual(method, args), pop());
 304                     case INVOKEINTERFACE: return push(new Invoke.Interface(method, args), pop());
 305                     case INVOKESPECIAL:   return push(new Invoke.Special(method, args), pop());
 306                     case INVOKESTATIC:    return push(new Invoke.Static(method, args));
 307                 }
 308             }
 309
 310                 // Field Access //////////////////////////////////////////////////////////////////////////////
 311
 312             case GETSTATIC:         return push(new Get((Type.Class.Field)arg, null));
 313             case PUTSTATIC:         new Put((Type.Class.Field)arg, pop(), null);
 314             case GETFIELD:          return push(new Get((Type.Class.Field)arg, pop()));
 315             case PUTFIELD:          new Put((Type.Class.Field)arg, pop(), pop());
 316
 317                 // Allocation //////////////////////////////////////////////////////////////////////////////
 318
 319             case NEW:
 320             case NEWARRAY:          return push(new Allocate((Type)arg, pop()));
 321             case ANEWARRAY:         return push(new Allocate(Type.OBJECT.makeArray(), pop()));
 322             case MULTIANEWARRAY:    return push(new Allocate(Type.OBJECT.makeArray(i2), /* FIXME */));
 323             case ARRAYLENGTH:       return push(new ArrayLength(pop()));
 324
 325                 // Runtime Type information //////////////////////////////////////////////////////////////////////////////
 326
 327             case CHECKCAST:         return push(new Cast(pop(), (Type)arg));
 328             case INSTANCEOF:        return push(new InstanceOf(pop(), (Type)arg));
 329
 330             case LDC: case LDC_W: case LDC2_W: return push(new Constant(arg));
 331
 332             case BIPUSH:    return push(new Constant(i1));  // FIXME
 333             case SIPUSH:    return push(new Constant(i1));  // FIXME
 334
 335             case TABLESWITCH:    new Branch((MethodGen.Switch)arg);
 336             case LOOKUPSWITCH:   new Branch((MethodGen.Switch)arg);
 337
 338             case MONITORENTER:   Op.monitorEnter(pop());
 339             case MONITOREXIT:    Op.monitorExit(pop());
 340
 341             case DUP_X1:         throw new Error("unimplemented");
 342             case DUP_X2:         throw new Error("unimplemented");
 343             case DUP2_X1:         throw new Error("unimplemented");
 344             case DUP2_X2:         throw new Error("unimplemented");
 345             case LCMP:         throw new Error("unimplemented");
 346             case FCMPL:         throw new Error("unimplemented");
 347             case FCMPG:         throw new Error("unimplemented");
 348             case DCMPL:         throw new Error("unimplemented");
 349             case DCMPG:         throw new Error("unimplemented");
 350             case GOTO_W:         throw new Error("unimplemented");
 351             case JSR_W:         throw new Error("unimplemented");
 352             default:          throw new Error("unhandled");
 353         }
 354     }
 355
 356 }