LLVM 20.0.0git
|
This node represents a polynomial recurrence on the trip count of the specified loop. More...
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Public Member Functions | |
Type * | getType () const |
const SCEV * | getStart () const |
const Loop * | getLoop () const |
const SCEV * | getStepRecurrence (ScalarEvolution &SE) const |
Constructs and returns the recurrence indicating how much this expression steps by. | |
bool | isAffine () const |
Return true if this represents an expression A + B*x where A and B are loop invariant values. | |
bool | isQuadratic () const |
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant values. | |
void | setNoWrapFlags (NoWrapFlags Flags) |
Set flags for a recurrence without clearing any previously set flags. | |
const SCEV * | evaluateAtIteration (const SCEV *It, ScalarEvolution &SE) const |
Return the value of this chain of recurrences at the specified iteration number. | |
const SCEV * | getNumIterationsInRange (const ConstantRange &Range, ScalarEvolution &SE) const |
Return the number of iterations of this loop that produce values in the specified constant range. | |
const SCEVAddRecExpr * | getPostIncExpr (ScalarEvolution &SE) const |
Return an expression representing the value of this expression one iteration of the loop ahead. | |
Public Member Functions inherited from llvm::SCEVNAryExpr | |
size_t | getNumOperands () const |
const SCEV * | getOperand (unsigned i) const |
ArrayRef< const SCEV * > | operands () const |
NoWrapFlags | getNoWrapFlags (NoWrapFlags Mask=NoWrapMask) const |
bool | hasNoUnsignedWrap () const |
bool | hasNoSignedWrap () const |
bool | hasNoSelfWrap () const |
Public Member Functions inherited from llvm::SCEV | |
SCEV (const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize) | |
SCEV (const SCEV &)=delete | |
SCEV & | operator= (const SCEV &)=delete |
SCEVTypes | getSCEVType () const |
Type * | getType () const |
Return the LLVM type of this SCEV expression. | |
ArrayRef< const SCEV * > | operands () const |
Return operands of this SCEV expression. | |
bool | isZero () const |
Return true if the expression is a constant zero. | |
bool | isOne () const |
Return true if the expression is a constant one. | |
bool | isAllOnesValue () const |
Return true if the expression is a constant all-ones value. | |
bool | isNonConstantNegative () const |
Return true if the specified scev is negated, but not a constant. | |
unsigned short | getExpressionSize () const |
void | print (raw_ostream &OS) const |
Print out the internal representation of this scalar to the specified stream. | |
void | dump () const |
This method is used for debugging. | |
Public Member Functions inherited from llvm::FoldingSetBase::Node | |
Node ()=default | |
void * | getNextInBucket () const |
void | SetNextInBucket (void *N) |
Static Public Member Functions | |
static const SCEV * | evaluateAtIteration (ArrayRef< const SCEV * > Operands, const SCEV *It, ScalarEvolution &SE) |
Return the value of this chain of recurrences at the specified iteration number. | |
static bool | classof (const SCEV *S) |
Methods for support type inquiry through isa, cast, and dyn_cast: | |
Static Public Member Functions inherited from llvm::SCEVNAryExpr | |
static bool | classof (const SCEV *S) |
Methods for support type inquiry through isa, cast, and dyn_cast: | |
Friends | |
class | ScalarEvolution |
Additional Inherited Members | |
Public Types inherited from llvm::SCEV | |
enum | NoWrapFlags { FlagAnyWrap = 0 , FlagNW = (1 << 0) , FlagNUW = (1 << 1) , FlagNSW = (1 << 2) , NoWrapMask = (1 << 3) - 1 } |
NoWrapFlags are bitfield indices into SubclassData. More... | |
Protected Member Functions inherited from llvm::SCEVNAryExpr | |
SCEVNAryExpr (const FoldingSetNodeIDRef ID, enum SCEVTypes T, const SCEV *const *O, size_t N) | |
Protected Attributes inherited from llvm::SCEVNAryExpr | |
const SCEV *const * | Operands |
size_t | NumOperands |
Protected Attributes inherited from llvm::SCEV | |
const unsigned short | ExpressionSize |
unsigned short | SubclassData = 0 |
This field is initialized to zero and may be used in subclasses to store miscellaneous information. | |
This node represents a polynomial recurrence on the trip count of the specified loop.
This is the primary focus of the ScalarEvolution framework; all the other SCEV subclasses are mostly just supporting infrastructure to allow SCEVAddRecExpr expressions to be created and analyzed.
All operands of an AddRec are required to be loop invariant.
Definition at line 347 of file ScalarEvolutionExpressions.h.
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition at line 418 of file ScalarEvolutionExpressions.h.
References llvm::SCEV::getSCEVType(), and llvm::scAddRecExpr.
|
static |
Return the value of this chain of recurrences at the specified iteration number.
Takes an explicit list of operands to represent an AddRec.
Definition at line 1001 of file ScalarEvolution.cpp.
References assert(), BinomialCoefficient(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMulExpr(), and llvm::SCEVNAryExpr::Operands.
const SCEV * SCEVAddRecExpr::evaluateAtIteration | ( | const SCEV * | It, |
ScalarEvolution & | SE | ||
) | const |
Return the value of this chain of recurrences at the specified iteration number.
We can evaluate this recurrence by multiplying each element in the chain by the binomial coefficient corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as:
A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3)
where BC(It, k) stands for binomial coefficient.
Definition at line 995 of file ScalarEvolution.cpp.
References evaluateAtIteration(), and llvm::SCEVNAryExpr::operands().
Referenced by countToEliminateCompares(), evaluateAtIteration(), EvaluateConstantChrecAtConstant(), genLoopLimit(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), and llvm::SCEVLoopAddRecRewriter::visitAddRecExpr().
Definition at line 359 of file ScalarEvolutionExpressions.h.
Referenced by CollectSubexprs(), CompareSCEVComplexity(), llvm::IndexedReference::computeRefCost(), countToEliminateCompares(), llvm::denormalizeForPostIncUse(), findIVOperand(), llvm::ScalarEvolution::forgetLcssaPhiWithNewPredecessor(), llvm::SCEVExpander::generateOverflowCheck(), llvm::ScalarEvolution::getAddExpr(), getCastsForInductionPHI(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getLoopInvariantPredicate(), llvm::ScalarEvolution::getMulExpr(), getPreStartForExtend(), llvm::getPtrStride(), getStepRecurrence(), getStrideFromPointer(), isExistingPhi(), llvm::InductionDescriptor::isInductionPHI(), IsKnownPredicateViaAddRecStart(), isLoopCounter(), isOneDimensionalArray(), isSimpleIVUser(), llvm::normalizeForPostIncUse(), llvm::SCEV::print(), llvm::ScalarEvolution::SimplifyICmpOperands(), llvm::ScalarEvolution::verify(), llvm::SCEVRewriteVisitor< SC >::visitAddRecExpr(), llvm::SCEVLoopAddRecRewriter::visitAddRecExpr(), and llvm::SCEVDivision::visitAddRecExpr().
const SCEV * SCEVAddRecExpr::getNumIterationsInRange | ( | const ConstantRange & | Range, |
ScalarEvolution & | SE | ||
) | const |
Return the number of iterations of this loop that produce values in the specified constant range.
Another way of looking at this is that it returns the first iteration number where the value is not in the condition, thus computing the exit count. If the iteration count can't be computed, an instance of SCEVCouldNotCompute is returned.
Definition at line 13378 of file ScalarEvolution.cpp.
References A, llvm::any_of(), assert(), llvm::BitWidth, llvm::ConstantRange::contains(), End, EvaluateConstantChrecAtConstant(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::ConstantRange::getLower(), getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ConstantRange::getUpper(), llvm::ConstantInt::getValue(), llvm::ScalarEvolution::getZero(), llvm::ConstantRange::isFullSet(), Operands, Range, SolveQuadraticAddRecRange(), and llvm::ConstantRange::subtract().
const SCEVAddRecExpr * SCEVAddRecExpr::getPostIncExpr | ( | ScalarEvolution & | SE | ) | const |
Return an expression representing the value of this expression one iteration of the loop ahead.
Definition at line 13450 of file ScalarEvolution.cpp.
References assert(), llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::Last, and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by canFoldTermCondOfLoop(), and genLoopLimit().
Definition at line 358 of file ScalarEvolutionExpressions.h.
References llvm::SCEVNAryExpr::Operands.
Referenced by llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds(), canBeCheaplyTransformed(), CollectSubexprs(), llvm::SCEVExpander::generateOverflowCheck(), genLoopLimit(), llvm::ScalarEvolution::getAddExpr(), getExtendAddRecStart(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getLoopInvariantPredicate(), getPreStartForExtend(), getType(), IsKnownPredicateViaAddRecStart(), isOneDimensionalArray(), mayUsePostIncMode(), llvm::LoopStructure::parseLoopStructure(), and llvm::SCEVDivision::visitAddRecExpr().
|
inline |
Constructs and returns the recurrence indicating how much this expression steps by.
If this is a polynomial of degree N, it returns a chrec of degree N-1. We cannot determine whether the step recurrence has self-wraparound.
Definition at line 365 of file ScalarEvolutionExpressions.h.
References llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddRecExpr(), getLoop(), llvm::SCEVNAryExpr::getOperand(), isAffine(), and llvm::SCEVNAryExpr::operands().
Referenced by llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds(), canFoldTermCondOfLoop(), CollectSubexprs(), countToEliminateCompares(), llvm::SCEVExpander::generateOverflowCheck(), genLoopLimit(), llvm::TargetTransformInfoImplBase::getConstantStrideStep(), getExtendAddRecStart(), llvm::SCEVWrapPredicate::getImpliedFlags(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getLoopInvariantPredicate(), getPreStartForExtend(), llvm::getPtrStride(), getStrideFromPointer(), IsIncrementNSW(), IsIncrementNUW(), llvm::InductionDescriptor::isInductionPHI(), IsKnownPredicateViaAddRecStart(), isLoopCounter(), isOneDimensionalArray(), mayUsePostIncMode(), llvm::LoopStructure::parseLoopStructure(), and llvm::SCEVDivision::visitAddRecExpr().
|
inline |
Definition at line 357 of file ScalarEvolutionExpressions.h.
References getStart(), and llvm::SCEV::getType().
Referenced by canBeCheaplyTransformed(), CollectSubexprs(), llvm::SCEVExpander::generateOverflowCheck(), genLoopLimit(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getMulExpr(), getPreStartForExtend(), isAddRecSExtable(), isExistingPhi(), IsIncrementNSW(), IsIncrementNUW(), mayUsePostIncMode(), and SolveQuadraticAddRecRange().
|
inline |
Return true if this represents an expression A + B*x where A and B are loop invariant values.
Definition at line 375 of file ScalarEvolutionExpressions.h.
References llvm::SCEVNAryExpr::getNumOperands().
Referenced by canFoldTermCondOfLoop(), CollectSubexprs(), countToEliminateCompares(), llvm::SCEVExpander::generateOverflowCheck(), getFalkorUnrollingPreferences(), llvm::ScalarEvolution::getLoopInvariantPredicate(), getStepRecurrence(), hasComputableBounds(), IsKnownPredicateViaAddRecStart(), isLoopCounter(), isOneDimensionalArray(), and llvm::SCEVDivision::visitAddRecExpr().
|
inline |
Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant values.
This corresponds to an addrec of the form {L,+,M,+,N}
Definition at line 384 of file ScalarEvolutionExpressions.h.
References llvm::SCEVNAryExpr::getNumOperands().
|
inline |
Set flags for a recurrence without clearing any previously set flags.
For AddRec, either NUW or NSW implies NW. Keep track of this fact here to make it easier to propagate flags.
Definition at line 389 of file ScalarEvolutionExpressions.h.
References llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::ScalarEvolution::setFlags(), and llvm::SCEV::SubclassData.
Referenced by llvm::ScalarEvolution::setNoWrapFlags().
|
friend |
Definition at line 348 of file ScalarEvolutionExpressions.h.