GenBCode: Compact local variable slots

After eliminating unreachable code, there may be unused local varaible
slots. Such gaps increase the method's frame size unnecessarily.

The optimization does not attempt to re-use the same local variable
slot for non-overlapping locals (proper register allocation):

    def f(b: Boolean) = if (b) { val x = e; x } else { val y = e; y }

x and y will not use the same slot, even though they could.

This was originally implemented by Miguel in
  https://github.com/lrytz/scala/commit/09c40359338f8770e4f99d045999af062112973e

3 files changed, 111 insertions, 18 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
index c206927db9..fd14083cf7 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
@@ -36,6 +36,14 @@ object BytecodeUtils {
     }
   }
 
+  object VarInstruction {
+    def unapply(instruction: AbstractInsnNode): Option[VarInsnNode] = {
+      if (isVarInstruction(instruction)) Some(instruction.asInstanceOf[VarInsnNode])
+      else None
+    }
+
+  }
+
   def isJumpNonJsr(instruction: AbstractInsnNode): Boolean = {
     val op = instruction.getOpcode
     // JSR is deprecated in classfile version 50, disallowed in 51. historically, it was used to implement finally.
@@ -47,6 +55,11 @@ object BytecodeUtils {
     (op >= Opcodes.IFEQ && op <= Opcodes.IF_ACMPNE) || op == Opcodes.IFNULL || op == Opcodes.IFNONNULL
   }
 
+  def isVarInstruction(instruction: AbstractInsnNode): Boolean = {
+    val op = instruction.getOpcode
+    (op >= Opcodes.ILOAD  && op <= Opcodes.ALOAD) || (op >= Opcodes.ISTORE && op <= Opcodes.ASTORE)
+  }
+
   def isExecutable(instruction: AbstractInsnNode): Boolean = instruction.getOpcode >= 0
 
   def nextExecutableInstruction(instruction: AbstractInsnNode, alsoKeep: AbstractInsnNode => Boolean = Set()): Option[AbstractInsnNode] = {
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 29754d5500..8fff478326 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -122,8 +122,11 @@ class LocalOpt(settings: ScalaSettings) {
       recurse = settings.YoptRecurseUnreachableJumps && (jumpsChanged || liveHandlerRemoved)
     }
 
-    // Removing stale local variable descriptors is required for correctness of unreachable-code, therefore no dedicated setting
-    val localsRemoved = if (settings.YoptUnreachableCode) removeUnusedLocalVariableNodes(method) else false
+    // (*) Removing stale local variable descriptors is required for correctness of unreachable-code
+    val localsRemoved =
+      if (settings.YoptCompactLocals) compactLocalVariables(method)
+      else if (settings.YoptUnreachableCode) removeUnusedLocalVariableNodes(method)() // (*)
+      else false
 
     val lineNumbersRemoved = if (settings.YoptEmptyLineNumbers) removeEmptyLineNumbers(method) else false
 
@@ -214,7 +217,7 @@ class LocalOpt(settings: ScalaSettings) {
    * the same index, but distinct start / end ranges are different variables, they may have not the
    * same type or name.
    */
-  def removeUnusedLocalVariableNodes(method: MethodNode): Boolean = {
+  def removeUnusedLocalVariableNodes(method: MethodNode)(fistLocalIndex: Int = parametersSize(method), renumber: Int => Int = identity): Boolean = {
     def variableIsUsed(start: AbstractInsnNode, end: LabelNode, varIndex: Int): Boolean = {
       start != end && (start match {
         case v: VarInsnNode if v.`var` == varIndex => true
@@ -224,23 +227,98 @@ class LocalOpt(settings: ScalaSettings) {
 
     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()
+      val index = local.index
+      // parameters and `this` (the lowest indices, starting at 0) are never removed or renumbered
+      if (index >= fistLocalIndex) {
+        if (!variableIsUsed(local.start, local.end, index)) localsIter.remove()
+        else if (renumber(index) != index) local.index = renumber(index)
+      }
     }
     method.localVariables.size != initialNumVars
   }
 
   /**
+   * The number of local varialbe slots used for parameters and for the `this` reference.
+   */
+  private def parametersSize(method: MethodNode): Int = {
+    // 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
+    paramsSize + thisSize
+  }
+
+  /**
+   * Compact the local variable slots used in the method's implementation. This prevents having
+   * unused slots for example after eliminating unreachable code.
+   *
+   * This transformation reduces the size of the frame for invoking the method. For example, if the
+   * method has an ISTORE instruction to the local variable 3, the maxLocals of the method is at
+   * least 4, even if some local variable slots below 3 are not used by any instruction.
+   *
+   * This could be improved by doing proper register allocation.
+   */
+  def compactLocalVariables(method: MethodNode): Boolean = {
+    // This array is built up to map local variable indices from old to new.
+    val renumber = collection.mutable.ArrayBuffer.empty[Int]
+
+    // Add the index of the local variable used by `varIns` to the `renumber` array.
+    def addVar(varIns: VarInsnNode): Unit = {
+      val index = varIns.`var`
+      val isWide = (varIns.getOpcode: @switch) match {
+        case Opcodes.LLOAD | Opcodes.DLOAD | Opcodes.LSTORE | Opcodes.DSTORE => true
+        case _ => false
+      }
+
+      // Ensure the length of `renumber`. Unused variable indices are mapped to -1.
+      val minLenght = if (isWide) index + 2 else index + 1
+      for (i <- renumber.length until minLenght) renumber += -1
+
+      renumber(index) = index
+      if (isWide) renumber(index + 1) = index
+    }
+
+    // first phase: collect all used local variables. if the variable at index x is used, set
+    // renumber(x) = x, otherwsie renumber(x) = -1. if the variable is wide (long or doulbe), set
+    // renumber(x+1) = x.
+
+    val firstLocalIndex = parametersSize(method)
+    for (i <- 0 until firstLocalIndex) renumber += i // parameters and `this` are always used.
+    method.instructions.iterator().asScala foreach {
+      case VarInstruction(varIns) => addVar(varIns)
+      case _ =>
+    }
+
+    // assign the next free slot to each used local variable.
+    // for example, rewrite (0, 1, -1, 3, -1, 5) to (0, 1, -1, 2, -1, 3).
+
+    var nextIndex = firstLocalIndex
+    for (i <- firstLocalIndex until renumber.length if renumber(i) != -1) {
+      renumber(i) = nextIndex
+      nextIndex += 1
+    }
+
+    // Update the local variable descriptors according to the renumber table, and eliminate stale entries
+    val removedLocalVariableDescriptors = removeUnusedLocalVariableNodes(method)(firstLocalIndex, renumber)
+
+    if (nextIndex == renumber.length) removedLocalVariableDescriptors
+    else {
+      // update variable instructions according to the renumber table
+      method.maxLocals = nextIndex
+      method.instructions.iterator().asScala.foreach {
+        case VarInstruction(varIns) =>
+          val oldIndex = varIns.`var`
+          if (oldIndex >= firstLocalIndex && renumber(oldIndex) != oldIndex)
+            varIns.`var` = renumber(varIns.`var`)
+        case _ =>
+      }
+      true
+    }
+  }
+
+  /**
    * 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/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 2406b9e66b..2c9d101106 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -215,20 +215,21 @@ trait ScalaSettings extends AbsScalaSettings
     val recurseUnreachableJumps = Choice("recurse-unreachable-jumps", "Recursively apply unreachable-code and simplify-jumps (if enabled) until reaching a fixpoint.")
     val emptyLineNumbers        = Choice("empty-line-numbers",        "Eliminate unnecessary line number information.")
     val emptyLabels             = Choice("empty-labels",              "Eliminate and collapse redundant labels in the bytecode.")
+    val compactLocals           = Choice("compact-locals",            "Eliminate empty slots in the sequence of local variables.")
 
     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)
+    val lDefault        = Choice("l:default",   "Enable default optimizations: "+ defaultChoices.mkString(","),                                    expandsTo = defaultChoices)
 
-    private val methodChoices = List(unreachableCode, simplifyJumps, recurseUnreachableJumps, emptyLineNumbers, emptyLabels)
-    val lMethod         = Choice("l:method",    "Enable intra-method optimizations: "+ methodChoices.mkString(","),                               expandsTo = methodChoices)
+    private val methodChoices = List(unreachableCode, simplifyJumps, recurseUnreachableJumps, emptyLineNumbers, emptyLabels, compactLocals)
+    val lMethod         = Choice("l:method",    "Enable intra-method optimizations: "+ methodChoices.mkString(","),                                expandsTo = methodChoices)
 
     private val projectChoices = List(lMethod)
-    val lProject        = Choice("l:project",   "Enable cross-method optimizations within the current project: "+ projectChoices.mkString(","),   expandsTo = projectChoices)
+    val lProject        = Choice("l:project",   "Enable cross-method optimizations within the current project: "+ projectChoices.mkString(","),    expandsTo = projectChoices)
 
     private val classpathChoices = List(lProject)
-    val lClasspath      = Choice("l:classpath", "Enable cross-method optmizations across the entire classpath: "+ classpathChoices.mkString(","), expandsTo = classpathChoices)
+    val lClasspath      = Choice("l:classpath", "Enable cross-method optimizations across the entire classpath: "+ classpathChoices.mkString(","), expandsTo = classpathChoices)
   }
 
   val Yopt = MultiChoiceSetting(
@@ -242,6 +243,7 @@ trait ScalaSettings extends AbsScalaSettings
   def YoptRecurseUnreachableJumps = Yopt.contains(YoptChoices.recurseUnreachableJumps)
   def YoptEmptyLineNumbers        = Yopt.contains(YoptChoices.emptyLineNumbers)
   def YoptEmptyLabels             = Yopt.contains(YoptChoices.emptyLabels)
+  def YoptCompactLocals           = Yopt.contains(YoptChoices.compactLocals)
 
   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."