Scala example source code file (Inliners.scala)
The Inliners.scala Scala example source code/* 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 accesibility 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) = currentIClazz.cunit.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.Ystatistics.value
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 linining 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 bookkpeeping 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 */
Other Scala source code examplesHere is a short list of links related to this Scala Inliners.scala source code file: |
The search page
Other Scala source code examples at this package level
Click here to learn more about this project
