Cleanup inline cost analysis code

[eraman]

Summary

Cleanups include:

• Return from analyzeCall when inlining is known to be unviable (instead of breaking from the cost analysis loop).
• Move code that sets Threshold to zero to updateThreshold
• Prevent threshold from going negative.

For context, see http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160222/334465.html

[davidxl]

I think the right fix is to move code in line 1217 -> 1237 into UpdateThreshold method.

Also it does not look good to update the threshold (subtracting singleBBbonus) within the loop. It should be safe to do that after the loop. To make the code more readable, it might be good to introduce two helper functions to addBonusToThreshold and subtractBonus ..

[eraman]

Incorporate some of David's comments and some other cleanup.

[hans]

Seems reasonable, I suppose, but I don't know this well enough to lgtm.

Can you compare the binary sizes of Clang bootstraps before and after to see if this patch changes things?

lib/Analysis/InlineCost.cpp

156

nit: blank line before this?

[davidxl]

lib/Analysis/InlineCost.cpp

578

allowSizeGrow does not sound like some property suitable for callsite. How about IsInUnreachablePath(..)

1323

Do we need this change?

1377

Is this one needed now?

[ahatanak]

I'm confused with the meaning of threshold here.

In the loop which visits the subset of basic blocks in the function, we use this exit condition:

if (Cost > Threshold)

This indicates as long as Cost doesn't exceed Threshold, the function is still eligible for inlining. If the function's Cost is equal to Threshold, it can still be inlined.

However, the last statement indicates that Cost has to be smaller than Threshold in order for it to be inlined:

return Cost < std::max(1, Threshold);

Shouldn't the loop exit when Cost >= Threshold? In that case, the minimum value of Threshold should be 1, not 0, to enable inlining zero-cost functions.

[eraman]

In D17584#362398, @ahatanak wrote:

I'm confused with the meaning of threshold here.

In the loop which visits the subset of basic blocks in the function, we use this exit condition:

if (Cost > Threshold)

This indicates as long as Cost doesn't exceed Threshold, the function is still eligible for inlining. If the function's Cost is equal to Threshold, it can still be inlined.

However, the last statement indicates that Cost has to be smaller than Threshold in order for it to be inlined:

return Cost < std::max(1, Threshold);

Shouldn't the loop exit when Cost >= Threshold? In that case, the minimum value of Threshold should be 1, not 0, to enable inlining zero-cost functions.

At worst, this delays early bailout. If we change it to Cost >= Threshold, then we need to handle the special case of Cost == 0 and Threshold == 0. I don't like this special casing of 0 cost (the Cost <= std::max(1, Threshold) check), but reverting that would require investigating the size increase seen by Hans.

lib/Analysis/InlineCost.cpp

578

I wanted a generic name to decide whether to set Threshold to 0.

1377

It's not strictly needed, but I think it makes the intention clear that Threshold is bounded below by 0.

[eraman]

Address review comments.

[davidxl]

lib/Analysis/InlineCost.cpp

1319–1325

why is the early bail out removed?

1339–1340

Why are these checks removed? Are they redundant? They do look like to be in the wrong place. Can you find out the original intention of the code? Is there a regression test somewhere?

[eraman]

lib/Analysis/InlineCost.cpp

1319–1325

Cost cannot be greater than Threshold in the first iteration - since there is a similar check in line 1245 above. Subsequently, if Cost exceeds Threshold, that's caught in analyzeBB which returns false and the bailout happens in that case.

1339–1340

I don't know why they were in the first place. If analyzeBlock returns false and it reaches the break stmt, it only means Cost > Threshold and we should be bailing out. There is no reason to break out of loop and return false at the end.

[davidxl]

good cleanup -- and I certainly hope we can do more cleanups in the future. Given the current state, I think it is worth doing a chrome size testing before committing. lgtm

David

lib/Analysis/InlineCost.cpp

1339–1340

ok -- looks like a left over in the original patch.

[reames]

You have three only vaguely related changes here. In general, this should have been split up. I'm going to request that the third piece be split and reviewed separately. Once that's done, the first two LGTM w/noted changes as well.

lib/Analysis/InlineCost.cpp

1319–1325

Please make this an assertion since it's a non-obvious loop invariant.

1377

This should be separated into it's own change. It isn't obvious to me that it's correct. (Not saying it isn't, just not obvious it is.) Separate this into it's own patch and add an assertion of the invariant you're asserting (i.e Threshold >= 0)

(Actually, you do that below. Still separate and separately review please.)

[eraman]

lib/Analysis/InlineCost.cpp

1377

Is this comment only for this subtraction of SingleBBBonus or do you want me to move all changes of the form Threshold -=X => Threshold = std::max(Threshold - X, 0) into a separate patch? I think you mean the latter, but please clarify

[eraman]

Reverted all instances of Threshold = std::max(0, Threshold - X) to Threshold -= X. This is not strictly required and Philip asked me to take it out of this patch.

[reames]

lib/Analysis/InlineCost.cpp

1320

This still needs to be made an assert.

[eraman]

Address Philip's comment and fix a bug discovered in the process.

lib/Analysis/InlineCost.cpp

1319–1325

There is a subtle bug in my reasoning that is caught by adding the assert as suggested by Philip. The invariant is maintained at the beginning of the first iteration. In the first iteration, if analyzeBlock returned true (Cost <= Threshold), Cost could still end up > Threshold when SingleBBBonus is subtracted, violating the invariant in the second iteration. What I have done now is to add a if (Cost > Threshold) return false immediately after the SingleBBBonus is subtracted. I think this is a bit more readable since the check is present immediately after the bonus is subtracted.

[eraman]

Ping

[ahatanak]

This patch fixes a major regression for one of our users who builds his project with -Oz.

[eraman]

Ping.

[ahatanak]

Philip, does this patch look good now or do you have any other comments?

There are users waiting for this bug to be fixed, so I would like to see some progress.

[davidxl]

Sorry for the long delay.

Easwaran, please split the patches into smaller ones.

1. check in the refactoring code (allowSizeGrowth) -- no further review is required
2. split out another NFC clean-up code (i.e. removal of IsRecursiveCall etc at line 1328)
3. the remaining changes.

[eraman]

In D17584#393215, @davidxl wrote:

Sorry for the long delay.

Easwaran, please split the patches into smaller ones.

1. check in the refactoring code (allowSizeGrowth) -- no further review is required

Checkd in this part. This actually fixes the issue Akira had because you won't end up with a positive bonus, but an initial zero threshold. But the complex control flow means there could be other unintended results.

2. split out another NFC clean-up code (i.e. removal of IsRecursiveCall etc at line 1328)
3. the remaining changes.

[eraman]

In D17584#395995, @eraman wrote:

In D17584#393215, @davidxl wrote:

Sorry for the long delay.

Easwaran, please split the patches into smaller ones.

1. check in the refactoring code (allowSizeGrowth) -- no further review is required

Checkd in this part. This actually fixes the issue Akira had because you won't end up with a positive bonus, but an initial zero threshold. But the complex control flow means there could be other unintended results.

2. split out another NFC clean-up code (i.e. removal of IsRecursiveCall etc at line 1328)
3. the remaining changes.

It's not clear whether you asked me to commit 2 and 3 above or send them as different patches for review. I suppose it is the latter - could you confirm if that's the case?

[ahatanak]

In D17584#395995, @eraman wrote:

Checkd in this part. This actually fixes the issue Akira had because you won't end up with a positive bonus, but an initial zero threshold. But the complex control flow means there could be other unintended results.

Thanks! r265852 fixed the code size regression for the user's project.

Why wasn't the test case (inline_unreachable-2.ll) checked in? The test passes only after the fix in r265852 is applied, so it seems that it could have been checked in too?

[eraman]

In D17584#399881, @ahatanak wrote:

In D17584#395995, @eraman wrote:

Checkd in this part. This actually fixes the issue Akira had because you won't end up with a positive bonus, but an initial zero threshold. But the complex control flow means there could be other unintended results.

Thanks! r265852 fixed the code size regression for the user's project.

Why wasn't the test case (inline_unreachable-2.ll) checked in? The test passes only after the fix in r265852 is applied, so it seems that it could have been checked in too?

Either part 1 or 3 above fixes the issue. I will check in the test case.

[eraman]

Submitted the second part. Instead of the third part, I think it is better to just return when Cost > Threshold instead of breaking out of the loop. Moving the check inside if (SingleBB && TI->getNumSuccessors() > 1) reduces the readability IMO.

[eraman]

Remove the parts that are already committed and tweak the remaining part.

[davidxl]

lib/Analysis/InlineCost.cpp

1323

does CA.Threshold needs to be readjusted? Probably not.

[eraman]

lib/Analysis/InlineCost.cpp

1323

I don't think it matters. AFAICT, the only situation where we use CA.Threshold even if CA.analyzeCall returns false is in providing diagnostics (-Rpass-analysis=inline and others). It'll still show Cost > Threshold. If we readjust, it might show Cost is much greater than threshold if the bonuses were removed, but in any case Cost itself is not accurate when we bail out early.

FYI, the second part I had already checked in has the same issue and I don't adjust the Threshold downwards.

lib/Analysis/InlineCost.cpp

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   /// inlined through this particular callsite.
   bool isKnownNonNullInCallee(Value *V);
 
   /// Update Threshold based on callsite properties such as callee
   /// attributes and callee hotness for PGO builds. The Callee is explicitly
   /// passed to support analyzing indirect calls whose target is inferred by
   /// analysis.
   void updateThreshold(CallSite CS, Function &Callee);
 
   /// Return true if size growth is allowed when inlining the callee at CS.
   bool allowSizeGrowth(CallSite CS);
 
   // Custom analysis routines.
   bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
 
   // Disable several entry points to the visitor so we don't accidentally use
   // them by declaring but not defining them here.
if (isAllocaDerivedArg(V))
     // We can actually predict the result of comparisons between an
     // alloca-derived value and null. Note that this fires regardless of
     // SROA firing.
     return true;
   
   return false;
 }
 
 bool CallAnalyzer::allowSizeGrowth(CallSite CS) {
   // If the normal destination of the invoke or the parent block of the call
   // site is unreachable-terminated, there is little point in inlining this
   // unless there is literally zero cost.
   // FIXME: Note that it is possible that an unreachable-terminated block has a
   // hot entry. For example, in below scenario inlining hot_call_X() may be
   // beneficial :
   // main() {
   //   hot_call_1();
bool CallAnalyzer::analyzeCall(CallSite CS) {
   // basic blocks in a breadth-first order as we insert live successors. To
   // accomplish this, prioritizing for small iterations because we exit after
   // crossing our threshold, we use a small-size optimized SetVector.
   typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
                                   SmallPtrSet<BasicBlock *, 16> > BBSetVector;
   BBSetVector BBWorklist;
   BBWorklist.insert(&F.getEntryBlock());
   // Note that we *must not* cache the size, this loop grows the worklist.
   for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
     // Bail out the moment we cross the threshold. This means we'll under-count
     // the cost, but only when undercounting doesn't matter.
     if (Cost > Threshold)
-      break;
+      return false;
 
     BasicBlock *BB = BBWorklist[Idx];
     if (BB->empty())
       continue;
 
     // Disallow inlining a blockaddress. A blockaddress only has defined
     // behavior for an indirect branch in the same function, and we do not
     // currently support inlining indirect branches. But, the inliner may not
     // see an indirect branch that ends up being dead code at a particular call
     // site. If the blockaddress escapes the function, e.g., via a global
     // variable, inlining may lead to an invalid cross-function reference.
     if (BB->hasAddressTaken())
       return false;
 
     // Analyze the cost of this block. If we blow through the threshold, this
     // returns false, and we can bail on out.
     if (!analyzeBlock(BB, EphValues))
       return false;
 
     TerminatorInst *TI = BB->getTerminator();
 
     // Add in the live successors by first checking whether we have terminator
     // that may be simplified based on the values simplified by this call.
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       if (BI->isConditional()) {
for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
       BBWorklist.insert(TI->getSuccessor(TIdx));
 
     // If we had any successors at this point, than post-inlining is likely to
     // have them as well. Note that we assume any basic blocks which existed
     // due to branches or switches which folded above will also fold after
     // inlining.
     if (SingleBB && TI->getNumSuccessors() > 1) {
       // Take off the bonus we applied to the threshold.
       Threshold -= SingleBBBonus;
       SingleBB = false;
     }
   }
 
   // If this is a noduplicate call, we can still inline as long as
   // inlining this would cause the removal of the caller (so the instruction
   // is not actually duplicated, just moved).
   if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)