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.

3 files changed, 507 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
new file mode 100644
index 0000000000..5718ad1c66
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
@@ -0,0 +1,123 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2014 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+
+package scala.tools.nsc
+package backend.jvm
+package opt
+
+import scala.annotation.{tailrec, switch}
+import scala.collection.mutable
+import scala.tools.asm.Opcodes
+import scala.tools.asm.tree._
+import scala.collection.convert.decorateAsScala._
+
+object BytecodeUtils {
+
+  object Goto {
+    def unapply(instruction: AbstractInsnNode): Option[JumpInsnNode] = {
+      if (instruction.getOpcode == Opcodes.GOTO) Some(instruction.asInstanceOf[JumpInsnNode])
+      else None
+    }
+  }
+
+  object JumpNonJsr {
+    def unapply(instruction: AbstractInsnNode): Option[JumpInsnNode] = {
+      if (isJumpNonJsr(instruction)) Some(instruction.asInstanceOf[JumpInsnNode])
+      else None
+    }
+  }
+
+  object ConditionalJump {
+    def unapply(instruction: AbstractInsnNode): Option[JumpInsnNode] = {
+      if (isConditionalJump(instruction)) Some(instruction.asInstanceOf[JumpInsnNode])
+      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.
+    op == Opcodes.GOTO || isConditionalJump(instruction)
+  }
+
+  def isConditionalJump(instruction: AbstractInsnNode): Boolean = {
+    val op = instruction.getOpcode
+    (op >= Opcodes.IFEQ && op <= Opcodes.IF_ACMPNE) || op == Opcodes.IFNULL || op == Opcodes.IFNONNULL
+  }
+
+  def isExecutable(instruction: AbstractInsnNode): Boolean = instruction.getOpcode >= 0
+
+  def nextExecutableInstruction(instruction: AbstractInsnNode, alsoKeep: AbstractInsnNode => Boolean = Set()): Option[AbstractInsnNode] = {
+    var result = instruction
+    do { result = result.getNext }
+    while (result != null && !isExecutable(result) && !alsoKeep(result))
+    Option(result)
+  }
+
+  def sameTargetExecutableInstruction(a: JumpInsnNode, b: JumpInsnNode): Boolean = {
+    // Compare next executable instead of the the labels. Identifies a, b as the same target:
+    //   LabelNode(a)
+    //   LabelNode(b)
+    //   Instr
+    nextExecutableInstruction(a.label) == nextExecutableInstruction(b.label)
+  }
+
+  def removeJumpAndAdjustStack(method: MethodNode, jump: JumpInsnNode) {
+    val instructions = method.instructions
+    val op = jump.getOpcode
+    if ((op >= Opcodes.IFEQ && op <= Opcodes.IFGE) || op == Opcodes.IFNULL || op == Opcodes.IFNONNULL) {
+      instructions.insert(jump, getPop(1))
+    } else if ((op >= Opcodes.IF_ICMPEQ && op <= Opcodes.IF_ICMPLE) || op == Opcodes.IF_ACMPEQ || op == Opcodes.IF_ACMPNE) {
+      instructions.insert(jump, getPop(1))
+      instructions.insert(jump, getPop(1))
+    } else {
+      // we can't remove JSR: its execution does not only jump, it also adds a return address to the stack
+      assert(jump.getOpcode == Opcodes.GOTO)
+    }
+    instructions.remove(jump)
+  }
+
+  def finalJumpTarget(source: JumpInsnNode): LabelNode = {
+    @tailrec def followGoto(label: LabelNode, seenLabels: Set[LabelNode]): LabelNode = nextExecutableInstruction(label) match {
+      case Some(Goto(dest)) =>
+        if (seenLabels(dest.label)) dest.label
+        else followGoto(dest.label, seenLabels + dest.label)
+
+      case _ => label
+    }
+    followGoto(source.label, Set(source.label))
+  }
+
+  def negateJumpOpcode(jumpOpcode: Int): Int = (jumpOpcode: @switch) match {
+    case Opcodes.IFEQ      => Opcodes.IFNE
+    case Opcodes.IFNE      => Opcodes.IFEQ
+
+    case Opcodes.IFLT      => Opcodes.IFGE
+    case Opcodes.IFGE      => Opcodes.IFLT
+
+    case Opcodes.IFGT      => Opcodes.IFLE
+    case Opcodes.IFLE      => Opcodes.IFGT
+
+    case Opcodes.IF_ICMPEQ => Opcodes.IF_ICMPNE
+    case Opcodes.IF_ICMPNE => Opcodes.IF_ICMPEQ
+
+    case Opcodes.IF_ICMPLT => Opcodes.IF_ICMPGE
+    case Opcodes.IF_ICMPGE => Opcodes.IF_ICMPLT
+
+    case Opcodes.IF_ICMPGT => Opcodes.IF_ICMPLE
+    case Opcodes.IF_ICMPLE => Opcodes.IF_ICMPGT
+
+    case Opcodes.IF_ACMPEQ => Opcodes.IF_ACMPNE
+    case Opcodes.IF_ACMPNE => Opcodes.IF_ACMPEQ
+
+    case Opcodes.IFNULL    => Opcodes.IFNONNULL
+    case Opcodes.IFNONNULL => Opcodes.IFNULL
+  }
+
+  def getPop(size: Int): InsnNode = {
+    val op = if (size == 1) Opcodes.POP else Opcodes.POP2
+    new InsnNode(op)
+  }
+}
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 3acd2d6154..682811bede 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -12,6 +12,7 @@ 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._
 
 /**
  * Intra-Method optimizations.
@@ -187,4 +188,166 @@ object LocalOpt {
     method.maxLocals = mw.getMaxLocals
     method.maxStack = mw.getMaxStack
   }
+  /**
+   * Apply various simplifications to branching instructions.
+   */
+  def simplifyJumps(method: MethodNode): Boolean = {
+    var changed = false
+
+    val allHanlders = method.tryCatchBlocks.asScala.toSet
+
+    // A set of all exception handlers that guard the current instruction, required for simplifyGotoReturn
+    var activeHandlers = Set.empty[TryCatchBlockNode]
+
+    // Instructions that need to be removed. simplifyBranchOverGoto returns an instruction to be
+    // removed. It cannot remove it itself because the instruction may be the successor of the current
+    // instruction of the iterator, which is not supported in ASM.
+    var instructionsToRemove = Set.empty[AbstractInsnNode]
+
+    val iterator = method.instructions.iterator()
+    while (iterator.hasNext) {
+      val instruction = iterator.next()
+
+      instruction match {
+        case l: LabelNode =>
+          activeHandlers ++= allHanlders.filter(_.start == l)
+          activeHandlers = activeHandlers.filter(_.end != l)
+        case _ =>
+      }
+
+      if (instructionsToRemove(instruction)) {
+        iterator.remove()
+        instructionsToRemove -= instruction
+      } else if (isJumpNonJsr(instruction)) { // fast path - all of the below only treat jumps
+        var jumpRemoved = simplifyThenElseSameTarget(method, instruction)
+
+        if (!jumpRemoved) {
+          changed = collapseJumpChains(instruction) || changed
+          jumpRemoved = removeJumpToSuccessor(method, instruction)
+
+          if (!jumpRemoved) {
+            val staleGoto = simplifyBranchOverGoto(method, instruction)
+            instructionsToRemove ++= staleGoto
+            changed ||= staleGoto.nonEmpty
+            changed = simplifyGotoReturn(method, instruction, inTryBlock = activeHandlers.nonEmpty) || changed
+          }
+        }
+        changed ||= jumpRemoved
+      }
+    }
+    assert(instructionsToRemove.isEmpty, "some optimization required removing a previously traversed instruction. add `instructionsToRemove.foreach(method.instructions.remove)`")
+    changed
+  }
+
+  /**
+   * Removes a conditional jump if it is followed by a GOTO to the same destination.
+   *
+   *      CondJump l;  [nops];  GOTO l;  [...]
+   *      POP*;        [nops];  GOTO l;  [...]
+   *
+   * Introduces 1 or 2 POP instructions, depending on the number of values consumed by the CondJump.
+   */
+  private def simplifyThenElseSameTarget(method: MethodNode, instruction: AbstractInsnNode): Boolean = instruction match {
+    case ConditionalJump(jump) =>
+      nextExecutableInstruction(instruction) match {
+        case Some(Goto(elseJump)) if sameTargetExecutableInstruction(jump, elseJump) =>
+          removeJumpAndAdjustStack(method, jump)
+          true
+
+        case _ => false
+      }
+    case _ => false
+  }
+
+  /**
+   * Replace jumps to a sequence of GOTO instructions by a jump to the final destination.
+   *
+   *      Jump l;  [any ops];  l: GOTO m;  [any ops];  m: GOTO n;  [any ops];   n: NotGOTO; [...]
+   *   => Jump n;  [rest unchaned]
+   *
+   * If there's a loop of GOTOs, the initial jump is replaced by one of the labels in the loop.
+   */
+  private def collapseJumpChains(instruction: AbstractInsnNode): Boolean = instruction match {
+    case JumpNonJsr(jump) =>
+      val target = finalJumpTarget(jump)
+      if (jump.label == target) false else {
+        jump.label = target
+        true
+      }
+
+    case _ => false
+  }
+
+  /**
+   * Eliminates unnecessary jump instructions
+   *
+   *      Jump l;  [nops];  l: [...]
+   *   => POP*;    [nops];  l: [...]
+   *
+   * Introduces 0, 1 or 2 POP instructions, depending on the number of values consumed by the Jump.
+   */
+  private def removeJumpToSuccessor(method: MethodNode, instruction: AbstractInsnNode) = instruction match {
+    case JumpNonJsr(jump) if nextExecutableInstruction(jump, alsoKeep = Set(jump.label)) == Some(jump.label) =>
+      removeJumpAndAdjustStack(method, jump)
+      true
+    case _ => false
+  }
+
+  /**
+   * If the "else" part of a conditional branch is a simple GOTO, negates the conditional branch
+   * and eliminates the GOTO.
+   *
+   *      CondJump l;         [nops, no labels];  GOTO m;  [nops];  l: [...]
+   *   => NegatedCondJump m;  [nops, no labels];           [nops];  l: [...]
+   *
+   * Note that no label definitions are allowed in the first [nops] section. Otherwsie, there could
+   * be some other jump to the GOTO, and eliminating it would change behavior.
+   *
+   * For technical reasons, we cannot remove the GOTO here (*).Instead this method returns an Option
+   * containing the GOTO that needs to be eliminated.
+   *
+   * (*) The ASM instruction iterator (used in the caller [[simplifyJumps]]) has an undefined
+   *     behavior if the successor of the current instruction is removed, which may be the case here
+   */
+  private def simplifyBranchOverGoto(method: MethodNode, instruction: AbstractInsnNode): Option[JumpInsnNode] = instruction match {
+    case ConditionalJump(jump) =>
+      // don't skip over labels, see doc comment
+      nextExecutableInstruction(jump, alsoKeep = _.isInstanceOf[LabelNode]) match {
+        case Some(Goto(goto)) =>
+          if (nextExecutableInstruction(goto, alsoKeep = Set(jump.label)) == Some(jump.label)) {
+            val newJump = new JumpInsnNode(negateJumpOpcode(jump.getOpcode), goto.label)
+            method.instructions.set(jump, newJump)
+            Some(goto)
+          } else None
+
+        case _ => None
+      }
+    case _ => None
+  }
+
+  /**
+   * Inlines xRETURN and ATHROW
+   *
+   *      GOTO l;            [any ops];  l: xRETURN/ATHROW
+   *   => xRETURN/ATHROW;    [any ops];  l: xRETURN/ATHROW
+   *
+   * inlining is only done if the GOTO instruction is not part of a try block, otherwise the
+   * rewrite might change the behavior. For xRETURN, the reason is that return insructions may throw
+   * an IllegalMonitorStateException, as described here:
+   *   http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.return
+   */
+  private def simplifyGotoReturn(method: MethodNode, instruction: AbstractInsnNode, inTryBlock: Boolean): Boolean = !inTryBlock && (instruction match {
+    case Goto(jump) =>
+      nextExecutableInstruction(jump.label) match {
+        case Some(target) =>
+          val op = target.getOpcode
+          if ((op >= Opcodes.IRETURN && op <= Opcodes.RETURN) || op == Opcodes.ATHROW) {
+            method.instructions.set(jump, target.clone(null))
+            true
+          } else false
+
+        case _ => false
+      }
+    case _ => false
+  })
 }
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))))
+  }
+}