Scala example source code file (Inliners.scala)
The Scala Inliners.scala source code/* NSC -- new Scala compiler
* Copyright 2005-2011 LAMP/EPFL
* @author Iulian Dragos
*/
package scala.tools.nsc
package backend.opt
import scala.collection.mutable
import scala.tools.nsc.symtab._
/**
* @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
}
val phaseName = "inliner"
/** 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
}
/* 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
override def apply(c: IClass) {
inliner analyzeClass c
}
}
def isBottomType(sym: Symbol) = sym == NullClass || sym == NothingClass
def posToStr(pos: util.Position) = if (pos.isDefined) pos.point.toString else "<nopos>"
/** Is the given class a closure? */
def isClosureClass(cls: Symbol): Boolean =
cls.isFinal && cls.isSynthetic && !cls.isModuleClass && cls.isAnonymousFunction
/**
* Simple inliner.
*/
class Inliner {
object NonPublicRefs extends Enumeration {
val Public, Protected, Private = Value
/** Cache whether a method calls private members. */
val usesNonPublics: mutable.Map[IMethod, Value] = new mutable.HashMap
}
import NonPublicRefs._
/* fresh name counter */
val fresh = new mutable.HashMap[String, Int] withDefaultValue 0
def freshName(s: String) = {
fresh(s) += 1
s + fresh(s)
}
private def hasInline(sym: Symbol) = sym hasAnnotation ScalaInlineClass
private def hasNoInline(sym: Symbol) = sym hasAnnotation ScalaNoInlineClass
/** The current iclass */
private var currentIClazz: IClass = _
private def warn(pos: Position, msg: String) = currentIClazz.cunit.warning(pos, msg)
def analyzeClass(cls: IClass): Unit =
if (settings.inline.value) {
if (settings.debug.value)
log("Analyzing " + cls)
this.currentIClazz = cls
cls.methods filterNot (_.symbol.isConstructor) foreach analyzeMethod
}
val tfa = new analysis.MethodTFA()
tfa.stat = global.opt.printStats
// how many times have we already inlined this method here?
private val inlinedMethodCount: mutable.Map[Symbol, Int] = new mutable.HashMap[Symbol, Int] {
override def default(k: Symbol) = 0
}
def analyzeMethod(m: IMethod) {
var sizeBeforeInlining = if (m.code ne null) m.code.blocks.length else 0
var instrBeforeInlining = if (m.code ne null) m.code.blocks.foldLeft(0)(_ + _.length) else 0
var retry = false
var count = 0
fresh.clear()
inlinedMethodCount.clear()
val caller = new IMethodInfo(m)
var info: tfa.lattice.Elem = null
def analyzeInc(msym: Symbol, i: Instruction, bb: BasicBlock): Boolean = {
var inlined = false
def paramTypes = msym.info.paramTypes
val receiver = (info.stack.types drop paramTypes.length).head match {
case REFERENCE(s) => s
case _ => NoSymbol
}
val concreteMethod = lookupImplFor(msym, receiver)
def warnNoInline(reason: String) = {
if (hasInline(msym) && !caller.isBridge)
warn(i.pos, "Could not inline required method %s because %s.".format(msym.originalName.decode, reason))
}
if (shouldLoadImplFor(concreteMethod, receiver))
icodes.load(concreteMethod.enclClass)
def isAvailable = icodes available concreteMethod.enclClass
def isCandidate = isClosureClass(receiver) || concreteMethod.isEffectivelyFinal || receiver.isFinal
def isApply = concreteMethod.name == nme.apply
def isCountable = !(isClosureClass(receiver)
|| isApply
|| isMonadicMethod(concreteMethod)
|| receiver.enclosingPackage == definitions.RuntimePackage
) // only count non-closures
if (settings.debug.value)
log("Treating " + i
+ "\n\treceiver: " + receiver
+ "\n\ticodes.available: " + isAvailable
+ "\n\tconcreteMethod.isEffectivelyFinal: " + concreteMethod.isEffectivelyFinal)
if (isAvailable && isCandidate) {
lookupIMethod(concreteMethod, receiver) match {
case Some(callee) =>
val inc = new IMethodInfo(callee)
val pair = new CallerCalleeInfo(caller, inc)
if (pair isStampedForInlining info.stack) {
retry = true
inlined = true
if (isCountable)
count += 1
pair.doInline(bb, i)
if (!inc.inline || inc.isMonadic)
caller.inlinedCalls += 1
inlinedMethodCount(inc.sym) += 1
/* Remove this method from the cache, as the calls-private relation
* might have changed after the inlining.
*/
usesNonPublics -= m
}
else {
if (settings.debug.value)
pair logFailure info.stack
warnNoInline(pair failureReason info.stack)
}
case None =>
warnNoInline("bytecode was not available")
if (settings.debug.value)
log("could not find icode\n\treceiver: " + receiver + "\n\tmethod: " + concreteMethod)
}
}
else warnNoInline(
if (!isAvailable) "bytecode was not available"
else "it is not final"
)
inlined
}
import scala.util.control.Breaks._
do {
retry = false
if (caller.inline) {
log("Not inlining into " + caller.sym.originalName.decode + " because it is marked @inline.")
}
else if (caller.hasCode) {
log("Analyzing " + m + " count " + count + " with " + caller.length + " blocks")
tfa init m
tfa.run
caller.linearized foreach { bb =>
info = tfa in bb
breakable {
for (i <- bb) {
i match {
case CALL_METHOD(msym, Dynamic) =>
if (analyzeInc(msym, i, bb)) break
case _ => ()
}
info = tfa.interpret(info, i)
}
}
}
if (tfa.stat)
log(m.symbol.fullName + " iterations: " + tfa.iterations + " (size: " + caller.length + ")")
}
}
while (retry && count < MAX_INLINE_RETRY)
m.normalize
if (sizeBeforeInlining > 0) {
val instrAfterInlining = m.code.blocks.foldLeft(0)(_ + _.length)
val prefix = if ((instrAfterInlining > 2 * instrBeforeInlining) && (instrAfterInlining > 200)) " !! " else ""
log(prefix + " %s blocks before inlining: %d (%d) after: %d (%d)".format(
m.symbol.fullName, sizeBeforeInlining, instrBeforeInlining, m.code.blocks.length, instrAfterInlining))
}
}
private def isMonadicMethod(sym: Symbol) = {
val (origName, _, _) = nme.splitSpecializedName(sym.name)
origName match {
case nme.foreach | nme.filter | nme.withFilter | nme.map | nme.flatMap => true
case _ => false
}
}
private def isHigherOrderMethod(sym: Symbol) =
sym.isMethod && atPhase(currentRun.erasurePhase.prev)(sym.info.paramTypes exists isFunctionType)
/** 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.isEffectivelyFinal && isMonadicMethod(sym) && isHigherOrderMethod(sym)
val res = hasInline(sym) || alwaysLoad || loadCondition
if (settings.debug.value)
log("shouldLoadImplFor: " + receiver + "." + sym + ": " + res)
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.isEffectivelyFinal && clazz.isFinal
def lookup(clazz: Symbol): Symbol = {
// println("\t\tlooking up " + meth + " in " + clazz.fullName + " meth.owner = " + meth.owner)
if (sym.owner == clazz || isBottomType(clazz)) sym
else sym.overridingSymbol(clazz) match {
case NoSymbol => if (sym.owner.isTrait) sym else lookup(clazz.superClass)
case imp => imp
}
}
if (needsLookup) {
val concreteMethod = lookup(clazz)
if (settings.debug.value)
log("\tlooked up method: " + concreteMethod.fullName)
concreteMethod
}
else sym
}
class IMethodInfo(val m: IMethod) {
val sym = m.symbol
val name = sym.name
def owner = sym.owner
def paramTypes = sym.info.paramTypes
def minimumStack = paramTypes.length + 1
def inline = hasInline(sym)
def noinline = hasNoInline(sym)
def numInlined = inlinedMethodCount(sym)
def isBridge = sym.isBridge
def isInClosure = isClosureClass(owner)
def isHigherOrder = isHigherOrderMethod(sym)
def isMonadic = isMonadicMethod(sym)
def handlers = m.exh
def blocks = if (m.code eq null) sys.error("blocks = null + " + m) else m.code.blocks
def locals = m.locals
def length = blocks.length
def openBlocks = blocks filterNot (_.closed)
def instructions = blocks.flatten
def linearized = linearizer linearize m
def isSmall = (length <= SMALL_METHOD_SIZE) && blocks(0).length < 10
def isLarge = length > MAX_INLINE_SIZE
def isRecursive = m.recursive
def hasCode = m.code != null
def hasSourceFile = m.sourceFile != null
def hasHandlers = handlers.nonEmpty
// the number of inlined calls in 'm', used by 'shouldInline'
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
}
class CallerCalleeInfo(val caller: IMethodInfo, val inc: IMethodInfo) {
def isLargeSum = caller.length + inc.length - 1 > SMALL_METHOD_SIZE
/** Inline 'inc' into 'caller' at the given block and instruction.
* The instruction must be a CALL_METHOD.
*/
def doInline(block: BasicBlock, instr: Instruction) {
val targetPos = instr.pos
log("Inlining " + inc.m + " in " + caller.m + " at pos: " + posToStr(targetPos))
def blockEmit(i: Instruction) = block.emit(i, targetPos)
def newLocal(baseName: String, kind: TypeKind) =
new Local(caller.sym.newVariable(targetPos, freshName(baseName)), kind, false)
val a = new analysis.MethodTFA(inc.m)
/* 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] = new mutable.HashMap
val varsInScope: mutable.Set[Local] = mutable.HashSet() ++= 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.Map[Local, Local] = new mutable.HashMap
/** 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(l.sym.pos, freshName(l.sym.name.toString))
// 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(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.blocks foreach { b =>
inlinedBlock += (b -> newBlock())
inlinedBlock(b).varsInScope ++= (b.varsInScope map inlinedLocals)
}
// analyse callee
a.run
// 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.code.startBlock)))
block.close
// duplicate the other blocks in the callee
linearizer linearize inc.m foreach { bb =>
var info = a in bb
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 = a.interpret(info, i)
}
inlinedBlock(bb).close
}
afterBlock emit instrAfter
afterBlock.close
// add exception handlers of the callee
caller addHandlers (inc.handlers map translateExh)
assert(pending.isEmpty, "Pending NEW elements: " + pending)
if (settings.debug.value) icodes.checkValid(caller.m)
}
def isStampedForInlining(stack: TypeStack) =
!sameSymbols && inc.hasCode && shouldInline && isSafeToInline(stack)
def logFailure(stack: TypeStack) = log(
"""|inline failed for %s:
| pair.sameSymbols: %s
| inc.numInlined < 2: %s
| inc.hasCode: %s
| isSafeToInline: %s
| shouldInline: %s
""".stripMargin.format(
inc.m, sameSymbols, inc.numInlined < 2,
inc.hasCode, isSafeToInline(stack), shouldInline
)
)
def failureReason(stack: TypeStack) =
if (!inc.hasCode) "bytecode was unavailable"
else if (!isSafeToInline(stack)) "it is unsafe (target may reference private fields)"
else "of a bug (run with -Ylog:inline -Ydebug for more information)"
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
/** A method is safe to inline when:
* - it does not contain calls to private methods when
* called from another class
* - it is not inlined into a position with non-empty stack,
* while having a top-level finalizer (see liftedTry problem)
* - it is not recursive
* Note:
* - synthetic private members are made public in this pass.
*/
def isSafeToInline(stack: TypeStack): Boolean = {
def makePublic(f: Symbol): Boolean =
inc.hasSourceFile && (f.isSynthetic || f.isParamAccessor) && {
if (settings.debug.value)
log("Making not-private symbol out of synthetic: " + f)
if (f hasFlag Flags.PRIVATE) f setFlag Flags.notPRIVATE
true
}
if (!inc.hasCode || inc.isRecursive)
return false
val accessNeeded = usesNonPublics.getOrElseUpdate(inc.m, {
// Avoiding crashing the compiler if there are open blocks.
inc.openBlocks foreach { b =>
warn(inc.sym.pos,
"Encountered open block in isSafeToInline: this indicates a bug in the optimizer!\n" +
" caller = " + caller.m + ", callee = " + inc.m
)
return false
}
def check(sym: Symbol, cond: Boolean) =
if (cond) Private
else if (sym.isProtected) Protected
else Public
def checkField(f: Symbol) = check(f, f.isPrivate && !makePublic(f))
def checkSuper(m: Symbol) = check(m, m.isPrivate || !m.isClassConstructor)
def checkMethod(m: Symbol) = check(m, m.isPrivate)
def getAccess(i: Instruction) = i match {
case CALL_METHOD(m, SuperCall(_)) => checkSuper(m)
case CALL_METHOD(m, _) => checkMethod(m)
case LOAD_FIELD(f, _) => checkField(f)
case STORE_FIELD(f, _) => checkField(f)
case _ => Public
}
def iterate(): NonPublicRefs.Value = {
var seenProtected = false
inc.instructions foreach { i =>
getAccess(i) match {
case Private => return Private
case Protected => seenProtected = true
case _ => ()
}
}
if (seenProtected) Protected else Public
}
iterate()
})
def isIllegalStack = (stack.length > inc.minimumStack && inc.hasHandlers) || {
if (settings.debug.value)
log("method " + inc.sym + " is used on a non-empty stack with finalizer.")
false
}
// if (!canAccess(accessNeeded))
// println("access needed and failed: " + accessNeeded)
canAccess(accessNeeded) && !isIllegalStack
}
/** Decide whether to inline or not. 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
*/
private def neverInline = caller.isBridge || !inc.hasCode || inc.noinline
private def alwaysInline = inc.inline
def shouldInline: Boolean = !neverInline && (alwaysInline || {
if (settings.debug.value)
log("shouldInline: " + caller.m + " with " + inc.m)
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 (caller.isSmall && isLargeSum) {
score -= 1
if (settings.debug.value)
log("shouldInline: score decreased to " + score + " because small " + caller + " would become large")
}
if (inc.isLarge)
score -= 1
if (inc.isMonadic)
score += 3
else if (inc.isHigherOrder)
score += 1
if (inc.isInClosure)
score += 2
if (inc.numInlined > 2)
score -= 2
log("shouldInline(" + inc.m + ") score: " + score)
score > 0
})
}
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) getOrElse None
}
} /* class Inliner */
} /* class Inliners */
Other Scala examples (source code examples)Here 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
