From 8c6327dd3893363719dabff8d1a74286a5f9a1da Mon Sep 17 00:00:00 2001
From: Lukas Rytz <lukas.rytz@gmail.com>
Date: Tue, 7 Oct 2014 21:17:14 +0200
Subject: GenBCode: Simplify branching instructions

This commit implements simplifications to branching instructions, for
example `CondJump l; GOTO l` is replaced by `POP; GOTO l`.

The individual optimizations are explained in doc comments.

A later commit will add compiler flags to allow enabling the new
optimizations.
---
 .../nsc/backend/jvm/opt/SimplifyJumpsTest.scala    | 221 +++++++++++++++++++++
 1 file changed, 221 insertions(+)
 create mode 100644 test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala

(limited to 'test')

diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala
new file mode 100644
index 0000000000..a51bce7939
--- /dev/null
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala
@@ -0,0 +1,221 @@
+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 CodeGenTools._
+import scala.tools.partest.ASMConverters
+import ASMConverters._
+
+@RunWith(classOf[JUnit4])
+class SimplifyJumpsTest {
+  @Test
+  def simpleGotoReturn(): Unit = {
+    val ops = List(
+      Jump(GOTO, Label(2)), // replaced by RETURN
+      Op(ICONST_1),         // need some code, otherwise removeJumpToSuccessor kicks in
+      Op(POP),
+      Label(1),             // multiple labels OK
+      Label(2),
+      Label(3),
+      Op(RETURN)
+    )
+    val method = genMethod()(ops: _*)
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), Op(RETURN) :: ops.tail)
+  }
+
+  @Test
+  def simpleGotoThrow(): Unit = {
+    val rest = List(
+      Op(ICONST_1),         // need some code, otherwise removeJumpToSuccessor kicks in
+      Op(POP),
+      Label(1),
+      Label(2),
+      Label(3),
+      Op(ATHROW)
+    )
+    val method = genMethod()(
+      Op(ACONST_NULL) ::
+      Jump(GOTO, Label(2)) :: // replaced by ATHROW
+      rest: _*
+    )
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), Op(ACONST_NULL) :: Op(ATHROW) :: rest)
+  }
+
+  @Test
+  def gotoThrowInTry(): Unit = {
+    val handler = List(ExceptionHandler(Label(1), Label(2), Label(4), Some("java/lang/Throwable")))
+    val initialInstrs = List(
+      Label(1),
+      Op(ACONST_NULL),
+      Jump(GOTO, Label(3)), // not by ATHROW (would move the ATHROW into a try block)
+      Label(2),
+      Op(ICONST_1),         // need some code, otherwise removeJumpToSuccessor kicks in
+      Op(POP),
+      Label(3),
+      Op(ATHROW),
+      Label(4),
+      Op(POP),
+      Op(RETURN)
+    )
+    val method = genMethod(handlers = handler)(initialInstrs: _*)
+    assertFalse(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), initialInstrs)
+
+    val optMethod = genMethod()(initialInstrs: _*) // no handler
+    assertTrue(LocalOpt.simplifyJumps(optMethod))
+    assertSameCode(instructionsFromMethod(optMethod).take(3), List(Label(1), Op(ACONST_NULL), Op(ATHROW)))
+  }
+
+  @Test
+  def simplifyBranchOverGoto(): Unit = {
+    val begin = List(
+      VarOp(ILOAD, 1),
+      Jump(IFGE, Label(2))
+    )
+    val rest = List(
+      Jump(GOTO, Label(3)),
+      Label(11), // other labels here are allowed
+      Label(2),
+      VarOp(ILOAD, 1),
+      Op(RETURN),
+      Label(3),
+      VarOp(ILOAD, 1),
+      Op(IRETURN)
+    )
+    val method = genMethod()(begin ::: rest: _*)
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(
+      instructionsFromMethod(method),
+      List(VarOp(ILOAD, 1), Jump(IFLT, Label(3))) ::: rest.tail )
+
+    // no label allowed between begin and rest. if there's another label, then there could be a
+    // branch that label. eliminating the  GOTO would change the behavior.
+    val nonOptMethod = genMethod()(begin ::: Label(22) :: rest: _*)
+    assertFalse(LocalOpt.simplifyJumps(nonOptMethod))
+  }
+
+  @Test
+  def ensureGotoRemoved(): Unit = {
+    def code(jumps: Instruction*) = List(
+      VarOp(ILOAD, 1)) ::: jumps.toList ::: List(
+      Label(2),
+
+      Op(RETURN),
+      Label(3),
+      Op(RETURN)
+    )
+
+    // ensures that the goto is safely removed. ASM supports removing while iterating, but not the
+    // next element of the current. Here, the current is the IFGE, the next is the GOTO.
+    val method = genMethod()(code(Jump(IFGE, Label(2)), Jump(GOTO, Label(3))): _*)
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), code(Jump(IFLT, Label(3))))
+  }
+
+  @Test
+  def removeJumpToSuccessor(): Unit = {
+    val ops = List(
+      Jump(GOTO, Label(1)),
+      Label(11),
+      Label(1),
+      Label(2),
+      VarOp(ILOAD, 1),
+      Op(IRETURN)
+    )
+    val method = genMethod()(ops: _*)
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), ops.tail)
+  }
+
+  @Test
+  def collapseJumpChains(): Unit = {
+    def ops(target1: Int, target2: Int, target3: Int) = List(
+      VarOp(ILOAD, 1),
+      Jump(IFGE, Label(target1)), // initially 1, then 3
+      VarOp(ILOAD, 1),
+      Op(IRETURN),
+
+      Label(2),
+      Jump(GOTO, Label(target3)),
+
+      Label(1),
+      Jump(GOTO, Label(target2)),     // initially 2, then 3
+
+      VarOp(ILOAD, 1),                // some code to prevent jumpToSuccessor optimization (once target2 is replaced by 3)
+      Op(RETURN),
+
+      Label(3),
+      VarOp(ILOAD, 1),
+      Op(IRETURN)
+    )
+    val method = genMethod()(ops(1, 2, 3): _*)
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), ops(3, 3, 3))
+  }
+
+  @Test
+  def collapseJumpChainLoop(): Unit = {
+    def ops(target: Int) = List(
+      VarOp(ILOAD, 1),
+      Jump(IFGE, Label(target)),
+
+      Label(4),
+      Jump(GOTO, Label(3)),
+
+      VarOp(ILOAD, 1), // some code to prevent jumpToSuccessor (label 3)
+      Op(IRETURN),
+
+      Label(3),
+      Jump(GOTO, Label(4)),
+
+      Label(2),
+      Jump(GOTO, Label(3))
+    )
+
+    val method = genMethod()(ops(2): _*)
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), ops(3))
+  }
+
+  @Test
+  def simplifyThenElseSameTarget(): Unit = {
+    def ops(jumpOp: Instruction) = List(
+      VarOp(ILOAD, 1),
+      jumpOp,
+      Label(2),
+      Jump(GOTO, Label(1)),
+
+      VarOp(ILOAD, 1), // some code to prevent jumpToSuccessor (label 1)
+      Op(IRETURN),
+
+      Label(1),
+      VarOp(ILOAD, 1),
+      Op(IRETURN)
+    )
+
+    val method = genMethod()(ops(Jump(IFGE, Label(1))): _*)
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), ops(Op(POP)))
+  }
+
+  @Test
+  def thenElseSameTargetLoop(): Unit = {
+    def ops(br: List[Instruction]) = List(
+      VarOp(ILOAD, 1),
+      VarOp(ILOAD, 2)) ::: br ::: List(
+      Label(1),
+      Jump(GOTO, Label(1))
+    )
+    val method = genMethod()(ops(List(Jump(IF_ICMPGE, Label(1)))): _*)
+    assertTrue(LocalOpt.simplifyJumps(method))
+    assertSameCode(instructionsFromMethod(method), ops(List(Op(POP), Op(POP))))
+  }
+}
-- 
cgit v1.2.3


From 46653d6fd5b160e148894012c06f07461aa18edb Mon Sep 17 00:00:00 2001
From: Lukas Rytz <lukas.rytz@gmail.com>
Date: Tue, 7 Oct 2014 21:18:50 +0200
Subject: 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.
---
 .../tools/nsc/backend/jvm/opt/BytecodeUtils.scala  |  42 +++++++++
 .../scala/tools/nsc/backend/jvm/opt/LocalOpt.scala |  58 ++++++++++++
 .../jvm/opt/EmptyLabelsAndLineNumbersTest.scala    | 101 +++++++++++++++++++++
 3 files changed, 201 insertions(+)
 create mode 100644 test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala

(limited to 'test')

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
+    })
+  }
+}
-- 
cgit v1.2.3


From b3db5c34c72dfa80a3a049a896a65b7c7da56e89 Mon Sep 17 00:00:00 2001
From: Lukas Rytz <lukas.rytz@gmail.com>
Date: Tue, 7 Oct 2014 21:19:58 +0200
Subject: GenBCode: Command-line flags for enabling cleanup optimizations

Add command-line flags `Yopt:...` for simplifying jumps, eliminating
stale line number and label nodes.

`LocalOpt.methodOptimizations` applies all enabled intra-method
optimizations in the right order.

Some cleanups for unreachable code elimination and its tests.
---
 .../scala/tools/nsc/backend/jvm/BackendStats.scala |   2 +-
 .../scala/tools/nsc/backend/jvm/GenBCode.scala     |  13 +-
 .../scala/tools/nsc/backend/jvm/opt/LocalOpt.scala | 192 ++++++++++++++-------
 .../scala/tools/nsc/settings/ScalaSettings.scala   |  24 ++-
 .../scala/tools/nsc/backend/jvm/CodeGenTools.scala |  16 ++
 .../tools/nsc/backend/jvm/DirectCompileTest.scala  |  50 +++---
 .../jvm/opt/EmptyExceptionHandlersTest.scala       |   8 +-
 .../jvm/opt/EmptyLabelsAndLineNumbersTest.scala    |   8 +-
 .../nsc/backend/jvm/opt/SimplifyJumpsTest.scala    |  24 +--
 .../nsc/backend/jvm/opt/UnreachableCodeTest.scala  |  60 +++----
 10 files changed, 236 insertions(+), 161 deletions(-)

(limited to 'test')

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
index 4b9383c67c..03306f30aa 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala
@@ -14,7 +14,7 @@ object BackendStats {
 
   val bcodeInitTimer  = newSubTimer("bcode initialization", bcodeTimer)
   val bcodeGenStat    = newSubTimer("code generation", bcodeTimer)
-  val bcodeDceTimer   = newSubTimer("dead code elimination", bcodeTimer)
+  val methodOptTimer  = newSubTimer("intra-method optimizations", bcodeTimer)
   val bcodeWriteTimer = newSubTimer("classfile writing", bcodeTimer)
 
   def timed[T](timer: Statistics.Timer)(body: => T): T = {
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
index ba94a9c44c..a45f586666 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
@@ -9,12 +9,12 @@ package tools.nsc
 package backend
 package jvm
 
-import scala.collection.{ mutable, immutable }
-import scala.annotation.switch
+import scala.collection.mutable
 import scala.reflect.internal.util.Statistics
 
 import scala.tools.asm
 import scala.tools.asm.tree.ClassNode
+import scala.tools.nsc.backend.jvm.opt.LocalOpt
 
 /*
  *  Prepare in-memory representations of classfiles using the ASM Tree API, and serialize them to disk.
@@ -215,13 +215,10 @@ 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
-        }
+      lazy val localOpt = new LocalOpt(settings)
 
-        dce()
+      def localOptimizations(classNode: ClassNode): Unit = {
+        BackendStats.timed(BackendStats.methodOptTimer)(localOpt.methodOptimizations(classNode))
       }
 
       def run() {
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 4af077c405..29754d5500 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -7,126 +7,203 @@ package scala.tools.nsc
 package backend.jvm
 package opt
 
+import scala.annotation.switch
 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 }
 import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
+import scala.tools.nsc.settings.ScalaSettings
 
 /**
- * Intra-Method optimizations.
+ * Optimizations within a single method.
+ *
+ * unreachable code
+ *   - removes instrucions of basic blocks to which no branch instruction points
+ *   + enables eliminating some exception handlers and local variable descriptors
+ *     > eliminating them is required for correctness, as explained in `removeUnreachableCode`
+ *
+ * empty exception handlers
+ *   - removes exception handlers whose try block is empty
+ *   + eliminating a handler where the try block is empty and reachable will turn the catch block
+ *     unreachble. in this case "unreachable code" is invoked recursively until reaching a fixpiont.
+ *     > for try blocks that are unreachable, "unreachable code" removes also the instructions of the
+ *       catch block, and the recrusive invocation is not necessary.
+ *
+ * simplify jumps
+ *   - various simplifications, see doc domments of individual optimizations
+ *   + changing or eliminating jumps may render some code unreachable, therefore "simplify jumps" is
+ *     executed in a loop with "unreachable code"
+ *
+ * empty local variable descriptors
+ *   - removes entries from the local variable table where the variable is not actually used
+ *   + enables eliminating labels that the entry points to (if they are not otherwise referenced)
+ *
+ * empty line numbers
+ *   - eliminates line number nodes that describe no executable instructions
+ *   + enables eliminating the label of the line number node (if it's not otherwise referenced)
+ *
+ * stale labels
+ *   - eliminate labels that are not referenced, merge sequences of label definitions.
  */
-object LocalOpt {
+class LocalOpt(settings: ScalaSettings) {
   /**
-   * Remove unreachable instructions from all (non-abstract) methods.
+   * Remove unreachable instructions from all (non-abstract) methods and apply various other
+   * cleanups to the bytecode.
    *
    * @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
+  def methodOptimizations(clazz: ClassNode): Boolean = {
+    settings.Yopt.value.nonEmpty && clazz.methods.asScala.foldLeft(false) {
+      case (changed, method) => methodOptimizations(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
+   * Also simplifies branching instructions, removes unused local variable descriptors, empty
+   * exception handlers, unnecessary label declarations and empty line number nodes.
    *
-   * Returns `true` if dead code in `method` has been eliminated.
+   * Returns `true` if the bytecode of `method` was changed.
    */
-  private def removeUnreachableCode(method: MethodNode, ownerClassName: String): Boolean = {
+  private def methodOptimizations(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
+    // This is required for correctness, for example:
+    //
+    //   def f = { return 0; try { 1 } catch { case _ => 2 } }
+    //
+    // The result after removeUnreachableCodeImpl:
+    //
+    //   TRYCATCHBLOCK L0 L1 L2 java/lang/Exception
+    //   L4
+    //     ICONST_0
+    //     IRETURN
+    //   L0
+    //   L1
+    //   L2
+    //
+    // If we don't eliminate the handler, the ClassWriter emits:
+    //
+    //   TRYCATCHBLOCK L0 L0 L0 java/lang/Exception
+    //   L1
+    //     ICONST_0
+    //     IRETURN
+    //   L0
+    //
+    // This triggers "ClassFormatError: Illegal exception table range in class file C". Similar
+    // for local variables in dead blocks. Maybe that's a bug in the ASM framework.
+
+    var recurse = true
+    var codeHandlersOrJumpsChanged = false
+    while (recurse) {
+      // unreachable-code, empty-handlers and simplify-jumps run until reaching a fixpoint (see doc on class LocalOpt)
+      val (codeRemoved, handlersRemoved, liveHandlerRemoved) = if (settings.YoptUnreachableCode) {
+        val (codeRemoved, liveLabels) = removeUnreachableCodeImpl(method, ownerClassName)
+        val removedHandlers = removeEmptyExceptionHandlers(method)
+        (codeRemoved, removedHandlers.nonEmpty, removedHandlers.exists(h => liveLabels(h.start)))
+      } else {
+        (false, false, false)
+      }
+
+      val jumpsChanged = if (settings.YoptSimplifyJumps) simplifyJumps(method) else false
+
+      codeHandlersOrJumpsChanged ||= (codeRemoved || handlersRemoved || jumpsChanged)
+
+      // The doc comment of class LocalOpt explains why we recurse if jumpsChanged || liveHandlerRemoved
+      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
+
+    val lineNumbersRemoved = if (settings.YoptEmptyLineNumbers) removeEmptyLineNumbers(method) else false
+
+    val labelsRemoved = if (settings.YoptEmptyLabels) removeEmptyLabelNodes(method) else false
+
+    // assert that local variable annotations are empty (we don't emit them) - otherwise we'd have
+    // to eliminate those covering an empty range, similar to removeUnusedLocalVariableNodes.
     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
+    codeHandlersOrJumpsChanged || localsRemoved || lineNumbersRemoved || labelsRemoved
   }
 
-  private def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: String): Boolean = {
-    val initialSize = method.instructions.size
-    if (initialSize == 0) return false
-
+  /**
+   * Removes unreachable basic blocks.
+   *
+   * TODO: rewrite, don't use computeMaxLocalsMaxStack (runs a ClassWriter) / Analyzer. Too slow.
+   */
+  def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: String): (Boolean, Set[LabelNode]) = {
     // 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
 
+    val initialSize = method.instructions.size
     var i = 0
+    var liveLabels = Set.empty[LabelNode]
     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()
+      itr.next() match {
+        case l: LabelNode =>
+          if (frames(i) != null) liveLabels += l
+
+        case ins =>
+          // label nodes are not removed: they might be referenced for example in a LocalVariableNode
+          if (frames(i) == null || ins.getOpcode == Opcodes.NOP) {
+            // 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
-    }
+    (method.instructions.size != initialSize, liveLabels)
   }
 
   /**
    * 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.
    *
+   * There are no executable instructions that we can assume don't throw (eg ILOAD). The JVM spec
+   * basically says that a VirtualMachineError may be thrown at any time:
+   *   http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.3
+   *
    * Note that no instructions are eliminated.
    *
-   * @return `true` if some exception handler was eliminated.
+   * @return the set of removed handlers
    */
-  def removeEmptyExceptionHandlers(method: MethodNode): Boolean = {
+  def removeEmptyExceptionHandlers(method: MethodNode): Set[TryCatchBlockNode] = {
     /** True if there exists code between start and end. */
     def containsExecutableCode(start: AbstractInsnNode, end: LabelNode): Boolean = {
-      start != end && (start.getOpcode match {
+      start != end && ((start.getOpcode : @switch) match {
         // FrameNode, LabelNode and LineNumberNode have opcode == -1.
-        case -1 | Opcodes.NOP | Opcodes.GOTO => containsExecutableCode(start.getNext, end)
+        case -1 | Opcodes.GOTO => containsExecutableCode(start.getNext, end)
         case _ => true
       })
     }
 
-    val initialNumberHandlers = method.tryCatchBlocks.size
+    var removedHandlers = Set.empty[TryCatchBlockNode]
     val handlersIter = method.tryCatchBlocks.iterator()
     while(handlersIter.hasNext) {
       val handler = handlersIter.next()
-      if (!containsExecutableCode(handler.start, handler.end)) handlersIter.remove()
+      if (!containsExecutableCode(handler.start, handler.end)) {
+        removedHandlers += handler
+        handlersIter.remove()
+      }
     }
-    method.tryCatchBlocks.size != initialNumberHandlers
+    removedHandlers
   }
 
   /**
@@ -136,13 +213,11 @@ object LocalOpt {
    * 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 v: VarInsnNode if v.`var` == varIndex => true
         case _ => variableIsUsed(start.getNext, end, varIndex)
       })
     }
@@ -162,10 +237,9 @@ object LocalOpt {
       if (!used)
         localsIter.remove()
     }
-    method.localVariables.size == initialNumVars
+    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/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 850534f2cc..2406b9e66b 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -210,21 +210,25 @@ trait ScalaSettings extends AbsScalaSettings
   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 unreachableCode         = Choice("unreachable-code",          "Eliminate unreachable code, exception handlers protecting no instructions, debug information of eliminated variables.")
+    val simplifyJumps           = Choice("simplify-jumps",            "Simplify branching instructions, eliminate unnecessery ones.")
+    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 lNone           = Choice("l:none",      "Don't enable any optimizations")
+    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(lDefault)
-    val lMethod         = Choice("l:method",    "Intra-method optimizations: "+ methodChoices.mkString(","),                              expandsTo = methodChoices)
+    private val methodChoices = List(unreachableCode, simplifyJumps, recurseUnreachableJumps, emptyLineNumbers, emptyLabels)
+    val lMethod         = Choice("l:method",    "Enable 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)
+    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", "Cross-method optmizations across the entire classpath: "+ classpathChoices.mkString(","), expandsTo = classpathChoices)
+    val lClasspath      = Choice("l:classpath", "Enable cross-method optmizations across the entire classpath: "+ classpathChoices.mkString(","), expandsTo = classpathChoices)
   }
 
   val Yopt = MultiChoiceSetting(
@@ -233,7 +237,11 @@ trait ScalaSettings extends AbsScalaSettings
     descr = "Enable optimizations",
     domain = YoptChoices)
 
-  def YoptUnreachableCode: Boolean = !Yopt.isSetByUser || Yopt.contains(YoptChoices.unreachableCode)
+  def YoptUnreachableCode         = !Yopt.isSetByUser || Yopt.contains(YoptChoices.unreachableCode)
+  def YoptSimplifyJumps           = Yopt.contains(YoptChoices.simplifyJumps)
+  def YoptRecurseUnreachableJumps = Yopt.contains(YoptChoices.recurseUnreachableJumps)
+  def YoptEmptyLineNumbers        = Yopt.contains(YoptChoices.emptyLineNumbers)
+  def YoptEmptyLabels             = Yopt.contains(YoptChoices.emptyLabels)
 
   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."
 
diff --git a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
index b892eb36cf..857263d65f 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
@@ -7,6 +7,8 @@ import scala.reflect.io.VirtualDirectory
 import scala.tools.asm.Opcodes
 import scala.tools.asm.tree.{AbstractInsnNode, LabelNode, ClassNode, MethodNode}
 import scala.tools.cmd.CommandLineParser
+import scala.tools.nsc.backend.jvm.opt.LocalOpt
+import scala.tools.nsc.settings.{MutableSettings, ScalaSettings}
 import scala.tools.nsc.{Settings, Global}
 import scala.tools.partest.ASMConverters
 import scala.collection.JavaConverters._
@@ -79,4 +81,18 @@ object CodeGenTools {
 
   def getSingleMethod(classNode: ClassNode, name: String): Method =
     convertMethod(classNode.methods.asScala.toList.find(_.name == name).get)
+
+  val localOpt = {
+    val settings = new MutableSettings(msg => throw new IllegalArgumentException(msg))
+    settings.processArguments(List("-Yopt:l:method"), processAll = true)
+    new LocalOpt(settings)
+  }
+
+  import scala.language.implicitConversions
+
+  implicit def aliveInstruction(ins: Instruction): (Instruction, Boolean) = (ins, true)
+
+  implicit class MortalInstruction(val ins: Instruction) extends AnyVal {
+    def dead: (Instruction, Boolean) = (ins, false)
+  }
 }
diff --git a/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala b/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala
index 2fb5bb8052..89900291ca 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala
@@ -10,13 +10,12 @@ import scala.tools.partest.ASMConverters._
 
 @RunWith(classOf[JUnit4])
 class DirectCompileTest {
-  val compiler = newCompiler(extraArgs = "-Ybackend:GenBCode")
+  val compiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:method")
 
   @Test
   def testCompile(): Unit = {
     val List(("C.class", bytes)) = compile(compiler)(
-      """
-        |class C {
+      """class C {
         |  def f = 1
         |}
       """.stripMargin)
@@ -26,19 +25,12 @@ class DirectCompileTest {
 
   @Test
   def testCompileClasses(): Unit = {
-    val List(cClass, cModuleClass) = compileClasses(compiler)(
-      """
-        |class C
-        |object C
-      """.stripMargin)
+    val List(cClass, cModuleClass) = compileClasses(compiler)("class C; object C")
 
     assertTrue(cClass.name == "C")
     assertTrue(cModuleClass.name == "C$")
 
-    val List(dMirror, dModuleClass) = compileClasses(compiler)(
-      """
-        |object D
-      """.stripMargin)
+    val List(dMirror, dModuleClass) = compileClasses(compiler)("object D")
 
     assertTrue(dMirror.name == "D")
     assertTrue(dModuleClass.name == "D$")
@@ -47,35 +39,35 @@ class DirectCompileTest {
   @Test
   def testCompileMethods(): Unit = {
     val List(f, g) = compileMethods(compiler)(
-      """
-        |def f = 10
+      """def f = 10
         |def g = f
       """.stripMargin)
     assertTrue(f.name == "f")
     assertTrue(g.name == "g")
 
-    assertTrue(instructionsFromMethod(f).dropNonOp ===
+    assertSameCode(instructionsFromMethod(f).dropNonOp,
       List(IntOp(BIPUSH, 10), Op(IRETURN)))
 
-    assertTrue(instructionsFromMethod(g).dropNonOp ===
-      List(VarOp(ALOAD, 0), Invoke(INVOKEVIRTUAL, "C", "f", "()I", false), Op(IRETURN)))
+    assertSameCode(instructionsFromMethod(g).dropNonOp,
+      List(VarOp(ALOAD, 0), Invoke(INVOKEVIRTUAL, "C", "f", "()I", itf = false), Op(IRETURN)))
   }
 
   @Test
   def testDropNonOpAliveLabels(): Unit = {
+    // makes sure that dropNoOp doesn't drop labels that are being used
     val List(f) = compileMethods(compiler)("""def f(x: Int) = if (x == 0) "a" else "b"""")
-    assertTrue(instructionsFromMethod(f).dropNonOp === List(
-        VarOp(ILOAD, 1),
-        Op(ICONST_0),
-        Jump(IF_ICMPEQ, Label(6)),
-        Jump(GOTO, Label(10)),
-        Label(6),
-        Ldc(LDC, "a"),
-        Jump(GOTO, Label(13)),
-        Label(10),
-        Ldc(LDC, "b"),
-        Label(13),
-        Op(ARETURN)
+    assertSameCode(instructionsFromMethod(f).dropLinesFrames, List(
+      Label(0),
+      VarOp(ILOAD, 1),
+      Op(ICONST_0),
+      Jump(IF_ICMPNE,
+      Label(7)),
+      Ldc(LDC, "a"),
+      Op(ARETURN),
+      Label(7),
+      Ldc(LDC, "b"),
+      Op(ARETURN),
+      Label(11)
     ))
   }
 }
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyExceptionHandlersTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyExceptionHandlersTest.scala
index 57fa1a7b66..7d83c54b5b 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyExceptionHandlersTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyExceptionHandlersTest.scala
@@ -26,7 +26,7 @@ class EmptyExceptionHandlersTest {
       Op(RETURN)
     )
     assertTrue(convertMethod(asmMethod).handlers.length == 1)
-    LocalOpt.removeEmptyExceptionHandlers(asmMethod)
+    localOpt.removeEmptyExceptionHandlers(asmMethod)
     assertTrue(convertMethod(asmMethod).handlers.isEmpty)
   }
 
@@ -35,12 +35,8 @@ class EmptyExceptionHandlersTest {
     val handlers = List(ExceptionHandler(Label(1), Label(2), Label(2), Some(exceptionDescriptor)))
     val asmMethod = genMethod(handlers = handlers)(
       Label(1),          // nops only
-      Op(NOP),
-      Op(NOP),
       Jump(GOTO, Label(3)),
-      Op(NOP),
       Label(3),
-      Op(NOP),
       Jump(GOTO, Label(4)),
 
       Label(2),          // handler
@@ -51,7 +47,7 @@ class EmptyExceptionHandlersTest {
       Op(RETURN)
     )
     assertTrue(convertMethod(asmMethod).handlers.length == 1)
-    LocalOpt.removeEmptyExceptionHandlers(asmMethod)
+    localOpt.removeEmptyExceptionHandlers(asmMethod)
     assertTrue(convertMethod(asmMethod).handlers.isEmpty)
   }
 
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala
index 213af4bcc1..8c0168826e 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala
@@ -15,8 +15,6 @@ import ASMConverters._
 
 @RunWith(classOf[JUnit4])
 class EmptyLabelsAndLineNumbersTest {
-  import UnreachableCodeTest._ // ".dead" extension method on instructions
-
   @Test
   def removeEmptyLineNumbers(): Unit = {
     val ops = List[(Instruction, Boolean)](
@@ -44,14 +42,14 @@ class EmptyLabelsAndLineNumbersTest {
     )
 
     val method = genMethod()(ops.map(_._1): _*)
-    assertTrue(LocalOpt.removeEmptyLineNumbers(method))
+    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: _*)))
+      assertThrows[AssertionError](localOpt.removeEmptyLineNumbers(genMethod()(ops: _*)))
 
     // line numbers have to be right after their referenced label node
     t(LineNumber(0, Label(1)), Label(1))
@@ -90,7 +88,7 @@ class EmptyLabelsAndLineNumbersTest {
     )
 
     val method = genMethod(handlers = handler)(ops(2, 3, 8, 8, 9, 11).map(_._1): _*)
-    assertTrue(LocalOpt.removeEmptyLabelNodes(method))
+    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 {
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala
index a51bce7939..360fa1d23d 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala
@@ -26,7 +26,7 @@ class SimplifyJumpsTest {
       Op(RETURN)
     )
     val method = genMethod()(ops: _*)
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), Op(RETURN) :: ops.tail)
   }
 
@@ -45,7 +45,7 @@ class SimplifyJumpsTest {
       Jump(GOTO, Label(2)) :: // replaced by ATHROW
       rest: _*
     )
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), Op(ACONST_NULL) :: Op(ATHROW) :: rest)
   }
 
@@ -66,11 +66,11 @@ class SimplifyJumpsTest {
       Op(RETURN)
     )
     val method = genMethod(handlers = handler)(initialInstrs: _*)
-    assertFalse(LocalOpt.simplifyJumps(method))
+    assertFalse(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), initialInstrs)
 
     val optMethod = genMethod()(initialInstrs: _*) // no handler
-    assertTrue(LocalOpt.simplifyJumps(optMethod))
+    assertTrue(localOpt.simplifyJumps(optMethod))
     assertSameCode(instructionsFromMethod(optMethod).take(3), List(Label(1), Op(ACONST_NULL), Op(ATHROW)))
   }
 
@@ -91,7 +91,7 @@ class SimplifyJumpsTest {
       Op(IRETURN)
     )
     val method = genMethod()(begin ::: rest: _*)
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(
       instructionsFromMethod(method),
       List(VarOp(ILOAD, 1), Jump(IFLT, Label(3))) ::: rest.tail )
@@ -99,7 +99,7 @@ class SimplifyJumpsTest {
     // no label allowed between begin and rest. if there's another label, then there could be a
     // branch that label. eliminating the  GOTO would change the behavior.
     val nonOptMethod = genMethod()(begin ::: Label(22) :: rest: _*)
-    assertFalse(LocalOpt.simplifyJumps(nonOptMethod))
+    assertFalse(localOpt.simplifyJumps(nonOptMethod))
   }
 
   @Test
@@ -116,7 +116,7 @@ class SimplifyJumpsTest {
     // ensures that the goto is safely removed. ASM supports removing while iterating, but not the
     // next element of the current. Here, the current is the IFGE, the next is the GOTO.
     val method = genMethod()(code(Jump(IFGE, Label(2)), Jump(GOTO, Label(3))): _*)
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), code(Jump(IFLT, Label(3))))
   }
 
@@ -131,7 +131,7 @@ class SimplifyJumpsTest {
       Op(IRETURN)
     )
     val method = genMethod()(ops: _*)
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), ops.tail)
   }
 
@@ -157,7 +157,7 @@ class SimplifyJumpsTest {
       Op(IRETURN)
     )
     val method = genMethod()(ops(1, 2, 3): _*)
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), ops(3, 3, 3))
   }
 
@@ -181,7 +181,7 @@ class SimplifyJumpsTest {
     )
 
     val method = genMethod()(ops(2): _*)
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), ops(3))
   }
 
@@ -202,7 +202,7 @@ class SimplifyJumpsTest {
     )
 
     val method = genMethod()(ops(Jump(IFGE, Label(1))): _*)
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), ops(Op(POP)))
   }
 
@@ -215,7 +215,7 @@ class SimplifyJumpsTest {
       Jump(GOTO, Label(1))
     )
     val method = genMethod()(ops(List(Jump(IF_ICMPGE, Label(1)))): _*)
-    assertTrue(LocalOpt.simplifyJumps(method))
+    assertTrue(localOpt.simplifyJumps(method))
     assertSameCode(instructionsFromMethod(method), ops(List(Op(POP), Op(POP))))
   }
 }
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala
index a3bd7ae6fe..4a45dd9138 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala
@@ -16,12 +16,20 @@ import ASMConverters._
 
 @RunWith(classOf[JUnit4])
 class UnreachableCodeTest {
-  import UnreachableCodeTest._
+
+  def assertEliminateDead(code: (Instruction, Boolean)*): Unit = {
+    val method = genMethod()(code.map(_._1): _*)
+    localOpt.removeUnreachableCodeImpl(method, "C")
+    val nonEliminated = instructionsFromMethod(method)
+    val expectedLive = code.filter(_._2).map(_._1).toList
+    assertSameCode(nonEliminated, expectedLive)
+  }
 
   // jvm-1.6 enables emitting stack map frames, which impacts the code generation wrt dead basic blocks,
   // see comment in BCodeBodyBuilder
-  val dceCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:unreachable-code")
-  val noOptCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:l:none")
+  val methodOptCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:l:method")
+  val dceCompiler       = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:unreachable-code")
+  val noOptCompiler     = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:l:none")
 
   // jvm-1.5 disables computing stack map frames, and it emits dead code as-is.
   val noOptNoFramesCompiler = newCompiler(extraArgs = "-target:jvm-1.5 -Ybackend:GenBCode -Yopt:l:none")
@@ -48,8 +56,8 @@ class UnreachableCodeTest {
   @Test
   def eliminateNop(): Unit = {
     assertEliminateDead(
-      // not dead, since visited by data flow analysis. need a different opt to eliminate it.
-      Op(NOP),
+      // reachable, but removed anyway.
+      Op(NOP).dead,
       Op(RETURN),
       Op(NOP).dead
     )
@@ -136,28 +144,31 @@ class UnreachableCodeTest {
 
   @Test
   def eliminateDeadCatchBlocks(): Unit = {
+    // the Label(1) is live: it's used in the local variable descriptor table (local variable "this" has a range from 0 to 1).
+    def wrapInDefault(code: Instruction*) = List(Label(0), LineNumber(1, Label(0))) ::: code.toList ::: List(Label(1))
+
     val code = "def f: Int = { return 0; try { 1 } catch { case _: Exception => 2 } }"
-    assertSameCode(singleMethodInstructions(dceCompiler)(code).dropNonOp,
-                   List(Op(ICONST_0), Op(IRETURN)))
+    val m = singleMethod(dceCompiler)(code)
+    assertTrue(m.handlers.isEmpty) // redundant (if code is gone, handler is gone), but done once here for extra safety
+    assertSameCode(m.instructions,
+      wrapInDefault(Op(ICONST_0), Op(IRETURN)))
 
     val code2 = "def f: Unit = { try { } catch { case _: Exception => () }; () }"
-    // DCE only removes dead basic blocks, but not NOPs, and also not useless jumps
-    assertSameCode(singleMethodInstructions(dceCompiler)(code2).dropNonOp,
-                   List(Op(NOP), Jump(GOTO, Label(33)), Label(33), Op(RETURN)))
+    // requires fixpoint optimization of methodOptCompiler (dce alone is not enough): first the handler is eliminated, then it's dead catch block.
+    assertSameCode(singleMethodInstructions(methodOptCompiler)(code2), wrapInDefault(Op(RETURN)))
 
     val code3 = "def f: Unit = { try { } catch { case _: Exception => try { } catch { case _: Exception => () } }; () }"
-    assertSameCode(singleMethodInstructions(dceCompiler)(code3).dropNonOp,
-      List(Op(NOP), Jump(GOTO, Label(33)), Label(33), Op(RETURN)))
+    assertSameCode(singleMethodInstructions(methodOptCompiler)(code3), wrapInDefault(Op(RETURN)))
 
+    // this example requires two iterations to get rid of the outer handler.
+    // the first iteration of DCE cannot remove the inner handler. then the inner (empty) handler is removed.
+    // then the second iteration of DCE removes the inner catch block, and then the outer handler is removed.
     val code4 = "def f: Unit = { try { try { } catch { case _: Exception => () } } catch { case _: Exception => () }; () }"
-    assertSameCode(singleMethodInstructions(dceCompiler)(code4).dropNonOp,
-      List(Op(NOP), Jump(GOTO, Label(4)), Label(4), Jump(GOTO, Label(7)), Label(7), Op(RETURN)))
+    assertSameCode(singleMethodInstructions(methodOptCompiler)(code4), wrapInDefault(Op(RETURN)))
   }
 
   @Test // test the dce-testing tools
   def metaTest(): Unit = {
-    assertEliminateDead() // no instructions
-
     assertThrows[AssertionError](
       assertEliminateDead(Op(RETURN).dead),
       _.contains("Expected: List()\nActual  : List(Op(RETURN))")
@@ -198,20 +209,3 @@ class UnreachableCodeTest {
                List(FrameEntry(F_FULL, List(INTEGER, DOUBLE, Label(1)), List("java/lang/Object", Label(3))), Label(1), Label(3)))
   }
 }
-
-object UnreachableCodeTest {
-  import scala.language.implicitConversions
-  implicit def aliveInstruction(ins: Instruction): (Instruction, Boolean) = (ins, true)
-
-  implicit class MortalInstruction(val ins: Instruction) extends AnyVal {
-    def dead: (Instruction, Boolean) = (ins, false)
-  }
-
-  def assertEliminateDead(code: (Instruction, Boolean)*): Unit = {
-    val cls = wrapInClass(genMethod()(code.map(_._1): _*))
-    LocalOpt.removeUnreachableCode(cls)
-    val nonEliminated = instructionsFromMethod(cls.methods.get(0))
-    val expectedLive = code.filter(_._2).map(_._1).toList
-    assertSameCode(nonEliminated, expectedLive)
-  }
-}
-- 
cgit v1.2.3


From be82759d7f56f1d78b4123fec0706f4f4565133e Mon Sep 17 00:00:00 2001
From: Lukas Rytz <lukas.rytz@gmail.com>
Date: Fri, 10 Oct 2014 18:02:20 +0200
Subject: GenBCode: Tests for combined method-level optimizations

---
 .../scala/tools/nsc/backend/jvm/CodeGenTools.scala |  5 ++
 .../nsc/backend/jvm/opt/MethodLevelOpts.scala      | 83 ++++++++++++++++++++++
 2 files changed, 88 insertions(+)
 create mode 100644 test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala

(limited to 'test')

diff --git a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
index 857263d65f..c1c5a71b83 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
@@ -82,6 +82,11 @@ object CodeGenTools {
   def getSingleMethod(classNode: ClassNode, name: String): Method =
     convertMethod(classNode.methods.asScala.toList.find(_.name == name).get)
 
+  def assertHandlerLabelPostions(h: ExceptionHandler, instructions: List[Instruction], startIndex: Int, endIndex: Int, handlerIndex: Int): Unit = {
+    val insVec = instructions.toVector
+    assertTrue(h.start == insVec(startIndex) && h.end == insVec(endIndex) && h.handler == insVec(handlerIndex))
+  }
+
   val localOpt = {
     val settings = new MutableSettings(msg => throw new IllegalArgumentException(msg))
     settings.processArguments(List("-Yopt:l:method"), processAll = true)
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala
new file mode 100644
index 0000000000..390e53fc4a
--- /dev/null
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala
@@ -0,0 +1,83 @@
+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 MethodLevelOpts {
+  val methodOptCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:l:method")
+
+  def wrapInDefault(code: Instruction*) = List(Label(0), LineNumber(1, Label(0))) ::: code.toList ::: List(Label(1))
+
+  @Test
+  def eliminateEmptyTry(): Unit = {
+    val code = "def f = { try {} catch { case _: Throwable => 0; () }; 1 }"
+    assertSameCode(singleMethodInstructions(methodOptCompiler)(code), wrapInDefault(Op(ICONST_1), Op(IRETURN)))
+  }
+
+  @Test
+  def cannotEliminateLoadBoxedUnit(): Unit = {
+    // the compiler inserts a boxed into the try block. it's therefore non-empty (and live) and not eliminated.
+    val code = "def f = { try {} catch { case _: Throwable => 0 }; 1 }"
+    val m = singleMethod(methodOptCompiler)(code)
+    assertTrue(m.handlers.length == 1)
+    assertSameCode(m.instructions.take(3), List(Label(0), LineNumber(1, Label(0)), Field(GETSTATIC, "scala/runtime/BoxedUnit", "UNIT", "Lscala/runtime/BoxedUnit;")))
+  }
+
+  @Test
+  def inlineThrowInCachtNotTry(): Unit = {
+    // the try block does not contain the `ATHROW` instruction, but in the catch block, `ATHROW` is inlined
+    val code = "def f(e: Exception) = throw { try e catch { case _: Throwable => e } }"
+    val m = singleMethod(methodOptCompiler)(code)
+    assertHandlerLabelPostions(m.handlers.head, m.instructions, 0, 3, 5)
+    assertSameCode(m.instructions,
+      wrapInDefault(VarOp(ALOAD, 1), Label(3), Op(ATHROW), Label(5), FrameEntry(4, List(), List("java/lang/Throwable")), Op(POP), VarOp(ALOAD, 1), Op(ATHROW))
+    )
+  }
+
+  @Test
+  def inlineReturnInCachtNotTry(): Unit = {
+    val code = "def f: Int = return { try 1 catch { case _: Throwable => 2 } }"
+    // cannot inline the IRETURN into the try block (because RETURN may throw IllegalMonitorState)
+    val m = singleMethod(methodOptCompiler)(code)
+    assertHandlerLabelPostions(m.handlers.head, m.instructions, 0, 3, 5)
+    assertSameCode(m.instructions,
+      wrapInDefault(Op(ICONST_1), Label(3), Op(IRETURN), Label(5), FrameEntry(4, List(), List("java/lang/Throwable")), Op(POP), Op(ICONST_2), Op(IRETURN)))
+  }
+
+  @Test
+  def simplifyJumpsInTryCatchFinally(): Unit = {
+    val code =
+      """def f: Int =
+        |  try {
+        |    return 1
+        |  } catch {
+        |    case _: Throwable =>
+        |    return 2
+        |  } finally {
+        |    return 2
+        |    // dead
+        |    val x = try 10 catch { case _: Throwable => 11 }
+        |    println(x)
+        |  }
+      """.stripMargin
+    val m = singleMethod(methodOptCompiler)(code)
+    assertTrue(m.handlers.length == 2)
+    assertSameCode(m.instructions.dropNonOp, // drop line numbers and lables that are only used by line numbers
+
+      // one single label left :-)
+      List(Op(ICONST_1), VarOp(ISTORE, 2), Jump(GOTO, Label(20)), Op(POP), Op(ICONST_2), VarOp(ISTORE, 2), Jump(GOTO, Label(20)), VarOp(ASTORE, 3), Op(ICONST_2), Op(IRETURN), Label(20), Op(ICONST_2), Op(IRETURN))
+    )
+  }
+}
-- 
cgit v1.2.3


From d39525ac06c8d319b43d3388d624fb2c1dcbd601 Mon Sep 17 00:00:00 2001
From: Lukas Rytz <lukas.rytz@gmail.com>
Date: Mon, 13 Oct 2014 14:34:24 +0200
Subject: 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
---
 .../tools/nsc/backend/jvm/opt/BytecodeUtils.scala  |  13 +++
 .../scala/tools/nsc/backend/jvm/opt/LocalOpt.scala | 104 ++++++++++++++++++---
 .../scala/tools/nsc/settings/ScalaSettings.scala   |  12 ++-
 .../jvm/opt/CompactLocalVariablesTest.scala        |  80 ++++++++++++++++
 4 files changed, 191 insertions(+), 18 deletions(-)
 create mode 100644 test/junit/scala/tools/nsc/backend/jvm/opt/CompactLocalVariablesTest.scala

(limited to 'test')

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,22 +227,97 @@ 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."
 
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/CompactLocalVariablesTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/CompactLocalVariablesTest.scala
new file mode 100644
index 0000000000..fc748196d0
--- /dev/null
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/CompactLocalVariablesTest.scala
@@ -0,0 +1,80 @@
+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 CodeGenTools._
+import scala.tools.partest.ASMConverters
+import ASMConverters._
+
+@RunWith(classOf[JUnit4])
+class CompactLocalVariablesTest {
+
+  // recurse-unreachable-jumps is required for eliminating catch blocks, in the first dce round they
+  // are still live.only after eliminating the empty handler the catch blocks become unreachable.
+  val methodOptCompiler     = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:unreachable-code,recurse-unreachable-jumps,compact-locals")
+  val noCompactVarsCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:unreachable-code,recurse-unreachable-jumps")
+
+  @Test
+  def compactUnused(): Unit = {
+    val code =
+      """def f: Double = {
+        |  try { }
+        |  catch {
+        |    case _: Throwable =>
+        |      // eliminated by dce
+        |      val i = 1
+        |      val d = 1d
+        |      val f = 1f
+        |      val l = 1l
+        |  }
+        |
+        |  val i = 1      // variable index 1 (it's an instance method, so at index 0 we have `this`)
+        |  val d = 1d     // 2,3
+        |  val f = 1f     // 4
+        |  val l = 1l     // 5,6
+        |
+        |  try { }
+        |  catch {
+        |    case _: Throwable =>
+        |      // eliminated by dce
+        |      val i = 1
+        |      val d = 1d
+        |      val f = 1f
+        |      val l = 1l
+        |  }
+        |
+        |  val ii = 1     // 7
+        |  val dd = 1d    // 8,9
+        |  val ff = 1f    // 10
+        |  val ll = 1l    // 11,12
+        |
+        |  i + ii + d + dd + f + ff + l + ll
+        |}
+        |""".stripMargin
+
+    val List(noCompact)   = compileMethods(noCompactVarsCompiler)(code)
+    val List(withCompact) = compileMethods(methodOptCompiler)(code)
+
+    // code is the same, except for local var indices
+    assertTrue(noCompact.instructions.size == withCompact.instructions.size)
+
+    val varOpSlots = convertMethod(withCompact).instructions collect {
+      case VarOp(_, v) => v
+    }
+    assertTrue(varOpSlots.toString, varOpSlots == List(1, 2, 4, 5, 7, 8, 10, 11,  // stores
+                                                       1, 7, 2, 8, 4, 10, 5, 11)) // loads
+
+    // the local variables descriptor table is cleaned up to remove stale entries after dce,
+    // also when the slots are not compacted
+    assertTrue(noCompact.localVariables.size == withCompact.localVariables.size)
+
+    assertTrue(noCompact.maxLocals == 25)
+    assertTrue(withCompact.maxLocals == 13)
+  }
+}
-- 
cgit v1.2.3


From 063e7741510bfaf4ccb61f7c0d94cae9353183aa Mon Sep 17 00:00:00 2001
From: Lukas Rytz <lukas.rytz@gmail.com>
Date: Fri, 7 Nov 2014 09:02:23 +0100
Subject: Address review comments

---
 .../scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala   |  8 +++++++-
 .../scala/tools/nsc/backend/jvm/opt/LocalOpt.scala        | 15 +++++++--------
 .../scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala |  2 +-
 3 files changed, 15 insertions(+), 10 deletions(-)

(limited to 'test')

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 fd14083cf7..6b4047c0a7 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
@@ -9,6 +9,7 @@ package opt
 
 import scala.annotation.{tailrec, switch}
 import scala.collection.mutable
+import scala.reflect.internal.util.Collections._
 import scala.tools.asm.Opcodes
 import scala.tools.asm.tree._
 import scala.collection.convert.decorateAsScala._
@@ -55,6 +56,11 @@ object BytecodeUtils {
     (op >= Opcodes.IFEQ && op <= Opcodes.IF_ACMPNE) || op == Opcodes.IFNULL || op == Opcodes.IFNONNULL
   }
 
+  def isReturn(instruction: AbstractInsnNode): Boolean = {
+    val op = instruction.getOpcode
+    op >= Opcodes.IRETURN && op <= Opcodes.RETURN
+  }
+
   def isVarInstruction(instruction: AbstractInsnNode): Boolean = {
     val op = instruction.getOpcode
     (op >= Opcodes.ILOAD  && op <= Opcodes.ALOAD) || (op >= Opcodes.ISTORE && op <= Opcodes.ASTORE)
@@ -157,7 +163,7 @@ object BytecodeUtils {
 
   def substituteLabel(reference: AnyRef, from: LabelNode, to: LabelNode): Unit = {
     def substList(list: java.util.List[LabelNode]) = {
-      list.asScala.zipWithIndex.foreach { case (l, i) =>
+      foreachWithIndex(list.asScala.toList) { case (l, i) =>
         if (l == from) list.set(i, 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 8fff478326..273112b93c 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -245,7 +245,7 @@ class LocalOpt(settings: ScalaSettings) {
   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 paramsSize = scala.tools.asm.Type.getArgumentTypes(method.desc).iterator.map(_.getSize max 1).sum
     val thisSize   = if ((method.access & Opcodes.ACC_STATIC) == 0) 1 else 0
     paramsSize + thisSize
   }
@@ -273,15 +273,15 @@ class LocalOpt(settings: ScalaSettings) {
       }
 
       // 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
+      val minLength = if (isWide) index + 2 else index + 1
+      for (i <- renumber.length until minLength) 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) = x, otherwise renumber(x) = -1. if the variable is wide (long or double), set
     // renumber(x+1) = x.
 
     val firstLocalIndex = parametersSize(method)
@@ -404,7 +404,7 @@ class LocalOpt(settings: ScalaSettings) {
   def simplifyJumps(method: MethodNode): Boolean = {
     var changed = false
 
-    val allHanlders = method.tryCatchBlocks.asScala.toSet
+    val allHandlers = method.tryCatchBlocks.asScala.toSet
 
     // A set of all exception handlers that guard the current instruction, required for simplifyGotoReturn
     var activeHandlers = Set.empty[TryCatchBlockNode]
@@ -420,7 +420,7 @@ class LocalOpt(settings: ScalaSettings) {
 
       instruction match {
         case l: LabelNode =>
-          activeHandlers ++= allHanlders.filter(_.start == l)
+          activeHandlers ++= allHandlers.filter(_.start == l)
           activeHandlers = activeHandlers.filter(_.end != l)
         case _ =>
       }
@@ -550,8 +550,7 @@ class LocalOpt(settings: ScalaSettings) {
     case Goto(jump) =>
       nextExecutableInstruction(jump.label) match {
         case Some(target) =>
-          val op = target.getOpcode
-          if ((op >= Opcodes.IRETURN && op <= Opcodes.RETURN) || op == Opcodes.ATHROW) {
+          if (isReturn(target) || target.getOpcode == Opcodes.ATHROW) {
             method.instructions.set(jump, target.clone(null))
             true
           } else false
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala
index 390e53fc4a..5b0f0f238a 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala
@@ -36,7 +36,7 @@ class MethodLevelOpts {
   }
 
   @Test
-  def inlineThrowInCachtNotTry(): Unit = {
+  def inlineThrowInCatchNotTry(): Unit = {
     // the try block does not contain the `ATHROW` instruction, but in the catch block, `ATHROW` is inlined
     val code = "def f(e: Exception) = throw { try e catch { case _: Throwable => e } }"
     val m = singleMethod(methodOptCompiler)(code)
-- 
cgit v1.2.3