[llvm][Inliner] Templatize PriorityInlineOrder

[taolq]

Summary

The patch templatize PriorityInlinerOrder so that it can accept any type priority metric.

[kazu]

llvm/lib/Transforms/IPO/Inliner.cpp

873–877

How about packaging the type int, isMoraDesirable, and evaluate into one class?

class Priority {
public:
  static bool isMoreDesirable(const Priority &S1, const Priority &S2) {
    return S1.size < S2.size;
  }
  static Priority evaluate(CallBase *CB) {
    ...
  }
  int size;
};

This way, we don't have to pass individual components to PriorityInlineOrder.

Once you do this, you should be able to your original definition of cmp more or less restore like so:

static bool cmp(const T &P1, const T &P2) {
  return Priority::isMoreDesirable(P2.second, P1.second);
}

[taolq]

This comment was removed by taolq.

[taolq]

• pack one class Priority

[taolq]

• renaming

[taolq]

• renaming size -> Size

[kazu]

Thank you for revising the patch!

llvm/lib/Transforms/IPO/Inliner.cpp

Calls.erase(std::remove_if(Calls.begin() + FirstIndex, Calls.end(), Pred),
                 Calls.end());
   }
 
 private:
   Container Calls;
   size_t FirstIndex = 0;
 };
 
+class Priority {
+public:
+  Priority(int Size) : Size(Size) {}
+
+  static bool isMoreDesirable(const Priority &S1, const Priority &S2) {
+    return S1.Size < S2.Size;
+  }
+
+  static Priority evaluate(CallBase *CB) {
+    Function *Callee = CB->getCalledFunction();
+    return Priority(Callee->getInstructionCount());
+  }
+
+  int Size;
+};
+
+template <typename PriorityT>
 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
   using T = std::pair<CallBase *, int>;
+  using HeapT = std::pair<CallBase *, PriorityT>;
   using reference = T &;
   using const_reference = const T &;
 
-  // Return true if S1 is more desirable than S2.
-  static bool isMoreDesirable(int S1, int S2) { return S1 < S2; }
-
-  static bool cmp(const T &P1, const T &P2) {
-    return isMoreDesirable(P2.second, P1.second);
-  }
-
-  int evaluate(CallBase *CB) {
-    Function *Callee = CB->getCalledFunction();
-    return (int)Callee->getInstructionCount();
+  static bool cmp(const HeapT &P1, const HeapT &P2) {
+    return PriorityT::isMoreDesirable(P2.second, P1.second);
   }
 
   // A call site could become less desirable for inlining because of the size
   // growth from prior inlining into the callee. This method is used to lazily
   // update the desirability of a call site if it's decreasing. It is only
   // called on pop() or front(), not every time the desirability changes. When
   // the desirability of the front call site decreases, an updated one would be
   // pushed right back into the heap. For simplicity, those cases where
   // the desirability of a call site increases are ignored here.
   void adjust() {
     bool Changed = false;
     do {
       CallBase *CB = Heap.front().first;
-      const int PreviousGoodness = Heap.front().second;
-      const int CurrentGoodness = evaluate(CB);
-      Changed = isMoreDesirable(PreviousGoodness, CurrentGoodness);
+      const PriorityT PreviousGoodness = Heap.front().second;
+      const PriorityT CurrentGoodness = PriorityT::evaluate(CB);
+      Changed = PriorityT::isMoreDesirable(PreviousGoodness, CurrentGoodness);
       if (Changed) {
         std::pop_heap(Heap.begin(), Heap.end(), cmp);
         Heap.pop_back();
         Heap.push_back({CB, CurrentGoodness});
         std::push_heap(Heap.begin(), Heap.end(), cmp);
       }
     } while (Changed);
   }
 
 public:
   size_t size() override { return Heap.size(); }
 
   void push(const T &Elt) override {
     CallBase *CB = Elt.first;
     const int InlineHistoryID = Elt.second;
-    const int Goodness = evaluate(CB);
+    const PriorityT Goodness = PriorityT::evaluate(CB);
 
     Heap.push_back({CB, Goodness});
     std::push_heap(Heap.begin(), Heap.end(), cmp);
     InlineHistoryMap[CB] = InlineHistoryID;
   }
 
   T pop() override {
     assert(size() > 0);
const_reference front() override {
     assert(size() > 0);
     adjust();
 
     CallBase *CB = Heap.front().first;
     return *InlineHistoryMap.find(CB);
   }
 
   void erase_if(function_ref<bool(T)> Pred) override {
-    Heap.erase(std::remove_if(Heap.begin(), Heap.end(), Pred), Heap.end());
+    auto PredWrapper = [=](HeapT P) -> bool {
+      return Pred(std::make_pair(P.first, 0));
+    };
+    Heap.erase(std::remove_if(Heap.begin(), Heap.end(), PredWrapper),
+               Heap.end());
     std::make_heap(Heap.begin(), Heap.end(), cmp);
   }
 
 private:
-  SmallVector<T, 16> Heap;
+  SmallVector<HeapT, 16> Heap;
   DenseMap<CallBase *, int> InlineHistoryMap;
 };
 
 PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
                                    CGSCCAnalysisManager &AM, LazyCallGraph &CG,
                                    CGSCCUpdateResult &UR) {
   const auto &MAMProxy =
       AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG);
PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
   // To compensate for this, we don't process transitive edges made immediate
   // by inlining until we've done one pass of inlining across the entire SCC.
   // Large, highly connected SCCs still lead to some amount of code bloat in
   // this model, but it is uniformly spread across all the functions in the SCC
   // and eventually they all become too large to inline, rather than
   // incrementally maknig a single function grow in a super linear fashion.
   std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> Calls;
   if (InlineEnablePriorityOrder)
-    Calls = std::make_unique<PriorityInlineOrder>();
+    Calls = std::make_unique<PriorityInlineOrder<Priority>>();
   else
     Calls = std::make_unique<DefaultInlineOrder<std::pair<CallBase *, int>>>();
   assert(Calls != nullptr && "Expected an initialized InlineOrder");
 
   // Populate the initial list of calls in this SCC.
   for (auto &N : InitialC) {
     auto &ORE =
         FAM.getResult<OptimizationRemarkEmitterAnalysis>(N.getFunction());
     // We want to generally process call sites top-down in order for
     // simplifications stemming from replacing the call with the returned value
     // after inlining to be visible to subsequent inlining decisions.
     // FIXME: Using instructions sequence is a really bad way to do this.
     // Instead we should do an actual RPO walk of the function body.
     for (Instruction &I : instructions(N.getFunction()))