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.

9 files changed, 396 insertions, 131 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala
index e366bbabb8..246d565987 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeHelpers.scala
@@ -332,125 +332,42 @@ abstract class BCodeHelpers extends BCodeIdiomatic with BytecodeWriters {
       getClassBTypeAndRegisterInnerClass(classSym).internalName
     }
 
-    private def assertClassNotArray(sym: Symbol): Unit = {
-      assert(sym.isClass, sym)
-      assert(sym != definitions.ArrayClass || isCompilingArray, sym)
-    }
-
-    private def assertClassNotArrayNotPrimitive(sym: Symbol): Unit = {
-      assertClassNotArray(sym)
-      assert(!primitiveTypeMap.contains(sym) || isCompilingPrimitive, sym)
-    }
-
     /**
      * The ClassBType for a class symbol. If the class is nested, the ClassBType is added to the
      * innerClassBufferASM.
      *
-     * The class symbol scala.Nothing is mapped to the class scala.runtime.Nothing$. Similarly,
-     * scala.Null is mapped to scala.runtime.Null$. This is because there exist no class files
-     * for the Nothing / Null. If used for example as a parameter type, we use the runtime classes
-     * in the classfile method signature.
-     *
-     * Note that the referenced class symbol may be an implementation class. For example when
-     * compiling a mixed-in method that forwards to the static method in the implementation class,
-     * the class descriptor of the receiver (the implementation class) is obtained by creating the
-     * ClassBType.
+     * TODO: clean up the way we track referenced inner classes.
+     * doing it during code generation is not correct when the optimizer changes the code.
      */
     final def getClassBTypeAndRegisterInnerClass(sym: Symbol): ClassBType = {
-      assertClassNotArrayNotPrimitive(sym)
-
-      if (sym == definitions.NothingClass) RT_NOTHING
-      else if (sym == definitions.NullClass) RT_NULL
-      else {
-       val r = classBTypeFromSymbol(sym)
-       if (r.isNestedClass) innerClassBufferASM += r
-       r
-      }
+      val r = classBTypeFromSymbol(sym)
+      if (r.isNestedClass) innerClassBufferASM += r
+      r
     }
 
     /**
-     * This method returns the BType for a type reference, for example a parameter type.
-     *
-     * If the result is a ClassBType for a nested class, it is added to the innerClassBufferASM.
-     *
-     * If `t` references a class, toTypeKind ensures that the class is not an implementation class.
-     * See also comment on getClassBTypeAndRegisterInnerClass, which is invoked for implementation
-     * classes.
+     * The BType for a type reference. If the result is a ClassBType for a nested class, it is added
+     * to the innerClassBufferASM.
+     * TODO: clean up the way we track referenced inner classes.
      */
-    final def toTypeKind(t: Type): BType = {
-      import definitions.ArrayClass
-
-      /**
-       * Primitive types are represented as TypeRefs to the class symbol of, for example, scala.Int.
-       * The `primitiveTypeMap` maps those class symbols to the corresponding PrimitiveBType.
-       */
-      def primitiveOrClassToBType(sym: Symbol): BType = {
-        assertClassNotArray(sym)
-        assert(!sym.isImplClass, sym)
-        primitiveTypeMap.getOrElse(sym, getClassBTypeAndRegisterInnerClass(sym))
-      }
-
-      /**
-       * When compiling Array.scala, the type parameter T is not erased and shows up in method
-       * signatures, e.g. `def apply(i: Int): T`. A TyperRef to T is replaced by ObjectReference.
-       */
-      def nonClassTypeRefToBType(sym: Symbol): ClassBType = {
-        assert(sym.isType && isCompilingArray, sym)
-        ObjectReference
-      }
-
-      t.dealiasWiden match {
-        case TypeRef(_, ArrayClass, List(arg))  => ArrayBType(toTypeKind(arg))  // Array type such as Array[Int] (kept by erasure)
-        case TypeRef(_, sym, _) if !sym.isClass => nonClassTypeRefToBType(sym)  // See comment on nonClassTypeRefToBType
-        case TypeRef(_, sym, _)                 => primitiveOrClassToBType(sym) // Common reference to a type such as scala.Int or java.lang.String
-        case ClassInfoType(_, _, sym)           => primitiveOrClassToBType(sym) // We get here, for example, for genLoadModule, which invokes toTypeKind(moduleClassSymbol.info)
-
-        /* AnnotatedType should (probably) be eliminated by erasure. However we know it happens for
-         * meta-annotated annotations (@(ann @getter) val x = 0), so we don't emit a warning.
-         * The type in the AnnotationInfo is an AnnotatedTpe. Tested in jvm/annotations.scala.
-         */
-        case a @ AnnotatedType(_, t) =>
-          debuglog(s"typeKind of annotated type $a")
-          toTypeKind(t)
-
-        /* ExistentialType should (probably) be eliminated by erasure. We know they get here for
-         * classOf constants:
-         *   class C[T]
-         *   class T { final val k = classOf[C[_]] }
-         */
-        case e @ ExistentialType(_, t) =>
-          debuglog(s"typeKind of existential type $e")
-          toTypeKind(t)
-
-        /* The cases below should probably never occur. They are kept for now to avoid introducing
-         * new compiler crashes, but we added a warning. The compiler / library bootstrap and the
-         * test suite don't produce any warning.
-         */
-
-        case tp =>
-          currentUnit.warning(tp.typeSymbol.pos,
-            s"an unexpected type representation reached the compiler backend while compiling $currentUnit: $tp. " +
-            "If possible, please file a bug on issues.scala-lang.org.")
-
-          tp match {
-            case ThisType(ArrayClass)               => ObjectReference // was introduced in 9b17332f11 to fix SI-999, but this code is not reached in its test, or any other test
-            case ThisType(sym)                      => getClassBTypeAndRegisterInnerClass(sym)
-            case SingleType(_, sym)                 => primitiveOrClassToBType(sym)
-            case ConstantType(_)                    => toTypeKind(t.underlying)
-            case RefinedType(parents, _)            => parents.map(toTypeKind(_).asClassBType).reduceLeft((a, b) => a.jvmWiseLUB(b))
-          }
-      }
+    final def toTypeKind(t: Type): BType = typeToBType(t) match {
+      case c: ClassBType if c.isNestedClass =>
+        innerClassBufferASM += c
+        c
+      case r => r
     }
 
-    /*
-     * must-single-thread
+    /**
+     * Class components that are nested classes are added to the innerClassBufferASM.
+     * TODO: clean up the way we track referenced inner classes.
      */
     final def asmMethodType(msym: Symbol): MethodBType = {
-      assert(msym.isMethod, s"not a method-symbol: $msym")
-      val resT: BType =
-        if (msym.isClassConstructor || msym.isConstructor) UNIT
-        else toTypeKind(msym.tpe.resultType)
-      MethodBType(msym.tpe.paramTypes map toTypeKind, resT)
+      val r = methodBTypeFromSymbol(msym)
+      (r.returnType :: r.argumentTypes) foreach {
+        case c: ClassBType if c.isNestedClass => innerClassBufferASM += c
+        case _ =>
+      }
+      r
     }
 
     /**
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala
index 48df4e1121..b4de5cf52f 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala
@@ -10,6 +10,7 @@ package backend
 package jvm
 
 import scala.collection.{ mutable, immutable }
+import scala.tools.nsc.backend.jvm.opt.ByteCodeRepository
 import scala.tools.nsc.symtab._
 import scala.annotation.switch
 
@@ -126,9 +127,12 @@ abstract class BCodeSkelBuilder extends BCodeHelpers {
       if (AsmUtils.traceClassEnabled && cnode.name.contains(AsmUtils.traceClassPattern))
         AsmUtils.traceClass(cnode)
 
-      cnode.innerClasses
-      assert(cd.symbol == claszSymbol, "Someone messed up BCodePhase.claszSymbol during genPlainClass().")
+      if (settings.YoptInlinerEnabled) {
+        // The inliner needs to find all classes in the code repo, also those being compiled
+        byteCodeRepository.classes(cnode.name) = (cnode, ByteCodeRepository.CompilationUnit)
+      }
 
+      assert(cd.symbol == claszSymbol, "Someone messed up BCodePhase.claszSymbol during genPlainClass().")
     } // end of method genPlainClass()
 
     /*
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
index fe4c4794a9..c93496fb49 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
@@ -10,7 +10,8 @@ import scala.annotation.switch
 import scala.tools.asm
 import asm.Opcodes
 import scala.tools.asm.tree.{InnerClassNode, ClassNode}
-import opt.{ByteCodeRepository, Inliner}
+import scala.tools.nsc.backend.jvm.BTypes.{MethodInlineInfo, InlineInfo}
+import scala.tools.nsc.backend.jvm.opt.{CallGraph, ByteCodeRepository, Inliner}
 import OptimizerReporting._
 import scala.collection.convert.decorateAsScala._
 
@@ -38,9 +39,14 @@ abstract class BTypes {
 
   val inliner: Inliner[this.type]
 
+  val callGraph: CallGraph[this.type]
+
   // Allows to define per-run caches here and in the CallGraph component, which don't have a global
   def recordPerRunCache[T <: collection.generic.Clearable](cache: T): T
 
+  // When building the call graph, we need to know if global inlining is allowed (the component doesn't have a global)
+  def inlineGlobalEnabled: Boolean
+
   /**
    * A map from internal names to ClassBTypes. Every ClassBType is added to this map on its
    * construction.
@@ -55,6 +61,23 @@ abstract class BTypes {
   val classBTypeFromInternalName: collection.concurrent.Map[InternalName, ClassBType] = recordPerRunCache(collection.concurrent.TrieMap.empty[InternalName, ClassBType])
 
   /**
+   * Build the [[InlineInfo]] for the methods of a class, given its internal name.
+   *
+   * The InlineInfo is part of the ClassBType's [[ClassInfo]]. Note that there are two ways to build
+   * a ClassBType: from a class symbol (methods in [[BTypesFromSymbols]]) or from a [[ClassNode]].
+   * The InlineInfo however contains information that can only be retrieved from the symbol of
+   * the class (e.g., is a method annotated @inline).
+   *
+   * This method (implemented in [[BTypesFromSymbols]]) looks up the class symbol in the symbol
+   * table, using the classfile name of the class.
+   *
+   * The method tries to undo some of the name mangling, but the lookup does not succeed for all
+   * classes. In case it fails, the resulting ClassBType will simply not have an InlineInfo, and
+   * we won't be able to inline its methods.
+   */
+  def inlineInfosFromSymbolLookup(internalName: InternalName): Map[String, MethodInlineInfo]
+
+  /**
    * Obtain the BType for a type descriptor or internal name. For class descriptors, the ClassBType
    * is constructed by parsing the corresponding classfile.
    * 
@@ -145,7 +168,8 @@ abstract class BTypes {
         val staticFlag = (innerEntry.access & Opcodes.ACC_STATIC) != 0
         NestedInfo(enclosingClass, Option(innerEntry.outerName), Option(innerEntry.innerName), staticFlag)
     }
-    classBType.info = ClassInfo(superClass, interfaces, flags, nestedClasses, nestedInfo)
+
+    classBType.info = ClassInfo(superClass, interfaces, flags, nestedClasses, nestedInfo, inlineInfosFromSymbolLookup(classBType.internalName))
     classBType
   }
 
@@ -901,9 +925,13 @@ abstract class BTypes {
    * @param nestedClasses Classes nested in this class. Those need to be added to the
    *                      InnerClass table, see the InnerClass spec summary above.
    * @param nestedInfo    If this describes a nested class, information for the InnerClass table.
+   * @param inlineInfos   The [[InlineInfo]]s for the methods declared in this class. The map is
+   *                      indexed by the string s"$name$descriptor" (to disambiguate overloads).
+   *                      Entries may be missing, see comment on [[inlineInfosFromSymbolLookup]].
    */
   final case class ClassInfo(superClass: Option[ClassBType], interfaces: List[ClassBType], flags: Int,
-                             nestedClasses: List[ClassBType], nestedInfo: Option[NestedInfo])
+                             nestedClasses: List[ClassBType], nestedInfo: Option[NestedInfo],
+                             inlineInfos: Map[String, MethodInlineInfo])
 
   /**
    * Information required to add a class to an InnerClass table.
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
index 117b377622..9ed7b3174b 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
@@ -9,8 +9,8 @@ package backend.jvm
 import scala.tools.asm
 import scala.tools.asm.tree.ClassNode
 import scala.tools.nsc.backend.jvm.opt.ByteCodeRepository.Source
-import scala.tools.nsc.backend.jvm.opt.{Inliner, ByteCodeRepository}
-import BTypes.InternalName
+import scala.tools.nsc.backend.jvm.opt.{CallGraph, Inliner, ByteCodeRepository}
+import scala.tools.nsc.backend.jvm.BTypes.{MethodInlineInfo, InlineInfo, InternalName}
 
 /**
  * This class mainly contains the method classBTypeFromSymbol, which extracts the necessary
@@ -40,12 +40,58 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes {
 
   val inliner: Inliner[this.type] = new Inliner(this)
 
+  val callGraph: CallGraph[this.type] = new CallGraph(this)
+
+  /**
+   * See doc in [[BTypes.inlineInfosFromSymbolLookup]].
+   * TODO: once the optimzier uses parallelism, lock before symbol table accesses
+   */
+  def inlineInfosFromSymbolLookup(internalName: InternalName): Map[String, MethodInlineInfo] = {
+    val name = internalName.replace('/', '.')
+
+    // TODO: de-mangle more class names
+
+    def inEmptyPackage = name.indexOf('.') == -1
+    def isModule       = name.endsWith("$")
+    def isTopLevel     = {
+      // TODO: this is conservative, there's also $'s introduced by name mangling, e.g., $colon$colon
+      // for this, use NameTransformer.decode
+      if (isModule) name.indexOf('$') == (name.length - 1)
+      else name.indexOf('$') == -1
+    }
+
+    val lookupName = {
+      if (isModule) newTermName(name.substring(0, name.length - 1))
+      else newTypeName(name)
+    }
+
+    // for now we only try classes that look like top-level
+    val classSym = if (!isTopLevel) NoSymbol else {
+      val member = {
+        if (inEmptyPackage) {
+          // rootMirror.getClassIfDefined fails for classes / modules in the empty package.
+          // maybe that should be fixed.
+          rootMirror.EmptyPackageClass.info.member(lookupName)
+        } else {
+          if (isModule) rootMirror.getModuleIfDefined(lookupName)
+          else rootMirror.getClassIfDefined(lookupName)
+        }
+      }
+      if (isModule) member.moduleClass else member
+    }
+
+    if (classSym == NoSymbol) Map.empty
+    else buildInlineInfos(classSym)
+  }
+
   final def initializeCoreBTypes(): Unit = {
     coreBTypes.setBTypes(new CoreBTypes[this.type](this))
   }
 
   def recordPerRunCache[T <: collection.generic.Clearable](cache: T): T = perRunCaches.recordCache(cache)
 
+  def inlineGlobalEnabled: Boolean = settings.YoptInlineGlobal
+
   // helpers that need access to global.
   // TODO @lry create a separate component, they don't belong to BTypesFromSymbols
 
@@ -78,22 +124,125 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes {
   // end helpers
 
   /**
-   * The ClassBType for a class symbol `sym`.
+   * The ClassBType for a class symbol `classSym`.
+   *
+   * The class symbol scala.Nothing is mapped to the class scala.runtime.Nothing$. Similarly,
+   * scala.Null is mapped to scala.runtime.Null$. This is because there exist no class files
+   * for the Nothing / Null. If used for example as a parameter type, we use the runtime classes
+   * in the classfile method signature.
+   *
+   * Note that the referenced class symbol may be an implementation class. For example when
+   * compiling a mixed-in method that forwards to the static method in the implementation class,
+   * the class descriptor of the receiver (the implementation class) is obtained by creating the
+   * ClassBType.
    */
   final def classBTypeFromSymbol(classSym: Symbol): ClassBType = {
     assert(classSym != NoSymbol, "Cannot create ClassBType from NoSymbol")
     assert(classSym.isClass, s"Cannot create ClassBType from non-class symbol $classSym")
-    assert(
-      (!primitiveTypeMap.contains(classSym) || isCompilingPrimitive) &&
-      (classSym != NothingClass && classSym != NullClass),
-      s"Cannot create ClassBType for special class symbol ${classSym.fullName}")
+    assertClassNotArrayNotPrimitive(classSym)
+    assert(!primitiveTypeMap.contains(classSym) || isCompilingPrimitive, s"Cannot create ClassBType for primitive class symbol $classSym")
+    if (classSym == NothingClass) RT_NOTHING
+    else if (classSym == NullClass) RT_NULL
+    else {
+      val internalName = classSym.javaBinaryName.toString
+      classBTypeFromInternalName.getOrElse(internalName, {
+        // The new ClassBType is added to the map in its constructor, before we set its info. This
+        // allows initializing cyclic dependencies, see the comment on variable ClassBType._info.
+        setClassInfo(classSym, ClassBType(internalName))
+      })
+    }
+  }
 
-    val internalName = classSym.javaBinaryName.toString
-    classBTypeFromInternalName.getOrElse(internalName, {
-      // The new ClassBType is added to the map in its constructor, before we set its info. This
-      // allows initializing cyclic dependencies, see the comment on variable ClassBType._info.
-      setClassInfo(classSym, ClassBType(internalName))
-    })
+  /**
+   * Builds a [[MethodBType]] for a method symbol.
+   */
+  final def methodBTypeFromSymbol(methodSymbol: Symbol): MethodBType = {
+    assert(methodSymbol.isMethod, s"not a method-symbol: $methodSymbol")
+    val resultType: BType =
+      if (methodSymbol.isClassConstructor || methodSymbol.isConstructor) UNIT
+      else typeToBType(methodSymbol.tpe.resultType)
+    MethodBType(methodSymbol.tpe.paramTypes map typeToBType, resultType)
+  }
+
+  /**
+   * This method returns the BType for a type reference, for example a parameter type.
+   *
+   * If `t` references a class, typeToBType ensures that the class is not an implementation class.
+   * See also comment on classBTypeFromSymbol, which is invoked for implementation classes.
+   */
+  final def typeToBType(t: Type): BType = {
+    import definitions.ArrayClass
+
+    /**
+     * Primitive types are represented as TypeRefs to the class symbol of, for example, scala.Int.
+     * The `primitiveTypeMap` maps those class symbols to the corresponding PrimitiveBType.
+     */
+    def primitiveOrClassToBType(sym: Symbol): BType = {
+      assertClassNotArray(sym)
+      assert(!sym.isImplClass, sym)
+      primitiveTypeMap.getOrElse(sym, classBTypeFromSymbol(sym))
+    }
+
+    /**
+     * When compiling Array.scala, the type parameter T is not erased and shows up in method
+     * signatures, e.g. `def apply(i: Int): T`. A TyperRef to T is replaced by ObjectReference.
+     */
+    def nonClassTypeRefToBType(sym: Symbol): ClassBType = {
+      assert(sym.isType && isCompilingArray, sym)
+      ObjectReference
+    }
+
+    t.dealiasWiden match {
+      case TypeRef(_, ArrayClass, List(arg))  => ArrayBType(typeToBType(arg)) // Array type such as Array[Int] (kept by erasure)
+      case TypeRef(_, sym, _) if !sym.isClass => nonClassTypeRefToBType(sym)  // See comment on nonClassTypeRefToBType
+      case TypeRef(_, sym, _)                 => primitiveOrClassToBType(sym) // Common reference to a type such as scala.Int or java.lang.String
+      case ClassInfoType(_, _, sym)           => primitiveOrClassToBType(sym) // We get here, for example, for genLoadModule, which invokes typeToBType(moduleClassSymbol.info)
+
+      /* AnnotatedType should (probably) be eliminated by erasure. However we know it happens for
+       * meta-annotated annotations (@(ann @getter) val x = 0), so we don't emit a warning.
+       * The type in the AnnotationInfo is an AnnotatedTpe. Tested in jvm/annotations.scala.
+       */
+      case a @ AnnotatedType(_, t) =>
+        debuglog(s"typeKind of annotated type $a")
+        typeToBType(t)
+
+      /* ExistentialType should (probably) be eliminated by erasure. We know they get here for
+       * classOf constants:
+       *   class C[T]
+       *   class T { final val k = classOf[C[_]] }
+       */
+      case e @ ExistentialType(_, t) =>
+        debuglog(s"typeKind of existential type $e")
+        typeToBType(t)
+
+      /* The cases below should probably never occur. They are kept for now to avoid introducing
+       * new compiler crashes, but we added a warning. The compiler / library bootstrap and the
+       * test suite don't produce any warning.
+       */
+
+      case tp =>
+        currentUnit.warning(tp.typeSymbol.pos,
+          s"an unexpected type representation reached the compiler backend while compiling $currentUnit: $tp. " +
+            "If possible, please file a bug on issues.scala-lang.org.")
+
+        tp match {
+          case ThisType(ArrayClass)               => ObjectReference // was introduced in 9b17332f11 to fix SI-999, but this code is not reached in its test, or any other test
+          case ThisType(sym)                      => classBTypeFromSymbol(sym)
+          case SingleType(_, sym)                 => primitiveOrClassToBType(sym)
+          case ConstantType(_)                    => typeToBType(t.underlying)
+          case RefinedType(parents, _)            => parents.map(typeToBType(_).asClassBType).reduceLeft((a, b) => a.jvmWiseLUB(b))
+        }
+    }
+  }
+
+  def assertClassNotArray(sym: Symbol): Unit = {
+    assert(sym.isClass, sym)
+    assert(sym != definitions.ArrayClass || isCompilingArray, sym)
+  }
+
+  def assertClassNotArrayNotPrimitive(sym: Symbol): Unit = {
+    assertClassNotArray(sym)
+    assert(!primitiveTypeMap.contains(sym) || isCompilingPrimitive, sym)
   }
 
   private def setClassInfo(classSym: Symbol, classBType: ClassBType): ClassBType = {
@@ -217,7 +366,9 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes {
 
     val nestedInfo = buildNestedInfo(classSym)
 
-    classBType.info = ClassInfo(superClass, interfaces, flags, nestedClasses, nestedInfo)
+    val inlineInfos = buildInlineInfos(classSym)
+
+    classBType.info = ClassInfo(superClass, interfaces, flags, nestedClasses, nestedInfo, inlineInfos)
     classBType
   }
 
@@ -272,6 +423,27 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes {
     }
   }
 
+  private def buildInlineInfos(classSym: Symbol): Map[String, MethodInlineInfo] = {
+    if (!settings.YoptInlinerEnabled) Map.empty
+    else {
+      // Primitve methods cannot be inlined, so there's no point in building an InlineInfo. Also, some
+      // primitive methods (e.g., `isInstanceOf`) have non-erased types, which confuses [[typeToBType]].
+      classSym.info.decls.iterator.filter(m => m.isMethod && !scalaPrimitives.isPrimitive(m)).map({
+        case methodSym =>
+          val methodBType = methodBTypeFromSymbol(methodSym)
+          val name        = methodSym.javaSimpleName.toString // same as in genDefDef
+          val signature   = name + methodBType.descriptor
+          val info        = MethodInlineInfo(
+            effectivelyFinal = methodSym.isEffectivelyFinalOrNotOverridden,
+            traitMethodWithStaticImplementation = false, // temporary, fixed in future commit
+            annotatedInline   = methodSym.hasAnnotation(ScalaInlineClass),
+            annotatedNoInline = methodSym.hasAnnotation(ScalaNoInlineClass)
+          )
+          (signature, info)
+      }).toMap
+    }
+  }
+
   /**
    * For top-level objects without a companion class, the compilere generates a mirror class with
    * static forwarders (Java compat). There's no symbol for the mirror class, but we still need a
@@ -289,7 +461,8 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes {
         interfaces = Nil,
         flags = asm.Opcodes.ACC_SUPER | asm.Opcodes.ACC_PUBLIC | asm.Opcodes.ACC_FINAL,
         nestedClasses = nested,
-        nestedInfo = None
+        nestedInfo = None,
+        Map.empty // no InlineInfo needed, scala never invokes methods on the mirror class
       )
       c
     })
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
index 4cff92d38b..74f46d04f9 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
@@ -293,7 +293,7 @@ object BytecodeUtils {
   }
 
   class BasicAnalyzer(methodNode: MethodNode, classInternalName: InternalName) {
-    val analyzer = new Analyzer[BasicValue](new BasicInterpreter)
+    val analyzer = new Analyzer(new BasicInterpreter)
     analyzer.analyze(classInternalName, methodNode)
     def frameAt(instruction: AbstractInsnNode): Frame[BasicValue] = analyzer.getFrames()(methodNode.instructions.indexOf(instruction))
   }
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
new file mode 100644
index 0000000000..bfaa67004c
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
@@ -0,0 +1,114 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2014 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+
+package scala.tools.nsc
+package backend.jvm
+package opt
+
+import scala.tools.asm.tree._
+import scala.collection.convert.decorateAsScala._
+import scala.tools.nsc.backend.jvm.opt.BytecodeUtils.BasicAnalyzer
+
+class CallGraph[BT <: BTypes](val btypes: BT) {
+  import btypes._
+
+  val callsites: collection.concurrent.Map[MethodInsnNode, Callsite] = recordPerRunCache(collection.concurrent.TrieMap.empty[MethodInsnNode, Callsite])
+
+  def addClass(classNode: ClassNode): Unit = {
+    for (m <- classNode.methods.asScala; callsite <- analyzeCallsites(m, classBTypeFromClassNode(classNode)))
+      callsites(callsite.callsiteInstruction) = callsite
+  }
+
+  def analyzeCallsites(methodNode: MethodNode, definingClass: ClassBType): List[Callsite] = {
+    // TODO: run dataflow analyses to make the call graph more precise
+    //  - producers to get forwarded parameters (ForwardedParam)
+    //  - typeAnalysis for more precise argument types, more precise callee
+    //  - nullAnalysis to skip emitting the receiver-null-check when inlining
+
+    // 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.
+    val analyzer = new BasicAnalyzer(methodNode, definingClass.internalName)
+
+    methodNode.instructions.iterator.asScala.collect({
+      case call: MethodInsnNode =>
+        // TODO: log an inliner warning if the callee method cannot be found in the code repo? eg it's not on the classpath.
+        val callee = byteCodeRepository.methodNode(call.owner, call.name, call.desc) map {
+          case (method, declarationClass) =>
+            val (declarationClassNode, source) = byteCodeRepository.classNodeAndSource(declarationClass)
+            val declarationClassBType          = classBTypeFromClassNode(declarationClassNode)
+            val methodSignature                = method.name + method.desc
+            val (safeToInline, annotatedInline, annotatedNoInline) = declarationClassBType.info.inlineInfos.get(methodSignature) match {
+              case Some(inlineInfo) =>
+                val canInlineFromSource = inlineGlobalEnabled || source == ByteCodeRepository.CompilationUnit
+                // TODO: for now, we consider a callee safeToInline only if it's final
+                // type analysis can render more calls safeToInline (e.g. when the precise receiver type is known)
+                (canInlineFromSource && inlineInfo.effectivelyFinal, Some(inlineInfo.annotatedInline), Some(inlineInfo.annotatedNoInline))
+              case None =>
+                (false, None, None)
+            }
+            Callee(
+              callee = method,
+              calleeDeclarationClass = declarationClassBType,
+              safeToInline = safeToInline,
+              annotatedInline = annotatedInline,
+              annotatedNoInline = annotatedNoInline
+            )
+        }
+
+        val argInfos = if (callee.isEmpty) Nil else {
+          // TODO: for now it's Nil, because we don't run any data flow analysis
+          // there's no point in using the parameter types, that doesn't add any information.
+          // NOTE: need to run the same analyses after inlining, to re-compute the argInfos for the
+          // new duplicated callsites, see Inliner.inline
+          Nil
+        }
+
+        Callsite(
+          callsiteInstruction = call,
+          callsiteMethod = methodNode,
+          callsiteClass = definingClass,
+          callee = callee,
+          argInfos = argInfos,
+          callsiteStackHeight = analyzer.frameAt(call).getStackSize
+        )
+    }).toList
+  }
+
+  /**
+   * A callsite in the call graph.
+   * @param callsiteInstruction The invocation instruction
+   * @param callsiteMethod      The method containing the callsite
+   * @param callsiteClass       The class containing the callsite
+   * @param callee              The callee. For virtual calls, an override of the callee might be invoked.
+   * @param argInfos            Information about the invocation receiver and arguments
+   * @param callsiteStackHeight The stack height at the callsite, required by the inliner
+   */
+  final case class Callsite(callsiteInstruction: MethodInsnNode, callsiteMethod: MethodNode, callsiteClass: ClassBType,
+                            callee: Option[Callee], argInfos: List[ArgInfo],
+                            callsiteStackHeight: Int) {
+    override def toString = s"Invocation of ${callsiteInstruction.name + callsiteInstruction.desc}@${callsiteMethod.instructions.indexOf(callsiteInstruction)} in ${callsiteMethod.name}"
+  }
+
+  /**
+   * Information about invocation arguments, obtained through data flow analysis of the callsite method.
+   */
+  sealed trait ArgInfo
+  final case class ArgTypeInfo(argType: BType, isPrecise: Boolean, knownNotNull: Boolean) extends ArgInfo
+  final case class ForwardedParam(index: Int) extends ArgInfo
+  // can be extended, e.g., with constant types
+
+  /**
+   * A callee in the call graph.
+   * @param callee                 The called method. For virtual calls, an override may actually be invoked.
+   * @param calleeDeclarationClass The class in which the callee is declared
+   * @param safeToInline           True if the callee can be safely inlined: it cannot be overridden,
+   *                               and the inliner settings (project / global) allow inlining it.
+   * @param annotatedInline        Defined if it is known whether the callee is annotated @inline
+   * @param annotatedNoInline      Defined if it is known whether the callee is annotated @noinline
+   */
+  final case class Callee(callee: MethodNode, calleeDeclarationClass: ClassBType,
+                          safeToInline: Boolean,
+                          annotatedInline: Option[Boolean], annotatedNoInline: Option[Boolean])
+}
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 f964b5b25d..7527491e9b 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -19,7 +19,7 @@ import scala.tools.asm.tree.analysis._
 
 class Inliner[BT <: BTypes](val btypes: BT) {
   import btypes._
-  import btypes.byteCodeRepository
+  import callGraph._
 
   /**
    * Copy and adapt the instructions of a method to a callsite.
@@ -152,6 +152,29 @@ class Inliner[BT <: BTypes](val btypes: BT) {
       callsiteMethod.localVariables.addAll(cloneLocalVariableNodes(callee, labelsMap, callee.name + "_").asJava)
       callsiteMethod.tryCatchBlocks.addAll(cloneTryCatchBlockNodes(callee, labelsMap).asJava)
 
+      // Add all invocation instructions that were inlined to the call graph
+      callee.instructions.iterator().asScala foreach {
+        case originalCallsiteIns: MethodInsnNode =>
+          callGraph.callsites.get(originalCallsiteIns) match {
+            case Some(originalCallsite) =>
+              val newCallsiteIns = instructionMap(originalCallsiteIns).asInstanceOf[MethodInsnNode]
+              callGraph.callsites(newCallsiteIns) = Callsite(
+                callsiteInstruction = newCallsiteIns,
+                callsiteMethod = callsiteMethod,
+                callsiteClass = callsiteClass,
+                callee = originalCallsite.callee,
+                argInfos = Nil, // TODO: re-compute argInfos for new destination (once we actually compute them)
+                callsiteStackHeight = callsiteStackHeight + originalCallsite.callsiteStackHeight
+              )
+
+            case None =>
+          }
+
+        case _ =>
+      }
+      // Remove the elided invocation from the call graph
+      callGraph.callsites.remove(callsiteInstruction)
+
       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 3a7250031a..23c8daa046 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -9,7 +9,7 @@ package opt
 
 import scala.annotation.switch
 import scala.tools.asm.Opcodes
-import scala.tools.asm.tree.analysis.{Analyzer, BasicValue, BasicInterpreter}
+import scala.tools.asm.tree.analysis.{Analyzer, BasicInterpreter}
 import scala.tools.asm.tree._
 import scala.collection.convert.decorateAsScala._
 import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
@@ -149,7 +149,7 @@ class LocalOpt(settings: ScalaSettings) {
   def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: String): (Boolean, Set[LabelNode]) = {
     // The data flow analysis requires the maxLocals / maxStack fields of the method to be computed.
     computeMaxLocalsMaxStack(method)
-    val a = new Analyzer[BasicValue](new BasicInterpreter)
+    val a = new Analyzer(new BasicInterpreter)
     a.analyze(ownerClassName, method)
     val frames = a.getFrames
 
diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index d7f4cca615..9674b4cfae 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -222,6 +222,8 @@ trait ScalaSettings extends AbsScalaSettings
     val emptyLineNumbers        = Choice("empty-line-numbers",        "Eliminate unnecessary line number information.")
     val emptyLabels             = Choice("empty-labels",              "Eliminate and collapse redundant labels in the bytecode.")
     val compactLocals           = Choice("compact-locals",            "Eliminate empty slots in the sequence of local variables.")
+    val inlineProject           = Choice("inline-project",            "Inline only methods defined in the files being compiled")
+    val inlineGlobal            = Choice("inline-global",             "Inline methods from any source, including classfiles on the compile classpath")
 
     val lNone           = Choice("l:none",      "Don't enable any optimizations.")
 
@@ -231,10 +233,10 @@ trait ScalaSettings extends AbsScalaSettings
     private val methodChoices = List(unreachableCode, simplifyJumps, recurseUnreachableJumps, emptyLineNumbers, emptyLabels, compactLocals)
     val lMethod         = Choice("l:method",    "Enable intra-method optimizations: "+ methodChoices.mkString(","),                                expandsTo = methodChoices)
 
-    private val projectChoices = List(lMethod)
+    private val projectChoices = List(lMethod, inlineProject)
     val lProject        = Choice("l:project",   "Enable cross-method optimizations within the current project: "+ projectChoices.mkString(","),    expandsTo = projectChoices)
 
-    private val classpathChoices = List(lProject)
+    private val classpathChoices = List(lProject, inlineGlobal)
     val lClasspath      = Choice("l:classpath", "Enable cross-method optimizations across the entire classpath: "+ classpathChoices.mkString(","), expandsTo = classpathChoices)
   }
 
@@ -252,6 +254,10 @@ trait ScalaSettings extends AbsScalaSettings
   def YoptEmptyLabels             = Yopt.contains(YoptChoices.emptyLabels)
   def YoptCompactLocals           = Yopt.contains(YoptChoices.compactLocals)
 
+  def YoptInlineProject           = Yopt.contains(YoptChoices.inlineProject)
+  def YoptInlineGlobal            = Yopt.contains(YoptChoices.inlineGlobal)
+  def YoptInlinerEnabled          = YoptInlineProject || YoptInlineGlobal
+
   private def removalIn212 = "This flag is scheduled for removal in 2.12. If you have a case where you need this flag then please report a bug."
 
   object YstatisticsPhases extends MultiChoiceEnumeration { val parser, typer, patmat, erasure, cleanup, jvm = Value }