Don't create inline requests for callsites that cannot be inlined

When traversing the call graph and collecting inline reqeusts, rule
out callsites that we already know cannot be inlined.

Note that we cannot perform all necessary checks already at this
stage: checks that depend on the callee body (the inlined code) are
deferred until the callsite is actually inlined. The reason is that
the code may change. Example:

    @inline final def f = try 1 catch { case _: Throwable => 2 }
    @inline final def g = f
    def t = println(g)

When collecting inline requests, the body of g invokes the public
method f, so g could be inlined into t. However, once f is inlined
into g, the body of g contains a try-catch block. Now we cannot inline
g into t anymore, because the call stack at the g callsite is
non-empty (the stack is cleared when entering a handler).

4 files changed, 197 insertions, 71 deletions

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 f88c131e8d..9a5341e131 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -41,6 +41,10 @@ class Inliner[BT <: BTypes](val btypes: BT) {
       val callsite = request.callsite
       val Right(callee) = callsite.callee // collectAndOrderInlineRequests returns callsites with a known callee
 
+      // TODO: if the request has downstream requests, create a snapshot to which we could roll back in case some downstream callsite cannot be inlined
+      // (Needs to revert modifications to the callee method, but also the call graph)
+      // (This assumes that inlining a request only makes sense if its downstream requests are satisfied - sync with heuristics!)
+
       // Inlining a method can create unreachable code. Example:
       //   def f = throw e
       //   def g = f; println() // println is unreachable after inlining f
@@ -265,8 +269,8 @@ class Inliner[BT <: BTypes](val btypes: BT) {
    *
    * @return An inliner warning for each callsite that could not be inlined.
    */
-  def inline(request: InlineRequest): List[CannotInlineWarning] = canInline(request.callsite) match {
-    case Some(warning) => List(warning)
+  def inline(request: InlineRequest): List[CannotInlineWarning] = canInlineBody(request.callsite) match {
+    case Some(w) => List(w)
     case None =>
       val instructionsMap = inlineCallsite(request.callsite)
       val postRequests = request.post.flatMap(post => {
@@ -284,7 +288,7 @@ class Inliner[BT <: BTypes](val btypes: BT) {
    * Copy and adapt the instructions of a method to a callsite.
    *
    * Preconditions:
-   *   - The callsite can safely be inlined (canInline is true)
+   *   - 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
@@ -481,10 +485,45 @@ class Inliner[BT <: BTypes](val btypes: BT) {
   }
 
   /**
-   * Check whether an inling can be performed.
+   * Check whether an inlining can be performed. This method performs tests that don't change even
+   * if the body of the callee is changed by the inliner / optimizer, so it can be used early
+   * (when looking at the call graph and collecting inline requests for the program).
+   *
+   * The tests that inspect the callee's instructions are implemented in method `canInlineBody`,
+   * which is queried when performing an inline.
+   *
    * @return `Some(message)` if inlining cannot be performed, `None` otherwise
    */
-  def canInline(callsite: Callsite): Option[CannotInlineWarning] = {
+  def earlyCanInlineCheck(callsite: Callsite): Option[CannotInlineWarning] = {
+    import callsite.{callsiteMethod, callsiteClass}
+    val Right(callsiteCallee) = callsite.callee
+    import callsiteCallee.{callee, calleeDeclarationClass}
+
+    if (isSynchronizedMethod(callee)) {
+      // Could be done by locking on the receiver, wrapping the inlined code in a try and unlocking
+      // in finally. But it's probably not worth the effort, scala never emits synchronized methods.
+      Some(SynchronizedMethod(calleeDeclarationClass.internalName, callee.name, callee.desc))
+    } else if (isStrictfpMethod(callsiteMethod) != isStrictfpMethod(callee)) {
+      Some(StrictfpMismatch(
+        calleeDeclarationClass.internalName, callee.name, callee.desc,
+        callsiteClass.internalName, callsiteMethod.name, callsiteMethod.desc))
+    } else
+      None
+  }
+
+  /**
+   * Check whether the body of the callee contains any instructions that prevent the callsite from
+   * being inlined. See also method `earlyCanInlineCheck`.
+   *
+   * The result of this check depends on changes to the callee method's body. For example, if the
+   * callee initially invokes a private method, it cannot be inlined into a different class. If the
+   * private method is inlined into the callee, inlining the callee becomes possible. Therefore
+   * we don't query it while traversing the call graph and selecting callsites to inline - it might
+   * rule out callsites that can be inlined just fine.
+   *
+   * @return `Some(message)` if inlining cannot be performed, `None` otherwise
+   */
+  def canInlineBody(callsite: Callsite): Option[CannotInlineWarning] = {
     import callsite.{callsiteInstruction, callsiteMethod, callsiteClass, callsiteStackHeight}
     val Right(callsiteCallee) = callsite.callee
     import callsiteCallee.{callee, calleeDeclarationClass}
@@ -518,14 +557,6 @@ class Inliner[BT <: BTypes](val btypes: BT) {
       Some(ResultingMethodTooLarge(
         calleeDeclarationClass.internalName, callee.name, callee.desc,
         callsiteClass.internalName, callsiteMethod.name, callsiteMethod.desc))
-    } else if (isSynchronizedMethod(callee)) {
-      // Could be done by locking on the receiver, wrapping the inlined code in a try and unlocking
-      // in finally. But it's probably not worth the effort, scala never emits synchronized methods.
-      Some(SynchronizedMethod(calleeDeclarationClass.internalName, callee.name, callee.desc))
-    } else if (isStrictfpMethod(callsiteMethod) != isStrictfpMethod(callee)) {
-      Some(StrictfpMismatch(
-        calleeDeclarationClass.internalName, callee.name, callee.desc,
-        callsiteClass.internalName, callsiteMethod.name, callsiteMethod.desc))
     } else if (!callee.tryCatchBlocks.isEmpty && stackHasNonParameters) {
       Some(MethodWithHandlerCalledOnNonEmptyStack(
         calleeDeclarationClass.internalName, callee.name, callee.desc,
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/InlinerHeuristics.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/InlinerHeuristics.scala
index e559b63c09..d8f12ffb11 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/InlinerHeuristics.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/InlinerHeuristics.scala
@@ -12,6 +12,7 @@ import scala.tools.asm.Type
 import scala.tools.asm.tree.{MethodNode, MethodInsnNode}
 import scala.tools.nsc.backend.jvm.BTypes.InternalName
 import scala.collection.convert.decorateAsScala._
+import scala.tools.nsc.backend.jvm.BackendReporting.OptimizerWarning
 
 class InlinerHeuristics[BT <: BTypes](val bTypes: BT) {
   import bTypes._
@@ -38,25 +39,32 @@ class InlinerHeuristics[BT <: BTypes](val bTypes: BT) {
     compilingMethods.map(methodNode => {
       var requests = Set.empty[InlineRequest]
       callGraph.callsites(methodNode).valuesIterator foreach {
-        case callsite @ Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, _, warning)), _, _, _, pos) =>
-          val request = inlineRequest(callsite)
-          requests ++= request
-          if (request.isEmpty) {
-            if (annotatedInline && bTypes.compilerSettings.YoptWarningEmitAtInlineFailed) {
-              // if the callsite is annotated @inline, we report an inline warning even if the underlying
-              // reason is, for example, mixed compilation (which has a separate -Yopt-warning flag).
-              def initMsg = s"${BackendReporting.methodSignature(calleeDeclClass.internalName, callee)} is annotated @inline but cannot be inlined"
-              def warnMsg = warning.map(" Possible reason:\n" + _).getOrElse("")
-              if (doRewriteTraitCallsite(callsite))
-                backendReporting.inlinerWarning(pos, s"$initMsg: the trait method call could not be rewritten to the static implementation method." + warnMsg)
-              else if (!safeToInline)
-                backendReporting.inlinerWarning(pos, s"$initMsg: the method is not final and may be overridden." + warnMsg)
-              else
-                backendReporting.inlinerWarning(pos, s"$initMsg." + warnMsg)
-            } else if (warning.isDefined && warning.get.emitWarning(compilerSettings)) {
-              // when annotatedInline is false, and there is some warning, the callsite metadata is possibly incomplete.
-              backendReporting.inlinerWarning(pos, s"there was a problem determining if method ${callee.name} can be inlined: \n"+ warning.get)
-            }
+        case callsite @ Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, _, callsiteWarning)), _, _, _, pos) =>
+          inlineRequest(callsite) match {
+            case Some(Right(req)) => requests += req
+            case Some(Left(w))    =>
+              if ((annotatedInline && bTypes.compilerSettings.YoptWarningEmitAtInlineFailed) || w.emitWarning(compilerSettings)) {
+                val annotWarn = if (annotatedInline) " is annotated @inline but" else ""
+                val msg = s"${BackendReporting.methodSignature(calleeDeclClass.internalName, callee)}$annotWarn could not be inlined:\n$w"
+                backendReporting.inlinerWarning(callsite.callsitePosition, msg)
+              }
+
+            case None =>
+              if (annotatedInline && bTypes.compilerSettings.YoptWarningEmitAtInlineFailed) {
+                // if the callsite is annotated @inline, we report an inline warning even if the underlying
+                // reason is, for example, mixed compilation (which has a separate -Yopt-warning flag).
+                def initMsg = s"${BackendReporting.methodSignature(calleeDeclClass.internalName, callee)} is annotated @inline but cannot be inlined"
+                def warnMsg = callsiteWarning.map(" Possible reason:\n" + _).getOrElse("")
+                if (doRewriteTraitCallsite(callsite))
+                  backendReporting.inlinerWarning(pos, s"$initMsg: the trait method call could not be rewritten to the static implementation method." + warnMsg)
+                else if (!safeToInline)
+                  backendReporting.inlinerWarning(pos, s"$initMsg: the method is not final and may be overridden." + warnMsg)
+                else
+                  backendReporting.inlinerWarning(pos, s"$initMsg." + warnMsg)
+              } else if (callsiteWarning.isDefined && callsiteWarning.get.emitWarning(compilerSettings)) {
+                // when annotatedInline is false, and there is some warning, the callsite metadata is possibly incomplete.
+                backendReporting.inlinerWarning(pos, s"there was a problem determining if method ${callee.name} can be inlined: \n"+ callsiteWarning.get)
+              }
           }
 
         case Callsite(ins, _, _, Left(warning), _, _, _, pos) =>
@@ -73,27 +81,40 @@ class InlinerHeuristics[BT <: BTypes](val bTypes: BT) {
    *
    * The resulting inline request may contain post-inlining requests of callsites that in turn are
    * also selected as individual inlining requests.
+   *
+   * @return `None` if this callsite should not be inlined according to the active heuristic
+   *         `Some(Left)` if the callsite cannot be inlined (for example because that would cause
+   *           an IllegalAccessError) but should be according to the heuristic
+   *           TODO: what if a downstream inline request would cause an IAE and we don't create an
+   *           InlineRequest for the original callsite? new subclass of OptimizerWarning.
+   *         `Some(Right)` if the callsite should be and can be inlined
    */
-  def inlineRequest(callsite: Callsite): Option[InlineRequest] = compilerSettings.YoptInlineHeuristics.value match {
-    case "everything" =>
-      if (callsite.callee.get.safeToInline) Some(InlineRequest(callsite, Nil))
-      else None
-
-    case "at-inline-annotated" =>
-      val callee = callsite.callee.get
-      if (callee.safeToInline && callee.annotatedInline) Some(InlineRequest(callsite, Nil))
-      else None
-
-    case "default" =>
-      val callee = callsite.callee.get
-      if (callee.safeToInline && !callee.annotatedNoInline) {
-        val shouldInlineHO = callee.samParamTypes.nonEmpty && (callee.samParamTypes exists {
-          case (index, _) => callsite.argInfos.contains(index)
-        })
-
-        if (shouldInlineHO || callee.annotatedInline) Some(InlineRequest(callsite, Nil))
+  def inlineRequest(callsite: Callsite): Option[Either[OptimizerWarning, InlineRequest]] = {
+    val callee = callsite.callee.get
+    def requestIfCanInline(callsite: Callsite): Either[OptimizerWarning, InlineRequest] = inliner.earlyCanInlineCheck(callsite) match {
+      case Some(w) => Left(w)
+      case None => Right(InlineRequest(callsite, Nil))
+    }
+
+    compilerSettings.YoptInlineHeuristics.value match {
+      case "everything" =>
+        if (callee.safeToInline) Some(requestIfCanInline(callsite))
+        else None
+
+      case "at-inline-annotated" =>
+        if (callee.safeToInline && callee.annotatedInline) Some(requestIfCanInline(callsite))
         else None
-      } else None
+
+      case "default" =>
+        if (callee.safeToInline && !callee.annotatedNoInline) {
+          val shouldInlineHO = callee.samParamTypes.nonEmpty && (callee.samParamTypes exists {
+            case (index, _) => callsite.argInfos.contains(index)
+          })
+
+          if (shouldInlineHO || callee.annotatedInline) Some(requestIfCanInline(callsite))
+          else None
+        } else None
+    }
   }
 
   /*
diff --git a/test/junit/scala/tools/nsc/backend/jvm/DefaultMethodTest.scala b/test/junit/scala/tools/nsc/backend/jvm/DefaultMethodTest.scala
index f9a55bb26e..e57e95bac4 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/DefaultMethodTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/DefaultMethodTest.scala
@@ -16,8 +16,8 @@ object DefaultMethodTest extends ClearAfterClass.Clearable {
 }
 
 class DefaultMethodTest extends ClearAfterClass {
-  ClearAfterClass.stateToClear = DirectCompileTest
-  val compiler = DirectCompileTest.compiler
+  ClearAfterClass.stateToClear = DefaultMethodTest
+  val compiler = DefaultMethodTest.compiler
 
   @Test
   def defaultMethodsViaGenBCode(): Unit = {
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 1108a37266..81c6dd2ce2 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
@@ -103,8 +103,7 @@ class InlinerTest extends ClearAfterClass {
       callsitePosition = NoPosition),
     post = post)
 
-  // inline first invocation of f into g in class C
-  def inlineTest(code: String, mod: ClassNode => Unit = _ => ()): (MethodNode, List[CannotInlineWarning]) = {
+  def inlineRequest(code: String, mod: ClassNode => Unit = _ => ()): (inlinerHeuristics.InlineRequest, MethodNode) = {
     val List(cls) = compile(code)
     mod(cls)
     val clsBType = classBTypeFromParsedClassfile(cls.name)
@@ -123,9 +122,19 @@ class InlinerTest extends ClearAfterClass {
       callsiteStackHeight = analyzer.frameAt(fCall).getStackSize,
       receiverKnownNotNull = true
     )
+    (request, g)
+  }
+
+  // inline first invocation of f into g in class C
+  def inlineTest(code: String, mod: ClassNode => Unit = _ => ()): MethodNode = {
+    val (request, g) = inlineRequest(code, mod)
+    inliner.inline(request)
+    g
+  }
 
-    val r = inliner.inline(request)
-    (g, r)
+  def canInlineTest(code: String, mod: ClassNode => Unit = _ => ()): Option[OptimizerWarning] = {
+    val cs = inlineRequest(code, mod)._1.callsite
+    inliner.earlyCanInlineCheck(cs) orElse inliner.canInlineBody(cs)
   }
 
   @Test
@@ -137,7 +146,7 @@ class InlinerTest extends ClearAfterClass {
         |}
       """.stripMargin
 
-    val (g, _) = inlineTest(code)
+    val g = inlineTest(code)
 
     val gConv = convertMethod(g)
     assertSameCode(gConv.instructions.dropNonOp,
@@ -171,7 +180,7 @@ class InlinerTest extends ClearAfterClass {
 
     // See also discussion around ATHROW in BCodeBodyBuilder
 
-    val (g, _) = inlineTest(code)
+    val g = inlineTest(code)
     val expectedInlined = List(
       VarOp(ALOAD, 0), VarOp(ASTORE, 1), // store this
       Field(GETSTATIC, "scala/Predef$", "MODULE$", "Lscala/Predef$;"), Invoke(INVOKEVIRTUAL, "scala/Predef$", "$qmark$qmark$qmark", "()Lscala/runtime/Nothing$;", false)) // inlined call to ???
@@ -192,11 +201,11 @@ class InlinerTest extends ClearAfterClass {
         |}
       """.stripMargin
 
-    val (_, can) = inlineTest(code, cls => {
+    val can = canInlineTest(code, cls => {
       val f = cls.methods.asScala.find(_.name == "f").get
       f.access |= ACC_SYNCHRONIZED
     })
-    assert(can.length == 1 && can.head.isInstanceOf[SynchronizedMethod], can)
+    assert(can.nonEmpty && can.get.isInstanceOf[SynchronizedMethod], can)
   }
 
   @Test
@@ -207,7 +216,7 @@ class InlinerTest extends ClearAfterClass {
         |  def g = f + 1
         |}
       """.stripMargin
-    val (_, r) = inlineTest(code)
+    val r = canInlineTest(code)
     assert(r.isEmpty, r)
   }
 
@@ -221,8 +230,8 @@ class InlinerTest extends ClearAfterClass {
         |  def g = println(f)
         |}
       """.stripMargin
-    val (_, r) = inlineTest(code)
-    assert(r.length == 1 && r.head.isInstanceOf[MethodWithHandlerCalledOnNonEmptyStack], r)
+    val r = canInlineTest(code)
+    assert(r.nonEmpty && r.get.isInstanceOf[MethodWithHandlerCalledOnNonEmptyStack], r)
   }
 
   @Test
@@ -264,9 +273,8 @@ class InlinerTest extends ClearAfterClass {
       receiverKnownNotNull = true
     )
 
-    val r = inliner.inline(request)
-
-    assert(r.length == 1 && r.head.isInstanceOf[IllegalAccessInstruction], r)
+    val r = inliner.canInlineBody(request.callsite)
+    assert(r.nonEmpty && r.get.isInstanceOf[IllegalAccessInstruction], r)
   }
 
   @Test
@@ -421,8 +429,9 @@ class InlinerTest extends ClearAfterClass {
       receiverKnownNotNull = false
     )
 
-    val r = inliner.inline(request)
-    assert(r.isEmpty, r)
+    val warning = inliner.canInlineBody(request.callsite)
+    assert(warning.isEmpty, warning)
+    inliner.inline(request)
     val ins = instructionsFromMethod(f)
 
     // no invocations, lowestOneBit is inlined
@@ -1096,10 +1105,11 @@ class InlinerTest extends ClearAfterClass {
       post = List(inlinerHeuristics.PostInlineRequest(fCall, Nil))
     )
 
-    val r = inliner.inline(request)
+    val warning = inliner.canInlineBody(request.callsite)
+    assert(warning.isEmpty, warning)
+    inliner.inline(request)
     assertNoInvoke(getSingleMethod(c, "h")) // no invoke in h: first g is inlined, then the inlined call to f is also inlined
     assertInvoke(getSingleMethod(c, "g"), "C", "f") // g itself still has the call to f
-    assert(r.isEmpty, r)
   }
 
   /**
@@ -1134,4 +1144,68 @@ class InlinerTest extends ClearAfterClass {
     assertInvoke(getSingleMethod(c, "t4"), "scala/Function1", "apply$mcII$sp")
     assertInvoke(getSingleMethod(c, "t5"), "C", "h")
   }
+
+  @Test
+  def twoStepNoInlineHandler(): Unit = {
+    val code =
+      """class C {
+        |  @inline final def f = try 1 catch { case _: Throwable => 2 }
+        |  @inline final def g = f
+        |  def t = println(g)       // cannot inline g onto non-empty stack once that f was inlined into g
+        |}
+      """.stripMargin
+
+    val warn =
+      """C::g()I is annotated @inline but could not be inlined:
+        |The operand stack at the callsite in C::t()V contains more values than the
+        |arguments expected by the callee C::g()I. These values would be discarded
+        |when entering an exception handler declared in the inlined method.""".stripMargin
+
+    val List(c) = compile(code, allowMessage = _.msg contains warn)
+    assertInvoke(getSingleMethod(c, "t"), "C", "g")
+  }
+
+  @Test
+  def twoStepNoInlinePrivate(): Unit = {
+    val code =
+      """class C {
+        |  @inline final def g = {
+        |    @noinline def f = 0
+        |    f
+        |  }
+        |  @inline final def h = g   // after inlining g, h has an invocate of private method f$1
+        |}
+        |class D {
+        |  def t(c: C) = c.h  // cannot inline
+        |}
+      """.stripMargin
+
+    val warn =
+      """C::h()I is annotated @inline but could not be inlined:
+        |The callee C::h()I contains the instruction INVOKESPECIAL C.f$1 ()I
+        |that would cause an IllegalAccessError when inlined into class D.""".stripMargin
+
+    val List(c, d) = compile(code, allowMessage = _.msg contains warn)
+    assertInvoke(getSingleMethod(c, "h"), "C", "f$1")
+    assertInvoke(getSingleMethod(d, "t"), "C", "h")
+  }
+
+  @Test
+  def twoStepInlinePrivate(): Unit = {
+    val code =
+      """class C {
+        |  @inline final def g = {  // initially, g invokes the private method f$1, but then f$1 is inlined
+        |    @inline def f = 0
+        |    f
+        |  }
+        |}
+        |class D {
+        |  def t(c: C) = c.g  // can inline
+        |}
+      """.stripMargin
+
+    val List(c, d) = compile(code)
+    assertNoInvoke(getSingleMethod(c, "g"))
+    assertNoInvoke(getSingleMethod(d, "t"))
+  }
 }