[ModuleInliner] Move InlinePriority and its derived classes to InlineOrder.cpp (NFC)

[kazu]

Summary

These classes are referred to only from getInlineOrder in
InlineOrder.cpp. This patch hides the entire class declarations and
definitions in InlineOrder.cpp.

[mtrofin]

llvm/lib/Analysis/InlineOrder.cpp

24

should it be in a anonymous namespace?

[kazu]

Use an anonymous namespace.

[kazu]

Thank you for the review Mircea!

llvm/lib/Analysis/InlineOrder.cpp

24

Good point!

[kosarev]

llvm/lib/Analysis/InlineOrder.cpp

124

It looks something is not quite right about how this heap is formed. An assert(std::is_heap(Heap.begin(), Heap.end(), isLess)); added before that line would fail on Transforms/Inline/nested-inline.ll. Can anyone take a look, please?

Originally caught on a build with libc++'s consistency checks enabled, https://github.com/llvm/llvm-project/issues/68594.

[taolq]

llvm/lib/Analysis/InlineOrder.cpp

124

Thanks for the information. I will take a look.

[taolq]

llvm/lib/Analysis/InlineOrder.cpp

124

I just figure it out. The assert you added failed because the Heap is updated lazily. After line 123 updateAndCheckDecreased, the priority has been changed, but the Heap has not been resorted yet.
So assert(std::is_heap(Heap.begin(), Heap.end(), isLess)); should be appended after std::push_heap.
And Transforms/Inline/nested-inline.ll would pass with that change.

[kosarev]

llvm/lib/Analysis/InlineOrder.cpp

124

I think std:pop_heap() requires the range to be a valid heap by the moment of the call; we should not rely on std::push_heap() fixing the heap.

Here's the backtrace:

******************** TEST 'LLVM :: Transforms/Inline/nested-inline.ll' FAILED ********************
Exit Code: 2

Command Output (stderr):
--
RUN: at line 1: /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt < /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll -passes=inline -S | /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/FileCheck /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll
+ /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt -passes=inline -S
+ /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/FileCheck /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll
RUN: at line 2: /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt < /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll -passes='cgscc(inline)' -S | /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/FileCheck /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll
+ /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt '-passes=cgscc(inline)' -S
+ /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/FileCheck /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll
RUN: at line 3: /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt < /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll -passes='module-inline' -S | /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/FileCheck /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll
+ /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt -passes=module-inline -S
+ /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/FileCheck /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll
/usr/include/c++/11/bits/stl_heap.h:325:
In function:
    void std::pop_heap(_RAIter, _RAIter, _Compare) [with _RAIter = 
    llvm::CallBase**; _Compare = std::function<bool(const llvm::CallBase*, 
    const llvm::CallBase*)>]

Error: elements in iterator range [first, last) do not form a heap with 
respect to the predicate __comp.

Objects involved in the operation:
    iterator "first" @ 0x7ffe489f0268 {
    }
    iterator "last" @ 0x7ffe489f0260 {
    }
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt -passes=module-inline -S
 #0 0x00007fd0a21586c8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/kosarev/labs/llvm-project/llvm/lib/Support/Unix/Signals.inc:723:22
 #1 0x00007fd0a2158ae4 PrintStackTraceSignalHandler(void*) /home/kosarev/labs/llvm-project/llvm/lib/Support/Unix/Signals.inc:798:1
 #2 0x00007fd0a2155f29 llvm::sys::RunSignalHandlers() /home/kosarev/labs/llvm-project/llvm/lib/Support/Signals.cpp:105:20
 #3 0x00007fd0a2157f60 SignalHandler(int) /home/kosarev/labs/llvm-project/llvm/lib/Support/Unix/Signals.inc:413:1
 #4 0x00007fd0a19dd520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #5 0x00007fd0a1a319fc __pthread_kill_implementation ./nptl/pthread_kill.c:44:76
 #6 0x00007fd0a1a319fc __pthread_kill_internal ./nptl/pthread_kill.c:78:10
 #7 0x00007fd0a1a319fc pthread_kill ./nptl/pthread_kill.c:89:10
 #8 0x00007fd0a19dd476 gsignal ./signal/../sysdeps/posix/raise.c:27:6
 #9 0x00007fd0a19c37f3 abort ./stdlib/abort.c:81:7
#10 0x00007fd0a1c681fb std::__throw_bad_exception() (/lib/x86_64-linux-gnu/libstdc++.so.6+0xa51fb)
#11 0x00007fd0a35e2228 void std::pop_heap<llvm::CallBase**, std::function<bool (llvm::CallBase const*, llvm::CallBase const*)>>(llvm::CallBase**, llvm::CallBase**, std::function<bool (llvm::CallBase const*, llvm::CallBase const*)>) /usr/include/c++/11/bits/stl_heap.h:327:18
#12 0x00007fd0a35da8b5 (anonymous namespace)::PriorityInlineOrder<(anonymous namespace)::SizePriority>::adjust() /home/kosarev/labs/llvm-project/llvm/lib/Analysis/InlineOrder.cpp:227:20
#13 0x00007fd0a35d9f98 (anonymous namespace)::PriorityInlineOrder<(anonymous namespace)::SizePriority>::pop() /home/kosarev/labs/llvm-project/llvm/lib/Analysis/InlineOrder.cpp:256:30
#14 0x00007fd0a85337d0 llvm::ModuleInlinerPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/kosarev/labs/llvm-project/llvm/lib/Transforms/IPO/ModuleInliner.cpp:180:24
#15 0x00007fd0a90fb66d llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/kosarev/labs/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:90:3
#16 0x00007fd0a294e171 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/kosarev/labs/llvm-project/llvm/include/llvm/IR/PassManager.h:521:20
#17 0x000055c2085d4371 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool, bool) /home/kosarev/labs/llvm-project/llvm/tools/opt/NewPMDriver.cpp:527:10
#18 0x000055c208605385 main /home/kosarev/labs/llvm-project/llvm/tools/opt/opt.cpp:698:27
#19 0x00007fd0a19c4d90 __libc_start_call_main ./csu/../sysdeps/nptl/libc_start_call_main.h:58:16
#20 0x00007fd0a19c4e40 call_init ./csu/../csu/libc-start.c:128:20
#21 0x00007fd0a19c4e40 __libc_start_main ./csu/../csu/libc-start.c:379:5
#22 0x000055c2085d1605 _start (/home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt+0x1c605)
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/FileCheck /home/kosarev/labs/llvm-project/llvm/test/Transforms/Inline/nested-inline.ll

[taolq]

llvm/lib/Analysis/InlineOrder.cpp

124

It makes sense. I will fix it asap.

[kazu]

@taolq has posted a PR:

https://github.com/llvm/llvm-project/pull/69206

Let's continue the discussion there.

llvm/include/llvm/Analysis/InlineOrder.h

Calls.erase(std::remove_if(Calls.begin() + FirstIndex, Calls.end(), Pred),
                 Calls.end());
   }
 
 private:
   Container Calls;
   size_t FirstIndex = 0;
 };
 
-class InlinePriority {
-public:
-  virtual ~InlinePriority() = default;
-  virtual bool hasLowerPriority(const CallBase *L, const CallBase *R) const = 0;
-  virtual void update(const CallBase *CB) = 0;
-  virtual bool updateAndCheckDecreased(const CallBase *CB) = 0;
-};
-
-class SizePriority : public InlinePriority {
-  using PriorityT = unsigned;
-  DenseMap<const CallBase *, PriorityT> Priorities;
-
-  PriorityT evaluate(const CallBase *CB) {
-    Function *Callee = CB->getCalledFunction();
-    return Callee->getInstructionCount();
-  }
-
-  bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) const {
-    return P1 < P2;
-  }
-
-public:
-  bool hasLowerPriority(const CallBase *L, const CallBase *R) const override {
-    const auto I1 = Priorities.find(L);
-    const auto I2 = Priorities.find(R);
-    assert(I1 != Priorities.end() && I2 != Priorities.end());
-    return isMoreDesirable(I2->second, I1->second);
-  }
-
-  // Update the priority associated with CB.
-  void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); };
-
-  bool updateAndCheckDecreased(const CallBase *CB) override {
-    auto It = Priorities.find(CB);
-    const auto OldPriority = It->second;
-    It->second = evaluate(CB);
-    const auto NewPriority = It->second;
-    return isMoreDesirable(OldPriority, NewPriority);
-  }
-};
-
-class CostPriority : public InlinePriority {
-  using PriorityT = int;
-  DenseMap<const CallBase *, PriorityT> Priorities;
-  std::function<InlineCost(const CallBase *)> getInlineCost;
-
-  PriorityT evaluate(const CallBase *CB) {
-    auto IC = getInlineCost(CB);
-    int cost = 0;
-    if (IC.isVariable())
-      cost = IC.getCost();
-    else
-      cost = IC.isNever() ? INT_MAX : INT_MIN;
-    return cost;
-  }
-
-  bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) const {
-    return P1 < P2;
-  }
-
-public:
-  CostPriority() = delete;
-  CostPriority(std::function<InlineCost(const CallBase *)> getInlineCost)
-      : getInlineCost(getInlineCost){};
-
-  bool hasLowerPriority(const CallBase *L, const CallBase *R) const override {
-    const auto I1 = Priorities.find(L);
-    const auto I2 = Priorities.find(R);
-    assert(I1 != Priorities.end() && I2 != Priorities.end());
-    return isMoreDesirable(I2->second, I1->second);
-  }
-
-  // Update the priority associated with CB.
-  void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); };
-
-  bool updateAndCheckDecreased(const CallBase *CB) override {
-    auto It = Priorities.find(CB);
-    const auto OldPriority = It->second;
-    It->second = evaluate(CB);
-    const auto NewPriority = It->second;
-    return isMoreDesirable(OldPriority, NewPriority);
-  }
-};
-
-class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
-  using T = std::pair<CallBase *, int>;
-  using reference = T &;
-  using const_reference = const T &;
-
-  // 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() {
-    while (PriorityPtr->updateAndCheckDecreased(Heap.front())) {
-      std::pop_heap(Heap.begin(), Heap.end(), isLess);
-      std::push_heap(Heap.begin(), Heap.end(), isLess);
-    }
-  }
-
-public:
-  PriorityInlineOrder(std::unique_ptr<InlinePriority> PriorityPtr)
-      : PriorityPtr(std::move(PriorityPtr)) {
-    isLess = [this](const CallBase *L, const CallBase *R) {
-      return this->PriorityPtr->hasLowerPriority(L, R);
-    };
-  }
-
-  size_t size() override { return Heap.size(); }
-
-  void push(const T &Elt) override {
-    CallBase *CB = Elt.first;
-    const int InlineHistoryID = Elt.second;
-
-    Heap.push_back(CB);
-    PriorityPtr->update(CB);
-    std::push_heap(Heap.begin(), Heap.end(), isLess);
-    InlineHistoryMap[CB] = InlineHistoryID;
-  }
-
-  T pop() override {
-    assert(size() > 0);
-    adjust();
-
-    CallBase *CB = Heap.front();
-    T Result = std::make_pair(CB, InlineHistoryMap[CB]);
-    InlineHistoryMap.erase(CB);
-    std::pop_heap(Heap.begin(), Heap.end(), isLess);
-    Heap.pop_back();
-    return Result;
-  }
-
-  const_reference front() override {
-    assert(size() > 0);
-    adjust();
-
-    CallBase *CB = Heap.front();
-    return *InlineHistoryMap.find(CB);
-  }
-
-  void erase_if(function_ref<bool(T)> Pred) override {
-    auto PredWrapper = [=](CallBase *CB) -> bool {
-      return Pred(std::make_pair(CB, 0));
-    };
-    llvm::erase_if(Heap, PredWrapper);
-    std::make_heap(Heap.begin(), Heap.end(), isLess);
-  }
-
-private:
-  SmallVector<CallBase *, 16> Heap;
-  std::function<bool(const CallBase *L, const CallBase *R)> isLess;
-  DenseMap<CallBase *, int> InlineHistoryMap;
-  std::unique_ptr<InlinePriority> PriorityPtr;
-};
-
 } // namespace llvm
 #endif // LLVM_ANALYSIS_INLINEORDER_H

llvm/lib/Analysis/InlineOrder.cpp

 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "inline-order"
 
+namespace {
+
+class InlinePriority {
+public:
+  virtual ~InlinePriority() = default;
+  virtual bool hasLowerPriority(const CallBase *L, const CallBase *R) const = 0;
+  virtual void update(const CallBase *CB) = 0;
+  virtual bool updateAndCheckDecreased(const CallBase *CB) = 0;
+};
+
+class SizePriority : public InlinePriority {
+  using PriorityT = unsigned;
+  DenseMap<const CallBase *, PriorityT> Priorities;
+
+  PriorityT evaluate(const CallBase *CB) {
+    Function *Callee = CB->getCalledFunction();
+    return Callee->getInstructionCount();
+  }
+
+  bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) const {
+    return P1 < P2;
+  }
+
+public:
+  bool hasLowerPriority(const CallBase *L, const CallBase *R) const override {
+    const auto I1 = Priorities.find(L);
+    const auto I2 = Priorities.find(R);
+    assert(I1 != Priorities.end() && I2 != Priorities.end());
+    return isMoreDesirable(I2->second, I1->second);
+  }
+
+  // Update the priority associated with CB.
+  void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); };
+
+  bool updateAndCheckDecreased(const CallBase *CB) override {
+    auto It = Priorities.find(CB);
+    const auto OldPriority = It->second;
+    It->second = evaluate(CB);
+    const auto NewPriority = It->second;
+    return isMoreDesirable(OldPriority, NewPriority);
+  }
+};
+
+class CostPriority : public InlinePriority {
+  using PriorityT = int;
+  DenseMap<const CallBase *, PriorityT> Priorities;
+  std::function<InlineCost(const CallBase *)> getInlineCost;
+
+  PriorityT evaluate(const CallBase *CB) {
+    auto IC = getInlineCost(CB);
+    int cost = 0;
+    if (IC.isVariable())
+      cost = IC.getCost();
+    else
+      cost = IC.isNever() ? INT_MAX : INT_MIN;
+    return cost;
+  }
+
+  bool isMoreDesirable(const PriorityT &P1, const PriorityT &P2) const {
+    return P1 < P2;
+  }
+
+public:
+  CostPriority() = delete;
+  CostPriority(std::function<InlineCost(const CallBase *)> getInlineCost)
+      : getInlineCost(getInlineCost){};
+
+  bool hasLowerPriority(const CallBase *L, const CallBase *R) const override {
+    const auto I1 = Priorities.find(L);
+    const auto I2 = Priorities.find(R);
+    assert(I1 != Priorities.end() && I2 != Priorities.end());
+    return isMoreDesirable(I2->second, I1->second);
+  }
+
+  // Update the priority associated with CB.
+  void update(const CallBase *CB) override { Priorities[CB] = evaluate(CB); };
+
+  bool updateAndCheckDecreased(const CallBase *CB) override {
+    auto It = Priorities.find(CB);
+    const auto OldPriority = It->second;
+    It->second = evaluate(CB);
+    const auto NewPriority = It->second;
+    return isMoreDesirable(OldPriority, NewPriority);
+  }
+};
+
+class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
+  using T = std::pair<CallBase *, int>;
+  using reference = T &;
+  using const_reference = const T &;
+
+  // 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() {
+    while (PriorityPtr->updateAndCheckDecreased(Heap.front())) {
+      std::pop_heap(Heap.begin(), Heap.end(), isLess);
+      std::push_heap(Heap.begin(), Heap.end(), isLess);
+    }
+  }
+
+public:
+  PriorityInlineOrder(std::unique_ptr<InlinePriority> PriorityPtr)
+      : PriorityPtr(std::move(PriorityPtr)) {
+    isLess = [this](const CallBase *L, const CallBase *R) {
+      return this->PriorityPtr->hasLowerPriority(L, R);
+    };
+  }
+
+  size_t size() override { return Heap.size(); }
+
+  void push(const T &Elt) override {
+    CallBase *CB = Elt.first;
+    const int InlineHistoryID = Elt.second;
+
+    Heap.push_back(CB);
+    PriorityPtr->update(CB);
+    std::push_heap(Heap.begin(), Heap.end(), isLess);
+    InlineHistoryMap[CB] = InlineHistoryID;
+  }
+
+  T pop() override {
+    assert(size() > 0);
+    adjust();
+
+    CallBase *CB = Heap.front();
+    T Result = std::make_pair(CB, InlineHistoryMap[CB]);
+    InlineHistoryMap.erase(CB);
+    std::pop_heap(Heap.begin(), Heap.end(), isLess);
+    Heap.pop_back();
+    return Result;
+  }
+
+  const_reference front() override {
+    assert(size() > 0);
+    adjust();
+
+    CallBase *CB = Heap.front();
+    return *InlineHistoryMap.find(CB);
+  }
+
+  void erase_if(function_ref<bool(T)> Pred) override {
+    auto PredWrapper = [=](CallBase *CB) -> bool {
+      return Pred(std::make_pair(CB, 0));
+    };
+    llvm::erase_if(Heap, PredWrapper);
+    std::make_heap(Heap.begin(), Heap.end(), isLess);
+  }
+
+private:
+  SmallVector<CallBase *, 16> Heap;
+  std::function<bool(const CallBase *L, const CallBase *R)> isLess;
+  DenseMap<CallBase *, int> InlineHistoryMap;
+  std::unique_ptr<InlinePriority> PriorityPtr;
+};
+
+} // namespace
+
 static llvm::InlineCost getInlineCostWrapper(CallBase &CB,
                                              FunctionAnalysisManager &FAM,
                                              const InlineParams &Params) {
   Function &Caller = *CB.getCaller();
   ProfileSummaryInfo *PSI =
       FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
           .getCachedResult<ProfileSummaryAnalysis>(
               *CB.getParent()->getParent()->getParent());