ScalarEvolution.cpp File Reference

#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionTracker.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.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/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include <algorithm>

Include dependency graph for ScalarEvolution.cpp:

Go to the source code of this file.

Classes
struct	MarkPendingLoopPredicate
Defines
#define	DEBUG_TYPE   "scalar-evolution"
Typedefs
typedef DenseMap< const Loop *, std::string >	VerifyMap
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")
	INITIALIZE_PASS_BEGIN (ScalarEvolution,"scalar-evolution","Scalar Evolution Analysis", false, true) INITIALIZE_PASS_END(ScalarEvolution
static void	GroupByComplexity (SmallVectorImpl< const SCEV * > &Ops, LoopInfo *LI)
static const SCEV *	BinomialCoefficient (const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
static const SCEV *	getOverflowLimitForStep (const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
static const SCEV *	getPreStartForSignExtend (const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE)
static const SCEV *	getSignExtendAddRecStart (const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE)
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 uint64_t	umul_ov (uint64_t i, uint64_t j, bool &Overflow)
static uint64_t	Choose (uint64_t n, uint64_t k, bool &Overflow)
static const APInt	gcd (const SCEVConstant *C1, const SCEVConstant *C2)
static void	PushDefUseChildren (Instruction *I, SmallVectorImpl< Instruction * > &Worklist)
static void	PushLoopPHIs (const Loop *L, SmallVectorImpl< Instruction * > &Worklist)
static ConstantInt *	EvaluateConstantChrecAtConstant (const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static bool	CanConstantFold (const Instruction *I)
static bool	canConstantEvolve (Instruction *I, const Loop *L)
static PHINode *	getConstantEvolvingPHIOperands (Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap)
static PHINode *	getConstantEvolvingPHI (Value *V, const Loop *L)
static Constant *	EvaluateExpression (Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout *DL, const TargetLibraryInfo *TLI)
static Constant *	BuildConstantFromSCEV (const SCEV *V)
static const SCEV *	SolveLinEquationWithOverflow (const APInt &A, const APInt &B, ScalarEvolution &SE)
static std::pair< const SCEV *, const SCEV * >	SolveQuadraticEquation (const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
static bool	HasSameValue (const SCEV *A, const SCEV *B)
static bool	containsUndefs (const SCEV *S)
static const APInt	srem (const SCEVConstant *C1, const SCEVConstant *C2)
static const APInt	sdiv (const SCEVConstant *C1, const SCEVConstant *C2)
static int	sizeOfSCEV (const SCEV *S)
static bool	findArrayDimensionsRec (ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes)
static bool	containsParameters (const SCEV *S)
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 void	replaceSubString (std::string &Str, StringRef From, StringRef To)
	replaceSubString - Replaces all occurrences of From in Str with To.
static void	getLoopBackedgeTakenCounts (Loop *L, VerifyMap &Map, ScalarEvolution &SE)
	getLoopBackedgeTakenCounts - Helper method for verifyAnalysis.
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::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
scalar	evolution
scalar Scalar Evolution	Analysis
scalar Scalar Evolution	false

---

Define Documentation

#define DEBUG_TYPE   "scalar-evolution"

Definition at line 92 of file ScalarEvolution.cpp.

---

Typedef Documentation

typedef DenseMap<const Loop *, std::string> VerifyMap

Definition at line 8028 of file ScalarEvolution.cpp.

---

Function Documentation

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

BinomialCoefficient - Compute BC(It, K). The result has width W. Assume, K > 0.

Definition at line 684 of file ScalarEvolution.cpp.

References llvm::APInt::countTrailingZeros(), llvm::IntegerType::get(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::APInt::getOneBitSet(), llvm::APInt::getSignedMinValue(), llvm::ScalarEvolution::getTruncateOrZeroExtend(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::getUDivExpr(), llvm::APInt::lshr(), llvm::MipsISD::Mult, llvm::APInt::multiplicativeInverse(), T, llvm::APInt::trunc(), and llvm::APInt::zext().

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

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

References llvm::CallingConv::C, llvm::dyn_cast(), llvm::ConstantExpr::getAdd(), llvm::ConstantExpr::getBitCast(), llvm::ConstantExpr::getGetElementPtr(), llvm::Type::getInt32Ty(), llvm::Type::getInt8PtrTy(), llvm::ConstantExpr::getIntegerCast(), llvm::SCEVUDivExpr::getLHS(), llvm::ConstantExpr::getMul(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVCastExpr::getOperand(), llvm::SCEVNAryExpr::getOperand(), llvm::Type::getPointerAddressSpace(), llvm::SCEVUDivExpr::getRHS(), llvm::SCEV::getSCEVType(), llvm::ConstantExpr::getSExt(), llvm::ConstantExpr::getTrunc(), llvm::SCEVCastExpr::getType(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::ConstantExpr::getUDiv(), llvm::ConstantExpr::getZExt(), llvm::Type::isPointerTy(), 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::AArch64DB::ST, and std::swap().

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

static bool CanConstantFold

(

const Instruction *

I

)

[static]

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

Definition at line 4920 of file ScalarEvolution.cpp.

References llvm::canConstantFoldCallTo().

Referenced by canConstantEvolve().

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

References umul_ov().

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

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]

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

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

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

static bool containsParameters

(

const SCEV *

S

)

[inline, static]

Definition at line 7335 of file ScalarEvolution.cpp.

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

Referenced by containsParameters(), and llvm::ScalarEvolution::findArrayDimensions().

static bool containsParameters

(

SmallVectorImpl< const SCEV * > &

Terms

)

[inline, static]

Definition at line 7345 of file ScalarEvolution.cpp.

References containsParameters().

static bool containsUndefs

(

const SCEV *

S

)

[inline, static]

Definition at line 6930 of file ScalarEvolution.cpp.

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

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

Definition at line 4823 of file ScalarEvolution.cpp.

References llvm::SCEVAddRecExpr::evaluateAtIteration(), and llvm::ScalarEvolution::getConstant().

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

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

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

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

Definition at line 7265 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getMulExpr(), llvm::SCEV::isZero(), llvm::IndexedInstrProf::Last, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

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

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

Definition at line 2270 of file ScalarEvolution.cpp.

References llvm::ARM_PROC::A, llvm::APInt::abs(), llvm::APInt::getBitWidth(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), llvm::APIntOps::GreatestCommonDivisor(), and llvm::APInt::zext().

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

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

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

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

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

Definition at line 4955 of file ScalarEvolution.cpp.

References canConstantEvolve(), llvm::dyn_cast(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::lookup(), llvm::User::op_begin(), llvm::User::op_end(), P, and llvm::TargetOpcode::PHI.

Referenced by getConstantEvolvingPHI().

static void getLoopBackedgeTakenCounts	(	Loop *	L,
		VerifyMap &	Map,
		ScalarEvolution &	SE
	)		[static]

getLoopBackedgeTakenCounts - Helper method for verifyAnalysis.

Definition at line 8041 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getBackedgeTakenCount(), I, llvm::SCEV::print(), llvm::LoopBase< BlockT, LoopT >::rbegin(), llvm::LoopBase< BlockT, LoopT >::rend(), replaceSubString(), and llvm::raw_string_ostream::str().

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

static const SCEV* getOverflowLimitForStep	(	const SCEV *	Step,
		ICmpInst::Predicate *	Pred,
		ScalarEvolution *	SE
	)		[static]

Definition at line 1064 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getConstant(), llvm::ConstantRange::getSignedMax(), llvm::APInt::getSignedMaxValue(), llvm::ConstantRange::getSignedMin(), llvm::APInt::getSignedMinValue(), llvm::ScalarEvolution::getSignedRange(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, llvm::ScalarEvolution::isKnownNegative(), and llvm::ScalarEvolution::isKnownPositive().

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

static const SCEV* getPreStartForSignExtend	(	const SCEVAddRecExpr *	AR,
		Type *	Ty,
		ScalarEvolution *	SE
	)		[static]

Definition at line 1087 of file ScalarEvolution.cpp.

References llvm::dbgs(), DEBUG, llvm::dyn_cast(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNSW, llvm::IntegerType::get(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getContext(), llvm::SCEVAddRecExpr::getLoop(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), getOverflowLimitForStep(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVAddRecExpr::getStart(), llvm::SCEVAddRecExpr::getStepRecurrence(), llvm::SCEVNAryExpr::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::isLoopEntryGuardedByCond(), llvm::SCEVNAryExpr::operands(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and llvm::SmallVectorTemplateCommon< T >::size().

Referenced by getSignExtendAddRecStart().

static const SCEV* getSignExtendAddRecStart	(	const SCEVAddRecExpr *	AR,
		Type *	Ty,
		ScalarEvolution *	SE
	)		[static]

Definition at line 1148 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getAddExpr(), getPreStartForSignExtend(), llvm::ScalarEvolution::getSignExtendExpr(), llvm::SCEVAddRecExpr::getStart(), and llvm::SCEVAddRecExpr::getStepRecurrence().

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

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

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

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

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

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

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

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

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

static int numberOfTerms

(

const SCEV *

S

)

[inline, static]

Definition at line 7353 of file ScalarEvolution.cpp.

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

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

Definition at line 7708 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT, LoopT >::begin(), llvm::LoopBase< BlockT, LoopT >::end(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::LoopBase< BlockT, LoopT >::getExitBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::ScalarEvolution::getMaxBackedgeTakenCount(), llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount(), I, llvm::Value::printAsOperand(), and llvm::SmallVectorTemplateCommon< T >::size().

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

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

PushDefUseChildren - Push users of the given Instruction onto the given Worklist.

Definition at line 3062 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), and llvm::Value::users().

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

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

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

Definition at line 4181 of file ScalarEvolution.cpp.

References llvm::BasicBlock::begin(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), I, and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().

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

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

Definition at line 7359 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getMulExpr(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and T.

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

static void replaceSubString	(	std::string &	Str,
		StringRef	From,
		StringRef	To
	)		[static]

replaceSubString - Replaces all occurrences of From in Str with To.

Definition at line 8031 of file ScalarEvolution.cpp.

References llvm::StringRef::data(), and llvm::StringRef::size().

Referenced by getLoopBackedgeTakenCounts().

static const APInt sdiv	(	const SCEVConstant *	C1,
		const SCEVConstant *	C2
	)		[static]

Definition at line 7017 of file ScalarEvolution.cpp.

References llvm::APInt::getBitWidth(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), llvm::APIntOps::sdiv(), and llvm::APInt::sext().

Referenced by llvm::Interpreter::visitBinaryOperator().

static int sizeOfSCEV

(

const SCEV *

S

)

[inline, static]

Definition at line 7048 of file ScalarEvolution.cpp.

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

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

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

References llvm::APInt::countTrailingZeros(), llvm::APInt::getBitWidth(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::APInt::lshr(), llvm::APInt::multiplicativeInverse(), llvm::APInt::setBit(), llvm::APInt::trunc(), llvm::APIntOps::urem(), and llvm::APInt::zext().

static std::pair<const SCEV *,const SCEV *> SolveQuadraticEquation	(	const SCEVAddRecExpr *	AddRec,
		ScalarEvolution &	SE
	)		[static]

SolveQuadraticEquation - Find the roots of the quadratic equation for the given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which might be the same) or two SCEVCouldNotCompute objects.

Definition at line 5614 of file ScalarEvolution.cpp.

References llvm::ARM_PROC::A, llvm::CallingConv::C, llvm::dyn_cast(), llvm::ConstantInt::get(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::APInt::isMinValue(), N, NC, llvm::APInt::sdiv(), and llvm::APIntOps::sdiv().

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

static const APInt srem	(	const SCEVConstant *	C1,
		const SCEVConstant *	C2
	)		[static]

Definition at line 7003 of file ScalarEvolution.cpp.

References llvm::APInt::getBitWidth(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), llvm::APInt::sext(), and llvm::APIntOps::srem().

Referenced by llvm::Interpreter::visitBinaryOperator().

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 uint64_t umul_ov	(	uint64_t	i,
		uint64_t	j,
		bool &	Overflow
	)		[static]

Definition at line 1862 of file ScalarEvolution.cpp.

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

---

Variable Documentation

scalar Scalar Evolution Analysis

Definition at line 121 of file ScalarEvolution.cpp.

scalar evolution

Definition at line 121 of file ScalarEvolution.cpp.

scalar Scalar Evolution false

Definition at line 121 of file ScalarEvolution.cpp.

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::desc("Verify ScalarEvolution's backedge taken counts (slow)")) [static]

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