GenBCode: Eliminate redundant labels and line number nodes

Cleanup optimizations
 - remove line number nodes that describe no executable instructions
 - squash sequences of label nodes, remove unreferenced labels

Command-line flags that allow enabling these transformations are added
in a later comimt.

3 files changed, 201 insertions, 0 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 5718ad1c66..c206927db9 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
@@ -120,4 +120,46 @@ object BytecodeUtils {
     val op = if (size == 1) Opcodes.POP else Opcodes.POP2
     new InsnNode(op)
   }
+
+  def labelReferences(method: MethodNode): Map[LabelNode, Set[AnyRef]] = {
+    val res = mutable.Map.empty[LabelNode, Set[AnyRef]]
+    def add(l: LabelNode, ref: AnyRef) = if (res contains l) res(l) = res(l) + ref else res(l) = Set(ref)
+
+    method.instructions.iterator().asScala foreach {
+      case jump: JumpInsnNode           => add(jump.label, jump)
+      case line: LineNumberNode         => add(line.start, line)
+      case switch: LookupSwitchInsnNode => switch.labels.asScala.foreach(add(_, switch)); add(switch.dflt, switch)
+      case switch: TableSwitchInsnNode  => switch.labels.asScala.foreach(add(_, switch)); add(switch.dflt, switch)
+      case _ =>
+    }
+    if (method.localVariables != null) {
+      method.localVariables.iterator().asScala.foreach(l => { add(l.start, l); add(l.end, l) })
+    }
+    if (method.tryCatchBlocks != null) {
+      method.tryCatchBlocks.iterator().asScala.foreach(l => { add(l.start, l); add(l.handler, l); add(l.end, l) })
+    }
+
+    res.toMap
+  }
+
+  def substituteLabel(reference: AnyRef, from: LabelNode, to: LabelNode): Unit = {
+    def substList(list: java.util.List[LabelNode]) = {
+      list.asScala.zipWithIndex.foreach { case (l, i) =>
+        if (l == from) list.set(i, to)
+      }
+    }
+    reference match {
+      case jump: JumpInsnNode           => jump.label = to
+      case line: LineNumberNode         => line.start = to
+      case switch: LookupSwitchInsnNode => substList(switch.labels); if (switch.dflt == from) switch.dflt = to
+      case switch: TableSwitchInsnNode  => substList(switch.labels); if (switch.dflt == from) switch.dflt = to
+      case local: LocalVariableNode     =>
+        if (local.start == from) local.start = to
+        if (local.end == from) local.end = to
+      case handler: TryCatchBlockNode   =>
+        if (handler.start == from) handler.start = to
+        if (handler.handler == from) handler.handler = to
+        if (handler.end == from) handler.end = to
+    }
+  }
 }
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 682811bede..4af077c405 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -188,6 +188,64 @@ object LocalOpt {
     method.maxLocals = mw.getMaxLocals
     method.maxStack = mw.getMaxStack
   }
+
+  /**
+   * Removes LineNumberNodes that don't describe any executable instructions.
+   *
+   * This method expects (and asserts) that the `start` label of each LineNumberNode is the
+   * lexically preceeding label declaration.
+   */
+  def removeEmptyLineNumbers(method: MethodNode): Boolean = {
+    def isEmpty(node: AbstractInsnNode): Boolean = node.getNext match {
+      case null => true
+      case l: LineNumberNode => true
+      case n if n.getOpcode >= 0 => false
+      case n => isEmpty(n)
+    }
+
+    val initialSize = method.instructions.size
+    val iterator = method.instructions.iterator()
+    var previousLabel: LabelNode = null
+    while (iterator.hasNext) {
+      iterator.next match {
+        case label: LabelNode => previousLabel = label
+        case line: LineNumberNode if isEmpty(line) =>
+          assert(line.start == previousLabel)
+          iterator.remove()
+        case _ =>
+      }
+    }
+    method.instructions.size != initialSize
+  }
+
+  /**
+   * Removes unreferenced label declarations, also squashes sequences of label definitions.
+   *
+   *      [ops];              Label(a); Label(b);  [ops];
+   *   => subs([ops], b, a);  Label(a);            subs([ops], b, a);
+   */
+  def removeEmptyLabelNodes(method: MethodNode): Boolean = {
+    val references = labelReferences(method)
+
+    val initialSize = method.instructions.size
+    val iterator = method.instructions.iterator()
+    var prev: LabelNode = null
+    while (iterator.hasNext) {
+      iterator.next match {
+        case label: LabelNode =>
+          if (!references.contains(label)) iterator.remove()
+          else if (prev != null) {
+            references(label).foreach(substituteLabel(_, label, prev))
+            iterator.remove()
+          } else prev = label
+
+        case instruction =>
+          if (instruction.getOpcode >= 0) prev = null
+      }
+    }
+    method.instructions.size != initialSize
+  }
+
   /**
    * Apply various simplifications to branching instructions.
    */
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala
new file mode 100644
index 0000000000..213af4bcc1
--- /dev/null
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala
@@ -0,0 +1,101 @@
+package scala.tools.nsc
+package backend.jvm
+package opt
+
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.junit.Test
+import scala.tools.asm.Opcodes._
+import org.junit.Assert._
+import scala.tools.testing.AssertUtil._
+
+import CodeGenTools._
+import scala.tools.partest.ASMConverters
+import ASMConverters._
+
+@RunWith(classOf[JUnit4])
+class EmptyLabelsAndLineNumbersTest {
+  import UnreachableCodeTest._ // ".dead" extension method on instructions
+
+  @Test
+  def removeEmptyLineNumbers(): Unit = {
+    val ops = List[(Instruction, Boolean)](
+      Label(1),
+      LineNumber(1, Label(1)),
+      Label(2),
+      Label(3),
+      Op(RETURN),
+
+      Label(4),
+      LineNumber(4, Label(4)).dead,
+      LineNumber(5, Label(4)),
+      Op(RETURN),
+
+      Label(5),
+      LineNumber(6, Label(5)).dead,
+      Label(6),
+      Label(7),
+      LineNumber(7, Label(7)),
+      Op(RETURN),
+
+      Label(9),
+      LineNumber(8, Label(9)).dead,
+      Label(10)
+    )
+
+    val method = genMethod()(ops.map(_._1): _*)
+    assertTrue(LocalOpt.removeEmptyLineNumbers(method))
+    assertSameCode(instructionsFromMethod(method), ops.filter(_._2).map(_._1))
+  }
+
+  @Test
+  def badlyLocatedLineNumbers(): Unit = {
+    def t(ops: Instruction*) =
+      assertThrows[AssertionError](LocalOpt.removeEmptyLineNumbers(genMethod()(ops: _*)))
+
+    // line numbers have to be right after their referenced label node
+    t(LineNumber(0, Label(1)), Label(1))
+    t(Label(0), Label(1), LineNumber(0, Label(0)))
+  }
+
+  @Test
+  def removeEmptyLabels(): Unit = {
+    val handler = List(ExceptionHandler(Label(4), Label(5), Label(6), Some("java/lang/Throwable")))
+    def ops(target1: Int, target2: Int, target3: Int, target4: Int, target5: Int, target6: Int) = List[(Instruction, Boolean)](
+      Label(1),
+      Label(2).dead,
+      Label(3).dead,
+      LineNumber(3, Label(target1)),
+      VarOp(ILOAD, 1),
+      Jump(IFGE, Label(target2)),
+
+      Label(4),
+      Label(5).dead,
+      Label(6).dead,
+      VarOp(ILOAD, 2),
+      Jump(IFGE, Label(target3)),
+
+      Label(7),
+      Label(8).dead,
+      Label(9).dead,
+      Op(RETURN),
+
+      LookupSwitch(LOOKUPSWITCH, Label(target4), List(1,2), List(Label(target4), Label(target5))),
+      TableSwitch(TABLESWITCH, 1, 2, Label(target4), List(Label(target4), Label(target5))),
+
+      Label(10),
+      LineNumber(10, Label(10)),
+      Label(11).dead,
+      LineNumber(12, Label(target6))
+    )
+
+    val method = genMethod(handlers = handler)(ops(2, 3, 8, 8, 9, 11).map(_._1): _*)
+    assertTrue(LocalOpt.removeEmptyLabelNodes(method))
+    val m = convertMethod(method)
+    assertSameCode(m.instructions, ops(1, 1, 7, 7, 7, 10).filter(_._2).map(_._1))
+    assertTrue(m.handlers match {
+      case List(ExceptionHandler(Label(4), Label(4), Label(4), _)) => true
+      case _ => false
+    })
+  }
+}