From b50a0d811f0fb99ccbc295741e66bab348b3f99e Mon Sep 17 00:00:00 2001 From: James Iry Date: Wed, 27 Feb 2013 12:36:41 -0800 Subject: SI-7006 Prevent unreachable blocks in GenICode This commit makes GenICode prevent the generation of most unreachable blocks. The new unreachable block prevention code can be disabled with a compiler flag. Because full unreachable analysis is no longer necessary for normal code it makes the unreachable block analysis run only under -optimise. A test is included to make sure unreachable code doesn't cause issues in code gen. A concrete example will help. def foo(): X = { try return something() catch { case e: Throwable => println(e) throw e } unreachableCode() ] Here unreachableCode() is unreachable but GenICode would create ICode for it and then ASM would turn it into a pile of NOPS. A previous commit added a reachability analysis step to eliminate that unreachable code but that added a bit of time to the compilation process even when optimization was turned off. This commit avoids generating most unreachable ICode in the first place so that full reachability analysis is only needed after doing other optimization work. The new code works by extending a mechanism that was already in place. When GenICode encountered a THROW or RETURN it would put the current block into "ignore" mode so that no further instructions would be written into the block. However, that ignore mode flag was itself ignored when it came to figuring out if follow on blocks should be written. So this commit goes through places like try/catch and if/else and uses the ignore mode of the current block to decide whether to create follow on blocks, or if it already has, to kill by putting them into ignore mode and closing them where they'll be removed from the method's list of active blocks. It's not quite as good as full reachability analysis. In particular because a label def can be emitted before anything that jumps to it, this simple logic is forced to leave label defs alone and that means some of them may be unreachable without being removed. However, in practice it gets close the the benefit of reachability analysis at very nearly no cost. --- .../tools/nsc/backend/icode/BasicBlocks.scala | 32 +++++- .../scala/tools/nsc/backend/icode/GenICode.scala | 117 ++++++++++++++------- .../scala/tools/nsc/backend/jvm/GenASM.scala | 3 +- .../scala/tools/nsc/settings/ScalaSettings.scala | 1 + 4 files changed, 114 insertions(+), 39 deletions(-) (limited to 'src') diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala index 917fe8b292..d772dcb6c4 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala @@ -17,7 +17,7 @@ trait BasicBlocks { self: ICodes => import opcodes._ - import global.{ settings, log, nme } + import global.{ settings, debuglog, log, nme } import nme.isExceptionResultName /** Override Array creation for efficiency (to not go through reflection). */ @@ -383,7 +383,6 @@ trait BasicBlocks { /** Close the block */ def close() { assert(!closed || ignore, this) - assert(instructionList.nonEmpty, "Empty block: " + this) if (ignore && closed) { // redundant `ignore &&` for clarity -- we should never be in state `!ignore && closed` // not doing anything to this block is important... // because the else branch reverses innocent blocks, which is wrong when they're in ignore mode (and closed) @@ -393,9 +392,38 @@ trait BasicBlocks { setFlag(DIRTYSUCCS) instructionList = instructionList.reverse instrs = instructionList.toArray + if (instructionList.isEmpty) { + debuglog(s"Removing empty block $this") + code removeBlock this + } } } + /** + * if cond is true, closes this block, entersIgnoreMode, and removes the block from + * its list of blocks. Used to allow a block to be started and then cancelled when it + * is discovered to be unreachable. + */ + def killIf(cond: Boolean) { + if (!settings.YdisableUnreachablePrevention.value && cond) { + debuglog(s"Killing block $this") + assert(instructionList.isEmpty, s"Killing a non empty block $this") + // only checked under debug because fetching predecessor list is moderately expensive + if (settings.debug.value) + assert(predecessors.isEmpty, s"Killing block $this which is referred to from ${predecessors.mkString}") + + close() + enterIgnoreMode() + } + } + + /** + * Same as killIf but with the logic of the condition reversed + */ + def killUnless(cond: Boolean) { + this killIf !cond + } + def open() { assert(closed, this) closed = false diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala index ed458a4bbe..468e2cfd35 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala @@ -376,12 +376,14 @@ abstract class GenICode extends SubComponent { "I produce UNIT in a context where " + expectedType + " is expected!") // alternatives may be already closed by a tail-recursive jump + val contReachable = !(thenCtx.bb.ignore && elseCtx.bb.ignore) thenCtx.bb.closeWith(JUMP(contCtx.bb)) elseCtx.bb.closeWith( if (elsep == EmptyTree) JUMP(contCtx.bb) else JUMP(contCtx.bb) setPos tree.pos ) + contCtx.bb killUnless contReachable (contCtx, resKind) } private def genLoadTry(tree: Try, ctx: Context, setGeneratedType: TypeKind => Unit): Context = { @@ -477,7 +479,11 @@ abstract class GenICode extends SubComponent { val resCtx: Context = tree match { case LabelDef(name, params, rhs) => def genLoadLabelDef = { - val ctx1 = ctx.newBlock() + val ctx1 = ctx.newBlock() // note: we cannot kill ctx1 if ctx is in ignore mode because + // label defs can be the target of jumps from other locations. + // that means label defs can lead to unreachable code without + // proper reachability analysis + if (nme.isLoopHeaderLabel(name)) ctx1.bb.loopHeader = true @@ -560,6 +566,7 @@ abstract class GenICode extends SubComponent { // the list, otherwise infinite recursion happens for // finalizers that contain 'return' val fctx = finalizerCtx.newBlock() + fctx.bb killIf ctx1.bb.ignore ctx1.bb.closeWith(JUMP(fctx.bb)) ctx1 = genLoad(f1, fctx, UNIT) } @@ -949,6 +956,8 @@ abstract class GenICode extends SubComponent { debuglog("Generating SWITCH statement.") val ctx1 = genLoad(selector, ctx, INT) // TODO: Java 7 allows strings in switches (so, don't assume INT and don't convert the literals using intValue) val afterCtx = ctx1.newBlock() + afterCtx.bb killIf ctx1.bb.ignore + var afterCtxReachable = false var caseCtx: Context = null generatedType = toTypeKind(tree.tpe) @@ -959,6 +968,7 @@ abstract class GenICode extends SubComponent { for (caze @ CaseDef(pat, guard, body) <- cases) { assert(guard == EmptyTree, guard) val tmpCtx = ctx1.newBlock() + tmpCtx.bb killIf ctx1.bb.ignore pat match { case Literal(value) => tags = value.intValue :: tags @@ -980,12 +990,15 @@ abstract class GenICode extends SubComponent { } caseCtx = genLoad(body, tmpCtx, generatedType) + afterCtxReachable |= !caseCtx.bb.ignore // close the block unless it's already been closed by the body, which closes the block if it ends in a jump (which is emitted to have alternatives share their body) caseCtx.bb.closeWith(JUMP(afterCtx.bb) setPos caze.pos) } + afterCtxReachable |= (default == afterCtx) ctx1.bb.emitOnly( SWITCH(tags.reverse map (x => List(x)), (default :: targets).reverse) setPos tree.pos ) + afterCtx.bb killUnless afterCtxReachable afterCtx } genLoadMatch @@ -1342,9 +1355,9 @@ abstract class GenICode extends SubComponent { private def genCond(tree: Tree, ctx: Context, thenCtx: Context, - elseCtx: Context): Unit = - { - def genComparisonOp(l: Tree, r: Tree, code: Int) { + elseCtx: Context): Boolean = + { + def genComparisonOp(l: Tree, r: Tree, code: Int): Boolean = { val op: TestOp = code match { case scalaPrimitives.LT => LT case scalaPrimitives.LE => LE @@ -1360,27 +1373,33 @@ abstract class GenICode extends SubComponent { lazy val nonNullSide = ifOneIsNull(l, r) if (isReferenceEqualityOp(code) && nonNullSide != null) { val ctx1 = genLoad(nonNullSide, ctx, ObjectReference) + val branchesReachable = !ctx1.bb.ignore ctx1.bb.emitOnly( CZJUMP(thenCtx.bb, elseCtx.bb, op, ObjectReference) ) + branchesReachable } else { val kind = getMaxType(l.tpe :: r.tpe :: Nil) var ctx1 = genLoad(l, ctx, kind) ctx1 = genLoad(r, ctx1, kind) + val branchesReachable = !ctx1.bb.ignore ctx1.bb.emitOnly( CJUMP(thenCtx.bb, elseCtx.bb, op, kind) setPos r.pos ) + branchesReachable } } debuglog("Entering genCond with tree: " + tree) // the default emission - def default() = { + def default(): Boolean = { val ctx1 = genLoad(tree, ctx, BOOL) + val branchesReachable = !ctx1.bb.ignore ctx1.bb.closeWith(CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL) setPos tree.pos) + branchesReachable } tree match { @@ -1392,11 +1411,12 @@ abstract class GenICode extends SubComponent { lazy val Select(lhs, _) = fun lazy val rhs = args.head - def genZandOrZor(and: Boolean) = { + def genZandOrZor(and: Boolean): Boolean = { val ctxInterm = ctx.newBlock() - if (and) genCond(lhs, ctx, ctxInterm, elseCtx) + val branchesReachable = if (and) genCond(lhs, ctx, ctxInterm, elseCtx) else genCond(lhs, ctx, thenCtx, ctxInterm) + ctxInterm.bb killUnless branchesReachable genCond(rhs, ctxInterm, thenCtx, elseCtx) } @@ -1436,7 +1456,7 @@ abstract class GenICode extends SubComponent { * @param thenCtx target context if the comparison yields true * @param elseCtx target context if the comparison yields false */ - def genEqEqPrimitive(l: Tree, r: Tree, ctx: Context)(thenCtx: Context, elseCtx: Context): Unit = { + def genEqEqPrimitive(l: Tree, r: Tree, ctx: Context)(thenCtx: Context, elseCtx: Context): Boolean = { def getTempLocal = ctx.method.lookupLocal(nme.EQEQ_LOCAL_VAR) getOrElse { ctx.makeLocal(l.pos, AnyRefClass.tpe, nme.EQEQ_LOCAL_VAR.toString) } @@ -1476,26 +1496,40 @@ abstract class GenICode extends SubComponent { val ctx1 = genLoad(l, ctx, ObjectReference) val ctx2 = genLoad(r, ctx1, ObjectReference) + val branchesReachable = !ctx2.bb.ignore ctx2.bb.emitOnly( CALL_METHOD(equalsMethod, if (settings.optimise.value) Dynamic else Static(onInstance = false)), CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL) ) + branchesReachable } else { - if (isNull(l)) + if (isNull(l)) { // null == expr -> expr eq null - genLoad(r, ctx, ObjectReference).bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference) - else if (isNull(r)) { + val ctx1 = genLoad(r, ctx, ObjectReference) + val branchesReachable = !ctx1.bb.ignore + ctx1.bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference) + branchesReachable + } else if (isNull(r)) { // expr == null -> expr eq null - genLoad(l, ctx, ObjectReference).bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference) + val ctx1 = genLoad(l, ctx, ObjectReference) + val branchesReachable = !ctx1.bb.ignore + ctx1.bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference) + branchesReachable } else { val eqEqTempLocal = getTempLocal var ctx1 = genLoad(l, ctx, ObjectReference) - lazy val nonNullCtx = ctx1.newBlock() + val branchesReachable = !ctx1.bb.ignore + lazy val nonNullCtx = { + val block = ctx1.newBlock() + block.bb killUnless branchesReachable + block + } // l == r -> if (l eq null) r eq null else l.equals(r) ctx1 = genLoad(r, ctx1, ObjectReference) val nullCtx = ctx1.newBlock() + nullCtx.bb killUnless branchesReachable ctx1.bb.emitOnly( STORE_LOCAL(eqEqTempLocal) setPos l.pos, @@ -1512,6 +1546,7 @@ abstract class GenICode extends SubComponent { CALL_METHOD(Object_equals, Dynamic), CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL) ) + branchesReachable } } } @@ -1957,6 +1992,7 @@ abstract class GenICode extends SubComponent { val outerCtx = this.dup // context for generating exception handlers, covered by the catch-all finalizer val finalizerCtx = this.dup // context for generating finalizer handler val normalExitCtx = outerCtx.newBlock() // context where flow will go on a "normal" (non-return, non-throw) exit from a try or catch handler + var normalExitReachable = false var tmp: Local = null val kind = toTypeKind(tree.tpe) val guardResult = kind != UNIT && mayCleanStack(finalizer) @@ -1971,6 +2007,7 @@ abstract class GenICode extends SubComponent { def emitFinalizer(ctx: Context): Context = if (!finalizer.isEmpty) { val ctx1 = finalizerCtx.dup.newBlock() + ctx1.bb killIf ctx.bb.ignore ctx.bb.closeWith(JUMP(ctx1.bb)) if (guardResult) { @@ -1986,32 +2023,38 @@ abstract class GenICode extends SubComponent { // Generate the catch-all exception handler that deals with uncaught exceptions coming // from the try or exception handlers. It catches the exception, runs the finally code, then rethrows // the exception - if (finalizer != EmptyTree) { - val exh = outerCtx.newExceptionHandler(NoSymbol, finalizer.pos) // finalizer covers exception handlers - this.addActiveHandler(exh) // .. and body aswell - val exhStartCtx = finalizerCtx.enterExceptionHandler(exh) - val exception = exhStartCtx.makeLocal(finalizer.pos, ThrowableClass.tpe, "exc") - loadException(exhStartCtx, exh, finalizer.pos) - exhStartCtx.bb.emit(STORE_LOCAL(exception)) - val exhEndCtx = genLoad(finalizer, exhStartCtx, UNIT) - exhEndCtx.bb.emit(LOAD_LOCAL(exception)) - exhEndCtx.bb.closeWith(THROW(ThrowableClass)) - exhEndCtx.bb.enterIgnoreMode() - finalizerCtx.endHandler() - } - - // Generate each exception handler - for ((sym, kind, handler) <- handlers) { - val exh = this.newExceptionHandler(sym, tree.pos) - val exhStartCtx = outerCtx.enterExceptionHandler(exh) - exhStartCtx.addFinalizer(finalizer, finalizerCtx) - loadException(exhStartCtx, exh, tree.pos) - val exhEndCtx = handler(exhStartCtx) - exhEndCtx.bb.closeWith(JUMP(normalExitCtx.bb)) - outerCtx.endHandler() + if (settings.YdisableUnreachablePrevention.value || !outerCtx.bb.ignore) { + if (finalizer != EmptyTree) { + val exh = outerCtx.newExceptionHandler(NoSymbol, finalizer.pos) // finalizer covers exception handlers + this.addActiveHandler(exh) // .. and body aswell + val exhStartCtx = finalizerCtx.enterExceptionHandler(exh) + exhStartCtx.bb killIf outerCtx.bb.ignore + val exception = exhStartCtx.makeLocal(finalizer.pos, ThrowableClass.tpe, "exc") + loadException(exhStartCtx, exh, finalizer.pos) + exhStartCtx.bb.emit(STORE_LOCAL(exception)) + val exhEndCtx = genLoad(finalizer, exhStartCtx, UNIT) + exhEndCtx.bb.emit(LOAD_LOCAL(exception)) + exhEndCtx.bb.closeWith(THROW(ThrowableClass)) + exhEndCtx.bb.enterIgnoreMode() + finalizerCtx.endHandler() + } + + // Generate each exception handler + for ((sym, kind, handler) <- handlers) { + val exh = this.newExceptionHandler(sym, tree.pos) + val exhStartCtx = outerCtx.enterExceptionHandler(exh) + exhStartCtx.bb killIf outerCtx.bb.ignore + exhStartCtx.addFinalizer(finalizer, finalizerCtx) + loadException(exhStartCtx, exh, tree.pos) + val exhEndCtx = handler(exhStartCtx) + normalExitReachable |= !exhEndCtx.bb.ignore + exhEndCtx.bb.closeWith(JUMP(normalExitCtx.bb)) + outerCtx.endHandler() + } } val bodyCtx = this.newBlock() + bodyCtx.bb killIf outerCtx.bb.ignore if (finalizer != EmptyTree) bodyCtx.addFinalizer(finalizer, finalizerCtx) @@ -2019,6 +2062,8 @@ abstract class GenICode extends SubComponent { outerCtx.bb.closeWith(JUMP(bodyCtx.bb)) + normalExitReachable |= !bodyEndCtx.bb.ignore + normalExitCtx.bb killUnless normalExitReachable bodyEndCtx.bb.closeWith(JUMP(normalExitCtx.bb)) emitFinalizer(normalExitCtx) diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala index 703922b20a..1fb7b11b20 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala @@ -3298,7 +3298,8 @@ abstract class GenASM extends SubComponent with BytecodeWriters with GenJVMASM { def normalize(m: IMethod) { if(!m.hasCode) { return } collapseJumpOnlyBlocks(m) - elimUnreachableBlocks(m) + if (settings.optimise.value) + elimUnreachableBlocks(m) icodes checkValid m } diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index 702071f906..2aee9bd4bc 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -173,6 +173,7 @@ trait ScalaSettings extends AbsScalaSettings val Yinvalidate = StringSetting ("-Yinvalidate", "classpath-entry", "Invalidate classpath entry before run", "") val noSelfCheck = BooleanSetting ("-Yno-self-type-checks", "Suppress check for self-type conformance among inherited members.") val YvirtClasses = false // too embryonic to even expose as a -Y //BooleanSetting ("-Yvirtual-classes", "Support virtual classes") + val YdisableUnreachablePrevention = BooleanSetting("-Ydisable-unreachable-prevention", "Disable the prevention of unreachable blocks in code generation.") val exposeEmptyPackage = BooleanSetting("-Yexpose-empty-package", "Internal only: expose the empty package.").internalOnly() -- cgit v1.2.3