SI-7006 Improve jump-elision code in GenASM

While working on SI-7006 I found a O(N*M) loop in jump-elision that
should be O(N). This commit clean that up. It also improves the
diagnostics in Members#removeBlock.

2 files changed, 36 insertions, 40 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
index 5c90fbf366..e471f4256b 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Members.scala
@@ -62,17 +62,18 @@ trait Members {
 
     def removeBlock(b: BasicBlock) {
       if (settings.debug.value) {
-        assert(blocks forall (p => !(p.successors contains b)),
-          "Removing block that is still referenced in method code " + b + "preds: " + b.predecessors
-        )
-        assert(b != startBlock || b.successors.length == 1,
-          "Removing start block with more than one successor."
-        )
+        // only do this sanity check when debug is turned on because it's moderately expensive
+        val referers = blocks filter (_.successors contains b)
+        assert(referers.isEmpty, s"Trying to removing block $b (with preds ${b.predecessors.mkString}) but it is still refered to from block(s) ${referers.mkString}")
       }
 
-      if (b == startBlock)
+      if (b == startBlock) {
+        assert(b.successors.length == 1,
+          s"Removing start block ${b} with ${b.successors.length} successors (${b.successors.mkString})."
+        )
         startBlock = b.successors.head
-
+      }
+      
       blocks -= b
       assert(!blocks.contains(b))
       method.exh filter (_ covers b) foreach (_.covered -= b)
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
index 75a8dfff90..6215503c01 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
@@ -3228,45 +3228,40 @@ abstract class GenASM extends SubComponent with BytecodeWriters with GenJVMASM {
           }
 
           def rephraseGotos(detour: Map[BasicBlock, BasicBlock]) {
-            for(Pair(oldTarget, newTarget) <- detour.iterator) {
-              if(m.startBlock == oldTarget) {
-                m.code.startBlock = newTarget
-              }
-              for(eh <- m.exh; if eh.startBlock == oldTarget) {
-                eh.setStartBlock(newTarget)
-              }
-              for(b <- m.blocks; if !detour.isDefinedAt(b)) {
-                val idxLast = (b.size - 1)
-                b.lastInstruction match {
-                  case JUMP(whereto) =>
-                    if (whereto == oldTarget) {
-                      b.replaceInstruction(idxLast, JUMP(newTarget))
-                    }
-                  case CJUMP(succ, fail, cond, kind) =>
-                    if ((succ == oldTarget) || (fail == oldTarget)) {
-                      b.replaceInstruction(idxLast, CJUMP(detour.getOrElse(succ, succ),
-                                                          detour.getOrElse(fail, fail),
-                                                          cond, kind))
-                    }
-                  case CZJUMP(succ, fail, cond, kind) =>
-                    if ((succ == oldTarget) || (fail == oldTarget)) {
-                      b.replaceInstruction(idxLast, CZJUMP(detour.getOrElse(succ, succ),
-                                                           detour.getOrElse(fail, fail),
-                                                           cond, kind))
-                    }
-                  case SWITCH(tags, labels) =>
-                    if(labels exists (detour.isDefinedAt(_))) {
-                      val newLabels = (labels map { lab => detour.getOrElse(lab, lab) })
-                      b.replaceInstruction(idxLast, SWITCH(tags, newLabels))
-                    }
-                  case _ => ()
+            def lookup(b: BasicBlock) = detour.getOrElse(b, b)
+            
+            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 _ => ()                
+              }
             }
           }
 
           /* remove from all containers that may contain a reference to */
           def elide(redu: BasicBlock) {
+            debuglog(s"Eliding jump only block $redu because it can be jumped around.")
             assert(m.startBlock != redu, "startBlock should have been re-wired by now")
             m.code.removeBlock(redu)
           }