ScalarEvolution.cpp File Reference

#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Streams.h"
#include "llvm/ADT/Statistic.h"
#include <ostream>
#include <algorithm>
#include <cmath>

Include dependency graph for ScalarEvolution.cpp:

Go to the source code of this file.

Defines
#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 void	GroupByComplexity (std::vector< SCEVHandle > &Ops)
static SCEVHandle	BinomialCoefficient (SCEVHandle It, unsigned K, ScalarEvolution &SE, const IntegerType *ResultTy)
	BinomialCoefficient - Compute BC(It, K). The result has width W.
static uint32_t	GetMinTrailingZeros (SCEVHandle S)
static ConstantInt *	EvaluateConstantChrecAtConstant (const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
static Constant *	GetAddressedElementFromGlobal (GlobalVariable *GV, const std::vector< ConstantInt * > &Indices)
static bool	CanConstantFold (const Instruction *I)
static PHINode *	getConstantEvolvingPHI (Value *V, const Loop *L)
static Constant *	EvaluateExpression (Value *V, Constant *PHIVal)
static SCEVHandle	SolveLinEquationWithOverflow (const APInt &A, const APInt &B, ScalarEvolution &SE)
static std::pair< SCEVHandle, SCEVHandle >	SolveQuadraticEquation (const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
static void	PrintLoopInfo (std::ostream &OS, const ScalarEvolution *SE, const Loop *L)
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 RegisterPass < ScalarEvolution >	R ("scalar-evolution","Scalar Evolution Analysis", false, true)
static ManagedStatic< std::map < ConstantInt *, SCEVConstant * > >	SCEVConstants
static ManagedStatic< std::map < std::pair< SCEV *, const Type * >, SCEVTruncateExpr * > >	SCEVTruncates
static ManagedStatic< std::map < std::pair< SCEV *, const Type * >, SCEVZeroExtendExpr * > >	SCEVZeroExtends
static ManagedStatic< std::map < std::pair< SCEV *, const Type * >, SCEVSignExtendExpr * > >	SCEVSignExtends
static ManagedStatic< std::map < std::pair< unsigned, std::vector< SCEV * > >, SCEVCommutativeExpr * > >	SCEVCommExprs
static ManagedStatic< std::map < std::pair< SCEV *, SCEV * > , SCEVUDivExpr * > >	SCEVUDivs
static ManagedStatic< std::map < std::pair< const Loop *, std::vector< SCEV * > >, SCEVAddRecExpr * > >	SCEVAddRecExprs
static ManagedStatic< std::map < Value *, SCEVUnknown * > >	SCEVUnknowns

---

Define Documentation

#define DEBUG_TYPE   "scalar-evolution"

Definition at line 62 of file ScalarEvolution.cpp.

---

Function Documentation

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

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

Definition at line 510 of file ScalarEvolution.cpp.

References llvm::APInt::countTrailingZeros(), llvm::IntegerType::get(), llvm::IntegerType::getBitWidth(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::APInt::getSignedMinValue(), llvm::ScalarEvolution::getTruncateOrZeroExtend(), llvm::ScalarEvolution::getUDivExpr(), llvm::Log2_32_Ceil(), llvm::APInt::lshr(), Mod, llvm::APInt::multiplicativeInverse(), T, llvm::APInt::trunc(), and llvm::APInt::zext().

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

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

References llvm::canConstantFoldCallTo(), and F.

Referenced by getConstantEvolvingPHI().

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

Definition at line 2066 of file ScalarEvolution.cpp.

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

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

static Constant* EvaluateExpression	(	Value *	V,
		Constant *	PHIVal
	)			[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 2245 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::ConstantFoldCompareInstOperands(), llvm::ConstantFoldInstOperands(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), and llvm::Value::getType().

static Constant* GetAddressedElementFromGlobal	(	GlobalVariable *	GV,
		const std::vector< ConstantInt * > &	Indices
	)			[static]

GetAddressedElementFromGlobal - Given a global variable with an initializer and a GEP expression (missing the pointer index) indexing into it, return the addressed element of the initializer or null if the index expression is invalid.

Definition at line 2080 of file ScalarEvolution.cpp.

References CA, llvm::GlobalVariable::getInitializer(), llvm::Value::getType(), and Idx.

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

References CanConstantFold(), llvm::LoopBase< BlockT >::contains(), llvm::dyn_cast(), llvm::LoopBase< BlockT >::getHeader(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Instruction::getParent(), Op, and PHI.

static uint32_t GetMinTrailingZeros

(

SCEVHandle

S

)

[static]

GetMinTrailingZeros - Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration). It is, at the same time, the minimum number of times S is divisible by 2. For example, given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S.

Definition at line 1670 of file ScalarEvolution.cpp.

References A, llvm::CallingConv::C, E, M, and T.

static void GroupByComplexity

(

std::vector< SCEVHandle > &

Ops

)

[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 determinstic 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 427 of file ScalarEvolution.cpp.

References llvm::SCEV::getSCEVType(), and std::swap().

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

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

Definition at line 3026 of file ScalarEvolution.cpp.

References llvm::LoopBase< BlockT >::begin(), E, llvm::LoopBase< BlockT >::end(), llvm::LoopBase< BlockT >::getExitBlocks(), llvm::LoopBase< BlockT >::getHeader(), llvm::ScalarEvolution::getIterationCount(), llvm::ScalarEvolution::hasLoopInvariantIterationCount(), and llvm::SmallVectorImpl< T >::size().

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

static SCEVHandle 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 2519 of file ScalarEvolution.cpp.

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

static std::pair<SCEVHandle,SCEVHandle> 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 2563 of file ScalarEvolution.cpp.

References A, llvm::dyn_cast(), llvm::ScalarEvolution::getConstant(), llvm::SCEVAddRecExpr::getNumOperands(), llvm::SCEVAddRecExpr::getOperand(), llvm::APInt::isMinValue(), M, llvm::APInt::sdiv(), and llvm::APIntOps::sdiv().

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

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

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

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

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

---

Variable Documentation

std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue

ConstantEvolutionLoopExitValue - This map contains entries for all of the PHI instructions that we attempt to compute constant evolutions for. This allows us to avoid potentially expensive recomputation of these properties. An instruction maps to null if we are unable to compute its exit value.

Definition at line 1386 of file ScalarEvolution.cpp.

Function& F

F - The function we are analyzing.

Definition at line 1363 of file ScalarEvolution.cpp.

std::map<const Loop*, SCEVHandle> IterationCounts

IterationCounts - Cache the iteration count of the loops for this function as they are computed.

Definition at line 1379 of file ScalarEvolution.cpp.

LoopInfo& LI

LI - The loop information for the function we are currently analyzing.

Definition at line 1367 of file ScalarEvolution.cpp.

Referenced by llvm::AliasSetTracker::add(), llvm::LiveIntervals::addIntervalsForSpills(), AddressIsTaken(), llvm::MachineLoopInfo::addTopLevelLoop(), llvm::LoopInfo::addTopLevelLoop(), AllGlobalLoadUsesSimpleEnoughForHeapSRA(), AllUsesOfLoadedValueWillTrapIfNull(), AnalyzeGlobal(), llvm::MachineLoopInfo::begin(), llvm::LoopInfo::begin(), llvm::MachineLoopInfo::changeLoopFor(), llvm::LoopInfo::changeLoopFor(), llvm::MachineLoopInfo::changeTopLevelLoop(), llvm::LoopInfo::changeTopLevelLoop(), CleanupConstantGlobalUsers(), llvm::LiveIntervals::computeNumbering(), llvm::LPPassManager::deleteLoopFromQueue(), llvm::PPCTargetLowering::EmitInstrWithCustomInserter(), EmitLiveInCopies(), llvm::PPCTargetLowering::EmitPartwordAtomicBinary(), llvm::MachineLoopInfo::empty(), llvm::LoopInfo::empty(), llvm::MachineLoopInfo::end(), llvm::LoopInfo::end(), EvaluateFunction(), FindAllMemoryUses(), llvm::FindAvailableLoadedValue(), llvm::LoopInfo::getBase(), llvm::MemoryDependenceAnalysis::getDependency(), GetHeapSROAValue(), llvm::MachineLoopInfo::getLoopDepth(), llvm::LoopInfo::getLoopDepth(), llvm::MachineLoopInfo::getLoopFor(), llvm::LoopInfo::getLoopFor(), llvm::LPPassManager::insertLoop(), llvm::isAllocaPromotable(), llvm::Instruction::isIdenticalTo(), llvm::MachineLoopInfo::isLoopHeader(), llvm::LoopInfo::isLoopHeader(), llvm::RSProfilers_std::isProfiling(), isSafeToLoadUnconditionally(), llvm::Instruction::isSameOperationAs(), llvm::LoopInfo::LoopInfo(), llvm::LPPassManager::LPPassManager(), llvm::MachineLoopInfo::MachineLoopInfo(), llvm::MachineLoopInfo::operator[](), llvm::LoopInfo::operator[](), OptimizeAwayTrappingUsesOfLoads(), OptimizeAwayTrappingUsesOfValue(), OptimizeGlobalAddressOfMalloc(), PerformHeapAllocSRoA(), llvm::LoopInfo::print(), llvm::MachineLoopInfo::releaseMemory(), llvm::LoopInfo::releaseMemory(), llvm::AliasSetTracker::remove(), llvm::MachineLoopInfo::removeBlock(), llvm::LoopInfo::removeBlock(), llvm::MachineLoopInfo::removeLoop(), llvm::LoopInfo::removeLoop(), llvm::LPPassManager::runOnFunction(), llvm::SimplifyCFG(), llvm::SplitBlock(), llvm::SplitCriticalEdge(), TryToShrinkGlobalToBoolean(), llvm::LoopInfo::~LoopInfo(), and llvm::MachineLoopInfo::~MachineLoopInfo().

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]

RegisterPass<ScalarEvolution> R("scalar-evolution","Scalar Evolution Analysis", false, true) [static]

Referenced by llvm::DominatorTree::compare(), llvm::ComputeMaskedBits(), llvm::ConstantFoldCompareInstruction(), llvm::FunctionLoweringInfo::CreateRegForValue(), llvm::ScheduleDAGSDNodes::EmitNode(), evaluateFCmpRelation(), evaluateICmpRelation(), llvm::SelectionDAG::FoldSetCC(), llvm::ImutAVLTree< ImutInfo >::foreach(), llvm::getBitcodeModuleProvider(), llvm::ScalarEvolution::getConstant(), getVal(), llvm::FunctionLoweringInfo::InitializeRegForValue(), llvm::InlineFunction(), llvm::AliasSet::mergeSetIn(), llvm::ParseBitcodeFile(), llvm::JoinPriorityQueue< llvm::CopyRecSort >::pop(), llvm::BumpPtrAllocator::PrintStats(), llvm::BitstreamReader::Read(), llvm::SCEVUDivExpr::replaceSymbolicValuesWithConcrete(), llvm::MachineLocation::set(), llvm::ImutAVLTree< ImutInfo >::size(), llvm::Interpreter::visitBinaryOperator(), llvm::Interpreter::visitFCmpInst(), llvm::Interpreter::visitICmpInst(), and llvm::Interpreter::visitSelectInst().

std::map<Value*, SCEVHandle> Scalars

Scalars - This is a cache of the scalars we have analyzed so far.

Definition at line 1375 of file ScalarEvolution.cpp.

ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >, SCEVAddRecExpr*> > SCEVAddRecExprs [static]

Definition at line 332 of file ScalarEvolution.cpp.

ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >, SCEVCommutativeExpr*> > SCEVCommExprs [static]

Definition at line 260 of file ScalarEvolution.cpp.

ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants [static]

Definition at line 167 of file ScalarEvolution.cpp.

ManagedStatic<std::map<std::pair<SCEV*, const Type*>, SCEVSignExtendExpr*> > SCEVSignExtends [static]

Definition at line 238 of file ScalarEvolution.cpp.

ManagedStatic<std::map<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> > SCEVTruncates [static]

Definition at line 194 of file ScalarEvolution.cpp.

ManagedStatic<std::map<std::pair<SCEV*, SCEV*>, SCEVUDivExpr*> > SCEVUDivs [static]

Definition at line 314 of file ScalarEvolution.cpp.

ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns [static]

Definition at line 382 of file ScalarEvolution.cpp.

ManagedStatic<std::map<std::pair<SCEV*, const Type*>, SCEVZeroExtendExpr*> > SCEVZeroExtends [static]

Definition at line 216 of file ScalarEvolution.cpp.

ScalarEvolution& SE

SE - A reference to the public ScalarEvolution object.

Definition at line 1359 of file ScalarEvolution.cpp.

Referenced by llvm::DominanceFrontier::calculate(), ChangeToUnreachable(), containsAddRecFromDifferentLoop(), llvm::LiveIntervals::findReachableMBBs(), llvm::LoopBase< BlockT >::isLoopExit(), llvm::Linker::LinkModules(), MarkAliveBlocks(), llvm::MergeBlockIntoPredecessor(), llvm::Type::PromoteAbstractToConcrete(), RecursiveResolveTypesI(), RemoveUnreachableBlocksFromFn(), llvm::set_difference(), llvm::set_subtract(), llvm::set_union(), llvm::SimplifyCFG(), llvm::UnrollLoop(), llvm::Archive::writeMember(), and WriteValueSymbolTable().

SCEVHandle UnknownValue

UnknownValue - This SCEV is used to represent unknown trip counts and things.

Definition at line 1371 of file ScalarEvolution.cpp.