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

[philip.pfaffe]

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.

[grosser]

LGTM.

include/polly/ScopInfo.h

public:
   using const_reverse_iterator = RegionToScopMapTy::const_reverse_iterator;
   using iterator = RegionToScopMapTy::iterator;
   using const_iterator = RegionToScopMapTy::const_iterator;
 
 private:
   /// 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 ∾
 
 public:
   ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,
            LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,
            AssumptionCache &AC);
 
   /// Get the Scop object for the given Region.
   ///
   /// @return If the given region is the maximal region within a scop, return
   ///         the scop object. If the given region is a subregion, return a
   ///         nullptr. Top level region containing the entry block of a function
   ///         is not considered in the scop creation.
   Scop *getScop(Region *R) const {
     auto MapIt = RegionToScopMap.find(R);
     if (MapIt != RegionToScopMap.end())
       return MapIt->second.get();
     return nullptr;
   }
 
+  /// Recompute the Scop-Information for a function.
+  ///
+  /// This invalidates any iterators.
+  void recompute();
+
+  /// Handle invalidation explicitely
+  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(); }
   const_iterator end() const { return RegionToScopMap.end(); }
   reverse_iterator rbegin() { return RegionToScopMap.rbegin(); }
   reverse_iterator rend() { return RegionToScopMap.rend(); }
   const_reverse_iterator rbegin() const { return RegionToScopMap.rbegin(); }
   const_reverse_iterator rend() const { return RegionToScopMap.rend(); }

include/polly/ScopPass.h

struct ScopStandardAnalysisResults {
   ScopInfo &SI;
   ScalarEvolution &SE;
   LoopInfo &LI;
   RegionInfo &RI;
 };
 
 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());
   }
 
 private:
-  SmallPriorityWorklist<Scop *, 4> &Worklist;
+  Scop *CurrentScop;
+  bool InvalidateCurrentScop;
+  SmallPriorityWorklist<Region *, 4> &Worklist;
   ScopAnalysisManager &SAM;
+  template <typename ScopPassT> friend class FunctionToScopPassAdaptor;
 };
 
 template <typename ScopPassT>
 class FunctionToScopPassAdaptor
     : public PassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> {
 public:
   explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {}
 
   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),
                                       AM.getResult<LoopAnalysis>(F),
                                       AM.getResult<RegionInfoAnalysis>(F)};
 
     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>>();
     PA.preserve<ScopAnalysisManagerFunctionProxy>();
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<ScopAnalysis>();
     PA.preserve<ScopInfoAnalysis>();
     PA.preserve<ScalarEvolutionAnalysis>();

lib/Analysis/ScopInfo.cpp

 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops",
                     "Polly - Create polyhedral description of Scops", false,
                     false)
 
 //===----------------------------------------------------------------------===//
 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) {
     Region *R = const_cast<Region *>(It);
     if (!SD.isMaxRegionInScop(*R))
       continue;
 
     ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE);
     std::unique_ptr<Scop> S = SB.getScop();
     if (!S)
       continue;
     ScopDetection::LoopStats Stats =
         ScopDetection::countBeneficialLoops(&S->getRegion(), SE, LI, 0);
     updateLoopCountStatistic(Stats);
     bool Inserted = RegionToScopMap.insert({R, std::move(S)}).second;
     assert(Inserted && "Building Scop for the same region twice!");
     (void)Inserted;
   }
 }
 
+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,
                                                FunctionAnalysisManager &FAM) {
   auto &SD = FAM.getResult<ScopAnalysis>(F);
   auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
   auto &LI = FAM.getResult<LoopAnalysis>(F);
   auto &AA = FAM.getResult<AAManager>(F);

lib/Analysis/ScopPass.cpp

 }
 
 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<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<DominatorTreeAnalysis>(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;

lib/CodeGen/CodeGeneration.cpp

public:
   }
 };
 } // namespace
 
 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();
 }
 
 char CodeGeneration::ID = 1;
 
 Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }