From 248d55af3e446ad69a64f08cfcc4879f9690e580 Mon Sep 17 00:00:00 2001 From: Mircea Trofin Date: Mon, 10 Jan 2022 11:18:04 -0800 Subject: [PATCH] [NFC][MLGO] Use LazyCallGraph::Node to track functions. This avoids the InlineAdvisor carrying the responsibility of deleting Function objects. We use LazyCallGraph::Node objects instead, which are stable in memory for the duration of the Module-wide performance of CGSCC passes started under the same ModuleToPostOrderCGSCCPassAdaptor (which is the case here) Differential Revision: https://reviews.llvm.org/D116964 --- llvm/include/llvm/Analysis/InlineAdvisor.h | 21 +++------------------ llvm/include/llvm/Analysis/MLInlineAdvisor.h | 12 ++++++++---- llvm/lib/Analysis/DevelopmentModeInlineAdvisor.cpp | 2 -- llvm/lib/Analysis/InlineAdvisor.cpp | 15 --------------- llvm/lib/Analysis/MLInlineAdvisor.cpp | 19 +++++++++++++------ llvm/lib/Transforms/IPO/Inliner.cpp | 9 +-------- 6 files changed, 25 insertions(+), 53 deletions(-) diff --git a/llvm/include/llvm/Analysis/InlineAdvisor.h b/llvm/include/llvm/Analysis/InlineAdvisor.h index 9f9bc3a..0405ca5 100644 --- a/llvm/include/llvm/Analysis/InlineAdvisor.h +++ b/llvm/include/llvm/Analysis/InlineAdvisor.h @@ -65,7 +65,9 @@ public: /// Call after inlining succeeded, and did not result in deleting the callee. void recordInlining(); - /// Call after inlining succeeded, and resulted in deleting the callee. + /// Call after inlining succeeded, and results in the callee being + /// delete-able, meaning, it has no more users, and will be cleaned up + /// subsequently. void recordInliningWithCalleeDeleted(); /// Call after the decision for a call site was to not inline. @@ -178,19 +180,6 @@ protected: FunctionAnalysisManager &FAM; std::unique_ptr ImportedFunctionsStats; - /// We may want to defer deleting functions to after the inlining for a whole - /// module has finished. This allows us to reliably use function pointers as - /// unique identifiers, as an efficient implementation detail of the - /// InlineAdvisor. Otherwise, it is possible the memory allocator - /// re-allocate Function objects at the same address of a deleted Function; - /// and Functions are potentially created during the function passes called - /// after each SCC inlining (e.g. argument promotion does that). - void freeDeletedFunctions(); - - bool isFunctionDeleted(const Function *F) const { - return DeletedFunctions.count(F); - } - enum class MandatoryInliningKind { NotMandatory, Always, Never }; static MandatoryInliningKind getMandatoryKind(CallBase &CB, @@ -201,8 +190,6 @@ protected: private: friend class InlineAdvice; - void markFunctionAsDeleted(Function *F); - std::unordered_set DeletedFunctions; }; /// The default (manual heuristics) implementation of the InlineAdvisor. This @@ -217,8 +204,6 @@ public: private: std::unique_ptr getAdviceImpl(CallBase &CB) override; - void onPassExit() override { freeDeletedFunctions(); } - InlineParams Params; }; diff --git a/llvm/include/llvm/Analysis/MLInlineAdvisor.h b/llvm/include/llvm/Analysis/MLInlineAdvisor.h index a218561..3d2d508 100644 --- a/llvm/include/llvm/Analysis/MLInlineAdvisor.h +++ b/llvm/include/llvm/Analysis/MLInlineAdvisor.h @@ -9,8 +9,8 @@ #ifndef LLVM_ANALYSIS_MLINLINEADVISOR_H #define LLVM_ANALYSIS_MLINLINEADVISOR_H -#include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/InlineAdvisor.h" +#include "llvm/Analysis/LazyCallGraph.h" #include "llvm/Analysis/MLModelRunner.h" #include "llvm/IR/PassManager.h" @@ -26,7 +26,6 @@ public: MLInlineAdvisor(Module &M, ModuleAnalysisManager &MAM, std::unique_ptr ModelRunner); - CallGraph *callGraph() const { return CG.get(); } virtual ~MLInlineAdvisor() = default; void onPassEntry() override; @@ -51,17 +50,22 @@ protected: virtual std::unique_ptr getAdviceFromModel(CallBase &CB, OptimizationRemarkEmitter &ORE); + // Get the initial 'level' of the function, or 0 if the function has been + // introduced afterwards. + // TODO: should we keep this updated? + unsigned getInitialFunctionLevel(const Function &F) const; + std::unique_ptr ModelRunner; private: int64_t getModuleIRSize() const; bool Invalid = true; - std::unique_ptr CG; + LazyCallGraph &CG; int64_t NodeCount = 0; int64_t EdgeCount = 0; - std::map FunctionLevels; + std::map FunctionLevels; const int32_t InitialIRSize = 0; int32_t CurrentIRSize = 0; diff --git a/llvm/lib/Analysis/DevelopmentModeInlineAdvisor.cpp b/llvm/lib/Analysis/DevelopmentModeInlineAdvisor.cpp index 26bdbda..94a60f6 100644 --- a/llvm/lib/Analysis/DevelopmentModeInlineAdvisor.cpp +++ b/llvm/lib/Analysis/DevelopmentModeInlineAdvisor.cpp @@ -412,8 +412,6 @@ size_t DevelopmentModeMLInlineAdvisor::getTotalSizeEstimate() { for (auto &F : M) { if (F.isDeclaration()) continue; - if (isFunctionDeleted(&F)) - continue; Ret += *getNativeSizeEstimate(F); } return Ret; diff --git a/llvm/lib/Analysis/InlineAdvisor.cpp b/llvm/lib/Analysis/InlineAdvisor.cpp index 140c88e..a0d8ce8 100644 --- a/llvm/lib/Analysis/InlineAdvisor.cpp +++ b/llvm/lib/Analysis/InlineAdvisor.cpp @@ -160,18 +160,6 @@ InlineAdvice::InlineAdvice(InlineAdvisor *Advisor, CallBase &CB, DLoc(CB.getDebugLoc()), Block(CB.getParent()), ORE(ORE), IsInliningRecommended(IsInliningRecommended) {} -void InlineAdvisor::markFunctionAsDeleted(Function *F) { - assert((!DeletedFunctions.count(F)) && - "Cannot put cause a function to become dead twice!"); - DeletedFunctions.insert(F); -} - -void InlineAdvisor::freeDeletedFunctions() { - for (auto *F : DeletedFunctions) - delete F; - DeletedFunctions.clear(); -} - void InlineAdvice::recordInlineStatsIfNeeded() { if (Advisor->ImportedFunctionsStats) Advisor->ImportedFunctionsStats->recordInline(*Caller, *Callee); @@ -186,7 +174,6 @@ void InlineAdvice::recordInlining() { void InlineAdvice::recordInliningWithCalleeDeleted() { markRecorded(); recordInlineStatsIfNeeded(); - Advisor->markFunctionAsDeleted(Callee); recordInliningWithCalleeDeletedImpl(); } @@ -523,8 +510,6 @@ InlineAdvisor::~InlineAdvisor() { ImportedFunctionsStats->dump(InlinerFunctionImportStats == InlinerFunctionImportStatsOpts::Verbose); } - - freeDeletedFunctions(); } std::unique_ptr InlineAdvisor::getMandatoryAdvice(CallBase &CB, diff --git a/llvm/lib/Analysis/MLInlineAdvisor.cpp b/llvm/lib/Analysis/MLInlineAdvisor.cpp index f5a65cd..83f118b 100644 --- a/llvm/lib/Analysis/MLInlineAdvisor.cpp +++ b/llvm/lib/Analysis/MLInlineAdvisor.cpp @@ -22,6 +22,7 @@ #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/FunctionPropertiesAnalysis.h" #include "llvm/Analysis/InlineCost.h" +#include "llvm/Analysis/LazyCallGraph.h" #include "llvm/Analysis/MLInlineAdvisor.h" #include "llvm/Analysis/MLModelRunner.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" @@ -90,7 +91,8 @@ MLInlineAdvisor::MLInlineAdvisor(Module &M, ModuleAnalysisManager &MAM, std::unique_ptr Runner) : InlineAdvisor( M, MAM.getResult(M).getManager()), - ModelRunner(std::move(Runner)), CG(new CallGraph(M)), + ModelRunner(std::move(Runner)), + CG(MAM.getResult(M)), InitialIRSize(getModuleIRSize()), CurrentIRSize(InitialIRSize) { assert(ModelRunner); @@ -100,7 +102,8 @@ MLInlineAdvisor::MLInlineAdvisor(Module &M, ModuleAnalysisManager &MAM, // critical in behavioral cloning - i.e. training a model to mimic the manual // heuristic's decisions - and, thus, equally important for training for // improvement. - for (auto I = scc_begin(CG.get()); !I.isAtEnd(); ++I) { + CallGraph CGraph(M); + for (auto I = scc_begin(&CGraph); !I.isAtEnd(); ++I) { const std::vector &CGNodes = *I; unsigned Level = 0; for (auto *CGNode : CGNodes) { @@ -110,7 +113,7 @@ MLInlineAdvisor::MLInlineAdvisor(Module &M, ModuleAnalysisManager &MAM, for (auto &I : instructions(F)) { if (auto *CS = getInlinableCS(I)) { auto *Called = CS->getCalledFunction(); - auto Pos = FunctionLevels.find(Called); + auto Pos = FunctionLevels.find(&CG.get(*Called)); // In bottom up traversal, an inlinable callee is either in the // same SCC, or to a function in a visited SCC. So not finding its // level means we haven't visited it yet, meaning it's in this SCC. @@ -123,11 +126,15 @@ MLInlineAdvisor::MLInlineAdvisor(Module &M, ModuleAnalysisManager &MAM, for (auto *CGNode : CGNodes) { Function *F = CGNode->getFunction(); if (F && !F->isDeclaration()) - FunctionLevels[F] = Level; + FunctionLevels[&CG.get(*F)] = Level; } } } +unsigned MLInlineAdvisor::getInitialFunctionLevel(const Function &F) const { + return CG.lookup(F) ? FunctionLevels.at(CG.lookup(F)) : 0; +} + void MLInlineAdvisor::onPassEntry() { // Function passes executed between InlinerPass runs may have changed the // module-wide features. @@ -192,7 +199,7 @@ void MLInlineAdvisor::onSuccessfulInlining(const MLInlineAdvice &Advice, int64_t MLInlineAdvisor::getModuleIRSize() const { int64_t Ret = 0; - for (auto &F : CG->getModule()) + for (auto &F : M) if (!F.isDeclaration()) Ret += getIRSize(F); return Ret; @@ -263,7 +270,7 @@ std::unique_ptr MLInlineAdvisor::getAdviceImpl(CallBase &CB) { *ModelRunner->getTensor(FeatureIndex::CalleeBasicBlockCount) = CalleeBefore.BasicBlockCount; *ModelRunner->getTensor(FeatureIndex::CallSiteHeight) = - FunctionLevels[&Caller]; + getInitialFunctionLevel(Caller); *ModelRunner->getTensor(FeatureIndex::NodeCount) = NodeCount; *ModelRunner->getTensor(FeatureIndex::NrCtantParams) = NrCtantParams; *ModelRunner->getTensor(FeatureIndex::EdgeCount) = EdgeCount; diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp index be34559..c5527c7 100644 --- a/llvm/lib/Transforms/IPO/Inliner.cpp +++ b/llvm/lib/Transforms/IPO/Inliner.cpp @@ -1045,14 +1045,7 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, UR.UpdatedC = nullptr; // And delete the actual function from the module. - // The Advisor may use Function pointers to efficiently index various - // internal maps, e.g. for memoization. Function cleanup passes like - // argument promotion create new functions. It is possible for a new - // function to be allocated at the address of a deleted function. We could - // index using names, but that's inefficient. Alternatively, we let the - // Advisor free the functions when it sees fit. - DeadF->getBasicBlockList().clear(); - M.getFunctionList().remove(DeadF); + M.getFunctionList().erase(DeadF); ++NumDeleted; } -- 2.7.4