diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/backend/opt')
5 files changed, 0 insertions, 2778 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala deleted file mode 100644 index a866173a88..0000000000 --- a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala +++ /dev/null @@ -1,235 +0,0 @@ - /* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Iulian Dragos - */ - -package scala.tools.nsc -package backend.opt - -import scala.tools.nsc.backend.icode.analysis.LubException - -/** - * @author Iulian Dragos - */ -abstract class ClosureElimination extends SubComponent { - import global._ - import icodes._ - import icodes.opcodes._ - - val phaseName = "closelim" - - override val enabled: Boolean = settings.Xcloselim - - /** Create a new phase */ - override def newPhase(p: Phase) = new ClosureEliminationPhase(p) - - /** A simple peephole optimizer. */ - val peephole = new PeepholeOpt { - - def peep(bb: BasicBlock, i1: Instruction, i2: Instruction) = (i1, i2) match { - case (CONSTANT(c), DROP(_)) => - if (c.tag == UnitTag) Some(List(i2)) else Some(Nil) - - case (LOAD_LOCAL(x), STORE_LOCAL(y)) => - if (x eq y) Some(Nil) else None - - case (STORE_LOCAL(x), LOAD_LOCAL(y)) if (x == y) => - var liveOut = liveness.out(bb) - if (!liveOut(x)) { - debuglog("store/load to a dead local? " + x) - val instrs = bb.getArray - var idx = instrs.length - 1 - while (idx > 0 && (instrs(idx) ne i2)) { - liveOut = liveness.interpret(liveOut, instrs(idx)) - idx -= 1 - } - if (!liveOut(x)) { - log("Removing dead store/load of " + x.sym.initialize.defString) - Some(Nil) - } else None - } else - Some(List(DUP(x.kind), STORE_LOCAL(x))) - - case (LOAD_LOCAL(_), DROP(_)) | (DUP(_), DROP(_)) => - Some(Nil) - - case (BOX(t1), UNBOX(t2)) if (t1 == t2) => - Some(Nil) - - case (LOAD_FIELD(sym, /* isStatic */false), DROP(_)) if !sym.hasAnnotation(definitions.VolatileAttr) && inliner.isClosureClass(sym.owner) => - Some(DROP(REFERENCE(definitions.ObjectClass)) :: Nil) - - case _ => None - } - } - - /** The closure elimination phase. - */ - class ClosureEliminationPhase(prev: Phase) extends ICodePhase(prev) { - - def name = phaseName - val closser = new ClosureElim - - override def apply(c: IClass): Unit = { - if (closser ne null) - closser analyzeClass c - } - } - - /** - * Remove references to the environment through fields of a closure object. - * This has to be run after an 'apply' method has been inlined, but it still - * references the closure object. - * - */ - class ClosureElim { - def analyzeClass(cls: IClass): Unit = if (settings.Xcloselim) { - log(s"Analyzing ${cls.methods.size} methods in $cls.") - cls.methods foreach { m => - analyzeMethod(m) - peephole(m) - }} - - val cpp = new copyPropagation.CopyAnalysis - - import copyPropagation._ - - /* Some embryonic copy propagation. */ - def analyzeMethod(m: IMethod): Unit = try {if (m.hasCode) { - cpp.init(m) - cpp.run() - - m.linearizedBlocks() foreach { bb => - var info = cpp.in(bb) - debuglog("Cpp info at entry to block " + bb + ": " + info) - - for (i <- bb) { - i match { - case LOAD_LOCAL(l) if info.bindings isDefinedAt LocalVar(l) => - val t = info.getBinding(l) - t match { - case Deref(This) | Const(_) => - bb.replaceInstruction(i, valueToInstruction(t)) - debuglog(s"replaced $i with $t") - - case _ => - val t = info.getAlias(l) - bb.replaceInstruction(i, LOAD_LOCAL(t)) - debuglog(s"replaced $i with $t") - } - - case LOAD_FIELD(f, false) /* if accessible(f, m.symbol) */ => - def replaceFieldAccess(r: Record) { - val Record(cls, _) = r - info.getFieldNonRecordValue(r, f) foreach { v => - bb.replaceInstruction(i, DROP(REFERENCE(cls)) :: valueToInstruction(v) :: Nil) - debuglog(s"replaced $i with $v") - } - } - - info.stack(0) match { - case r @ Record(_, bindings) if bindings isDefinedAt f => - replaceFieldAccess(r) - - case Deref(LocalVar(l)) => - info.getBinding(l) match { - case r @ Record(_, bindings) if bindings isDefinedAt f => - replaceFieldAccess(r) - case _ => - } - case Deref(Field(r1, f1)) => - info.getFieldValue(r1, f1) match { - case Some(r @ Record(_, bindings)) if bindings isDefinedAt f => - replaceFieldAccess(r) - case _ => - } - - case _ => - } - - case UNBOX(boxType) => - info.stack match { - case Deref(LocalVar(loc1)) :: _ if info.bindings isDefinedAt LocalVar(loc1) => - val value = info.getBinding(loc1) - value match { - case Boxed(LocalVar(loc2)) if loc2.kind == boxType => - bb.replaceInstruction(i, DROP(icodes.ObjectReference) :: valueToInstruction(info.getBinding(loc2)) :: Nil) - debuglog("replaced " + i + " with " + info.getBinding(loc2)) - case _ => - () - } - case Boxed(LocalVar(loc1)) :: _ if loc1.kind == boxType => - val loc2 = info.getAlias(loc1) - bb.replaceInstruction(i, DROP(icodes.ObjectReference) :: valueToInstruction(Deref(LocalVar(loc2))) :: Nil) - debuglog("replaced " + i + " with " + LocalVar(loc2)) - case _ => - } - - case _ => - } - info = cpp.interpret(info, i) - } - } - }} catch { - case e: LubException => - Console.println("In method: " + m) - Console.println(e) - e.printStackTrace - } - - /* Partial mapping from values to instructions that load them. */ - def valueToInstruction(v: Value): Instruction = (v: @unchecked) match { - case Deref(LocalVar(v)) => - LOAD_LOCAL(v) - case Const(k) => - CONSTANT(k) - case Deref(This) => - THIS(definitions.ObjectClass) - case Boxed(LocalVar(v)) => - LOAD_LOCAL(v) - } - } /* class ClosureElim */ - - - /** Peephole optimization. */ - abstract class PeepholeOpt { - /** Concrete implementations will perform their optimizations here */ - def peep(bb: BasicBlock, i1: Instruction, i2: Instruction): Option[List[Instruction]] - - var liveness: global.icodes.liveness.LivenessAnalysis = null - - def apply(m: IMethod): Unit = if (m.hasCode) { - liveness = new global.icodes.liveness.LivenessAnalysis - liveness.init(m) - liveness.run() - m foreachBlock transformBlock - } - - def transformBlock(b: BasicBlock): Unit = if (b.size >= 2) { - var newInstructions: List[Instruction] = b.toList - var redo = false - - do { - var h = newInstructions.head - var t = newInstructions.tail - var seen: List[Instruction] = Nil - redo = false - - while (t != Nil) { - peep(b, h, t.head) match { - case Some(newInstrs) => - newInstructions = seen reverse_::: newInstrs ::: t.tail - redo = true - case None => - () - } - seen = h :: seen - h = t.head - t = t.tail - } - } while (redo) - b fromList newInstructions - } - } - -} /* class ClosureElimination */ diff --git a/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala b/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala deleted file mode 100644 index eafaf41932..0000000000 --- a/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala +++ /dev/null @@ -1,626 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author James Iry - */ - -package scala -package tools.nsc -package backend.opt - -import scala.annotation.tailrec - -/** - * ConstantOptimization uses abstract interpretation to approximate for - * each instruction what constants a variable or stack slot might hold - * or cannot hold. From this it will eliminate unreachable conditionals - * where only one branch is reachable, e.g. to eliminate unnecessary - * null checks. - * - * With some more work it could be extended to - * - cache stable values (final fields, modules) in locals - * - replace the copy propagation in ClosureElimination - * - fold constants - * - eliminate unnecessary stores and loads - * - propagate knowledge gathered from conditionals for further optimization - */ -abstract class ConstantOptimization extends SubComponent { - import global._ - import icodes._ - import icodes.opcodes._ - - val phaseName = "constopt" - - /** Create a new phase */ - override def newPhase(p: Phase) = new ConstantOptimizationPhase(p) - - override val enabled: Boolean = settings.YconstOptimization - - /** - * The constant optimization phase. - */ - class ConstantOptimizationPhase(prev: Phase) extends ICodePhase(prev) { - - def name = phaseName - - override def apply(c: IClass) { - if (settings.YconstOptimization) { - val analyzer = new ConstantOptimizer - analyzer optimizeClass c - } - } - } - - class ConstantOptimizer { - def optimizeClass(cls: IClass) { - log(s"Analyzing ${cls.methods.size} methods in $cls.") - cls.methods foreach { m => - optimizeMethod(m) - } - } - - def optimizeMethod(m: IMethod) { - if (m.hasCode) { - log(s"Analyzing ${m.symbol}") - val replacementInstructions = interpretMethod(m) - for (block <- m.blocks) { - if (replacementInstructions contains block) { - val instructions = replacementInstructions(block) - block.replaceInstruction(block.lastInstruction, instructions) - } - } - } - } - - /** - * A single possible (or impossible) datum that can be held in Contents - */ - private sealed abstract class Datum - /** - * A constant datum - */ - private case class Const(c: Constant) extends Datum { - def isIntAssignable = c.tag >= BooleanTag && c.tag <= IntTag - def toInt = c.tag match { - case BooleanTag => if (c.booleanValue) 1 else 0 - case _ => c.intValue - } - - /** - * True if this constant would compare to other as true under primitive eq - */ - override def equals(other: Any) = other match { - case oc @ Const(o) => (this eq oc) || (if (this.isIntAssignable && oc.isIntAssignable) this.toInt == oc.toInt else c.value == o.value) - case _ => false - } - - /** - * Hash code consistent with equals - */ - override def hashCode = if (this.isIntAssignable) this.toInt else c.hashCode - - } - /** - * A datum that has been Boxed via a BOX instruction - */ - private case class Boxed(c: Datum) extends Datum - - /** - * The knowledge we have about the abstract state of one location in terms - * of what constants it might or cannot hold. Forms a lower - * lattice where lower elements in the lattice indicate less knowledge. - * - * With the following partial ordering (where '>' indicates more precise knowledge) - * - * Possible(xs) > Possible(xs + y) - * Possible(xs) > Impossible(ys) - * Impossible(xs + y) > Impossible(xs) - * - * and the following merges, which indicate merging knowledge from two paths through - * the code, - * - * // left must be 1 or 2, right must be 2 or 3 then we must have a 1, 2 or 3 - * Possible(xs) merge Possible(ys) => Possible(xs union ys) - * - * // Left says can't be 2 or 3, right says can't be 3 or 4 - * // then it's not 3 (it could be 2 from the right or 4 from the left) - * Impossible(xs) merge Impossible(ys) => Impossible(xs intersect ys) - * - * // Left says it can't be 2 or 3, right says it must be 3 or 4, then - * // it can't be 2 (left rules out 4 and right says 3 is possible) - * Impossible(xs) merge Possible(ys) => Impossible(xs -- ys) - * - * Intuitively, Possible(empty) says that a location can't hold anything, - * it's uninitialized. However, Possible(empty) never appears in the code. - * - * Conversely, Impossible(empty) says nothing is impossible, it could be - * anything. Impossible(empty) is given a synonym UNKNOWN and is used - * for, e.g., the result of an arbitrary method call. - */ - private sealed abstract class Contents { - /** - * Join this Contents with another coming from another path. Join enforces - * the lattice structure. It is symmetrical and never moves upward in the - * lattice - */ - final def merge(other: Contents): Contents = if (this eq other) this else (this, other) match { - case (Possible(possible1), Possible(possible2)) => - Possible(possible1 union possible2) - case (Impossible(impossible1), Impossible(impossible2)) => - Impossible(impossible1 intersect impossible2) - case (Impossible(impossible), Possible(possible)) => - Impossible(impossible -- possible) - case (Possible(possible), Impossible(impossible)) => - Impossible(impossible -- possible) - } - // TODO we could have more fine-grained knowledge, e.g. know that 0 < x < 3. But for now equality/inequality is a good start. - def mightEqual(other: Contents): Boolean - def mightNotEqual(other: Contents): Boolean - } - private def SingleImpossible(x: Datum) = new Impossible(Set(x)) - - /** - * The location is known to have one of a set of values. - */ - private case class Possible(possible: Set[Datum]) extends Contents { - assert(possible.nonEmpty, "Contradiction: had an empty possible set indicating an uninitialized location") - def mightEqual(other: Contents): Boolean = (this eq other) || (other match { - // two Possibles might be equal if they have any possible members in common - case Possible(possible2) => (possible intersect possible2).nonEmpty - // a possible can be equal to an impossible if the impossible doesn't rule - // out all the possibilities - case Impossible(possible2) => (possible -- possible2).nonEmpty - }) - def mightNotEqual(other: Contents): Boolean = (other match { - case Possible(possible2) => - // two Possibles must equal if each is known to be of the same, single value - val mustEqual = possible.size == 1 && possible == possible2 - !mustEqual - case Impossible(_) => true - }) - } - private def SinglePossible(x: Datum) = new Possible(Set(x)) - - /** - * The location is known to not have any of a set of values value (e.g null). - */ - private case class Impossible(impossible: Set[Datum]) extends Contents { - def mightEqual(other: Contents): Boolean = (this eq other) || (other match { - case Possible(_) => other mightEqual this - case _ => true - }) - def mightNotEqual(other: Contents): Boolean = (this eq other) || (other match { - case Possible(_) => other mightNotEqual this - case _ => true - }) - } - - /** - * Our entire knowledge about the contents of all variables and the stack. It forms - * a lattice primarily driven by the lattice structure of Contents. - * - * In addition to the rules of contents, State has the following properties: - * - The merge of two sets of locals holds the merges of locals found in the intersection - * of the two sets of locals. Locals not found in a - * locals map are thus possibly uninitialized and attempting to load them results - * in an error. - * - The stack heights of two states must match otherwise it's an error to merge them - * - * State is immutable in order to aid in structure sharing of local maps and stacks - */ - private case class State(locals: Map[Local, Contents], stack: List[Contents]) { - def mergeLocals(olocals: Map[Local, Contents]): Map[Local, Contents] = if (locals eq olocals) locals else Map((for { - key <- (locals.keySet intersect olocals.keySet).toSeq - } yield (key, locals(key) merge olocals(key))): _*) - - def merge(other: State): State = if (this eq other) this else { - @tailrec def mergeStacks(l: List[Contents], r: List[Contents], out: List[Contents]): List[Contents] = (l, r) match { - case (Nil, Nil) => out.reverse - case (l, r) if l eq r => out.reverse ++ l - case (lhead :: ltail, rhead :: rtail) => mergeStacks(ltail, rtail, (lhead merge rhead) :: out) - case _ => sys.error("Mismatched stack heights") - } - - val newLocals = mergeLocals(other.locals) - - val newStack = if (stack eq other.stack) stack else mergeStacks(stack, other.stack, Nil) - State(newLocals, newStack) - } - - /** - * Peek at the top of the stack without modifying it. Error if the stack is empty - */ - def peek(n: Int): Contents = stack(n) - /** - * Push contents onto a stack - */ - def push(contents: Contents): State = this copy (stack = contents :: stack) - /** - * Drop n elements from the stack - */ - def drop(number: Int): State = this copy (stack = stack drop number) - /** - * Store the top of the stack into the specified local. An error if the stack - * is empty - */ - def store(variable: Local): State = { - val contents = stack.head - val newVariables = locals + ((variable, contents)) - new State(newVariables, stack.tail) - } - /** - * Load the specified local onto the top of the stack. An error if the local is uninitialized. - */ - def load(variable: Local): State = { - val contents: Contents = locals.getOrElse(variable, sys.error(s"$variable is not initialized")) - push(contents) - } - /** - * A copy of this State with an empty stack - */ - def cleanStack: State = if (stack.isEmpty) this else this copy (stack = Nil) - } - - // some precomputed constants - private val NULL = Const(Constant(null: Any)) - private val UNKNOWN = Impossible(Set.empty) - private val NOT_NULL = SingleImpossible(NULL) - private val CONST_UNIT = SinglePossible(Const(Constant(()))) - private val CONST_FALSE = SinglePossible(Const(Constant(false))) - private val CONST_ZERO_BYTE = SinglePossible(Const(Constant(0: Byte))) - private val CONST_ZERO_SHORT = SinglePossible(Const(Constant(0: Short))) - private val CONST_ZERO_CHAR = SinglePossible(Const(Constant(0: Char))) - private val CONST_ZERO_INT = SinglePossible(Const(Constant(0: Int))) - private val CONST_ZERO_LONG = SinglePossible(Const(Constant(0: Long))) - private val CONST_ZERO_FLOAT = SinglePossible(Const(Constant(0.0f))) - private val CONST_ZERO_DOUBLE = SinglePossible(Const(Constant(0.0d))) - private val CONST_NULL = SinglePossible(NULL) - - /** - * Given a TypeKind, figure out what '0' for it means in order to interpret CZJUMP - */ - private def getZeroOf(k: TypeKind): Contents = k match { - case UNIT => CONST_UNIT - case BOOL => CONST_FALSE - case BYTE => CONST_ZERO_BYTE - case SHORT => CONST_ZERO_SHORT - case CHAR => CONST_ZERO_CHAR - case INT => CONST_ZERO_INT - case LONG => CONST_ZERO_LONG - case FLOAT => CONST_ZERO_FLOAT - case DOUBLE => CONST_ZERO_DOUBLE - case REFERENCE(_) => CONST_NULL - case ARRAY(_) => CONST_NULL - case BOXED(_) => CONST_NULL - case ConcatClass => abort("no zero of ConcatClass") - } - - // normal locals can't be null, so we use null to mean the magic 'this' local - private val THIS_LOCAL: Local = null - - /** - * interpret a single instruction to find its impact on the abstract state - */ - private def interpretInst(in: State, inst: Instruction): State = { - // pop the consumed number of values off the `in` state's stack, producing a new state - def dropConsumed: State = in drop inst.consumed - - inst match { - case THIS(_) => - in load THIS_LOCAL - - case CONSTANT(k) => - // treat NaN as UNKNOWN because NaN must never equal NaN - val const = if (k.isNaN) UNKNOWN - else SinglePossible(Const(k)) - in push const - - case LOAD_ARRAY_ITEM(_) | LOAD_FIELD(_, _) | CALL_PRIMITIVE(_) => - dropConsumed push UNKNOWN - - case LOAD_LOCAL(local) => - // TODO if a local is known to hold a constant then we can replace this instruction with a push of that constant - in load local - - case STORE_LOCAL(local) => - in store local - - case STORE_THIS(_) => - // if a local is already known to have a constant and we're replacing with the same constant then we can - // replace this with a drop - in store THIS_LOCAL - - case CALL_METHOD(_, _) => - // TODO we could special case implementations of equals that are known, e.g. String#equals - // We could turn Possible(string constants).equals(Possible(string constants) into an eq check - // We could turn nonConstantString.equals(constantString) into constantString.equals(nonConstantString) - // and eliminate the null check that likely precedes this call - val initial = dropConsumed - (0 until inst.produced).foldLeft(initial) { case (know, _) => know push UNKNOWN } - - case BOX(_) => - val value = in peek 0 - // we simulate boxing by, um, boxing the possible/impossible contents - // so if we have Possible(1,2) originally then we'll end up with - // a Possible(Boxed(1), Boxed(2)) - // Similarly, if we know the input is not a 0 then we'll know the - // output is not a Boxed(0) - val newValue = value match { - case Possible(values) => Possible(values map Boxed) - case Impossible(values) => Impossible(values map Boxed) - } - dropConsumed push newValue - - case UNBOX(_) => - val value = in peek 0 - val newValue = value match { - // if we have a Possible, then all the possibilities - // should themselves be Boxes. In that - // case we can merge them to figure out what the UNBOX will produce - case Possible(inners) => - assert(inners.nonEmpty, "Empty possible set indicating an uninitialized location") - val sanitized: Set[Contents] = (inners map { - case Boxed(content) => SinglePossible(content) - case _ => UNKNOWN - }) - sanitized reduce (_ merge _) - // if we have an impossible then the thing that's impossible - // should be a box. We'll unbox that to see what we get - case unknown@Impossible(inners) => - if (inners.isEmpty) { - unknown - } else { - val sanitized: Set[Contents] = (inners map { - case Boxed(content) => SingleImpossible(content) - case _ => UNKNOWN - }) - sanitized reduce (_ merge _) - } - } - dropConsumed push newValue - - case LOAD_MODULE(_) | NEW(_) | LOAD_EXCEPTION(_) => - in push NOT_NULL - - case CREATE_ARRAY(_, _) => - dropConsumed push NOT_NULL - - case IS_INSTANCE(_) => - // TODO IS_INSTANCE is going to be followed by a C(Z)JUMP - // and if IS_INSTANCE/C(Z)JUMP the branch for "true" can - // know that whatever was checked was not a null - // see the TODO on CJUMP for more information about propagating null - // information - // TODO if the top of stack is guaranteed null then we can eliminate this IS_INSTANCE check and - // replace with a constant false, but how often is a knowable null checked for instanceof? - // TODO we could track type information and statically know to eliminate IS_INSTANCE - // which might be a nice win under specialization - dropConsumed push UNKNOWN // it's actually a Possible(true, false) but since the following instruction - // will be a conditional jump comparing to true or false there - // nothing to be gained by being more precise - - case CHECK_CAST(_) => - // TODO we could track type information and statically know to eliminate CHECK_CAST - // but that's probably not a huge win - in - - case DUP(_) => - val value = in peek 0 - in push value - - case DROP(_) | MONITOR_ENTER() | MONITOR_EXIT() | STORE_ARRAY_ITEM(_) | STORE_FIELD(_, _) => - dropConsumed - - case SCOPE_ENTER(_) | SCOPE_EXIT(_) => - in - - case JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | RETURN(_) | THROW(_) | SWITCH(_, _) => - dumpClassesAndAbort("Unexpected block ending instruction: " + inst) - } - } - /** - * interpret the last instruction of a block which will be jump, a conditional branch, a throw, or a return. - * It will result in a map from target blocks to the input state computed for that block. It - * also computes a replacement list of instructions - */ - private def interpretLast(in: State, inst: Instruction): (Map[BasicBlock, State], List[Instruction]) = { - def canSwitch(in1: Contents, tagSet: List[Int]) = { - in1 mightEqual Possible(tagSet.toSet map { tag: Int => Const(Constant(tag)) }) - } - - /* common code for interpreting CJUMP and CZJUMP */ - def interpretConditional(kind: TypeKind, val1: Contents, val2: Contents, success: BasicBlock, failure: BasicBlock, cond: TestOp): (Map[BasicBlock, State], List[Instruction]) = { - // TODO use reaching analysis to update the state in the two branches - // e.g. if the comparison was checking null equality on local x - // then the in the success branch we know x is null and - // on the failure branch we know it is not - // in fact, with copy propagation we could propagate that knowledge - // back through a chain of locations - // - // TODO if we do all that we need to be careful in the - // case that success and failure are the same target block - // because we're using a Map and don't want one possible state to clobber the other - // alternative maybe we should just replace the conditional with a jump if both targets are the same - - def mightEqual = val1 mightEqual val2 - def mightNotEqual = val1 mightNotEqual val2 - def guaranteedEqual = mightEqual && !mightNotEqual - - def succPossible = cond match { - case EQ => mightEqual - case NE => mightNotEqual - case LT | GT => !guaranteedEqual // if the two are guaranteed to be equal then they can't be LT/GT - case LE | GE => true - } - - def failPossible = cond match { - case EQ => mightNotEqual - case NE => mightEqual - case LT | GT => true - case LE | GE => !guaranteedEqual // if the two are guaranteed to be equal then they must be LE/GE - } - - val out = in drop inst.consumed - - var result = Map[BasicBlock, State]() - if (succPossible) { - result += ((success, out)) - } - - if (failPossible) { - result += ((failure, out)) - } - - val replacements = if (result.size == 1) List.fill(inst.consumed)(DROP(kind)) :+ JUMP(result.keySet.head) - else inst :: Nil - - (result, replacements) - } - - inst match { - case JUMP(whereto) => - (Map((whereto, in)), inst :: Nil) - - case CJUMP(success, failure, cond, kind) => - val in1 = in peek 0 - val in2 = in peek 1 - interpretConditional(kind, in1, in2, success, failure, cond) - - case CZJUMP(success, failure, cond, kind) => - val in1 = in peek 0 - val in2 = getZeroOf(kind) - interpretConditional(kind, in1, in2, success, failure, cond) - - case SWITCH(tags, labels) => - val in1 = in peek 0 - val reachableNormalLabels = tags zip labels collect { case (tagSet, label) if canSwitch(in1, tagSet) => label } - val reachableLabels = if (tags.isEmpty) { - assert(labels.size == 1, s"When SWITCH node has empty array of tags it should have just one (default) label: $labels") - labels - } else if (labels.lengthCompare(tags.length) > 0) { - // if we've got an extra label then it's the default - val defaultLabel = labels.last - // see if the default is reachable by seeing if the input might be out of the set - // of all tags - val allTags = Possible(tags.flatten.toSet map { tag: Int => Const(Constant(tag)) }) - if (in1 mightNotEqual allTags) { - reachableNormalLabels :+ defaultLabel - } else { - reachableNormalLabels - } - } else { - reachableNormalLabels - } - // TODO similar to the comment in interpretConditional, we should update our the State going into each - // branch based on which tag is being matched. Also, just like interpretConditional, if target blocks - // are the same we need to merge State rather than clobber - - // alternative, maybe we should simplify the SWITCH to not have same target labels - val newState = in drop inst.consumed - val result = Map(reachableLabels map { label => (label, newState) }: _*) - if (reachableLabels.size == 1) (result, DROP(INT) :: JUMP(reachableLabels.head) :: Nil) - else (result, inst :: Nil) - - // these instructions don't have target blocks - // (exceptions are assumed to be reachable from all instructions) - case RETURN(_) | THROW(_) => - (Map.empty, inst :: Nil) - - case _ => - dumpClassesAndAbort("Unexpected non-block ending instruction: " + inst) - } - } - - /** - * Analyze a single block to find how it transforms an input state into a states for its successor blocks - * Also computes a list of instructions to be used to replace its last instruction - */ - private def interpretBlock(in: State, block: BasicBlock): (Map[BasicBlock, State], Map[BasicBlock, State], List[Instruction]) = { - debuglog(s"interpreting block $block") - // number of instructions excluding the last one - val normalCount = block.size - 1 - - var exceptionState = in.cleanStack - var normalExitState = in - var idx = 0 - while (idx < normalCount) { - val inst = block(idx) - normalExitState = interpretInst(normalExitState, inst) - if (normalExitState.locals ne exceptionState.locals) - exceptionState = exceptionState.copy(locals = exceptionState mergeLocals normalExitState.locals) - idx += 1 - } - - val pairs = block.exceptionSuccessors map { b => (b, exceptionState) } - val exceptionMap = Map(pairs: _*) - - val (normalExitMap, newInstructions) = interpretLast(normalExitState, block.lastInstruction) - - (normalExitMap, exceptionMap, newInstructions) - } - - /** - * Analyze a single method to find replacement instructions - */ - private def interpretMethod(m: IMethod): Map[BasicBlock, List[Instruction]] = { - import scala.collection.mutable.{ Set => MSet, Map => MMap } - - debuglog(s"interpreting method $m") - var iterations = 0 - - // initially we know that 'this' is not null and the params are initialized to some unknown value - val initThis: Iterator[(Local, Contents)] = if (m.isStatic) Iterator.empty else Iterator.single((THIS_LOCAL, NOT_NULL)) - val initOtherLocals: Iterator[(Local, Contents)] = m.params.iterator map { param => (param, UNKNOWN) } - val initialLocals: Map[Local, Contents] = Map((initThis ++ initOtherLocals).toSeq: _*) - val initialState = State(initialLocals, Nil) - - // worklist of basic blocks to process, initially the start block - val worklist = MSet(m.startBlock) - // worklist of exception basic blocks. They're kept in a separate set so they can be - // processed after normal flow basic blocks. That's because exception basic blocks - // are more likely to have multiple predecessors and queueing them for later - // increases the chances that they'll only need to be interpreted once - val exceptionlist = MSet[BasicBlock]() - // our current best guess at what the input state is for each block - // initially we only know about the start block - val inputState = MMap[BasicBlock, State]((m.startBlock, initialState)) - - // update the inputState map based on new information from interpreting a block - // When the input state of a block changes, add it back to the work list to be - // reinterpreted - def updateInputStates(outputStates: Map[BasicBlock, State], worklist: MSet[BasicBlock]) { - for ((block, newState) <- outputStates) { - val oldState = inputState get block - val updatedState = oldState map (x => x merge newState) getOrElse newState - if (oldState != Some(updatedState)) { - worklist add block - inputState(block) = updatedState - } - } - } - - // the instructions to be used as the last instructions on each block - val replacements = MMap[BasicBlock, List[Instruction]]() - - while (worklist.nonEmpty || exceptionlist.nonEmpty) { - if (worklist.isEmpty) { - // once the worklist is empty, start processing exception blocks - val block = exceptionlist.head - exceptionlist remove block - worklist add block - } else { - iterations += 1 - val block = worklist.head - worklist remove block - val (normalExitMap, exceptionMap, newInstructions) = interpretBlock(inputState(block), block) - - updateInputStates(normalExitMap, worklist) - updateInputStates(exceptionMap, exceptionlist) - replacements(block) = newInstructions - } - } - - debuglog(s"method $m with ${m.blocks.size} reached fixpoint in $iterations iterations") - replacements.toMap - } - } -} diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala deleted file mode 100644 index 8911a3a28c..0000000000 --- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala +++ /dev/null @@ -1,450 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Iulian Dragos - */ - - -package scala.tools.nsc -package backend.opt - -import scala.collection.{ mutable, immutable } - -/** - */ -abstract class DeadCodeElimination extends SubComponent { - import global._ - import icodes._ - import icodes.opcodes._ - import definitions.RuntimePackage - - /** The block and index where an instruction is located */ - type InstrLoc = (BasicBlock, Int) - - val phaseName = "dce" - - override val enabled: Boolean = settings.Xdce - - /** Create a new phase */ - override def newPhase(p: Phase) = new DeadCodeEliminationPhase(p) - - /** Dead code elimination phase. - */ - class DeadCodeEliminationPhase(prev: Phase) extends ICodePhase(prev) { - - def name = phaseName - val dce = new DeadCode() - - override def apply(c: IClass) { - if (settings.Xdce && (dce ne null)) - dce.analyzeClass(c) - } - } - - /** closures that are instantiated at least once, after dead code elimination */ - val liveClosures = perRunCaches.newSet[Symbol]() - - /** closures that are eliminated, populated by GenASM.AsmPhase.run() - * these class symbols won't have a .class physical file, thus shouldn't be included in InnerClasses JVM attribute, - * otherwise some tools get confused or slow (SI-6546) - * */ - val elidedClosures = perRunCaches.newSet[Symbol]() - - /** Remove dead code. - */ - class DeadCode { - - def analyzeClass(cls: IClass) { - log(s"Analyzing ${cls.methods.size} methods in $cls.") - cls.methods.foreach { m => - this.method = m - dieCodeDie(m) - global.closureElimination.peephole(m) - } - } - - val rdef = new reachingDefinitions.ReachingDefinitionsAnalysis - - /** Use-def chain: give the reaching definitions at the beginning of given instruction. */ - var defs: immutable.Map[InstrLoc, immutable.Set[rdef.lattice.Definition]] = immutable.HashMap.empty - - /** Useful instructions which have not been scanned yet. */ - val worklist: mutable.Set[InstrLoc] = new mutable.LinkedHashSet - - /** what instructions have been marked as useful? */ - val useful: mutable.Map[BasicBlock, mutable.BitSet] = perRunCaches.newMap() - - /** what local variables have been accessed at least once? */ - var accessedLocals: List[Local] = Nil - - /** Map from a local and a basic block to the instructions that store to that local in that basic block */ - val localStores = mutable.Map[(Local, BasicBlock), mutable.BitSet]() withDefault {_ => mutable.BitSet()} - - /** Stores that clobber previous stores to array or ref locals. See SI-5313 */ - val clobbers = mutable.Set[InstrLoc]() - - /** the current method. */ - var method: IMethod = _ - - /** Map instructions who have a drop on some control path, to that DROP instruction. */ - val dropOf: mutable.Map[InstrLoc, List[InstrLoc]] = perRunCaches.newMap() - - def dieCodeDie(m: IMethod) { - if (m.hasCode) { - debuglog("dead code elimination on " + m) - dropOf.clear() - localStores.clear() - clobbers.clear() - m.code.blocks.clear() - m.code.touched = true - accessedLocals = m.params.reverse - m.code.blocks ++= linearizer.linearize(m) - m.code.touched = true - collectRDef(m) - mark() - sweep(m) - accessedLocals = accessedLocals.distinct - val diff = m.locals diff accessedLocals - if (diff.nonEmpty) { - val msg = diff.map(_.sym.name)mkString(", ") - log(s"Removed ${diff.size} dead locals: $msg") - m.locals = accessedLocals.reverse - } - } - } - - /** collect reaching definitions and initial useful instructions for this method. */ - def collectRDef(m: IMethod): Unit = if (m.hasCode) { - defs = immutable.HashMap.empty; worklist.clear(); useful.clear() - rdef.init(m) - rdef.run() - - m foreachBlock { bb => - useful(bb) = new mutable.BitSet(bb.size) - var rd = rdef.in(bb) - for ((i, idx) <- bb.toList.zipWithIndex) { - - // utility for adding to worklist - def moveToWorkList() = moveToWorkListIf(cond = true) - - // utility for (conditionally) adding to worklist - def moveToWorkListIf(cond: Boolean) = - if (cond) { - debuglog("in worklist: " + i) - worklist += ((bb, idx)) - } else { - debuglog("not in worklist: " + i) - } - - // instruction-specific logic - i match { - - case LOAD_LOCAL(_) => - defs = defs + (((bb, idx), rd.vars)) - moveToWorkListIf(cond = false) - - case STORE_LOCAL(l) => - /* SI-4935 Check whether a module is stack top, if so mark the instruction that loaded it - * (otherwise any side-effects of the module's constructor go lost). - * (a) The other two cases where a module's value is stored (STORE_FIELD and STORE_ARRAY_ITEM) - * are already marked (case clause below). - * (b) A CALL_METHOD targeting a method `m1` where the receiver is potentially a module (case clause below) - * will have the module's load marked provided `isSideEffecting(m1)`. - * TODO check for purity (the ICode?) of the module's constructor (besides m1's purity). - * See also https://github.com/paulp/scala/blob/topic/purity-analysis/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala - */ - val necessary = rdef.findDefs(bb, idx, 1) exists { p => - val (bb1, idx1) = p - bb1(idx1) match { - case LOAD_MODULE(module) => isLoadNeeded(module) - case _ => false - } - } - moveToWorkListIf(necessary) - - // add it to the localStores map - val key = (l, bb) - val set = localStores(key) - set += idx - localStores(key) = set - - case RETURN(_) | JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | STORE_FIELD(_, _) | - THROW(_) | LOAD_ARRAY_ITEM(_) | STORE_ARRAY_ITEM(_) | SCOPE_ENTER(_) | SCOPE_EXIT(_) | STORE_THIS(_) | - LOAD_EXCEPTION(_) | SWITCH(_, _) | MONITOR_ENTER() | MONITOR_EXIT() | CHECK_CAST(_) | CREATE_ARRAY(_, _) => - moveToWorkList() - - case LOAD_FIELD(sym, isStatic) if isStatic || !inliner.isClosureClass(sym.owner) => - // static load may trigger static initialization. - // non-static load can throw NPE (but we know closure fields can't be accessed via a - // null reference. - moveToWorkList() - case CALL_METHOD(m1, _) if isSideEffecting(m1) => - moveToWorkList() - - case CALL_METHOD(m1, SuperCall(_)) => - moveToWorkList() // super calls to constructor - - case DROP(_) => - val necessary = rdef.findDefs(bb, idx, 1) exists { p => - val (bb1, idx1) = p - bb1(idx1) match { - case CALL_METHOD(m1, _) if isSideEffecting(m1) => true - case LOAD_EXCEPTION(_) | DUP(_) | LOAD_MODULE(_) => true - case _ => - dropOf((bb1, idx1)) = (bb,idx) :: dropOf.getOrElse((bb1, idx1), Nil) - debuglog("DROP is inessential: " + i + " because of: " + bb1(idx1) + " at " + bb1 + ":" + idx1) - false - } - } - moveToWorkListIf(necessary) - case LOAD_MODULE(sym) if isLoadNeeded(sym) => - moveToWorkList() // SI-4859 Module initialization might side-effect. - case CALL_PRIMITIVE(Arithmetic(DIV | REM, INT | LONG) | ArrayLength(_)) => - moveToWorkList() // SI-8601 Might divide by zero - case _ => () - moveToWorkListIf(cond = false) - } - rd = rdef.interpret(bb, idx, rd) - } - } - } - - private def isLoadNeeded(module: Symbol): Boolean = { - module.info.member(nme.CONSTRUCTOR).filter(isSideEffecting) != NoSymbol - } - - /** Mark useful instructions. Instructions in the worklist are each inspected and their - * dependencies are marked useful too, and added to the worklist. - */ - def mark() { -// log("Starting with worklist: " + worklist) - while (!worklist.isEmpty) { - val (bb, idx) = worklist.head - worklist -= ((bb, idx)) - debuglog("Marking instr: \tBB_" + bb + ": " + idx + " " + bb(idx)) - - val instr = bb(idx) - // adds the instructions that define the stack values about to be consumed to the work list to - // be marked useful - def addDefs() = for ((bb1, idx1) <- rdef.findDefs(bb, idx, instr.consumed) if !useful(bb1)(idx1)) { - debuglog(s"\t${bb1(idx1)} is consumed by $instr") - worklist += ((bb1, idx1)) - } - - // DROP logic -- if an instruction is useful, its drops are also useful - // and we don't mark the DROPs as useful directly but add them to the - // worklist so we also mark their reaching defs as useful - see SI-7060 - if (!useful(bb)(idx)) { - useful(bb) += idx - dropOf.get((bb, idx)) foreach { - for ((bb1, idx1) <- _) { - /* - * SI-7060: A drop that we now mark as useful can be reached via several paths, - * so we should follow by marking all its reaching definition as useful too: - */ - debuglog("\tAdding: " + bb1(idx1) + " to the worklist, as a useful DROP.") - worklist += ((bb1, idx1)) - } - } - - // per-instruction logic - instr match { - case LOAD_LOCAL(l1) => - for ((l2, bb1, idx1) <- defs((bb, idx)) if l1 == l2; if !useful(bb1)(idx1)) { - debuglog("\tAdding " + bb1(idx1)) - worklist += ((bb1, idx1)) - } - - case STORE_LOCAL(l1) if l1.kind.isRefOrArrayType => - addDefs() - // see SI-5313 - // search for clobbers of this store if we aren't doing l1 = null - // this doesn't catch the second store in x=null;l1=x; but in practice this catches - // a lot of null stores very cheaply - if (idx == 0 || bb(idx - 1) != CONSTANT(Constant(null))) - findClobbers(l1, bb, idx + 1) - - case nw @ NEW(REFERENCE(sym)) => - assert(nw.init ne null, "null new.init at: " + bb + ": " + idx + "(" + instr + ")") - worklist += findInstruction(bb, nw.init) - if (inliner.isClosureClass(sym)) { - liveClosures += sym - } - - // it may be better to move static initializers from closures to - // the enclosing class, to allow the optimizer to remove more closures. - // right now, the only static fields in closures are created when caching - // 'symbol literals. - case LOAD_FIELD(sym, true) if inliner.isClosureClass(sym.owner) => - log("added closure class for field " + sym) - liveClosures += sym.owner - - case LOAD_EXCEPTION(_) => - () - - case _ => - addDefs() - } - } - } - } - - /** - * Finds and marks all clobbers of the given local starting in the given - * basic block at the given index - * - * Storing to local variables of reference or array type may be indirectly - * observable because it may remove a reference to an object which may allow the object - * to be gc'd. See SI-5313. In this code I call the LOCAL_STORE(s) that immediately follow a - * LOCAL_STORE and that store to the same local "clobbers." If a LOCAL_STORE is marked - * useful then its clobbers must go into the set of clobbers, which will be - * compensated for later - */ - def findClobbers(l: Local, bb: BasicBlock, idx: Int) { - // previously visited blocks tracked to prevent searching forever in a cycle - val inspected = mutable.Set[BasicBlock]() - // our worklist of blocks that still need to be checked - val blocksToBeInspected = mutable.Set[BasicBlock]() - - // Tries to find the next clobber of l1 in bb1 starting at idx1. - // if it finds one it adds the clobber to clobbers set for later - // handling. If not it adds the direct successor blocks to - // the uninspectedBlocks to try to find clobbers there. Either way - // it adds the exception successor blocks for further search - def findClobberInBlock(idx1: Int, bb1: BasicBlock) { - val key = ((l, bb1)) - val foundClobber = (localStores contains key) && { - def minIdx(s : mutable.BitSet) = if(s.isEmpty) -1 else s.min - - // find the smallest index greater than or equal to idx1 - val clobberIdx = minIdx(localStores(key) dropWhile (_ < idx1)) - if (clobberIdx == -1) - false - else { - debuglog(s"\t${bb1(clobberIdx)} is a clobber of ${bb(idx)}") - clobbers += ((bb1, clobberIdx)) - true - } - } - - // always need to look into the exception successors for additional clobbers - // because we don't know when flow might enter an exception handler - blocksToBeInspected ++= (bb1.exceptionSuccessors filterNot inspected) - // If we didn't find a clobber here then we need to look at successor blocks. - // if we found a clobber then we don't need to search in the direct successors - if (!foundClobber) { - blocksToBeInspected ++= (bb1.directSuccessors filterNot inspected) - } - } - - // first search starting at the current index - // note we don't put bb in the inspected list yet because a loop may later force - // us back around to search from the beginning of bb - findClobberInBlock(idx, bb) - // then loop until we've exhausted the set of uninspected blocks - while(!blocksToBeInspected.isEmpty) { - val bb1 = blocksToBeInspected.head - blocksToBeInspected -= bb1 - inspected += bb1 - findClobberInBlock(0, bb1) - } - } - - def sweep(m: IMethod) { - val compensations = computeCompensations(m) - - debuglog("Sweeping: " + m) - - m foreachBlock { bb => - debuglog(bb + ":") - val oldInstr = bb.toList - bb.open() - bb.clear() - for ((i, idx) <- oldInstr.zipWithIndex) { - if (useful(bb)(idx)) { - debuglog(" * " + i + " is useful") - bb.emit(i, i.pos) - compensations.get((bb, idx)) match { - case Some(is) => is foreach bb.emit - case None => () - } - // check for accessed locals - i match { - case LOAD_LOCAL(l) if !l.arg => - accessedLocals = l :: accessedLocals - case STORE_LOCAL(l) if !l.arg => - accessedLocals = l :: accessedLocals - case _ => () - } - } else { - i match { - case NEW(REFERENCE(sym)) => - log(s"Eliminated instantiation of $sym inside $m") - case STORE_LOCAL(l) if clobbers contains ((bb, idx)) => - // if an unused instruction was a clobber of a used store to a reference or array type - // then we'll replace it with the store of a null to make sure the reference is - // eliminated. See SI-5313 - bb emit CONSTANT(Constant(null)) - bb emit STORE_LOCAL(l) - case _ => () - } - debuglog(" " + i + " [swept]") - } - } - - if (bb.nonEmpty) bb.close() - else log(s"empty block encountered in $m") - } - } - - private def computeCompensations(m: IMethod): mutable.Map[InstrLoc, List[Instruction]] = { - val compensations: mutable.Map[InstrLoc, List[Instruction]] = new mutable.HashMap - - m foreachBlock { bb => - assert(bb.closed, "Open block in computeCompensations") - foreachWithIndex(bb.toList) { (i, idx) => - if (!useful(bb)(idx)) { - foreachWithIndex(i.consumedTypes.reverse) { (consumedType, depth) => - debuglog("Finding definitions of: " + i + "\n\t" + consumedType + " at depth: " + depth) - val defs = rdef.findDefs(bb, idx, 1, depth) - for (d <- defs) { - val (bb, idx) = d - debuglog("rdef: "+ bb(idx)) - bb(idx) match { - case DUP(_) if idx > 0 => - bb(idx - 1) match { - case nw @ NEW(_) => - val init = findInstruction(bb, nw.init) - log("Moving DROP to after <init> call: " + nw.init) - compensations(init) = List(DROP(consumedType)) - case _ => - compensations(d) = List(DROP(consumedType)) - } - case _ => - compensations(d) = List(DROP(consumedType)) - } - } - } - } - } - } - compensations - } - - private def findInstruction(bb: BasicBlock, i: Instruction): InstrLoc = { - for (b <- linearizer.linearizeAt(method, bb)) { - val idx = b.toList indexWhere (_ eq i) - if (idx != -1) - return (b, idx) - } - abort("could not find init in: " + method) - } - - private def isPure(sym: Symbol) = ( - (sym.isGetter && sym.isEffectivelyFinalOrNotOverridden && !sym.isLazy) - || (sym.isPrimaryConstructor && (sym.enclosingPackage == RuntimePackage || inliner.isClosureClass(sym.owner))) - ) - /** Is 'sym' a side-effecting method? TODO: proper analysis. */ - private def isSideEffecting(sym: Symbol) = !isPure(sym) - - } /* DeadCode */ -} diff --git a/src/compiler/scala/tools/nsc/backend/opt/InlineExceptionHandlers.scala b/src/compiler/scala/tools/nsc/backend/opt/InlineExceptionHandlers.scala deleted file mode 100644 index 9f6883f03f..0000000000 --- a/src/compiler/scala/tools/nsc/backend/opt/InlineExceptionHandlers.scala +++ /dev/null @@ -1,392 +0,0 @@ -/* NSC -- new scala compiler - * Copyright 2005-2013 LAMP/EPFL - */ - -package scala.tools.nsc -package backend.opt - -import java.util.concurrent.TimeUnit - -/** - * This optimization phase inlines the exception handlers so that further phases can optimize the code better - * - * {{{ - * try { - * ... - * if (condition) - * throw IllegalArgumentException("sth") - * } catch { - * case e: IllegalArgumentException => <handler code> - * case e: ... => ... - * } - * }}} - * - * will inline the exception handler code to: - * - * {{{ - * try { - * ... - * if (condition) - * <handler code> // + jump to the end of the catch statement - * } catch { - * case e: IllegalArgumentException => <handler code> - * case e: ... => ... - * } - * }}} - * - * Q: How does the inlining work, ICode level? - * A: if a block contains a THROW(A) instruction AND there is a handler that takes A or a superclass of A we do: - * 1. We duplicate the handler code such that we can transform THROW into a JUMP - * 2. We analyze the handler to see what local it expects the exception to be placed in - * 3. We place the exception that is thrown in the correct "local variable" slot and clean up the stack - * 4. We finally JUMP to the duplicate handler - * All the above logic is implemented in InlineExceptionHandlersPhase.apply(bblock: BasicBlock) - * - * Q: Why do we need to duplicate the handler? - * A: An exception might be thrown in a method that we invoke in the function and we cannot see that THROW command - * directly. In order to catch such exceptions, we keep the exception handler in place and duplicate it in order - * to inline its code. - * - * @author Vlad Ureche - */ -abstract class InlineExceptionHandlers extends SubComponent { - import global._ - import icodes._ - import icodes.opcodes._ - - val phaseName = "inlinehandlers" - - /** Create a new phase */ - override def newPhase(p: Phase) = new InlineExceptionHandlersPhase(p) - - override def enabled = settings.inlineHandlers - - /** - * Inlining Exception Handlers - */ - class InlineExceptionHandlersPhase(prev: Phase) extends ICodePhase(prev) { - def name = phaseName - - /* This map is used to keep track of duplicated exception handlers - * explanation: for each exception handler basic block, there is a copy of it - * -some exception handler basic blocks might not be duplicated because they have an unknown format => Option[(...)] - * -some exception handler duplicates expect the exception on the stack while others expect it in a local - * => Option[Local] - */ - private val handlerCopies = perRunCaches.newMap[BasicBlock, Option[(Option[Local], BasicBlock)]]() - /* This map is the inverse of handlerCopies, used to compute the stack of duplicate blocks */ - private val handlerCopiesInverted = perRunCaches.newMap[BasicBlock, (BasicBlock, TypeKind)]() - private def handlerLocal(bb: BasicBlock): Option[Local] = - for (v <- handlerCopies get bb ; (local, block) <- v ; l <- local) yield l - - /* Type Flow Analysis */ - private val tfa: analysis.MethodTFA = new analysis.MethodTFA() - private var tfaCache: Map[Int, tfa.lattice.Elem] = Map.empty - private var analyzedMethod: IMethod = NoIMethod - - /* Blocks that need to be analyzed */ - private var todoBlocks: List[BasicBlock] = Nil - - /* Used only for warnings */ - private var currentClass: IClass = null - - /** Apply exception handler inlining to a class */ - override def apply(c: IClass): Unit = - if (settings.inlineHandlers) { - val startTime = System.nanoTime() - currentClass = c - - debuglog("Starting InlineExceptionHandlers on " + c) - c.methods foreach applyMethod - debuglog("Finished InlineExceptionHandlers on " + c + "... " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime) + "ms") - currentClass = null - } - - /** - * Apply exception handler inlining to a method - * - * Note: for each exception handling block, we (might) create duplicates. Therefore we iterate until we get to a - * fixed point where all the possible handlers have been inlined. - * - * TODO: Should we have an inlining depth limit? A nested sequence of n try-catch blocks can lead to at most 2n - * inlined blocks, so worst case scenario we double the size of the code - */ - private def applyMethod(method: IMethod): Unit = { - if (method.hasCode) { - // create the list of starting blocks - todoBlocks = global.icodes.linearizer.linearize(method) - - while (todoBlocks.nonEmpty) { - val levelBlocks = todoBlocks - todoBlocks = Nil - levelBlocks foreach applyBasicBlock // new blocks will be added to todoBlocks - } - } - - // Cleanup the references after we finished the file - handlerCopies.clear() - handlerCopiesInverted.clear() - todoBlocks = Nil - - // Type flow analysis cleanup - analyzedMethod = NoIMethod - tfaCache = Map.empty - //TODO: Need a way to clear tfa structures - } - - /** Apply exception handler inlining to a basic block */ - private def applyBasicBlock(bblock: BasicBlock): Unit = { - /* - * The logic of this entire method: - * - for each basic block, we look at each instruction until we find a THROW instruction - * - once we found a THROW instruction, we decide if it is DECIDABLE which of handler will catch the exception - * (see method findExceptionHandler for more details) - * - if we decided there is a handler that will catch the exception, we need to replace the THROW instruction by - * a set of equivalent instructions: - * * we need to compute the static types of the stack slots - * * we need to clear the stack, everything but the exception instance on top (or in a local variable slot) - * * we need to JUMP to the duplicate exception handler - * - we compute the static types of the stack slots in function getTypesAtInstruction - * - we duplicate the exception handler (and we get back the information of whether the duplicate expects the - * exception instance on top of the stack or in a local variable slot) - * - we compute the necessary code to put the exception in its place, clear the stack and JUMP - * - we change the THROW exception to the new Clear stack + JUMP code - */ - for { - (instr @ THROW(clazz), index) <- bblock.iterator.zipWithIndex - // Decide if any handler fits this exception - // If not, then nothing to do, we cannot determine statically which handler will catch the exception - (handler, caughtException) <- findExceptionHandler(toTypeKind(clazz.tpe), bblock.exceptionSuccessors) - } { - log(" Replacing " + instr + " in " + bblock + " to new handler") - - // Solve the stack and drop the element that we already stored, which should be the exception - // needs to be done here to be the first thing before code becomes altered - val typeInfo = getTypesAtInstruction(bblock, index) - - // Duplicate exception handler - duplicateExceptionHandlerCache(handler) match { - case None => - log(" Could not duplicate handler for " + instr + " in " + bblock) - - case Some((exceptionLocalOpt, newHandler)) => - val onStackException = typeInfo.head - val thrownException = toTypeKind(clazz.tpe) - - // A couple of sanity checks, to make sure we don't touch code we can't safely handle - val canReplaceHandler = ( - typeInfo.nonEmpty - && (index == bblock.length - 1) - && (onStackException <:< thrownException) - ) - // in other words: what's on the stack MUST conform to what's in the THROW(..)! - - if (!canReplaceHandler) { - reporter.warning(NoPosition, "Unable to inline the exception handler inside incorrect" + - " block:\n" + bblock.iterator.mkString("\n") + "\nwith stack: " + typeInfo + " just " + - "before instruction index " + index) - } - else { - // Prepare the new code to replace the THROW instruction - val newCode = exceptionLocalOpt match { - // the handler duplicate expects the exception in a local: easy one :) - case Some(local) => - // in the first cycle we remove the exception Type - STORE_LOCAL(local) +: typeInfo.tail.map(x => DROP(x)) :+ JUMP(newHandler) - - // we already have the exception on top of the stack, only need to JUMP - case None if typeInfo.length == 1 => - JUMP(newHandler) :: Nil - - // we have the exception on top of the stack but we have other stuff on the stack - // create a local, load exception, clear the stack and finally store the exception on the stack - case _ => - val exceptionType = typeInfo.head - // Here we could create a single local for all exceptions of a certain type. TODO: try that. - val localName = currentClass.cunit.freshTermName("exception$") - val localType = exceptionType - val localSymbol = bblock.method.symbol.newValue(localName).setInfo(localType.toType) - val local = new Local(localSymbol, localType, false) - - bblock.method.addLocal(local) - - // Save the exception, drop the stack and place back the exception - STORE_LOCAL(local) :: typeInfo.tail.map(x => DROP(x)) ::: List(LOAD_LOCAL(local), JUMP(newHandler)) - } - // replace THROW by the new code - bblock.replaceInstruction(instr, newCode) - - // notify the successors changed for the current block - // notify the predecessors changed for the inlined handler block - bblock.touched = true - newHandler.touched = true - - log(" Replaced " + instr + " in " + bblock + " to new handler") - log("OPTIMIZED class " + currentClass + " method " + - bblock.method + " block " + bblock + " newhandler " + - newHandler + ":\n\t\t" + onStackException + " <:< " + - thrownException + " <:< " + caughtException) - - } - } - } - } - - /** - * Gets the types on the stack at a certain point in the program. Note that we want to analyze the method lazily - * and therefore use the analyzedMethod variable - */ - private def getTypesAtInstruction(bblock: BasicBlock, index: Int): List[TypeKind] = { - // get the stack at the block entry - var typeInfo = getTypesAtBlockEntry(bblock) - - // perform tfa to the current instruction - log(" stack at the beginning of block " + bblock + " in function " + - bblock.method + ": " + typeInfo.stack) - for (i <- 0 to (index - 1)) { - typeInfo = tfa.interpret(typeInfo, bblock(i)) - log(" stack after interpret: " + typeInfo.stack + " after instruction " + - bblock(i)) - } - log(" stack before instruction " + index + " of block " + bblock + " in function " + - bblock.method + ": " + typeInfo.stack) - - // return the result - typeInfo.stack.types - } - - /** - * Gets the stack at the block entry. Normally the typeFlowAnalysis should be run again, but we know how to compute - * the stack for handler duplicates. For the locals, it's safe to assume the info from the original handler is - * still valid (a more precise analysis can be done, but it's not necessary) - */ - private def getTypesAtBlockEntry(bblock: BasicBlock): tfa.lattice.Elem = { - // lazily perform tfa, because it's expensive - // cache results by block label, as rewriting the code messes up the block's hashCode - if (analyzedMethod eq NoIMethod) { - analyzedMethod = bblock.method - tfa.init(bblock.method) - tfa.run() - log(" performed tfa on method: " + bblock.method) - - for (block <- bblock.method.blocks.sortBy(_.label)) - tfaCache += block.label -> tfa.in(block) - } - - log(" getting typeinfo at the beginning of block " + bblock) - - tfaCache.getOrElse(bblock.label, { - // this block was not analyzed, but it's a copy of some other block so its stack should be the same - log(" getting typeinfo at the beginning of block " + bblock + " as a copy of " + - handlerCopiesInverted(bblock)) - val (origBlock, exception) = handlerCopiesInverted(bblock) - val typeInfo = getTypesAtBlockEntry(origBlock) - val stack = - if (handlerLocal(origBlock).nonEmpty) Nil // empty stack, the handler copy expects an empty stack - else List(exception) // one slot on the stack for the exception - - // If we use the mutability property, it crashes the analysis - tfa.lattice.IState(new analysis.VarBinding(typeInfo.vars), new icodes.TypeStack(stack)) - }) - } - - /** - * Finds the first exception handler that matches the current exception - * - * Note the following code: - * {{{ - * try { - * throw new IllegalArgumentException("...") - * } catch { - * case e: RuntimeException => log("RuntimeException") - * case i: IllegalArgumentException => log("IllegalArgumentException") - * } - * }}} - * - * will print "RuntimeException" => we need the *first* valid handler - * - * There's a hidden catch here: say we have the following code: - * {{{ - * try { - * val exception: Throwable = - * if (scala.util.Random.nextInt % 2 == 0) - * new IllegalArgumentException("even") - * else - * new StackOverflowError("odd") - * throw exception - * } catch { - * case e: IllegalArgumentException => - * println("Correct, IllegalArgumentException") - * case e: StackOverflowError => - * println("Correct, StackOverflowException") - * case t: Throwable => - * println("WROOOONG, not Throwable!") - * } - * }}} - * - * We don't want to select a handler if there's at least one that's more specific! - */ - def findExceptionHandler(thrownException: TypeKind, handlers: List[BasicBlock]): Option[(BasicBlock, TypeKind)] = { - for (handler <- handlers ; LOAD_EXCEPTION(clazz) <- handler take 1) { - val caughtException = toTypeKind(clazz.tpe) - // we'll do inlining here: createdException <:< thrownException <:< caughtException, good! - if (thrownException <:< caughtException) - return Some((handler, caughtException)) - // we can't do inlining here, the handling mechanism is more precise than we can reason about - if (caughtException <:< thrownException) - return None - // no result yet, look deeper in the handler stack - } - None - } - - /** - * This function takes care of duplicating the basic block code for inlining the handler - * - * Note: This function does not duplicate the same basic block twice. It will contain a map of the duplicated - * basic blocks - */ - private def duplicateExceptionHandlerCache(handler: BasicBlock) = - handlerCopies.getOrElseUpdate(handler, duplicateExceptionHandler(handler)) - - /** This function takes care of actual duplication */ - private def duplicateExceptionHandler(handler: BasicBlock): Option[(Option[Local], BasicBlock)] = { - log(" duplicating handler block " + handler) - - handler take 2 match { - case Seq(LOAD_EXCEPTION(caughtClass), next) => - val (dropCount, exceptionLocal) = next match { - case STORE_LOCAL(local) => (2, Some(local)) // we drop both LOAD_EXCEPTION and STORE_LOCAL - case _ => (1, None) // we only drop the LOAD_EXCEPTION and expect the exception on the stack - } - val caughtException = toTypeKind(caughtClass.tpe) - // copy the exception handler code once again, dropping the LOAD_EXCEPTION - val copy = handler.code.newBlock() - copy.emitOnly((handler.iterator drop dropCount).toSeq: _*) - - // extend the handlers of the handler to the copy - for (parentHandler <- handler.method.exh ; if parentHandler covers handler) { - parentHandler.addCoveredBlock(copy) - // notify the parent handler that the successors changed - parentHandler.startBlock.touched = true - } - - // notify the successors of the inlined handler might have changed - copy.touched = true - handler.touched = true - log(" duplicated handler block " + handler + " to " + copy) - - // announce the duplicate handler - handlerCopiesInverted(copy) = ((handler, caughtException)) - todoBlocks ::= copy - - Some((exceptionLocal, copy)) - - case _ => - reporter.warning(NoPosition, "Unable to inline the exception handler due to incorrect format:\n" + - handler.iterator.mkString("\n")) - None - } - } - } -} diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala deleted file mode 100644 index 8cd2a14066..0000000000 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ /dev/null @@ -1,1075 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL - * @author Iulian Dragos - */ - - -package scala.tools.nsc -package backend.opt - -import scala.collection.mutable -import scala.tools.nsc.symtab._ -import scala.reflect.internal.util.NoSourceFile - -/** - * Inliner balances two competing goals: - * (a) aggressive inlining of: - * (a.1) the apply methods of anonymous closures, so that their anon-classes can be eliminated; - * (a.2) higher-order-methods defined in an external library, e.g. `Range.foreach()` among many others. - * (b) circumventing the barrier to inter-library inlining that private accesses in the callee impose. - * - * Summing up the discussion in SI-5442 and SI-5891, - * the current implementation achieves to a large degree both goals above, and - * overcomes a problem exhibited by previous versions: - * - * (1) Problem: Attempting to access a private member `p` at runtime resulting in an `IllegalAccessError`, - * where `p` is defined in a library L, and is accessed from a library C (for Client), - * where C was compiled against L', an optimized version of L where the inliner made `p` public at the bytecode level. - * The only such members are fields, either synthetic or isParamAccessor, and thus having a dollar sign in their name - * (the accessibility of methods and constructors isn't touched by the inliner). - * - * Thus we add one more goal to our list: - * (c) Compile C (either optimized or not) against any of L or L', - * so that it runs with either L or L' (in particular, compile against L' and run with L). - * - * The chosen strategy is described in some detail in the comments for `accessRequirements()` and `potentiallyPublicized()`. - * Documentation at http://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/2011Q4/Inliner.pdf - * - * @author Iulian Dragos - */ -abstract class Inliners extends SubComponent { - import global._ - import icodes._ - import icodes.opcodes._ - import definitions.{ - NullClass, NothingClass, ObjectClass, - PredefModule, RuntimePackage, ScalaInlineClass, ScalaNoInlineClass, - isFunctionType, isByNameParamType - } - - val phaseName = "inliner" - - override val enabled: Boolean = settings.inline - - /** Debug - for timing the inliner. */ - /**** - private def timed[T](s: String, body: => T): T = { - val t1 = System.currentTimeMillis() - val res = body - val t2 = System.currentTimeMillis() - val ms = (t2 - t1).toInt - if (ms >= MAX_INLINE_MILLIS) - println("%s: %d milliseconds".format(s, ms)) - - res - } - ****/ - - /** Look up implementation of method 'sym in 'clazz'. - */ - def lookupImplFor(sym: Symbol, clazz: Symbol): Symbol = { - // TODO: verify that clazz.superClass is equivalent here to clazz.tpe.parents(0).typeSymbol (.tpe vs .info) - def needsLookup = ( - (clazz != NoSymbol) - && (clazz != sym.owner) - && !sym.isEffectivelyFinalOrNotOverridden - && clazz.isEffectivelyFinalOrNotOverridden - ) - def lookup(clazz: Symbol): Symbol = { - // println("\t\tlooking up " + meth + " in " + clazz.fullName + " meth.owner = " + meth.owner) - assert(clazz != NoSymbol, "Walked up past Object.superClass looking for " + sym + - ", most likely this reveals the TFA at fault (receiver and callee don't match).") - if (sym.owner == clazz || isBottomType(clazz)) sym - else sym.overridingSymbol(clazz) orElse ( - if (sym.owner.isTrait) sym - else lookup(clazz.superClass) - ) - } - if (needsLookup) { - val concreteMethod = lookup(clazz) - debuglog("\tlooked up method: " + concreteMethod.fullName) - - concreteMethod - } - else sym - } - - /* A warning threshold */ - private final val MAX_INLINE_MILLIS = 2000 - - /** The maximum size in basic blocks of methods considered for inlining. */ - final val MAX_INLINE_SIZE = 16 - - /** Maximum loop iterations. */ - final val MAX_INLINE_RETRY = 15 - - /** Small method size (in blocks) */ - val SMALL_METHOD_SIZE = 1 - - /** Create a new phase */ - override def newPhase(p: Phase) = new InliningPhase(p) - - /** The Inlining phase. - */ - class InliningPhase(prev: Phase) extends ICodePhase(prev) { - def name = phaseName - val inliner = new Inliner - - object iclassOrdering extends Ordering[IClass] { - def compare(a: IClass, b: IClass) = { - val sourceNamesComparison = (a.cunit.toString() compare b.cunit.toString()) - if(sourceNamesComparison != 0) sourceNamesComparison - else { - val namesComparison = (a.toString() compare b.toString()) - if(namesComparison != 0) namesComparison - else { - a.symbol.id compare b.symbol.id - } - } - } - } - val queue = new mutable.PriorityQueue[IClass]()(iclassOrdering) - - override def apply(c: IClass) { queue += c } - - override def run() { - knownLacksInline.clear() - knownHasInline.clear() - try { - super.run() - for(c <- queue) { inliner analyzeClass c } - } finally { - inliner.clearCaches() - knownLacksInline.clear() - knownHasInline.clear() - } - } - } - - def isBottomType(sym: Symbol) = sym == NullClass || sym == NothingClass - - /** Is the given class a closure? */ - def isClosureClass(cls: Symbol): Boolean = - cls.isFinal && cls.isSynthetic && !cls.isModuleClass && cls.isAnonymousFunction - - /* - TODO now that Inliner runs faster we could consider additional "monadic methods" (in the limit, all those taking a closure as last arg) - Any "monadic method" occurring in a given caller C that is not `isMonadicMethod()` will prevent CloseElim from eliminating - any anonymous-closure-class any whose instances are given as argument to C invocations. - */ - def isMonadicMethod(sym: Symbol) = { - nme.unspecializedName(sym.name) match { - case nme.foreach | nme.filter | nme.withFilter | nme.map | nme.flatMap => true - case _ => false - } - } - - val knownLacksInline = mutable.Set.empty[Symbol] // cache to avoid multiple inliner.hasInline() calls. - val knownHasInline = mutable.Set.empty[Symbol] // as above. Motivated by the need to warn on "inliner failures". - - def hasInline(sym: Symbol) = { - if (knownLacksInline(sym)) false - else if(knownHasInline(sym)) true - else { - val b = (sym hasAnnotation ScalaInlineClass) - if(b) { knownHasInline += sym } - else { knownLacksInline += sym } - - b - } - } - - def hasNoInline(sym: Symbol) = sym hasAnnotation ScalaNoInlineClass - - /** - * Simple inliner. - */ - class Inliner { - object NonPublicRefs extends Enumeration { - val Private, Protected, Public = Value - - /** Cache whether a method calls private members. */ - val usesNonPublics = mutable.Map.empty[IMethod, Value] - } - import NonPublicRefs._ - - /** The current iclass */ - private var currentIClazz: IClass = _ - private def warn(pos: Position, msg: String) = currentRun.reporting.inlinerWarning(pos, msg) - - private def ownedName(sym: Symbol): String = exitingUncurry { - val count = ( - if (!sym.isMethod) 1 - else if (sym.owner.isAnonymousFunction) 3 - else 2 - ) - (sym.ownerChain take count filterNot (_.isPackageClass)).reverseMap(_.nameString).mkString(".") - } - private def inlineLog(what: String, main: => String, comment: => String) { - def cstr = comment match { - case "" => "" - case str => " // " + str - } - val width = if (currentIClazz eq null) 40 else currentIClazz.symbol.enclosingPackage.fullName.length + 25 - val fmt = "%8s %-" + width + "s" + cstr - log(fmt.format(what, main)) - } - private def inlineLog(what: String, main: Symbol, comment: => String) { - inlineLog(what, ownedName(main), comment) - } - - val recentTFAs = mutable.Map.empty[Symbol, Tuple2[Boolean, analysis.MethodTFA]] - - private def getRecentTFA(incm: IMethod, forceable: Boolean): (Boolean, analysis.MethodTFA) = { - - def containsRETURN(blocks: List[BasicBlock]) = blocks exists { bb => bb.lastInstruction.isInstanceOf[RETURN] } - - val opt = recentTFAs.get(incm.symbol) - if(opt.isDefined) { - // FYI val cachedBBs = opt.get._2.in.keySet - // FYI assert(incm.blocks.toSet == cachedBBs) - // incm.code.touched plays no role here - return opt.get - } - - val hasRETURN = containsRETURN(incm.code.blocksList) || (incm.exh exists { eh => containsRETURN(eh.blocks) }) - var a: analysis.MethodTFA = null - if(hasRETURN) { a = new analysis.MethodTFA(incm); a.run() } - - if(forceable) { recentTFAs.put(incm.symbol, (hasRETURN, a)) } - - (hasRETURN, a) - } - - def clearCaches() { - // methods - NonPublicRefs.usesNonPublics.clear() - recentTFAs.clear() - tfa.knownUnsafe.clear() - tfa.knownSafe.clear() - tfa.knownNever.clear() - // basic blocks - tfa.preCandidates.clear() - tfa.relevantBBs.clear() - // callsites - tfa.remainingCALLs.clear() - tfa.isOnWatchlist.clear() - } - - object imethodOrdering extends Ordering[IMethod] { - def compare(a: IMethod, b: IMethod) = { - val namesComparison = (a.toString() compare b.toString()) - if(namesComparison != 0) namesComparison - else { - a.symbol.id compare b.symbol.id - } - } - } - - def analyzeClass(cls: IClass): Unit = - if (settings.inline) { - inlineLog("class", s"${cls.symbol.decodedName}", s"analyzing ${cls.methods.size} methods in $cls") - - this.currentIClazz = cls - val ms = cls.methods sorted imethodOrdering - ms foreach { im => - if (hasInline(im.symbol)) { - inlineLog("skip", im.symbol, "no inlining into @inline methods") - } - else if(im.hasCode && !im.symbol.isBridge) { - analyzeMethod(im) - } - } - } - - val tfa = new analysis.MTFAGrowable() - tfa.stat = global.settings.YstatisticsEnabled - val staleOut = new mutable.ListBuffer[BasicBlock] - val splicedBlocks = mutable.Set.empty[BasicBlock] - val staleIn = mutable.Set.empty[BasicBlock] - - /** - * A transformation local to the body of the IMethod received as argument. - * An inlining decision consists in replacing a callsite with the body of the callee. - * Please notice that, because `analyzeMethod()` itself may modify a method body, - * the particular callee bodies that end up being inlined depend on the particular order in which methods are visited - * (no topological sorting over the call-graph is attempted). - * - * Making an inlining decision requires type-flow information for both caller and callee. - * Regarding the caller, such information is needed only for basic blocks containing inlining candidates - * (and their transitive predecessors). This observation leads to using a custom type-flow analysis (MTFAGrowable) - * that can be re-inited, i.e. that reuses lattice elements (type-flow information computed in a previous iteration) - * as starting point for faster convergence in a new iteration. - * - * The mechanics of inlining are iterative for a given invocation of `analyzeMethod(m)`, - * and are affected by inlinings from previous iterations - * (ie, "heuristic" rules are based on statistics tracked for that purpose): - * - * (1) before the iterations proper start, so-called preinlining is performed. - * Those callsites whose (receiver, concreteMethod) are both known statically - * can be analyzed for inlining before computing a type-flow. Details in `preInline()` - * - * (2) the first iteration computes type-flow information for basic blocks containing inlining candidates - * (and their transitive predecessors), so called `relevantBBs` basic blocks. - * The ensuing analysis of each candidate (performed by `analyzeInc()`) - * may result in a CFG isomorphic to that of the callee being inserted in place of the callsite - * (i.e. a CALL_METHOD instruction is replaced with a single-entry single-exit CFG, - * a substitution we call "successful inlining"). - * - * (3) following iterations have `relevantBBs` updated to focus on the inlined basic blocks and their successors only. - * Details in `MTFAGrowable.reinit()` - * */ - def analyzeMethod(m: IMethod): Unit = { - // m.normalize - if (settings.debug) - inlineLog("caller", ownedName(m.symbol), "in " + m.symbol.owner.fullName) - - val sizeBeforeInlining = m.code.blockCount - val instrBeforeInlining = m.code.instructionCount - var retry = false - var count = 0 - - // fresh name counter - val fresh = mutable.HashMap.empty[String, Int] withDefaultValue 0 - // how many times have we already inlined this method here? - val inlinedMethodCount = mutable.HashMap.empty[Symbol, Int] withDefaultValue 0 - val caller = new IMethodInfo(m) - def analyzeMessage = s"Analyzing ${caller.length} blocks of $m for inlining sites." - - def preInline(isFirstRound: Boolean): Int = { - val inputBlocks = caller.m.linearizedBlocks() - val callsites: Function1[BasicBlock, List[opcodes.CALL_METHOD]] = { - if(isFirstRound) tfa.conclusives else tfa.knownBeforehand - } - inlineWithoutTFA(inputBlocks, callsites) - } - - /* - * Inline straightforward callsites (those that can be inlined without a TFA). - * - * To perform inlining, all we need to know is listed as formal params in `analyzeInc()`: - * - callsite and block containing it - * - actual (ie runtime) class of the receiver - * - actual (ie runtime) method being invoked - * - stack length just before the callsite (to check whether enough arguments have been pushed). - * The assert below lists the conditions under which "no TFA is needed" - * (the statically known receiver and method are both final, thus, at runtime they can't be any others than those). - * - */ - def inlineWithoutTFA(inputBlocks: Traversable[BasicBlock], callsites: Function1[BasicBlock, List[opcodes.CALL_METHOD]]): Int = { - var inlineCount = 0 - import scala.util.control.Breaks._ - for(x <- inputBlocks; easyCake = callsites(x); if easyCake.nonEmpty) { - breakable { - for(ocm <- easyCake) { - assert(ocm.method.isEffectivelyFinalOrNotOverridden && ocm.method.owner.isEffectivelyFinalOrNotOverridden) - if(analyzeInc(ocm, x, ocm.method.owner, -1, ocm.method)) { - inlineCount += 1 - break() - } - } - } - } - - inlineCount - } - - /* - * Decides whether it's feasible and desirable to inline the body of the method given by `concreteMethod` - * at the program point given by `i` (a callsite). The boolean result indicates whether inlining was performed. - * - */ - def analyzeInc(i: CALL_METHOD, bb: BasicBlock, receiver: Symbol, stackLength: Int, concreteMethod: Symbol): Boolean = { - assert(bb.toList contains i, "Candidate callsite does not belong to BasicBlock.") - val shouldWarn = hasInline(i.method) - - def warnNoInline(reason: String): Boolean = { - def msg = "Could not inline required method %s because %s.".format(i.method.unexpandedName.decode, reason) - if (settings.debug) - inlineLog("fail", i.method.fullName, reason) - if (shouldWarn) - warn(i.pos, msg) - - false - } - - var isAvailable = icodes available concreteMethod.enclClass - - if (!isAvailable && shouldLoadImplFor(concreteMethod, receiver)) { - // Until r22824 this line was: - // icodes.icode(concreteMethod.enclClass, true) - // - // Changing it to - // icodes.load(concreteMethod.enclClass) - // was the proximate cause for SI-3882: - // error: Illegal index: 0 overlaps List((variable par1,LONG)) - // error: Illegal index: 0 overlaps List((variable par1,LONG)) - isAvailable = icodes.load(concreteMethod.enclClass) - } - - def isCandidate = ( - isClosureClass(receiver) - || concreteMethod.isEffectivelyFinalOrNotOverridden - || receiver.isEffectivelyFinalOrNotOverridden - ) - - def isApply = concreteMethod.name == nme.apply - - def isCountable = !( - isClosureClass(receiver) - || isApply - || isMonadicMethod(concreteMethod) - || receiver.enclosingPackage == definitions.RuntimePackage - ) // only count non-closures - - debuglog("Treating " + i - + "\n\treceiver: " + receiver - + "\n\ticodes.available: " + isAvailable - + "\n\tconcreteMethod.isEffectivelyFinalOrNotOverridden: " + concreteMethod.isEffectivelyFinalOrNotOverridden) - - if (!isCandidate) warnNoInline("it can be overridden") - else if (!isAvailable) warnNoInline("bytecode unavailable") - else lookupIMethod(concreteMethod, receiver) filter (callee => callee.hasCode || warnNoInline("callee has no code")) exists { callee => - val inc = new IMethodInfo(callee) - val pair = new CallerCalleeInfo(caller, inc, fresh, inlinedMethodCount) - - if (inc.hasHandlers && (stackLength == -1)) { - // no inlining is done, yet don't warn about it, stackLength == -1 indicates we're trying to inlineWithoutTFA. - // Shortly, a TFA will be computed and an error message reported if indeed inlining not possible. - false - } - else { - val isSafe = pair isStampedForInlining stackLength match { - case DontInlineHere(msg) => warnNoInline(msg) - case NeverSafeToInline => false - case InlineableAtThisCaller => true - case FeasibleInline(required, toPublicize) => - for (f <- toPublicize) { - inlineLog("access", f, "making public") - f setFlag Flags.notPRIVATE - f setFlag Flags.notPROTECTED - } - // only add to `knownSafe` after all `toPublicize` fields actually made public. - if (required == NonPublicRefs.Public) - tfa.knownSafe += inc.sym - - true - } - isSafe && { - retry = true - if (isCountable) count += 1 - pair.doInline(bb, i) - if (!pair.isInlineForced || inc.isMonadic) caller.inlinedCalls += 1 - inlinedMethodCount(inc.sym) += 1 - - // Remove the caller from the cache (this inlining might have changed its calls-private relation). - usesNonPublics -= m - recentTFAs -= m.symbol - true - } - } - } - } - - /* Pre-inlining consists in invoking the usual inlining subroutine with (receiver class, concrete method) pairs as input - * where both method and receiver are final, which implies that the receiver computed via TFA will always match `concreteMethod.owner`. - * - * As with any invocation of `analyzeInc()` the inlining outcome is based on heuristics which favor inlining an isMonadicMethod before other methods. - * That's why preInline() is invoked twice: any inlinings downplayed by the heuristics during the first round get an opportunity to rank higher during the second. - * - * As a whole, both `preInline()` invocations amount to priming the inlining process, - * so that the first TFA that is run afterwards is able to gain more information as compared to a cold-start. - */ - /*val totalPreInlines = */ { // Val name commented out to emphasize it is never used - val firstRound = preInline(isFirstRound = true) - if(firstRound == 0) 0 else (firstRound + preInline(isFirstRound = false)) - } - staleOut.clear() - splicedBlocks.clear() - staleIn.clear() - - do { - retry = false - debuglog(analyzeMessage) - - /* it's important not to inline in unreachable basic blocks. linearizedBlocks() returns only reachable ones. */ - tfa.callerLin = caller.m.linearizedBlocks() - /* TODO Do we really want to inline inside exception handlers? - * Seems counterproductive (the larger the method the less likely it will be JITed). - * The alternative would be `linearizer.linearizeAt(caller.m, caller.m.startBlock)`. - * And, we would cut down on TFA iterations, too. - * See also comment on the same topic in TypeFlowAnalysis. */ - - tfa.reinit(m, staleOut.toList, splicedBlocks, staleIn) - tfa.run - - staleOut.clear() - splicedBlocks.clear() - staleIn.clear() - - import scala.util.control.Breaks._ - for(bb <- tfa.callerLin; if tfa.preCandidates(bb)) { - val cms = bb.toList collect { case cm : CALL_METHOD => cm } - breakable { - for (cm <- cms; if tfa.remainingCALLs.isDefinedAt(cm)) { - val analysis.CallsiteInfo(_, receiver, stackLength, concreteMethod) = tfa.remainingCALLs(cm) - if (analyzeInc(cm, bb, receiver, stackLength, concreteMethod)) { - break() - } - } - } - } - - /* As part of inlining, some instructions are moved to a new block. - * In detail: the instructions moved to a new block originally appeared after a (by now inlined) callsite. - * Their new home is an `afterBlock` created by `doInline()` to that effect. - * Each block in staleIn is one such `afterBlock`. - * - * Some of those instructions may be CALL_METHOD possibly tracked in `remainingCALLs` - * (with an entry still noting the old containing block). However, that causes no problem: - * - * (1) such callsites won't be analyzed for inlining by `analyzeInc()` (*in this iteration*) - * because of the `break` that abandons the original basic block where it was contained. - * - * (2) Additionally, its new containing block won't be visited either (*in this iteration*) - * because the new blocks don't show up in the linearization computed before inlinings started: - * `for(bb <- tfa.callerLin; if tfa.preCandidates(bb)) {` - * - * For a next iteration, the new home of any instructions that have moved - * will be tracked properly in `remainingCALLs` after `MTFAGrowable.reinit()` puts on radar their new homes. - * - */ - if(retry) { - for(afterBlock <- staleIn) { - val justCALLsAfter = afterBlock.toList collect { case c : opcodes.CALL_METHOD => c } - for(ia <- justCALLsAfter) { tfa.remainingCALLs.remove(ia) } - } - } - - /* - if(splicedBlocks.nonEmpty) { // TODO explore (saves time but leads to slightly different inlining decisions) - // opportunistically perform straightforward inlinings before the next typeflow round - val savedRetry = retry - val savedStaleOut = staleOut.toSet; staleOut.clear() - val savedStaleIn = staleIn.toSet ; staleIn.clear() - val howmany = inlineWithoutTFA(splicedBlocks, tfa.knownBeforehand) - splicedBlocks ++= staleIn - staleOut.clear(); staleOut ++= savedStaleOut; - staleIn.clear(); staleIn ++= savedStaleIn; - retry = savedRetry - } - */ - - if (tfa.stat) - log(m.symbol.fullName + " iterations: " + tfa.iterations + " (size: " + caller.length + ")") - } - while (retry && count < MAX_INLINE_RETRY) - - for(inlFail <- tfa.warnIfInlineFails) { - warn(inlFail.pos, "At the end of the day, could not inline @inline-marked method " + inlFail.method.unexpandedName.decode) - } - - m.normalize() - if (sizeBeforeInlining > 0) { - val instrAfterInlining = m.code.instructionCount - val inlinings = caller.inlinedCalls - if (inlinings > 0) { - val s1 = s"instructions $instrBeforeInlining -> $instrAfterInlining" - val s2 = if (sizeBeforeInlining == m.code.blockCount) "" else s", blocks $sizeBeforeInlining -> ${m.code.blockCount}" - val callees = inlinedMethodCount.toList map { case (k, v) => k.fullNameString + ( if (v == 1) "" else "/" + v ) } - - inlineLog("inlined", m.symbol.fullName, callees.sorted.mkString(inlinings + " inlined: ", ", ", "")) - inlineLog("<<tldr>>", m.symbol.fullName, s"${m.symbol.nameString}: $s1$s2") - } - } - } - - private def isHigherOrderMethod(sym: Symbol) = ( - sym.isMethod - && enteringExplicitOuter(sym.info.paramTypes exists isFunctionType) // was "at erasurePhase.prev" - ) - - /** Should method 'sym' being called in 'receiver' be loaded from disk? */ - def shouldLoadImplFor(sym: Symbol, receiver: Symbol): Boolean = { - def alwaysLoad = (receiver.enclosingPackage == RuntimePackage) || (receiver == PredefModule.moduleClass) - def loadCondition = sym.isEffectivelyFinalOrNotOverridden && isMonadicMethod(sym) && isHigherOrderMethod(sym) - - val res = hasInline(sym) || alwaysLoad || loadCondition - debuglog("shouldLoadImplFor: " + receiver + "." + sym + ": " + res) - res - } - - class IMethodInfo(val m: IMethod) { - override def toString = m.toString - - val sym = m.symbol - def owner = sym.owner - def paramTypes = sym.info.paramTypes - def minimumStack = paramTypes.length + 1 - - def isBridge = sym.isBridge - val isInClosure = isClosureClass(owner) - val isHigherOrder = isHigherOrderMethod(sym) - def isMonadic = isMonadicMethod(sym) - - def handlers = m.exh - def blocks = m.blocks - def locals = m.locals - def length = blocks.length - def openBlocks = blocks filterNot (_.closed) - def instructions = m.code.instructions - - def isSmall = (length <= SMALL_METHOD_SIZE) && blocks(0).length < 10 - def isLarge = length > MAX_INLINE_SIZE - def isRecursive = m.recursive - def hasHandlers = handlers.nonEmpty || m.bytecodeHasEHs - - def isSynchronized = sym.hasFlag(Flags.SYNCHRONIZED) - def hasNonFinalizerHandler = handlers exists { - case _: Finalizer => true - case _ => false - } - - // the number of inlined calls in 'm', used by 'isScoreOK' - var inlinedCalls = 0 - - def addLocals(ls: List[Local]) = m.locals ++= ls - def addLocal(l: Local) = addLocals(List(l)) - def addHandlers(exhs: List[ExceptionHandler]) = m.exh = exhs ::: m.exh - - /** - * This method inspects the callee's instructions, finding out the most restrictive accessibility implied by them. - * - * Rather than giving up upon encountering an access to a private field `p`, it provisorily admits `p` as "can-be-made-public", provided: - * - `p` is being compiled as part of this compilation run, and - * - `p` is synthetic or param-accessor. - * - * This method is side-effect free, in particular it lets the invoker decide - * whether the accessibility of the `toBecomePublic` fields should be changed or not. - */ - def accessRequirements: AccessReq = { - - var toBecomePublic: List[Symbol] = Nil - - def check(sym: Symbol, cond: Boolean) = - if (cond) Private - else if (sym.isProtected) Protected - else Public - - def canMakePublic(f: Symbol): Boolean = - (m.sourceFile ne NoSourceFile) && - (f.isSynthetic || f.isParamAccessor) && - { toBecomePublic = f :: toBecomePublic; true } - - /* A safety check to consider as private, for the purposes of inlining, a public field that: - * (1) is defined in an external library, and - * (2) can be presumed synthetic (due to a dollar sign in its name). - * Such field was made public by `doMakePublic()` and we don't want to rely on that, - * because under other compilation conditions (ie no -optimize) that won't be the case anymore. - * - * This allows aggressive intra-library inlining (making public if needed) - * that does not break inter-library scenarios (see comment for `Inliners`). - * - * TODO handle more robustly the case of a trait var changed at the source-level from public to private[this] - * (eg by having ICodeReader use unpickler, see SI-5442). - - DISABLED - - def potentiallyPublicized(f: Symbol): Boolean = { - (m.sourceFile eq NoSourceFile) && f.name.containsChar('$') - } - */ - - - def isPrivateForInlining(sym: Symbol): Boolean = { - if (sym.isJavaDefined) { - def check(sym: Symbol) = !(sym.isPublic || sym.isProtected) - check(sym) || check(sym.owner) // SI-7582 Must check the enclosing class *and* the symbol for Java. - } - else sym.isPrivate // Scala never emits package-private bytecode - } - - def checkField(f: Symbol) = check(f, isPrivateForInlining(f) && !canMakePublic(f)) - def checkSuper(n: Symbol) = check(n, isPrivateForInlining(n) || !n.isClassConstructor) - def checkMethod(n: Symbol) = check(n, isPrivateForInlining(n)) - - def getAccess(i: Instruction) = i match { - case CALL_METHOD(n, SuperCall(_)) => checkSuper(n) - case CALL_METHOD(n, _) => checkMethod(n) - case LOAD_FIELD(f, _) => checkField(f) - case STORE_FIELD(f, _) => checkField(f) - case _ => Public - } - - var seen = Public - val iter = instructions.iterator - while((seen ne Private) && iter.hasNext) { - val i = iter.next() - getAccess(i) match { - case Private => - inlineLog("access", s"instruction $i requires private access", "pos=" + i.pos) - toBecomePublic = Nil - seen = Private - case Protected => seen = Protected - case _ => () - } - } - - AccessReq(seen, toBecomePublic) - } - - } - - /** - * Classifies a pair (caller, callee) into one of four categories: - * - * (a) inlining should be performed, classified in turn into: - * (a.1) `InlineableAtThisCaller`: unconditionally at this caller - * (a.2) `FeasibleInline`: it only remains for certain access requirements to be met (see `IMethodInfo.accessRequirements()`) - * - * (b) inlining shouldn't be performed, classified in turn into: - * (b.1) `DontInlineHere`: indicates that this particular occurrence of the callee at the caller shouldn't be inlined. - * - Nothing is said about the outcome for other callers, or for other occurrences of the callee for the same caller. - * - In particular inlining might be possible, but heuristics gave a low score for it. - * (b.2) `NeverSafeToInline`: the callee can't be inlined anywhere, irrespective of caller. - * - * The classification above is computed by `isStampedForInlining()` based on which `analyzeInc()` goes on to: - * - either log the reason for failure --- case (b) ---, - * - or perform inlining --- case (a) ---. - */ - sealed abstract class InlineSafetyInfo - case object NeverSafeToInline extends InlineSafetyInfo - case object InlineableAtThisCaller extends InlineSafetyInfo - case class DontInlineHere(msg: String) extends InlineSafetyInfo - case class FeasibleInline(accessNeeded: NonPublicRefs.Value, toBecomePublic: List[Symbol]) extends InlineSafetyInfo - - case class AccessReq( - accessNeeded: NonPublicRefs.Value, - toBecomePublic: List[Symbol] - ) - - final class CallerCalleeInfo(val caller: IMethodInfo, val inc: IMethodInfo, fresh: mutable.Map[String, Int], inlinedMethodCount: scala.collection.Map[Symbol, Int]) { - - assert(!caller.isBridge && inc.m.hasCode, - "A guard in Inliner.analyzeClass() should have prevented from getting here.") - - def isLargeSum = caller.length + inc.length - 1 > SMALL_METHOD_SIZE - - private def freshName(s: String): TermName = { - fresh(s) += 1 - newTermName(s + fresh(s)) - } - - private def isKnownToInlineSafely: Boolean = { tfa.knownSafe(inc.sym) } - - val isInlineForced = hasInline(inc.sym) - val isInlineForbidden = hasNoInline(inc.sym) - assert(!(isInlineForced && isInlineForbidden), "method ("+inc.m+") marked both @inline and @noinline.") - - /** Inline 'inc' into 'caller' at the given block and instruction. - * The instruction must be a CALL_METHOD. - */ - def doInline(block: BasicBlock, instr: CALL_METHOD) { - - staleOut += block - - tfa.remainingCALLs.remove(instr) // this bookkeeping is done here and not in MTFAGrowable.reinit due to (1st) convenience and (2nd) necessity. - tfa.isOnWatchlist.remove(instr) // ditto - tfa.warnIfInlineFails.remove(instr) - - val targetPos = instr.pos - - def blockEmit(i: Instruction) = block.emit(i, targetPos) - def newLocal(baseName: String, kind: TypeKind) = - new Local(caller.sym.newVariable(freshName(baseName), targetPos) setInfo kind.toType, kind, false) - - val (hasRETURN, a) = getRecentTFA(inc.m, isInlineForced) - - /* The exception handlers that are active at the current block. */ - val activeHandlers = caller.handlers filter (_ covered block) - - /* Map 'original' blocks to the ones inlined in the caller. */ - val inlinedBlock = mutable.Map[BasicBlock, BasicBlock]() - - val varsInScope = mutable.HashSet[Local]() ++= block.varsInScope - - /* Side effects varsInScope when it sees SCOPE_ENTERs. */ - def instrBeforeFilter(i: Instruction): Boolean = { - i match { case SCOPE_ENTER(l) => varsInScope += l ; case _ => () } - i ne instr - } - val instrBefore = block.toList takeWhile instrBeforeFilter - val instrAfter = block.toList drop (instrBefore.length + 1) - - assert(!instrAfter.isEmpty, "CALL_METHOD cannot be the last instruction in block!") - - // store the '$this' into the special local - val inlinedThis = newLocal("$inlThis", REFERENCE(ObjectClass)) - - /* buffer for the returned value */ - val retVal = inc.m.returnType match { - case UNIT => null - case x => newLocal("$retVal", x) - } - - val inlinedLocals = mutable.HashMap.empty[Local, Local] - - /* Add a new block in the current context. */ - def newBlock() = { - val b = caller.m.code.newBlock() - activeHandlers foreach (_ addCoveredBlock b) - if (retVal ne null) b.varsInScope += retVal - b.varsInScope += inlinedThis - b.varsInScope ++= varsInScope - b - } - - def translateExh(e: ExceptionHandler) = { - val handler: ExceptionHandler = e.dup - handler.covered = handler.covered map inlinedBlock - handler setStartBlock inlinedBlock(e.startBlock) - handler - } - - /* alfa-rename `l` in caller's context. */ - def dupLocal(l: Local): Local = { - val sym = caller.sym.newVariable(freshName(l.sym.name.toString), l.sym.pos) - // sym.setInfo(l.sym.tpe) - val dupped = new Local(sym, l.kind, false) - inlinedLocals(l) = dupped - dupped - } - - val afterBlock = newBlock() - - /* Map from nw.init instructions to their matching NEW call */ - val pending: mutable.Map[Instruction, NEW] = new mutable.HashMap - - /* Map an instruction from the callee to one suitable for the caller. */ - def map(i: Instruction): Instruction = { - def assertLocal(l: Local) = { - assert(caller.locals contains l, "Could not find local '" + l + "' in locals, nor in inlinedLocals: " + inlinedLocals) - i - } - def isInlined(l: Local) = inlinedLocals isDefinedAt l - - val newInstr = i match { - case THIS(clasz) => LOAD_LOCAL(inlinedThis) - case STORE_THIS(_) => STORE_LOCAL(inlinedThis) - case JUMP(whereto) => JUMP(inlinedBlock(whereto)) - case CJUMP(succ, fail, cond, kind) => CJUMP(inlinedBlock(succ), inlinedBlock(fail), cond, kind) - case CZJUMP(succ, fail, cond, kind) => CZJUMP(inlinedBlock(succ), inlinedBlock(fail), cond, kind) - case SWITCH(tags, labels) => SWITCH(tags, labels map inlinedBlock) - case RETURN(_) => JUMP(afterBlock) - case LOAD_LOCAL(l) if isInlined(l) => LOAD_LOCAL(inlinedLocals(l)) - case STORE_LOCAL(l) if isInlined(l) => STORE_LOCAL(inlinedLocals(l)) - case LOAD_LOCAL(l) => assertLocal(l) - case STORE_LOCAL(l) => assertLocal(l) - case SCOPE_ENTER(l) if isInlined(l) => SCOPE_ENTER(inlinedLocals(l)) - case SCOPE_EXIT(l) if isInlined(l) => SCOPE_EXIT(inlinedLocals(l)) - - case nw @ NEW(sym) => - val r = NEW(sym) - pending(nw.init) = r - r - - case CALL_METHOD(meth, Static(true)) if meth.isClassConstructor => - CALL_METHOD(meth, Static(onInstance = true)) - - case _ => i.clone() - } - // check any pending NEW's - pending remove i foreach (_.init = newInstr.asInstanceOf[CALL_METHOD]) - newInstr - } - - caller addLocals (inc.locals map dupLocal) - caller addLocal inlinedThis - - if (retVal ne null) - caller addLocal retVal - - inc.m foreachBlock { b => - inlinedBlock += (b -> newBlock()) - inlinedBlock(b).varsInScope ++= (b.varsInScope map inlinedLocals) - } - - // re-emit the instructions before the call - block.open() - block.clear() - block emit instrBefore - - // store the arguments into special locals - inc.m.params.reverse foreach (p => blockEmit(STORE_LOCAL(inlinedLocals(p)))) - blockEmit(STORE_LOCAL(inlinedThis)) - - // jump to the start block of the callee - blockEmit(JUMP(inlinedBlock(inc.m.startBlock))) - block.close() - - // duplicate the other blocks in the callee - val calleeLin = inc.m.linearizedBlocks() - calleeLin foreach { bb => - var info = if(hasRETURN) (a in bb) else null - def emitInlined(i: Instruction) = inlinedBlock(bb).emit(i, targetPos) - def emitDrops(toDrop: Int) = info.stack.types drop toDrop foreach (t => emitInlined(DROP(t))) - - for (i <- bb) { - i match { - case RETURN(UNIT) => emitDrops(0) - case RETURN(kind) => - if (info.stack.length > 1) { - emitInlined(STORE_LOCAL(retVal)) - emitDrops(1) - emitInlined(LOAD_LOCAL(retVal)) - } - case _ => () - } - emitInlined(map(i)) - info = if(hasRETURN) a.interpret(info, i) else null - } - inlinedBlock(bb).close() - } - - afterBlock emit instrAfter - afterBlock.close() - - staleIn += afterBlock - splicedBlocks ++= (calleeLin map inlinedBlock) - - // add exception handlers of the callee - caller addHandlers (inc.handlers map translateExh) - assert(pending.isEmpty, "Pending NEW elements: " + pending) - if (settings.debug) icodes.checkValid(caller.m) - } - - def isStampedForInlining(stackLength: Int): InlineSafetyInfo = { - - if(tfa.blackballed(inc.sym)) { return NeverSafeToInline } - - if(!isKnownToInlineSafely) { - - if(inc.openBlocks.nonEmpty) { - val msg = ("Encountered " + inc.openBlocks.size + " open block(s) in isSafeToInline: this indicates a bug in the optimizer!\n" + - " caller = " + caller.m + ", callee = " + inc.m) - warn(inc.sym.pos, msg) - tfa.knownNever += inc.sym - return DontInlineHere("Open blocks in " + inc.m) - } - - val reasonWhyNever: String = { - var rs: List[String] = Nil - if(inc.isRecursive) { rs ::= "is recursive" } - if(isInlineForbidden) { rs ::= "is annotated @noinline" } - if(inc.isSynchronized) { rs ::= "is synchronized method" } - if(inc.m.bytecodeHasEHs) { rs ::= "bytecode contains exception handlers / finally clause" } // SI-6188 - if(inc.m.bytecodeHasInvokeDynamic) { rs ::= "bytecode contains invoke dynamic" } - if(rs.isEmpty) null else rs.mkString("", ", and ", "") - } - - if(reasonWhyNever != null) { - tfa.knownNever += inc.sym - inlineLog("never", inc.sym, reasonWhyNever) - // next time around NeverSafeToInline is returned, thus skipping (duplicate) msg, this is intended. - return DontInlineHere(inc.m + " " + reasonWhyNever) - } - - if(sameSymbols) { // TODO but this also amounts to recursive, ie should lead to adding to tfa.knownNever, right? - tfa.knownUnsafe += inc.sym - return DontInlineHere("sameSymbols (ie caller == callee)") - } - - } - - /* - * From here on, two main categories of checks remain, (a) and (b) below: - * (a.1) either the scoring heuristics give green light; or - * (a.2) forced as candidate due to @inline. - * After that, safety proper is checked: - * (b.1) the callee does not contain calls to private methods when called from another class - * (b.2) the callee is not going to be inlined into a position with non-empty stack, - * while having a top-level finalizer (see liftedTry problem) - * As a result of (b), some synthetic private members can be chosen to become public. - */ - - val score = inlinerScore - val scoreStr = if (score > 0) "+" + score else "" + score - val what = if (score > 0) "ok to" else "don't" - inlineLog(scoreStr, inc.m.symbol, s"$what inline into ${ownedName(caller.m.symbol)}") - - if (!isInlineForced && score <= 0) { - // During inlining retry, a previous caller-callee pair that scored low may pass. - // Thus, adding the callee to tfa.knownUnsafe isn't warranted. - return DontInlineHere(s"inliner heuristic") - } - - if(inc.hasHandlers && (stackLength > inc.minimumStack)) { - return DontInlineHere("callee contains exception handlers / finally clause, and is invoked with non-empty operand stack") // SI-6157 - } - - if(isKnownToInlineSafely) { return InlineableAtThisCaller } - - if(stackLength > inc.minimumStack && inc.hasNonFinalizerHandler) { - val msg = "method " + inc.sym + " is used on a non-empty stack with finalizer." - debuglog(msg) - // FYI: not reason enough to add inc.sym to tfa.knownUnsafe (because at other callsite in this caller, inlining might be ok) - return DontInlineHere(msg) - } - - val accReq = inc.accessRequirements - if(!canAccess(accReq.accessNeeded)) { - tfa.knownUnsafe += inc.sym - val msg = "access level required by callee not matched by caller" - inlineLog("fail", inc.sym, msg) - return DontInlineHere(msg) - } - - FeasibleInline(accReq.accessNeeded, accReq.toBecomePublic) - - } - - def canAccess(level: NonPublicRefs.Value) = level match { - case Private => caller.owner == inc.owner - case Protected => caller.owner.tpe <:< inc.owner.tpe - case Public => true - } - private def sameSymbols = caller.sym == inc.sym - - /** Gives green light for inlining (which may still be vetoed later). Heuristics: - * - it's bad to make the caller larger (> SMALL_METHOD_SIZE) if it was small - * - it's bad to inline large methods - * - it's good to inline higher order functions - * - it's good to inline closures functions. - * - it's bad (useless) to inline inside bridge methods - */ - def inlinerScore: Int = { - var score = 0 - - // better not inline inside closures, but hope that the closure itself is repeatedly inlined - if (caller.isInClosure) score -= 2 - else if (caller.inlinedCalls < 1) score -= 1 // only monadic methods can trigger the first inline - - if (inc.isSmall) score += 1 - // if (inc.hasClosureParam) score += 2 - if (inc.isLarge) score -= 1 - if (caller.isSmall && isLargeSum) { - score -= 1 - debuglog(s"inliner score decreased to $score because small caller $caller would become large") - } - - if (inc.isMonadic) score += 3 - else if (inc.isHigherOrder) score += 1 - - if (inc.isInClosure) score += 2 - if (inlinedMethodCount(inc.sym) > 2) score -= 2 - score - } - } - - def lookupIMethod(meth: Symbol, receiver: Symbol): Option[IMethod] = { - def tryParent(sym: Symbol) = icodes icode sym flatMap (_ lookupMethod meth) - - (receiver.info.baseClasses.iterator map tryParent find (_.isDefined)).flatten - } - } /* class Inliner */ -} /* class Inliners */ |