Eliminate unreachable code in GenBCode

We rely on dead code elimination provided by the ASM framework, as
described in the ASM User Guide (http://asm.ow2.org/index.html),
Section 8.2.1. It runs a data flow analysis, which only computes
information for reachable instructions. Instructions for which no
data is available after the analyis are unreachable.

There's one issue with the ASM framework (or the way we use it): Data
flow analysis requires the maxlocals and maxstack of each method to be
computed. The ASM framework calculates these maxes only when
writing the classfiles, not during code generation. In order to run
DCE, we therefore run a MethodWriter beforehand on every method. This
assings the MethodNode's maxStack/maxLocals, but it does more work
(writes the instructions to a byte array).

This is also what Miguel uses on his branch. The change is basically
the same as https://github.com/lrytz/scala/commit/bfadf92c20.

We could probably make this faster (and allocate less memory) by
hacking the ASM framework: create a subclass of MethodWriter with a
/dev/null byteVector. Another option would be to create a separate
visitor for computing those values, duplicating the functionality from
the MethodWriter.

For now, I added some timers to be able to measure the time DCE takes.
Here's compiling the library with -Ystatistics:jvm

    time in backend               : 1 spans, 6597ms
    bcode initialization          : 1 spans, 8ms (0.1%)
    code generation               : 1 spans, 4580ms (69.4%)
    dead code elimination         : 3771 spans, 742ms (11.2%)
    classfile writing             : 1 spans, 879ms (13.3%)

5 files changed, 125 insertions, 3 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
index 7bf61b4f51..53ac5bfdc7 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
@@ -713,6 +713,8 @@ abstract class BTypes {
           // TODO @lry I don't really understand the reasoning here.
           // Both this and other are classes. The code takes (transitively) all superclasses and
           // finds the first common one.
+          // MOST LIKELY the answer can be found here, see the comments and links by Miguel:
+          //  - https://issues.scala-lang.org/browse/SI-3872
           firstCommonSuffix(this :: this.superClassesTransitive, other :: other.superClassesTransitive)
       }
 
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
new file mode 100644
index 0000000000..921aef7aca
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
@@ -0,0 +1,19 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2014 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+
+package scala.tools.nsc
+package backend.jvm
+
+import scala.reflect.internal.util.Statistics
+
+object BackendStats {
+  import Statistics.{newTimer, newSubTimer}
+  val bcodeTimer = newTimer("time in backend", "jvm")
+
+  val bcodeInitTimer  = newSubTimer("bcode initialization", bcodeTimer)
+  val bcodeGenStat    = newSubTimer("code generation", bcodeTimer)
+  val bcodeDceTimer   = newSubTimer("dead code elimination", bcodeTimer)
+  val bcodeWriteTimer = newSubTimer("classfile writing", bcodeTimer)
+}
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
index 0a7c894a69..a7cc1f69cf 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
@@ -11,6 +11,7 @@ package jvm
 
 import scala.collection.{ mutable, immutable }
 import scala.annotation.switch
+import scala.reflect.internal.util.Statistics
 
 import scala.tools.asm
 
@@ -222,8 +223,12 @@ abstract class GenBCode extends BCodeSyncAndTry {
             return
           }
           else {
-            try   { addToQ3(item) }
-            catch {
+            try {
+              val dceStart = Statistics.startTimer(BackendStats.bcodeDceTimer)
+              opt.LocalOpt.removeUnreachableCode(item.plain)
+              Statistics.stopTimer(BackendStats.bcodeDceTimer, dceStart)
+              addToQ3(item)
+          } catch {
               case ex: Throwable =>
                 ex.printStackTrace()
                 error(s"Error while emitting ${item.plain.name}\n${ex.getMessage}")
@@ -272,10 +277,13 @@ abstract class GenBCode extends BCodeSyncAndTry {
      *
      */
     override def run() {
+      val bcodeStart = Statistics.startTimer(BackendStats.bcodeTimer)
 
+      val initStart = Statistics.startTimer(BackendStats.bcodeInitTimer)
       arrivalPos = 0 // just in case
       scalaPrimitives.init()
       bTypes.intializeCoreBTypes()
+      Statistics.stopTimer(BackendStats.bcodeInitTimer, initStart)
 
       // initBytecodeWriter invokes fullName, thus we have to run it before the typer-dependent thread is activated.
       bytecodeWriter  = initBytecodeWriter(cleanup.getEntryPoints)
@@ -287,6 +295,7 @@ abstract class GenBCode extends BCodeSyncAndTry {
 
       // closing output files.
       bytecodeWriter.close()
+      Statistics.stopTimer(BackendStats.bcodeTimer, bcodeStart)
 
       /* TODO Bytecode can be verified (now that all classfiles have been written to disk)
        *
@@ -312,9 +321,15 @@ abstract class GenBCode extends BCodeSyncAndTry {
     private def buildAndSendToDisk(needsOutFolder: Boolean) {
 
       feedPipeline1()
+      val genStart = Statistics.startTimer(BackendStats.bcodeGenStat)
       (new Worker1(needsOutFolder)).run()
+      Statistics.stopTimer(BackendStats.bcodeGenStat, genStart)
+
       (new Worker2).run()
+
+      val writeStart = Statistics.startTimer(BackendStats.bcodeWriteTimer)
       drainQ3()
+      Statistics.stopTimer(BackendStats.bcodeWriteTimer, writeStart)
 
     }
 
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
new file mode 100644
index 0000000000..b3a515c2ae
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -0,0 +1,86 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2014 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+
+package scala.tools.nsc
+package backend.jvm
+package opt
+
+import scala.tools.asm.{MethodWriter, ClassWriter}
+import scala.tools.asm.tree.analysis.{Analyzer, BasicValue, BasicInterpreter}
+import scala.tools.asm.tree.{LabelNode, ClassNode, MethodNode}
+import scala.collection.convert.decorateAsScala._
+
+/**
+ * Intra-Method optimizations.
+ */
+object LocalOpt {
+  /**
+   * Remove unreachable instructions from all (non-abstract) methods.
+   *
+   * @param clazz The class whose methods are optimized
+   * @return      `true` if unreachable code was elminated in some method, `false` otherwise.
+   */
+  def removeUnreachableCode(clazz: ClassNode): Boolean = {
+    clazz.methods.asScala.foldLeft(false) {
+      case (changed, method) => removeUnreachableCode(method, clazz) || changed
+    }
+  }
+
+  /**
+   * Remove unreachable code from a method.
+   * We rely on dead code elimination provided by the ASM framework, as described in the ASM User
+   * Guide (http://asm.ow2.org/index.html), Section 8.2.1. It runs a data flow analysis, which only
+   * computes Frame information for reachable instructions. Instructions for which no Frame data is
+   * available after the analyis are unreachable.
+   */
+  private def removeUnreachableCode(method: MethodNode, ownerClass: ClassNode): Boolean = {
+    val initialSize = method.instructions.size
+    if (initialSize == 0) return false
+
+    // The data flow analysis requires the maxLocals / maxStack fields of the method to be computed.
+    computeMaxLocalsMaxStack(method)
+    val a = new Analyzer[BasicValue](new BasicInterpreter)
+    a.analyze(ownerClass.name, method)
+    val frames = a.getFrames
+
+    var i = 0
+    val itr = method.instructions.iterator()
+    while (itr.hasNext) {
+      val ins = itr.next()
+      // Don't remove label nodes: they might be referenced for example in a LocalVariableNode
+      if (frames(i) == null && !ins.isInstanceOf[LabelNode]) {
+        // Instruction iterators allow removing during iteration.
+        // Removing is O(1): instructions are doubly linked list elements.
+        itr.remove()
+      }
+      i += 1
+    }
+
+    method.instructions.size == initialSize
+  }
+
+  /**
+   * In order to run an Analyzer, the maxLocals / maxStack fields need to be available. The ASM
+   * framework only computes these values during bytecode generation.
+   *
+   * Sicne there's currently no better way, we run a bytecode generator on the method and extract
+   * the computed values. This required changes to the ASM codebase:
+   *   - the [[MethodWriter]] class was made public
+   *   - accessors for maxLocals / maxStack were added to the MethodWriter class
+   *
+   * We could probably make this faster (and allocate less memory) by hacking the ASM framework
+   * more: create a subclass of MethodWriter with a /dev/null byteVector. Another option would be
+   * to create a separate visitor for computing those values, duplicating the functionality from the
+   * MethodWriter.
+   */
+  private def computeMaxLocalsMaxStack(method: MethodNode) {
+    val cw = new ClassWriter(ClassWriter.COMPUTE_MAXS)
+    val excs = method.exceptions.asScala.toArray
+    val mw = cw.visitMethod(method.access, method.name, method.desc, method.signature, excs).asInstanceOf[MethodWriter]
+    method.accept(mw)
+    method.maxLocals = mw.getMaxLocals
+    method.maxStack = mw.getMaxStack
+  }
+}
diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 91b03869e5..98eb831a9d 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -211,7 +211,7 @@ trait ScalaSettings extends AbsScalaSettings
 
   private def removalIn212 = "This flag is scheduled for removal in 2.12. If you have a case where you need this flag then please report a bug."
 
-  object YstatisticsPhases extends MultiChoiceEnumeration { val parser, typer, patmat, erasure, cleanup = Value }
+  object YstatisticsPhases extends MultiChoiceEnumeration { val parser, typer, patmat, erasure, cleanup, jvm = Value }
   val Ystatistics = {
     val description = "Print compiler statistics for specific phases"
     MultiChoiceSetting(