diff options
author | Lukas Rytz <lukas.rytz@gmail.com> | 2015-11-13 16:34:27 +0100 |
---|---|---|
committer | Lukas Rytz <lukas.rytz@gmail.com> | 2015-11-13 20:03:03 +0100 |
commit | d4bfc59b781b465ef980cd7082462eb2cfe2c8b8 (patch) | |
tree | 49a3775a4fb175f72a596e2605d492bb2f0f94f3 /src/compiler | |
parent | 12b6598714d72bd1d275d756de0b8e7df04d1f16 (diff) | |
download | scala-d4bfc59b781b465ef980cd7082462eb2cfe2c8b8.tar.gz scala-d4bfc59b781b465ef980cd7082462eb2cfe2c8b8.tar.bz2 scala-d4bfc59b781b465ef980cd7082462eb2cfe2c8b8.zip |
Support specialized functions in closure optimizer
Fixes https://github.com/scala/scala-dev/issues/52.
An IndyLambda may create a specialized function type, where the SAM
is the corresponding specialized variant of apply. If this closure
is invoked through the generic apply method, the closure optimizer
would previously not re-write the invocation to the $anonfun method.
This is now done, including the necessary box / unbox operations.
Diffstat (limited to 'src/compiler')
4 files changed, 179 insertions, 47 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/CoreBTypes.scala b/src/compiler/scala/tools/nsc/backend/jvm/CoreBTypes.scala index 79aa4308c5..0317e08d9e 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/CoreBTypes.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/CoreBTypes.scala @@ -119,6 +119,7 @@ class CoreBTypes[BTFS <: BTypesFromSymbols[_ <: Global]](val bTypes: BTFS) { lazy val jliMethodHandlesLookupRef : ClassBType = classBTypeFromSymbol(exitingPickler(rootMirror.getRequiredClass("java.lang.invoke.MethodHandles.Lookup"))) // didn't find a reliable non-stringly-typed way that works for inner classes in the backend lazy val srLambdaDeserializerRef : ClassBType = classBTypeFromSymbol(requiredModule[scala.runtime.LambdaDeserializer.type].moduleClass) lazy val srBoxesRunTimeRef : ClassBType = classBTypeFromSymbol(requiredClass[scala.runtime.BoxesRunTime]) + lazy val srBoxedUnitRef : ClassBType = classBTypeFromSymbol(requiredClass[scala.runtime.BoxedUnit]) lazy val hashMethodSym: Symbol = getMember(ScalaRunTimeModule, nme.hash_) @@ -202,6 +203,11 @@ trait CoreBTypesProxyGlobalIndependent[BTS <: BTypes] { def jliMethodHandlesRef : ClassBType def jliMethodHandlesLookupRef : ClassBType def srLambdaDeserializerRef : ClassBType + def srBoxesRunTimeRef : ClassBType + def srBoxedUnitRef : ClassBType + + def asmBoxTo : Map[BType, MethodNameAndType] + def asmUnboxTo: Map[BType, MethodNameAndType] } /** @@ -242,6 +248,7 @@ final class CoreBTypesProxy[BTFS <: BTypesFromSymbols[_ <: Global]](val bTypes: def jliMethodHandlesLookupRef : ClassBType = _coreBTypes.jliMethodHandlesLookupRef def srLambdaDeserializerRef : ClassBType = _coreBTypes.srLambdaDeserializerRef def srBoxesRunTimeRef : ClassBType = _coreBTypes.srBoxesRunTimeRef + def srBoxedUnitRef : ClassBType = _coreBTypes.srBoxedUnitRef def hashMethodSym: Symbol = _coreBTypes.hashMethodSym diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/BackendUtils.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/BackendUtils.scala index 204c6a33ce..e4fdcdc542 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/BackendUtils.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/BackendUtils.scala @@ -7,6 +7,7 @@ import scala.tools.asm.{Opcodes, Handle, Type, Label} import scala.tools.asm.tree._ import scala.tools.asm.tree.analysis.{Frame, BasicInterpreter, Analyzer, Value} import scala.tools.nsc.backend.jvm.BTypes._ +import scala.tools.nsc.backend.jvm.opt.BytecodeUtils import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._ import java.lang.invoke.LambdaMetafactory import scala.collection.mutable @@ -23,6 +24,7 @@ import scala.collection.convert.decorateAsScala._ */ class BackendUtils[BT <: BTypes](val btypes: BT) { import btypes._ + import callGraph.ClosureInstantiation /** * A wrapper to make ASM's Analyzer a bit easier to use. @@ -141,6 +143,14 @@ class BackendUtils[BT <: BTypes](val btypes: BT) { (result, map, hasSerializableClosureInstantiation) } + def getBoxedUnit: FieldInsnNode = new FieldInsnNode(Opcodes.GETSTATIC, coreBTypes.srBoxedUnitRef.internalName, "UNIT", coreBTypes.srBoxedUnitRef.descriptor) + + private val anonfunAdaptedName = """.*\$anonfun\$\d+\$adapted""" + def hasAdaptedImplMethod(closureInit: ClosureInstantiation): Boolean = { + BytecodeUtils.isrJFunctionType(Type.getReturnType(closureInit.lambdaMetaFactoryCall.indy.desc).getInternalName) && + closureInit.lambdaMetaFactoryCall.implMethod.getName.matches(anonfunAdaptedName) + } + /** * Visit the class node and collect all referenced nested classes. */ 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 b192e1b46a..64677ddcc0 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala @@ -461,7 +461,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) { // When re-writing the closure callsite to the implMethod, we have to insert a cast. // // The check below ensures that - // (1) the implMethod type has the expected singature (captured types plus argument types + // (1) the implMethod type has the expected signature (captured types plus argument types // from instantiatedMethodType) // (2) the receiver of the implMethod matches the first captured type // (3) all parameters that are not the same in samMethodType and instantiatedMethodType 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 4203a93f2e..4e1e878aa8 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala @@ -11,7 +11,7 @@ import scala.annotation.switch import scala.collection.immutable import scala.collection.immutable.IntMap import scala.reflect.internal.util.NoPosition -import scala.tools.asm.{Type, Opcodes} +import scala.tools.asm.{Handle, Type, Opcodes} import scala.tools.asm.tree._ import scala.tools.nsc.backend.jvm.BTypes.InternalName import BytecodeUtils._ @@ -23,7 +23,9 @@ import scala.collection.convert.decorateAsScala._ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { import btypes._ import callGraph._ + import coreBTypes._ import backendUtils._ + import ClosureOptimizer._ /** * If a closure is allocated and invoked within the same method, re-write the invocation to the @@ -81,6 +83,7 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { // We don't need to worry about the method being too large for running an analysis: large // methods are not added to the call graph / closureInstantiations map. lazy val prodCons = new ProdConsAnalyzer(methodNode, closureInits.valuesIterator.next().ownerClass.internalName) + // sorting for bytecode stability (e.g. indices of local vars created during the rewrite) val sortedInits = immutable.TreeSet.empty ++ closureInits.values sortedInits.iterator.map(init => (init, closureCallsites(init, prodCons))).filter(_._2.nonEmpty) }).toList // mapping to a list (not a map) to keep the sorting @@ -118,20 +121,7 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { val argTypes = closureInit.lambdaMetaFactoryCall.samMethodType.getArgumentTypes val firstArgLocal = ownerMethod.maxLocals - // The comment in the unapply method of `LambdaMetaFactoryCall` explains why we have to introduce - // casts for arguments that have different types in samMethodType and instantiatedMethodType. - val castLoadTypes = { - val instantiatedMethodType = closureInit.lambdaMetaFactoryCall.instantiatedMethodType - (argTypes, instantiatedMethodType.getArgumentTypes).zipped map { - case (samArgType, instantiatedArgType) if samArgType != instantiatedArgType => - // the LambdaMetaFactoryCall extractor ensures that the two types are reference types, - // so we don't end up casting primitive values. - Some(instantiatedArgType) - case _ => - None - } - } - val argLocals = LocalsList.fromTypes(firstArgLocal, argTypes, castLoadTypes) + val argLocals = LocalsList.fromTypes(firstArgLocal, argTypes) ownerMethod.maxLocals = firstArgLocal + argLocals.size (captureLocals, argLocals) @@ -169,6 +159,28 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { }).toList } + /** + * Check whether `invocation` invokes the SAM of the IndyLambda `closureInit`. + * + * In addition to a perfect match, we also identify cases where a generic FunctionN is created + * but the invocation is to a specialized variant apply$sp... Vice-versa, we also allow the + * case where a specialized FunctionN$sp.. is created but the generic apply is invoked. In + * these cases, the translation will introduce the necessary box / unbox invocations. Example: + * + * val f: Int => Any = (x: Int) => 1 + * f(10) + * + * The IndyLambda creates a specialized `JFunction1$mcII$sp`, whose SAM is `apply$mcII$sp(I)I`. + * The invocation calls `apply(Object)Object`: the method name and type don't match. + * We identify these cases, insert the necessary unbox operation for the arguments, and invoke + * the `$anonfun(I)I` method. + * + * Tests in InlinerTest.optimizeSpecializedClosures. In that test, methods t4/t4a/t5/t8 show + * examples where the parameters have to be unboxed because generic `apply` is called, but the + * lambda body method takes primitive types. + * The opposite case is in t9: a the specialized `apply$sp..` is invoked, but the lambda body + * method takes boxed arguments, so we have to insert boxing operations. + */ private def isSamInvocation(invocation: MethodInsnNode, closureInit: ClosureInstantiation, prodCons: => ProdConsAnalyzer): Boolean = { val indy = closureInit.lambdaMetaFactoryCall.indy if (invocation.getOpcode == INVOKESTATIC) false @@ -183,11 +195,97 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { receiverProducers.size == 1 && receiverProducers.head == indy } - invocation.name == indy.name && { - val indySamMethodDesc = closureInit.lambdaMetaFactoryCall.samMethodType.getDescriptor - indySamMethodDesc == invocation.desc - } && - closureIsReceiver // most expensive check last + def isSpecializedVersion(specName: String, nonSpecName: String) = specName.startsWith(nonSpecName) && specName.substring(nonSpecName.length).matches(specializationSuffix) + + def sameOrSpecializedType(specTp: Type, nonSpecTp: Type) = { + specTp == nonSpecTp || { + val specDesc = specTp.getDescriptor + val nonSpecDesc = nonSpecTp.getDescriptor + specDesc.length == 1 && primitives.contains(specDesc) && nonSpecDesc == ObjectRef.descriptor + } + } + + def specializedDescMatches(specMethodDesc: String, nonSpecMethodDesc: String) = { + val specArgs = Type.getArgumentTypes(specMethodDesc) + val nonSpecArgs = Type.getArgumentTypes(nonSpecMethodDesc) + specArgs.corresponds(nonSpecArgs)(sameOrSpecializedType) && sameOrSpecializedType(Type.getReturnType(specMethodDesc), Type.getReturnType(nonSpecMethodDesc)) + } + + def nameAndDescMatch = { + val aName = invocation.name + val bName = indy.name + val aDesc = invocation.desc + val bDesc = closureInit.lambdaMetaFactoryCall.samMethodType.getDescriptor + if (aName == bName) aDesc == bDesc + else if (isSpecializedVersion(aName, bName)) specializedDescMatches(aDesc, bDesc) + else if (isSpecializedVersion(bName, aName)) specializedDescMatches(bDesc, aDesc) + else false + } + + nameAndDescMatch && closureIsReceiver // most expensive check last + } + } + + private def isPrimitiveType(asmType: Type) = { + val sort = asmType.getSort + Type.VOID <= sort && sort <= Type.DOUBLE + } + + private def unboxOp(primitiveType: Type): MethodInsnNode = { + val bType = bTypeForDescriptorOrInternalNameFromClassfile(primitiveType.getDescriptor) + val MethodNameAndType(name, methodBType) = asmUnboxTo(bType) + new MethodInsnNode(INVOKESTATIC, srBoxesRunTimeRef.internalName, name, methodBType.descriptor, /*itf =*/ false) + } + + private def boxOp(primitiveType: Type): MethodInsnNode = { + val bType = bTypeForDescriptorOrInternalNameFromClassfile(primitiveType.getDescriptor) + val MethodNameAndType(name, methodBType) = asmBoxTo(bType) + new MethodInsnNode(INVOKESTATIC, srBoxesRunTimeRef.internalName, name, methodBType.descriptor, /*itf =*/ false) + } + + /** + * The argument types of the lambda body method may differ in two ways from the argument types of + * the closure member method that is invoked (and replaced by a call to the body). + * - The lambda body method may have more specific types than the invoked closure member, see + * comment in [[LambdaMetaFactoryCall.unapply]]. + * - The invoked closure member might be a specialized variant of the SAM or vice-versa, see + * comment method [[isSamInvocation]]. + */ + private def adaptStoredArguments(closureInit: ClosureInstantiation, invocation: MethodInsnNode): Int => Option[AbstractInsnNode] = { + val invokeDesc = invocation.desc + // The lambda body method has additional parameters for captured values. Here we need to consider + // only those parameters of the body method that correspond to lambda parameters. This happens + // to be exactly LMF.instantiatedMethodType. In fact, `LambdaMetaFactoryCall.unapply` ensures + // that the body method signature is exactly (capturedParams + instantiatedMethodType). + val lambdaBodyMethodDescWithoutCaptures = closureInit.lambdaMetaFactoryCall.instantiatedMethodType.getDescriptor + if (invokeDesc == lambdaBodyMethodDescWithoutCaptures) { + _ => None + } else { + val invokeArgTypes = Type.getArgumentTypes(invokeDesc) + val implMethodArgTypes = Type.getArgumentTypes(lambdaBodyMethodDescWithoutCaptures) + val res = new Array[Option[AbstractInsnNode]](invokeArgTypes.length) + for (i <- invokeArgTypes.indices) { + if (invokeArgTypes(i) == implMethodArgTypes(i)) { + res(i) = None + } else if (isPrimitiveType(implMethodArgTypes(i)) && invokeArgTypes(i).getDescriptor == ObjectRef.descriptor) { + res(i) = Some(unboxOp(implMethodArgTypes(i))) + } else if (isPrimitiveType(invokeArgTypes(i)) && implMethodArgTypes(i).getDescriptor == ObjectRef.descriptor) { + res(i) = Some(boxOp(invokeArgTypes(i))) + } else { + assert(!isPrimitiveType(invokeArgTypes(i)), invokeArgTypes(i)) + assert(!isPrimitiveType(implMethodArgTypes(i)), implMethodArgTypes(i)) + // The comment in the unapply method of `LambdaMetaFactoryCall` explains why we have to introduce + // casts for arguments that have different types in samMethodType and instantiatedMethodType. + // + // Note: + // - invokeArgTypes is the same as the argument types in the IndyLambda's samMethodType, + // this is ensured by the `isSamInvocation` filter in this file + // - implMethodArgTypes is the same as the arg types in the IndyLambda's instantiatedMethodType, + // this is ensured by the unapply method in LambdaMetaFactoryCall (file CallGraph) + res(i) = Some(new TypeInsnNode(CHECKCAST, implMethodArgTypes(i).getInternalName)) + } + } + res } } @@ -196,7 +294,7 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { val lambdaBodyHandle = closureInit.lambdaMetaFactoryCall.implMethod // store arguments - insertStoreOps(invocation, ownerMethod, argumentLocalsList) + insertStoreOps(invocation, ownerMethod, argumentLocalsList, adaptStoredArguments(closureInit, invocation)) // drop the closure from the stack ownerMethod.instructions.insertBefore(invocation, new InsnNode(POP)) @@ -228,8 +326,22 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { val bodyInvocation = new MethodInsnNode(bodyOpcode, lambdaBodyHandle.getOwner, lambdaBodyHandle.getName, lambdaBodyHandle.getDesc, isInterface) ownerMethod.instructions.insertBefore(invocation, bodyInvocation) - val returnType = Type.getReturnType(lambdaBodyHandle.getDesc) - fixLoadedNothingOrNullValue(returnType, bodyInvocation, ownerMethod, btypes) // see comment of that method + val bodyReturnType = Type.getReturnType(lambdaBodyHandle.getDesc) + val invocationReturnType = Type.getReturnType(invocation.desc) + if (isPrimitiveType(invocationReturnType) && bodyReturnType.getDescriptor == ObjectRef.descriptor) { + val op = + if (invocationReturnType.getSort == Type.VOID) getPop(1) + else unboxOp(invocationReturnType) + ownerMethod.instructions.insertBefore(invocation, op) + } else if (isPrimitiveType(bodyReturnType) && invocationReturnType.getDescriptor == ObjectRef.descriptor) { + val op = + if (bodyReturnType.getSort == Type.VOID) getBoxedUnit + else boxOp(bodyReturnType) + ownerMethod.instructions.insertBefore(invocation, op) + } else { + // see comment of that method + fixLoadedNothingOrNullValue(bodyReturnType, bodyInvocation, ownerMethod, btypes) + } ownerMethod.instructions.remove(invocation) @@ -277,6 +389,9 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { // Rewriting a closure invocation may render code unreachable. For example, the body method of // (x: T) => ??? has return type Nothing$, and an ATHROW is added (see fixLoadedNothingOrNullValue). unreachableCodeEliminated -= ownerMethod + + if (hasAdaptedImplMethod(closureInit) && inliner.canInlineBody(bodyMethodCallsite).isEmpty) + inliner.inlineCallsite(bodyMethodCallsite) } /** @@ -293,13 +408,10 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { // local. On the other hand, further optimizations (copy propagation, remove unused locals) will // clean it up. - // Captured variables don't need to be cast when loaded at the callsite (castLoadTypes are None). - // This is checked in `isClosureInstantiation`: the types of the captured variables in the indy - // instruction match exactly the corresponding parameter types in the body method. - val localsForCaptures = LocalsList.fromTypes(firstCaptureLocal, capturedTypes, castLoadTypes = _ => None) + val localsForCaptures = LocalsList.fromTypes(firstCaptureLocal, capturedTypes) closureInit.ownerMethod.maxLocals = firstCaptureLocal + localsForCaptures.size - insertStoreOps(indy, closureInit.ownerMethod, localsForCaptures) + insertStoreOps(indy, closureInit.ownerMethod, localsForCaptures, _ => None) insertLoadOps(indy, closureInit.ownerMethod, localsForCaptures) localsForCaptures @@ -311,8 +423,16 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { * * The lowest stack value is stored in the head of the locals list, so the last local is stored first. */ - private def insertStoreOps(before: AbstractInsnNode, methodNode: MethodNode, localsList: LocalsList) = - insertLocalValueOps(before, methodNode, localsList, store = true) + private def insertStoreOps(before: AbstractInsnNode, methodNode: MethodNode, localsList: LocalsList, beforeStore: Int => Option[AbstractInsnNode]) = { + // The first instruction needs to store into the last local of the `localsList`. + // To avoid reversing the list, we use `insert(previous)`. + val previous = before.getPrevious + def ins(op: AbstractInsnNode) = methodNode.instructions.insert(previous, op) + for ((l, i) <- localsList.locals.zipWithIndex) { + ins(new VarInsnNode(l.storeOpcode, l.local)) + beforeStore(i) foreach ins + } + } /** * Insert load operations in front of the `before` instruction to copy the local values denoted @@ -320,20 +440,10 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { * * The head of the locals list will be the lowest value on the stack, so the first local is loaded first. */ - private def insertLoadOps(before: AbstractInsnNode, methodNode: MethodNode, localsList: LocalsList) = - insertLocalValueOps(before, methodNode, localsList, store = false) - - private def insertLocalValueOps(before: AbstractInsnNode, methodNode: MethodNode, localsList: LocalsList, store: Boolean): Unit = { - // If `store` is true, the first instruction needs to store into the last local of the `localsList`. - // Load instructions on the other hand are emitted in the order of the list. - // To avoid reversing the list, we use `insert(previousInstr)` for stores and `insertBefore(before)` for loads. - lazy val previous = before.getPrevious + private def insertLoadOps(before: AbstractInsnNode, methodNode: MethodNode, localsList: LocalsList) = { for (l <- localsList.locals) { - val varOp = new VarInsnNode(if (store) l.storeOpcode else l.loadOpcode, l.local) - if (store) methodNode.instructions.insert(previous, varOp) - else methodNode.instructions.insertBefore(before, varOp) - if (!store) for (castType <- l.castLoadedValue) - methodNode.instructions.insert(varOp, new TypeInsnNode(CHECKCAST, castType.getInternalName)) + val op = new VarInsnNode(l.loadOpcode, l.local) + methodNode.instructions.insertBefore(before, op) } } @@ -355,12 +465,12 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { * Local(6, refOpOffset) :: * Nil */ - def fromTypes(firstLocal: Int, types: Array[Type], castLoadTypes: Int => Option[Type]): LocalsList = { + def fromTypes(firstLocal: Int, types: Array[Type]): LocalsList = { var sizeTwoOffset = 0 val locals: List[Local] = types.indices.map(i => { // The ASM method `type.getOpcode` returns the opcode for operating on a value of `type`. val offset = types(i).getOpcode(ILOAD) - ILOAD - val local = Local(firstLocal + i + sizeTwoOffset, offset, castLoadTypes(i)) + val local = Local(firstLocal + i + sizeTwoOffset, offset) if (local.size == 2) sizeTwoOffset += 1 local })(collection.breakOut) @@ -374,10 +484,15 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) { * The xLOAD / xSTORE opcodes are in the following sequence: I, L, F, D, A, so the offset for * a local variable holding a reference (`A`) is 4. See also method `getOpcode` in [[scala.tools.asm.Type]]. */ - case class Local(local: Int, opcodeOffset: Int, castLoadedValue: Option[Type]) { + case class Local(local: Int, opcodeOffset: Int) { def size = if (loadOpcode == LLOAD || loadOpcode == DLOAD) 2 else 1 def loadOpcode = ILOAD + opcodeOffset def storeOpcode = ISTORE + opcodeOffset } } + +object ClosureOptimizer { + val primitives = "BSIJCFDZV" + val specializationSuffix = s"(\\$$mc[$primitives]+\\$$sp)" +} |