From 84369e51b213a0d4bdd16d1581e27dbf70925aa0 Mon Sep 17 00:00:00 2001 From: Philip Pfaffe Date: Mon, 15 May 2017 13:43:01 +0000 Subject: [PATCH] [Polly][NewPM][WIP] Add a ScopPassManager This patch adds both a ScopAnalysisManager and a ScopPassManager. The ScopAnalysisManager is itself a Function-Analysis, and manages analyses on Scops. The ScopPassManager takes care of building Scop pass pipelines. This patch is marked WIP because I've left two FIXMEs which I need to think about some more. Both of these deal with invalidation: Deferred invalidation is currently not implemented. Deferred invalidation deals with analyses which cache references to other analysis results. If these results are invalidated, invalidation needs to be propagated into the caching analyses. The ScopPassManager as implemented assumes that ScopPasses do not affect other Scops in any way. There has been some discussion about this on other patch threads, however it makes sense to reiterate this for this specific patch. I'm uploading this patch even though it's incomplete to encourage discussion and give you an impression of how this is going to work. Differential Revision: https://reviews.llvm.org/D33192 git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@303062 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/polly/ScopInfo.h | 6 ++ include/polly/ScopPass.h | 147 ++++++++++++++++++++++++++++++++++++++++++++++ lib/Analysis/ScopInfo.cpp | 2 +- lib/Analysis/ScopPass.cpp | 100 +++++++++++++++++++++++++++++++ unittests/CMakeLists.txt | 1 + 5 files changed, 255 insertions(+), 1 deletion(-) diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h index c56fa7c5..aa49c719 100644 --- a/include/polly/ScopInfo.h +++ b/include/polly/ScopInfo.h @@ -1572,6 +1572,9 @@ private: /// The underlying Region. Region &R; + /// The name of the SCoP (identical to the regions name) + std::string name; + // Access functions of the SCoP. // // This owns all the MemoryAccess objects of the Scop created in this pass. @@ -2201,6 +2204,8 @@ public: /// could be executed. bool isEmpty() const { return Stmts.empty(); } + const StringRef getName() const { return name; } + typedef ArrayInfoSetTy::iterator array_iterator; typedef ArrayInfoSetTy::const_iterator const_array_iterator; typedef iterator_range array_range; @@ -2795,6 +2800,7 @@ public: iterator end() { return RegionToScopMap.end(); } const_iterator begin() const { return RegionToScopMap.begin(); } const_iterator end() const { return RegionToScopMap.end(); } + bool empty() const { return RegionToScopMap.empty(); } }; struct ScopInfoAnalysis : public AnalysisInfoMixin { diff --git a/include/polly/ScopPass.h b/include/polly/ScopPass.h index 9f916bf8..573e613b 100644 --- a/include/polly/ScopPass.h +++ b/include/polly/ScopPass.h @@ -18,12 +18,86 @@ #ifndef POLLY_SCOP_PASS_H #define POLLY_SCOP_PASS_H +#include "polly/ScopInfo.h" +#include "llvm/ADT/PriorityWorklist.h" #include "llvm/Analysis/RegionPass.h" +#include "llvm/IR/PassManager.h" using namespace llvm; namespace polly { class Scop; +class SPMUpdater; +struct ScopStandardAnalysisResults; + +using ScopAnalysisManager = + AnalysisManager; +using ScopAnalysisManagerFunctionProxy = + InnerAnalysisManagerProxy; +using FunctionAnalysisManagerScopProxy = + OuterAnalysisManagerProxy; +} // namespace polly + +namespace llvm { +using polly::Scop; +using polly::ScopInfo; +using polly::ScopAnalysisManager; +using polly::ScopStandardAnalysisResults; +using polly::ScopAnalysisManagerFunctionProxy; +using polly::SPMUpdater; + +template <> +class InnerAnalysisManagerProxy::Result { +public: + explicit Result(ScopAnalysisManager &InnerAM, ScopInfo &SI) + : InnerAM(&InnerAM), SI(&SI) {} + Result(Result &&R) : InnerAM(std::move(R.InnerAM)), SI(R.SI) { + R.InnerAM = nullptr; + } + Result &operator=(Result &&RHS) { + InnerAM = RHS.InnerAM; + SI = RHS.SI; + RHS.InnerAM = nullptr; + return *this; + } + ~Result() { + if (!InnerAM) + return; + InnerAM->clear(); + } + + ScopAnalysisManager &getManager() { return *InnerAM; } + + bool invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv); + +private: + ScopAnalysisManager *InnerAM; + ScopInfo *SI; +}; + +template <> +InnerAnalysisManagerProxy::Result +InnerAnalysisManagerProxy::run( + Function &F, FunctionAnalysisManager &FAM); + +template <> +PreservedAnalyses +PassManager::run(Scop &InitialS, ScopAnalysisManager &AM, + ScopStandardAnalysisResults &, SPMUpdater &); +extern template class PassManager; +extern template class InnerAnalysisManagerProxy; +extern template class OuterAnalysisManagerProxy; +} // namespace llvm + +namespace polly { +using ScopPassManager = + PassManager; /// ScopPass - This class adapts the RegionPass interface to allow convenient /// creation of passes that operate on the Polly IR. Instead of overriding @@ -52,6 +126,79 @@ private: void print(raw_ostream &OS, const Module *) const override; }; +struct ScopStandardAnalysisResults { + DominatorTree &DT; + ScalarEvolution &SE; + LoopInfo &LI; + RegionInfo &RI; +}; + +class SPMUpdater { +public: + SPMUpdater(SmallPriorityWorklist &Worklist, + ScopAnalysisManager &SAM) + : Worklist(Worklist), SAM(SAM) {} + + void SkipScop(Scop &S) { + if (Worklist.erase(&S)) + SAM.clear(S); + } + +private: + SmallPriorityWorklist &Worklist; + ScopAnalysisManager &SAM; +}; + +template +class FunctionToScopPassAdaptor + : public PassInfoMixin> { +public: + explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { + PreservedAnalyses PA = PreservedAnalyses::all(); + auto &Scops = AM.getResult(F); + if (Scops.empty()) + return PA; + + ScopAnalysisManager &SAM = + AM.getResult(F).getManager(); + + ScopStandardAnalysisResults AR = {AM.getResult(F), + AM.getResult(F), + AM.getResult(F), + AM.getResult(F)}; + + SmallPriorityWorklist Worklist; + SPMUpdater Updater{Worklist, SAM}; + + for (auto &S : Scops) + if (auto *scop = S.second.get()) + Worklist.insert(scop); + + while (!Worklist.empty()) { + Scop *scop = Worklist.pop_back_val(); + PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR, Updater); + + SAM.invalidate(*scop, PassPA); + PA.intersect(std::move(PassPA)); + }; + + PA.preserveSet>(); + PA.preserve(); + return PA; + } + +private: + ScopPassT Pass; +}; // namespace polly + +template +FunctionToScopPassAdaptor +createFunctionToScopPassAdaptor(ScopPassT Pass) { + return FunctionToScopPassAdaptor(std::move(Pass)); +} + } // namespace polly #endif diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp index 5e566fb3..941566b9 100644 --- a/lib/Analysis/ScopInfo.cpp +++ b/lib/Analysis/ScopInfo.cpp @@ -3279,7 +3279,7 @@ static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) { Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI, ScopDetection::DetectionContext &DC) - : SE(&ScalarEvolution), R(R), IsOptimized(false), + : SE(&ScalarEvolution), R(R), name(R.getNameStr()), IsOptimized(false), HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false), MaxLoopDepth(0), CopyStmtsNum(0), DC(DC), IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr), diff --git a/lib/Analysis/ScopPass.cpp b/lib/Analysis/ScopPass.cpp index dbe90b8d..b385f682 100644 --- a/lib/Analysis/ScopPass.cpp +++ b/lib/Analysis/ScopPass.cpp @@ -14,6 +14,8 @@ #include "polly/ScopPass.h" #include "polly/ScopInfo.h" +#include "llvm/Analysis/AssumptionCache.h" + using namespace llvm; using namespace polly; @@ -35,3 +37,101 @@ void ScopPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.setPreservesAll(); } + +namespace llvm { + +template class PassManager; +template class InnerAnalysisManagerProxy; +template class OuterAnalysisManagerProxy; + +template <> +PreservedAnalyses +PassManager::run(Scop &S, ScopAnalysisManager &AM, + ScopStandardAnalysisResults &AR, SPMUpdater &U) { + auto PA = PreservedAnalyses::all(); + for (auto &Pass : Passes) { + auto PassPA = Pass->run(S, AM, AR, U); + + AM.invalidate(S, PassPA); + PA.intersect(std::move(PassPA)); + } + + // All analyses for 'this' Scop have been invalidated above. + // If ScopPasses affect break other scops they have to propagate this + // information through the updater + PA.preserveSet>(); + return PA; +} + +bool ScopAnalysisManagerFunctionProxy::Result::invalidate( + Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv) { + + // First, check whether our ScopInfo is about to be invalidated + auto PAC = PA.getChecker(); + if (!(PAC.preserved() || PAC.preservedSet>() || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA))) { + + // As everything depends on ScopInfo, we must drop all existing results + for (auto &S : *SI) + if (auto *scop = S.second.get()) + if (InnerAM) + InnerAM->clear(*scop); + + InnerAM = nullptr; + return true; // Invalidate the proxy result as well. + } + + bool allPreserved = PA.allAnalysesInSetPreserved>(); + + // Invalidate all non-preserved analyses + // Even if all analyses were preserved, we still need to run deferred + // invalidation + for (auto &S : *SI) { + Optional InnerPA; + auto *scop = S.second.get(); + if (!scop) + continue; + + if (auto *OuterProxy = + InnerAM->getCachedResult(*scop)) { + for (const auto &InvPair : OuterProxy->getOuterInvalidations()) { + auto *OuterAnalysisID = InvPair.first; + const auto &InnerAnalysisIDs = InvPair.second; + + if (Inv.invalidate(OuterAnalysisID, F, PA)) { + if (!InnerPA) + InnerPA = PA; + for (auto *InnerAnalysisID : InnerAnalysisIDs) + InnerPA->abandon(InnerAnalysisID); + } + } + + if (InnerPA) { + InnerAM->invalidate(*scop, *InnerPA); + continue; + } + } + + if (!allPreserved) + InnerAM->invalidate(*scop, PA); + } + + return false; // This proxy is still valid +} + +template <> +ScopAnalysisManagerFunctionProxy::Result +ScopAnalysisManagerFunctionProxy::run(Function &F, + FunctionAnalysisManager &FAM) { + return Result(*InnerAM, FAM.getResult(F)); +} +} // namespace llvm diff --git a/unittests/CMakeLists.txt b/unittests/CMakeLists.txt index e5e0f6c5..b7470580 100644 --- a/unittests/CMakeLists.txt +++ b/unittests/CMakeLists.txt @@ -22,3 +22,4 @@ endfunction() add_subdirectory(Isl) add_subdirectory(Flatten) add_subdirectory(DeLICM) +add_subdirectory(ScopPassManager) -- 2.11.4.GIT