[ModuleInliner] Add a cost-benefit-based priority

[kazu]

Summary

This patch teaches the module inliner a traversal order designed for
the instrumentation FDO (+ThinLTO) scenario.

The new traversal order prioritizes call sites in the following order:

1. Those call sites that are expected to reduce the caller size

2. Those call sites that have gone through the cost-benefit analaysis

3. The remaining call sites

With this fairly simple traversal order, a large internel benchmark
yields performance comparable to the bottom-up inliner -- both in
terms of the execution performance and .text* sizes.

Big thanks goes to Liqiang Tao for the module inliner infrastructure.

I still have hacks outside this patch to prevent excessively long
compilation or .text* size explosion. I'm trying to come up with
acceptable solutions in near future.

[kazu]

Use getStaticBonusApplied.

[kazu]

Please take a look. Thanks!

[wenlei]

a large internel benchmark yields performance comparable to the bottom-up inliner -- both in terms of the execution performance and .text* sizes.

This looks promising. The comparison is between enable-module-inliner on vs off, right? Do you plan to tune and open up module inliner for sample PGO and non-PGO cases where cost-benefit analysis isn't available yet?

llvm/lib/Analysis/InlineOrder.cpp

34

perhaps just name it "cost-benefit"? "ratio" can be confusing.

[kazu]

In D134376#3818545, @wenlei wrote:

a large internel benchmark yields performance comparable to the bottom-up inliner -- both in terms of the execution performance and .text* sizes.

This looks promising. The comparison is between enable-module-inliner on vs off, right?

Thanks. Yes, -mllvm -enable-module-inliner is the only difference. Both the baseline and the experiment use FDO, ThinLTO, and -fsplit-machine-functions.

One thing I might point out here is that I am not doing any cleanup beyond whatever basic cleanups InlineFunction performs. With the bottom-up inliner, we diligently clean up after each SCC (see PassBuilder::addPGOInstrPasses), but that doesn't seem to matter with the module inliner. My hypothesis is that once we inline those call sites that reduce the caller size, followed by ones with high benefit-to-cost ratios, then we've captured the vast majority of the benefit from inlining. That is, we don't really need the exact "tightest" instruction count after DCE, CSE, etc. Even if the module inliner didn't give us additional performance, it could still simplify our life -- no CGSCC maintenance or successive cleanups.

Do you plan to tune and open up module inliner for sample PGO and non-PGO cases where cost-benefit analysis isn't available yet?

Yes, I'd like to do something for the sample PGO case. I'd like to enable the cost-benefit analysis for the sample PGO, but that's been my hardest project. IIUC, the sample profile loader keeps inlining functions top down until the weight of the inlining subtree goes below the threshold. As a result, by the time we get to the profile-driven inliner (Inliner.cpp), we don't have a lot of interesting decisions left to make. For the sample PGO case, I think I have to depart from the top-down inlining and start inlining callees from where it matters according to some combinations of context sensitivity, profile counts, and the usual metrics from trial inlining (InlineCost.cpp), etc.

The non-PGO case isn't our primary interest. That said, if I come up with reasonable heuristics, I might contribute that. There may be a long-term benefit in steering the community toward the module inliner as the sole inliner as opposed to directing them to the two different inliners (Inliner.cpp and ModuleInliner.cpp) depending on whether they are using instrumentation FDO or not.

[taolq]

LGTM.
Thanks for this work. It's glad to see this infrastructure works well.
Looking forward to discovering reasonable heuristics :-D
Don't forget to resolve the comment.

[kazu]

Renamed OptRatio to CostBenefit.

Renamed optratio to cost-benefit.

[kazu]

In D134376#3822942, @taolq wrote:

LGTM.
Thanks for this work. It's glad to see this infrastructure works well.
Looking forward to discovering reasonable heuristics :-D

Thank you for the review! We just started the module inliner journey. I'm also looking forward to improving both the priority and threshold functions.

llvm/lib/Analysis/InlineOrder.cpp

 enum class InlinePriorityMode : int { Size, Cost, OptRatio };
 
 static cl::opt<InlinePriorityMode> UseInlinePriority(
     "inline-priority-mode", cl::init(InlinePriorityMode::Size), cl::Hidden,
     cl::desc("Choose the priority mode to use in module inline"),
     cl::values(clEnumValN(InlinePriorityMode::Size, "size",
                           "Use callee size priority."),
                clEnumValN(InlinePriorityMode::Cost, "cost",
-                          "Use inline cost priority.")));
+                          "Use inline cost priority."),
+               clEnumValN(InlinePriorityMode::OptRatio, "optratio",
+                          "Use cost-benefit ratio.")));
+
+static cl::opt<int> ModuleInlinerTopPriorityThreshold(
+    "moudle-inliner-top-priority-threshold", cl::Hidden, cl::init(0),
+    cl::desc("The cost threshold for call sites that get inlined without the "
+             "cost-benefit analysis"));
 
 namespace {
 
 llvm::InlineCost getInlineCostWrapper(CallBase &CB,
                                       FunctionAnalysisManager &FAM,
                                       const InlineParams &Params) {
   Function &Caller = *CB.getCaller();
   ProfileSummaryInfo *PSI =
public:
   static bool isMoreDesirable(const CostPriority &P1, const CostPriority &P2) {
     return P1.Cost < P2.Cost;
   }
 
 private:
   int Cost;
 };
 
+class CostBenefitPriority {
+public:
+  CostBenefitPriority() = default;
+  CostBenefitPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
+                      const InlineParams &Params) {
+    auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
+    Cost = IC.getCost();
+    StaticBonusApplied = IC.getStaticBonusApplied();
+    CostBenefit = IC.getCostBenefit();
+  }
+
+  static bool isMoreDesirable(const CostBenefitPriority &P1,
+                              const CostBenefitPriority &P2) {
+    // We prioritize call sites in the dictionary order of the following
+    // priorities:
+    //
+    // 1. Those call sites that are expected to reduce the caller size when
+    //    inlined.  Within them, we prioritize those call sites with bigger
+    //    reduction.
+    //
+    // 2. Those call sites that have gone through the cost-benefit analysis.
+    //    Currently, they are limited to hot call sites.  Within them, we
+    //    prioritize those call sites with higher benefit-to-cost ratios.
+    //
+    // 3. Remaining call sites are prioritized according to their costs.
+
+    // We add back StaticBonusApplied to determine whether we expect the caller
+    // to shrink (even if we don't delete the callee).
+    bool P1ReducesCallerSize =
+        P1.Cost + P1.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
+    bool P2ReducesCallerSize =
+        P2.Cost + P2.StaticBonusApplied < ModuleInlinerTopPriorityThreshold;
+    if (P1ReducesCallerSize || P2ReducesCallerSize) {
+      // If one reduces the caller size while the other doesn't, then return
+      // true iff P1 reduces the caller size.
+      if (P1ReducesCallerSize != P2ReducesCallerSize)
+        return P1ReducesCallerSize;
+
+      // If they both reduce the caller size, pick the one with the smaller
+      // cost.
+      return P1.Cost < P2.Cost;
+    }
+
+    bool P1HasCB = P1.CostBenefit.has_value();
+    bool P2HasCB = P2.CostBenefit.has_value();
+    if (P1HasCB || P2HasCB) {
+      // If one has undergone the cost-benefit analysis while the other hasn't,
+      // then return true iff P1 has.
+      if (P1HasCB != P2HasCB)
+        return P1HasCB;
+
+      // If they have undergone the cost-benefit analysis, then pick the one
+      // with a higher benefit-to-cost ratio.
+      APInt LHS = P1.CostBenefit->getBenefit() * P2.CostBenefit->getCost();
+      APInt RHS = P2.CostBenefit->getBenefit() * P1.CostBenefit->getCost();
+      return LHS.ugt(RHS);
+    }
+
+    // Remaining call sites are ordered according to their costs.
+    return P1.Cost < P2.Cost;
+  }
+
+private:
+  int Cost;
+  int StaticBonusApplied;
+  Optional<CostBenefitPair> CostBenefit;
+};
+
 template <typename PriorityT>
 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
   using T = std::pair<CallBase *, int>;
 
   bool hasLowerPriority(const CallBase *L, const CallBase *R) const {
     const auto I1 = Priorities.find(L);
     const auto I2 = Priorities.find(R);
     assert(I1 != Priorities.end() && I2 != Priorities.end());
llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params) {
   case InlinePriorityMode::Size:
     LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
     return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
 
   case InlinePriorityMode::Cost:
     LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
     return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
 
-  default:
-    llvm_unreachable("Unsupported Inline Priority Mode");
-    break;
+  case InlinePriorityMode::OptRatio:
+    LLVM_DEBUG(
+        dbgs() << "    Current used priority: cost-benefit priority ---- \n");
+    return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM, Params);
   }
   return nullptr;
 }