[New-PM] Lift Scop Pipeline to CGSCC-level

[lksbhm]

Summary

This patch is intended as a preparation to teach polly interprocedural analysis.

The reason we want to have polly passes run in CGSCC scope instead of function scope is the deterministic iteration order over functions: To be able to "look into" a region's callees, we ideally want ScopInfo to be already available for every callee. The CGSCC AnalysisManager ensures this - except for callees which are part of the analyzed function's SCC. But we aren't interested in those anyways. For that matter, the differential's most important part is the change from FunctionToScopPassAdaptor to CGSCCToScopPassAdaptor and buildDefaultPollyPipeline taking a CGSCC-AM now instead of a Function-AM.

However, this differential also includes some further CGSCC-related changes to prepare for upcoming patches: In RegisterPasses.cpp we add a parseCGSCCPipeline callback, allowing us to run the ScopInfoPrinterPass in a CGSCC-pipeline as well (making no difference at the moment, but using the CGSCC_PASS macro in PollyPasses.def).

Regarding tests: @philip.pfaffe is currently working on porting the existing lit test-suite to the new passmanager. I would suggest waiting for this effort to be complete before I add any more tests to the repo. That being said, I am not opposed to doing so if asked.

I apologize for the seemingly unnecessary small changes (e.g. renaming FAM->AM), but we had a lot of code churn while developing our IPO changes, and I didn't think it important enough to waste time reverting them again.

[lksbhm]

Remove OwningInnerAnalysisManagerProxy's friend class ... and AnalysisKey which weren't necessary.
Move OwningScopAnalysisManagerFunctionProxy-related code in ScopPass.cpp closer together [nfc]

[Meinersbur]

Are you also going to downstream patches that need this? If yes, what exactly do they need to analyze the callee for?

[lksbhm]

In D45210#1056073, @Meinersbur wrote:

Are you also going to downstream patches that need this? If yes, what exactly do they need to analyze the callee for?

I hope I didn't misunderstand your question, but we intend to fully integrate our interprocedural analysis efforts into upstream polly. In fact, I intend to get the next patch ready for review tomorrow which probably will make things clearer.

Basically, we made an extended version of ScopInfo which stores additional information about how MemoryAccesses depend on function parameters for all accesses in a function. By querying this information for a callee, we can add the induced MemoryAccesses to the surrounding ScopStmt by projecting them into the caller-function's scope and therefore model the effects of the CallInst (I hope this explanation is both understandable and accurate. @philip.pfaffe can hopefully correct me if there is anything wrong or missing). I hope I was able to clarify things a little.

[Meinersbur]

Thanks for your response. Looking forward to your follow-up patches. I am not too knowledgeable with the new pass manager, so I will let Philip review.
Would it make sense to keep code that analyzes SCoP's function-wise and only use a CGSCC pass when interprocedural analysis is enabled?

If I understand correctly, you are analyzing which data a function accesses. Similar to the "summary functions" in PENCIL.

Another possibility would have been to inline the callee's scop to get a single scop. We already have a 'hack' for this called ScopInliner.

Michael

[lksbhm]

Would it make sense to keep code that analyzes SCoP's function-wise and only use a CGSCC pass when interprocedural analysis is enabled?

Our approach doesn't actually change the level at which scop analysis happens, if that is the question. I.e. ScopInfoAnalysis remains a function analysis. The only reason we want to process the callgraph at cgscc-level when running a scop pass pipeline is the guaranteed ordering which maximizes the callee ScopInfo availability. Or, from the implementation point of view, we cannot run ScopInfoAnalysis on-demand for a callee but instead have to depend on it already having run before. This is where cgscc's post-order traversal comes in handy.
However, if you're asking whether it would make sense to have both FunctionToScopPassAdaptor alongside CGSCCToScopPassAdaptor, this might be something worth considering.

Similar to the "summary functions" in PENCIL.

From quickly glancing at the paper you linked to, the "function summaries" section seems very related to our approach :)

Another possibility would have been to inline the callee's scop to get a single scop. We already have a 'hack' for this called ScopInliner.

I'm not familiar with the way ScopInliner works. I'm assuming this is on llvm IR level(?)

[philip.pfaffe]

include/polly/ScopPass.h

36

Unrelated change

53

Should have three slashes

186

Unrelated change

264

No curly braces required here

283

unrelated change

lib/Analysis/ScopPass.cpp

15

This shouldn't be removed

lib/Support/RegisterPasses.cpp

717

Irrelevant

[Meinersbur]

Philip and me talked about the idea keeping both Function- and CGSCC-level passes around. Philipp was convinced that there was no benefit. For reference, here were my concerns (I don't know the new pas manager that well):

1. A function-level transformation pass wants to use Polly analysis. Since function passes can be run in any order by the pass manager, it does not necessarily correspond to the CGSCC (reverse? post-order) expected by the Polly passes. Callees have been already modified by this hypothetical pass after being analyzed by Polly.

2. A JIT or similar (e.g. clang runs a few LLVM passes directly after codegening a function) may not have added or know all callers/callees to the llvm::Module yet, i.e. the call graph is not complete/available.

[Rational: There must be some reason for why not all LLVM function passes are CGSCC-passes]

Other than a few nitpicks: LGTM.

include/polly/ScopPass.h

283

The comments are added by clang-format, make check-polly probably already complained about format changes.

lib/Analysis/ScopInfo.cpp

5150–5159

[Style] You could just call the other overload than to duplicate its code.

lib/Analysis/ScopPass.cpp

149

[Nit] Unnecessary change

lib/Support/RegisterPasses.cpp

702

The meaning of the FIXME comment is not clear without the deleted code.
Suggestion:

// FIXME: When VerifyEachPass is enabled, we are supposed to add a VerifierPass to the pipeline here. However, there is no CGSCC-level verifier pass.

[lksbhm]

Implement changes requested in review

[lksbhm]

include/polly/ScopPass.h

283

This is the only remark I didn't do any changes for with the latest update. Since the closing brace is for the CGSCCToScopPassAdaptor, the "namespace" comment is clearly misplaced. I ran the polly-update-format target with a clang-format built half an hour ago and it didn't re-insert the comment. However, RegisterPasses.cpp would get it's corresponding header moved above the other includes. I assume this is an unrelated change as well, though, so I didn't put it in the diff.

[philip.pfaffe]

In D45210#1057799, @Meinersbur wrote:

1. A function-level transformation pass wants to use Polly analysis. Since function passes can be run in any order by the pass manager, it does not necessarily correspond to the CGSCC (reverse? post-order) expected by the Polly passes. Callees have been already modified by this hypothetical pass after being analyzed by Polly.

This patch only changes the layering for ScopPasses. Note that Scop analyses are still being proxied in and out of function. As a consequence, function layer passes are not affected by this change.

2. A JIT or similar (e.g. clang runs a few LLVM passes directly after codegening a function) may not have added or know all callers/callees to the llvm::Module yet, i.e. the call graph is not complete/available.

This should probably be discussed as part of a review for interprocedural analysis. But fundamentally speaking, if the callee cannot be analyzed then the region containing the call cannot be modeled. So, worst case, nothing changes from what we're doing right now.

[Meinersbur]

include/polly/ScopPass.h

283

You are of course right that the // namespace polly is misplaced. Sorry, I didn't notice that. I just committed a change to correct that (if you have commit rights, and notice such things, you can just fix them in a commit tagged "NFC").

Regarding the header move: It looks like this patch moves #include "polly/RegisterPasses.h" to where it belongs alphabetically. However, clang-format identifies it as the header of the translation unit and moves it to the beginning (where, AFAICS it is in trunk).

Part of make check-polly is that it is clang-format clean. We have a problem if it is not, the buildbots (http://lab.llvm.org:8011/builders/polly-amd64-linux) will consider the build as "failed". This forces us to use the formatting as defined by clang-format (if clang-format itself changes, we apply its suggestions in a dedicated commit).

[lksbhm]

Rebase onto top of trunk and run clang-format.
Only changes between previous patch version and this are // namespace polly comment removal (already in trunk) and #include RegisterPasses.h now first include in RegisterPasses.cpp

[Meinersbur]

LGTM. @philip.pfaffe, do you agree?

[philip.pfaffe]

LGTM too!

Since we can do new-PM lit testing now, does it make sense to include test cases here?

[lksbhm]

Rebase patch and port some tests where the cgscc() nesting needs to be explicit to the new passmanager

We already have a fully ported testsuite (see D45493) and these are the tests that fail after this patch without the necessary modifications.
Therefore we have decided that it makes sense to attach them as tests for this change. NOTE however that this patch now depends on D45484 in order for the tests to be executable (and D45493 for the remaining ports)

[lksbhm]

test/Isl/CodeGen/loop_with_condition_nested.ll

226 ↗

(On Diff #141859)

The BasicBlock order is different in new-pm it seems. So that's why we need to duplicate this

test/Isl/CodeGen/perf_monitoring_trip_counts_per_scop.ll

68 ↗

(On Diff #141859)

Globals are printed in a different order as well

test/ScopInfo/aliasing_with_non_affine_access.ll

15 ↗

(On Diff #141859)

Function iteration order on cgscc level is also different sometimes. Should make sense to have a different run for each test anyways

[lksbhm]

1. Add parseCGSCCPipeline callback to PassBuilder in RegisterPasses.cpp (no idea how this went missing before)
2. Change some new-pm lit test RUN lines to use the function-level scop analysis printer pass. Those turned out to be function traversal ordering dependent, which isn't the same on cgscc-level as it is on function-level

include/polly/ScopInfo.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
+#include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/RegionPass.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
struct ScopInfoAnalysis : public AnalysisInfoMixin<ScopInfoAnalysis> {
 
   Result run(Function &, FunctionAnalysisManager &);
 };
 
 struct ScopInfoPrinterPass : public PassInfoMixin<ScopInfoPrinterPass> {
   ScopInfoPrinterPass(raw_ostream &OS) : Stream(OS) {}
 
   PreservedAnalyses run(Function &, FunctionAnalysisManager &);
+  PreservedAnalyses run(LazyCallGraph::SCC &, CGSCCAnalysisManager &,
+                        LazyCallGraph &, CGSCCUpdateResult &);
 
   raw_ostream &Stream;
 };
 
 //===----------------------------------------------------------------------===//
 /// The legacy pass manager's analysis pass to compute scop information
 ///        for the whole function.
 ///

include/polly/ScopPass.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCOP_PASS_H
 #define POLLY_SCOP_PASS_H
 
 #include "polly/ScopInfo.h"
 #include "llvm/ADT/PriorityWorklist.h"
+#include "llvm/Analysis/CGSCCPassManager.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<Scop, ScopStandardAnalysisResults &>;
+
 using ScopAnalysisManagerFunctionProxy =
     InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
 using FunctionAnalysisManagerScopProxy =
     OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
                               ScopStandardAnalysisResults &>;
 } // namespace polly
 
 namespace llvm {
 using polly::Scop;
 using polly::ScopAnalysisManager;
 using polly::ScopAnalysisManagerFunctionProxy;
 using polly::ScopInfo;
 using polly::ScopStandardAnalysisResults;
 using polly::SPMUpdater;
 
+/// Implementation of ScopAnalysisManagerFunctionProxy
+// @{
 template <>
 class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::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;
   }
public:
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &Inv);
 
 private:
   ScopAnalysisManager *InnerAM;
   ScopInfo *SI;
 };
 
+template <>
+InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
+InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
+    Function &F, FunctionAnalysisManager &AM);
+
+extern template class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
+// @}
+
 // A partial specialization of the require analysis template pass to handle
 // extra parameters
 template <typename AnalysisT>
 struct RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager,
                            ScopStandardAnalysisResults &, SPMUpdater &>
     : PassInfoMixin<
           RequireAnalysisPass<AnalysisT, Scop, ScopAnalysisManager,
                               ScopStandardAnalysisResults &, SPMUpdater &>> {
   PreservedAnalyses run(Scop &L, ScopAnalysisManager &AM,
                         ScopStandardAnalysisResults &AR, SPMUpdater &) {
     (void)AM.template getResult<AnalysisT>(L, AR);
     return PreservedAnalyses::all();
   }
 };
 
 template <>
-InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
-InnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
-    Function &F, FunctionAnalysisManager &FAM);
-
-template <>
 PreservedAnalyses
 PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &,
             SPMUpdater &>::run(Scop &InitialS, ScopAnalysisManager &AM,
                                ScopStandardAnalysisResults &, SPMUpdater &);
 extern template class PassManager<Scop, ScopAnalysisManager,
                                   ScopStandardAnalysisResults &, SPMUpdater &>;
-extern template class InnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
 extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Scop,
                                                 ScopStandardAnalysisResults &>;
 } // namespace llvm
 
 namespace polly {
 
 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
 class OwningInnerAnalysisManagerProxy
-    : public InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT> {
+    : public InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT,
+                                       ExtraArgTs...> {
 public:
   OwningInnerAnalysisManagerProxy()
-      : InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>(InnerAM) {}
+      : InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>(
+            InnerAM) {}
   using Result = typename InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT,
                                                     ExtraArgTs...>::Result;
   Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
              ExtraArgTs...) {
     return Result(InnerAM);
   }
 
   AnalysisManagerT &getManager() { return InnerAM; }
 
 private:
+  friend AnalysisInfoMixin<
+      OwningInnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>>;
+
+  static AnalysisKey Key;
+
   AnalysisManagerT InnerAM;
 };
 
+/// @name OwningScopAnalysisManagerFunctionProxy
+// @{
+using OwningScopAnalysisManagerFunctionProxy =
+    OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
+
 template <>
 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::Result
 OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>::run(
     Function &F, FunctionAnalysisManager &FAM);
 extern template class OwningInnerAnalysisManagerProxy<ScopAnalysisManager,
                                                       Function>;
+// @}
 
-using OwningScopAnalysisManagerFunctionProxy =
-    OwningInnerAnalysisManagerProxy<ScopAnalysisManager, Function>;
 using ScopPassManager =
     PassManager<Scop, ScopAnalysisManager, ScopStandardAnalysisResults &,
                 SPMUpdater &>;
 
 /// 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 {
protected:
   virtual void printScop(raw_ostream &OS, Scop &S) const {}
 
   /// getAnalysisUsage - Subclasses that override getAnalysisUsage
   /// must call this.
   ///
   virtual void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
-  bool runOnRegion(Region *R, RGPassManager &RGM) override;
+  bool runOnRegion(Region *R, RGPassManager &RGM) final override;
   void print(raw_ostream &OS, const Module *) const override;
 };
 
 struct ScopStandardAnalysisResults {
   DominatorTree &DT;
   ScopInfo &SI;
   ScalarEvolution &SE;
   LoopInfo &LI;
void invalidateScop(Scop &S) {
     SAM.clear(S, S.getName());
   }
 
 private:
   Scop *CurrentScop;
   bool InvalidateCurrentScop;
   SmallPriorityWorklist<Region *, 4> &Worklist;
   ScopAnalysisManager &SAM;
-  template <typename ScopPassT> friend class FunctionToScopPassAdaptor;
+  template <typename ScopPassT> friend class CGSCCToScopPassAdaptor;
 };
 
 template <typename ScopPassT>
-class FunctionToScopPassAdaptor
-    : public PassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> {
+class CGSCCToScopPassAdaptor
+    : public PassInfoMixin<CGSCCToScopPassAdaptor<ScopPassT>> {
 public:
-  explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {}
+  explicit CGSCCToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {}
 
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
+  PreservedAnalyses run(LazyCallGraph::SCC &SCC, CGSCCAnalysisManager &CGAM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &) {
     PreservedAnalyses PA = PreservedAnalyses::all();
-    auto &SD = AM.getResult<ScopAnalysis>(F);
+    for (auto &SCCNode : SCC) {
+      auto &F = SCCNode.getFunction();
+      auto &AM = CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(SCC, CG)
+                     .getManager();
+      auto &SAM =
+          AM.getResult<ScopAnalysisManagerFunctionProxy>(F).getManager();
       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();
+      ScopStandardAnalysisResults AR = {
+          AM.getResult<DominatorTreeAnalysis>(F), SI,
+          AM.getResult<LoopAnalysis>(F), AM.getResult<RegionInfoAnalysis>(F)};
 
       SPMUpdater Updater{Worklist, SAM};
 
       while (!Worklist.empty()) {
         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())
+        if (Updater.invalidateCurrentScop()) {
           SI.recompute();
-    };
+        }
+      }
+    }
 
     PA.preserveSet<AllAnalysesOn<Scop>>();
     PA.preserve<ScopAnalysisManagerFunctionProxy>();
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<ScopAnalysis>();
     PA.preserve<ScopInfoAnalysis>();
     PA.preserve<ScalarEvolutionAnalysis>();
     PA.preserve<LoopAnalysis>();
     PA.preserve<RegionInfoAnalysis>();
     return PA;
   }
 
 private:
   ScopPassT Pass;
-}; // namespace polly
+};
 
 template <typename ScopPassT>
-FunctionToScopPassAdaptor<ScopPassT>
-createFunctionToScopPassAdaptor(ScopPassT Pass) {
-  return FunctionToScopPassAdaptor<ScopPassT>(std::move(Pass));
+CGSCCToScopPassAdaptor<ScopPassT> createCGSCCToScopPassAdaptor(ScopPassT Pass) {
+  return CGSCCToScopPassAdaptor<ScopPassT>(std::move(Pass));
 }
 } // namespace polly
 
 #endif

lib/Analysis/ScopInfo.cpp

for (auto &It : reverse(SI)) {
     if (It.second)
       It.second->print(Stream, PollyPrintInstructions);
     else
       Stream << "Invalid Scop!\n";
   }
   return PreservedAnalyses::all();
 }
 
+PreservedAnalyses ScopInfoPrinterPass::run(LazyCallGraph::SCC &SCC,
+                                           CGSCCAnalysisManager &CGAM,
+                                           LazyCallGraph &CG,
+                                           CGSCCUpdateResult &) {
+  for (auto &SCCNode : SCC) {
+    Function &F = SCCNode.getFunction();
+    auto &FAM =
+        CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(SCC, CG).getManager();
+    auto &SI = FAM.getResult<ScopInfoAnalysis>(F);
+    for (auto &It : reverse(SI)) {
+      if (It.second)
+        It.second->print(Stream, PollyPrintInstructions);
+      else
+        Stream << "Invalid Scop!\n";
+    }
+  }
+  return PreservedAnalyses::all();
+}
+
 void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<RegionInfoPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<ScopDetectionWrapperPass>();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<AssumptionCacheTracker>();

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"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 
if (auto *OuterProxy =
         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<ScopInfoAnalysis>(F));
+                                      FunctionAnalysisManager &AM) {
+  return Result(*InnerAM, AM.getResult<ScopInfoAnalysis>(F));
 }
 } // namespace llvm
 
 namespace polly {
 template <>
 OwningScopAnalysisManagerFunctionProxy::Result
 OwningScopAnalysisManagerFunctionProxy::run(Function &F,
-                                            FunctionAnalysisManager &FAM) {
-  return Result(InnerAM, FAM.getResult<ScopInfoAnalysis>(F));
+                                            FunctionAnalysisManager &AM) {
+  return Result(InnerAM, AM.getResult<ScopInfoAnalysis>(F));
 }
 } // namespace polly

lib/Support/PollyPasses.def

 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("polly-detect", ScopAnalysis())
 FUNCTION_ANALYSIS("polly-function-scops", ScopInfoAnalysis())
 #undef FUNCTION_ANALYSIS
 
 #ifndef FUNCTION_PASS
 #define FUNCTION_PASS(NAME, CREATE_PASS)
 #endif
 FUNCTION_PASS("polly-prepare", CodePreparationPass())
 FUNCTION_PASS("print<polly-detect>", ScopAnalysisPrinterPass(errs()))
 FUNCTION_PASS("print<polly-function-scops>", ScopInfoPrinterPass(errs()))
 #undef FUNCTION_PASS
 
+#ifndef CGSCC_PASS
+#define CGSCC_PASS(NAME, CREATE_PASS)
+#endif
+CGSCC_PASS("print<polly-function-scops>", ScopInfoPrinterPass(errs()))
+#undef CGSCC_PASS
+
 #ifndef SCOP_ANALYSIS
 #define SCOP_ANALYSIS(NAME, CREATE_PASS)
 #endif
 SCOP_ANALYSIS("polly-ast", IslAstAnalysis())
 SCOP_ANALYSIS("polly-dependences", DependenceAnalysis())
 #undef SCOP_ANALYSIS
 
 #ifndef SCOP_PASS
 #define SCOP_PASS(NAME, CREATE_PASS)
 #endif
 SCOP_PASS("polly-export-jscop", JSONExportPass())
 SCOP_PASS("polly-import-jscop", JSONImportPass())
 SCOP_PASS("print<polly-ast>", IslAstPrinterPass(outs()))
 SCOP_PASS("print<polly-dependences>", DependenceInfoPrinterPass(outs()))
 SCOP_PASS("polly-codegen", CodeGenerationPass())
 #undef SCOP_PASS

lib/Support/RegisterPasses.cpp

registerPollyScalarOptimizerLatePasses(const llvm::PassManagerBuilder &Builder,
   if (PassPosition != POSITION_BEFORE_VECTORIZER)
     return;
 
   PM.add(polly::createCodePreparationPass());
   polly::registerPollyPasses(PM);
   PM.add(createCodegenCleanupPass());
 }
 
-static void buildDefaultPollyPipeline(FunctionPassManager &PM,
+static void buildDefaultPollyPipeline(CGSCCPassManager &PM,
                                       PassBuilder::OptimizationLevel Level) {
   if (!polly::shouldEnablePolly())
     return;
   PassBuilder PB;
   ScopPassManager SPM;
 
   // TODO add utility passes for the various command line options, once they're
   // ported
default: // Does it actually make sense to distinguish IslAst codegen?
       break;
     }
   }
 #ifdef GPU_CODEGEN
   else
     llvm_unreachable("Hybrid Target with GPU support is not implemented");
 #endif
 
-  PM.addPass(CodePreparationPass());
-  PM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
-  PM.addPass(PB.buildFunctionSimplificationPipeline(
+  FunctionPassManager FPM;
+
+  FPM.addPass(CodePreparationPass());
+  FPM.addPass(PB.buildFunctionSimplificationPipeline(
       Level, PassBuilder::ThinLTOPhase::None)); // Cleanup
 
   assert(!DumpAfter && "This option is not implemented");
   assert(DumpAfterFile.empty() && "This option is not implemented");
 
   if (CFGPrinter)
-    PM.addPass(llvm::CFGPrinterPass());
+    FPM.addPass(llvm::CFGPrinterPass());
+
+  PM.addPass(CGSCCToScopPassAdaptor<ScopPassManager>(std::move(SPM)));
+  PM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM)));
 }
 
 /// Register Polly to be available as an optimizer
 ///
 ///
 /// We can currently run Polly at three different points int the pass manager.
 /// a) very early, b) after the canonicalizing loop transformations and c) right
 /// before the vectorizer.

 static llvm::RegisterStandardPasses
     RegisterPollyOptimizerLoopEnd(llvm::PassManagerBuilder::EP_LoopOptimizerEnd,
                                   registerPollyLoopOptimizerEndPasses);
 
 static llvm::RegisterStandardPasses RegisterPollyOptimizerScalarLate(
     llvm::PassManagerBuilder::EP_VectorizerStart,
     registerPollyScalarOptimizerLatePasses);
 
-static OwningScopAnalysisManagerFunctionProxy
-createScopAnalyses(FunctionAnalysisManager &FAM) {
+static void registerScopAnalyses(FunctionAnalysisManager &AM) {
+  AM.registerPass([&AM] {
     OwningScopAnalysisManagerFunctionProxy Proxy;
 #define SCOP_ANALYSIS(NAME, CREATE_PASS)                                       \
   Proxy.getManager().registerPass([] { return CREATE_PASS; });
 
 #include "PollyPasses.def"
 
     Proxy.getManager().registerPass(
-      [&FAM] { return FunctionAnalysisManagerScopProxy(FAM); });
+        [&AM] { return FunctionAnalysisManagerScopProxy(AM); });
     return Proxy;
+  });
 }
 
 static void registerFunctionAnalyses(FunctionAnalysisManager &FAM) {
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)                                   \
   FAM.registerPass([] { return CREATE_PASS; });
 
 #include "PollyPasses.def"
+}
+
+static bool
+parseCGSCCPipeline(StringRef Name, CGSCCPassManager &PM,
+                   ArrayRef<PassBuilder::PipelineElement> Pipeline) {
+#define CGSCC_PASS(NAME, CREATE_PASS)                                          \
+  if (Name == NAME) {                                                          \
+    PM.addPass(CREATE_PASS);                                                   \
+    return true;                                                               \
+  }
 
-  FAM.registerPass([&FAM] { return createScopAnalyses(FAM); });
+#include "PollyPasses.def"
+  return false;
 }
 
 static bool
 parseFunctionPipeline(StringRef Name, FunctionPassManager &FPM,
                       ArrayRef<PassBuilder::PipelineElement> Pipeline) {
   if (parseAnalysisUtilityPasses<OwningScopAnalysisManagerFunctionProxy>(
           "polly-scop-analyses", Name, FPM))
     return true;
if (Name == NAME) {                                                          \
     return true;                                                               \
   }
 
 #include "PollyPasses.def"
 
   return false;
 }
 
-static bool parseScopPipeline(StringRef Name, FunctionPassManager &FPM,
+static bool parseScopPipeline(StringRef Name, CGSCCPassManager &PM,
                               ArrayRef<PassBuilder::PipelineElement> Pipeline) {
   if (Name != "scop")
     return false;
   if (!Pipeline.empty()) {
     ScopPassManager SPM;
     for (const auto &E : Pipeline)
       if (!parseScopPass(E.Name, SPM))
         return false;
-    FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
+    PM.addPass(createCGSCCToScopPassAdaptor(std::move(SPM)));
   }
   return true;
 }
 
 static bool isScopPassName(StringRef Name) {
 #define SCOP_ANALYSIS(NAME, CREATE_PASS)                                       \
   if (Name == "require<" NAME ">")                                             \
     return true;                                                               \
parseTopLevelPipeline(ModulePassManager &MPM,
                       ArrayRef<PassBuilder::PipelineElement> Pipeline,
                       bool VerifyEachPass, bool DebugLogging) {
   std::vector<PassBuilder::PipelineElement> FullPipeline;
   StringRef FirstName = Pipeline.front().Name;
 
   if (!isScopPassName(FirstName))
     return false;
 
-  FunctionPassManager FPM(DebugLogging);
+  CGSCCPassManager PM(DebugLogging);
   ScopPassManager SPM(DebugLogging);
 
   for (auto &Element : Pipeline) {
     auto &Name = Element.Name;
     auto &InnerPipeline = Element.InnerPipeline;
     if (!InnerPipeline.empty()) // Scop passes don't have inner pipelines
       return false;
     if (!parseScopPass(Name, SPM))
       return false;
   }
 
-  FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
-  if (VerifyEachPass)
-    FPM.addPass(VerifierPass());
-  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  PM.addPass(createCGSCCToScopPassAdaptor(std::move(SPM)));
+  // FIXME Regarding VerifyEachPass: There is no CGSCC-level verifier pass
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(PM)));
   if (VerifyEachPass)
     MPM.addPass(VerifierPass());
 
   return true;
 }
 
 void RegisterPollyPasses(PassBuilder &PB) {
   PB.registerAnalysisRegistrationCallback(registerFunctionAnalyses);
+  PB.registerAnalysisRegistrationCallback(registerScopAnalyses);
   PB.registerPipelineParsingCallback(parseFunctionPipeline);
   PB.registerPipelineParsingCallback(parseScopPipeline);
   PB.registerParseTopLevelPipelineCallback(parseTopLevelPipeline);
 
+  // FIXME There is no cgscc-level registerVectorizerStartEPCallback as
+  // of now
   if (PassPosition == POSITION_BEFORE_VECTORIZER)
-    PB.registerVectorizerStartEPCallback(buildDefaultPollyPipeline);
+    PB.registerCGSCCOptimizerLateEPCallback(buildDefaultPollyPipeline);
   // FIXME else Error?
 }
 } // namespace polly

unittests/ScopPassManager/PassManagerTest.cpp

 }
 
 TEST_F(ScopPassRegistry, PrintScopInfo) {
   FunctionPassManager FPM;
   FPM.addPass(ScopInfoPrinterPass(errs()));
 }
 
 TEST_F(ScopPassRegistry, PrinIslAstInfo) {
-  FunctionPassManager FPM;
+  CGSCCPassManager PM;
   ScopPassManager SPM;
   // SPM.addPass(IslAstPrinterPass(errs()));
-  FPM.addPass(createFunctionToScopPassAdaptor(std::move(SPM)));
+  PM.addPass(createCGSCCToScopPassAdaptor(std::move(SPM)));
 }
 } // namespace