From 848295e4486cc33791fd41af5782e0a82ee4f474 Mon Sep 17 00:00:00 2001 From: Miguel Garcia Date: Tue, 26 Jun 2012 00:03:49 +0200 Subject: refactoring to functional style Inliner's isStampedForInlining() --- .../scala/tools/nsc/backend/icode/Repository.scala | 12 +- .../backend/icode/analysis/TypeFlowAnalysis.scala | 7 +- .../scala/tools/nsc/backend/opt/Inliners.scala | 342 +++++++++++++-------- 3 files changed, 223 insertions(+), 138 deletions(-) (limited to 'src/compiler') diff --git a/src/compiler/scala/tools/nsc/backend/icode/Repository.scala b/src/compiler/scala/tools/nsc/backend/icode/Repository.scala index 290979d205..663b626bef 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Repository.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Repository.scala @@ -38,19 +38,21 @@ trait Repository { } /** Load bytecode for given symbol. */ - def load(sym: Symbol) { + def load(sym: Symbol): Boolean = { try { val (c1, c2) = icodeReader.readClass(sym) - assert(c1.symbol == sym || c2.symbol == sym, - "c1.symbol = %s, c2.symbol = %s, sym = %s".format(c1.symbol, c2.symbol, sym)) + assert(c1.symbol == sym || c2.symbol == sym, "c1.symbol = %s, c2.symbol = %s, sym = %s".format(c1.symbol, c2.symbol, sym)) loaded += (c1.symbol -> c1) loaded += (c2.symbol -> c2) + + true } catch { case e: Throwable => // possible exceptions are MissingRequirementError, IOException and TypeError -> no better common supertype log("Failed to load %s. [%s]".format(sym.fullName, e.getMessage)) - if (settings.debug.value) - e.printStackTrace + if (settings.debug.value) { e.printStackTrace } + + false } } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala index 258466030f..06edaf17d2 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala @@ -565,9 +565,10 @@ abstract class TypeFlowAnalysis { val msym = cm.method val style = cm.style - !msym.isAccessor && - !msym.isConstructor && !blackballed(msym) && - (style.isDynamic || (style.hasInstance && style.isStatic)) + !blackballed(msym) && + !msym.isConstructor && + (!msym.isAccessor || inliner.isClosureClass(msym.owner)) && + (style.isDynamic || (style.hasInstance && style.isStatic)) } override def init(m: icodes.IMethod) { diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index f34faee459..44acfed411 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -177,7 +177,8 @@ abstract class Inliners extends SubComponent { private def warn(pos: Position, msg: String) = currentIClazz.cunit.inlinerWarning(pos, msg) val recentTFAs = mutable.Map.empty[Symbol, Tuple2[Boolean, analysis.MethodTFA]] - private def getRecentTFA(incm: IMethod): (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] } @@ -193,7 +194,7 @@ abstract class Inliners extends SubComponent { var a: analysis.MethodTFA = null if(hasRETURN) { a = new analysis.MethodTFA(incm); a.run } - if(hasInline(incm.symbol)) { recentTFAs.put(incm.symbol, (hasRETURN, a)) } + if(forceable) { recentTFAs.put(incm.symbol, (hasRETURN, a)) } (hasRETURN, a) } @@ -337,14 +338,15 @@ abstract class Inliners extends SubComponent { assert(bb.toList contains i, "Candidate callsite does not belong to BasicBlock.") var inlined = false - val msym = i.method + val shouldWarn = hasInline(i.method) - 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)) - } + def warnNoInline(reason: String) = { + if (shouldWarn) { + warn(i.pos, "Could not inline required method %s because %s.".format(i.method.originalName.decode, reason)) + } + } - def isAvailable = icodes available concreteMethod.enclClass + var isAvailable = icodes available concreteMethod.enclClass if (!isAvailable && shouldLoadImplFor(concreteMethod, receiver)) { // Until r22824 this line was: @@ -355,21 +357,23 @@ abstract class Inliners extends SubComponent { // 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)) - icodes.load(concreteMethod.enclClass) + isAvailable = icodes.load(concreteMethod.enclClass) } - def isCandidate = ( - isClosureClass(receiver) - || concreteMethod.isEffectivelyFinal - || receiver.isEffectivelyFinal - ) - def isApply = concreteMethod.name == nme.apply - def isCountable = !( - isClosureClass(receiver) - || isApply - || isMonadicMethod(concreteMethod) - || receiver.enclosingPackage == definitions.RuntimePackage - ) // only count non-closures + def isCandidate = ( + isClosureClass(receiver) + || concreteMethod.isEffectivelyFinal + || receiver.isEffectivelyFinal + ) + + 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 @@ -378,43 +382,62 @@ abstract class Inliners extends SubComponent { if (isAvailable && isCandidate) { lookupIMethod(concreteMethod, receiver) match { - case Some(callee) => + + case Some(callee) if callee.hasCode => val inc = new IMethodInfo(callee) val pair = new CallerCalleeInfo(caller, inc, fresh, inlinedMethodCount) - if (pair isStampedForInlining stackLength) { + (pair isStampedForInlining stackLength) match { - inc.doMakePublic() // `helperIsSafeToInline() populated a list on which `doMakePublic()` acts. - if(inc.accessNeeded == NonPublicRefs.Public) { tfa.knownSafe += inc.sym } + case inlInfo if inlInfo.isSafe => - retry = true - inlined = true - if (isCountable) { count += 1 }; + (inlInfo: @unchecked) match { - pair.doInline(bb, i) - if (!inc.inline || inc.isMonadic) { caller.inlinedCalls += 1 }; - inlinedMethodCount(inc.sym) += 1 + case FeasibleInline(accessNeeded, toBecomePublic) => + for(f <- toBecomePublic) { + debuglog("Making public (synthetic) field-symbol: " + f) + f setFlag Flags.notPRIVATE + f setFlag Flags.notPROTECTED + } + // only add to `knownSafe` after all `toBecomePublic` fields actually made public. + if(accessNeeded == NonPublicRefs.Public) { tfa.knownSafe += inc.sym } - // Remove the caller from the cache (this inlining might have changed its calls-private relation). - usesNonPublics -= m - recentTFAs -= m.symbol - } - else { - if(inc.accessNeeded == NonPublicRefs.Public) { tfa.knownUnsafe += inc.sym } + case InlineableAtThisCaller => () - if (settings.debug.value) { pair logFailure stackLength } + } - warnNoInline(pair failureReason stackLength) + retry = true + inlined = 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 + + + case DontInlineHere(msg) => + debuglog("inline failed, reason: " + msg) + warnNoInline(msg) + + case NeverSafeToInline => () } + + case Some(callee) => + assert(!callee.hasCode, "The case clause right before this one should have handled this case.") + warnNoInline("callee (" + callee + ") has no code") + () + case None => warnNoInline("bytecode was not available") debuglog("could not find icode\n\treceiver: " + receiver + "\n\tmethod: " + concreteMethod) } + } else { + warnNoInline(if(!isAvailable) "bytecode was not available" else "it can be overridden") } - else warnNoInline( - if (!isAvailable) "bytecode was not available" - else "it can be overridden" - ) inlined } @@ -544,11 +567,8 @@ abstract class Inliners extends SubComponent { def paramTypes = sym.info.paramTypes def minimumStack = paramTypes.length + 1 - def inline = hasInline(sym) - def noinline = hasNoInline(sym) - def isBridge = sym.isBridge - def isInClosure = isClosureClass(owner) + val isInClosure = isClosureClass(owner) val isHigherOrder = isHigherOrderMethod(sym) def isMonadic = isMonadicMethod(sym) @@ -564,21 +584,33 @@ abstract class Inliners extends SubComponent { def isLarge = length > MAX_INLINE_SIZE def isRecursive = m.recursive def hasHandlers = handlers.nonEmpty + + def isSynchronized = sym.hasFlag(Flags.SYNCHRONIZED) def hasNonFinalizerHandler = handlers exists { case _: Finalizer => true case _ => false } - // the number of inlined calls in 'm', used by 'shouldInline' + // 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 - private var toBecomePublic: List[Symbol] = Nil + /** + * 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 = { - lazy val accessNeeded: NonPublicRefs.Value = { + var toBecomePublic: List[Symbol] = Nil def check(sym: Symbol, cond: Boolean) = if (cond) Private @@ -586,13 +618,22 @@ abstract class Inliners extends SubComponent { else Public def canMakePublic(f: Symbol): Boolean = - (m.sourceFile ne NoSourceFile) && (f.isSynthetic || f.isParamAccessor) && + (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 is presumed synthetic (due to a dollar sign in its name), - * where the field was potentially publicized by `doMakePublic()`. - * We don't want to rely on it being public, as under other compilation conditions that won't be the case. */ + /* 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). + * */ def potentiallyPublicized(f: Symbol): Boolean = { (m.sourceFile eq NoSourceFile) && f.name.containsChar('$') } @@ -610,7 +651,6 @@ abstract class Inliners extends SubComponent { case _ => Public } - toBecomePublic = Nil var seen = Public val iter = instructions.iterator while((seen ne Private) && iter.hasNext) { @@ -625,20 +665,50 @@ abstract class Inliners extends SubComponent { } } - seen + AccessReq(seen, toBecomePublic) } - def doMakePublic() { - for(f <- toBecomePublic) { - debuglog("Making not-private symbol out of synthetic: " + f) - f setFlag Flags.notPRIVATE - } - toBecomePublic = Nil - } + } + /** + * 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 { + def isSafe = false + def isUnsafe = !isSafe } + case object NeverSafeToInline extends InlineSafetyInfo + case object InlineableAtThisCaller extends InlineSafetyInfo { override def isSafe = true } + case class DontInlineHere(msg: String) extends InlineSafetyInfo + case class FeasibleInline(accessNeeded: NonPublicRefs.Value, + toBecomePublic: List[Symbol]) extends InlineSafetyInfo { + override def isSafe = true + } + + case class AccessReq( + accessNeeded: NonPublicRefs.Value, + toBecomePublic: List[Symbol] + ) + + final class CallerCalleeInfo(val caller: IMethodInfo, val inc: IMethodInfo, fresh: mutable.Map[String, Int], inlinedMethodCount: collection.Map[Symbol, Int]) { + + assert(!caller.isBridge && inc.m.hasCode, + "A guard in Inliner.analyzeClass() should have prevented from getting here.") - class CallerCalleeInfo(val caller: IMethodInfo, val inc: IMethodInfo, fresh: mutable.Map[String, Int], inlinedMethodCount: collection.Map[Symbol, Int]) { def isLargeSum = caller.length + inc.length - 1 > SMALL_METHOD_SIZE private def freshName(s: String): TermName = { @@ -646,6 +716,12 @@ abstract class Inliners extends SubComponent { 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. */ @@ -663,7 +739,7 @@ abstract class Inliners extends SubComponent { def newLocal(baseName: String, kind: TypeKind) = new Local(caller.sym.newVariable(freshName(baseName), targetPos), kind, false) - val (hasRETURN, a) = getRecentTFA(inc.m) + val (hasRETURN, a) = getRecentTFA(inc.m, isInlineForced) /* The exception handlers that are active at the current block. */ val activeHandlers = caller.handlers filter (_ covered block) @@ -823,88 +899,94 @@ abstract class Inliners extends SubComponent { if (settings.debug.value) icodes.checkValid(caller.m) } - def isStampedForInlining(stackLength: Int) = - !sameSymbols && inc.m.hasCode && shouldInline && - isSafeToInline(stackLength) && { - // `isSafeToInline(stackLength, true)` must be invoked last in this AND expr because - // it prepares input for `doMakePublic()`, which in turn is invoked right before `doInline()`. - true - } + def isStampedForInlining(stackLength: Int): InlineSafetyInfo = { - def logFailure(stackLength: Int) = log( - """|inline failed for %s: - | pair.sameSymbols: %s - | inc.numInlined < 2: %s - | inc.m.hasCode: %s - | isSafeToInline: %s - | shouldInline: %s - """.stripMargin.format( - inc.m, sameSymbols, inlinedMethodCount(inc.sym) < 2, - inc.m.hasCode, isSafeToInline(stackLength), shouldInline - ) - ) - - def failureReason(stackLength: Int) = - if (!inc.m.hasCode) "bytecode was unavailable" - else if (inc.m.symbol.hasFlag(Flags.SYNCHRONIZED)) "method is synchronized" - else if (!isSafeToInline(stackLength)) "it is unsafe (target may reference private fields)" - else "of a bug (run with -Ylog:inline -Ydebug for more information)" + if(tfa.blackballed(inc.sym)) { return NeverSafeToInline } - 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 - private def sameOwner = caller.owner == inc.owner + if(!isKnownToInlineSafely) { - /** 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(stackLength: Int): Boolean = { + 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) + } - if(tfa.blackballed(inc.sym)) { return false } - if(tfa.knownSafe(inc.sym)) { return true } + 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(rs.isEmpty) null else rs.mkString("", ", and ", "") + } - helperIsSafeToInline(stackLength) - } + if(reasonWhyNever != null) { + tfa.knownNever += inc.sym + // 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)") + } - private def helperIsSafeToInline(stackLength: Int): Boolean = { + } - if (!inc.m.hasCode || inc.isRecursive) { return false } - if (inc.m.symbol.hasFlag(Flags.SYNCHRONIZED)) { return false } + /* + * 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. + */ - 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 + if(!isInlineForced && !isScoreOK) { + // 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("too low score (heuristics)") } - val isIllegalStack = (stackLength > inc.minimumStack && inc.hasNonFinalizerHandler) - if(isIllegalStack) { debuglog("method " + inc.sym + " is used on a non-empty stack with finalizer.") } + 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 + return DontInlineHere("access level required by callee not matched by caller") + } + + FeasibleInline(accReq.accessNeeded, accReq.toBecomePublic) + + } - !isIllegalStack && canAccess(inc.accessNeeded) + 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 + private def sameOwner = caller.owner == inc.owner - /** Decide whether to inline or not. Heuristics: + /** 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 */ - private def neverInline = caller.isBridge || !inc.m.hasCode || inc.noinline - private def alwaysInline = inc.inline - - def shouldInline: Boolean = !neverInline && (alwaysInline || { - debuglog("shouldInline: " + caller.m + " with " + inc.m) + def isScoreOK: Boolean = { + debuglog("shouldInline: " + caller.m + " , callee:" + inc.m) var score = 0 @@ -928,7 +1010,7 @@ abstract class Inliners extends SubComponent { log("shouldInline(" + inc.m + ") score: " + score) score > 0 - }) + } } def lookupIMethod(meth: Symbol, receiver: Symbol): Option[IMethod] = { -- cgit v1.2.3