Integrate the inliner into the backend pipeline

The current heuristics are simple: attempt to inline every method
annotated `@inline`. Cycles in the inline request graph are broken
in a determinisitc manner. Inlining is then performed starting at the
leaves of the inline request graph, i.e., with those callsites where
the target method has no callsites to inline.

This expansion strategy can make a method grow arbitrarily. We will
most likely have to add some thresholds and / or other measures to
prevent size issues.

5 files changed, 389 insertions, 14 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
index 9b3bd7648d..173aa0ca30 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala
@@ -217,11 +217,26 @@ abstract class GenBCode extends BCodeSyncAndTry {
     class Worker2 {
       lazy val localOpt = new LocalOpt(settings)
 
+      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)
+            }
+        }
+        bTypes.inliner.runInliner()
+      }
+
       def localOptimizations(classNode: ClassNode): Unit = {
         BackendStats.timed(BackendStats.methodOptTimer)(localOpt.methodOptimizations(classNode))
       }
 
       def run() {
+        if (settings.YoptInlinerEnabled) runGlobalOptimizations()
+
         while (true) {
           val item = q2.poll
           if (item.isPoison) {
@@ -269,7 +284,12 @@ abstract class GenBCode extends BCodeSyncAndTry {
 
     var arrivalPos = 0
 
-    /*
+    /**
+     * The `run` method is overridden because the backend has a different data flow than the default
+     * phase: the backend does not transform compilation units one by one, but on all units in the
+     * same run. This allows cross-unit optimizations and running some stages of the backend
+     * concurrently on multiple units.
+     *
      *  A run of the BCodePhase phase comprises:
      *
      *    (a) set-up steps (most notably supporting maps in `BCodeTypes`,
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 7527491e9b..b74c7ba86c 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -7,6 +7,7 @@ package scala.tools.nsc
 package backend.jvm
 package opt
 
+import scala.annotation.tailrec
 import scala.tools.asm
 import asm.Opcodes._
 import asm.tree._
@@ -16,11 +17,132 @@ import AsmUtils._
 import BytecodeUtils._
 import OptimizerReporting._
 import scala.tools.asm.tree.analysis._
+import collection.mutable
 
 class Inliner[BT <: BTypes](val btypes: BT) {
   import btypes._
   import callGraph._
 
+  def runInliner(): Unit = {
+    for (request <- collectAndOrderInlineRequests) {
+      val Some(callee) = request.callee
+      inline(request.callsiteInstruction, request.callsiteStackHeight, request.callsiteMethod, request.callsiteClass,
+        callee.callee, callee.calleeDeclarationClass,
+        receiverKnownNotNull = false, keepLineNumbers = false)
+    }
+  }
+
+  /**
+   * Ordering for inline requests. Required to make the inliner deterministic:
+   *   - Always remove the same request when breaking inlining cycles
+   *   - Perform inlinings in a consistent order
+   */
+  object callsiteOrdering extends Ordering[Callsite] {
+    override def compare(x: Callsite, y: Callsite): Int = {
+      val cls = x.callsiteClass.internalName compareTo y.callsiteClass.internalName
+      if (cls != 0) return cls
+
+      val name = x.callsiteMethod.name compareTo y.callsiteMethod.name
+      if (name != 0) return name
+
+      val desc = x.callsiteMethod.desc compareTo y.callsiteMethod.desc
+      if (desc != 0) return desc
+
+      def pos(c: Callsite) = c.callsiteMethod.instructions.indexOf(c.callsiteInstruction)
+      pos(x) - pos(y)
+    }
+  }
+
+  /**
+   * Select callsites from the call graph that should be inlined. The resulting list of inlining
+   * requests is allowed to have cycles, and the callsites can appear in any order.
+   */
+  def selectCallsitesForInlining: List[Callsite] = {
+    callsites.iterator.filter({
+      case (_, callsite) => callsite.callee match {
+        case Some(Callee(callee, _, safeToInline, Some(annotatedInline), _)) =>
+          // TODO: fix inlining from traits.
+          // For trait methods the callee is abstract: "trait T { @inline final def f = 1}".
+          // A callsite (t: T).f is `safeToInline` (effectivelyFinal is true), but the callee is the
+          // abstract method in the interface.
+          !isAbstractMethod(callee) && safeToInline && annotatedInline
+        case _ => false
+      }
+      case _ => false
+    }).map(_._2).toList
+  }
+
+  /**
+   * Returns the callsites that can be inlined. Ensures that the returned inline request graph does
+   * not contain cycles.
+   *
+   * The resulting list is sorted such that the leaves of the inline request graph are on the left.
+   * Once these leaves are inlined, the successive elements will be leaves, etc.
+   */
+  private def collectAndOrderInlineRequests: List[Callsite] = {
+    val requests = selectCallsitesForInlining
+
+    // This map is an index to look up the inlining requests for a method. The value sets are mutable
+    // to allow removing elided requests (to break inlining cycles). The map itself is mutable to
+    // allow efficient building: requests.groupBy would build values as List[Callsite] that need to
+    // be transformed to mutable sets.
+    val inlineRequestsForMethod: mutable.Map[MethodNode, mutable.Set[Callsite]] = mutable.HashMap.empty.withDefaultValue(mutable.HashSet.empty)
+    for (r <- requests) inlineRequestsForMethod.getOrElseUpdate(r.callsiteMethod, mutable.HashSet.empty) += r
+
+    /**
+     * Break cycles in the inline request graph by removing callsites.
+     *
+     * The list `requests` is traversed left-to-right, removing those callsites that are part of a
+     * cycle. Elided callsites are also removed from the `inlineRequestsForMethod` map.
+     */
+    def breakInlineCycles(requests: List[Callsite]): List[Callsite] = {
+      // is there a path of inline requests from start to goal?
+      def isReachable(start: MethodNode, goal: MethodNode): Boolean = {
+        @tailrec def reachableImpl(check: List[MethodNode], visited: Set[MethodNode]): Boolean = check match {
+          case x :: xs =>
+            if (x == goal) true
+            else if (visited(x)) reachableImpl(xs, visited)
+            else {
+              val callees = inlineRequestsForMethod(x).map(_.callee.get.callee)
+              reachableImpl(xs ::: callees.toList, visited + x)
+            }
+
+          case Nil =>
+            false
+        }
+        reachableImpl(List(start), Set.empty)
+      }
+
+      val result = new mutable.ListBuffer[Callsite]()
+      // sort the inline requests to ensure that removing requests is deterministic
+      for (r <- requests.sorted(callsiteOrdering)) {
+        // is there a chain of inlining requests that would inline the callsite method into the callee?
+        if (isReachable(r.callee.get.callee, r.callsiteMethod))
+          inlineRequestsForMethod(r.callsiteMethod) -= r
+        else
+          result += r
+      }
+      result.toList
+    }
+
+    // sort the remaining inline requests such that the leaves appear first, then those requests
+    // that become leaves, etc.
+    def leavesFirst(requests: List[Callsite], visited: Set[Callsite] = Set.empty): List[Callsite] = {
+      if (requests.isEmpty) Nil
+      else {
+        val (leaves, others) = requests.partition(r => {
+          val inlineRequestsForCallee = inlineRequestsForMethod(r.callee.get.callee)
+          inlineRequestsForCallee.forall(visited)
+        })
+        assert(leaves.nonEmpty, requests)
+        leaves ::: leavesFirst(others, visited ++ leaves)
+      }
+    }
+
+    leavesFirst(breakInlineCycles(requests))
+  }
+
+
   /**
    * Copy and adapt the instructions of a method to a callsite.
    *
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 23c8daa046..8c5a31658c 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -12,6 +12,7 @@ import scala.tools.asm.Opcodes
 import scala.tools.asm.tree.analysis.{Analyzer, BasicInterpreter}
 import scala.tools.asm.tree._
 import scala.collection.convert.decorateAsScala._
+import scala.tools.nsc.backend.jvm.BTypes.InternalName
 import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
 import scala.tools.nsc.settings.ScalaSettings
 
@@ -48,6 +49,37 @@ import scala.tools.nsc.settings.ScalaSettings
  */
 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
+    }
+  }
+
+  /**
+   * 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
+   * depends on this property.
+   */
+  def minimalRemoveUnreachableCode(method: MethodNode, ownerClassName: InternalName): Boolean = {
+    if (method.instructions.size == 0) return false // fast path for abstract methods
+
+    val (codeRemoved, _) = removeUnreachableCodeImpl(method, ownerClassName)
+    if (codeRemoved) {
+      // Required for correctness, see comment in class LocalOpt
+      removeEmptyExceptionHandlers(method)
+      removeUnusedLocalVariableNodes(method)()
+    }
+    codeRemoved
+  }
+
+  /**
    * Remove unreachable instructions from all (non-abstract) methods and apply various other
    * cleanups to the bytecode.
    *
@@ -73,7 +105,7 @@ class LocalOpt(settings: ScalaSettings) {
    *
    * Returns `true` if the bytecode of `method` was changed.
    */
-  def methodOptimizations(method: MethodNode, ownerClassName: String): Boolean = {
+  def methodOptimizations(method: MethodNode, ownerClassName: InternalName): Boolean = {
     if (method.instructions.size == 0) return false // fast path for abstract methods
 
     // unreachable-code also removes unused local variable nodes and empty exception handlers.
@@ -124,7 +156,7 @@ class LocalOpt(settings: ScalaSettings) {
 
     // (*) Removing stale local variable descriptors is required for correctness of unreachable-code
     val localsRemoved =
-      if (settings.YoptCompactLocals) compactLocalVariables(method)
+      if (settings.YoptCompactLocals) compactLocalVariables(method) // also removes unused
       else if (settings.YoptUnreachableCode) removeUnusedLocalVariableNodes(method)() // (*)
       else false
 
@@ -146,7 +178,7 @@ class LocalOpt(settings: ScalaSettings) {
    *
    * TODO: rewrite, don't use computeMaxLocalsMaxStack (runs a ClassWriter) / Analyzer. Too slow.
    */
-  def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: String): (Boolean, Set[LabelNode]) = {
+  def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: InternalName): (Boolean, 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)
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/CallGraphTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/CallGraphTest.scala
index 400fb6b00a..5946f50f0c 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/CallGraphTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/CallGraphTest.scala
@@ -23,8 +23,6 @@ import scala.collection.convert.decorateAsScala._
 
 @RunWith(classOf[JUnit4])
 class CallGraphTest {
-  // no need to move the compiler instance to a companion: there's a single test method, so only a
-  // single instance created.
   val compiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:inline-global")
   import compiler.genBCode.bTypes._
 
@@ -72,13 +70,7 @@ class CallGraphTest {
 
     // Get the ClassNodes from the code repo (don't use the unparsed ClassNodes returned by compile).
     // The callGraph.callsites map is indexed by instructions of those ClassNodes.
-    val clss @ List(cCls, cMod, dCls, testCls) = compile(code).map(c => byteCodeRepository.classNode(c.name))
-    clss.foreach(cls => {
-      // add classes to the call graph manually, the compiler doesn't do it yet. the next commit removes these lines.
-      cls.methods.asScala foreach BytecodeUtils.computeMaxLocalsMaxStack
-      callGraph.addClass(cls)
-    })
-
+    val List(cCls, cMod, dCls, testCls) = compile(code).map(c => byteCodeRepository.classNode(c.name))
 
     val List(cf1, cf2, cf3, cf4, cf5, cf6, cf7) = cCls.methods.iterator.asScala.filter(_.name.startsWith("f")).toList.sortBy(_.name)
     val List(df1, df3) = dCls.methods.iterator.asScala.filter(_.name.startsWith("f")).toList.sortBy(_.name)
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 6cd89e1323..819252841e 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
@@ -23,7 +23,7 @@ import scala.collection.convert.decorateAsScala._
 import scala.tools.testing.ClearAfterClass
 
 object InlinerTest extends ClearAfterClass.Clearable {
-  var compiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:project")
+  var compiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:classpath")
 
   // allows inspecting the caches after a compilation run
   def notPerRun: List[Clearable] = List(compiler.genBCode.bTypes.classBTypeFromInternalName, compiler.genBCode.bTypes.byteCodeRepository.classes, compiler.genBCode.bTypes.callGraph.callsites)
@@ -44,6 +44,15 @@ class InlinerTest extends ClearAfterClass {
     compileClasses(compiler)(code)
   }
 
+  def checkCallsite(callsite: callGraph.Callsite, callee: MethodNode) = {
+    assert(callsite.callsiteMethod.instructions.contains(callsite.callsiteInstruction), instructionsFromMethod(callsite.callsiteMethod))
+
+    val callsiteClassNode = byteCodeRepository.classNode(callsite.callsiteClass.internalName)
+    assert(callsiteClassNode.methods.contains(callsite.callsiteMethod), callsiteClassNode.methods.asScala.map(_.name).toList)
+
+    assert(callsite.callee.get.callee == callee, callsite.callee.get.callee.name)
+  }
+
   // inline first invocation of f into g in class C
   def inlineTest(code: String, mod: ClassNode => Unit = _ => ()): (MethodNode, Option[String]) = {
     val List(cls) = compile(code)
@@ -205,4 +214,204 @@ class InlinerTest extends ClearAfterClass {
 
     assert(r.get contains "would cause an IllegalAccessError", r)
   }
+
+  @Test
+  def inlineSimpleAtInline(): Unit = {
+    val code =
+      """class C {
+        |  @inline final def f = 0
+        |  final def g = 1
+        |
+        |  def test = f + g
+        |}
+      """.stripMargin
+    val List(cCls) = compile(code)
+    val instructions = instructionsFromMethod(cCls.methods.asScala.find(_.name == "test").get)
+    assert(instructions.contains(Op(ICONST_0)), instructions mkString "\n")
+    assert(!instructions.contains(Op(ICONST_1)), instructions)
+  }
+
+  @Test
+  def cyclicInline(): Unit = {
+    val code =
+      """class C {
+        |  @inline final def f: Int = g
+        |  @inline final def g: Int = f
+        |}
+      """.stripMargin
+    val List(c) = compile(code)
+    val methods @ List(_, g) = c.methods.asScala.filter(_.name.length == 1).toList
+    val List(fIns, gIns) = methods.map(instructionsFromMethod(_).dropNonOp)
+    val invokeG = Invoke(INVOKEVIRTUAL, "C", "g", "()I", false)
+    assert(fIns contains invokeG, fIns) // no inlining into f, that request is elided
+    assert(gIns contains invokeG, gIns) // f is inlined into g, g invokes itself recursively
+
+    assert(callGraph.callsites.size == 3, callGraph.callsites)
+    for (callsite <- callGraph.callsites.values if methods.contains(callsite.callsiteMethod)) {
+      checkCallsite(callsite, g)
+    }
+  }
+
+  @Test
+  def cyclicInline2(): Unit = {
+    val code =
+      """class C {
+        |  @inline final def h: Int = f
+        |  @inline final def f: Int = g + g
+        |  @inline final def g: Int = h
+        |}
+      """.stripMargin
+    val List(c) = compile(code)
+    val methods @ List(f, g, h) = c.methods.asScala.filter(_.name.length == 1).sortBy(_.name).toList
+    val List(fIns, gIns, hIns) = methods.map(instructionsFromMethod(_).dropNonOp)
+    val invokeG = Invoke(INVOKEVIRTUAL, "C", "g", "()I", false)
+    assert(fIns.count(_ == invokeG) == 2, fIns) // no inlining into f, these requests are elided
+    assert(gIns.count(_ == invokeG) == 2, gIns)
+    assert(hIns.count(_ == invokeG) == 2, hIns)
+
+    assert(callGraph.callsites.size == 7, callGraph.callsites)
+    for (callsite <- callGraph.callsites.values if methods.contains(callsite.callsiteMethod)) {
+      checkCallsite(callsite, g)
+    }
+  }
+
+  @Test
+  def arraycopy(): Unit = {
+    // also tests inlining of a void-returning method (no return value on the stack)
+    val code =
+      """class C {
+        |  def f(src: AnyRef, srcPos: Int, dest: AnyRef, destPos: Int, length: Int): Unit = {
+        |    compat.Platform.arraycopy(src, srcPos, dest, destPos, length)
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compile(code)
+    val ins = instructionsFromMethod(c.methods.asScala.find(_.name == "f").get)
+    val invokeSysArraycopy = Invoke(INVOKESTATIC, "java/lang/System", "arraycopy", "(Ljava/lang/Object;ILjava/lang/Object;II)V", false)
+    assert(ins contains invokeSysArraycopy, ins mkString "\n")
+  }
+
+  @Test
+  def arrayMemberMethod(): Unit = {
+    // This used to crash when building the call graph. The `owner` field of the MethodInsnNode
+    // for the invocation of `clone` is not an internal name, but a full array descriptor
+    // [Ljava.lang.Object; - the documentation in the ASM library didn't mention that possibility.
+    val code =
+      """class C {
+        |  def f(a: Array[Object]) = {
+        |    a.clone()
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compile(code)
+    assert(callGraph.callsites.values exists (_.callsiteInstruction.name == "clone"))
+  }
+
+  @Test
+  def atInlineInTraitDoesNotCrash(): Unit = {
+    val code =
+      """trait T {
+        |  @inline final def f = 0
+        |}
+        |class C {
+        |  def g(t: T) = t.f
+        |}
+      """.stripMargin
+    val List(c, t, tClass) = compile(code)
+    val ins = instructionsFromMethod(c.methods.asScala.find(_.name == "g").get)
+    val invokeF = Invoke(INVOKEINTERFACE, "T", "f", "()I", true)
+    // no inlining yet
+    assert(ins contains invokeF, ins mkString "\n")
+  }
+
+  @Test
+  def inlinePrivateMethodWithHandler(): Unit = {
+    val code =
+      """class C {
+        |  @inline private def f = try { 0 } catch { case _: Throwable => 1 }
+        |  def g = f
+        |}
+      """.stripMargin
+    val List(c) = compile(code)
+    val ins = instructionsFromMethod(c.methods.asScala.find(_.name == "g").get)
+    println(ins)
+    // no more invoke, f is inlined
+    assert(ins.count(_.isInstanceOf[Invoke]) == 0, ins mkString "\n")
+  }
+
+  @Test
+  def inlineStaticCall(): Unit = {
+    val code =
+      """class C {
+        |  def f = Integer.lowestOneBit(103)
+        |}
+      """.stripMargin
+
+    val List(c) = compile(code)
+    val f = c.methods.asScala.find(_.name == "f").get
+    val callsiteIns = f.instructions.iterator().asScala.collect({ case c: MethodInsnNode => c }).next()
+    val clsBType = classBTypeFromParsedClassfile(c.name)
+    val analyzer = new BasicAnalyzer(f, clsBType.internalName)
+
+    val integerClassBType = classBTypeFromInternalName("java/lang/Integer")
+    val lowestOneBitMethod = byteCodeRepository.methodNode(integerClassBType.internalName, "lowestOneBit", "(I)I").get._1
+
+    val r = inliner.inline(
+      callsiteIns,
+      analyzer.frameAt(callsiteIns).getStackSize,
+      f,
+      clsBType,
+      lowestOneBitMethod,
+      integerClassBType,
+      receiverKnownNotNull = false,
+      keepLineNumbers = false)
+
+    assert(r.isEmpty, r)
+    val ins = instructionsFromMethod(f)
+
+    // no invocations, lowestOneBit is inlined
+    assert(ins.count(_.isInstanceOf[Invoke]) == 0, ins mkString "\n")
+
+    // no null check when inlining a static method
+    ins foreach {
+      case Jump(IFNONNULL, _) => assert(false, ins mkString "\n")
+      case _ =>
+    }
+  }
+
+  @Test
+  def maxLocalsMaxStackAfterInline(): Unit = {
+    val code =
+      """class C {
+        |  @inline final def f1(x: Int): Int = {
+        |    val a = x + 1
+        |    math.max(a, math.min(10, a - 1))
+        |  }
+        |
+        |  @inline final def f2(x: Int): Unit = {
+        |    val a = x + 1
+        |    println(math.max(a, 10))
+        |  }
+        |
+        |  def g1 = println(f1(32))
+        |  def g2 = println(f2(32))
+        |}
+      """.stripMargin
+
+    val List(c) = compile(code)
+    val ms @ List(f1, f2, g1, g2) = c.methods.asScala.filter(_.name.length == 2).toList
+
+    // stack height at callsite of f1 is 1, so max of g1 after inlining is max of f1 + 1
+    assert(g1.maxStack == 7 && f1.maxStack == 6, s"${g1.maxStack} - ${f1.maxStack}")
+
+    // locals in f1: this, x, a
+    // locals in g1 after inlining: this, this-of-f1, x, a, return value
+    assert(g1.maxLocals == 5 && f1.maxLocals == 3, s"${g1.maxLocals} - ${f1.maxLocals}")
+
+    // like maxStack in g1 / f1
+    assert(g2.maxStack == 5 && f2.maxStack == 4, s"${g2.maxStack} - ${f2.maxStack}")
+
+    // like maxLocals for g1 / f1, but no return value
+    assert(g2.maxLocals == 4 && f2.maxLocals == 3, s"${g2.maxLocals} - ${f2.maxLocals}")
+  }
 }