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