[LoopNest] Handle loop-nest passes in LoopPassManager

Per http://llvm.org/OpenProjects.html#llvm_loopnest, the goal of this
patch (and other following patches) is to create facilities that allow
implementing loop nest passes that run on top-level loop nests for the
New Pass Manager.

This patch extends the functionality of LoopPassManager to handle
loop-nest passes by specializing the definition of LoopPassManager that
accepts both kinds of passes in addPass.

Only loop passes are executed if L is not a top-level one, and both
kinds of passes are executed if L is top-level. Currently, loop nest
passes should have the following run method:

PreservedAnalyses run(LoopNest &, LoopAnalysisManager &,
LoopStandardAnalysisResults &, LPMUpdater &);

Reviewed By: Whitney, ychen
Differential Revision: https://reviews.llvm.org/D87045

1 files changed, 112 insertions, 36 deletions

diff --git a/llvm/lib/Transforms/Scalar/LoopPassManager.cpp b/llvm/lib/Transforms/Scalar/LoopPassManager.cpp
index 90e23c8..809f43e 100644
--- a/llvm/lib/Transforms/Scalar/LoopPassManager.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopPassManager.cpp
@@ -12,58 +12,101 @@
 
 using namespace llvm;
 
-// Explicit template instantiations and specialization defininitions for core
-// template typedefs.
 namespace llvm {
-template class PassManager<Loop, LoopAnalysisManager,
-                           LoopStandardAnalysisResults &, LPMUpdater &>;
 
 /// Explicitly specialize the pass manager's run method to handle loop nest
 /// structure updates.
-template <>
 PreservedAnalyses
 PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
             LPMUpdater &>::run(Loop &L, LoopAnalysisManager &AM,
                                LoopStandardAnalysisResults &AR, LPMUpdater &U) {
-  PreservedAnalyses PA = PreservedAnalyses::all();
 
   if (DebugLogging)
     dbgs() << "Starting Loop pass manager run.\n";
 
+  // Runs loop-nest passes only when the current loop is a top-level one.
+  PreservedAnalyses PA = (L.isOutermost() && !LoopNestPasses.empty())
+                             ? runWithLoopNestPasses(L, AM, AR, U)
+                             : runWithoutLoopNestPasses(L, AM, AR, U);
+
+  // Invalidation for the current loop should be handled above, and other loop
+  // analysis results shouldn't be impacted by runs over this loop. Therefore,
+  // the remaining analysis results in the AnalysisManager are preserved. We
+  // mark this with a set so that we don't need to inspect each one
+  // individually.
+  // FIXME: This isn't correct! This loop and all nested loops' analyses should
+  // be preserved, but unrolling should invalidate the parent loop's analyses.
+  PA.preserveSet<AllAnalysesOn<Loop>>();
+
+  if (DebugLogging)
+    dbgs() << "Finished Loop pass manager run.\n";
+
+  return PA;
+}
+
+// Run both loop passes and loop-nest passes on top-level loop \p L.
+PreservedAnalyses
+LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM,
+                                       LoopStandardAnalysisResults &AR,
+                                       LPMUpdater &U) {
+  assert(L.isOutermost() &&
+         "Loop-nest passes should only run on top-level loops.");
+  PreservedAnalyses PA = PreservedAnalyses::all();
+
   // Request PassInstrumentation from analysis manager, will use it to run
   // instrumenting callbacks for the passes later.
   PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(L, AR);
-  for (auto &Pass : Passes) {
-    // Check the PassInstrumentation's BeforePass callbacks before running the
-    // pass, skip its execution completely if asked to (callback returns false).
-    if (!PI.runBeforePass<Loop>(*Pass, L))
-      continue;
 
-    PreservedAnalyses PassPA;
-    {
-      TimeTraceScope TimeScope(Pass->name(), L.getName());
-      PassPA = Pass->run(L, AM, AR, U);
+  unsigned LoopPassIndex = 0, LoopNestPassIndex = 0;
+
+  // `LoopNestPtr` points to the `LoopNest` object for the current top-level
+  // loop and `IsLoopNestPtrValid` indicates whether the pointer is still valid.
+  // The `LoopNest` object will have to be re-constructed if the pointer is
+  // invalid when encountering a loop-nest pass.
+  std::unique_ptr<LoopNest> LoopNestPtr;
+  bool IsLoopNestPtrValid = false;
+
+  for (size_t I = 0, E = IsLoopNestPass.size(); I != E; ++I) {
+    Optional<PreservedAnalyses> PassPA;
+    if (!IsLoopNestPass[I]) {
+      // The `I`-th pass is a loop pass.
+      auto &Pass = LoopPasses[LoopPassIndex++];
+      PassPA = runSinglePass(L, Pass, AM, AR, U, PI);
+    } else {
+      // The `I`-th pass is a loop-nest pass.
+      auto &Pass = LoopNestPasses[LoopNestPassIndex++];
+
+      // If the loop-nest object calculated before is no longer valid,
+      // re-calculate it here before running the loop-nest pass.
+      if (!IsLoopNestPtrValid) {
+        LoopNestPtr = LoopNest::getLoopNest(L, AR.SE);
+        IsLoopNestPtrValid = true;
+      }
+      PassPA = runSinglePass(*LoopNestPtr, Pass, AM, AR, U, PI);
     }
 
-    // do not pass deleted Loop into the instrumentation
-    if (U.skipCurrentLoop())
-      PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);
-    else
-      PI.runAfterPass<Loop>(*Pass, L, PassPA);
+    // `PassPA` is `None` means that the before-pass callbacks in
+    // `PassInstrumentation` return false. The pass does not run in this case,
+    // so we can skip the following procedure.
+    if (!PassPA)
+      continue;
 
     // If the loop was deleted, abort the run and return to the outer walk.
     if (U.skipCurrentLoop()) {
-      PA.intersect(std::move(PassPA));
+      PA.intersect(std::move(*PassPA));
       break;
     }
 
     // Update the analysis manager as each pass runs and potentially
     // invalidates analyses.
-    AM.invalidate(L, PassPA);
+    AM.invalidate(L, *PassPA);
 
     // Finally, we intersect the final preserved analyses to compute the
     // aggregate preserved set for this pass manager.
-    PA.intersect(std::move(PassPA));
+    PA.intersect(std::move(*PassPA));
+
+    // Check if the current pass preserved the loop-nest object or not.
+    IsLoopNestPtrValid &= PassPA->getChecker<LoopNestAnalysis>().preserved();
 
     // FIXME: Historically, the pass managers all called the LLVM context's
     // yield function here. We don't have a generic way to acquire the
@@ -71,22 +114,53 @@ PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
     // in the new pass manager so it is currently omitted.
     // ...getContext().yield();
   }
+  return PA;
+}
 
-  // Invalidation for the current loop should be handled above, and other loop
-  // analysis results shouldn't be impacted by runs over this loop. Therefore,
-  // the remaining analysis results in the AnalysisManager are preserved. We
-  // mark this with a set so that we don't need to inspect each one
-  // individually.
-  // FIXME: This isn't correct! This loop and all nested loops' analyses should
-  // be preserved, but unrolling should invalidate the parent loop's analyses.
-  PA.preserveSet<AllAnalysesOn<Loop>>();
+// Run all loop passes on loop \p L. Loop-nest passes don't run either because
+// \p L is not a top-level one or simply because there are no loop-nest passes
+// in the pass manager at all.
+PreservedAnalyses
+LoopPassManager::runWithoutLoopNestPasses(Loop &L, LoopAnalysisManager &AM,
+                                          LoopStandardAnalysisResults &AR,
+                                          LPMUpdater &U) {
+  PreservedAnalyses PA = PreservedAnalyses::all();
 
-  if (DebugLogging)
-    dbgs() << "Finished Loop pass manager run.\n";
+  // Request PassInstrumentation from analysis manager, will use it to run
+  // instrumenting callbacks for the passes later.
+  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(L, AR);
+  for (auto &Pass : LoopPasses) {
+    Optional<PreservedAnalyses> PassPA = runSinglePass(L, Pass, AM, AR, U, PI);
 
+    // `PassPA` is `None` means that the before-pass callbacks in
+    // `PassInstrumentation` return false. The pass does not run in this case,
+    // so we can skip the following procedure.
+    if (!PassPA)
+      continue;
+
+    // If the loop was deleted, abort the run and return to the outer walk.
+    if (U.skipCurrentLoop()) {
+      PA.intersect(std::move(*PassPA));
+      break;
+    }
+
+    // Update the analysis manager as each pass runs and potentially
+    // invalidates analyses.
+    AM.invalidate(L, *PassPA);
+
+    // Finally, we intersect the final preserved analyses to compute the
+    // aggregate preserved set for this pass manager.
+    PA.intersect(std::move(*PassPA));
+
+    // FIXME: Historically, the pass managers all called the LLVM context's
+    // yield function here. We don't have a generic way to acquire the
+    // context and it isn't yet clear what the right pattern is for yielding
+    // in the new pass manager so it is currently omitted.
+    // ...getContext().yield();
+  }
   return PA;
 }
-}
+} // namespace llvm
 
 PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
@@ -152,8 +226,10 @@ PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,
   PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
     if (isSpecialPass(PassID, {"PassManager"}))
       return;
-    assert(any_isa<const Loop *>(IR));
-    const Loop *L = any_cast<const Loop *>(IR);
+    assert(any_isa<const Loop *>(IR) || any_isa<const LoopNest *>(IR));
+    const Loop *L = any_isa<const Loop *>(IR)
+                        ? any_cast<const Loop *>(IR)
+                        : &any_cast<const LoopNest *>(IR)->getOutermostLoop();
     assert(L && "Loop should be valid for printing");
 
     // Verify the loop structure and LCSSA form before visiting the loop.