This is an archive of the discontinued LLVM Phabricator instance.

Cleanup inline cost analysis code
AcceptedPublic

Authored by eraman on Feb 24 2016, 3:50 PM.

Details

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

Diff Detail

Event Timeline

eraman updated this revision to Diff 48987.Feb 24 2016, 3:50 PM
eraman retitled this revision from to Fixes to inline cost analysis to prevent inlining when thresholds become negative.
eraman updated this object.
eraman added reviewers: hans, chandlerc.
eraman added subscribers: ahatanak, 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 updated this revision to Diff 49107.Feb 25 2016, 12:26 PM
eraman retitled this revision from Fixes to inline cost analysis to prevent inlining when thresholds become negative to Cleanup inline cost analysis code.
eraman updated this object.

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

hans edited edge metadata.Feb 25 2016, 1:26 PM

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 added inline comments.Feb 25 2016, 7:01 PM
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?

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 marked 2 inline comments as done.Feb 26 2016, 1:29 PM

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 updated this revision to Diff 49228.Feb 26 2016, 1:29 PM
eraman edited edge metadata.

Address review comments.

davidxl added inline comments.Feb 26 2016, 4:19 PM
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 added inline comments.Feb 26 2016, 5:04 PM
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 accepted this revision.Feb 26 2016, 8:57 PM
davidxl added a reviewer: 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.

This revision is now accepted and ready to land.Feb 26 2016, 8:57 PM
reames added a subscriber: reames.Mar 9 2016, 3:37 PM

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 added inline comments.Mar 9 2016, 3:58 PM
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 updated this revision to Diff 50505.Mar 11 2016, 5:37 PM
eraman edited edge metadata.

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 added inline comments.Mar 11 2016, 5:41 PM
lib/Analysis/InlineCost.cpp
1320

This still needs to be made an assert.

eraman updated this revision to Diff 50640.Mar 14 2016, 1:41 PM
eraman marked an inline comment as done.

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.

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

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.

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 added a comment.Apr 8 2016, 3:51 PM

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.

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

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.

  1. split out another NFC clean-up code (i.e. removal of IsRecursiveCall etc at line 1328)
  2. 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?

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?

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.

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 updated this revision to Diff 53630.Apr 13 2016, 3:29 PM

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

davidxl added inline comments.Apr 13 2016, 3:50 PM
lib/Analysis/InlineCost.cpp
1323

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

eraman added inline comments.Apr 13 2016, 4:04 PM
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.