Remove stale local variables and exception handlers after DCE

This is required for correctness of the generated bytecode. Exception
handlers and local variable descriptors specify code offset ranges.
These offsets have to exist, not be eliminated.

5 files changed, 136 insertions, 10 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala
index 68b6f1af37..ba97cf3748 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala
@@ -282,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
 
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/BackendStats.scala b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
index 921aef7aca..d96ee933b7 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
@@ -16,4 +16,11 @@ object BackendStats {
   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) = {
+    val start = Statistics.startTimer(timer)
+    val res = body
+    Statistics.stopTimer(timer, start)
+    res
+  }
 }
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
index a788cea532..ba94a9c44c 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
@@ -14,6 +14,7 @@ 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.
@@ -214,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) {
@@ -224,9 +233,7 @@ abstract class GenBCode extends BCodeSyncAndTry {
           }
           else {
             try {
-              val dceStart = Statistics.startTimer(BackendStats.bcodeDceTimer)
-              if (settings.YoptUnreachableCode) opt.LocalOpt.removeUnreachableCode(item.plain)
-              Statistics.stopTimer(BackendStats.bcodeDceTimer, dceStart)
+              localOptimizations(item.plain)
               addToQ3(item)
           } catch {
               case ex: Throwable =>
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
index b3a515c2ae..3acd2d6154 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -7,10 +7,11 @@ package scala.tools.nsc
 package backend.jvm
 package opt
 
-import scala.tools.asm.{MethodWriter, ClassWriter}
+import scala.tools.asm.{Opcodes, MethodWriter, ClassWriter}
 import scala.tools.asm.tree.analysis.{Analyzer, BasicValue, BasicInterpreter}
-import scala.tools.asm.tree.{LabelNode, ClassNode, MethodNode}
+import scala.tools.asm.tree._
 import scala.collection.convert.decorateAsScala._
+import scala.collection.{ mutable => m }
 
 /**
  * Intra-Method optimizations.
@@ -24,7 +25,7 @@ object LocalOpt {
    */
   def removeUnreachableCode(clazz: ClassNode): Boolean = {
     clazz.methods.asScala.foldLeft(false) {
-      case (changed, method) => removeUnreachableCode(method, clazz) || changed
+      case (changed, method) => removeUnreachableCode(method, clazz.name) || changed
     }
   }
 
@@ -34,15 +35,44 @@ object LocalOpt {
    * 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, ownerClass: ClassNode): Boolean = {
+  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(ownerClass.name, method)
+    a.analyze(ownerClassName, method)
     val frames = a.getFrames
 
     var i = 0
@@ -58,10 +88,84 @@ object LocalOpt {
       i += 1
     }
 
-    method.instructions.size == initialSize
+    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.
    *