diff options
| -rw-r--r-- | src/compiler/scala/tools/nsc/backend/opt/Inliners.scala | 989 |
1 files changed, 511 insertions, 478 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index 668565ddf6..6a5a107d2d 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -7,9 +7,9 @@ package scala.tools.nsc package backend.opt - import scala.util.control.Breaks._ -import scala.collection.mutable.{Map, HashMap, Set, HashSet} +import scala.collection.{ mutable, immutable } +import mutable.{ HashMap, HashSet } import scala.tools.nsc.symtab._ /** @@ -19,6 +19,11 @@ 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" @@ -28,15 +33,24 @@ abstract class Inliners extends SubComponent { val res = body val t2 = System.currentTimeMillis() val ms = (t2 - t1).toInt - if (ms >= 2000) + 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) @@ -47,255 +61,59 @@ abstract class Inliners extends SubComponent { val inliner = new Inliner override def apply(c: IClass) { - inliner.analyzeClass(c) + 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 - val fresh = new HashMap[String, Int] + /** Cache whether a method calls private members. */ + val usesNonPublics: mutable.Map[IMethod, Value] = new HashMap + } + import NonPublicRefs._ /* fresh name counter */ + val fresh = new HashMap[String, Int] var count = 0 - - def freshName(s: String) = fresh.get(s) match { - case Some(count) => - fresh(s) = count + 1 - s + count - case None => - fresh(s) = 1 - s + "0" + def freshName(s: String) = { + val count = fresh.getOrElseUpdate(s, 0) + fresh(s) += 1 + s + count } - private def hasInline(sym: Symbol) = sym hasAnnotation definitions.ScalaInlineClass - private def hasNoInline(sym: Symbol) = sym hasAnnotation definitions.ScalaNoInlineClass - - /** Inline the 'callee' method inside the 'caller' in the given - * basic block, at the given instruction (which has to be a CALL_METHOD). - */ - def inline(caller: IMethod, - block: BasicBlock, - instr: Instruction, - callee: IMethod) { - def posToStr(pos: util.Position) = if (pos.isDefined) pos.point.toString else "<nopos>" - log("Inlining " + callee + " in " + caller + " at pos: " + posToStr(instr.pos)) - - val targetPos = instr.pos - val a = new analysis.MethodTFA(callee) - - /* The exception handlers that are active at the current block. */ - val activeHandlers = caller.exh.filter(_.covered.contains(block)) - - /* Map 'original' blocks to the ones inlined in the caller. */ - val inlinedBlock: Map[BasicBlock, BasicBlock] = new HashMap - - val varsInScope: Set[Local] = HashSet() ++= block.varsInScope - - val instrBefore = block.toList.takeWhile { - case i @ SCOPE_ENTER(l) => varsInScope += l - i ne instr - case i => - i ne instr - } - 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 = new Local(caller.symbol.newVariable(instr.pos, freshName("$inlThis")), REFERENCE(definitions.ObjectClass), false); - - /** buffer for the returned value */ - val retVal = - if (callee.returnType != UNIT) - new Local(caller.symbol.newVariable(instr.pos, freshName("$retVal")), callee.returnType, false); - else - null; - - /** Add a new block in the current context. */ - def newBlock = { - val b = caller.code.newBlock - activeHandlers.foreach (_.addCoveredBlock(b)) - if (retVal ne null) b.varsInScope += retVal - b.varsInScope += inlinedThis - b.varsInScope ++= varsInScope - b - } - - def translateExh(e: ExceptionHandler) = { - var handler: ExceptionHandler = e.dup - handler.covered = handler.covered.map(inlinedBlock) - handler.setStartBlock(inlinedBlock(e.startBlock)) - handler - } - - var inlinedLocals: Map[Local, Local] = new HashMap - - /** alfa-rename `l' in caller's context. */ - def dupLocal(l: Local): Local = { - val sym = caller.symbol.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 - } - - def addLocals(m: IMethod, ls: List[Local]) = - m.locals = m.locals ::: ls; - def addLocal(m: IMethod, l: Local): Unit = - addLocals(m, List(l)); - - val afterBlock = newBlock; - - /** Map from nw.init instructions to their matching NEW call */ - val pending: collection.mutable.Map[Instruction, NEW] = new collection.mutable.HashMap - - /** Map an instruction from the callee to one suitable for the caller. */ - def map(i: Instruction): Instruction = { - val newInstr = i match { - case THIS(clasz) => - LOAD_LOCAL(inlinedThis); - - case STORE_THIS(_) => - STORE_LOCAL(inlinedThis) - - case JUMP(whereto) => - JUMP(inlinedBlock(whereto)); - - case CJUMP(success, failure, cond, kind) => - CJUMP(inlinedBlock(success), inlinedBlock(failure), cond, kind); - - case CZJUMP(success, failure, cond, kind) => - CZJUMP(inlinedBlock(success), inlinedBlock(failure), cond, kind); - - case SWITCH(tags, labels) => - SWITCH(tags, labels map inlinedBlock); - - case RETURN(kind) => - JUMP(afterBlock); - - case LOAD_LOCAL(l) if inlinedLocals.isDefinedAt(l) => - LOAD_LOCAL(inlinedLocals(l)) - - case STORE_LOCAL(l) if inlinedLocals.isDefinedAt(l) => - STORE_LOCAL(inlinedLocals(l)) - - case LOAD_LOCAL(l) => - assert(caller.locals contains l, - "Could not find local '" + l + "' in locals, nor in inlinedLocals: " + inlinedLocals) - i - case STORE_LOCAL(l) => - assert(caller.locals contains l, - "Could not find local '" + l + "' in locals, nor in inlinedLocals: " + inlinedLocals) - i - - case SCOPE_ENTER(l) if inlinedLocals.isDefinedAt(l) => - SCOPE_ENTER(inlinedLocals(l)) - - case SCOPE_EXIT(l) if inlinedLocals.isDefinedAt(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 - if (pending isDefinedAt i) { - pending(i).init = newInstr.asInstanceOf[CALL_METHOD] - pending -= i - } - newInstr - } - - addLocals(caller, callee.locals map dupLocal); - addLocal(caller, inlinedThis); - if (retVal ne null) - addLocal(caller, retVal); - callee.code.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 - instrBefore.foreach(i => block.emit(i, i.pos)) - - // store the arguments into special locals - callee.params.reverse.foreach { param => - block.emit(STORE_LOCAL(inlinedLocals(param)), targetPos); - } - block.emit(STORE_LOCAL(inlinedThis), targetPos); - - // jump to the start block of the callee - block.emit(JUMP(inlinedBlock(callee.code.startBlock)), targetPos); - block.close - - // duplicate the other blocks in the callee - linearizer.linearize(callee).foreach { bb => - var info = a.in(bb); - for (i <- bb) { - i match { - case RETURN(kind) => kind match { - case UNIT => - if (!info.stack.types.isEmpty) { - info.stack.types foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); } - } - case _ => - if (info.stack.length > 1) { - inlinedBlock(bb).emit(STORE_LOCAL(retVal), targetPos); - info.stack.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); } - inlinedBlock(bb).emit(LOAD_LOCAL(retVal), targetPos); - } - } - case _ => (); - } - inlinedBlock(bb).emit(map(i), targetPos); - info = a.interpret(info, i); - } - inlinedBlock(bb).close - } - - instrAfter.foreach(i => afterBlock.emit(i, i.pos)); - afterBlock.close; - count += 1 - - // add exception handlers of the callee - caller.exh = (callee.exh map translateExh) ::: caller.exh; - assert(pending.isEmpty, "Pending NEW elements: " + pending) - } + 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 - } + def analyzeClass(cls: IClass): Unit = + if (settings.inline.value) { + if (settings.debug.value) + log("Analyzing " + cls) - val tfa = new analysis.MethodTFA(); - tfa.stat = settings.Ystatistics.value + this.currentIClazz = cls + cls.methods filterNot (_.symbol.isConstructor) foreach analyzeMethod + } + + val tfa = new analysis.MethodTFA() + tfa.stat = settings.Ystatistics.value // how many times have we already inlined this method here? - private val inlinedMethods: Map[Symbol, Int] = new HashMap[Symbol, Int] { + private val inlinedMethodCount: mutable.Map[Symbol, Int] = new HashMap[Symbol, Int] { override def default(k: Symbol) = 0 } @@ -303,303 +121,518 @@ abstract class Inliners extends SubComponent { var retry = false var count = 0 fresh.clear - inlinedMethods.clear + inlinedMethodCount.clear val caller = new IMethodInfo(m) + var info: tfa.lattice.Elem = null + + def analyzeInc(msym: Symbol, i: Instruction, bb: BasicBlock) = { + val inc = new SymMethodInfo(msym) + val receiver = (info.stack.types drop inc.paramTypes.length).head match { + case REFERENCE(s) => s + case _ => NoSymbol + } + val concreteMethod = inc lookupImplFor receiver + + def warnNoInline(reason: String) = { + if (inc.inline && !caller.isBridge) + warn(i.pos, "Could not inline required method %s because %s.".format(msym.originalName.decode, reason)) + } + + if (shouldLoad(receiver, concreteMethod)) + icodes.icode(receiver, true) + + def isAvailable = icodes available receiver + def isCandidate = isClosureClass(receiver) || concreteMethod.isEffectivelyFinal || receiver.isFinal + def isApply = concreteMethod.name == nme.apply + def isCountable = !(isClosureClass(receiver) && isApply) // 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 + if (isCountable) + count += 1 + + pair.doInline(bb, i) + 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" + ) + } do { - retry = false; - if (m.code ne null) { - log("Analyzing " + m + " count " + count + " with " + m.code.blocks.length + " blocks"); - tfa.init(m) + 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 - for (bb <- linearizer.linearize(m)) { - var info = tfa.in(bb); + caller.linearized foreach { bb => + info = tfa in bb + for (i <- bb) { if (!retry) { i match { - case CALL_METHOD(msym, Dynamic) => - val inc = new SymMethodInfo(msym) - - def warnNoInline(reason: String) = { - if (caller.inline && !inc.isBridge && !inc.hasBlocker) - currentIClazz.cunit.warning(i.pos, - "Could not inline required method %s because %s.".format(msym.originalName.decode, reason)) - } - - val receiver = info.stack.types.drop(msym.info.paramTypes.length).head match { - case REFERENCE(s) => s; - case _ => NoSymbol; - } - var concreteMethod = msym; - if (receiver != msym.owner && receiver != NoSymbol) { - if (settings.debug.value) - log("" + i + " has actual receiver: " + receiver); - if (!concreteMethod.isEffectivelyFinal && receiver.isFinal) { - concreteMethod = lookupImpl(concreteMethod, receiver) - if (settings.debug.value) - log("\tlooked up method: " + concreteMethod.fullName) - } - } - - if (shouldLoad(receiver, concreteMethod)) { - icodes.icode(receiver, true) - } - if (settings.debug.value) - log("Treating " + i - + "\n\treceiver: " + receiver - + "\n\ticodes.available: " + icodes.available(receiver) - + "\n\tconcreteMethod.isEffectivelyFinal: " + concreteMethod.isFinal); - - if ( icodes.available(receiver) - && (isClosureClass(receiver) - || concreteMethod.isEffectivelyFinal - || receiver.isFinal)) { - icodes.icode(receiver).get.lookupMethod(concreteMethod) match { - case Some(inc) => - if (inc.symbol != m.symbol - && (inc.code ne null) - && shouldInline(m, inc) - && isSafeToInline(m, inc, info.stack)) { - retry = true; - if (!(isClosureClass(receiver) && (concreteMethod.name == nme.apply))) // only count non-closures - count = count + 1; - inline(m, bb, i, inc); - inlinedMethods(inc.symbol) += 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) - log("inline failed for " + inc + " because:\n\tinc.symbol != m.symbol: " + (inc.symbol != m.symbol) - + "\n\t(inlinedMethods(inc.symbol) < 2): " + (inlinedMethods(inc.symbol) < 2) - + "\n\tinc.code ne null: " + (inc.code ne null) + (if (inc.code ne null) - "\n\tisSafeToInline(m, inc, info.stack): " + isSafeToInline(m, inc, info.stack) - + "\n\tshouldInline heuristics: " + shouldInline(m, inc) else "")); - warnNoInline( - if (inc.code eq null) "bytecode was unavailable" - else if (!isSafeToInline(m, inc, info.stack)) "it is unsafe (target may reference private fields)" - else "of a bug (run with -Ylog:inline -Ydebug for more information)") - } - 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 (icodes.available(receiver)) "it is not final" else "bytecode was not available") - - case _ => (); + case CALL_METHOD(msym, Dynamic) => analyzeInc(msym, i, bb) + case _ => () } info = tfa.interpret(info, i) - }}} - if (tfa.stat) log(m.symbol.fullName + " iterations: " + tfa.iterations + " (size: " + m.code.blocks.length + ")") - }} while (retry && count < 15) + } + } + } + + if (tfa.stat) + log(m.symbol.fullName + " iterations: " + tfa.iterations + " (size: " + caller.length + ")") + } + } + while (retry && count < MAX_INLINE_RETRY) + m.normalize } - /** small method size (in blocks) */ - val SMALL_METHOD_SIZE = 1 - class SymMethodInfo(val sym: Symbol) { - val name = sym.name - val owner = sym.owner - - def inline = hasInline(sym) - def noinline = hasNoInline(sym) - def numInlined = inlinedMethods(sym) + 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 lookupImplFor(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 != owner) && !isEffectivelyFinal && clazz.isFinal + + def lookup(clazz: Symbol): Symbol = { + // println("\t\tlooking up " + meth + " in " + clazz.fullName + " meth.owner = " + meth.owner) + if (owner == clazz || isBottomType(clazz)) sym + else sym.overridingSymbol(clazz) match { + case NoSymbol => if (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 + } def isBridge = sym.isBridge def isInClosure = isClosureClass(owner) - def isHigherOrder = sym.isMethod && atPhase(currentRun.erasurePhase.prev)(sym.info.paramTypes exists definitions.isFunctionType) + def isHigherOrder = sym.isMethod && atPhase(currentRun.erasurePhase.prev)(paramTypes exists isFunctionType) def isMonadic = name match { case nme.foreach | nme.filter | nme.map | nme.flatMap => true case _ => false } - def isEffectivelyFinal = sym.isEffectivelyFinal - def coMembers = sym.owner.tpe.members - def coPrivates = coMembers filter (_.isPrivate) - def coGetters = coMembers filter (_.isGetter) - - /** Does this method have a quality which blocks us from inlining it - * until later? At present that means private members or getters exist - * in the class alongside it. - */ - def hasBlocker = coPrivates.nonEmpty || coGetters.nonEmpty + def isEffectivelyFinal = sym.isEffectivelyFinal + def shouldBeLoaded = inline || (isEffectivelyFinal && isMonadic && isHigherOrder) } - class IMethodInfo(m: IMethod) extends SymMethodInfo(m.symbol) { - def length = m.code.blocks.length - def isRecursive = m.recursive - - def isSmall = length <= SMALL_METHOD_SIZE - def isLarge = length > MAX_INLINE_SIZE - def isLargeSum(other: IMethodInfo) = length + other.length - 1 > SMALL_METHOD_SIZE + class IMethodInfo(val m: IMethod) extends SymMethodInfo(m.symbol) { + def handlers = m.exh + def blocks = 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 + def isLarge = length > MAX_INLINE_SIZE + def isRecursive = m.recursive + def hasCode = m.code != null + def hasSourceFile = m.sourceFile != null + def hasHandlers = handlers.nonEmpty + + 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 } - /** Should the given method be loaded from disk? */ - def shouldLoad(receiver: Symbol, method: Symbol): Boolean = { - if (settings.debug.value) - log("shouldLoad: " + receiver + "." + method) + class CallerCalleeInfo(val caller: IMethodInfo, val inc: IMethodInfo) { + def isLargeSum = caller.length + inc.length - 1 > SMALL_METHOD_SIZE - val caller = new SymMethodInfo(method) - def alwaysLoad = ( - (receiver.enclosingPackage == definitions.RuntimePackage) || - (receiver == definitions.PredefModule.moduleClass) || - caller.inline + /** 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 HashMap + + val varsInScope: mutable.Set[Local] = HashSet() ++= block.varsInScope + + val instrBefore = block.toList.takeWhile { + case i @ SCOPE_ENTER(l) => varsInScope += l + i ne instr + case i => + i ne instr + } + + 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 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 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(success, failure, cond, kind) => + CJUMP(inlinedBlock(success), inlinedBlock(failure), cond, kind) + + case CZJUMP(success, failure, cond, kind) => + CZJUMP(inlinedBlock(success), inlinedBlock(failure), cond, kind) + + case SWITCH(tags, labels) => + SWITCH(tags, labels map inlinedBlock) + + case RETURN(kind) => + 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 + instrBefore foreach (i => block.emit(i, i.pos)) + + // 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 + } + + instrAfter foreach (i => afterBlock.emit(i, i.pos)) + afterBlock.close + count += 1 + + // add exception handlers of the callee + caller addHandlers (inc.handlers map translateExh) + assert(pending.isEmpty, "Pending NEW elements: " + pending) + } + + 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 + ) ) - (caller.isEffectivelyFinal && caller.isMonadic && caller.isHigherOrder) || alwaysLoad - } + 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)" - /** Cache whether a method calls private members. */ - val usesNonPublics: Map[IMethod, NonPublicRefs.Value] = new HashMap; + 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) + + f setFlag Flags.notPRIVATE + true + } - object NonPublicRefs extends Enumeration { - val Public, Protected, Private = Value - } + if (inc.isRecursive) + return false - /** 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(caller: IMethod, callee: IMethod, stack: TypeStack): Boolean = { - def makePublic(f: Symbol): Boolean = - if ((callee.sourceFile ne null) - && (f.hasFlag(Flags.SYNTHETIC | Flags.PARAMACCESSOR))) { - if (settings.debug.value) log("Making not-private symbol out of synthetic: " + f) - f.setFlag(Flags.notPRIVATE) - true - } else false - - import NonPublicRefs._ - var callsNonPublic = Public - - if (callee.recursive) return false - - usesNonPublics.get(callee) match { - case Some(b) => - callsNonPublic = b - case None => + val accessNeeded = usesNonPublics.getOrElseUpdate(inc.m, { // Avoiding crashing the compiler if there are open blocks. - callee.code.blocks filterNot (_.closed) foreach { b => - currentIClazz.cunit.warning(callee.symbol.pos, - "Encountered open block in isSafeToInline: this indicates a bug in the optimizer!\n" + - " caller = " + caller + ", callee = " + callee - ) + 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 + } - breakable { - for (b <- callee.code.blocks; i <- b) - i match { - case CALL_METHOD(m, style) => - if (m.hasFlag(Flags.PRIVATE) || - (style.isSuper && !m.isClassConstructor)) { - callsNonPublic = Private - break - } - if (m.hasFlag(Flags.PROTECTED)) callsNonPublic = Protected - - case LOAD_FIELD(f, _) => - if (f.hasFlag(Flags.PRIVATE) && !makePublic(f)) { - callsNonPublic = Private; - break - } - if (f.hasFlag(Flags.PROTECTED)) callsNonPublic = Protected - - case STORE_FIELD(f, _) => - if (f.hasFlag(Flags.PRIVATE) && !makePublic(f)) { - callsNonPublic = Private; - break - } - if (f.hasFlag(Flags.PROTECTED)) callsNonPublic = Protected - - case _ => () + 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 } - usesNonPublics += (callee -> callsNonPublic) - } + iterate() + }) - if ((callsNonPublic == Private && (caller.symbol.owner != callee.symbol.owner)) - || callsNonPublic == Protected && !(caller.symbol.owner.tpe <:< callee.symbol.owner.tpe)) - return false; + 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.") - if (stack.length > (1 + callee.symbol.info.paramTypes.length) && - callee.exh != Nil) { - if (settings.debug.value) log("method " + callee.symbol + " is used on a non-empty stack with finalizer."); - false - } else - true - } + false + } - private def lookupImpl(meth: Symbol, clazz: Symbol): Symbol = { - //println("\t\tlooking up " + meth + " in " + clazz.fullName + " meth.owner = " + meth.owner) - if (meth.owner == clazz - || clazz == definitions.NullClass - || clazz == definitions.NothingClass) meth - else { - val implementingMethod = meth.overridingSymbol(clazz) - if (implementingMethod != NoSymbol) - implementingMethod - else if (meth.owner.isTrait) - meth - else - lookupImpl(meth, clazz.tpe.parents(0).typeSymbol) + 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 - */ - def shouldInline(mcaller: IMethod, mcallee: IMethod): Boolean = { - val caller = new IMethodInfo(mcaller) - val inc = new IMethodInfo(mcallee) - - if (caller.isBridge || inc.noinline || inc.hasBlocker) - return false - - if (inc.inline) - return true + /** 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.noinline + private def alwaysInline = inc.inline - if (settings.debug.value) - log("shouldInline: " + mcaller + " with " + mcallee) + def shouldInline: Boolean = !neverInline && (alwaysInline || { + if (settings.debug.value) + log("shouldInline: " + caller.m + " with " + inc.m) + + var score = 0 + 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 += 2 + else if (inc.isHigherOrder) + score += 1 + if (inc.isInClosure) + score += 2 + if (inc.numInlined > 2) + score -= 2 - var score = 0 - if (inc.isSmall) - score += 1 - if (caller.isSmall && (caller isLargeSum inc)) { - 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 += 2 - 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 + }) + } + + /** Should the given method be loaded from disk? */ + def shouldLoad(receiver: Symbol, method: Symbol): Boolean = { if (settings.debug.value) - log("shouldInline(" + mcallee + ") score: " + score) + log("shouldLoad: " + receiver + "." + method) - score > 0 + val caller = new SymMethodInfo(method) + def alwaysLoad = (receiver.enclosingPackage == RuntimePackage) || (receiver == PredefModule.moduleClass) + + caller.shouldBeLoaded || alwaysLoad } + + def lookupIMethod(meth: Symbol, receiver: Symbol): Option[IMethod] = + icodes.icode(receiver).get lookupMethod meth } /* class Inliner */ } /* class Inliners */ |