#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/SaveAndRestore.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <map>
#include <memory>
#include <tuple>
#include <utility>
#include <vector>

Macros
#define	DEBUG_TYPE "scalar-evolution"

Functions
	STATISTIC (NumArrayLenItCounts, "Number of trip counts computed with array length")

	STATISTIC (NumTripCountsComputed, "Number of loops with predictable loop counts")

	STATISTIC (NumTripCountsNotComputed, "Number of loops without predictable loop counts")

	STATISTIC (NumBruteForceTripCountsComputed, "Number of loops with trip counts computed by force")

static int	CompareValueComplexity (EquivalenceClasses< const Value > &EqCacheValue, const LoopInfo const LI, Value LV, Value RV, unsigned Depth)
	Compare the two values `LV` and `RV` in terms of their "complexity" where "complexity" is a partial (and somewhat ad-hoc) relation used to order operands in SCEV expressions. More...

static int	CompareSCEVComplexity (EquivalenceClasses< const SCEV > &EqCacheSCEV, EquivalenceClasses< const Value > &EqCacheValue, const LoopInfo const LI, const SCEV LHS, const SCEV *RHS, DominatorTree &DT, unsigned Depth=0)

static void	GroupByComplexity (SmallVectorImpl< const SCEV > &Ops, LoopInfo LI, DominatorTree &DT)
	Given a list of SCEV objects, order them by their complexity, and group objects of the same complexity together by value. More...

static int	sizeOfSCEV (const SCEV *S)

static const SCEV *	BinomialCoefficient (const SCEV It, unsigned K, ScalarEvolution &SE, Type ResultTy)
	Compute BC(It, K). The result has width W. Assume, K > 0. More...

static const SCEV *	getSignedOverflowLimitForStep (const SCEV Step, ICmpInst::Predicate Pred, ScalarEvolution *SE)

static const SCEV *	getUnsignedOverflowLimitForStep (const SCEV Step, ICmpInst::Predicate Pred, ScalarEvolution *SE)

template<typename ExtendOpTy >
static const SCEV *	getPreStartForExtend (const SCEVAddRecExpr AR, Type Ty, ScalarEvolution *SE, unsigned Depth)

template<typename ExtendOpTy >
static const SCEV *	getExtendAddRecStart (const SCEVAddRecExpr AR, Type Ty, ScalarEvolution *SE, unsigned Depth)

static APInt	extractConstantWithoutWrapping (ScalarEvolution &SE, const SCEVConstant ConstantTerm, const SCEVAddExpr WholeAddExpr)

static APInt	extractConstantWithoutWrapping (ScalarEvolution &SE, const APInt &ConstantStart, const SCEV *Step)

static bool	CollectAddOperandsWithScales (DenseMap< const SCEV , APInt > &M, SmallVectorImpl< const SCEV > &NewOps, APInt &AccumulatedConstant, const SCEV const Ops, size_t NumOperands, const APInt &Scale, ScalarEvolution &SE)
	Process the given Ops list, which is a list of operands to be added under the given scale, update the given map. More...

static SCEV::NoWrapFlags	StrengthenNoWrapFlags (ScalarEvolution SE, SCEVTypes Type, const SmallVectorImpl< const SCEV > &Ops, SCEV::NoWrapFlags Flags)

static uint64_t	umul_ov (uint64_t i, uint64_t j, bool &Overflow)

static uint64_t	Choose (uint64_t n, uint64_t k, bool &Overflow)
	Compute the result of "n choose k", the binomial coefficient. More...

static bool	containsConstantInAddMulChain (const SCEV *StartExpr)
	Determine if any of the operands in this SCEV are a constant or if any of the add or multiply expressions in this SCEV contain a constant. More...

static const APInt	gcd (const SCEVConstant C1, const SCEVConstant C2)

static std::pair< const SCEV , ConstantInt >	splitAddExpr (const SCEV *S)
	Try to split a SCEVAddExpr into a pair of {SCEV, ConstantInt}. More...

static bool	SCEVLostPoisonFlags (const SCEV S, const Value V)
	Check whether value has nuw/nsw/exact set but SCEV does not. More...

static void	PushDefUseChildren (Instruction I, SmallVectorImpl< Instruction > &Worklist)
	Push users of the given Instruction onto the given Worklist. More...

static Optional< BinaryOp >	MatchBinaryOp (Value *V, DominatorTree &DT)
	Try to map `V` into a BinaryOp, and return `None` on failure. More...

static Type *	isSimpleCastedPHI (const SCEV Op, const SCEVUnknown SymbolicPHI, bool &Signed, ScalarEvolution &SE)
	Helper function to createAddRecFromPHIWithCasts. More...

static const Loop *	isIntegerLoopHeaderPHI (const PHINode *PN, LoopInfo &LI)

static bool	IsAvailableOnEntry (const Loop L, DominatorTree &DT, const SCEV S, BasicBlock *BB)

static bool	BrPHIToSelect (DominatorTree &DT, BranchInst BI, PHINode Merge, Value &C, Value &LHS, Value *&RHS)

static Optional< ConstantRange >	GetRangeFromMetadata (Value *V)
	Helper method to assign a range to V from metadata present in the IR. More...

static ConstantRange	getRangeForAffineARHelper (APInt Step, const ConstantRange &StartRange, const APInt &MaxBECount, unsigned BitWidth, bool Signed)

static unsigned	getConstantTripCount (const SCEVConstant *ExitCount)

static void	PushLoopPHIs (const Loop L, SmallVectorImpl< Instruction > &Worklist)
	Push PHI nodes in the header of the given loop onto the given Worklist. More...

static ConstantInt *	EvaluateConstantChrecAtConstant (const SCEVAddRecExpr AddRec, ConstantInt C, ScalarEvolution &SE)

static bool	CanConstantFold (const Instruction *I)
	Return true if we can constant fold an instruction of the specified type, assuming that all operands were constants. More...

static bool	canConstantEvolve (Instruction I, const Loop L)
	Determine whether this instruction can constant evolve within this loop assuming its operands can all constant evolve. More...

static PHINode *	getConstantEvolvingPHIOperands (Instruction UseInst, const Loop L, DenseMap< Instruction , PHINode > &PHIMap, unsigned Depth)
	getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instruction operand until reaching a loop header phi. More...

static PHINode *	getConstantEvolvingPHI (Value V, const Loop L)
	getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is derived from. More...

static Constant *	EvaluateExpression (Value V, const Loop L, DenseMap< Instruction , Constant > &Vals, const DataLayout &DL, const TargetLibraryInfo *TLI)
	EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node in the loop has the value PHIVal. More...

static Constant *	getOtherIncomingValue (PHINode PN, BasicBlock BB)

static Constant *	BuildConstantFromSCEV (const SCEV *V)
	This builds up a Constant using the ConstantExpr interface. More...

static const SCEV *	SolveLinEquationWithOverflow (const APInt &A, const SCEV *B, ScalarEvolution &SE)
	Finds the minimum unsigned root of the following equation: More...

static Optional< std::tuple< APInt, APInt, APInt, APInt, unsigned > >	GetQuadraticEquation (const SCEVAddRecExpr *AddRec)
	For a given quadratic addrec, generate coefficients of the corresponding quadratic equation, multiplied by a common value to ensure that they are integers. More...

static Optional< APInt >	MinOptional (Optional< APInt > X, Optional< APInt > Y)
	Helper function to compare optional APInts: (a) if X and Y both exist, return min(X, Y), (b) if neither X nor Y exist, return None, (c) if exactly one of X and Y exists, return that value. More...

static Optional< APInt >	TruncIfPossible (Optional< APInt > X, unsigned BitWidth)
	Helper function to truncate an optional APInt to a given BitWidth. More...

static Optional< APInt >	SolveQuadraticAddRecExact (const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
	Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations. More...

static Optional< APInt >	SolveQuadraticAddRecRange (const SCEVAddRecExpr *AddRec, const ConstantRange &Range, ScalarEvolution &SE)
	Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations. More...

static bool	HasSameValue (const SCEV A, const SCEV B)
	SCEV structural equivalence is usually sufficient for testing whether two expressions are equal, however for the purposes of looking for a condition guarding a loop, it can be useful to be a little more general, since a front-end may have replicated the controlling expression. More...

static const SCEV *	MatchNotExpr (const SCEV *Expr)
	If Expr computes ~A, return A else return nullptr. More...

template<typename MaxExprType >
static bool	IsMaxConsistingOf (const SCEV MaybeMaxExpr, const SCEV Candidate)
	Is MaybeMaxExpr an SMax or UMax of Candidate and some other values? More...

template<typename MaxExprType >
static bool	IsMinConsistingOf (ScalarEvolution &SE, const SCEV MaybeMinExpr, const SCEV Candidate)
	Is MaybeMinExpr an SMin or UMin of Candidate and some other values? More...

static bool	IsKnownPredicateViaAddRecStart (ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV LHS, const SCEV RHS)

static bool	IsKnownPredicateViaMinOrMax (ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV LHS, const SCEV RHS)
	Is LHS `Pred` RHS true on the virtue of LHS or RHS being a Min or Max expression? More...

static bool	containsUndefs (const SCEV *S)

static bool	findArrayDimensionsRec (ScalarEvolution &SE, SmallVectorImpl< const SCEV > &Terms, SmallVectorImpl< const SCEV > &Sizes)

static bool	containsParameters (SmallVectorImpl< const SCEV *> &Terms)

static int	numberOfTerms (const SCEV *S)

static const SCEV *	removeConstantFactors (ScalarEvolution &SE, const SCEV *T)

static void	PrintLoopInfo (raw_ostream &OS, ScalarEvolution SE, const Loop L)

static StringRef	loopDispositionToStr (ScalarEvolution::LoopDisposition LD)

	INITIALIZE_PASS_BEGIN (ScalarEvolutionWrapperPass, "scalar-evolution", "Scalar Evolution Analysis", false, true) INITIALIZE_PASS_END(ScalarEvolutionWrapperPass

Variables
static cl::opt< unsigned >	MaxBruteForceIterations ("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))

static cl::opt< bool >	VerifySCEV ("verify-scev", cl::Hidden, cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))

static cl::opt< bool >	VerifySCEVMap ("verify-scev-maps", cl::Hidden, cl::desc("Verify no dangling value in ScalarEvolution's " "ExprValueMap (slow)"))

static cl::opt< bool >	VerifyIR ("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))

static cl::opt< unsigned >	MulOpsInlineThreshold ("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))

static cl::opt< unsigned >	AddOpsInlineThreshold ("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))

static cl::opt< unsigned >	MaxSCEVCompareDepth ("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))

static cl::opt< unsigned >	MaxSCEVOperationsImplicationDepth ("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))

static cl::opt< unsigned >	MaxValueCompareDepth ("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))

static cl::opt< unsigned >	MaxArithDepth ("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))

static cl::opt< unsigned >	MaxConstantEvolvingDepth ("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))

static cl::opt< unsigned >	MaxExtDepth ("scalar-evolution-max-ext-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt"), cl::init(8))

static cl::opt< unsigned >	MaxAddRecSize ("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))

scalar	evolution

scalar Scalar Evolution	Analysis

scalar Scalar Evolution	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "scalar-evolution"

Definition at line 139 of file ScalarEvolution.cpp.

Function Documentation

◆ BinomialCoefficient()

static const SCEV* BinomialCoefficient	(	const SCEV *	It,
		unsigned	K,
		ScalarEvolution &	SE,
		Type *	ResultTy
	)

static

◆ BrPHIToSelect()

static bool BrPHIToSelect	(	DominatorTree &	DT,
		BranchInst *	BI,
		PHINode *	Merge,
		Value *&	C,
		Value *&	LHS,
		Value *&	RHS
	)

static

Definition at line 5250 of file ScalarEvolution.cpp.

References llvm::all_of(), assert(), llvm::PHINode::blocks(), C, llvm::computeKnownBits(), llvm::KnownBits::countMinTrailingZeros(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), E, GEP, llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getNumIncomingValues(), llvm::User::getOperandUse(), llvm::Instruction::getParent(), llvm::GEPOperator::getSourceElementType(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::GEPOperator::idx_begin(), llvm::GEPOperator::idx_end(), IsAvailableOnEntry(), llvm::Type::isSized(), llvm::SCEV::isZero(), LLVM_FALLTHROUGH, llvm::AArch64CC::LS, llvm::SmallVectorTemplateBase< T >::push_back(), RA, llvm::SimplifyInstruction(), and std::swap().

◆ BuildConstantFromSCEV()

static Constant* BuildConstantFromSCEV ( const SCEV * V )

static

This builds up a Constant using the ConstantExpr interface.

That way, we will return Constants for objects which aren't represented by a SCEVConstant, because SCEVConstant is restricted to ConstantInt. Returns NULL if the SCEV isn't representable as a Constant.

Definition at line 7988 of file ScalarEvolution.cpp.

◆ canConstantEvolve()

static bool canConstantEvolve	(	Instruction *	I,
		const Loop *	L
	)

static

Determine whether this instruction can constant evolve within this loop assuming its operands can all constant evolve.

Definition at line 7665 of file ScalarEvolution.cpp.

References CanConstantFold(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::LoopBase< BlockT, LoopT >::getHeader(), and llvm::Instruction::getParent().

Referenced by EvaluateExpression(), getConstantEvolvingPHI(), and getConstantEvolvingPHIOperands().

◆ CanConstantFold()

static bool CanConstantFold ( const Instruction * I )

static

Return true if we can constant fold an instruction of the specified type, assuming that all operands were constants.

Definition at line 7651 of file ScalarEvolution.cpp.

References llvm::canConstantFoldCallTo(), and F().

Referenced by BuildConstantFromSCEV(), and canConstantEvolve().

◆ Choose()

static uint64_t Choose	(	uint64_t	n,
		uint64_t	k,
		bool &	Overflow
	)

static

Compute the result of "n choose k", the binomial coefficient.

If an intermediate computation overflows, Overflow will be set and the return will be garbage. Overflow is not cleared on absence of overflow.

Definition at line 2821 of file ScalarEvolution.cpp.

References umul_ov().

Referenced by llvm::ScalarEvolution::getMulExpr().

◆ CollectAddOperandsWithScales()

static bool CollectAddOperandsWithScales	(	DenseMap< const SCEV *, APInt > &	M,
		SmallVectorImpl< const SCEV *> &	NewOps,
		APInt &	AccumulatedConstant,
		const SCEV const	Ops,
		size_t	NumOperands,
		const APInt &	Scale,
		ScalarEvolution &	SE
	)

static

Process the given Ops list, which is a list of operands to be added under the given scale, update the given map.

This is a helper function for getAddRecExpr. As an example of what it does, given a sequence of operands that would form an add expression like this:

m + n + 13 + (A * (o + p + (B * (q + m + 29)))) + r + (-1 * r)

where A and B are constants, update the map with these values:

(m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0)

and add 13 + A*B*29 to AccumulatedConstant. This will allow getAddRecExpr to produce this:

13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B)

This form often exposes folding opportunities that are hidden in the original operand list.

Return true iff it appears that any interesting folding opportunities may be exposed. This helps getAddRecExpr short-circuit extra work in the common case where no interesting opportunities are present, and is also used as a check to avoid infinite recursion.

Definition at line 2228 of file ScalarEvolution.cpp.

References llvm::MCID::Add, C, llvm::dyn_cast(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by llvm::ScalarEvolution::getAddExpr().

◆ CompareSCEVComplexity()

static int CompareSCEVComplexity	(	EquivalenceClasses< const SCEV *> &	EqCacheSCEV,
		EquivalenceClasses< const Value *> &	EqCacheValue,
		const LoopInfo *const	LI,
		const SCEV *	LHS,
		const SCEV *	RHS,
		DominatorTree &	DT,
		unsigned	Depth = `0`
	)

static

Definition at line 633 of file ScalarEvolution.cpp.

References assert(), CompareValueComplexity(), llvm::Depth, llvm::DominatorTree::dominates(), llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), llvm::SCEVUDivExpr::getLHS(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVCastExpr::getOperand(), llvm::SCEVNAryExpr::getOperand(), llvm::SCEVUDivExpr::getRHS(), llvm::SCEV::getSCEVType(), llvm::SCEVUnknown::getValue(), llvm::EquivalenceClasses< ElemTy >::isEquivalent(), llvm_unreachable, MaxSCEVCompareDepth, RA, llvm::scAddExpr, llvm::scAddRecExpr, llvm::scConstant, llvm::scCouldNotCompute, llvm::scMulExpr, llvm::scSignExtend, llvm::scSMaxExpr, llvm::scTruncate, llvm::scUDivExpr, llvm::scUMaxExpr, llvm::scUnknown, llvm::scZeroExtend, llvm::EquivalenceClasses< ElemTy >::unionSets(), and X.

Referenced by GroupByComplexity().

◆ CompareValueComplexity()

static int CompareValueComplexity	(	EquivalenceClasses< const Value *> &	EqCacheValue,
		const LoopInfo *const	LI,
		Value *	LV,
		Value *	RV,
		unsigned	Depth
	)

static

Compare the two values LV and RV in terms of their "complexity" where "complexity" is a partial (and somewhat ad-hoc) relation used to order operands in SCEV expressions.

EqCache is a set of pairs of values that have been previously deemed to be "equally complex" by this routine. It is intended to avoid exponential time complexity in cases like:

a = f(x, y) b = f(a, a) c = f(b, b)

d = f(x, y) e = f(d, d) f = f(e, e)

CompareValueComplexity(f, c)

Since we do not continue running this routine on expression trees once we have seen unequal values, there is no need to track them in the cache.

Definition at line 556 of file ScalarEvolution.cpp.

References llvm::LoopInfoBase< BlockT, LoopT >::getLoopDepth(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Value::getType(), llvm::Value::getValueID(), llvm::EquivalenceClasses< ElemTy >::isEquivalent(), llvm::GlobalValue::isInternalLinkage(), llvm::Type::isPointerTy(), llvm::GlobalValue::isPrivateLinkage(), llvm::AArch64CC::LT, MaxValueCompareDepth, RA, llvm::seq(), and llvm::EquivalenceClasses< ElemTy >::unionSets().

Referenced by CompareSCEVComplexity().

◆ containsConstantInAddMulChain()

static bool containsConstantInAddMulChain ( const SCEV * StartExpr )

static

Determine if any of the operands in this SCEV are a constant or if any of the add or multiply expressions in this SCEV contain a constant.

Definition at line 2846 of file ScalarEvolution.cpp.

References F(), llvm::ARM_MB::ST, and llvm::SCEVTraversal< SV >::visitAll().

Referenced by llvm::ScalarEvolution::getMulExpr().

◆ containsParameters()

static bool containsParameters ( SmallVectorImpl< const SCEV *> & Terms )

inlinestatic

Definition at line 11014 of file ScalarEvolution.cpp.

References llvm::SCEVExprContains().

Referenced by llvm::ScalarEvolution::findArrayDimensions().

◆ containsUndefs()

static bool containsUndefs ( const SCEV * S )

inlinestatic

Definition at line 10805 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVUnknown::getValue(), llvm::SCEVCastExpr::Op, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::PPCISD::SC, llvm::SCEVExprContains(), llvm::SmallVectorBase::size(), llvm::Unknown, and llvm::visitAll().

Referenced by llvm::ScalarEvolution::verify().

◆ EvaluateConstantChrecAtConstant()

static ConstantInt* EvaluateConstantChrecAtConstant	(	const SCEVAddRecExpr *	AddRec,
		ConstantInt *	C,
		ScalarEvolution &	SE
	)

static

Definition at line 7419 of file ScalarEvolution.cpp.

References assert(), llvm::computeKnownBits(), llvm::ConstantFoldCompareInstOperands(), llvm::ConstantFoldLoadThroughGEPIndices(), llvm::dyn_cast(), llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::ConstantInt::get(), getConstant(), llvm::ScalarEvolution::getConstant(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::ConstantExpr::getICmp(), llvm::PHINode::getIncomingValueForBlock(), llvm::GlobalVariable::getInitializer(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPredecessor(), llvm::User::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::User::getOperand(), llvm::BasicBlock::getTerminator(), llvm::SCEVNAryExpr::getType(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), llvm::GlobalVariable::hasDefinitiveInitializer(), llvm::Optional< T >::hasValue(), llvm::SCEVAddRecExpr::isAffine(), llvm::GlobalVariable::isConstant(), isLoopInvariant(), llvm::KnownBits::isNegative(), llvm::KnownBits::isNonNegative(), llvm::APInt::isStrictlyPositive(), llvm::LoadInst::isVolatile(), llvm_unreachable, llvm::PatternMatch::m_AShr(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), MaxBruteForceIterations, and llvm::SCEVCastExpr::Ty.

Referenced by llvm::SCEVAddRecExpr::getNumIterationsInRange(), SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().

◆ EvaluateExpression()

static Constant* EvaluateExpression	(	Value *	V,
		const Loop *	L,
		DenseMap< Instruction , Constant > &	Vals,
		const DataLayout &	DL,
		const TargetLibraryInfo *	TLI
	)

static

EvaluateExpression - Given an expression that passes the getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node in the loop has the value PHIVal.

If we can't fold this expression for some reason, return null.

Definition at line 7741 of file ScalarEvolution.cpp.

References C, canConstantEvolve(), llvm::ConstantFoldCompareInstOperands(), llvm::ConstantFoldInstOperands(), llvm::ConstantFoldLoadFromConstPtr(), llvm::dyn_cast(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Value::getType(), llvm::LoadInst::isVolatile(), and llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup().

Referenced by llvm::FileCheckPattern::getCount(), and getOtherIncomingValue().

◆ extractConstantWithoutWrapping() [1/2]

static APInt extractConstantWithoutWrapping	(	ScalarEvolution &	SE,
		const SCEVConstant *	ConstantTerm,
		const SCEVAddExpr *	WholeAddExpr
	)

static

Definition at line 1565 of file ScalarEvolution.cpp.

References C, E, llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), llvm::ScalarEvolution::GetMinTrailingZeros(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), I, llvm::APInt::trunc(), and llvm::APInt::zext().

Referenced by llvm::ScalarEvolution::getSignExtendExpr(), and llvm::ScalarEvolution::getZeroExtendExpr().

◆ extractConstantWithoutWrapping() [2/2]

static APInt extractConstantWithoutWrapping	(	ScalarEvolution &	SE,
		const APInt &	ConstantStart,
		const SCEV *	Step
	)

static

Definition at line 1586 of file ScalarEvolution.cpp.

References llvm::APInt::getBitWidth(), llvm::ScalarEvolution::GetMinTrailingZeros(), llvm::APInt::trunc(), and llvm::APInt::zext().

◆ findArrayDimensionsRec()

static bool findArrayDimensionsRec	(	ScalarEvolution &	SE,
		SmallVectorImpl< const SCEV *> &	Terms,
		SmallVectorImpl< const SCEV *> &	Sizes
	)

static

Definition at line 10967 of file ScalarEvolution.cpp.

References E, llvm::ScalarEvolution::getMulExpr(), llvm::SCEV::isZero(), llvm::SCEVCastExpr::Op, llvm::SmallVectorTemplateBase< T >::push_back(), llvm::remove_if(), and llvm::SmallVectorBase::size().

Referenced by llvm::ScalarEvolution::findArrayDimensions().

◆ gcd()

static const APInt gcd	(	const SCEVConstant *	C1,
		const SCEVConstant *	C2
	)

static

Definition at line 3278 of file ScalarEvolution.cpp.

References llvm::APInt::abs(), B, llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), llvm::APIntOps::GreatestCommonDivisor(), and llvm::APInt::zext().

Referenced by llvm::ScalarEvolution::getUDivExactExpr().

◆ getConstantEvolvingPHI()

static PHINode* getConstantEvolvingPHI	(	Value *	V,
		const Loop *	L
	)

static

getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node in the loop that V is derived from.

We allow arbitrary operations along the way, but the operands of an operation must either be constants or a value derived from a constant PHI. If this expression does not fit with these constraints, return null.

Definition at line 7725 of file ScalarEvolution.cpp.

References canConstantEvolve(), llvm::dyn_cast(), and getConstantEvolvingPHIOperands().

Referenced by getOtherIncomingValue().

◆ getConstantEvolvingPHIOperands()

static PHINode* getConstantEvolvingPHIOperands	(	Instruction *	UseInst,
		const Loop *	L,
		DenseMap< Instruction , PHINode > &	PHIMap,
		unsigned	Depth
	)

static

getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by recursing through each instruction operand until reaching a loop header phi.

Definition at line 7683 of file ScalarEvolution.cpp.

References canConstantEvolve(), llvm::dyn_cast(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), MaxConstantEvolvingDepth, llvm::SCEVCastExpr::Op, llvm::User::operands(), and P.

Referenced by getConstantEvolvingPHI().

◆ getConstantTripCount()

static unsigned getConstantTripCount ( const SCEVConstant * ExitCount )

static

Definition at line 6499 of file ScalarEvolution.cpp.

References llvm::APInt::getActiveBits(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), and llvm::ConstantInt::getZExtValue().

Referenced by llvm::ScalarEvolution::getSmallConstantMaxTripCount(), and llvm::ScalarEvolution::getSmallConstantTripCount().

◆ getExtendAddRecStart()

template<typename ExtendOpTy >

static const SCEV* getExtendAddRecStart	(	const SCEVAddRecExpr *	AR,
		Type *	Ty,
		ScalarEvolution *	SE,
		unsigned	Depth
	)

static

Definition at line 1471 of file ScalarEvolution.cpp.

References llvm::Depth, and llvm::SCEVCastExpr::Ty.

◆ getOtherIncomingValue()

static Constant* getOtherIncomingValue	(	PHINode *	PN,
		BasicBlock *	BB
	)

static

◆ getPreStartForExtend()

template<typename ExtendOpTy >

static const SCEV* getPreStartForExtend	(	const SCEVAddRecExpr *	AR,
		Type *	Ty,
		ScalarEvolution *	SE,
		unsigned	Depth
	)

static

Definition at line 1397 of file ScalarEvolution.cpp.

References llvm::SCEVAddRecExpr::getLoop().

◆ GetQuadraticEquation()

static Optional<std::tuple<APInt, APInt, APInt, APInt, unsigned> > GetQuadraticEquation ( const SCEVAddRecExpr * AddRec )

static

For a given quadratic addrec, generate coefficients of the corresponding quadratic equation, multiplied by a common value to ensure that they are integers.

The returned value is a tuple { A, B, C, M, BitWidth }, where Ax^2 + Bx + C is the quadratic function, M is the value that A, B and C were multiplied by, and BitWidth is the bit width of the original addrec coefficients. This function returns None if the addrec coefficients are not compile- time constants.

Definition at line 8362 of file ScalarEvolution.cpp.

References assert(), B, C, llvm::dbgs(), llvm::dyn_cast(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::APInt::isNullValue(), LLVM_DEBUG, N, NC, llvm::None, and llvm::APInt::sext().

Referenced by SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().

◆ getRangeForAffineARHelper()

static ConstantRange getRangeForAffineARHelper	(	APInt	Step,
		const ConstantRange &	StartRange,
		const APInt &	MaxBECount,
		unsigned	BitWidth,
		bool	Signed
	)

static

Definition at line 5741 of file ScalarEvolution.cpp.

◆ GetRangeFromMetadata()

static Optional<ConstantRange> GetRangeFromMetadata ( Value * V )

static

Helper method to assign a range to V from metadata present in the IR.

Definition at line 5537 of file ScalarEvolution.cpp.

◆ getSignedOverflowLimitForStep()

static const SCEV* getSignedOverflowLimitForStep	(	const SCEV *	Step,
		ICmpInst::Predicate *	Pred,
		ScalarEvolution *	SE
	)

static

Definition at line 1305 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getConstant(), llvm::APInt::getSignedMaxValue(), llvm::APInt::getSignedMinValue(), llvm::ScalarEvolution::getSignedRangeMax(), llvm::ScalarEvolution::getSignedRangeMin(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::ScalarEvolution::isKnownNegative(), and llvm::ScalarEvolution::isKnownPositive().

Referenced by llvm::ScalarEvolution::getSignExtendExpr(), and getUnsignedOverflowLimitForStep().

◆ getUnsignedOverflowLimitForStep()

static const SCEV* getUnsignedOverflowLimitForStep	(	const SCEV *	Step,
		ICmpInst::Predicate *	Pred,
		ScalarEvolution *	SE
	)

static

Definition at line 1325 of file ScalarEvolution.cpp.

References llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::ScalarEvolution::getConstant(), llvm::APInt::getMinValue(), getSignedOverflowLimitForStep(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::getUnsignedRangeMax(), llvm::ScalarEvolution::getZeroExtendExpr(), and llvm::CmpInst::ICMP_ULT.

◆ GroupByComplexity()

static void GroupByComplexity	(	SmallVectorImpl< const SCEV *> &	Ops,
		LoopInfo *	LI,
		DominatorTree &	DT
	)

static

Given a list of SCEV objects, order them by their complexity, and group objects of the same complexity together by value.

When this routine is finished, we know that any duplicates in the vector are consecutive and that complexity is monotonically increasing.

Note that we go take special precautions to ensure that we get deterministic results from this routine. In other words, we don't want the results of this to depend on where the addresses of various SCEV objects happened to land in memory.

Definition at line 782 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateCommon< T >::begin(), CompareSCEVComplexity(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SCEV::getSCEVType(), llvm::SmallVectorBase::size(), and std::swap().

Referenced by llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getSMaxExpr(), and llvm::ScalarEvolution::getUMaxExpr().

◆ HasSameValue()

static bool HasSameValue	(	const SCEV *	A,
		const SCEV *	B
	)

static

SCEV structural equivalence is usually sufficient for testing whether two expressions are equal, however for the purposes of looking for a condition guarding a loop, it can be useful to be a little more general, since a front-end may have replicated the controlling expression.

Definition at line 8790 of file ScalarEvolution.cpp.

References B, and llvm::Instruction::isIdenticalTo().

Referenced by IsKnownPredicateViaMinOrMax(), llvm::ScalarEvolution::isLoopInvariantPredicate(), and llvm::ScalarEvolution::SimplifyICmpOperands().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	ScalarEvolutionWrapperPass	,
		"scalar-evolution"	,
		"Scalar Evolution Analysis"	,
		false	,
		true
	)

Referenced by llvm::ScalarEvolutionPrinterPass::run().

◆ IsAvailableOnEntry()

static bool IsAvailableOnEntry	(	const Loop *	L,
		DominatorTree &	DT,
		const SCEV *	S,
		BasicBlock *	BB
	)

static

◆ isIntegerLoopHeaderPHI()

static const Loop* isIntegerLoopHeaderPHI	(	const PHINode *	PN,
		LoopInfo &	LI
	)

static

◆ IsKnownPredicateViaAddRecStart()

static bool IsKnownPredicateViaAddRecStart	(	ScalarEvolution &	SE,
		ICmpInst::Predicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS
	)

static

Definition at line 10085 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVAddRecExpr::isAffine(), llvm::ScalarEvolution::isKnownPredicate(), llvm::ICmpInst::isRelational(), and llvm::CmpInst::isSigned().

Referenced by IsKnownPredicateViaMinOrMax().

◆ IsKnownPredicateViaMinOrMax()

static bool IsKnownPredicateViaMinOrMax	(	ScalarEvolution &	SE,
		ICmpInst::Predicate	Pred,
		const SCEV *	LHS,
		const SCEV *	RHS
	)

static

Is LHS Pred RHS true on the virtue of LHS or RHS being a Min or Max expression?

Definition at line 10119 of file ScalarEvolution.cpp.

◆ IsMaxConsistingOf()

template<typename MaxExprType >

static bool IsMaxConsistingOf	(	const SCEV *	MaybeMaxExpr,
		const SCEV *	Candidate
	)

static

Is MaybeMaxExpr an SMax or UMax of Candidate and some other values?

Definition at line 10065 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), and llvm::find().

◆ IsMinConsistingOf()

template<typename MaxExprType >

static bool IsMinConsistingOf	(	ScalarEvolution &	SE,
		const SCEV *	MaybeMinExpr,
		const SCEV *	Candidate
	)

static

Is MaybeMinExpr an SMin or UMin of Candidate and some other values?

Definition at line 10075 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getNotSCEV(), and MatchNotExpr().

◆ isSimpleCastedPHI()

static Type* isSimpleCastedPHI	(	const SCEV *	Op,
		const SCEVUnknown *	SymbolicPHI,
		bool &	Signed,
		ScalarEvolution &	SE
	)

static

Helper function to createAddRecFromPHIWithCasts.

We have a phi node whose symbolic (unknown) SCEV is SymbolicPHI, which is updated via the loop backedge by a SCEVAddExpr, possibly also with a few casts on the way. This function checks if Op, an operand of this SCEVAddExpr, follows one of the following patterns: Op == (SExt ix (Trunc iy (SymbolicPHI) to ix) to iy) Op == (ZExt ix (Trunc iy (SymbolicPHI) to ix) to iy) If the SCEV expression of Op conforms with one of the expected patterns we return the type of the truncation operation, and indicate whether the truncated type should be treated as signed/unsigned by setting Signed to true/false, respectively.

Definition at line 4599 of file ScalarEvolution.cpp.

References llvm::dyn_cast(), llvm::SCEVCastExpr::getOperand(), llvm::SCEVCastExpr::getType(), llvm::SCEV::getType(), llvm::SCEVUnknown::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::SCEVCastExpr::Op, and X.

Referenced by isIntegerLoopHeaderPHI().

◆ loopDispositionToStr()

static StringRef loopDispositionToStr ( ScalarEvolution::LoopDisposition LD )

static

Definition at line 11453 of file ScalarEvolution.cpp.

References llvm_unreachable, llvm::ScalarEvolution::LoopComputable, llvm::ScalarEvolution::LoopInvariant, and llvm::ScalarEvolution::LoopVariant.

Referenced by llvm::ScalarEvolution::print().

◆ MatchBinaryOp()

static Optional<BinaryOp> MatchBinaryOp	(	Value *	V,
		DominatorTree &	DT
	)

static

Try to map V into a BinaryOp, and return None on failure.

Definition at line 4481 of file ScalarEvolution.cpp.

References llvm::MCID::Add, llvm::dyn_cast(), F(), llvm::ConstantInt::get(), getBitWidth(), llvm::APInt::getOneBitSet(), llvm::SCEV::getType(), llvm::isOverflowIntrinsicNoWrap(), llvm::None, llvm::SCEVCastExpr::Op, llvm::Intrinsic::sadd_with_overflow, llvm::Intrinsic::smul_with_overflow, llvm::Intrinsic::ssub_with_overflow, llvm::Intrinsic::uadd_with_overflow, llvm::Intrinsic::umul_with_overflow, llvm::Intrinsic::usub_with_overflow, and X.

Referenced by llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds(), and getRangeForAffineARHelper().

◆ MatchNotExpr()

static const SCEV* MatchNotExpr ( const SCEV * Expr )

static

If Expr computes ~A, return A else return nullptr.

Definition at line 10049 of file ScalarEvolution.cpp.

References llvm::MCID::Add, llvm::dyn_cast(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), and llvm::SCEV::isAllOnesValue().

Referenced by IsMinConsistingOf().

◆ MinOptional()

static Optional<APInt> MinOptional	(	Optional< APInt >	X,
		Optional< APInt >	Y
	)

static

Helper function to compare optional APInts: (a) if X and Y both exist, return min(X, Y), (b) if neither X nor Y exist, return None, (c) if exactly one of X and Y exists, return that value.

Definition at line 8415 of file ScalarEvolution.cpp.

References llvm::APInt::getBitWidth(), llvm::Optional< T >::hasValue(), llvm::max(), llvm::None, llvm::APInt::sextOrSelf(), llvm::APInt::slt(), llvm::RISCVFenceField::W, X, and Y.

Referenced by SolveQuadraticAddRecRange().

◆ numberOfTerms()

static int numberOfTerms ( const SCEV * S )

inlinestatic

Definition at line 11022 of file ScalarEvolution.cpp.

Referenced by llvm::ScalarEvolution::findArrayDimensions().

◆ PrintLoopInfo()

static void PrintLoopInfo	(	raw_ostream &	OS,
		ScalarEvolution *	SE,
		const Loop *	L
	)

static

Definition at line 11395 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::ScalarEvolution::getMaxBackedgeTakenCount(), llvm::ScalarEvolution::getPredicatedBackedgeTakenCount(), llvm::ScalarEvolution::getSmallConstantTripMultiple(), llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount(), llvm::ScalarEvolution::isBackedgeTakenCountMaxOrZero(), llvm::SCEVUnionPredicate::print(), and llvm::SmallVectorBase::size().

Referenced by llvm::ScalarEvolution::print().

◆ PushDefUseChildren()

static void PushDefUseChildren	(	Instruction *	I,
		SmallVectorImpl< Instruction *> &	Worklist
	)

static

Push users of the given Instruction onto the given Worklist.

Definition at line 4167 of file ScalarEvolution.cpp.

References llvm::MCID::Add, assert(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SelectInst::getCondition(), llvm::BranchInst::getCondition(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::SelectInst::getFalseValue(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Type::getInt1Ty(), llvm::SCEVAddRecExpr::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::ScalarEvolution::getMinusSCEV(), llvm::Operator::getOpcode(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::SCEVAddRecExpr::getPostIncExpr(), llvm::ScalarEvolution::getSCEV(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::BranchInst::getSuccessor(), llvm::SelectInst::getTrueValue(), llvm::Optional< T >::getValue(), llvm::SCEVUnknown::getValue(), llvm::SCEVNAryExpr::hasNoSignedWrap(), llvm::SCEVNAryExpr::hasNoUnsignedWrap(), llvm::Optional< T >::hasValue(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SCEVAddRecExpr::isAffine(), llvm::BranchInst::isConditional(), llvm::ScalarEvolution::isLoopInvariant(), llvm::ConstantRange::makeGuaranteedNoWrapRegion(), llvm::None, llvm::SCEVCastExpr::Op, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), Rewriter, llvm::MCID::Select, llvm::ScalarEvolution::setFlags(), SI, and llvm::Value::users().

Referenced by llvm::ScalarEvolution::forgetLoop(), and llvm::ScalarEvolution::forgetValue().

◆ PushLoopPHIs()

static void PushLoopPHIs	(	const Loop *	L,
		SmallVectorImpl< Instruction *> &	Worklist
	)

static

Push PHI nodes in the header of the given loop onto the given Worklist.

Definition at line 6619 of file ScalarEvolution.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallVectorBase::empty(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::Instruction::getParent(), llvm::SmallPtrSetImpl< PtrType >::insert(), isLoopInvariant(), llvm::BasicBlock::phis(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::Value::users().

Referenced by llvm::ScalarEvolution::forgetLoop().

◆ removeConstantFactors()

static const SCEV* removeConstantFactors	(	ScalarEvolution &	SE,
		const SCEV *	T
	)

static

Definition at line 11028 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getMulExpr(), llvm::SCEVCastExpr::Op, llvm::SmallVectorTemplateBase< T >::push_back(), and T.

Referenced by llvm::ScalarEvolution::findArrayDimensions().

◆ SCEVLostPoisonFlags()

static bool SCEVLostPoisonFlags	(	const SCEV *	S,
		const Value *	V
	)

static

Check whether value has nuw/nsw/exact set but SCEV does not.

TODO: In reality it is better to check the poison recursevely but this is better than nothing.

Definition at line 3897 of file ScalarEvolution.cpp.

References I.

Referenced by llvm::ScalarEvolution::getSCEV().

◆ sizeOfSCEV()

static int sizeOfSCEV ( const SCEV * S )

inlinestatic

Definition at line 826 of file ScalarEvolution.cpp.

References assert(), D, F(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), llvm::ScalarEvolution::getConstant(), llvm::SCEVAddRecExpr::getLoop(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::ScalarEvolution::getOne(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEV::getType(), llvm::ScalarEvolution::getZero(), llvm::SCEVAddRecExpr::isAffine(), llvm::SCEV::isOne(), llvm::SCEV::isZero(), llvm::SCEVCastExpr::Op, llvm::SCEVNAryExpr::operands(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SCEVParameterRewriter::rewrite(), llvm::APInt::sdivrem(), llvm::APInt::sext(), Size, llvm::SmallVectorBase::size(), llvm::ARM_MB::ST, llvm::SCEVCastExpr::Ty, and llvm::SCEVTraversal< SV >::visitAll().

◆ SolveLinEquationWithOverflow()

static const SCEV* SolveLinEquationWithOverflow	(	const APInt &	A,
		const SCEV *	B,
		ScalarEvolution &	SE
	)

static

Finds the minimum unsigned root of the following equation:

A * X = B (mod N)

where N = 2^BW and BW is the common bit width of A and B. The signedness of A and B isn't important.

If the equation does not have a solution, SCEVCouldNotCompute is returned.

Definition at line 8313 of file ScalarEvolution.cpp.

References assert(), llvm::APInt::countTrailingZeros(), D, llvm::APInt::getBitWidth(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::ScalarEvolution::GetMinTrailingZeros(), llvm::ScalarEvolution::getMulExpr(), llvm::APInt::getOneBitSet(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::getUDivExactExpr(), llvm::APInt::lshr(), llvm::Mod, llvm::APInt::multiplicativeInverse(), llvm::APInt::setBit(), llvm::APInt::trunc(), and llvm::APInt::zext().

◆ SolveQuadraticAddRecExact()

static Optional<APInt> SolveQuadraticAddRecExact	(	const SCEVAddRecExpr *	AddRec,
		ScalarEvolution &	SE
	)

static

Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n iterations.

The values L, M, N are assumed to be signed, and they should all have the same bit widths. Find the least n >= 0 such that c(n) = 0 in the arithmetic modulo 2^BW, where BW is the bit width of the addrec's coefficients. If the calculated value is a BW-bit integer (for BW > 1), it will be returned as such, otherwise the bit width of the returned value may be greater than BW.

This function returns None if (a) the addrec coefficients are not constant, or (b) SolveQuadraticEquationWrap was unable to find a solution. For cases like x^2 = 5, no integer solutions exist, in other cases an integer solution may exist, but SolveQuadraticEquationWrap may fail to find it.

Definition at line 8462 of file ScalarEvolution.cpp.

References B, C, llvm::dbgs(), EvaluateConstantChrecAtConstant(), llvm::ConstantInt::get(), llvm::ScalarEvolution::getContext(), GetQuadraticEquation(), llvm::Optional< T >::hasValue(), LLVM_DEBUG, llvm::None, llvm::APIntOps::SolveQuadraticEquationWrap(), T, TruncIfPossible(), and X.

Referenced by SolveQuadraticAddRecRange().

◆ SolveQuadraticAddRecRange()

static Optional<APInt> SolveQuadraticAddRecRange	(	const SCEVAddRecExpr *	AddRec,
		const ConstantRange &	Range,
		ScalarEvolution &	SE
	)

static

Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n iterations.

The values M, N are assumed to be signed, and they should all have the same bit widths. Find the least n such that c(n) does not belong to the given range, while c(n-1) does.

This function returns None if (a) the addrec coefficients are not constant, or (b) SolveQuadraticEquationWrap was unable to find a solution for the bounds of the range.

Definition at line 8494 of file ScalarEvolution.cpp.

References assert(), B, C, llvm::ConstantRange::contains(), llvm::dbgs(), llvm::dyn_cast(), EvaluateConstantChrecAtConstant(), llvm::ConstantInt::get(), llvm::SCEVConstant::getAPInt(), llvm::APInt::getBitWidth(), getConstant(), llvm::ScalarEvolution::getContext(), llvm::SCEVAddRecExpr::getLoop(), llvm::ConstantRange::getLower(), llvm::SCEVNAryExpr::getOperand(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), GetQuadraticEquation(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVNAryExpr::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ConstantRange::getUpper(), llvm::Optional< T >::hasValue(), llvm::SCEVAddRecExpr::isAffine(), llvm::Type::isIntegerTy(), llvm::APInt::isNegative(), llvm::SCEVAddRecExpr::isQuadratic(), llvm::SCEV::isZero(), LLVM_DEBUG, llvm::Lower, MinOptional(), llvm::None, llvm::APInt::sextOrSelf(), SolveQuadraticAddRecExact(), llvm::APIntOps::SolveQuadraticEquationWrap(), T, TruncIfPossible(), llvm::Upper, and X.

Referenced by llvm::SCEVAddRecExpr::getNumIterationsInRange().

◆ splitAddExpr()

static std::pair<const SCEV *, ConstantInt *> splitAddExpr ( const SCEV * S )

static

Try to split a SCEVAddExpr into a pair of {SCEV, ConstantInt}.

If S is a SCEVAddExpr and is composed of a sub SCEV S' and an offset I, then return {S', I}, else return {S, nullptr}.

Definition at line 3839 of file ScalarEvolution.cpp.

References llvm::MCID::Add, assert(), llvm::dyn_cast(), SI, and VerifySCEVMap.

Referenced by llvm::ScalarEvolution::eraseValueFromMap(), and llvm::ScalarEvolution::getSCEV().

◆ STATISTIC() [1/4]

STATISTIC	(	NumArrayLenItCounts	,
		"Number of trip counts computed with array length"
	)

◆ STATISTIC() [2/4]

STATISTIC	(	NumTripCountsComputed	,
		"Number of loops with predictable loop counts"
	)

◆ STATISTIC() [3/4]

STATISTIC	(	NumTripCountsNotComputed	,
		"Number of loops without predictable loop counts"
	)

◆ STATISTIC() [4/4]

STATISTIC	(	NumBruteForceTripCountsComputed	,
		"Number of loops with trip counts computed by force"
	)

◆ StrengthenNoWrapFlags()

static SCEV::NoWrapFlags StrengthenNoWrapFlags	(	ScalarEvolution *	SE,
		SCEVTypes	Type,
		const SmallVectorImpl< const SCEV *> &	Ops,
		SCEV::NoWrapFlags	Flags
	)

static

◆ TruncIfPossible()

static Optional<APInt> TruncIfPossible	(	Optional< APInt >	X,
		unsigned	BitWidth
	)

static

Helper function to truncate an optional APInt to a given BitWidth.

When solving addrec-related equations, it is preferable to return a value that has the same bit width as the original addrec's coefficients. If the solution fits in the original bit width, truncate it (except for i1). Returning a value of a different bit width may inhibit some optimizations.

In general, a solution to a quadratic equation generated from an addrec may require BW+1 bits, where BW is the bit width of the addrec's coefficients. The reason is that the coefficients of the quadratic equation are BW+1 bits wide (to avoid truncation when converting from the addrec to the equation).

Definition at line 8438 of file ScalarEvolution.cpp.

References llvm::APInt::getBitWidth(), llvm::Optional< T >::hasValue(), llvm::isIntN(), llvm::None, llvm::APInt::trunc(), llvm::RISCVFenceField::W, and X.

Referenced by SolveQuadraticAddRecExact(), and SolveQuadraticAddRecRange().

◆ umul_ov()

static uint64_t umul_ov	(	uint64_t	i,
		uint64_t	j,
		bool &	Overflow
	)

static

Definition at line 2812 of file ScalarEvolution.cpp.

Referenced by Choose(), llvm::ScalarEvolution::getMulExpr(), and llvm::APInt::shl().

Variable Documentation

◆ AddOpsInlineThreshold

cl::opt<unsigned> AddOpsInlineThreshold("scev-addops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining addition operands into a SCEV"), cl::init(500))

static

Referenced by llvm::ScalarEvolution::getAddExpr().

◆ Analysis

scalar Scalar Evolution Analysis

Definition at line 11931 of file ScalarEvolution.cpp.

◆ evolution

scalar evolution

Definition at line 11931 of file ScalarEvolution.cpp.

◆ false

scalar Scalar Evolution false

Definition at line 11931 of file ScalarEvolution.cpp.

◆ MaxAddRecSize

cl::opt<unsigned> MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8))

static

Referenced by llvm::ScalarEvolution::getMulExpr().

◆ MaxArithDepth

cl::opt<unsigned> MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden, cl::desc("Maximum depth of recursive arithmetics"), cl::init(32))

static

Referenced by llvm::ScalarEvolution::getAddExpr(), and llvm::ScalarEvolution::getMulExpr().

◆ MaxBruteForceIterations

cl::opt<unsigned> MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), cl::init(100))

static

Referenced by EvaluateConstantChrecAtConstant(), and getOtherIncomingValue().

◆ MaxConstantEvolvingDepth

cl::opt<unsigned> MaxConstantEvolvingDepth("scalar-evolution-max-constant-evolving-depth", cl::Hidden, cl::desc("Maximum depth of recursive constant evolving"), cl::init(32))

static

Referenced by getConstantEvolvingPHIOperands().

◆ MaxExtDepth

cl::opt<unsigned> MaxExtDepth("scalar-evolution-max-ext-depth", cl::Hidden, cl::desc("Maximum depth of recursive SExt/ZExt"), cl::init(8))

static

Referenced by llvm::ScalarEvolution::getSignExtendExpr(), and llvm::ScalarEvolution::getZeroExtendExpr().

◆ MaxSCEVCompareDepth

cl::opt<unsigned> MaxSCEVCompareDepth("scalar-evolution-max-scev-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV complexity comparisons"), cl::init(32))

static

Referenced by CompareSCEVComplexity().

◆ MaxSCEVOperationsImplicationDepth

cl::opt<unsigned> MaxSCEVOperationsImplicationDepth("scalar-evolution-max-scev-operations-implication-depth", cl::Hidden, cl::desc("Maximum depth of recursive SCEV operations implication analysis"), cl::init(2))

static

Referenced by IsKnownPredicateViaMinOrMax().

◆ MaxValueCompareDepth

cl::opt<unsigned> MaxValueCompareDepth("scalar-evolution-max-value-compare-depth", cl::Hidden, cl::desc("Maximum depth of recursive value complexity comparisons"), cl::init(2))

static

Referenced by CompareValueComplexity().

◆ MulOpsInlineThreshold

cl::opt<unsigned> MulOpsInlineThreshold("scev-mulops-inline-threshold", cl::Hidden, cl::desc("Threshold for inlining multiplication operands into a SCEV"), cl::init(32))

static

Referenced by llvm::ScalarEvolution::getMulExpr().

◆ VerifyIR

cl::opt<bool> VerifyIR("scev-verify-ir", cl::Hidden, cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"), cl::init(false))

static

Referenced by llvm::ScalarEvolution::isLoopBackedgeGuardedByCond(), and llvm::ScalarEvolution::isLoopEntryGuardedByCond().

◆ VerifySCEV

cl::opt<bool> VerifySCEV("verify-scev", cl::Hidden, cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))

static

Referenced by llvm::ScalarEvolutionWrapperPass::verifyAnalysis().

◆ VerifySCEVMap

cl::opt<bool> VerifySCEVMap("verify-scev-maps", cl::Hidden, cl::desc("Verify no dangling value in ScalarEvolution's " "ExprValueMap (slow)"))

static

Referenced by splitAddExpr().

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ BinomialCoefficient()

◆ BrPHIToSelect()

◆ BuildConstantFromSCEV()

◆ canConstantEvolve()

◆ CanConstantFold()

◆ Choose()

◆ CollectAddOperandsWithScales()

◆ CompareSCEVComplexity()

◆ CompareValueComplexity()

◆ containsConstantInAddMulChain()

◆ containsParameters()

◆ containsUndefs()

◆ EvaluateConstantChrecAtConstant()

◆ EvaluateExpression()

◆ extractConstantWithoutWrapping() [1/2]

◆ extractConstantWithoutWrapping() [2/2]

◆ findArrayDimensionsRec()

◆ gcd()

◆ getConstantEvolvingPHI()

◆ getConstantEvolvingPHIOperands()

◆ getConstantTripCount()

◆ getExtendAddRecStart()

◆ getOtherIncomingValue()

◆ getPreStartForExtend()

◆ GetQuadraticEquation()

◆ getRangeForAffineARHelper()

◆ GetRangeFromMetadata()

◆ getSignedOverflowLimitForStep()

◆ getUnsignedOverflowLimitForStep()

◆ GroupByComplexity()

◆ HasSameValue()

◆ INITIALIZE_PASS_BEGIN()

◆ IsAvailableOnEntry()

◆ isIntegerLoopHeaderPHI()

◆ IsKnownPredicateViaAddRecStart()

◆ IsKnownPredicateViaMinOrMax()

◆ IsMaxConsistingOf()

◆ IsMinConsistingOf()

◆ isSimpleCastedPHI()

◆ loopDispositionToStr()

◆ MatchBinaryOp()

◆ MatchNotExpr()

◆ MinOptional()

◆ numberOfTerms()

◆ PrintLoopInfo()

◆ PushDefUseChildren()

◆ PushLoopPHIs()

◆ removeConstantFactors()

◆ SCEVLostPoisonFlags()

◆ sizeOfSCEV()

◆ SolveLinEquationWithOverflow()

◆ SolveQuadraticAddRecExact()

◆ SolveQuadraticAddRecRange()

◆ splitAddExpr()

◆ STATISTIC() [1/4]

◆ STATISTIC() [2/4]

◆ STATISTIC() [3/4]

◆ STATISTIC() [4/4]

◆ StrengthenNoWrapFlags()

◆ TruncIfPossible()

◆ umul_ov()

Variable Documentation

◆ AddOpsInlineThreshold

◆ Analysis

◆ evolution

◆ false

◆ MaxAddRecSize

◆ MaxArithDepth

◆ MaxBruteForceIterations

◆ MaxConstantEvolvingDepth

◆ MaxExtDepth

◆ MaxSCEVCompareDepth

◆ MaxSCEVOperationsImplicationDepth

◆ MaxValueCompareDepth