[Polly][NewPM][WIP] Add a ScopPassManager

[philip.pfaffe]

Summary

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.

[Meinersbur]

I don't feel confident enough to evaluate the design. I don't know the new pass manager well enough nor its design pattern. so atm I can only give a very peripheral review.

ScopAnalysisManagerFunctionProxy and FunctionToScopPassAdaptor made me think about Java for some reason :). It feels like over-engineering, but I cannot claim that it isn't the way it is supposed to be done.

include/polly/ScopInfo.h

2129

There is already getNameStr. Why the need for another one?

include/polly/ScopPass.h

9–10

double //?

36

Is it necessary to have this in the llvm namespace? Normally we should stay in our Polly namespace.

If it is necessary, doesn't it mean this should be moved to LLVM (respectively that the new pass manager is not designed for extensibility)?

lib/Analysis/ScopInfo.cpp

3216

This is more a description than a name.

lib/Analysis/ScopPass.cpp

17

Independent of what makes more sense: We use quotes to inlcude llvm headers everwhere else.

[philip.pfaffe]

• Fix minor nits.

include/polly/ScopInfo.h

2129

The PassManager expects IR-Units to provide a getName() function. Constructing and returning a std::string (instead of StringRef) from this seems wasteful.

Assuming the the information used in getNameStr() to build the name doesn't change over the lifetime of the Scop, does it make sense to drop getNameStr(), store the name in the Scop itself and return that from getName()?

include/polly/ScopPass.h

36

Stylistically I agree with your concern.

However, I'm specializing members here (the run() method and the Result member class). This must happen in an enclosing namespace of the template definition.

[philip.pfaffe]

Rebased and fixed a few small template issues.

I've added a prototype for a unittest. Right now it doesn't really test anything, but it shows how the pass manager is expected to be used. A real unittest for the invalidation paths will be complete soon.

Sorry that my updates are so slow right now, I've got zero spare time...

[grosser]

Hi Philip,

this already looks very good. I am pleased to see the overall structure written out. I understand that there are still pieces missing, but as this is nicely independent of everything else I believe we can gradually build this up in LLVM. Hence, I believe committing this already soon makes sense such that people can play and experiment with it.

Now, what would be really useful is:

1. The ability to actually run (and test) individual passes with 'opt'

2. The ability to run polly in -O3

I assume 2) is only possible after your patch has been accepted by Chandler. As mentioned earlier, Polly-specific #ifdefs might be a good idea to early on establish a full flow.

I am not clear what is missing for 1).

Best,
Tobias

include/polly/ScopInfo.h

1531

Newline before comment??

2129

If you believe getNameStr() could be implemented more efficiently, then we can do this. However, I would assume getName[Str]() is only called when actually dumping a scop. So eagerly constructing the name string might even have a negative effect performance wise.

I personally do not have a strong opinion if we have getNameStr or getName or if we create the name eagerly or not, until this becomes significant in any profile I see. So if you prefer one over the other I am OK with this.

However, from my perspective I would ignore likely minimal performance effects for now and just include what is needed for this patch without introducing redundancies.

include/polly/ScopPass.h

9–10

This just seems a reformatting of the original comment, without any actual changes. Can you just leave the original format and keep this part unchanged?

lib/Analysis/ScopPass.cpp

63

All passes that just work on 'Scop' should not affect other scops. However, the code generation passes have indeed the potential to affect other scops.

An option that is potentially the most savest option is add more logic into the scoppassmanager. This manager could construct one scopinfo at a time, run all scop passes (except code generation), and then does code generation itself. It then constructs the next scopingo, runs all passes, and does code generation.

This however is possibly unnecessary complicated. So my feeling is that we should ignore this for now, assume everything is safe, get test cases, and build up the flow. After we got something working, we can get test coverage and failing cases and then look into how to handle them best. My feeling is that the general structure should not change, but might just become slightly more complex. As this is independent to everything else in Polly and unlikely to regress anything, I believe we can develop this in-tree.

92

allPreserved

[philip.pfaffe]

1. The ability to actually run (and test) individual passes with 'opt'

2. The ability to run polly in -O3

I assume 2) is only possible after your patch has been accepted by Chandler. As mentioned earlier, Polly-specific #ifdefs might be a good idea to early on establish a full flow.

I am not clear what is missing for 1).

2. is tied very closely to PassBuilders ability to accept injected plugin passes, yes.

On the other hand, while it would be technically possible to forward declare the polly passes in PassBuilder (and the PassRegistry.def), that would pose a severe violation of layering, because we'd need to make lib/Passes depend on polly, both logically as well as in a build-system sense. This dependency doesn't currently exist: LLVM_LINK_POLLY_INTO_TOOLS (which would be the flag we'd #ifdef on), only affects tools. Forward declaring Polly in the PassBuilder would however pull polly dependencies into the PassBuilder.

The good news is I've talked to Chandler about this some more, and there will be progress on the Plugins patch soon!

include/polly/ScopInfo.h

2129

I'm completely in favor of lazily building the name.

That would mean initializing the name member on the first call of getName(). I didn't dare to rename getNameStr() (or, in other words, return std::string from getName()), because I can't guarantee that this function won't be called in a context where a StringRef is expected, thus creating a dangling reference to a termporary.

lib/Analysis/ScopPass.cpp

63

There is actually a rather clean way to implement this, and it's very similar to what the LoopPassManager does today. We can pass an Updater along the Scop pipeline down into CodeGeneration. Using that we can propagate ScopInfo invalidations into the ScopPassManager which can then skip now-invalid Scops. This works under two conditions:

1. Invalidation occurs only for Scops that haven't been transformed yet. If I understand the current implementation correctly, that's condition holds.
2. CodeGeneration actually knows which potential Scops it breaks. From the previous discussions I'm under the impression that there are only a handful of ways it does that, so it sounds like it's easily checkable. Worst case I assume the Updater would need to verify all remaining Scops.

I expect this to be a an uninvasive change. Most of the work would need to go into CodeGeneration in figuring out which Scops to skip.

[philip.pfaffe]

• Fix minor nits

[philip.pfaffe]

Sorry, I should just stop using arc ...

[philip.pfaffe]

I've added an update mechanism for the Scop worklist. As discussed inline, the ScopPassManager passes a small Updater object down through the Scop pipeline. Transformation passes such as CodeGen may use this updater to inform the PM about Scops that are to be skipped because they aren't valid anymore. It is up to those passes now to figure out the correct Scops to skip.

This takes care of the remaining FIXME.

[grosser]

In D32539#752299, @philip.pfaffe wrote:

1. The ability to actually run (and test) individual passes with 'opt'

2. The ability to run polly in -O3

I assume 2) is only possible after your patch has been accepted by Chandler. As mentioned earlier, Polly-specific #ifdefs might be a good idea to early on establish a full flow.

I am not clear what is missing for 1).

2. is tied very closely to PassBuilders ability to accept injected plugin passes, yes.

On the other hand, while it would be technically possible to forward declare the polly passes in PassBuilder (and the PassRegistry.def), that would pose a severe violation of layering, because we'd need to make lib/Passes depend on polly, both logically as well as in a build-system sense. This dependency doesn't currently exist: LLVM_LINK_POLLY_INTO_TOOLS (which would be the flag we'd #ifdef on), only affects tools. Forward declaring Polly in the PassBuilder would however pull polly dependencies into the PassBuilder.

The good news is I've talked to Chandler about this some more, and there will be progress on the Plugins patch soon!

I see.

I think that patch looks good to me so far. (Similar to the other two). They certainly go into the right direction and they are almost 100% independent of Polly. I think it makes sense to commit them to Polly already today facilitate further testing. After this has happened, you could already work on a patch that registers the Polly passes (using the new pass manager plugin). If we happen to have time, we could then already run Polly once with the new pass manager on the LLVM test suite and possibly even discuss the results next week. ;)

include/polly/ScopInfo.h

2129

Ah, OK. I now realize that returning a std::string is not only wasteful, but might indeed result in memory corruption. In this case, let's just use the approach you propose. No need to over-optimize with lazy initialization.

lib/Analysis/ScopInfo.cpp

3216

I agree with Michael here. Can we drop the "Scop for region "?

lib/Analysis/ScopPass.cpp

63

I am not certain it will be easy to know which scops have been invalidate. Anyway, the best will likely be to just commit this baseline implementation, run the LLVM test suite and see if or what is failing, if at all.

[philip.pfaffe]

• Fixed the updater (Analyses don't care)
• Clean up the testcase a bit (i.e., made it compile based on the patch)
• Removed sugar from the Scop name

[philip.pfaffe]

Landed in rL303062.

[grosser]

It seems you forgot to commit the unit tests. Also, please update the commit message in the future.

[philip.pfaffe]

Yes, I noticed that. I fixed it in rL303064. I saw your rL303066, was that to appease the buildbots and we hit a race condition? Or was that to fix the failing build in http://lab.llvm.org:8011/builders/polly-amd64-linux/builds/6821/ ?

Sorry about the noise!

[grosser]

I tried to fix the buildbots. Can you fix it if I broke something?

[philip.pfaffe]

You didn't break anything, it's a CMake issue (looks like I missed adding an LLVM library dependency). Will fix.

include/polly/ScopInfo.h

 private:
   Scop(const Scop &) = delete;
   const Scop &operator=(const Scop &) = delete;
 
   ScalarEvolution *SE;
 
   /// 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.
   AccFuncVector AccessFunctions;
 
   /// Flag to indicate that the scheduler actually optimized the SCoP.
   bool IsOptimized;
public:
   iterator_range<ParameterSetTy::iterator> parameters() const {
     return make_range(Parameters.begin(), Parameters.end());
   }
 
   /// Return whether this scop is empty, i.e. contains no statements that
   /// 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<ArrayInfoSetTy::iterator> array_range;
   typedef iterator_range<ArrayInfoSetTy::const_iterator> const_array_range;
 
   inline array_iterator array_begin() { return ScopArrayInfoSet.begin(); }
 
   inline array_iterator array_end() { return ScopArrayInfoSet.end(); }
if (MapIt != RegionToScopMap.end())
       return MapIt->second.get();
     return nullptr;
   }
 
   iterator begin() { return RegionToScopMap.begin(); }
   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<ScopInfoAnalysis> {
   static AnalysisKey Key;
   using Result = ScopInfo;
   Result run(Function &, FunctionAnalysisManager &);
 };
 

include/polly/ScopPass.h

 //===--------- ScopPass.h - Pass for Static Control Parts --------*-C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
-//
-// This file defines the ScopPass class.  ScopPasses are just RegionPasses,
-// except they operate on Polly IR (Scop and ScopStmt) built by ScopInfo Pass.
-// Because they operate on Polly IR, not the LLVM IR, ScopPasses are not allowed
-// to modify the LLVM IR. Due to this limitation, the ScopPass class takes
-// care of declaring that no LLVM passes are invalidated.
+// // This file defines the ScopPass class.  ScopPasses are just RegionPasses,
+// // except they operate on Polly IR (Scop and ScopStmt) built by ScopInfo
+// Pass. Because they operate on Polly IR, not the LLVM IR, ScopPasses are not
+// allowed to modify the LLVM IR. Due to this limitation, the ScopPass class
+// takes care of declaring that no LLVM passes are invalidated.
 //
 //===----------------------------------------------------------------------===//
 
 #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;
+struct ScopStandardAnalysisResults;
+
+using ScopAnalysisManager = AnalysisManager<Scop>;
+using ScopAnalysisManagerFunctionProxy =
+    InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
+} // namespace polly
+
+namespace llvm {
+using polly::Scop;
+using polly::ScopInfo;
+using polly::ScopAnalysisManager;
+using polly::ScopStandardAnalysisResults;
+using polly::ScopAnalysisManagerFunctionProxy;
+
+template <>
+PreservedAnalyses
+PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &>::run(
+    Scop &InitialS, ScopAnalysisManager &AM, ScopStandardAnalysisResults &);
+extern template class PassManager<Scop, ScopAnalysisManager,
+                                  ScopStandardAnalysisResults &>;
+
+template <> class ScopAnalysisManagerFunctionProxy::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 <>
+ScopAnalysisManagerFunctionProxy::Result
+ScopAnalysisManagerFunctionProxy::run(Function &F,
+                                      FunctionAnalysisManager &FAM);
+} // namespace llvm
+
+namespace polly {
+using ScopPassManager =
+    PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &>;
 
 /// ScopPass - This class adapts the RegionPass interface to allow convenient
 /// creation of passes that operate on the Polly IR. Instead of overriding
 /// runOnRegion, subclasses override runOnScop.
 class ScopPass : public RegionPass {
   Scop *S;
 
 protected:
protected:
   ///
   virtual void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
   bool runOnRegion(Region *R, RGPassManager &RGM) override;
   void print(raw_ostream &OS, const Module *) const override;
 };
 
+struct ScopStandardAnalysisResults {
+  DominatorTree &DT;
+  ScalarEvolution &SE;
+  LoopInfo &LI;
+  RegionInfo &RI;
+};
+
+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())
+      return PA;
+
+    ScopAnalysisManager &SAM =
+        AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager();
+
+    ScopStandardAnalysisResults AR = {AM.getResult<DominatorTreeAnalysis>(F),
+                                      AM.getResult<ScalarEvolutionAnalysis>(F),
+                                      AM.getResult<LoopAnalysis>(F),
+                                      AM.getResult<RegionInfoAnalysis>(F)};
+
+    for (auto &S : Scops) {
+      if (auto *scop = S.second.get()) {
+        PreservedAnalyses PassPA = Pass.run(*scop, SAM, AR);
+
+        SAM.invalidate(*scop, PassPA);
+        PA.intersect(std::move(PassPA));
+      }
+    }
+
+    PA.preserveSet<AllAnalysesOn<Scop>>();
+    PA.preserve<ScopAnalysisManagerFunctionProxy>();
+    return PA;
+  }
+
+private:
+  ScopPassT Pass;
+}; // namespace polly
+
+template <typename ScopPassT>
+FunctionToScopPassAdaptor<ScopPassT>
+createFunctionToScopPassAdaptor(ScopPassT Pass) {
+  return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass));
+}
+
 } // namespace polly
 
 #endif

lib/Analysis/ScopInfo.cpp

while (L) {
     L = L->getParentLoop();
   }
 
   return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;
 }
 
 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
            ScopDetection::DetectionContext &DC)
-    : SE(&ScalarEvolution), R(R), IsOptimized(false),
-      HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false),
-      MaxLoopDepth(0), CopyStmtsNum(0), DC(DC),
+    : SE(&ScalarEvolution), R(R), name("Scop for region " + R.getNameStr()),
+      IsOptimized(false), HasSingleExitEdge(R.getExitingBlock()),
+      HasErrorBlock(false), MaxLoopDepth(0), CopyStmtsNum(0), DC(DC),
       IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr),
       Affinator(this, LI), AssumedContext(nullptr), InvalidContext(nullptr),
       Schedule(nullptr) {
   if (IslOnErrorAbort)
     isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT);
   buildContext();
 }
 

lib/Analysis/ScopPass.cpp

 //===- ScopPass.cpp - The base class of Passes that operate on Polly IR ---===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the definitions of the ScopPass members.
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/ScopPass.h"
 #include "polly/ScopInfo.h"
 
+#include <llvm/Analysis/AssumptionCache.h>
+
 using namespace llvm;
 using namespace polly;
 
 bool ScopPass::runOnRegion(Region *R, RGPassManager &RGM) {
   S = nullptr;
 
   if ((S = getAnalysis<ScopInfoRegionPass>().getScop()))
     return runOnScop(*S);
 
   return false;
 }
 
 void ScopPass::print(raw_ostream &OS, const Module *M) const {
   if (S)
     printScop(OS, *S);
 }
 
 void ScopPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<ScopInfoRegionPass>();
   AU.setPreservesAll();
 }
+
+namespace llvm {
+
+template class PassManager<Scop, ScopAnalysisManager,
+                           ScopStandardAnalysisResults &>;
+
+template <>
+PreservedAnalyses
+PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &>::run(
+    Scop &S, ScopAnalysisManager &AM, ScopStandardAnalysisResults &AR) {
+  auto PA = PreservedAnalyses::all();
+  for (auto &Pass : Passes) {
+    auto PassPA = Pass->run(S, AM, AR);
+
+    AM.invalidate(S, PassPA);
+    PA.intersect(std::move(PassPA));
+  }
+
+  // All analyses for 'this' Scop have been invalidated above. Different Scops
+  // aren't affected
+  // FIXME is this correct wrt. the current pass behaviours?
+  PA.preserveSet<AllAnalysesOn<Scop>>();
+  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<ScopAnalysisManagerFunctionProxy>();
+  if (!(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))) {
+
+    // 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.
+  }
+
+  // FIXME What about deferred invalidation?
+
+  if (PA.allAnalysesInSetPreserved<AllAnalysesOn<Scop>>())
+    for (auto &S : *SI)
+      if (auto *scop = S.second.get())
+        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<ScopInfoAnalysis>(F));
+}
+} // namespace llvm