From 6e30a9cc08f11e4a8b41413096b36ddf4c4b3f44 Mon Sep 17 00:00:00 2001 From: Kazu Hirata Date: Fri, 16 Sep 2022 15:36:40 -0700 Subject: [PATCH] [Inliner] Retire DefaultInlineOrder (NFC) 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. Differential Revision: https://reviews.llvm.org/D134080 --- llvm/include/llvm/Analysis/InlineOrder.h | 32 +-------------------------- llvm/lib/Analysis/InlineOrder.cpp | 3 --- llvm/lib/Transforms/IPO/Inliner.cpp | 36 ++++++++++++++++++------------- llvm/lib/Transforms/IPO/ModuleInliner.cpp | 4 +--- 4 files changed, 23 insertions(+), 52 deletions(-) diff --git a/llvm/include/llvm/Analysis/InlineOrder.h b/llvm/include/llvm/Analysis/InlineOrder.h index 18f4fed..1ce920e 100644 --- a/llvm/include/llvm/Analysis/InlineOrder.h +++ b/llvm/include/llvm/Analysis/InlineOrder.h @@ -21,7 +21,7 @@ namespace llvm { 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 @@ std::unique_ptr>> 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 index 9461162..295983b 100644 --- a/llvm/lib/Analysis/InlineOrder.cpp +++ b/llvm/lib/Analysis/InlineOrder.cpp @@ -216,9 +216,6 @@ std::unique_ptr>> 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 index 4d32266..3615199 100644 --- 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 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, // 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 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, 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 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, // 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 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, // 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 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, } 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 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, 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 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, 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 index ac9b2ec..eddccbb 100644 --- a/llvm/lib/Transforms/IPO/ModuleInliner.cpp +++ b/llvm/lib/Transforms/IPO/ModuleInliner.cpp @@ -52,9 +52,7 @@ STATISTIC(NumDeleted, "Number of functions deleted because all callers found"); 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."))); -- 2.7.4