1 //===- LoopSimplify.h - Loop Canonicalization Pass --------------*- 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 // 10 // This pass performs several transformations to transform natural loops into a 11 // simpler form, which makes subsequent analyses and transformations simpler and 12 // more effective. 13 // 14 // Loop pre-header insertion guarantees that there is a single, non-critical 15 // entry edge from outside of the loop to the loop header. This simplifies a 16 // number of analyses and transformations, such as LICM. 17 // 18 // Loop exit-block insertion guarantees that all exit blocks from the loop 19 // (blocks which are outside of the loop that have predecessors inside of the 20 // loop) only have predecessors from inside of the loop (and are thus dominated 21 // by the loop header). This simplifies transformations such as store-sinking 22 // that are built into LICM. 23 // 24 // This pass also guarantees that loops will have exactly one backedge. 25 // 26 // Indirectbr instructions introduce several complications. If the loop 27 // contains or is entered by an indirectbr instruction, it may not be possible 28 // to transform the loop and make these guarantees. Client code should check 29 // that these conditions are true before relying on them. 30 // 31 // Note that the simplifycfg pass will clean up blocks which are split out but 32 // end up being unnecessary, so usage of this pass should not pessimize 33 // generated code. 34 // 35 // This pass obviously modifies the CFG, but updates loop information and 36 // dominator information. 37 // 38 //===----------------------------------------------------------------------===// 39 #ifndef LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H 40 #define LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H 41 42 #include "llvm/Analysis/AssumptionCache.h" 43 #include "llvm/Analysis/ScalarEvolution.h" 44 #include "llvm/IR/Dominators.h" 45 #include "llvm/IR/PassManager.h" 46 47 namespace llvm { 48 49 /// This pass is responsible for loop canonicalization. 50 class LoopSimplifyPass : public PassInfoMixin<LoopSimplifyPass> { 51 public: 52 PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM); 53 }; 54 55 /// \brief Simplify each loop in a loop nest recursively. 56 /// 57 /// This takes a potentially un-simplified loop L (and its children) and turns 58 /// it into a simplified loop nest with preheaders and single backedges. It will 59 /// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null. 60 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, 61 AssumptionCache *AC, bool PreserveLCSSA); 62 63 } // end namespace llvm 64 65 #endif // LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H 66