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

#include "llvm/Analysis/ScalarEvolutionExpressions.h"

Inheritance diagram for llvm::SCEVAddRecExpr:

[legend]

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 + Bx + Cx^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.

Detailed Description

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.

Member Function Documentation

◆ classof()

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

inlinestatic

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.

◆ evaluateAtIteration() [1/2]

const SCEV * SCEVAddRecExpr::evaluateAtIteration	(	ArrayRef< const SCEV * >	Operands,
		const SCEV *	It,
		ScalarEvolution &	SE
	)

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

References assert(), BinomialCoefficient(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMulExpr(), and llvm::SCEVNAryExpr::Operands.

◆ evaluateAtIteration() [2/2]

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

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

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

◆ getLoop()

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

inline

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().

◆ getNumIterationsInRange()

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 13485 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().