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