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/Analysis/AliasAnalysis.h"
19 #include "llvm/Analysis/EHPersonalities.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/IR/IRBuilder.h"
25 class AliasSetTracker;
26 class AssumptionCache;
33 class PredIteratorCache;
34 class ScalarEvolution;
35 class TargetLibraryInfo;
37 /// \brief Captures loop safety information.
38 /// It keep information for loop & its header may throw exception.
39 struct LICMSafetyInfo {
40 bool MayThrow; // The current loop contains an instruction which
42 bool HeaderMayThrow; // Same as previous, but specific to loop header
43 // Used to update funclet bundle operands.
44 DenseMap<BasicBlock *, ColorVector> BlockColors;
45 LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false)
49 /// The RecurrenceDescriptor is used to identify recurrences variables in a
50 /// loop. Reduction is a special case of recurrence that has uses of the
51 /// recurrence variable outside the loop. The method isReductionPHI identifies
52 /// reductions that are basic recurrences.
54 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
55 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
56 /// array[i]; } is a summation of array elements. Basic recurrences are a
57 /// special case of chains of recurrences (CR). See ScalarEvolution for CR
60 /// This struct holds information about recurrence variables.
61 class RecurrenceDescriptor {
64 /// This enum represents the kinds of recurrences that we support.
66 RK_NoRecurrence, ///< Not a recurrence.
67 RK_IntegerAdd, ///< Sum of integers.
68 RK_IntegerMult, ///< Product of integers.
69 RK_IntegerOr, ///< Bitwise or logical OR of numbers.
70 RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
71 RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
72 RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
73 RK_FloatAdd, ///< Sum of floats.
74 RK_FloatMult, ///< Product of floats.
75 RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
78 // This enum represents the kind of minmax recurrence.
79 enum MinMaxRecurrenceKind {
89 RecurrenceDescriptor()
90 : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence),
91 MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr),
92 RecurrenceType(nullptr), IsSigned(false) {}
94 RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
95 MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
96 bool Signed, SmallPtrSetImpl<Instruction *> &CI)
97 : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
98 UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
99 CastInsts.insert(CI.begin(), CI.end());
102 /// This POD struct holds information about a potential recurrence operation.
106 InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
107 : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
108 UnsafeAlgebraInst(UAI) {}
110 InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
111 : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
112 UnsafeAlgebraInst(UAI) {}
114 bool isRecurrence() { return IsRecurrence; }
116 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
118 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
120 MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
122 Instruction *getPatternInst() { return PatternLastInst; }
125 // Is this instruction a recurrence candidate.
127 // The last instruction in a min/max pattern (select of the select(icmp())
128 // pattern), or the current recurrence instruction otherwise.
129 Instruction *PatternLastInst;
130 // If this is a min/max pattern the comparison predicate.
131 MinMaxRecurrenceKind MinMaxKind;
132 // Recurrence has unsafe algebra.
133 Instruction *UnsafeAlgebraInst;
136 /// Returns a struct describing if the instruction 'I' can be a recurrence
137 /// variable of type 'Kind'. If the recurrence is a min/max pattern of
138 /// select(icmp()) this function advances the instruction pointer 'I' from the
139 /// compare instruction to the select instruction and stores this pointer in
140 /// 'PatternLastInst' member of the returned struct.
141 static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
142 InstDesc &Prev, bool HasFunNoNaNAttr);
144 /// Returns true if instruction I has multiple uses in Insts
145 static bool hasMultipleUsesOf(Instruction *I,
146 SmallPtrSetImpl<Instruction *> &Insts);
148 /// Returns true if all uses of the instruction I is within the Set.
149 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
151 /// Returns a struct describing if the instruction if the instruction is a
152 /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
154 static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
156 /// Returns identity corresponding to the RecurrenceKind.
157 static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
159 /// Returns the opcode of binary operation corresponding to the
161 static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
163 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
164 static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK,
165 Value *Left, Value *Right);
167 /// Returns true if Phi is a reduction of type Kind and adds it to the
168 /// RecurrenceDescriptor.
169 static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
170 bool HasFunNoNaNAttr,
171 RecurrenceDescriptor &RedDes);
173 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
174 /// returned in RedDes.
175 static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
176 RecurrenceDescriptor &RedDes);
178 RecurrenceKind getRecurrenceKind() { return Kind; }
180 MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
182 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
184 Instruction *getLoopExitInstr() { return LoopExitInstr; }
186 /// Returns true if the recurrence has unsafe algebra which requires a relaxed
187 /// floating-point model.
188 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
190 /// Returns first unsafe algebra instruction in the PHI node's use-chain.
191 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
193 /// Returns true if the recurrence kind is an integer kind.
194 static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
196 /// Returns true if the recurrence kind is a floating point kind.
197 static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
199 /// Returns true if the recurrence kind is an arithmetic kind.
200 static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
202 /// Determines if Phi may have been type-promoted. If Phi has a single user
203 /// that ANDs the Phi with a type mask, return the user. RT is updated to
204 /// account for the narrower bit width represented by the mask, and the AND
205 /// instruction is added to CI.
206 static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
207 SmallPtrSetImpl<Instruction *> &Visited,
208 SmallPtrSetImpl<Instruction *> &CI);
210 /// Returns true if all the source operands of a recurrence are either
211 /// SExtInsts or ZExtInsts. This function is intended to be used with
212 /// lookThroughAnd to determine if the recurrence has been type-promoted. The
213 /// source operands are added to CI, and IsSigned is updated to indicate if
214 /// all source operands are SExtInsts.
215 static bool getSourceExtensionKind(Instruction *Start, Instruction *Exit,
216 Type *RT, bool &IsSigned,
217 SmallPtrSetImpl<Instruction *> &Visited,
218 SmallPtrSetImpl<Instruction *> &CI);
220 /// Returns the type of the recurrence. This type can be narrower than the
221 /// actual type of the Phi if the recurrence has been type-promoted.
222 Type *getRecurrenceType() { return RecurrenceType; }
224 /// Returns a reference to the instructions used for type-promoting the
226 SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
228 /// Returns true if all source operands of the recurrence are SExtInsts.
229 bool isSigned() { return IsSigned; }
232 // The starting value of the recurrence.
233 // It does not have to be zero!
234 TrackingVH<Value> StartValue;
235 // The instruction who's value is used outside the loop.
236 Instruction *LoopExitInstr;
237 // The kind of the recurrence.
239 // If this a min/max recurrence the kind of recurrence.
240 MinMaxRecurrenceKind MinMaxKind;
241 // First occurance of unasfe algebra in the PHI's use-chain.
242 Instruction *UnsafeAlgebraInst;
243 // The type of the recurrence.
244 Type *RecurrenceType;
245 // True if all source operands of the recurrence are SExtInsts.
247 // Instructions used for type-promoting the recurrence.
248 SmallPtrSet<Instruction *, 8> CastInsts;
251 /// A struct for saving information about induction variables.
252 class InductionDescriptor {
254 /// This enum represents the kinds of inductions that we support.
256 IK_NoInduction, ///< Not an induction variable.
257 IK_IntInduction, ///< Integer induction variable. Step = C.
258 IK_PtrInduction ///< Pointer induction var. Step = C / sizeof(elem).
262 /// Default constructor - creates an invalid induction.
263 InductionDescriptor()
264 : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {}
266 /// Get the consecutive direction. Returns:
267 /// 0 - unknown or non-consecutive.
268 /// 1 - consecutive and increasing.
269 /// -1 - consecutive and decreasing.
270 int getConsecutiveDirection() const;
272 /// Compute the transformed value of Index at offset StartValue using step
274 /// For integer induction, returns StartValue + Index * StepValue.
275 /// For pointer induction, returns StartValue[Index * StepValue].
276 /// FIXME: The newly created binary instructions should contain nsw/nuw
277 /// flags, which can be found from the original scalar operations.
278 Value *transform(IRBuilder<> &B, Value *Index) const;
280 Value *getStartValue() const { return StartValue; }
281 InductionKind getKind() const { return IK; }
282 ConstantInt *getStepValue() const { return StepValue; }
284 static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
285 InductionDescriptor &D);
288 /// Private constructor - used by \c isInductionPHI.
289 InductionDescriptor(Value *Start, InductionKind K, ConstantInt *Step);
292 TrackingVH<Value> StartValue;
296 ConstantInt *StepValue;
299 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
302 /// \brief Simplify each loop in a loop nest recursively.
304 /// This takes a potentially un-simplified loop L (and its children) and turns
305 /// it into a simplified loop nest with preheaders and single backedges. It will
306 /// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null.
307 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE,
308 AssumptionCache *AC, bool PreserveLCSSA);
310 /// \brief Put loop into LCSSA form.
312 /// Looks at all instructions in the loop which have uses outside of the
313 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
314 /// the loop are rewritten to use this node.
316 /// LoopInfo and DominatorTree are required and preserved.
318 /// If ScalarEvolution is passed in, it will be preserved.
320 /// Returns true if any modifications are made to the loop.
321 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
322 ScalarEvolution *SE);
324 /// \brief Put a loop nest into LCSSA form.
326 /// This recursively forms LCSSA for a loop nest.
328 /// LoopInfo and DominatorTree are required and preserved.
330 /// If ScalarEvolution is passed in, it will be preserved.
332 /// Returns true if any modifications are made to the loop.
333 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
334 ScalarEvolution *SE);
336 /// \brief Walk the specified region of the CFG (defined by all blocks
337 /// dominated by the specified block, and that are in the current loop) in
338 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
339 /// uses before definitions, allowing us to sink a loop body in one pass without
340 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
341 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
342 /// instructions of the loop and loop safety information as arguments.
343 /// It returns changed status.
344 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
345 TargetLibraryInfo *, Loop *, AliasSetTracker *,
348 /// \brief Walk the specified region of the CFG (defined by all blocks
349 /// dominated by the specified block, and that are in the current loop) in depth
350 /// first order w.r.t the DominatorTree. This allows us to visit definitions
351 /// before uses, allowing us to hoist a loop body in one pass without iteration.
352 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
353 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
354 /// loop and loop safety information as arguments. It returns changed status.
355 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
356 TargetLibraryInfo *, Loop *, AliasSetTracker *,
359 /// \brief Try to promote memory values to scalars by sinking stores out of
360 /// the loop and moving loads to before the loop. We do this by looping over
361 /// the stores in the loop, looking for stores to Must pointers which are
362 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
363 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
364 /// AliasSet information for all instructions of the loop and loop safety
365 /// information as arguments. It returns changed status.
366 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
367 SmallVectorImpl<Instruction*> &,
368 PredIteratorCache &, LoopInfo *,
369 DominatorTree *, Loop *, AliasSetTracker *,
372 /// \brief Computes safety information for a loop
373 /// checks loop body & header for the possibility of may throw
374 /// exception, it takes LICMSafetyInfo and loop as argument.
375 /// Updates safety information in LICMSafetyInfo argument.
376 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
378 /// \brief Returns the instructions that use values defined in the loop.
379 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);