Add interface to order inlining

[taolq]

Summary

This patch abstract Calls in Inliner:run to InlineOrder.
With this patch, we could customize the inlining order.

Now this patch is a minimal refactoring,
some works are still needed to be done.

[mtrofin]

I believe this is in the right direction.

I recommend informing the nuances of the API by trying first to replace all the uses of Calls (and the adjustment of the index iterating through Calls, line 906)

Please note the linter notes (virtual dtor, etc)

llvm/include/llvm/Analysis/InlineOrder.h

17 ↗

(On Diff #348509)

Since this is an abstraction meant for the inliner, I'd just define it in Inliner.cpp (i.e. no need for a header)

[kazu]

I also agree this is in the right direction. I've left some minor comments.

llvm/include/llvm/Analysis/InlineOrder.h

38 ↗

(On Diff #348509)

I would keep this private. If you need to accommodate functions like erase, just add a method to this class.

llvm/lib/Transforms/IPO/Inliner.cpp

766

I'd remove this line.

[taolq]

move codes from InlineOrder.h to Inliner.cpp

[taolq]

change impl of DefaultInlineOrder: SmallVector -> std::deque
remove operator[] from InlineOrder
replace usage of API of DefaultInlinOrder: indexing -> front() & pop()

[kazu]

Thanks for the update. I'd generalize the code around Call.erase a little bit more to accommodate other underlying data structures. See the comments below for details.

llvm/lib/Transforms/IPO/Inliner.cpp

67

Remove this if you use SmallVector. See below.

689

I would change this:

virtual void erase_if(function_ref<bool (CallBase *)> Pred) = 0;

where you would erase all elements satisfying Pred -- somewhat like erase_if in llvm/include/llvm/ADT/STLExtras.h.

I'm suggesting this because you need to heapify the contents after erasing elements if your underlying structure is a priority queue for example. std::remove_if removes items while maintaining the iteration order of surviving elements, but this property is specific to DefaultInlineOrder. Other inline orders may not be compatible with this property.

691–692

You shouldn't need these functions once you implement erase_if.

697

If we never add things to the front, I would stick to SmallVector and keep an index I to point to the first valid element just like the original code.

713

Change to erase_if accordingly.

717–718

Likewise, you shouldn't need these.

928–931

Change this to:

Calls.erase_if([&](CallBase *Call) { return Call->getCaller() == &Callee; });

This way, you shouldn't need begin or end.

[taolq]

• generalize Calls.erase
• simplify API

[kazu]

Thanks for updating the patch!

[dyung]

This change appears to be causing 6 or 7 lit tests to hang. Can you take a look and fix or revert?

https://lab.llvm.org/buildbot/#/builders/139/builds/5158 (7 tests hanging)
https://lab.llvm.org/buildbot/#/builders/43/builds/6983 (6 tests hanging)
https://lab.llvm.org/buildbot/#/builders/107/builds/8830 (6 tests hanging)
https://lab.llvm.org/buildbot/#/builders/110/builds/3878 (6 tests hanging)

[taolq]

In D103315#2801062, @dyung wrote:

This change appears to be causing 6 or 7 lit tests to hang. Can you take a look and fix or revert?

https://lab.llvm.org/buildbot/#/builders/139/builds/5158 (7 tests hanging)
https://lab.llvm.org/buildbot/#/builders/43/builds/6983 (6 tests hanging)
https://lab.llvm.org/buildbot/#/builders/107/builds/8830 (6 tests hanging)
https://lab.llvm.org/buildbot/#/builders/110/builds/3878 (6 tests hanging)

Thanks for reminding. I will tentatively revert it soon.

[thakis]

(Looks like the revert landed in 48252d7570bdf5ab77451d0f049047f1c40742dd)

[taolq]

• modify API & fix timeout test cases

[taolq]

In D103315#2801624, @thakis wrote:

(Looks like the revert landed in 48252d7570bdf5ab77451d0f049047f1c40742dd)

Now it's fixed and landed.

llvm/lib/Transforms/IPO/Inliner.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <algorithm>
 #include <cassert>
 #include <functional>
 #include <sstream>
 #include <tuple>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "inline"
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 &;
+
+  virtual ~InlineOrder() {}
+
+  virtual size_t size() = 0;
+
+  virtual void push(const T &Elt) = 0;
+
+  virtual void pop() = 0;
+
+  virtual 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 &;
+
+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 {
+    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;
+};
+
 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,
   // 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.
-  SmallVector<std::pair<CallBase *, int>, 16> Calls;
+  DefaultInlineOrder<std::pair<CallBase *, int>> 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))
         if (Function *Callee = CB->getCalledFunction()) {
           if (!Callee->isDeclaration())
-            Calls.push_back({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"
PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
   // 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. Note that we cannot cache the size as
-  // inlining can introduce new calls that need to be processed.
-  for (int I = 0; I < (int)Calls.size(); ++I) {
+  // Loop forward over all of the calls.
+  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[I].first->getCaller();
+    Function &F = *Calls.front().first->getCaller();
     LazyCallGraph::Node &N = *CG.lookup(F);
-    if (CG.lookupSCC(N) != C)
+    if (CG.lookupSCC(N) != C) {
+      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;
-    for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) {
-      auto &P = Calls[I];
+    while (!Calls.empty() && Calls.front().first->getCaller() == &F) {
+      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;
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_back({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(
-              std::remove_if(Calls.begin() + I + 1, Calls.end(),
-                             [&](const std::pair<CallBase *, int> &Call) {
-                               return Call.first->getCaller() == &Callee;
-                             }),
-              Calls.end());
+          Calls.erase_if([&](const std::pair<CallBase *, int> &Call) {
+          });
           // 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) &&
                  "Cannot put cause a function to become dead twice!");
           DeadFunctions.push_back(&Callee);
           CalleeWasDeleted = true;
         }
       }
       if (CalleeWasDeleted)
         Advice->recordInliningWithCalleeDeleted();
       else
         Advice->recordInlining();
     }
 
-    // Back the call index up by one to put us in a good position to go around
-    // the outer loop.
-    --I;
-
     if (!DidInline)
       continue;
     Changed = true;
 
     // At this point, since we have made changes we have at least removed
     // a call instruction. However, in the process we do some incremental
     // simplification of the surrounding code. This simplification can
     // essentially do all of the same things as a function pass and we can