#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstIterator.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:

Classes
struct	MarkPendingLoopPredicate

Macros
#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 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 TD, 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 const APInt	gcd (const SCEVConstant C1, const SCEVConstant C2)

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

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

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

static void	replaceSubString (std::string &Str, StringRef From, StringRef To)
	replaceSubString - Replaces all occurences of From in Str with To. More...

static void	getLoopBackedgeTakenCounts (Loop *L, VerifyMap &Map, ScalarEvolution &SE)
	getLoopBackedgeTakenCounts - Helper method for verifyAnalysis. More...

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

Macro Definition Documentation

#define DEBUG_TYPE "scalar-evolution"

Definition at line 61 of file ScalarEvolution.cpp.

Typedef Documentation

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

Definition at line 7638 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 683 of file ScalarEvolution.cpp.

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

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

References CanConstantFold(), llvm::LoopBase< N, M >::contains(), llvm::LoopBase< N, M >::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 4740 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 1839 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 1385 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< T >::value >::push_back().

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

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

static

Definition at line 4643 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 *	TD,
		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 4831 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(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::lookup(), and TD.

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

static

Definition at line 6680 of file ScalarEvolution.cpp.

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

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 4814 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 4775 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 7651 of file ScalarEvolution.cpp.

References llvm::ScalarEvolution::getBackedgeTakenCount(), I, llvm::SCEV::print(), llvm::LoopBase< N, M >::rbegin(), llvm::LoopBase< N, M >::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 1063 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 1086 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(), I, llvm::ScalarEvolution::isLoopEntryGuardedByCond(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), 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 639 of file ScalarEvolution.cpp.

References llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SCEV::getSCEVType(), llvm::SmallVectorTemplateCommon< T >::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 5674 of file ScalarEvolution.cpp.

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

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

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

static

Definition at line 7317 of file ScalarEvolution.cpp.

References llvm::LoopBase< N, M >::begin(), llvm::LoopBase< N, M >::end(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::LoopBase< N, M >::getExitBlocks(), llvm::LoopBase< N, M >::getHeader(), llvm::ScalarEvolution::getMaxBackedgeTakenCount(), llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount(), I, llvm::SmallVectorTemplateCommon< T >::size(), and llvm::WriteAsOperand().

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

References llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::Value::use_begin(), and llvm::Value::use_end().

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

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

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

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

static

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

Definition at line 7641 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 6708 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 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 5386 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 5430 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 6694 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 1830 of file ScalarEvolution.cpp.

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

Variable Documentation

scalar Scalar Evolution Analysis

Definition at line 119 of file ScalarEvolution.cpp.

scalar evolution

Definition at line 119 of file ScalarEvolution.cpp.

scalar Scalar Evolution false

Definition at line 119 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().

Classes

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation