Go to the documentation of this file.
30 static inline int sizeOfSCEV(
const SCEV *
S) {
34 FindSCEVSize() =
default;
36 bool follow(
const SCEV *
S) {
42 bool isDone()
const {
return false; }
56 const SCEV *Denominator,
const SCEV **Quotient,
57 const SCEV **Remainder) {
58 assert(Numerator && Denominator &&
"Uninitialized SCEV");
64 if (Numerator == Denominator) {
77 if (Denominator->
isOne()) {
78 *Quotient = Numerator;
84 if (
const SCEVMulExpr *
T = dyn_cast<SCEVMulExpr>(Denominator)) {
86 *Quotient = Numerator;
87 for (
const SCEV *
Op :
T->operands()) {
95 *Remainder = Numerator;
104 *Quotient =
D.Quotient;
105 *Remainder =
D.Remainder;
109 if (
const SCEVConstant *
D = dyn_cast<SCEVConstant>(Denominator)) {
111 APInt DenominatorVal =
D->getAPInt();
115 if (NumeratorBW > DenominatorBW)
116 DenominatorVal = DenominatorVal.
sext(NumeratorBW);
117 else if (NumeratorBW < DenominatorBW)
118 NumeratorVal = NumeratorVal.
sext(DenominatorBW);
122 APInt::sdivrem(NumeratorVal, DenominatorVal, QuotientVal, RemainderVal);
130 const SCEV *StartQ, *StartR, *StepQ, *StepR;
132 return cannotDivide(Numerator);
139 return cannotDivide(Numerator);
152 divide(SE,
Op, Denominator, &Q, &R);
155 if (Ty != Q->
getType() || Ty != R->getType())
156 return cannotDivide(Numerator);
162 if (Qs.size() == 1) {
176 bool FoundDenominatorTerm =
false;
179 if (Ty !=
Op->getType())
180 return cannotDivide(Numerator);
182 if (FoundDenominatorTerm) {
189 divide(SE,
Op, Denominator, &Q, &R);
197 return cannotDivide(Numerator);
199 FoundDenominatorTerm =
true;
203 if (FoundDenominatorTerm) {
212 if (!isa<SCEVUnknown>(Denominator))
213 return cannotDivide(Numerator);
217 RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] = Zero;
220 if (Remainder->
isZero()) {
222 RewriteMap[cast<SCEVUnknown>(Denominator)->getValue()] = One;
231 if (sizeOfSCEV(Diff) > sizeOfSCEV(Numerator))
232 return cannotDivide(Numerator);
233 divide(SE, Diff, Denominator, &Q, &R);
235 return cannotDivide(Numerator);
240 const SCEV *Denominator)
241 : SE(
S), Denominator(Denominator) {
247 cannotDivide(Numerator);
252 void SCEVDivision::cannotDivide(
const SCEV *Numerator) {
254 Remainder = Numerator;
void visitConstant(const SCEVConstant *Numerator)
This is an optimization pass for GlobalISel generic memory operations.
void visitMulExpr(const SCEVMulExpr *Numerator)
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const SCEV * getStart() const
static const SCEV * rewrite(const SCEV *Scev, ScalarEvolution &SE, ValueToSCEVMapTy &Map)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
The main scalar evolution driver.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getBitWidth() const
Return the number of bits in the APInt.
ArrayRef< const SCEV * > operands() const
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
Visit all nodes in the expression tree using worklist traversal.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
This node represents multiplication of some number of SCEVs.
void visitAddExpr(const SCEVAddExpr *Numerator)
This class represents an analyzed expression in the program.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
This class represents a constant integer value.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
const SCEV * getConstant(ConstantInt *V)
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
static void divide(ScalarEvolution &SE, const SCEV *Numerator, const SCEV *Denominator, const SCEV **Quotient, const SCEV **Remainder)
const Loop * getLoop() const
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
This node represents a polynomial recurrence on the trip count of the specified loop.
void visitAddRecExpr(const SCEVAddRecExpr *Numerator)
bool isOne() const
Return true if the expression is a constant one.
APInt sext(unsigned width) const
Sign extend to a new width.
const APInt & getAPInt() const
This node represents an addition of some number of SCEVs.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
Type * getType() const
Return the LLVM type of this SCEV expression.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
bool isZero() const
Return true if the expression is a constant zero.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.