1 //===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file "describes" induction and recurrence variables.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
14 #define LLVM_ANALYSIS_IVDESCRIPTORS_H
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/StringRef.h"
20 #include "llvm/IR/InstrTypes.h"
21 #include "llvm/IR/Instruction.h"
22 #include "llvm/IR/Operator.h"
23 #include "llvm/IR/ValueHandle.h"
24 #include "llvm/Support/Casting.h"
29 class AssumptionCache;
31 class PredicatedScalarEvolution;
32 class ScalarEvolution;
35 class ICFLoopSafetyInfo;
37 /// The RecurrenceDescriptor is used to identify recurrences variables in a
38 /// loop. Reduction is a special case of recurrence that has uses of the
39 /// recurrence variable outside the loop. The method isReductionPHI identifies
40 /// reductions that are basic recurrences.
42 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
43 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
44 /// array[i]; } is a summation of array elements. Basic recurrences are a
45 /// special case of chains of recurrences (CR). See ScalarEvolution for CR
48 /// This struct holds information about recurrence variables.
49 class RecurrenceDescriptor {
51 /// This enum represents the kinds of recurrences that we support.
53 RK_NoRecurrence, ///< Not a recurrence.
54 RK_IntegerAdd, ///< Sum of integers.
55 RK_IntegerMult, ///< Product of integers.
56 RK_IntegerOr, ///< Bitwise or logical OR of numbers.
57 RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
58 RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
59 RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
60 RK_FloatAdd, ///< Sum of floats.
61 RK_FloatMult, ///< Product of floats.
62 RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
65 // This enum represents the kind of minmax recurrence.
66 enum MinMaxRecurrenceKind {
76 RecurrenceDescriptor() = default;
78 RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
79 FastMathFlags FMF, MinMaxRecurrenceKind MK,
80 Instruction *UAI, Type *RT, bool Signed,
81 SmallPtrSetImpl<Instruction *> &CI)
82 : StartValue(Start), LoopExitInstr(Exit), Kind(K), FMF(FMF),
83 MinMaxKind(MK), UnsafeAlgebraInst(UAI), RecurrenceType(RT),
85 CastInsts.insert(CI.begin(), CI.end());
88 /// This POD struct holds information about a potential recurrence operation.
91 InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
92 : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
93 UnsafeAlgebraInst(UAI) {}
95 InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
96 : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
97 UnsafeAlgebraInst(UAI) {}
99 bool isRecurrence() { return IsRecurrence; }
101 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
103 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
105 MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
107 Instruction *getPatternInst() { return PatternLastInst; }
110 // Is this instruction a recurrence candidate.
112 // The last instruction in a min/max pattern (select of the select(icmp())
113 // pattern), or the current recurrence instruction otherwise.
114 Instruction *PatternLastInst;
115 // If this is a min/max pattern the comparison predicate.
116 MinMaxRecurrenceKind MinMaxKind;
117 // Recurrence has unsafe algebra.
118 Instruction *UnsafeAlgebraInst;
121 /// Returns a struct describing if the instruction 'I' can be a recurrence
122 /// variable of type 'Kind'. If the recurrence is a min/max pattern of
123 /// select(icmp()) this function advances the instruction pointer 'I' from the
124 /// compare instruction to the select instruction and stores this pointer in
125 /// 'PatternLastInst' member of the returned struct.
126 static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
127 InstDesc &Prev, bool HasFunNoNaNAttr);
129 /// Returns true if instruction I has multiple uses in Insts
130 static bool hasMultipleUsesOf(Instruction *I,
131 SmallPtrSetImpl<Instruction *> &Insts,
132 unsigned MaxNumUses);
134 /// Returns true if all uses of the instruction I is within the Set.
135 static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
137 /// Returns a struct describing if the instruction if the instruction is a
138 /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
140 static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
142 /// Returns a struct describing if the instruction is a
143 /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
144 static InstDesc isConditionalRdxPattern(RecurrenceKind Kind, Instruction *I);
146 /// Returns identity corresponding to the RecurrenceKind.
147 static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
149 /// Returns the opcode of binary operation corresponding to the
151 static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
153 /// Returns true if Phi is a reduction of type Kind and adds it to the
154 /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
155 /// non-null, the minimal bit width needed to compute the reduction will be
157 static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
158 bool HasFunNoNaNAttr,
159 RecurrenceDescriptor &RedDes,
160 DemandedBits *DB = nullptr,
161 AssumptionCache *AC = nullptr,
162 DominatorTree *DT = nullptr);
164 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
165 /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
166 /// non-null, the minimal bit width needed to compute the reduction will be
168 static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
169 RecurrenceDescriptor &RedDes,
170 DemandedBits *DB = nullptr,
171 AssumptionCache *AC = nullptr,
172 DominatorTree *DT = nullptr);
174 /// Returns true if Phi is a first-order recurrence. A first-order recurrence
175 /// is a non-reduction recurrence relation in which the value of the
176 /// recurrence in the current loop iteration equals a value defined in the
177 /// previous iteration. \p SinkAfter includes pairs of instructions where the
178 /// first will be rescheduled to appear after the second if/when the loop is
179 /// vectorized. It may be augmented with additional pairs if needed in order
180 /// to handle Phi as a first-order recurrence.
182 isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
183 DenseMap<Instruction *, Instruction *> &SinkAfter,
186 RecurrenceKind getRecurrenceKind() { return Kind; }
188 MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
190 FastMathFlags getFastMathFlags() { return FMF; }
192 TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
194 Instruction *getLoopExitInstr() { return LoopExitInstr; }
196 /// Returns true if the recurrence has unsafe algebra which requires a relaxed
197 /// floating-point model.
198 bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
200 /// Returns first unsafe algebra instruction in the PHI node's use-chain.
201 Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
203 /// Returns true if the recurrence kind is an integer kind.
204 static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
206 /// Returns true if the recurrence kind is a floating point kind.
207 static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
209 /// Returns true if the recurrence kind is an arithmetic kind.
210 static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
212 /// Returns the type of the recurrence. This type can be narrower than the
213 /// actual type of the Phi if the recurrence has been type-promoted.
214 Type *getRecurrenceType() { return RecurrenceType; }
216 /// Returns a reference to the instructions used for type-promoting the
218 SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
220 /// Returns true if all source operands of the recurrence are SExtInsts.
221 bool isSigned() { return IsSigned; }
224 // The starting value of the recurrence.
225 // It does not have to be zero!
226 TrackingVH<Value> StartValue;
227 // The instruction who's value is used outside the loop.
228 Instruction *LoopExitInstr = nullptr;
229 // The kind of the recurrence.
230 RecurrenceKind Kind = RK_NoRecurrence;
231 // The fast-math flags on the recurrent instructions. We propagate these
232 // fast-math flags into the vectorized FP instructions we generate.
234 // If this a min/max recurrence the kind of recurrence.
235 MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
236 // First occurrence of unasfe algebra in the PHI's use-chain.
237 Instruction *UnsafeAlgebraInst = nullptr;
238 // The type of the recurrence.
239 Type *RecurrenceType = nullptr;
240 // True if all source operands of the recurrence are SExtInsts.
241 bool IsSigned = false;
242 // Instructions used for type-promoting the recurrence.
243 SmallPtrSet<Instruction *, 8> CastInsts;
246 /// A struct for saving information about induction variables.
247 class InductionDescriptor {
249 /// This enum represents the kinds of inductions that we support.
251 IK_NoInduction, ///< Not an induction variable.
252 IK_IntInduction, ///< Integer induction variable. Step = C.
253 IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
254 IK_FpInduction ///< Floating point induction variable.
258 /// Default constructor - creates an invalid induction.
259 InductionDescriptor() = default;
261 /// Get the consecutive direction. Returns:
262 /// 0 - unknown or non-consecutive.
263 /// 1 - consecutive and increasing.
264 /// -1 - consecutive and decreasing.
265 int getConsecutiveDirection() const;
267 Value *getStartValue() const { return StartValue; }
268 InductionKind getKind() const { return IK; }
269 const SCEV *getStep() const { return Step; }
270 BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
271 ConstantInt *getConstIntStepValue() const;
273 /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
274 /// induction, the induction descriptor \p D will contain the data describing
275 /// this induction. If by some other means the caller has a better SCEV
276 /// expression for \p Phi than the one returned by the ScalarEvolution
277 /// analysis, it can be passed through \p Expr. If the def-use chain
278 /// associated with the phi includes casts (that we know we can ignore
279 /// under proper runtime checks), they are passed through \p CastsToIgnore.
281 isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
282 InductionDescriptor &D, const SCEV *Expr = nullptr,
283 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
285 /// Returns true if \p Phi is a floating point induction in the loop \p L.
286 /// If \p Phi is an induction, the induction descriptor \p D will contain
287 /// the data describing this induction.
288 static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
289 InductionDescriptor &D);
291 /// Returns true if \p Phi is a loop \p L induction, in the context associated
292 /// with the run-time predicate of PSE. If \p Assume is true, this can add
293 /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
295 /// If \p Phi is an induction, \p D will contain the data describing this
297 static bool isInductionPHI(PHINode *Phi, const Loop *L,
298 PredicatedScalarEvolution &PSE,
299 InductionDescriptor &D, bool Assume = false);
301 /// Returns true if the induction type is FP and the binary operator does
302 /// not have the "fast-math" property. Such operation requires a relaxed FP
304 bool hasUnsafeAlgebra() {
305 return (IK == IK_FpInduction) && InductionBinOp &&
306 !cast<FPMathOperator>(InductionBinOp)->isFast();
309 /// Returns induction operator that does not have "fast-math" property
310 /// and requires FP unsafe mode.
311 Instruction *getUnsafeAlgebraInst() {
312 if (IK != IK_FpInduction)
315 if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
317 return InductionBinOp;
320 /// Returns binary opcode of the induction operator.
321 Instruction::BinaryOps getInductionOpcode() const {
322 return InductionBinOp ? InductionBinOp->getOpcode()
323 : Instruction::BinaryOpsEnd;
326 /// Returns a reference to the type cast instructions in the induction
327 /// update chain, that are redundant when guarded with a runtime
328 /// SCEV overflow check.
329 const SmallVectorImpl<Instruction *> &getCastInsts() const {
330 return RedundantCasts;
334 /// Private constructor - used by \c isInductionPHI.
335 InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
336 BinaryOperator *InductionBinOp = nullptr,
337 SmallVectorImpl<Instruction *> *Casts = nullptr);
340 TrackingVH<Value> StartValue;
342 InductionKind IK = IK_NoInduction;
344 const SCEV *Step = nullptr;
345 // Instruction that advances induction variable.
346 BinaryOperator *InductionBinOp = nullptr;
347 // Instructions used for type-casts of the induction variable,
348 // that are redundant when guarded with a runtime SCEV overflow check.
349 SmallVector<Instruction *, 2> RedundantCasts;
352 } // end namespace llvm
354 #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H