1 //===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -*- C++ -*-=========//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines some loop transformation utilities.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
15 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/IRBuilder.h"
24 class AliasSetTracker;
25 class AssumptionCache;
32 class PredIteratorCache;
33 class ScalarEvolution;
34 class TargetLibraryInfo;
36 /// \brief Captures loop safety information.
37 /// It keep information for loop & its header may throw exception.
38 struct LICMSafetyInfo {
39 bool MayThrow; // The current loop contains an instruction which
41 bool HeaderMayThrow; // Same as previous, but specific to loop header
42 LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false)
46 /// The RecurrenceDescriptor is used to identify recurrences variables in a
47 /// loop. Reduction is a special case of recurrence that has uses of the
48 /// recurrence variable outside the loop. The method isReductionPHI identifies
49 /// reductions that are basic recurrences.
51 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
52 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
53 /// array[i]; } is a summation of array elements. Basic recurrences are a
54 /// special case of chains of recurrences (CR). See ScalarEvolution for CR
57 /// This POD struct holds information about a potential recurrence operation.
58 class RecurrenceInstDesc {
61 // This enum represents the kind of minmax recurrence.
62 enum MinMaxRecurrenceKind {
71 RecurrenceInstDesc(bool IsRecur, Instruction *I)
72 : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid) {}
74 RecurrenceInstDesc(Instruction *I, MinMaxRecurrenceKind K)
75 : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K) {}
77 bool isRecurrence() { return IsRecurrence; }
79 MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
81 Instruction *getPatternInst() { return PatternLastInst; }
84 // Is this instruction a recurrence candidate.
86 // The last instruction in a min/max pattern (select of the select(icmp())
87 // pattern), or the current recurrence instruction otherwise.
88 Instruction *PatternLastInst;
89 // If this is a min/max pattern the comparison predicate.
90 MinMaxRecurrenceKind MinMaxKind;
93 /// This struct holds information about recurrence variables.
94 class RecurrenceDescriptor {
97 /// This enum represents the kinds of recurrences that we support.
99 RK_NoRecurrence, ///< Not a recurrence.
100 RK_IntegerAdd, ///< Sum of integers.
101 RK_IntegerMult, ///< Product of integers.
102 RK_IntegerOr, ///< Bitwise or logical OR of numbers.
103 RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
104 RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
105 RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
106 RK_FloatAdd, ///< Sum of floats.
107 RK_FloatMult, ///< Product of floats.
108 RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
111 RecurrenceDescriptor()
112 : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence),
113 MinMaxKind(RecurrenceInstDesc::MRK_Invalid) {}
115 RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
116 RecurrenceInstDesc::MinMaxRecurrenceKind MK)
117 : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {}
119 /// Returns a struct describing if the instruction 'I' can be a recurrence
120 /// variable of type 'Kind'. If the recurrence is a min/max pattern of
121 /// select(icmp()) this function advances the instruction pointer 'I' from the
122 /// compare instruction to the select instruction and stores this pointer in
123 /// 'PatternLastInst' member of the returned struct.
124 static RecurrenceInstDesc isRecurrenceInstr(Instruction *I,
126 RecurrenceInstDesc &Prev,
127 bool HasFunNoNaNAttr);
129 /// Returns true if instuction I has multiple uses in Insts
130 static bool hasMultipleUsesOf(Instruction *I,
131 SmallPtrSetImpl<Instruction *> &Insts);
133 /// Returns true if all uses of the instruction I is within the Set.
134 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
136 /// Returns a struct describing if the instruction if the instruction is a
137 /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
139 static RecurrenceInstDesc isMinMaxSelectCmpPattern(Instruction *I,
140 RecurrenceInstDesc &Prev);
142 /// Returns identity corresponding to the RecurrenceKind.
143 static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
145 /// Returns the opcode of binary operation corresponding to the
147 static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
149 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
150 static Value *createMinMaxOp(IRBuilder<> &Builder,
151 RecurrenceInstDesc::MinMaxRecurrenceKind RK,
152 Value *Left, Value *Right);
154 /// Returns true if Phi is a reduction of type Kind and adds it to the
155 /// RecurrenceDescriptor.
156 static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
157 bool HasFunNoNaNAttr,
158 RecurrenceDescriptor &RedDes);
160 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
161 /// returned in RedDes.
162 static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
163 RecurrenceDescriptor &RedDes);
165 RecurrenceKind getRecurrenceKind() { return Kind; }
167 RecurrenceInstDesc::MinMaxRecurrenceKind getMinMaxRecurrenceKind() {
171 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
173 Instruction *getLoopExitInstr() { return LoopExitInstr; }
176 // The starting value of the recurrence.
177 // It does not have to be zero!
178 TrackingVH<Value> StartValue;
179 // The instruction who's value is used outside the loop.
180 Instruction *LoopExitInstr;
181 // The kind of the recurrence.
183 // If this a min/max recurrence the kind of recurrence.
184 RecurrenceInstDesc::MinMaxRecurrenceKind MinMaxKind;
187 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
189 /// \brief Simplify each loop in a loop nest recursively.
191 /// This takes a potentially un-simplified loop L (and its children) and turns
192 /// it into a simplified loop nest with preheaders and single backedges. It
193 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
195 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
196 AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr,
197 AssumptionCache *AC = nullptr);
199 /// \brief Put loop into LCSSA form.
201 /// Looks at all instructions in the loop which have uses outside of the
202 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
203 /// the loop are rewritten to use this node.
205 /// LoopInfo and DominatorTree are required and preserved.
207 /// If ScalarEvolution is passed in, it will be preserved.
209 /// Returns true if any modifications are made to the loop.
210 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
211 ScalarEvolution *SE = nullptr);
213 /// \brief Put a loop nest into LCSSA form.
215 /// This recursively forms LCSSA for a loop nest.
217 /// LoopInfo and DominatorTree are required and preserved.
219 /// If ScalarEvolution is passed in, it will be preserved.
221 /// Returns true if any modifications are made to the loop.
222 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
223 ScalarEvolution *SE = nullptr);
225 /// \brief Walk the specified region of the CFG (defined by all blocks
226 /// dominated by the specified block, and that are in the current loop) in
227 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
228 /// uses before definitions, allowing us to sink a loop body in one pass without
229 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
230 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
231 /// instructions of the loop and loop safety information as arguments.
232 /// It returns changed status.
233 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
234 TargetLibraryInfo *, Loop *, AliasSetTracker *,
237 /// \brief Walk the specified region of the CFG (defined by all blocks
238 /// dominated by the specified block, and that are in the current loop) in depth
239 /// first order w.r.t the DominatorTree. This allows us to visit definitions
240 /// before uses, allowing us to hoist a loop body in one pass without iteration.
241 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
242 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
243 /// loop and loop safety information as arguments. It returns changed status.
244 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
245 TargetLibraryInfo *, Loop *, AliasSetTracker *,
248 /// \brief Try to promote memory values to scalars by sinking stores out of
249 /// the loop and moving loads to before the loop. We do this by looping over
250 /// the stores in the loop, looking for stores to Must pointers which are
251 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
252 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
253 /// AliasSet information for all instructions of the loop and loop safety
254 /// information as arguments. It returns changed status.
255 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
256 SmallVectorImpl<Instruction*> &,
257 PredIteratorCache &, LoopInfo *,
258 DominatorTree *, Loop *, AliasSetTracker *,
261 /// \brief Computes safety information for a loop
262 /// checks loop body & header for the possiblity of may throw
263 /// exception, it takes LICMSafetyInfo and loop as argument.
264 /// Updates safety information in LICMSafetyInfo argument.
265 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
267 /// \brief Checks if the given PHINode in a loop header is an induction
268 /// variable. Returns true if this is an induction PHI along with the step
270 bool isInductionPHI(PHINode *, ScalarEvolution *, ConstantInt *&);