1 package org.ibex.classgen;
6 * a highly streamlined SSA-form intermediate representation of a
7 * sequence of JVM instructions; all stack manipulation is factored
10 public class JSSA extends MethodGen implements CGConst {
12 // Constructor //////////////////////////////////////////////////////////////////////////////
14 public JSSA(Type.Class c, DataInput in, ConstantPool cp) throws IOException {
16 local = new Expr[maxLocals];
17 stack = new Expr[maxStack];
18 for(int i=0; i<this.method.getNumArgs(); i++)
19 local[i] = new Argument("arg"+i, this.method.getArgType(i));
20 for(int i=0; i<size(); i++) {
22 Object arg = getArg(i);
23 Object o = addOp(op, arg);
31 public void debugBodyToString(StringBuffer sb) {
32 StringBuffer sb0 = new StringBuffer();
33 super.debugBodyToString(sb0);
34 StringTokenizer st = new StringTokenizer(sb0.toString(), "\n");
35 String[] lines = new String[st.countTokens()];
36 for(int i=0; i<lines.length; i++) lines[i] = st.nextToken();
37 for(int j=0; j<ofs[0]; j++) {
38 String s = " /* " + lines[j].trim();
39 while(s.length() < 50) s += " ";
44 for(int i=0; i<numOps; i++) {
45 String s = " /* " + lines[ofs[i]].trim();
46 while(s.length() < 50) s += " ";
48 s += ops[i].toString();
51 for(int j=ofs[i]+1; j<(i==numOps-1?size():ofs[i+1]); j++) {
52 s = " /* " + lines[j].trim();
53 while(s.length() < 50) s += " ";
61 private Object[] ops = new Object[65535];
62 private int[] ofs = new int[65535];
63 private int numOps = 0;
65 // Instance Data; used ONLY during constructor; then thrown away /////////////////////////////////////////////////
67 /** this models the JVM locals; it is only used for unwinding stack-ops into an SSA-tree, then thrown away */
68 private final Expr[] local;
70 /** this models the JVM stack; it is only used for unwinding stack-ops into an SSA-tree, then thrown away */
71 private final Expr[] stack;
73 /** JVM stack pointer */
76 private Expr push(Expr e) {
77 if(sp == stack.length-1) throw new IllegalStateException("stack overflow");
78 return stack[sp++] = e;
81 if(sp == 0) throw new IllegalStateException("stack underflow");
86 // SSA-node classes /////////////////////////////////////////////////////////////////////////////////////////
88 public final Expr VOID_EXPR = new Expr() {
89 public Type getType() { return Type.VOID; }
92 /** an purely imperative operation which does not generate data */
93 public abstract class Op {
94 //public abstract Op[] predecessors(); // not implemented yet
95 //public abstract Op[] successors(); // not implemented yet
96 public String toString() { return name(); }
98 String name = this.getClass().getName();
99 if (name.indexOf('$') != -1) name = name.substring(name.lastIndexOf('$')+1);
100 if (name.indexOf('.') != -1) name = name.substring(name.lastIndexOf('.')+1);
105 /** an operation which generates data */
106 public abstract class Expr extends Op {
107 //public abstract Expr[] contributors(); // not implemented yet
108 //public abstract Expr[] dependents(); // not implemented yet
110 /** every JSSA.Expr either remembers its type _OR_ knows how to figure it out (the latter is preferred to eliminate
111 * redundant information that could possibly "disagree" with itself -- this happened a LOT in Soot) */
112 public abstract Type getType();
116 * A "nondeterministic merge" -- for example when the first instruction in a loop reads from a local which could have been
117 * written to either by some instruction at the end of the previous iteration of the loop or by some instruction before
118 * the loop (on the first iteration).
120 public class Phi extends Expr {
121 private final Expr[] inputs;
122 public Phi(Expr[] inputs) {
123 this.inputs = new Expr[inputs.length];
124 System.arraycopy(inputs, 0, this.inputs, 0, inputs.length);
126 public Type getType() {
128 Type t = inputs[0].getType();
130 // FIXME: actually this should check type-unifiability... fe, the "type of null" unifies with any Type.Ref
131 for(int i=1; i<inputs.length; i++)
132 if (inputs[i].getType() != t)
133 throw new Error("Phi node with disagreeing types! Crisis!");
138 public class Argument extends Expr {
139 public final String name;
141 public Argument(String name, Type t) { this.name = name; this.t = t; }
142 public String toString() { return name; }
143 public Type getType() { return t; }
146 // Binary Operations //////////////////////////////////////////////////////////////////////////////
148 public abstract class BinExpr extends Expr {
149 public final Expr e1;
150 public final Expr e2;
151 public BinExpr(Expr e1, Expr e2) { this.e1 = e1; this.e2 = e2; }
152 public String toString() {
153 return name() + "("+e1+", "+e2+")";
157 public class Comparison extends BinExpr {
158 public Comparison(Expr e1, Expr e2) { super(e1, e2); }
159 public Type getType() { return Type.BOOLEAN; }
161 public class Gt extends Comparison { public Gt(Expr e1, Expr e2) { super(e1, e2); } }
162 public class Lt extends Comparison { public Lt(Expr e1, Expr e2) { super(e1, e2); } }
163 public class Eq extends Comparison { public Eq(Expr e1, Expr e2) { super(e1, e2); } }
164 public class Not extends Expr {
166 public Not(Expr e) { this.e = e; }
167 public Type getType() { return Type.BOOLEAN; }
170 // Math Operations //////////////////////////////////////////////////////////////////////////////
172 public class Math extends BinExpr {
173 private final String show;
174 public Math(Expr e1, Expr e2, String show) { super(e2, e1); this.show = show; }
175 public String toString() { return e1+" "+show+" "+e2; }
176 public Type getType() {
177 Type t = e1.getType();
178 if (t != e2.getType()) throw new Error("types disagree");
182 public class Add extends Math { public Add(Expr e, Expr e2) { super(e, e2, "+"); } }
183 public class Sub extends Math { public Sub(Expr e, Expr e2) { super(e, e2, "-"); } }
184 public class Mul extends Math { public Mul(Expr e, Expr e2) { super(e, e2, "*"); } }
185 public class Rem extends Math { public Rem(Expr e, Expr e2) { super(e, e2, "%"); } }
186 //public class Neg extends Math { public Neg(Expr e) { super(e, "-"); } }
187 public class Div extends Math { public Div(Expr e, Expr e2) { super(e, e2, "/"); } }
188 public class Shl extends Math { public Shl(Expr e, Expr e2) { super(e, e2, "<<"); } }
189 public class Shr extends Math { public Shr(Expr e, Expr e2) { super(e, e2, ">>"); } }
190 public class Ushr extends Math { public Ushr(Expr e, Expr e2) { super(e, e2, ">>>"); } }
191 public class And extends Math { public And(Expr e, Expr e2) { super(e, e2, "&"); } }
192 public class Or extends Math { public Or(Expr e, Expr e2) { super(e, e2, "|"); } }
193 public class Xor extends Math { public Xor(Expr e, Expr e2) { super(e, e2, "^"); } }
195 // Other operations //////////////////////////////////////////////////////////////////////////////
197 public class Cast extends Expr {
200 public Cast(Expr e, Type t) {
201 if(e.getType().isRef() != t.isRef()) throw new IllegalArgumentException("invalid cast");
202 // FEATURE: Check that one is a subclass of the other if it is a ref
206 public Type getType() { return t; }
209 public class InstanceOf extends Expr {
212 public InstanceOf(Expr e, Type.Ref t) {
213 if(!e.getType().isRef()) throw new IllegalArgumentException("can't do an instanceof check on a non-ref");
217 public Type getType() { return Type.BOOLEAN; }
220 public class Throw extends Op {
222 public Throw(Expr e) {
223 if(!e.getType().isRef()) throw new IllegalArgumentException("can't throw a non ref");
224 // FEATURE: CHeck that it is a subclass of Throwable
229 public class Branch extends Op {
230 public Branch(Expr condition, Object destination) { }
231 public Branch(Label destination) { }
232 public Branch(MethodGen.Switch s) { }
235 public class Goto extends Branch { }
236 public class RET extends Branch { }
237 public class JSR extends Branch { public JSR(Label l) { super(l); } }
238 public class If extends Branch { }
240 /** represents a "returnaddr" pushed onto the stack */
241 public class Label extends Expr {
243 public Type getType() { throw new Error("attempted to call getType() on a Label"); }
244 public Label(Op op) { this.op = op; }
245 public Label(int i) { this.op = null; /* FIXME */ }
248 public class New extends Expr {
249 public final Type.Class t;
250 public Type getType() { return t; }
251 public New(Type.Class t) { this.t = t; }
254 public class NewArray extends Expr {
255 public final Type.Array t;
256 public final Expr[] dims;
257 public NewArray(Type.Array t, Expr[] dims) { this.t = t; this.dims = dims; }
258 public NewArray(Type.Array t, Expr dim) { this(t,new Expr[]{dim}); }
259 public Type getType() { return t; }
262 // FEATURE: Array stuff
264 public class Return extends Op {
266 public Return() { this(VOID_EXPR); }
267 public Return(Expr e) { this.e = e; }
268 public String toString() { return e.getType() == Type.VOID ? "return" : ("return "+e.toString()); }
271 /** GETFIELD and GETSTATIC */
272 public class Get extends Expr {
273 final Type.Class.Field f;
275 public Type getType() { return f.getType(); }
276 public Get(Type.Class.Field f) { this(f, null); }
277 public Get(Type.Class.Field f, Expr e) { this.f = f; this.e = e; }
278 public String toString() {
282 : f.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
288 /** PUTFIELD and PUTSTATIC */
289 public class Put extends Op {
290 final Type.Class.Field f;
293 public Put(Type.Class.Field f, Expr v) { this(f, v, null); }
294 public Put(Type.Class.Field f, Expr v, Expr e) { this.f = f; this.v = v; this.e = e; }
295 public String toString() {
299 : f.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
301 : f.toString()) + " = " + v;
305 public class ArrayPut extends Op {
307 public ArrayPut(Expr e, Expr i, Expr v) { this.e = e; this.i = i; this.v = v; }
310 public class ArrayGet extends Expr {
312 public ArrayGet(Expr e, Expr i) { this.e = e; this.i = i; }
313 public Type getType() { return e.getType().asArray().getElementType(); }
316 public class ArrayLength extends Expr {
318 public ArrayLength(Expr e) { this.e = e; }
319 public Type getType() { return Type.INT; }
322 public abstract class Invoke extends Expr {
323 public final Expr[] arguments;
324 public final Type.Class.Method method;
325 protected Invoke(Type.Class.Method m, Expr[] a) { this.arguments = a; this.method = m; }
327 public Type getType() { return method.getReturnType(); }
328 protected void args(StringBuffer sb) {
330 for(int i=0; i<arguments.length; i++) {
331 if (i>0) sb.append(", ");
332 sb.append(arguments[i]+"");
337 public String toString() {
338 StringBuffer sb = new StringBuffer();
339 sb.append(method.getDeclaringClass() == JSSA.this.method.getDeclaringClass()
341 : (method.getDeclaringClass() + "." + method.name));
343 return sb.toString();
346 public class InvokeStatic extends Invoke { public InvokeStatic(Type.Class.Method m, Expr[] a) { super(m,a); } }
347 public class InvokeSpecial extends InvokeVirtual {
348 public InvokeSpecial(Type.Class.Method m, Expr[] a, Expr e) { super(m,a,e); }
349 public String toString() {
350 StringBuffer sb = new StringBuffer();
351 sb.append(method.name.equals("<init>") ? "super" : method.name);
353 return sb.toString();
356 public class InvokeInterface extends InvokeVirtual{public InvokeInterface(Type.Class.Method m, Expr[] a, Expr e){super(m,a,e);}}
357 public class InvokeVirtual extends Invoke {
358 public final Expr instance;
359 public InvokeVirtual(Type.Class.Method m, Expr[] a, Expr e) { super(m, a); instance = e; }
360 public String toString() {
361 StringBuffer sb = new StringBuffer();
362 sb.append(method.name);
364 return sb.toString();
368 public class Constant extends Expr {
369 private final Object o;
370 public Constant(int i) { this(new Integer(i)); }
371 public Constant(Object o) { this.o = o; }
372 public String toString() { return o.toString(); }
373 public Type getType() {
374 if (o instanceof Byte) return Type.BYTE;
375 if (o instanceof Short) return Type.SHORT;
376 if (o instanceof Character) return Type.CHAR;
377 if (o instanceof Boolean) return Type.BOOLEAN;
378 if (o instanceof Long) return Type.LONG;
379 if (o instanceof Double) return Type.DOUBLE;
380 if (o instanceof Float) return Type.FLOAT;
381 if (o instanceof ConstantPool.Ent) throw new Error("unimplemented");
382 throw new Error("this should not happen");
387 // Implementation //////////////////////////////////////////////////////////////////////////////
389 private Object addOp(int op, Object arg) {
393 MethodGen.Wide w = (MethodGen.Wide)arg;
400 MethodGen.Pair p = (MethodGen.Pair)arg;
407 case NOP: return null;
409 // Stack manipulations //////////////////////////////////////////////////////////////////////////////
411 case ACONST_NULL: return stack[sp++] = new Constant(null);
412 case ICONST_M1: return stack[sp++] = new Constant(-1);
413 case ICONST_0: case LCONST_0: case FCONST_0: case DCONST_0: push(new Constant(0)); return null;
414 case ICONST_1: case LCONST_1: case FCONST_1: case DCONST_1: push(new Constant(1)); return null;
415 case ICONST_2: case FCONST_2: push(new Constant(2)); return null;
416 case ICONST_3: push(new Constant(3)); return null;
417 case ICONST_4: push(new Constant(4)); return null;
418 case ICONST_5: push(new Constant(5)); return null;
419 case ILOAD: case LLOAD: case FLOAD: case DLOAD: case ALOAD: return push(local[i1]);
420 case ILOAD_0: case LLOAD_0: case FLOAD_0: case DLOAD_0: case ALOAD_0: return push(local[0]);
421 case ILOAD_1: case LLOAD_1: case FLOAD_1: case DLOAD_1: case ALOAD_1: return push(local[1]);
422 case ALOAD_2: case DLOAD_2: case FLOAD_2: case LLOAD_2: case ILOAD_2: return push(local[2]);
423 case ILOAD_3: case LLOAD_3: case FLOAD_3: case DLOAD_3: case ALOAD_3: return push(local[3]);
424 case ISTORE: case LSTORE: case FSTORE: case DSTORE: case ASTORE: local[i1] = pop(); return null;
425 case ISTORE_0: case LSTORE_0: case FSTORE_0: case DSTORE_0: case ASTORE_0: local[0] = pop(); return null;
426 case ISTORE_1: case LSTORE_1: case FSTORE_1: case DSTORE_1: case ASTORE_1: local[1] = pop(); return null;
427 case ASTORE_2: case DSTORE_2: case FSTORE_2: case LSTORE_2: case ISTORE_2: local[2] = pop(); return null;
428 case ISTORE_3: case LSTORE_3: case FSTORE_3: case DSTORE_3: case ASTORE_3: local[3] = pop(); return null;
429 case POP: stack[--sp] = null;
430 case POP2: stack[--sp] = null; stack[--sp] = null; /** fixme: pops a WORD, not an item */
431 case DUP: stack[sp] = stack[sp-1]; sp++;
432 case DUP2: stack[sp] = stack[sp-2]; stack[sp+1] = stack[sp-1]; sp+=2;
434 // Conversions //////////////////////////////////////////////////////////////////////////////
436 // coercions are added as-needed when converting from JSSA back to bytecode, so we can
437 // simply discard them here (assuming the bytecode we're reading in was valid in the first place)
439 case I2L: case F2L: case D2L: push(new Cast(pop(), Type.LONG)); return null;
440 case I2F: case L2F: case D2F: push(new Cast(pop(), Type.FLOAT)); return null;
441 case I2D: case L2D: case F2D: push(new Cast(pop(), Type.DOUBLE)); return null;
442 case L2I: case F2I: case D2I: push(new Cast(pop(), Type.INT)); return null;
443 case I2B: push(new Cast(pop(), Type.BYTE)); return null;
444 case I2C: push(new Cast(pop(), Type.CHAR)); return null;
445 case I2S: push(new Cast(pop(), Type.SHORT)); return null;
446 case SWAP: { Expr e1 = pop(), e2 = pop(); push(e2); push(e1); return null; }
448 // Math //////////////////////////////////////////////////////////////////////////////
450 case IADD: case LADD: case FADD: case DADD: push(new Add(pop(), pop())); return null;
451 case ISUB: case LSUB: case FSUB: case DSUB: push(new Sub(pop(), pop())); return null;
452 case IMUL: case LMUL: case FMUL: case DMUL: push(new Mul(pop(), pop())); return null;
453 case IREM: case LREM: case FREM: case DREM: push(new Rem(pop(), pop())); return null;
454 //case INEG: case LNEG: case FNEG: case DNEG: push(new Neg(pop())); return null;
455 case IDIV: case LDIV: case FDIV: case DDIV: push(new Div(pop(), pop())); return null;
456 case ISHL: case LSHL: push(new Shl(pop(), pop())); return null;
457 case ISHR: case LSHR: push(new Shr(pop(), pop())); return null;
458 case IUSHR: case LUSHR: push(new Ushr(pop(), pop())); return null;
459 case IAND: case LAND: push(new And(pop(), pop())); return null;
460 case IOR: case LOR: push(new Or(pop(), pop())); return null;
461 case IXOR: case LXOR: push(new Xor(pop(), pop())); return null;
462 case IINC: return local[i1] = new Add(local[i1], new Constant(i2));
464 // Control and branching //////////////////////////////////////////////////////////////////////////////
466 case IFNULL: return new Branch(new Eq(pop(), new Constant(null)), new Label(i1));
467 case IFNONNULL: return new Branch(new Not(new Eq(pop(),new Constant(null))),new Label(i1));
468 case IFEQ: return new Branch( new Eq(new Constant(0), pop()), arg);
469 case IFNE: return new Branch(new Not(new Eq(new Constant(0), pop())), arg);
470 case IFLT: return new Branch( new Lt(new Constant(0), pop()), arg);
471 case IFGE: return new Branch(new Not(new Lt(new Constant(0), pop())), arg);
472 case IFGT: return new Branch( new Gt(new Constant(0), pop()), arg);
473 case IFLE: return new Branch(new Not(new Gt(new Constant(0), pop())), arg);
474 case IF_ICMPEQ: return new Branch( new Eq(pop(), pop()), arg);
475 case IF_ICMPNE: return new Branch(new Not(new Eq(pop(), pop())), arg);
476 case IF_ICMPLT: return new Branch( new Lt(pop(), pop()), arg);
477 case IF_ICMPGE: return new Branch(new Not(new Lt(pop(), pop())), arg);
478 case IF_ICMPGT: return new Branch( new Gt(pop(), pop()), arg);
479 case IF_ICMPLE: return new Branch(new Not(new Gt(pop(), pop())), arg);
480 case IF_ACMPEQ: return new Branch( new Eq(pop(), pop()), arg);
481 case IF_ACMPNE: return new Branch(new Not(new Eq(pop(), pop())), arg);
482 case ATHROW: return new Throw(pop());
483 case GOTO: return new Branch(new Label(i1));
484 case JSR: return new JSR(new Label(i1));
485 case RET: return new RET();
486 case RETURN: return new Return();
487 case IRETURN: case LRETURN: case FRETURN: case DRETURN: case ARETURN:
488 return new Return(pop());
490 // Array manipulations //////////////////////////////////////////////////////////////////////////////
492 case IALOAD: case LALOAD: case FALOAD: case DALOAD: case AALOAD:
493 case BALOAD: case CALOAD: case SALOAD: push(new ArrayGet(pop(), pop())); return null;
494 case IASTORE: case LASTORE: case FASTORE: case DASTORE: case AASTORE:
495 case BASTORE: case CASTORE: case SASTORE: return new ArrayPut(pop(), pop(), pop());
497 // Invocation //////////////////////////////////////////////////////////////////////////////
499 case INVOKEVIRTUAL: case INVOKESPECIAL: case INVOKESTATIC: case INVOKEINTERFACE: {
500 Type.Class.Method method = (Type.Class.Method)arg;
501 Expr args[] = new Expr[method.getNumArgs()];
502 for(int i=0; i<args.length; i++) args[args.length-i-1] = pop();
504 case INVOKEVIRTUAL: return push(new InvokeVirtual(method, args, pop()));
505 case INVOKEINTERFACE: return push(new InvokeInterface(method, args, pop()));
506 case INVOKESPECIAL: return push(new InvokeSpecial(method, args, pop()));
507 case INVOKESTATIC: return push(new InvokeStatic(method, args));
511 // Field Access //////////////////////////////////////////////////////////////////////////////
513 case GETSTATIC: push(new Get((Type.Class.Field)arg, null)); return null;
514 case PUTSTATIC: return new Put((Type.Class.Field)arg, pop(), null);
515 case GETFIELD: push(new Get((Type.Class.Field)arg, pop())); return null;
516 case PUTFIELD: return new Put((Type.Class.Field)arg, pop(), pop());
518 // Allocation //////////////////////////////////////////////////////////////////////////////
520 case NEW: push(new New((Type.Class)arg)); return null;
523 switch(((Integer)arg).intValue()) {
524 case 4: base = Type.BOOLEAN; break;
525 case 5: base = Type.CHAR; break;
526 case 6: base = Type.FLOAT; break;
527 case 7: base = Type.DOUBLE; break;
528 case 8: base = Type.BYTE; break;
529 case 9: base = Type.SHORT; break;
530 case 10: base = Type.INT; break;
531 case 11: base = Type.LONG; break;
532 default: throw new IllegalStateException("invalid array type");
534 push(new NewArray(base.makeArray(),pop()));
537 case ANEWARRAY: push(new NewArray(((Type.Ref)arg).makeArray(), pop())); return null;
538 case MULTIANEWARRAY: {
539 MethodGen.MultiANewArray mana = (MethodGen.MultiANewArray) arg;
540 Expr[] dims = new Expr[mana.dims];
541 for(int i=0;i<dims.length;i++) dims[i] = pop();
542 push(new NewArray(mana.type, dims));
545 case ARRAYLENGTH: push(new ArrayLength(pop())); return null;
547 // Runtime Type information //////////////////////////////////////////////////////////////////////////////
549 case CHECKCAST: push(new Cast(pop(), (Type.Ref)arg)); return null;
550 case INSTANCEOF: push(new InstanceOf(pop(), (Type.Ref)arg)); return null;
552 case LDC: case LDC_W: case LDC2_W: push(new Constant(arg)); return null;
554 case BIPUSH: push(new Constant(i1)); // FIXME return null;
555 case SIPUSH: push(new Constant(i1)); // FIXME return null;
557 case TABLESWITCH: new Branch((MethodGen.Switch)arg);
558 case LOOKUPSWITCH: new Branch((MethodGen.Switch)arg);
561 case MONITORENTER: Op.monitorEnter(pop());
562 case MONITOREXIT: Op.monitorExit(pop());
565 case DUP_X1: throw new Error("unimplemented");
566 case DUP_X2: throw new Error("unimplemented");
567 case DUP2_X1: throw new Error("unimplemented");
568 case DUP2_X2: throw new Error("unimplemented");
569 case LCMP: throw new Error("unimplemented");
570 case FCMPL: throw new Error("unimplemented");
571 case FCMPG: throw new Error("unimplemented");
572 case DCMPL: throw new Error("unimplemented");
573 case DCMPG: throw new Error("unimplemented");
574 case GOTO_W: throw new Error("unimplemented");
575 case JSR_W: throw new Error("unimplemented");
576 default: throw new Error("unhandled");
580 public static void main(String[] args) throws Exception {
581 InputStream is = Class.forName(args[0]).getClassLoader().getResourceAsStream(args[0].replace('.', '/')+".class");
582 System.out.println(new ClassFile(new DataInputStream(is), true).toString());