LLVM  15.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"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/IR/IntrinsicInst.h"
20 #include "llvm/IR/ValueHandle.h"
21 
22 namespace llvm {
23 
24 class AssumptionCache;
25 class DemandedBits;
26 class DominatorTree;
27 class Instruction;
28 class Loop;
29 class PredicatedScalarEvolution;
30 class ScalarEvolution;
31 class SCEV;
32 class StoreInst;
33 
34 /// These are the kinds of recurrences that we support.
35 enum 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.
70 public:
71  RecurrenceDescriptor() = default;
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 first-order recurrence. A first-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 the
186  /// previous iteration. \p SinkAfter includes pairs of instructions where the
187  /// first will be rescheduled to appear after the second if/when the loop is
188  /// vectorized. It may be augmented with additional pairs if needed in order
189  /// to handle Phi as a first-order recurrence.
190  static bool
191  isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
193  DominatorTree *DT);
194 
195  RecurKind getRecurrenceKind() const { return Kind; }
196 
197  unsigned getOpcode() const { return getOpcode(getRecurrenceKind()); }
198 
199  FastMathFlags getFastMathFlags() const { return FMF; }
200 
201  TrackingVH<Value> getRecurrenceStartValue() const { return StartValue; }
202 
203  Instruction *getLoopExitInstr() const { return LoopExitInstr; }
204 
205  /// Returns true if the recurrence has floating-point math that requires
206  /// precise (ordered) operations.
207  bool hasExactFPMath() const { return ExactFPMathInst != nullptr; }
208 
209  /// Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
210  Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
211 
212  /// Returns true if the recurrence kind is an integer kind.
213  static bool isIntegerRecurrenceKind(RecurKind Kind);
214 
215  /// Returns true if the recurrence kind is a floating point kind.
216  static bool isFloatingPointRecurrenceKind(RecurKind Kind);
217 
218  /// Returns true if the recurrence kind is an arithmetic kind.
219  static bool isArithmeticRecurrenceKind(RecurKind 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.
233  static bool isMinMaxRecurrenceKind(RecurKind 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 
278 private:
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.
285  RecurKind Kind = RecurKind::None;
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.
307 public:
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 
316 public:
317  /// Default constructor - creates an invalid induction.
318  InductionDescriptor() = default;
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 
370  Type *getElementType() const {
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 
382 private:
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
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4637
llvm::InductionDescriptor::InductionKind
InductionKind
This enum represents the kinds of inductions that we support.
Definition: IVDescriptors.h:309
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::RecurKind::Or
@ Or
Bitwise or logical OR of integers.
llvm::RecurKind::FMul
@ FMul
Product of floats.
IntrinsicInst.h
llvm::InductionDescriptor::getExactFPMathInst
Instruction * getExactFPMathInst()
Returns floating-point induction operator that does not allow reassociation (transforming the inducti...
Definition: IVDescriptors.h:357
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::RecurrenceDescriptor::hasExactFPMath
bool hasExactFPMath() const
Returns true if the recurrence has floating-point math that requires precise (ordered) operations.
Definition: IVDescriptors.h:207
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2176
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::RecurrenceDescriptor::isFPMinMaxRecurrenceKind
static bool isFPMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating-point min/max kind.
Definition: IVDescriptors.h:228
llvm::RecurrenceDescriptor::InstDesc::getPatternInst
Instruction * getPatternInst() const
Definition: IVDescriptors.h:104
MapVector.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::InductionDescriptor::getInductionOpcode
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
Definition: IVDescriptors.h:365
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
llvm::InductionDescriptor::IK_IntInduction
@ IK_IntInduction
Integer induction variable. Step = C.
Definition: IVDescriptors.h:311
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::InductionDescriptor::getInductionBinOp
BinaryOperator * getInductionBinOp() const
Definition: IVDescriptors.h:323
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:1302
llvm::RecurKind::SelectFCmp
@ SelectFCmp
Integer select(fcmp(),x,y) where one of (x,y) is loop invariant.
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
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::InductionDescriptor::getKind
InductionKind getKind() const
Definition: IVDescriptors.h:321
llvm::RecurrenceDescriptor::RecurrenceDescriptor
RecurrenceDescriptor()=default
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:21
llvm::RecurKind::SMin
@ SMin
Signed integer min implemented in terms of select(cmp()).
llvm::RecurKind
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:35
llvm::RecurrenceDescriptor::isIntMinMaxRecurrenceKind
static bool isIntMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer min/max kind.
Definition: IVDescriptors.h:222
llvm::RecurrenceDescriptor::getCastInsts
const SmallPtrSet< Instruction *, 8 > & getCastInsts() const
Returns a reference to the instructions used for type-promoting the recurrence.
Definition: IVDescriptors.h:249
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:306
llvm::RecurrenceDescriptor::getMinWidthCastToRecurrenceTypeInBits
unsigned getMinWidthCastToRecurrenceTypeInBits() const
Returns the minimum width used by the recurrence in bits.
Definition: IVDescriptors.h:252
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:88
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:1149
llvm::InductionDescriptor::IK_PtrInduction
@ IK_PtrInduction
Pointer induction var. Step = C / sizeof(elem).
Definition: IVDescriptors.h:312
llvm::RecurrenceDescriptor::InstDesc::getExactFPMathInst
Instruction * getExactFPMathInst() const
Definition: IVDescriptors.h:100
llvm::RecurrenceDescriptor::isSelectCmpRecurrenceKind
static bool isSelectCmpRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
Definition: IVDescriptors.h:239
llvm::RecurrenceDescriptor::getExactFPMathInst
Instruction * getExactFPMathInst() const
Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
Definition: IVDescriptors.h:210
llvm::RecurrenceDescriptor::getRecurrenceType
Type * getRecurrenceType() const
Returns the type of the recurrence.
Definition: IVDescriptors.h:245
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:378
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:825
llvm::RecurrenceDescriptor::getOpcode
unsigned getOpcode() const
Definition: IVDescriptors.h:197
llvm::RecurrenceDescriptor::isSelectCmpPattern
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),...
Definition: IVDescriptors.cpp:646
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:392
llvm::RecurrenceDescriptor::getRecurrenceIdentity
Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const
Returns identity corresponding to the RecurrenceKind.
Definition: IVDescriptors.cpp:1065
llvm::Instruction
Definition: Instruction.h:42
llvm::RecurrenceDescriptor::getRecurrenceKind
RecurKind getRecurrenceKind() const
Definition: IVDescriptors.h:195
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, ScalarEvolution *SE=nullptr)
Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.
Definition: IVDescriptors.cpp:230
llvm::RecurrenceDescriptor::isFMulAddIntrinsic
static bool isFMulAddIntrinsic(Instruction *I)
Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
Definition: IVDescriptors.h:268
llvm::RecurKind::None
@ None
Not a recurrence.
SmallPtrSet.h
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::RecurrenceDescriptor::InstDesc::needsExactFPMath
bool needsExactFPMath() const
Definition: IVDescriptors.h:98
llvm::None
const NoneType None
Definition: None.h:24
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:257
llvm::InductionDescriptor::getStartValue
Value * getStartValue() const
Definition: IVDescriptors.h:320
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::SmallPtrSetImpl::end
iterator end() const
Definition: SmallPtrSet.h:408
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:58
llvm::RecurKind::Add
@ Add
Sum of integers.
llvm::InductionDescriptor::getElementType
Type * getElementType() const
Definition: IVDescriptors.h:370
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::TrackingVH< Value >
llvm::InductionDescriptor::getConstIntStepValue
ConstantInt * getConstIntStepValue() const
Definition: IVDescriptors.cpp:1296
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::InductionDescriptor::IK_FpInduction
@ IK_FpInduction
Floating point induction variable.
Definition: IVDescriptors.h:313
llvm::RecurrenceDescriptor::isArithmeticRecurrenceKind
static bool isArithmeticRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an arithmetic kind.
Definition: IVDescriptors.cpp:66
llvm::RecurKind::UMax
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
llvm::InductionDescriptor::IK_NoInduction
@ IK_NoInduction
Not an induction variable.
Definition: IVDescriptors.h:310
llvm::BinaryOperator
Definition: InstrTypes.h:188
llvm::RecurrenceDescriptor::IntermediateStore
StoreInst * IntermediateStore
Reductions may store temporary or final result to an invariant address.
Definition: IVDescriptors.h:276
llvm::RecurrenceDescriptor::getFastMathFlags
FastMathFlags getFastMathFlags() const
Definition: IVDescriptors.h:199
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::RecurrenceDescriptor::InstDesc::isRecurrence
bool isRecurrence() const
Definition: IVDescriptors.h:96
llvm::InductionDescriptor::getStep
const SCEV * getStep() const
Definition: IVDescriptors.h:322
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:738
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:86
llvm::RecurrenceDescriptor::getRecurrenceStartValue
TrackingVH< Value > getRecurrenceStartValue() const
Definition: IVDescriptors.h:201
llvm::RecurrenceDescriptor::InstDesc::getRecKind
RecurKind getRecKind() const
Definition: IVDescriptors.h:102
llvm::RecurKind::FMulAdd
@ FMulAdd
Fused multiply-add of floats (a * b + c).
llvm::RecurrenceDescriptor::isFloatingPointRecurrenceKind
static bool isFloatingPointRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating point kind.
Definition: IVDescriptors.cpp:62
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:1504
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:34
llvm::RecurrenceDescriptor::RecurrenceDescriptor
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
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:938
llvm::Instruction::hasAllowReassoc
bool hasAllowReassoc() const
Determine whether the allow-reassociation flag is set.
Definition: Instruction.cpp:254
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:786
llvm::RecurrenceDescriptor
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:69
llvm::RecurKind::SelectICmp
@ SelectICmp
Integer select(icmp(),x,y) where one of (x,y) is loop invariant.
llvm::RecurKind::FAdd
@ FAdd
Sum of floats.
SmallVector.h
llvm::PHINode
Definition: Instructions.h:2651
llvm::RecurrenceDescriptor::isIntegerRecurrenceKind
static bool isIntegerRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer kind.
Definition: IVDescriptors.cpp:42
llvm::SmallVectorImpl< Instruction * >
llvm::RecurrenceDescriptor::InstDesc::InstDesc
InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP=nullptr)
Definition: IVDescriptors.h:92
llvm::SmallPtrSetImpl< Instruction * >
llvm::RecurrenceDescriptor::isOrdered
bool isOrdered() const
Expose an ordered FP reduction to the instance users.
Definition: IVDescriptors.h:260
llvm::RecurrenceDescriptor::isReductionPHI
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.
Definition: IVDescriptors.cpp:839
llvm::RecurKind::FMin
@ FMin
FP min implemented in terms of select(cmp()).
llvm::RecurrenceDescriptor::getLoopExitInstr
Instruction * getLoopExitInstr() const
Definition: IVDescriptors.h:203
llvm::RecurrenceDescriptor::isMinMaxRecurrenceKind
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
Definition: IVDescriptors.h:233
llvm::RecurrenceDescriptor::isRecurrenceInstr
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 ...
Definition: IVDescriptors.cpp:775
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:682
llvm::RecurKind::SMax
@ SMax
Signed integer max implemented in terms of select(cmp()).
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::RecurKind::Xor
@ Xor
Bitwise or logical XOR of integers.