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 57namespace llvm { 58 59// Forward declarations of an update tracking API used in the pass manager. 60class 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. 65template <> 66PreservedAnalyses 67PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, 68 LPMUpdater &>::run(Loop &InitialL, LoopAnalysisManager &AM, 69 LoopStandardAnalysisResults &AnalysisResults, 70 LPMUpdater &U); 71extern 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. 79typedef 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. 86template <typename AnalysisT> 87struct 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. 100template <typename AnalysisT> 101using RequireAnalysisLoopPass = 102 RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager, 103 LoopStandardAnalysisResults &, LPMUpdater &>; 104 105namespace 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. 113template <typename RangeT> 114inline 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 139template <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. 147class LPMUpdater { 148public: 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, llvm::StringRef Name) { 168 LAM.clear(L, Name); 169 assert((&L == CurrentL || CurrentL->contains(&L)) && 170 "Cannot delete a loop outside of the " 171 "subloop tree currently being processed."); 172 if (&L == CurrentL) 173 SkipCurrentLoop = true; 174 } 175 176 /// Loop passes should use this method to indicate they have added new child 177 /// loops of the current loop. 178 /// 179 /// \p NewChildLoops must contain only the immediate children. Any nested 180 /// loops within them will be visited in postorder as usual for the loop pass 181 /// manager. 182 void addChildLoops(ArrayRef<Loop *> NewChildLoops) { 183 // Insert ourselves back into the worklist first, as this loop should be 184 // revisited after all the children have been processed. 185 Worklist.insert(CurrentL); 186 187#ifndef NDEBUG 188 for (Loop *NewL : NewChildLoops) 189 assert(NewL->getParentLoop() == CurrentL && "All of the new loops must " 190 "be immediate children of " 191 "the current loop!"); 192#endif 193 194 internal::appendLoopsToWorklist(NewChildLoops, Worklist); 195 196 // Also skip further processing of the current loop--it will be revisited 197 // after all of its newly added children are accounted for. 198 SkipCurrentLoop = true; 199 } 200 201 /// Loop passes should use this method to indicate they have added new 202 /// sibling loops to the current loop. 203 /// 204 /// \p NewSibLoops must only contain the immediate sibling loops. Any nested 205 /// loops within them will be visited in postorder as usual for the loop pass 206 /// manager. 207 void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) { 208#ifndef NDEBUG 209 for (Loop *NewL : NewSibLoops) 210 assert(NewL->getParentLoop() == ParentL && 211 "All of the new loops must be siblings of the current loop!"); 212#endif 213 214 internal::appendLoopsToWorklist(NewSibLoops, Worklist); 215 216 // No need to skip the current loop or revisit it, as sibling loops 217 // shouldn't impact anything. 218 } 219 220private: 221 template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor; 222 223 /// The \c FunctionToLoopPassAdaptor's worklist of loops to process. 224 SmallPriorityWorklist<Loop *, 4> &Worklist; 225 226 /// The analysis manager for use in the current loop nest. 227 LoopAnalysisManager &LAM; 228 229 Loop *CurrentL; 230 bool SkipCurrentLoop; 231 232#ifndef NDEBUG 233 // In debug builds we also track the parent loop to implement asserts even in 234 // the face of loop deletion. 235 Loop *ParentL; 236#endif 237 238 LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist, 239 LoopAnalysisManager &LAM) 240 : Worklist(Worklist), LAM(LAM) {} 241}; 242 243/// \brief Adaptor that maps from a function to its loops. 244/// 245/// Designed to allow composition of a LoopPass(Manager) and a 246/// FunctionPassManager. Note that if this pass is constructed with a \c 247/// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy 248/// analysis prior to running the loop passes over the function to enable a \c 249/// LoopAnalysisManager to be used within this run safely. 250template <typename LoopPassT> 251class FunctionToLoopPassAdaptor 252 : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> { 253public: 254 explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) { 255 LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); 256 LoopCanonicalizationFPM.addPass(LCSSAPass()); 257 } 258 259 /// \brief Runs the loop passes across every loop in the function. 260 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { 261 // Before we even compute any loop analyses, first run a miniature function 262 // pass pipeline to put loops into their canonical form. Note that we can 263 // directly build up function analyses after this as the function pass 264 // manager handles all the invalidation at that layer. 265 PreservedAnalyses PA = LoopCanonicalizationFPM.run(F, AM); 266 267 // Get the loop structure for this function 268 LoopInfo &LI = AM.getResult<LoopAnalysis>(F); 269 270 // If there are no loops, there is nothing to do here. 271 if (LI.empty()) 272 return PA; 273 274 // Get the analysis results needed by loop passes. 275 LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F), 276 AM.getResult<AssumptionAnalysis>(F), 277 AM.getResult<DominatorTreeAnalysis>(F), 278 AM.getResult<LoopAnalysis>(F), 279 AM.getResult<ScalarEvolutionAnalysis>(F), 280 AM.getResult<TargetLibraryAnalysis>(F), 281 AM.getResult<TargetIRAnalysis>(F)}; 282 283 // Setup the loop analysis manager from its proxy. It is important that 284 // this is only done when there are loops to process and we have built the 285 // LoopStandardAnalysisResults object. The loop analyses cached in this 286 // manager have access to those analysis results and so it must invalidate 287 // itself when they go away. 288 LoopAnalysisManager &LAM = 289 AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager(); 290 291 // A postorder worklist of loops to process. 292 SmallPriorityWorklist<Loop *, 4> Worklist; 293 294 // Register the worklist and loop analysis manager so that loop passes can 295 // update them when they mutate the loop nest structure. 296 LPMUpdater Updater(Worklist, LAM); 297 298 // Add the loop nests in the reverse order of LoopInfo. For some reason, 299 // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For 300 // the purpose of unrolling, loop deletion, and LICM, we largely want to 301 // work forward across the CFG so that we visit defs before uses and can 302 // propagate simplifications from one loop nest into the next. 303 // FIXME: Consider changing the order in LoopInfo. 304 internal::appendLoopsToWorklist(reverse(LI), Worklist); 305 306 do { 307 Loop *L = Worklist.pop_back_val(); 308 309 // Reset the update structure for this loop. 310 Updater.CurrentL = L; 311 Updater.SkipCurrentLoop = false; 312 313#ifndef NDEBUG 314 // Save a parent loop pointer for asserts. 315 Updater.ParentL = L->getParentLoop(); 316 317 // Verify the loop structure and LCSSA form before visiting the loop. 318 L->verifyLoop(); 319 assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) && 320 "Loops must remain in LCSSA form!"); 321#endif 322 323 PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater); 324 // FIXME: We should verify the set of analyses relevant to Loop passes 325 // are preserved. 326 327 // If the loop hasn't been deleted, we need to handle invalidation here. 328 if (!Updater.skipCurrentLoop()) 329 // We know that the loop pass couldn't have invalidated any other 330 // loop's analyses (that's the contract of a loop pass), so directly 331 // handle the loop analysis manager's invalidation here. 332 LAM.invalidate(*L, PassPA); 333 334 // Then intersect the preserved set so that invalidation of module 335 // analyses will eventually occur when the module pass completes. 336 PA.intersect(std::move(PassPA)); 337 } while (!Worklist.empty()); 338 339 // By definition we preserve the proxy. We also preserve all analyses on 340 // Loops. This precludes *any* invalidation of loop analyses by the proxy, 341 // but that's OK because we've taken care to invalidate analyses in the 342 // loop analysis manager incrementally above. 343 PA.preserveSet<AllAnalysesOn<Loop>>(); 344 PA.preserve<LoopAnalysisManagerFunctionProxy>(); 345 // We also preserve the set of standard analyses. 346 PA.preserve<DominatorTreeAnalysis>(); 347 PA.preserve<LoopAnalysis>(); 348 PA.preserve<ScalarEvolutionAnalysis>(); 349 // FIXME: What we really want to do here is preserve an AA category, but 350 // that concept doesn't exist yet. 351 PA.preserve<AAManager>(); 352 PA.preserve<BasicAA>(); 353 PA.preserve<GlobalsAA>(); 354 PA.preserve<SCEVAA>(); 355 return PA; 356 } 357 358private: 359 LoopPassT Pass; 360 361 FunctionPassManager LoopCanonicalizationFPM; 362}; 363 364/// \brief A function to deduce a loop pass type and wrap it in the templated 365/// adaptor. 366template <typename LoopPassT> 367FunctionToLoopPassAdaptor<LoopPassT> 368createFunctionToLoopPassAdaptor(LoopPassT Pass) { 369 return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass)); 370} 371 372/// \brief Pass for printing a loop's contents as textual IR. 373class PrintLoopPass : public PassInfoMixin<PrintLoopPass> { 374 raw_ostream &OS; 375 std::string Banner; 376 377public: 378 PrintLoopPass(); 379 PrintLoopPass(raw_ostream &OS, const std::string &Banner = ""); 380 381 PreservedAnalyses run(Loop &L, LoopAnalysisManager &, 382 LoopStandardAnalysisResults &, LPMUpdater &); 383}; 384} 385 386#endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H 387