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