diff options
Diffstat (limited to 'src/compiler')
14 files changed, 1008 insertions, 116 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeIdiomatic.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeIdiomatic.scala index a25f5cad63..535e1a8620 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeIdiomatic.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeIdiomatic.scala @@ -436,7 +436,7 @@ abstract class BCodeIdiomatic extends SubComponent { else { emitTypeBased(JCodeMethodN.returnOpcodes, tk) } } - /* Emits one of tableswitch or lookoupswitch. + /* Emits one of tableswitch or lookupswitch. * * can-multi-thread */ diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala index 0f67852804..d2d510e8a9 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeSkelBuilder.scala @@ -140,7 +140,7 @@ abstract class BCodeSkelBuilder extends BCodeHelpers { if (AsmUtils.traceClassEnabled && cnode.name.contains(AsmUtils.traceClassPattern)) AsmUtils.traceClass(cnode) - if (settings.YoptInlinerEnabled) { + if (settings.YoptAddToBytecodeRepository) { // The inliner needs to find all classes in the code repo, also those being compiled byteCodeRepository.add(cnode, ByteCodeRepository.CompilationUnit) } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala index 176292669c..7f0aaa7305 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala @@ -44,6 +44,8 @@ abstract class BTypes { val inliner: Inliner[this.type] + val closureOptimizer: ClosureOptimizer[this.type] + val callGraph: CallGraph[this.type] val backendReporting: BackendReporting @@ -940,7 +942,7 @@ abstract class BTypes { */ def jvmWiseLUB(other: ClassBType): Either[NoClassBTypeInfo, ClassBType] = { def isNotNullOrNothing(c: ClassBType) = !c.isNullType && !c.isNothingType - assert(isNotNullOrNothing(this) && isNotNullOrNothing(other), s"jvmWiseLub for null or nothing: $this - $other") + assert(isNotNullOrNothing(this) && isNotNullOrNothing(other), s"jvmWiseLUB for null or nothing: $this - $other") tryEither { val res: ClassBType = (this.isInterface.orThrow, other.isInterface.orThrow) match { @@ -965,7 +967,7 @@ abstract class BTypes { firstCommonSuffix(this :: this.superClassesTransitive.orThrow, other :: other.superClassesTransitive.orThrow) } - assert(isNotNullOrNothing(res), s"jvmWiseLub computed: $res") + assert(isNotNullOrNothing(res), s"jvmWiseLUB computed: $res") Right(res) } } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala index d68c916f09..5f8f0e167c 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala @@ -7,7 +7,7 @@ package scala.tools.nsc package backend.jvm import scala.tools.asm -import scala.tools.nsc.backend.jvm.opt.{LocalOpt, CallGraph, Inliner, ByteCodeRepository} +import scala.tools.nsc.backend.jvm.opt._ import scala.tools.nsc.backend.jvm.BTypes.{InlineInfo, MethodInlineInfo, InternalName} import BackendReporting._ import scala.tools.nsc.settings.ScalaSettings @@ -42,6 +42,8 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes { val inliner: Inliner[this.type] = new Inliner(this) + val closureOptimizer: ClosureOptimizer[this.type] = new ClosureOptimizer(this) + val callGraph: CallGraph[this.type] = new CallGraph(this) val backendReporting: BackendReporting = new BackendReportingImpl(global) diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BackendReporting.scala b/src/compiler/scala/tools/nsc/backend/jvm/BackendReporting.scala index d641f708d2..4fc05cafdc 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BackendReporting.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BackendReporting.scala @@ -247,6 +247,28 @@ object BackendReporting { callsiteClass: InternalName, callsiteName: String, callsiteDesc: String) extends CannotInlineWarning /** + * Used in `rewriteClosureApplyInvocations` when a closure apply callsite cannot be rewritten + * to the closure body method. + */ + trait RewriteClosureApplyToClosureBodyFailed extends OptimizerWarning { + def pos: Position + + override def emitWarning(settings: ScalaSettings): Boolean = this match { + case RewriteClosureAccessCheckFailed(_, cause) => cause.emitWarning(settings) + case RewriteClosureIllegalAccess(_, _) => settings.YoptWarningEmitAtInlineFailed + } + + override def toString: String = this match { + case RewriteClosureAccessCheckFailed(_, cause) => + s"Failed to rewrite the closure invocation to its implementation method:\n" + cause + case RewriteClosureIllegalAccess(_, callsiteClass) => + s"The closure body invocation cannot be rewritten because the target method is not accessible in class $callsiteClass." + } + } + case class RewriteClosureAccessCheckFailed(pos: Position, cause: OptimizerWarning) extends RewriteClosureApplyToClosureBodyFailed + case class RewriteClosureIllegalAccess(pos: Position, callsiteClass: InternalName) extends RewriteClosureApplyToClosureBodyFailed + + /** * Used in the InlineInfo of a ClassBType, when some issue occurred obtaining the inline information. */ sealed trait ClassInlineInfoWarning extends OptimizerWarning { diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala index a33725ed34..16e8aee1dd 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala @@ -216,12 +216,17 @@ abstract class GenBCode extends BCodeSyncAndTry { class Worker2 { def runGlobalOptimizations(): Unit = { import scala.collection.convert.decorateAsScala._ - q2.asScala foreach { - case Item2(_, _, plain, _, _) => - // skip mirror / bean: wd don't inline into tem, and they are not used in the plain class - if (plain != null) callGraph.addClass(plain) + if (settings.YoptBuildCallGraph) { + q2.asScala foreach { + case Item2(_, _, plain, _, _) => + // skip mirror / bean: wd don't inline into tem, and they are not used in the plain class + if (plain != null) callGraph.addClass(plain) + } } - bTypes.inliner.runInliner() + if (settings.YoptInlinerEnabled) + bTypes.inliner.runInliner() + if (settings.YoptClosureElimination) + closureOptimizer.rewriteClosureApplyInvocations() } def localOptimizations(classNode: ClassNode): Unit = { @@ -229,7 +234,7 @@ abstract class GenBCode extends BCodeSyncAndTry { } def run() { - if (settings.YoptInlinerEnabled) runGlobalOptimizations() + runGlobalOptimizations() while (true) { val item = q2.poll diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala index 98e93c125b..8d8ea839e6 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala @@ -94,7 +94,7 @@ object InstructionStackEffect { val isSize2 = peekStack(0).getSize == 2 if (isSize2) t(1, 0) else t(2, 0) - case DUP => t(0, 1) + case DUP => t(1, 2) case DUP_X1 => t(2, 3) @@ -104,7 +104,7 @@ object InstructionStackEffect { case DUP2 => val isSize2 = peekStack(0).getSize == 2 - if (isSize2) t(0, 1) else t(0, 2) + if (isSize2) t(1, 2) else t(2, 4) case DUP2_X1 => val isSize2 = peekStack(0).getSize == 2 diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzer.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzer.scala new file mode 100644 index 0000000000..ad75363102 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzer.scala @@ -0,0 +1,450 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2015 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.tools.nsc +package backend.jvm +package analysis + +import java.util + +import scala.annotation.switch +import scala.collection.mutable +import scala.tools.asm.{Type, MethodVisitor} +import scala.tools.asm.Opcodes._ +import scala.tools.asm.tree._ +import scala.tools.asm.tree.analysis._ +import scala.tools.nsc.backend.jvm.BTypes.InternalName + +import opt.BytecodeUtils._ + +import scala.collection.convert.decorateAsScala._ + +/** + * This class provides additional queries over ASM's built-in `SourceValue` analysis. + * + * The analysis computes for each value in a frame a set of source instructions, which are the + * potential producers. Most instructions produce either nothing or a stack value. For example, + * a `LOAD` instruction is the producer of the value pushed onto the stack. The exception are + * `STORE` instructions, which produce a new value for a local variable slot, so they are used + * as producers for the value they stored. + * + * Note that pseudo-instructions are used as initial producers for parameters and local variables. + * See the documentation on class InitialProducer. + * + * This class implements the following queries over the data computed by the SourceValue analysis: + * + * - producersForValueAt(insn, slot) + * - consumersOfValueAt(insn, slot) + * + * - producersForInputsOf(insn) + * - consumersOfOutputsFrom(insn) + * + * - initialProducersForValueAt(insn, slot) + * - ultimateConsumersOfValueAt(insn, slot) + * + * - initialProducersForInputsOf(insn) + * - ultimateConsumersOfOutputsFrom(insn) + * + * The following operations are considered as copying operations: + * - xLOAD, xSTORE + * - DUP, DUP2, DUP_X1, DUP_X2, DUP2_X1, DUP2_X2 + * - SWAP + * - CHECKCAST + * + * If ever needed, we could introduce a mode where primitive conversions (l2i) are considered as + * copying operations. + */ +class ProdConsAnalyzer(methodNode: MethodNode, classInternalName: InternalName) { + val analyzer = new Analyzer(new InitialProducerSourceInterpreter) + analyzer.analyze(classInternalName, methodNode) + + def frameAt(insn: AbstractInsnNode) = analyzer.frameAt(insn, methodNode) + + /** + * Returns the potential producer instructions of a (local or stack) value in the frame of `insn`. + * This method simply returns the producer information computed by the SourceValue analysis. + */ + def producersForValueAt(insn: AbstractInsnNode, slot: Int): Set[AbstractInsnNode] = { + frameAt(insn).getValue(slot).insns.asScala.toSet + } + + /** + * Returns the potential consumer instructions of a (local or stack) value in the frame of `insn`. + * This is the counterpart of `producersForValueAt`. + */ + def consumersOfValueAt(insn: AbstractInsnNode, slot: Int): Set[AbstractInsnNode] = { + producersForValueAt(insn, slot).flatMap(prod => { + val outputNumber = outputValueSlots(prod).indexOf(slot) + _consumersOfOutputsFrom.get(prod).map(v => { + v(outputNumber) + }).getOrElse(Set.empty) + }) + } + + /** + * Returns the potential producer instructions of any of the values consumed by `insn`. + */ + def producersForInputsOf(insn: AbstractInsnNode): Set[AbstractInsnNode] = { + inputValues(insn).iterator.flatMap(v => v.insns.asScala).toSet + } + + def consumersOfOutputsFrom(insn: AbstractInsnNode): Set[AbstractInsnNode] = + _consumersOfOutputsFrom.get(insn).map(v => v.indices.flatMap(v.apply)(collection.breakOut): Set[AbstractInsnNode]).getOrElse(Set.empty) + + /** + * Returns the potential initial producer instructions of a value in the frame of `insn`. + * + * Unlike `producersForValueAt`, producers are tracked through copying instructions such as STORE + * and LOAD. If the producer of the value is a LOAD, then the producers of the stored value(s) are + * returned instead. + */ + def initialProducersForValueAt(insn: AbstractInsnNode, slot: Int): Set[AbstractInsnNode] = { + def initialProducers(insn: AbstractInsnNode, producedSlot: Int): Set[AbstractInsnNode] = { + if (isCopyOperation(insn)) { + _initialProducersCache.getOrElseUpdate((insn, producedSlot), { + val (sourceValue, sourceValueSlot) = copyOperationSourceValue(insn, producedSlot) + sourceValue.insns.iterator.asScala.flatMap(initialProducers(_, sourceValueSlot)).toSet + }) + } else { + Set(insn) + } + } + producersForValueAt(insn, slot).flatMap(initialProducers(_, slot)) + } + + /** + * Returns the potential ultimate consumers of a value in the frame of `insn`. Consumers are + * tracked through copying operations such as SOTRE and LOAD. + */ + def ultimateConsumersOfValueAt(insn: AbstractInsnNode, slot: Int): Set[AbstractInsnNode] = { + def ultimateConsumers(insn: AbstractInsnNode, consumedSlot: Int): Set[AbstractInsnNode] = { + if (isCopyOperation(insn)) { + _ultimateConsumersCache.getOrElseUpdate((insn, consumedSlot), { + for { + producedSlot <- copyOperationProducedValueSlots(insn, consumedSlot) + consumer <- consumersOfValueAt(insn.getNext, producedSlot) + ultimateConsumer <- ultimateConsumers(consumer, producedSlot) + } yield ultimateConsumer + }) + } else { + Set(insn) + } + } + consumersOfValueAt(insn, slot).flatMap(ultimateConsumers(_, slot)) + } + + def initialProducersForInputsOf(insn: AbstractInsnNode): Set[AbstractInsnNode] = { + inputValueSlots(insn).flatMap(slot => initialProducersForValueAt(insn, slot)).toSet + } + + def ultimateConsumersOfOutputsFrom(insn: AbstractInsnNode): Set[AbstractInsnNode] = { + lazy val next = insn.getNext + outputValueSlots(insn).flatMap(slot => ultimateConsumersOfValueAt(next, slot)).toSet + } + + private def isCopyOperation(insn: AbstractInsnNode): Boolean = { + isVarInstruction(insn) || { + (insn.getOpcode: @switch) match { + case DUP | DUP_X1 | DUP_X2 | DUP2 | DUP2_X1 | DUP2_X2 | SWAP | CHECKCAST => true + case _ => false + } + } + } + + /** + * Returns the value and its frame slot that `copyOp` copies into `producedSlot`. + * + * Example: + * - copyOp = DUP_X1, assume it produces slots 2,3,4 + * - producedSlot = 3 + * - the result is the value at slot 2 in the frame of `copyOp` + */ + private def copyOperationSourceValue(copyOp: AbstractInsnNode, producedSlot: Int): (SourceValue, Int) = { + val frame = frameAt(copyOp) + + // Index of the produced value. Example: DUP_X1 produces 3 values, so producedIndex is 0, 1 or 2, + // where 0 corresponds to the lowest value on the stack. + def producedIndex(numConsumed: Int) = { + val numUsedSlotsBeforeCopy = frame.stackTop + 1 + producedSlot - (numUsedSlotsBeforeCopy - numConsumed) + } + + def stackValue(n: Int) = (frame.peekStack(n), frame.stackTop - n) + + def dupX1Case = (producedIndex(2): @switch) match { + case 0 | 2 => stackValue(0) + case 1 => stackValue(1) + } + + // Form 1 of dup_x2 + def dupX2Case = (producedIndex(3): @switch) match { + case 0 | 3 => stackValue(0) + case 1 => stackValue(2) + case 2 => stackValue(1) + } + + // Form 1 of dup2_x1 + def dup2X1Case = (producedIndex(3): @switch) match { + case 0 | 3 => stackValue(1) + case 1 | 4 => stackValue(0) + case 2 => stackValue(2) + } + + if (isLoad(copyOp)) { + val slot = copyOp.asInstanceOf[VarInsnNode].`var` + (frame.getLocal(slot), slot) + } else if (isStore(copyOp)) { + stackValue(0) + } else (copyOp.getOpcode: @switch) match { + case DUP => + stackValue(0) // the current stack top is the source of both produced values + + case DUP_X1 => + dupX1Case + + case DUP_X2 => + if (frame.peekStack(1).getSize == 2) dupX1Case + else dupX2Case + + case DUP2 => + if (frame.peekStack(0).getSize == 2) stackValue(0) + else { + (producedIndex(2): @switch) match { + case 0 | 2 => stackValue(1) + case 1 | 3 => stackValue(0) + } + } + + case DUP2_X1 => + if (frame.peekStack(0).getSize == 2) dupX1Case + else dup2X1Case + + case DUP2_X2 => + val v1isSize2 = frame.peekStack(0).getSize == 2 + if (v1isSize2) { + val v2isSize2 = frame.peekStack(1).getSize == 2 + if (v2isSize2) dupX1Case // Form 4 + else dupX2Case // Form 2 + } else { + val v3isSize2 = frame.peekStack(2).getSize == 2 + if (v3isSize2) dup2X1Case // Form 3 + else { + // Form 1 + (producedIndex(4): @switch) match { + case 0 | 4 => stackValue(1) + case 1 | 5 => stackValue(0) + case 2 => stackValue(3) + case 3 => stackValue(2) + } + } + } + + case SWAP => + if (producedIndex(2) == 0) stackValue(0) + else stackValue(1) + + case CHECKCAST => + stackValue(0) + } + } + + /** + * Returns the value slots into which `copyOp` copies the value at `consumedSlot`. + * + * Example: + * - copyOp = DUP_X1, assume it consumes slots 2,3 and produces 2,3,4 + * - if consumedSlot == 2, the result is Set(3) + * - if consumedSlot == 3, the result is Set(2, 4) + */ + private def copyOperationProducedValueSlots(copyOp: AbstractInsnNode, consumedSlot: Int): Set[Int] = { + if (isStore(copyOp)) Set(copyOp.asInstanceOf[VarInsnNode].`var`) + else { + val nextFrame = frameAt(copyOp.getNext) + val top = nextFrame.stackTop + + // Index of the consumed value. Example: DUP_X1 consumes two values, so consumedIndex is + // 0 or 1, where 0 corresponds to the lower value on the stack. + def consumedIndex(numProduced: Int) = { + val numUsedSlotsAfterCopy = top + 1 + consumedSlot - (numUsedSlotsAfterCopy - numProduced) + } + + def dupX1Case = (consumedIndex(3): @switch) match { + case 0 => Set(top - 1) + case 1 => Set(top - 2, top) + } + + def dupX2Case = (consumedIndex(4): @switch) match { + case 0 => Set(top - 2) + case 1 => Set(top - 1) + case 2 => Set(top - 3, top) + } + + def dup2X1Case = (consumedIndex(5): @switch) match { + case 0 => Set(top - 2) + case 1 => Set(top - 4, top - 1) + case 2 => Set(top - 3, top) + } + + if (isLoad(copyOp)) Set(top) + else (copyOp.getOpcode: @switch) match { + case DUP => + Set(top - 1, top) + + case DUP_X1 => + dupX1Case + + case DUP_X2 => + if (nextFrame.peekStack(1).getSize == 2) dupX1Case + else dupX2Case + + case DUP2 => + if (nextFrame.peekStack(0).getSize == 2) Set(top - 1, top) + else (consumedIndex(4): @switch) match { + case 0 => Set(top - 3, top - 1) + case 1 => Set(top - 2, top) + } + + case DUP2_X1 => + if (nextFrame.peekStack(0).getSize == 2) dupX1Case + else dup2X1Case + + case DUP2_X2 => + val v1isSize2 = nextFrame.peekStack(0).getSize == 2 + if (v1isSize2) { + val v2isSize2 = nextFrame.peekStack(1).getSize == 2 + if (v2isSize2) dupX1Case // Form 4 + else dupX2Case // Form 2 + } else { + val v3isSize2 = nextFrame.peekStack(2).getSize == 2 + if (v3isSize2) dup2X1Case // Form 3 + else { + // Form 1 + (consumedIndex(6): @switch) match { + case 0 => Set(top - 3) + case 1 => Set(top - 2) + case 2 => Set(top - 5, top - 1) + case 3 => Set(top - 4, top) + } + } + } + + case SWAP => + if (consumedIndex(2) == 0) Set(top) + else Set(top - 1) + + case CHECKCAST => + Set(top) + } + } + } + + /** Returns the frame values consumed by executing `insn`. */ + private def inputValues(insn: AbstractInsnNode): Seq[SourceValue] = { + lazy val frame = frameAt(insn) + inputValueSlots(insn) map frame.getValue + } + + /** Returns the frame slots holding the values consumed by executing `insn`. */ + private def inputValueSlots(insn: AbstractInsnNode): Seq[Int] = { + if (insn.getOpcode == -1) return Seq.empty + if (isLoad(insn)) { + Seq(insn.asInstanceOf[VarInsnNode].`var`) + } else if (insn.getOpcode == IINC) { + Seq(insn.asInstanceOf[IincInsnNode].`var`) + } else { + val frame = frameAt(insn) + val stackEffect = InstructionStackEffect(insn, frame) + val stackSize = frame.getLocals + frame.getStackSize + (stackSize - stackEffect._1) until stackSize + } + } + + /** Returns the frame slots holding the values produced by executing `insn`. */ + private def outputValueSlots(insn: AbstractInsnNode): Seq[Int] = insn match { + case ParameterProducer(local) => Seq(local) + case UninitializedLocalProducer(local) => Seq(local) + case ExceptionProducer(frame) => Seq(frame.stackTop) + case _ => + if (insn.getOpcode == -1) return Seq.empty + if (isStore(insn)) { + Seq(insn.asInstanceOf[VarInsnNode].`var`) + } else if (insn.getOpcode == IINC) { + Seq(insn.asInstanceOf[IincInsnNode].`var`) + } else { + val frame = frameAt(insn) + val stackEffect = InstructionStackEffect(insn, frame) + val nextFrame = frameAt(insn.getNext) + val stackSize = nextFrame.getLocals + nextFrame.getStackSize + (stackSize - stackEffect._2) until stackSize + } + } + + /** For each instruction, a set of potential consumers of the produced values. */ + private lazy val _consumersOfOutputsFrom: Map[AbstractInsnNode, Vector[Set[AbstractInsnNode]]] = { + var res = Map.empty[AbstractInsnNode, Vector[Set[AbstractInsnNode]]] + for { + insn <- methodNode.instructions.iterator.asScala + frame = frameAt(insn) + i <- inputValueSlots(insn) + producer <- frame.getValue(i).insns.asScala + } { + val producedSlots = outputValueSlots(producer) + val currentConsumers = res.getOrElse(producer, Vector.fill(producedSlots.size)(Set.empty[AbstractInsnNode])) + val outputIndex = producedSlots.indexOf(i) + res = res.updated(producer, currentConsumers.updated(outputIndex, currentConsumers(outputIndex) + insn)) + } + res + } + + private val _initialProducersCache: mutable.AnyRefMap[(AbstractInsnNode, Int), Set[AbstractInsnNode]] = mutable.AnyRefMap.empty + private val _ultimateConsumersCache: mutable.AnyRefMap[(AbstractInsnNode, Int), Set[AbstractInsnNode]] = mutable.AnyRefMap.empty +} + +/** + * A class for pseudo-instructions representing the initial producers of local values that have + * no producer instruction in the method: + * - parameters, including `this` + * - uninitialized local variables + * - exception values in handlers + * + * The ASM built-in SourceValue analysis yields an empty producers set for such values. This leads + * to ambiguities. Example (in Java one can re-assign parameter): + * + * void foo(int a) { + * if (a == 0) a = 1; + * return a; + * } + * + * In the first frame of the method, the SoruceValue for parameter `a` gives an empty set of + * producer instructions. + * + * In the frame of the `IRETURN` instruction, the SoruceValue for parameter `a` lists a single + * producer instruction: the `ISTORE 1`. This makes it look as if there was a single producer for + * `a`, where in fact it might still hold the parameter's initial value. + */ +abstract class InitialProducer extends AbstractInsnNode(-1) { + override def getType: Int = throw new UnsupportedOperationException + override def clone(labels: util.Map[LabelNode, LabelNode]): AbstractInsnNode = throw new UnsupportedOperationException + override def accept(cv: MethodVisitor): Unit = throw new UnsupportedOperationException +} + +case class ParameterProducer(local: Int) extends InitialProducer +case class UninitializedLocalProducer(local: Int) extends InitialProducer +case class ExceptionProducer[V <: Value](handlerFrame: Frame[V]) extends InitialProducer + +class InitialProducerSourceInterpreter extends SourceInterpreter { + override def newParameterValue(isInstanceMethod: Boolean, local: Int, tp: Type): SourceValue = { + new SourceValue(tp.getSize, ParameterProducer(local)) + } + + override def newEmptyNonParameterLocalValue(local: Int): SourceValue = { + new SourceValue(1, UninitializedLocalProducer(local)) + } + + override def newExceptionValue(tryCatchBlockNode: TryCatchBlockNode, handlerFrame: Frame[_ <: Value], exceptionType: Type): SourceValue = { + new SourceValue(1, ExceptionProducer(handlerFrame)) + } +}
\ No newline at end of file diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/ByteCodeRepository.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/ByteCodeRepository.scala index dbf19744fa..a5b85e54e7 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/ByteCodeRepository.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/ByteCodeRepository.scala @@ -102,7 +102,7 @@ class ByteCodeRepository(val classPath: ClassFileLookup[AbstractFile], val isJav } /** - * The method node for a method matching `name` and `descriptor`, accessed in class `classInternalName`. + * The method node for a method matching `name` and `descriptor`, accessed in class `ownerInternalNameOrArrayDescriptor`. * The declaration of the method may be in one of the parents. * * @return The [[MethodNode]] of the requested method and the [[InternalName]] of its declaring 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 9bd016f964..0ec550981a 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala @@ -14,7 +14,6 @@ import scala.tools.asm.commons.CodeSizeEvaluator import scala.tools.asm.tree.analysis._ import scala.tools.asm.{MethodWriter, ClassWriter, Label, Opcodes} import scala.tools.asm.tree._ -import scala.collection.convert.decorateAsScala._ import GenBCode._ import scala.collection.convert.decorateAsScala._ import scala.collection.convert.decorateAsJava._ @@ -73,11 +72,18 @@ object BytecodeUtils { op >= Opcodes.IRETURN && op <= Opcodes.RETURN } - def isVarInstruction(instruction: AbstractInsnNode): Boolean = { + def isLoad(instruction: AbstractInsnNode): Boolean = { val op = instruction.getOpcode - (op >= Opcodes.ILOAD && op <= Opcodes.ALOAD) || (op >= Opcodes.ISTORE && op <= Opcodes.ASTORE) + op >= Opcodes.ILOAD && op <= Opcodes.ALOAD } + def isStore(instruction: AbstractInsnNode): Boolean = { + val op = instruction.getOpcode + op >= Opcodes.ISTORE && op <= Opcodes.ASTORE + } + + def isVarInstruction(instruction: AbstractInsnNode): Boolean = isLoad(instruction) || isStore(instruction) + def isExecutable(instruction: AbstractInsnNode): Boolean = instruction.getOpcode >= 0 def isConstructor(methodNode: MethodNode): Boolean = { 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 0932564b1f..8abecdb261 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala @@ -11,6 +11,7 @@ import scala.reflect.internal.util.{NoPosition, Position} import scala.tools.asm.tree.analysis.{Value, Analyzer, BasicInterpreter} import scala.tools.asm.{Opcodes, Type} import scala.tools.asm.tree._ +import scala.collection.concurrent import scala.collection.convert.decorateAsScala._ import scala.tools.nsc.backend.jvm.BTypes.InternalName import scala.tools.nsc.backend.jvm.BackendReporting._ @@ -21,14 +22,25 @@ import BytecodeUtils._ class CallGraph[BT <: BTypes](val btypes: BT) { import btypes._ - val callsites: collection.concurrent.Map[MethodInsnNode, Callsite] = recordPerRunCache(collection.concurrent.TrieMap.empty[MethodInsnNode, Callsite]) + val callsites: concurrent.Map[MethodInsnNode, Callsite] = recordPerRunCache(concurrent.TrieMap.empty) + + val closureInstantiations: concurrent.Map[InvokeDynamicInsnNode, (MethodNode, ClassBType)] = recordPerRunCache(concurrent.TrieMap.empty) def addClass(classNode: ClassNode): Unit = { - for (m <- classNode.methods.asScala; callsite <- analyzeCallsites(m, classBTypeFromClassNode(classNode))) - callsites(callsite.callsiteInstruction) = callsite + val classType = classBTypeFromClassNode(classNode) + for { + m <- classNode.methods.asScala + (calls, closureInits) = analyzeCallsites(m, classType) + } { + calls foreach (callsite => callsites(callsite.callsiteInstruction) = callsite) + closureInits foreach (indy => closureInstantiations(indy) = (m, classType)) + } } - def analyzeCallsites(methodNode: MethodNode, definingClass: ClassBType): List[Callsite] = { + /** + * Returns a list of callsites in the method, plus a list of closure instantiation indy instructions. + */ + def analyzeCallsites(methodNode: MethodNode, definingClass: ClassBType): (List[Callsite], List[InvokeDynamicInsnNode]) = { case class CallsiteInfo(safeToInline: Boolean, safeToRewrite: Boolean, annotatedInline: Boolean, annotatedNoInline: Boolean, @@ -116,7 +128,10 @@ class CallGraph[BT <: BTypes](val btypes: BT) { case _ => false } - methodNode.instructions.iterator.asScala.collect({ + val callsites = new collection.mutable.ListBuffer[Callsite] + val closureInstantiations = new collection.mutable.ListBuffer[InvokeDynamicInsnNode] + + methodNode.instructions.iterator.asScala foreach { case call: MethodInsnNode => val callee: Either[OptimizerWarning, Callee] = for { (method, declarationClass) <- byteCodeRepository.methodNode(call.owner, call.name, call.desc): Either[OptimizerWarning, (MethodNode, InternalName)] @@ -147,7 +162,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) { receiverNotNullByAnalysis(call, numArgs) } - Callsite( + callsites += Callsite( callsiteInstruction = call, callsiteMethod = methodNode, callsiteClass = definingClass, @@ -157,7 +172,14 @@ class CallGraph[BT <: BTypes](val btypes: BT) { receiverKnownNotNull = receiverNotNull, callsitePosition = callsitePositions.getOrElse(call, NoPosition) ) - }).toList + + case indy: InvokeDynamicInsnNode => + if (closureOptimizer.isClosureInstantiation(indy)) closureInstantiations += indy + + case _ => + } + + (callsites.toList, closureInstantiations.toList) } /** @@ -201,7 +223,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) { * @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 safeToRewrite True if the callee the interface method of a concrete trait method + * @param safeToRewrite True if the callee is the interface method of a concrete trait method * 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 diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala new file mode 100644 index 0000000000..1648a53ed8 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala @@ -0,0 +1,369 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2015 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.tools.nsc +package backend.jvm +package opt + +import scala.annotation.switch +import scala.reflect.internal.util.NoPosition +import scala.tools.asm.{Handle, Type, Opcodes} +import scala.tools.asm.tree._ +import scala.tools.nsc.backend.jvm.BTypes.InternalName +import scala.tools.nsc.backend.jvm.analysis.ProdConsAnalyzer +import BytecodeUtils._ +import BackendReporting._ +import Opcodes._ +import scala.tools.nsc.backend.jvm.opt.ByteCodeRepository.CompilationUnit +import scala.collection.convert.decorateAsScala._ + +class ClosureOptimizer[BT <: BTypes](val btypes: BT) { + import btypes._ + import callGraph._ + + def rewriteClosureApplyInvocations(): Unit = { + closureInstantiations foreach { + case (indy, (methodNode, ownerClass)) => + val warnings = rewriteClosureApplyInvocations(indy, methodNode, ownerClass) + warnings.foreach(w => backendReporting.inlinerWarning(w.pos, w.toString)) + } + } + + private val lambdaMetaFactoryInternalName: InternalName = "java/lang/invoke/LambdaMetafactory" + + private val metafactoryHandle = { + val metafactoryMethodName: String = "metafactory" + val metafactoryDesc: String = "(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;" + new Handle(H_INVOKESTATIC, lambdaMetaFactoryInternalName, metafactoryMethodName, metafactoryDesc) + } + + private val altMetafactoryHandle = { + val altMetafactoryMethodName: String = "altMetafactory" + val altMetafactoryDesc: String = "(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;" + new Handle(H_INVOKESTATIC, lambdaMetaFactoryInternalName, altMetafactoryMethodName, altMetafactoryDesc) + } + + def isClosureInstantiation(indy: InvokeDynamicInsnNode): Boolean = { + (indy.bsm == metafactoryHandle || indy.bsm == altMetafactoryHandle) && + { + indy.bsmArgs match { + case Array(samMethodType: Type, implMethod: Handle, instantiatedMethodType: Type, xs @ _*) => + // LambdaMetaFactory performs a number of automatic adaptations when invoking the lambda + // implementation method (casting, boxing, unboxing, and primitive widening, see Javadoc). + // + // The closure optimizer supports only one of those adaptations: it will cast arguments + // to the correct type when re-writing a closure call to the body method. Example: + // + // val fun: String => String = l => l + // val l = List("") + // fun(l.head) + // + // The samMethodType of Function1 is `(Object)Object`, while the instantiatedMethodType + // is `(String)String`. The return type of `List.head` is `Object`. + // + // The implMethod has the signature `C$anonfun(String)String`. + // + // At the closure callsite, we have an `INVOKEINTERFACE Function1.apply (Object)Object`, + // so the object returned by `List.head` can be directly passed into the call (no cast). + // + // The closure object will cast the object to String before passing it to the implMethod. + // + // 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 + // 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 + // are reference types, so that we can insert casts to perform the same adaptation + // that the closure object would. + + val isStatic = implMethod.getTag == H_INVOKESTATIC + val indyParamTypes = Type.getArgumentTypes(indy.desc) + val instantiatedMethodArgTypes = instantiatedMethodType.getArgumentTypes + val expectedImplMethodType = { + val paramTypes = (if (isStatic) indyParamTypes else indyParamTypes.tail) ++ instantiatedMethodArgTypes + Type.getMethodType(instantiatedMethodType.getReturnType, paramTypes: _*) + } + + { + Type.getType(implMethod.getDesc) == expectedImplMethodType // (1) + } && { + isStatic || implMethod.getOwner == indyParamTypes(0).getInternalName // (2) + } && { + def isReference(t: Type) = t.getSort == Type.OBJECT || t.getSort == Type.ARRAY + (samMethodType.getArgumentTypes, instantiatedMethodArgTypes).zipped forall { + case (samArgType, instArgType) => + samArgType == instArgType || isReference(samArgType) && isReference(instArgType) // (3) + } + } + + case _ => + false + } + } + } + + def isSamInvocation(invocation: MethodInsnNode, indy: InvokeDynamicInsnNode, prodCons: => ProdConsAnalyzer): Boolean = { + if (invocation.getOpcode == INVOKESTATIC) false + else { + def closureIsReceiver = { + val invocationFrame = prodCons.frameAt(invocation) + val receiverSlot = { + val numArgs = Type.getArgumentTypes(invocation.desc).length + invocationFrame.stackTop - numArgs + } + val receiverProducers = prodCons.initialProducersForValueAt(invocation, receiverSlot) + receiverProducers.size == 1 && receiverProducers.head == indy + } + + invocation.name == indy.name && { + val indySamMethodDesc = indy.bsmArgs(0).asInstanceOf[Type].getDescriptor // safe, checked in isClosureInstantiation + indySamMethodDesc == invocation.desc + } && + closureIsReceiver // most expensive check last + } + } + + /** + * Stores the values captured by a closure creation into fresh local variables. + * Returns the list of locals holding the captured values. + */ + private def storeCaptures(indy: InvokeDynamicInsnNode, methodNode: MethodNode): LocalsList = { + val capturedTypes = Type.getArgumentTypes(indy.desc) + val firstCaptureLocal = methodNode.maxLocals + + // This could be optimized: in many cases the captured values are produced by LOAD instructions. + // If the variable is not modified within the method, we could avoid introducing yet another + // 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) + methodNode.maxLocals = firstCaptureLocal + localsForCaptures.size + + insertStoreOps(indy, methodNode, localsForCaptures) + insertLoadOps(indy, methodNode, localsForCaptures) + + localsForCaptures + } + + /** + * Insert store operations in front of the `before` instruction to copy stack values into the + * locals denoted by `localsList`. + * + * 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) + + /** + * Insert load operations in front of the `before` instruction to copy the local values denoted + * by `localsList` onto the stack. + * + * 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 + 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)) + } + } + + def rewriteClosureApplyInvocations(indy: InvokeDynamicInsnNode, methodNode: MethodNode, ownerClass: ClassBType): List[RewriteClosureApplyToClosureBodyFailed] = { + val lambdaBodyHandle = indy.bsmArgs(1).asInstanceOf[Handle] // safe, checked in isClosureInstantiation + + // Kept as a lazy val to make sure the analysis is only computed if it's actually needed. + // ProdCons is used to identify closure body invocations (see isSamInvocation), but only if the + // callsite has the right name and signature. If the method has no invcation instruction with + // the right name and signature, the analysis is not executed. + lazy val prodCons = new ProdConsAnalyzer(methodNode, ownerClass.internalName) + + // First collect all callsites without modifying the instructions list yet. + // Once we start modifying the instruction list, prodCons becomes unusable. + + // A list of callsites and stack heights. If the invocation cannot be rewritten, a warning + // message is stored in the stack height value. + val invocationsToRewrite: List[(MethodInsnNode, Either[RewriteClosureApplyToClosureBodyFailed, Int])] = methodNode.instructions.iterator.asScala.collect({ + case invocation: MethodInsnNode if isSamInvocation(invocation, indy, prodCons) => + val bodyAccessible: Either[OptimizerWarning, Boolean] = for { + (bodyMethodNode, declClass) <- byteCodeRepository.methodNode(lambdaBodyHandle.getOwner, lambdaBodyHandle.getName, lambdaBodyHandle.getDesc): Either[OptimizerWarning, (MethodNode, InternalName)] + isAccessible <- inliner.memberIsAccessible(bodyMethodNode.access, classBTypeFromParsedClassfile(declClass), classBTypeFromParsedClassfile(lambdaBodyHandle.getOwner), ownerClass) + } yield { + isAccessible + } + + def pos = callGraph.callsites.get(invocation).map(_.callsitePosition).getOrElse(NoPosition) + val stackSize: Either[RewriteClosureApplyToClosureBodyFailed, Int] = bodyAccessible match { + case Left(w) => Left(RewriteClosureAccessCheckFailed(pos, w)) + case Right(false) => Left(RewriteClosureIllegalAccess(pos, ownerClass.internalName)) + case _ => Right(prodCons.frameAt(invocation).getStackSize) + } + + (invocation, stackSize) + }).toList + + if (invocationsToRewrite.isEmpty) Nil + else { + // lazy val to make sure locals for captures and arguments are only allocated if there's + // effectively a callsite to rewrite. + lazy val (localsForCapturedValues, argumentLocalsList) = { + val captureLocals = storeCaptures(indy, methodNode) + + // allocate locals for storing the arguments of the closure apply callsites. + // if there are multiple callsites, the same locals are re-used. + val argTypes = indy.bsmArgs(0).asInstanceOf[Type].getArgumentTypes // safe, checked in isClosureInstantiation + val firstArgLocal = methodNode.maxLocals + + // The comment in `isClosureInstantiation` explains why we have to introduce casts for + // arguments that have different types in samMethodType and instantiatedMethodType. + val castLoadTypes = { + val instantiatedMethodType = indy.bsmArgs(2).asInstanceOf[Type] + (argTypes, instantiatedMethodType.getArgumentTypes).zipped map { + case (samArgType, instantiatedArgType) if samArgType != instantiatedArgType => + // isClosureInstantiation 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) + methodNode.maxLocals = firstArgLocal + argLocals.size + + (captureLocals, argLocals) + } + + val warnings = invocationsToRewrite flatMap { + case (invocation, Left(warning)) => Some(warning) + + case (invocation, Right(stackHeight)) => + // store arguments + insertStoreOps(invocation, methodNode, argumentLocalsList) + + // drop the closure from the stack + methodNode.instructions.insertBefore(invocation, new InsnNode(POP)) + + // load captured values and arguments + insertLoadOps(invocation, methodNode, localsForCapturedValues) + insertLoadOps(invocation, methodNode, argumentLocalsList) + + // update maxStack + val capturesStackSize = localsForCapturedValues.size + val invocationStackHeight = stackHeight + capturesStackSize - 1 // -1 because the closure is gone + if (invocationStackHeight > methodNode.maxStack) + methodNode.maxStack = invocationStackHeight + + // replace the callsite with a new call to the body method + val bodyOpcode = (lambdaBodyHandle.getTag: @switch) match { + case H_INVOKEVIRTUAL => INVOKEVIRTUAL + case H_INVOKESTATIC => INVOKESTATIC + case H_INVOKESPECIAL => INVOKESPECIAL + case H_INVOKEINTERFACE => INVOKEINTERFACE + case H_NEWINVOKESPECIAL => + val insns = methodNode.instructions + insns.insertBefore(invocation, new TypeInsnNode(NEW, lambdaBodyHandle.getOwner)) + insns.insertBefore(invocation, new InsnNode(DUP)) + INVOKESPECIAL + } + val isInterface = bodyOpcode == INVOKEINTERFACE + val bodyInvocation = new MethodInsnNode(bodyOpcode, lambdaBodyHandle.getOwner, lambdaBodyHandle.getName, lambdaBodyHandle.getDesc, isInterface) + methodNode.instructions.insertBefore(invocation, bodyInvocation) + methodNode.instructions.remove(invocation) + + // update the call graph + val originalCallsite = callGraph.callsites.remove(invocation) + + // the method node is needed for building the call graph entry + val bodyMethod = byteCodeRepository.methodNode(lambdaBodyHandle.getOwner, lambdaBodyHandle.getName, lambdaBodyHandle.getDesc) + def bodyMethodIsBeingCompiled = byteCodeRepository.classNodeAndSource(lambdaBodyHandle.getOwner).map(_._2 == CompilationUnit).getOrElse(false) + val bodyMethodCallsite = Callsite( + callsiteInstruction = bodyInvocation, + callsiteMethod = methodNode, + callsiteClass = 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) + }), + argInfos = Nil, + callsiteStackHeight = invocationStackHeight, + receiverKnownNotNull = true, // see below (*) + callsitePosition = originalCallsite.map(_.callsitePosition).getOrElse(NoPosition) + ) + // (*) The documentation in class LambdaMetafactory says: + // "if implMethod corresponds to an instance method, the first capture argument + // (corresponding to the receiver) must be non-null" + // Explanation: If the lambda body method is non-static, the receiver is a captured + // value. It can only be captured within some instance method, so we know it's non-null. + callGraph.callsites(bodyInvocation) = bodyMethodCallsite + None + } + + warnings.toList + } + } + + /** + * A list of local variables. Each local stores information about its type, see class [[Local]]. + */ + case class LocalsList(locals: List[Local]) { + val size = locals.iterator.map(_.size).sum + } + + object LocalsList { + /** + * A list of local variables starting at `firstLocal` that can hold values of the types in the + * `types` parameter. + * + * For example, `fromTypes(3, Array(Int, Long, String))` returns + * Local(3, intOpOffset) :: + * Local(4, longOpOffset) :: // note that this local occupies two slots, the next is at 6 + * Local(6, refOpOffset) :: + * Nil + */ + def fromTypes(firstLocal: Int, types: Array[Type], castLoadTypes: Int => Option[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)) + if (local.size == 2) sizeTwoOffset += 1 + local + })(collection.breakOut) + LocalsList(locals) + } + } + + /** + * Stores a local varaible index the opcode offset required for operating on that variable. + * + * 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]) { + def size = if (loadOpcode == LLOAD || loadOpcode == DLOAD) 2 else 1 + + def loadOpcode = ILOAD + opcodeOffset + def storeOpcode = ISTORE + opcodeOffset + } +} 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 b4f091b37f..e8e848161c 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala @@ -26,7 +26,8 @@ class Inliner[BT <: BTypes](val btypes: BT) { def eliminateUnreachableCodeAndUpdateCallGraph(methodNode: MethodNode, definingClass: InternalName): Unit = { localOpt.minimalRemoveUnreachableCode(methodNode, definingClass) foreach { - case invocation: MethodInsnNode => callGraph.callsites.remove(invocation) + case invocation: MethodInsnNode => callGraph.callsites.remove(invocation) + case indy: InvokeDynamicInsnNode => callGraph.closureInstantiations.remove(indy) case _ => } } @@ -432,7 +433,7 @@ 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 + // Add all invocation instructions and closure instantiations that were inlined to the call graph callee.instructions.iterator().asScala foreach { case originalCallsiteIns: MethodInsnNode => callGraph.callsites.get(originalCallsiteIns) match { @@ -452,6 +453,15 @@ class Inliner[BT <: BTypes](val btypes: BT) { case None => } + case indy: InvokeDynamicInsnNode => + callGraph.closureInstantiations.get(indy) match { + case Some((methodNode, ownerClass)) => + val newIndy = instructionMap(indy).asInstanceOf[InvokeDynamicInsnNode] + callGraph.closureInstantiations(newIndy) = (callsiteMethod, callsiteClass) + + case None => + } + case _ => } // Remove the elided invocation from the call graph @@ -529,98 +539,97 @@ class Inliner[BT <: BTypes](val btypes: BT) { } /** - * Returns the first instruction in the `instructions` list that would cause a - * [[java.lang.IllegalAccessError]] when inlined into the `destinationClass`. - * - * If validity of some instruction could not be checked because an error occurred, the instruction - * is returned together with a warning message that describes the problem. + * Check if a type is accessible to some class, as defined in JVMS 5.4.4. + * (A1) C is public + * (A2) C and D are members of the same run-time package */ - def findIllegalAccess(instructions: InsnList, calleeDeclarationClass: ClassBType, destinationClass: ClassBType): Option[(AbstractInsnNode, Option[OptimizerWarning])] = { - - /** - * Check if a type is accessible to some class, as defined in JVMS 5.4.4. - * (A1) C is public - * (A2) C and D are members of the same run-time package - */ - def classIsAccessible(accessed: BType, from: ClassBType = destinationClass): Either[OptimizerWarning, Boolean] = (accessed: @unchecked) match { - // TODO: A2 requires "same run-time package", which seems to be package + classloader (JMVS 5.3.). is the below ok? - case c: ClassBType => c.isPublic.map(_ || c.packageInternalName == from.packageInternalName) - case a: ArrayBType => classIsAccessible(a.elementType, from) - case _: PrimitiveBType => Right(true) - } + def classIsAccessible(accessed: BType, from: ClassBType): Either[OptimizerWarning, Boolean] = (accessed: @unchecked) match { + // TODO: A2 requires "same run-time package", which seems to be package + classloader (JMVS 5.3.). is the below ok? + case c: ClassBType => c.isPublic.map(_ || c.packageInternalName == from.packageInternalName) + case a: ArrayBType => classIsAccessible(a.elementType, from) + case _: PrimitiveBType => Right(true) + } - /** - * Check if a member reference is accessible from the [[destinationClass]], as defined in the - * JVMS 5.4.4. Note that the class name in a field / method reference is not necessarily the - * class in which the member is declared: - * - * class A { def f = 0 }; class B extends A { f } - * - * The INVOKEVIRTUAL instruction uses a method reference "B.f ()I". Therefore this method has - * two parameters: - * - * @param memberDeclClass The class in which the member is declared (A) - * @param memberRefClass The class used in the member reference (B) - * - * (B0) JVMS 5.4.3.2 / 5.4.3.3: when resolving a member of class C in D, the class C is resolved - * first. According to 5.4.3.1, this requires C to be accessible in D. - * - * JVMS 5.4.4 summary: A field or method R is accessible to a class D (destinationClass) iff - * (B1) R is public - * (B2) R is protected, declared in C (memberDeclClass) and D is a subclass of C. - * If R is not static, R must contain a symbolic reference to a class T (memberRefClass), - * such that T is either a subclass of D, a superclass of D, or D itself. - * Also (P) needs to be satisfied. - * (B3) R is either protected or has default access and declared by a class in the same - * run-time package as D. - * If R is protected, also (P) needs to be satisfied. - * (B4) R is private and is declared in D. - * - * (P) When accessing a protected instance member, the target object on the stack (the receiver) - * has to be a subtype of D (destinationClass). This is enforced by classfile verification - * (https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1.8). - * - * TODO: we cannot currently implement (P) because we don't have the necessary information - * available. Once we have a type propagation analysis implemented, we can extract the receiver - * type from there (https://github.com/scala-opt/scala/issues/13). - */ - def memberIsAccessible(memberFlags: Int, memberDeclClass: ClassBType, memberRefClass: ClassBType): Either[OptimizerWarning, Boolean] = { - // TODO: B3 requires "same run-time package", which seems to be package + classloader (JMVS 5.3.). is the below ok? - def samePackageAsDestination = memberDeclClass.packageInternalName == destinationClass.packageInternalName - def targetObjectConformsToDestinationClass = false // needs type propagation analysis, see above - - def memberIsAccessibleImpl = { - val key = (ACC_PUBLIC | ACC_PROTECTED | ACC_PRIVATE) & memberFlags - key match { - case ACC_PUBLIC => // B1 - Right(true) - - case ACC_PROTECTED => // B2 - val isStatic = (ACC_STATIC & memberFlags) != 0 - tryEither { - val condB2 = destinationClass.isSubtypeOf(memberDeclClass).orThrow && { - isStatic || memberRefClass.isSubtypeOf(destinationClass).orThrow || destinationClass.isSubtypeOf(memberRefClass).orThrow - } - Right( - (condB2 || samePackageAsDestination /* B3 (protected) */) && - (isStatic || targetObjectConformsToDestinationClass) // (P) - ) + /** + * Check if a member reference is accessible from the [[destinationClass]], as defined in the + * JVMS 5.4.4. Note that the class name in a field / method reference is not necessarily the + * class in which the member is declared: + * + * class A { def f = 0 }; class B extends A { f } + * + * The INVOKEVIRTUAL instruction uses a method reference "B.f ()I". Therefore this method has + * two parameters: + * + * @param memberDeclClass The class in which the member is declared (A) + * @param memberRefClass The class used in the member reference (B) + * + * (B0) JVMS 5.4.3.2 / 5.4.3.3: when resolving a member of class C in D, the class C is resolved + * first. According to 5.4.3.1, this requires C to be accessible in D. + * + * JVMS 5.4.4 summary: A field or method R is accessible to a class D (destinationClass) iff + * (B1) R is public + * (B2) R is protected, declared in C (memberDeclClass) and D is a subclass of C. + * If R is not static, R must contain a symbolic reference to a class T (memberRefClass), + * such that T is either a subclass of D, a superclass of D, or D itself. + * Also (P) needs to be satisfied. + * (B3) R is either protected or has default access and declared by a class in the same + * run-time package as D. + * If R is protected, also (P) needs to be satisfied. + * (B4) R is private and is declared in D. + * + * (P) When accessing a protected instance member, the target object on the stack (the receiver) + * has to be a subtype of D (destinationClass). This is enforced by classfile verification + * (https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1.8). + * + * TODO: we cannot currently implement (P) because we don't have the necessary information + * available. Once we have a type propagation analysis implemented, we can extract the receiver + * type from there (https://github.com/scala-opt/scala/issues/13). + */ + def memberIsAccessible(memberFlags: Int, memberDeclClass: ClassBType, memberRefClass: ClassBType, from: ClassBType): Either[OptimizerWarning, Boolean] = { + // TODO: B3 requires "same run-time package", which seems to be package + classloader (JMVS 5.3.). is the below ok? + def samePackageAsDestination = memberDeclClass.packageInternalName == from.packageInternalName + def targetObjectConformsToDestinationClass = false // needs type propagation analysis, see above + + def memberIsAccessibleImpl = { + val key = (ACC_PUBLIC | ACC_PROTECTED | ACC_PRIVATE) & memberFlags + key match { + case ACC_PUBLIC => // B1 + Right(true) + + case ACC_PROTECTED => // B2 + val isStatic = (ACC_STATIC & memberFlags) != 0 + tryEither { + val condB2 = from.isSubtypeOf(memberDeclClass).orThrow && { + isStatic || memberRefClass.isSubtypeOf(from).orThrow || from.isSubtypeOf(memberRefClass).orThrow } + Right( + (condB2 || samePackageAsDestination /* B3 (protected) */) && + (isStatic || targetObjectConformsToDestinationClass) // (P) + ) + } - case 0 => // B3 (default access) - Right(samePackageAsDestination) + case 0 => // B3 (default access) + Right(samePackageAsDestination) - case ACC_PRIVATE => // B4 - Right(memberDeclClass == destinationClass) - } + case ACC_PRIVATE => // B4 + Right(memberDeclClass == from) } + } - classIsAccessible(memberDeclClass) match { // B0 - case Right(true) => memberIsAccessibleImpl - case r => r - } + classIsAccessible(memberDeclClass, from) match { // B0 + case Right(true) => memberIsAccessibleImpl + case r => r } + } + /** + * Returns the first instruction in the `instructions` list that would cause a + * [[java.lang.IllegalAccessError]] when inlined into the `destinationClass`. + * + * If validity of some instruction could not be checked because an error occurred, the instruction + * is returned together with a warning message that describes the problem. + */ + def findIllegalAccess(instructions: InsnList, calleeDeclarationClass: ClassBType, destinationClass: ClassBType): Option[(AbstractInsnNode, Option[OptimizerWarning])] = { /** * Check if `instruction` can be transplanted to `destinationClass`. * @@ -637,18 +646,18 @@ class Inliner[BT <: BTypes](val btypes: BT) { // NEW, ANEWARRAY, CHECKCAST or INSTANCEOF. For these instructions, the reference // "must be a symbolic reference to a class, array, or interface type" (JVMS 6), so // it can be an internal name, or a full array descriptor. - classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(ti.desc)) + classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(ti.desc), destinationClass) case ma: MultiANewArrayInsnNode => // "a symbolic reference to a class, array, or interface type" - classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(ma.desc)) + classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(ma.desc), destinationClass) case fi: FieldInsnNode => val fieldRefClass = classBTypeFromParsedClassfile(fi.owner) for { (fieldNode, fieldDeclClassNode) <- byteCodeRepository.fieldNode(fieldRefClass.internalName, fi.name, fi.desc): Either[OptimizerWarning, (FieldNode, InternalName)] fieldDeclClass = classBTypeFromParsedClassfile(fieldDeclClassNode) - res <- memberIsAccessible(fieldNode.access, fieldDeclClass, fieldRefClass) + res <- memberIsAccessible(fieldNode.access, fieldDeclClass, fieldRefClass, destinationClass) } yield { res } @@ -664,7 +673,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { Right(destinationClass == calleeDeclarationClass) case _ => // INVOKEVIRTUAL, INVOKESTATIC, INVOKEINTERFACE and INVOKESPECIAL of constructors - memberIsAccessible(methodFlags, methodDeclClass, methodRefClass) + memberIsAccessible(methodFlags, methodDeclClass, methodRefClass, destinationClass) } } @@ -683,7 +692,7 @@ class Inliner[BT <: BTypes](val btypes: BT) { Right(false) case ci: LdcInsnNode => ci.cst match { - case t: asm.Type => classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(t.getInternalName)) + case t: asm.Type => classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(t.getInternalName), destinationClass) case _ => Right(true) } diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index c83cc28e2a..c9d97a9469 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -234,6 +234,7 @@ trait ScalaSettings extends AbsScalaSettings 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 nullnessTracking = Choice("nullness-tracking", "Track nullness / non-nullness of local variables and apply optimizations.") + val closureElimination = Choice("closure-elimination" , "Rewrite closure invocations to the implementation method and eliminate closures.") 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.") @@ -242,7 +243,7 @@ trait ScalaSettings extends AbsScalaSettings private val defaultChoices = List(unreachableCode) val lDefault = Choice("l:default", "Enable default optimizations: "+ defaultChoices.mkString(","), expandsTo = defaultChoices) - private val methodChoices = List(unreachableCode, simplifyJumps, emptyLineNumbers, emptyLabels, compactLocals, nullnessTracking) + private val methodChoices = List(unreachableCode, simplifyJumps, emptyLineNumbers, emptyLabels, compactLocals, nullnessTracking, closureElimination) val lMethod = Choice("l:method", "Enable intra-method optimizations: "+ methodChoices.mkString(","), expandsTo = methodChoices) private val projectChoices = List(lMethod, inlineProject) @@ -265,11 +266,15 @@ trait ScalaSettings extends AbsScalaSettings def YoptEmptyLabels = Yopt.contains(YoptChoices.emptyLabels) def YoptCompactLocals = Yopt.contains(YoptChoices.compactLocals) def YoptNullnessTracking = Yopt.contains(YoptChoices.nullnessTracking) + def YoptClosureElimination = Yopt.contains(YoptChoices.closureElimination) def YoptInlineProject = Yopt.contains(YoptChoices.inlineProject) def YoptInlineGlobal = Yopt.contains(YoptChoices.inlineGlobal) def YoptInlinerEnabled = YoptInlineProject || YoptInlineGlobal + def YoptBuildCallGraph = YoptInlinerEnabled || YoptClosureElimination + def YoptAddToBytecodeRepository = YoptInlinerEnabled || YoptClosureElimination + val YoptInlineHeuristics = ChoiceSetting( name = "-Yopt-inline-heuristics", helpArg = "strategy", |