1 //===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===// 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 /// \file 9 /// 10 /// This header provides classes for managing a pipeline of passes over loops 11 /// in LLVM IR. 12 /// 13 /// The primary loop pass pipeline is managed in a very particular way to 14 /// provide a set of core guarantees: 15 /// 1) Loops are, where possible, in simplified form. 16 /// 2) Loops are *always* in LCSSA form. 17 /// 3) A collection of Loop-specific analysis results are available: 18 /// - LoopInfo 19 /// - DominatorTree 20 /// - ScalarEvolution 21 /// - AAManager 22 /// 4) All loop passes preserve #1 (where possible), #2, and #3. 23 /// 5) Loop passes run over each loop in the loop nest from the innermost to 24 /// the outermost. Specifically, all inner loops are processed before 25 /// passes run over outer loops. When running the pipeline across an inner 26 /// loop creates new inner loops, those are added and processed in this 27 /// order as well. 28 /// 29 /// This process is designed to facilitate transformations which simplify, 30 /// reduce, and remove loops. For passes which are more oriented towards 31 /// optimizing loops, especially optimizing loop *nests* instead of single 32 /// loops in isolation, this framework is less interesting. 33 /// 34 //===----------------------------------------------------------------------===// 35 36 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H 37 #define LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H 38 39 #include "llvm/ADT/PriorityWorklist.h" 40 #include "llvm/Analysis/LoopAnalysisManager.h" 41 #include "llvm/Analysis/LoopInfo.h" 42 #include "llvm/Analysis/LoopNestAnalysis.h" 43 #include "llvm/IR/PassInstrumentation.h" 44 #include "llvm/IR/PassManager.h" 45 #include "llvm/Support/Compiler.h" 46 #include "llvm/Transforms/Utils/LCSSA.h" 47 #include "llvm/Transforms/Utils/LoopSimplify.h" 48 #include "llvm/Transforms/Utils/LoopUtils.h" 49 #include <memory> 50 51 namespace llvm { 52 53 // Forward declarations of an update tracking API used in the pass manager. 54 class LPMUpdater; 55 class PassInstrumentation; 56 57 namespace { 58 59 template <typename PassT> 60 using HasRunOnLoopT = decltype(std::declval<PassT>().run( 61 std::declval<Loop &>(), std::declval<LoopAnalysisManager &>(), 62 std::declval<LoopStandardAnalysisResults &>(), 63 std::declval<LPMUpdater &>())); 64 65 } // namespace 66 67 // Explicit specialization and instantiation declarations for the pass manager. 68 // See the comments on the definition of the specialization for details on how 69 // it differs from the primary template. 70 template <> 71 class PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, 72 LPMUpdater &> 73 : public PassInfoMixin< 74 PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, 75 LPMUpdater &>> { 76 public: 77 explicit PassManager() = default; 78 79 // FIXME: These are equivalent to the default move constructor/move 80 // assignment. However, using = default triggers linker errors due to the 81 // explicit instantiations below. Find a way to use the default and remove the 82 // duplicated code here. PassManager(PassManager && Arg)83 PassManager(PassManager &&Arg) 84 : IsLoopNestPass(std::move(Arg.IsLoopNestPass)), 85 LoopPasses(std::move(Arg.LoopPasses)), 86 LoopNestPasses(std::move(Arg.LoopNestPasses)) {} 87 88 PassManager &operator=(PassManager &&RHS) { 89 IsLoopNestPass = std::move(RHS.IsLoopNestPass); 90 LoopPasses = std::move(RHS.LoopPasses); 91 LoopNestPasses = std::move(RHS.LoopNestPasses); 92 return *this; 93 } 94 95 LLVM_ABI PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 96 LoopStandardAnalysisResults &AR, 97 LPMUpdater &U); 98 99 LLVM_ABI void 100 printPipeline(raw_ostream &OS, 101 function_ref<StringRef(StringRef)> MapClassName2PassName); 102 /// Add either a loop pass or a loop-nest pass to the pass manager. Append \p 103 /// Pass to the list of loop passes if it has a dedicated \fn run() method for 104 /// loops and to the list of loop-nest passes if the \fn run() method is for 105 /// loop-nests instead. Also append whether \p Pass is loop-nest pass or not 106 /// to the end of \var IsLoopNestPass so we can easily identify the types of 107 /// passes in the pass manager later. addPass(PassT && Pass)108 template <typename PassT> LLVM_ATTRIBUTE_MINSIZE void addPass(PassT &&Pass) { 109 if constexpr (is_detected<HasRunOnLoopT, PassT>::value) { 110 using LoopPassModelT = 111 detail::PassModel<Loop, PassT, LoopAnalysisManager, 112 LoopStandardAnalysisResults &, LPMUpdater &>; 113 IsLoopNestPass.push_back(false); 114 // Do not use make_unique or emplace_back, they cause too many template 115 // instantiations, causing terrible compile times. 116 LoopPasses.push_back(std::unique_ptr<LoopPassConceptT>( 117 new LoopPassModelT(std::forward<PassT>(Pass)))); 118 } else { 119 using LoopNestPassModelT = 120 detail::PassModel<LoopNest, PassT, LoopAnalysisManager, 121 LoopStandardAnalysisResults &, LPMUpdater &>; 122 IsLoopNestPass.push_back(true); 123 // Do not use make_unique or emplace_back, they cause too many template 124 // instantiations, causing terrible compile times. 125 LoopNestPasses.push_back(std::unique_ptr<LoopNestPassConceptT>( 126 new LoopNestPassModelT(std::forward<PassT>(Pass)))); 127 } 128 } 129 isEmpty()130 bool isEmpty() const { return LoopPasses.empty() && LoopNestPasses.empty(); } 131 isRequired()132 static bool isRequired() { return true; } 133 getNumLoopPasses()134 size_t getNumLoopPasses() const { return LoopPasses.size(); } getNumLoopNestPasses()135 size_t getNumLoopNestPasses() const { return LoopNestPasses.size(); } 136 137 protected: 138 using LoopPassConceptT = 139 detail::PassConcept<Loop, LoopAnalysisManager, 140 LoopStandardAnalysisResults &, LPMUpdater &>; 141 using LoopNestPassConceptT = 142 detail::PassConcept<LoopNest, LoopAnalysisManager, 143 LoopStandardAnalysisResults &, LPMUpdater &>; 144 145 // BitVector that identifies whether the passes are loop passes or loop-nest 146 // passes (true for loop-nest passes). 147 BitVector IsLoopNestPass; 148 std::vector<std::unique_ptr<LoopPassConceptT>> LoopPasses; 149 std::vector<std::unique_ptr<LoopNestPassConceptT>> LoopNestPasses; 150 151 /// Run either a loop pass or a loop-nest pass. Returns `std::nullopt` if 152 /// PassInstrumentation's BeforePass returns false. Otherwise, returns the 153 /// preserved analyses of the pass. 154 template <typename IRUnitT, typename PassT> 155 std::optional<PreservedAnalyses> 156 runSinglePass(IRUnitT &IR, PassT &Pass, LoopAnalysisManager &AM, 157 LoopStandardAnalysisResults &AR, LPMUpdater &U, 158 PassInstrumentation &PI); 159 160 LLVM_ABI PreservedAnalyses 161 runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM, 162 LoopStandardAnalysisResults &AR, LPMUpdater &U); 163 LLVM_ABI PreservedAnalyses 164 runWithoutLoopNestPasses(Loop &L, LoopAnalysisManager &AM, 165 LoopStandardAnalysisResults &AR, LPMUpdater &U); 166 167 private: getLoopFromIR(Loop & L)168 static const Loop &getLoopFromIR(Loop &L) { return L; } getLoopFromIR(LoopNest & LN)169 static const Loop &getLoopFromIR(LoopNest &LN) { 170 return LN.getOutermostLoop(); 171 } 172 }; 173 174 /// The Loop pass manager. 175 /// 176 /// See the documentation for the PassManager template for details. It runs 177 /// a sequence of Loop passes over each Loop that the manager is run over. This 178 /// typedef serves as a convenient way to refer to this construct. 179 typedef PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, 180 LPMUpdater &> 181 LoopPassManager; 182 183 /// A partial specialization of the require analysis template pass to forward 184 /// the extra parameters from a transformation's run method to the 185 /// AnalysisManager's getResult. 186 template <typename AnalysisT> 187 struct RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager, 188 LoopStandardAnalysisResults &, LPMUpdater &> 189 : PassInfoMixin< 190 RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager, 191 LoopStandardAnalysisResults &, LPMUpdater &>> { 192 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 193 LoopStandardAnalysisResults &AR, LPMUpdater &) { 194 (void)AM.template getResult<AnalysisT>(L, AR); 195 return PreservedAnalyses::all(); 196 } 197 void printPipeline(raw_ostream &OS, 198 function_ref<StringRef(StringRef)> MapClassName2PassName) { 199 auto ClassName = AnalysisT::name(); 200 auto PassName = MapClassName2PassName(ClassName); 201 OS << "require<" << PassName << '>'; 202 } 203 }; 204 205 /// An alias template to easily name a require analysis loop pass. 206 template <typename AnalysisT> 207 using RequireAnalysisLoopPass = 208 RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager, 209 LoopStandardAnalysisResults &, LPMUpdater &>; 210 211 class FunctionToLoopPassAdaptor; 212 213 /// This class provides an interface for updating the loop pass manager based 214 /// on mutations to the loop nest. 215 /// 216 /// A reference to an instance of this class is passed as an argument to each 217 /// Loop pass, and Loop passes should use it to update LPM infrastructure if 218 /// they modify the loop nest structure. 219 /// 220 /// \c LPMUpdater comes with two modes: the loop mode and the loop-nest mode. In 221 /// loop mode, all the loops in the function will be pushed into the worklist 222 /// and when new loops are added to the pipeline, their subloops are also 223 /// inserted recursively. On the other hand, in loop-nest mode, only top-level 224 /// loops are contained in the worklist and the addition of new (top-level) 225 /// loops will not trigger the addition of their subloops. 226 class LPMUpdater { 227 public: 228 /// This can be queried by loop passes which run other loop passes (like pass 229 /// managers) to know whether the loop needs to be skipped due to updates to 230 /// the loop nest. 231 /// 232 /// If this returns true, the loop object may have been deleted, so passes 233 /// should take care not to touch the object. 234 bool skipCurrentLoop() const { return SkipCurrentLoop; } 235 236 /// Loop passes should use this method to indicate they have deleted a loop 237 /// from the nest. 238 /// 239 /// Note that this loop must either be the current loop or a subloop of the 240 /// current loop. This routine must be called prior to removing the loop from 241 /// the loop nest. 242 /// 243 /// If this is called for the current loop, in addition to clearing any 244 /// state, this routine will mark that the current loop should be skipped by 245 /// the rest of the pass management infrastructure. 246 void markLoopAsDeleted(Loop &L, llvm::StringRef Name) { 247 LAM.clear(L, Name); 248 assert((&L == CurrentL || CurrentL->contains(&L)) && 249 "Cannot delete a loop outside of the " 250 "subloop tree currently being processed."); 251 if (&L == CurrentL) 252 SkipCurrentLoop = true; 253 } 254 255 void setParentLoop(Loop *L) { 256 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 257 ParentL = L; 258 #endif 259 } 260 261 /// Loop passes should use this method to indicate they have added new child 262 /// loops of the current loop. 263 /// 264 /// \p NewChildLoops must contain only the immediate children. Any nested 265 /// loops within them will be visited in postorder as usual for the loop pass 266 /// manager. 267 void addChildLoops(ArrayRef<Loop *> NewChildLoops) { 268 assert(!LoopNestMode && 269 "Child loops should not be pushed in loop-nest mode."); 270 // Insert ourselves back into the worklist first, as this loop should be 271 // revisited after all the children have been processed. 272 Worklist.insert(CurrentL); 273 274 #ifndef NDEBUG 275 for (Loop *NewL : NewChildLoops) 276 assert(NewL->getParentLoop() == CurrentL && "All of the new loops must " 277 "be immediate children of " 278 "the current loop!"); 279 #endif 280 281 appendLoopsToWorklist(NewChildLoops, Worklist); 282 283 // Also skip further processing of the current loop--it will be revisited 284 // after all of its newly added children are accounted for. 285 SkipCurrentLoop = true; 286 } 287 288 /// Loop passes should use this method to indicate they have added new 289 /// sibling loops to the current loop. 290 /// 291 /// \p NewSibLoops must only contain the immediate sibling loops. Any nested 292 /// loops within them will be visited in postorder as usual for the loop pass 293 /// manager. 294 void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) { 295 #if LLVM_ENABLE_ABI_BREAKING_CHECKS && !defined(NDEBUG) 296 for (Loop *NewL : NewSibLoops) 297 assert(NewL->getParentLoop() == ParentL && 298 "All of the new loops must be siblings of the current loop!"); 299 #endif 300 301 if (LoopNestMode) 302 Worklist.insert(NewSibLoops); 303 else 304 appendLoopsToWorklist(NewSibLoops, Worklist); 305 306 // No need to skip the current loop or revisit it, as sibling loops 307 // shouldn't impact anything. 308 } 309 310 /// Restart the current loop. 311 /// 312 /// Loop passes should call this method to indicate the current loop has been 313 /// sufficiently changed that it should be re-visited from the begining of 314 /// the loop pass pipeline rather than continuing. 315 void revisitCurrentLoop() { 316 // Tell the currently in-flight pipeline to stop running. 317 SkipCurrentLoop = true; 318 319 // And insert ourselves back into the worklist. 320 Worklist.insert(CurrentL); 321 } 322 323 bool isLoopNestChanged() const { 324 return LoopNestChanged; 325 } 326 327 /// Loopnest passes should use this method to indicate if the 328 /// loopnest has been modified. 329 void markLoopNestChanged(bool Changed) { 330 LoopNestChanged = Changed; 331 } 332 333 private: 334 friend class llvm::FunctionToLoopPassAdaptor; 335 336 /// The \c FunctionToLoopPassAdaptor's worklist of loops to process. 337 SmallPriorityWorklist<Loop *, 4> &Worklist; 338 339 /// The analysis manager for use in the current loop nest. 340 LoopAnalysisManager &LAM; 341 342 Loop *CurrentL; 343 bool SkipCurrentLoop; 344 const bool LoopNestMode; 345 bool LoopNestChanged; 346 347 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 348 // In debug builds we also track the parent loop to implement asserts even in 349 // the face of loop deletion. 350 Loop *ParentL; 351 #endif 352 353 LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist, 354 LoopAnalysisManager &LAM, bool LoopNestMode = false, 355 bool LoopNestChanged = false) 356 : Worklist(Worklist), LAM(LAM), LoopNestMode(LoopNestMode), 357 LoopNestChanged(LoopNestChanged) {} 358 }; 359 360 template <typename IRUnitT, typename PassT> 361 std::optional<PreservedAnalyses> LoopPassManager::runSinglePass( 362 IRUnitT &IR, PassT &Pass, LoopAnalysisManager &AM, 363 LoopStandardAnalysisResults &AR, LPMUpdater &U, PassInstrumentation &PI) { 364 // Get the loop in case of Loop pass and outermost loop in case of LoopNest 365 // pass which is to be passed to BeforePass and AfterPass call backs. 366 const Loop &L = getLoopFromIR(IR); 367 // Check the PassInstrumentation's BeforePass callbacks before running the 368 // pass, skip its execution completely if asked to (callback returns false). 369 if (!PI.runBeforePass<Loop>(*Pass, L)) 370 return std::nullopt; 371 372 PreservedAnalyses PA = Pass->run(IR, AM, AR, U); 373 374 // do not pass deleted Loop into the instrumentation 375 if (U.skipCurrentLoop()) 376 PI.runAfterPassInvalidated<IRUnitT>(*Pass, PA); 377 else 378 PI.runAfterPass<Loop>(*Pass, L, PA); 379 return PA; 380 } 381 382 /// Adaptor that maps from a function to its loops. 383 /// 384 /// Designed to allow composition of a LoopPass(Manager) and a 385 /// FunctionPassManager. Note that if this pass is constructed with a \c 386 /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy 387 /// analysis prior to running the loop passes over the function to enable a \c 388 /// LoopAnalysisManager to be used within this run safely. 389 /// 390 /// The adaptor comes with two modes: the loop mode and the loop-nest mode, and 391 /// the worklist updater lived inside will be in the same mode as the adaptor 392 /// (refer to the documentation of \c LPMUpdater for more detailed explanation). 393 /// Specifically, in loop mode, all loops in the function will be pushed into 394 /// the worklist and processed by \p Pass, while only top-level loops are 395 /// processed in loop-nest mode. Please refer to the various specializations of 396 /// \fn createLoopFunctionToLoopPassAdaptor to see when loop mode and loop-nest 397 /// mode are used. 398 class FunctionToLoopPassAdaptor 399 : public PassInfoMixin<FunctionToLoopPassAdaptor> { 400 public: 401 using PassConceptT = 402 detail::PassConcept<Loop, LoopAnalysisManager, 403 LoopStandardAnalysisResults &, LPMUpdater &>; 404 405 explicit FunctionToLoopPassAdaptor(std::unique_ptr<PassConceptT> Pass, 406 bool UseMemorySSA = false, 407 bool UseBlockFrequencyInfo = false, 408 bool UseBranchProbabilityInfo = false, 409 bool LoopNestMode = false) 410 : Pass(std::move(Pass)), UseMemorySSA(UseMemorySSA), 411 UseBlockFrequencyInfo(UseBlockFrequencyInfo), 412 UseBranchProbabilityInfo(UseBranchProbabilityInfo), 413 LoopNestMode(LoopNestMode) { 414 LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); 415 LoopCanonicalizationFPM.addPass(LCSSAPass()); 416 } 417 418 /// Runs the loop passes across every loop in the function. 419 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 420 LLVM_ABI void 421 printPipeline(raw_ostream &OS, 422 function_ref<StringRef(StringRef)> MapClassName2PassName); 423 424 static bool isRequired() { return true; } 425 426 bool isLoopNestMode() const { return LoopNestMode; } 427 428 private: 429 std::unique_ptr<PassConceptT> Pass; 430 431 FunctionPassManager LoopCanonicalizationFPM; 432 433 bool UseMemorySSA = false; 434 bool UseBlockFrequencyInfo = false; 435 bool UseBranchProbabilityInfo = false; 436 const bool LoopNestMode; 437 }; 438 439 /// A function to deduce a loop pass type and wrap it in the templated 440 /// adaptor. 441 /// 442 /// If \p Pass is a loop pass, the returned adaptor will be in loop mode. 443 /// 444 /// If \p Pass is a loop-nest pass, \p Pass will first be wrapped into a 445 /// \c LoopPassManager and the returned adaptor will be in loop-nest mode. 446 template <typename LoopPassT> 447 inline FunctionToLoopPassAdaptor 448 createFunctionToLoopPassAdaptor(LoopPassT &&Pass, bool UseMemorySSA = false, 449 bool UseBlockFrequencyInfo = false, 450 bool UseBranchProbabilityInfo = false) { 451 if constexpr (is_detected<HasRunOnLoopT, LoopPassT>::value) { 452 using PassModelT = 453 detail::PassModel<Loop, LoopPassT, LoopAnalysisManager, 454 LoopStandardAnalysisResults &, LPMUpdater &>; 455 // Do not use make_unique, it causes too many template instantiations, 456 // causing terrible compile times. 457 return FunctionToLoopPassAdaptor( 458 std::unique_ptr<FunctionToLoopPassAdaptor::PassConceptT>( 459 new PassModelT(std::forward<LoopPassT>(Pass))), 460 UseMemorySSA, UseBlockFrequencyInfo, UseBranchProbabilityInfo, false); 461 } else { 462 LoopPassManager LPM; 463 LPM.addPass(std::forward<LoopPassT>(Pass)); 464 using PassModelT = 465 detail::PassModel<Loop, LoopPassManager, LoopAnalysisManager, 466 LoopStandardAnalysisResults &, LPMUpdater &>; 467 // Do not use make_unique, it causes too many template instantiations, 468 // causing terrible compile times. 469 return FunctionToLoopPassAdaptor( 470 std::unique_ptr<FunctionToLoopPassAdaptor::PassConceptT>( 471 new PassModelT(std::move(LPM))), 472 UseMemorySSA, UseBlockFrequencyInfo, UseBranchProbabilityInfo, true); 473 } 474 } 475 476 /// If \p Pass is an instance of \c LoopPassManager, the returned adaptor will 477 /// be in loop-nest mode if the pass manager contains only loop-nest passes. 478 template <> 479 inline FunctionToLoopPassAdaptor 480 createFunctionToLoopPassAdaptor<LoopPassManager>( 481 LoopPassManager &&LPM, bool UseMemorySSA, bool UseBlockFrequencyInfo, 482 bool UseBranchProbabilityInfo) { 483 // Check if LPM contains any loop pass and if it does not, returns an adaptor 484 // in loop-nest mode. 485 using PassModelT = 486 detail::PassModel<Loop, LoopPassManager, LoopAnalysisManager, 487 LoopStandardAnalysisResults &, LPMUpdater &>; 488 bool LoopNestMode = (LPM.getNumLoopPasses() == 0); 489 // Do not use make_unique, it causes too many template instantiations, 490 // causing terrible compile times. 491 return FunctionToLoopPassAdaptor( 492 std::unique_ptr<FunctionToLoopPassAdaptor::PassConceptT>( 493 new PassModelT(std::move(LPM))), 494 UseMemorySSA, UseBlockFrequencyInfo, UseBranchProbabilityInfo, 495 LoopNestMode); 496 } 497 498 /// Pass for printing a loop's contents as textual IR. 499 class PrintLoopPass : public PassInfoMixin<PrintLoopPass> { 500 raw_ostream &OS; 501 std::string Banner; 502 503 public: 504 LLVM_ABI PrintLoopPass(); 505 LLVM_ABI PrintLoopPass(raw_ostream &OS, const std::string &Banner = ""); 506 507 LLVM_ABI PreservedAnalyses run(Loop &L, LoopAnalysisManager &, 508 LoopStandardAnalysisResults &, LPMUpdater &); 509 }; 510 } 511 512 #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H 513