10 files changed, 360 insertions, 17 deletions

diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala
index 7ab7d5872a..12c1a80f02 100644
--- a/src/compiler/scala/tools/nsc/Global.scala
+++ b/src/compiler/scala/tools/nsc/Global.scala
@@ -26,7 +26,7 @@ import transform._
 import backend.icode.{ICodes, GenICode, Checkers}
 import backend.ScalaPrimitives
 import backend.jvm.GenJVM
-import backend.opt.{Inliners, ClosureElimination}
+import backend.opt.{Inliners, ClosureElimination, DeadCodeElimination}
 import backend.icode.analysis._
 
 class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable
@@ -99,7 +99,7 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable
   def inform(msg: String) = System.err.println(msg)
   def inform[T](msg: String, value: T): T = { inform(msg+value); value }
 
-    //reporter.info(null, msg, true);
+  //reporter.info(null, msg, true);
   def informProgress(msg: String) =
     if (settings.verbose.value) inform("[" + msg + "]")
 
@@ -311,7 +311,11 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable
     val global: Global.this.type = Global.this
   }
 
-  object closser extends ClosureElimination {
+  object closureElimination extends ClosureElimination {
+    val global: Global.this.type = Global.this
+  }
+
+  object deadCode extends DeadCodeElimination {
     val global: Global.this.type = Global.this
   }
 
@@ -344,7 +348,8 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable
     cleanup,
     genicode,
     inliner,
-    closser,
+    closureElimination,
+    deadCode,
     genJVM,
     sampleTransform);
 
@@ -416,10 +421,10 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable
 
     override val terminalPhase : Phase =
       if (onlyPresentation) typerPhase.next.next
-      else new GlobalPhase(p) {
+      else /* new GlobalPhase(p) {
         def name = "terminal"
         def apply(unit: CompilationUnit): unit = {}
-      }
+      }*/ p;
 
     private def addUnit(unit: CompilationUnit): unit = {
       unitbuf += unit
diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala
index e54c051d11..8721d377e0 100644
--- a/src/compiler/scala/tools/nsc/Settings.scala
+++ b/src/compiler/scala/tools/nsc/Settings.scala
@@ -112,6 +112,7 @@ class Settings(error: String => unit) {
 
   val inline        = BooleanSetting("-Xinline", "Perform inlining when possible")
   val Xcloselim     = BooleanSetting("-Xcloselim", "Perform closure elimination")
+  val Xdce          = BooleanSetting("-Xdce", "Perform dead code elimination")
   val Xshowcls      = StringSetting ("-Xshowcls", "class", "Show class info", "")
   val Xshowobj      = StringSetting ("-Xshowobj", "object", "Show object info", "")
   val Xshowicode    = BooleanSetting("-Xshowicode", "Print the generated ICode")
diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
index 5209fde3cb..df0a85a0bb 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
@@ -87,6 +87,29 @@ trait BasicBlocks requires ICodes {
       else
         instructionList.length;
 
+    /** Return the index of the instruction which produced the value
+	   *  consumed by the given instruction. */
+    def findDef(pos: Int): Option[Int] = {
+      assert(closed);
+      var i = pos;
+      var d = 0;
+      while (i > 0 && d >= 0) {
+        i = i - 1;
+        d = d + (instrs(i).consumed - instrs(i).produced);
+      }
+      if (i >= 0)
+        Some(i)
+      else
+        None
+    }
+
+    /** Return the n-th instruction. */
+    def apply(n: Int): Instruction = {
+      if (closed)
+        instrs(n)
+      else
+        instructionList.reverse(n)
+    }
 
     ///////////////////// Substitutions ///////////////////////
 
@@ -146,6 +169,23 @@ trait BasicBlocks requires ICodes {
       changed
     }
 
+    /** Remove instructions found at the given positions. */
+    def removeInstructionsAt(positions: Int*): Unit = {
+      assert(closed);
+      val removed = positions.toList;
+      val newInstrs = new Array[Instruction](instrs.length - positions.length);
+      var i = 0;
+      var j = 0;
+      while (i < instrs.length) {
+        if (!removed.contains(i)) {
+          newInstrs(j) = instrs(i);
+          j = j + 1;
+        }
+        i = i + 1;
+      }
+      instrs = newInstrs;
+    }
+
     /** Replace all instructions found in the map. */
     def subst(map: Map[Instruction, Instruction]) =
       if (!closed) substOnList(map) else {
diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
index 9863b54417..b16e9a9893 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
@@ -11,6 +11,7 @@ import java.io.PrintWriter;
 
 import scala.tools.nsc.symtab._;
 import scala.collection.mutable.HashMap;
+import analysis.Liveness;
 
 /** Glue together ICode parts.
  */
@@ -68,16 +69,16 @@ abstract class ICodes extends AnyRef
          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) }) */) {
-        Console.println("Block " + b + ".lastInstruction" + b.lastInstruction);
-        Console.println(" has successors: " + b.successors + " and succ has pred: " + succ.predecessors);
-        //yield Pair(b, succ)
-      }
-//    Console.println("Mergeable: " + mergeablePairs.mkString("", "\n", ""));
+         succ.predecessors.head == b;
+         !(m.exh.contains { (e: ExceptionHandler) => e.covers(b) && !e.covers(succ) }))
+        yield Pair(b, succ)
     ()
   }
 
+  object liveness extends Liveness {
+    val global: ICodes.this.global.type = ICodes.this.global;
+  }
+
   def init = { }
 }
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
index ea280b6fd2..856e91283b 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala
@@ -62,6 +62,12 @@ trait Opcodes requires ICodes {
     /** This abstract method returns the number of produced elements on the stack */
     def produced : Int = 0;
 
+    /** This instruction consumes these types from the top of the stack. */
+    def consumedTypes: List[TypeKind] = Nil;
+
+    /** This instruction produces these types on top of the stack. */
+    def producedTypes: List[TypeKind] = Nil;
+
     /** This method returns the difference of size of the stack when the instruction is used */
     def difference = produced-consumed;
 
@@ -71,7 +77,7 @@ trait Opcodes requires ICodes {
 
   object opcodes {
 
-    /** Loads the "this" references on top of the stack.
+    /** Loads "this" on top of the stack.
      * Stack: ...
      *    ->: ...:ref
      */
@@ -81,6 +87,8 @@ trait Opcodes requires ICodes {
 
       override def consumed = 0;
       override def produced = 1;
+
+      override def producedTypes = List(REFERENCE(clasz));
     }
 
     /** Loads a constant on the stack.
@@ -93,6 +101,8 @@ trait Opcodes requires ICodes {
 
       override def consumed = 0;
       override def produced = 1;
+
+      override def producedTypes = List(toTypeKind(constant.tpe));
     }
 
     /** Loads an element of an array. The array and the index should
@@ -106,6 +116,9 @@ trait Opcodes requires ICodes {
 
       override def consumed = 2;
       override def produced = 1;
+
+      override def consumedTypes = List(ARRAY(kind), INT);
+      override def producedTypes = List(kind);
     }
 
     /** Load a local variable on the stack. It can be a method argument.
@@ -118,6 +131,8 @@ trait Opcodes requires ICodes {
 
       override def consumed = 0;
       override def produced = 1;
+
+      override def producedTypes = List(local.kind);
     }
 
     /** Load a field on the stack. The object to which it refers should be
@@ -132,6 +147,9 @@ trait Opcodes requires ICodes {
 
       override def consumed = if(isStatic) 0 else 1;
       override def produced = 1;
+
+      override def consumedTypes = if (isStatic) Nil else List(REFERENCE(field.owner));
+      override def producedTypes = List(toTypeKind(field.tpe));
     }
 
     case class LOAD_MODULE(module: Symbol) extends Instruction {
@@ -143,6 +161,8 @@ trait Opcodes requires ICodes {
 
       override def consumed = 0;
       override def produced = 1;
+
+      override def producedTypes = List(REFERENCE(module));
     }
 
     /** Store a value into an array at a specified index.
@@ -155,6 +175,8 @@ trait Opcodes requires ICodes {
 
       override def consumed = 3;
       override def produced = 0;
+
+      override def consumedTypes = List(ARRAY(kind), INT, kind);
     }
 
     /** Store a value into a local variable. It can be an argument.
@@ -167,6 +189,8 @@ trait Opcodes requires ICodes {
 
       override def consumed = 1;
       override def produced = 0;
+
+      override def consumedTypes = List(local.kind);
     }
 
     /** Store a value into a field.
@@ -180,6 +204,12 @@ trait Opcodes requires ICodes {
 
       override def consumed = if(isStatic) 1 else 2;
       override def produced = 0;
+
+      override def consumedTypes =
+        if (isStatic)
+          List(toTypeKind(field.tpe))
+        else
+          List(REFERENCE(field.owner), toTypeKind(field.tpe));
     }
 
     /** Call a primitive function.
@@ -206,7 +236,38 @@ trait Opcodes requires ICodes {
         case EndConcat => 1;
       }
       override def produced = 1;
-    }
+
+      override def consumedTypes = primitive match {
+        case Negation(kind) => List(kind);
+        case Test(_, kind, true) => List(kind);
+        case Test(_, kind, false) => List(kind, kind);
+        case Comparison(_, kind) => List(kind, kind);
+        case Arithmetic(NOT, kind) => List(kind);
+        case Arithmetic(_, kind) => List(kind, kind);
+        case Logical(_, kind) => List(kind, kind);
+        case Shift(_, kind) => List(kind, INT);
+        case Conversion(from, _) => List(from);
+        case ArrayLength(kind) => List(ARRAY(kind));
+        case StringConcat(kind) => List(ConcatClass, kind);
+        case StartConcat => Nil;
+        case EndConcat => List(ConcatClass);
+      }
+
+      override def producedTypes = primitive match {
+        case Negation(kind) => List(kind);
+        case Test(_, _, true) => List(BOOL);
+        case Test(_, _, false) => List(BOOL);
+        case Comparison(_, _) => List(INT);
+        case Arithmetic(_, kind) => List(kind);
+        case Logical(_, kind) => List(kind);
+        case Shift(_, kind) => List(kind);
+        case Conversion(_, to) => List(to);
+        case ArrayLength(_) => List(INT);
+        case StringConcat(_) => List(ConcatClass);
+        case StartConcat => List(ConcatClass);
+        case EndConcat => List(REFERENCE(global.definitions.StringClass));
+      }
+   }
 
     /** This class represents a CALL_METHOD instruction
      * STYLE: dynamic / static(StaticInstance)
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 9585c929dc..36e10d6366 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala
@@ -15,5 +15,5 @@ trait CompleteLattice {
   def bottom: Elem;
 
   /** Compute the least upper bound of a list of elements. */
-  def lub(xs: List[Elem]): Elem =  xs reduceLeft lub2;
+  def lub(xs: List[Elem]): Elem = if (xs == Nil) bottom else xs reduceLeft lub2;
 }
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 4c18086d13..1dfe643afd 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala
@@ -42,4 +42,21 @@ trait DataFlowAnalysis[L <: CompleteLattice] {
       }
     }
   }
+
+  def backwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = {
+    while (!worklist.isEmpty) {
+      val point = worklist.elements.next; worklist -= point;
+
+      out(point) = lattice.lub(point.successors map in.apply);
+      val input = f(point, out(point));
+
+      if (in(point) == (lattice.bottom) || input != in(point)) {
+        in(point) = input;
+        point.predecessors foreach { p =>
+          if (!worklist.contains(p))
+            worklist += p;
+        }
+      }
+    }
+  }
 }
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala
new file mode 100644
index 0000000000..dfaf52a24c
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala
@@ -0,0 +1,109 @@
+package scala.tools.nsc.backend.icode.analysis;
+
+import scala.collection.mutable.{HashMap, Map}
+import scala.collection.immutable.{Set, ListSet}
+
+/**
+ * Compute liveness information for local variables.
+ */
+abstract class Liveness {
+  val global: Global;
+  import global._;
+  import icodes._;
+
+  /** The lattice for this analysis.   */
+  object livenessLattice extends CompleteLattice {
+		type Elem = Set[Local];
+
+    val top: Elem = new ListSet[Local]() {
+      override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef];
+    }
+
+    val bottom: Elem = new ListSet[Local]() {
+      override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef];
+    }
+
+    def lub2(a: Elem, b: Elem): Elem = a incl b;
+  }
+
+  final class LivenessAnalysis extends DataFlowAnalysis[livenessLattice.type] {
+    type P = BasicBlock;
+    val lattice = livenessLattice;
+
+    var method: IMethod = _;
+
+    val gen: Map[BasicBlock, Set[Local]] = new HashMap();
+    val kill:Map[BasicBlock, Set[Local]] = new HashMap();
+
+    def init(m: IMethod): Unit = {
+      this.method = m;
+
+      for (val b <- m.code.blocks.toList;
+           val Pair(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._;
+
+    /** Return the gen and kill sets for this block. */
+    def genAndKill(b: BasicBlock): Pair[Set[Local], Set[Local]] = {
+			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 _ => ();
+      }
+      Pair(genSet, killSet)
+    }
+
+    override def run: Unit = {
+      backwardAnalysis(blockTransfer);
+      if (settings.debug.value) {
+        linearizer.linearize(method).foreach(b => if (b != method.code.startBlock)
+          assert(in(b) != lattice.bottom,
+            "Block " + b + " in " + this.method + " has input equal to bottom -- not visited?"));
+      }
+    }
+
+    def blockTransfer(b: BasicBlock, out: lattice.Elem): lattice.Elem =
+      gen(b) incl (out excl kill(b))
+
+    /** Abstract interpretation for one instruction. */
+    def interpret(out: lattice.Elem, i: Instruction): lattice.Elem = {
+      var in = out;
+
+      if (settings.debug.value) {
+        log("- " + i);
+        log("out: " + out);
+        log("\n");
+      }
+
+      i match {
+        case LOAD_LOCAL(l) => in = in + l;
+        case STORE_LOCAL(l) => in = in - l;
+        case _ =>
+          ()
+      }
+      in
+    } /* def interpret */
+
+    override def toString(): String = {
+      val buf = new StringBuffer();
+      for (val b <- method.code.blocks.toList) {
+        buf.append("\nlive-in(" + b + ")=" + in(b) + "\nlive-out(" + b + ")=" + out(b));
+      }
+      buf.toString()
+    }
+  } /* Liveness analysis */
+}
diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
index f13eb65832..27bb116a3f 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 = "closurelim";
+  val phaseName = "closurelimination";
 
   /** 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
new file mode 100644
index 0000000000..791dcd50c2
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
@@ -0,0 +1,109 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author  Iulian Dragos
+ */
+
+// $Id: $
+
+package scala.tools.nsc.backend.opt;
+
+import scala.collection.mutable.{Map, HashMap};
+import scala.tools.nsc.backend.icode.analysis.LubError;
+import scala.tools.nsc.symtab._;
+
+/**
+ */
+abstract class DeadCodeElimination extends SubComponent {
+  import global._;
+  import icodes._;
+  import icodes.opcodes._;
+
+  val phaseName = "deadcode";
+
+  /** Create a new phase */
+  override def newPhase(p: Phase) = new DeadCodeEliminationPhase(p);
+
+  /** Dead code elimination phase.
+   */
+  class DeadCodeEliminationPhase(prev: Phase) extends GlobalPhase(prev) {
+    def name = phaseName;
+    override def newFlags = phaseNewFlags;
+
+    override def erasedTypes = true;
+		val dce = new DeadCode();
+
+    override def run: Unit = {
+      if (settings.debug.value) inform("[running phase " + name + " on icode]");
+      if (settings.Xdce.value)
+        classes.values foreach dce.analyzeClass;
+    }
+    override def apply(unit: CompilationUnit): Unit =
+      abort("Dead code elimination works on icode classes, not on compilation units!");
+  }
+
+  /** Remove dead code.
+   */
+  class DeadCode {
+    def analyzeClass(cls: IClass): Unit =
+      cls.methods.foreach { m =>
+        analyzeMethod(m);
+      }
+
+    val a = new liveness.LivenessAnalysis();
+
+    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 Pair(i, pos) <- bb.toList.zipWithIndex.reverse) {
+        var live = a.out(bb);
+
+        i match {
+          case STORE_LOCAL(l) if (!live(l)) =>
+            removeDefUse(bb, pos);
+          case _ => ()
+        }
+        live = a.interpret(live, i);
+      }
+    }
+
+    /** 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: Int): Unit = {
+      bb.findDef(use) match {
+        case Some(defPos) =>
+          val definition = bb(defPos);
+          if (isSafeToRemove(definition)) {
+            log("Removing instructions at BB " + bb + " def: " + definition + ", use: " + bb(use));
+
+            if (definition.consumed == 0) {
+              bb.removeInstructionsAt(defPos, use)
+            } else {
+              bb.replaceInstruction(definition, definition.consumedTypes map DROP);
+              bb.removeInstructionsAt(use);
+            }
+          }
+        case None =>
+        	val i = bb(use);
+          bb.replaceInstruction(i, i.consumedTypes map DROP);
+          log("Replaced dead " + i + " by DROP in bb " + bb);
+      }
+    }
+
+    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;
+    }
+
+  } /* DeadCode */
+}
\ No newline at end of file