LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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/LoopInfo.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.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 <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 getNegativeSCEV (const SCEVHandle &V)
static SCEVHandle getMinusSCEV (const SCEVHandle &LHS, const SCEVHandle &RHS)
static ConstantIntBinomial (ConstantInt *N, unsigned M)
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

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 * >, SCEVUDivExpr * > 
SCEVUDivs
static std::map< std::pair<
const Loop *, std::vector<
SCEV * > >, SCEVAddRecExpr * > 
SCEVAddRecExprs
static std::map< Value *,
SCEVUnknown * > 
SCEVUnknowns


Function Documentation

static ConstantInt* Binomial ConstantInt N,
unsigned  M
[static]
 

Binomial - Evaluate N!/((N-M)!*M!) . Note that N is often large and M is often very small, so we try to reduce the number of N! terms we need to evaluate by evaluating this as (N!/(N-M)!)/M!

Definition at line 446 of file ScalarEvolution.cpp.

References llvm::ConstantUInt::get(), llvm::ConstantExpr::getCast(), llvm::ConstantIntegral::getRawValue(), llvm::Value::getType(), and llvm::Type::ULongTy.

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

References llvm::ISD::Call, llvm::ConstantFoldCall(), and llvm::Select.

Referenced by EvaluateExpression().

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

Definition at line 1495 of file ScalarEvolution.cpp.

References llvm::SCEVAddRecExpr::evaluateAtIteration(), and llvm::SCEVConstant::get().

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

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

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

References llvm::GlobalVariable::getInitializer(), and llvm::Constant::getNullValue().

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

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

static SCEVHandle getMinusSCEV const SCEVHandle LHS,
const SCEVHandle RHS
[static]
 

getMinusSCEV - Return a SCEV corresponding to LHS - RHS.

Definition at line 437 of file ScalarEvolution.cpp.

References llvm::SCEVAddExpr::get(), and getNegativeSCEV().

Referenced by PartialFact().

static SCEVHandle getNegativeSCEV const SCEVHandle V  )  [static]
 

getNegativeSCEV - Return a SCEV corresponding to -V = -1*V

Definition at line 428 of file ScalarEvolution.cpp.

References llvm::SCEVMulExpr::get(), llvm::SCEVUnknown::get(), llvm::SCEVUnknown::getIntegerSCEV(), and llvm::ConstantExpr::getNeg().

Referenced by llvm::SCEVUDivExpr::get(), getMinusSCEV(), and llvm::SCEVAddRecExpr::getNumIterationsInRange().

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

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

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

References llvm::SCEV::getSCEVType().

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

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

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

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

Definition at line 2307 of file ScalarEvolution.cpp.

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

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

References B, C, llvm::SCEVAddRecExpr::getNumOperands(), llvm::SCEVAddRecExpr::getOperand(), llvm::Type::getSignedVersion(), llvm::Value::getType(), llvm::Type::getUnsignedVersion(), llvm::ConstantUInt::getValue(), llvm::SCEVConstant::getValue(), and M.

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


Variable Documentation

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(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Div(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Div(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::EqualTo(), llvm::SCEVConstant::get(), llvm::DOTGraphTraits< const DSGraph * >::getEdgeTarget(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::LessThan(), llvm::AliasSet::mergeSetIn(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Mul(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Or(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Rem(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Shl(), DirectIntRules< ConstantClass, BuiltinType, Ty >::Shr(), DirectRules< ConstantClass, BuiltinType, Ty, DirectIntRules< ConstantClass, BuiltinType, Ty > >::Sub(), llvm::Interpreter::visitBinaryOperator(), llvm::Interpreter::visitSelectInst(), and DirectIntRules< ConstantClass, BuiltinType, Ty >::Xor().

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

Definition at line 285 of file ScalarEvolution.cpp.

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

Definition at line 245 of file ScalarEvolution.cpp.

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

Definition at line 159 of file ScalarEvolution.cpp.

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

Definition at line 191 of file ScalarEvolution.cpp.

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

Definition at line 265 of file ScalarEvolution.cpp.

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

Definition at line 310 of file ScalarEvolution.cpp.

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

Definition at line 218 of file ScalarEvolution.cpp.