text: //===- LoopPassManager.cpp - Loop pass management -------------------------===//
  //
  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  // See https://llvm.org/LICENSE.txt for license information.
  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  //
  //===----------------------------------------------------------------------===//
  
  #include "llvm/Transforms/Scalar/LoopPassManager.h"
  #include "llvm/Analysis/AssumptionCache.h"
  #include "llvm/Analysis/BlockFrequencyInfo.h"
  #include "llvm/Analysis/BranchProbabilityInfo.h"
  #include "llvm/Analysis/MemorySSA.h"
  #include "llvm/Analysis/ScalarEvolution.h"
  #include "llvm/Analysis/TargetLibraryInfo.h"
  #include "llvm/Analysis/TargetTransformInfo.h"
  #include "llvm/Support/TimeProfiler.h"
  
  using namespace llvm;
  
  namespace llvm {
  
  /// Explicitly specialize the pass manager's run method to handle loop nest
  /// structure updates.
  PreservedAnalyses
  PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
              LPMUpdater &>::run(Loop &L, LoopAnalysisManager &AM,
                                 LoopStandardAnalysisResults &AR, LPMUpdater &U) {
    // 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>>();
  
    return PA;
  }
  
  void PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
                   LPMUpdater &>::printPipeline(raw_ostream &OS,
                                                function_ref<StringRef(StringRef)>
                                                    MapClassName2PassName) {
    assert(LoopPasses.size() + LoopNestPasses.size() == IsLoopNestPass.size());
  
    unsigned IdxLP = 0, IdxLNP = 0;
    for (unsigned Idx = 0, Size = IsLoopNestPass.size(); Idx != Size; ++Idx) {
      if (IsLoopNestPass[Idx]) {
        auto *P = LoopNestPasses[IdxLNP++].get();
        P->printPipeline(OS, MapClassName2PassName);
      } else {
        auto *P = LoopPasses[IdxLP++].get();
        P->printPipeline(OS, MapClassName2PassName);
      }
      if (Idx + 1 < Size)
        OS << ",";
    }
  }
  
  // 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);
  
    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);
      }
  
      // `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;
  }
  
  // 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();
  
    // 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));
  
      // 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;
  }
  } // namespace llvm
  
  void FunctionToLoopPassAdaptor::printPipeline(
      raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
    OS << (UseMemorySSA ? "loop-mssa(" : "loop(");
    Pass->printPipeline(OS, MapClassName2PassName);
    OS << ")";
  }
  PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,
                                                   FunctionAnalysisManager &AM) {
    // Before we even compute any loop analyses, first run a miniature function
    // pass pipeline to put loops into their canonical form. Note that we can
    // directly build up function analyses after this as the function pass
    // manager handles all the invalidation at that layer.
    PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
  
    PreservedAnalyses PA = PreservedAnalyses::all();
    // Check the PassInstrumentation's BeforePass callbacks before running the
    // canonicalization pipeline.
    if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
      PA = LoopCanonicalizationFPM.run(F, AM);
      PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);
    }
  
    // Get the loop structure for this function
    LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
  
    // If there are no loops, there is nothing to do here.
    if (LI.empty())
      return PA;
  
    // Get the analysis results needed by loop passes.
    MemorySSA *MSSA =
        UseMemorySSA ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) : nullptr;
    BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
                                  ? (&AM.getResult<BlockFrequencyAnalysis>(F))
                                  : nullptr;
    BranchProbabilityInfo *BPI =
        UseBranchProbabilityInfo && F.hasProfileData()
            ? (&AM.getResult<BranchProbabilityAnalysis>(F))
            : nullptr;
    LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
                                       AM.getResult<AssumptionAnalysis>(F),
                                       AM.getResult<DominatorTreeAnalysis>(F),
                                       AM.getResult<LoopAnalysis>(F),
                                       AM.getResult<ScalarEvolutionAnalysis>(F),
                                       AM.getResult<TargetLibraryAnalysis>(F),
                                       AM.getResult<TargetIRAnalysis>(F),
                                       BFI,
                                       BPI,
                                       MSSA};
  
    // Setup the loop analysis manager from its proxy. It is important that
    // this is only done when there are loops to process and we have built the
    // LoopStandardAnalysisResults object. The loop analyses cached in this
    // manager have access to those analysis results and so it must invalidate
    // itself when they go away.
    auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
    if (UseMemorySSA)
      LAMFP.markMSSAUsed();
    LoopAnalysisManager &LAM = LAMFP.getManager();
  
    // A postorder worklist of loops to process.
    SmallPriorityWorklist<Loop *, 4> Worklist;
  
    // Register the worklist and loop analysis manager so that loop passes can
    // update them when they mutate the loop nest structure.
    LPMUpdater Updater(Worklist, LAM, LoopNestMode);
  
    // Add the loop nests in the reverse order of LoopInfo. See method
    // declaration.
    if (!LoopNestMode) {
      appendLoopsToWorklist(LI, Worklist);
    } else {
      for (Loop *L : LI)
        Worklist.insert(L);
    }
  
  #ifndef NDEBUG
    PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
      if (isSpecialPass(PassID, {"PassManager"}))
        return;
      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.
      L->verifyLoop();
      assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
             "Loops must remain in LCSSA form!");
    });
  #endif
  
    do {
      Loop *L = Worklist.pop_back_val();
      assert(!(LoopNestMode && L->getParentLoop()) &&
             "L should be a top-level loop in loop-nest mode.");
  
      // Reset the update structure for this loop.
      Updater.CurrentL = L;
      Updater.SkipCurrentLoop = false;
  
  #ifndef NDEBUG
      // Save a parent loop pointer for asserts.
      Updater.ParentL = L->getParentLoop();
  #endif
      // 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());
        PassPA = Pass->run(*L, LAM, LAR, Updater);
      }
  
      // Do not pass deleted Loop into the instrumentation.
      if (Updater.skipCurrentLoop())
        PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);
      else
        PI.runAfterPass<Loop>(*Pass, *L, PassPA);
  
      if (LAR.MSSA && !PassPA.getChecker<MemorySSAAnalysis>().preserved())
        report_fatal_error("Loop pass manager using MemorySSA contains a pass "
                           "that does not preserve MemorySSA");
  
  #ifndef NDEBUG
      // LoopAnalysisResults should always be valid.
      if (VerifyDomInfo)
        LAR.DT.verify();
      if (VerifyLoopInfo)
        LAR.LI.verify(LAR.DT);
      if (VerifySCEV)
        LAR.SE.verify();
      if (LAR.MSSA && VerifyMemorySSA)
        LAR.MSSA->verifyMemorySSA();
  #endif
  
      // If the loop hasn't been deleted, we need to handle invalidation here.
      if (!Updater.skipCurrentLoop())
        // We know that the loop pass couldn't have invalidated any other
        // loop's analyses (that's the contract of a loop pass), so directly
        // handle the loop analysis manager's invalidation here.
        LAM.invalidate(*L, PassPA);
  
      // Then intersect the preserved set so that invalidation of module
      // analyses will eventually occur when the module pass completes.
      PA.intersect(std::move(PassPA));
    } while (!Worklist.empty());
  
  #ifndef NDEBUG
    PI.popBeforeNonSkippedPassCallback();
  #endif
  
    // By definition we preserve the proxy. We also preserve all analyses on
    // Loops. This precludes *any* invalidation of loop analyses by the proxy,
    // but that's OK because we've taken care to invalidate analyses in the
    // loop analysis manager incrementally above.
    PA.preserveSet<AllAnalysesOn<Loop>>();
    PA.preserve<LoopAnalysisManagerFunctionProxy>();
    // We also preserve the set of standard analyses.
    PA.preserve<DominatorTreeAnalysis>();
    PA.preserve<LoopAnalysis>();
    PA.preserve<ScalarEvolutionAnalysis>();
    if (UseBlockFrequencyInfo && F.hasProfileData())
      PA.preserve<BlockFrequencyAnalysis>();
    if (UseBranchProbabilityInfo && F.hasProfileData())
      PA.preserve<BranchProbabilityAnalysis>();
    if (UseMemorySSA)
      PA.preserve<MemorySSAAnalysis>();
    return PA;
  }
  
  PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}
  PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
      : OS(OS), Banner(Banner) {}
  
  PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &,
                                       LoopStandardAnalysisResults &,
                                       LPMUpdater &) {
    printLoop(L, OS, Banner);
    return PreservedAnalyses::all();
  }
  