Eliminate unreachable code before inlining a method

Running an ASM analyzer returns null frames for unreachable
instructions in the analyzed method. The inliner (and other components
of the optimizer) require unreachable code to be eliminated to avoid
null frames.

Before this change, unreachable code was eliminated before building
the call graph, but not again before inlining: the inliner assumed
that methods in the call graph have no unreachable code.

This invariant can break when inlining a method. Example:

  def f = throw e
  def g = f; println()

When building the call graph, both f and g contain no unreachable
code. After inlining f, the println() call becomes unreachable. This
breaks the inliner's assumption if it tries to inline a call to g.

This change intruduces a cache to remember methods that have no
unreachable code. This allows invoking DCE every time no dead code is
required, and bail out fast. This also simplifies following the
control flow in the optimizer (call DCE whenever no dead code is
required).

6 files changed, 81 insertions, 44 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)
   }
 
   /**