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