From 131193c8a763d354ae9a8818ffc8059d0e5dfcaf Mon Sep 17 00:00:00 2001
From: adam <adam@megacz.com>
Date: Thu, 30 Jun 2005 07:05:01 +0000
Subject: [PATCH] massive rewrite of Code.java

darcs-hash:20050630070501-5007d-701e24f59351581fb7568f122ce04a0b2ecbb98f.gz
---
 src/org/ibex/classgen/Code.java      |  398 +++++++++++++++++++++++++++++-----
 src/org/ibex/classgen/MethodGen.java |    3 +-
 src/org/ibex/classgen/Type.java      |    1 +
 3 files changed, 343 insertions(+), 59 deletions(-)

diff --git a/src/org/ibex/classgen/Code.java b/src/org/ibex/classgen/Code.java
index 22c8fc6..d4c459f 100644
--- a/src/org/ibex/classgen/Code.java
+++ b/src/org/ibex/classgen/Code.java
@@ -1,74 +1,356 @@
 package org.ibex.classgen;
-public class Code {
 
-    /**
-     *  This should actually be called "ValueProducer", but that
-     *  requires more typing.
-     *
-     *  A Value is anything that generates an item on the stack.
-     *  Every instruction that causes something new to appear on the
-     *  stack implements Value.  Every instruction that uses
-     *  something(s) on the stack will hold a reference to the thing
-     *  (almost always an instruction) that generates the thing(s) it
-     *  removes from the stack.
-     */
-    public interface Value {
-        // commented out so that the rest of this file compiles
-        // Instruction[] getUsers();
+/**
+ *  a highly streamlined SSA-form intermediate representation of a
+ *  sequence of JVM instructions; all stack manipulation is factored
+ *  out.
+ */
+public class JSSA {
+
+    // Constructor //////////////////////////////////////////////////////////////////////////////
+    
+    public JSSA(MethodGen mg) {
+        Expr[] reg = new Expr[5];
+        for(int i=0; i<mg.size(); i++) {
+            int    op  = mg.get(i);
+            Object arg = mg.getArg(i);
+            addOp(mg, op, arg);
+        }
+    }
+
+    // Instance Data; used ONLY during constructor; then thrown away /////////////////////////////////////////////////
+
+    /** this models the JVM registers; it is only used for unwinding stack-ops into an SSA-tree, then thrown away */
+    private Expr[] reg = new Expr[5];
+    
+    /** this models the JVM stack; it is only used for unwinding stack-ops into an SSA-tree, then thrown away */
+    private Expr[] stack = new Expr[65535];
+
+    /** JVM stack pointer */
+    private int sp = 0;
+    
+    private Expr push(Expr e) { return stack[sp++] = e; }
+    private Expr pop()        { return stack[--sp]; }
+
+
+    // SSA-node classes /////////////////////////////////////////////////////////////////////////////////////////
+
+    /** an purely imperative operation which does not generate data */
+    public abstract class Op {
+        //public abstract Op[] predecessors();  // not implemented yet
+        //public abstract Op[] successors();    // not implemented yet
+    }
+
+    /** an operation which generates data */
+    public abstract class Expr extends Op {
+        //public abstract Expr[] contributors();  // not implemented yet
+        //public abstract Expr[] dependents();    // not implemented yet
+
+        /** every JSSA.Expr either remembers its type _OR_ knows how to figure it out (the latter is preferred to eliminate
+         *  redundant information that could possibly "disagree" with itself -- this happened a LOT in Soot) */
+        public abstract Type getType();
     }
 
     /**
-     *  A "nondeterministic box" -- for example when the first
-     *  instruction in a loop reads from a local which could have been
-     *  written to either by some instruction at the end of the
-     *  previous iteration of the loop or by some instruction before
+     *  A "nondeterministic merge" -- for example when the first instruction in a loop reads from a local which could have been
+     *  written to either by some instruction at the end of the previous iteration of the loop or by some instruction before
      *  the loop (on the first iteration).
      */
-    public class Phi implements Value {
-        public Phi(Value[] inputs) { }
-        public Instruction[] getUsers() { return null; /* FIXME */ }
+    public class Phi extends Expr {
+        private final Expr[] inputs;
+        public Phi(Expr[] inputs) {
+            this.inputs = new Expr[inputs.length];
+            System.arraycopy(inputs, 0, this.inputs, 0, inputs.length);
+        }
+        public Type getType() {
+            // sanity check
+            Type t = inputs[0].getType();
+
+            // FIXME: actually this should check type-unifiability... fe, the "type of null" unifies with any Type.Ref
+            for(int i=1; i<inputs.length; i++)
+                if (inputs[i].getType() != t)
+                    throw new Error("Phi node with disagreeing types!  Crisis!");
+        }
     }
 
-    /** any instruction which does not -- by itself -- remove anything from the stack */
-    public class Instruction { }
 
-    /** any instruction that consumes one item from the stack */
-    public class OneOp           extends Instruction { Value in;  }
+public class Cast extends Expr {
+    final Expr e;
+    final Type t;
+    public Cast(Expr e, Type t) { this.e = e; this.t = t; }
+    public Type getType() { return t; }
+}
 
-    /** any instruction that consumes two items from the stack */
-    public class TwoOp           extends Instruction { Value in1, in2; }
-    
-    /** a sequence of instructions */
-    public class Sequence        extends Instruction { Instruction[] code; }
-    public class Monitor         extends Sequence    { Value objectToSynchronizeOn; }
-    public class TryCatchFinally extends Sequence    { OneOp[] catchBodies;  Instruction finallyBody; }
-
-    public class Goto            extends Instruction                  { Instruction target; }
-    public class JSR             extends Instruction implements Value { Instruction target; }
-    public class Ret             extends OneOp                        { }
-    public class Nop             extends Instruction                  { }
-
-    public class Constant        extends Instruction implements Value { /** ??? **/ }
-    public class LDC             extends Instruction implements Value { Type.Class klass; }
-    public class New             extends Instruction implements Value { Type.Ref   type; }
-    public class ArrayLength     extends OneOp       implements Value { }
-    public class ArrayIndex      extends Instruction implements Value { }
-    public class Return          extends OneOp                        { }
-    public class ReturnVoid      extends Instruction                  { }
-    public class CheckCast       extends OneOp       implements Value { Type.Ref   castTarget; }
-    public class Instanceof      extends OneOp       implements Value { Type.Class klass; }
-    public class If              extends OneOp                        { Instruction thenTarget, elseTarget; }
-    public class Switch          extends OneOp {
-        public class Table extends Switch { }
-        public class Lookup extends Switch { }
+public class InstanceOf extends Expr {
+    final Expr e;
+    final Type t;
+    public InstanceOf(Expr e, Type t) { this.e = e; this.t = t; }
+    public Type getType() { return Type.BOOLEAN; }
+}
+
+public class Branch extends Op {
+    public class Goto extends Branch { }
+    public class GoSub extends Branch { }
+    public class Ret extends Branch { }
+    public class If extends Branch { }
+}
+
+/** represents a "returnaddr" pushed onto the stack */
+public class Label extends Expr {
+    public final Op op;
+    public Type getType() { throw new Error("attempted to call getType() on a Label"); }
+    public Label(Op op) { this.op = op; }
+}
+
+public class Allocate extends Expr {
+    public final Type t;
+    public Type getType() { return t; }
+    public Allocate(Type t) { this.t = t; }
+}
+
+public class Return extends Op {
+    final Expr e;
+    public Return() { this(null); }
+    public Return(Expr e) { this.e = e; }
+}
+
+/** GETFIELD and GETSTATIC */
+public class Get extends Expr {
+    final Type.Class.Field f;
+    final Expr e;
+    public Type getType() { return f.getType(); }
+    public Get(Field f) { this(f, null); }
+    public Get(Field f, Expr e) { this.f = f; this.e = e; }
+}
+
+/** PUTFIELD and PUTSTATIC */
+public class Put extends Op {
+    final Type.Class.Field f;
+    final Expr v;
+    final Expr e;
+    public Put(Field f, Expr v) { this(f, v, null); }
+    public Put(Field f, Expr v, Expr e) { this.f = f; this.v = v; this.e = e; }
+}
+
+public class ArrayPut extends Op {
+    final Expr e, i, v;
+    public ArrayPut(Expr e, Expr i, Expr v) { this.e = e; this.i = i; this.v = v; }
+}
+
+public class ArrayGet extends Expr {
+    final Expr e, i;
+    public ArrayGet(Expr e, Expr i) { this.e = e; this.i = i; this.v = v; }
+    public Type getType() { return e.getType().asArray().elementType(); }
+}
+
+public class ArrayLength extends Expr {
+    final Expr e;
+    public ArrayLength(Expr e) { this.e = e; }
+    public Type getType() { return Type.INTEGER; }
+}
+
+public abstract class Invoke extends Op {
+    public final Expr[] arguments;
+    public final Type.Class.Method method;
+    protected Invoke(Type.Class.Method m, Expr[] a) { this.arguments = a; this.method m; } 
+
+    public Type getType() { return method.getReturnType(); }
+
+    public class Static    extends Invoke { public Static(Type.Class.Method m, Expr[] a) { super(m,a); } }
+    public class Special   extends Virtual { public Special(Type.Class.Method m, Expr[] a, Expr e) { super(m,a,e); } }
+    public class Interface extends Virtual { public Virtual(Type.Class.Method m, Expr[] a, Expr e) { super(m,a,e); } }
+    public class Virtual   extends Invoke {
+        public final Expr instance;
+        public Virtual(Type.Class.Method m, Expr[] a, Expr e) { super(m, a); instance = e; }
+    }
+}
+
+public static class Constant extends Expr {
+    private final Object o;
+    public Constant(Object o) { this.o = o; }
+    public Type getType() {
+        if (o instanceof Byte) return Type.BYTE;
+        if (o instanceof Short) return Type.SHORT;
+        if (o instanceof Char) return Type.CHAR;
+        if (o instanceof Boolean) return Type.BOOLEAN;
+        if (o instanceof Long) return Type.LONG;
+        if (o instanceof Double) return Type.DOUBLE;
+        if (o instanceof Float) return Type.FLOAT;
+        if (o instanceof ConstantPool.Ent) throw new Error("unimplemented");
+        throw new Error("this should not happen");
     }
+}
+
+    // Implementation //////////////////////////////////////////////////////////////////////////////
+
+    private void addOp(MethodGen mg, int op, Object arg) {
+        Number number = null;
+        int i1 = 0;
+        int i2 = 0;
+        if (op==WIDE) {
+            Wide w = (Wide)arg;
+            op = w.op;
+            arg = null;
+            i1 = w.varNum;
+            i2 = w.n;
+        }
+        if (op==IINC) {
+            Pair p = (Pair)arg;
+            arg = null;
+            i1 = p.i1;
+            i2 = p.i2;
+        }
+        if (arg != null && arg instanceof Number) number = (Number)arg;
+        switch(op) {
+
+            case NOP: return null;
+
+                // Stack manipulations //////////////////////////////////////////////////////////////////////////////
+
+            case ACONST_NULL:                                                      return stack[sp++] = new Constant(null);
+            case ICONST_M1:                                                        return stack[sp++] = new Constant(-1);
+            case ICONST_0: case LCONST_0: case FCONST_0: case DCONST_0:            return reg[0] = new Constant(i1);
+            case ICONST_1: case LCONST_1: case FCONST_1: case DCONST_1:            return reg[1] = new Constant(i1);
+            case ICONST_2: case FCONST_2:                                          return reg[2] = new Constant(i1);
+            case ICONST_3:                                                         return reg[3] = new Constant(i1);
+            case ICONST_4:                                                         return reg[4] = new Constant(i1);
+            case ICONST_5:                                                         return reg[5] = new Constant(i1);
+            case ILOAD:    case LLOAD:    case FLOAD:    case DLOAD:    case ALOAD:    return stack[sp++] = reg[i1];
+            case ILOAD_0:  case LLOAD_0:  case FLOAD_0:  case DLOAD_0:  case ALOAD_0:  return stack[sp++] = reg[0]; 
+            case ILOAD_1:  case LLOAD_1:  case FLOAD_1:  case DLOAD_1:  case ALOAD_1:  return stack[sp++] = reg[1]; 
+            case ALOAD_2:  case DLOAD_2:  case FLOAD_2:  case LLOAD_2:  case ILOAD_2:  return stack[sp++] = reg[2]; 
+            case ILOAD_3:  case LLOAD_3:  case FLOAD_3:  case DLOAD_3:  case ALOAD_3:  return stack[sp++] = reg[3]; 
+            case ISTORE:   case LSTORE:   case FSTORE:   case DSTORE:   case ASTORE:   return reg[i1] = stack[sp++];
+            case ISTORE_0: case LSTORE_0: case FSTORE_0: case DSTORE_0: case ASTORE_0: return reg[0] = stack[sp++]; 
+            case ISTORE_1: case LSTORE_1: case FSTORE_1: case DSTORE_1: case ASTORE_1: return reg[1] = stack[sp++]; 
+            case ASTORE_2: case DSTORE_2: case FSTORE_2: case LSTORE_2: case ISTORE_2: return reg[2] = stack[sp++]; 
+            case ISTORE_3: case LSTORE_3: case FSTORE_3: case DSTORE_3: case ASTORE_3: return reg[3] = stack[sp++]; 
+            case POP:      stack[--sp] = null;                    
+            case POP2:     stack[--sp] = null; stack[--sp] = null;   /** fixme: pops a WORD, not an item */
+            case DUP:      stack[sp] = stack[sp-1]; sp++;
+            case DUP2:     stack[sp] = stack[sp-2]; stack[sp+1] = stack[sp-1]; sp+=2;
+
+                // Conversions //////////////////////////////////////////////////////////////////////////////
+
+                // coercions are added as-needed when converting from JSSA back to bytecode, so we can
+                // simply discard them here (assuming the bytecode we're reading in was valid in the first place)
+
+            case I2L: case F2L: case D2L:               return push(new Cast(pop(), Type.LONG));
+            case I2F: case L2F: case D2F:               return push(new Cast(pop(), Type.FLOAT));
+            case I2D: case L2D: case F2D:               return push(new Cast(pop(), Type.DOUBLE));
+            case L2I: case F2I: case D2I:               return push(new Cast(pop(), Type.INT));
+            case I2B:                                   return push(new Cast(pop(), Type.BYTE));
+            case I2C:                                   return push(new Cast(pop(), Type.CHAR));
+            case I2S:                                   return push(new Cast(pop(), Type.SHORT));
+            case SWAP:                                  { Expr e1 = pop(), e2 = pop(); return push(e2); return push(e1); }
+
+                // Math //////////////////////////////////////////////////////////////////////////////
+                   
+            case IADD: case LADD: case FADD: case DADD: return push(new Add(pop(), pop()));
+            case ISUB: case LSUB: case FSUB: case DSUB: return push(new Sub(pop(), pop()));
+            case IMUL: case LMUL: case FMUL: case DMUL: return push(new Mul(pop(), pop()));
+            case IREM: case LREM: case FREM: case DREM: return push(new Rem(pop(), pop()));
+            case INEG: case LNEG: case FNEG: case DNEG: return push(new Neg(pop(), pop()));
+            case IDIV: case LDIV: case FDIV: case DDIV: return push(new Div(pop(), pop()));
+            case ISHL: case LSHL:                       return push(new Shl(pop(), pop()));
+            case ISHR: case LSHR:                       return push(new Shr(pop(), pop()));
+            case IUSHR: case LUSHR:                     return push(new Ushr(pop(), pop()));
+            case IAND: case LAND:                       return push(new And(pop(), pop()));
+            case IOR:  case LOR:                        return push(new Or(pop(), pop()));
+            case IXOR: case LXOR:                       return push(new Xor(pop(), pop()));
+            case IINC:                                  return reg[i1] = new Add(reg[i1], new Constant(i2));
+
+                // Control and branching //////////////////////////////////////////////////////////////////////////////
+
+            case IFNULL:                                return new Branch(eq(pop(), new Constant(null)), new Label(arg));
+            case IFNONNULL:                             return new Branch(not(eq(pop(), new Constant(null))), new Label(arg));
+            case IFEQ:                                  return new Branch(    eq(new Constant(0), pop()),  arg);
+            case IFNE:                                  return new Branch(not(eq(new Constant(0), pop())), arg);
+            case IFLT:                                  return new Branch(    lt(new Constant(0), pop()),  arg);
+            case IFGE:                                  return new Branch(not(lt(new Constant(0), pop())), arg);
+            case IFGT:                                  return new Branch(    gt(new Constant(0), pop()),  arg);
+            case IFLE:                                  return new Branch(not(gt(new Constant(0), pop())), arg);
+            case IF_ICMPEQ:                             return new Branch(    eq(pop(), pop()),  arg);
+            case IF_ICMPNE:                             return new Branch(not(eq(pop(), pop())), arg);
+            case IF_ICMPLT:                             return new Branch(    lt(pop(), pop()),  arg);
+            case IF_ICMPGE:                             return new Branch(not(lt(pop(), pop())), arg);
+            case IF_ICMPGT:                             return new Branch(    gt(pop(), pop()),  arg);
+            case IF_ICMPLE:                             return new Branch(not(gt(pop(), pop())), arg);
+            case IF_ACMPEQ:                             return new Branch(    eq(pop(), pop()),  arg);
+            case IF_ACMPNE:                             return new Branch(not(eq(pop(), pop())), arg);
+            case ATHROW:                                return new Throw(pop());
+            case GOTO:                                  return new Branch(new Label(arg));
+            case JSR:                                   return new Branch.JSR(new Label(arg));
+            case RET:                                   return new Branch.RET();
+            case RETURN:                                return new Return();
+            case IRETURN: case LRETURN: case FRETURN: case DRETURN: case ARETURN:
+                return new Return(pop());
+
+                // Array manipulations //////////////////////////////////////////////////////////////////////////////
+
+            case IALOAD:  case LALOAD:  case FALOAD:  case DALOAD:  case AALOAD:
+            case BALOAD:  case CALOAD:  case SALOAD:                                  return push(new ArrayGet(pop(), pop()));
+            case IASTORE: case LASTORE: case FASTORE: case DASTORE: case AASTORE:
+            case BASTORE: case CASTORE: case SASTORE:                                 return new ArrayPut(pop(), pop(), pop());
+
+                // Invocation //////////////////////////////////////////////////////////////////////////////
+
+            case INVOKEVIRTUAL: case INVOKESPECIAL: case INVOKESTATIC: case INVOKEINTERFACE: {
+                Type.Class.Method method = (Type.Class.Method)arg;
+                Expr args[] = new Expr[method.getNumArgs()];
+                for(int i=0; i<args.length; i++) args[args.length-i] = pop();
+                switch(op) {
+                    case INVOKEVIRTUAL:   return push(new Invoke.Virtual(method, args), pop());  
+                    case INVOKEINTERFACE: return push(new Invoke.Interface(method, args), pop());
+                    case INVOKESPECIAL:   return push(new Invoke.Special(method, args), pop());  
+                    case INVOKESTATIC:    return push(new Invoke.Static(method, args));          
+                }
+            }
+
+                // Field Access //////////////////////////////////////////////////////////////////////////////
+
+            case GETSTATIC:         return push(new Get((Type.Class.Field)arg, null));
+            case PUTSTATIC:         new Put((Type.Class.Field)arg, pop(), null);
+            case GETFIELD:          return push(new Get((Type.Class.Field)arg, pop()));
+            case PUTFIELD:          new Put((Type.Class.Field)arg, pop(), pop());
+
+                // Allocation //////////////////////////////////////////////////////////////////////////////
+
+            case NEW:
+            case NEWARRAY:          return push(new Allocate((Type)arg, pop()));
+            case ANEWARRAY:         return push(new Allocate(Type.OBJECT.makeArray(), pop()));
+            case MULTIANEWARRAY:    return push(new Allocate(Type.OBJECT.makeArray(i2), /* FIXME */));
+            case ARRAYLENGTH:       return push(new ArrayLength(pop()));
+
+                // Runtime Type information //////////////////////////////////////////////////////////////////////////////
+
+            case CHECKCAST:         return push(new Cast(pop(), (Type)arg));
+            case INSTANCEOF:        return push(new InstanceOf(pop(), (Type)arg));
+
+            case LDC: case LDC_W: case LDC2_W: return push(new Constant(arg));
+
+            case BIPUSH:    return push(new Constant(i1));  // FIXME
+            case SIPUSH:    return push(new Constant(i1));  // FIXME
+
+            case TABLESWITCH:    new Branch((MethodGen.Switch)arg);
+            case LOOKUPSWITCH:   new Branch((MethodGen.Switch)arg);
+
+            case MONITORENTER:   Op.monitorEnter(pop());
+            case MONITOREXIT:    Op.monitorExit(pop());
 
-    public abstract class Invoke extends Instruction {
-        Value[] arguments;
-        Type.Class.Method method;
-        public class Static  extends Invoke implements Value { }
-        public class Special extends Invoke implements Value { }
-        public class Virtual extends Invoke implements Value { Value instance; }
+            case DUP_X1:         throw new Error("unimplemented");
+            case DUP_X2:         throw new Error("unimplemented");
+            case DUP2_X1:         throw new Error("unimplemented");
+            case DUP2_X2:         throw new Error("unimplemented");
+            case LCMP:         throw new Error("unimplemented");
+            case FCMPL:         throw new Error("unimplemented");
+            case FCMPG:         throw new Error("unimplemented");
+            case DCMPL:         throw new Error("unimplemented");
+            case DCMPG:         throw new Error("unimplemented");
+            case GOTO_W:         throw new Error("unimplemented");
+            case JSR_W:         throw new Error("unimplemented");
+            default:          throw new Error("unhandled");
+        }
     }
 
 }
diff --git a/src/org/ibex/classgen/MethodGen.java b/src/org/ibex/classgen/MethodGen.java
index 3d59a12..3405fc9 100644
--- a/src/org/ibex/classgen/MethodGen.java
+++ b/src/org/ibex/classgen/MethodGen.java
@@ -25,7 +25,8 @@ public class MethodGen implements CGConst {
     private byte[] op;
     private Object[] arg;
     private ConstantPool.Ent[] cparg;
-    
+
+   
     // Constructors //////////////////////////////////////////////////////////////////////////////
 
     MethodGen(Type.Class.Method method, int flags) {
diff --git a/src/org/ibex/classgen/Type.java b/src/org/ibex/classgen/Type.java
index 95d9394..5eba76d 100644
--- a/src/org/ibex/classgen/Type.java
+++ b/src/org/ibex/classgen/Type.java
@@ -44,6 +44,7 @@ public class Type {
     public       boolean equals(java.lang.Object o) { return this==o; }
 
     public Type.Array  makeArray() { return (Type.Array)instance("["+descriptor); }
+    public Type.Array  makeArray(int i) { return i==0 ? this : makeArray().makeArray(i-1); }
 
     public Type.Ref    asRef()       { throw new RuntimeException("attempted to use "+this+" as a Type.Ref, which it is not"); }
     public Type.Class  asClass()     { throw new RuntimeException("attempted to use "+this+" as a Type.Class, which it is not"); }
-- 
1.7.10.4