354 lines · cpp
1//===- LoopPassManager.cpp - Loop pass management -------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Transforms/Scalar/LoopPassManager.h"10#include "llvm/Analysis/AssumptionCache.h"11#include "llvm/Analysis/MemorySSA.h"12#include "llvm/Analysis/ScalarEvolution.h"13#include "llvm/Analysis/TargetLibraryInfo.h"14#include "llvm/Analysis/TargetTransformInfo.h"15 16using namespace llvm;17 18/// Explicitly specialize the pass manager's run method to handle loop nest19/// structure updates.20PreservedAnalyses21PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,22 LPMUpdater &>::run(Loop &L, LoopAnalysisManager &AM,23 LoopStandardAnalysisResults &AR, LPMUpdater &U) {24 // Runs loop-nest passes only when the current loop is a top-level one.25 PreservedAnalyses PA = (L.isOutermost() && !LoopNestPasses.empty())26 ? runWithLoopNestPasses(L, AM, AR, U)27 : runWithoutLoopNestPasses(L, AM, AR, U);28 29 // Invalidation for the current loop should be handled above, and other loop30 // analysis results shouldn't be impacted by runs over this loop. Therefore,31 // the remaining analysis results in the AnalysisManager are preserved. We32 // mark this with a set so that we don't need to inspect each one33 // individually.34 // FIXME: This isn't correct! This loop and all nested loops' analyses should35 // be preserved, but unrolling should invalidate the parent loop's analyses.36 PA.preserveSet<AllAnalysesOn<Loop>>();37 38 return PA;39}40 41void PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,42 LPMUpdater &>::printPipeline(raw_ostream &OS,43 function_ref<StringRef(StringRef)>44 MapClassName2PassName) {45 assert(LoopPasses.size() + LoopNestPasses.size() == IsLoopNestPass.size());46 47 unsigned IdxLP = 0, IdxLNP = 0;48 for (unsigned Idx = 0, Size = IsLoopNestPass.size(); Idx != Size; ++Idx) {49 if (IsLoopNestPass[Idx]) {50 auto *P = LoopNestPasses[IdxLNP++].get();51 P->printPipeline(OS, MapClassName2PassName);52 } else {53 auto *P = LoopPasses[IdxLP++].get();54 P->printPipeline(OS, MapClassName2PassName);55 }56 if (Idx + 1 < Size)57 OS << ',';58 }59}60 61// Run both loop passes and loop-nest passes on top-level loop \p L.62PreservedAnalyses63LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM,64 LoopStandardAnalysisResults &AR,65 LPMUpdater &U) {66 assert(L.isOutermost() &&67 "Loop-nest passes should only run on top-level loops.");68 PreservedAnalyses PA = PreservedAnalyses::all();69 70 // Request PassInstrumentation from analysis manager, will use it to run71 // instrumenting callbacks for the passes later.72 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(L, AR);73 74 unsigned LoopPassIndex = 0, LoopNestPassIndex = 0;75 76 // `LoopNestPtr` points to the `LoopNest` object for the current top-level77 // loop and `IsLoopNestPtrValid` indicates whether the pointer is still valid.78 // The `LoopNest` object will have to be re-constructed if the pointer is79 // invalid when encountering a loop-nest pass.80 std::unique_ptr<LoopNest> LoopNestPtr;81 bool IsLoopNestPtrValid = false;82 Loop *OuterMostLoop = &L;83 84 for (size_t I = 0, E = IsLoopNestPass.size(); I != E; ++I) {85 std::optional<PreservedAnalyses> PassPA;86 if (!IsLoopNestPass[I]) {87 // The `I`-th pass is a loop pass.88 auto &Pass = LoopPasses[LoopPassIndex++];89 PassPA = runSinglePass(L, Pass, AM, AR, U, PI);90 } else {91 // The `I`-th pass is a loop-nest pass.92 auto &Pass = LoopNestPasses[LoopNestPassIndex++];93 94 // If the loop-nest object calculated before is no longer valid,95 // re-calculate it here before running the loop-nest pass.96 //97 // FIXME: PreservedAnalysis should not be abused to tell if the98 // status of loopnest has been changed. We should use and only99 // use LPMUpdater for this purpose.100 if (!IsLoopNestPtrValid || U.isLoopNestChanged()) {101 while (auto *ParentLoop = OuterMostLoop->getParentLoop())102 OuterMostLoop = ParentLoop;103 LoopNestPtr = LoopNest::getLoopNest(*OuterMostLoop, AR.SE);104 IsLoopNestPtrValid = true;105 U.markLoopNestChanged(false);106 }107 108 PassPA = runSinglePass(*LoopNestPtr, Pass, AM, AR, U, PI);109 }110 111 // `PassPA` is `None` means that the before-pass callbacks in112 // `PassInstrumentation` return false. The pass does not run in this case,113 // so we can skip the following procedure.114 if (!PassPA)115 continue;116 117 // If the loop was deleted, abort the run and return to the outer walk.118 if (U.skipCurrentLoop()) {119 PA.intersect(std::move(*PassPA));120 break;121 }122 123 // Update the analysis manager as each pass runs and potentially124 // invalidates analyses.125 AM.invalidate(IsLoopNestPass[I] ? *OuterMostLoop : L, *PassPA);126 127 // Finally, we intersect the final preserved analyses to compute the128 // aggregate preserved set for this pass manager.129 PA.intersect(std::move(*PassPA));130 131 // Check if the current pass preserved the loop-nest object or not.132 IsLoopNestPtrValid &= PassPA->getChecker<LoopNestAnalysis>().preserved();133 134 // After running the loop pass, the parent loop might change and we need to135 // notify the updater, otherwise U.ParentL might gets outdated and triggers136 // assertion failures in addSiblingLoops and addChildLoops.137 U.setParentLoop((IsLoopNestPass[I] ? *OuterMostLoop : L).getParentLoop());138 }139 return PA;140}141 142// Run all loop passes on loop \p L. Loop-nest passes don't run either because143// \p L is not a top-level one or simply because there are no loop-nest passes144// in the pass manager at all.145PreservedAnalyses146LoopPassManager::runWithoutLoopNestPasses(Loop &L, LoopAnalysisManager &AM,147 LoopStandardAnalysisResults &AR,148 LPMUpdater &U) {149 PreservedAnalyses PA = PreservedAnalyses::all();150 151 // Request PassInstrumentation from analysis manager, will use it to run152 // instrumenting callbacks for the passes later.153 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(L, AR);154 for (auto &Pass : LoopPasses) {155 std::optional<PreservedAnalyses> PassPA =156 runSinglePass(L, Pass, AM, AR, U, PI);157 158 // `PassPA` is `None` means that the before-pass callbacks in159 // `PassInstrumentation` return false. The pass does not run in this case,160 // so we can skip the following procedure.161 if (!PassPA)162 continue;163 164 // If the loop was deleted, abort the run and return to the outer walk.165 if (U.skipCurrentLoop()) {166 PA.intersect(std::move(*PassPA));167 break;168 }169 170 // Update the analysis manager as each pass runs and potentially171 // invalidates analyses.172 AM.invalidate(L, *PassPA);173 174 // Finally, we intersect the final preserved analyses to compute the175 // aggregate preserved set for this pass manager.176 PA.intersect(std::move(*PassPA));177 178 // After running the loop pass, the parent loop might change and we need to179 // notify the updater, otherwise U.ParentL might gets outdated and triggers180 // assertion failures in addSiblingLoops and addChildLoops.181 U.setParentLoop(L.getParentLoop());182 }183 return PA;184}185 186void FunctionToLoopPassAdaptor::printPipeline(187 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {188 OS << (UseMemorySSA ? "loop-mssa(" : "loop(");189 Pass->printPipeline(OS, MapClassName2PassName);190 OS << ')';191}192 193PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,194 FunctionAnalysisManager &AM) {195 // Before we even compute any loop analyses, first run a miniature function196 // pass pipeline to put loops into their canonical form. Note that we can197 // directly build up function analyses after this as the function pass198 // manager handles all the invalidation at that layer.199 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);200 201 PreservedAnalyses PA = PreservedAnalyses::all();202 // Check the PassInstrumentation's BeforePass callbacks before running the203 // canonicalization pipeline.204 if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {205 PA = LoopCanonicalizationFPM.run(F, AM);206 PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);207 }208 209 // Get the loop structure for this function210 LoopInfo &LI = AM.getResult<LoopAnalysis>(F);211 212 // If there are no loops, there is nothing to do here.213 if (LI.empty())214 return PA;215 216 // Get the analysis results needed by loop passes.217 MemorySSA *MSSA =218 UseMemorySSA ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) : nullptr;219 LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),220 AM.getResult<AssumptionAnalysis>(F),221 AM.getResult<DominatorTreeAnalysis>(F),222 AM.getResult<LoopAnalysis>(F),223 AM.getResult<ScalarEvolutionAnalysis>(F),224 AM.getResult<TargetLibraryAnalysis>(F),225 AM.getResult<TargetIRAnalysis>(F),226 MSSA};227 228 // Setup the loop analysis manager from its proxy. It is important that229 // this is only done when there are loops to process and we have built the230 // LoopStandardAnalysisResults object. The loop analyses cached in this231 // manager have access to those analysis results and so it must invalidate232 // itself when they go away.233 auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);234 if (UseMemorySSA)235 LAMFP.markMSSAUsed();236 LoopAnalysisManager &LAM = LAMFP.getManager();237 238 // A postorder worklist of loops to process.239 SmallPriorityWorklist<Loop *, 4> Worklist;240 241 // Register the worklist and loop analysis manager so that loop passes can242 // update them when they mutate the loop nest structure.243 LPMUpdater Updater(Worklist, LAM, LoopNestMode);244 245 // Add the loop nests in the reverse order of LoopInfo. See method246 // declaration.247 if (!LoopNestMode) {248 appendLoopsToWorklist(LI, Worklist);249 } else {250 for (Loop *L : LI)251 Worklist.insert(L);252 }253 254#ifndef NDEBUG255 PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {256 if (isSpecialPass(PassID, {"PassManager"}))257 return;258 assert(llvm::any_cast<const Loop *>(&IR));259 const Loop **LPtr = llvm::any_cast<const Loop *>(&IR);260 const Loop *L = LPtr ? *LPtr : nullptr;261 assert(L && "Loop should be valid for printing");262 263 // Verify the loop structure and LCSSA form before visiting the loop.264 L->verifyLoop();265 assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&266 "Loops must remain in LCSSA form!");267 });268#endif269 270 do {271 Loop *L = Worklist.pop_back_val();272 assert(!(LoopNestMode && L->getParentLoop()) &&273 "L should be a top-level loop in loop-nest mode.");274 275 // Reset the update structure for this loop.276 Updater.CurrentL = L;277 Updater.SkipCurrentLoop = false;278 279#if LLVM_ENABLE_ABI_BREAKING_CHECKS280 // Save a parent loop pointer for asserts.281 Updater.ParentL = L->getParentLoop();282#endif283 // Check the PassInstrumentation's BeforePass callbacks before running the284 // pass, skip its execution completely if asked to (callback returns285 // false).286 if (!PI.runBeforePass<Loop>(*Pass, *L))287 continue;288 289 PreservedAnalyses PassPA = Pass->run(*L, LAM, LAR, Updater);290 291 // Do not pass deleted Loop into the instrumentation.292 if (Updater.skipCurrentLoop())293 PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);294 else295 PI.runAfterPass<Loop>(*Pass, *L, PassPA);296 297 if (LAR.MSSA && !PassPA.getChecker<MemorySSAAnalysis>().preserved())298 reportFatalUsageError("Loop pass manager using MemorySSA contains a pass "299 "that does not preserve MemorySSA");300 301#ifndef NDEBUG302 // LoopAnalysisResults should always be valid.303 if (VerifyDomInfo)304 LAR.DT.verify();305 if (VerifyLoopInfo)306 LAR.LI.verify(LAR.DT);307 if (VerifySCEV)308 LAR.SE.verify();309 if (LAR.MSSA && VerifyMemorySSA)310 LAR.MSSA->verifyMemorySSA();311#endif312 313 // If the loop hasn't been deleted, we need to handle invalidation here.314 if (!Updater.skipCurrentLoop())315 // We know that the loop pass couldn't have invalidated any other316 // loop's analyses (that's the contract of a loop pass), so directly317 // handle the loop analysis manager's invalidation here.318 LAM.invalidate(*L, PassPA);319 320 // Then intersect the preserved set so that invalidation of module321 // analyses will eventually occur when the module pass completes.322 PA.intersect(std::move(PassPA));323 } while (!Worklist.empty());324 325#ifndef NDEBUG326 PI.popBeforeNonSkippedPassCallback();327#endif328 329 // By definition we preserve the proxy. We also preserve all analyses on330 // Loops. This precludes *any* invalidation of loop analyses by the proxy,331 // but that's OK because we've taken care to invalidate analyses in the332 // loop analysis manager incrementally above.333 PA.preserveSet<AllAnalysesOn<Loop>>();334 PA.preserve<LoopAnalysisManagerFunctionProxy>();335 // We also preserve the set of standard analyses.336 PA.preserve<DominatorTreeAnalysis>();337 PA.preserve<LoopAnalysis>();338 PA.preserve<ScalarEvolutionAnalysis>();339 if (UseMemorySSA)340 PA.preserve<MemorySSAAnalysis>();341 return PA;342}343 344PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}345PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)346 : OS(OS), Banner(Banner) {}347 348PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &,349 LoopStandardAnalysisResults &,350 LPMUpdater &) {351 printLoop(L, OS, Banner);352 return PreservedAnalyses::all();353}354