1 //===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 /// \file 10 /// 11 /// This header provides classes for managing a pipeline of passes over loops 12 /// in LLVM IR. 13 /// 14 /// The primary loop pass pipeline is managed in a very particular way to 15 /// provide a set of core guarantees: 16 /// 1) Loops are, where possible, in simplified form. 17 /// 2) Loops are *always* in LCSSA form. 18 /// 3) A collection of Loop-specific analysis results are available: 19 /// - LoopInfo 20 /// - DominatorTree 21 /// - ScalarEvolution 22 /// - AAManager 23 /// 4) All loop passes preserve #1 (where possible), #2, and #3. 24 /// 5) Loop passes run over each loop in the loop nest from the innermost to 25 /// the outermost. Specifically, all inner loops are processed before 26 /// passes run over outer loops. When running the pipeline across an inner 27 /// loop creates new inner loops, those are added and processed in this 28 /// order as well. 29 /// 30 /// This process is designed to facilitate transformations which simplify, 31 /// reduce, and remove loops. For passes which are more oriented towards 32 /// optimizing loops, especially optimizing loop *nests* instead of single 33 /// loops in isolation, this framework is less interesting. 34 /// 35 //===----------------------------------------------------------------------===// 36 37 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H 38 #define LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H 39 40 #include "llvm/ADT/PostOrderIterator.h" 41 #include "llvm/ADT/PriorityWorklist.h" 42 #include "llvm/ADT/STLExtras.h" 43 #include "llvm/Analysis/AliasAnalysis.h" 44 #include "llvm/Analysis/BasicAliasAnalysis.h" 45 #include "llvm/Analysis/GlobalsModRef.h" 46 #include "llvm/Analysis/LoopAnalysisManager.h" 47 #include "llvm/Analysis/LoopInfo.h" 48 #include "llvm/Analysis/ScalarEvolution.h" 49 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 50 #include "llvm/Analysis/TargetLibraryInfo.h" 51 #include "llvm/Analysis/TargetTransformInfo.h" 52 #include "llvm/IR/Dominators.h" 53 #include "llvm/IR/PassManager.h" 54 #include "llvm/Transforms/Utils/LCSSA.h" 55 #include "llvm/Transforms/Utils/LoopSimplify.h" 56 57 namespace llvm { 58 59 // Forward declarations of an update tracking API used in the pass manager. 60 class LPMUpdater; 61 62 // Explicit specialization and instantiation declarations for the pass manager. 63 // See the comments on the definition of the specialization for details on how 64 // it differs from the primary template. 65 template <> 66 PreservedAnalyses 67 PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, 68 LPMUpdater &>::run(Loop &InitialL, LoopAnalysisManager &AM, 69 LoopStandardAnalysisResults &AnalysisResults, 70 LPMUpdater &U); 71 extern template class PassManager<Loop, LoopAnalysisManager, 72 LoopStandardAnalysisResults &, LPMUpdater &>; 73 74 /// \brief The Loop pass manager. 75 /// 76 /// See the documentation for the PassManager template for details. It runs 77 /// a sequence of Loop passes over each Loop that the manager is run over. This 78 /// typedef serves as a convenient way to refer to this construct. 79 typedef PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, 80 LPMUpdater &> 81 LoopPassManager; 82 83 /// A partial specialization of the require analysis template pass to forward 84 /// the extra parameters from a transformation's run method to the 85 /// AnalysisManager's getResult. 86 template <typename AnalysisT> 87 struct RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager, 88 LoopStandardAnalysisResults &, LPMUpdater &> 89 : PassInfoMixin< 90 RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager, 91 LoopStandardAnalysisResults &, LPMUpdater &>> { 92 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 93 LoopStandardAnalysisResults &AR, LPMUpdater &) { 94 (void)AM.template getResult<AnalysisT>(L, AR); 95 return PreservedAnalyses::all(); 96 } 97 }; 98 99 /// An alias template to easily name a require analysis loop pass. 100 template <typename AnalysisT> 101 using RequireAnalysisLoopPass = 102 RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager, 103 LoopStandardAnalysisResults &, LPMUpdater &>; 104 105 namespace internal { 106 /// Helper to implement appending of loops onto a worklist. 107 /// 108 /// We want to process loops in postorder, but the worklist is a LIFO data 109 /// structure, so we append to it in *reverse* postorder. 110 /// 111 /// For trees, a preorder traversal is a viable reverse postorder, so we 112 /// actually append using a preorder walk algorithm. 113 template <typename RangeT> 114 inline void appendLoopsToWorklist(RangeT &&Loops, 115 SmallPriorityWorklist<Loop *, 4> &Worklist) { 116 // We use an internal worklist to build up the preorder traversal without 117 // recursion. 118 SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist; 119 120 // We walk the initial sequence of loops in reverse because we generally want 121 // to visit defs before uses and the worklist is LIFO. 122 for (Loop *RootL : reverse(Loops)) { 123 assert(PreOrderLoops.empty() && "Must start with an empty preorder walk."); 124 assert(PreOrderWorklist.empty() && 125 "Must start with an empty preorder walk worklist."); 126 PreOrderWorklist.push_back(RootL); 127 do { 128 Loop *L = PreOrderWorklist.pop_back_val(); 129 PreOrderWorklist.append(L->begin(), L->end()); 130 PreOrderLoops.push_back(L); 131 } while (!PreOrderWorklist.empty()); 132 133 Worklist.insert(std::move(PreOrderLoops)); 134 PreOrderLoops.clear(); 135 } 136 } 137 } 138 139 template <typename LoopPassT> class FunctionToLoopPassAdaptor; 140 141 /// This class provides an interface for updating the loop pass manager based 142 /// on mutations to the loop nest. 143 /// 144 /// A reference to an instance of this class is passed as an argument to each 145 /// Loop pass, and Loop passes should use it to update LPM infrastructure if 146 /// they modify the loop nest structure. 147 class LPMUpdater { 148 public: 149 /// This can be queried by loop passes which run other loop passes (like pass 150 /// managers) to know whether the loop needs to be skipped due to updates to 151 /// the loop nest. 152 /// 153 /// If this returns true, the loop object may have been deleted, so passes 154 /// should take care not to touch the object. 155 bool skipCurrentLoop() const { return SkipCurrentLoop; } 156 157 /// Loop passes should use this method to indicate they have deleted a loop 158 /// from the nest. 159 /// 160 /// Note that this loop must either be the current loop or a subloop of the 161 /// current loop. This routine must be called prior to removing the loop from 162 /// the loop nest. 163 /// 164 /// If this is called for the current loop, in addition to clearing any 165 /// state, this routine will mark that the current loop should be skipped by 166 /// the rest of the pass management infrastructure. 167 void markLoopAsDeleted(Loop &L) { 168 LAM.clear(L); 169 assert(CurrentL->contains(&L) && "Cannot delete a loop outside of the " 170 "subloop tree currently being processed."); 171 if (&L == CurrentL) 172 SkipCurrentLoop = true; 173 } 174 175 /// Loop passes should use this method to indicate they have added new child 176 /// loops of the current loop. 177 /// 178 /// \p NewChildLoops must contain only the immediate children. Any nested 179 /// loops within them will be visited in postorder as usual for the loop pass 180 /// manager. 181 void addChildLoops(ArrayRef<Loop *> NewChildLoops) { 182 // Insert ourselves back into the worklist first, as this loop should be 183 // revisited after all the children have been processed. 184 Worklist.insert(CurrentL); 185 186 #ifndef NDEBUG 187 for (Loop *NewL : NewChildLoops) 188 assert(NewL->getParentLoop() == CurrentL && "All of the new loops must " 189 "be immediate children of " 190 "the current loop!"); 191 #endif 192 193 internal::appendLoopsToWorklist(NewChildLoops, Worklist); 194 195 // Also skip further processing of the current loop--it will be revisited 196 // after all of its newly added children are accounted for. 197 SkipCurrentLoop = true; 198 } 199 200 /// Loop passes should use this method to indicate they have added new 201 /// sibling loops to the current loop. 202 /// 203 /// \p NewSibLoops must only contain the immediate sibling loops. Any nested 204 /// loops within them will be visited in postorder as usual for the loop pass 205 /// manager. 206 void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) { 207 #ifndef NDEBUG 208 for (Loop *NewL : NewSibLoops) 209 assert(NewL->getParentLoop() == ParentL && 210 "All of the new loops must be siblings of the current loop!"); 211 #endif 212 213 internal::appendLoopsToWorklist(NewSibLoops, Worklist); 214 215 // No need to skip the current loop or revisit it, as sibling loops 216 // shouldn't impact anything. 217 } 218 219 private: 220 template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor; 221 222 /// The \c FunctionToLoopPassAdaptor's worklist of loops to process. 223 SmallPriorityWorklist<Loop *, 4> &Worklist; 224 225 /// The analysis manager for use in the current loop nest. 226 LoopAnalysisManager &LAM; 227 228 Loop *CurrentL; 229 bool SkipCurrentLoop; 230 231 #ifndef NDEBUG 232 // In debug builds we also track the parent loop to implement asserts even in 233 // the face of loop deletion. 234 Loop *ParentL; 235 #endif 236 237 LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist, 238 LoopAnalysisManager &LAM) 239 : Worklist(Worklist), LAM(LAM) {} 240 }; 241 242 /// \brief Adaptor that maps from a function to its loops. 243 /// 244 /// Designed to allow composition of a LoopPass(Manager) and a 245 /// FunctionPassManager. Note that if this pass is constructed with a \c 246 /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy 247 /// analysis prior to running the loop passes over the function to enable a \c 248 /// LoopAnalysisManager to be used within this run safely. 249 template <typename LoopPassT> 250 class FunctionToLoopPassAdaptor 251 : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> { 252 public: 253 explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) { 254 LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); 255 LoopCanonicalizationFPM.addPass(LCSSAPass()); 256 } 257 258 /// \brief Runs the loop passes across every loop in the function. 259 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { 260 // Before we even compute any loop analyses, first run a miniature function 261 // pass pipeline to put loops into their canonical form. Note that we can 262 // directly build up function analyses after this as the function pass 263 // manager handles all the invalidation at that layer. 264 PreservedAnalyses PA = LoopCanonicalizationFPM.run(F, AM); 265 266 // Get the loop structure for this function 267 LoopInfo &LI = AM.getResult<LoopAnalysis>(F); 268 269 // If there are no loops, there is nothing to do here. 270 if (LI.empty()) 271 return PA; 272 273 // Get the analysis results needed by loop passes. 274 LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F), 275 AM.getResult<AssumptionAnalysis>(F), 276 AM.getResult<DominatorTreeAnalysis>(F), 277 AM.getResult<LoopAnalysis>(F), 278 AM.getResult<ScalarEvolutionAnalysis>(F), 279 AM.getResult<TargetLibraryAnalysis>(F), 280 AM.getResult<TargetIRAnalysis>(F)}; 281 282 // Setup the loop analysis manager from its proxy. It is important that 283 // this is only done when there are loops to process and we have built the 284 // LoopStandardAnalysisResults object. The loop analyses cached in this 285 // manager have access to those analysis results and so it must invalidate 286 // itself when they go away. 287 LoopAnalysisManager &LAM = 288 AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager(); 289 290 // A postorder worklist of loops to process. 291 SmallPriorityWorklist<Loop *, 4> Worklist; 292 293 // Register the worklist and loop analysis manager so that loop passes can 294 // update them when they mutate the loop nest structure. 295 LPMUpdater Updater(Worklist, LAM); 296 297 // Add the loop nests in the reverse order of LoopInfo. For some reason, 298 // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For 299 // the purpose of unrolling, loop deletion, and LICM, we largely want to 300 // work forward across the CFG so that we visit defs before uses and can 301 // propagate simplifications from one loop nest into the next. 302 // FIXME: Consider changing the order in LoopInfo. 303 internal::appendLoopsToWorklist(reverse(LI), Worklist); 304 305 do { 306 Loop *L = Worklist.pop_back_val(); 307 308 // Reset the update structure for this loop. 309 Updater.CurrentL = L; 310 Updater.SkipCurrentLoop = false; 311 312 #ifndef NDEBUG 313 // Save a parent loop pointer for asserts. 314 Updater.ParentL = L->getParentLoop(); 315 316 // Verify the loop structure and LCSSA form before visiting the loop. 317 L->verifyLoop(); 318 assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) && 319 "Loops must remain in LCSSA form!"); 320 #endif 321 322 PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater); 323 // FIXME: We should verify the set of analyses relevant to Loop passes 324 // are preserved. 325 326 // If the loop hasn't been deleted, we need to handle invalidation here. 327 if (!Updater.skipCurrentLoop()) 328 // We know that the loop pass couldn't have invalidated any other 329 // loop's analyses (that's the contract of a loop pass), so directly 330 // handle the loop analysis manager's invalidation here. 331 LAM.invalidate(*L, PassPA); 332 333 // Then intersect the preserved set so that invalidation of module 334 // analyses will eventually occur when the module pass completes. 335 PA.intersect(std::move(PassPA)); 336 } while (!Worklist.empty()); 337 338 // By definition we preserve the proxy. We also preserve all analyses on 339 // Loops. This precludes *any* invalidation of loop analyses by the proxy, 340 // but that's OK because we've taken care to invalidate analyses in the 341 // loop analysis manager incrementally above. 342 PA.preserveSet<AllAnalysesOn<Loop>>(); 343 PA.preserve<LoopAnalysisManagerFunctionProxy>(); 344 // We also preserve the set of standard analyses. 345 PA.preserve<DominatorTreeAnalysis>(); 346 PA.preserve<LoopAnalysis>(); 347 PA.preserve<ScalarEvolutionAnalysis>(); 348 // FIXME: What we really want to do here is preserve an AA category, but 349 // that concept doesn't exist yet. 350 PA.preserve<AAManager>(); 351 PA.preserve<BasicAA>(); 352 PA.preserve<GlobalsAA>(); 353 PA.preserve<SCEVAA>(); 354 return PA; 355 } 356 357 private: 358 LoopPassT Pass; 359 360 FunctionPassManager LoopCanonicalizationFPM; 361 }; 362 363 /// \brief A function to deduce a loop pass type and wrap it in the templated 364 /// adaptor. 365 template <typename LoopPassT> 366 FunctionToLoopPassAdaptor<LoopPassT> 367 createFunctionToLoopPassAdaptor(LoopPassT Pass) { 368 return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass)); 369 } 370 371 /// \brief Pass for printing a loop's contents as textual IR. 372 class PrintLoopPass : public PassInfoMixin<PrintLoopPass> { 373 raw_ostream &OS; 374 std::string Banner; 375 376 public: 377 PrintLoopPass(); 378 PrintLoopPass(raw_ostream &OS, const std::string &Banner = ""); 379 380 PreservedAnalyses run(Loop &L, LoopAnalysisManager &, 381 LoopStandardAnalysisResults &, LPMUpdater &); 382 }; 383 } 384 385 #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H 386