LLVM: llvm::SCEVAddRecExpr Class Reference (original) (raw)

This node represents a polynomial recurrence on the trip count of the specified loop. More...

#include "[llvm/Analysis/ScalarEvolutionExpressions.h](ScalarEvolutionExpressions%5F8h%5Fsource.html)"

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.
LLVM_ABI const SCEV * evaluateAtIteration (const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
LLVM_ABI 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.
LLVM_ABI 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
LLVM_ABI Type * getType () const
Return the LLVM type of this SCEV expression.
LLVM_ABI ArrayRef< const SCEV * > operands () const
Return operands of this SCEV expression.
LLVM_ABI bool isZero () const
Return true if the expression is a constant zero.
LLVM_ABI bool isOne () const
Return true if the expression is a constant one.
LLVM_ABI bool isAllOnesValue () const
Return true if the expression is a constant all-ones value.
LLVM_ABI bool isNonConstantNegative () const
Return true if the specified scev is negated, but not a constant.
unsigned short getExpressionSize () const
LLVM_ABI void print (raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
LLVM_ABI 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 LLVM_ABI 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 348 of file ScalarEvolutionExpressions.h.

◆ classof()

bool llvm::SCEVAddRecExpr::classof ( const SCEV * S) inlinestatic

◆ evaluateAtIteration() [1/2]

◆ evaluateAtIteration() [2/2]

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 980 of file ScalarEvolution.cpp.

References evaluateAtIteration(), llvm::SCEVNAryExpr::operands(), and ScalarEvolution.

Referenced by countToEliminateCompares(), evaluateAtIteration(), EvaluateConstantChrecAtConstant(), genLoopLimit(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), isKnownLessThan(), shouldPeelLastIteration(), and llvm::SCEVLoopAddRecRewriter::visitAddRecExpr().

◆ getLoop()

const Loop * llvm::SCEVAddRecExpr::getLoop ( ) const inline

Definition at line 360 of file ScalarEvolutionExpressions.h.

Referenced by CompareSCEVComplexity(), llvm::IndexedReference::computeRefCost(), llvm::ScalarEvolution::convertSCEVToAddRecWithPredicates(), countToEliminateCompares(), llvm::denormalizeForPostIncUse(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), findIVOperand(), llvm::ScalarEvolution::forgetLcssaPhiWithNewPredecessor(), llvm::SCEVExpander::generateOverflowCheck(), llvm::ScalarEvolution::getAddExpr(), getCastsForInductionPHI(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getLoopInvariantPredicate(), llvm::ScalarEvolution::getMulExpr(), getNumIterationsInRange(), getPostIncExpr(), getPreStartForExtend(), getStepRecurrence(), getStrideFromAddRec(), isExistingPhi(), isKnownLessThan(), isOneDimensionalArray(), isSimpleIVUser(), llvm::normalizeForPostIncUse(), llvm::SCEV::print(), llvm::ScalarEvolution::SimplifyICmpOperands(), llvm::ScalarEvolution::verify(), llvm::SCEVDivision::visitAddRecExpr(), llvm::SCEVLoopAddRecRewriter::visitAddRecExpr(), and llvm::SCEVRewriteVisitor< SC >::visitAddRecExpr().

◆ getNumIterationsInRange()

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 13600 of file ScalarEvolution.cpp.

References A(), llvm::any_of(), assert(), llvm::BitWidth, llvm::cast(), llvm::dyn_cast(), EvaluateConstantChrecAtConstant(), llvm::SCEV::FlagNW, llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getCouldNotCompute(), getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getOperand(), getStart(), getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ConstantInt::getValue(), llvm::ScalarEvolution::getZero(), llvm::isa(), isAffine(), isQuadratic(), llvm::SCEVNAryExpr::Operands, llvm::SCEVNAryExpr::operands(), Range, ScalarEvolution, and SolveQuadraticAddRecRange().

◆ getPostIncExpr()

Return an expression representing the value of this expression one iteration of the loop ahead.

Definition at line 13672 of file ScalarEvolution.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, assert(), llvm::cast(), llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), getLoop(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::Last, and ScalarEvolution.

Referenced by canFoldTermCondOfLoop(), and genLoopLimit().

◆ getStart()

const SCEV * llvm::SCEVAddRecExpr::getStart ( ) const inline

Definition at line 359 of file ScalarEvolutionExpressions.h.

References llvm::SCEVNAryExpr::Operands.

Referenced by llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds(), canBeCheaplyTransformed(), collectConstantAbsSteps(), llvm::ScalarEvolution::convertSCEVToAddRecWithPredicates(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), findSplitCandidate(), llvm::SCEVExpander::generateOverflowCheck(), genLoopLimit(), llvm::ScalarEvolution::getAddExpr(), getExtendAddRecStart(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getLoopInvariantPredicate(), getNumIterationsInRange(), getPreStartForExtend(), getType(), isKnownLessThan(), llvm::ScalarEvolution::isKnownMultipleOf(), isOneDimensionalArray(), isSafeToTruncateWideIVType(), normalizePredicate(), llvm::LoopStructure::parseLoopStructure(), and llvm::SCEVDivision::visitAddRecExpr().

◆ getStepRecurrence()

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 366 of file ScalarEvolutionExpressions.h.

References llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddRecExpr(), getLoop(), llvm::SCEVNAryExpr::getOperand(), isAffine(), llvm::SCEVNAryExpr::operands(), and ScalarEvolution.

Referenced by llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds(), canFoldTermCondOfLoop(), collectConstantAbsSteps(), llvm::ScalarEvolution::convertSCEVToAddRecWithPredicates(), countToEliminateCompares(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), llvm::SCEVExpander::generateOverflowCheck(), genLoopLimit(), llvm::TargetTransformInfoImplBase::getConstantStrideStep(), getExtendAddRecStart(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getLoopInvariantPredicate(), getPreStartForExtend(), getStrideFromAddRec(), IsIncrementNSW(), IsIncrementNUW(), isKnownLessThan(), llvm::ScalarEvolution::isKnownMultipleOf(), isOneDimensionalArray(), normalizePredicate(), llvm::LoopStructure::parseLoopStructure(), and llvm::SCEVDivision::visitAddRecExpr().

◆ getType()

Type * llvm::SCEVAddRecExpr::getType ( ) const inline

Definition at line 358 of file ScalarEvolutionExpressions.h.

References getStart(), and llvm::SCEV::getType().

Referenced by canBeCheaplyTransformed(), generateLoopLatchCheck(), llvm::SCEVExpander::generateOverflowCheck(), genLoopLimit(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getMulExpr(), getPreStartForExtend(), isAddRecSExtable(), isExistingPhi(), IsIncrementNSW(), IsIncrementNUW(), isNoWrap(), isSafeToTruncateWideIVType(), and SolveQuadraticAddRecRange().

◆ isAffine()

bool llvm::SCEVAddRecExpr::isAffine ( ) const inline

Return true if this represents an expression A + B*x where A and B are loop invariant values.

Definition at line 376 of file ScalarEvolutionExpressions.h.

References llvm::SCEVNAryExpr::getNumOperands().

Referenced by canFoldTermCondOfLoop(), collectConstantAbsSteps(), countToEliminateCompares(), llvm::SCEVExpander::generateOverflowCheck(), getFalkorUnrollingPreferences(), llvm::ScalarEvolution::getLoopInvariantPredicate(), getNumIterationsInRange(), getStepRecurrence(), isKnownLessThan(), isOneDimensionalArray(), and llvm::SCEVDivision::visitAddRecExpr().

◆ isQuadratic()

bool llvm::SCEVAddRecExpr::isQuadratic ( ) const inline

◆ setNoWrapFlags()

void llvm::SCEVAddRecExpr::setNoWrapFlags ( NoWrapFlags Flags) inline

◆ ScalarEvolution

The documentation for this class was generated from the following files: