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