LoopPassManager.cpp 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373
  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-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. #include "llvm/Transforms/Scalar/LoopPassManager.h"
  9. #include "llvm/Analysis/AssumptionCache.h"
  10. #include "llvm/Analysis/BlockFrequencyInfo.h"
  11. #include "llvm/Analysis/BranchProbabilityInfo.h"
  12. #include "llvm/Analysis/MemorySSA.h"
  13. #include "llvm/Analysis/ScalarEvolution.h"
  14. #include "llvm/Analysis/TargetLibraryInfo.h"
  15. #include "llvm/Analysis/TargetTransformInfo.h"
  16. #include "llvm/Support/TimeProfiler.h"
  17. using namespace llvm;
  18. namespace llvm {
  19. /// Explicitly specialize the pass manager's run method to handle loop nest
  20. /// structure updates.
  21. PreservedAnalyses
  22. PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
  23. LPMUpdater &>::run(Loop &L, LoopAnalysisManager &AM,
  24. LoopStandardAnalysisResults &AR, LPMUpdater &U) {
  25. // Runs loop-nest passes only when the current loop is a top-level one.
  26. PreservedAnalyses PA = (L.isOutermost() && !LoopNestPasses.empty())
  27. ? runWithLoopNestPasses(L, AM, AR, U)
  28. : runWithoutLoopNestPasses(L, AM, AR, U);
  29. // Invalidation for the current loop should be handled above, and other loop
  30. // analysis results shouldn't be impacted by runs over this loop. Therefore,
  31. // the remaining analysis results in the AnalysisManager are preserved. We
  32. // mark this with a set so that we don't need to inspect each one
  33. // individually.
  34. // FIXME: This isn't correct! This loop and all nested loops' analyses should
  35. // be preserved, but unrolling should invalidate the parent loop's analyses.
  36. PA.preserveSet<AllAnalysesOn<Loop>>();
  37. return PA;
  38. }
  39. void PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
  40. LPMUpdater &>::printPipeline(raw_ostream &OS,
  41. function_ref<StringRef(StringRef)>
  42. MapClassName2PassName) {
  43. assert(LoopPasses.size() + LoopNestPasses.size() == IsLoopNestPass.size());
  44. unsigned IdxLP = 0, IdxLNP = 0;
  45. for (unsigned Idx = 0, Size = IsLoopNestPass.size(); Idx != Size; ++Idx) {
  46. if (IsLoopNestPass[Idx]) {
  47. auto *P = LoopNestPasses[IdxLNP++].get();
  48. P->printPipeline(OS, MapClassName2PassName);
  49. } else {
  50. auto *P = LoopPasses[IdxLP++].get();
  51. P->printPipeline(OS, MapClassName2PassName);
  52. }
  53. if (Idx + 1 < Size)
  54. OS << ",";
  55. }
  56. }
  57. // Run both loop passes and loop-nest passes on top-level loop \p L.
  58. PreservedAnalyses
  59. LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM,
  60. LoopStandardAnalysisResults &AR,
  61. LPMUpdater &U) {
  62. assert(L.isOutermost() &&
  63. "Loop-nest passes should only run on top-level loops.");
  64. PreservedAnalyses PA = PreservedAnalyses::all();
  65. // Request PassInstrumentation from analysis manager, will use it to run
  66. // instrumenting callbacks for the passes later.
  67. PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(L, AR);
  68. unsigned LoopPassIndex = 0, LoopNestPassIndex = 0;
  69. // `LoopNestPtr` points to the `LoopNest` object for the current top-level
  70. // loop and `IsLoopNestPtrValid` indicates whether the pointer is still valid.
  71. // The `LoopNest` object will have to be re-constructed if the pointer is
  72. // invalid when encountering a loop-nest pass.
  73. std::unique_ptr<LoopNest> LoopNestPtr;
  74. bool IsLoopNestPtrValid = false;
  75. Loop *OuterMostLoop = &L;
  76. for (size_t I = 0, E = IsLoopNestPass.size(); I != E; ++I) {
  77. std::optional<PreservedAnalyses> PassPA;
  78. if (!IsLoopNestPass[I]) {
  79. // The `I`-th pass is a loop pass.
  80. auto &Pass = LoopPasses[LoopPassIndex++];
  81. PassPA = runSinglePass(L, Pass, AM, AR, U, PI);
  82. } else {
  83. // The `I`-th pass is a loop-nest pass.
  84. auto &Pass = LoopNestPasses[LoopNestPassIndex++];
  85. // If the loop-nest object calculated before is no longer valid,
  86. // re-calculate it here before running the loop-nest pass.
  87. //
  88. // FIXME: PreservedAnalysis should not be abused to tell if the
  89. // status of loopnest has been changed. We should use and only
  90. // use LPMUpdater for this purpose.
  91. if (!IsLoopNestPtrValid || U.isLoopNestChanged()) {
  92. while (auto *ParentLoop = OuterMostLoop->getParentLoop())
  93. OuterMostLoop = ParentLoop;
  94. LoopNestPtr = LoopNest::getLoopNest(*OuterMostLoop, AR.SE);
  95. IsLoopNestPtrValid = true;
  96. U.markLoopNestChanged(false);
  97. }
  98. PassPA = runSinglePass(*LoopNestPtr, Pass, AM, AR, U, PI);
  99. }
  100. // `PassPA` is `None` means that the before-pass callbacks in
  101. // `PassInstrumentation` return false. The pass does not run in this case,
  102. // so we can skip the following procedure.
  103. if (!PassPA)
  104. continue;
  105. // If the loop was deleted, abort the run and return to the outer walk.
  106. if (U.skipCurrentLoop()) {
  107. PA.intersect(std::move(*PassPA));
  108. break;
  109. }
  110. // Update the analysis manager as each pass runs and potentially
  111. // invalidates analyses.
  112. AM.invalidate(IsLoopNestPass[I] ? *OuterMostLoop : L, *PassPA);
  113. // Finally, we intersect the final preserved analyses to compute the
  114. // aggregate preserved set for this pass manager.
  115. PA.intersect(std::move(*PassPA));
  116. // Check if the current pass preserved the loop-nest object or not.
  117. IsLoopNestPtrValid &= PassPA->getChecker<LoopNestAnalysis>().preserved();
  118. // After running the loop pass, the parent loop might change and we need to
  119. // notify the updater, otherwise U.ParentL might gets outdated and triggers
  120. // assertion failures in addSiblingLoops and addChildLoops.
  121. U.setParentLoop((IsLoopNestPass[I] ? *OuterMostLoop : L).getParentLoop());
  122. }
  123. return PA;
  124. }
  125. // Run all loop passes on loop \p L. Loop-nest passes don't run either because
  126. // \p L is not a top-level one or simply because there are no loop-nest passes
  127. // in the pass manager at all.
  128. PreservedAnalyses
  129. LoopPassManager::runWithoutLoopNestPasses(Loop &L, LoopAnalysisManager &AM,
  130. LoopStandardAnalysisResults &AR,
  131. LPMUpdater &U) {
  132. PreservedAnalyses PA = PreservedAnalyses::all();
  133. // Request PassInstrumentation from analysis manager, will use it to run
  134. // instrumenting callbacks for the passes later.
  135. PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(L, AR);
  136. for (auto &Pass : LoopPasses) {
  137. std::optional<PreservedAnalyses> PassPA =
  138. runSinglePass(L, Pass, AM, AR, U, PI);
  139. // `PassPA` is `None` means that the before-pass callbacks in
  140. // `PassInstrumentation` return false. The pass does not run in this case,
  141. // so we can skip the following procedure.
  142. if (!PassPA)
  143. continue;
  144. // If the loop was deleted, abort the run and return to the outer walk.
  145. if (U.skipCurrentLoop()) {
  146. PA.intersect(std::move(*PassPA));
  147. break;
  148. }
  149. // Update the analysis manager as each pass runs and potentially
  150. // invalidates analyses.
  151. AM.invalidate(L, *PassPA);
  152. // Finally, we intersect the final preserved analyses to compute the
  153. // aggregate preserved set for this pass manager.
  154. PA.intersect(std::move(*PassPA));
  155. // After running the loop pass, the parent loop might change and we need to
  156. // notify the updater, otherwise U.ParentL might gets outdated and triggers
  157. // assertion failures in addSiblingLoops and addChildLoops.
  158. U.setParentLoop(L.getParentLoop());
  159. }
  160. return PA;
  161. }
  162. } // namespace llvm
  163. void FunctionToLoopPassAdaptor::printPipeline(
  164. raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
  165. OS << (UseMemorySSA ? "loop-mssa(" : "loop(");
  166. Pass->printPipeline(OS, MapClassName2PassName);
  167. OS << ")";
  168. }
  169. PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,
  170. FunctionAnalysisManager &AM) {
  171. // Before we even compute any loop analyses, first run a miniature function
  172. // pass pipeline to put loops into their canonical form. Note that we can
  173. // directly build up function analyses after this as the function pass
  174. // manager handles all the invalidation at that layer.
  175. PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
  176. PreservedAnalyses PA = PreservedAnalyses::all();
  177. // Check the PassInstrumentation's BeforePass callbacks before running the
  178. // canonicalization pipeline.
  179. if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
  180. PA = LoopCanonicalizationFPM.run(F, AM);
  181. PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);
  182. }
  183. // Get the loop structure for this function
  184. LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
  185. // If there are no loops, there is nothing to do here.
  186. if (LI.empty())
  187. return PA;
  188. // Get the analysis results needed by loop passes.
  189. MemorySSA *MSSA =
  190. UseMemorySSA ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) : nullptr;
  191. BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
  192. ? (&AM.getResult<BlockFrequencyAnalysis>(F))
  193. : nullptr;
  194. BranchProbabilityInfo *BPI =
  195. UseBranchProbabilityInfo && F.hasProfileData()
  196. ? (&AM.getResult<BranchProbabilityAnalysis>(F))
  197. : nullptr;
  198. LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
  199. AM.getResult<AssumptionAnalysis>(F),
  200. AM.getResult<DominatorTreeAnalysis>(F),
  201. AM.getResult<LoopAnalysis>(F),
  202. AM.getResult<ScalarEvolutionAnalysis>(F),
  203. AM.getResult<TargetLibraryAnalysis>(F),
  204. AM.getResult<TargetIRAnalysis>(F),
  205. BFI,
  206. BPI,
  207. MSSA};
  208. // Setup the loop analysis manager from its proxy. It is important that
  209. // this is only done when there are loops to process and we have built the
  210. // LoopStandardAnalysisResults object. The loop analyses cached in this
  211. // manager have access to those analysis results and so it must invalidate
  212. // itself when they go away.
  213. auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
  214. if (UseMemorySSA)
  215. LAMFP.markMSSAUsed();
  216. LoopAnalysisManager &LAM = LAMFP.getManager();
  217. // A postorder worklist of loops to process.
  218. SmallPriorityWorklist<Loop *, 4> Worklist;
  219. // Register the worklist and loop analysis manager so that loop passes can
  220. // update them when they mutate the loop nest structure.
  221. LPMUpdater Updater(Worklist, LAM, LoopNestMode);
  222. // Add the loop nests in the reverse order of LoopInfo. See method
  223. // declaration.
  224. if (!LoopNestMode) {
  225. appendLoopsToWorklist(LI, Worklist);
  226. } else {
  227. for (Loop *L : LI)
  228. Worklist.insert(L);
  229. }
  230. #ifndef NDEBUG
  231. PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
  232. if (isSpecialPass(PassID, {"PassManager"}))
  233. return;
  234. assert(any_cast<const Loop *>(&IR) || any_cast<const LoopNest *>(&IR));
  235. const Loop **LPtr = any_cast<const Loop *>(&IR);
  236. const Loop *L = LPtr ? *LPtr : nullptr;
  237. if (!L)
  238. L = &any_cast<const LoopNest *>(IR)->getOutermostLoop();
  239. assert(L && "Loop should be valid for printing");
  240. // Verify the loop structure and LCSSA form before visiting the loop.
  241. L->verifyLoop();
  242. assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
  243. "Loops must remain in LCSSA form!");
  244. });
  245. #endif
  246. do {
  247. Loop *L = Worklist.pop_back_val();
  248. assert(!(LoopNestMode && L->getParentLoop()) &&
  249. "L should be a top-level loop in loop-nest mode.");
  250. // Reset the update structure for this loop.
  251. Updater.CurrentL = L;
  252. Updater.SkipCurrentLoop = false;
  253. #ifndef NDEBUG
  254. // Save a parent loop pointer for asserts.
  255. Updater.ParentL = L->getParentLoop();
  256. #endif
  257. // Check the PassInstrumentation's BeforePass callbacks before running the
  258. // pass, skip its execution completely if asked to (callback returns
  259. // false).
  260. if (!PI.runBeforePass<Loop>(*Pass, *L))
  261. continue;
  262. PreservedAnalyses PassPA = Pass->run(*L, LAM, LAR, Updater);
  263. // Do not pass deleted Loop into the instrumentation.
  264. if (Updater.skipCurrentLoop())
  265. PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);
  266. else
  267. PI.runAfterPass<Loop>(*Pass, *L, PassPA);
  268. if (LAR.MSSA && !PassPA.getChecker<MemorySSAAnalysis>().preserved())
  269. report_fatal_error("Loop pass manager using MemorySSA contains a pass "
  270. "that does not preserve MemorySSA");
  271. #ifndef NDEBUG
  272. // LoopAnalysisResults should always be valid.
  273. if (VerifyDomInfo)
  274. LAR.DT.verify();
  275. if (VerifyLoopInfo)
  276. LAR.LI.verify(LAR.DT);
  277. if (VerifySCEV)
  278. LAR.SE.verify();
  279. if (LAR.MSSA && VerifyMemorySSA)
  280. LAR.MSSA->verifyMemorySSA();
  281. #endif
  282. // If the loop hasn't been deleted, we need to handle invalidation here.
  283. if (!Updater.skipCurrentLoop())
  284. // We know that the loop pass couldn't have invalidated any other
  285. // loop's analyses (that's the contract of a loop pass), so directly
  286. // handle the loop analysis manager's invalidation here.
  287. LAM.invalidate(*L, PassPA);
  288. // Then intersect the preserved set so that invalidation of module
  289. // analyses will eventually occur when the module pass completes.
  290. PA.intersect(std::move(PassPA));
  291. } while (!Worklist.empty());
  292. #ifndef NDEBUG
  293. PI.popBeforeNonSkippedPassCallback();
  294. #endif
  295. // By definition we preserve the proxy. We also preserve all analyses on
  296. // Loops. This precludes *any* invalidation of loop analyses by the proxy,
  297. // but that's OK because we've taken care to invalidate analyses in the
  298. // loop analysis manager incrementally above.
  299. PA.preserveSet<AllAnalysesOn<Loop>>();
  300. PA.preserve<LoopAnalysisManagerFunctionProxy>();
  301. // We also preserve the set of standard analyses.
  302. PA.preserve<DominatorTreeAnalysis>();
  303. PA.preserve<LoopAnalysis>();
  304. PA.preserve<ScalarEvolutionAnalysis>();
  305. if (UseBlockFrequencyInfo && F.hasProfileData())
  306. PA.preserve<BlockFrequencyAnalysis>();
  307. if (UseBranchProbabilityInfo && F.hasProfileData())
  308. PA.preserve<BranchProbabilityAnalysis>();
  309. if (UseMemorySSA)
  310. PA.preserve<MemorySSAAnalysis>();
  311. return PA;
  312. }
  313. PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}
  314. PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
  315. : OS(OS), Banner(Banner) {}
  316. PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &,
  317. LoopStandardAnalysisResults &,
  318. LPMUpdater &) {
  319. printLoop(L, OS, Banner);
  320. return PreservedAnalyses::all();
  321. }