[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 ↗

(On Diff #107994)

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 ↗

(On Diff #107994)

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 ↗

(On Diff #107994)

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

1328–1329 ↗

(On Diff #107994)

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!

llvm/trunk/lib/Analysis/InlineCost.cpp

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool ContainsNoDuplicateCall;
   bool HasReturn;
   bool HasIndirectBr;
   bool HasFrameEscape;
 
   /// Number of bytes allocated statically by the callee.
   uint64_t AllocatedSize;
   unsigned NumInstructions, NumVectorInstructions;
-  int FiftyPercentVectorBonus, TenPercentVectorBonus;
-  int VectorBonus;
+  int VectorBonus, TenPercentVectorBonus;
+  // Bonus to be applied when the callee has only one reachable basic block.
+  int SingleBBBonus;
 
   /// 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,
                const InlineParams &Params)
       : 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) {}
+        NumVectorInstructions(0), VectorBonus(0), SingleBBBonus(0),
+        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.
auto MinIfValid = [](int A, Optional<int> B) {
     return B ? std::min(A, B.getValue()) : A;
   };
 
   // return max(A, B) if B is valid.
   auto MaxIfValid = [](int A, Optional<int> B) {
     return B ? std::max(A, B.getValue()) : A;
   };
 
+  // Various bonus percentages. These are multiplied by Threshold to get the
+  // bonus values.
+  // SingleBBBonus: This bonus is applied if the callee has a single reachable
+  // basic block at the given callsite context. This is speculatively applied
+  // and withdrawn if more than one basic block is seen.
+  //
+  // Vector bonuses: We want to more aggressively inline vector-dense kernels
+  // and apply this bonus based on the percentage of vector instructions. A
+  // bonus is applied if the vector instructions exceed 50% and half that amount
+  // is applied if it exceeds 10%. Note that these bonuses are some what
+  // arbitrary and evolved over time by accident as much as because they are
+  // principled bonuses.
+  // FIXME: It would be nice to base the bonus values on something more
+  // scientific.
+  //
+  // 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;
+
+  // Lambda to set all the above bonus and bonus percentages to 0.
+  auto DisallowAllBonuses = [&]() {
+    SingleBBBonusPercent = 0;
+    VectorBonusPercent = 0;
+    LastCallToStaticBonus = 0;
+  };
+
   // Use the OptMinSizeThreshold or OptSizeThreshold knob if they are available
   // and reduce the threshold if the caller has the necessary attribute.
-  if (Caller->optForMinSize())
+  if (Caller->optForMinSize()) {
     Threshold = MinIfValid(Threshold, Params.OptMinSizeThreshold);
-  else if (Caller->optForSize())
+    // For minsize, we want to disable the single BB bonus and the vector
+    // bonuses, but not the last-call-to-static bonus. Inlining the last call to
+    // a static function will, at the minimum, eliminate the parameter setup and
+    // call/return instructions.
+    SingleBBBonusPercent = 0;
+    VectorBonusPercent = 0;
+  } else if (Caller->optForSize())
     Threshold = MinIfValid(Threshold, Params.OptSizeThreshold);
 
   // Adjust the threshold based on inlinehint attribute and profile based
   // hotness information if the caller does not have MinSize attribute.
   if (!Caller->optForMinSize()) {
     if (Callee.hasFnAttribute(Attribute::InlineHint))
       Threshold = MaxIfValid(Threshold, Params.HintThreshold);
     if (PSI) {
       BlockFrequencyInfo *CallerBFI = GetBFI ? &((*GetBFI)(*Caller)) : nullptr;
       // FIXME: After switching to the new passmanager, simplify the logic below
       // by checking only the callsite hotness/coldness. The check for CallerBFI
       // exists only because we do not have BFI available with the old PM.
       //
       // Use callee's hotness information only if we have no way of determining
       // callsite's hotness information. Callsite hotness can be determined if
       // 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");
+          // Do not apply bonuses for a cold callsite including the
+          // LastCallToStatic bonus. While this bonus might result in code size
+          // reduction, it can cause the size of a non-cold caller to increase
+          // preventing it from being inlined.
+          DisallowAllBonuses();
           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.
           Threshold = MaxIfValid(Threshold, Params.HintThreshold);
         } else if (PSI->isFunctionEntryCold(&Callee)) {
           DEBUG(dbgs() << "Cold callee.\n");
+          // Do not apply bonuses for a cold callee including the
+          // LastCallToStatic bonus. While this bonus might result in code size
+          // 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.
   Threshold *= TTI.getInliningThresholdMultiplier();
+
+  SingleBBBonus = Threshold * SingleBBBonusPercent / 100;
+  VectorBonus = Threshold * VectorBonusPercent / 100;
+
+  bool OnlyOneCallAndLocalLinkage =
+      F.hasLocalLinkage() && F.hasOneUse() && &F == CS.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;
 }
 
 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::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);
 
-  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;
-
   // 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);
+  Threshold += (SingleBBBonus + VectorBonus);
 
   // 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)
-    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)
     return false;
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());
+  bool SingleBB = true;
   // 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;
 
     BasicBlock *BB = BBWorklist[Idx];
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
     // inlining.
     if (SingleBB && TI->getNumSuccessors() > 1) {
       // Take off the bonus we applied to the threshold.
       Threshold -= SingleBBBonus;
       SingleBB = false;
     }
   }
 
+  bool OnlyOneCallAndLocalLinkage =
+      F.hasLocalLinkage() && F.hasOneUse() && &F == CS.getCalledFunction();
   // 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)
     return false;
 
   // We applied the maximum possible vector bonus at the beginning. Now,
   // subtract the excess bonus, if any, from the Threshold before
   // comparing against Cost.
   if (NumVectorInstructions <= NumInstructions / 10)
-    Threshold -= FiftyPercentVectorBonus;
+    Threshold -= VectorBonus;
   else if (NumVectorInstructions <= NumInstructions / 2)
-    Threshold -= (FiftyPercentVectorBonus - TenPercentVectorBonus);
+    Threshold -= VectorBonus/2;
 
   return Cost < std::max(1, Threshold);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 /// \brief Dump stats about this call's analysis.
 LLVM_DUMP_METHOD void CallAnalyzer::dump() {
 #define DEBUG_PRINT_STAT(x) dbgs() << "      " #x ": " << x << "\n"

llvm/trunk/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 ]

llvm/trunk/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}

llvm/trunk/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
+}
+