Merge pull request #3971 from lrytz/opt/dce

GenBCode: eliminate unreachable code

8 files changed, 323 insertions, 13 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala
index 397171049f..daf36ce374 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala
@@ -9,7 +9,6 @@ package tools.nsc
 package backend
 package jvm
 
-import scala.collection.{ mutable, immutable }
 import scala.annotation.switch
 
 import scala.tools.asm
@@ -283,9 +282,10 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder {
           val Local(tk, _, idx, isSynth) = locals.getOrMakeLocal(sym)
           if (rhs == EmptyTree) { emitZeroOf(tk) }
           else { genLoad(rhs, tk) }
+          val localVarStart = currProgramPoint()
           bc.store(idx, tk)
           if (!isSynth) { // there are case <synthetic> ValDef's emitted by patmat
-            varsInScope ::= (sym -> currProgramPoint())
+            varsInScope ::= (sym -> localVarStart)
           }
           generatedType = UNIT
 
@@ -815,7 +815,51 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder {
           case _    => bc.emitT2T(from, to)
         }
       } else if (from.isNothingType) {
-        emit(asm.Opcodes.ATHROW) // ICode enters here into enterIgnoreMode, we'll rely instead on DCE at ClassNode level.
+        /* There are two possibilities for from.isNothingType: emitting a "throw e" expressions and
+         * loading a (phantom) value of type Nothing.
+         *
+         * The Nothing type in Scala's type system does not exist in the JVM. In bytecode, Nothing
+         * is mapped to scala.runtime.Nothing$. To the JVM, a call to Predef.??? looks like it would
+         * return an object of type Nothing$. We need to do something with that phantom object on
+         * the stack. "Phantom" because it never exists: such methods always throw, but the JVM does
+         * not know that.
+         *
+         * Note: The two verifiers (old: type inference, new: type checking) have different
+         * requirements. Very briefly:
+         *
+         * Old (http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.2.1): at
+         * each program point, no matter what branches were taken to get there
+         *   - Stack is same size and has same typed values
+         *   - Local and stack values need to have consistent types
+         *   - In practice, the old verifier seems to ignore unreachable code and accept any
+         *     instructions after an ATHROW. For example, there can be another ATHROW (without
+         *     loading another throwable first).
+         *
+         * New (http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1)
+         *   - Requires consistent stack map frames. GenBCode generates stack frames if -target:jvm-1.6
+         *     or higher.
+         *   - In practice: the ASM library computes stack map frames for us (ClassWriter). Emitting
+         *     correct frames after an ATHROW is probably complex, so ASM uses the following strategy:
+         *       - Every time when generating an ATHROW, a new basic block is started.
+         *       - During classfile writing, such basic blocks are found to be dead: no branches go there
+         *       - Eliminating dead code would probably require complex shifts in the output byte buffer
+         *       - But there's an easy solution: replace all code in the dead block with with
+         *         `nop; nop; ... nop; athrow`, making sure the bytecode size stays the same
+         *       - The corresponding stack frame can be easily generated: on entering a dead the block,
+         *         the frame requires a single Throwable on the stack.
+         *       - Since there are no branches to the dead block, the frame requirements are never violated.
+         *
+         * To summarize the above: it does matter what we emit after an ATHROW.
+         *
+         * NOW: if we end up here because we emitted a load of a (phantom) value of type Nothing$,
+         * there was no ATHROW emitted. So, we have to make the verifier happy and do something
+         * with that value. Since Nothing$ extends Throwable, the easiest is to just emit an ATHROW.
+         *
+         * If we ended up here because we generated a "throw e" expression, we know the last
+         * emitted instruction was an ATHROW. As explained above, it is OK to emit a second ATHROW,
+         * the verifiers will be happy.
+         */
+        emit(asm.Opcodes.ATHROW)
       } else if (from.isNullType) {
         bc drop from
         emit(asm.Opcodes.ACONST_NULL)
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala
index 5670715cd3..14bffd67ab 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala
@@ -782,14 +782,9 @@ abstract class BCodeHelpers extends BCodeIdiomatic with BytecodeWriters {
     }
   } // end of trait BCClassGen
 
-  /* basic functionality for class file building of plain, mirror, and beaninfo classes. */
-  abstract class JBuilder extends BCInnerClassGen {
-
-  } // end of class JBuilder
-
   /* functionality for building plain and mirror classes */
   abstract class JCommonBuilder
-    extends JBuilder
+    extends BCInnerClassGen
     with    BCAnnotGen
     with    BCForwardersGen
     with    BCPickles { }
@@ -851,7 +846,7 @@ abstract class BCodeHelpers extends BCodeIdiomatic with BytecodeWriters {
   } // end of class JMirrorBuilder
 
   /* builder of bean info classes */
-  class JBeanInfoBuilder extends JBuilder {
+  class JBeanInfoBuilder extends BCInnerClassGen {
 
     /*
      * Generate a bean info class that describes the given class.
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala
index 4592031a31..03bc32061b 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala
@@ -346,6 +346,13 @@ abstract class BCodeSkelBuilder extends BCodeHelpers {
 
     /*
      * Bookkeeping for method-local vars and method-params.
+     *
+     * TODO: use fewer slots. local variable slots are never re-used in separate blocks.
+     * In the following example, x and y could use the same slot.
+     *   def foo() = {
+     *     { val x = 1 }
+     *     { val y = "a" }
+     *   }
      */
     object locals {
 
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..4b9383c67c
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
@@ -0,0 +1,24 @@
+/* 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)
+
+  def timed[T](timer: Statistics.Timer)(body: => T): T = {
+    val start = Statistics.startTimer(timer)
+    try body finally Statistics.stopTimer(timer, start)
+  }
+}
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
index 0a7c894a69..ba94a9c44c 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
@@ -11,8 +11,10 @@ package jvm
 
 import scala.collection.{ mutable, immutable }
 import scala.annotation.switch
+import scala.reflect.internal.util.Statistics
 
 import scala.tools.asm
+import scala.tools.asm.tree.ClassNode
 
 /*
  *  Prepare in-memory representations of classfiles using the ASM Tree API, and serialize them to disk.
@@ -213,6 +215,14 @@ abstract class GenBCode extends BCodeSyncAndTry {
      *          - converting the plain ClassNode to byte array and placing it on queue-3
      */
     class Worker2 {
+      def localOptimizations(classNode: ClassNode): Unit = {
+        def dce(): Boolean = BackendStats.timed(BackendStats.bcodeDceTimer) {
+          if (settings.YoptUnreachableCode) opt.LocalOpt.removeUnreachableCode(classNode)
+          else false
+        }
+
+        dce()
+      }
 
       def run() {
         while (true) {
@@ -222,8 +232,10 @@ abstract class GenBCode extends BCodeSyncAndTry {
             return
           }
           else {
-            try   { addToQ3(item) }
-            catch {
+            try {
+              localOptimizations(item.plain)
+              addToQ3(item)
+          } catch {
               case ex: Throwable =>
                 ex.printStackTrace()
                 error(s"Error while emitting ${item.plain.name}\n${ex.getMessage}")
@@ -272,10 +284,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 +302,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 +328,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..3acd2d6154
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -0,0 +1,190 @@
+/* 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.{Opcodes, MethodWriter, ClassWriter}
+import scala.tools.asm.tree.analysis.{Analyzer, BasicValue, BasicInterpreter}
+import scala.tools.asm.tree._
+import scala.collection.convert.decorateAsScala._
+import scala.collection.{ mutable => m }
+
+/**
+ * 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.name) || 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.
+   *
+   * TODO doc: it also removes empty handlers, unused local vars
+   *
+   * Returns `true` if dead code in `method` has been eliminated.
+   */
+  private def removeUnreachableCode(method: MethodNode, ownerClassName: String): Boolean = {
+    if (method.instructions.size == 0) return false // fast path for abstract methods
+
+    val codeRemoved = removeUnreachableCodeImpl(method, ownerClassName)
+
+    // unreachable-code also removes unused local variable nodes and empty exception handlers.
+    // This is required for correctness: such nodes are not allowed to refer to instruction offsets
+    // that don't exist (because they have been eliminated).
+    val localsRemoved = removeUnusedLocalVariableNodes(method)
+    val handlersRemoved = removeEmptyExceptionHandlers(method)
+
+    // When eliminating a handler, the catch block becomes unreachable. The recursive invocation
+    // removes these blocks.
+    // Note that invoking removeUnreachableCode*Impl* a second time is not enough: removing the dead
+    // catch block can render other handlers empty, which also have to be removed in turn.
+    if (handlersRemoved) removeUnreachableCode(method, ownerClassName)
+
+    // assert that we can leave local variable annotations as-is
+    def nullOrEmpty[T](l: java.util.List[T]) = l == null || l.isEmpty
+    assert(nullOrEmpty(method.visibleLocalVariableAnnotations), method.visibleLocalVariableAnnotations)
+    assert(nullOrEmpty(method.invisibleLocalVariableAnnotations), method.invisibleLocalVariableAnnotations)
+
+    codeRemoved || localsRemoved || handlersRemoved
+  }
+
+  private def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: String): 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(ownerClassName, 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
+  }
+
+  /**
+   * Remove exception handlers that cover empty code blocks from all methods of `clazz`.
+   * Returns `true` if any exception handler was eliminated.
+   */
+  def removeEmptyExceptionHandlers(clazz: ClassNode): Boolean = {
+    clazz.methods.asScala.foldLeft(false) {
+      case (changed, method) => removeEmptyExceptionHandlers(method) || changed
+    }
+  }
+
+  /**
+   * Remove exception handlers that cover empty code blocks. A block is considered empty if it
+   * consist only of labels, frames, line numbers, nops and gotos.
+   *
+   * Note that no instructions are eliminated.
+   *
+   * @return `true` if some exception handler was eliminated.
+   */
+  def removeEmptyExceptionHandlers(method: MethodNode): Boolean = {
+    /** True if there exists code between start and end. */
+    def containsExecutableCode(start: AbstractInsnNode, end: LabelNode): Boolean = {
+      start != end && (start.getOpcode match {
+        // FrameNode, LabelNode and LineNumberNode have opcode == -1.
+        case -1 | Opcodes.NOP | Opcodes.GOTO => containsExecutableCode(start.getNext, end)
+        case _ => true
+      })
+    }
+
+    val initialNumberHandlers = method.tryCatchBlocks.size
+    val handlersIter = method.tryCatchBlocks.iterator()
+    while(handlersIter.hasNext) {
+      val handler = handlersIter.next()
+      if (!containsExecutableCode(handler.start, handler.end)) handlersIter.remove()
+    }
+    method.tryCatchBlocks.size != initialNumberHandlers
+  }
+
+  /**
+   * Remove all non-parameter entries from the local variable table which denote variables that are
+   * not actually read or written.
+   *
+   * Note that each entry in the local variable table has a start, end and index. Two entries with
+   * the same index, but distinct start / end ranges are different variables, they may have not the
+   * same type or name.
+   *
+   * TODO: also re-allocate locals to occupy fewer slots after eliminating unused ones
+   */
+  def removeUnusedLocalVariableNodes(method: MethodNode): Boolean = {
+    def variableIsUsed(start: AbstractInsnNode, end: LabelNode, varIndex: Int): Boolean = {
+      start != end && (start match {
+        case v: VarInsnNode =>  v.`var` == varIndex
+        case _ => variableIsUsed(start.getNext, end, varIndex)
+      })
+    }
+
+    val initialNumVars = method.localVariables.size
+    val localsIter = method.localVariables.iterator()
+    // The parameters and `this` (for instance methods) have the lowest indices in the local variables
+    // table. Note that double / long fields occupy two slots, so we sum up the sizes. Since getSize
+    // returns 0 for void, we have to add `max 1`.
+    val paramsSize = scala.tools.asm.Type.getArgumentTypes(method.desc).map(_.getSize max 1).sum
+    val thisSize = if ((method.access & Opcodes.ACC_STATIC) == 0) 1 else 0
+    val endParamIndex = paramsSize + thisSize
+    while (localsIter.hasNext) {
+      val local = localsIter.next()
+      // parameters and `this` have the lowest indices, starting at 0
+      val used = local.index < endParamIndex || variableIsUsed(local.start, local.end, local.index)
+      if (!used)
+        localsIter.remove()
+    }
+    method.localVariables.size == initialNumVars
+  }
+
+
+  /**
+   * 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..466e397dd7 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -209,9 +209,35 @@ trait ScalaSettings extends AbsScalaSettings
   // the current standard is "inline" but we are moving towards "method"
   val Ydelambdafy        = ChoiceSetting     ("-Ydelambdafy", "strategy", "Strategy used for translating lambdas into JVM code.", List("inline", "method"), "inline")
 
+  object YoptChoices extends MultiChoiceEnumeration {
+    val unreachableCode = Choice("unreachable-code", "Eliminate unreachable code")
+
+    val lNone           = Choice("l:none",      "Don't enable any optimizations")
+
+    private val defaultChoices = List(unreachableCode)
+    val lDefault        = Choice("l:default",   "Enable default optimizations: "+ defaultChoices.mkString(","),                           expandsTo = defaultChoices)
+
+    private val methodChoices = List(lDefault)
+    val lMethod         = Choice("l:method",    "Intra-method optimizations: "+ methodChoices.mkString(","),                              expandsTo = methodChoices)
+
+    private val projectChoices = List(lMethod)
+    val lProject        = Choice("l:project",   "Cross-method optimizations within the current project: "+ projectChoices.mkString(","),  expandsTo = projectChoices)
+
+    private val classpathChoices = List(lProject)
+    val lClasspath      = Choice("l:classpath", "Cross-method optmizations across the entire classpath: "+ classpathChoices.mkString(","), expandsTo = classpathChoices)
+  }
+
+  val Yopt = MultiChoiceSetting(
+    name = "-Yopt",
+    helpArg = "optimization",
+    descr = "Enable optimizations",
+    domain = YoptChoices)
+
+  def YoptUnreachableCode: Boolean = !Yopt.isSetByUser || Yopt.contains(YoptChoices.unreachableCode)
+
   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(