LLVM 17.0.0git
IVDescriptors.h
Go to the documentation of this file.
1//===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This file "describes" induction and recurrence variables.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
14#define LLVM_ANALYSIS_IVDESCRIPTORS_H
15
16#include "llvm/ADT/MapVector.h"
20#include "llvm/IR/ValueHandle.h"
21
22namespace llvm {
23
24class AssumptionCache;
25class DemandedBits;
26class DominatorTree;
27class Instruction;
28class Loop;
29class PredicatedScalarEvolution;
30class ScalarEvolution;
31class SCEV;
32class StoreInst;
33
34/// These are the kinds of recurrences that we support.
35enum class RecurKind {
36 None, ///< Not a recurrence.
37 Add, ///< Sum of integers.
38 Mul, ///< Product of integers.
39 Or, ///< Bitwise or logical OR of integers.
40 And, ///< Bitwise or logical AND of integers.
41 Xor, ///< Bitwise or logical XOR of integers.
42 SMin, ///< Signed integer min implemented in terms of select(cmp()).
43 SMax, ///< Signed integer max implemented in terms of select(cmp()).
44 UMin, ///< Unisgned integer min implemented in terms of select(cmp()).
45 UMax, ///< Unsigned integer max implemented in terms of select(cmp()).
46 FAdd, ///< Sum of floats.
47 FMul, ///< Product of floats.
48 FMin, ///< FP min implemented in terms of select(cmp()).
49 FMax, ///< FP max implemented in terms of select(cmp()).
50 FMulAdd, ///< Fused multiply-add of floats (a * b + c).
51 SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop
52 ///< invariant
53 SelectFCmp ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
54 ///< invariant
55};
56
57/// The RecurrenceDescriptor is used to identify recurrences variables in a
58/// loop. Reduction is a special case of recurrence that has uses of the
59/// recurrence variable outside the loop. The method isReductionPHI identifies
60/// reductions that are basic recurrences.
61///
62/// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
63/// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
64/// array[i]; } is a summation of array elements. Basic recurrences are a
65/// special case of chains of recurrences (CR). See ScalarEvolution for CR
66/// references.
67
68/// This struct holds information about recurrence variables.
70public:
72
74 RecurKind K, FastMathFlags FMF, Instruction *ExactFP,
75 Type *RT, bool Signed, bool Ordered,
77 unsigned MinWidthCastToRecurTy)
78 : IntermediateStore(Store), StartValue(Start), LoopExitInstr(Exit),
79 Kind(K), FMF(FMF), ExactFPMathInst(ExactFP), RecurrenceType(RT),
80 IsSigned(Signed), IsOrdered(Ordered),
81 MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) {
82 CastInsts.insert(CI.begin(), CI.end());
83 }
84
85 /// This POD struct holds information about a potential recurrence operation.
86 class InstDesc {
87 public:
88 InstDesc(bool IsRecur, Instruction *I, Instruction *ExactFP = nullptr)
89 : IsRecurrence(IsRecur), PatternLastInst(I),
90 RecKind(RecurKind::None), ExactFPMathInst(ExactFP) {}
91
92 InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP = nullptr)
93 : IsRecurrence(true), PatternLastInst(I), RecKind(K),
94 ExactFPMathInst(ExactFP) {}
95
96 bool isRecurrence() const { return IsRecurrence; }
97
98 bool needsExactFPMath() const { return ExactFPMathInst != nullptr; }
99
100 Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
101
102 RecurKind getRecKind() const { return RecKind; }
103
104 Instruction *getPatternInst() const { return PatternLastInst; }
105
106 private:
107 // Is this instruction a recurrence candidate.
108 bool IsRecurrence;
109 // The last instruction in a min/max pattern (select of the select(icmp())
110 // pattern), or the current recurrence instruction otherwise.
111 Instruction *PatternLastInst;
112 // If this is a min/max pattern.
113 RecurKind RecKind;
114 // Recurrence does not allow floating-point reassociation.
115 Instruction *ExactFPMathInst;
116 };
117
118 /// Returns a struct describing if the instruction 'I' can be a recurrence
119 /// variable of type 'Kind' for a Loop \p L and reduction PHI \p Phi.
120 /// If the recurrence is a min/max pattern of select(icmp()) this function
121 /// advances the instruction pointer 'I' from the compare instruction to the
122 /// select instruction and stores this pointer in 'PatternLastInst' member of
123 /// the returned struct.
124 static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I,
125 RecurKind Kind, InstDesc &Prev,
126 FastMathFlags FuncFMF);
127
128 /// Returns true if instruction I has multiple uses in Insts
129 static bool hasMultipleUsesOf(Instruction *I,
131 unsigned MaxNumUses);
132
133 /// Returns true if all uses of the instruction I is within the Set.
135
136 /// Returns a struct describing if the instruction is a llvm.(s/u)(min/max),
137 /// llvm.minnum/maxnum or a Select(ICmp(X, Y), X, Y) pair of instructions
138 /// corresponding to a min(X, Y) or max(X, Y), matching the recurrence kind \p
139 /// Kind. \p Prev specifies the description of an already processed select
140 /// instruction, so its corresponding cmp can be matched to it.
141 static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind,
142 const InstDesc &Prev);
143
144 /// Returns a struct describing whether the instruction is either a
145 /// Select(ICmp(A, B), X, Y), or
146 /// Select(FCmp(A, B), X, Y)
147 /// where one of (X, Y) is a loop invariant integer and the other is a PHI
148 /// value. \p Prev specifies the description of an already processed select
149 /// instruction, so its corresponding cmp can be matched to it.
150 static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
151 Instruction *I, InstDesc &Prev);
152
153 /// Returns a struct describing if the instruction is a
154 /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
155 static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I);
156
157 /// Returns identity corresponding to the RecurrenceKind.
159
160 /// Returns the opcode corresponding to the RecurrenceKind.
161 static unsigned getOpcode(RecurKind Kind);
162
163 /// Returns true if Phi is a reduction of type Kind and adds it to the
164 /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
165 /// non-null, the minimal bit width needed to compute the reduction will be
166 /// computed.
167 static bool
168 AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop,
169 FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes,
170 DemandedBits *DB = nullptr, AssumptionCache *AC = nullptr,
171 DominatorTree *DT = nullptr, ScalarEvolution *SE = nullptr);
172
173 /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
174 /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
175 /// non-null, the minimal bit width needed to compute the reduction will be
176 /// computed. If \p SE is non-null, store instructions to loop invariant
177 /// addresses are processed.
178 static bool
179 isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes,
180 DemandedBits *DB = nullptr, AssumptionCache *AC = nullptr,
181 DominatorTree *DT = nullptr, ScalarEvolution *SE = nullptr);
182
183 /// Returns true if Phi is a fixed-order recurrence. A fixed-order recurrence
184 /// is a non-reduction recurrence relation in which the value of the
185 /// recurrence in the current loop iteration equals a value defined in a
186 /// previous iteration (e.g. if the value is defined in the previous
187 /// iteration, we refer to it as first-order recurrence, if it is defined in
188 /// the iteration before the previous, we refer to it as second-order
189 /// recurrence and so on). \p SinkAfter includes pairs of instructions where
190 /// the first will be rescheduled to appear after the second if/when the loop
191 /// is vectorized. It may be augmented with additional pairs if needed in
192 /// order to handle Phi as a first-order recurrence.
193 static bool
194 isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop,
196 DominatorTree *DT);
197
198 RecurKind getRecurrenceKind() const { return Kind; }
199
200 unsigned getOpcode() const { return getOpcode(getRecurrenceKind()); }
201
202 FastMathFlags getFastMathFlags() const { return FMF; }
203
204 TrackingVH<Value> getRecurrenceStartValue() const { return StartValue; }
205
206 Instruction *getLoopExitInstr() const { return LoopExitInstr; }
207
208 /// Returns true if the recurrence has floating-point math that requires
209 /// precise (ordered) operations.
210 bool hasExactFPMath() const { return ExactFPMathInst != nullptr; }
211
212 /// Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
213 Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
214
215 /// Returns true if the recurrence kind is an integer kind.
216 static bool isIntegerRecurrenceKind(RecurKind Kind);
217
218 /// Returns true if the recurrence kind is a floating point kind.
220
221 /// Returns true if the recurrence kind is an integer min/max kind.
223 return Kind == RecurKind::UMin || Kind == RecurKind::UMax ||
224 Kind == RecurKind::SMin || Kind == RecurKind::SMax;
225 }
226
227 /// Returns true if the recurrence kind is a floating-point min/max kind.
229 return Kind == RecurKind::FMin || Kind == RecurKind::FMax;
230 }
231
232 /// Returns true if the recurrence kind is any min/max kind.
235 }
236
237 /// Returns true if the recurrence kind is of the form
238 /// select(cmp(),x,y) where one of (x,y) is loop invariant.
240 return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp;
241 }
242
243 /// Returns the type of the recurrence. This type can be narrower than the
244 /// actual type of the Phi if the recurrence has been type-promoted.
245 Type *getRecurrenceType() const { return RecurrenceType; }
246
247 /// Returns a reference to the instructions used for type-promoting the
248 /// recurrence.
249 const SmallPtrSet<Instruction *, 8> &getCastInsts() const { return CastInsts; }
250
251 /// Returns the minimum width used by the recurrence in bits.
253 return MinWidthCastToRecurrenceType;
254 }
255
256 /// Returns true if all source operands of the recurrence are SExtInsts.
257 bool isSigned() const { return IsSigned; }
258
259 /// Expose an ordered FP reduction to the instance users.
260 bool isOrdered() const { return IsOrdered; }
261
262 /// Attempts to find a chain of operations from Phi to LoopExitInst that can
263 /// be treated as a set of reductions instructions for in-loop reductions.
265 Loop *L) const;
266
267 /// Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
269 return isa<IntrinsicInst>(I) &&
270 cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fmuladd;
271 }
272
273 /// Reductions may store temporary or final result to an invariant address.
274 /// If there is such a store in the loop then, after successfull run of
275 /// AddReductionVar method, this field will be assigned the last met store.
277
278private:
279 // The starting value of the recurrence.
280 // It does not have to be zero!
281 TrackingVH<Value> StartValue;
282 // The instruction who's value is used outside the loop.
283 Instruction *LoopExitInstr = nullptr;
284 // The kind of the recurrence.
286 // The fast-math flags on the recurrent instructions. We propagate these
287 // fast-math flags into the vectorized FP instructions we generate.
288 FastMathFlags FMF;
289 // First instance of non-reassociative floating-point in the PHI's use-chain.
290 Instruction *ExactFPMathInst = nullptr;
291 // The type of the recurrence.
292 Type *RecurrenceType = nullptr;
293 // True if all source operands of the recurrence are SExtInsts.
294 bool IsSigned = false;
295 // True if this recurrence can be treated as an in-order reduction.
296 // Currently only a non-reassociative FAdd can be considered in-order,
297 // if it is also the only FAdd in the PHI's use chain.
298 bool IsOrdered = false;
299 // Instructions used for type-promoting the recurrence.
301 // The minimum width used by the recurrence.
302 unsigned MinWidthCastToRecurrenceType;
303};
304
305/// A struct for saving information about induction variables.
307public:
308 /// This enum represents the kinds of inductions that we support.
310 IK_NoInduction, ///< Not an induction variable.
311 IK_IntInduction, ///< Integer induction variable. Step = C.
312 IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
313 IK_FpInduction ///< Floating point induction variable.
314 };
315
316public:
317 /// Default constructor - creates an invalid induction.
319
320 Value *getStartValue() const { return StartValue; }
321 InductionKind getKind() const { return IK; }
322 const SCEV *getStep() const { return Step; }
323 BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
325
326 /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
327 /// induction, the induction descriptor \p D will contain the data describing
328 /// this induction. If by some other means the caller has a better SCEV
329 /// expression for \p Phi than the one returned by the ScalarEvolution
330 /// analysis, it can be passed through \p Expr. If the def-use chain
331 /// associated with the phi includes casts (that we know we can ignore
332 /// under proper runtime checks), they are passed through \p CastsToIgnore.
333 static bool
334 isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
335 InductionDescriptor &D, const SCEV *Expr = nullptr,
336 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
337
338 /// Returns true if \p Phi is a floating point induction in the loop \p L.
339 /// If \p Phi is an induction, the induction descriptor \p D will contain
340 /// the data describing this induction.
341 static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
343
344 /// Returns true if \p Phi is a loop \p L induction, in the context associated
345 /// with the run-time predicate of PSE. If \p Assume is true, this can add
346 /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
347 /// induction.
348 /// If \p Phi is an induction, \p D will contain the data describing this
349 /// induction.
350 static bool isInductionPHI(PHINode *Phi, const Loop *L,
352 InductionDescriptor &D, bool Assume = false);
353
354 /// Returns floating-point induction operator that does not allow
355 /// reassociation (transforming the induction requires an override of normal
356 /// floating-point rules).
358 if (IK == IK_FpInduction && InductionBinOp &&
359 !InductionBinOp->hasAllowReassoc())
360 return InductionBinOp;
361 return nullptr;
362 }
363
364 /// Returns binary opcode of the induction operator.
366 return InductionBinOp ? InductionBinOp->getOpcode()
367 : Instruction::BinaryOpsEnd;
368 }
369
371 assert(IK == IK_PtrInduction && "Only pointer induction has element type");
372 return ElementType;
373 }
374
375 /// Returns a reference to the type cast instructions in the induction
376 /// update chain, that are redundant when guarded with a runtime
377 /// SCEV overflow check.
379 return RedundantCasts;
380 }
381
382private:
383 /// Private constructor - used by \c isInductionPHI.
384 InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
385 BinaryOperator *InductionBinOp = nullptr,
386 Type *ElementType = nullptr,
387 SmallVectorImpl<Instruction *> *Casts = nullptr);
388
389 /// Start value.
390 TrackingVH<Value> StartValue;
391 /// Induction kind.
393 /// Step value.
394 const SCEV *Step = nullptr;
395 // Instruction that advances induction variable.
396 BinaryOperator *InductionBinOp = nullptr;
397 // Element type for pointer induction variables.
398 // TODO: This can be dropped once support for typed pointers is removed.
399 Type *ElementType = nullptr;
400 // Instructions used for type-casts of the induction variable,
401 // that are redundant when guarded with a runtime SCEV overflow check.
402 SmallVector<Instruction *, 2> RedundantCasts;
403};
404
405} // end namespace llvm
406
407#endif // LLVM_ANALYSIS_IVDESCRIPTORS_H
basic Basic Alias true
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
A cache of @llvm.assume calls within a function.
BinaryOps getOpcode() const
Definition: InstrTypes.h:391
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:21
A struct for saving information about induction variables.
BinaryOperator * getInductionBinOp() const
InductionKind getKind() const
const SCEV * getStep() const
InductionKind
This enum represents the kinds of inductions that we support.
@ IK_NoInduction
Not an induction variable.
@ IK_FpInduction
Floating point induction variable.
@ IK_PtrInduction
Pointer induction var. Step = C / sizeof(elem).
@ IK_IntInduction
Integer induction variable. Step = C.
static bool isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D, const SCEV *Expr=nullptr, SmallVectorImpl< Instruction * > *CastsToIgnore=nullptr)
Returns true if Phi is an induction in the loop L.
static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE, InductionDescriptor &D)
Returns true if Phi is a floating point induction in the loop L.
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
Type * getElementType() const
const SmallVectorImpl< Instruction * > & getCastInsts() const
Returns a reference to the type cast instructions in the induction update chain, that are redundant w...
Value * getStartValue() const
Instruction * getExactFPMathInst()
Returns floating-point induction operator that does not allow reassociation (transforming the inducti...
InductionDescriptor()=default
Default constructor - creates an invalid induction.
ConstantInt * getConstIntStepValue() const
bool hasAllowReassoc() const LLVM_READONLY
Determine whether the allow-reassociation flag is set.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
This POD struct holds information about a potential recurrence operation.
Definition: IVDescriptors.h:86
InstDesc(bool IsRecur, Instruction *I, Instruction *ExactFP=nullptr)
Definition: IVDescriptors.h:88
Instruction * getPatternInst() const
InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP=nullptr)
Definition: IVDescriptors.h:92
Instruction * getExactFPMathInst() const
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:69
static bool isFPMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating-point min/max kind.
Instruction * getExactFPMathInst() const
Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
static bool isFMulAddIntrinsic(Instruction *I)
Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
FastMathFlags getFastMathFlags() const
bool hasExactFPMath() const
Returns true if the recurrence has floating-point math that requires precise (ordered) operations.
Instruction * getLoopExitInstr() const
unsigned getOpcode() const
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction * > &Insts, unsigned MaxNumUses)
Returns true if instruction I has multiple uses in Insts.
static bool isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, MapVector< Instruction *, Instruction * > &SinkAfter, DominatorTree *DT)
Returns true if Phi is a fixed-order recurrence.
static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction in TheLoop.
RecurrenceDescriptor(Value *Start, Instruction *Exit, StoreInst *Store, RecurKind K, FastMathFlags FMF, Instruction *ExactFP, Type *RT, bool Signed, bool Ordered, SmallPtrSetImpl< Instruction * > &CI, unsigned MinWidthCastToRecurTy)
Definition: IVDescriptors.h:73
Type * getRecurrenceType() const
Returns the type of the recurrence.
const SmallPtrSet< Instruction *, 8 > & getCastInsts() const
Returns a reference to the instructions used for type-promoting the recurrence.
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction * > &Set)
Returns true if all uses of the instruction I is within the Set.
unsigned getMinWidthCastToRecurrenceTypeInBits() const
Returns the minimum width used by the recurrence in bits.
TrackingVH< Value > getRecurrenceStartValue() const
SmallVector< Instruction *, 4 > getReductionOpChain(PHINode *Phi, Loop *L) const
Attempts to find a chain of operations from Phi to LoopExitInst that can be treated as a set of reduc...
static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi, Instruction *I, InstDesc &Prev)
Returns a struct describing whether the instruction is either a Select(ICmp(A, B),...
bool isSigned() const
Returns true if all source operands of the recurrence are SExtInsts.
static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I)
Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode),...
RecurKind getRecurrenceKind() const
bool isOrdered() const
Expose an ordered FP reduction to the instance users.
Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const
Returns identity corresponding to the RecurrenceKind.
StoreInst * IntermediateStore
Reductions may store temporary or final result to an invariant address.
static bool isFloatingPointRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating point kind.
static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I, RecurKind Kind, InstDesc &Prev, FastMathFlags FuncFMF)
Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a ...
static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind, const InstDesc &Prev)
Returns a struct describing if the instruction is a llvm.
static bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop, FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes, DemandedBits *DB=nullptr, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.
static bool isIntegerRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer kind.
static bool isIntMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer min/max kind.
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
static bool isSelectCmpRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
This class represents an analyzed expression in the program.
The main scalar evolution driver.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
iterator end() const
Definition: SmallPtrSet.h:408
iterator begin() const
Definition: SmallPtrSet.h:403
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:331
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:35
@ UMin
Unisgned integer min implemented in terms of select(cmp()).
@ Or
Bitwise or logical OR of integers.
@ SelectFCmp
Integer select(fcmp(),x,y) where one of (x,y) is loop invariant.
@ Mul
Product of integers.
@ None
Not a recurrence.
@ Xor
Bitwise or logical XOR of integers.
@ FMax
FP max implemented in terms of select(cmp()).
@ FMulAdd
Fused multiply-add of floats (a * b + c).
@ FMul
Product of floats.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ And
Bitwise or logical AND of integers.
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ FMin
FP min implemented in terms of select(cmp()).
@ SelectICmp
Integer select(icmp(),x,y) where one of (x,y) is loop invariant.
@ Add
Sum of integers.
@ FAdd
Sum of floats.
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
constexpr std::nullopt_t None
Definition: None.h:28