[llvm][Inliner] Add an optional PriorityInlineOrder

[taolq]

Summary

This patch adds an optional PriorityInlineOrder, which uses the heap to order inlining.
The callsite which size is smaller would have a higher priority.

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

707

you can also delay pop-ing. Or, better, have pop return T, and front return reference and be a const function (i.e. a peek - you need it I think in the for loop, line 899).

824

add a flag to this file to control which InlineOrder you use.

[taolq]

• Add inline order option
• modify pop() & front() API

[mtrofin]

With the introduction of the flag, there shouldn't be any more failing tests, right?

llvm/lib/Transforms/IPO/Inliner.cpp

104

nit: drop the second inline, simpler:

InlineEnablePriorityOrder
inline-enable-priority-order

824

nit: when the flag is enabled, you end up allocating an object just to drop it right after. You can just allocate the appropriate one on each branch of the if statement. Then, if you want, just assert after the if that CallsPtr is not null - this will help maintaining this later, when there are more than 2 ordering implementations, and it makes the design crystal-clear.

[kazu]

llvm/lib/Transforms/IPO/Inliner.cpp

824

nit: I would just leave the name as is -- "Calls". "CallsPtr" is a bit mouthful although I understand what you mean here.

[taolq]

In D104028#2817188, @mtrofin wrote:

With the introduction of the flag, there shouldn't be any more failing tests, right?

Yes, all tests pass.

[mtrofin]

In D104028#2818310, @taolq wrote:

In D104028#2817188, @mtrofin wrote:

With the introduction of the flag, there shouldn't be any more failing tests, right?

Yes, all tests pass.

Worth changing the summary (and also the git commit - the latter gets copied to the former only the first time you arc diff )

[taolq]

• renaming option and Calls
• allocate Calls once on the branch statement

[ChuanqiXu]

I am tuning the performance by reordering inlining in downstream. My first try was to use std::priority_queue. But I tried to use the inline cost heuristic to order them. In this patch it looks like sort callsites by HistoryID? What's the intention?
BTW, for the performance side, SPEC2017 shows some regression with some improvement if we use std::priority_queue by InlineCost. It may be irrelevant to this patch.

PS2: Did you consider to move InlineOrder(s) class out of Inlined.cpp into the header and make it as a member of InlinedPass just like the Advisor? I guess it may be more easier to use them.

llvm/lib/Transforms/IPO/Inliner.cpp

763–774

I prefer to use std::vector<T> as data member instead of PriorityQueue. After that, the implementation may be simpler. For example:

swap all the required element to the end of the vector
std::make_heap(...)

And the implementation for pop and push wouldn't be much harder.

[taolq]

In D104028#2818736, @ChuanqiXu wrote:

I am tuning the performance by reordering inlining in downstream. My first try was to use std::priority_queue. But I tried to use the inline cost heuristic to order them. In this patch it looks like sort callsites by HistoryID? What's the intention?

Thanks for your comments. In this patch, callsites are sorted by callee size (see PriorityInlindeOrder::evaluate())

BTW, for the performance side, SPEC2017 shows some regression with some improvement if we use std::priority_queue by InlineCost. It may be irrelevant to this patch.

That sounds great! I would like to use more elaborate priority functions in the future, e.g. consider both inline costs, callee size, and other profile.

PS2: Did you consider to move InlineOrder(s) class out of Inlined.cpp into the header and make it as a member of InlinedPass just like the Advisor? I guess it may be more easier to use them.

It is defined in Inliner.cpp, because it is an abstraction meant for the inliner.

[ChuanqiXu]

In D104028#2818832, @taolq wrote:

Thanks for your comments. In this patch, callsites are sorted by callee size (see PriorityInlindeOrder::evaluate())

Sorry, I missed that.

That sounds great! I would like to use more elaborate priority functions in the future, e.g. consider both inline costs, callee size, and other profile.

The main point is the regression. Calculate the inline cost for every callsite is costful. In other words, it grows the compile-time without significant improvements. (We could discuss this in other threads further, it may be irrelevant)

It is defined in Inliner.cpp, because it is an abstraction meant for the inliner.

I am fine to remain it in Inliner.cpp. But the reason may be a little weird for me since there many components of inlining didn't be put in inliner.cpp.

[ChuanqiXu]

llvm/lib/Transforms/IPO/Inliner.cpp

902–904

It may be better to:

CallBase *CB = Calls->front().first;
const int InlineHistoryID = Calls->front().second;

Since we would call pop() immediately, the reference P would be invalid. It may be possible that programmers may refer P after Calls->pop(), which is a disaster. Another option is to replace auto &P = with auto P =.

[yurai007]

llvm/lib/Transforms/IPO/Inliner.cpp

722

nit: use 'final' to unlock devirtualization opportunity for overridden members.

828

nit: std::make_unique?

[taolq]

• replace implementation of PriorityInlineOrder from PriorityQueue to SmallVector

[ChuanqiXu]

llvm/lib/Transforms/IPO/Inliner.cpp

19

Now it is not necessary.

800–823

Since we add new order strategy, we need edit the comment too.

[taolq]

• remove useless header file
• add tests for PriorityInlineOrder

[kazu]

In D104028#2818736, @ChuanqiXu wrote:

I am tuning the performance by reordering inlining in downstream. My first try was to use std::priority_queue. But I tried to use the inline cost heuristic to order them. In this patch it looks like sort callsites by HistoryID? What's the intention?

The intention here is to make it easy to try out different priority functions -- callee size, dynamic call count, impacts on callers, etc.

In D104028#2818867, @ChuanqiXu wrote:

The main point is the regression. Calculate the inline cost for every callsite is costful. In other words, it grows the compile-time without significant improvements. (We could discuss this in other threads further, it may be irrelevant)

The compilation time is not a main concern while we are gathering insights.

[mtrofin]

llvm/test/Transforms/Inline/inline_call.ll

3 ↗

(On Diff #352448)

in this and the other test files, is there something different in the output from line 2 and line 3, so that you can add a check that enable-priority-order actually does something different?

[ChuanqiXu]

In D104028#2822410, @kazu wrote:

In D104028#2818736, @ChuanqiXu wrote:

I am tuning the performance by reordering inlining in downstream. My first try was to use std::priority_queue. But I tried to use the inline cost heuristic to order them. In this patch it looks like sort callsites by HistoryID? What's the intention?

The intention here is to make it easy to try out different priority functions -- callee size, dynamic call count, impacts on callers, etc.

In D104028#2818867, @ChuanqiXu wrote:

The main point is the regression. Calculate the inline cost for every callsite is costful. In other words, it grows the compile-time without significant improvements. (We could discuss this in other threads further, it may be irrelevant)

The compilation time is not a main concern while we are gathering insights.

Yeah, I understood it. I comment this just because I find that someone are doing something similar with me so that I want to share something.

BTW: It'd better to add a tag before the title, like '[Inline]' or '[Inliner]'.

[taolq]

• Add a test

[kazu]

llvm/lib/Transforms/IPO/Inliner.cpp

802

smaller

[taolq]

• fix typo

[mtrofin]

llvm/test/Transforms/Inline/monster_scc.ll

73 ↗

(On Diff #352880)

These look like the old cases, though - is there a difference that the priority-based ordering introduces? (maybe I'm missing it)

132 ↗

(On Diff #352880)

same comment - what's the difference?

[taolq]

llvm/test/Transforms/Inline/monster_scc.ll

73 ↗

(On Diff #352880)

Actually, they are different. Each one, (old inline pass, new inline pass, PriorityInlineOrder) makes a different function body after inlining.
The inlined function name is hard to distinguish. You could also focus on the number of called functions.
e.g. with PriorityInlineOrder, this function has 7 call after inlining, more than the previous two cases.

132 ↗

(On Diff #352880)

After inlining, the called functions are different.
These check the sequence of call statements.

[mtrofin]

lgtm

[fhahn]

It looks like this change may cause the following failure on GreenDragon. It would be great if you could take a look.

ommand Output (stderr):
--
+ : 'RUN: at line 42'
+ /Users/buildslave/jenkins/workspace/clang-stage1-RA/clang-build/bin/opt -S -inline -inline-threshold=150 -enable-new-pm=0
+ /Users/buildslave/jenkins/workspace/clang-stage1-RA/clang-build/bin/FileCheck /Users/buildslave/jenkins/workspace/clang-stage1-RA/llvm-project/llvm/test/Transforms/Inline/monster_scc.ll --check-prefixes=CHECK,OLD
+ : 'RUN: at line 43'
+ /Users/buildslave/jenkins/workspace/clang-stage1-RA/clang-build/bin/opt -S -passes=inline -inline-threshold=150
+ /Users/buildslave/jenkins/workspace/clang-stage1-RA/clang-build/bin/FileCheck /Users/buildslave/jenkins/workspace/clang-stage1-RA/llvm-project/llvm/test/Transforms/Inline/monster_scc.ll --check-prefixes=CHECK,NEW
+ : 'RUN: at line 44'
+ /Users/buildslave/jenkins/workspace/clang-stage1-RA/clang-build/bin/opt -S -passes=inline -inline-threshold=150 -inline-enable-priority-order=true
+ /Users/buildslave/jenkins/workspace/clang-stage1-RA/clang-build/bin/FileCheck /Users/buildslave/jenkins/workspace/clang-stage1-RA/llvm-project/llvm/test/Transforms/Inline/monster_scc.ll --check-prefixes=CHECK,PO
/Users/buildslave/jenkins/workspace/clang-stage1-RA/llvm-project/llvm/test/Transforms/Inline/monster_scc.ll:76:7: error: PO: expected string not found in input
; PO: call void @_Z1fILb1ELi2EEvPbS0_(
      ^
<stdin>:19:34: note: scanning from here
 call void @_Z1fILb1ELi1EEvPbS0_(i8* %add.ptr2, i8* %E)
                                 ^
<stdin>:23:2: note: possible intended match here
 call void @_Z1fILb0ELi1EEvPbS0_(i8* %add.ptr2, i8* %E)
 ^
/Users/buildslave/jenkins/workspace/clang-stage1-RA/llvm-project/llvm/test/Transforms/Inline/monster_scc.ll:137:7: error: PO: expected string not found in input
; PO: call void @_Z1fILb0ELi1EEvPbS0_(
      ^
<stdin>:43:34: note: scanning from here
 call void @_Z1fILb1ELi1EEvPbS0_(i8* %add.ptr2, i8* %E)
                                 ^
<stdin>:72:2: note: possible intended match here
 call void @_Z1fILb0ELi3EEvPbS0_(i8* %add.ptr2.i9, i8* %E)
 ^

https://green.lab.llvm.org/green/job/clang-stage1-RA/21735/consoleFull#2293633728254eaf0-7326-4999-85b0-388101f2d404

[thakis]

Looks like this breaks tests on mac: http://45.33.8.238/macm1/11921/step_11.txt

Please take a look and revert for now if it takes a while to fix.

[taolq]

• remove test monster_scc.ll which has a different output in macOS

[fhahn]

In D104028#2828545, @taolq wrote:

• remove test monster_scc.ll which has a different output in macOS

Could you elaborate *why* it has a different output? Not sure if removing the test because it fails on macOS is the best way forward. It would be good to understand *why* there's a difference first.

[taolq]

In D104028#2829050, @fhahn wrote:

In D104028#2828545, @taolq wrote:

• remove test monster_scc.ll which has a different output in macOS

Could you elaborate *why* it has a different output? Not sure if removing the test because it fails on macOS is the best way forward. It would be good to understand *why* there's a difference first.

I don't know the reason yet. I will figure it out.

llvm/lib/Transforms/IPO/Inliner.cpp

 // are profitable to inline are implemented elsewhere.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/PriorityQueue.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AssumptionCache.h"

 static cl::opt<std::string> CGSCCInlineReplayFile(
     "cgscc-inline-replay", cl::init(""), cl::value_desc("filename"),
     cl::desc(
         "Optimization remarks file containing inline remarks to be replayed "
         "by inlining from cgscc inline remarks."),
     cl::Hidden);
 
 LegacyInlinerBase::LegacyInlinerBase(char &ID) : CallGraphSCCPass(ID) {}
 
 LegacyInlinerBase::LegacyInlinerBase(char &ID, bool InsertLifetime)
     : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {}
 
 /// For this class, we declare that we require and preserve the call graph.
 /// If the derived class implements this method, it should
 /// always explicitly call the implementation here.
 void LegacyInlinerBase::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<AssumptionCacheTracker>();
public:
   virtual ~InlineOrder() {}
 
   virtual size_t size() = 0;
 
   virtual void push(const T &Elt) = 0;
 
   virtual void pop() = 0;
 
-  virtual reference front() = 0;
+  virtual T front() = 0;
 
   virtual void erase_if(function_ref<bool(T)> Pred) = 0;
 
   bool empty() { return !size(); }
 };
 
 template <typename T, typename Container = SmallVector<T, 16>>
 class DefaultInlineOrder : public InlineOrder<T> {
   using reference = T &;
 
 public:
   size_t size() override { return Calls.size() - FirstIndex; }
 
   void push(const T &Elt) override { Calls.push_back(Elt); }
 
   void pop() override {
     assert(size() > 0);
     FirstIndex++;
   }
 
-  reference front() override {
+  T front() override {
     assert(size() > 0);
     return Calls[FirstIndex];
   }
 
   void erase_if(function_ref<bool(T)> Pred) override {
     Calls.erase(std::remove_if(Calls.begin() + FirstIndex, Calls.end(), Pred),
                 Calls.end());
   }
 
 private:
   Container Calls;
   size_t FirstIndex = 0;
 };
 
+class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
+  using T = std::pair<CallBase *, int>;
+  using reference = T &;
+
+  struct Compare {
+    bool operator()(const T &P1, const T &P2) { return P1.second > P2.second; }
+  };
+
+  int evaluate(CallBase *CB) {
+    Function *Callee = CB->getCalledFunction();
+    return (int)Callee->getInstructionCount();
+  }
+
+public:
+  size_t size() override { return PQ.size(); }
+
+  void push(const T &Elt) override {
+    CallBase *CB = Elt.first;
+    const int InlineHistoryID = Elt.second;
+    const int Goodness = evaluate(CB);
+
+    PQ.push({CB, Goodness});
+    InlineHistoryMap[CB] = InlineHistoryID;
+  }
+
+  void pop() override {
+    assert(size() > 0);
+
+    auto &Elt = PQ.top();
+    CallBase *CB = Elt.first;
+    InlineHistoryMap.erase(CB);
+    PQ.pop();
+  }
+
+  T front() override {
+    assert(size() > 0);
+    CallBase *CB = PQ.top().first;
+    return std::make_pair(CB, InlineHistoryMap[CB]);
+  }
+
+  void erase_if(function_ref<bool(T)> Pred) override {
+    PriorityQueue<T, std::vector<T>, Compare> TempPQ;
+    while (!PQ.empty()) {
+      auto P = PQ.top();
+      PQ.pop();
+      if (Pred({P.first, 0}))
+        InlineHistoryMap.erase(P.first);
+      else
+        TempPQ.push(P);
+    }
+    PQ = std::move(TempPQ);
+  }
+
+private:
+  PriorityQueue<T, std::vector<T>, Compare> PQ;
+  DenseMap<CallBase *, int> InlineHistoryMap;
+};
+
 PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
                                    CGSCCAnalysisManager &AM, LazyCallGraph &CG,
                                    CGSCCUpdateResult &UR) {
   const auto &MAMProxy =
       AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG);
   bool Changed = false;
 
   assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
   Module &M = *InitialC.begin()->getFunction().getParent();
   ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(M);
 
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(InitialC, CG)
           .getManager();
 
   InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M);
   Advisor.onPassEntry();
 
   auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); });
 
   // We use a single common worklist for calls across the entire SCC. We
   // process these in-order and append new calls introduced during inlining to
   // the end.
   //
   // Note that this particular order of processing is actually critical to
   // avoid very bad behaviors. Consider *highly connected* call graphs where
   // each function contains a small amount of code and a couple of calls to
   // other functions. Because the LLVM inliner is fundamentally a bottom-up
   // inliner, it can handle gracefully the fact that these all appear to be
   // reasonable inlining candidates as it will flatten things until they become
   // too big to inline, and then move on and flatten another batch.
   //
   // However, when processing call edges *within* an SCC we cannot rely on this
   // bottom-up behavior. As a consequence, with heavily connected *SCCs* of
   // functions we can end up incrementally inlining N calls into each of
   // N functions because each incremental inlining decision looks good and we
   // don't have a topological ordering to prevent explosions.
   //
   // 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.
-  DefaultInlineOrder<std::pair<CallBase *, int>> Calls;
+  PriorityInlineOrder Calls;
 
   // 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()))
       if (auto *CB = dyn_cast<CallBase>(&I))
auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
       return FAM.getResult<AssumptionAnalysis>(F);
     };
 
     // Now process as many calls as we have within this caller in the sequence.
     // We bail out as soon as the caller has to change so we can update the
     // call graph and prepare the context of that new caller.
     bool DidInline = false;
     while (!Calls.empty() && Calls.front().first->getCaller() == &F) {
-      auto &P = Calls.front();
+      auto P = Calls.front();
       Calls.pop();
       CallBase *CB = P.first;
       const int InlineHistoryID = P.second;
       Function &Callee = *CB->getCalledFunction();
 
       if (InlineHistoryID != -1 &&
           inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
         setInlineRemark(*CB, "recursive");
         continue;
       }
 
       // Check if this inlining may repeat breaking an SCC apart that has