[CSSPGO] Allow inlining recursive call for preinliner

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

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;
+  // If preinline decision is used we want to allow inline recursive call.
+  // TODO: Evaluate if this is helpful for AutoFDO too in general.
+  Params.AllowRecursiveCall = ProfileIsCS && UsePreInlinerDecision;
   // 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);