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.

6 files changed, 171 insertions, 29 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.
    *
diff --git a/src/partest-extras/scala/tools/partest/ASMConverters.scala b/src/partest-extras/scala/tools/partest/ASMConverters.scala
index f4a90d9acf..d443a31112 100644
--- a/src/partest-extras/scala/tools/partest/ASMConverters.scala
+++ b/src/partest-extras/scala/tools/partest/ASMConverters.scala
@@ -3,7 +3,6 @@ package scala.tools.partest
 import scala.collection.JavaConverters._
 import scala.tools.asm
 import asm.{tree => t}
-import scala.tools.asm.tree.LabelNode
 
 /** Makes using ASM from ByteCodeTests more convenient.
  *
@@ -15,13 +14,9 @@ object ASMConverters {
   /**
    * Transform the instructions of an ASM Method into a list of [[Instruction]]s.
    */
-  def instructionsFromMethod(meth: t.MethodNode): List[Instruction] = {
-    val insns = meth.instructions
-    val asmToScala = new AsmToScala {
-      def labelIndex(l: t.LabelNode) = insns.indexOf(l)
-    }
-    asmToScala.convert(insns.iterator.asScala.toList)
-  }
+  def instructionsFromMethod(meth: t.MethodNode): List[Instruction] = new AsmToScala(meth).instructions
+
+  def convertMethod(meth: t.MethodNode): Method = new AsmToScala(meth).method
 
   implicit class RichInstructionLists(val self: List[Instruction]) extends AnyVal {
     def === (other: List[Instruction]) = equivalentBytecode(self, other)
@@ -61,6 +56,8 @@ object ASMConverters {
     }
   }
 
+  case class Method(instructions: List[Instruction], handlers: List[ExceptionHandler], localVars: List[LocalVariable])
+
   case class Field       (opcode: Int, owner: String, name: String, desc: String)               extends Instruction
   case class Incr        (opcode: Int, `var`: Int, incr: Int)                                   extends Instruction
   case class Op          (opcode: Int)                                                          extends Instruction
@@ -69,7 +66,7 @@ object ASMConverters {
   case class Ldc         (opcode: Int, cst: Any)                                                extends Instruction
   case class LookupSwitch(opcode: Int, dflt: Label, keys: List[Int], labels: List[Label])       extends Instruction
   case class TableSwitch (opcode: Int, min: Int, max: Int, dflt: Label, labels: List[Label])    extends Instruction
-  case class Method      (opcode: Int, owner: String, name: String, desc: String, itf: Boolean) extends Instruction
+  case class Invoke      (opcode: Int, owner: String, name: String, desc: String, itf: Boolean) extends Instruction
   case class NewArray    (opcode: Int, desc: String, dims: Int)                                 extends Instruction
   case class TypeOp      (opcode: Int, desc: String)                                            extends Instruction
   case class VarOp       (opcode: Int, `var`: Int)                                              extends Instruction
@@ -77,13 +74,18 @@ object ASMConverters {
   case class FrameEntry  (`type`: Int, local: List[Any], stack: List[Any])                      extends Instruction { def opcode: Int = -1 }
   case class LineNumber  (line: Int, start: Label)                                              extends Instruction { def opcode: Int = -1 }
 
-  abstract class AsmToScala {
+  case class ExceptionHandler(start: Label, end: Label, handler: Label, desc: Option[String])
+  case class LocalVariable(name: String, desc: String, signature: Option[String], start: Label, end: Label, index: Int)
 
-    def labelIndex(l: t.LabelNode): Int
+  class AsmToScala(asmMethod: t.MethodNode) {
 
-    def op(i: t.AbstractInsnNode): Int = i.getOpcode
+    def instructions: List[Instruction] = asmMethod.instructions.iterator.asScala.toList map apply
 
-    def convert(instructions: List[t.AbstractInsnNode]): List[Instruction] = instructions map apply
+    def method: Method = Method(instructions, convertHandlers(asmMethod), convertLocalVars(asmMethod))
+
+    private def labelIndex(l: t.LabelNode): Int = asmMethod.instructions.indexOf(l)
+    
+    private def op(i: t.AbstractInsnNode): Int = i.getOpcode
 
     private def lst[T](xs: java.util.List[T]): List[T] = if (xs == null) Nil else xs.asScala.toList
 
@@ -108,7 +110,7 @@ object ASMConverters {
       case i: t.LdcInsnNode            => Ldc          (op(i), i.cst: Any)
       case i: t.LookupSwitchInsnNode   => LookupSwitch (op(i), applyLabel(i.dflt), lst(i.keys) map (x => x: Int), lst(i.labels) map applyLabel)
       case i: t.TableSwitchInsnNode    => TableSwitch  (op(i), i.min, i.max, applyLabel(i.dflt), lst(i.labels) map applyLabel)
-      case i: t.MethodInsnNode         => Method       (op(i), i.owner, i.name, i.desc, i.itf)
+      case i: t.MethodInsnNode         => Invoke       (op(i), i.owner, i.name, i.desc, i.itf)
       case i: t.MultiANewArrayInsnNode => NewArray     (op(i), i.desc, i.dims)
       case i: t.TypeInsnNode           => TypeOp       (op(i), i.desc)
       case i: t.VarInsnNode            => VarOp        (op(i), i.`var`)
@@ -116,6 +118,14 @@ object ASMConverters {
       case i: t.FrameNode              => FrameEntry   (i.`type`, mapOverFrameTypes(lst(i.local)), mapOverFrameTypes(lst(i.stack)))
       case i: t.LineNumberNode         => LineNumber   (i.line, applyLabel(i.start))
     }
+
+    private def convertHandlers(method: t.MethodNode): List[ExceptionHandler] = {
+      method.tryCatchBlocks.asScala.map(h => ExceptionHandler(applyLabel(h.start), applyLabel(h.end), applyLabel(h.handler), Option(h.`type`)))(collection.breakOut)
+    }
+
+    private def convertLocalVars(method: t.MethodNode): List[LocalVariable] = {
+      method.localVariables.asScala.map(v => LocalVariable(v.name, v.desc, Option(v.signature), applyLabel(v.start), applyLabel(v.end), v.index))(collection.breakOut)
+    }
   }
 
   import collection.mutable.{Map => MMap}
@@ -159,15 +169,21 @@ object ASMConverters {
     }) && equivalentBytecode(as.tail, bs.tail, varMap, labelMap)
   }
 
-  /**
-   * Convert back a list of [[Instruction]]s to ASM land. The code is emitted into the parameter
-   * `method`.
-   */
   def applyToMethod(method: t.MethodNode, instructions: List[Instruction]): Unit = {
     val asmLabel = createLabelNodes(instructions)
     instructions.foreach(visitMethod(method, _, asmLabel))
   }
 
+  /**
+   * Convert back a [[Method]] to ASM land. The code is emitted into the parameter `asmMethod`.
+   */
+  def applyToMethod(asmMethod: t.MethodNode, method: Method): Unit = {
+    val asmLabel = createLabelNodes(method.instructions)
+    method.instructions.foreach(visitMethod(asmMethod, _, asmLabel))
+    method.handlers.foreach(h => asmMethod.visitTryCatchBlock(asmLabel(h.start), asmLabel(h.end), asmLabel(h.handler), h.desc.orNull))
+    method.localVars.foreach(v => asmMethod.visitLocalVariable(v.name, v.desc, v.signature.orNull, asmLabel(v.start), asmLabel(v.end), v.index))
+  }
+
   private def createLabelNodes(instructions: List[Instruction]): Map[Label, asm.Label] = {
     val labels = instructions collect {
       case l: Label => l
@@ -190,7 +206,7 @@ object ASMConverters {
     case Ldc(op, cst)                            => method.visitLdcInsn(cst)
     case LookupSwitch(op, dflt, keys, labels)    => method.visitLookupSwitchInsn(asmLabel(dflt), keys.toArray, (labels map asmLabel).toArray)
     case TableSwitch(op, min, max, dflt, labels) => method.visitTableSwitchInsn(min, max, asmLabel(dflt), (labels map asmLabel).toArray: _*)
-    case Method(op, owner, name, desc, itf)      => method.visitMethodInsn(op, owner, name, desc, itf)
+    case Invoke(op, owner, name, desc, itf)      => method.visitMethodInsn(op, owner, name, desc, itf)
     case NewArray(op, desc, dims)                => method.visitMultiANewArrayInsn(desc, dims)
     case TypeOp(op, desc)                        => method.visitTypeInsn(op, desc)
     case VarOp(op, vr)                           => method.visitVarInsn(op, vr)