diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/backend/opt/InlineExceptionHandlers.scala')
-rw-r--r-- | src/compiler/scala/tools/nsc/backend/opt/InlineExceptionHandlers.scala | 392 |
1 files changed, 0 insertions, 392 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/opt/InlineExceptionHandlers.scala b/src/compiler/scala/tools/nsc/backend/opt/InlineExceptionHandlers.scala deleted file mode 100644 index 9f6883f03f..0000000000 --- a/src/compiler/scala/tools/nsc/backend/opt/InlineExceptionHandlers.scala +++ /dev/null @@ -1,392 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - */ - -package scala.tools.nsc -package backend.opt - -import java.util.concurrent.TimeUnit - -/** - * This optimization phase inlines the exception handlers so that further phases can optimize the code better - * - * {{{ - * try { - * ... - * if (condition) - * throw IllegalArgumentException("sth") - * } catch { - * case e: IllegalArgumentException => <handler code> - * case e: ... => ... - * } - * }}} - * - * will inline the exception handler code to: - * - * {{{ - * try { - * ... - * if (condition) - * <handler code> // + jump to the end of the catch statement - * } catch { - * case e: IllegalArgumentException => <handler code> - * case e: ... => ... - * } - * }}} - * - * Q: How does the inlining work, ICode level? - * A: if a block contains a THROW(A) instruction AND there is a handler that takes A or a superclass of A we do: - * 1. We duplicate the handler code such that we can transform THROW into a JUMP - * 2. We analyze the handler to see what local it expects the exception to be placed in - * 3. We place the exception that is thrown in the correct "local variable" slot and clean up the stack - * 4. We finally JUMP to the duplicate handler - * All the above logic is implemented in InlineExceptionHandlersPhase.apply(bblock: BasicBlock) - * - * Q: Why do we need to duplicate the handler? - * A: An exception might be thrown in a method that we invoke in the function and we cannot see that THROW command - * directly. In order to catch such exceptions, we keep the exception handler in place and duplicate it in order - * to inline its code. - * - * @author Vlad Ureche - */ -abstract class InlineExceptionHandlers extends SubComponent { - import global._ - import icodes._ - import icodes.opcodes._ - - val phaseName = "inlinehandlers" - - /** Create a new phase */ - override def newPhase(p: Phase) = new InlineExceptionHandlersPhase(p) - - override def enabled = settings.inlineHandlers - - /** - * Inlining Exception Handlers - */ - class InlineExceptionHandlersPhase(prev: Phase) extends ICodePhase(prev) { - def name = phaseName - - /* This map is used to keep track of duplicated exception handlers - * explanation: for each exception handler basic block, there is a copy of it - * -some exception handler basic blocks might not be duplicated because they have an unknown format => Option[(...)] - * -some exception handler duplicates expect the exception on the stack while others expect it in a local - * => Option[Local] - */ - private val handlerCopies = perRunCaches.newMap[BasicBlock, Option[(Option[Local], BasicBlock)]]() - /* This map is the inverse of handlerCopies, used to compute the stack of duplicate blocks */ - private val handlerCopiesInverted = perRunCaches.newMap[BasicBlock, (BasicBlock, TypeKind)]() - private def handlerLocal(bb: BasicBlock): Option[Local] = - for (v <- handlerCopies get bb ; (local, block) <- v ; l <- local) yield l - - /* Type Flow Analysis */ - private val tfa: analysis.MethodTFA = new analysis.MethodTFA() - private var tfaCache: Map[Int, tfa.lattice.Elem] = Map.empty - private var analyzedMethod: IMethod = NoIMethod - - /* Blocks that need to be analyzed */ - private var todoBlocks: List[BasicBlock] = Nil - - /* Used only for warnings */ - private var currentClass: IClass = null - - /** Apply exception handler inlining to a class */ - override def apply(c: IClass): Unit = - if (settings.inlineHandlers) { - val startTime = System.nanoTime() - currentClass = c - - debuglog("Starting InlineExceptionHandlers on " + c) - c.methods foreach applyMethod - debuglog("Finished InlineExceptionHandlers on " + c + "... " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime) + "ms") - currentClass = null - } - - /** - * Apply exception handler inlining to a method - * - * Note: for each exception handling block, we (might) create duplicates. Therefore we iterate until we get to a - * fixed point where all the possible handlers have been inlined. - * - * TODO: Should we have an inlining depth limit? A nested sequence of n try-catch blocks can lead to at most 2n - * inlined blocks, so worst case scenario we double the size of the code - */ - private def applyMethod(method: IMethod): Unit = { - if (method.hasCode) { - // create the list of starting blocks - todoBlocks = global.icodes.linearizer.linearize(method) - - while (todoBlocks.nonEmpty) { - val levelBlocks = todoBlocks - todoBlocks = Nil - levelBlocks foreach applyBasicBlock // new blocks will be added to todoBlocks - } - } - - // Cleanup the references after we finished the file - handlerCopies.clear() - handlerCopiesInverted.clear() - todoBlocks = Nil - - // Type flow analysis cleanup - analyzedMethod = NoIMethod - tfaCache = Map.empty - //TODO: Need a way to clear tfa structures - } - - /** Apply exception handler inlining to a basic block */ - private def applyBasicBlock(bblock: BasicBlock): Unit = { - /* - * The logic of this entire method: - * - for each basic block, we look at each instruction until we find a THROW instruction - * - once we found a THROW instruction, we decide if it is DECIDABLE which of handler will catch the exception - * (see method findExceptionHandler for more details) - * - if we decided there is a handler that will catch the exception, we need to replace the THROW instruction by - * a set of equivalent instructions: - * * we need to compute the static types of the stack slots - * * we need to clear the stack, everything but the exception instance on top (or in a local variable slot) - * * we need to JUMP to the duplicate exception handler - * - we compute the static types of the stack slots in function getTypesAtInstruction - * - we duplicate the exception handler (and we get back the information of whether the duplicate expects the - * exception instance on top of the stack or in a local variable slot) - * - we compute the necessary code to put the exception in its place, clear the stack and JUMP - * - we change the THROW exception to the new Clear stack + JUMP code - */ - for { - (instr @ THROW(clazz), index) <- bblock.iterator.zipWithIndex - // Decide if any handler fits this exception - // If not, then nothing to do, we cannot determine statically which handler will catch the exception - (handler, caughtException) <- findExceptionHandler(toTypeKind(clazz.tpe), bblock.exceptionSuccessors) - } { - log(" Replacing " + instr + " in " + bblock + " to new handler") - - // Solve the stack and drop the element that we already stored, which should be the exception - // needs to be done here to be the first thing before code becomes altered - val typeInfo = getTypesAtInstruction(bblock, index) - - // Duplicate exception handler - duplicateExceptionHandlerCache(handler) match { - case None => - log(" Could not duplicate handler for " + instr + " in " + bblock) - - case Some((exceptionLocalOpt, newHandler)) => - val onStackException = typeInfo.head - val thrownException = toTypeKind(clazz.tpe) - - // A couple of sanity checks, to make sure we don't touch code we can't safely handle - val canReplaceHandler = ( - typeInfo.nonEmpty - && (index == bblock.length - 1) - && (onStackException <:< thrownException) - ) - // in other words: what's on the stack MUST conform to what's in the THROW(..)! - - if (!canReplaceHandler) { - reporter.warning(NoPosition, "Unable to inline the exception handler inside incorrect" + - " block:\n" + bblock.iterator.mkString("\n") + "\nwith stack: " + typeInfo + " just " + - "before instruction index " + index) - } - else { - // Prepare the new code to replace the THROW instruction - val newCode = exceptionLocalOpt match { - // the handler duplicate expects the exception in a local: easy one :) - case Some(local) => - // in the first cycle we remove the exception Type - STORE_LOCAL(local) +: typeInfo.tail.map(x => DROP(x)) :+ JUMP(newHandler) - - // we already have the exception on top of the stack, only need to JUMP - case None if typeInfo.length == 1 => - JUMP(newHandler) :: Nil - - // we have the exception on top of the stack but we have other stuff on the stack - // create a local, load exception, clear the stack and finally store the exception on the stack - case _ => - val exceptionType = typeInfo.head - // Here we could create a single local for all exceptions of a certain type. TODO: try that. - val localName = currentClass.cunit.freshTermName("exception$") - val localType = exceptionType - val localSymbol = bblock.method.symbol.newValue(localName).setInfo(localType.toType) - val local = new Local(localSymbol, localType, false) - - bblock.method.addLocal(local) - - // Save the exception, drop the stack and place back the exception - STORE_LOCAL(local) :: typeInfo.tail.map(x => DROP(x)) ::: List(LOAD_LOCAL(local), JUMP(newHandler)) - } - // replace THROW by the new code - bblock.replaceInstruction(instr, newCode) - - // notify the successors changed for the current block - // notify the predecessors changed for the inlined handler block - bblock.touched = true - newHandler.touched = true - - log(" Replaced " + instr + " in " + bblock + " to new handler") - log("OPTIMIZED class " + currentClass + " method " + - bblock.method + " block " + bblock + " newhandler " + - newHandler + ":\n\t\t" + onStackException + " <:< " + - thrownException + " <:< " + caughtException) - - } - } - } - } - - /** - * Gets the types on the stack at a certain point in the program. Note that we want to analyze the method lazily - * and therefore use the analyzedMethod variable - */ - private def getTypesAtInstruction(bblock: BasicBlock, index: Int): List[TypeKind] = { - // get the stack at the block entry - var typeInfo = getTypesAtBlockEntry(bblock) - - // perform tfa to the current instruction - log(" stack at the beginning of block " + bblock + " in function " + - bblock.method + ": " + typeInfo.stack) - for (i <- 0 to (index - 1)) { - typeInfo = tfa.interpret(typeInfo, bblock(i)) - log(" stack after interpret: " + typeInfo.stack + " after instruction " + - bblock(i)) - } - log(" stack before instruction " + index + " of block " + bblock + " in function " + - bblock.method + ": " + typeInfo.stack) - - // return the result - typeInfo.stack.types - } - - /** - * Gets the stack at the block entry. Normally the typeFlowAnalysis should be run again, but we know how to compute - * the stack for handler duplicates. For the locals, it's safe to assume the info from the original handler is - * still valid (a more precise analysis can be done, but it's not necessary) - */ - private def getTypesAtBlockEntry(bblock: BasicBlock): tfa.lattice.Elem = { - // lazily perform tfa, because it's expensive - // cache results by block label, as rewriting the code messes up the block's hashCode - if (analyzedMethod eq NoIMethod) { - analyzedMethod = bblock.method - tfa.init(bblock.method) - tfa.run() - log(" performed tfa on method: " + bblock.method) - - for (block <- bblock.method.blocks.sortBy(_.label)) - tfaCache += block.label -> tfa.in(block) - } - - log(" getting typeinfo at the beginning of block " + bblock) - - tfaCache.getOrElse(bblock.label, { - // this block was not analyzed, but it's a copy of some other block so its stack should be the same - log(" getting typeinfo at the beginning of block " + bblock + " as a copy of " + - handlerCopiesInverted(bblock)) - val (origBlock, exception) = handlerCopiesInverted(bblock) - val typeInfo = getTypesAtBlockEntry(origBlock) - val stack = - if (handlerLocal(origBlock).nonEmpty) Nil // empty stack, the handler copy expects an empty stack - else List(exception) // one slot on the stack for the exception - - // If we use the mutability property, it crashes the analysis - tfa.lattice.IState(new analysis.VarBinding(typeInfo.vars), new icodes.TypeStack(stack)) - }) - } - - /** - * Finds the first exception handler that matches the current exception - * - * Note the following code: - * {{{ - * try { - * throw new IllegalArgumentException("...") - * } catch { - * case e: RuntimeException => log("RuntimeException") - * case i: IllegalArgumentException => log("IllegalArgumentException") - * } - * }}} - * - * will print "RuntimeException" => we need the *first* valid handler - * - * There's a hidden catch here: say we have the following code: - * {{{ - * try { - * val exception: Throwable = - * if (scala.util.Random.nextInt % 2 == 0) - * new IllegalArgumentException("even") - * else - * new StackOverflowError("odd") - * throw exception - * } catch { - * case e: IllegalArgumentException => - * println("Correct, IllegalArgumentException") - * case e: StackOverflowError => - * println("Correct, StackOverflowException") - * case t: Throwable => - * println("WROOOONG, not Throwable!") - * } - * }}} - * - * We don't want to select a handler if there's at least one that's more specific! - */ - def findExceptionHandler(thrownException: TypeKind, handlers: List[BasicBlock]): Option[(BasicBlock, TypeKind)] = { - for (handler <- handlers ; LOAD_EXCEPTION(clazz) <- handler take 1) { - val caughtException = toTypeKind(clazz.tpe) - // we'll do inlining here: createdException <:< thrownException <:< caughtException, good! - if (thrownException <:< caughtException) - return Some((handler, caughtException)) - // we can't do inlining here, the handling mechanism is more precise than we can reason about - if (caughtException <:< thrownException) - return None - // no result yet, look deeper in the handler stack - } - None - } - - /** - * This function takes care of duplicating the basic block code for inlining the handler - * - * Note: This function does not duplicate the same basic block twice. It will contain a map of the duplicated - * basic blocks - */ - private def duplicateExceptionHandlerCache(handler: BasicBlock) = - handlerCopies.getOrElseUpdate(handler, duplicateExceptionHandler(handler)) - - /** This function takes care of actual duplication */ - private def duplicateExceptionHandler(handler: BasicBlock): Option[(Option[Local], BasicBlock)] = { - log(" duplicating handler block " + handler) - - handler take 2 match { - case Seq(LOAD_EXCEPTION(caughtClass), next) => - val (dropCount, exceptionLocal) = next match { - case STORE_LOCAL(local) => (2, Some(local)) // we drop both LOAD_EXCEPTION and STORE_LOCAL - case _ => (1, None) // we only drop the LOAD_EXCEPTION and expect the exception on the stack - } - val caughtException = toTypeKind(caughtClass.tpe) - // copy the exception handler code once again, dropping the LOAD_EXCEPTION - val copy = handler.code.newBlock() - copy.emitOnly((handler.iterator drop dropCount).toSeq: _*) - - // extend the handlers of the handler to the copy - for (parentHandler <- handler.method.exh ; if parentHandler covers handler) { - parentHandler.addCoveredBlock(copy) - // notify the parent handler that the successors changed - parentHandler.startBlock.touched = true - } - - // notify the successors of the inlined handler might have changed - copy.touched = true - handler.touched = true - log(" duplicated handler block " + handler + " to " + copy) - - // announce the duplicate handler - handlerCopiesInverted(copy) = ((handler, caughtException)) - todoBlocks ::= copy - - Some((exceptionLocal, copy)) - - case _ => - reporter.warning(NoPosition, "Unable to inline the exception handler due to incorrect format:\n" + - handler.iterator.mkString("\n")) - None - } - } - } -} |