diff --git a/llvm/include/llvm/Analysis/InlineOrder.h b/llvm/include/llvm/Analysis/InlineOrder.h --- a/llvm/include/llvm/Analysis/InlineOrder.h +++ b/llvm/include/llvm/Analysis/InlineOrder.h @@ -21,7 +21,7 @@ class CallBase; class Function; -enum class InlinePriorityMode : int { NoPriority, Size, Cost, OptRatio }; +enum class InlinePriorityMode : int { Size, Cost, OptRatio }; template class InlineOrder { public: @@ -47,35 +47,5 @@ getInlineOrder(InlinePriorityMode UseInlinePriority, FunctionAnalysisManager &FAM, const InlineParams &Params); -template > -class DefaultInlineOrder : public InlineOrder { - 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 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 diff --git a/llvm/lib/Analysis/InlineOrder.cpp b/llvm/lib/Analysis/InlineOrder.cpp --- a/llvm/lib/Analysis/InlineOrder.cpp +++ b/llvm/lib/Analysis/InlineOrder.cpp @@ -216,9 +216,6 @@ llvm::getInlineOrder(InlinePriorityMode UseInlinePriority, FunctionAnalysisManager &FAM, const InlineParams &Params) { switch (UseInlinePriority) { - case InlinePriorityMode::NoPriority: - return std::make_unique>>(); - case InlinePriorityMode::Size: LLVM_DEBUG(dbgs() << " Current used priority: Size priority ---- \n"); return std::make_unique( diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp --- a/llvm/lib/Transforms/IPO/Inliner.cpp +++ b/llvm/lib/Transforms/IPO/Inliner.cpp @@ -31,7 +31,6 @@ #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" @@ -785,7 +784,7 @@ // 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; + SmallVector, 16> Calls; // Populate the initial list of calls in this SCC. for (auto &N : InitialC) { @@ -800,7 +799,7 @@ if (auto *CB = dyn_cast(&I)) if (Function *Callee = CB->getCalledFunction()) { if (!Callee->isDeclaration()) - Calls.push({CB, -1}); + Calls.push_back({CB, -1}); else if (!isa(I)) { using namespace ore; setInlineRemark(*CB, "unavailable definition"); @@ -839,18 +838,17 @@ // be deleted as a batch after inlining. SmallVector 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() @@ -864,8 +862,8 @@ // 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(); @@ -949,7 +947,7 @@ } 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. @@ -984,9 +982,13 @@ if (Callee.isDiscardableIfUnused() && Callee.hasZeroLiveUses() && !CG.isLibFunction(Callee)) { if (Callee.hasLocalLinkage() || !Callee.hasComdat()) { - Calls.erase_if([&](const std::pair &Call) { - return Call.first->getCaller() == &Callee; - }); + Calls.erase( + std::remove_if(Calls.begin() + I + 1, Calls.end(), + [&](const std::pair &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 @@ -1006,6 +1008,10 @@ 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; diff --git a/llvm/lib/Transforms/IPO/ModuleInliner.cpp b/llvm/lib/Transforms/IPO/ModuleInliner.cpp --- a/llvm/lib/Transforms/IPO/ModuleInliner.cpp +++ b/llvm/lib/Transforms/IPO/ModuleInliner.cpp @@ -52,9 +52,7 @@ static cl::opt 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.")));