1 //===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- 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 "describes" induction and recurrence variables.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
15 #define LLVM_ANALYSIS_IVDESCRIPTORS_H
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/Optional.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/StringRef.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/DemandedBits.h"
25 #include "llvm/Analysis/EHPersonalities.h"
26 #include "llvm/Analysis/MustExecute.h"
27 #include "llvm/Analysis/TargetTransformInfo.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Operator.h"
32 #include "llvm/IR/ValueHandle.h"
33 #include "llvm/Support/Casting.h"
38 class AliasSetTracker;
43 class OptimizationRemarkEmitter;
44 class PredicatedScalarEvolution;
45 class PredIteratorCache;
46 class ScalarEvolution;
48 class TargetLibraryInfo;
49 class TargetTransformInfo;
51 /// The RecurrenceDescriptor is used to identify recurrences variables in a
52 /// loop. Reduction is a special case of recurrence that has uses of the
53 /// recurrence variable outside the loop. The method isReductionPHI identifies
54 /// reductions that are basic recurrences.
56 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
57 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
58 /// array[i]; } is a summation of array elements. Basic recurrences are a
59 /// special case of chains of recurrences (CR). See ScalarEvolution for CR
62 /// This struct holds information about recurrence variables.
63 class RecurrenceDescriptor {
65 /// This enum represents the kinds of recurrences that we support.
67 RK_NoRecurrence, ///< Not a recurrence.
68 RK_IntegerAdd, ///< Sum of integers.
69 RK_IntegerMult, ///< Product of integers.
70 RK_IntegerOr, ///< Bitwise or logical OR of numbers.
71 RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
72 RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
73 RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
74 RK_FloatAdd, ///< Sum of floats.
75 RK_FloatMult, ///< Product of floats.
76 RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
79 // This enum represents the kind of minmax recurrence.
80 enum MinMaxRecurrenceKind {
90 RecurrenceDescriptor() = default;
92 RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
93 MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
94 bool Signed, SmallPtrSetImpl<Instruction *> &CI)
95 : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
96 UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
97 CastInsts.insert(CI.begin(), CI.end());
100 /// This POD struct holds information about a potential recurrence operation.
103 InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
104 : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
105 UnsafeAlgebraInst(UAI) {}
107 InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
108 : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
109 UnsafeAlgebraInst(UAI) {}
111 bool isRecurrence() { return IsRecurrence; }
113 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
115 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
117 MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
119 Instruction *getPatternInst() { return PatternLastInst; }
122 // Is this instruction a recurrence candidate.
124 // The last instruction in a min/max pattern (select of the select(icmp())
125 // pattern), or the current recurrence instruction otherwise.
126 Instruction *PatternLastInst;
127 // If this is a min/max pattern the comparison predicate.
128 MinMaxRecurrenceKind MinMaxKind;
129 // Recurrence has unsafe algebra.
130 Instruction *UnsafeAlgebraInst;
133 /// Returns a struct describing if the instruction 'I' can be a recurrence
134 /// variable of type 'Kind'. If the recurrence is a min/max pattern of
135 /// select(icmp()) this function advances the instruction pointer 'I' from the
136 /// compare instruction to the select instruction and stores this pointer in
137 /// 'PatternLastInst' member of the returned struct.
138 static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
139 InstDesc &Prev, bool HasFunNoNaNAttr);
141 /// Returns true if instruction I has multiple uses in Insts
142 static bool hasMultipleUsesOf(Instruction *I,
143 SmallPtrSetImpl<Instruction *> &Insts,
144 unsigned MaxNumUses);
146 /// Returns true if all uses of the instruction I is within the Set.
147 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
149 /// Returns a struct describing if the instruction if the instruction is a
150 /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
152 static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
154 /// Returns a struct describing if the instruction is a
155 /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
156 static InstDesc isConditionalRdxPattern(RecurrenceKind Kind, Instruction *I);
158 /// Returns identity corresponding to the RecurrenceKind.
159 static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
161 /// Returns the opcode of binary operation corresponding to the
163 static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
165 /// Returns true if Phi is a reduction of type Kind and adds it to the
166 /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
167 /// non-null, the minimal bit width needed to compute the reduction will be
169 static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
170 bool HasFunNoNaNAttr,
171 RecurrenceDescriptor &RedDes,
172 DemandedBits *DB = nullptr,
173 AssumptionCache *AC = nullptr,
174 DominatorTree *DT = nullptr);
176 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
177 /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
178 /// non-null, the minimal bit width needed to compute the reduction will be
180 static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
181 RecurrenceDescriptor &RedDes,
182 DemandedBits *DB = nullptr,
183 AssumptionCache *AC = nullptr,
184 DominatorTree *DT = nullptr);
186 /// Returns true if Phi is a first-order recurrence. A first-order recurrence
187 /// is a non-reduction recurrence relation in which the value of the
188 /// recurrence in the current loop iteration equals a value defined in the
189 /// previous iteration. \p SinkAfter includes pairs of instructions where the
190 /// first will be rescheduled to appear after the second if/when the loop is
191 /// vectorized. It may be augmented with additional pairs if needed in order
192 /// to handle Phi as a first-order recurrence.
194 isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
195 DenseMap<Instruction *, Instruction *> &SinkAfter,
198 RecurrenceKind getRecurrenceKind() { return Kind; }
200 MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
202 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
204 Instruction *getLoopExitInstr() { return LoopExitInstr; }
206 /// Returns true if the recurrence has unsafe algebra which requires a relaxed
207 /// floating-point model.
208 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
210 /// Returns first unsafe algebra instruction in the PHI node's use-chain.
211 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
213 /// Returns true if the recurrence kind is an integer kind.
214 static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
216 /// Returns true if the recurrence kind is a floating point kind.
217 static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
219 /// Returns true if the recurrence kind is an arithmetic kind.
220 static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
222 /// Returns the type of the recurrence. This type can be narrower than the
223 /// actual type of the Phi if the recurrence has been type-promoted.
224 Type *getRecurrenceType() { return RecurrenceType; }
226 /// Returns a reference to the instructions used for type-promoting the
228 SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
230 /// Returns true if all source operands of the recurrence are SExtInsts.
231 bool isSigned() { return IsSigned; }
234 // The starting value of the recurrence.
235 // It does not have to be zero!
236 TrackingVH<Value> StartValue;
237 // The instruction who's value is used outside the loop.
238 Instruction *LoopExitInstr = nullptr;
239 // The kind of the recurrence.
240 RecurrenceKind Kind = RK_NoRecurrence;
241 // If this a min/max recurrence the kind of recurrence.
242 MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
243 // First occurrence of unasfe algebra in the PHI's use-chain.
244 Instruction *UnsafeAlgebraInst = nullptr;
245 // The type of the recurrence.
246 Type *RecurrenceType = nullptr;
247 // True if all source operands of the recurrence are SExtInsts.
248 bool IsSigned = false;
249 // Instructions used for type-promoting the recurrence.
250 SmallPtrSet<Instruction *, 8> CastInsts;
253 /// A struct for saving information about induction variables.
254 class InductionDescriptor {
256 /// This enum represents the kinds of inductions that we support.
258 IK_NoInduction, ///< Not an induction variable.
259 IK_IntInduction, ///< Integer induction variable. Step = C.
260 IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
261 IK_FpInduction ///< Floating point induction variable.
265 /// Default constructor - creates an invalid induction.
266 InductionDescriptor() = default;
268 /// Get the consecutive direction. Returns:
269 /// 0 - unknown or non-consecutive.
270 /// 1 - consecutive and increasing.
271 /// -1 - consecutive and decreasing.
272 int getConsecutiveDirection() const;
274 Value *getStartValue() const { return StartValue; }
275 InductionKind getKind() const { return IK; }
276 const SCEV *getStep() const { return Step; }
277 BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
278 ConstantInt *getConstIntStepValue() const;
280 /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
281 /// induction, the induction descriptor \p D will contain the data describing
282 /// this induction. If by some other means the caller has a better SCEV
283 /// expression for \p Phi than the one returned by the ScalarEvolution
284 /// analysis, it can be passed through \p Expr. If the def-use chain
285 /// associated with the phi includes casts (that we know we can ignore
286 /// under proper runtime checks), they are passed through \p CastsToIgnore.
288 isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
289 InductionDescriptor &D, const SCEV *Expr = nullptr,
290 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
292 /// Returns true if \p Phi is a floating point induction in the loop \p L.
293 /// If \p Phi is an induction, the induction descriptor \p D will contain
294 /// the data describing this induction.
295 static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
296 InductionDescriptor &D);
298 /// Returns true if \p Phi is a loop \p L induction, in the context associated
299 /// with the run-time predicate of PSE. If \p Assume is true, this can add
300 /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
302 /// If \p Phi is an induction, \p D will contain the data describing this
304 static bool isInductionPHI(PHINode *Phi, const Loop *L,
305 PredicatedScalarEvolution &PSE,
306 InductionDescriptor &D, bool Assume = false);
308 /// Returns true if the induction type is FP and the binary operator does
309 /// not have the "fast-math" property. Such operation requires a relaxed FP
311 bool hasUnsafeAlgebra() {
312 return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
315 /// Returns induction operator that does not have "fast-math" property
316 /// and requires FP unsafe mode.
317 Instruction *getUnsafeAlgebraInst() {
318 if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
320 return InductionBinOp;
323 /// Returns binary opcode of the induction operator.
324 Instruction::BinaryOps getInductionOpcode() const {
325 return InductionBinOp ? InductionBinOp->getOpcode()
326 : Instruction::BinaryOpsEnd;
329 /// Returns a reference to the type cast instructions in the induction
330 /// update chain, that are redundant when guarded with a runtime
331 /// SCEV overflow check.
332 const SmallVectorImpl<Instruction *> &getCastInsts() const {
333 return RedundantCasts;
337 /// Private constructor - used by \c isInductionPHI.
338 InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
339 BinaryOperator *InductionBinOp = nullptr,
340 SmallVectorImpl<Instruction *> *Casts = nullptr);
343 TrackingVH<Value> StartValue;
345 InductionKind IK = IK_NoInduction;
347 const SCEV *Step = nullptr;
348 // Instruction that advances induction variable.
349 BinaryOperator *InductionBinOp = nullptr;
350 // Instructions used for type-casts of the induction variable,
351 // that are redundant when guarded with a runtime SCEV overflow check.
352 SmallVector<Instruction *, 2> RedundantCasts;
355 } // end namespace llvm
357 #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H