llvm::SCEV Class Reference

This class represents an analyzed expression in the program. More...

#include "llvm/Analysis/ScalarEvolution.h"

Inheritance diagram for llvm::SCEV:

Public Types
enum	NoWrapFlags {   FlagAnyWrap = 0 , FlagNW = (1 << 0) , FlagNUW = (1 << 1) , FlagNSW = (1 << 2) ,   NoWrapMask = (1 << 3) - 1 }
	NoWrapFlags are bitfield indices into SubclassData. More...

Public Member Functions
	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< SCEVUse >	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.
LLVM_ABI void	computeAndSetCanonical (ScalarEvolution &SE)
	Compute and set the canonical SCEV, by constructing a SCEV with the same operands, but all SCEVUse flags dropped.
LLVM_ABI const SCEV *	getCanonical () const
	Return the canonical SCEV.
Public Member Functions inherited from llvm::FoldingSetBase::Node
	Node ()=default
void *	getNextInBucket () const
void	SetNextInBucket (void *N)

Protected Attributes
const unsigned short	ExpressionSize
unsigned short	SubclassData = 0
	This field is initialized to zero and may be used in subclasses to store miscellaneous information.
const SCEV *	CanonicalSCEV = nullptr
	Pointer to the canonical version of the SCEV, i.e.

Friends
struct	FoldingSetTrait< SCEV >

Detailed Description

This class represents an analyzed expression in the program.

These are opaque objects that the client is not allowed to do much with directly.

Definition at line 151 of file ScalarEvolution.h.

Member Enumeration Documentation

NoWrapFlags

enum llvm::SCEV::NoWrapFlags

NoWrapFlags are bitfield indices into SubclassData.

Add and Mul expressions may have no-unsigned-wrap <NUW> or no-signed-wrap <NSW> properties, which are derived from the IR operator. NSW is a misnomer that we use to mean no signed overflow or underflow.

AddRec expressions may have a no-self-wraparound <NW> property if, in the integer domain, abs(step) * max-iteration(loop) <= unsigned-max(bitwidth). This means that the recurrence will never reach its start value if the step is non-zero. Computing the same value on each iteration is not considered wrapping, and recurrences with step = 0 are trivially <NW>. <NW> is independent of the sign of step and the value the add recurrence starts with.

Note that NUW and NSW are also valid properties of a recurrence, and either implies NW. For convenience, NW will be set for a recurrence whenever either NUW or NSW are set.

We require that the flag on a SCEV apply to the entire scope in which that SCEV is defined. A SCEV's scope is set of locations dominated by a defining location, which is in turn described by the following rules:

• A SCEVUnknown is at the point of definition of the Value.
• A SCEVConstant is defined at all points.
• A SCEVAddRec is defined starting with the header of the associated loop.
• All other SCEVs are defined at the earlest point all operands are defined.

The above rules describe a maximally hoisted form (without regards to potential control dependence). A SCEV is defined anywhere a corresponding instruction could be defined in said maximally hoisted form. Note that SCEVUDivExpr (currently the only expression type which can trap) can be defined per these rules in regions where it would trap at runtime. A SCEV being defined does not require the existence of any instruction within the defined scope.

Enumerator
FlagAnyWrap
FlagNW
FlagNUW
FlagNSW
NoWrapMask

Definition at line 210 of file ScalarEvolution.h.

Constructor & Destructor Documentation

SCEV() [1/2]

llvm::SCEV::SCEV ( const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize )

inlineexplicit

Definition at line 218 of file ScalarEvolution.h.

References ExpressionSize.

Referenced by llvm::SCEVCastExpr::classof(), llvm::SCEVConstant::classof(), llvm::SCEVCouldNotCompute::classof(), llvm::SCEVNAryExpr::classof(), llvm::SCEVUDivExpr::classof(), llvm::SCEVUnknown::classof(), llvm::SCEVVScale::classof(), getCanonical(), operator=(), print(), llvm::SCEVConstant::ScalarEvolution, llvm::SCEVUDivExpr::ScalarEvolution, llvm::SCEVUnknown::ScalarEvolution, llvm::SCEVVScale::ScalarEvolution, SCEV(), llvm::SCEVCastExpr::SCEVCastExpr(), llvm::SCEVCouldNotCompute::SCEVCouldNotCompute(), and llvm::SCEVNAryExpr::SCEVNAryExpr().

SCEV() [2/2]

llvm::SCEV::SCEV ( const SCEV & )

delete

References SCEV().

Member Function Documentation

computeAndSetCanonical()

void SCEV::computeAndSetCanonical

(

ScalarEvolution &

SE

)

Compute and set the canonical SCEV, by constructing a SCEV with the same operands, but all SCEVUse flags dropped.

Definition at line 261 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::back(), CanonicalSCEV, llvm::cast(), Changed, llvm::dyn_cast(), FlagAnyWrap, llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getPtrToAddrExpr(), llvm::ScalarEvolution::getPtrToIntExpr(), getSCEVType(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::ScalarEvolution::getSMaxExpr(), llvm::ScalarEvolution::getSMinExpr(), llvm::ScalarEvolution::getTruncateExpr(), getType(), llvm::ScalarEvolution::getUDivExpr(), llvm::ScalarEvolution::getUMaxExpr(), llvm::ScalarEvolution::getUMinExpr(), llvm::ScalarEvolution::getZeroExtendExpr(), llvm_unreachable, operands(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scMulExpr, llvm::scPtrToAddr, llvm::scPtrToInt, llvm::scSequentialUMinExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, llvm::scVScale, and llvm::scZeroExtend.

Referenced by llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getLosslessPtrToIntExpr(), llvm::ScalarEvolution::getMinMaxExpr(), llvm::ScalarEvolution::getPtrToAddrExpr(), llvm::ScalarEvolution::getSequentialMinMaxExpr(), llvm::ScalarEvolution::getSignExtendExprImpl(), llvm::ScalarEvolution::getTruncateExpr(), llvm::ScalarEvolution::getUDivExpr(), llvm::ScalarEvolution::getUnknown(), llvm::ScalarEvolution::getVScale(), and llvm::ScalarEvolution::getZeroExtendExprImpl().

dump()

LLVM_DUMP_METHOD void SCEV::dump

(

)

const

This method is used for debugging.

Definition at line 360 of file ScalarEvolution.cpp.

References llvm::dbgs(), LLVM_DUMP_METHOD, and print().

getCanonical()

LLVM_ABI const SCEV * llvm::SCEV::getCanonical ( ) const

inline

Return the canonical SCEV.

Definition at line 269 of file ScalarEvolution.h.

References assert(), CanonicalSCEV, LLVM_ABI, and SCEV().

Referenced by llvm::SCEVUse::getCanonical().

getExpressionSize()

unsigned short llvm::SCEV::getExpressionSize ( ) const

inline

Definition at line 253 of file ScalarEvolution.h.

References ExpressionSize.

Referenced by hasHugeExpression().

getSCEVType()

SCEVTypes llvm::SCEV::getSCEVType ( ) const

inline

Definition at line 224 of file ScalarEvolution.h.

Referenced by llvm::SCEVAddExpr::classof(), llvm::SCEVAddRecExpr::classof(), llvm::SCEVCastExpr::classof(), llvm::SCEVCommutativeExpr::classof(), llvm::SCEVConstant::classof(), llvm::SCEVCouldNotCompute::classof(), llvm::SCEVIntegralCastExpr::classof(), llvm::SCEVMinMaxExpr::classof(), llvm::SCEVMulExpr::classof(), llvm::SCEVNAryExpr::classof(), llvm::SCEVPtrToAddrExpr::classof(), llvm::SCEVPtrToIntExpr::classof(), llvm::SCEVSequentialMinMaxExpr::classof(), llvm::SCEVSequentialUMinExpr::classof(), llvm::SCEVSignExtendExpr::classof(), llvm::SCEVSMaxExpr::classof(), llvm::SCEVSMinExpr::classof(), llvm::SCEVTruncateExpr::classof(), llvm::SCEVUDivExpr::classof(), llvm::SCEVUMaxExpr::classof(), llvm::SCEVUMinExpr::classof(), llvm::SCEVUnknown::classof(), llvm::SCEVVScale::classof(), llvm::SCEVZeroExtendExpr::classof(), computeAndSetCanonical(), llvm::SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(), getExprBase(), getType(), GroupByComplexity(), isHighCostExpansion(), operands(), print(), SCEVMinMaxExprContains(), llvm::SCEVVisitor< SCEVSequentialMinMaxDeduplicatingVisitor, RetVal >::visit(), and llvm::SCEVTraversal< SV >::visitAll().

getType()

Type * SCEV::getType

(

)

const

Return the LLVM type of this SCEV expression.

Definition at line 479 of file ScalarEvolution.cpp.

References llvm::cast(), getSCEVType(), llvm_unreachable, llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scPtrToAddr, llvm::scPtrToInt, llvm::scSequentialUMinExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, llvm::scVScale, and llvm::scZeroExtend.

Referenced by llvm::VPlanTransforms::addMinimumIterationCheck(), llvm::SCEVAAResult::alias(), areAllLoadsDereferenceable(), BinomialCoefficient(), calculateRtStride(), llvm::cannotBeMaxInLoop(), llvm::cannotBeMinInLoop(), CollectSubexprs(), computeAndSetCanonical(), llvm::ScalarEvolution::computeConstantDifference(), llvm::LoopVectorizationCostModel::computeMaxVF(), llvm::IndexedReference::computeRefCost(), computeTripCount(), llvm::ScalarEvolution::convertSCEVToAddRecWithPredicates(), countToEliminateCompares(), createNodeForSelectViaUMinSeq(), createReplacement(), llvm::delinearizeFixedSizeArray(), llvm::DependenceInfo::depends(), DoInitialMatch(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), expandBounds(), llvm::SCEVExpander::expandCodeFor(), llvm::VPlanTransforms::expandSCEVs(), ExtractImmediate(), FindLoopCounter(), findSplitCandidate(), llvm::SCEVExpander::generateOverflowCheck(), genLoopLimit(), llvm::ScalarEvolution::getAnyExtendExpr(), llvm::ScalarEvolution::getGEPExpr(), llvm::ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(), llvm::ScalarEvolution::getLosslessPtrToIntExpr(), getMaxTCFromNonZeroRange(), llvm::ScalarEvolution::getMinTrailingZeros(), getNewAlignment(), llvm::ScalarEvolution::getPtrToAddrExpr(), llvm::vputils::getSCEVExprForVPValue(), getSignedOverflowLimitForStep(), llvm::ScalarEvolution::getSignExtendExprImpl(), getSmallConstantTripCount(), llvm::getStartAndEndForAccess(), llvm::getStartAndEndForAccess(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::SCEVAddRecExpr::getType(), llvm::SCEVMinMaxExpr::getType(), llvm::SCEVMulExpr::getType(), llvm::SCEVSequentialMinMaxExpr::getType(), llvm::SCEVUDivExpr::getType(), llvm::ScalarEvolution::getUMinFromMismatchedTypes(), getUnsignedOverflowLimitForStep(), llvm::ScalarEvolution::getZeroExtendExprImpl(), llvm::hasIterationCountInvariantInParent(), llvm::SCEVWrapPredicate::implies(), isConditionTrueViaVFAndUF(), llvm::ARMTTIImpl::isHardwareLoopProfitable(), llvm::ScalarEvolution::isKnownMultipleOf(), llvm::isKnownNegativeInLoop(), llvm::isKnownNonNegativeInLoop(), llvm::isKnownNonPositiveInLoop(), llvm::isKnownPositiveInLoop(), llvm::ScalarEvolution::isLoopBackedgeGuardedByCond(), isSafeDecreasingBound(), isSafeDependenceDistance(), isSafeIncreasingBound(), IsSimplerBaseSCEVForTarget(), llvm::SCEVPatternMatch::bind_cst_ty::match(), llvm::SCEVPatternMatch::cst_pred_ty< Predicate >::match(), llvm::SCEVPatternMatch::SCEVURem_match< Op0_t, Op1_t >::match(), mayUsePostIncMode(), llvm::VPlanTransforms::optimizeFindIVReductions(), optimizeLoopExitWithUnknownExitCount(), llvm::LoopStructure::parseLoopStructure(), llvm::peelLoop(), PrintSCEVWithTypeHint(), llvm::replaceSymbolicStrideSCEV(), llvm::ScalarEvolution::LoopGuards::rewrite(), shouldPeelLastIteration(), simplifyBranchConditionForVFAndUF(), llvm::VPlanTransforms::simplifyKnownEVL(), splitLoopBound(), llvm::UnrollRuntimeLoopRemainder(), llvm::validateDelinearizationResult(), verifyTripCount(), SCEVCastSinkingRewriter::visit(), llvm::SCEVDivision::visitAddExpr(), llvm::SCEVDivision::visitAddRecExpr(), and llvm::SCEVDivision::visitMulExpr().

isAllOnesValue()

bool SCEV::isAllOnesValue

(

)

const

Return true if the expression is a constant all-ones value.

Definition at line 547 of file ScalarEvolution.cpp.

References llvm::SCEVPatternMatch::m_scev_AllOnes(), and llvm::PatternMatch::match().

isNonConstantNegative()

bool SCEV::isNonConstantNegative

(

)

const

Return true if the specified scev is negated, but not a constant.

Definition at line 549 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::SCEVConstant::getAPInt(), llvm::APInt::isNegative(), and llvm::Mul.

Referenced by calculateRtStride().

isOne()

bool SCEV::isOne

(

)

const

Return true if the expression is a constant one.

Definition at line 545 of file ScalarEvolution.cpp.

References llvm::SCEVPatternMatch::m_scev_One(), and llvm::PatternMatch::match().

Referenced by llvm::ScalarEvolution::convertSCEVToAddRecWithPredicates(), genLoopLimit(), getStartForNegStride(), and normalizePredicate().

isZero()

bool SCEV::isZero

(

)

const

Return true if the expression is a constant zero.

Definition at line 543 of file ScalarEvolution.cpp.

References llvm::SCEVPatternMatch::m_scev_Zero(), and llvm::PatternMatch::match().

Referenced by breakBackedgeIfNotTaken(), calculateRtStride(), llvm::LoopVectorizationCostModel::computeMaxVF(), llvm::DependenceInfo::depends(), llvm::SCEVDivision::divide(), dumpExampleDependence(), evaluatePtrAddRecAtMaxBTCWillNotWrap(), llvm::findArrayDimensions(), FindLoopCounter(), isAlwaysFoldable(), llvm::LoopVectorizationPlanner::selectEpilogueVectorizationFactor(), SolveQuadraticAddRecRange(), and llvm::ScalarEvolution::verify().

operands()

ArrayRef< SCEVUse > SCEV::operands

(

)

const

Return operands of this SCEV expression.

Definition at line 514 of file ScalarEvolution.cpp.

References llvm::cast(), getSCEVType(), llvm_unreachable, llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scPtrToAddr, llvm::scPtrToInt, llvm::scSequentialUMinExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, llvm::scVScale, and llvm::scZeroExtend.

Referenced by computeAndSetCanonical(), llvm::ScalarEvolution::computeConstantDifference(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getNotSCEV(), getSetupCost(), llvm::ScalarEvolution::verify(), and llvm::SCEVTraversal< SV >::visitAll().

operator=()

SCEV & llvm::SCEV::operator= ( const SCEV & )

delete

References SCEV().

print()

void SCEV::print

(

raw_ostream &

OS

)

const

Print out the internal representation of this scalar to the specified stream.

This should really only be used for debugging purposes.

Definition at line 366 of file ScalarEvolution.cpp.

References llvm::cast(), FlagNSW, FlagNUW, llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::SCEVUDivExpr::getLHS(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVCastExpr::getOperand(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVUDivExpr::getRHS(), getSCEVType(), llvm::SCEVCastExpr::getType(), llvm::SCEVNAryExpr::hasNoSelfWrap(), llvm::SCEVNAryExpr::hasNoSignedWrap(), llvm::SCEVNAryExpr::hasNoUnsignedWrap(), llvm::interleaved(), llvm_unreachable, llvm::make_pointee_range(), llvm::SCEVNAryExpr::operands(), llvm::Value::printAsOperand(), llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, SCEV(), llvm::scMulExpr, llvm::scPtrToAddr, llvm::scPtrToInt, llvm::scSequentialUMinExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scSMinExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUMinExpr, llvm::scUnknown, llvm::scVScale, and llvm::scZeroExtend.

Referenced by dump(), llvm::operator<<(), llvm::ScalarEvolution::print(), and llvm::SCEVUse::print().

Friends And Related Symbol Documentation

FoldingSetTrait< SCEV >

friend struct FoldingSetTrait< SCEV >

friend

Definition at line 143 of file ScalarEvolution.h.

References llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::getPointer().

Member Data Documentation

CanonicalSCEV

const SCEV* llvm::SCEV::CanonicalSCEV = nullptr

protected

Pointer to the canonical version of the SCEV, i.e.

one where all operands have no SCEVUse flags.

Definition at line 171 of file ScalarEvolution.h.

Referenced by computeAndSetCanonical(), and getCanonical().

ExpressionSize

const unsigned short llvm::SCEV::ExpressionSize

protected

Definition at line 163 of file ScalarEvolution.h.

Referenced by getExpressionSize(), and SCEV().

SubclassData

unsigned short llvm::SCEV::SubclassData = 0

protected

This field is initialized to zero and may be used in subclasses to store miscellaneous information.

Definition at line 167 of file ScalarEvolution.h.

Referenced by llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVAddRecExpr::setNoWrapFlags(), and llvm::SCEVCommutativeExpr::setNoWrapFlags().

---

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

• include/llvm/Analysis/ScalarEvolution.h
• lib/Analysis/ScalarEvolution.cpp