LLVM API Documentation
#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 ConstantInt * | EvaluateConstantChrecAtConstant (const SCEVAddRecExpr *AddRec, Constant *C) |
static Constant * | GetAddressedElementFromGlobal (GlobalVariable *GV, const std::vector< ConstantInt * > &Indices) |
static bool | CanConstantFold (const Instruction *I) |
static Constant * | ConstantFold (const Instruction *I, std::vector< Constant * > &Operands) |
static PHINode * | getConstantEvolvingPHI (Value *V, const Loop *L) |
static Constant * | EvaluateExpression (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< ScalarEvolution > | R ("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 |
Function & | F |
LoopInfo & | LI |
SCEVHandle | UnknownValue |
std::map< Value *, SCEVHandle > | Scalars |
std::map< const Loop *, SCEVHandle > | IterationCounts |
std::map< PHINode *, Constant * > | ConstantEvolutionLoopExitValue |
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().
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.
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().
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.
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.
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] |
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] |
UnknownValue - This SCEV is used to represent unknown trip counts and things.
Definition at line 1076 of file ScalarEvolution.cpp.