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 struct holds information about recurrence variables.
58 class RecurrenceDescriptor {
61 /// This enum represents the kinds of recurrences that we support.
63 RK_NoRecurrence, ///< Not a recurrence.
64 RK_IntegerAdd, ///< Sum of integers.
65 RK_IntegerMult, ///< Product of integers.
66 RK_IntegerOr, ///< Bitwise or logical OR of numbers.
67 RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
68 RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
69 RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
70 RK_FloatAdd, ///< Sum of floats.
71 RK_FloatMult, ///< Product of floats.
72 RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
75 // This enum represents the kind of minmax recurrence.
76 enum MinMaxRecurrenceKind {
86 RecurrenceDescriptor()
87 : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence),
88 MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr) {}
90 RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
91 MinMaxRecurrenceKind MK,
92 Instruction *UAI /*Unsafe Algebra Inst*/)
93 : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
94 UnsafeAlgebraInst(UAI) {}
96 /// This POD struct holds information about a potential recurrence operation.
100 InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
101 : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
102 UnsafeAlgebraInst(UAI) {}
104 InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
105 : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
106 UnsafeAlgebraInst(UAI) {}
108 bool isRecurrence() { return IsRecurrence; }
110 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
112 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
114 MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
116 Instruction *getPatternInst() { return PatternLastInst; }
119 // Is this instruction a recurrence candidate.
121 // The last instruction in a min/max pattern (select of the select(icmp())
122 // pattern), or the current recurrence instruction otherwise.
123 Instruction *PatternLastInst;
124 // If this is a min/max pattern the comparison predicate.
125 MinMaxRecurrenceKind MinMaxKind;
126 // Recurrence has unsafe algebra.
127 Instruction *UnsafeAlgebraInst;
130 /// Returns a struct describing if the instruction 'I' can be a recurrence
131 /// variable of type 'Kind'. If the recurrence is a min/max pattern of
132 /// select(icmp()) this function advances the instruction pointer 'I' from the
133 /// compare instruction to the select instruction and stores this pointer in
134 /// 'PatternLastInst' member of the returned struct.
135 static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
136 InstDesc &Prev, bool HasFunNoNaNAttr);
138 /// Returns true if instruction I has multiple uses in Insts
139 static bool hasMultipleUsesOf(Instruction *I,
140 SmallPtrSetImpl<Instruction *> &Insts);
142 /// Returns true if all uses of the instruction I is within the Set.
143 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
145 /// Returns a struct describing if the instruction if the instruction is a
146 /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
148 static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
150 /// Returns identity corresponding to the RecurrenceKind.
151 static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
153 /// Returns the opcode of binary operation corresponding to the
155 static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
157 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
158 static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK,
159 Value *Left, Value *Right);
161 /// Returns true if Phi is a reduction of type Kind and adds it to the
162 /// RecurrenceDescriptor.
163 static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
164 bool HasFunNoNaNAttr,
165 RecurrenceDescriptor &RedDes);
167 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
168 /// returned in RedDes.
169 static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
170 RecurrenceDescriptor &RedDes);
172 RecurrenceKind getRecurrenceKind() { return Kind; }
174 MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
176 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
178 Instruction *getLoopExitInstr() { return LoopExitInstr; }
180 /// Returns true if the recurrence has unsafe algebra which requires a relaxed
181 /// floating-point model.
182 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
184 /// Returns first unsafe algebra instruction in the PHI node's use-chain.
185 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
188 // The starting value of the recurrence.
189 // It does not have to be zero!
190 TrackingVH<Value> StartValue;
191 // The instruction who's value is used outside the loop.
192 Instruction *LoopExitInstr;
193 // The kind of the recurrence.
195 // If this a min/max recurrence the kind of recurrence.
196 MinMaxRecurrenceKind MinMaxKind;
197 // First occurance of unasfe algebra in the PHI's use-chain.
198 Instruction *UnsafeAlgebraInst;
201 /// A struct for saving information about induction variables.
202 class InductionDescriptor {
204 /// This enum represents the kinds of inductions that we support.
206 IK_NoInduction, ///< Not an induction variable.
207 IK_IntInduction, ///< Integer induction variable. Step = C.
208 IK_PtrInduction ///< Pointer induction var. Step = C / sizeof(elem).
212 /// Private constructor - use \c isInductionPHI.
213 InductionDescriptor(Value *Start, InductionKind K, ConstantInt *Step);
215 /// Default constructor - creates an invalid induction.
216 InductionDescriptor()
217 : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {}
219 /// Get the consecutive direction. Returns:
220 /// 0 - unknown or non-consecutive.
221 /// 1 - consecutive and increasing.
222 /// -1 - consecutive and decreasing.
223 int getConsecutiveDirection() const;
225 /// Compute the transformed value of Index at offset StartValue using step
227 /// For integer induction, returns StartValue + Index * StepValue.
228 /// For pointer induction, returns StartValue[Index * StepValue].
229 /// FIXME: The newly created binary instructions should contain nsw/nuw
230 /// flags, which can be found from the original scalar operations.
231 Value *transform(IRBuilder<> &B, Value *Index) const;
233 Value *getStartValue() const { return StartValue; }
234 InductionKind getKind() const { return IK; }
235 ConstantInt *getStepValue() const { return StepValue; }
237 static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
238 InductionDescriptor &D);
242 TrackingVH<Value> StartValue;
246 ConstantInt *StepValue;
249 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
251 /// \brief Simplify each loop in a loop nest recursively.
253 /// This takes a potentially un-simplified loop L (and its children) and turns
254 /// it into a simplified loop nest with preheaders and single backedges. It
255 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
257 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
258 ScalarEvolution *SE = nullptr, AssumptionCache *AC = nullptr);
260 /// \brief Put loop into LCSSA form.
262 /// Looks at all instructions in the loop which have uses outside of the
263 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
264 /// the loop are rewritten to use this node.
266 /// LoopInfo and DominatorTree are required and preserved.
268 /// If ScalarEvolution is passed in, it will be preserved.
270 /// Returns true if any modifications are made to the loop.
271 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
272 ScalarEvolution *SE = nullptr);
274 /// \brief Put a loop nest into LCSSA form.
276 /// This recursively forms LCSSA for a loop nest.
278 /// LoopInfo and DominatorTree are required and preserved.
280 /// If ScalarEvolution is passed in, it will be preserved.
282 /// Returns true if any modifications are made to the loop.
283 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
284 ScalarEvolution *SE = nullptr);
286 /// \brief Walk the specified region of the CFG (defined by all blocks
287 /// dominated by the specified block, and that are in the current loop) in
288 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
289 /// uses before definitions, allowing us to sink a loop body in one pass without
290 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
291 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
292 /// instructions of the loop and loop safety information as arguments.
293 /// It returns changed status.
294 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
295 TargetLibraryInfo *, Loop *, AliasSetTracker *,
298 /// \brief Walk the specified region of the CFG (defined by all blocks
299 /// dominated by the specified block, and that are in the current loop) in depth
300 /// first order w.r.t the DominatorTree. This allows us to visit definitions
301 /// before uses, allowing us to hoist a loop body in one pass without iteration.
302 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
303 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
304 /// loop and loop safety information as arguments. It returns changed status.
305 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
306 TargetLibraryInfo *, Loop *, AliasSetTracker *,
309 /// \brief Try to promote memory values to scalars by sinking stores out of
310 /// the loop and moving loads to before the loop. We do this by looping over
311 /// the stores in the loop, looking for stores to Must pointers which are
312 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
313 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
314 /// AliasSet information for all instructions of the loop and loop safety
315 /// information as arguments. It returns changed status.
316 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
317 SmallVectorImpl<Instruction*> &,
318 PredIteratorCache &, LoopInfo *,
319 DominatorTree *, Loop *, AliasSetTracker *,
322 /// \brief Computes safety information for a loop
323 /// checks loop body & header for the possibility of may throw
324 /// exception, it takes LICMSafetyInfo and loop as argument.
325 /// Updates safety information in LICMSafetyInfo argument.
326 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
328 /// \brief Returns the instructions that use values defined in the loop.
329 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);