[InlineCost] cleanup calculations of Cost and Threshold

[fedor.sergeev]

Summary

Doing better separation of Cost and Threshold.
Cost counts the abstract complexity of live instructions, while Threshold is an upper bound of complexity that inlining is comfortable to pay.
There are two parts:

• huge 15K last-call-to-static bonus is no longer subtracted from Cost but rather is now added to Threshold.
  
  That makes much more sense, as the cost of inlining (Cost) is not changed by the fact that internal function is called once. It only changes the likelyhood of this inlining being profitable (Threshold).
• bonus for calls proved-to-be-inlinable into callee is no longer subtracted from Cost but added to Threshold instead.

While calculations are somewhat different, overall InlineResult should stay the same since Cost >= Threshold compares the same.

[yrouban]

I would split this change into NFC and last-call-to-static.

lib/Analysis/InlineCost.cpp

295 ↗

(On Diff #195275)

Cost is int, why do we use int64_t? May be UpperBound should be int?

316 ↗

(On Diff #195275)

may be all const initialization can be moved to field declarations like you do with Cost, VectorBonus, ...

[fedor.sergeev]

lib/Analysis/InlineCost.cpp

295 ↗

(On Diff #195275)

This is inspired by the original visitSwitchInst usages, where calculation specifically used std::min to avoid int32 overflows.
I decided that it should be ok to use the same sequence elsewhere.

[fedor.sergeev]

moving NFC part out of this change

[fedor.sergeev]

ping?

[apilipenko]

lib/Analysis/InlineCost.cpp

162–167 ↗

(On Diff #195296)

I don't think we need to store it here. Other bonuses, like VectorBonus, are "speculative", i.e. we apply them first and revoke if the conditions don't hold.

258–263 ↗

(On Diff #195296)

If you don't store it in a field, you don't need a setter function.

[fedor.sergeev]

removing InlineCallBonus

[chandlerc]

llvm/trunk/lib/Analysis/InlineCost.cpp

983–984

The change doesn't say anything about how it addresses this last sentence in the comment that seems to be indicating that the decision to update cost (instead of threshold) was not made arbitrarily.

How did you verify that this doesn't in fact change the way bonuses end up being applied?

[chandlerc]

Pointing out the (serious) bug in this change below.

llvm/trunk/lib/Analysis/InlineCost.cpp

1337

I think this is the source of the (huge) behavior change.

We reduced the cost to apply some forms of bonus because it only decreases the *cost* of inlining, but doesn't increase the *benefit* of inlining. Now that is reversed.

So in this case, if the inner call is to a function where this is the last call, the threshold is now *HUGE*, and the cost is small. We take that huge threshold, and apply it blindly to our threshold here.

This will cause us to inline waaay too much along call stacks that (eventually) have an reachable, inlinable call to function which is the last call to that function.

[rupprecht]

Thanks for the explanation. Temporarily reverted in r365000.

[fedor.sergeev]

In D60740#1567790, @rupprecht wrote:

Thanks for the explanation. Temporarily reverted in r365000.

Thanks for @chandlerc doing the analysis and @rupprecht doing a revert!
I will surely get to addressing this issue now.

llvm/trunk/lib/Analysis/InlineCost.cpp

void CallAnalyzer::updateThreshold(CallBase &Call, Function &Callee) {
   // LstCallToStaticBonus: This large bonus is applied to ensure the inlining
   // of the last call to a static function as inlining such functions is
   // guaranteed to reduce code size.
   //
   // These bonus percentages may be set to 0 based on properties of the caller
   // and the callsite.
   int SingleBBBonusPercent = 50;
   int VectorBonusPercent = 150;
-  int LastCallToStaticBonus = InlineConstants::LastCallToStaticBonus;
+
+  int LastCallToStaticBonus = 0;
+  bool OnlyOneCallAndLocalLinkage =
+      F.hasLocalLinkage() && F.hasOneUse() && &F == Call.getCalledFunction();
+  // If there is only one call of the function, and it has internal linkage,
+  // we can allow to inline pretty anything as it will lead to size reduction
+  // anyway.
+  if (OnlyOneCallAndLocalLinkage)
+    LastCallToStaticBonus = InlineConstants::LastCallToStaticBonus;
 
   // Lambda to set all the above bonus and bonus percentages to 0.
   auto DisallowAllBonuses = [&]() {
     SingleBBBonusPercent = 0;
     VectorBonusPercent = 0;
     LastCallToStaticBonus = 0;
   };
 
if (!Caller->hasOptSize() && HotCallSiteThreshold) {
         // reduction, it can cause the size of a non-cold caller to increase
         // preventing it from being inlined.
         DisallowAllBonuses();
         Threshold = MinIfValid(Threshold, Params.ColdThreshold);
       }
     }
   }
 
-  // Finally, take the target-specific inlining threshold multiplier into
-  // account.
+  // Take the target-specific inlining threshold multiplier into account.
   Threshold *= TTI.getInliningThresholdMultiplier();
 
   SingleBBBonus = Threshold * SingleBBBonusPercent / 100;
   VectorBonus = Threshold * VectorBonusPercent / 100;
 
-  bool OnlyOneCallAndLocalLinkage =
-      F.hasLocalLinkage() && F.hasOneUse() && &F == Call.getCalledFunction();
-  // If there is only one call of the function, and it has internal linkage,
-  // the cost of inlining it drops dramatically. It may seem odd to update
-  // Cost in updateThreshold, but the bonus depends on the logic in this method.
-  if (OnlyOneCallAndLocalLinkage)
-    Cost -= LastCallToStaticBonus;
+  Threshold += LastCallToStaticBonus;
 }
 
 bool CallAnalyzer::visitCmpInst(CmpInst &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   // First try to handle simplified comparisons.
   if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
         return ConstantExpr::getCompare(I.getPredicate(), COps[0], COps[1]);
       }))
bool CallAnalyzer::visitCallBase(CallBase &Call) {
   // during devirtualization and so we want to give it a hefty bonus for
   // inlining, but cap that bonus in the event that inlining wouldn't pan
   // out. Pretend to inline the function, with a custom threshold.
   auto IndirectCallParams = Params;
   IndirectCallParams.DefaultThreshold = InlineConstants::IndirectCallThreshold;
   CallAnalyzer CA(TTI, GetAssumptionCache, GetBFI, PSI, ORE, *F, Call,
                   IndirectCallParams);
   if (CA.analyzeCall(Call)) {
-    // We were able to inline the indirect call! Subtract the cost from the
-    // threshold to get the bonus we want to apply, but don't go below zero.
-    Cost -= std::max(0, CA.getThreshold() - CA.getCost());
+    // We were able to inline the indirect call! Increase the threshold
+    // with the bonus we want to apply (less the cost of inlinee).
+    // Make sure the bonus doesn't go below zero.
+    Threshold += std::max(0, CA.getThreshold() - CA.getCost());
   }
 
   if (!F->onlyReadsMemory())
     disableLoadElimination();
   return Base::visitCallBase(Call);
 }
 
 bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {

llvm/trunk/test/LTO/Resolution/X86/diagnostic-handler-remarks-with-hotness.ll

 ; YAML-NEXT: Function:        main
 ; YAML-NEXT: Hotness:         300
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - Callee:          tinkywinky
 ; YAML-NEXT:   - String:          ' inlined into '
 ; YAML-NEXT:   - Caller:          main
 ; YAML-NEXT:   - String:          ' with '
 ; YAML-NEXT:   - String:          '(cost='
-; YAML-NEXT:   - Cost:            '-15000'
+; YAML-NEXT:   - Cost:            '0'
 ; YAML-NEXT:   - String:          ', threshold='
-; YAML-NEXT:   - Threshold:       '337'
+; YAML-NEXT:   - Threshold:       '15337'
 ; YAML-NEXT:   - String:          ')'
 ; YAML-NEXT: ...
 
-; CHECK: tinkywinky inlined into main with (cost=-15000, threshold=337) (hotness: 300)
+; CHECK: tinkywinky inlined into main with (cost=0, threshold=15337) (hotness: 300)
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-scei-ps4"
 
 declare i32 @patatino()
 
 define i32 @tinkywinky() {
   %a = call i32 @patatino()

llvm/trunk/test/LTO/Resolution/X86/diagnostic-handler-remarks.ll

 ; YAML-NEXT: Name:            Inlined
 ; YAML-NEXT: Function:        main
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - Callee:          tinkywinky
 ; YAML-NEXT:   - String:          ' inlined into '
 ; YAML-NEXT:   - Caller:          main
 ; YAML-NEXT:   - String:          ' with '
 ; YAML-NEXT:   - String:          '(cost='
-; YAML-NEXT:   - Cost:            '-15000'
+; YAML-NEXT:   - Cost:            '0'
 ; YAML-NEXT:   - String:          ', threshold='
-; YAML-NEXT:   - Threshold:       '337'
+; YAML-NEXT:   - Threshold:       '15337'
 ; YAML-NEXT:   - String:          ')'
 ; YAML-NEXT: ...
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-scei-ps4"
 
 declare i32 @patatino()
 

llvm/trunk/test/LTO/X86/diagnostic-handler-remarks-with-hotness.ll

 ; YAML-NEXT: Function:        main
 ; YAML-NEXT: Hotness:         300
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - Callee:          foo
 ; YAML-NEXT:   - String:          ' inlined into '
 ; YAML-NEXT:   - Caller:          main
 ; YAML-NEXT:   - String:          ' with '
 ; YAML-NEXT:   - String:          '(cost='
-; YAML-NEXT:   - Cost:            '-15000'
+; YAML-NEXT:   - Cost:            '0'
 ; YAML-NEXT:   - String:          ', threshold='
-; YAML-NEXT:   - Threshold:       '337'
+; YAML-NEXT:   - Threshold:       '15337'
 ; YAML-NEXT:   - String:          ')'
 ; YAML-NEXT: ...
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-darwin"
 
 declare i32 @bar()
 

llvm/trunk/test/LTO/X86/diagnostic-handler-remarks.ll

 ; YAML-NEXT: Name:            Inlined
 ; YAML-NEXT: Function:        main
 ; YAML-NEXT: Args:
 ; YAML-NEXT:   - Callee:          foo
 ; YAML-NEXT:   - String:          ' inlined into '
 ; YAML-NEXT:   - Caller:          main
 ; YAML-NEXT:   - String:          ' with '
 ; YAML-NEXT:   - String:          '(cost='
-; YAML-NEXT:   - Cost:            '-15000'
+; YAML-NEXT:   - Cost:            '0'
 ; YAML-NEXT:   - String:          ', threshold='
-; YAML-NEXT:   - Threshold:       '337'
+; YAML-NEXT:   - Threshold:       '15337'
 ; YAML-NEXT:   - String:          ')'
 ; YAML-NEXT: ...
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-darwin"
 
 declare i32 @bar()
 

llvm/trunk/test/Transforms/Inline/ARM/inline-fp.ll

 ; RUN: opt -S -inline -mtriple=arm-eabi -pass-remarks=.* -pass-remarks-missed=.* < %s 2>&1 | FileCheck %s -check-prefix=NOFP
 ; RUN: opt -S -inline -mtriple=arm-eabi -mattr=+vfp2 -pass-remarks=.* -pass-remarks-missed=.* < %s 2>&1 | FileCheck %s -check-prefix=FULLFP
 ; RUN: opt -S -inline -mtriple=arm-eabi -mattr=+vfp2,-fp64 -pass-remarks=.* -pass-remarks-missed=.* < %s 2>&1 | FileCheck %s -check-prefix=SINGLEFP
 ; Make sure that soft float implementations are calculated as being more expensive
 ; to the inliner.
 
 ; NOFP-DAG: single not inlined into test_single because too costly to inline (cost=125, threshold=75)
 ; NOFP-DAG: single not inlined into test_single because too costly to inline (cost=125, threshold=75)
 ; NOFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15, threshold=75)
-; NOFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15015, threshold=75)
+; NOFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15, threshold=15075)
 ; NOFP-DAG: double not inlined into test_double because too costly to inline (cost=125, threshold=75)
 ; NOFP-DAG: double not inlined into test_double because too costly to inline (cost=125, threshold=75)
 ; NOFP-DAG: single_force_soft not inlined into test_single_force_soft because too costly to inline (cost=125, threshold=75)
 ; NOFP-DAG: single_force_soft not inlined into test_single_force_soft because too costly to inline (cost=125, threshold=75)
 ; NOFP-DAG: single_force_soft_fneg not inlined into test_single_force_soft_fneg because too costly to inline (cost=100, threshold=75)
 ; NOFP-DAG: single_force_soft_fneg not inlined into test_single_force_soft_fneg because too costly to inline (cost=100, threshold=75)
 
 ; FULLFP-DAG: single inlined into test_single with (cost=0, threshold=75)
-; FULLFP-DAG: single inlined into test_single with (cost=-15000, threshold=75)
+; FULLFP-DAG: single inlined into test_single with (cost=0, threshold=15075)
 ; FULLFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15, threshold=75)
-; FULLFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15015, threshold=75)
+; FULLFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15, threshold=15075)
 ; FULLFP-DAG: double inlined into test_double with (cost=0, threshold=75)
-; FULLFP-DAG: double inlined into test_double with (cost=-15000, threshold=75)
+; FULLFP-DAG: double inlined into test_double with (cost=0, threshold=15075)
 ; FULLFP-DAG: single_force_soft not inlined into test_single_force_soft because too costly to inline (cost=125, threshold=75)
 ; FULLFP-DAG: single_force_soft not inlined into test_single_force_soft because too costly to inline (cost=125, threshold=75)
 ; FULLFP-DAG: single_force_soft_fneg not inlined into test_single_force_soft_fneg because too costly to inline (cost=100, threshold=75)
 ; FULLFP-DAG: single_force_soft_fneg not inlined into test_single_force_soft_fneg because too costly to inline (cost=100, threshold=75)
 
 ; SINGLEFP-DAG: single inlined into test_single with (cost=0, threshold=75)
-; SINGLEFP-DAG: single inlined into test_single with (cost=-15000, threshold=75)
+; SINGLEFP-DAG: single inlined into test_single with (cost=0, threshold=15075)
 ; SINGLEFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15, threshold=75)
-; SINGLEFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15015, threshold=75)
+; SINGLEFP-DAG: single_cheap inlined into test_single_cheap with (cost=-15, threshold=15075)
 ; SINGLEFP-DAG: double not inlined into test_double because too costly to inline (cost=125, threshold=75)
 ; SINGLEFP-DAG: double not inlined into test_double because too costly to inline (cost=125, threshold=75)
 ; SINGLEFP-DAG: single_force_soft not inlined into test_single_force_soft because too costly to inline (cost=125, threshold=75)
 ; SINGLEFP-DAG: single_force_soft not inlined into test_single_force_soft because too costly to inline (cost=125, threshold=75)
 ; SINGLEFP-DAG: single_force_soft_fneg not inlined into test_single_force_soft_fneg because too costly to inline (cost=100, threshold=75)
 ; SINGLEFP-DAG: single_force_soft_fneg not inlined into test_single_force_soft_fneg because too costly to inline (cost=100, threshold=75)
 
 define i32 @test_single(i32 %a, i8 %b, i32 %c, i8 %d) #0 {