[CSSPGO] Allow inlining recursive call for preinliner

[wenlei]

Summary

When preinliner is used for CSSPGO, we try to honor global preinliner decision as much as we can except for uninlinable callees. We rely on InlineCost::Never to prevent us from illegal inlining.

However, it turns out that we use InlineCost::Never for both illeagle inlining and some of the "not-so-beneficial" inlining.

The most common one is recursive inlining, while it can bloat size a lot during CGSCC bottom-up inlining, it's less of a problem when recursive inlining is guided by profile and done in top-down manner.

Ideally it'd be better to have a clear separation between inline legality check vs cost-benefit check, but that requires a bigger change.

This change enables InlineCost computation to allow inlining recursive calls, controlled by InlineParams. In SampleLoader, we now enable recursive inlining for CSSPGO when global preinliner decision is used.

With this change, we saw a few perf improvements on SPEC2017 with CSSPGO and preinliner on: 2% for povray_r, 6% for xalancbmk_s, 3% omnetpp_s, while size is about the same (no noticeable perf change for all other benchmarks)

[wlei]

Nice to see we can handle recursion inlining. I guess here the recursion inlining is from different call site since we actually do compression to block many "recursion". Now with this, I'm wondering if we can change compression strategy to allow more duplication context, see if we can find a balance between the profile size and duplication.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1295

Should this also be enabled for csspgo without preliner?

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1295

Hmm.. actually this is what it currently does. UsePreInlinerDecision is on by default for CSSPGO. So basically, we have sample-profile-use-preinliner indirectly controls whether we allow recursive inline. Do you think we should have separate switch just for recursive inlining? That probably makes experimenting with AutoFDO a bit easier too.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1295

Oh yeah, UsePreInlinerDecision is on by default for CSSPGO. A separate switch would be more solid like the decision won't be changed when UsePreInlinerDecision is off. It is also handy for experimenting with AutoFDO.

[wenlei]

Address comments.

llvm/lib/Transforms/IPO/SampleProfile.cpp

1295

Ok, done.

[hoy]

lgtm

llvm/lib/Analysis/InlineCost.cpp

939

Nit: move this to the field initializer list? AllowRecursiveCall(Params.AllowRecursiveCall.getValue())

[wenlei]

llvm/lib/Analysis/InlineCost.cpp

939

We can't use initializer list directly because that field is in base class (we need it to be in the base because the uses are from base). The params of base's ctor are high level stuff, so I wasn't sure if it's good to add this as a ctor param, and decided to leave it.

[hoy]

llvm/lib/Analysis/InlineCost.cpp

939

I see, makes sense to leave it as is.

llvm/include/llvm/Analysis/InlineCost.h

struct InlineParams {
   /// Threshold to use when the callsite is considered cold.
   Optional<int> ColdCallSiteThreshold;
 
   /// Compute inline cost even when the cost has exceeded the threshold.
   Optional<bool> ComputeFullInlineCost;
 
   /// Indicate whether we should allow inline deferral.
   Optional<bool> EnableDeferral = true;
+
+  /// Indicate whether we allow inlining for recursive call.
+  Optional<bool> AllowRecursiveCall = false;
 };
 
 /// 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,

llvm/lib/Analysis/InlineCost.cpp

protected:
   /// The mapping of the blocks to their known unique successors due to the
   /// constant arguments.
   DenseMap<BasicBlock *, BasicBlock *> KnownSuccessors;
 
   /// Model the elimination of repeated loads that is expected to happen
   /// whenever we simplify away the stores that would otherwise cause them to be
   /// loads.
   bool EnableLoadElimination;
+
+  /// Whether we allow inlining for recursive call.
+  bool AllowRecursiveCall;
+
   SmallPtrSet<Value *, 16> LoadAddrSet;
 
   AllocaInst *getSROAArgForValueOrNull(Value *V) const {
     auto It = SROAArgValues.find(V);
     if (It == SROAArgValues.end() || EnabledSROAAllocas.count(It->second) == 0)
       return nullptr;
     return It->second;
   }

 public:
   CallAnalyzer(Function &Callee, CallBase &Call, const TargetTransformInfo &TTI,
                function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
                function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
                ProfileSummaryInfo *PSI = nullptr,
                OptimizationRemarkEmitter *ORE = nullptr)
       : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI),
         PSI(PSI), F(Callee), DL(F.getParent()->getDataLayout()), ORE(ORE),
-        CandidateCall(Call), EnableLoadElimination(true) {}
+        CandidateCall(Call), EnableLoadElimination(true),
+        AllowRecursiveCall(false) {}
 
   InlineResult analyze();
 
   Optional<Constant *> getSimplifiedValue(Instruction *I) {
     if (SimplifiedValues.find(I) != SimplifiedValues.end())
       return SimplifiedValues[I];
     return None;
   }
InlineCostCallAnalyzer(
       bool IgnoreThreshold = false)
       : CallAnalyzer(Callee, Call, TTI, GetAssumptionCache, GetBFI, PSI, ORE),
         ComputeFullInlineCost(OptComputeFullInlineCost ||
                               Params.ComputeFullInlineCost || ORE ||
                               isCostBenefitAnalysisEnabled()),
         Params(Params), Threshold(Params.DefaultThreshold),
         BoostIndirectCalls(BoostIndirect), IgnoreThreshold(IgnoreThreshold),
         CostBenefitAnalysisEnabled(isCostBenefitAnalysisEnabled()),
-        Writer(this) {}
+        Writer(this) {
+    AllowRecursiveCall = Params.AllowRecursiveCall.getValue();
+  }
 
   /// Annotation Writer for instruction details
   InlineCostAnnotationWriter Writer;
 
   void dump();
 
   // Prints the same analysis as dump(), but its definition is not dependent
   // on the build.
case Intrinsic::strip_invariant_group:
       return true;
     }
   }
 
   if (F == Call.getFunction()) {
     // This flag will fully abort the analysis, so don't bother with anything
     // else.
     IsRecursiveCall = true;
+    if (!AllowRecursiveCall)
       return false;
   }
 
   if (TTI.isLoweredToCall(F)) {
     onLoweredCall(F, Call, IsIndirectCall);
   }
 
   if (!(Call.onlyReadsMemory() || (IsIndirectCall && F->onlyReadsMemory())))
     disableLoadElimination();
if (Base::visit(&I))
       ++NumInstructionsSimplified;
     else
       onMissedSimplification();
 
     onInstructionAnalysisFinish(&I);
     using namespace ore;
     // If the visit this instruction detected an uninlinable pattern, abort.
     InlineResult IR = InlineResult::success();
-    if (IsRecursiveCall)
+    if (IsRecursiveCall && !AllowRecursiveCall)
       IR = InlineResult::failure("recursive");
     else if (ExposesReturnsTwice)
       IR = InlineResult::failure("exposes returns twice");
     else if (HasDynamicAlloca)
       IR = InlineResult::failure("dynamic alloca");
     else if (HasIndirectBr)
       IR = InlineResult::failure("indirect branch");
     else if (HasUninlineableIntrinsic)

llvm/lib/Transforms/IPO/SampleProfile.cpp

static cl::opt<bool> CallsitePrioritizedInline(
     cl::desc("Use call site prioritized inlining for sample profile loader."
              "Currently only CSSPGO is supported."));
 
 static cl::opt<bool> UsePreInlinerDecision(
     "sample-profile-use-preinliner", cl::Hidden, cl::ZeroOrMore,
     cl::init(false),
     cl::desc("Use the preinliner decisions stored in profile context."));
 
+static cl::opt<bool> AllowRecursiveInline(
+    "sample-profile-recursive-inline", cl::Hidden, cl::ZeroOrMore,
+    cl::init(false),
+    cl::desc("Allow sample loader inliner to inline recursive calls."));
+
 static cl::opt<std::string> ProfileInlineReplayFile(
     "sample-profile-inline-replay", cl::init(""), cl::value_desc("filename"),
     cl::desc(
         "Optimization remarks file containing inline remarks to be replayed "
         "by inlining from sample profile loader."),
     cl::Hidden);
 
 static cl::opt<unsigned>
if (CallsitePrioritizedInline) {
     else if (!ProfileSizeInline)
       return InlineCost::getNever("cold callsite");
   }
 
   Function *Callee = Candidate.CallInstr->getCalledFunction();
   assert(Callee && "Expect a definition for inline candidate of direct call");
 
   InlineParams Params = getInlineParams();
+  // We will ignore the threshold from inline cost, so always get full cost.
   Params.ComputeFullInlineCost = true;
+  Params.AllowRecursiveCall = AllowRecursiveInline;
   // Checks if there is anything in the reachable portion of the callee at
   // this callsite that makes this inlining potentially illegal. Need to
   // set ComputeFullInlineCost, otherwise getInlineCost may return early
   // when cost exceeds threshold without checking all IRs in the callee.
   // The acutal cost does not matter because we only checks isNever() to
   // see if it is legal to inline the callsite.
   InlineCost Cost = getInlineCost(*Candidate.CallInstr, Callee, Params,
                                   GetTTI(*Callee), GetAC, GetTLI);
 
   // Honor always inline and never inline from call analyzer
if (!ProfileSizeInline.getNumOccurrences())
       ProfileSizeInline = true;
     if (!CallsitePrioritizedInline.getNumOccurrences())
       CallsitePrioritizedInline = true;
 
     // For CSSPGO, use preinliner decision by default when available.
     if (!UsePreInlinerDecision.getNumOccurrences())
       UsePreInlinerDecision = true;
 
+    // For CSSPGO, we also allow recursive inline to best use context profile.
+    if (!AllowRecursiveInline.getNumOccurrences())
+      AllowRecursiveInline = true;
+
     // Enable iterative-BFI by default for CSSPGO.
     if (!UseIterativeBFIInference.getNumOccurrences())
       UseIterativeBFIInference = true;
 
     // Tracker for profiles under different context
     ContextTracker = std::make_unique<SampleContextTracker>(
         Reader->getProfiles(), &GUIDToFuncNameMap);
   }