SI-7006 Simplify jump-only block destination determination

With proper reachability analysis, the code for finding the final
destination of jump-only blocks was more complicated than needed. This
commit simplifies and speeds up that process using a standard
Tortoise and Hare algorithm on a Map from jump-only blocks to their
immediate destinations.

Test t7006 is increased a bit to make sure we don't get stuck on
infinite loops and to make sure we're deleting all but the essential
jump.

1 files changed, 92 insertions, 110 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
index 218c2c3ff5..91cb1857ac 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
@@ -11,6 +11,7 @@ import scala.reflect.internal.pickling.{ PickleFormat, PickleBuffer }
 import scala.tools.nsc.symtab._
 import scala.tools.asm
 import asm.Label
+import scala.annotation.tailrec
 
 /**
  *  @author  Iulian Dragos (version 1.0, FJBG-based implementation)
@@ -3120,54 +3121,6 @@ abstract class GenASM extends SubComponent with BytecodeWriters with GenJVMASM {
       }
     }
 
-    private def directSuccStar(b: BasicBlock): List[BasicBlock] = { directSuccStar(List(b)) }
-
-    /** Transitive closure of successors potentially reachable due to normal (non-exceptional) control flow.
-       Those BBs in the argument are also included in the result */
-    private def directSuccStar(starters: Traversable[BasicBlock]): List[BasicBlock] = {
-      val result = new mutable.ListBuffer[BasicBlock]
-      var toVisit: List[BasicBlock] = starters.toList.distinct
-      while(toVisit.nonEmpty) {
-        val h   = toVisit.head
-        toVisit = toVisit.tail
-        result += h
-        for(p <- h.directSuccessors; if !result.contains(p) && !toVisit.contains(p)) { toVisit = p :: toVisit }
-      }
-      result.toList
-    }
-
-    /** Returns:
-     *  for single-block self-loops, the pair (start, Nil)
-     *  for other cycles,            the pair (backedge-target, basic-blocks-in-the-cycle-except-backedge-target)
-     *  otherwise a pair consisting of:
-     *    (a) the endpoint of a (single or multi-hop) chain of JUMPs
-     *        (such endpoint does not start with a JUMP and therefore is not part of the chain); and
-     *    (b) the chain (ie blocks to be removed when collapsing the chain of jumps).
-     *  Precondition: the BasicBlock given as argument starts with an unconditional JUMP.
-     */
-    private def finalDestination(start: BasicBlock): (BasicBlock, List[BasicBlock]) = {
-      if (settings.debug.value) assert(isJumpOnly(start), "not the start of a (single or multi-hop) chain of JUMPs.")
-      var hops: List[BasicBlock] = Nil
-      var prev = start
-      var done = false
-      do {
-        done = getJumpOnlyTarget(prev) match {
-          case Some(dest) =>
-            if (dest == start) { return (start, hops) } // leave infinite-loops in place
-            hops ::= prev
-            if (hops.contains(dest)) {
-              // leave infinite-loops in place
-              return (dest, hops filterNot (dest eq _))
-            }
-            prev = dest
-            false
-          case None => true
-        }
-      } while(!done)
-
-      (prev, hops)
-    }
-
     /**
      * Collapse a chain of "jump-only" blocks such as:
      *
@@ -3199,76 +3152,105 @@ abstract class GenASM extends SubComponent with BytecodeWriters with GenJVMASM {
     private def collapseJumpOnlyBlocks(m: IMethod) {
       assert(m.hasCode, "code-less method")
 
-          /* "start" is relative in a cycle, but we call this helper with the "first" entry-point we found. */
-          def realTarget(jumpStart: BasicBlock): Map[BasicBlock, BasicBlock] = {
-            if (settings.debug.value) assert(isJumpOnly(jumpStart), "not part of a jump-chain")
-            val Pair(dest, redundants) = finalDestination(jumpStart)
-            (for(skipOver <- redundants) yield Pair(skipOver, dest)).toMap
-          }
-
-          def rephraseGotos(detour: Map[BasicBlock, BasicBlock]) {
-            def lookup(b: BasicBlock) = detour.getOrElse(b, b)
+      def rephraseGotos(detour: mutable.Map[BasicBlock, BasicBlock]) {
+        def lookup(b: BasicBlock) = detour.getOrElse(b, b)
             
-            m.code.startBlock = lookup(m.code.startBlock)
-              
-            for(eh <- m.exh)
-              eh.setStartBlock(lookup(eh.startBlock))
+        m.code.startBlock = lookup(m.code.startBlock)
+          
+        for(eh <- m.exh)
+          eh.setStartBlock(lookup(eh.startBlock))
             
-            for (b <- m.blocks) {
-              def replaceLastInstruction(i: Instruction) = {
-                if (b.lastInstruction != i) {
-	              val idxLast = b.size - 1
-	              debuglog(s"In block $b, replacing last instruction ${b.lastInstruction} with ${i}")
-	              b.replaceInstruction(idxLast, i)
-                }
-              }
-              
-              b.lastInstruction match {
-                case JUMP(whereto) =>
-                  replaceLastInstruction(JUMP(lookup(whereto)))
-                case CJUMP(succ, fail, cond, kind) =>
-                  replaceLastInstruction(CJUMP(lookup(succ), lookup(fail), cond, kind))
-                case CZJUMP(succ, fail, cond, kind)  =>             
-                  replaceLastInstruction(CZJUMP(lookup(succ), lookup(fail), cond, kind))
-                case SWITCH(tags, labels) =>
-                  val newLabels = (labels map lookup)
-                  replaceLastInstruction(SWITCH(tags, newLabels))
-                case _ => ()                
-              }
+        for (b <- m.blocks) {
+          def replaceLastInstruction(i: Instruction) = {
+            if (b.lastInstruction != i) {
+              val idxLast = b.size - 1
+	          debuglog(s"In block $b, replacing last instruction ${b.lastInstruction} with ${i}")
+	          b.replaceInstruction(idxLast, i)
             }
           }
-
-          /* remove from all containers that may contain a reference to */
-          def elide(redu: BasicBlock) {
-            debuglog(s"Will elide jump only block $redu because it can be jumped around.")
-            assert(m.startBlock != redu, "startBlock should have been re-wired by now")
+ 
+          b.lastInstruction match {
+            case JUMP(whereto) =>
+              replaceLastInstruction(JUMP(lookup(whereto)))
+            case CJUMP(succ, fail, cond, kind) =>
+              replaceLastInstruction(CJUMP(lookup(succ), lookup(fail), cond, kind))
+            case CZJUMP(succ, fail, cond, kind)  =>             
+              replaceLastInstruction(CZJUMP(lookup(succ), lookup(fail), cond, kind))
+            case SWITCH(tags, labels) =>
+              val newLabels = (labels map lookup)
+              replaceLastInstruction(SWITCH(tags, newLabels))
+            case _ => ()                
           }
+        }
+      }
 
-      var wasReduced = false
-      val entryPoints: List[BasicBlock] = m.startBlock :: (m.exh map (_.startBlock))
-
-      val elided     = mutable.Set.empty[BasicBlock] // debug
-      val newTargets = mutable.Set.empty[BasicBlock] // debug
-
-      for (ep <- entryPoints) {
-        var reachable = directSuccStar(ep) // this list may contain blocks belonging to jump-chains that we'll skip over
-        while(reachable.nonEmpty) {
-          val h = reachable.head
-          reachable = reachable.tail
-          if(isJumpOnly(h)) {
-            val detour = realTarget(h)
-            if(detour.nonEmpty) {
-              wasReduced = true
-              reachable = (reachable filterNot (detour.keySet.contains(_)))
-              rephraseGotos(detour)
-              detour.keySet foreach elide
-              elided     ++= detour.keySet
-              newTargets ++= detour.values
-            }
+      /**
+       * Computes a mapping from jump only block to its
+       * final destination which is either a non-jump-only
+       * block or, if it's in a jump-only block cycle, is
+       * itself
+       */
+      def computeDetour: mutable.Map[BasicBlock, BasicBlock] = {
+        // fetch the jump only blocks and their immediate destinations
+        val pairs = for {
+          block <- m.blocks.toIterator
+          target <- getJumpOnlyTarget(block)
+        } yield(block, target)
+
+        // mapping from a jump-only block to our current knowledge of its
+        // final destination. Initially it's just jump block to immediate jump
+        // target
+        val detour = mutable.Map[BasicBlock, BasicBlock](pairs.toSeq:_*)
+
+        // for each jump-only block find its final destination
+        // taking advantage of the destinations we found for previous
+        // blocks
+        for (key <- detour.keySet) {
+          // we use the Robert Floyd's classic Tortoise and Hare algorithm
+          @tailrec 
+          def findDestination(tortoise: BasicBlock, hare: BasicBlock): BasicBlock = {
+            if (tortoise == hare)
+              // cycle detected, map key to key
+              key
+            else if (detour contains hare) {
+              // advance hare once
+              val hare1 = detour(hare)
+              // make sure we can advance hare a second time
+              if (detour contains hare1)
+                // advance tortoise once and hare a second time
+                findDestination(detour(tortoise), detour(hare1))
+              else
+                // hare1 is not in the map so it's not a jump-only block, it's the destination
+                hare1
+            } else
+              // hare is not in the map so it's not a jump-only block, it's the destination
+              hare
           }
+          // update the mapping for key based on its final destination
+          detour(key) = findDestination(key, detour(key))
+        }
+        detour
+      }
+      
+      val detour = computeDetour
+      rephraseGotos(detour)
+
+      if (settings.debug.value) {
+        val (remappings, cycles) = detour partition {case (source, target) => source != target}
+        for ((source, target) <- remappings) {
+		   debuglog(s"Will elide jump only block $source because it can be jumped around to get to $target.")
+		   if (m.startBlock == source) debugwarn("startBlock should have been re-wired by now")        
+        }
+        val sources = remappings.keySet
+        val targets = remappings.values.toSet
+        val intersection = sources intersect targets
+        
+        if (intersection.nonEmpty) debugwarn(s"contradiction: we seem to have some source and target overlap in blocks ${intersection.mkString}. Map was ${detour.mkString}")
+        
+        for ((source, _) <- cycles) {
+          debuglog(s"Block $source is in a do-nothing infinite loop. Did the user write 'while(true){}'?")
         }
       }
-      assert(newTargets.intersect(elided).isEmpty, "contradiction: we just elided the final destionation of a jump-chain")
     }
     
     /**
@@ -3284,7 +3266,7 @@ abstract class GenASM extends SubComponent with BytecodeWriters with GenJVMASM {
       // yet to be  marked reachable, initially only the start block
       val worklist = mutable.Set(m.startBlock)
       
-      while (!worklist.isEmpty) {
+      while (worklist.nonEmpty) {
         val block = worklist.head
         worklist remove block
         // we know that one is reachable