LLVM API Documentation

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/ConstantRange.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/Statistic.h"
#include <cmath>
#include <iostream>
#include <algorithm>

Include dependency graph for ScalarEvolution.cpp:

Go to the source code of this file.

Functions

static void GroupByComplexity (std::vector< SCEVHandle > &Ops)
static SCEVHandle getTruncateOrZeroExtend (const SCEVHandle &V, const Type *Ty)
static SCEVHandle PartialFact (SCEVHandle V, unsigned NumSteps)
 PartialFact - Compute V!/(V-NumSteps)!
static ConstantIntEvaluateConstantChrecAtConstant (const SCEVAddRecExpr *AddRec, Constant *C)
static ConstantGetAddressedElementFromGlobal (GlobalVariable *GV, const std::vector< ConstantInt * > &Indices)
static bool CanConstantFold (const Instruction *I)
static ConstantConstantFold (const Instruction *I, std::vector< Constant * > &Operands)
static PHINodegetConstantEvolvingPHI (Value *V, const Loop *L)
static ConstantEvaluateExpression (Value *V, Constant *PHIVal)
static std::pair< SCEVHandle,
SCEVHandle
SolveQuadraticEquation (const SCEVAddRecExpr *AddRec)
static void PrintLoopInfo (std::ostream &OS, const ScalarEvolution *SE, const Loop *L)

Variables

RegisterAnalysis< ScalarEvolutionR ("scalar-evolution","Scalar Evolution Analysis")
Statistic NumBruteForceEvaluations ("scalar-evolution","Number of brute force evaluations needed to ""calculate high-order polynomial exit values")
Statistic NumArrayLenItCounts ("scalar-evolution","Number of trip counts computed with array length")
Statistic NumTripCountsComputed ("scalar-evolution","Number of loops with predictable loop counts")
Statistic NumTripCountsNotComputed ("scalar-evolution","Number of loops without predictable loop counts")
Statistic NumBruteForceTripCountsComputed ("scalar-evolution","Number of loops with trip counts computed by force")
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 std::map< ConstantInt *,
SCEVConstant * > 
SCEVConstants
static std::map< std::pair<
SCEV *, const Type * >, SCEVTruncateExpr * > 
SCEVTruncates
static std::map< std::pair<
SCEV *, const Type * >, SCEVZeroExtendExpr * > 
SCEVZeroExtends
static std::map< std::pair<
unsigned, std::vector< SCEV * > >,
SCEVCommutativeExpr * > 
SCEVCommExprs
static std::map< std::pair<
SCEV *, SCEV * >, SCEVSDivExpr * > 
SCEVSDivs
static std::map< std::pair<
const Loop *, std::vector<
SCEV * > >, SCEVAddRecExpr * > 
SCEVAddRecExprs
static std::map< Value *,
SCEVUnknown * > 
SCEVUnknowns
FunctionF
LoopInfoLI
SCEVHandle UnknownValue
std::map< Value *, SCEVHandleScalars
std::map< const Loop *, SCEVHandleIterationCounts
std::map< PHINode *, Constant * > ConstantEvolutionLoopExitValue


Function Documentation

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

References llvm::canConstantFoldCallTo(), and F.

Referenced by getConstantEvolvingPHI().

static Constant* ConstantFold ( const Instruction I,
std::vector< Constant * > &  Operands 
) [static]

ConstantFold - Constant fold an instruction of the specified type with the specified constant operands. This function may modify the operands vector.

Definition at line 1695 of file ScalarEvolution.cpp.

References Base, llvm::Call, llvm::ConstantFoldCall(), GV, and llvm::Select.

Referenced by EvaluateExpression().

static ConstantInt* EvaluateConstantChrecAtConstant ( const SCEVAddRecExpr AddRec,
Constant C 
) [static]

Definition at line 1562 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, llvm::SCEVAddRecExpr::evaluateAtIteration(), 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 1766 of file ScalarEvolution.cpp.

References llvm::CallingConv::C, ConstantFold(), llvm::User::getNumOperands(), llvm::User::getOperand(), GV, and V.

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

References GV, 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 1726 of file ScalarEvolution.cpp.

References CanConstantFold(), llvm::Loop::contains(), llvm::Loop::getHeader(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), Op, llvm::PHI, and V.

static SCEVHandle getTruncateOrZeroExtend ( const SCEVHandle V,
const Type Ty 
) [static]

getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the input value to the specified type. If the type must be extended, it is zero extended.

Definition at line 473 of file ScalarEvolution.cpp.

References llvm::SCEVZeroExtendExpr::get(), llvm::SCEVTruncateExpr::get(), llvm::Type::getPrimitiveSize(), llvm::Type::isInteger(), Ty, and V.

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

Referenced by llvm::SCEVMulExpr::get(), and llvm::SCEVAddExpr::get().

static SCEVHandle PartialFact ( SCEVHandle  V,
unsigned  NumSteps 
) [static]

PartialFact - Compute V!/(V-NumSteps)!

Definition at line 502 of file ScalarEvolution.cpp.

References llvm::SCEVMulExpr::get(), llvm::SCEVUnknown::get(), llvm::ConstantUInt::get(), llvm::ConstantExpr::getCast(), llvm::SCEVUnknown::getIntegerSCEV(), llvm::SCEV::getMinusSCEV(), llvm::Value::getType(), Ty, llvm::Type::ULongTy, V, and Val.

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

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

Definition at line 2476 of file ScalarEvolution.cpp.

References llvm::Loop::begin(), E, llvm::Loop::end(), llvm::Loop::getExitBlocks(), llvm::Loop::getHeader(), llvm::ScalarEvolution::getIterationCount(), llvm::Value::getName(), llvm::ScalarEvolution::hasLoopInvariantIterationCount(), and SE.

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

static std::pair<SCEVHandle,SCEVHandle> SolveQuadraticEquation ( const SCEVAddRecExpr AddRec  )  [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 2020 of file ScalarEvolution.cpp.

References A, B, llvm::CallingConv::C, llvm::SCEVAddRecExpr::getNumOperands(), llvm::SCEVAddRecExpr::getOperand(), llvm::Value::getType(), llvm::ConstantUInt::getValue(), and M.

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


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

Function& F

F - The function we are analyzing.

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

LoopInfo& LI

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

Definition at line 1072 of file ScalarEvolution.cpp.

Referenced by llvm::AliasSetTracker::add(), llvm::Loop::addBasicBlockToLoop(), AddressIsTaken(), AllUsesOfLoadedValueWillTrapIfNull(), CleanupConstantGlobalUsers(), CloneLoop(), llvm::ConvertExpressionToType(), EvaluateFunction(), llvm::ExpressionConvertibleToType(), FindIntervalInVector(), InstCombineLoadCast(), llvm::Instruction::isIdenticalTo(), llvm::RSProfilers_std::isProfiling(), isSafeToLoadUnconditionally(), OperandConvertibleToType(), llvm::operator<<(), OptimizeAwayTrappingUsesOfLoads(), OptimizeAwayTrappingUsesOfValue(), OptimizeGlobalAddressOfMalloc(), llvm::ScalarEvolution::print(), llvm::AliasSetTracker::remove(), llvm::ModuloSchedulingSBPass::runOnFunction(), ShrinkGlobalToBoolean(), llvm::SplitCriticalEdge(), and llvm::LiveRangeInfo::~LiveRangeInfo().

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]

Statistic NumArrayLenItCounts("scalar-evolution","Number of trip counts computed with array length") [static]

Statistic NumBruteForceEvaluations("scalar-evolution","Number of brute force evaluations needed to ""calculate high-order polynomial exit values") [static]

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

Statistic NumBruteForceTripCountsComputed("scalar-evolution","Number of loops with trip counts computed by force") [static]

Statistic NumTripCountsComputed("scalar-evolution","Number of loops with predictable loop counts") [static]

Statistic NumTripCountsNotComputed("scalar-evolution","Number of loops without predictable loop counts") [static]

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

Referenced by DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Add(), DirectIntRules< ConstantClass, BuiltinType, Ty >::And(), llvm::ConstantFoldGetElementPtr(), llvm::FunctionLoweringInfo::CreateRegForValue(), DirectFPRules< ConstantClass, BuiltinType, Ty >::Div(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Div(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Div(), llvm::SDNode::dump(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::EqualTo(), evaluateRelation(), llvm::SCEVConstant::get(), llvm::DOTGraphTraits< const DSGraph * >::getEdgeTarget(), getVal(), llvm::FunctionLoweringInfo::InitializeRegForValue(), isRegister0(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::LessThan(), llvm::DefaultIntrinsicLowering::LowerIntrinsicCall(), llvm::AliasSet::mergeSetIn(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Mul(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Or(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Rem(), llvm::SCEVSDivExpr::replaceSymbolicValuesWithConcrete(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Shl(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Shr(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Sub(), llvm::UpgradeIntrinsicFunction(), llvm::Interpreter::visitBinaryOperator(), llvm::Interpreter::visitSelectInst(), and DirectIntRules< ConstantClass, BuiltinType, Ty >::Xor().

std::map<Value*, SCEVHandle> Scalars

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

Definition at line 1080 of file ScalarEvolution.cpp.

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

Definition at line 320 of file ScalarEvolution.cpp.

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

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

Definition at line 253 of file ScalarEvolution.cpp.

Referenced by llvm::SCEVMulExpr::get(), llvm::SCEVAddExpr::get(), and llvm::SCEVCommutativeExpr::~SCEVCommutativeExpr().

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

Definition at line 167 of file ScalarEvolution.cpp.

std::map<std::pair<SCEV*, SCEV*>, SCEVSDivExpr*> SCEVSDivs [static]

Definition at line 300 of file ScalarEvolution.cpp.

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

Definition at line 199 of file ScalarEvolution.cpp.

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

Definition at line 368 of file ScalarEvolution.cpp.

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

Definition at line 226 of file ScalarEvolution.cpp.

Referenced by llvm::SCEVZeroExtendExpr::get().

SCEVHandle UnknownValue

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

Definition at line 1076 of file ScalarEvolution.cpp.