[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

713

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).

823–828

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

823–828

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

823–828

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

769–780

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

904–906

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

728

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

827

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.

799–822

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

801

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);
 
+static cl::opt<bool> InlineEnablePriorityOrder(
+    "inline-enable-priority-order", cl::Hidden, cl::init(false),
+    cl::desc("Enable the priority inline order for the inliner"));
+
 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.
assert(IAA->getAdvisor() &&
          "Expected a present InlineAdvisorAnalysis also have an "
          "InlineAdvisor initialized");
   return *IAA->getAdvisor();
 }
 
 template <typename T> class InlineOrder {
 public:
   using reference = T &;
+  using const_reference = const T &;
 
   virtual ~InlineOrder() {}
 
   virtual size_t size() = 0;
 
   virtual void push(const T &Elt) = 0;
 
-  virtual void pop() = 0;
+  virtual T pop() = 0;
 
-  virtual reference front() = 0;
+  virtual const_reference 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 &;
+  using const_reference = const T &;
 
 public:
   size_t size() override { return Calls.size() - FirstIndex; }
 
   void push(const T &Elt) override { Calls.push_back(Elt); }
 
-  void pop() override {
+  T pop() override {
     assert(size() > 0);
-    FirstIndex++;
+    return Calls[FirstIndex++];
   }
 
-  reference front() override {
+  const_reference 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 &;
+  using const_reference = const T &;
+
+  static bool cmp(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 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);
+    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);
+    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);
+  }
+
+private:
+  SmallVector<T, 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);
   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;
+  std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> Calls;
+  if (InlineEnablePriorityOrder)
+    Calls.reset(new PriorityInlineOrder());
+  else
+    Calls.reset(new 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()))
       if (auto *CB = dyn_cast<CallBase>(&I))
         if (Function *Callee = CB->getCalledFunction()) {
           if (!Callee->isDeclaration())
-            Calls.push({CB, -1});
+            Calls->push({CB, -1});
           else if (!isa<IntrinsicInst>(I)) {
             using namespace ore;
             setInlineRemark(*CB, "unavailable definition");
             ORE.emit([&]() {
               return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
                      << NV("Callee", Callee) << " will not be inlined into "
                      << NV("Caller", CB->getCaller())
                      << " because its definition is unavailable"
                      << setIsVerbose();
             });
           }
         }
   }
-  if (Calls.empty())
+  if (Calls->empty())
     return PreservedAnalyses::all();
 
   // Capture updatable variable for the current SCC.
   auto *C = &InitialC;
 
   // When inlining a callee produces new call sites, we want to keep track of
   // the fact that they were inlined from the callee.  This allows us to avoid
   // infinite inlining in some obscure cases.  To represent this, we use an
   // index into the InlineHistory vector.
   SmallVector<std::pair<Function *, int>, 16> InlineHistory;
 
   // Track a set vector of inlined callees so that we can augment the caller
   // with all of their edges in the call graph before pruning out the ones that
   // got simplified away.
   SmallSetVector<Function *, 4> InlinedCallees;
 
   // Track the dead functions to delete once finished with inlining calls. We
   // defer deleting these to make it easier to handle the call graph updates.
   SmallVector<Function *, 4> DeadFunctions;
 
   // Loop forward over all of the calls.
-  while (!Calls.empty()) {
+  while (!Calls->empty()) {
     // We expect the calls to typically be batched with sequences of calls that
     // have the same caller, so we first set up some shared infrastructure for
     // this caller. We also do any pruning we can at this layer on the caller
     // alone.
-    Function &F = *Calls.front().first->getCaller();
+    Function &F = *Calls->front().first->getCaller();
     LazyCallGraph::Node &N = *CG.lookup(F);
     if (CG.lookupSCC(N) != C) {
-      Calls.pop();
+      Calls->pop();
       continue;
     }
 
     LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
                       << "    Function size: " << F.getInstructionCount()
                       << "\n");
 
     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();
-      Calls.pop();
+    while (!Calls->empty() && Calls->front().first->getCaller() == &F) {
+      auto P = 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;
       }
 
while (!Calls->empty() && Calls->front().first->getCaller() == &F) {
             // the post-inline cleanup and the next DevirtSCCRepeatedPass
             // iteration because the next iteration may not happen and we may
             // miss inlining it.
             if (tryPromoteCall(*ICB))
               NewCallee = ICB->getCalledFunction();
           }
           if (NewCallee)
             if (!NewCallee->isDeclaration())
-              Calls.push({ICB, NewHistoryID});
+              Calls->push({ICB, NewHistoryID});
         }
       }
 
       // Merge the attributes based on the inlining.
       AttributeFuncs::mergeAttributesForInlining(F, Callee);
 
       // For local functions, check whether this makes the callee trivially
       // dead. In that case, we can drop the body of the function eagerly
       // which may reduce the number of callers of other functions to one,
       // changing inline cost thresholds.
       bool CalleeWasDeleted = false;
       if (Callee.hasLocalLinkage()) {
         // To check this we also need to nuke any dead constant uses (perhaps
         // made dead by this operation on other functions).
         Callee.removeDeadConstantUsers();
         if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
-          Calls.erase_if([&](const std::pair<CallBase *, int> &Call) {
+          Calls->erase_if([&](const std::pair<CallBase *, int> &Call) {
             return Call.first->getCaller() == &Callee;
           });
           // Clear the body and queue the function itself for deletion when we
           // finish inlining and call graph updates.
           // Note that after this point, it is an error to do anything other
           // than use the callee's address or delete it.
           Callee.dropAllReferences();
           assert(!is_contained(DeadFunctions, &Callee) &&