[Inliner] Do not apply any bonus for cold callsites.

[eraman]

Summary

Inlining cold callsites into a not-cold caller could prevent further
inlining of the caller.

[chandlerc]

This change makes lots of sense to me.... However, the change description should really spell out more details about what's going on. You should assume that some of the readers of the change description don't know (or have forgotten) some of the context in your head about why this is all important and how it fits together.

I'm guessing that far and away the biggest difference is the last-call bonus? I suspect it is worth calling out that specific case.

Does function-attrs mark these as coldcc so that we use a cheaper calling convention for them? If not, we should do that. We should also discount the cost of calling them when computing other functions' inline cost. Probably just worth a FIXME comment here or a mention in the description as future work.

lib/Analysis/InlineCost.cpp

712

Would it make more sense to just update the bonuses to reflect what they should be for cold call sites?

I mostly find the boolean interaction with all the bonuses very brittle and easy got get wrong. Are there other ways of structuring this?

If not, I might set the boolean based on semantics rather than logic -- specifically that this is a *cold* call edge. That will make it more obvious why we would skip bonuses below for that case.

1328–1329

However you end up changing around the logic above, you should update the comments here to make it *really clear* what tradeoff you're making with this code as it is different now.

Notably, we have a bool whose only purpose is to organize the predicates going into this if, and now we have a new predicate that is not in the bool... which I think makes sense, but is a little odd to be omitted from the comment.

[eraman]

In D35823#819607, @chandlerc wrote:

Does function-attrs mark these as coldcc so that we use a cheaper calling convention for them?

No. In InlineCost, calls with coldcc get a high penalty (2000). So marking them as coldcc in function-attrs (which comes before inlining) will have the effect of not inlining them.

If not, we should do that. We should also discount the cost of calling them when computing other functions' inline cost.

It's not clear to me why we should do this. Is it because coldcc calls are cheaper (or even free)?
>Probably just worth a FIXME comment here or a mention in the description as future work.

lib/Analysis/InlineCost.cpp

712

I've attempted to do this by keeping the bonus percentages as variables that are reset when the callsite is cold.

1328–1329

I've added comments saying why we disable this even if it might reduce code size. Let me know if you are expecting something more.

[eraman]

Address Chandler's comments.

[eraman]

Replace the two vector bonus variables by one.

The smaller vector bonus is half of the larger one, so I've used just one VectorBonus variable.

[chandlerc]

LGTM, thanks!

lib/Analysis/InlineCost.cpp

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool HasIndirectBr;
   bool HasFrameEscape;
 
   /// Number of bytes allocated statically by the callee.
   uint64_t AllocatedSize;
   unsigned NumInstructions, NumVectorInstructions;
   int FiftyPercentVectorBonus, TenPercentVectorBonus;
   int VectorBonus;
+  bool DoNotApplyBonuses;
 
   /// While we walk the potentially-inlined instructions, we build up and
   /// maintain a mapping of simplified values specific to this callsite. The
   /// idea is to propagate any special information we have about arguments to
   /// this call through the inlinable section of the function, and account for
   /// likely simplifications post-inlining. The most important aspect we track
   /// is CFG altering simplifications -- when we prove a basic block dead, that
   /// can cause dramatic shifts in the cost of inlining a function.
CallAnalyzer(const TargetTransformInfo &TTI,
       : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI),
         PSI(PSI), F(Callee), DL(F.getParent()->getDataLayout()),
         CandidateCS(CSArg), Params(Params), Threshold(Params.DefaultThreshold),
         Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
         ExposesReturnsTwice(false), HasDynamicAlloca(false),
         ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
         HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
         NumVectorInstructions(0), FiftyPercentVectorBonus(0),
-        TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
-        NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
-        NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
-        SROACostSavings(0), SROACostSavingsLost(0) {}
+        TenPercentVectorBonus(0), VectorBonus(0), DoNotApplyBonuses(false),
+        NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0),
+        NumConstantPtrCmps(0), NumConstantPtrDiffs(0),
+        NumInstructionsSimplified(0), SROACostSavings(0),
+        SROACostSavingsLost(0) {}
 
   bool analyzeCall(CallSite CS);
 
   int getThreshold() { return Threshold; }
   int getCost() { return Cost; }
 
   // Keep a bunch of stats about the cost savings found so we can print them
   // out when debugging.
if (PSI) {
       // sample profile is used (which adds hotness metadata to calls) or if
       // caller's BlockFrequencyInfo is available.
       if (CallerBFI || PSI->hasSampleProfile()) {
         if (PSI->isHotCallSite(CS, CallerBFI)) {
           DEBUG(dbgs() << "Hot callsite.\n");
           Threshold = Params.HotCallSiteThreshold.getValue();
         } else if (isColdCallSite(CS, CallerBFI)) {
           DEBUG(dbgs() << "Cold callsite.\n");
+          DoNotApplyBonuses = true;
           Threshold = MinIfValid(Threshold, Params.ColdCallSiteThreshold);
         }
       } else {
         if (PSI->isFunctionEntryHot(&Callee)) {
           DEBUG(dbgs() << "Hot callee.\n");
           // If callsite hotness can not be determined, we may still know
           // that the callee is hot and treat it as a weaker hint for threshold
           // increase.
bool CallAnalyzer::analyzeCall(CallSite CS) {
   // FIXME: It would be nice to remove all such bonuses. At least it would be
   // nice to base the bonus values on something more scientific.
   assert(NumInstructions == 0);
   assert(NumVectorInstructions == 0);
 
   // Update the threshold based on callsite properties
   updateThreshold(CS, F);
 
+  if (!DoNotApplyBonuses) {
     FiftyPercentVectorBonus = 3 * Threshold / 2;
     TenPercentVectorBonus = 3 * Threshold / 4;
+  }
 
   // Track whether the post-inlining function would have more than one basic
   // block. A single basic block is often intended for inlining. Balloon the
   // threshold by 50% until we pass the single-BB phase.
   bool SingleBB = true;
-  int SingleBBBonus = Threshold / 2;
+  int SingleBBBonus = 0;
+  if (!DoNotApplyBonuses)
+    SingleBBBonus = Threshold / 2;
 
   // Speculatively apply all possible bonuses to Threshold. If cost exceeds
   // this Threshold any time, and cost cannot decrease, we can stop processing
   // the rest of the function body.
   Threshold += (SingleBBBonus + FiftyPercentVectorBonus);
 
   // Give out bonuses for the callsite, as the instructions setting them up
   // will be gone after inlining.
   Cost -= getCallsiteCost(CS, DL);
 
   // If there is only one call of the function, and it has internal linkage,
   // the cost of inlining it drops dramatically.
   bool OnlyOneCallAndLocalLinkage =
       F.hasLocalLinkage() && F.hasOneUse() && &F == CS.getCalledFunction();
-  if (OnlyOneCallAndLocalLinkage)
+  if (OnlyOneCallAndLocalLinkage && !DoNotApplyBonuses)
     Cost -= InlineConstants::LastCallToStaticBonus;
 
   // If this function uses the coldcc calling convention, prefer not to inline
   // it.
   if (F.getCallingConv() == CallingConv::Cold)
     Cost += InlineConstants::ColdccPenalty;
 
   // Check if we're done. This can happen due to bonuses and penalties.
   if (Cost > Threshold)

test/Transforms/Inline/last-call-bonus.ll

 ; The goal of this test is checking if LastCallToStaticBonus is applied
 ; correctly while deciding inline deferral. For the test code below, when
 ; inliner evaluates the callsite of bar->baz, it checks if inlining of bar->baz
 ; prevents ininling of foo->bar, even when foo->bar inlining is more beneficial
 ; than bar->baz inlining. As LastCallToStaticBonus has a massive value, and
 ; both baz and bar has only one caller, the cost of foo->bar inlining and
 ; bar->baz inlining should be non-trivial for inliner to compute that bar->baz
 ; inlining can actaully prevent foo->bar inlining. To make the cost of these
 ; callsites big enough, loop unrolling pass with very high threshold is used to
 ; preprocess the test.
 
 ; RUN: opt < %s -loop-unroll -inline -unroll-threshold=15000 -inline-threshold=250 -S | FileCheck %s
+; RUN: opt < %s -passes='function(require<opt-remark-emit>,loop(unroll)),require<profile-summary>,cgscc(inline)' -unroll-threshold=15000 -inline-threshold=250 -S | FileCheck %s
 ; CHECK-LABEL: define internal i32 @bar()
 
 define internal i32 @baz() {
 entry:
   br label %bb1
 
 bb1:
   %ind = phi i32 [ 0, %entry ], [ %inc, %bb1 ]

test/Transforms/Inline/last-call-no-bonus.ll

+; This code is virtually identical to last-call-bonus.ll, but the callsites
+; to the internal functions are cold, thereby preventing the last call to
+; static bonus from being applied.
+
+; RUN: opt < %s -passes='function(require<opt-remark-emit>,loop(unroll)),require<profile-summary>,cgscc(inline)' -unroll-threshold=15000 -inline-threshold=250 -S | FileCheck %s
+
+; CHECK-LABEL: define internal i32 @baz
+define internal i32 @baz() {
+entry:
+  br label %bb1
+
+bb1:
+  %ind = phi i32 [ 0, %entry ], [ %inc, %bb1 ]
+  call void @extern()
+  %inc = add nsw i32 %ind, 1
+  %cmp = icmp sgt i32 %inc, 510
+  br i1 %cmp, label %ret, label %bb1
+
+ret:
+  ret i32 0
+}
+
+; CHECK-LABEL: define internal i32 @bar
+define internal i32 @bar(i1 %b) {
+entry:
+  br label %bb1
+
+bb1:
+  %ind = phi i32 [ 0, %entry ], [ %inc, %bb1 ]
+  call void @extern()
+  %inc = add nsw i32 %ind, 1
+  %cmp = icmp sgt i32 %inc, 510
+  br i1 %cmp, label %for.exit, label %bb1
+
+for.exit:
+  br i1 %b, label %bb2, label %ret, !prof !0
+bb2:
+; CHECK: call i32 @baz
+  call i32 @baz()
+  br label %ret
+ret:
+  ret i32 0
+}
+; CHECK-LABEL: define i32 @foo
+define i32 @foo(i1 %b) {
+entry:
+  br i1 %b, label %bb1, label %ret, !prof !0
+bb1:
+; CHECK: call i32 @bar
+  call i32 @bar(i1 %b)
+  br label %ret
+ret:
+  ret i32 0
+}
+
+declare void @extern()
+
+!0 = !{!"branch_weights", i32 1, i32 2500}

test/Transforms/Inline/vector-no-bonus.ll

+; The code in this test is very similar to vector-bonus.ll except for
+; the fact that the call to bar is cold thereby preventing the application of
+; the vector bonus.
+; RUN: opt < %s -inline -inline-threshold=35  -S | FileCheck %s
+; RUN: opt < %s -passes='cgscc(inline)' -inline-threshold=35  -S | FileCheck %s
+
+define i32 @bar(<4 x i32> %v, i32 %i) #0 {
+entry:
+  %cmp = icmp sgt i32 %i, 4
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %mul1 = mul nsw i32 %i, %i
+  br label %return
+
+if.else:                                          ; preds = %entry
+  %add1 = add nsw i32 %i, %i
+  %add2 = add nsw i32 %i, %i
+  %add3 = add nsw i32 %i, %i
+  %add4 = add nsw i32 %i, %i
+  %add5 = add nsw i32 %i, %i
+  %add6 = add nsw i32 %i, %i
+  %vecext = extractelement <4 x i32> %v, i32 0
+  %vecext7 = extractelement <4 x i32> %v, i32 1
+  %add7 = add nsw i32 %vecext, %vecext7
+  br label %return
+
+return:                                           ; preds = %if.else, %if.then
+  %retval.0 = phi i32 [ %mul1, %if.then ], [ %add7, %if.else ]
+  ret i32 %retval.0
+}
+
+define i32 @foo(<4 x i32> %v, i32 %a) #1 {
+; CHECK-LABEL: @foo(
+; CHECK-NOT: call i32 @bar
+; CHECK: ret
+entry:
+  %cmp = icmp eq i32 %a, 0
+  br i1 %cmp, label %callbb, label %ret
+callbb:
+  %call = call i32 @bar(<4 x i32> %v, i32 %a)
+  br label %ret
+ret:
+  %call1 = phi i32 [%call, %callbb], [0, %entry]
+  ret i32 %call1
+}
+