Go to the documentation of this file.
13 #ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
14 #define LLVM_ANALYSIS_IVDESCRIPTORS_H
24 class AssumptionCache;
29 class PredicatedScalarEvolution;
30 class ScalarEvolution;
77 unsigned MinWidthCastToRecurTy)
79 Kind(K), FMF(FMF), ExactFPMathInst(ExactFP), RecurrenceType(RT),
80 IsSigned(
Signed), IsOrdered(Ordered),
81 MinWidthCastToRecurrenceType(MinWidthCastToRecurTy) {
82 CastInsts.insert(CI.
begin(), CI.
end());
89 : IsRecurrence(IsRecur), PatternLastInst(
I),
93 : IsRecurrence(
true), PatternLastInst(
I), RecKind(K),
94 ExactFPMathInst(ExactFP) {}
131 unsigned MaxNumUses);
142 const InstDesc &Prev);
253 return MinWidthCastToRecurrenceType;
269 return isa<IntrinsicInst>(
I) &&
270 cast<IntrinsicInst>(
I)->getIntrinsicID() == Intrinsic::fmuladd;
292 Type *RecurrenceType =
nullptr;
294 bool IsSigned =
false;
298 bool IsOrdered =
false;
302 unsigned MinWidthCastToRecurrenceType;
360 return InductionBinOp;
366 return InductionBinOp ? InductionBinOp->
getOpcode()
367 : Instruction::BinaryOpsEnd;
379 return RedundantCasts;
386 Type *ElementType =
nullptr,
394 const SCEV *Step =
nullptr;
399 Type *ElementType =
nullptr;
407 #endif // LLVM_ANALYSIS_IVDESCRIPTORS_H
InductionKind
This enum represents the kinds of inductions that we support.
This is an optimization pass for GlobalISel generic memory operations.
@ Or
Bitwise or logical OR of integers.
Instruction * getExactFPMathInst()
Returns floating-point induction operator that does not allow reassociation (transforming the inducti...
Represents a single loop in the control flow graph.
bool hasExactFPMath() const
Returns true if the recurrence has floating-point math that requires precise (ordered) operations.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static bool isFPMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating-point min/max kind.
Instruction * getPatternInst() const
The main scalar evolution driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Instruction::BinaryOps getInductionOpcode() const
Returns binary opcode of the induction operator.
@ IK_IntInduction
Integer induction variable. Step = C.
The instances of the Type class are immutable: once they are created, they are never changed.
BinaryOperator * getInductionBinOp() const
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.
@ SelectFCmp
Integer select(fcmp(),x,y) where one of (x,y) is loop invariant.
This class implements a map that also provides access to all stored values in a deterministic order.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
InductionKind getKind() const
RecurrenceDescriptor()=default
Convenience struct for specifying and reasoning about fast-math flags.
@ SMin
Signed integer min implemented in terms of select(cmp()).
RecurKind
These are the kinds of recurrences that we support.
static bool isIntMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer min/max kind.
const SmallPtrSet< Instruction *, 8 > & getCastInsts() const
Returns a reference to the instructions used for type-promoting the recurrence.
This is the shared class of boolean and integer constants.
A struct for saving information about induction variables.
unsigned getMinWidthCastToRecurrenceTypeInBits() const
Returns the minimum width used by the recurrence in bits.
@ And
Bitwise or logical AND of integers.
InstDesc(bool IsRecur, Instruction *I, Instruction *ExactFP=nullptr)
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...
@ IK_PtrInduction
Pointer induction var. Step = C / sizeof(elem).
Instruction * getExactFPMathInst() const
static bool isSelectCmpRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
Instruction * getExactFPMathInst() const
Returns 1st non-reassociative FP instruction in the PHI node's use-chain.
Type * getRecurrenceType() const
Returns the type of the recurrence.
const SmallVectorImpl< Instruction * > & getCastInsts() const
Returns a reference to the type cast instructions in the induction update chain, that are redundant w...
static bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl< Instruction * > &Insts, unsigned MaxNumUses)
Returns true if instruction I has multiple uses in Insts.
unsigned getOpcode() const
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),...
BinaryOps getOpcode() const
Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const
Returns identity corresponding to the RecurrenceKind.
RecurKind getRecurrenceKind() const
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.
static bool isFMulAddIntrinsic(Instruction *I)
Returns true if the instruction is a call to the llvm.fmuladd intrinsic.
bool needsExactFPMath() const
@ UMin
Unisgned integer min implemented in terms of select(cmp()).
bool isSigned() const
Returns true if all source operands of the recurrence are SExtInsts.
Value * getStartValue() const
This class represents an analyzed expression in the program.
An instruction for storing to memory.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
InductionDescriptor()=default
Default constructor - creates an invalid induction.
Type * getElementType() const
ConstantInt * getConstIntStepValue() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
@ IK_FpInduction
Floating point induction variable.
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
@ IK_NoInduction
Not an induction variable.
StoreInst * IntermediateStore
Reductions may store temporary or final result to an invariant address.
FastMathFlags getFastMathFlags() const
A cache of @llvm.assume calls within a function.
bool isRecurrence() const
const SCEV * getStep() const
static InstDesc isConditionalRdxPattern(RecurKind Kind, Instruction *I)
Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode),...
@ Mul
Product of integers.
@ FMax
FP max implemented in terms of select(cmp()).
This POD struct holds information about a potential recurrence operation.
TrackingVH< Value > getRecurrenceStartValue() const
RecurKind getRecKind() const
@ FMulAdd
Fused multiply-add of floats (a * b + c).
static bool isFloatingPointRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is a floating point kind.
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.
static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl< Instruction * > &Set)
Returns true if all uses of the instruction I is within the Set.
constexpr std::nullopt_t None
RecurrenceDescriptor(Value *Start, Instruction *Exit, StoreInst *Store, RecurKind K, FastMathFlags FMF, Instruction *ExactFP, Type *RT, bool Signed, bool Ordered, SmallPtrSetImpl< Instruction * > &CI, unsigned MinWidthCastToRecurTy)
bool hasAllowReassoc() const LLVM_READONLY
Determine whether the allow-reassociation flag is set.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
@ SelectICmp
Integer select(icmp(),x,y) where one of (x,y) is loop invariant.
static bool isIntegerRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is an integer kind.
InstDesc(Instruction *I, RecurKind K, Instruction *ExactFP=nullptr)
bool isOrdered() const
Expose an ordered FP reduction to the instance users.
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.
@ FMin
FP min implemented in terms of select(cmp()).
Instruction * getLoopExitInstr() const
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
static bool isFixedOrderRecurrence(PHINode *Phi, Loop *TheLoop, MapVector< Instruction *, Instruction * > &SinkAfter, DominatorTree *DT)
Returns true if Phi is a fixed-order recurrence.
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 ...
static InstDesc isMinMaxPattern(Instruction *I, RecurKind Kind, const InstDesc &Prev)
Returns a struct describing if the instruction is a llvm.
@ SMax
Signed integer max implemented in terms of select(cmp()).
LLVM Value Representation.
@ Xor
Bitwise or logical XOR of integers.