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