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/LLVMContext.h"#include "llvm/Operator.h"#include "llvm/Analysis/ConstantFolding.h"#include "llvm/Analysis/Dominators.h"#include "llvm/Analysis/LoopInfo.h"#include "llvm/Analysis/ValueTracking.h"#include "llvm/Assembly/Writer.h"#include "llvm/Target/TargetData.h"#include "llvm/Support/CommandLine.h"#include "llvm/Support/Compiler.h"#include "llvm/Support/ConstantRange.h"#include "llvm/Support/ErrorHandling.h"#include "llvm/Support/GetElementPtrTypeIterator.h"#include "llvm/Support/InstIterator.h"#include "llvm/Support/MathExtras.h"#include "llvm/Support/raw_ostream.h"#include "llvm/ADT/Statistic.h"#include "llvm/ADT/STLExtras.h"#include "llvm/ADT/SmallPtrSet.h"#include <algorithm>
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 bool | CompareTypes (const Type *A, const Type *B) |
| static void | GroupByComplexity (SmallVectorImpl< const SCEV * > &Ops, LoopInfo *LI) |
| static const SCEV * | BinomialCoefficient (const SCEV *It, unsigned K, ScalarEvolution &SE, const Type *ResultTy) |
| static bool | CollectAddOperandsWithScales (DenseMap< const SCEV *, APInt > &M, SmallVector< const SCEV *, 8 > &NewOps, APInt &AccumulatedConstant, const SmallVectorImpl< const SCEV * > &Ops, const APInt &Scale, ScalarEvolution &SE) |
| static void | PushDefUseChildren (Instruction *I, SmallVectorImpl< Instruction * > &Worklist) |
| static void | PushLoopPHIs (const Loop *L, SmallVectorImpl< Instruction * > &Worklist) |
| static ConstantInt * | EvaluateConstantChrecAtConstant (const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE) |
| static Constant * | GetAddressedElementFromGlobal (LLVMContext &Context, 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 const SCEV * | SolveLinEquationWithOverflow (const APInt &A, const APInt &B, ScalarEvolution &SE) |
| static std::pair< const SCEV *, const SCEV * > | SolveQuadraticEquation (const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) |
| static bool | HasSameValue (const SCEV *A, const SCEV *B) |
| static void | PrintLoopInfo (raw_ostream &OS, 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) |
| #define DEBUG_TYPE "scalar-evolution" |
Definition at line 61 of file ScalarEvolution.cpp.
| static const SCEV* BinomialCoefficient | ( | const SCEV * | It, | |
| unsigned | K, | |||
| ScalarEvolution & | SE, | |||
| const Type * | ResultTy | |||
| ) | [static] |
BinomialCoefficient - Compute BC(It, K). The result has width W. Assume, K > 0.
Definition at line 568 of file ScalarEvolution.cpp.
References llvm::APInt::countTrailingZeros(), llvm::IntegerType::get(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::ScalarEvolution::getIntegerSCEV(), llvm::ScalarEvolution::getMinusSCEV(), llvm::ScalarEvolution::getMulExpr(), llvm::APInt::getSignedMinValue(), llvm::ScalarEvolution::getTruncateOrZeroExtend(), llvm::SCEV::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ScalarEvolution::getUDivExpr(), llvm::APInt::lshr(), Mod, llvm::APInt::multiplicativeInverse(), S, 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 3704 of file ScalarEvolution.cpp.
References llvm::canConstantFoldCallTo().
Referenced by getConstantEvolvingPHI(), and llvm::ScalarEvolution::getSCEVAtScope().
| static bool CollectAddOperandsWithScales | ( | DenseMap< const SCEV *, APInt > & | M, | |
| SmallVector< const SCEV *, 8 > & | NewOps, | |||
| APInt & | AccumulatedConstant, | |||
| const SmallVectorImpl< const SCEV * > & | Ops, | |||
| const APInt & | Scale, | |||
| ScalarEvolution & | SE | |||
| ) | [static] |
CollectAddOperandsWithScales - Process the given Ops list, which is a list of operands to be added under the given scale, update the given map. This is a helper function for getAddRecExpr. As an example of what it does, given a sequence of operands that would form an add expression like this:
m + n + 13 + (A * (o + p + (B * q + m + 29))) + r + (-1 * r)
where A and B are constants, update the map with these values:
(m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0)
and add 13 + A*B*29 to AccumulatedConstant. This will allow getAddRecExpr to produce this:
13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B)
This form often exposes folding opportunities that are hidden in the original operand list.
Return true iff it appears that any interesting folding opportunities may be exposed. This helps getAddRecExpr short-circuit extra work in the common case where no interesting opportunities are present, and is also used as a check to avoid infinite recursion.
Definition at line 1102 of file ScalarEvolution.cpp.
References llvm::CallingConv::C, llvm::dyn_cast(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), llvm::DenseMap< KeyT, ValueT, KeyInfoT, ValueInfoT >::insert(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), llvm::SmallVectorImpl< T >::push_back(), and llvm::SmallVectorImpl< T >::size().
Referenced by llvm::ScalarEvolution::getAddExpr().
Definition at line 347 of file ScalarEvolution.cpp.
References AI, llvm::IntegerType::getBitWidth(), llvm::StructType::getElementType(), llvm::SequentialType::getElementType(), llvm::StructType::getNumElements(), llvm::VectorType::getNumElements(), llvm::ArrayType::getNumElements(), and llvm::Type::getTypeID().
| static ConstantInt* EvaluateConstantChrecAtConstant | ( | const SCEVAddRecExpr * | AddRec, | |
| ConstantInt * | C, | |||
| ScalarEvolution & | SE | |||
| ) | [static] |
Definition at line 3580 of file ScalarEvolution.cpp.
References llvm::SCEVAddRecExpr::evaluateAtIteration(), llvm::ScalarEvolution::getConstant(), 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 3761 of file ScalarEvolution.cpp.
References llvm::CallingConv::C, llvm::ConstantFoldCompareInstOperands(), llvm::ConstantFoldInstOperands(), Context, llvm::BasicBlock::getContext(), llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), and llvm::Value::getType().
| static Constant* GetAddressedElementFromGlobal | ( | LLVMContext & | Context, | |
| 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 3594 of file ScalarEvolution.cpp.
References CA, llvm::GlobalVariable::getInitializer(), llvm::Constant::getNullValue(), llvm::Value::getType(), Idx, and llvm_unreachable.
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 3720 of file ScalarEvolution.cpp.
References CanConstantFold(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Instruction::getParent(), Op, and PHI.
| static void GroupByComplexity | ( | SmallVectorImpl< const SCEV * > & | Ops, | |
| LoopInfo * | LI | |||
| ) | [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 525 of file ScalarEvolution.cpp.
References llvm::SmallVectorImpl< T >::begin(), llvm::SmallVectorImpl< T >::end(), llvm::SCEV::getSCEVType(), S, llvm::SmallVectorImpl< T >::size(), and std::swap().
Referenced by llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMulExpr(), llvm::ScalarEvolution::getSMaxExpr(), and llvm::ScalarEvolution::getUMaxExpr().
HasSameValue - SCEV structural equivalence is usually sufficient for testing whether two expressions are equal, however for the purposes of looking for a condition guarding a loop, it can be useful to be a little more general, since a front-end may have replicated the controlling expression.
Definition at line 4344 of file ScalarEvolution.cpp.
References AI, and llvm::Instruction::isIdenticalTo().
Referenced by llvm::ScalarEvolution::isKnownPredicate().
| static void PrintLoopInfo | ( | raw_ostream & | OS, | |
| ScalarEvolution * | SE, | |||
| const Loop * | L | |||
| ) | [static] |
Definition at line 5122 of file ScalarEvolution.cpp.
References llvm::LoopBase< BlockT, LoopT >::begin(), E, llvm::LoopBase< BlockT, LoopT >::end(), llvm::ScalarEvolution::getBackedgeTakenCount(), llvm::LoopBase< BlockT, LoopT >::getExitBlocks(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::ScalarEvolution::getMaxBackedgeTakenCount(), llvm::ScalarEvolution::hasLoopInvariantBackedgeTakenCount(), PrintLoopInfo(), and llvm::SmallVectorImpl< T >::size().
| static void PushDefUseChildren | ( | Instruction * | I, | |
| SmallVectorImpl< Instruction * > & | Worklist | |||
| ) | [static] |
PushDefUseChildren - Push users of the given Instruction onto the given Worklist.
Definition at line 2390 of file ScalarEvolution.cpp.
References llvm::SmallVectorImpl< T >::push_back(), llvm::Value::use_begin(), and llvm::Value::use_end().
Referenced by llvm::ScalarEvolution::forgetLoopBackedgeTakenCount().
| static void PushLoopPHIs | ( | const Loop * | L, | |
| SmallVectorImpl< Instruction * > & | Worklist | |||
| ) | [static] |
PushLoopPHIs - Push PHI nodes in the header of the given loop onto the given Worklist.
Definition at line 3176 of file ScalarEvolution.cpp.
References llvm::BasicBlock::begin(), llvm::dyn_cast(), llvm::LoopBase< BlockT, LoopT >::getHeader(), Header, and llvm::SmallVectorImpl< T >::push_back().
Referenced by llvm::ScalarEvolution::forgetLoopBackedgeTakenCount().
| static const SCEV* 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 4097 of file ScalarEvolution.cpp.
References llvm::APInt::countTrailingZeros(), llvm::APInt::getBitWidth(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::APInt::lshr(), Mod, llvm::APInt::multiplicativeInverse(), llvm::APInt::set(), llvm::APInt::trunc(), llvm::APIntOps::urem(), and llvm::APInt::zext().
| static std::pair<const SCEV *,const SCEV *> 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 4141 of file ScalarEvolution.cpp.
References A, llvm::CallingConv::C, Context, llvm::dyn_cast(), llvm::ConstantInt::get(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::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" | ||||
| ) |
Definition at line 387 of file ScalarEvolution.cpp.
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] |