/* 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 }