diff options
8 files changed, 96 insertions, 45 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala index 74990fad02..57471874e2 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala @@ -11,7 +11,7 @@ import scala.collection.concurrent.TrieMap import scala.reflect.internal.util.Position import scala.tools.asm import asm.Opcodes -import scala.tools.asm.tree.{MethodInsnNode, InnerClassNode, ClassNode} +import scala.tools.asm.tree.{MethodNode, MethodInsnNode, InnerClassNode, ClassNode} import scala.tools.nsc.backend.jvm.BTypes.{InlineInfo, MethodInlineInfo} import scala.tools.nsc.backend.jvm.BackendReporting._ import scala.tools.nsc.backend.jvm.opt._ @@ -39,6 +39,8 @@ abstract class BTypes { */ val byteCodeRepository: ByteCodeRepository + val localOpt: LocalOpt + val inliner: Inliner[this.type] val callGraph: CallGraph[this.type] @@ -85,6 +87,18 @@ abstract class BTypes { val javaDefinedClasses: collection.mutable.Set[InternalName] = recordPerRunCache(collection.mutable.Set.empty) /** + * Cache, contains methods whose unreachable instructions are eliminated. + * + * The ASM Analyzer class does not compute any frame information for unreachable instructions. + * Transformations that use an analyzer (including inlining) therefore require unreachable code + * to be eliminated. + * + * This cache allows running dead code elimination whenever an analyzer is used. If the method + * is already optimized, DCE can return early. + */ + val unreachableCodeEliminated: collection.mutable.Set[MethodNode] = recordPerRunCache(collection.mutable.Set.empty) + + /** * Obtain the BType for a type descriptor or internal name. For class descriptors, the ClassBType * is constructed by parsing the corresponding classfile. * diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala index ad434889cf..41ce35888a 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala @@ -7,7 +7,7 @@ package scala.tools.nsc package backend.jvm import scala.tools.asm -import scala.tools.nsc.backend.jvm.opt.{CallGraph, Inliner, ByteCodeRepository} +import scala.tools.nsc.backend.jvm.opt.{LocalOpt, CallGraph, Inliner, ByteCodeRepository} import scala.tools.nsc.backend.jvm.BTypes.{InlineInfo, MethodInlineInfo, InternalName} import BackendReporting._ @@ -37,6 +37,8 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes { val byteCodeRepository = new ByteCodeRepository(global.classPath, javaDefinedClasses, recordPerRunCache(collection.concurrent.TrieMap.empty)) + val localOpt = new LocalOpt(settings, unreachableCodeEliminated) + val inliner: Inliner[this.type] = new Inliner(this) val callGraph: CallGraph[this.type] = new CallGraph(this) diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala index be1595dc29..4bfd70bf1e 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala @@ -215,17 +215,15 @@ abstract class GenBCode extends BCodeSyncAndTry { * - converting the plain ClassNode to byte array and placing it on queue-3 */ class Worker2 { - lazy val localOpt = new LocalOpt(settings) + // This instance is removed in a future commit that refactors LocalOpt + lazy val localOpt = new LocalOpt(settings, collection.mutable.Set()) def runGlobalOptimizations(): Unit = { import scala.collection.convert.decorateAsScala._ q2.asScala foreach { case Item2(_, _, plain, _, _) => // skip mirror / bean: wd don't inline into tem, and they are not used in the plain class - if (plain != null) { - localOpt.minimalRemoveUnreachableCode(plain) - callGraph.addClass(plain) - } + if (plain != null) callGraph.addClass(plain) } bTypes.inliner.runInliner() } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala index 47d32c94cb..a5a9f5e054 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala @@ -50,7 +50,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) { // (1) A non-final method can be safe to inline if the receiver type is a final subclass. Example: // class A { @inline def f = 1 }; object B extends A; B.f // can be inlined // - // TODO: type analysis can render more calls statically resolved. Example˜∫ + // TODO: type analysis can render more calls statically resolved. Example: // new A.f // can be inlined, the receiver type is known to be exactly A. val isStaticallyResolved: Boolean = { methodInlineInfo.effectivelyFinal || @@ -92,6 +92,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) { // TODO: for now we run a basic analyzer to get the stack height at the call site. // once we run a more elaborate analyzer (types, nullness), we can get the stack height out of there. + localOpt.minimalRemoveUnreachableCode(methodNode, definingClass.internalName) val analyzer = new AsmAnalyzer(methodNode, definingClass.internalName) methodNode.instructions.iterator.asScala.collect({ diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala index fbbb6bb5e0..538b02cdbb 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala @@ -24,21 +24,39 @@ class Inliner[BT <: BTypes](val btypes: BT) { import btypes._ import callGraph._ + def eliminateUnreachableCodeAndUpdateCallGraph(methodNode: MethodNode, definingClass: InternalName): Unit = { + localOpt.minimalRemoveUnreachableCode(methodNode, definingClass) foreach { + case invocation: MethodInsnNode => callGraph.callsites.remove(invocation) + case _ => + } + } + def runInliner(): Unit = { rewriteFinalTraitMethodInvocations() for (request <- collectAndOrderInlineRequests) { val Right(callee) = request.callee // collectAndOrderInlineRequests returns callsites with a known callee - val r = inline(request.callsiteInstruction, request.callsiteStackHeight, request.callsiteMethod, request.callsiteClass, - callee.callee, callee.calleeDeclarationClass, - receiverKnownNotNull = false, keepLineNumbers = false) - - for (warning <- r) { - if ((callee.annotatedInline && btypes.warnSettings.atInlineFailed) || warning.emitWarning(warnSettings)) { - val annotWarn = if (callee.annotatedInline) " is annotated @inline but" else "" - val msg = s"${BackendReporting.methodSignature(callee.calleeDeclarationClass.internalName, callee.callee)}$annotWarn could not be inlined:\n$warning" - backendReporting.inlinerWarning(request.callsitePosition, msg) + // Inlining a method can create unreachable code. Example: + // def f = throw e + // def g = f; println() // println is unreachable after inlining f + // If we have an inline request for a call to g, and f has been already inlined into g, we + // need to run DCE before inlining g. + eliminateUnreachableCodeAndUpdateCallGraph(callee.callee, callee.calleeDeclarationClass.internalName) + + // DCE above removes unreachable callsites from the call graph. If the inlining request denotes + // such an eliminated callsite, do nothing. + if (callGraph.callsites contains request.callsiteInstruction) { + val r = inline(request.callsiteInstruction, request.callsiteStackHeight, request.callsiteMethod, request.callsiteClass, + callee.callee, callee.calleeDeclarationClass, + receiverKnownNotNull = false, keepLineNumbers = false) + + for (warning <- r) { + if ((callee.annotatedInline && btypes.warnSettings.atInlineFailed) || warning.emitWarning(warnSettings)) { + val annotWarn = if (callee.annotatedInline) " is annotated @inline but" else "" + val msg = s"${BackendReporting.methodSignature(callee.calleeDeclarationClass.internalName, callee.callee)}$annotWarn could not be inlined:\n$warning" + backendReporting.inlinerWarning(request.callsitePosition, msg) + } } } } @@ -168,6 +186,8 @@ class Inliner[BT <: BTypes](val btypes: BT) { // VerifyError. We run a `SourceInterpreter` to find all producer instructions of the // receiver value and add a cast to the self type after each. if (!selfTypeOk) { + // there's no need to run eliminateUnreachableCode here. building the call graph does that + // already, no code can become unreachable in the meantime. val analyzer = new AsmAnalyzer(callsite.callsiteMethod, callsite.callsiteClass.internalName, new SourceInterpreter) val receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekDown(traitMethodArgumentTypes.length) for (i <- receiverValue.insns.asScala) { @@ -434,6 +454,9 @@ class Inliner[BT <: BTypes](val btypes: BT) { // Remove the elided invocation from the call graph callGraph.callsites.remove(callsiteInstruction) + // Inlining a method body can render some code unreachable, see example above (in runInliner). + unreachableCodeEliminated -= callsiteMethod + callsiteMethod.maxLocals += returnType.getSize + callee.maxLocals callsiteMethod.maxStack = math.max(callsiteMethod.maxStack, callee.maxStack + callsiteStackHeight) diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala index f6cfc5598b..fb5cfeb167 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala @@ -47,44 +47,37 @@ import scala.tools.nsc.settings.ScalaSettings * stale labels * - eliminate labels that are not referenced, merge sequences of label definitions. */ -class LocalOpt(settings: ScalaSettings) { - /** - * Remove unreachable code from all methods of `classNode`. See of its overload. - * - * @param classNode The class to optimize - * @return `true` if unreachable code was removed from any method - */ - def minimalRemoveUnreachableCode(classNode: ClassNode): Boolean = { - classNode.methods.asScala.foldLeft(false) { - case (changed, method) => minimalRemoveUnreachableCode(method, classNode.name) || changed - } - } - +class LocalOpt(settings: ScalaSettings, unreachableCodeEliminated: collection.mutable.Set[MethodNode]) { /** * Remove unreachable code from a method. * * This implementation only removes instructions that are unreachable for an ASM analyzer / * interpreter. This ensures that future analyses will not produce `null` frames. The inliner * and call graph builder depend on this property. + * + * @return A set containing the eliminated instructions */ - def minimalRemoveUnreachableCode(method: MethodNode, ownerClassName: InternalName): Boolean = { - if (method.instructions.size == 0) return false // fast path for abstract methods + def minimalRemoveUnreachableCode(method: MethodNode, ownerClassName: InternalName): Set[AbstractInsnNode] = { + if (method.instructions.size == 0) return Set.empty // fast path for abstract methods + if (unreachableCodeEliminated(method)) return Set.empty // we know there is no unreachable code // For correctness, after removing unreachable code, we have to eliminate empty exception // handlers, see scaladoc of def methodOptimizations. Removing an live handler may render more // code unreachable and therefore requires running another round. - def removalRound(): Boolean = { - val (codeRemoved, liveLabels) = removeUnreachableCodeImpl(method, ownerClassName) - if (codeRemoved) { + def removalRound(): Set[AbstractInsnNode] = { + val (removedInstructions, liveLabels) = removeUnreachableCodeImpl(method, ownerClassName) + val removedRecursively = if (removedInstructions.nonEmpty) { val liveHandlerRemoved = removeEmptyExceptionHandlers(method).exists(h => liveLabels(h.start)) if (liveHandlerRemoved) removalRound() - } - codeRemoved + else Set.empty + } else Set.empty + removedInstructions ++ removedRecursively } - val codeRemoved = removalRound() - if (codeRemoved) removeUnusedLocalVariableNodes(method)() - codeRemoved + val removedInstructions = removalRound() + if (removedInstructions.nonEmpty) removeUnusedLocalVariableNodes(method)() + unreachableCodeEliminated += method + removedInstructions } /** @@ -145,9 +138,9 @@ class LocalOpt(settings: ScalaSettings) { def removalRound(): Boolean = { // unreachable-code, empty-handlers and simplify-jumps run until reaching a fixpoint (see doc on class LocalOpt) val (codeRemoved, handlersRemoved, liveHandlerRemoved) = if (settings.YoptUnreachableCode) { - val (codeRemoved, liveLabels) = removeUnreachableCodeImpl(method, ownerClassName) + val (removedInstructions, liveLabels) = removeUnreachableCodeImpl(method, ownerClassName) val removedHandlers = removeEmptyExceptionHandlers(method) - (codeRemoved, removedHandlers.nonEmpty, removedHandlers.exists(h => liveLabels(h.start))) + (removedInstructions.nonEmpty, removedHandlers.nonEmpty, removedHandlers.exists(h => liveLabels(h.start))) } else { (false, false, false) } @@ -179,6 +172,8 @@ class LocalOpt(settings: ScalaSettings) { assert(nullOrEmpty(method.visibleLocalVariableAnnotations), method.visibleLocalVariableAnnotations) assert(nullOrEmpty(method.invisibleLocalVariableAnnotations), method.invisibleLocalVariableAnnotations) + unreachableCodeEliminated += method + codeHandlersOrJumpsChanged || localsRemoved || lineNumbersRemoved || labelsRemoved } @@ -186,8 +181,10 @@ class LocalOpt(settings: ScalaSettings) { * Removes unreachable basic blocks. * * TODO: rewrite, don't use computeMaxLocalsMaxStack (runs a ClassWriter) / Analyzer. Too slow. + * + * @return A set containing eliminated instructions, and a set containing all live label nodes. */ - def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: InternalName): (Boolean, Set[LabelNode]) = { + def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: InternalName): (Set[AbstractInsnNode], Set[LabelNode]) = { // The data flow analysis requires the maxLocals / maxStack fields of the method to be computed. computeMaxLocalsMaxStack(method) val a = new Analyzer(new BasicInterpreter) @@ -197,6 +194,7 @@ class LocalOpt(settings: ScalaSettings) { val initialSize = method.instructions.size var i = 0 var liveLabels = Set.empty[LabelNode] + var removedInstructions = Set.empty[AbstractInsnNode] val itr = method.instructions.iterator() while (itr.hasNext) { itr.next() match { @@ -209,11 +207,12 @@ class LocalOpt(settings: ScalaSettings) { // Instruction iterators allow removing during iteration. // Removing is O(1): instructions are doubly linked list elements. itr.remove() + removedInstructions += ins } } i += 1 } - (method.instructions.size != initialSize, liveLabels) + (removedInstructions, liveLabels) } /** diff --git a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala index 5d5215d887..3ba3caa5e3 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala @@ -160,7 +160,7 @@ object CodeGenTools { val localOpt = { val settings = new MutableSettings(msg => throw new IllegalArgumentException(msg)) settings.processArguments(List("-Yopt:l:method"), processAll = true) - new LocalOpt(settings) + new LocalOpt(settings, collection.mutable.Set()) } import scala.language.implicitConversions diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala index 39fb28570e..9d23d92c2a 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala @@ -950,4 +950,18 @@ class InlinerTest extends ClearAfterClass { assertInvoke(getSingleMethod(t, "t3"), "B", "<init>") assertInvoke(getSingleMethod(t, "t4"), "B", "<init>") } + + @Test + def inlineMayRenderCodeDead(): Unit = { + val code = + """class C { + | @inline final def f: String = throw new Error("") + | @inline final def g: String = "a" + f + "b" // after inlining f, need to run DCE, because the rest of g becomes dead. + | def t = g // the inliner requires no dead code when inlining g (uses an Analyzer). + |} + """.stripMargin + + val List(c) = compile(code) + assertInvoke(getSingleMethod(c, "t"), "java/lang/Error", "<init>") + } } |