From 4f2d784a09e5df244ebbee33d23cf931fcacb740 Mon Sep 17 00:00:00 2001 From: James Iry Date: Sun, 24 Feb 2013 06:28:45 -0800 Subject: 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. --- .../scala/tools/nsc/backend/jvm/GenASM.scala | 202 ++++++++++----------- 1 file changed, 92 insertions(+), 110 deletions(-) (limited to 'src') 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 -- cgit v1.2.3