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