diff options
5 files changed, 169 insertions, 120 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala index c1293d4e81..fcb8991baa 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala @@ -7,6 +7,7 @@ package scala.tools.nsc package backend.jvm package opt +import scala.collection.immutable.IntMap import scala.reflect.internal.util.{NoPosition, Position} import scala.tools.asm.tree.analysis.{Value, Analyzer, BasicInterpreter} import scala.tools.asm.{Opcodes, Type, Handle} @@ -48,6 +49,32 @@ class CallGraph[BT <: BTypes](val btypes: BT) { */ val closureInstantiations: mutable.Map[MethodNode, Map[InvokeDynamicInsnNode, ClosureInstantiation]] = recordPerRunCache(concurrent.TrieMap.empty withDefaultValue Map.empty) + def removeCallsite(invocation: MethodInsnNode, methodNode: MethodNode): Option[Callsite] = { + val methodCallsites = callsites(methodNode) + val newCallsites = methodCallsites - invocation + if (newCallsites.isEmpty) callsites.remove(methodNode) + else callsites(methodNode) = newCallsites + methodCallsites.get(invocation) + } + + def addCallsite(callsite: Callsite): Unit = { + val methodCallsites = callsites(callsite.callsiteMethod) + callsites(callsite.callsiteMethod) = methodCallsites + (callsite.callsiteInstruction -> callsite) + } + + def removeClosureInstantiation(indy: InvokeDynamicInsnNode, methodNode: MethodNode): Option[ClosureInstantiation] = { + val methodClosureInits = closureInstantiations(methodNode) + val newClosureInits = methodClosureInits - indy + if (newClosureInits.isEmpty) closureInstantiations.remove(methodNode) + else closureInstantiations(methodNode) = newClosureInits + methodClosureInits.get(indy) + } + + def addClosureInstantiation(closureInit: ClosureInstantiation) = { + val methodClosureInits = closureInstantiations(closureInit.ownerMethod) + closureInstantiations(closureInit.ownerMethod) = methodClosureInits + (closureInit.lambdaMetaFactoryCall.indy -> closureInit) + } + def addClass(classNode: ClassNode): Unit = { val classType = classBTypeFromClassNode(classNode) classNode.methods.asScala.foreach(addMethod(_, classType)) @@ -61,70 +88,6 @@ class CallGraph[BT <: BTypes](val btypes: BT) { * Returns a list of callsites in the method, plus a list of closure instantiation indy instructions. */ def addMethod(methodNode: MethodNode, definingClass: ClassBType): Unit = { - - case class CallsiteInfo(safeToInline: Boolean, safeToRewrite: Boolean, - annotatedInline: Boolean, annotatedNoInline: Boolean, - warning: Option[CalleeInfoWarning]) - - /** - * Analyze a callsite and gather meta-data that can be used for inlining decisions. - */ - def analyzeCallsite(calleeMethodNode: MethodNode, calleeDeclarationClassBType: ClassBType, receiverTypeInternalName: InternalName, calleeSource: Source): CallsiteInfo = { - val methodSignature = calleeMethodNode.name + calleeMethodNode.desc - - try { - // The inlineInfo.methodInfos of a ClassBType holds an InlineInfo for each method *declared* - // within a class (not for inherited methods). Since we already have the classBType of the - // callee, we only check there for the methodInlineInfo, we should find it there. - calleeDeclarationClassBType.info.orThrow.inlineInfo.methodInfos.get(methodSignature) match { - case Some(methodInlineInfo) => - val canInlineFromSource = compilerSettings.YoptInlineGlobal || calleeSource == CompilationUnit - - val isAbstract = BytecodeUtils.isAbstractMethod(calleeMethodNode) - - // (1) A non-final method can be safe to inline if the receiver type is a final subclass. Example: - // class A { @inline def f = 1 }; object B extends A; B.f // can be inlined - // - // TODO: type analysis can render more calls statically resolved. Example: - // new A.f // can be inlined, the receiver type is known to be exactly A. - val isStaticallyResolved: Boolean = { - methodInlineInfo.effectivelyFinal || - classBTypeFromParsedClassfile(receiverTypeInternalName).info.orThrow.inlineInfo.isEffectivelyFinal // (1) - } - - val isRewritableTraitCall = isStaticallyResolved && methodInlineInfo.traitMethodWithStaticImplementation - - val warning = calleeDeclarationClassBType.info.orThrow.inlineInfo.warning.map( - MethodInlineInfoIncomplete(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, _)) - - // (1) For invocations of final trait methods, the callee isStaticallyResolved but also - // abstract. Such a callee is not safe to inline - it needs to be re-written to the - // static impl method first (safeToRewrite). - // (2) Final trait methods can be rewritten from the interface to the static implementation - // method to enable inlining. - CallsiteInfo( - safeToInline = - canInlineFromSource && - isStaticallyResolved && // (1) - !isAbstract && - !BytecodeUtils.isConstructor(calleeMethodNode) && - !BytecodeUtils.isNativeMethod(calleeMethodNode), - safeToRewrite = canInlineFromSource && isRewritableTraitCall, // (2) - annotatedInline = methodInlineInfo.annotatedInline, - annotatedNoInline = methodInlineInfo.annotatedNoInline, - warning = warning) - - case None => - val warning = MethodInlineInfoMissing(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, calleeDeclarationClassBType.info.orThrow.inlineInfo.warning) - CallsiteInfo(false, false, false, false, Some(warning)) - } - } catch { - case Invalid(noInfo: NoClassBTypeInfo) => - val warning = MethodInlineInfoError(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, noInfo) - CallsiteInfo(false, false, false, false, Some(warning)) - } - } - // 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 @@ -158,7 +121,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) { (declarationClassNode, source) <- byteCodeRepository.classNodeAndSource(declarationClass): Either[OptimizerWarning, (ClassNode, Source)] declarationClassBType = classBTypeFromClassNode(declarationClassNode) } yield { - val CallsiteInfo(safeToInline, safeToRewrite, annotatedInline, annotatedNoInline, warning) = analyzeCallsite(method, declarationClassBType, call.owner, source) + val CallsiteInfo(safeToInline, safeToRewrite, annotatedInline, annotatedNoInline, higherOrderParams, warning) = analyzeCallsite(method, declarationClassBType, call.owner, source) Callee( callee = method, calleeDeclarationClass = declarationClassBType, @@ -166,6 +129,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) { safeToRewrite = safeToRewrite, annotatedInline = annotatedInline, annotatedNoInline = annotatedNoInline, + higherOrderParams = higherOrderParams, calleeInfoWarning = warning) } @@ -206,30 +170,73 @@ class CallGraph[BT <: BTypes](val btypes: BT) { closureInstantiations(methodNode) = methodClosureInstantiations } - def removeCallsite(invocation: MethodInsnNode, methodNode: MethodNode): Option[Callsite] = { - val methodCallsites = callsites(methodNode) - val newCallsites = methodCallsites - invocation - if (newCallsites.isEmpty) callsites.remove(methodNode) - else callsites(methodNode) = newCallsites - methodCallsites.get(invocation) - } - - def addCallsite(callsite: Callsite): Unit = { - val methodCallsites = callsites(callsite.callsiteMethod) - callsites(callsite.callsiteMethod) = methodCallsites + (callsite.callsiteInstruction -> callsite) - } - - def removeClosureInstantiation(indy: InvokeDynamicInsnNode, methodNode: MethodNode): Option[ClosureInstantiation] = { - val methodClosureInits = closureInstantiations(methodNode) - val newClosureInits = methodClosureInits - indy - if (newClosureInits.isEmpty) closureInstantiations.remove(methodNode) - else closureInstantiations(methodNode) = newClosureInits - methodClosureInits.get(indy) - } + /** + * Just a named tuple used as return type of `analyzeCallsite`. + */ + private case class CallsiteInfo(safeToInline: Boolean, safeToRewrite: Boolean, + annotatedInline: Boolean, annotatedNoInline: Boolean, + higherOrderParams: IntMap[ClassBType], + warning: Option[CalleeInfoWarning]) - def addClosureInstantiation(closureInit: ClosureInstantiation) = { - val methodClosureInits = closureInstantiations(closureInit.ownerMethod) - closureInstantiations(closureInit.ownerMethod) = methodClosureInits + (closureInit.lambdaMetaFactoryCall.indy -> closureInit) + /** + * Analyze a callsite and gather meta-data that can be used for inlining decisions. + */ + private def analyzeCallsite(calleeMethodNode: MethodNode, calleeDeclarationClassBType: ClassBType, receiverTypeInternalName: InternalName, calleeSource: Source): CallsiteInfo = { + val methodSignature = calleeMethodNode.name + calleeMethodNode.desc + + try { + // The inlineInfo.methodInfos of a ClassBType holds an InlineInfo for each method *declared* + // within a class (not for inherited methods). Since we already have the classBType of the + // callee, we only check there for the methodInlineInfo, we should find it there. + calleeDeclarationClassBType.info.orThrow.inlineInfo.methodInfos.get(methodSignature) match { + case Some(methodInlineInfo) => + val canInlineFromSource = compilerSettings.YoptInlineGlobal || calleeSource == CompilationUnit + + val isAbstract = BytecodeUtils.isAbstractMethod(calleeMethodNode) + + val receiverType = classBTypeFromParsedClassfile(receiverTypeInternalName) + // (1) A non-final method can be safe to inline if the receiver type is a final subclass. Example: + // class A { @inline def f = 1 }; object B extends A; B.f // can be inlined + // + // TODO: type analysis can render more calls statically resolved. Example: + // new A.f // can be inlined, the receiver type is known to be exactly A. + val isStaticallyResolved: Boolean = { + methodInlineInfo.effectivelyFinal || + receiverType.info.orThrow.inlineInfo.isEffectivelyFinal // (1) + } + + val isRewritableTraitCall = isStaticallyResolved && methodInlineInfo.traitMethodWithStaticImplementation + + val warning = calleeDeclarationClassBType.info.orThrow.inlineInfo.warning.map( + MethodInlineInfoIncomplete(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, _)) + + // (1) For invocations of final trait methods, the callee isStaticallyResolved but also + // abstract. Such a callee is not safe to inline - it needs to be re-written to the + // static impl method first (safeToRewrite). + // (2) Final trait methods can be rewritten from the interface to the static implementation + // method to enable inlining. + CallsiteInfo( + safeToInline = + canInlineFromSource && + isStaticallyResolved && // (1) + !isAbstract && + !BytecodeUtils.isConstructor(calleeMethodNode) && + !BytecodeUtils.isNativeMethod(calleeMethodNode), + safeToRewrite = canInlineFromSource && isRewritableTraitCall, // (2) + annotatedInline = methodInlineInfo.annotatedInline, + annotatedNoInline = methodInlineInfo.annotatedNoInline, + higherOrderParams = inliner.heuristics.higherOrderParams(calleeMethodNode, receiverType), + warning = warning) + + case None => + val warning = MethodInlineInfoMissing(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, calleeDeclarationClassBType.info.orThrow.inlineInfo.warning) + CallsiteInfo(false, false, false, false, IntMap.empty, Some(warning)) + } + } catch { + case Invalid(noInfo: NoClassBTypeInfo) => + val warning = MethodInlineInfoError(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, noInfo) + CallsiteInfo(false, false, false, false, IntMap.empty, Some(warning)) + } } /** @@ -277,12 +284,14 @@ class CallGraph[BT <: BTypes](val btypes: BT) { * that can be safely re-written to the static implementation method. * @param annotatedInline True if the callee is annotated @inline * @param annotatedNoInline True if the callee is annotated @noinline + * @param higherOrderParams A map from parameter positions to SAM parameter types * @param calleeInfoWarning An inliner warning if some information was not available while * gathering the information about this callee. */ final case class Callee(callee: MethodNode, calleeDeclarationClass: ClassBType, safeToInline: Boolean, safeToRewrite: Boolean, annotatedInline: Boolean, annotatedNoInline: Boolean, + higherOrderParams: IntMap[ClassBType], calleeInfoWarning: Option[CalleeInfoWarning]) { assert(!(safeToInline && safeToRewrite), s"A callee of ${callee.name} can be either safeToInline or safeToRewrite, but not both.") } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala index 3fbc374a93..ba6897b06e 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala @@ -240,14 +240,17 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { callsiteMethod = ownerMethod, callsiteClass = closureInit.ownerClass, callee = bodyMethod.map({ - case (bodyMethodNode, bodyMethodDeclClass) => Callee( - callee = bodyMethodNode, - calleeDeclarationClass = classBTypeFromParsedClassfile(bodyMethodDeclClass), - safeToInline = compilerSettings.YoptInlineGlobal || bodyMethodIsBeingCompiled, - safeToRewrite = false, // the lambda body method is not a trait interface method - annotatedInline = false, - annotatedNoInline = false, - calleeInfoWarning = None) + case (bodyMethodNode, bodyMethodDeclClass) => + val bodyDeclClassType = classBTypeFromParsedClassfile(bodyMethodDeclClass) + Callee( + callee = bodyMethodNode, + calleeDeclarationClass = bodyDeclClassType, + safeToInline = compilerSettings.YoptInlineGlobal || bodyMethodIsBeingCompiled, + safeToRewrite = false, // the lambda body method is not a trait interface method + annotatedInline = false, + annotatedNoInline = false, + inliner.heuristics.higherOrderParams(bodyMethodNode, bodyDeclClassType), + calleeInfoWarning = None) }), argInfos = Nil, callsiteStackHeight = invocationStackHeight, 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 f4673be974..265685ad84 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala @@ -100,7 +100,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { * True for statically resolved trait callsites that should be rewritten to the static implementation method. */ def doRewriteTraitCallsite(callsite: Callsite) = callsite.callee match { - case Right(Callee(callee, calleeDeclarationClass, safeToInline, true, annotatedInline, annotatedNoInline, infoWarning)) => true + case Right(Callee(_, _, _, safeToRewrite, _, _, _, _)) => safeToRewrite case _ => false } @@ -113,7 +113,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { */ def rewriteFinalTraitMethodInvocation(callsite: Callsite): Unit = { if (doRewriteTraitCallsite(callsite)) { - val Right(Callee(callee, calleeDeclarationClass, _, _, annotatedInline, annotatedNoInline, infoWarning)) = callsite.callee + val Right(Callee(callee, calleeDeclarationClass, _, _, annotatedInline, annotatedNoInline, higherOrderParams, infoWarning)) = callsite.callee val traitMethodArgumentTypes = asm.Type.getArgumentTypes(callee.desc) @@ -160,6 +160,10 @@ class Inliner[BT <: BTypes](val btypes: BT) { callsite.callsiteMethod.instructions.remove(callsite.callsiteInstruction) callGraph.removeCallsite(callsite.callsiteInstruction, callsite.callsiteMethod) + val staticCallHigherOrderParams = { + if (selfParamType.info.get.inlineInfo.sam.isEmpty) higherOrderParams - 0 + else higherOrderParams.updated(0, selfParamType) + } val staticCallsite = Callsite( callsiteInstruction = newCallsiteInstruction, callsiteMethod = callsite.callsiteMethod, @@ -171,6 +175,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { safeToRewrite = false, annotatedInline = annotatedInline, annotatedNoInline = annotatedNoInline, + higherOrderParams = staticCallHigherOrderParams, calleeInfoWarning = infoWarning)), argInfos = Nil, callsiteStackHeight = callsite.callsiteStackHeight, diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/InlinerHeuristics.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/InlinerHeuristics.scala index df2eb813d3..7cfc797317 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/InlinerHeuristics.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/InlinerHeuristics.scala @@ -7,6 +7,8 @@ package scala.tools.nsc package backend.jvm package opt +import scala.collection.immutable.IntMap +import scala.tools.asm.Type import scala.tools.asm.tree.{MethodNode, MethodInsnNode} import scala.tools.nsc.backend.jvm.BTypes.InternalName import scala.collection.convert.decorateAsScala._ @@ -20,21 +22,26 @@ class InlinerHeuristics[BT <: BTypes](val bTypes: BT) { case class PostInlineRequest(callsiteInstruction: MethodInsnNode, post: List[PostInlineRequest]) /** - * Select callsites from the call graph that should be inlined. The resulting list of inlining - * requests is allowed to have cycles, and the callsites can appear in any order. + * Select callsites from the call graph that should be inlined, grouped by the containing method. + * Cyclic inlining requests are allowed, the inliner will eliminate requests to break cycles. */ def selectCallsitesForInlining: Map[MethodNode, Set[InlineRequest]] = { - // We should only return inlining requests for callsites being compiled (not for callsites in + // We should only create inlining requests for callsites being compiled (not for callsites in // classes on the classpath). The call graph may contain callsites of classes parsed from the // classpath. In order to get only the callsites being compiled, we start at the map of // compilingClasses in the byteCodeRepository. - val compilingMethods = byteCodeRepository.compilingClasses.valuesIterator.flatMap(_.methods.iterator.asScala) - compilingMethods.map(methodNode => { - val requests = callGraph.callsites(methodNode).valuesIterator.filter({ - case callsite @ Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, warning)), _, _, _, pos) => - val res = doInlineCallsite(callsite) + val compilingMethods = for { + classNode <- byteCodeRepository.compilingClasses.valuesIterator + methodNode <- classNode.methods.iterator.asScala + } yield methodNode - if (!res) { + compilingMethods.map(methodNode => { + var requests = Set.empty[InlineRequest] + callGraph.callsites(methodNode).valuesIterator foreach { + case callsite @ Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, _, warning)), _, _, _, pos) => + val request = inlineRequest(callsite) + requests ++= request + if (request.isEmpty) { if (annotatedInline && bTypes.compilerSettings.YoptWarningEmitAtInlineFailed) { // if the callsite is annotated @inline, we report an inline warning even if the underlying // reason is, for example, mixed compilation (which has a separate -Yopt-warning flag). @@ -52,27 +59,51 @@ class InlinerHeuristics[BT <: BTypes](val bTypes: BT) { } } - res - case Callsite(ins, _, _, Left(warning), _, _, _, pos) => if (warning.emitWarning(compilerSettings)) backendReporting.inlinerWarning(pos, s"failed to determine if ${ins.name} should be inlined:\n$warning") - false - }) - - (methodNode, requests.map(InlineRequest(_, Nil)).toSet) + } + (methodNode, requests) }).filterNot(_._2.isEmpty).toMap } + def higherOrderParams(methodNode: MethodNode, receiverType: ClassBType): IntMap[ClassBType] = { + var res = IntMap.empty[ClassBType] + val paramTypes = { + val params = Type.getMethodType(methodNode.desc).getArgumentTypes.map(t => bTypeForDescriptorOrInternalNameFromClassfile(t.getDescriptor)) + val isStatic = BytecodeUtils.isStaticMethod(methodNode) + if (isStatic) params else receiverType +: params + } + for (i <- paramTypes.indices) { + paramTypes(i) match { + case c: ClassBType => + if (c.info.get.inlineInfo.sam.isDefined) res = res.updated(i, c) + + case _ => + } + } + res + } + /** - * The current inlining heuristics are simple: inline calls to methods annotated @inline. + * Returns the inline request for a callsite if the callsite should be inlined according to the + * current heuristics (`-Yopt-inline-heuristics`). + * + * The resulting inline request may contain post-inlining requests of callsites that in turn are + * also selected as individual inlining requests. */ - def doInlineCallsite(callsite: Callsite): Boolean = callsite match { - case Callsite(_, _, _, Right(Callee(callee, calleeDeclClass, safeToInline, _, annotatedInline, _, warning)), _, _, _, pos) => - if (compilerSettings.YoptInlineHeuristics.value == "everything") safeToInline - else annotatedInline && safeToInline + def inlineRequest(callsite: Callsite): Option[InlineRequest] = compilerSettings.YoptInlineHeuristics.value match { + case "everything" => + if (callsite.callee.get.safeToInline) Some(InlineRequest(callsite, Nil)) + else None + + case "at-inline-annotated" => + val callee = callsite.callee.get + if (callee.safeToInline && callee.annotatedInline) Some(InlineRequest(callsite, Nil)) + else None + +// case "default" => - case _ => 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 d727951a6b..135ebe9a78 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala @@ -6,6 +6,7 @@ import org.junit.runner.RunWith import org.junit.runners.JUnit4 import org.junit.Test import scala.collection.generic.Clearable +import scala.collection.immutable.IntMap import scala.collection.mutable.ListBuffer import scala.reflect.internal.util.{NoPosition, BatchSourceFile} import scala.tools.asm.Opcodes._ @@ -95,7 +96,7 @@ class InlinerTest extends ClearAfterClass { callsiteInstruction = callsiteInstruction, callsiteMethod = callsiteMethod, callsiteClass = callsiteClass, - callee = Right(callGraph.Callee(callee = callee, calleeDeclarationClass = calleeDeclarationClass, safeToInline = true, safeToRewrite = false, annotatedInline = false, annotatedNoInline = false, calleeInfoWarning = None)), + callee = Right(callGraph.Callee(callee = callee, calleeDeclarationClass = calleeDeclarationClass, safeToInline = true, safeToRewrite = false, annotatedInline = false, annotatedNoInline = false, higherOrderParams = IntMap.empty, calleeInfoWarning = None)), argInfos = Nil, callsiteStackHeight = callsiteStackHeight, receiverKnownNotNull = receiverKnownNotNull, |