[Inliner] Retire DefaultInlineOrder (NFC)

[kazu]

Summary

DefaultInlineOrder was largely an exercise in generalizing the
traversal order of call sites within the inliner.

Now that the module inliner is starting to form its shape, there is no
point in sharing DefaultInlineOrder between the module inliner and the
CGSCC inliner. DefaultInlineOrder and all the other inline orders are
mutually exclusive in the following sense:

• The use of DefaultInlineOrder doesn't make sense in the module inliner because there is no priority inherent in the order in which call sites are added to the list of call sites -- SmallVector.

• The use of any other inline order doesn't make sense in the CGSCC inliner because little prioritization can be done within one CGSCC.

This patch essentially reverts the addition of DefaultInlineOrder so
that the loop structure of Inliner.cpp looks like the state just
before we started working on the module inliner (circa June 2021).

At the same time, ww remove the choice of DefaultInlineOrder from
UseInlinePriority.

llvm/include/llvm/Analysis/InlineOrder.h

 #include "llvm/IR/InstrTypes.h"
 #include <algorithm>
 #include <utility>
 
 namespace llvm {
 class CallBase;
 class Function;
 
-enum class InlinePriorityMode : int { NoPriority, Size, Cost, OptRatio };
+enum class InlinePriorityMode : int { Size, Cost, OptRatio };
 
 template <typename T> class InlineOrder {
 public:
   using reference = T &;
   using const_reference = const T &;
 
   virtual ~InlineOrder() = default;
 
public:
 
   bool empty() { return !size(); }
 };
 
 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
 getInlineOrder(InlinePriorityMode UseInlinePriority,
                FunctionAnalysisManager &FAM, const InlineParams &Params);
 
-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;
-};
-
 } // namespace llvm
 #endif // LLVM_ANALYSIS_INLINEORDER_H

llvm/lib/Analysis/InlineOrder.cpp

static llvm::InlineCost getInlineCostWrapper(CallBase &CB,
   return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
                        GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
 }
 
 std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>>
 llvm::getInlineOrder(InlinePriorityMode UseInlinePriority,
                      FunctionAnalysisManager &FAM, const InlineParams &Params) {
   switch (UseInlinePriority) {
-  case InlinePriorityMode::NoPriority:
-    return std::make_unique<DefaultInlineOrder<std::pair<CallBase *, int>>>();
-
   case InlinePriorityMode::Size:
     LLVM_DEBUG(dbgs() << "    Current used priority: Size priority ---- \n");
     return std::make_unique<PriorityInlineOrder>(
         std::make_unique<SizePriority>());
 
   case InlinePriorityMode::Cost:
     LLVM_DEBUG(dbgs() << "    Current used priority: Cost priority ---- \n");
     return std::make_unique<PriorityInlineOrder>(

llvm/lib/Transforms/IPO/Inliner.cpp

 #include "llvm/ADT/StringRef.h"
 #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/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/ReplayInlineAdvisor.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/Utils/ImportedFunctionsInliningStatistics.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
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.
-  DefaultInlineOrder<std::pair<CallBase *, int>> Calls;
+  SmallVector<std::pair<CallBase *, int>, 16> 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({CB, -1});
+            Calls.push_back({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,
   // 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;
 
   // Track potentially dead non-local functions with comdats to see if they can
   // be deleted as a batch after inlining.
   SmallVector<Function *, 4> DeadFunctionsInComdats;
 
-  // Loop forward over all of the calls.
-  while (!Calls.empty()) {
+  // 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) {
     // 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[I].first->getCaller();
     LazyCallGraph::Node &N = *CG.lookup(F);
-    if (CG.lookupSCC(N) != C) {
-      Calls.pop();
+    if (CG.lookupSCC(N) != C)
       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.pop();
+    for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) {
+      auto &P = Calls[I];
       CallBase *CB = P.first;
       const int InlineHistoryID = P.second;
       Function &Callee = *CB->getCalledFunction();
 
       if (InlineHistoryID != -1 &&
           inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
         LLVM_DEBUG(dbgs() << "Skipping inlining due to history: "
                           << F.getName() << " -> " << Callee.getName() << "\n");
for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) {
             // 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_back({ICB, NewHistoryID});
               // Continually inlining through an SCC can result in huge compile
               // times and bloated code since we arbitrarily stop at some point
               // when the inliner decides it's not profitable to inline anymore.
               // We attempt to mitigate this by making these calls exponentially
               // more expensive.
               // This doesn't apply to calls in the same SCC since if we do
               // inline through the SCC the function will end up being
               // self-recursive which the inliner bails out on, and inlining
for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) {
       // 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. Non-local
       // discardable functions with comdats are checked later on.
       bool CalleeWasDeleted = false;
       if (Callee.isDiscardableIfUnused() && Callee.hasZeroLiveUses() &&
           !CG.isLibFunction(Callee)) {
         if (Callee.hasLocalLinkage() || !Callee.hasComdat()) {
-          Calls.erase_if([&](const std::pair<CallBase *, int> &Call) {
+          Calls.erase(
+              std::remove_if(Calls.begin() + I + 1, Calls.end(),
+                             [&](const std::pair<CallBase *, int> &Call) {
                                return Call.first->getCaller() == &Callee;
-          });
+                             }),
+              Calls.end());
+
           // 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;
         } else {
           DeadFunctionsInComdats.push_back(&Callee);
         }
       }
       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

llvm/lib/Transforms/IPO/ModuleInliner.cpp

 #define DEBUG_TYPE "module-inline"
 
 STATISTIC(NumInlined, "Number of functions inlined");
 STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
 
 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::NoPriority, "no priority",
-                          "Use no priority, visit callsites in bottom-up."),
-               clEnumValN(InlinePriorityMode::Size, "size",
+    cl::values(clEnumValN(InlinePriorityMode::Size, "size",
                           "Use callee size priority."),
                clEnumValN(InlinePriorityMode::Cost, "cost",
                           "Use inline cost priority.")));
 
 /// Return true if the specified inline history ID
 /// indicates an inline history that includes the specified function.
 static bool inlineHistoryIncludes(
     Function *F, int InlineHistoryID,