Run DCE before the closure optimizer (fixes a crash)

Before identifying function callsites within the same method as a
closure allocation, run DCE. The ProdCons analysis used to identify
these function calls may crash if there is unreachable code, as
observed in the community build with scala-js.

The crash was rare because inlining, which is performed before closure
optimizations, already runs DCE. However, inlining may render more
code unreachable (e.g. when inlining a method that throws).

Also make sure that DCE is always performed on the callee before
inlining: move the DCE invocation into the inlineCallsite method,
which is also invoked by the closure optimizer.

4 files changed, 154 insertions, 111 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BackendReporting.scala b/src/compiler/scala/tools/nsc/backend/jvm/BackendReporting.scala
index 05cc484135..13f4738d3d 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BackendReporting.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BackendReporting.scala
@@ -287,7 +287,7 @@ object BackendReporting {
         s"Failed to get the type of a method of class symbol $classFullName due to SI-9111."
 
       case ClassNotFoundWhenBuildingInlineInfoFromSymbol(missingClass) =>
-        s"Failed to build the inline information: $missingClass."
+        s"Failed to build the inline information: $missingClass"
 
       case UnknownScalaInlineInfoVersion(internalName, version) =>
         s"Cannot read ScalaInlineInfo version $version in classfile $internalName. Use a more recent compiler."
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
index 61d10eeae9..a041af2621 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
@@ -8,7 +8,7 @@ package backend.jvm
 package opt
 
 import scala.annotation.switch
-import scala.collection.immutable
+import scala.collection.{mutable, immutable}
 import scala.collection.immutable.IntMap
 import scala.reflect.internal.util.NoPosition
 import scala.tools.asm.{Handle, Type, Opcodes}
@@ -73,37 +73,58 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) {
       }
     }
 
-    // For each closure instantiation, a list of callsites of the closure that can be re-written
-    // If a callsite cannot be rewritten, for example because the lambda body method is not accessible,
-    // a warning is returned instead.
-    val callsitesToRewrite: List[(ClosureInstantiation, List[Either[RewriteClosureApplyToClosureBodyFailed, (MethodInsnNode, Int)]])] = {
-      closureInstantiations.iterator.flatMap({
-        case (methodNode, closureInits) =>
-          if (!AsmAnalyzer.sizeOKForSourceValue(methodNode)) Nil else {
+    // Use collections that keep insertion order, ensures order of closure rewrites (bytecode stability)
+    val toRewrite = mutable.LinkedHashMap.empty[ClosureInstantiation, mutable.ArrayBuffer[(MethodInsnNode, Int)]]
+    def addRewrite(init: ClosureInstantiation, invocation: MethodInsnNode, stackHeight: Int) = {
+      val calls = toRewrite.getOrElseUpdate(init, mutable.ArrayBuffer.empty[(MethodInsnNode, Int)])
+      calls += ((invocation, stackHeight))
+    }
+
+    // For each closure instantiation find callsites of the closure and add them to the toRewrite
+    // buffer (cannot change a method's bytecode while still looking for further invocations to
+    // rewrite, the frame indices of the ProdCons analysis would get out of date). If a callsite
+    // cannot be rewritten, for example because the lambda body method is not accessible, issue a
+    // warning. The `toList` in the next line prevents modifying closureInstantiations while
+    // iterating it: minimalRemoveUnreachableCode (called in the loop) removes elements.
+    for (method <- closureInstantiations.keysIterator.toList if AsmAnalyzer.sizeOKForBasicValue(method)) closureInstantiations.get(method) match {
+      case Some(closureInitsBeforeDCE) if closureInitsBeforeDCE.nonEmpty =>
+        val ownerClass = closureInitsBeforeDCE.head._2.ownerClass.internalName
+
+        // Advanced ProdCons queries (initialProducersForValueAt) expect no unreachable code.
+        localOpt.minimalRemoveUnreachableCode(method, ownerClass)
+
+        if (AsmAnalyzer.sizeOKForSourceValue(method)) closureInstantiations.get(method) match {
+          case Some(closureInits) =>
             // A lazy val to ensure the analysis only runs if necessary (the value is passed by name to `closureCallsites`)
-            // We don't need to worry about the method being too large for running an analysis: large
-            // methods are not added to the call graph / closureInstantiations map.
-            lazy val prodCons = new ProdConsAnalyzer(methodNode, closureInits.valuesIterator.next().ownerClass.internalName)
+            lazy val prodCons = new ProdConsAnalyzer(method, ownerClass)
+
             // sorting for bytecode stability (e.g. indices of local vars created during the rewrite)
             val sortedInits = immutable.TreeSet.empty ++ closureInits.values
-            sortedInits.iterator.map(init => (init, closureCallsites(init, prodCons))).filter(_._2.nonEmpty)
-          }
-      }).toList // mapping to a list (not a map) to keep the sorting
+
+            for (init <- sortedInits) {
+              val callsites = closureCallsites(init, prodCons)
+              if (callsites.nonEmpty) {
+                callsites foreach {
+                  case Left(warning) =>
+                    backendReporting.inlinerWarning(warning.pos, warning.toString)
+
+                  case Right((invocation, stackHeight)) =>
+                    addRewrite(init, invocation, stackHeight)
+                }
+              }
+            }
+
+          case _ =>
+        }
+
+      case _ =>
     }
 
-    // Rewrite all closure callsites (or issue inliner warnings for those that cannot be rewritten)
-    for ((closureInit, callsites) <- callsitesToRewrite) {
-      // Local variables that hold the captured values and the closure invocation arguments.
-      // They are lazy vals to ensure that locals for captured values are only allocated if there's
-      // actually a callsite to rewrite (an not only warnings to be issued).
-      lazy val (localsForCapturedValues, argumentLocalsList) = localsForClosureRewrite(closureInit)
-      for (callsite <- callsites) callsite match {
-        case Left(warning) =>
-          backendReporting.inlinerWarning(warning.pos, warning.toString)
-
-        case Right((invocation, stackHeight)) =>
-          rewriteClosureApplyInvocation(closureInit, invocation, stackHeight, localsForCapturedValues, argumentLocalsList)
-      }
+    toRewrite foreach {
+      case (closureInit, invocations) =>
+        // Local variables that hold the captured values and the closure invocation arguments.
+        val (localsForCapturedValues, argumentLocalsList) = localsForClosureRewrite(closureInit)
+        for ((invocation, stackHeight) <- invocations) rewriteClosureApplyInvocation(closureInit, invocation, stackHeight, localsForCapturedValues, argumentLocalsList)
     }
   }
 
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 d1bccf614e..f247e884ae 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -70,11 +70,13 @@ class Inliner[BT <: BTypes](val btypes: BT) {
     }
   }
 
+  // Rewriting final trait method callsites to the implementation class enables inlining.
   def rewriteFinalTraitMethodInvocations(): Unit = {
-    // Rewriting final trait method callsites to the implementation class enables inlining.
-    // We cannot just iterate over the values of the `callsites` map because the rewrite changes the
-    // map. Therefore we first copy the values to a list.
-    callsites.valuesIterator.flatMap(_.valuesIterator).toList.foreach(rewriteFinalTraitMethodInvocation)
+    // Collect callsites to rewrite before actually rewriting anything. This prevents changing the
+    // `callsties` map while iterating it.
+    val toRewrite = mutable.ArrayBuffer.empty[Callsite]
+    for (css <- callsites.valuesIterator; cs <- css.valuesIterator if doRewriteTraitCallsite(cs)) toRewrite += cs
+    toRewrite foreach rewriteFinalTraitMethodInvocation
   }
 
   /**
@@ -93,78 +95,82 @@ class Inliner[BT <: BTypes](val btypes: BT) {
    * (the receiver type is the interface, so the method is abstract).
    */
   def rewriteFinalTraitMethodInvocation(callsite: Callsite): Unit = {
-    if (doRewriteTraitCallsite(callsite)) {
-      val Right(Callee(callee, calleeDeclarationClass, _, _, annotatedInline, annotatedNoInline, samParamTypes, infoWarning)) = callsite.callee
+    // The analyzer used below needs to have a non-null frame for the callsite instruction
+    localOpt.minimalRemoveUnreachableCode(callsite.callsiteMethod, callsite.callsiteClass.internalName)
 
-      val traitMethodArgumentTypes = asm.Type.getArgumentTypes(callee.desc)
+    // If the callsite was eliminated by DCE, do nothing.
+    if (!callGraph.containsCallsite(callsite)) return
 
-      val implClassInternalName = calleeDeclarationClass.internalName + "$class"
+    val Right(Callee(callee, calleeDeclarationClass, _, _, annotatedInline, annotatedNoInline, samParamTypes, infoWarning)) = callsite.callee
 
-      val selfParamTypeV: Either[OptimizerWarning, ClassBType] = calleeDeclarationClass.info.map(_.inlineInfo.traitImplClassSelfType match {
-        case Some(internalName) => classBTypeFromParsedClassfile(internalName)
-        case None               => calleeDeclarationClass
-      })
+    val traitMethodArgumentTypes = asm.Type.getArgumentTypes(callee.desc)
 
-      def implClassMethodV(implMethodDescriptor: String): Either[OptimizerWarning, MethodNode] = {
-        byteCodeRepository.methodNode(implClassInternalName, callee.name, implMethodDescriptor).map(_._1)
-      }
+    val implClassInternalName = calleeDeclarationClass.internalName + "$class"
 
-      // The rewrite reading the implementation class and the implementation method from the bytecode
-      // repository. If either of the two fails, the rewrite is not performed.
-      val res = for {
-        selfParamType        <- selfParamTypeV
-        implMethodDescriptor =  asm.Type.getMethodDescriptor(asm.Type.getReturnType(callee.desc), selfParamType.toASMType +: traitMethodArgumentTypes: _*)
-        implClassMethod      <- implClassMethodV(implMethodDescriptor)
-        implClassBType       =  classBTypeFromParsedClassfile(implClassInternalName)
-        selfTypeOk           <- calleeDeclarationClass.isSubtypeOf(selfParamType)
-      } yield {
-
-        // The self parameter type may be incompatible with the trait type.
-        //   trait T { self: S => def foo = 1 }
-        // The $self parameter type of T$class.foo is S, which may be unrelated to T. If we re-write
-        // a call to T.foo to T$class.foo, we need to cast the receiver to S, otherwise we get a
-        // 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) {
-          // We don't need to worry about the method being too large for running an analysis.
-          // Callsites of large methods are not added to the call graph.
-          val analyzer = new AsmAnalyzer(callsite.callsiteMethod, callsite.callsiteClass.internalName, new Analyzer(new SourceInterpreter))
-          val receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekStack(traitMethodArgumentTypes.length)
-          for (i <- receiverValue.insns.asScala) {
-            val cast = new TypeInsnNode(CHECKCAST, selfParamType.internalName)
-            callsite.callsiteMethod.instructions.insert(i, cast)
-          }
-        }
+    val selfParamTypeV: Either[OptimizerWarning, ClassBType] = calleeDeclarationClass.info.map(_.inlineInfo.traitImplClassSelfType match {
+      case Some(internalName) => classBTypeFromParsedClassfile(internalName)
+      case None               => calleeDeclarationClass
+    })
 
-        val newCallsiteInstruction = new MethodInsnNode(INVOKESTATIC, implClassInternalName, callee.name, implMethodDescriptor, false)
-        callsite.callsiteMethod.instructions.insert(callsite.callsiteInstruction, newCallsiteInstruction)
-        callsite.callsiteMethod.instructions.remove(callsite.callsiteInstruction)
+    def implClassMethodV(implMethodDescriptor: String): Either[OptimizerWarning, MethodNode] = {
+      byteCodeRepository.methodNode(implClassInternalName, callee.name, implMethodDescriptor).map(_._1)
+    }
 
-        callGraph.removeCallsite(callsite.callsiteInstruction, callsite.callsiteMethod)
-        val staticCallSamParamTypes = {
-          if (selfParamType.info.get.inlineInfo.sam.isEmpty) samParamTypes - 0
-          else samParamTypes.updated(0, selfParamType)
+    // The rewrite reading the implementation class and the implementation method from the bytecode
+    // repository. If either of the two fails, the rewrite is not performed.
+    val res = for {
+      selfParamType        <- selfParamTypeV
+      implMethodDescriptor =  asm.Type.getMethodDescriptor(asm.Type.getReturnType(callee.desc), selfParamType.toASMType +: traitMethodArgumentTypes: _*)
+      implClassMethod      <- implClassMethodV(implMethodDescriptor)
+      implClassBType       =  classBTypeFromParsedClassfile(implClassInternalName)
+      selfTypeOk           <- calleeDeclarationClass.isSubtypeOf(selfParamType)
+    } yield {
+
+      // The self parameter type may be incompatible with the trait type.
+      //   trait T { self: S => def foo = 1 }
+      // The $self parameter type of T$class.foo is S, which may be unrelated to T. If we re-write
+      // a call to T.foo to T$class.foo, we need to cast the receiver to S, otherwise we get a
+      // 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) {
+        // We don't need to worry about the method being too large for running an analysis.
+        // Callsites of large methods are not added to the call graph.
+        val analyzer = new AsmAnalyzer(callsite.callsiteMethod, callsite.callsiteClass.internalName, new Analyzer(new SourceInterpreter))
+        val receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekStack(traitMethodArgumentTypes.length)
+        for (i <- receiverValue.insns.asScala) {
+          val cast = new TypeInsnNode(CHECKCAST, selfParamType.internalName)
+          callsite.callsiteMethod.instructions.insert(i, cast)
         }
-        val staticCallsite = callsite.copy(
-          callsiteInstruction = newCallsiteInstruction,
-          callee              = Right(Callee(
-            callee                 = implClassMethod,
-            calleeDeclarationClass = implClassBType,
-            safeToInline           = true,
-            safeToRewrite          = false,
-            annotatedInline        = annotatedInline,
-            annotatedNoInline      = annotatedNoInline,
-            samParamTypes          = staticCallSamParamTypes,
-            calleeInfoWarning      = infoWarning))
-        )
-        callGraph.addCallsite(staticCallsite)
       }
 
-      for (warning <- res.left) {
-        val Right(callee) = callsite.callee
-        val newCallee = callee.copy(calleeInfoWarning = Some(RewriteTraitCallToStaticImplMethodFailed(calleeDeclarationClass.internalName, callee.callee.name, callee.callee.desc, warning)))
-        callGraph.addCallsite(callsite.copy(callee = Right(newCallee)))
+      val newCallsiteInstruction = new MethodInsnNode(INVOKESTATIC, implClassInternalName, callee.name, implMethodDescriptor, false)
+      callsite.callsiteMethod.instructions.insert(callsite.callsiteInstruction, newCallsiteInstruction)
+      callsite.callsiteMethod.instructions.remove(callsite.callsiteInstruction)
+
+      callGraph.removeCallsite(callsite.callsiteInstruction, callsite.callsiteMethod)
+      val staticCallSamParamTypes = {
+        if (selfParamType.info.get.inlineInfo.sam.isEmpty) samParamTypes - 0
+        else samParamTypes.updated(0, selfParamType)
       }
+      val staticCallsite = callsite.copy(
+        callsiteInstruction = newCallsiteInstruction,
+        callee              = Right(Callee(
+          callee                 = implClassMethod,
+          calleeDeclarationClass = implClassBType,
+          safeToInline           = true,
+          safeToRewrite          = false,
+          annotatedInline        = annotatedInline,
+          annotatedNoInline      = annotatedNoInline,
+          samParamTypes          = staticCallSamParamTypes,
+          calleeInfoWarning      = infoWarning))
+      )
+      callGraph.addCallsite(staticCallsite)
+    }
+
+    for (warning <- res.left) {
+      val Right(callee) = callsite.callee
+      val newCallee = callee.copy(calleeInfoWarning = Some(RewriteTraitCallToStaticImplMethodFailed(calleeDeclarationClass.internalName, callee.callee.name, callee.callee.desc, warning)))
+      callGraph.addCallsite(callsite.copy(callee = Right(newCallee)))
     }
   }
 
@@ -302,21 +308,9 @@ class Inliner[BT <: BTypes](val btypes: BT) {
   def inline(request: InlineRequest): List[CannotInlineWarning] = canInlineBody(request.callsite) match {
     case Some(w) => List(w)
     case None =>
-      // 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.
-      val Right(callee) = request.callsite.callee
-      localOpt.minimalRemoveUnreachableCode(callee.callee, callee.calleeDeclarationClass.internalName)
-      // Skip over DCE'd callsites
-      if (callGraph.containsCallsite(request.callsite)) {
-        inlineCallsite(request.callsite)
-        val postRequests = request.post.flatMap(adaptPostRequestForMainCallsite(_, request.callsite))
-        postRequests flatMap inline
-      } else {
-        Nil
-      }
+      inlineCallsite(request.callsite)
+      val postRequests = request.post.flatMap(adaptPostRequestForMainCallsite(_, request.callsite))
+      postRequests flatMap inline
   }
 
   /**
@@ -325,8 +319,6 @@ class Inliner[BT <: BTypes](val btypes: BT) {
    * Preconditions:
    *   - The callsite can safely be inlined (canInlineBody is true)
    *   - The maxLocals and maxStack values of the callsite method are correctly computed
-   *   - The callsite method contains no unreachable basic blocks, i.e., running an Analyzer does
-   *     not produce any `null` frames
    *
    * @return A map associating instruction nodes of the callee with the corresponding cloned
    *         instruction in the callsite method.
@@ -336,6 +328,17 @@ class Inliner[BT <: BTypes](val btypes: BT) {
     val Right(callsiteCallee) = callsite.callee
     import callsiteCallee.{callee, calleeDeclarationClass}
 
+    // Inlining requires the callee not to have unreachable code, the analyzer used below should not
+    // return any `null` frames. Note that 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 on g's body before inlining g.
+    localOpt.minimalRemoveUnreachableCode(callee, calleeDeclarationClass.internalName)
+
+    // If the callsite was eliminated by DCE, do nothing.
+    if (!callGraph.containsCallsite(callsite)) return
+
     // New labels for the cloned instructions
     val labelsMap = cloneLabels(callee)
     val (clonedInstructions, instructionMap, hasSerializableClosureInstantiation) = cloneInstructions(callee, labelsMap)
@@ -512,7 +515,7 @@ class Inliner[BT <: BTypes](val btypes: BT) {
     // Remove the elided invocation from the call graph
     callGraph.removeCallsite(callsiteInstruction, callsiteMethod)
 
-    // Inlining a method body can render some code unreachable, see example above (in runInliner).
+    // Inlining a method body can render some code unreachable, see example above in this method.
     unreachableCodeEliminated -= callsiteMethod
   }
 
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
index 0f87280000..b314643fb1 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
@@ -87,4 +87,23 @@ class ClosureOptimizerTest extends ClearAfterClass {
         TypeOp(CHECKCAST, "java/lang/String"), Invoke(INVOKESTATIC, "C", "C$$$anonfun$1", "(Ljava/lang/String;)Ljava/lang/String;", false),
         Op(ARETURN)))
   }
+
+  @Test
+  def closureOptWithUnreachableCode(): Unit = {
+    // this example used to crash the ProdCons analysis in the closure optimizer - ProdCons
+    // expects no unreachable code.
+    val code =
+      """class C {
+        |  @inline final def m = throw new Error("")
+        |  def t = {
+        |    val f = (x: Int) => x + 1
+        |    m
+        |    f(10) // unreachable after inlining m
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(compiler)(code)
+    assertEquals(getSingleMethod(c, "t").instructions.summary,
+      List(NEW, DUP, LDC, "<init>", ATHROW))
+  }
 }