Build a call graph for inlining decisions

Inlining decisions will be taken by analyzing the ASM bytecode. This
commit adds tools to build a call graph representation that can be
used for these decisions.

The call graph is currently built by considering method descriptors of
callsite instructions. It will become more precise by using data flow
analyses.

3 files changed, 157 insertions, 6 deletions

diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/BTypesFromClassfileTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/BTypesFromClassfileTest.scala
index 4481fcd6be..65c96226ff 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/BTypesFromClassfileTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/BTypesFromClassfileTest.scala
@@ -59,6 +59,15 @@ class BTypesFromClassfileTest {
       else (fromSym.flags | ACC_PRIVATE | ACC_PUBLIC) == (fromClassfile.flags | ACC_PRIVATE | ACC_PUBLIC)
     }, s"class flags differ\n$fromSym\n$fromClassfile")
 
+    // when parsing from classfile, the inline infos are obtained through the classSymbol, which
+    // is searched based on the classfile name. this lookup can fail.
+    assert(fromSym.inlineInfos.size == fromClassfile.inlineInfos.size || fromClassfile.inlineInfos.isEmpty,
+      s"wrong # of inline infos:\n${fromSym.inlineInfos.keys.toList.sorted}\n${fromClassfile.inlineInfos.keys.toList.sorted}")
+    fromClassfile.inlineInfos foreach {
+      case (signature, inlineInfo) =>
+        assert(fromSym.inlineInfos(signature) == inlineInfo, s"inline infos differ for $signature:\n$inlineInfo\n${fromClassfile.inlineInfos(signature)}")
+    }
+
     val chk1 = sameBTypes(fromSym.superClass, fromClassfile.superClass, checked)
 
     val chk2 = sameBTypes(fromSym.interfaces, fromClassfile.interfaces, chk1)
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/CallGraphTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/CallGraphTest.scala
new file mode 100644
index 0000000000..400fb6b00a
--- /dev/null
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/CallGraphTest.scala
@@ -0,0 +1,146 @@
+package scala.tools.nsc
+package backend.jvm
+package opt
+
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.junit.Test
+import scala.collection.generic.Clearable
+import scala.tools.asm.Opcodes._
+import org.junit.Assert._
+
+import scala.tools.asm.tree._
+import scala.tools.asm.tree.analysis._
+import scala.tools.nsc.backend.jvm.opt.BytecodeUtils.BasicAnalyzer
+import scala.tools.testing.AssertUtil._
+
+import CodeGenTools._
+import scala.tools.partest.ASMConverters
+import ASMConverters._
+import AsmUtils._
+
+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._
+
+  // allows inspecting the caches after a compilation run
+  val notPerRun: List[Clearable] = List(classBTypeFromInternalName, byteCodeRepository.classes, callGraph.callsites)
+  notPerRun foreach compiler.perRunCaches.unrecordCache
+
+  def compile(code: String): List[ClassNode] = {
+    notPerRun.foreach(_.clear())
+    compileClasses(compiler)(code)
+  }
+
+  def callsInMethod(methodNode: MethodNode): List[MethodInsnNode] = methodNode.instructions.iterator.asScala.collect({
+    case call: MethodInsnNode => call
+  }).toList
+
+  @Test
+  def callGraphStructure(): Unit = {
+    val code =
+      """class C {
+        |  // try-catch prevents inlining - we want to analyze the callsite
+        |  def f1                   = try { 0 } catch { case _: Throwable => 1 }
+        |  final def f2             = try { 0 } catch { case _: Throwable => 1 }
+        |
+        |  @inline def f3           = try { 0 } catch { case _: Throwable => 1 }
+        |  @inline final def f4     = try { 0 } catch { case _: Throwable => 1 }
+        |
+        |  @noinline def f5         = try { 0 } catch { case _: Throwable => 1 }
+        |  @noinline final def f6   = try { 0 } catch { case _: Throwable => 1 }
+        |
+        |  @inline @noinline def f7 = try { 0 } catch { case _: Throwable => 1 }
+        |}
+        |class D extends C {
+        |  @inline override def f1  = try { 0 } catch { case _: Throwable => 1 }
+        |  override final def f3    = try { 0 } catch { case _: Throwable => 1 }
+        |}
+        |object C {
+        |  def g1                   = try { 0 } catch { case _: Throwable => 1 }
+        |}
+        |class Test {
+        |  def t1(c: C) = c.f1 + c.f2 + c.f3 + c.f4 + c.f5 + c.f6 + c.f7 + C.g1
+        |  def t2(d: D) = d.f1 + d.f2 + d.f3 + d.f4 + d.f5 + d.f6 + d.f7 + C.g1
+        |}
+      """.stripMargin
+
+    // 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(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)
+    val g1 = cMod.methods.iterator.asScala.find(_.name == "g1").get
+    val List(t1, t2) = testCls.methods.iterator.asScala.filter(_.name.startsWith("t")).toList.sortBy(_.name)
+
+    val List(cf1Call, cf2Call, cf3Call, cf4Call, cf5Call, cf6Call, cf7Call, cg1Call) = callsInMethod(t1)
+    val List(df1Call, df2Call, df3Call, df4Call, df5Call, df6Call, df7Call, dg1Call) = callsInMethod(t2)
+
+    def checkCallsite(callsite: callGraph.Callsite,
+                      call: MethodInsnNode, callsiteMethod: MethodNode, target: MethodNode, calleeDeclClass: ClassBType,
+                      safeToInline: Boolean, atInline: Boolean, atNoInline: Boolean) = try {
+      assert(callsite.callsiteInstruction == call)
+      assert(callsite.callsiteMethod == callsiteMethod)
+      val callee = callsite.callee.get
+      assert(callee.callee == target)
+      assert(callee.calleeDeclarationClass == calleeDeclClass)
+      assert(callee.safeToInline == safeToInline)
+      assert(callee.annotatedInline.get == atInline)
+      assert(callee.annotatedNoInline.get == atNoInline)
+
+      assert(callsite.argInfos == List()) // not defined yet
+    } catch {
+      case e: Throwable => println(callsite); throw e
+    }
+
+    val cClassBType  = classBTypeFromClassNode(cCls)
+    val cMClassBType = classBTypeFromClassNode(cMod)
+    val dClassBType  = classBTypeFromClassNode(dCls)
+
+    checkCallsite(callGraph.callsites(cf1Call),
+      cf1Call, t1, cf1, cClassBType, false, false, false)
+    checkCallsite(callGraph.callsites(cf2Call),
+      cf2Call, t1, cf2, cClassBType, true, false, false)
+    checkCallsite(callGraph.callsites(cf3Call),
+      cf3Call, t1, cf3, cClassBType, false, true, false)
+    checkCallsite(callGraph.callsites(cf4Call),
+      cf4Call, t1, cf4, cClassBType, true, true, false)
+    checkCallsite(callGraph.callsites(cf5Call),
+      cf5Call, t1, cf5, cClassBType, false, false, true)
+    checkCallsite(callGraph.callsites(cf6Call),
+      cf6Call, t1, cf6, cClassBType, true, false, true)
+    checkCallsite(callGraph.callsites(cf7Call),
+      cf7Call, t1, cf7, cClassBType, false, true, true)
+    checkCallsite(callGraph.callsites(cg1Call),
+      cg1Call, t1, g1, cMClassBType, true, false, false)
+
+    checkCallsite(callGraph.callsites(df1Call),
+      df1Call, t2, df1, dClassBType, false, true, false)
+    checkCallsite(callGraph.callsites(df2Call),
+      df2Call, t2, cf2, cClassBType, true, false, false)
+    checkCallsite(callGraph.callsites(df3Call),
+      df3Call, t2, df3, dClassBType, true, false, false)
+    checkCallsite(callGraph.callsites(df4Call),
+      df4Call, t2, cf4, cClassBType, true, true, false)
+    checkCallsite(callGraph.callsites(df5Call),
+      df5Call, t2, cf5, cClassBType, false, false, true)
+    checkCallsite(callGraph.callsites(df6Call),
+      df6Call, t2, cf6, cClassBType, true, false, true)
+    checkCallsite(callGraph.callsites(df7Call),
+      df7Call, t2, cf7, cClassBType, false, true, true)
+    checkCallsite(callGraph.callsites(dg1Call),
+      dg1Call, t2, g1, cMClassBType, true, false, false)
+  }
+}
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 2ec6853f13..6cd89e1323 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
@@ -26,7 +26,7 @@ object InlinerTest extends ClearAfterClass.Clearable {
   var compiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:project")
 
   // allows inspecting the caches after a compilation run
-  def notPerRun: List[Clearable] = List(compiler.genBCode.bTypes.classBTypeFromInternalName, compiler.genBCode.bTypes.byteCodeRepository.classes)
+  def notPerRun: List[Clearable] = List(compiler.genBCode.bTypes.classBTypeFromInternalName, compiler.genBCode.bTypes.byteCodeRepository.classes, compiler.genBCode.bTypes.callGraph.callsites)
   notPerRun foreach compiler.perRunCaches.unrecordCache
 
   def clear(): Unit = { compiler = null }
@@ -41,11 +41,7 @@ class InlinerTest extends ClearAfterClass {
 
   def compile(code: String): List[ClassNode] = {
     InlinerTest.notPerRun.foreach(_.clear())
-    val cls = compileClasses(compiler)(code)
-    // the compiler doesn't add classes being compiled to the code repo yet, so we do it manually.
-    // this line is removed in the next commit.
-    for (c <- cls) byteCodeRepository.classes(c.name) = (c, ByteCodeRepository.Classfile)
-    cls
+    compileClasses(compiler)(code)
   }
 
   // inline first invocation of f into g in class C