[LoopPassManager] Implement and use LoopNestAnalysis::run() instead of manually creating LoopNests

[aeubanks]

Summary

The current code is basically just emulating what the analysis manager does.

[uabelho]

Hello,

I bisected a crash back to this commit:

opt -passes='function(loop-flatten,loop(loop-unroll-and-jam,loop-deletion))' bbi-73307.ll -o /dev/null

crashes with

opt: ../include/llvm/Analysis/LoopInfo.h:160: const std::vector<LoopT *> &llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getSubLoops() const [BlockT = llvm::BasicBlock, LoopT = llvm::Loop]: Assertion `!isInvalid() && "Loop not in a valid state!"' failed.

bbi-73307.ll505 BDownload

[aeubanks]

reverted

I think the issue is that the loop nest analysis is a loop analysis. If we already have the loop nest analysis cached, if there's an inner loop that gets modified (deleted in this case), the loop nest analysis on the outer-most loop is not invalidated. Perhaps the loop nest shouldn't be a loop analysis.

llvm/lib/Analysis/LoopNestAnalysis.cpp

raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
   OS << ", Loops: ( ";
   for (const Loop *L : LN.getLoops())
     OS << L->getName() << " ";
   OS << ")";
 
   return OS;
 }
 
+LoopNestAnalysis::Result
+LoopNestAnalysis::run(Loop &L, LoopAnalysisManager &AM,
+                      LoopStandardAnalysisResults &AR) {
+  return LoopNest(L, AR.SE);
+}
+
 //===----------------------------------------------------------------------===//
 // LoopNestPrinterPass implementation
 //
 
 PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &U) {
   if (auto LN = LoopNest::getLoopNest(L, AR.SE))
     OS << *LN << "\n";
 
   return PreservedAnalyses::all();
 }

llvm/lib/Passes/PassRegistry.def

 #ifndef LOOP_ANALYSIS
 #define LOOP_ANALYSIS(NAME, CREATE_PASS)
 #endif
 LOOP_ANALYSIS("no-op-loop", NoOpLoopAnalysis())
 LOOP_ANALYSIS("access-info", LoopAccessAnalysis())
 LOOP_ANALYSIS("ddg", DDGAnalysis())
 LOOP_ANALYSIS("iv-users", IVUsersAnalysis())
 LOOP_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))
+LOOP_ANALYSIS("loop-nest", LoopNestAnalysis())
 #undef LOOP_ANALYSIS
 
 #ifndef LOOP_PASS
 #define LOOP_PASS(NAME, CREATE_PASS)
 #endif
 LOOP_PASS("canon-freeze", CanonicalizeFreezeInLoopsPass())
 LOOP_PASS("dot-ddg", DDGDotPrinterPass())
 LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass())

llvm/lib/Transforms/Scalar/LoopPassManager.cpp

LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM,
   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);
 
   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);
+      LoopNest &LN = AM.getResult<LoopNestAnalysis>(L, AR);
+      PassPA = runSinglePass(LN, 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));
 
-    // Check if the current pass preserved the loop-nest object or not.
-    IsLoopNestPtrValid &= PassPA->getChecker<LoopNestAnalysis>().preserved();
-
     // After running the loop pass, the parent loop might change and we need to
     // notify the updater, otherwise U.ParentL might gets outdated and triggers
     // assertion failures in addSiblingLoops and addChildLoops.
     U.setParentLoop(L.getParentLoop());
   }
   return PA;
 }
 

llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp

LoopPassManagerTest()
                   "  br i1 %cond.0, label %loop.g.0, label %end\n"
                   "end:\n"
                   "  ret void\n"
                   "}\n")),
         LAM(), FAM(), MAM() {
     // Register our mock analysis.
     LAM.registerPass([&] { return MLAHandle.getAnalysis(); });
 
+    LAM.registerPass([&] { return LoopNestAnalysis(); });
+
     // We need DominatorTreeAnalysis for LoopAnalysis.
     FAM.registerPass([&] { return DominatorTreeAnalysis(); });
     FAM.registerPass([&] { return LoopAnalysis(); });
     // We also allow loop passes to assume a set of other analyses and so need
     // those.
     FAM.registerPass([&] { return AAManager(); });
     FAM.registerPass([&] { return AssumptionAnalysis(); });
     FAM.registerPass([&] { return BlockFrequencyAnalysis(); });