[Inliner] Optimize shouldBeDeferred

[eraman]

Summary

This has some minor optimizations to shouldBeDeferred. This is not
strictly NFC because the early exit inside the loop assumes
TotalSecondaryCost is monotonically non-decreasing, which is not true if
the threshold used by CostAnalyzer is negative. AFAICT the thresholds do
not go below 0 for the default values of the various options we use.

[eraman]

Rebase.

[eraman]

Reviving this old patch as Wei recently noticed a case where a large function with many callees and many callers spent significant amount of time in shouldBeDeferred. This was triggered by change in profile causing many callees to be inlined into this large function.

[chandlerc]

Nice, LGTM!

Does it make sense to add a (very early) assert that the thresholds are non-negative? I agree with you that it shouldn't be happening and it seems like a good invariant to enforce. Can of course be a follow-up patch.

lib/Transforms/IPO/Inliner.cpp

340

Despite the old variable's name, this should be ApplyLastCallBonus.

[eraman]

In D34919#1346838, @chandlerc wrote:

Nice, LGTM!

Does it make sense to add a (very early) assert that the thresholds are non-negative? I agree with you that it shouldn't be happening and it seems like a good invariant to enforce. Can of course be a follow-up patch.

I don't know if we make implicit assumptions about threshold being positive, but I agree this seems a reasonable invariant to enforce. I turned on an assert and found that a test case that passes --inline-threshold=-2 breaks. I will add the assert in a follow-up patch along with the fix to the test.

[eraman]

Fix variable naming.

[eraman]

In D34919#1346759, @eraman wrote:

Reviving this old patch as Wei recently noticed a case where a large function with many callees and many callers spent significant amount of time in shouldBeDeferred. This was triggered by change in profile causing many callees to be inlined into this large function.

The instance Wei observed didn't have multiple callers. I mis-understood the case and Wei thought this patch fixed the issue, but it actually didn't. Still, I think this is a useful fix.

[chandlerc]

In D34919#1347095, @eraman wrote:

In D34919#1346759, @eraman wrote:

Reviving this old patch as Wei recently noticed a case where a large function with many callees and many callers spent significant amount of time in shouldBeDeferred. This was triggered by change in profile causing many callees to be inlined into this large function.

The instance Wei observed didn't have multiple callers. I mis-understood the case and Wei thought this patch fixed the issue, but it actually didn't. Still, I think this is a useful fix.

Totally agree, still LGTM.

lib/Transforms/IPO/Inliner.cpp

 /// caller if \p CS is suppressed for inlining.
 static bool
 shouldBeDeferred(Function *Caller, CallSite CS, InlineCost IC,
                  int &TotalSecondaryCost,
                  function_ref<InlineCost(CallSite CS)> GetInlineCost) {
   // For now we only handle local or inline functions.
   if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
     return false;
+  // If the cost of inlining CS is non-positive, it is not going to prevent the
+  // caller from being inlined into its callers and hence we don't need to
+  // defer.
+  if (IC.getCost() <= 0)
+    return false;
   // Try to detect the case where the current inlining candidate caller (call
   // it B) is a static or linkonce-ODR function and is an inlining candidate
   // elsewhere, and the current candidate callee (call it C) is large enough
   // that inlining it into B would make B too big to inline later. In these
   // circumstances it may be best not to inline C into B, but to inline B into
   // its callers.
   //
   // This only applies to static and linkonce-ODR functions because those are
   // expected to be available for inlining in the translation units where they
   // are used. Thus we will always have the opportunity to make local inlining
   // decisions. Importantly the linkonce-ODR linkage covers inline functions
   // and templates in C++.
   //
   // FIXME: All of this logic should be sunk into getInlineCost. It relies on
   // the internal implementation of the inline cost metrics rather than
   // treating them as truly abstract units etc.
   TotalSecondaryCost = 0;
   // The candidate cost to be imposed upon the current function.
   int CandidateCost = IC.getCost() - 1;
-  // This bool tracks what happens if we do NOT inline C into B.
-  bool callerWillBeRemoved = Caller->hasLocalLinkage();
+  // If the caller has local linkage and can be inlined to all its callers, we
+  // can apply a huge negative bonus to TotalSecondaryCost.
+  bool ApplyLastCallBonus = Caller->hasLocalLinkage() && !Caller->hasOneUse();
   // This bool tracks what happens if we DO inline C into B.
   bool inliningPreventsSomeOuterInline = false;
   for (User *U : Caller->users()) {
+    // If the caller will not be removed (either because it does not have a
+    // local linkage or because the LastCallToStaticBonus has been already
+    // applied), then we can exit the loop early.
+    if (!ApplyLastCallBonus && TotalSecondaryCost >= IC.getCost())
+      return false;
     CallSite CS2(U);
 
     // If this isn't a call to Caller (it could be some other sort
     // of reference) skip it.  Such references will prevent the caller
     // from being removed.
     if (!CS2 || CS2.getCalledFunction() != Caller) {
-      callerWillBeRemoved = false;
+      ApplyLastCallBonus = false;
       continue;
     }
 
     InlineCost IC2 = GetInlineCost(CS2);
     ++NumCallerCallersAnalyzed;
     if (!IC2) {
-      callerWillBeRemoved = false;
+      ApplyLastCallBonus = false;
       continue;
     }
     if (IC2.isAlways())
       continue;
 
     // See if inlining of the original callsite would erase the cost delta of
     // this callsite. We subtract off the penalty for the call instruction,
     // which we would be deleting.
     if (IC2.getCostDelta() <= CandidateCost) {
       inliningPreventsSomeOuterInline = true;
       TotalSecondaryCost += IC2.getCost();
     }
   }
   // If all outer calls to Caller would get inlined, the cost for the last
   // one is set very low by getInlineCost, in anticipation that Caller will
   // be removed entirely.  We did not account for this above unless there
   // is only one caller of Caller.
-  if (callerWillBeRemoved && !Caller->hasOneUse())
+  if (ApplyLastCallBonus)
     TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
 
   if (inliningPreventsSomeOuterInline && TotalSecondaryCost < IC.getCost())
     return true;
 
   return false;
 }