diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/backend/jvm/opt/BoxUnbox.scala')
| -rw-r--r-- | src/compiler/scala/tools/nsc/backend/jvm/opt/BoxUnbox.scala | 907 |
1 files changed, 907 insertions, 0 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/BoxUnbox.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/BoxUnbox.scala new file mode 100644 index 0000000000..78fc7e1ecf --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BoxUnbox.scala @@ -0,0 +1,907 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2014 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.tools.nsc +package backend.jvm +package opt + +import scala.annotation.tailrec +import scala.tools.asm.Type +import scala.tools.asm.Opcodes._ +import scala.tools.asm.tree._ +import scala.collection.mutable +import scala.collection.JavaConverters._ +import scala.tools.nsc.backend.jvm.BTypes.InternalName +import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._ + +class BoxUnbox[BT <: BTypes](val btypes: BT) { + import btypes._ + import backendUtils._ + + /** + * Eliminate box-unbox pairs within `method`. Such appear commonly after closure elimination: + * + * def t2 = { + * val f = (b: Byte, i: Int) => i + b // no specialized variant for this function type + * f(1, 2) // invokes the generic `apply` + * } + * + * The closure optimizer re-writes the `apply` call to `anonfun$adapted` method, which takes + * boxed arguments. After inlining this method, we get + * + * def t2 = { + * val a = boxByte(1) + * val b = boxInteger(2) + * val r = boxInteger(anonfun$(unboxByte(a), unboxInt(b))) + * unboxInt(r) + * } + * + * All these box/unbox operations are eliminated here. + * + * Implementation: for every box operation, find all consumers of the boxed value, then all + * producers of these consumers, repeat until reaching a fixpoint. If this results in a set of + * boxing and unboxing operations, the box can be eliminated. + * + * There are two methods for eliminating boxes: + * M1: If there is a single boxing operation, the boxed value(s) are stored into new local + * variable(s) at the allocation site. Accesses to the boxed value are re-written to reads / + * writes of these locals. Advantages: + * - supports mutable boxes (IntRef and friends) + * - supports eliminating unbox operations even if the box object needs to be created + * because it escapes (see E4) + * - works by keeping the unboxed value(s) in locals AND the box in its original form + * - only for immutable boxes: modifications to the escaped box cannot be applied to + * the local variable(s) holding the boxed value(s). + * Restriction: + * - does not work if there are multiple boxing operations (see E1) + * + * M2: If there are multiple boxing operations, the boxing operations are simply eliminated, + * leaving the unboxed value(s) on the stack. Store / load operations that previously + * acted on the box are adapted to handle the boxed type(s). If the box contains multiple + * values (or a size-2 value, which doesn't fit into locals that were used for the box), + * new local slots are used for store / load operations. Restrictions: + * - does not support re-writing writes to (mutable) boxes (see E2) + * - does not support re-writing reads of boxes that also escape (see E3) + * + * + * E1: M1 only works if there's a single boxing operation. + * def e1(b: Boolean) = { + * val i: Integer = box(10) // 10 is stored into a new local, box operation and i removed + * val j: Integer = box(20) // 20 is stored into a new local, box operation and j removed + * val r = if (b) i else j // loads and stores of the box are eliminated, r no longer exists + * unbox(r) // cannot rewrite: we don't know which local to load + * } + * Note: the example has no write and the box does not escape, so M2 works here. + * + * E2: mutable boxes with multiple boxing operations cannot be eliminated. + * M1: see E1 + * M2: cannot replace an `IntRef` on the stack by an `Int` value on the stack, an Int on the + * stack cannot be modified. + * + * def e2(b: Boolean) = { + * val r1 = new IntRef(0) + * val r2 = new IntRef(1) + * val modRef = if (b) r1 else r2 + * modRef.elem += 10 // M1: cannot rewrite: which local to write? same as E1. + * (if (b) r1 else r2).elem += 10 // M2: cannot change an Int on the stack + * (r1.elem, r2.elem) + * } + * + * + * E3: escaping boxes with multiple boxing operations cannot be rewritten. + * M1: see E1. + * M2: at *, instead of an Integer, an Int is on the stack, but the escape method expects an + * Integer. We cannot just create a box at this point: if there are multiple escapes (or + * an escape is executed more than once), the difference could be observed (reference + * equality). + * + * def e3(b: Boolean) = { + * val i: Integer = box(1) + * val j: Integer = box(2) + * escape(if (b) i else j) // * + * unbox(if (b) i else j) + * } + * + * + * E4: M1 supports rewriting unbox operations of immutable boxes that escape + * def e4 = { + * val i: Integer = box(10) // 10 is stored into a new local, loaded as argument for the box call + * escape(i) // not changed, still loads the local i holding the box + * unbox(i) // rewritten to a pop (of the box) and a load of the local variable + * } + * + * + * E4 seems to be a bit of a corner case, but it's necessary to unblock box eliminations with + * mutual dependencies. Example: + * + * val ((a, b), c) = ((1, 2), 3) + * a + b + c + * + * generates (after a few cleanups) the following (pseudo-bytecode, ignoring primitive boxing, specialization): + * + * load 1, load 2, new Tuple2 // stack: Tuple2 + * load 3 // stack: Tuple2; Int + * val local1 = new Tuple2 + * val local2 = local1._1.asInstanceOf[Tuple2] + * val c = local1._2.asInstanceOf[Int] + * if (local2 == null) throw new MatchError(local1) + * val a = local2._1 + * val b = local2._2 + * a + b + c + * + * In order to eliminate the tuples, we first need to eliminate the outer tuple (stored in local1) + * - single box operation, so we use M1 + * - there are three consumers of the outer tuple: `local1._1`, `local1._2` and + * `new MatchError(local1)`. in the last one, the tuple escapes. + * - note that the MatchError creation is dead code: local2 is never null. However, our nullness + * analysis cannot identify this: it does not track nullness through tuple stores and loads. + * - if we re-write the non-escaping consumers of the outer tuple, but keep the tuple allocation + * and the escaping consumer, we get the following: + * + * load 1, load 2 + * val newLocal1 = new Tuple2; load newLocal1 // stack: Tuple2 + * val newLocal2 = 3; load newLocal2 // stack: Tuple2; Int + * val local1 = new Tuple2 + * val local2 = newLocal1 + * val c = newLocal2 + * if (local2 == null) throw new MatchError(local1) + * val a = local2._1 + * val b = local2._2 + * a + b + c + * + * At this point, the nullness analysis sees that `local2 == null` is false, dead code elimination + * removes the `throw new MatchError(local1)`. After eliminating the allocation of the outer tuple, + * the inner tuple (stored in newLocal1) can also be eliminated. + * + * + * Special case for tuples wrt specialization: a tuple getter may box or unbox the value stored + * in the tuple: calling `_1` on a `Tuple2$mcII$sp` boxes the primitive Int stored in the tuple. + * Similarly, calling `_1$mcI$sp` on a non-specialized `Tuple2` unboxes the Integer in the tuple. + * When eliminating such getters, we have to introduce appropriate box / unbox calls. + * + * + * TODO: add new calls (box / unbox) to the call graph (not urgent) + * TODO: update the call graph because stack heights change (not urgent). + * this may also affect other optimizations, we ignored the issue so far. check how stack + * heights stored in the call graph are used. + * Note: these tasks are not urgent because the call graph is not currently used during / after + * method-local optimizations, only before to perform inlining and closure rewriting. + */ + def boxUnboxElimination(method: MethodNode, owner: InternalName): Boolean = { + AsmAnalyzer.sizeOKForSourceValue(method) && { + val toInsertBefore = mutable.Map.empty[AbstractInsnNode, List[AbstractInsnNode]] + val toReplace = mutable.Map.empty[AbstractInsnNode, List[AbstractInsnNode]] + val toDelete = mutable.Set.empty[AbstractInsnNode] + + val knownHandled = mutable.Set.empty[AbstractInsnNode] + + lazy val prodCons = new ProdConsAnalyzer(method, owner) + + var nextLocal = method.maxLocals + def getLocal(size: Int) = { + val r = nextLocal + nextLocal += size + r + } + + var maxStackGrowth = 0 + + /** Method M1 for eliminating box-unbox pairs (see doc comment in the beginning of this file) */ + def replaceBoxOperationsSingleCreation(creation: BoxCreation, finalCons: Set[BoxConsumer], boxKind: BoxKind, keepBox: Boolean): Unit = { + /** + * If the box is eliminated, all copy operations (loads, stores, others) of the box need to + * be removed. This method returns all copy operations that should be removed. + * + * Returns `None` in case some exotic copy operation is found that cannot be removed + * (DUP2_X1 and friends - these are never emitted by scalac). In this case, the box cannot + * be eliminated. + */ + def copyOpsToEliminate: Option[Set[AbstractInsnNode]] = { + var elidableCopyOps = Set.empty[AbstractInsnNode] + var replaceOK = true + val copyOps = new CopyOpsIterator(Set(creation), finalCons, prodCons) + while (replaceOK && copyOps.hasNext) copyOps.next() match { + case vi: VarInsnNode => + elidableCopyOps += vi + + case copyOp if copyOp.getOpcode == DUP => + elidableCopyOps += copyOp + + case _ => + replaceOK = false + } + if (replaceOK) Some(elidableCopyOps) else None + } + + val canRewrite = keepBox || (copyOpsToEliminate match { + case Some(copyOps) => + toDelete ++= copyOps + true + + case _ => false + }) + + if (canRewrite) { + val localSlots: Vector[(Int, Type)] = boxKind.boxedTypes.map(tp => (getLocal(tp.getSize), tp))(collection.breakOut) + + // store boxed value(s) into localSlots + val storeOps = localSlots.toList reverseMap { case (slot, tp) => + new VarInsnNode(tp.getOpcode(ISTORE), slot) + } + val storeInitialValues = creation.loadInitialValues match { + case Some(ops) => ops ::: storeOps + case None => storeOps + } + if (keepBox) { + val loadOps: List[VarInsnNode] = localSlots.map({ case (slot, tp) => + new VarInsnNode(tp.getOpcode(ILOAD), slot) + })(collection.breakOut) + toInsertBefore(creation.valuesConsumer) = storeInitialValues ::: loadOps + } else { + toReplace(creation.valuesConsumer) = storeInitialValues + toDelete ++= creation.allInsns - creation.valuesConsumer + } + + // rewrite consumers + finalCons foreach { + case write: StaticSetterOrInstanceWrite => + assert(!keepBox, s"cannot eliminate box write if the box remains (and escapes): $write") + val (slot, tp) = localSlots(boxKind.extractedValueIndex(write)) + val storeOp = new VarInsnNode(tp.getOpcode(ISTORE), slot) + toReplace(write.consumer) = List(storeOp) + + case c: EscapingConsumer => + assert(keepBox, s"found escaping consumer, but box is eliminated: $c") + + case extraction => + val (slot, tp) = localSlots(boxKind.extractedValueIndex(extraction)) + val loadOps = new VarInsnNode(tp.getOpcode(ILOAD), slot) :: extraction.postExtractionAdaptationOps(tp) + if (keepBox) toReplace(extraction.consumer) = getPop(1) :: loadOps + else toReplace(extraction.consumer) = loadOps + toDelete ++= extraction.allInsns - extraction.consumer + } + } + } + + /** Method M2 for eliminating box-unbox pairs (see doc comment in the beginning of this file) */ + def replaceBoxOperationsMultipleCreations(allCreations: Set[BoxCreation], allConsumers: Set[BoxConsumer], boxKind: BoxKind): Unit = { + /** + * If a single-value size-1 box is eliminated, local variables slots holding the box are + * reused to hold the unboxed value. In case there's an entry for that local variable in the + * method's local variables table (debug info), adapt the type. + * + * If there are multiple entries for a local variable that's changing types, then all + * entries for that variable are deleted - it's not obvious how to find the correct entry. + * Note that scalac never re-uses local variable slots for non-overlapping locals. Also note + * that all locals that are newly created during the optimizer don't have an entry either. + * + * Finally, note that variables that become unused are removed later from the table by + * removeUnusedLocalVariableNodes in LocalOpt. + * + * Unlike modifications that affect the method's instructions (which uses toReplace etc), + * we can directly modify the local variable table - it does not affect the frames of the + * ProdCons analysis. + */ + def updateLocalVariableTypes(reTypedLocals: Map[Int, Type]): Unit = { + lazy val localsByIndex = method.localVariables.asScala.groupBy(_.index) + for ((index, tp) <- reTypedLocals) localsByIndex.get(index).map(_.toList) match { + case Some(List(local)) => + local.desc = tp.getDescriptor + case Some(locals) => + locals foreach method.localVariables.remove + case _ => + } + } + + /** Remove box creations - leave the boxed value(s) on the stack instead. */ + def replaceCreationOps(): Unit = { + for (creation <- allCreations) creation.loadInitialValues match { + case None => + toDelete ++= creation.allInsns + + case Some(ops) => + toReplace(creation.valuesConsumer) = ops + toDelete ++= (creation.allInsns - creation.valuesConsumer) + } + } + + /** + * Replace a value extraction operation. For a single-value box, the extraction operation can + * just be removed. An extraction from a multi-value box is replaced by POP operations for the + * non-used values, and an xSTORE / xLOAD for the extracted value. Example: tuple3._2 becomes + * POP; xSTORE n; POP; xLOAD n. + */ + def replaceExtractionOps(): Unit = { + if (boxKind.boxedTypes.lengthCompare(1) == 0) { + // fast path for single-value boxes + allConsumers.foreach(extraction => extraction.postExtractionAdaptationOps(boxKind.boxedTypes.head) match { + case Nil => + toDelete ++= extraction.allInsns + case ops => + toReplace(extraction.consumer) = ops + toDelete ++= extraction.allInsns - extraction.consumer + }) + } else { + for (extraction <- allConsumers) { + val valueIndex = boxKind.extractedValueIndex(extraction) + val replacementOps = if (valueIndex == 0) { + val pops = boxKind.boxedTypes.tail.map(t => getPop(t.getSize)) + pops ::: extraction.postExtractionAdaptationOps(boxKind.boxedTypes.head) + } else { + var loadOps: List[AbstractInsnNode] = null + val consumeStack = boxKind.boxedTypes.zipWithIndex reverseMap { + case (tp, i) => + if (i == valueIndex) { + val resultSlot = getLocal(tp.getSize) + loadOps = new VarInsnNode(tp.getOpcode(ILOAD), resultSlot) :: extraction.postExtractionAdaptationOps(tp) + new VarInsnNode(tp.getOpcode(ISTORE), resultSlot) + } else { + getPop(tp.getSize) + } + } + consumeStack ::: loadOps + } + toReplace(extraction.consumer) = replacementOps + toDelete ++= extraction.allInsns - extraction.consumer + } + } + } + + checkCopyOpReplacements(allCreations, allConsumers, boxKind.boxedTypes, nextLocal, prodCons) match { + case Some((replacements, nextCopyOpLocal, reTypedLocals)) => + toReplace ++= replacements + updateLocalVariableTypes(reTypedLocals) + nextLocal = nextCopyOpLocal + replaceCreationOps() + replaceExtractionOps() + // Conservative (safe) value for stack growth. In every frame that initially has a multi-value + // box on the stack, the stack now contains all of the individual values. So for every eliminated + // box, the maxStack may be up to N-1 slots larger. + maxStackGrowth += boxKind.boxedTypes.length - 1 + + case None => + } + } + + val it = method.instructions.iterator + while (it.hasNext) { + val insn = it.next() + if (!knownHandled(insn)) BoxKind.valueCreationKind(insn, prodCons) match { + case Some((boxCreation, boxKind)) => + allCreationsConsumers(boxCreation, boxKind, prodCons) match { + case Some((allCreations, allConsumers)) => + val (escapingConsumers, boxConsumers) = allConsumers.partition(_.isEscaping) + if (boxConsumers.nonEmpty) { + for (c <- allCreations) knownHandled ++= c.allInsns + for (e <- allConsumers) knownHandled ++= e.allInsns + + val hasEscaping = escapingConsumers.nonEmpty + val hasWrite = allConsumers.exists(_.isWrite) + if (!hasEscaping && !hasWrite) { + // M2 -- see doc comment in the beginning of this file + // If both M1 and M2 can be applied, we prefer M2 because it doesn't introduce new locals. + replaceBoxOperationsMultipleCreations(allCreations, allConsumers, boxKind) + } else if (allCreations.size == 1 && (!hasEscaping || !boxKind.isMutable)) { + // M1 -- see doc comment in the beginning of this file + replaceBoxOperationsSingleCreation(allCreations.head, allConsumers, boxKind, keepBox = hasEscaping) + } + } + + case None => + } + + case None => + } + } + + def removeFromCallGraph(insn: AbstractInsnNode): Unit = insn match { + case mi: MethodInsnNode => callGraph.removeCallsite(mi, method) + case _ => + } + + for ((location, ops) <- toInsertBefore; op <- ops) + method.instructions.insertBefore(location, op) + + for ((oldOp, newOps) <- toReplace) { + for (newOp <- newOps) method.instructions.insertBefore(oldOp, newOp) + method.instructions.remove(oldOp) + removeFromCallGraph(oldOp) + } + + for (op <- toDelete) { + method.instructions.remove(op) + removeFromCallGraph(op) + } + + method.maxLocals = nextLocal + method.maxStack += maxStackGrowth + toInsertBefore.nonEmpty || toReplace.nonEmpty || toDelete.nonEmpty + } + } + + /** + * Given a box creations operation + * - find all ultimate consumers for the produced value. then: + * - for all consumed values, find all producer operations. check that all are box creations + * - recurse until reaching a fixpoint + * + * Returns a set of box creations and a set of box consumers. Note that the box consumers may + * contain [[EscapingConsumer]]s, even if there are multiple box creation operations. The callee + * will handle this case (and not attempt to eliminate the box). + */ + def allCreationsConsumers(initialCreation: BoxCreation, boxKind: BoxKind, prodCons: ProdConsAnalyzer): Option[(Set[BoxCreation], Set[BoxConsumer])] = { + var creations = Set(initialCreation) + var consumers = Set.empty[BoxConsumer] + + def addCreations(boxConsumer: BoxConsumer): Boolean = { + val newProds = boxConsumer.boxProducers(prodCons).filterNot(prod => creations.exists(_.producer == prod)) + newProds.forall(prod => boxKind.checkBoxCreation(prod, prodCons) match { + case Some(boxCreation) => + creations += boxCreation + addBoxConsumers(boxCreation) + + case _ => false + }) + } + + def addBoxConsumers(creation: BoxCreation): Boolean = { + val newCons = creation.boxConsumers(prodCons, ultimate = true).filterNot(cons => consumers.exists(_.consumer == cons)) + newCons.forall(cons => boxKind.checkBoxConsumer(cons, prodCons) match { + case Some(boxConsumer) => + consumers += boxConsumer + addCreations(boxConsumer) + + case _ => + creations.size <= 1 && { + // If there's a single box creation, the box operations can still be rewritten + consumers += EscapingConsumer(cons) + true + } + }) + } + + if (addBoxConsumers(initialCreation)) Some((creations, consumers)) + else None + } + + /** + * Takes two sets `initialProds` and `finalCons` such that all boxes produced by the first set + * are only consumed by an operation in the second set. + * + * Returns a map that replaces copy operations (ALOAD / ASTORE) between the producers and + * consumers with corresponding copy operations for the values stored in the box. The returned + * `Int` value returns the next free local variable slot. + * + * Examples: + * - for an Integer box, an ASTORE x is simply replaced by ISTORE x + * - for a pair of two references, an ASTORE x is replaced by `ASTORE x1; ASTORE x2` where x1 + * and x2 are fresh locals + * + * Not all copy operations can be supported: DUP only works for single-value boxes, the more + * exotic copy operations (DUP2_X2) are not supported (note that Scalac never emits them). If a + * copy operation cannot be replaced, this method returns `None`. + */ + def checkCopyOpReplacements(initialProds: Set[BoxCreation], finalCons: Set[BoxConsumer], valueTypes: List[Type], nextLocal: Int, prodCons: ProdConsAnalyzer): Option[(Map[AbstractInsnNode, List[AbstractInsnNode]], Int, Map[Int, Type])] = { + var replacements = Map.empty[AbstractInsnNode, List[AbstractInsnNode]] + var reTypedLocals = Map.empty[Int, Type] + + var nextCopyOpLocal = nextLocal + val newLocalsMap: mutable.LongMap[List[(Type, Int)]] = mutable.LongMap.empty + def newLocals(index: Int) = newLocalsMap.getOrElseUpdate(index, valueTypes match { + case List(t) if t.getSize == 1 => + reTypedLocals += index -> t + List((t, index)) + case _ => valueTypes.map(t => { + val newIndex = nextCopyOpLocal + nextCopyOpLocal += t.getSize + (t, newIndex) + }) + }) + + var replaceOK = true + val copyOps = new CopyOpsIterator(initialProds, finalCons, prodCons) + while (replaceOK && copyOps.hasNext) copyOps.next() match { + case vi: VarInsnNode => + val isLoad = vi.getOpcode == ALOAD + val typedVarOp = (tp: (Type, Int)) => { + val opc = tp._1.getOpcode(if (isLoad) ILOAD else ISTORE) + new VarInsnNode(opc, tp._2) + } + val locs = newLocals(vi.`var`) + replacements += vi -> (if (isLoad) locs.map(typedVarOp) else locs.reverseMap(typedVarOp)) + + case copyOp => + if (copyOp.getOpcode == DUP && valueTypes.lengthCompare(1) == 0) { + if (valueTypes.head.getSize == 2) + replacements += copyOp -> List(new InsnNode(DUP2)) + } else { + replaceOK = false + } + } + if (replaceOK) Some((replacements, nextCopyOpLocal, reTypedLocals)) else None + } + + /** + * For a set of box creation operations and a corresponding set of box consumer operations, + * this iterator returns all copy operations (load, store, dup) that are in between. + */ + class CopyOpsIterator(initialCreations: Set[BoxCreation], finalCons: Set[BoxConsumer], prodCons: ProdConsAnalyzer) extends Iterator[AbstractInsnNode] { + private var queue = mutable.Queue.empty[AbstractInsnNode] ++ initialCreations.iterator.flatMap(_.boxConsumers(prodCons, ultimate = false)) + + // a single copy operation can consume multiple producers: val a = if (b) box(1) else box(2). + // the `ASTORE a` has two producers (the two box operations). we need to handle it only once. + private val visited = mutable.Set.empty[AbstractInsnNode] + + private val boxConsumingOps = finalCons.map(_.consumer) + + @tailrec private def advanceToNextCopyOp(): Unit = { + if (queue.nonEmpty) { + val h = queue.front + if (visited(h) || boxConsumingOps(h)) { + queue.dequeue() + advanceToNextCopyOp() + } + } + } + + def hasNext: Boolean = { + advanceToNextCopyOp() + queue.nonEmpty + } + + def next(): AbstractInsnNode = { + advanceToNextCopyOp() + val r = queue.dequeue() + visited += r + queue ++= prodCons.consumersOfOutputsFrom(r) + r + } + } + + trait BoxKind { + def checkBoxCreation(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[BoxCreation] + def checkBoxConsumer(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[BoxConsumer] + def boxedTypes: List[Type] + def extractedValueIndex(extraction: BoxConsumer): Int + def isMutable: Boolean + } + + object BoxKind { + def valueCreationKind(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[(BoxCreation, BoxKind)] = { + PrimitiveBox.checkPrimitiveBox(insn, None, prodCons) orElse + Ref.checkRefCreation(insn, None, prodCons) orElse + Tuple.checkTupleCreation(insn, None, prodCons) + } + + /** + * Check if `newOp` is part of a standard object construction pattern in which: + * + * NEW T + * DUP + * [load constructor args] + * INVOKESPECIAL T.init + * + * The method ensures that the entire construction pattern is closed in itself, without any + * branches going in or out. This is checked by looking at producers / consumers: + * - `DUP` is the only consumer of `NEW`, and vice versa + * - `DUP` the only producer for the receiver of the constructor call + * - The set of consumers of `DUP` without the constructor call is the same as + * the set of consumers of the value on the stack top after the constructor call + */ + def checkInstanceCreation(newOp: TypeInsnNode, prodCons: ProdConsAnalyzer): Option[(InsnNode, MethodInsnNode)] = { + val newCons = prodCons.consumersOfOutputsFrom(newOp) + if (newCons.size == 1 && newCons.head.getOpcode == DUP) { + val dupOp = newCons.head.asInstanceOf[InsnNode] + if (prodCons.producersForInputsOf(dupOp) == Set(newOp)) { + val dupCons = prodCons.consumersOfOutputsFrom(dupOp) + val initCalls = dupCons collect { + case mi: MethodInsnNode if mi.name == GenBCode.INSTANCE_CONSTRUCTOR_NAME && mi.owner == newOp.desc => mi + } + if (initCalls.size == 1) { + val initCall = initCalls.head + val numArgs = Type.getArgumentTypes(initCall.desc).length + val receiverProds = prodCons.producersForValueAt(initCall, prodCons.frameAt(initCall).stackTop - numArgs) + if (receiverProds == Set(dupOp)) { + val dupConsWithoutInit = dupCons - initCall + val afterInit = initCall.getNext + val stackTopAfterInit = prodCons.frameAt(afterInit).stackTop + val initializedInstanceCons = prodCons.consumersOfValueAt(afterInit, stackTopAfterInit) + if (initializedInstanceCons == dupConsWithoutInit && prodCons.producersForValueAt(afterInit, stackTopAfterInit) == Set(dupOp)) { + return Some((dupOp, initCall)) + } + } + } + } + } + None + } + + /** + * If `mi` is an invocation of a method on Predef, check if the receiver is a GETSTATIC of + * Predef.MODULE$ and return it. + */ + def checkReceiverPredefLoad(mi: MethodInsnNode, prodCons: ProdConsAnalyzer): Option[AbstractInsnNode] = { + val numArgs = Type.getArgumentTypes(mi.desc).length + val receiverProds = prodCons.producersForValueAt(mi, prodCons.frameAt(mi).stackTop - numArgs) + if (receiverProds.size == 1) { + val prod = receiverProds.head + if (isPredefLoad(prod) && prodCons.consumersOfOutputsFrom(prod) == Set(mi)) return Some(prod) + } + None + } + } + + case class PrimitiveBox(boxedType: Type, boxClass: InternalName) extends BoxKind { + import PrimitiveBox._ + def checkBoxCreation(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[BoxCreation] = checkPrimitiveBox(insn, Some(this), prodCons).map(_._1) + def checkBoxConsumer(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[BoxConsumer] = checkPrimitiveUnbox(insn, this, prodCons) + def boxedTypes: List[Type] = List(boxedType) + def extractedValueIndex(extraction: BoxConsumer): Int = 0 + def isMutable = false + } + + object PrimitiveBox { + private def boxedType(mi: MethodInsnNode) = Type.getArgumentTypes(mi.desc)(0) + + private def boxClass(mi: MethodInsnNode) = { + if (mi.name == GenBCode.INSTANCE_CONSTRUCTOR_NAME) mi.owner + else Type.getReturnType(mi.desc).getInternalName + } + + def checkPrimitiveBox(insn: AbstractInsnNode, expectedKind: Option[PrimitiveBox], prodCons: ProdConsAnalyzer): Option[(BoxCreation, PrimitiveBox)] = { + // mi is either a box factory or a box constructor invocation + def checkKind(mi: MethodInsnNode) = expectedKind match { + case Some(kind) => if (kind.boxClass == boxClass(mi)) expectedKind else None + case None => Some(PrimitiveBox(boxedType(mi), boxClass(mi))) + } + + insn match { + case mi: MethodInsnNode => + if (isScalaBox(mi) || isJavaBox(mi)) checkKind(mi).map((StaticFactory(mi, loadInitialValues = None), _)) + else if (isPredefAutoBox(mi)) + for (predefLoad <- BoxKind.checkReceiverPredefLoad(mi, prodCons); kind <- checkKind(mi)) + yield (ModuleFactory(predefLoad, mi), kind) + else None + + case ti: TypeInsnNode if ti.getOpcode == NEW => + for ((dupOp, initCall) <- BoxKind.checkInstanceCreation(ti, prodCons) if isPrimitiveBoxConstructor(initCall); kind <- checkKind(initCall)) + yield (InstanceCreation(ti, dupOp, initCall), kind) + + case _ => None + } + } + + def checkPrimitiveUnbox(insn: AbstractInsnNode, kind: PrimitiveBox, prodCons: ProdConsAnalyzer): Option[BoxConsumer] = { + def typeOK(mi: MethodInsnNode) = kind.boxedType == Type.getReturnType(mi.desc) + insn match { + case mi: MethodInsnNode => + if ((isScalaUnbox(mi) || isJavaUnbox(mi)) && typeOK(mi)) Some(StaticGetterOrInstanceRead(mi)) + else if (isPredefAutoUnbox(mi) && typeOK(mi)) BoxKind.checkReceiverPredefLoad(mi, prodCons).map(ModuleGetter(_, mi)) + else None + + case _ => None + } + } + } + + case class Ref(boxedType: Type, refClass: InternalName) extends BoxKind { + import Ref._ + def checkBoxCreation(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[BoxCreation] = checkRefCreation(insn, Some(this), prodCons).map(_._1) + def checkBoxConsumer(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[BoxConsumer] = checkRefConsumer(insn, this, prodCons) + def boxedTypes: List[Type] = List(boxedType) + def extractedValueIndex(extraction: BoxConsumer): Int = 0 + def isMutable = true + } + + object Ref { + private def boxedType(mi: MethodInsnNode): Type = runtimeRefClassBoxedType(mi.owner) + private def refClass(mi: MethodInsnNode): InternalName = mi.owner + private def loadZeroValue(refZeroCall: MethodInsnNode): List[AbstractInsnNode] = List(loadZeroForTypeSort(runtimeRefClassBoxedType(refZeroCall.owner).getSort)) + + def checkRefCreation(insn: AbstractInsnNode, expectedKind: Option[Ref], prodCons: ProdConsAnalyzer): Option[(BoxCreation, Ref)] = { + def checkKind(mi: MethodInsnNode): Option[Ref] = expectedKind match { + case Some(kind) => if (kind.refClass == refClass(mi)) expectedKind else None + case None => Some(Ref(boxedType(mi), refClass(mi))) + } + + insn match { + case mi: MethodInsnNode => + if (isRefCreate(mi)) checkKind(mi).map((StaticFactory(mi, loadInitialValues = None), _)) + else if (isRefZero(mi)) checkKind(mi).map((StaticFactory(mi, loadInitialValues = Some(loadZeroValue(mi))), _)) + else None + + case ti: TypeInsnNode if ti.getOpcode == NEW => + for ((dupOp, initCall) <- BoxKind.checkInstanceCreation(ti, prodCons) if isRuntimeRefConstructor(initCall); kind <- checkKind(initCall)) + yield (InstanceCreation(ti, dupOp, initCall), kind) + + case _ => None + } + } + + def checkRefConsumer(insn: AbstractInsnNode, kind: Ref, prodCons: ProdConsAnalyzer): Option[BoxConsumer] = insn match { + case fi: FieldInsnNode if fi.owner == kind.refClass && fi.name == "elem" => + if (fi.getOpcode == GETFIELD) Some(StaticGetterOrInstanceRead(fi)) + else if (fi.getOpcode == PUTFIELD) Some(StaticSetterOrInstanceWrite(fi)) + else None + + case _ => None + } + } + + case class Tuple(boxedTypes: List[Type], tupleClass: InternalName) extends BoxKind { + import Tuple._ + def checkBoxCreation(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[BoxCreation] = checkTupleCreation(insn, Some(this), prodCons).map(_._1) + def checkBoxConsumer(insn: AbstractInsnNode, prodCons: ProdConsAnalyzer): Option[BoxConsumer] = checkTupleExtraction(insn, this, prodCons) + def extractedValueIndex(extraction: BoxConsumer): Int = extraction match { + case StaticGetterOrInstanceRead(mi: MethodInsnNode) => tupleGetterIndex(mi.name) + case PrimitiveBoxingGetter(mi) => tupleGetterIndex(mi.name) + case PrimitiveUnboxingGetter(mi, _) => tupleGetterIndex(mi.name) + case _ => throw new AssertionError(s"Expected tuple getter, found $extraction") + } + def isMutable = false + } + + object Tuple { + private def boxedTypes(mi: MethodInsnNode): List[Type] = Type.getArgumentTypes(mi.desc).toList + private def tupleClass(mi: MethodInsnNode): InternalName = mi.owner + + def checkTupleCreation(insn: AbstractInsnNode, expectedKind: Option[Tuple], prodCons: ProdConsAnalyzer): Option[(BoxCreation, Tuple)] = { + def checkKind(mi: MethodInsnNode): Option[Tuple] = expectedKind match { + case Some(kind) => if (kind.tupleClass == tupleClass(mi)) expectedKind else None + case None => Some(Tuple(boxedTypes(mi), tupleClass(mi))) + } + + insn match { + // no need to check for TupleN.apply: the compiler transforms case companion apply calls to constructor invocations + case ti: TypeInsnNode if ti.getOpcode == NEW => + for ((dupOp, initCall) <- BoxKind.checkInstanceCreation(ti, prodCons) if isTupleConstructor(initCall); kind <- checkKind(initCall)) + yield (InstanceCreation(ti, dupOp, initCall), kind) + + case _ => None + } + } + + private val specializedTupleClassR = "scala/Tuple[12]\\$mc[IJDCZ]{1,2}\\$sp".r + private def isSpecializedTupleClass(tupleClass: InternalName) = specializedTupleClassR.pattern.matcher(tupleClass).matches + + private val specializedTupleGetterR = "_[12]\\$mc[IJDCZ]\\$sp".r + private def isSpecializedTupleGetter(mi: MethodInsnNode) = specializedTupleGetterR.pattern.matcher(mi.name).matches + + private val tupleGetterR = "_\\d\\d?".r + private def isTupleGetter(mi: MethodInsnNode) = tupleGetterR.pattern.matcher(mi.name).matches + + def checkTupleExtraction(insn: AbstractInsnNode, kind: Tuple, prodCons: ProdConsAnalyzer): Option[BoxConsumer] = { + val expectedTupleClass = kind.tupleClass + insn match { + case mi: MethodInsnNode => + val tupleClass = mi.owner + if (isSpecializedTupleClass(expectedTupleClass)) { + val typeOK = tupleClass == expectedTupleClass || tupleClass == expectedTupleClass.substring(0, expectedTupleClass.indexOf('$')) + if (typeOK) { + if (isSpecializedTupleGetter(mi)) return Some(StaticGetterOrInstanceRead(mi)) + else if (isTupleGetter(mi)) return Some(PrimitiveBoxingGetter(mi)) + } + } else if (expectedTupleClass == tupleClass) { + if (isSpecializedTupleGetter(mi)) return Some(PrimitiveUnboxingGetter(mi, Type.getReturnType(mi.desc))) + else if (isTupleGetter(mi)) return Some(StaticGetterOrInstanceRead(mi)) + } + + case _ => + } + None + } + + private val getterIndexPattern = "_(\\d{1,2}).*".r + def tupleGetterIndex(getterName: String) = getterName match { case getterIndexPattern(i) => i.toInt - 1 } + } + + // TODO: add more + // case class ValueClass(valueClass: Type, valueType: Type) extends BoxKind + + sealed trait BoxCreation { + // to support box creation operations that don't consume an initial value from the stack, e.g., IntRef.zero + val loadInitialValues: Option[List[AbstractInsnNode]] + + /** + * The instruction that produces the box value; for instance creations, the `NEW` operation. + */ + def producer: AbstractInsnNode + + /** + * The instruction that consumes the boxed values; for instance creations, the `init` call. + */ + def valuesConsumer: MethodInsnNode = this match { + case StaticFactory(call, _) => call + case ModuleFactory(_, call) => call + case InstanceCreation(_, _, initCall) => initCall + } + + def allInsns: Set[AbstractInsnNode] = this match { + case StaticFactory(c, _) => Set(c) + case ModuleFactory(m, c) => Set(m, c) + case InstanceCreation(n, d, i) => Set(n, d, i) + } + + /** + * The consumers of the box produced by this box creation. If `ultimate` is true, then the + * final consumers are returned (e.g., an unbox operation), otherwise direct consumers (e.g., + * a store operation). + */ + def boxConsumers(prodCons: ProdConsAnalyzer, ultimate: Boolean): Set[AbstractInsnNode] = { + val startInsn = this match { + // for the non-transitive case (ultimate == false), it's important to start at the `dupOp`, + // not the `newOp` - look at the BoxCreation as a black box, get its consumers. + case InstanceCreation(_, dupOp, _) => dupOp + case _ => producer + } + val cons = if (ultimate) prodCons.ultimateConsumersOfOutputsFrom(startInsn) else prodCons.consumersOfOutputsFrom(startInsn) + this match { + case InstanceCreation(_, _, initCall) => cons - initCall + case _ => cons + } + } + } + + case class StaticFactory(producer: MethodInsnNode, loadInitialValues: Option[List[AbstractInsnNode]]) extends BoxCreation + case class ModuleFactory(moduleLoad: AbstractInsnNode, producer: MethodInsnNode) extends BoxCreation { + val loadInitialValues: Option[List[AbstractInsnNode]] = None + } + case class InstanceCreation(newOp: TypeInsnNode, dupOp: InsnNode, initCall: MethodInsnNode) extends BoxCreation { + def producer = newOp + val loadInitialValues: Option[List[AbstractInsnNode]] = None + } + + sealed trait BoxConsumer { + val consumer: AbstractInsnNode + + def allInsns: Set[AbstractInsnNode] = this match { + case ModuleGetter(m, c) => Set(m, c) + case _ => Set(consumer) + } + + /** + * The initial producers of the box value consumed by this box consumer + */ + def boxProducers(prodCons: ProdConsAnalyzer): Set[AbstractInsnNode] = { + val stackTop = prodCons.frameAt(consumer).stackTop + val slot = if (isWrite) stackTop - 1 else stackTop + prodCons.initialProducersForValueAt(consumer, slot) + } + + def isEscaping = this match { + case _: EscapingConsumer => true + case _ => false + } + + def isWrite = this match { + case _: StaticSetterOrInstanceWrite => true + case _ => false + } + + /** + * If this box consumer extracts a boxed value and applies a conversion, this method returns + * equivalent conversion operations. For example, invoking `_1$mcI$sp` on a non-specialized + * `Tuple2` extracts the Integer value and unboxes it. + */ + def postExtractionAdaptationOps(typeOfExtractedValue: Type): List[AbstractInsnNode] = this match { + case PrimitiveBoxingGetter(_) => List(getScalaBox(typeOfExtractedValue)) + case PrimitiveUnboxingGetter(_, unboxedPrimitive) => List(getScalaUnbox(unboxedPrimitive)) + case _ => Nil + } + } + + /** Static extractor (BoxesRunTime.unboxToInt) or GETFIELD or getter invocation */ + case class StaticGetterOrInstanceRead(consumer: AbstractInsnNode) extends BoxConsumer + /** A getter that boxes the returned value, e.g., `Tuple2$mcII$sp._1` */ + case class PrimitiveBoxingGetter(consumer: MethodInsnNode) extends BoxConsumer + /** A getter that unboxes the returned value, e.g., `Tuple2._1$mcI$sp` */ + case class PrimitiveUnboxingGetter(consumer: MethodInsnNode, unboxedPrimitive: Type) extends BoxConsumer + /** An extractor method in a Scala module, e.g., `Predef.Integer2int` */ + case class ModuleGetter(moduleLoad: AbstractInsnNode, consumer: MethodInsnNode) extends BoxConsumer + /** PUTFIELD or setter invocation */ + case class StaticSetterOrInstanceWrite(consumer: AbstractInsnNode) extends BoxConsumer + /** An unknown box consumer */ + case class EscapingConsumer(consumer: AbstractInsnNode) extends BoxConsumer +} |