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/CommandLine.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/Visibility.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 |
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 1708 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 1721 of file ScalarEvolution.cpp.
References Base, Call, llvm::ConstantFoldCall(), GV, and Select.
Referenced by EvaluateExpression().
static ConstantInt* EvaluateConstantChrecAtConstant | ( | const SCEVAddRecExpr * | AddRec, | |
Constant * | C | |||
) | [static] |
Definition at line 1588 of file ScalarEvolution.cpp.
References 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 1792 of file ScalarEvolution.cpp.
References 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 1601 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 1752 of file ScalarEvolution.cpp.
References CanConstantFold(), llvm::Loop::contains(), llvm::Loop::getHeader(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), Op, 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 474 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 414 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 503 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 2502 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 2046 of file ScalarEvolution.cpp.
References A, B, 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 1092 of file ScalarEvolution.cpp.
F - The function we are analyzing.
Definition at line 1069 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 1085 of file ScalarEvolution.cpp.
LI - The loop information for the function we are currently analyzing.
Definition at line 1073 of file ScalarEvolution.cpp.
Referenced by llvm::AliasSetTracker::add(), llvm::Loop::addBasicBlockToLoop(), AddressIsTaken(), AllUsesOfLoadedValueWillTrapIfNull(), CleanupConstantGlobalUsers(), CloneLoop(), llvm::ConvertExpressionToType(), llvm::ScheduleDAG::EmitSchedule(), 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(), ShrinkGlobalToBoolean(), and llvm::SplitCriticalEdge().
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 llvm::ConstantFoldGetElementPtr(), llvm::FunctionLoweringInfo::CreateRegForValue(), llvm::SDNode::dump(), evaluateRelation(), llvm::SCEVConstant::get(), llvm::DOTGraphTraits< const DSGraph * >::getEdgeTarget(), getVal(), llvm::FunctionLoweringInfo::InitializeRegForValue(), isRegister0(), llvm::DefaultIntrinsicLowering::LowerIntrinsicCall(), llvm::AliasSet::mergeSetIn(), llvm::SCEVSDivExpr::replaceSymbolicValuesWithConcrete(), llvm::UpgradeIntrinsicFunction(), llvm::Interpreter::visitBinaryOperator(), 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 1081 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 254 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 168 of file ScalarEvolution.cpp.
std::map<std::pair<SCEV*, SCEV*>, SCEVSDivExpr*> SCEVSDivs [static] |
Definition at line 301 of file ScalarEvolution.cpp.
std::map<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> SCEVTruncates [static] |
Definition at line 200 of file ScalarEvolution.cpp.
std::map<Value*, SCEVUnknown*> SCEVUnknowns [static] |
Definition at line 369 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 1077 of file ScalarEvolution.cpp.