[llvm][Inline] Refactor out InlineOrder

[taolq]

Summary

Move InlineOrder to separated file.

[kazu]

llvm/include/llvm/Analysis/InlineOrder.h

2

Please remove this empty line.

14–18

Please include what you use like "llvm/ADT/SmallVector.h", <algorithm>, etc.

LLVM header files are supposed to be self contained, meaning that a C++ source file that does nothing but include a header file compiles without a problem. While developing this patch, you could try to include this header file as the first one in Inliner.cpp to see if you get any errors from the compiler.

21–25

Please remove these.

77

If we are moving this class outside a .cpp, I might rename it to InlinePriority or something to avoid potential conflicts.

174

Please add a newline at the end.

[taolq]

• fix clang-tidy errors

[kazu]

LGTM. Thank you for updating the patch!

llvm/include/llvm/Analysis/InlineOrder.h

+//===- InlineOrder.h - Inlining order abstraction -*- C++ ---*-------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+#ifndef LLVM_ANALYSIS_INLINEORDER_H
+#define LLVM_ANALYSIS_INLINEORDER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include <algorithm>
+#include <utility>
+
+namespace llvm {
+class CallBase;
+class Function;
+class Module;
+
+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 T pop() = 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); }
+
+  T pop() override {
+    assert(size() > 0);
+    return Calls[FirstIndex++];
+  }
+
+  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 InlineSizePriority {
+public:
+  InlineSizePriority(int Size) : Size(Size) {}
+
+  static bool isMoreDesirable(const InlineSizePriority &S1,
+                              const InlineSizePriority &S2) {
+    return S1.Size < S2.Size;
+  }
+
+  static InlineSizePriority evaluate(CallBase *CB) {
+    Function *Callee = CB->getCalledFunction();
+    return InlineSizePriority(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 &;
+
+  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 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 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);
+    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 {
+    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<HeapT, 16> Heap;
+  DenseMap<CallBase *, int> InlineHistoryMap;
+};
+} // namespace llvm
+#endif // LLVM_ANALYSIS_INLINEORDER_H

llvm/lib/Transforms/IPO/Inliner.cpp

 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InlineAdvisor.h"
 #include "llvm/Analysis/InlineCost.h"
+#include "llvm/Analysis/InlineOrder.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/Utils/ImportedFunctionsInliningStatistics.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
if (!IAA) {
     return *OwnedAdvisor;
   }
   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 T pop() = 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); }
-
-  T pop() override {
-    assert(size() > 0);
-    return Calls[FirstIndex++];
-  }
-
-  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 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 &;
-
-  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 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 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);
-    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 {
-    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<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);
   bool Changed = false;
 
   assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
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<Priority>>();
+    Calls = std::make_unique<PriorityInlineOrder<InlineSizePriority>>();
   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());