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/IntrinsicInst.h"
24 #include "llvm/IR/Operator.h"
25 #include "llvm/IR/ValueHandle.h"
26 #include "llvm/Support/Casting.h"
27 
28 namespace llvm {
29 
30 class DemandedBits;
31 class AssumptionCache;
32 class Loop;
33 class PredicatedScalarEvolution;
34 class ScalarEvolution;
35 class SCEV;
36 class DominatorTree;
37 
38 /// These are the kinds of recurrences that we support.
39 enum class RecurKind {
40  None, ///< Not a recurrence.
41  Add, ///< Sum of integers.
42  Mul, ///< Product of integers.
43  Or, ///< Bitwise or logical OR of integers.
44  And, ///< Bitwise or logical AND of integers.
45  Xor, ///< Bitwise or logical XOR of integers.
46  SMin, ///< Signed integer min implemented in terms of select(cmp()).
47  SMax, ///< Signed integer max implemented in terms of select(cmp()).
48  UMin, ///< Unisgned integer min implemented in terms of select(cmp()).
49  UMax, ///< Unsigned integer max implemented in terms of select(cmp()).
50  FAdd, ///< Sum of floats.
51  FMul, ///< Product of floats.
52  FMin, ///< FP min implemented in terms of select(cmp()).
53  FMax, ///< FP max implemented in terms of select(cmp()).
54  FMulAdd, ///< Fused multiply-add of floats (a * b + c).
55  SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop
56  ///< invariant
57  SelectFCmp ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
58  ///< invariant
59 };
60 
61 /// The RecurrenceDescriptor is used to identify recurrences variables in a
62 /// loop. Reduction is a special case of recurrence that has uses of the
63 /// recurrence variable outside the loop. The method isReductionPHI identifies
64 /// reductions that are basic recurrences.
65 ///
66 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
67 /// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
68 /// array[i]; } is a summation of array elements. Basic recurrences are a
69 /// special case of chains of recurrences (CR). See ScalarEvolution for CR
70 /// references.
71 
72 /// This struct holds information about recurrence variables.
74 public:
75  RecurrenceDescriptor() = default;
76 
78  FastMathFlags FMF, Instruction *ExactFP, Type *RT,
79  bool Signed, bool Ordered,
81  unsigned MinWidthCastToRecurTy)
82  : StartValue(Start), LoopExitInstr(Exit), Kind(K), FMF(FMF),
83  ExactFPMathInst(ExactFP), RecurrenceType(RT), IsSigned(Signed),
84  IsOrdered(Ordered),
85  MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) {
86  CastInsts.insert(CI.begin(), CI.end());
87  }
88 
89  /// This POD struct holds information about a potential recurrence operation.
90  class InstDesc {
91  public:
92  InstDesc(bool IsRecur, Instruction *I, Instruction *ExactFP = nullptr)
93  : IsRecurrence(IsRecur), PatternLastInst(I),
94  RecKind(RecurKind::None), ExactFPMathInst(ExactFP) {}
95 
96  InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP = nullptr)
97  : IsRecurrence(true), PatternLastInst(I), RecKind(K),
98  ExactFPMathInst(ExactFP) {}
99 
100  bool isRecurrence() const { return IsRecurrence; }
101 
102  bool needsExactFPMath() const { return ExactFPMathInst != nullptr; }
103 
104  Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
105 
106  RecurKind getRecKind() const { return RecKind; }
107 
108  Instruction *getPatternInst() const { return PatternLastInst; }
109 
110  private:
111  // Is this instruction a recurrence candidate.
112  bool IsRecurrence;
113  // The last instruction in a min/max pattern (select of the select(icmp())
114  // pattern), or the current recurrence instruction otherwise.
115  Instruction *PatternLastInst;
116  // If this is a min/max pattern.
117  RecurKind RecKind;
118  // Recurrence does not allow floating-point reassociation.
119  Instruction *ExactFPMathInst;
120  };
121 
122  /// Returns a struct describing if the instruction 'I' can be a recurrence
123  /// variable of type 'Kind' for a Loop \p L and reduction PHI \p Phi.
124  /// If the recurrence is a min/max pattern of select(icmp()) this function
125  /// advances the instruction pointer 'I' from the compare instruction to the
126  /// select instruction and stores this pointer in 'PatternLastInst' member of
127  /// the returned struct.
128  static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I,
129  RecurKind Kind, InstDesc &Prev,
130  FastMathFlags FuncFMF);
131 
132  /// Returns true if instruction I has multiple uses in Insts
133  static bool hasMultipleUsesOf(Instruction *I,
135  unsigned MaxNumUses);
136 
137  /// Returns true if all uses of the instruction I is within the Set.
139 
140  /// Returns a struct describing if the instruction is a llvm.(s/u)(min/max),
141  /// llvm.minnum/maxnum or a Select(ICmp(X, Y), X, Y) pair of instructions
142  /// corresponding to a min(X, Y) or max(X, Y), matching the recurrence kind \p
143  /// Kind. \p Prev specifies the description of an already processed select
144  /// instruction, so its corresponding cmp can be matched to it.
145  static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind,
146  const InstDesc &Prev);
147 
148  /// Returns a struct describing whether the instruction is either a
149  /// Select(ICmp(A, B), X, Y), or
150  /// Select(FCmp(A, B), X, Y)
151  /// where one of (X, Y) is a loop invariant integer and the other is a PHI
152  /// value. \p Prev specifies the description of an already processed select
153  /// instruction, so its corresponding cmp can be matched to it.
154  static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
155  Instruction *I, InstDesc &Prev);
156 
157  /// Returns a struct describing if the instruction is a
158  /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
159  static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I);
160 
161  /// Returns identity corresponding to the RecurrenceKind.
163 
164  /// Returns the opcode corresponding to the RecurrenceKind.
165  static unsigned getOpcode(RecurKind Kind);
166 
167  /// Returns true if Phi is a reduction of type Kind and adds it to the
168  /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
169  /// non-null, the minimal bit width needed to compute the reduction will be
170  /// computed.
171  static bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop,
172  FastMathFlags FuncFMF,
173  RecurrenceDescriptor &RedDes,
174  DemandedBits *DB = nullptr,
175  AssumptionCache *AC = nullptr,
176  DominatorTree *DT = nullptr);
177 
178  /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
179  /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
180  /// non-null, the minimal bit width needed to compute the reduction will be
181  /// computed.
182  static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
183  RecurrenceDescriptor &RedDes,
184  DemandedBits *DB = nullptr,
185  AssumptionCache *AC = nullptr,
186  DominatorTree *DT = nullptr);
187 
188  /// Returns true if Phi is a first-order recurrence. A first-order recurrence
189  /// is a non-reduction recurrence relation in which the value of the
190  /// recurrence in the current loop iteration equals a value defined in the
191  /// previous iteration. \p SinkAfter includes pairs of instructions where the
192  /// first will be rescheduled to appear after the second if/when the loop is
193  /// vectorized. It may be augmented with additional pairs if needed in order
194  /// to handle Phi as a first-order recurrence.
195  static bool
196  isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
198  DominatorTree *DT);
199 
200  RecurKind getRecurrenceKind() const { return Kind; }
201 
202  unsigned getOpcode() const { return getOpcode(getRecurrenceKind()); }
203 
204  FastMathFlags getFastMathFlags() const { return FMF; }
205 
206  TrackingVH<Value> getRecurrenceStartValue() const { return StartValue; }
207 
208  Instruction *getLoopExitInstr() const { return LoopExitInstr; }
209 
210  /// Returns true if the recurrence has floating-point math that requires
211  /// precise (ordered) operations.
212  bool hasExactFPMath() const { return ExactFPMathInst != nullptr; }
213 
214  /// Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
215  Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
216 
217  /// Returns true if the recurrence kind is an integer kind.
218  static bool isIntegerRecurrenceKind(RecurKind Kind);
219 
220  /// Returns true if the recurrence kind is a floating point kind.
221  static bool isFloatingPointRecurrenceKind(RecurKind Kind);
222 
223  /// Returns true if the recurrence kind is an arithmetic kind.
224  static bool isArithmeticRecurrenceKind(RecurKind Kind);
225 
226  /// Returns true if the recurrence kind is an integer min/max kind.
228  return Kind == RecurKind::UMin || Kind == RecurKind::UMax ||
229  Kind == RecurKind::SMin || Kind == RecurKind::SMax;
230  }
231 
232  /// Returns true if the recurrence kind is a floating-point min/max kind.
234  return Kind == RecurKind::FMin || Kind == RecurKind::FMax;
235  }
236 
237  /// Returns true if the recurrence kind is any min/max kind.
238  static bool isMinMaxRecurrenceKind(RecurKind Kind) {
240  }
241 
242  /// Returns true if the recurrence kind is of the form
243  /// select(cmp(),x,y) where one of (x,y) is loop invariant.
245  return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp;
246  }
247 
248  /// Returns the type of the recurrence. This type can be narrower than the
249  /// actual type of the Phi if the recurrence has been type-promoted.
250  Type *getRecurrenceType() const { return RecurrenceType; }
251 
252  /// Returns a reference to the instructions used for type-promoting the
253  /// recurrence.
254  const SmallPtrSet<Instruction *, 8> &getCastInsts() const { return CastInsts; }
255 
256  /// Returns the minimum width used by the recurrence in bits.
258  return MinWidthCastToRecurrenceType;
259  }
260 
261  /// Returns true if all source operands of the recurrence are SExtInsts.
262  bool isSigned() const { return IsSigned; }
263 
264  /// Expose an ordered FP reduction to the instance users.
265  bool isOrdered() const { return IsOrdered; }
266 
267  /// Attempts to find a chain of operations from Phi to LoopExitInst that can
268  /// be treated as a set of reductions instructions for in-loop reductions.
270  Loop *L) const;
271 
272  /// Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
274  return isa<IntrinsicInst>(I) &&
275  cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fmuladd;
276  }
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:4644
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: 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:765
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:530
llvm::RecurrenceDescriptor::hasExactFPMath
bool hasExactFPMath() const
Returns true if the recurrence has floating-point math that requires precise (ordered) operations.
Definition: IVDescriptors.h:212
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:2170
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1177
llvm::RecurrenceDescriptor::isFPMinMaxRecurrenceKind
static bool isFPMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating-point min/max kind.
Definition: IVDescriptors.h:233
llvm::RecurrenceDescriptor::InstDesc::getPatternInst
Instruction * getPatternInst() const
Definition: IVDescriptors.h:108
MapVector.h
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
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: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
DenseMap.h
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:1160
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:449
Operator.h
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: Operator.h:165
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:39
llvm::RecurrenceDescriptor::isIntMinMaxRecurrenceKind
static bool isIntMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer min/max kind.
Definition: IVDescriptors.h:227
llvm::RecurrenceDescriptor::getCastInsts
const SmallPtrSet< Instruction *, 8 > & getCastInsts() const
Returns a reference to the instructions used for type-promoting the recurrence.
Definition: IVDescriptors.h:254
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:306
llvm::RecurrenceDescriptor::getMinWidthCastToRecurrenceTypeInBits
unsigned getMinWidthCastToRecurrenceTypeInBits() const
Returns the minimum width used by the recurrence in bits.
Definition: IVDescriptors.h:257
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:92
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:1036
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:104
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:244
InstrTypes.h
llvm::RecurrenceDescriptor::getExactFPMathInst
Instruction * getExactFPMathInst() const
Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
Definition: IVDescriptors.h:215
llvm::RecurrenceDescriptor::getRecurrenceType
Type * getRecurrenceType() const
Returns the type of the recurrence.
Definition: IVDescriptors.h:250
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:751
llvm::RecurrenceDescriptor::getOpcode
unsigned getOpcode() const
Definition: IVDescriptors.h:202
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:572
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:394
llvm::RecurrenceDescriptor::getRecurrenceIdentity
Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const
Returns identity corresponding to the RecurrenceKind.
Definition: IVDescriptors.cpp:952
llvm::Instruction
Definition: Instruction.h:45
llvm::RecurrenceDescriptor::getRecurrenceKind
RecurKind getRecurrenceKind() const
Definition: IVDescriptors.h:200
llvm::RecurrenceDescriptor::isFMulAddIntrinsic
static bool isFMulAddIntrinsic(Instruction *I)
Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
Definition: IVDescriptors.h:273
llvm::RecurKind::None
@ None
Not a recurrence.
SmallPtrSet.h
llvm::RecurrenceDescriptor::InstDesc::needsExactFPMath
bool needsExactFPMath() const
Definition: IVDescriptors.h:102
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:262
llvm::InductionDescriptor::getStartValue
Value * getStartValue() const
Definition: IVDescriptors.h:320
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
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: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:402
llvm::TrackingVH< Value >
llvm::InductionDescriptor::getConstIntStepValue
ConstantInt * getConstIntStepValue() const
Definition: IVDescriptors.cpp:1154
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:76
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::RecurrenceDescriptor::RecurrenceDescriptor
RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurKind K, FastMathFlags FMF, Instruction *ExactFP, Type *RT, bool Signed, bool Ordered, SmallPtrSetImpl< Instruction * > &CI, unsigned MinWidthCastToRecurTy)
Definition: IVDescriptors.h:77
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:240
llvm::BinaryOperator
Definition: InstrTypes.h:190
llvm::RecurrenceDescriptor::getFastMathFlags
FastMathFlags getFastMathFlags() const
Definition: IVDescriptors.h:204
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:100
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:664
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:90
llvm::RecurrenceDescriptor::getRecurrenceStartValue
TrackingVH< Value > getRecurrenceStartValue() const
Definition: IVDescriptors.h:206
llvm::RecurrenceDescriptor::InstDesc::getRecKind
RecurKind getRecKind() const
Definition: IVDescriptors.h:106
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:72
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:1362
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:850
llvm::Instruction::hasAllowReassoc
bool hasAllowReassoc() const
Determine whether the allow-reassociation flag is set.
Definition: Instruction.cpp:255
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:789
llvm::RecurrenceDescriptor
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:73
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:2657
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:96
llvm::SmallPtrSetImpl< Instruction * >
llvm::RecurrenceDescriptor::isOrdered
bool isOrdered() const
Expose an ordered FP reduction to the instance users.
Definition: IVDescriptors.h:265
llvm::RecurKind::FMin
@ FMin
FP min implemented in terms of select(cmp()).
llvm::RecurrenceDescriptor::getLoopExitInstr
Instruction * getLoopExitInstr() const
Definition: IVDescriptors.h:208
llvm::RecurrenceDescriptor::isMinMaxRecurrenceKind
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
Definition: IVDescriptors.h:238
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:701
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:608
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.