[NewPM][Inliner] Make inlined calls to functions in same SCC as callee exponentially expensive

[aeubanks]

Summary

Introduce a new attribute "function-inline-cost-multiplier" which
multiplies the inline cost of a call site (or all calls to a callee) by
the multiplier.

When processing the list of calls created by inlining, check each call
to see if the new call's callee is in the same SCC as the original
callee. If so, set the "function-inline-cost-multiplier" attribute of
the new call site to double the original call site's attribute value.
This does not happen when the original call site is intra-SCC.

This is an alternative to D120584, which marks the call sites as
noinline.

Hopefully fixes PR45253.

[aeubanks]

llvm/test/Transforms/Inline/inline-cost-attributes.ll

27

this is due to implementation details of the printer pass

[nikic]

llvm/lib/Transforms/IPO/Inliner.cpp

973

CB has been deleted at this point -- the old cost multiplier needs to be fetched before InlineFunction is called.

[aeubanks]

UAF

[nikic]

I've not tested this as extensively, but this variant is also performance neutral on my side, and does seem to address the issue in practice.

This approach is a bit more ad-hoc than D120584, and it wouldn't be my first choice, unless we had evidence that it actually performs better than D120584 in some real-world instance. However, if this approach is more appealing to @davidxl, then I'm also fine with it as a compromise solution.

llvm/lib/Analysis/InlineCost.cpp

912

We should probably export this string so it's not repeated three times.

[davidxl]

llvm/lib/Transforms/IPO/Inliner.cpp

973

let '2' be controllable by an option.

[aeubanks]

address comments

[nikic]

I've been testing this with more cases, and unfortunately this one does sometimes do appreciably worse than D120584. For a fluent_bundle-derived test case, this approach takes 2x longer to compile than the previous version.

[aeubanks]

Perhaps we can experiment with the default value for -intra-scc-cost-multiplier. I know davidxl has done a lot of work with inline tuning so I'm inclined to go with this patch for now.

[aeubanks]

I did see a consistent 0.75-1% regression on an important internal benchmark with the other approach (which I believe we actually care about), although some benchmarks are sensitive to alignment.

[nikic]

In D121084#3365187, @aeubanks wrote:

I did see a consistent 0.75-1% regression on an important internal benchmark with the other approach (which I believe we actually care about), although some benchmarks are sensitive to alignment.

And the regressions is not present with this variant? If so, yeah, let's go with this.

llvm/lib/Transforms/IPO/Inliner.cpp

971

Should we also fetch the previous multiplier of ICB here and multiply it in? Not sure if it's really relevant in practice, but currently we're only preserving the existing multiplier from CB, but not ICB.

[aeubanks]

In D121084#3365306, @nikic wrote:

In D121084#3365187, @aeubanks wrote:

I did see a consistent 0.75-1% regression on an important internal benchmark with the other approach (which I believe we actually care about), although some benchmarks are sensitive to alignment.

And the regressions is not present with this variant? If so, yeah, let's go with this.

I haven't tested this variant yet and the benchmarks take hours to run. I'm going to start it now, but given that 14.0.0 is tomorrow I'll submit this tonight if the benchmark isn't done by then and request a cherry-pick since davidxl is happy with this and it helps with many of the worst compile time issues. If this does turn out to be similar to the noinline patch in terms of performance then we can do something with the noinline patch.

llvm/lib/Transforms/IPO/Inliner.cpp

971

if we had

a -> b <-> c

z -> a <-> d

where both the a -> b and z -> a inlinings were problematic, then multiplying the value in ICB could help, else we'd restart the multipliers

as you said, probably very unlikely, we can do that in a follow-up change if we think it's important

[tstellar]

Is this the patch we should backport to release/14.x?

[aeubanks]

In D121084#3366293, @tstellar wrote:

Is this the patch we should backport to release/14.x?

yeah that'd be awesome, thanks

[davide]

Hey folks, this is still not enough. We're seeing exponential behaviors when linking real-world projects.

Here's a reduced example that still goes exponential.
https://github.com/llvm/llvm-project/issues/59126

cc: @davidxl @aeubanks

llvm/include/llvm/Analysis/InlineCost.h

 const int LastCallToStaticBonus = 15000;
 const int ColdccPenalty = 2000;
 /// Do not inline functions which allocate this many bytes on the stack
 /// when the caller is recursive.
 const unsigned TotalAllocaSizeRecursiveCaller = 1024;
 /// Do not inline dynamic allocas that have been constant propagated to be
 /// static allocas above this amount in bytes.
 const uint64_t MaxSimplifiedDynamicAllocaToInline = 65536;
+
+const char FunctionInlineCostMultiplierAttributeName[] =
+    "function-inline-cost-multiplier";
 } // namespace InlineConstants
 
 // The cost-benefit pair computed by cost-benefit analysis.
 class CostBenefitPair {
 public:
   CostBenefitPair(APInt Cost, APInt Benefit) : Cost(Cost), Benefit(Benefit) {}
 
   const APInt &getCost() const { return Cost; }
struct InlineParams {
 
   /// Indicate whether we should allow inline deferral.
   Optional<bool> EnableDeferral;
 
   /// Indicate whether we allow inlining for recursive call.
   Optional<bool> AllowRecursiveCall = false;
 };
 
+Optional<int> getStringFnAttrAsInt(CallBase &CB, StringRef AttrKind);
+
 /// Generate the parameters to tune the inline cost analysis based only on the
 /// commandline options.
 InlineParams getInlineParams();
 
 /// Generate the parameters to tune the inline cost analysis based on command
 /// line options. If -inline-threshold option is not explicitly passed,
 /// \p Threshold is used as the default threshold.
 InlineParams getInlineParams(int Threshold);

llvm/lib/Analysis/InlineCost.cpp

static cl::opt<bool> InlineCallerSupersetNoBuiltin(
     cl::desc("Allow inlining when caller has a superset of callee's nobuiltin "
              "attributes."));
 
 static cl::opt<bool> DisableGEPConstOperand(
     "disable-gep-const-evaluation", cl::Hidden, cl::init(false),
     cl::desc("Disables evaluation of GetElementPtr with constant operands"));
 
 namespace {
-class InlineCostCallAnalyzer;
-
 /// This function behaves more like CallBase::hasFnAttr: when it looks for the
 /// requested attribute, it check both the call instruction and the called
 /// function (if it's available and operand bundles don't prohibit that).
 Attribute getFnAttr(CallBase &CB, StringRef AttrKind) {
   Attribute CallAttr = CB.getFnAttr(AttrKind);
   if (CallAttr.isValid())
     return CallAttr;
 
   // Operand bundles override attributes on the called function, but don't
   // override attributes directly present on the call instruction.
   if (!CB.isFnAttrDisallowedByOpBundle(AttrKind))
     if (const Function *F = CB.getCalledFunction())
       return F->getFnAttribute(AttrKind);
 
   return {};
 }
+} // namespace
 
+namespace llvm {
 Optional<int> getStringFnAttrAsInt(CallBase &CB, StringRef AttrKind) {
   Attribute Attr = getFnAttr(CB, AttrKind);
   int AttrValue;
   if (Attr.getValueAsString().getAsInteger(10, AttrValue))
     return None;
   return AttrValue;
 }
+} // namespace llvm
+
+namespace {
+class InlineCostCallAnalyzer;
 
 // This struct is used to store information about inline cost of a
 // particular instruction
 struct InstructionCostDetail {
   int CostBefore = 0;
   int CostAfter = 0;
   int ThresholdBefore = 0;
   int ThresholdAfter = 0;
if (NumVectorInstructions <= NumInstructions / 10)
       Threshold -= VectorBonus;
     else if (NumVectorInstructions <= NumInstructions / 2)
       Threshold -= VectorBonus / 2;
 
     if (Optional<int> AttrCost =
             getStringFnAttrAsInt(CandidateCall, "function-inline-cost"))
       Cost = *AttrCost;
 
+    if (Optional<int> AttrCostMult = getStringFnAttrAsInt(
+            CandidateCall,
+            InlineConstants::FunctionInlineCostMultiplierAttributeName))
+      Cost *= *AttrCostMult;
+
     if (Optional<int> AttrThreshold =
             getStringFnAttrAsInt(CandidateCall, "function-inline-threshold"))
       Threshold = *AttrThreshold;
 
     if (auto Result = costBenefitAnalysis()) {
       DecidedByCostBenefit = true;
       if (Result.getValue())
         return InlineResult::success();

llvm/lib/Transforms/IPO/Inliner.cpp

 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InlineAdvisor.h"

 /// prior to LLVM's code generator having support for stack coloring based on
 /// lifetime markers. It is now in the process of being removed. To experiment
 /// with disabling it and relying fully on lifetime marker based stack
 /// coloring, you can pass this flag to LLVM.
 static cl::opt<bool>
     DisableInlinedAllocaMerging("disable-inlined-alloca-merging",
                                 cl::init(false), cl::Hidden);
 
+static cl::opt<int> IntraSCCCostMultiplier(
+    "intra-scc-cost-multiplier", cl::init(2), cl::Hidden,
+    cl::desc(
+        "Cost multiplier to multiply onto inlined call sites where the "
+        "new call was previously an intra-SCC call (not relevant when the "
+        "original call was already intra-SCC). This can accumulate over "
+        "multiple inlinings (e.g. if a call site already had a cost "
+        "multiplier and one of its inlined calls was also subject to "
+        "this, the inlined call would have the original multiplier "
+        "multiplied by intra-scc-cost-multiplier). This is to prevent tons of "
+        "inlining through a child SCC which can cause terrible compile times"));
+
 /// A flag for test, so we can print the content of the advisor when running it
 /// as part of the default (e.g. -O3) pipeline.
 static cl::opt<bool> KeepAdvisorForPrinting("keep-inline-advisor-for-printing",
                                             cl::init(false), cl::Hidden);
 
 extern cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats;
 
 static cl::opt<std::string> CGSCCInlineReplayFile(
while (!Calls->empty() && Calls->front().first->getCaller() == &F) {
         continue;
       }
 
       // Check if this inlining may repeat breaking an SCC apart that has
       // already been split once before. In that case, inlining here may
       // trigger infinite inlining, much like is prevented within the inliner
       // itself by the InlineHistory above, but spread across CGSCC iterations
       // and thus hidden from the full inline history.
-      if (CG.lookupSCC(*CG.lookup(Callee)) == C &&
-          UR.InlinedInternalEdges.count({&N, C})) {
+      LazyCallGraph::SCC *CalleeSCC = CG.lookupSCC(*CG.lookup(Callee));
+      if (CalleeSCC == C && UR.InlinedInternalEdges.count({&N, C})) {
         LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node "
                              "previously split out of this SCC by inlining: "
                           << F.getName() << " -> " << Callee.getName() << "\n");
         setInlineRemark(*CB, "recursive SCC split");
         continue;
       }
 
       std::unique_ptr<InlineAdvice> Advice =
           Advisor.getAdvice(*CB, OnlyMandatory);
 
       // Check whether we want to inline this callsite.
       if (!Advice)
         continue;
 
       if (!Advice->isInliningRecommended()) {
         Advice->recordUnattemptedInlining();
         continue;
       }
 
+      int CBCostMult =
+          getStringFnAttrAsInt(
+              *CB, InlineConstants::FunctionInlineCostMultiplierAttributeName)
+              .getValueOr(1);
+
       // Setup the data structure used to plumb customization into the
       // `InlineFunction` routine.
       InlineFunctionInfo IFI(
           /*cg=*/nullptr, GetAssumptionCache, PSI,
           &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())),
           &FAM.getResult<BlockFrequencyAnalysis>(Callee));
 
       InlineResult IR =
while (!Calls->empty() && Calls->front().first->getCaller() == &F) {
           if (!NewCallee) {
             // Try to promote an indirect (virtual) call without waiting for
             // the post-inline cleanup and the next DevirtSCCRepeatedPass
             // iteration because the next iteration may not happen and we may
             // miss inlining it.
             if (tryPromoteCall(*ICB))
               NewCallee = ICB->getCalledFunction();
           }
-          if (NewCallee)
-            if (!NewCallee->isDeclaration())
+          if (NewCallee) {
+            if (!NewCallee->isDeclaration()) {
               Calls->push({ICB, NewHistoryID});
+              // Continually inlining through an SCC can result in huge compile
+              // times and bloated code since we arbitrarily stop at some point
+              // when the inliner decides it's not profitable to inline anymore.
+              // We attempt to mitigate this by making these calls exponentially
+              // more expensive.
+              // This doesn't apply to calls in the same SCC since if we do
+              // inline through the SCC the function will end up being
+              // self-recursive which the inliner bails out on, and inlining
+              // within an SCC is necessary for performance.
+              if (CalleeSCC != C &&
+                  CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) {
+                Attribute NewCBCostMult = Attribute::get(
+                    M.getContext(),
+                    InlineConstants::FunctionInlineCostMultiplierAttributeName,
+                    itostr(CBCostMult * IntraSCCCostMultiplier));
+                ICB->addFnAttr(NewCBCostMult);
+              }
+            }
+          }
         }
       }
 
       // Merge the attributes based on the inlining.
       AttributeFuncs::mergeAttributesForInlining(F, Callee);
 
       // For local functions or discardable functions without comdats, check
       // whether this makes the callee trivially dead. In that case, we can drop

llvm/test/Transforms/Inline/inline-cost-attributes.ll

 ; REQUIRES: asserts
 ; RUN: opt -inline-cost-full -passes='cgscc(inline)' -debug-only=inline -disable-output %s 2>&1 | FileCheck --check-prefix=INLINER %s
 ; RUN: opt -inline-cost-full -passes='print<inline-cost>' -disable-output %s 2>&1 | FileCheck --check-prefix=COST %s
 
 declare void @extern() "call-threshold-bonus"="31"
 
 define void @fn1() "function-inline-cost"="321" "function-inline-threshold"="123" "call-inline-cost"="271" {
 entry:
   ret void
 }
 
 define void @fn2() "function-inline-threshold"="41" {
 ; INLINER-LABEL: Inlining calls in: fn2
-; INLINER-NEXT: Function size: 6
+; INLINER-NEXT: Function size: 7
 ; INLINER-NEXT: NOT Inlining (cost=321, threshold=123), Call:   call void @fn1()
+; INLINER-NEXT: NOT Inlining (cost=963, threshold=123), Call:   call void @fn1()
 ; INLINER-NEXT: NOT Inlining (cost=321, threshold=321), Call:   call void @fn1()
 ; INLINER-NEXT: NOT Inlining (cost=197, threshold=123), Call:   call void @fn1()
 ; INLINER-NEXT: Inlining (cost=197, threshold=321), Call:   call void @fn1()
 
 ; COST-LABEL: define void @fn2()
 ; COST-NEXT: entry:
 ; COST-NEXT: threshold delta = 31
 ; COST-NEXT: call void @extern()
 ; COST-NEXT: cost delta = 132, threshold delta = 193
 ; COST-NEXT: call void @fn1()
+; COST-NEXT: cost delta = 132, threshold delta = 193
+; COST-NEXT: call void @fn1()
 ; COST-NEXT: cost delta = 0
 ; COST-NEXT: call void @fn1()
 ; COST-NEXT: cost delta = 271, threshold delta = 17
 ; COST-NEXT: call void @fn1()
 ; COST-NEXT: cost delta = 473
 ; COST-NEXT: call void @fn1()
 
 entry:
   call void @extern()
   call void @fn1() "call-inline-cost"="132" "call-threshold-bonus"="193"
+  call void @fn1() "call-inline-cost"="132" "call-threshold-bonus"="193" "function-inline-cost-multiplier"="3"
   call void @fn1() "call-inline-cost"="0" "function-inline-threshold"="321"
   call void @fn1() "call-threshold-bonus"="17" "function-inline-cost"="197"
   call void @fn1() "call-inline-cost"="473" "function-inline-cost"="197" "function-inline-threshold"="321"
   ret void
 }
 
 define void @fn3() {
 ; INLINER-LABEL: Inlining calls in: fn3
 ; INLINER-NEXT: Function size: 3
 ; INLINER-NEXT: Inlining (cost=386, threshold=849), Call:   call void @fn1()
 ; INLINER-NEXT: Size after inlining: 2
-; INLINER-NEXT: NOT Inlining (cost=403, threshold=41), Call:   call void @fn2()
+; INLINER-NEXT: NOT Inlining (cost=535, threshold=41), Call:   call void @fn2()
 
 entry:
   call void @fn1() "function-inline-cost"="386" "function-inline-threshold"="849"
   call void @fn2()
   ret void
 }

llvm/test/Transforms/Inline/mut-rec-scc-2.ll

+; RUN: opt -S -passes='inline' < %s | FileCheck %s
+
+; Make sure we don't mark calls within the same SCC as original function with noinline.
+; CHECK-NOT: function-inline-cost-multiplier
+
+define void @samescc1() {
+  call void @samescc2()
+  ret void
+}
+
+define void @samescc2() {
+  call void @samescc3()
+  ret void
+}
+
+define void @samescc3() {
+  call void @samescc1()
+  ret void
+}

llvm/test/Transforms/Inline/mut-rec-scc.ll

+; RUN: opt -S -passes='cgscc(inline,instcombine)' < %s | FileCheck %s
+; RUN: opt -S -intra-scc-cost-multiplier=3 -passes='cgscc(inline,instcombine)' < %s | FileCheck %s --check-prefix=THREE
+
+; We use call to a dummy function to avoid inlining test1 into test2 or vice
+; versa, such that we aren't left with a trivial cycle, as trivial cycles are
+; special-cased to never be inlined.
+; However, InstCombine will eliminate these calls after inlining, and thus
+; make the functions eligible for inlining in their callers.
+declare void @dummy() readnone nounwind willreturn
+
+define void @test1() {
+; CHECK-LABEL: define void @test1(
+; CHECK-NEXT:    call void @test2()
+; CHECK-NEXT:    call void @test2()
+; CHECK-NEXT:    ret void
+;
+  call void @test2()
+  call void @test2()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  ret void
+}
+
+define void @test2() {
+; CHECK-LABEL: define void @test2(
+; CHECK-NEXT:    call void @test1()
+; CHECK-NEXT:    call void @test1()
+; CHECK-NEXT:    ret void
+;
+  call void @test1()
+  call void @test1()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  call void @dummy()
+  ret void
+}
+
+; The inlined call sites should have the "function-inline-cost-multiplier" call site attribute.
+; This test is a bit fragile in the exact number of inlining that happens based on thresholds.
+define void @test3() {
+; CHECK-LABEL: define void @test3(
+; CHECK-NEXT:    call void @test2() #[[COSTMULT:[0-9]+]]
+; CHECK-NEXT:    call void @test2() #[[COSTMULT]]
+; CHECK-NEXT:    call void @test2() #[[COSTMULT]]
+; CHECK-NEXT:    call void @test2() #[[COSTMULT]]
+; CHECK-NEXT:    call void @test2() #[[COSTMULT]]
+; CHECK-NEXT:    call void @test2() #[[COSTMULT]]
+; CHECK-NEXT:    call void @test2() #[[COSTMULT]]
+; CHECK-NEXT:    call void @test2() #[[COSTMULT]]
+; CHECK-NEXT:    ret void
+;
+  call void @test2()
+  call void @test2()
+  ret void
+}
+
+; CHECK: [[COSTMULT]] = { "function-inline-cost-multiplier"="4" }
+; THREE: "function-inline-cost-multiplier"="9"