From 105642af5eef694332b7181e0b333215d211332b Mon Sep 17 00:00:00 2001 From: Reid Kleckner Date: Fri, 31 Jan 2020 16:05:32 -0800 Subject: [PATCH] Add PassManagerImpl.h to hide implementation details ClangBuildAnalyzer results show that a lot of time is spent instantiating AnalysisManager::getResultImpl across the code base: **** Templates that took longest to instantiate: 50445 ms: llvm::AnalysisManager::getResultImpl (412 times, avg 122 ms) 47797 ms: llvm::AnalysisManager::getResult (389 times, avg 122 ms) 46894 ms: std::tie (2452 times, avg 19 ms) 43851 ms: llvm::BumpPtrAllocatorImpl::Allocate (3228 times, avg 13 ms) 33911 ms: std::tie (897 times, avg 37 ms) 33854 ms: std::tie (1897 times, avg 17 ms) 27886 ms: std::basic_string, std::allocator >::basic_string (11156 times, avg 2 ms) I mentioned this result to @chandlerc, and he suggested this direction. AnalysisManager is already explicitly instantiated, and getResultImpl doesn't need to be inlined. Move the definition to an Impl header, and include that header in files that explicitly instantiate AnalysisManager. There are only four (real) IR units: - function - module - loop - cgscc Looking at a specific transform (ArgumentPromotion.cpp), here are three compilations before & after this change: BEFORE: $ for i in $(seq 3) ; do ./ccit.bat ; done peak memory: 258.15MB real: 0m6.297s peak memory: 257.54MB real: 0m5.906s peak memory: 257.47MB real: 0m6.219s AFTER: $ for i in $(seq 3) ; do ./ccit.bat ; done peak memory: 235.35MB real: 0m5.454s peak memory: 234.72MB real: 0m5.235s peak memory: 234.39MB real: 0m5.469s The 20MB of memory saved seems real, and the time improvement seems like it is there. Reviewed By: MaskRay Differential Revision: https://reviews.llvm.org/D73817 --- llvm/include/llvm/IR/PassManager.h | 119 ++-------------------- llvm/include/llvm/IR/PassManagerImpl.h | 157 ++++++++++++++++++++++++++++++ llvm/lib/Analysis/CGSCCPassManager.cpp | 1 + llvm/lib/Analysis/LoopAnalysisManager.cpp | 1 + llvm/lib/IR/PassManager.cpp | 1 + llvm/unittests/IR/PassManagerTest.cpp | 1 + 6 files changed, 167 insertions(+), 113 deletions(-) create mode 100644 llvm/include/llvm/IR/PassManagerImpl.h diff --git a/llvm/include/llvm/IR/PassManager.h b/llvm/include/llvm/IR/PassManager.h index 58591ab..751c8f8 100644 --- a/llvm/include/llvm/IR/PassManager.h +++ b/llvm/include/llvm/IR/PassManager.h @@ -727,9 +727,9 @@ public: /// Construct an empty analysis manager. /// /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs(). - AnalysisManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {} - AnalysisManager(AnalysisManager &&) = default; - AnalysisManager &operator=(AnalysisManager &&) = default; + AnalysisManager(bool DebugLogging = false); + AnalysisManager(AnalysisManager &&); + AnalysisManager &operator=(AnalysisManager &&); /// Returns true if the analysis manager has an empty results cache. bool empty() const { @@ -744,20 +744,7 @@ public: /// This doesn't invalidate, but instead simply deletes, the relevant results. /// It is useful when the IR is being removed and we want to clear out all the /// memory pinned for it. - void clear(IRUnitT &IR, llvm::StringRef Name) { - if (DebugLogging) - dbgs() << "Clearing all analysis results for: " << Name << "\n"; - - auto ResultsListI = AnalysisResultLists.find(&IR); - if (ResultsListI == AnalysisResultLists.end()) - return; - // Delete the map entries that point into the results list. - for (auto &IDAndResult : ResultsListI->second) - AnalysisResults.erase({IDAndResult.first, &IR}); - - // And actually destroy and erase the results associated with this IR. - AnalysisResultLists.erase(ResultsListI); - } + void clear(IRUnitT &IR, llvm::StringRef Name); /// Clear all analysis results cached by this AnalysisManager. /// @@ -856,67 +843,7 @@ public: /// /// Walk through all of the analyses pertaining to this unit of IR and /// invalidate them, unless they are preserved by the PreservedAnalyses set. - void invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { - // We're done if all analyses on this IR unit are preserved. - if (PA.allAnalysesInSetPreserved>()) - return; - - if (DebugLogging) - dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName() - << "\n"; - - // Track whether each analysis's result is invalidated in - // IsResultInvalidated. - SmallDenseMap IsResultInvalidated; - Invalidator Inv(IsResultInvalidated, AnalysisResults); - AnalysisResultListT &ResultsList = AnalysisResultLists[&IR]; - for (auto &AnalysisResultPair : ResultsList) { - // This is basically the same thing as Invalidator::invalidate, but we - // can't call it here because we're operating on the type-erased result. - // Moreover if we instead called invalidate() directly, it would do an - // unnecessary look up in ResultsList. - AnalysisKey *ID = AnalysisResultPair.first; - auto &Result = *AnalysisResultPair.second; - - auto IMapI = IsResultInvalidated.find(ID); - if (IMapI != IsResultInvalidated.end()) - // This result was already handled via the Invalidator. - continue; - - // Try to invalidate the result, giving it the Invalidator so it can - // recursively query for any dependencies it has and record the result. - // Note that we cannot reuse 'IMapI' here or pre-insert the ID, as - // Result.invalidate may insert things into the map, invalidating our - // iterator. - bool Inserted = - IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, Inv)}) - .second; - (void)Inserted; - assert(Inserted && "Should never have already inserted this ID, likely " - "indicates a cycle!"); - } - - // Now erase the results that were marked above as invalidated. - if (!IsResultInvalidated.empty()) { - for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) { - AnalysisKey *ID = I->first; - if (!IsResultInvalidated.lookup(ID)) { - ++I; - continue; - } - - if (DebugLogging) - dbgs() << "Invalidating analysis: " << this->lookUpPass(ID).name() - << " on " << IR.getName() << "\n"; - - I = ResultsList.erase(I); - AnalysisResults.erase({ID, &IR}); - } - } - - if (ResultsList.empty()) - AnalysisResultLists.erase(&IR); - } + void invalidate(IRUnitT &IR, const PreservedAnalyses &PA); private: /// Look up a registered analysis pass. @@ -937,41 +864,7 @@ private: /// Get an analysis result, running the pass if necessary. ResultConceptT &getResultImpl(AnalysisKey *ID, IRUnitT &IR, - ExtraArgTs... ExtraArgs) { - typename AnalysisResultMapT::iterator RI; - bool Inserted; - std::tie(RI, Inserted) = AnalysisResults.insert(std::make_pair( - std::make_pair(ID, &IR), typename AnalysisResultListT::iterator())); - - // If we don't have a cached result for this function, look up the pass and - // run it to produce a result, which we then add to the cache. - if (Inserted) { - auto &P = this->lookUpPass(ID); - if (DebugLogging) - dbgs() << "Running analysis: " << P.name() << " on " << IR.getName() - << "\n"; - - PassInstrumentation PI; - if (ID != PassInstrumentationAnalysis::ID()) { - PI = getResult(IR, ExtraArgs...); - PI.runBeforeAnalysis(P, IR); - } - - AnalysisResultListT &ResultList = AnalysisResultLists[&IR]; - ResultList.emplace_back(ID, P.run(IR, *this, ExtraArgs...)); - - PI.runAfterAnalysis(P, IR); - - // P.run may have inserted elements into AnalysisResults and invalidated - // RI. - RI = AnalysisResults.find({ID, &IR}); - assert(RI != AnalysisResults.end() && "we just inserted it!"); - - RI->second = std::prev(ResultList.end()); - } - - return *RI->second->second; - } + ExtraArgTs... ExtraArgs); /// Get a cached analysis result or return null. ResultConceptT *getCachedResultImpl(AnalysisKey *ID, IRUnitT &IR) const { diff --git a/llvm/include/llvm/IR/PassManagerImpl.h b/llvm/include/llvm/IR/PassManagerImpl.h new file mode 100644 index 0000000..978655a --- /dev/null +++ b/llvm/include/llvm/IR/PassManagerImpl.h @@ -0,0 +1,157 @@ +//===- PassManagerImpl.h - Pass management infrastructure -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// +/// Provides implementations for PassManager and AnalysisManager template +/// methods. These classes should be explicitly instantiated for any IR unit, +/// and files doing the explicit instantiation should include this header. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_IR_PASSMANAGERIMPL_H +#define LLVM_IR_PASSMANAGERIMPL_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +template +inline AnalysisManager::AnalysisManager( + bool DebugLogging) + : DebugLogging(DebugLogging) {} + +template +inline AnalysisManager::AnalysisManager( + AnalysisManager &&) = default; + +template +inline AnalysisManager & +AnalysisManager::operator=(AnalysisManager &&) = + default; + +template +inline void +AnalysisManager::clear(IRUnitT &IR, + llvm::StringRef Name) { + if (DebugLogging) + dbgs() << "Clearing all analysis results for: " << Name << "\n"; + + auto ResultsListI = AnalysisResultLists.find(&IR); + if (ResultsListI == AnalysisResultLists.end()) + return; + // Delete the map entries that point into the results list. + for (auto &IDAndResult : ResultsListI->second) + AnalysisResults.erase({IDAndResult.first, &IR}); + + // And actually destroy and erase the results associated with this IR. + AnalysisResultLists.erase(ResultsListI); +} + +template +inline typename AnalysisManager::ResultConceptT & +AnalysisManager::getResultImpl( + AnalysisKey *ID, IRUnitT &IR, ExtraArgTs... ExtraArgs) { + typename AnalysisResultMapT::iterator RI; + bool Inserted; + std::tie(RI, Inserted) = AnalysisResults.insert(std::make_pair( + std::make_pair(ID, &IR), typename AnalysisResultListT::iterator())); + + // If we don't have a cached result for this function, look up the pass and + // run it to produce a result, which we then add to the cache. + if (Inserted) { + auto &P = this->lookUpPass(ID); + if (DebugLogging) + dbgs() << "Running analysis: " << P.name() << " on " << IR.getName() + << "\n"; + + PassInstrumentation PI; + if (ID != PassInstrumentationAnalysis::ID()) { + PI = getResult(IR, ExtraArgs...); + PI.runBeforeAnalysis(P, IR); + } + + AnalysisResultListT &ResultList = AnalysisResultLists[&IR]; + ResultList.emplace_back(ID, P.run(IR, *this, ExtraArgs...)); + + PI.runAfterAnalysis(P, IR); + + // P.run may have inserted elements into AnalysisResults and invalidated + // RI. + RI = AnalysisResults.find({ID, &IR}); + assert(RI != AnalysisResults.end() && "we just inserted it!"); + + RI->second = std::prev(ResultList.end()); + } + + return *RI->second->second; +} + +template +inline void AnalysisManager::invalidate( + IRUnitT &IR, const PreservedAnalyses &PA) { + // We're done if all analyses on this IR unit are preserved. + if (PA.allAnalysesInSetPreserved>()) + return; + + if (DebugLogging) + dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName() + << "\n"; + + // Track whether each analysis's result is invalidated in + // IsResultInvalidated. + SmallDenseMap IsResultInvalidated; + Invalidator Inv(IsResultInvalidated, AnalysisResults); + AnalysisResultListT &ResultsList = AnalysisResultLists[&IR]; + for (auto &AnalysisResultPair : ResultsList) { + // This is basically the same thing as Invalidator::invalidate, but we + // can't call it here because we're operating on the type-erased result. + // Moreover if we instead called invalidate() directly, it would do an + // unnecessary look up in ResultsList. + AnalysisKey *ID = AnalysisResultPair.first; + auto &Result = *AnalysisResultPair.second; + + auto IMapI = IsResultInvalidated.find(ID); + if (IMapI != IsResultInvalidated.end()) + // This result was already handled via the Invalidator. + continue; + + // Try to invalidate the result, giving it the Invalidator so it can + // recursively query for any dependencies it has and record the result. + // Note that we cannot reuse 'IMapI' here or pre-insert the ID, as + // Result.invalidate may insert things into the map, invalidating our + // iterator. + bool Inserted = + IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, Inv)}).second; + (void)Inserted; + assert(Inserted && "Should never have already inserted this ID, likely " + "indicates a cycle!"); + } + + // Now erase the results that were marked above as invalidated. + if (!IsResultInvalidated.empty()) { + for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) { + AnalysisKey *ID = I->first; + if (!IsResultInvalidated.lookup(ID)) { + ++I; + continue; + } + + if (DebugLogging) + dbgs() << "Invalidating analysis: " << this->lookUpPass(ID).name() + << " on " << IR.getName() << "\n"; + + I = ResultsList.erase(I); + AnalysisResults.erase({ID, &IR}); + } + } + + if (ResultsList.empty()) + AnalysisResultLists.erase(&IR); +} +} // end namespace llvm + +#endif // LLVM_IR_PASSMANAGERIMPL_H diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp index 4485c3d..0aa1704 100644 --- a/llvm/lib/Analysis/CGSCCPassManager.cpp +++ b/llvm/lib/Analysis/CGSCCPassManager.cpp @@ -20,6 +20,7 @@ #include "llvm/IR/InstIterator.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/PassManager.h" +#include "llvm/IR/PassManagerImpl.h" #include "llvm/Support/Casting.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" diff --git a/llvm/lib/Analysis/LoopAnalysisManager.cpp b/llvm/lib/Analysis/LoopAnalysisManager.cpp index 02d40fb..21017c0 100644 --- a/llvm/lib/Analysis/LoopAnalysisManager.cpp +++ b/llvm/lib/Analysis/LoopAnalysisManager.cpp @@ -14,6 +14,7 @@ #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/IR/Dominators.h" +#include "llvm/IR/PassManagerImpl.h" using namespace llvm; diff --git a/llvm/lib/IR/PassManager.cpp b/llvm/lib/IR/PassManager.cpp index cde9b87..a8aa1e1 100644 --- a/llvm/lib/IR/PassManager.cpp +++ b/llvm/lib/IR/PassManager.cpp @@ -9,6 +9,7 @@ #include "llvm/IR/PassManager.h" #include "llvm/ADT/STLExtras.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/IR/PassManagerImpl.h" using namespace llvm; diff --git a/llvm/unittests/IR/PassManagerTest.cpp b/llvm/unittests/IR/PassManagerTest.cpp index 4d644d8..5b1f902 100644 --- a/llvm/unittests/IR/PassManagerTest.cpp +++ b/llvm/unittests/IR/PassManagerTest.cpp @@ -11,6 +11,7 @@ #include "llvm/IR/Function.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" +#include "llvm/IR/PassManagerImpl.h" #include "llvm/Support/SourceMgr.h" #include "gtest/gtest.h" -- 2.7.4