[InlineOrder] Add TopDownInlineOrder

[IBricchi]

Summary

Adds a top down order to the ModuleInliner. A top down inlining order ensures
that all possible inlining decisions are possible (depending on what the
InliningAdvisor chooses), e.g., callsites in callees can be independently
inlined.

[kazu]

llvm/lib/Analysis/InlineOrder.cpp

293

Lowercase. we

300

Put a period CD..

302

Are you duplicating much of InlineOrder because you use NodeCallCount as cache and do not care about updating the priority while the priority queue is consumed? I'm wondering if there is a good way for you to take what you need without duplicating the rest.

305

Maybe "how many places" instead of "how many times". Otherwise, we might sound like we are talking about profiling counts.

309

Capitalize the first letter and put a period at the end. Check which call sites caller has least calls.

311

Please rename this to LeftCount.

https://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

This applies to other variables in the same function.

321

How do you ensure the top down inlining when you have a run of single edges with NodeCallCount alone? Here, each one of B, C, D, etc is called from exactly one place, but there is a clear order in the call graph.

 A
/ \
B C
| |
D E
| |
F G
| |
H I

337

Put a period at the end like functions..

339

Likewise.

340–347

How does this work? It looks like NodeCallCount keeps changing while you are pushing all call sites at the beginning of the inlining pass (see ModuleInliner.cpp:145). So, a call site inserted at the beginning of the population loop and another call site inserted toward the end of the population loop are based on totally different values of NodeCallCount even though you haven't done any inlining at all. Unless you call std::make_heap at the end of the initial population loop, I am not sure if call sites are in any particular order that makes sense.

375

Put some comment like:

// A map from a function to the number of call sites it is statically called from.

llvm/test/Transforms/Inline/module-inliner-basic.ll

22

Please add a new line. The message "No newline at end of file" is a bit distracting now and when somebody adds more lines to the file and examines the diff.

llvm/test/Transforms/Inline/top-down-inliner-multiple-heads.ll

33

Likewise.

llvm/test/Transforms/Inline/top-down-inliner-recursion.ll

33

Likewise.

llvm/test/Transforms/Inline/top-down-inliner-simple.ll

34

Likewise.

[IBricchi]

llvm/lib/Analysis/InlineOrder.cpp

321

You make a good point, I forgot to decrease the call count when we pop the Caller node. This should be addressed now.

I've provided a more indepth explanation as a response to one of your later comments.

340–347

The idea is basically that we only ever consider callers that appear the least number of times in our "NodeCallCount" however as we pop calls we also remove them from our "NodeCallCount" so in the above example.

 A
/ \
B C
| |
D E
| |
F G
| |
H I

If we decide not to inline A->B or A->C, once poped we would effectively end up counts that represent a call graph like:

B C
| |
D E
| |
F G
| |
H I

Which would then consider B->D or C->E, and so on...

If the calls do get inlined we would end up with counts for a similar call graph:

AB AC
|  |
D  E
|  |
F  G
|  |
H  I

The bulk of the call sites an the heap aren't necessarily in a particular order, only the top of the heap, but since it's only ever accessed by popping the top is the only value that really needs to be in the right place.

[IBricchi]

llvm/lib/Analysis/InlineOrder.cpp

302

Do you mean duplication from PriorityInlineOrder?

Most of the duplication is to keep track of InlineHistory, and managing what CallBases are corrently being considered (heap). I'm not sure which parts we would be able to remove.

We could replace the Heap with a vector or set and not worry about the orider but I'm not sure if that's the kind of change you were suggesting.

[IBricchi]

Thanks for the review @hiraditya I've come to realize this patch might not fit well with the other inline-order options. Instead I think it might make more sense to implement the functionality using custom plugins.

I opened a separate PR in this direction https://reviews.llvm.org/D140637. I would appreciate it if you could take a look at that.

llvm/lib/Analysis/InlineOrder.cpp

 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "inline-order"
 
-enum class InlinePriorityMode : int { Size, Cost, CostBenefit, ML };
+enum class InlinePriorityMode : int { Size, Cost, CostBenefit, ML, TopDown };
 
 static cl::opt<InlinePriorityMode> UseInlinePriority(
     "inline-priority-mode", cl::init(InlinePriorityMode::Size), cl::Hidden,
     cl::desc("Choose the priority mode to use in module inline"),
     cl::values(clEnumValN(InlinePriorityMode::Size, "size",
                           "Use callee size priority."),
                clEnumValN(InlinePriorityMode::Cost, "cost",
                           "Use inline cost priority."),
                clEnumValN(InlinePriorityMode::CostBenefit, "cost-benefit",
                           "Use cost-benefit ratio."),
-               clEnumValN(InlinePriorityMode::ML, "ml",
-                          "Use ML.")));
+               clEnumValN(InlinePriorityMode::ML, "ml", "Use ML."),
+               clEnumValN(InlinePriorityMode::TopDown, "top-down",
+                          "Use callgraph top-down priority.")));
 
 static cl::opt<int> ModuleInlinerTopPriorityThreshold(
     "moudle-inliner-top-priority-threshold", cl::Hidden, cl::init(0),
     cl::desc("The cost threshold for call sites that get inlined without the "
              "cost-benefit analysis"));
 
 namespace {
 
private:
   SmallVector<CallBase *, 16> Heap;
   std::function<bool(const CallBase *L, const CallBase *R)> isLess;
   DenseMap<CallBase *, int> InlineHistoryMap;
   DenseMap<const CallBase *, PriorityT> Priorities;
   FunctionAnalysisManager &FAM;
   const InlineParams &Params;
 };
 
+/// Top Down Inline Order
+/// The order in which inlining decisions are made impacts the explorable
+/// decision space for the inliner.
+/// For example with:
+/// A   B
+///  \ /
+///   C
+///   |
+///   D
+/// In this case, if we were to first make a decision on the C->D call site
+/// We would lose the ability to make separate decisions for the A->C->D and
+/// B->C->D call paths. And a final inlining graph like:
+/// ACD  B
+///      |
+///      C
+///      |
+///      D
+/// Could not be generated since we have two different inlining decisions for CD
+/// With the top-down inliner, we can explore all possible inlining decisions.
+class TopDownInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
+  using T = std::pair<CallBase *, int>;
+
+  // We keep track of how many times a function has been called. This is used
+  // to order call sites in a top-down fashion by selecting the call site with
+  // the least number of calls to its caller at each step.
+
+  // check which call sites caller has least calls
+  bool hasLowerPriority(const CallBase *L, const CallBase *R) const {
+    int left_count = 0;
+    const auto left_I = NodeCallCount.find(L->getCaller());
+    if (left_I != NodeCallCount.end())
+      left_count = left_I->second;
+
+    int right_count = 0;
+    const auto right_I = NodeCallCount.find(R->getCaller());
+    if (right_I != NodeCallCount.end())
+      right_count = right_I->second;
+
+    return left_count > right_count;
+  }
+
+public:
+  TopDownInlineOrder() : NodeCallCount{} {
+    isLess = [&](const CallBase *L, const CallBase *R) {
+      return 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;
+
+    // We keep track of how many times a function is called by other functions
+    // This count can be used to determine the top of the call graph by ordering
+    // the heap form least calls to most calls
+    Function *Callee = CB->getCalledFunction();
+    if (NodeCallCount.find(Callee) == NodeCallCount.end()) {
+      NodeCallCount[Callee] = 0;
+    }
+    NodeCallCount[Callee]++;
+
+    Heap.push_back(CB);
+    std::push_heap(Heap.begin(), Heap.end(), isLess);
+
+    InlineHistoryMap[CB] = InlineHistoryID;
+  }
+
+  T pop() override {
+    assert(size() > 0);
+
+    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;
+  }
+
+  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;
+  DenseMap<const Function *, int> NodeCallCount;
+};
+
 } // namespace
 
 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
 llvm::getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params) {
   switch (UseInlinePriority) {
   case InlinePriorityMode::Size:
     LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
     return std::make_unique<PriorityInlineOrder<SizePriority>>(FAM, Params);
 
   case InlinePriorityMode::Cost:
     LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
     return std::make_unique<PriorityInlineOrder<CostPriority>>(FAM, Params);
 
   case InlinePriorityMode::CostBenefit:
     LLVM_DEBUG(
         dbgs() << "    Current used priority: cost-benefit priority ---- \n");
-    return std::make_unique<PriorityInlineOrder<CostBenefitPriority>>(FAM, Params);
   case InlinePriorityMode::ML:
     LLVM_DEBUG(
         dbgs() << "    Current used priority: ML priority ---- \n");
     return std::make_unique<PriorityInlineOrder<MLPriority>>(FAM, Params);
+  case InlinePriorityMode::TopDown:
+    LLVM_DEBUG(
+        dbgs() << "    Current used priority: top-down priority ---- \n");
+    return std::make_unique<TopDownInlineOrder>();
   }
   return nullptr;
 }

llvm/test/Transforms/Inline/module-inliner-basic.ll

 ; RUN: opt -passes=module-inline                                    -S < %s | FileCheck %s
 ; RUN: opt -passes=module-inline -inline-priority-mode=size         -S < %s | FileCheck %s
 ; RUN: opt -passes=module-inline -inline-priority-mode=cost         -S < %s | FileCheck %s
 ; RUN: opt -passes=module-inline -inline-priority-mode=cost-benefit -S < %s | FileCheck %s
 ; RUN: opt -passes=module-inline -inline-priority-mode=ml           -S < %s | FileCheck %s
+; RUN: opt -passes=module-inline -inline-priority-mode=top-down     -S < %s | FileCheck %s
 
 define i32 @callee(i32 %a) {
 entry:
   %add = add nsw i32 %a, 1
   ret i32 %add
 }
 
 define i32 @caller(i32 %a) {
 entry:
   %call = call i32 @callee(i32 %a)
   ret i32 %call
 }
 
 ; CHECK-LABEL: @caller
 ; CHECK-NOT:     call
-; CHECK:         ret
+; CHECK:         ret
 No newline at end of file

llvm/test/Transforms/Inline/top-down-inliner-multiple-heads.ll

+; RUN: opt -passes=module-inline -inline-priority-mode=top-down --debug -S < %s 2>&1 | FileCheck %s
+
+; Call graph:
+;   A->C<-B
+;      |   
+;      v  
+;      D
+;      |
+;      v
+;      E
+
+define void @A() {
+    call void @C()
+    ret void
+}
+define internal void @B() {
+    call void @C()
+    ret void
+}
+define internal void @C() {
+    call void @D()
+    ret void
+}
+define internal void @D() {
+    call void @E()
+    ret void
+}
+define internal void @E() {
+    ret void
+}
+
+; Since we're inlining top-down A and B are the only valid callers
+; CHECK-NOT: Analyzing call of {{C|D|E}}... (caller:{{C|D}})
 No newline at end of file

llvm/test/Transforms/Inline/top-down-inliner-recursion.ll

+; RUN: opt -passes=module-inline -inline-priority-mode=top-down --debug -S < %s 2>&1 | FileCheck %s
+
+; Call graph:
+;      A
+;      |
+;      v
+;      B<-\ 
+;      |  |
+;      v  |
+;      C--/
+
+define void @A() {
+    call void @B();
+    ret void
+}
+define internal void @B() {
+    call void @C()
+    ret void
+}
+define internal void @C() {
+    call void @B()
+    ret void
+}
+
+; Check the top part of the call graph
+; CHECK: Analyzing call of B... (caller:A)
+; CHECK: Analyzing call of C... (caller:A)
+; Failed recursive call
+; CHECK: Inlining calls in: A 
+; The inlining order in the SCC may be arbitrary
+; CHECK: Analyzing call of {{B|C}}... (caller:{{B|C}})
+; CHECK: Analyzing call of {{B|C}}... (caller:{{B|C}})
+; CHECK: Analyzing call of {{B|C}}... (caller:{{B|C}})
 No newline at end of file

llvm/test/Transforms/Inline/top-down-inliner-simple.ll

+; RUN: opt -passes=module-inline -inline-priority-mode=top-down --debug -S < %s 2>&1 | FileCheck %s
+
+; Call graph:
+;   /--A--\
+;   |     |
+;   v     v
+;   B->D<-C
+;      |   
+;      v  
+;      E
+
+define void @A() {
+    call void @B()
+    call void @C()
+    ret void
+}
+define internal void @B() {
+    call void @D()
+    ret void
+}
+define internal void @C() {
+    call void @D()
+    ret void
+}
+define internal void @D() {
+    call void @E()
+    ret void
+}
+define internal void @E() {
+    ret void
+}
+
+; Since we're inlining top-down A is the only valid caller
+; CHECK-NOT: Analyzing call of {{B|C|D|E}}... (caller:{{B|C|D}})
 No newline at end of file