added DCode

3 files changed, 495 insertions, 0 deletions

diff --git a/src/compiler/scala/tools/nsc/interdf/DCode.scala b/src/compiler/scala/tools/nsc/interdf/DCode.scala
new file mode 100644
index 0000000000..4e2b329313
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/interdf/DCode.scala
@@ -0,0 +1,111 @@
+package scala.tools.nsc.interdf
+
+/** A variation of ICode that uses direct variable access
+  * instead of a stack. It is not needed for compilation, but
+  * it is a convenient representation for analysis.
+  *
+  * Note that instructions are grouped into basic blocks.
+  * Control flow between blocks is represented at the
+  * block level, not in instructions -- not even
+  * control instructions.
+  */
+abstract class DCode
+extends Object
+with ICodeToDCode
+{
+  val compiler: Global
+  import compiler._
+
+  /** A variable local to a Code instance; it corresponds to a stack position. */
+  case class StackVar(id: int) {
+    override def toString = "sv$" + id
+  }
+
+  /** A counter for generating fresh StackVar's */
+  private var svctr = 0
+
+  /** Generate a fresh StackVar. */
+  def genStackVar = {
+    svctr = svctr + 1
+    new StackVar(svctr)
+  }
+
+  /** One instruction to execute. */
+  abstract class Instruction
+  case class StrTrip(str: String) extends Instruction // XXX kill this
+  object opcodes {
+    import compiler.icodes.{Primitive, TypeKind, TestOp, Local}
+    import compiler.icodes.opcodes.InvokeStyle
+
+
+    /* standard pattern match:
+         case THIS(lhs, clasz)  =>
+         case CONSTANT(lhs, const)  =>
+         CASE VAR(lhs, rhs) =>
+         case LOAD_ARRAY_ITEM(lhs, ary, idx, kind)  =>
+         case LOAD_LOCAL(lhs, local, isArg)  =>
+         case LOAD_FIELD(lhs, from, field, isStatic)  =>
+         case LOAD_MODULE(lhs, module)  =>
+         case STORE_ARRAY_ITEM(ary, idx, obj, kind)  =>
+         case STORE_LOCAL(local, obj, isArg)  =>
+         case STORE_FIELD(into, field, obj, isStatic)  =>
+         case CALL_PRIMITIVE(lhs, primitive, args)  =>
+         case CALL_METHOD(lhs, rcvr, method, args, style)  =>
+         case NEW(lhs, kind)  =>
+         case CREATE_ARRAY(lhs, elem, size)  =>
+         case IS_INSTANCE(lhs, rhs, tpe)  =>
+         case CHECK_CAST(lhs, rhs, tpe)  =>
+         case SWITCH(obj, tags[List[int]])  =>
+         case JUMP()  =>
+         case CJUMP(left, cond, right, kind)  =>
+         case CZJUMP(obj, cond, kind)  =>
+         case RETURN(obj, kind)  =>
+         case RETURN_VOID(kind) =>
+         case THROW(exc)  =>
+         case MONITOR_ENTER(obj)  =>
+         case MONITOR_EXIT(obj)  =>
+         case NOP()  =>
+     */
+
+
+    case class THIS(lhs: StackVar, clasz: Symbol) extends Instruction
+    case class CONSTANT(lhs: StackVar, const: Constant) extends Instruction
+    case class VAR(lhs: StackVar, rhs: StackVar) extends Instruction
+    case class LOAD_ARRAY_ITEM(lhs: StackVar, ary: StackVar, idx: StackVar, kind: TypeKind) extends Instruction
+    case class LOAD_LOCAL(lhs: StackVar, local: Local, isArg: Boolean) extends Instruction
+    case class LOAD_FIELD(lhs: StackVar, from: StackVar, field: Symbol, isStatic: Boolean) extends Instruction
+    case class LOAD_MODULE(lhs: StackVar, module: Symbol) extends Instruction
+    case class STORE_ARRAY_ITEM(ary: StackVar, idx: StackVar, obj: StackVar, kind: TypeKind) extends Instruction
+    case class STORE_LOCAL(local: Local, obj: StackVar, isArg: Boolean) extends Instruction
+    case class STORE_FIELD(into: StackVar, field: Symbol, obj: StackVar, isStatic: Boolean) extends Instruction
+    case class CALL_PRIMITIVE(lhs: StackVar, primitive: Primitive, args: List[StackVar]) extends Instruction
+    case class CALL_METHOD(lhs: StackVar, rcvr: Option[StackVar], method: Symbol, args: List[StackVar], style: InvokeStyle) extends Instruction
+    case class NEW(lhs: StackVar, kind: TypeKind) extends Instruction
+    case class CREATE_ARRAY(lhs: StackVar, elem: TypeKind, size: StackVar) extends Instruction
+    case class IS_INSTANCE(lhs: StackVar, rhs: StackVar, tpe: TypeKind) extends Instruction
+    case class CHECK_CAST(lhs: StackVar, rhs: StackVar, tpe: TypeKind) extends Instruction
+    case class SWITCH(obj: StackVar, tags: List[List[int]]) extends Instruction
+    case class JUMP() extends Instruction
+    case class CJUMP(left: StackVar, cond: TestOp, right: StackVar, kind: TypeKind) extends Instruction
+    case class CZJUMP(obj: StackVar, cond: TestOp, kind: TypeKind) extends Instruction
+    case class RETURN(obj: StackVar, kind: TypeKind) extends Instruction
+    case class RETURN_VOID(kind: TypeKind) extends Instruction
+    case class THROW(exc: StackVar) extends Instruction
+    case class MONITOR_ENTER(obj: StackVar) extends Instruction
+    case class MONITOR_EXIT(obj: StackVar) extends Instruction
+    case class NOP() extends Instruction
+  }
+
+  class BasicBlock(
+      var instrs: List[Instruction],
+      var next: List[BasicBlock])
+  {
+    def this() = this(Nil, Nil)
+  }
+
+  class Code(val blocks: List[BasicBlock])
+  {
+    def start = blocks.head
+  }
+}
+
diff --git a/src/compiler/scala/tools/nsc/interdf/ICodeToDCode.scala b/src/compiler/scala/tools/nsc/interdf/ICodeToDCode.scala
new file mode 100644
index 0000000000..f72fe2d266
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/interdf/ICodeToDCode.scala
@@ -0,0 +1,324 @@
+package scala.tools.nsc.interdf
+import scala.collection.mutable.{HashMap, HashSet, Queue}
+
+/** Translation routine from ICode to DCode.
+  *
+  * To convert ICode to DCode, stack accesses must be
+  * translated to StackVar accesses.  Pushes turn into
+  * writes, while pops turn into reads.
+  *
+  * During the translation, the converter maintains abstract
+  * stacks that specify which StackVar's at each program
+  * point correspond to which stack positions.  These
+  * stacks maintain the invariant that no variable
+  * is used twice.
+  *
+  * Whenever an instruction pushes onto the stack, a new
+  * StackVar is allocated.  Other choices seem reasonable,
+  * but this one hopefully provides a moderate number of
+  * variables that correspond to the structure of the original
+  * program.
+  *
+  * During translation, whenever an icode block is visited
+  * the first time, the translator records that block.  Upon
+  * subsequent visits along a different incoming control
+  * edge, the first stack and the new stack do not in general
+  * agree.  To accodomodate this mismatch, (1) the first visit
+  * translates the block according to the first seen stack, and
+  * (2) later visits must prefix their entry to the block with
+  * another block that rewrites the stack variables to conform
+  * to the first visit.
+  */
+
+trait ICodeToDCode requires DCode {
+  import compiler.{icodes => I}
+  import I.{opcodes=>IOP}
+  import I.UNIT
+  import opcodes._
+  import compiler.icodes.opcodes.{Static, Dynamic}
+
+  /** Convert ICode into DCode. */
+  def icodeToDCode(code: I.Code): Code = {
+    /** Convert one ICode instruction to a DCode instruction */
+    def convIns(ins: I.Instruction, stack: List[StackVar]): Pair[Instruction, List[StackVar]] = {
+      ins match {
+        case IOP.THIS(clasz) => {
+          val lhs = genStackVar
+          Pair(THIS(lhs, clasz),
+               lhs::stack)
+        }
+        case IOP.CONSTANT(const) => {
+          val lhs = genStackVar
+          Pair(CONSTANT(lhs, const),
+               lhs::stack)
+        }
+        case IOP.LOAD_ARRAY_ITEM(kind) => {
+          val lhs = genStackVar
+          val idx::ary::stkbase = stack
+          Pair(LOAD_ARRAY_ITEM(lhs, ary, idx, kind),
+               lhs::stkbase)
+        }
+        case IOP.LOAD_LOCAL(local, isArg) => {
+          val lhs = genStackVar
+          Pair(LOAD_LOCAL(lhs, local, isArg),
+               lhs::stack)
+        }
+        case IOP.LOAD_FIELD(field, isStatic) => {
+          val lhs = genStackVar
+          val obj::stkbase = stack
+          Pair(LOAD_FIELD(lhs, obj, field, isStatic),
+               lhs::stkbase)
+        }
+        case IOP.LOAD_MODULE(module) => {
+          val lhs = genStackVar
+          Pair(LOAD_MODULE(lhs, module),
+               lhs::stack)
+        }
+        case IOP.STORE_ARRAY_ITEM(kind) => {
+          val obj::idx::ary::stkbase = stack
+          Pair(STORE_ARRAY_ITEM(ary, idx, obj, kind),
+               stkbase)
+        }
+        case IOP.STORE_LOCAL(local, isArg) => {
+          val obj::stkbase = stack
+          Pair(STORE_LOCAL(local, obj, isArg),
+               stkbase)
+        }
+        case IOP.STORE_FIELD(field, isStatic) => {
+          val obj::into::stkbase = stack
+          Pair(STORE_FIELD(into, field, obj, isStatic),
+               stkbase)
+        }
+        case IOP.CALL_PRIMITIVE(primitive) => {
+          val lhs = genStackVar
+          val numArgs = ins.consumed
+          val args = stack.take(numArgs).reverse
+          val stkbase = stack.drop(numArgs)
+          Pair(CALL_PRIMITIVE(lhs, primitive, args),
+               lhs::stkbase)
+        }
+        case IOP.CALL_METHOD(method, style) => {
+          val lhs = genStackVar
+
+          val numargs = method.tpe.paramTypes.length
+          val args = stack.take(numargs).reverse
+          val stack2 = stack.drop(numargs)
+
+          val Pair(rcvr,stkbase) = style match {
+            case Dynamic | Static(true) =>
+              Pair(Some(stack2.head), stack2.tail)
+
+            case _ => Pair(None, stack2)
+          }
+
+          Pair(CALL_METHOD(lhs, rcvr, method, args, style),
+               lhs::stkbase)
+        }
+        case IOP.NEW(kind) => {
+          val lhs = genStackVar
+          Pair(NEW(lhs, kind),
+               lhs::stack)
+        }
+        case IOP.CREATE_ARRAY(elem) => {
+          val lhs = genStackVar
+          val size::stkbase = stack
+          Pair(CREATE_ARRAY(lhs, elem, size),
+               lhs::stkbase)
+        }
+        case IOP.IS_INSTANCE(tpe) => {
+          val lhs = genStackVar
+          val rhs::stkbase = stack
+          Pair(IS_INSTANCE(lhs, rhs, tpe),
+               lhs::stkbase)
+        }
+        case IOP.CHECK_CAST(tpe) => {
+          val lhs = genStackVar
+          val rhs::stkbase = stack
+          Pair(CHECK_CAST(lhs, rhs, tpe),
+               lhs::stkbase)
+        }
+        case IOP.SWITCH(tags, labels) => {
+          val obj::stkbase = stack
+          Pair(SWITCH(obj, tags),
+               stkbase)
+        }
+        case IOP.JUMP(where) => Pair(JUMP(), stack)
+        case IOP.CJUMP(success, failure, cond, kind) => {
+          val right::left::stkbase = stack
+          Pair(CJUMP(left, cond, right, kind),
+               stkbase)
+        }
+        case IOP.CZJUMP(success, failure, cond, kind) => {
+          val obj::stkbase = stack
+          Pair(CZJUMP(obj, cond, kind),
+               stkbase)
+        }
+        case IOP.RETURN(kind) if kind==UNIT => {
+          Pair(RETURN_VOID(kind), stack)
+        }
+        case IOP.RETURN(kind) => { // kind != UNIT
+          val obj::stkbase = stack
+          Pair(RETURN(obj, kind),
+               stkbase)
+        }
+        case IOP.THROW() => {
+          val exc::stkbase = stack
+          Pair(THROW(exc),
+               stkbase)
+        }
+        case IOP.DROP(kind) => {
+          Pair(NOP, stack.tail)
+        }
+        case IOP.DUP(kind) => {
+          val sv = genStackVar
+          Pair(VAR(sv, stack.head),
+               sv::stack)
+        }
+        case IOP.MONITOR_ENTER() => {
+          val obj::stkbase = stack
+          Pair(MONITOR_ENTER(obj),
+               stkbase)
+        }
+        case IOP.MONITOR_EXIT() => {
+          val obj::stkbase = stack
+          Pair(MONITOR_EXIT(obj),
+               stkbase)
+        }
+      }
+    }
+
+    /** Convert the instructions from an ICode block to a Triples block */
+    def convInstrs(icblk: I.BasicBlock,
+                   tripblk: BasicBlock,
+                   startStack: List[StackVar]): List[StackVar] = {
+      def convLoop(instrs: List[I.Instruction], stack: List[StackVar]):
+              Pair[List[Instruction], List[StackVar]] = {
+        instrs match {
+          case Nil => Pair(Nil, stack)
+          case ins::insRest => {
+            val Pair(dins, nextStack) = convIns(ins, stack)
+            ins match {
+              case _:IOP.RETURN  => ()
+              case _ => {
+                if(!((nextStack.length - stack.length) ==  (ins.produced - ins.consumed))) {
+                  Console.println("bad conversion!")
+                  Console.println("Instruction: " + ins)
+                  Console.println("in stack: " + stack)
+                  Console.println("out stack: " + nextStack)
+                  throw new Error("assertion failed")
+                }
+              }
+            }
+            val Pair(dinsRest, finalStack) = convLoop(insRest, nextStack)
+            Pair(dins::dinsRest, finalStack)
+          }
+        }
+      }
+      val Pair(ins, outStack) = convLoop(icblk.instructions, startStack)
+      tripblk.instrs = ins
+      outStack
+    }
+
+    /** compute a block for rewriting the variables of
+      * one stack to the variables of another */
+    def rewriteStack(before: List[StackVar], after: List[StackVar]): BasicBlock = {
+      val beforeSet = new HashSet[StackVar]; beforeSet ++= before
+      val firstInsrs = new Queue[Instruction]
+      val lastInsrs = new Queue[Instruction]
+
+      for{val Pair(b, a) <- before.zip(after)
+          b != a}
+      {
+        if(!beforeSet.contains(a)) {
+          // safe to kill 'a'
+          firstInsrs += VAR(a, b)
+        } else {
+          // save 'a' to a temp variable, and only kill it at the end
+          val tmpvar = genStackVar
+          firstInsrs += VAR(tmpvar, b)
+          lastInsrs += VAR(a, tmpvar)
+        }
+      }
+
+      val insrs = firstInsrs.toList ::: lastInsrs.toList
+      new BasicBlock(insrs, Nil)
+    }
+
+    /** Accumulates converted blocks */
+    val blockMap = new HashMap[I.BasicBlock, BasicBlock]
+
+    /** Records which input-stack was used the first time each ICode
+      * block was converted to a DCode block.
+      */
+    val firstStackForBlock = new HashMap[BasicBlock, List[StackVar]]
+
+
+    /** calculate the next pointers for a given block */
+    def setNext(icblk: I.BasicBlock,
+                tripblk: BasicBlock,
+                endStack: List[StackVar]): Unit = {
+      import compiler.icodes.opcodes._
+
+      val out = icblk.lastInstruction match {
+        case SWITCH(tags, labels) => labels
+        case JUMP(where) => List(where)
+        case CJUMP(success, failure, _, _) => List(success, failure)
+        case CZJUMP(success, failure, _, _) => List(success, failure)
+        case RETURN(kind) => Nil
+        case THROW() => Nil
+        case _ => throw new Error("basic block falls off the end")
+      }
+      tripblk.next = out.map(b => conv(b, endStack))
+    }
+
+    /** Convert one basic block to a BB buffer. Memoes using blockMap.*/
+    def conv(blk: I.BasicBlock, stack: List[StackVar]): BasicBlock = {
+      blockMap.get(blk) match {
+        case Some(bb) => {
+          // Already seen.  Add a translation block if necessary
+          // in front of the previously converted block.
+          val firstStack = firstStackForBlock(bb)
+          assert(stack.length == firstStack.length)
+          if(stack == firstStack)
+            bb // same stacks -- no translation needed
+          else {
+            // different stacks; need to insert a translation block
+            val trans = rewriteStack(stack, firstStack)
+            trans.next = List(bb)
+            trans
+          }
+        }
+        case None => {
+          // new translation
+          val newblk = new BasicBlock
+          blockMap.update(blk, newblk)  // record this *before* recursing via setNext()
+          firstStackForBlock(newblk) = stack
+
+          val outStack = convInstrs(blk, newblk, stack)
+          setNext(blk, newblk, outStack)
+          newblk
+        }
+      }
+    }
+
+
+    /** Find all blocks reachable from a specified block */
+    def traverseAndCollect(b: BasicBlock): List[BasicBlock] = {
+      val seen = new HashSet[BasicBlock]
+      def trav(b: BasicBlock): List[BasicBlock] = {
+        if(seen.contains(b))
+          Nil
+        else {
+          seen += b
+          b :: b.next.flatMap(trav)
+        }
+      }
+      trav(b)
+    }
+
+    /* run the conversion */
+    val start = conv(code.startBlock, Nil)
+    val blocks = traverseAndCollect(start)
+    new Code(blocks)
+  }
+}
diff --git a/src/compiler/scala/tools/nsc/interdf/PrintDCode.scala b/src/compiler/scala/tools/nsc/interdf/PrintDCode.scala
new file mode 100644
index 0000000000..daa8681a96
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/interdf/PrintDCode.scala
@@ -0,0 +1,60 @@
+package scala.tools.nsc.interdf
+import scala.tools.nsc.reporters.ConsoleReporter
+import scala.collection.mutable.HashMap
+
+/** An example use of DCode: compile the requested files and then
+  * print out their DCode
+  */
+object PrintDCode {
+  def printDCode(dcode: DCode, files: List[String]) = {
+    import dcode._
+
+    val blockNames = new HashMap[BasicBlock,String]
+    def blockName(blk: BasicBlock): String = {
+      if(blockNames.contains(blk))
+        blockNames(blk)
+      else {
+        val name = "blk" + blockNames.size
+        blockNames(blk) = name
+        name
+      }
+    }
+
+    val run = new compiler.Run
+    run.compile(files)  // XXX this actually compiles the files; really, it should not
+                        // produce the class files....
+
+    for(val unit  <- run.units)
+        Console.println("Unit: " + unit)
+
+     for(val Pair(nam, cls) <- compiler.icodes.classes.toList) {
+       Console.println("Name: " + nam + " class: " + cls)
+       for(val meth <- cls.methods) {
+         Console.println("  method: " + meth)
+         val converted = icodeToDCode(meth.code)
+         converted.blocks.map(blockName) // name the blocks in order
+         for(val blk <- converted.blocks) {
+           Console.println("     " + blockName(blk) + ":")
+           for(val ins <- blk.instrs)
+             Console.println("        " + ins)
+           Console.println("     blocks after " +
+                           blockName(blk) + ": " + blk.next.map(blockName))
+           Console.println
+         }
+       }
+     }
+  }
+
+  def main(args: Array[String]): Unit = {
+    val reporter = new ConsoleReporter()
+    def error(msg: String): Unit =
+      reporter.error(null,
+          msg + "\n  " + "HACK" + " -help  gives more information")
+
+    val command = new CompilerCommand(List.fromArray(args), error, false)
+    object compiler extends Global(command.settings, reporter)
+    val comp = compiler
+    val dcode = new DCode{val compiler = comp}
+    printDCode(dcode, command.files)
+  }
+}