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  : StartValue(Start), LoopExitInstr(Exit), Kind(K), FMF(FMF),
82  ExactFPMathInst(ExactFP), RecurrenceType(RT), IsSigned(Signed),
83  IsOrdered(Ordered) {
84  CastInsts.insert(CI.begin(), CI.end());
85  }
86 
87  /// This POD struct holds information about a potential recurrence operation.
88  class InstDesc {
89  public:
90  InstDesc(bool IsRecur, Instruction *I, Instruction *ExactFP = nullptr)
91  : IsRecurrence(IsRecur), PatternLastInst(I),
92  RecKind(RecurKind::None), ExactFPMathInst(ExactFP) {}
93 
94  InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP = nullptr)
95  : IsRecurrence(true), PatternLastInst(I), RecKind(K),
96  ExactFPMathInst(ExactFP) {}
97 
98  bool isRecurrence() const { return IsRecurrence; }
99 
100  bool needsExactFPMath() const { return ExactFPMathInst != nullptr; }
101 
102  Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
103 
104  RecurKind getRecKind() const { return RecKind; }
105 
106  Instruction *getPatternInst() const { return PatternLastInst; }
107 
108  private:
109  // Is this instruction a recurrence candidate.
110  bool IsRecurrence;
111  // The last instruction in a min/max pattern (select of the select(icmp())
112  // pattern), or the current recurrence instruction otherwise.
113  Instruction *PatternLastInst;
114  // If this is a min/max pattern.
115  RecurKind RecKind;
116  // Recurrence does not allow floating-point reassociation.
117  Instruction *ExactFPMathInst;
118  };
119 
120  /// Returns a struct describing if the instruction 'I' can be a recurrence
121  /// variable of type 'Kind' for a Loop \p L and reduction PHI \p Phi.
122  /// If the recurrence is a min/max pattern of select(icmp()) this function
123  /// advances the instruction pointer 'I' from the compare instruction to the
124  /// select instruction and stores this pointer in 'PatternLastInst' member of
125  /// the returned struct.
126  static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I,
127  RecurKind Kind, InstDesc &Prev,
128  FastMathFlags FuncFMF);
129 
130  /// Returns true if instruction I has multiple uses in Insts
131  static bool hasMultipleUsesOf(Instruction *I,
133  unsigned MaxNumUses);
134 
135  /// Returns true if all uses of the instruction I is within the Set.
137 
138  /// Returns a struct describing if the instruction is a llvm.(s/u)(min/max),
139  /// llvm.minnum/maxnum or a Select(ICmp(X, Y), X, Y) pair of instructions
140  /// corresponding to a min(X, Y) or max(X, Y), matching the recurrence kind \p
141  /// Kind. \p Prev specifies the description of an already processed select
142  /// instruction, so its corresponding cmp can be matched to it.
143  static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind,
144  const InstDesc &Prev);
145 
146  /// Returns a struct describing whether the instruction is either a
147  /// Select(ICmp(A, B), X, Y), or
148  /// Select(FCmp(A, B), X, Y)
149  /// where one of (X, Y) is a loop invariant integer and the other is a PHI
150  /// value. \p Prev specifies the description of an already processed select
151  /// instruction, so its corresponding cmp can be matched to it.
152  static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi,
153  Instruction *I, InstDesc &Prev);
154 
155  /// Returns a struct describing if the instruction is a
156  /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.
157  static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I);
158 
159  /// Returns identity corresponding to the RecurrenceKind.
161 
162  /// Returns the opcode corresponding to the RecurrenceKind.
163  static unsigned getOpcode(RecurKind Kind);
164 
165  /// Returns true if Phi is a reduction of type Kind and adds it to the
166  /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
167  /// non-null, the minimal bit width needed to compute the reduction will be
168  /// computed.
169  static bool AddReductionVar(PHINode *Phi, RecurKind Kind, Loop *TheLoop,
170  FastMathFlags FuncFMF,
171  RecurrenceDescriptor &RedDes,
172  DemandedBits *DB = nullptr,
173  AssumptionCache *AC = nullptr,
174  DominatorTree *DT = nullptr);
175 
176  /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
177  /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
178  /// non-null, the minimal bit width needed to compute the reduction will be
179  /// computed.
180  static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
181  RecurrenceDescriptor &RedDes,
182  DemandedBits *DB = nullptr,
183  AssumptionCache *AC = nullptr,
184  DominatorTree *DT = nullptr);
185 
186  /// Returns true if Phi is a first-order recurrence. A first-order recurrence
187  /// is a non-reduction recurrence relation in which the value of the
188  /// recurrence in the current loop iteration equals a value defined in the
189  /// previous iteration. \p SinkAfter includes pairs of instructions where the
190  /// first will be rescheduled to appear after the second if/when the loop is
191  /// vectorized. It may be augmented with additional pairs if needed in order
192  /// to handle Phi as a first-order recurrence.
193  static bool
194  isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
196  DominatorTree *DT);
197 
198  RecurKind getRecurrenceKind() const { return Kind; }
199 
200  unsigned getOpcode() const { return getOpcode(getRecurrenceKind()); }
201 
202  FastMathFlags getFastMathFlags() const { return FMF; }
203 
204  TrackingVH<Value> getRecurrenceStartValue() const { return StartValue; }
205 
206  Instruction *getLoopExitInstr() const { return LoopExitInstr; }
207 
208  /// Returns true if the recurrence has floating-point math that requires
209  /// precise (ordered) operations.
210  bool hasExactFPMath() const { return ExactFPMathInst != nullptr; }
211 
212  /// Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
213  Instruction *getExactFPMathInst() const { return ExactFPMathInst; }
214 
215  /// Returns true if the recurrence kind is an integer kind.
216  static bool isIntegerRecurrenceKind(RecurKind Kind);
217 
218  /// Returns true if the recurrence kind is a floating point kind.
219  static bool isFloatingPointRecurrenceKind(RecurKind Kind);
220 
221  /// Returns true if the recurrence kind is an arithmetic kind.
222  static bool isArithmeticRecurrenceKind(RecurKind Kind);
223 
224  /// Returns true if the recurrence kind is an integer min/max kind.
226  return Kind == RecurKind::UMin || Kind == RecurKind::UMax ||
227  Kind == RecurKind::SMin || Kind == RecurKind::SMax;
228  }
229 
230  /// Returns true if the recurrence kind is a floating-point min/max kind.
232  return Kind == RecurKind::FMin || Kind == RecurKind::FMax;
233  }
234 
235  /// Returns true if the recurrence kind is any min/max kind.
236  static bool isMinMaxRecurrenceKind(RecurKind Kind) {
238  }
239 
240  /// Returns true if the recurrence kind is of the form
241  /// select(cmp(),x,y) where one of (x,y) is loop invariant.
243  return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp;
244  }
245 
246  /// Returns the type of the recurrence. This type can be narrower than the
247  /// actual type of the Phi if the recurrence has been type-promoted.
248  Type *getRecurrenceType() const { return RecurrenceType; }
249 
250  /// Returns a reference to the instructions used for type-promoting the
251  /// recurrence.
252  const SmallPtrSet<Instruction *, 8> &getCastInsts() const { return CastInsts; }
253 
254  /// Returns true if all source operands of the recurrence are SExtInsts.
255  bool isSigned() const { return IsSigned; }
256 
257  /// Expose an ordered FP reduction to the instance users.
258  bool isOrdered() const { return IsOrdered; }
259 
260  /// Attempts to find a chain of operations from Phi to LoopExitInst that can
261  /// be treated as a set of reductions instructions for in-loop reductions.
263  Loop *L) const;
264 
265  /// Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
267  return isa<IntrinsicInst>(I) &&
268  cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fmuladd;
269  }
270 
271 private:
272  // The starting value of the recurrence.
273  // It does not have to be zero!
274  TrackingVH<Value> StartValue;
275  // The instruction who's value is used outside the loop.
276  Instruction *LoopExitInstr = nullptr;
277  // The kind of the recurrence.
278  RecurKind Kind = RecurKind::None;
279  // The fast-math flags on the recurrent instructions. We propagate these
280  // fast-math flags into the vectorized FP instructions we generate.
281  FastMathFlags FMF;
282  // First instance of non-reassociative floating-point in the PHI's use-chain.
283  Instruction *ExactFPMathInst = nullptr;
284  // The type of the recurrence.
285  Type *RecurrenceType = nullptr;
286  // True if all source operands of the recurrence are SExtInsts.
287  bool IsSigned = false;
288  // True if this recurrence can be treated as an in-order reduction.
289  // Currently only a non-reassociative FAdd can be considered in-order,
290  // if it is also the only FAdd in the PHI's use chain.
291  bool IsOrdered = false;
292  // Instructions used for type-promoting the recurrence.
294 };
295 
296 /// A struct for saving information about induction variables.
298 public:
299  /// This enum represents the kinds of inductions that we support.
301  IK_NoInduction, ///< Not an induction variable.
302  IK_IntInduction, ///< Integer induction variable. Step = C.
303  IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
304  IK_FpInduction ///< Floating point induction variable.
305  };
306 
307 public:
308  /// Default constructor - creates an invalid induction.
309  InductionDescriptor() = default;
310 
311  Value *getStartValue() const { return StartValue; }
312  InductionKind getKind() const { return IK; }
313  const SCEV *getStep() const { return Step; }
314  BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
316 
317  /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
318  /// induction, the induction descriptor \p D will contain the data describing
319  /// this induction. If by some other means the caller has a better SCEV
320  /// expression for \p Phi than the one returned by the ScalarEvolution
321  /// analysis, it can be passed through \p Expr. If the def-use chain
322  /// associated with the phi includes casts (that we know we can ignore
323  /// under proper runtime checks), they are passed through \p CastsToIgnore.
324  static bool
325  isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
326  InductionDescriptor &D, const SCEV *Expr = nullptr,
327  SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
328 
329  /// Returns true if \p Phi is a floating point induction in the loop \p L.
330  /// If \p Phi is an induction, the induction descriptor \p D will contain
331  /// the data describing this induction.
332  static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
334 
335  /// Returns true if \p Phi is a loop \p L induction, in the context associated
336  /// with the run-time predicate of PSE. If \p Assume is true, this can add
337  /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
338  /// induction.
339  /// If \p Phi is an induction, \p D will contain the data describing this
340  /// induction.
341  static bool isInductionPHI(PHINode *Phi, const Loop *L,
343  InductionDescriptor &D, bool Assume = false);
344 
345  /// Returns floating-point induction operator that does not allow
346  /// reassociation (transforming the induction requires an override of normal
347  /// floating-point rules).
349  if (IK == IK_FpInduction && InductionBinOp &&
350  !InductionBinOp->hasAllowReassoc())
351  return InductionBinOp;
352  return nullptr;
353  }
354 
355  /// Returns binary opcode of the induction operator.
357  return InductionBinOp ? InductionBinOp->getOpcode()
358  : Instruction::BinaryOpsEnd;
359  }
360 
361  Type *getElementType() const {
362  assert(IK == IK_PtrInduction && "Only pointer induction has element type");
363  return ElementType;
364  }
365 
366  /// Returns a reference to the type cast instructions in the induction
367  /// update chain, that are redundant when guarded with a runtime
368  /// SCEV overflow check.
370  return RedundantCasts;
371  }
372 
373 private:
374  /// Private constructor - used by \c isInductionPHI.
375  InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
376  BinaryOperator *InductionBinOp = nullptr,
377  Type *ElementType = nullptr,
378  SmallVectorImpl<Instruction *> *Casts = nullptr);
379 
380  /// Start value.
381  TrackingVH<Value> StartValue;
382  /// Induction kind.
384  /// Step value.
385  const SCEV *Step = nullptr;
386  // Instruction that advances induction variable.
387  BinaryOperator *InductionBinOp = nullptr;
388  // Element type for pointer induction variables.
389  // TODO: This can be dropped once support for typed pointers is removed.
390  Type *ElementType = nullptr;
391  // Instructions used for type-casts of the induction variable,
392  // that are redundant when guarded with a runtime SCEV overflow check.
393  SmallVector<Instruction *, 2> RedundantCasts;
394 };
395 
396 } // end namespace llvm
397 
398 #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4631
llvm::InductionDescriptor::InductionKind
InductionKind
This enum represents the kinds of inductions that we support.
Definition: IVDescriptors.h:300
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:748
IntrinsicInst.h
llvm::InductionDescriptor::getExactFPMathInst
Instruction * getExactFPMathInst()
Returns floating-point induction operator that does not allow reassociation (transforming the inducti...
Definition: IVDescriptors.h:348
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:210
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:2154
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:231
llvm::RecurrenceDescriptor::InstDesc::getPatternInst
Instruction * getPatternInst() const
Definition: IVDescriptors.h:106
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:356
llvm::InductionDescriptor::IK_IntInduction
@ IK_IntInduction
Integer induction variable. Step = C.
Definition: IVDescriptors.h:302
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:314
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:1143
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:312
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:225
llvm::RecurrenceDescriptor::getCastInsts
const SmallPtrSet< Instruction *, 8 > & getCastInsts() const
Returns a reference to the instructions used for type-promoting the recurrence.
Definition: IVDescriptors.h:252
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:297
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:90
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:1019
llvm::InductionDescriptor::IK_PtrInduction
@ IK_PtrInduction
Pointer induction var. Step = C / sizeof(elem).
Definition: IVDescriptors.h:303
llvm::RecurrenceDescriptor::InstDesc::getExactFPMathInst
Instruction * getExactFPMathInst() const
Definition: IVDescriptors.h:102
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:242
InstrTypes.h
llvm::RecurrenceDescriptor::getExactFPMathInst
Instruction * getExactFPMathInst() const
Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
Definition: IVDescriptors.h:213
llvm::RecurrenceDescriptor::getRecurrenceType
Type * getRecurrenceType() const
Returns the type of the recurrence.
Definition: IVDescriptors.h:248
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:369
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:734
llvm::RecurrenceDescriptor::getOpcode
unsigned getOpcode() const
Definition: IVDescriptors.h:200
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:555
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:394
llvm::Instruction
Definition: Instruction.h:45
llvm::RecurrenceDescriptor::getRecurrenceKind
RecurKind getRecurrenceKind() const
Definition: IVDescriptors.h:198
llvm::RecurrenceDescriptor::isFMulAddIntrinsic
static bool isFMulAddIntrinsic(Instruction *I)
Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
Definition: IVDescriptors.h:266
llvm::RecurKind::None
@ None
Not a recurrence.
SmallPtrSet.h
llvm::RecurrenceDescriptor::getRecurrenceIdentity
Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF)
Returns identity corresponding to the RecurrenceKind.
Definition: IVDescriptors.cpp:935
llvm::RecurrenceDescriptor::InstDesc::needsExactFPMath
bool needsExactFPMath() const
Definition: IVDescriptors.h:100
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:255
llvm::InductionDescriptor::getStartValue
Value * getStartValue() const
Definition: IVDescriptors.h:311
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:59
llvm::RecurKind::Add
@ Add
Sum of integers.
llvm::InductionDescriptor::getElementType
Type * getElementType() const
Definition: IVDescriptors.h:361
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
llvm::TrackingVH< Value >
llvm::InductionDescriptor::getConstIntStepValue
ConstantInt * getConstIntStepValue() const
Definition: IVDescriptors.cpp:1137
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::InductionDescriptor::IK_FpInduction
@ IK_FpInduction
Floating point induction variable.
Definition: IVDescriptors.h:304
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:301
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: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:228
llvm::BinaryOperator
Definition: InstrTypes.h:190
llvm::RecurrenceDescriptor::getFastMathFlags
FastMathFlags getFastMathFlags() const
Definition: IVDescriptors.h:202
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:98
llvm::InductionDescriptor::getStep
const SCEV * getStep() const
Definition: IVDescriptors.h:313
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:647
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:88
llvm::RecurrenceDescriptor::getRecurrenceStartValue
TrackingVH< Value > getRecurrenceStartValue() const
Definition: IVDescriptors.h:204
llvm::RecurrenceDescriptor::InstDesc::getRecKind
RecurKind getRecKind() const
Definition: IVDescriptors.h:104
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:1345
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:833
llvm::Instruction::hasAllowReassoc
bool hasAllowReassoc() const
Determine whether the allow-reassociation flag is set.
Definition: Instruction.cpp:251
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:2648
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:94
llvm::SmallPtrSetImpl< Instruction * >
llvm::RecurrenceDescriptor::isOrdered
bool isOrdered() const
Expose an ordered FP reduction to the instance users.
Definition: IVDescriptors.h:258
llvm::RecurKind::FMin
@ FMin
FP min implemented in terms of select(cmp()).
llvm::RecurrenceDescriptor::getLoopExitInstr
Instruction * getLoopExitInstr() const
Definition: IVDescriptors.h:206
llvm::RecurrenceDescriptor::isMinMaxRecurrenceKind
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
Definition: IVDescriptors.h:236
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1883
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:684
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:591
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.