[Polly][PM] Improve invalidation in the Scop-Pipeline

pfaffe · pfaffe · commit f43e7c2e9733 · 2017-08-10T07:43:46.000Z
Summary: During code generation for a Scop we modify the IR of a function. While this shouldn't affect a Scop in the formal sense, the implementation caches various information about the IR such as SCEV expressions for bounds or parameters. This cached information needs to be updated or invalidated. To this end, SPMUpdater allows passes to report when they've invalidated a Scop to the PassManager, which will then flush and recompute all Scops. This in turn invalidates all iterators, so references to Scops shouldn't be held. Reviewers: grosser, Meinersbur, bollu Reviewed By: grosser Subscribers: llvm-commits, pollydev Differential Revision: https://reviews.llvm.org/D36524 llvm-svn: 310551
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
@@ -3044,6 +3044,13 @@ class ScopInfo {
   /// A map of Region to its Scop object containing
   ///        Polly IR of static control part.
   RegionToScopMapTy RegionToScopMap;
+  const DataLayout &DL;
+  ScopDetection &SD;
+  ScalarEvolution &SE;
+  LoopInfo &LI;
+  AliasAnalysis &AA;
+  DominatorTree &DT;
+  AssumptionCache &AC;
 
 public:
   ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
@@ -3063,6 +3070,15 @@ class ScopInfo {
     return nullptr;
   }
 
+  /// Recompute the Scop-Information for a function.
+  ///
+  /// This invalidates any iterators.
+  void recompute();
+
+  /// Handle invalidation explicitly
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &Inv);
+
   iterator begin() { return RegionToScopMap.begin(); }
   iterator end() { return RegionToScopMap.end(); }
   const_iterator begin() const { return RegionToScopMap.begin(); }
diff --git a/polly/include/polly/ScopPass.h b/polly/include/polly/ScopPass.h
@@ -180,18 +180,26 @@ struct ScopStandardAnalysisResults {
 
 class SPMUpdater {
 public:
-  SPMUpdater(SmallPriorityWorklist<Scop *, 4> &Worklist,
+  SPMUpdater(SmallPriorityWorklist<Region *, 4> &Worklist,
              ScopAnalysisManager &SAM)
-      : Worklist(Worklist), SAM(SAM) {}
+      : Worklist(Worklist), SAM(SAM), InvalidateCurrentScop(false) {}
 
-  void SkipScop(Scop &S) {
-    if (Worklist.erase(&S))
-      SAM.clear(S);
+  bool invalidateCurrentScop() const { return InvalidateCurrentScop; }
+
+  void invalidateScop(Scop &S) {
+    if (&S == CurrentScop)
+      InvalidateCurrentScop = true;
+
+    Worklist.erase(&S.getRegion());
+    SAM.clear(S);
   }
 
 private:
-  SmallPriorityWorklist<Scop *, 4> &Worklist;
+  Scop *CurrentScop;
+  bool InvalidateCurrentScop;
+  SmallPriorityWorklist<Region *, 4> &Worklist;
   ScopAnalysisManager &SAM;
+  template <typename ScopPassT> friend class FunctionToScopPassAdaptor;
 };
 
 template <typename ScopPassT>
@@ -202,10 +210,16 @@ class FunctionToScopPassAdaptor
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
     PreservedAnalyses PA = PreservedAnalyses::all();
-    auto &Scops = AM.getResult<ScopInfoAnalysis>(F);
-    if (Scops.empty())
+    auto &SD = AM.getResult<ScopAnalysis>(F);
+    auto &SI = AM.getResult<ScopInfoAnalysis>(F);
+    if (SI.empty())
       return PA;
 
+    SmallPriorityWorklist<Region *, 4> Worklist;
+    for (auto &S : SI)
+      if (S.second)
+        Worklist.insert(S.first);
+
     ScopStandardAnalysisResults AR = {AM.getResult<DominatorTreeAnalysis>(F),
                                       AM.getResult<ScopInfoAnalysis>(F),
                                       AM.getResult<ScalarEvolutionAnalysis>(F),
@@ -215,19 +229,23 @@ class FunctionToScopPassAdaptor
     ScopAnalysisManager &SAM =
         AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager();
 
-    SmallPriorityWorklist<Scop *, 4> 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();
+      Region *R = Worklist.pop_back_val();
+      if (!SD.isMaxRegionInScop(*R))
+        continue;
+      Scop *scop = SI.getScop(R);
+      if (!scop)
+        continue;
+      Updater.CurrentScop = scop;
+      Updater.InvalidateCurrentScop = false;
       PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR, Updater);
 
       SAM.invalidate(*scop, PassPA);
       PA.intersect(std::move(PassPA));
+      if (Updater.invalidateCurrentScop())
+        SI.recompute();
     };
 
     PA.preserveSet<AllAnalysesOn<Scop>>();
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
@@ -5227,7 +5227,13 @@ INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops",
 //===----------------------------------------------------------------------===//
 ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
                    LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,
-                   AssumptionCache &AC) {
+                   AssumptionCache &AC)
+    : DL(DL), SD(SD), SE(SE), LI(LI), AA(AA), DT(DT), AC(AC) {
+  recompute();
+}
+
+void ScopInfo::recompute() {
+  RegionToScopMap.clear();
   /// Create polyhedral description of scops for all the valid regions of a
   /// function.
   for (auto &It : SD) {
@@ -5248,6 +5254,20 @@ ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
   }
 }
 
+bool ScopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
+                          FunctionAnalysisManager::Invalidator &Inv) {
+  // Check whether the analysis, all analyses on functions have been preserved
+  // or anything we're holding references to is being invalidated
+  auto PAC = PA.getChecker<ScopInfoAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
+         Inv.invalidate<ScopAnalysis>(F, PA) ||
+         Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
+         Inv.invalidate<LoopAnalysis>(F, PA) ||
+         Inv.invalidate<AAManager>(F, PA) ||
+         Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
+         Inv.invalidate<AssumptionAnalysis>(F, PA);
+}
+
 AnalysisKey ScopInfoAnalysis::Key;
 
 ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F,
diff --git a/polly/lib/Analysis/ScopPass.cpp b/polly/lib/Analysis/ScopPass.cpp
@@ -79,11 +79,11 @@ bool ScopAnalysisManagerFunctionProxy::Result::invalidate(
 
   // First, check whether our ScopInfo is about to be invalidated
   auto PAC = PA.getChecker<ScopAnalysisManagerFunctionProxy>();
-  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
-        Inv.invalidate<ScopInfoAnalysis>(F, PA) ||
-        Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
-        Inv.invalidate<LoopAnalysis>(F, PA) ||
-        Inv.invalidate<DominatorTreeAnalysis>(F, PA))) {
+  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
+      Inv.invalidate<ScopInfoAnalysis>(F, PA) ||
+      Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
+      Inv.invalidate<LoopAnalysis>(F, PA) ||
+      Inv.invalidate<DominatorTreeAnalysis>(F, PA)) {
 
     // As everything depends on ScopInfo, we must drop all existing results
     for (auto &S : *SI)
diff --git a/polly/lib/CodeGen/CodeGeneration.cpp b/polly/lib/CodeGen/CodeGeneration.cpp
@@ -328,8 +328,10 @@ PreservedAnalyses
 polly::CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
                                ScopStandardAnalysisResults &AR, SPMUpdater &U) {
   auto &AI = SAM.getResult<IslAstAnalysis>(S, AR);
-  if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI))
+  if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI)) {
+    U.invalidateScop(S);
     return PreservedAnalyses::none();
+  }
 
   return PreservedAnalyses::all();
 }
