Revamped the icode analyses and removed some ex...

Revamped the icode analyses and removed some exhaustivity checks

14 files changed, 351 insertions, 84 deletions

diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala
index 8d8297afd1..b097b865ab 100644
--- a/src/compiler/scala/tools/nsc/Global.scala
+++ b/src/compiler/scala/tools/nsc/Global.scala
@@ -319,11 +319,11 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
   object genicode extends GenICode {
     val global: Global.this.type = Global.this
   }
-
+/*
   object icodePrinter extends backend.icode.Printers {
     val global: Global.this.type = Global.this
   }
-
+*/
   object scalaPrimitives extends ScalaPrimitives {
     val global: Global.this.type = Global.this
   }
@@ -617,7 +617,7 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable
   }
 
   private def writeICode(): Unit = {
-    val printer = new icodePrinter.TextPrinter(null, icodes.linearizer)
+    val printer = new icodes.TextPrinter(null, icodes.linearizer)
     icodes.classes.values.foreach((cls) => {
       val suffix = if (cls.symbol.hasFlag(Flags.MODULE)) "$.icode" else ".icode"
       var file = getFile(cls.symbol, suffix)
diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
index 8a6d480ca3..f54e102fca 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
@@ -80,7 +80,7 @@ trait BasicBlocks requires ICodes {
     }
 
     /** Compute an hashCode for the block */
-    override def hashCode() = label;
+//    override def hashCode() = label;
 
     /** Apply a function to all the instructions of the block. */
     def traverse(f: Instruction => unit) = {
@@ -123,6 +123,33 @@ trait BasicBlocks requires ICodes {
       None
     }
 
+    def findDefs(idx: Int, m: Int): List[(BasicBlock, Int)] = {
+      assert(closed)
+      var res: List[(BasicBlock, Int)] = Nil
+      var i = idx
+      var n = m
+      // "I look for who produced the 'n' elements below the 'd' topmost slots of the stack"
+      var d = 0
+      while (n > 0) {
+        i = i - 1
+        val prod = instrs(i).produced
+        if (prod > d) {
+          res = (this, i) :: res
+          n   = n - (prod - d)
+        }
+        d = d + (instrs(i).consumed - instrs(i).produced);
+      }
+      res
+    }
+
+    def findDefs(bb: BasicBlock, d: Int, n: Int): List[(BasicBlock, Int)] = {
+      var i = bb.size
+      while (n > 0 && i > 0) {
+
+      }
+      Nil
+    }
+
     /** Return the n-th instruction. */
     def apply(n: Int): Instruction =
       if (closed)
@@ -219,6 +246,18 @@ trait BasicBlocks requires ICodes {
       instrs = newInstrs
     }
 
+    /** Remove the last instruction of this basic block. It is
+     *  fast for an open block, but slower when the block is closed.
+     */
+    def removeLastInstruction: Unit = {
+      if (closed)
+        removeInstructionsAt(size)
+      else {
+        instructionList = instructionList.tail
+        touched = true
+      }
+    }
+
     /** Replaces all instructions found in the map.
      *
      *  @param map ...
@@ -287,6 +326,7 @@ trait BasicBlocks requires ICodes {
     def open = {
       closed = false
       ignore = false
+      instructionList = instructionList.reverse  // prepare for appending to the head
     }
 
     def clear: Unit = {
@@ -358,11 +398,11 @@ trait BasicBlocks requires ICodes {
       preds
     }
 
-    override def equals(other: Any): Boolean = other match {
+/*    override def equals(other: Any): Boolean = other match {
       case that: BasicBlock => that.label == label && that.code == code
       case _ => false
     }
-
+*/
     // Instead of it, rather use a printer
     def print() : unit = print(java.lang.System.out)
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
index 9b08ac20e7..404ebd649f 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
@@ -7,11 +7,11 @@
 
 package scala.tools.nsc.backend.icode;
 
-import java.io.PrintWriter;
+import java.io.PrintWriter
 
 import scala.tools.nsc.symtab._;
 import scala.collection.mutable.HashMap;
-import analysis.Liveness;
+import analysis.{Liveness, ReachingDefinitions};
 
 /** Glue together ICode parts.
  */
@@ -24,6 +24,7 @@ abstract class ICodes extends AnyRef
                                  with ExceptionHandlers
                                  with Primitives
                                  with Linearizers
+                                 with Printers
 {
   val global: Global;
 
@@ -43,41 +44,19 @@ abstract class ICodes extends AnyRef
     else
       global.abort("Unknown linearizer: " + global.settings.Xlinearizer.value);
 
-
   /** Print all classes and basic blocks. Used for debugging. */
   def dump: Unit = {
-    val printer = new global.icodePrinter.TextPrinter(new PrintWriter(Console.out, true),
-                                                      new global.icodes.DumpLinearizer());
-
-    global.icodes.classes.values foreach { c => printer.printClass(c); }
-  }
+    val printer = new TextPrinter(new PrintWriter(Console.out, true),
+                                  new DumpLinearizer);
 
-  def dump(m: global.icodes.IMethod) = {
-    val printer = new global.icodePrinter.TextPrinter(new PrintWriter(Console.out, true),
-                                                      new global.icodes.DumpLinearizer());
-    printer.printMethod(m);
+    classes.values foreach { c => printer.printClass(c); }
   }
 
-  /** Merge together blocks that have a single successor which has a
-   * single predecessor. Exception handlers are taken into account (they
-   * might force to break a block of straight line code like that).
-   *
-   * This method should be most effective after heavy inlining.
-   */
-  def normalize(m: IMethod): Unit = if (m.code ne null) {
-    Console.println("Method " + m);
-    val mergeablePairs =
-      for (val b <- m.code.blocks.toList;
-         b.successors.length == 1;
-         val succ = b.successors.head;
-         succ.predecessors.length == 1;
-         succ.predecessors.head == b;
-         !(m.exh.contains { (e: ExceptionHandler) => e.covers(b) && !e.covers(succ) }))
-        yield (b, succ)
-    ()
+  object liveness extends Liveness {
+    val global: ICodes.this.global.type = ICodes.this.global;
   }
 
-  object liveness extends Liveness {
+  object reachingDefinitions extends ReachingDefinitions {
     val global: ICodes.this.global.type = ICodes.this.global;
   }
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
index f185c4c4b3..6f01d7ce18 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
@@ -7,6 +7,8 @@
 
 package scala.tools.nsc.backend.icode;
 
+import java.io.PrintWriter;
+
 import scala.collection.mutable.HashMap;
 import scala.collection.mutable.{Set, HashSet};
 import scala.{Symbol => scala_Symbol};
@@ -230,6 +232,49 @@ trait Members requires ICodes {
         case _ => ()
       }
     }
+
+    /** Merge together blocks that have a single successor which has a
+     * single predecessor. Exception handlers are taken into account (they
+     * might force to break a block of straight line code like that).
+     *
+     * This method should be most effective after heavy inlining.
+     */
+    def normalize: Unit = if (this.code ne null) {
+      import scala.collection.mutable.{Map, HashMap}
+      val nextBlock: Map[BasicBlock, BasicBlock] = HashMap.empty
+      for (val b <- code.blocks.toList;
+        b.successors.length == 1;
+        val succ = b.successors.head;
+        succ ne b;
+        succ.predecessors.length == 1;
+        succ.predecessors.head eq b;
+        !(exh.contains { (e: ExceptionHandler) => e.covers(b) && !e.covers(succ) })) {
+          nextBlock(b) = succ
+      }
+
+      var bb = code.startBlock
+      while (!nextBlock.isEmpty) {
+        if (nextBlock.isDefinedAt(bb)) {
+          bb.open
+          var succ = bb
+          do {
+            succ = nextBlock(succ);
+            bb.removeLastInstruction
+            succ.toList foreach { i => bb.emit(i, i.pos) }
+            code.blocks -= succ
+            nextBlock -= bb
+          } while (nextBlock.isDefinedAt(succ))
+          bb.close
+        } else
+          bb = nextBlock.keys.next
+      }
+    }
+
+    def dump = {
+      val printer = new TextPrinter(new PrintWriter(Console.out, true),
+                                    new DumpLinearizer);
+      printer.printMethod(this);
+    }
   }
 
   /** Represent local variables and parameters */
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
index 6002c3ea6d..c02f121ae0 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
@@ -73,6 +73,9 @@ trait Opcodes requires ICodes {
 
     /** The corresponding position in the source file */
     var pos: Int = Position.NOPOS;
+
+    /** Used by dead code elimination. */
+    var useful: Boolean = true
   }
 
   object opcodes {
@@ -365,6 +368,8 @@ trait Opcodes requires ICodes {
 
       override def consumed = 1;
       override def produced = 1;
+      override val consumedTypes = List(REFERENCE(global.definitions.ObjectClass))
+      override def producedTypes = List(typ)
     }
 
     /** This class represents a SWITCH instruction
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
index 621936693d..06785a45ea 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
@@ -12,8 +12,8 @@ import java.io.PrintWriter;
 import scala.tools.nsc.util.Position;
 import scala.tools.nsc.symtab.Flags;
 
-abstract class Printers {
-  val global: Global;
+trait Printers requires ICodes {
+//  val global: Global;
   import global._;
   import global.icodes.opcodes._;
   import global.icodes._;
@@ -88,6 +88,7 @@ abstract class Printers {
         println(" {");
         println("locals: " + m.locals.mkString("", ", ", ""));
         println("startBlock: " + m.code.startBlock);
+        println("blocks: " + m.code.blocks.mkString("[", ",", "]"));
         println;
         lin.linearize(m) foreach printBlock;
         println("}");
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
index 4da3c1db2b..8084a409fb 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
@@ -271,12 +271,12 @@ abstract class CopyPropagation {
           case Static(onInstance) =>
             if (onInstance) {
               val obj = out.stack.drop(method.info.paramTypes.length).head
-              if (method.isConstructor) {
+              if (method.isPrimaryConstructor) {
                 obj match {
                   case Record(_, bindings) =>
                     for (val v <- out.stack.take(method.info.paramTypes.length + 1);
                          v ne obj) {
-                       bindings ++= getBindingsForClosure(in, method);
+                       bindings ++= getBindingsForPrimaryCtor(in, method);
                     }
                   case _ => ()
                 }
@@ -301,10 +301,10 @@ abstract class CopyPropagation {
           val v1 =
             kind match {
               case REFERENCE(cls) =>
-                if (isClosureClass(cls))
+/*                if (isClosureClass(cls))
                   Record(cls, new HashMap[Symbol, Value])
-                else Unknown
-
+                else Unknown */
+                Record(cls, new HashMap[Symbol, Value])
               case _ =>
                 Unknown
             }
@@ -434,22 +434,19 @@ abstract class CopyPropagation {
       }
     }
 
-    /** Return bindings from closure's fields to the values on the stack. This
+    /** Return bindings from an object fields to the values on the stack. This
      *  method has to find the correct mapping from fields to the order in which
-     *  they are passed on the stack.
-     *
-     *  @param in   ...
-     *  @param ctor ...
-     *  @return     ...
+     *  they are passed on the stack. It works for primary constructors.
      */
-    private def getBindingsForClosure(in: copyLattice.State, ctor: Symbol): Map[Symbol, Value] = {
+    private def getBindingsForPrimaryCtor(in: copyLattice.State, ctor: Symbol): Map[Symbol, Value] = {
       val paramAccessors = ctor.owner.constrParamAccessors;
       var values = in.stack.take(1 + ctor.info.paramTypes.length).reverse.drop(1);
       val bindings = new HashMap[Symbol, Value];
 
       // this relies on having the same order in paramAccessors and
       // the arguments on the stack. It should be the same!
-      for (val p <- paramAccessors) {
+      for (val (p, i) <- paramAccessors.zipWithIndex) {
+        assert(p.tpe == ctor.tpe.paramTypes(i))
         bindings += p -> values.head;
         values = values.tail;
       }
@@ -475,11 +472,7 @@ abstract class CopyPropagation {
      *  @return  ...
      */
     final def isPureMethod(m: Symbol): Boolean =
-      // MO: I added !m.hasFlag(DEFERRED) in a refactoring where
-      // getters now can be abstract whereas before they could not.
-      // Adding the condition thus keeps the old behavior.
-      // todo: review whether this is correct, or whether abstract getters should be included.
-      m.isGetter && !m.hasFlag(DEFERRED);
+      m.isGetter // abstract getters are still pure, as we 'know'
 
     final override def toString(): String = {
       var res = ""
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala
index 4be33c4ef1..72c74804fb 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala
@@ -45,6 +45,8 @@ abstract class Liveness {
 
     def init(m: IMethod): Unit = {
       this.method = m
+      gen.clear
+      kill.clear
 
       for (val b <- m.code.blocks.toList;
            val Pair(g, k) = genAndKill(b)) {
@@ -68,8 +70,8 @@ abstract class Liveness {
       var genSet = new ListSet[Local]
       var killSet = new ListSet[Local]
       for (val i <- b.toList) i match {
-        case LOAD_LOCAL(local) if (!killSet(local)) => genSet = genSet + local
-        case STORE_LOCAL(local) =>  killSet = killSet + local
+        case LOAD_LOCAL(local)  if (!killSet(local)) => genSet = genSet + local
+        case STORE_LOCAL(local) if (!genSet(local))  => killSet = killSet + local
         case _ => ()
       }
       Pair(genSet, killSet)
@@ -87,7 +89,10 @@ abstract class Liveness {
     def blockTransfer(b: BasicBlock, out: lattice.Elem): lattice.Elem =
       gen(b) incl (out excl kill(b))
 
-    /** Abstract interpretation for one instruction. */
+    /** Abstract interpretation for one instruction. Very important:
+     *  liveness is a backward DFA, so this method should be used to compute
+     *  liveness *before* the given instruction `i'.
+     */
     def interpret(out: lattice.Elem, i: Instruction): lattice.Elem = {
       var in = out
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala
new file mode 100644
index 0000000000..7c09d9a499
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala
@@ -0,0 +1,128 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2007 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+
+// $Id:  $
+
+package scala.tools.nsc.backend.icode.analysis
+
+import compat.StringBuilder
+import scala.collection.mutable.{HashMap, Map}
+import scala.collection.immutable.{Set, ListSet, HashSet}
+
+/** Compute reaching definitions. We are only interested in reaching
+ *  definitions for local variables, since values on the stack
+ *  behave as-if in SSA form: the closest instruction which produces a value
+ *  on the stack is a reaching definition.
+ */
+abstract class ReachingDefinitions {
+  val global: Global
+  import global._
+  import icodes._
+
+  /** The lattice for reaching definitions. Elements are
+   *  a triple (local variable, basic block, index of instruction of that basic block)
+   */
+  object rdefLattice extends CompleteLattice {
+    type Definition = (Local, BasicBlock, Int)
+    type Elem = Set[Definition]
+
+    val top: Elem = new ListSet[Definition]() {
+      override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]
+    }
+
+    val bottom: Elem = new ListSet[Definition]() {
+      override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]
+    }
+
+    def lub2(a: Elem, b: Elem): Elem = a incl b
+  }
+
+  class ReachingDefinitionsAnalysis extends DataFlowAnalysis[rdefLattice.type] {
+    type P = BasicBlock
+    val lattice = rdefLattice
+    import lattice.Definition
+    import lattice.Elem
+
+    var method: IMethod = _
+
+    val gen: Map[BasicBlock, Set[Definition]] = new HashMap()
+    val kill:Map[BasicBlock, Set[Local]]      = new HashMap()
+
+    def init(m: IMethod): Unit = {
+      this.method = m
+      gen.clear
+      kill.clear
+
+      for (val b <- m.code.blocks.toList;
+           val (g, k) = genAndKill(b)) {
+        gen  += b -> g
+        kill += b -> k
+      }
+
+      init {
+        worklist ++= m.code.blocks.toList
+        m.code.blocks.foreach { b =>
+          in(b)  = lattice.bottom
+          out(b) = lattice.bottom
+        }
+      }
+    }
+
+    import opcodes._
+
+    def genAndKill(b: BasicBlock): (Set[Definition], Set[Local]) = {
+      var genSet: Set[Definition] = new HashSet
+      var killSet: Set[Local] = new HashSet
+      for (val (i, idx) <- b.toList.zipWithIndex) i match {
+        case STORE_LOCAL(local) =>
+          killSet = killSet + local
+          genSet  = updateReachingDefinition(b, idx, genSet)
+        case _ => ()
+      }
+      (genSet, killSet)
+    }
+
+    override def run: Unit = {
+      forwardAnalysis(blockTransfer)
+      if (settings.debug.value) {
+        linearizer.linearize(method).foreach(b => if (b != method.code.startBlock)
+          assert(lattice.bottom != in(b),
+            "Block " + b + " in " + this.method + " has input equal to bottom -- not visited?"));
+      }
+    }
+
+    import opcodes._
+    def updateReachingDefinition(b: BasicBlock, idx: Int, rd: Set[Definition]): Set[Definition] = {
+      val STORE_LOCAL(local) = b(idx)
+      var tmp = local
+      (rd filter { case (l, _, _) => l != tmp }) + (tmp, b, idx)
+    }
+
+    private def blockTransfer(b: BasicBlock, in: Set[Definition]): Set[Definition] =
+      (in filter { case (l, _, _) => !kill(b)(l) }) incl gen(b)
+
+    /** Return the reaching definitions corresponding to the point after idx. */
+    def interpret(b: BasicBlock, idx: Int, in: lattice.Elem): Elem = {
+      var out = in
+      b(idx) match {
+        case STORE_LOCAL(l1) =>
+          out = updateReachingDefinition(b, idx, out)
+        case _ =>
+          ()
+      }
+
+      out
+    }
+
+    override def toString: String = {
+      val sb = new compat.StringBuilder
+      sb.append("rdef: \n")
+      for (val b <- method.code.blocks)
+        sb.append("rdef_entry(" + b + ")= " + in(b)).append("\nrdef_exit(" + b + ")= " + out(b))
+      sb.toString()
+    }
+
+  }
+}
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
index 71ca0959bd..a5c78fdf41 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
@@ -658,7 +658,7 @@ abstract class GenJVM extends SubComponent {
             "\nCurrent block: " + b +
             "\nCurrent instruction: " + instr +
             "\n---------------------" +
-            dump(method)
+            method.dump
           }
         }
         def assert(cond: Boolean, msg: String) = if (!cond) throw new CompilationError(msg);
@@ -1156,7 +1156,7 @@ abstract class GenJVM extends SubComponent {
             jcode.emitT2T(javaType(INT), javaType(kind))
         }
 
-        case Comparison(op, kind) => (op, kind) match {
+        case Comparison(op, kind) => ((op, kind): @unsealed) match {
           case (CMP, LONG)    => jcode.emitLCMP()
           case (CMPL, FLOAT)  => jcode.emitFCMPL()
           case (CMPG, FLOAT)  => jcode.emitFCMPG()
@@ -1471,7 +1471,7 @@ abstract class GenJVM extends SubComponent {
       }}).reverse
 
     def assert(cond: Boolean, msg: String) = if (!cond) {
-      dump(method)
+      method.dump
       throw new Error(msg + "\nMethod: " + method)
     }
 
diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
index 8b7fa9a3f3..cf43b4f611 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
@@ -18,7 +18,7 @@ abstract class ClosureElimination extends SubComponent {
   import icodes._;
   import icodes.opcodes._;
 
-  val phaseName = "closurelimination";
+  val phaseName = "closelim";
 
   /** Create a new phase */
   override def newPhase(p: Phase) = new ClosureEliminationPhase(p);
diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
index 152d33354e..329a2fe0bd 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
@@ -7,7 +7,8 @@
 
 package scala.tools.nsc.backend.opt;
 
-import scala.collection.mutable.{Map, HashMap};
+import scala.collection._
+import scala.collection.immutable.{Map, HashMap, Set, HashSet};
 import scala.tools.nsc.backend.icode.analysis.LubError;
 import scala.tools.nsc.symtab._;
 
@@ -18,7 +19,7 @@ abstract class DeadCodeElimination extends SubComponent {
   import icodes._;
   import icodes.opcodes._;
 
-  val phaseName = "deadcode";
+  val phaseName = "dce";
 
   /** Create a new phase */
   override def newPhase(p: Phase) = new DeadCodeEliminationPhase(p);
@@ -40,26 +41,77 @@ abstract class DeadCodeElimination extends SubComponent {
   class DeadCode {
     def analyzeClass(cls: IClass): Unit =
       cls.methods.foreach { m =>
-        analyzeMethod(m);
+//        analyzeMethod(m);
+	collectRDef(m)
       }
 
     val a = new liveness.LivenessAnalysis();
+    val rdef = new reachingDefinitions.ReachingDefinitionsAnalysis;
+
+    /** Use-def chain: give the reaching definitions at the beginning of given instruction. */
+    var defs: Map[(BasicBlock, Int), Set[rdef.lattice.Definition]] = HashMap.empty
+
+    /** Useful instructions which have not been scanned yet. */
+    val worklist: mutable.Set[(BasicBlock, Int)] = new mutable.HashSet
+
+    /** collect reaching definitions and initial useful instructions for this method. */
+    def collectRDef(m: IMethod): Unit = if (m.code ne null) {
+      log("rdef on " + m);
+      defs = HashMap.empty; worklist.clear
+      rdef.init(m);
+      rdef.run;
+
+      for (val bb <- m.code.blocks.toList) {
+        var rd = rdef.in(bb);
+        Console.println("** Block " + bb + " **")
+        for (val Pair(i, idx) <- bb.toList.zipWithIndex) {
+          i match {
+            case LOAD_LOCAL(l) => defs((bb, idx)) = rd
+            case RETURN(_) => worklist += (bb, idx)
+            case CALL_METHOD(m, _) if isSideEffecting(m) => worklist += (bb, idx)
+            case _ => ()
+          }
+          rd = rdef.interpret(bb, idx, rd);
+        }
+      }
+    }
+
+    /** Mark useful instructions. Instructions in the worklist are each inspected and their
+     *  dependecies are marked useful too, and added to the worklist.
+     */
+    def mark {
+      while (!worklist.isEmpty) {
+        val (bb, idx) = worklist.elements.next
+        worklist -= (bb, idx)
+
+        val instr = bb(idx)
+        assert(!instr.useful)
+        instr match {
+          case LOAD_LOCAL(l1) =>
+            for (val (_, bb1, idx1) <- defs((bb, idx)); !bb1(idx1).useful)
+              worklist += (bb1, idx1)
+          case _ =>
+            for (val (bb1, idx1) <- bb.findDefs(idx, 0); !bb1(idx1).useful)
+              worklist += (bb1, idx1)
+        }
+      }
+    }
 
     def analyzeMethod(m: IMethod): Unit = if (m.code ne null) {
       log("DCE on " + m);
       a.init(m);
       a.run;
 
-      for (val bb <- m.code.blocks.toList;
-           val (i, pos) <- bb.toList.zipWithIndex.reverse) {
+      for (val bb <- m.code.blocks.toList) {
         var live = a.out(bb);
-
-        i match {
-          case STORE_LOCAL(l) if (!live(l)) =>
-            removeDefUse(bb, i);
-          case _ => ()
+        for (val Pair(i, pos) <- bb.toList.zipWithIndex.reverse) {
+          i match {
+            case STORE_LOCAL(l) if (!live(l)) =>
+              removeDefUse(bb, i);
+            case _ => ()
+          }
+          live = a.interpret(live, i);
         }
-        live = a.interpret(live, i);
       }
     }
 
@@ -78,8 +130,8 @@ abstract class DeadCodeElimination extends SubComponent {
             if (definition.consumed == 0) {
               bb.removeInstructionsAt(defPos, usePos)
             } else {
-              bb.replaceInstruction(definition, definition.consumedTypes map DROP);
               bb.removeInstructionsAt(usePos);
+              bb.replaceInstruction(definition, definition.consumedTypes map DROP);
             }
           }
         case None =>
@@ -88,6 +140,11 @@ abstract class DeadCodeElimination extends SubComponent {
       }
     }
 
+    /** Is 'sym' a side-effecting method? TODO: proper analysis.  */
+    private def isSideEffecting(sym: Symbol): Boolean = {
+      sym.isClassConstructor // for testing only
+    }
+
     def isSafeToRemove(i: Instruction): Boolean = i match {
 /*      case LOAD_LOCAL(l) => true
       case LOAD_FIELD(_, _) => true
diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
index ea3442222e..31d648e129 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
@@ -7,7 +7,7 @@
 
 package scala.tools.nsc.backend.opt;
 
-import scala.collection.mutable.{Map, HashMap};
+import scala.collection.mutable.{Map, HashMap, Set, HashSet};
 import scala.tools.nsc.symtab._;
 
 /**
@@ -41,13 +41,18 @@ abstract class Inliners extends SubComponent {
    */
   class Inliner {
 
+    val fresh = new HashMap[String, Int]
+
     /* fresh name counter */
     var count = 0;
 
-    def freshName(s: String) = {
-      val ret = s + this.count;
-      this.count = this.count + 1;
-      ret
+    def freshName(s: String) = fresh.get(s) match {
+      case Some(count) =>
+        fresh(s) = count + 1
+        s + count
+      case None =>
+        fresh(s) = 1
+        s + "0"
     }
 
     /** Inline the 'callee' method inside the 'caller' in the given
@@ -69,7 +74,14 @@ abstract class Inliners extends SubComponent {
        /* Map 'original' blocks to the ones inlined in the caller. */
        val inlinedBlock: Map[BasicBlock, BasicBlock] = new HashMap;
 
-       val instrBefore = block.toList.takeWhile( i => i ne instr);
+       val varsInScope: Set[Local] = new HashSet[Local] ++ block.varsInScope.elements
+
+       val instrBefore = block.toList.takeWhile {
+         case i @ SCOPE_ENTER(l) => varsInScope += l
+           i ne instr
+         case i =>
+           i ne instr
+       }
        val instrAfter  = block.toList.drop(instrBefore.length + 1);
 
        assert(!instrAfter.isEmpty, "CALL_METHOD cannot be the last instrcution in block!");
@@ -90,6 +102,7 @@ abstract class Inliners extends SubComponent {
          activeHandlers.foreach (.addBlock(b));
          if (retVal ne null) b.varsInScope += retVal
          b.varsInScope += inlinedThis
+         b.varsInScope ++= varsInScope
          b
        }
 
@@ -240,6 +253,7 @@ abstract class Inliners extends SubComponent {
     def analyzeMethod(m: IMethod): Unit = try {
       var retry = false;
       var count = 0;
+      fresh.clear
 
       do {
         retry = false;
@@ -295,14 +309,14 @@ abstract class Inliners extends SubComponent {
                 info = tfa.interpret(info, i);
               }}}}
       } while (retry && count < 15);
-      normalize(m);
+      m.normalize
     } catch {
       case e =>
         Console.println("############# Cought exception: " + e + " #################");
         Console.println("\nMethod: " + m +
                         "\nMethod owner: " + m.symbol.owner);
         e.printStackTrace();
-        dump(m);
+        m.dump
         throw e;
     }
 
diff --git a/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala b/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala
index 5b521f12c8..c5f1e2115c 100644
--- a/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala
+++ b/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala
@@ -699,7 +699,7 @@ abstract class ICodeReader extends ClassfileParser {
         }
       }
 
-      icodes.dump(method)
+      method.dump
       tfa.init(method)
       tfa.run
       for (val bb <- linearizer.linearize(method)) {