diff options
12 files changed, 553 insertions, 137 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 } 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 |