change implementation of DefaultInlineOrder & adjust API of DefaultInlineOrder

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 <deque>
 #include <functional>
 #include <sstream>
 #include <tuple>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
if (!IAA) {
     return *OwnedAdvisor;
   }
   assert(IAA->getAdvisor() &&
          "Expected a present InlineAdvisorAnalysis also have an "
          "InlineAdvisor initialized");
   return *IAA->getAdvisor();
 }
 
-class InlineOrder {
+template <typename T, typename Container> class InlineOrder {
 public:
-  using T = std::pair<CallBase *, int>;
-  using iterator = T *;
-  using const_iterator = const T *;
-  using reference = T &;
+  using iterator = typename Container::iterator;
+  using const_iterator = typename Container::const_iterator;
+  using reference = typename Container::reference;
 
   virtual ~InlineOrder() {}
 
   virtual size_t size() = 0;
-  virtual reference operator[](size_t idx) = 0;
-  virtual void push_back(const T &Elt) = 0;
-  virtual T pop() = 0;
+
+  virtual void push(const T &Elt) = 0;
+
+  virtual void pop() = 0;
+
+  virtual reference front() = 0;
+
   virtual iterator erase(const_iterator B, const_iterator E) = 0;
+
   virtual iterator begin() = 0;
   virtual iterator end() = 0;
 
   bool empty() { return !size(); }
 };
 
-class DefaultInlineOrder : public InlineOrder {
+template <typename T, typename Container = std::deque<T>>
+class DefaultInlineOrder : public InlineOrder<T, Container> {
+  using Base = InlineOrder<T, Container>;
+  using iterator = typename Base::iterator;
+  using const_iterator = typename Base::const_iterator;
+  using reference = typename Base::reference;
+
 public:
   size_t size() override { return Calls.size(); }
-  reference operator[](size_t idx) override { return Calls[idx]; }
-  void push_back(const T &Elt) override { Calls.push_back(Elt); }
-  T pop() override { return Calls.pop_back_val(); }
+
+  void push(const T &Elt) override { Calls.push_back(Elt); }
+
+  void pop() override { Calls.pop_front(); }
+
+  reference front() override { return Calls.front(); }
+
   iterator erase(const_iterator CB, const_iterator CE) override {
     return Calls.erase(CB, CE);
   }
+
   iterator begin() override { return Calls.begin(); }
   iterator end() override { return Calls.end(); }
 
 private:
-  SmallVector<T, 16> Calls;
+  Container Calls;
 };
 
 PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
                                    CGSCCAnalysisManager &AM, LazyCallGraph &CG,
                                    CGSCCUpdateResult &UR) {
   const auto &MAMProxy =
       AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG);
   bool Changed = false;
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 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,
   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) {
+  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)
       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(),
+              std::remove_if(Calls.begin(), 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;
         }
       }
       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