1 //===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -*- 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 file defines some loop transformation utilities.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
15 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
16 
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/IR/Dominators.h"
19 
20 namespace llvm {
21 class AliasAnalysis;
22 class AliasSet;
23 class AliasSetTracker;
24 class AssumptionCache;
25 class BasicBlock;
26 class DataLayout;
27 class DominatorTree;
28 class Loop;
29 class LoopInfo;
30 class Pass;
31 class PredIteratorCache;
32 class ScalarEvolution;
33 class TargetLibraryInfo;
34 
35 /// \brief Captures loop safety information.
36 /// It keep information for loop & its header may throw exception.
37 struct LICMSafetyInfo {
38   bool MayThrow;           // The current loop contains an instruction which
39                            // may throw.
40   bool HeaderMayThrow;     // Same as previous, but specific to loop header
LICMSafetyInfoLICMSafetyInfo41   LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false)
42   {}
43 };
44 
45 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
46 
47 /// \brief Simplify each loop in a loop nest recursively.
48 ///
49 /// This takes a potentially un-simplified loop L (and its children) and turns
50 /// it into a simplified loop nest with preheaders and single backedges. It
51 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
52 /// passed into it.
53 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
54                   AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr,
55                   AssumptionCache *AC = nullptr);
56 
57 /// \brief Put loop into LCSSA form.
58 ///
59 /// Looks at all instructions in the loop which have uses outside of the
60 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
61 /// the loop are rewritten to use this node.
62 ///
63 /// LoopInfo and DominatorTree are required and preserved.
64 ///
65 /// If ScalarEvolution is passed in, it will be preserved.
66 ///
67 /// Returns true if any modifications are made to the loop.
68 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
69                ScalarEvolution *SE = nullptr);
70 
71 /// \brief Put a loop nest into LCSSA form.
72 ///
73 /// This recursively forms LCSSA for a loop nest.
74 ///
75 /// LoopInfo and DominatorTree are required and preserved.
76 ///
77 /// If ScalarEvolution is passed in, it will be preserved.
78 ///
79 /// Returns true if any modifications are made to the loop.
80 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
81                           ScalarEvolution *SE = nullptr);
82 
83 /// \brief Walk the specified region of the CFG (defined by all blocks
84 /// dominated by the specified block, and that are in the current loop) in
85 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
86 /// uses before definitions, allowing us to sink a loop body in one pass without
87 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
88 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
89 /// instructions of the loop and loop safety information as arguments.
90 /// It returns changed status.
91 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
92                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
93                 LICMSafetyInfo *);
94 
95 /// \brief Walk the specified region of the CFG (defined by all blocks
96 /// dominated by the specified block, and that are in the current loop) in depth
97 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
98 /// before uses, allowing us to hoist a loop body in one pass without iteration.
99 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
100 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
101 /// loop and loop safety information as arguments. It returns changed status.
102 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
103                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
104                  LICMSafetyInfo *);
105 
106 /// \brief Try to promote memory values to scalars by sinking stores out of
107 /// the loop and moving loads to before the loop.  We do this by looping over
108 /// the stores in the loop, looking for stores to Must pointers which are
109 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
110 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
111 /// AliasSet information for all instructions of the loop and loop safety
112 /// information as arguments. It returns changed status.
113 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
114                                   SmallVectorImpl<Instruction*> &,
115                                   PredIteratorCache &, LoopInfo *,
116                                   DominatorTree *, Loop *, AliasSetTracker *,
117                                   LICMSafetyInfo *);
118 
119 /// \brief Computes safety information for a loop
120 /// checks loop body & header for the possiblity of may throw
121 /// exception, it takes LICMSafetyInfo and loop as argument.
122 /// Updates safety information in LICMSafetyInfo argument.
123 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
124 
125 /// \brief Checks if the given PHINode in a loop header is an induction
126 /// variable. Returns true if this is an induction PHI along with the step
127 /// value.
128 bool isInductionPHI(PHINode *, ScalarEvolution *, ConstantInt *&);
129 }
130 
131 #endif
132