Major rewrite of optimization phases.

22 files changed, 616 insertions, 212 deletions

diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala
index ee02445fc6..a61d878258 100644
--- a/src/compiler/scala/tools/nsc/Settings.scala
+++ b/src/compiler/scala/tools/nsc/Settings.scala
@@ -120,6 +120,7 @@ class Settings(error: String => unit) {
 //  val showPhases    = BooleanSetting("-showphases", "Print a synopsis of compiler phases")
 
   val inline        = BooleanSetting("-Xinline", "Perform inlining when possible")
+  val XO            = BooleanSetting("-XO", "Optimize. implies -Xinline, -Xcloselim and -Xdce")
   val Xcloselim     = BooleanSetting("-Xcloselim", "Perform closure elimination")
   val Xdce          = BooleanSetting("-Xdce", "Perform dead code elimination")
   val Xwarndeadcode = BooleanSetting("-Xwarndeadcode", "Emit warnings for dead code")
diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
index f56c50cfc5..2704345841 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
@@ -9,7 +9,7 @@ package scala.tools.nsc.backend.icode
 
 import compat.StringBuilder
 import scala.tools.nsc.ast._
-import scala.collection.mutable.{Map, Set, HashSet}
+import scala.collection.mutable.{Map, Set, LinkedHashSet}
 import scala.tools.nsc.util.Position
 import scala.tools.nsc.backend.icode.analysis.ProgramPoint
 
@@ -21,10 +21,12 @@ trait BasicBlocks requires ICodes {
    *  either executed all, or none. No jumps
    *  to/from the "middle" of the basic block are allowed.
    */
-  class BasicBlock (theLabel: int, val code: Code)
+  class BasicBlock (theLabel: int, val method: IMethod)
         extends AnyRef
         with ProgramPoint[BasicBlock] {
 
+    def code = method.code
+
     /** The label of the block */
     val label = theLabel
 
@@ -36,10 +38,13 @@ trait BasicBlocks requires ICodes {
     /** Is this block the head of a while? */
     var loopHeader = false
 
+    /** Is this block the start block of an exception handler? */
+    var exceptionHandlerHeader = false
+
     /** Local variables that are in scope at entry of this basic block. Used
      *  for debugging information.
      */
-    var varsInScope: Set[Local] = HashSet.empty
+    var varsInScope: Set[Local] = new LinkedHashSet()
 
     /** ICode instructions, used as temporary storage while emitting code.
      * Once closed is called, only the `instrs' array should be used.
@@ -59,6 +64,12 @@ trait BasicBlocks requires ICodes {
       instructionList
     }
 
+    /** return the underlying array of instructions */
+    def getArray: Array[Instruction] = {
+      assert(closed)
+      instrs
+    }
+
     def fromList(is: List[Instruction]): Unit = {
       instrs = toInstructionArray(is)
       closed = true
@@ -123,32 +134,6 @@ 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 =
@@ -226,6 +211,25 @@ trait BasicBlocks requires ICodes {
       changed
     }
 
+    /** Insert instructions in 'is' immediately after index 'idx'. */
+    def insertAfter(idx: Int, is: List[Instruction]) {
+      assert(closed, "Instructions can be replaced only after the basic block is closed")
+
+      var i = idx + 1
+      if (i < instrs.length) {
+        val newInstrs = new Array[Instruction](instrs.length + is.length);
+        Array.copy(instrs, 0, newInstrs, 0, i)
+        var j = i
+        for (val x <- is) {
+          newInstrs(j) = x
+          j = j + 1
+        }
+        if (i + 1 < instrs.length)
+          Array.copy(instrs, i + 1, newInstrs, j, instrs.length - i)
+        instrs = newInstrs;
+      }
+    }
+
     /** Removes instructions found at the given positions.
      *
      *  @param positions ...
@@ -324,6 +328,7 @@ trait BasicBlocks requires ICodes {
     }
 
     def open = {
+      assert(closed)
       closed = false
       ignore = false
       instructionList = instructionList.reverse  // prepare for appending to the head
@@ -373,8 +378,8 @@ trait BasicBlocks requires ICodes {
     def isClosed = closed
 
     // TODO: Take care of exception handlers!
-    def successors : List[BasicBlock] = if (isEmpty) Nil else
-      lastInstruction match {
+    def successors : List[BasicBlock] = if (isEmpty) Nil else {
+      var res = lastInstruction match {
         case JUMP (where) => List(where)
         case CJUMP(success, failure, _, _) => success :: failure :: Nil
         case CZJUMP(success, failure, _, _) => success :: failure :: Nil
@@ -388,6 +393,11 @@ trait BasicBlocks requires ICodes {
           }
           else Nil
       }
+      method.exh.foreach { e: ExceptionHandler =>
+        if (e.covers(this)) res = e.startBlock :: res
+      }
+      res
+    }
 
     /** Returns the precessors of this block, in the current 'code' chunk.
      *  This is signifficant only if there are exception handlers, which live
@@ -399,7 +409,7 @@ trait BasicBlocks requires ICodes {
     }
 
     override def equals(other: Any): Boolean = other match {
-      case that: BasicBlock => that.label == label && that.code == code
+      case that: BasicBlock => (that.label == label) && (that.code == code)
       case _ => false
     }
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala b/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala
index dd6a0a4487..43f6a8d3dd 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala
@@ -26,7 +26,10 @@ trait ExceptionHandlers requires ICodes {
 
     var resultKind: TypeKind = _;
 
-    def setStartBlock(b: BasicBlock) = _startBlock = b;
+    def setStartBlock(b: BasicBlock) = {
+      _startBlock = b;
+      b.exceptionHandlerHeader = true
+    }
     def startBlock = _startBlock;
 
     /** The list of blocks that are covered by this exception handler */
diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
index 7276a7ff12..0dab705502 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
@@ -507,9 +507,11 @@ abstract class GenICode extends SubComponent  {
 
                 (pat.symbol.tpe.symbol, kind, {
                   ctx: Context =>
+                    if (settings.Xdce.value)
+                      ctx.bb.emit(LOAD_EXCEPTION(), pat.pos)
                     ctx.bb.emit(STORE_LOCAL(exception), pat.pos);
-                  val ctx1 = genLoad(body, ctx, kind);
-                  genLoad(finalizer, ctx1, UNIT);
+                    val ctx1 = genLoad(body, ctx, kind);
+                    genLoad(finalizer, ctx1, UNIT);
                 })
             }
 
@@ -522,6 +524,8 @@ abstract class GenICode extends SubComponent  {
                                           .setInfo(definitions.ThrowableClass.tpe),
                                           REFERENCE(definitions.ThrowableClass), false);
               ctx.method.addLocal(exception);
+              if (settings.Xdce.value)
+                ctx.bb.emit(LOAD_EXCEPTION())
               ctx.bb.emit(STORE_LOCAL(exception));
               val ctx1 = genLoad(finalizer, ctx, UNIT);
               ctx1.bb.emit(LOAD_LOCAL(exception));
@@ -541,6 +545,8 @@ abstract class GenICode extends SubComponent  {
                 val tmp = new Local(ctx.method.symbol.newVariable(tree.pos, unit.fresh.newName("tmp")).setInfo(tree.tpe).setFlag(Flags.SYNTHETIC),
                     kind, false);
                 ctx1.method.addLocal(tmp)
+                if (settings.Xdce.value)
+                  ctx.bb.emit(LOAD_EXCEPTION())
                 ctx1.bb.emit(STORE_LOCAL(tmp))
                 val ctx2 = genLoad(duppedFinalizer, ctx1, UNIT)
                 ctx2.bb.emit(LOAD_LOCAL(tmp))
@@ -571,7 +577,7 @@ abstract class GenICode extends SubComponent  {
           else if (sym == definitions.Object_asInstanceOf)
             cast = true
           else
-            abort("Unexpected type application " + fun + "[sym: " + sym + "]")
+            abort("Unexpected type application " + fun + "[sym: " + sym.fullNameString + "]" + " in: " + tree)
 
           val Select(obj, _) = fun
           val l = toTypeKind(obj.tpe)
@@ -642,11 +648,14 @@ abstract class GenICode extends SubComponent  {
             case rt @ REFERENCE(cls) =>
               assert(ctor.owner == cls,
                      "Symbol " + ctor.owner.fullNameString + " is different than " + tpt)
-              ctx1.bb.emit(NEW(rt), tree.pos)
+              val nw = NEW(rt)
+              ctx1.bb.emit(nw, tree.pos)
               ctx1.bb.emit(DUP(generatedType))
               ctx1 = genLoadArguments(args, ctor.info.paramTypes, ctx)
 
-              ctx1.bb.emit(CALL_METHOD(ctor, Static(true)), tree.pos)
+              val init = CALL_METHOD(ctor, Static(true))
+              nw.init = init
+              ctx1.bb.emit(init, tree.pos)
 
             case _ =>
               abort("Cannot instantiate " + tpt + "of kind: " + generatedType)
@@ -797,6 +806,9 @@ abstract class GenICode extends SubComponent  {
             if (settings.debug.value && hostClass != sym.owner)
               log("Set more precise host class for " + sym.fullNameString + " host: " + hostClass);
             ctx1.bb.emit(CALL_METHOD(sym, invokeStyle) setHostClass hostClass, tree.pos)
+            if (sym == ctx1.method.symbol) {
+              ctx1.method.recursive = true
+            }
             generatedType =
               if (sym.isClassConstructor) UNIT
               else toTypeKind(sym.info.resultType);
@@ -1524,22 +1536,27 @@ abstract class GenICode extends SubComponent  {
                 if (settings.debug.value)
                   log("Pruning empty if branch.");
                 changed = true
-                assert(p.replaceInstruction(p.lastInstruction,
+                p.replaceInstruction(p.lastInstruction,
                                      if (block == succ)
-                                       CJUMP(cont, fail, cond, kind)
+                                       if (block == fail)
+                                         CJUMP(cont, cont, cond, kind)
+                                       else
+                                         CJUMP(cont, fail, cond, kind)
                                      else if (block == fail)
                                        CJUMP(succ, cont, cond, kind)
                                      else
-                                       abort("Could not find block in preds")),
-                       "Didn't find p.lastInstruction")
+                                       abort("Could not find block in preds"))
 
               case CZJUMP(succ, fail, cond, kind) =>
                 if (settings.debug.value)
-                  log("Pruning empty if branch.");
+                  log("Pruning empty ifz branch.");
                 changed = true
                 p.replaceInstruction(p.lastInstruction,
                                      if (block == succ)
-                                       CZJUMP(cont, fail, cond, kind)
+                                       if (block == fail)
+                                         CZJUMP(cont, cont, cond, kind)
+                                       else
+                                         CZJUMP(cont, fail, cond, kind)
                                      else if (block == fail)
                                        CZJUMP(succ, cont, cond, kind)
                                      else
@@ -1547,20 +1564,21 @@ abstract class GenICode extends SubComponent  {
 
               case JUMP(b) =>
                 if (settings.debug.value)
-                  log("Pruning empty if branch.");
+                  log("Pruning empty JMP branch.");
                 changed = true
                 assert(p.replaceInstruction(p.lastInstruction, JUMP(cont)),
                        "Didn't find p.lastInstruction")
 
               case SWITCH(tags, labels) =>
                 if (settings.debug.value)
-                  log("Pruning empty if branch.");
+                  log("Pruning empty SWITCH branch.");
                 changed = true
                 p.replaceInstruction(p.lastInstruction,
                                      SWITCH(tags, labels map (l => if (l == block) cont else l)))
             }
           }
           if (changed) {
+            log("Removing block: " + block)
             method.code.removeBlock(block);
             for (val e <- method.exh) {
               e.covered = e.covered filter (.!=(block))
@@ -1788,7 +1806,7 @@ abstract class GenICode extends SubComponent  {
       def enterMethod(m: IMethod, d: DefDef): Context = {
         val ctx1 = new Context(this) setMethod(m)
         ctx1.labels = new HashMap()
-        ctx1.method.code = new Code(m.symbol.simpleName.toString())
+        ctx1.method.code = new Code(m.symbol.simpleName.toString(), m)
         ctx1.bb = ctx1.method.code.startBlock
         ctx1.defdef = d
         ctx1.scope = EmptyScope
diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
index 404ebd649f..b73b0db448 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
@@ -60,7 +60,17 @@ abstract class ICodes extends AnyRef
     val global: ICodes.this.global.type = ICodes.this.global;
   }
 
-  def init = { }
+  var AnyRefReference: TypeKind = _
+  def init = {
+    AnyRefReference = REFERENCE(global.definitions.AnyRefClass)
+  }
+
+  import global.settings
+  if (settings.XO.value) {
+    settings.inline.value = true
+    settings.Xcloselim.value = true
+    settings.Xdce.value = true
+  }
 
   /** A phase which works on icode. */
   abstract class ICodePhase(prev: Phase) extends global.GlobalPhase(prev) {
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
index c25dc4aa3b..dd60378bcd 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
@@ -15,6 +15,7 @@ trait Linearizers requires ICodes {
 
   abstract class Linearizer {
     def linearize(c: IMethod): List[BasicBlock];
+    def linearizeAt(c: IMethod, start: BasicBlock): List[BasicBlock]
   }
 
   /**
@@ -44,6 +45,12 @@ trait Linearizers requires ICodes {
       blocks.reverse;
     }
 
+    def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = {
+      blocks = Nil
+      worklist.clear
+      linearize(start)
+    }
+
     /** Linearize another subtree and append it to the existing blocks. */
     def linearize(startBlock: BasicBlock): List[BasicBlock] = {
       //blocks = startBlock :: Nil;
@@ -102,6 +109,12 @@ trait Linearizers requires ICodes {
       blocks.reverse
     }
 
+    def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = {
+      blocks = Nil
+      dfs(start)
+      blocks.reverse
+    }
+
     def dfs(b: BasicBlock): Unit =
       if (b.size > 0 && add(b))
         b.successors foreach dfs;
@@ -144,6 +157,13 @@ trait Linearizers requires ICodes {
         m.code.startBlock :: (blocks.remove(.==(m.code.startBlock)))
     }
 
+    def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = {
+      blocks = Nil
+      visited.clear
+      rpo(start)
+      blocks
+    }
+
     def rpo(b: BasicBlock): Unit =
       if (b.size > 0 && !(visited contains b)) {
         visited += b;
@@ -168,5 +188,10 @@ trait Linearizers requires ICodes {
   class DumpLinearizer extends Linearizer {
     def linearize(m: IMethod): List[BasicBlock] =
       m.code.blocks.toList;
+
+    def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = {
+      error("not implemented")
+    }
   }
+
 }
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
index 6f01d7ce18..d3ecef16a8 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
@@ -10,7 +10,7 @@ package scala.tools.nsc.backend.icode;
 import java.io.PrintWriter;
 
 import scala.collection.mutable.HashMap;
-import scala.collection.mutable.{Set, HashSet};
+import scala.collection.mutable.{Set, HashSet, ListBuffer};
 import scala.{Symbol => scala_Symbol};
 
 import scala.tools.nsc.symtab.Flags;
@@ -22,10 +22,10 @@ trait Members requires ICodes {
    * This class represents the intermediate code of a method or
    * other multi-block piece of code, like exception handlers.
    */
-  class Code(label: String) {
+  class Code(label: String, method: IMethod) {
 
     /** The set of all blocks */
-    val blocks: HashSet[BasicBlock] = new HashSet;
+    val blocks: ListBuffer[BasicBlock] = new ListBuffer
 
     /** The start block of the method */
     var startBlock: BasicBlock = null;
@@ -41,7 +41,7 @@ trait Members requires ICodes {
     def removeBlock(b: BasicBlock) = {
       if (settings.debug.value) {
         assert(blocks.forall(p => !(p.successors.contains(b))),
-               "Removing block that is still referenced in method code " + label);
+               "Removing block that is still referenced in method code " + b + "preds: " + b.predecessors);
         if (b == startBlock)
           assert(b.successors.length == 1,
                  "Removing start block with more than one successor.");
@@ -74,7 +74,7 @@ trait Members requires ICodes {
       traverse0(startBlock :: Nil)
     }
 
-    def traverse(f: BasicBlock => Unit) = blocks foreach f;
+    def traverse(f: BasicBlock => Unit) = blocks.toList foreach f;
 
     /* This method applies the given function to each basic block. */
     def traverseFeedBack(f: (BasicBlock, HashMap[BasicBlock, Boolean])  => Unit) = {
@@ -110,7 +110,7 @@ trait Members requires ICodes {
     /* Create a new block and append it to the list
      */
     def newBlock: BasicBlock = {
-      val block = new BasicBlock(nextLabel, this);
+      val block = new BasicBlock(nextLabel, method);
       blocks += block;
       block;
     }
@@ -167,6 +167,8 @@ trait Members requires ICodes {
     var sourceFile: String = _;
     var returnType: TypeKind = _;
 
+    var recursive: Boolean = false
+
     /** local variables and method parameters */
     var locals: List[Local] = Nil;
 
@@ -248,7 +250,8 @@ trait Members requires ICodes {
         succ ne b;
         succ.predecessors.length == 1;
         succ.predecessors.head eq b;
-        !(exh.contains { (e: ExceptionHandler) => e.covers(b) && !e.covers(succ) })) {
+        !(exh.exists { (e: ExceptionHandler) =>
+            (e.covers(succ) && !e.covers(b)) || (e.covers(b) && !e.covers(succ)) })) {
           nextBlock(b) = succ
       }
 
@@ -261,8 +264,9 @@ trait Members requires ICodes {
             succ = nextBlock(succ);
             bb.removeLastInstruction
             succ.toList foreach { i => bb.emit(i, i.pos) }
-            code.blocks -= succ
+            code.removeBlock(succ)
             nextBlock -= bb
+            exh foreach { e => e.covered = e.covered.remove { b1 => b1 == succ } }
           } while (nextBlock.isDefinedAt(succ))
           bb.close
         } else
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
index c02f121ae0..4cd6c6312f 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
@@ -39,6 +39,9 @@ import scala.tools.nsc.util.Position;
   case DUP(kind) =>
   case MONITOR_ENTER() =>
   case MONITOR_EXIT() =>
+  case SCOPE_ENTER(lv) =>
+  case SCOPE_EXIT(lv) =>
+  case LOAD_EXCEPTION() =>
 */
 
 
@@ -75,7 +78,7 @@ trait Opcodes requires ICodes {
     var pos: Int = Position.NOPOS;
 
     /** Used by dead code elimination. */
-    var useful: Boolean = true
+    var useful: Boolean = false
   }
 
   object opcodes {
@@ -296,28 +299,48 @@ trait Opcodes requires ICodes {
           case Dynamic => 1
           case Static(true) => 1
           case Static(false) => 0
-          case SuperCall(_) => 0
+          case SuperCall(_) => 1
         });
 
         result;
       }
+
+      override def consumedTypes = {
+        val args = method.tpe.paramTypes map toTypeKind
+        style match {
+          case Dynamic | Static(true) => AnyRefReference :: args
+          case _ => args
+        }
+      }
+
       override def produced =
         if(toTypeKind(method.tpe.resultType) == UNIT)
           0
         else if(method.isConstructor)
           0
         else 1
+
+      /** object idenity is equality for CALL_METHODs. Needed for
+       *  being able to store such instructions into maps, when more
+       *  than one CALL_METHOD to the same method might exist.
+       */
+      override def equals(other: Any) = other match {
+        case o: AnyRef => this eq o
+        case _ => false
+      }
     }
 
     case class BOX(boxType: TypeKind) extends Instruction {
       override def toString(): String = "BOX " + boxType
       override def consumed = 1
+      override def consumedTypes = boxType :: Nil
       override def produced = 1
     }
 
     case class UNBOX(boxType: TypeKind) extends Instruction {
       override def toString(): String = "UNBOX " + boxType
       override def consumed = 1
+      override def consumedTypes = AnyRefReference :: Nil
       override def produced = 1
     }
 
@@ -331,6 +354,9 @@ trait Opcodes requires ICodes {
 
       override def consumed = 0;
       override def produced = 1;
+
+      /** The corresponding constructor call. */
+      var init: CALL_METHOD = _
     }
 
 
@@ -343,6 +369,7 @@ trait Opcodes requires ICodes {
       override def toString(): String ="CREATE_ARRAY "+elem.toString();
 
       override def consumed = 1;
+      override def consumedTypes = INT :: Nil
       override def produced = 1;
     }
 
@@ -355,6 +382,7 @@ trait Opcodes requires ICodes {
       override def toString(): String ="IS_INSTANCE "+typ.toString();
 
       override def consumed = 1;
+      override def consumedTypes = AnyRefReference :: Nil
       override def produced = 1;
     }
 
@@ -368,7 +396,7 @@ trait Opcodes requires ICodes {
 
       override def consumed = 1;
       override def produced = 1;
-      override val consumedTypes = List(REFERENCE(global.definitions.ObjectClass))
+      override val consumedTypes = List(AnyRefReference)
       override def producedTypes = List(typ)
     }
 
@@ -535,6 +563,18 @@ trait Opcodes requires ICodes {
       override def produced = 0
     }
 
+    /** Fake instruction. It designates the VM who pushes an exception
+     *  on top of the /empty/ stack at the beginning of each exception handler.
+     *  Note: Unlike other instructions, it consumes all elements on the stack!
+     *        then pushes one exception instance.
+     */
+    case class LOAD_EXCEPTION() extends Instruction {
+      override def toString(): String = "LOAD_EXCEPTION"
+      override def consumed = error("LOAD_EXCEPTION does clean the whole stack, no idea how many things it consumes!")
+      override def produced = 1
+      override def producedTypes = AnyRefReference :: Nil
+    }
+
     /** This class represents a method invocation style. */
     sealed abstract class InvokeStyle {
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
index 06785a45ea..97fb9c2d21 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
@@ -124,8 +124,8 @@ trait Printers requires ICodes {
     }
 
     def printInstruction(i: Instruction): Unit = {
-//      if (settings.debug.value)
-//        print("/* " + Position.line(clazz.cunit.source, i.pos) + " */ ");
+      if (settings.Xdce.value)
+        print(if (i.useful) "   " else " * ");
       println(i.toString());
     }
   }
diff --git a/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala b/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala
index a95865e13b..f9476842a0 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala
@@ -104,7 +104,11 @@ trait TypeKinds requires ICodes {
     else if (a == b) a
     else if (a == REFERENCE(definitions.AllClass)) b
     else if (b == REFERENCE(definitions.AllClass)) a
-    else throw new CheckerError("Incompatible types: " + a + " with " + b)
+    else (a, b) match {
+      case (BOXED(a1), BOXED(b1)) => if (a1 == b1) a else REFERENCE(definitions.AnyRefClass)
+      case (BOXED(_), REFERENCE(_)) | (REFERENCE(_), BOXED(_)) => REFERENCE(definitions.AnyRefClass)
+      case _ => throw new CheckerError("Incompatible types: " + a + " with " + b)
+    }
   }
 
   /** The unit value */
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala
index 3e0aa892d8..f124ea777f 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala
@@ -22,5 +22,11 @@ trait CompleteLattice {
   def bottom: Elem
 
   /** Compute the least upper bound of a list of elements. */
-  def lub(xs: List[Elem]): Elem = if (xs == Nil) bottom else xs reduceLeft lub2
+  def lub(xs: List[Elem]): Elem = try {
+    if (xs == Nil) bottom else xs reduceLeft lub2
+  } catch {
+      case e: LubError =>
+        Console.println("Lub on blocks: " + xs)
+        throw e
+  }
 }
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 8084a409fb..1bb33a5ca9 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
@@ -131,16 +131,30 @@ abstract class CopyPropagation {
     val top    = new State(emptyBinding, Nil)
     val bottom = new State(emptyBinding, Nil)
 
+    val exceptionHandlerStack = Unknown :: Nil
+
     def lub2(a: Elem, b: Elem): Elem = {
       if (a eq bottom)      b
       else if (b eq bottom) a
       else if (a == b) a
       else {
-        if (a.stack.length != b.stack.length)
+        val resStack =
+          if (a.stack eq exceptionHandlerStack) a.stack
+          else if (b.stack eq exceptionHandlerStack) b.stack
+          else {
+            if (a.stack.length != b.stack.length)
+              throw new LubError(a, b, "Invalid stacks in states: ");
+            List.map2(a.stack, b.stack) { (v1, v2) =>
+              if (v1 == v2) v1 else Unknown
+            }
+          }
+
+/*        if (a.stack.length != b.stack.length)
           throw new LubError(a, b, "Invalid stacks in states: ");
         val resStack = List.map2(a.stack, b.stack) { (v1, v2) =>
           if (v1 == v2) v1 else Unknown
         }
+        */
         val commonPairs = a.bindings.toList intersect (b.bindings.toList)
         val resBindings = new HashMap[Location, Value]
         for (val Pair(k, v) <- commonPairs)
@@ -165,9 +179,11 @@ abstract class CopyPropagation {
         m.code.blocks.foreach { b =>
           in(b)  = lattice.bottom
           out(b) = lattice.bottom
+          assert(out.contains(b))
+          log("Added point: " + b)
         }
         m.exh foreach { e =>
-          in(e.startBlock) = new copyLattice.State(copyLattice.emptyBinding, Unknown :: Nil);
+          in(e.startBlock) = new copyLattice.State(copyLattice.emptyBinding, copyLattice.exceptionHandlerStack);
         }
 
         // first block is special: it's not bottom, but a precisely defined state with no bindings
@@ -244,7 +260,7 @@ abstract class CopyPropagation {
                 case _ =>
                   out.bindings += LocalVar(local) -> v;
               }
-            case Nil => error("Incorrect icode. Expecting something on the stack.")
+            case Nil => Predef.error("Incorrect icode in " + method + ". Expecting something on the stack.")
           }
           out.stack = out.stack drop 1;
 
@@ -271,7 +287,8 @@ abstract class CopyPropagation {
           case Static(onInstance) =>
             if (onInstance) {
               val obj = out.stack.drop(method.info.paramTypes.length).head
-              if (method.isPrimaryConstructor) {
+//              if (method.isPrimaryConstructor) {
+              if (method.isPrimaryConstructor/* && isClosureClass(method.owner)*/) {
                 obj match {
                   case Record(_, bindings) =>
                     for (val v <- out.stack.take(method.info.paramTypes.length + 1);
@@ -353,6 +370,9 @@ abstract class CopyPropagation {
         case SCOPE_ENTER(_) | SCOPE_EXIT(_) =>
           ()
 
+        case LOAD_EXCEPTION() =>
+          out.stack = Unknown :: Nil
+
         case _ =>
           dump
           abort("Unknown instruction: " + i)
@@ -408,7 +428,7 @@ abstract class CopyPropagation {
     final def simulateCall(state: copyLattice.State, method: Symbol, static: Boolean): copyLattice.State = {
       val out = new copyLattice.State(state.bindings, state.stack);
       out.stack = out.stack.drop(method.info.paramTypes.length + (if (static) 0 else 1));
-      if (method.info.resultType != definitions.UnitClass.tpe)
+      if (method.info.resultType != definitions.UnitClass.tpe && !method.isConstructor)
         out.stack = Unknown :: out.stack;
       if (!isPureMethod(method))
         invalidateRecords(out);
@@ -446,8 +466,9 @@ abstract class CopyPropagation {
       // this relies on having the same order in paramAccessors and
       // the arguments on the stack. It should be the same!
       for (val (p, i) <- paramAccessors.zipWithIndex) {
-        assert(p.tpe == ctor.tpe.paramTypes(i))
-        bindings += p -> values.head;
+//        assert(p.tpe == ctor.tpe.paramTypes(i), "In: " + ctor.fullNameString + " having: " + (paramAccessors map (.tpe))+ " vs. " + ctor.tpe.paramTypes)
+	if (p.tpe == ctor.tpe.paramTypes(i))
+	  bindings += p -> values.head;
         values = values.tail;
       }
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala
index 3d4d3e6f14..7a3e858baa 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala
@@ -18,8 +18,8 @@ trait DataFlowAnalysis[L <: CompleteLattice] {
 
   val worklist: Set[P] = new LinkedHashSet
 
-  val in:  Map[P, lattice.Elem] = new HashMap
-  val out: Map[P, lattice.Elem] = new HashMap
+  val in:  Map[P, lattice.Elem] = new collection.jcl.HashMap
+  val out: Map[P, lattice.Elem] = new collection.jcl.HashMap
   val visited: HashSet[P] = new HashSet
 
   /* Implement this function to initialize the worklist.  */
@@ -36,7 +36,7 @@ trait DataFlowAnalysis[L <: CompleteLattice] {
    *
    *  @param f the transfer function.
    */
-  def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit =
+  def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = try {
     while (!worklist.isEmpty) {
 //      Console.println("worklist in: " + worklist);
       val point = worklist.elements.next; worklist -= point; visited += point;
@@ -44,8 +44,7 @@ trait DataFlowAnalysis[L <: CompleteLattice] {
 //      Console.println("taking out point: " + point + " worklist out: " + worklist);
 
       if ((lattice.bottom == out(point)) || output != out(point)) {
-//        Console.println("Output changed at " + point + " added to worklist: ")
-//        Console.println("\t" + worklist)
+//        Console.println("Output changed at " + point + " from: " + out(point) + " to: " + output + " and they are different: " + (output != out(point)))
         out(point) = output
         val succs = point.successors
         succs foreach { p =>
@@ -55,6 +54,13 @@ trait DataFlowAnalysis[L <: CompleteLattice] {
         }
       }
     }
+  } catch {
+    case e: NoSuchElementException =>
+      Console.println("in: " + in.mkString("", "\n", ""))
+      Console.println("out: " + out.mkString("", "\n", ""))
+      e.printStackTrace
+      Predef.error("Could not find element " + e.getMessage)
+  }
 
   /** ...
    *
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala
index 9f99e942fa..3b610e11bc 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala
@@ -26,39 +26,67 @@ abstract class ReachingDefinitions {
    */
   object rdefLattice extends CompleteLattice {
     type Definition = (Local, BasicBlock, Int)
-    type Elem = Set[Definition]
+    type Elem = (Set[Definition], Stack)
+    type StackPos = Set[(BasicBlock, Int)]
+    type Stack = List[StackPos]
 
-    val top: Elem = new ListSet[Definition]() {
+    val top: Elem = (new ListSet[Definition]() {
       override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]
-    }
+    }, Nil)
 
-    val bottom: Elem = new ListSet[Definition]() {
+    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
+      override def toString = "<bottom>"
+    }, Nil)
+
+    /** The least upper bound is set inclusion for locals, and pairwise set inclusion for stacks. */
+    def lub2(a: Elem, b: Elem): Elem =
+      if (bottom == a) b
+      else if (bottom == b) a
+      else {
+        val locals = a._1 incl b._1
+        val stack = if (a._2 == Nil)
+          b._2
+        else if (b._2 == Nil) a._2
+        else List.map2(a._2, b._2) (_ incl _)
+
+        val res = (locals, stack)
+
+//        Console.println("\tlub2: " + a + ", " + b)
+//        Console.println("\tis: " + res)
+
+//        if (res._1 eq bottom._1) (new ListSet[Definition], Nil)
+//        else res
+        res
+      }
   }
 
   class ReachingDefinitionsAnalysis extends DataFlowAnalysis[rdefLattice.type] {
     type P = BasicBlock
     val lattice = rdefLattice
     import lattice.Definition
+    import lattice.Stack
     import lattice.Elem
 
     var method: IMethod = _
 
     val gen: Map[BasicBlock, Set[Definition]] = new HashMap()
     val kill:Map[BasicBlock, Set[Local]]      = new HashMap()
+    val drops: Map[BasicBlock, Int]           = new HashMap()
+    val outStack: Map[BasicBlock, Stack]      = new HashMap()
 
     def init(m: IMethod): Unit = {
       this.method = m
-      gen.clear
-      kill.clear
+      gen.clear;   kill.clear
+      drops.clear; outStack.clear
 
       for (val b <- m.code.blocks.toList;
-           val (g, k) = genAndKill(b)) {
+           val (g, k) = genAndKill(b);
+           val (d, st) = dropsAndGen(b)) {
         gen  += b -> g
         kill += b -> k
+        drops += b -> d
+        outStack += b -> st
       }
 
       init {
@@ -67,6 +95,10 @@ abstract class ReachingDefinitions {
           in(b)  = lattice.bottom
           out(b) = lattice.bottom
         }
+        m.exh foreach { e =>
+          in(e.startBlock) = (new ListSet[Definition], List(new ListSet[(BasicBlock, Int)]))
+        }
+
       }
     }
 
@@ -84,6 +116,34 @@ abstract class ReachingDefinitions {
       (genSet, killSet)
     }
 
+    private def dropsAndGen(b: BasicBlock): (Int, List[Set[(BasicBlock, Int)]]) = {
+      var depth = 0
+      var drops = 0
+      var stackOut: List[Set[(BasicBlock, Int)]] = Nil
+
+      for (val (instr, idx) <- b.toList.zipWithIndex) {
+        if (instr == LOAD_EXCEPTION())
+          ()
+        else if (instr.consumed > depth) {
+          drops = drops + (instr.consumed - depth)
+          depth = 0
+          stackOut = Nil
+        } else {
+          stackOut = stackOut.drop(instr.consumed)
+          depth = depth - instr.consumed
+        }
+        var prod = instr.produced
+        depth = depth + prod
+        while (prod > 0) {
+          stackOut = (new collection.immutable.Set1((b, idx))) :: stackOut
+          prod = prod - 1
+        }
+      }
+//      Console.println("drops(" + b + ") = " + drops)
+//      Console.println("stackout(" + b + ") = " + stackOut)
+      (drops, stackOut)
+    }
+
     override def run: Unit = {
       forwardAnalysis(blockTransfer)
       if (settings.debug.value) {
@@ -100,20 +160,34 @@ abstract class ReachingDefinitions {
       (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)
+    private def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = {
+      var locals: Set[Definition] = (in._1 filter { case (l, _, _) => !kill(b)(l) }) incl gen(b)
+      if (locals eq lattice.bottom._1) locals = new ListSet[Definition]
+      (locals, outStack(b) ::: in._2.drop(drops(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 {
+      var locals = in._1
+      var stack  = in._2
+      val instr = b(idx)
+      instr match {
         case STORE_LOCAL(l1) =>
-          out = updateReachingDefinition(b, idx, out)
+          locals = updateReachingDefinition(b, idx, locals)
+          stack = stack.drop(instr.consumed)
+        case LOAD_EXCEPTION() =>
+          stack = Nil
         case _ =>
-          ()
+          stack = stack.drop(instr.consumed)
+      }
+
+      var prod = instr.produced
+      while (prod > 0) {
+        stack = (new collection.immutable.Set1((b, idx))) :: stack
+        prod = prod - 1
       }
 
-      out
+      (locals, stack)
     }
 
     override def toString: String = {
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
index 9d27858b0a..e7f4738b5e 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
@@ -43,10 +43,13 @@ abstract class TypeFlowAnalysis {
 
     override val top    = new TypeStack
     override val bottom = new TypeStack
+    val exceptionHandlerStack: TypeStack = new TypeStack(List(REFERENCE(definitions.AnyRefClass)))
 
     def lub2(s1: TypeStack, s2: TypeStack) = {
       if (s1 eq bottom) s2
       else if (s2 eq bottom) s1
+      else if (s1 eq exceptionHandlerStack) s1
+      else if (s2 eq exceptionHandlerStack) s2
       else {
         if (s1.length != s2.length)
           throw new CheckerError("Incompatible stacks: " + s1 + " and " + s2);
@@ -124,10 +127,7 @@ abstract class TypeFlowAnalysis {
           out(b) = typeFlowLattice.bottom
         }
         m.exh foreach { e =>
-          val stack = new TypeStack
-          stack.push(
-            REFERENCE(if (e.cls eq NoSymbol) definitions.ObjectClass else e.cls))
-          in(e.startBlock) = Pair(in(e.startBlock)._1, stack)
+          in(e.startBlock) = Pair(in(e.startBlock)._1, typeStackLattice.exceptionHandlerStack)
         }
       }
     }
@@ -146,8 +146,9 @@ abstract class TypeFlowAnalysis {
       }
     }
 
-    def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem =
+    def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = {
       b.toList.foldLeft(in)(interpret)
+    }
 
     /** Abstract interpretation for one instruction. */
     def interpret(in: typeFlowLattice.Elem, i: Instruction): typeFlowLattice.Elem = {
@@ -155,10 +156,10 @@ abstract class TypeFlowAnalysis {
       val bindings = out._1
       val stack = out._2
 
-/*      if (settings.debug.value) {
-        Console.println("Stack: " + stack);
-        Console.println(i);
-      } */
+//      if (settings.debug.value) {
+//        Console.println("Stack: " + stack);
+//        Console.println(i);
+//      }
       i match {
 
         case THIS(clasz) =>
@@ -319,6 +320,10 @@ abstract class TypeFlowAnalysis {
         case SCOPE_ENTER(_) | SCOPE_EXIT(_) =>
           ()
 
+        case LOAD_EXCEPTION() =>
+          stack.pop(stack.length)
+          stack.push(typeLattice.Object)
+
         case _ =>
           dump
           abort("Unknown instruction: " + i)
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
index 939238062c..97a101a1a9 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
@@ -132,9 +132,6 @@ abstract class GenJVM extends SubComponent {
     var remoteClass: Boolean = false
 
     def genClass(c: IClass): Unit = {
-      if (settings.debug.value)
-        log("Generating class " + c.symbol +
-            " flags: " + Flags.flagsToString(c.symbol.flags))
       clasz = c
       innerClasses = ListSet.empty
 
@@ -388,10 +385,7 @@ abstract class GenJVM extends SubComponent {
     }
 
     def genMethod(m: IMethod): Unit = {
-      if (settings.debug.value)
-        log("Generating method " + m.symbol +
-            " flags: " + Flags.flagsToString(m.symbol.flags) +
-            " owner: " + m.symbol.owner);
+      log("Generating method " + m.symbol.fullNameString)
       method = m
       endPC.clear
       computeLocalVarsIndex(m)
@@ -624,19 +618,20 @@ abstract class GenJVM extends SubComponent {
         ranges
       }
 
-      this.method.exh foreach ((e) => {
+      this.method.exh foreach { e =>
         ranges(e).sort({ (p1, p2) => p1._1 < p2._1 })
-        .foreach ((p) => {
-          if (settings.debug.value)
-            log("Adding exception handler " + e + "at block: " + e.startBlock + " for " + method +
-                " from: " + p._1 + " to: " + p._2 + " catching: " + e.cls);
-          jcode.addExceptionHandler(p._1, p._2,
-                                    labels(e.startBlock).getAnchor(),
-                                    if (e.cls == NoSymbol)
-                                      null
-                                    else javaName(e.cls))
-        })
-      });
+        .foreach { p =>
+          if (p._1 < p._2) {
+            if (settings.debug.value)
+              log("Adding exception handler " + e + "at block: " + e.startBlock + " for " + method +
+                  " from: " + p._1 + " to: " + p._2 + " catching: " + e.cls);
+            jcode.addExceptionHandler(p._1, p._2,
+                                      labels(e.startBlock).getAnchor(),
+                                      if (e.cls == NoSymbol) null else javaName(e.cls))
+          } else
+            log("Empty exception range: " + p)
+        }
+      }
     }
 
     /** local variables whose scope appears in this block. */
@@ -998,6 +993,9 @@ abstract class GenJVM extends SubComponent {
               b.varsInScope -= lv
             } else
               assert(false, "Illegal local var nesting: " + method)
+
+          case LOAD_EXCEPTION() =>
+            ()
         }
 
         crtPC = jcode.getPC()
diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
index 9bdd2f64e9..b13656353a 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
@@ -115,7 +115,7 @@ abstract class ClosureElimination extends SubComponent {
 
               }
 
-            case LOAD_FIELD(f, false) =>
+            case LOAD_FIELD(f, false) if accessible(f, m.symbol) =>
               info.stack(0) match {
                 case r @ Record(cls, bindings) if bindings.isDefinedAt(f) =>
                   info.getLocalForField(r, f) match {
@@ -151,6 +151,7 @@ abstract class ClosureElimination extends SubComponent {
       case e: LubError =>
         Console.println("In method: " + m);
         Console.println(e);
+        e.printStackTrace
     }
 
     /* Partial mapping from values to instructions that load them. */
@@ -162,6 +163,13 @@ abstract class ClosureElimination extends SubComponent {
         THIS(definitions.ObjectClass)
     }
 
+    /** is field 'f' accessible from method 'm'? */
+    def accessible(f: Symbol, m: Symbol): Boolean =
+      f.isPublic || (f.hasFlag(Flags.PROTECTED) && (enclPackage(f) == enclPackage(m)))
+
+    private def enclPackage(sym: Symbol): Symbol =
+      if ((sym == NoSymbol) || sym.isPackageClass) sym else enclPackage(sym.owner)
+
   } /* class ClosureElim */
 
 
@@ -191,7 +199,6 @@ abstract class ClosureElimination extends SubComponent {
         while (t != Nil) {
           peep(h, t.head) match {
             case Some(newInstrs) =>
-            	Console.println("Replacing " + h + " : " + t.head + " by " + newInstrs);
               newInstructions = seen.reverse ::: newInstrs ::: t.tail;
               redo = true;
             case None =>
diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
index a2818d08f0..28fcda23b2 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
@@ -41,34 +41,55 @@ abstract class DeadCodeElimination extends SubComponent {
   class DeadCode {
     def analyzeClass(cls: IClass): Unit =
       cls.methods.foreach { m =>
+        this.method = m
 //        analyzeMethod(m);
-	collectRDef(m)
+	dieCodeDie(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
+    val worklist: mutable.Set[(BasicBlock, Int)] = new mutable.LinkedHashSet
+
+    /** what instructions have been marked as useful? */
+    val useful: mutable.Map[BasicBlock, mutable.BitSet] = new mutable.HashMap
+
+    /** the current method. */
+    var method: IMethod = _
+
+    def dieCodeDie(m: IMethod): Unit = if (m.code ne null) {
+      log("dead code elimination on " + m);
+//      (new DepthFirstLinerizer).linearize(m)
+      m.code.blocks.clear
+      m.code.blocks ++= linearizer.linearize(m)
+      collectRDef(m)
+      mark
+      sweep(m)
+    }
 
     /** 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
+      defs = HashMap.empty; worklist.clear; useful.clear;
       rdef.init(m);
       rdef.run;
 
       for (val bb <- m.code.blocks.toList) {
+        useful(bb) = new mutable.BitSet(bb.size)
         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 LOAD_LOCAL(l) =>
+              defs = defs + ((bb, idx)) -> rd._1
+//              Console.println(i + ": " + (bb, idx) + " rd: " + rd + " and having: " + defs)
+            case RETURN(_) | JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) |
+                 DROP(_) | THROW()   | STORE_FIELD(_, _) | STORE_ARRAY_ITEM(_) |
+                 LOAD_EXCEPTION() | SWITCH(_, _) | MONITOR_ENTER() | MONITOR_EXIT() => worklist += ((bb, idx))
+            case CALL_METHOD(m1, _) if isSideEffecting(m1) => worklist += ((bb, idx))
+            case CALL_METHOD(m1, SuperCall(_)) =>
+              worklist += ((bb, idx)) // super calls to constructor
             case _ => ()
           }
           rd = rdef.interpret(bb, idx, rd);
@@ -80,81 +101,155 @@ abstract class DeadCodeElimination extends SubComponent {
      *  dependecies are marked useful too, and added to the worklist.
      */
     def mark {
+//      log("Starting with worklist: " + worklist)
       while (!worklist.isEmpty) {
         val (bb, idx) = worklist.elements.next
         worklist -= ((bb, idx))
+        if (settings.debug.value)
+          log("Marking instr: \tBB_" + bb + ": " + idx + " " + 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))
+        if (!useful(bb)(idx)) {
+          useful(bb) += idx
+          instr match {
+            case LOAD_LOCAL(l1) =>
+              for (val (l2, bb1, idx1) <- defs((bb, idx)); l1 == l2; !useful(bb1)(idx1))
+                worklist += ((bb1, idx1))
+
+            case nw @ NEW(_) =>
+              assert(nw.init ne null, "null new.init at: " + bb + ": " + idx + "(" + instr + ")")
+              worklist += findInstruction(bb, nw.init)
+
+            case LOAD_EXCEPTION() =>
+              ()
+
+            case _ =>
+              for (val (bb1, idx1) <- findDefs(bb, idx, instr.consumed); !useful(bb1)(idx1))
+                worklist += ((bb1, idx1))
+          }
         }
       }
     }
 
-    def analyzeMethod(m: IMethod): Unit = if (m.code ne null) {
-      log("DCE on " + m);
-      a.init(m);
-      a.run;
+    def sweep(m: IMethod) {
+      val compensations = computeCompensations(m)
 
       for (val bb <- m.code.blocks.toList) {
-        var live = a.out(bb);
-        for (val Pair(i, pos) <- bb.toList.zipWithIndex.reverse) {
-          i match {
-            case STORE_LOCAL(l) if (!live(l)) =>
-              removeDefUse(bb, i);
-            case _ => ()
+//        Console.println("** Sweeping block " + bb + " **")
+        val oldInstr = bb.toList
+        bb.open
+        bb.clear
+        for (val Pair(i, idx) <- oldInstr.zipWithIndex) {
+          if (useful(bb)(idx)) {
+//            log(" " + i + " is useful")
+            bb.emit(i, i.pos)
+            compensations.get(bb, idx) match {
+              case Some(is) => is foreach bb.emit
+              case None => ()
+            }
+          } else {
+            i match {
+              case NEW(REFERENCE(sym)) =>
+                log("skipped object creation: " + sym)
+                //Console.println("skipping class file altogether: " + sym.fullNameString)
+                icodes.classes -= sym
+              case _ => ()
+            }
+            log("Skipped: bb_" + bb + ": " + idx + "( " + i + ")")
           }
-          live = a.interpret(live, i);
         }
+
+        if (bb.size > 0)
+          bb.close
+        else
+          log("empty block encountered")
       }
     }
 
-    /** Remove a pair def-use, if safe to do so. The `use' is given by index
-     *  in the basic block. The `def' is the closest previous instruction which
-     *  produced the top value on the stack.
-     */
-    def removeDefUse(bb: BasicBlock, use: Instruction): Unit = {
-      val usePos = bb.indexOf(use)
-      bb.findDef(usePos) match {
-        case Some(defPos) =>
-          val definition = bb(defPos);
-          if (isSafeToRemove(definition)) {
-            log("Removing instructions at BB " + bb + " def: " + definition + ", use: " + use);
-
-            if (definition.consumed == 0) {
-              bb.removeInstructionsAt(defPos, usePos)
-            } else {
-              bb.removeInstructionsAt(usePos);
-              bb.replaceInstruction(definition, definition.consumedTypes map DROP);
+    private def computeCompensations(m: IMethod): mutable.Map[(BasicBlock, Int), List[Instruction]] = {
+      val compensations: mutable.Map[(BasicBlock, Int), List[Instruction]] = new mutable.HashMap
+
+      for (val bb <- m.code.blocks.toList) {
+        assert(bb.isClosed, "Open block in computeCompensations")
+        for (val (i, idx) <- bb.toList.zipWithIndex) {
+          if (!useful(bb)(idx)) {
+            val defs = findDefs(bb, idx, i.consumed)
+            for (val d <- defs) {
+              if (!compensations.isDefinedAt(d))
+                compensations(d) = i.consumedTypes map DROP
             }
           }
-        case None =>
-          bb.replaceInstruction(use, use.consumedTypes map DROP);
-          log("Replaced dead " + use + " by DROP in bb " + bb);
+        }
       }
+      compensations
     }
 
-    /** Is 'sym' a side-effecting method? TODO: proper analysis.  */
-    private def isSideEffecting(sym: Symbol): Boolean = {
-      sym.isClassConstructor // for testing only
+    private def withClosed[a](bb: BasicBlock)(f: => a): a = {
+      if (bb.size > 0) bb.close
+      val res = f
+      if (bb.size > 0) bb.open
+      res
     }
 
-    def isSafeToRemove(i: Instruction): Boolean = i match {
-/*      case LOAD_LOCAL(l) => true
-      case LOAD_FIELD(_, _) => true
-      case THIS(_) => true
-*/
-      case CALL_METHOD(m, style) =>
-        (m.isClassConstructor &&
-         definitions.refClass.values.contains(m.owner));
-      case _ => true;
+    private def findInstruction(bb: BasicBlock, i: Instruction): (BasicBlock, Int) = {
+      def find(bb: BasicBlock): Option[(BasicBlock, Int)] = {
+        var xs = bb.toList
+        xs.zipWithIndex find { hd => hd._1 eq i } match {
+          case Some(_, idx) => Some(bb, idx)
+          case None => None
+        }
+      }
+
+      for (val b <- linearizer.linearizeAt(method, bb))
+        find(b) match {
+          case Some(p) => return p
+          case None => ()
+        }
+      abort("could not find init in: " + method)
     }
 
+    def findDefs(bb: BasicBlock, idx: Int, m: Int): List[(BasicBlock, Int)] = if (idx > 0) {
+      assert(bb.isClosed)
+      var instrs = bb.getArray
+      var res: List[(BasicBlock, Int)] = Nil
+      var i = idx
+      var n = m
+      var d = 0
+      // "I look for who produced the 'n' elements below the 'd' topmost slots of the stack"
+      while (n > 0 && i > 0) {
+        i = i - 1
+        val prod = instrs(i).produced
+        if (prod > d) {
+          res = (bb, i) :: res
+          n   = n - (prod - d)
+          if (bb(i) != LOAD_EXCEPTION)
+            d = instrs(i).consumed
+        } else {
+          d = d - prod
+          d = d + instrs(i).consumed;
+        }
+      }
+
+      if (n > 0) {
+        val stack = rdef.in(bb)._2
+        assert(stack.length >= n, "entry stack is too small, expected: " + n + " found: " + stack)
+        stack.drop(d).take(n) foreach { defs =>
+          res = defs.toList ::: res
+        }
+      }
+      res
+    } else {
+      val stack = rdef.in(bb)._2
+      assert(stack.length >= m, "entry stack is too small, expected: " + m + " found: " + stack)
+      stack.take(m) flatMap (.toList)
+    }
+
+    /** Is 'sym' a side-effecting method? TODO: proper analysis.  */
+    private def isSideEffecting(sym: Symbol): Boolean = {
+      !(sym.isGetter // for testing only
+       || (sym.isConstructor
+           && sym.owner.owner == definitions.getModule("scala.runtime").moduleClass)
+       || (sym.isConstructor && inliner.isClosureClass(sym.owner)))
+    }
   } /* DeadCode */
 }
diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
index 31d648e129..a98bb82155 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
@@ -20,6 +20,9 @@ abstract class Inliners extends SubComponent {
 
   val phaseName = "inliner";
 
+  /** The maximum size in basic blocks of methods considered for inlining. */
+  final val MAX_INLINE_SIZE = 16
+
   /** Create a new phase */
   override def newPhase(p: Phase) = new InliningPhase(p);
 
@@ -63,7 +66,11 @@ abstract class Inliners extends SubComponent {
                instr:  Instruction,
                callee: IMethod): Unit = {
        log("Inlining " + callee + " in " + caller + " at pos: " +
-           classes(caller.symbol.owner).cunit.position(instr.pos));
+           (try {
+             classes(caller.symbol.owner).cunit.position(instr.pos).toString
+           } catch {
+             case _ => "<nopos>"
+           }));
 
        val targetPos = instr.pos;
        val a = new analysis.MethodTFA(callee);
@@ -99,7 +106,7 @@ abstract class Inliners extends SubComponent {
        /** Add a new block in the current context. */
        def newBlock = {
          val b = caller.code.newBlock;
-         activeHandlers.foreach (.addBlock(b));
+         activeHandlers.foreach (.addCoveredBlock(b));
          if (retVal ne null) b.varsInScope += retVal
          b.varsInScope += inlinedThis
          b.varsInScope ++= varsInScope
@@ -131,8 +138,12 @@ abstract class Inliners extends SubComponent {
 
        val afterBlock = newBlock;
 
+       /** Map from nw.init instructions to their matching NEW call */
+       val pending: collection.jcl.Map[Instruction, NEW] = new collection.jcl.HashMap
+
        /** Map an instruction from the callee to one suitable for the caller. */
-       def map(i: Instruction): Instruction = i match {
+       def map(i: Instruction): Instruction = {
+         val newInstr = i match {
            case THIS(clasz) =>
              LOAD_LOCAL(inlinedThis);
 
@@ -172,8 +183,23 @@ abstract class Inliners extends SubComponent {
            case SCOPE_EXIT(l) if inlinedLocals.isDefinedAt(l) =>
              SCOPE_EXIT(inlinedLocals(l))
 
+           case nw @ NEW(sym) =>
+             val r = NEW(sym)
+             pending(nw.init) = r
+             r
+
+           case CALL_METHOD(meth, Static(true)) if (meth.isClassConstructor) =>
+             CALL_METHOD(meth, Static(true))
+
            case _ => i
          }
+         // check any pending NEW's
+         if (pending isDefinedAt i) {
+           pending(i).init = newInstr.asInstanceOf[CALL_METHOD]
+           pending -= i
+         }
+         newInstr
+       }
 
        addLocals(caller, callee.locals map dupLocal);
        addLocal(caller, inlinedThis);
@@ -233,6 +259,7 @@ abstract class Inliners extends SubComponent {
 
        // add exception handlers of the callee
        caller.exh = (callee.exh map translateExh) ::: caller.exh;
+       assert(pending.isEmpty, "Pending NEW elements: " + pending)
      }
 
     val InlineAttr = if (settings.inline.value) try {
@@ -254,11 +281,14 @@ abstract class Inliners extends SubComponent {
       var retry = false;
       var count = 0;
       fresh.clear
+      // how many times have we already inlined this method here?
+      val inlinedMethods: Map[Symbol, Int] = new HashMap[Symbol, Int] {
+        override def default(k: Symbol) = 0
+      }
 
       do {
         retry = false;
         if (m.code ne null) {
-//          this.count = 0;
           if (settings.debug.value)
             log("Analyzing " + m + " count " + count);
           tfa.init(m);
@@ -280,7 +310,9 @@ abstract class Inliners extends SubComponent {
                         log("" + i + " has actual receiver: " + receiver);
                     }
                     if (settings.debug.value)
-                      log("Treating " + i);
+                      log("Treating " + i
+                          + "\n\tclasses.contains: " + classes.contains(receiver)
+                          + "\n\tconcreteMethod.isFinal: " + concreteMethod.isFinal);
 
                     if (   classes.contains(receiver)
                         && (isClosureClass(receiver)
@@ -288,16 +320,28 @@ abstract class Inliners extends SubComponent {
                             || msym.attributes.exists(a => a.atp == InlineAttr))) {
                       classes(receiver).lookupMethod(concreteMethod) match {
                         case Some(inc) =>
-                          if (inc != m && (inc.code ne null)
+                          if (inc.symbol != m.symbol
+                              && (inlinedMethods(inc.symbol) < 2)
+                              && (inc.code ne null)
+                              && shouldInline(m, inc)
+                              && (inc.code.blocks.length <= MAX_INLINE_SIZE)
                               && isSafeToInline(m, inc, info._2)) {
                             retry = true;
                             if (!isClosureClass(receiver)) // only count non-closures
                                 count = count + 1;
                             inline(m, bb, i, inc);
+                            inlinedMethods(inc.symbol) = inlinedMethods(inc.symbol) + 1
 
                             /* Remove this method from the cache, as the calls-private relation
                                might have changed after the inlining. */
                             callsPrivate -= m;
+                          } else {
+                            if (settings.debug.value)
+                              log("inline failed because:\n\tinc.symbol != m.symbol: " + (inc.symbol != m.symbol)
+                                  + "\n\t(inlinedMethods(inc.symbol) < 2): " + (inlinedMethods(inc.symbol) < 2)
+                                  + "\n\tinc.code ne null: " + (inc.code ne null)
+                                  + "\n\tinc.code.blocks.length < MAX_INLINE_SIZE: " + (inc.code.blocks.length < MAX_INLINE_SIZE) + "(" + inc.code.blocks.length + ")"
+                                  + "\n\tisSafeToInline(m, inc, info._2): " + isSafeToInline(m, inc, info._2));
                           }
                         case None =>
                           ();
@@ -320,30 +364,25 @@ abstract class Inliners extends SubComponent {
         throw e;
     }
 
-    def isClosureClass(cls: Symbol): Boolean = {
-      val res =
-        cls.isFinal &&
-        cls.tpe.parents.exists { t =>
-          val TypeRef(_, sym, _) = t;
-          definitions.FunctionClass exists sym.==
-        }
-      res
-    }
-
     /** Cache whether a method calls private members. */
     val callsPrivate: Map[IMethod, Boolean] = new HashMap;
 
+    def isRecursive(m: IMethod): Boolean = m.recursive
+
     /** A method is safe to inline when:
      *    - it does not contain calls to private methods when
      *      called from another class
      *    - it is not inlined into a position with non-empty stack,
      *      while having a top-level finalizer (see liftedTry problem)
+     *    - it is not recursive
      * Note:
      *    - synthetic private members are made public in this pass.
      */
     def isSafeToInline(caller: IMethod, callee: IMethod, stack: TypeStack): Boolean = {
       var callsPrivateMember = false;
 
+      if (callee.recursive) return false;
+
       callsPrivate get (callee) match {
         case Some(b) => callsPrivateMember = b;
         case None =>
@@ -382,7 +421,8 @@ abstract class Inliners extends SubComponent {
         return false;
 
       if (stack.length > (1 + callee.symbol.info.paramTypes.length) &&
-          (callee.exh exists (.covered.contains(callee.code.startBlock)))) {
+          callee.exh != Nil) {
+//          (callee.exh exists (.covered.contains(callee.code.startBlock)))) {
         if (settings.debug.value) log("method " + callee.symbol + " is used on a non-empty stack with finalizer.");
         false
       } else
@@ -390,4 +430,41 @@ abstract class Inliners extends SubComponent {
     }
 
   } /* class Inliner */
+
+  def isClosureClass(cls: Symbol): Boolean = {
+    val res =
+      cls.isFinal &&
+      cls.tpe.parents.exists { t =>
+        val TypeRef(_, sym, _) = t;
+        definitions.FunctionClass exists sym.==
+      }
+    res
+  }
+
+  /** small method size (in blocks) */
+  val SMALL_METHOD_SIZE = 4
+
+  /** Decide whether to inline or not. Heuristics:
+   *   - it's bad to make the caller larger (> SMALL_METHOD_SIZE)
+   *        if it was small
+   *   - it's good to inline higher order functions
+   *   - it's good to inline closures functions.
+   *   - it's bad (useless) to inline inside bridge methods
+   */
+  def shouldInline(caller: IMethod, callee: IMethod): Boolean = {
+     if (caller.symbol.hasFlag(Flags.BRIDGE)) return false;
+
+     var score = 0
+     if (callee.code.blocks.length <= SMALL_METHOD_SIZE) score = score + 1
+     if (caller.code.blocks.length <= SMALL_METHOD_SIZE
+         && (caller.code.blocks.length + callee.code.blocks.length) < SMALL_METHOD_SIZE)
+       score = score - 1
+
+     if (callee.symbol.tpe.paramTypes.exists(definitions.isFunctionType))
+       score = score + 2
+     if (isClosureClass(callee.symbol.owner))
+       score = score + 2
+
+     score > 0
+   }
 } /* class Inliners */
diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala
index 66bdf9dfd1..166c455dff 100644
--- a/src/compiler/scala/tools/nsc/symtab/Types.scala
+++ b/src/compiler/scala/tools/nsc/symtab/Types.scala
@@ -2560,15 +2560,15 @@ trait Types requires SymbolTable {
           if (lubType.decls.isEmpty) lubBase else lubType
         }
     }
-    if (settings.debug.value) {
-      log(indent + "lub of " + ts + " at depth "+depth)//debug
-      indent = indent + "  "
-    }
+//    if (settings.debug.value) {
+//      log(indent + "lub of " + ts + " at depth "+depth)//debug
+//      indent = indent + "  "
+//    }
     val res = lub0(ts)
-    if (settings.debug.value) {
-      indent = indent.substring(0, indent.length() - 2)
-      log(indent + "lub of " + ts + " is " + res)//debug
-    }
+//    if (settings.debug.value) {
+//      indent = indent.substring(0, indent.length() - 2)
+//      log(indent + "lub of " + ts + " is " + res)//debug
+//    }
     res
   }
 
diff --git a/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala b/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala
index c5f1e2115c..320b9a6286 100644
--- a/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala
+++ b/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala
@@ -587,7 +587,7 @@ abstract class ICodeReader extends ClassfileParser {
     def toBasicBlock: Code = {
       import opcodes._
 
-      val code = new Code(method.symbol.name.toString);
+      val code = new Code(method.symbol.name.toString, method);
       method.setCode(code)
       var bb = code.startBlock
 
diff --git a/src/library/scala/List.scala b/src/library/scala/List.scala
index 73d633515a..b6723b5517 100644
--- a/src/library/scala/List.scala
+++ b/src/library/scala/List.scala
@@ -666,7 +666,7 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @param f function to apply to each element.
    *  @return <code>[f(a0), ..., f(an)]</code> if this list is <code>[a0, ..., an]</code>.
    */
-  override def map[b](f: a => b): List[b] = {
+  final override def map[b](f: a => b): List[b] = {
     val b = new ListBuffer[b]
     var these = this
     while (!these.isEmpty) {
@@ -696,7 +696,7 @@ sealed abstract class List[+a] extends Seq[a] {
    *
    *  @param f the treatment to apply to each element.
    */
-  override def foreach(f: a => Unit): Unit = {
+  final override def foreach(f: a => Unit): Unit = {
     var these = this
     while (!these.isEmpty) {
       f(these.head)
@@ -710,7 +710,7 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @param p the predicate used to filter the list.
    *  @return the elements of this list satisfying <code>p</code>.
    */
-  override def filter(p: a => Boolean): List[a] = {
+  final override def filter(p: a => Boolean): List[a] = {
     // return same list if all elements satisfy p
     var these = this
     while (!these.isEmpty && p(these.head)) {
@@ -964,7 +964,7 @@ sealed abstract class List[+a] extends Seq[a] {
    *  @return  <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
    *           this list is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>.
    */
-  override def flatMap[b](f: a => Iterable[b]): List[b] = {
+  final override def flatMap[b](f: a => Iterable[b]): List[b] = {
     val b = new ListBuffer[b]
     var these = this
     while (!these.isEmpty) {