[llvm][Inliner] Make PriorityInlineOrder lazily updated

[taolq]

Summary

This patch makes PriorityInlineOrder lazily updated.
The PriorityInlineOrder would lazily update the desirability of a call site if it's decreasing.

[kazu]

llvm/lib/Transforms/IPO/Inliner.cpp

732–737

Could we split this function into two like so?

// 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); }

The reason I am suggesting this is that the current implementation of cmp encapsulates two things -- the order of arguments dictated by std::make_heap and our logic about which one is more desirable.

By hiding > inside isMoreDesirable, the reader doesn't have to worry about whether this metric is "the higher the better" or "the lower the better".

See below for an additional use of isMoreDesirable.

749

For simplicity

757

I'd say:

Changed = isMoreDesirable(PreviousGoodness, CurrentGoodness);

This way, we don't express the comparison operator < at multiple places, making it easier to try other cost metrics.

856

Do you really mean to put ! here?

[taolq]

llvm/lib/Transforms/IPO/Inliner.cpp

856

Oh, I forgot to remove the hard code for testing.

[ChuanqiXu]

How do you think about:

T pop() {
    if (!initialized) {
        make_heap ...
        initialized = true;
    }
}
// same as front

It seems simple and cheaper.

Another option is:

SmallVector<CallBase*> CallSites;
// Fill CallSites
if (InlineEnablePriorityOrder)
    Calls = std::make_unique<PriorityInlineOrder>(CallSites); // Do make heap here
else
    Calls = std::make_unique<InlinerOrder>(CallSites);

It looks good too.

[taolq]

llvm/lib/Transforms/IPO/Inliner.cpp

732–737

This refactoring is sexy. I love it! Thanks a lot.

[taolq]

• refactor cmp in PriorityInlineOrder
• remove the hard code for testing

[taolq]

In D104654#2832141, @ChuanqiXu wrote:

How do you think about:

T pop() {
    if (!initialized) {
        make_heap ...
        initialized = true;
    }
}
// same as front

It seems simple and cheaper.

I think this if branch is not necessary. Because whenever pop() is called, the heap inside is maintained.
So there is not necessary to do that.

Another option is:

SmallVector<CallBase*> CallSites;
// Fill CallSites
if (InlineEnablePriorityOrder)
    Calls = std::make_unique<PriorityInlineOrder>(CallSites); // Do make heap here
else
    Calls = std::make_unique<InlinerOrder>(CallSites);

It looks good too.

Since this class is only used here, we could keep it minimal, no need to consider the generality.
Even without this construct methrod, it could work.

(Maybe I made some misunderstanding. The lazily update is for the priority of the call site which is pushed in heap,
not for the heap. The heap is already well maintained.

[kazu]

LGTM with a typo fix.

llvm/lib/Transforms/IPO/Inliner.cpp

745

callee

[ChuanqiXu]

In D104654#2832191, @taolq wrote:

In D104654#2832141, @ChuanqiXu wrote:

How do you think about:

T pop() {
    if (!initialized) {
        make_heap ...
        initialized = true;
    }
}
// same as front

It seems simple and cheaper.

I think this if branch is not necessary. Because whenever pop() is called, the heap inside is maintained.
So there is not necessary to do that.

Another option is:

SmallVector<CallBase*> CallSites;
// Fill CallSites
if (InlineEnablePriorityOrder)
    Calls = std::make_unique<PriorityInlineOrder>(CallSites); // Do make heap here
else
    Calls = std::make_unique<InlinerOrder>(CallSites);

It looks good too.

Since this class is only used here, we could keep it minimal, no need to consider the generality.
Even without this construct methrod, it could work.

(Maybe I made some misunderstanding. The lazily update is for the priority of the call site which is pushed in heap,
not for the heap. The heap is already well maintained.

Sorry for misunderstanding. The implementation looks good.

[taolq]

• fix typo

llvm/lib/Transforms/IPO/Inliner.cpp

private:
   size_t FirstIndex = 0;
 };
 
 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
   using T = std::pair<CallBase *, int>;
   using reference = T &;
   using const_reference = const T &;
 
-  static bool cmp(const T &P1, const T &P2) { return P1.second > P2.second; }
+  // 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();
   }
 
+  // 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);
+      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);
 
     Heap.push_back({CB, Goodness});
     std::push_heap(Heap.begin(), Heap.end(), cmp);
     InlineHistoryMap[CB] = InlineHistoryID;
   }
 
   T pop() override {
     assert(size() > 0);
+    adjust();
+
     CallBase *CB = Heap.front().first;
     T Result = std::make_pair(CB, InlineHistoryMap[CB]);
     InlineHistoryMap.erase(CB);
     std::pop_heap(Heap.begin(), Heap.end(), cmp);
     Heap.pop_back();
     return Result;
   }
 
   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());
     std::make_heap(Heap.begin(), Heap.end(), cmp);
   }
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>();
   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 =