#include <ScalarEvolutionExpressions.h>
Detailed Description
SCEVAddRecExpr - This node represents a polynomial recurrence on the trip count of the specified loop. This is the primary focus of the ScalarEvolution framework; all the other SCEV subclasses are mostly just supporting infrastructure to allow SCEVAddRecExpr expressions to be created and analyzed.
All operands of an AddRec are required to be loop invariant.
Definition at line 288 of file ScalarEvolutionExpressions.h.
Member Function Documentation
| static bool llvm::SCEVAddRecExpr::classof | ( | const SCEV * | S | ) | [inline, static] |
Methods for support type inquiry through isa, cast, and dyn_cast:
Reimplemented from llvm::SCEVNAryExpr.
Definition at line 356 of file ScalarEvolutionExpressions.h.
References llvm::SCEV::getSCEVType(), and llvm::scAddRecExpr.
| void SCEVAddRecExpr::collectParametricTerms | ( | ScalarEvolution & | SE, |
| SmallVectorImpl< const SCEV * > & | Terms | ||
| ) | const |
Collect parametric terms occurring in step expressions.
Find parametric terms in this SCEVAddRecExpr.
Definition at line 6979 of file ScalarEvolution.cpp.
References llvm::dbgs(), DEBUG, and llvm::visitAll().
Referenced by delinearize().
| void SCEVAddRecExpr::computeAccessFunctions | ( | ScalarEvolution & | SE, |
| SmallVectorImpl< const SCEV * > & | Subscripts, | ||
| SmallVectorImpl< const SCEV * > & | Sizes | ||
| ) | const |
Return in Subscripts the access functions for each dimension in Sizes.
Third step of delinearization: compute the access functions for the Subscripts based on the dimensions in Sizes.
Definition at line 7461 of file ScalarEvolution.cpp.
References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), DEBUG, llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), isAffine(), llvm::IndexedInstrProf::Last, llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), and llvm::SmallVectorTemplateCommon< T, typename >::size().
Referenced by delinearize().
| void SCEVAddRecExpr::delinearize | ( | ScalarEvolution & | SE, |
| SmallVectorImpl< const SCEV * > & | Subscripts, | ||
| SmallVectorImpl< const SCEV * > & | Sizes, | ||
| const SCEV * | ElementSize | ||
| ) | const |
Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array access.
The delinearization is a 3 step process: the first two steps compute the sizes of each subscript and the third step computes the access functions for the delinearized array:
1. Find the terms in the step functions 2. Compute the array size 3. Compute the access function: divide the SCEV by the array size starting with the innermost dimensions found in step 2. The Quotient is the SCEV to be divided in the next step of the recursion. The Remainder is the subscript of the innermost dimension. Loop over all array dimensions computed in step 2.
To compute a uniform array size for several memory accesses to the same object, one can collect in step 1 all the step terms for all the memory accesses, and compute in step 2 a unique array shape. This guarantees that the array shape will be the same across all memory accesses.
FIXME: We could derive the result of steps 1 and 2 from a description of the array shape given in metadata.
Example:
A[][n][m]
for i for j for k A[j+k][2i][5i] =
The initial SCEV:
A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
1. Find the different terms in the step functions: -> [2*m, 5, n*m, n*m]
2. Compute the array size: sort and unique them -> [n*m, 2*m, 5] find the GCD of all the terms = 1 divide by the GCD and erase constant terms -> [n*m, 2*m] GCD = m divide by GCD -> [n, 2] remove constant terms -> [n] size of the array is A[unknown][n][m]
3. Compute the access function a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k The remainder is the subscript of the innermost array dimension: [5i].
b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k The Remainder is the subscript of the next array dimension: [2i].
The subscript of the outermost dimension is the Quotient: [j+k].
Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
Splits the SCEV into two vectors of SCEVs representing the subscripts and sizes of an array access. Returns the remainder of the delinearization that is the offset start of the array. The SCEV->delinearize algorithm computes the multiples of SCEV coefficients: that is a pattern matching of sub expressions in the stride and base of a SCEV corresponding to the computation of a GCD (greatest common divisor) of base and stride. When SCEV->delinearize fails, it returns the SCEV unchanged.
For example: when analyzing the memory access A[i][j][k] in this loop nest
void foo(long n, long m, long o, double A[n][m][o]) {
for (long i = 0; i < n; i++) for (long j = 0; j < m; j++) for (long k = 0; k < o; k++) A[i][j][k] = 1.0; }
the delinearization input is the following AddRec SCEV:
AddRec: {{{A,+,(8 * m * o)}<for.i>,+,(8 * o)}<for.j>,+,8}<for.k>
From this SCEV, we are able to say that the base offset of the access is A because it appears as an offset that does not divide any of the strides in the loops:
CHECK: Base offset: A
and then SCEV->delinearize determines the size of some of the dimensions of the array as these are the multiples by which the strides are happening:
CHECK: ArrayDecl[UnknownSize][m][o] with elements of sizeof(double) bytes.
Note that the outermost dimension remains of UnknownSize because there are no strides that would help identifying the size of the last dimension: when the array has been statically allocated, one could compute the size of that dimension by dividing the overall size of the array by the size of the known dimensions: m * o * 8.
Finally delinearize provides the access functions for the array reference that does correspond to A[i][j][k] of the above C testcase:
CHECK: ArrayRef[{0,+,1}<for.i>][{0,+,1}<for.j>][{0,+,1}<for.k>]
The testcases are checking the output of a function pass: DelinearizationPass that walks through all loads and stores of a function asking for the SCEV of the memory access with respect to all enclosing loops, calling SCEV->delinearize on that and printing the results.
Definition at line 7565 of file ScalarEvolution.cpp.
References collectParametricTerms(), computeAccessFunctions(), llvm::dbgs(), DEBUG, llvm::SmallVectorBase::empty(), and llvm::ScalarEvolution::findArrayDimensions().
| const SCEV * SCEVAddRecExpr::evaluateAtIteration | ( | const SCEV * | It, |
| ScalarEvolution & | SE | ||
| ) | const |
evaluateAtIteration - Return the value of this chain of recurrences at the specified iteration number.
evaluateAtIteration - Return the value of this chain of recurrences at the specified iteration number. We can evaluate this recurrence by multiplying each element in the chain by the binomial coefficient corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as:
A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3)
where BC(It, k) stands for binomial coefficient.
Definition at line 803 of file ScalarEvolution.cpp.
References BinomialCoefficient(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMulExpr(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), getStart(), and llvm::SCEVNAryExpr::getType().
Referenced by EvaluateConstantChrecAtConstant(), and llvm::SCEVApplyRewriter::visitAddRecExpr().
| const Loop* llvm::SCEVAddRecExpr::getLoop | ( | ) | const [inline] |
Definition at line 299 of file ScalarEvolutionExpressions.h.
Referenced by CollectSubexprs(), findIVOperand(), FindLoopCounter(), genLoopLimit(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getMulExpr(), getNumIterationsInRange(), getPreStartForSignExtend(), getStepRecurrence(), isExistingPhi(), llvm::ScalarEvolution::isKnownPredicate(), isSimpleIVUser(), isStridedPtr(), llvm::SCEV::print(), llvm::SCEVParameterRewriter::visitAddRecExpr(), and llvm::SCEVApplyRewriter::visitAddRecExpr().
| const SCEV * SCEVAddRecExpr::getNumIterationsInRange | ( | ConstantRange | Range, |
| ScalarEvolution & | SE | ||
| ) | const |
getNumIterationsInRange - Return the number of iterations of this loop that produce values in the specified constant range. Another way of looking at this is that it returns the first iteration number where the value is not in the condition, thus computing the exit count. If the iteration count can't be computed, an instance of SCEVCouldNotCompute is returned.
Definition at line 6783 of file ScalarEvolution.cpp.
References llvm::ARM_PROC::A, llvm::ConstantRange::contains(), llvm::dyn_cast(), EvaluateConstantChrecAtConstant(), llvm::SCEV::FlagAnyWrap, llvm::SCEV::FlagNW, llvm::ConstantInt::get(), llvm::ScalarEvolution::getAddRecExpr(), llvm::ScalarEvolution::getConstant(), llvm::ScalarEvolution::getContext(), llvm::ScalarEvolution::getCouldNotCompute(), llvm::ConstantExpr::getICmp(), getLoop(), llvm::ConstantRange::getLower(), llvm::ScalarEvolution::getNegativeSCEV(), llvm::SCEVNAryExpr::getNoWrapFlags(), llvm::SCEVNAryExpr::getNumOperands(), llvm::SCEVNAryExpr::getOperand(), getStart(), llvm::SCEVNAryExpr::getType(), llvm::ScalarEvolution::getTypeSizeInBits(), llvm::ConstantRange::getUpper(), llvm::SCEVConstant::getValue(), llvm::ConstantInt::getValue(), llvm::CmpInst::ICMP_ULT, isAffine(), llvm::ConstantRange::isFullSet(), isQuadratic(), llvm::SCEVNAryExpr::op_begin(), llvm::SCEVNAryExpr::op_end(), llvm::SCEVNAryExpr::Operands, llvm::PPCISD::SC, llvm::APInt::sge(), SolveQuadraticEquation(), llvm::ConstantRange::subtract(), std::swap(), and llvm::APIntOps::udiv().
| const SCEVAddRecExpr* llvm::SCEVAddRecExpr::getPostIncExpr | ( | ScalarEvolution & | SE | ) | const [inline] |
getPostIncExpr - Return an expression representing the value of this expression one iteration of the loop ahead.
Definition at line 351 of file ScalarEvolutionExpressions.h.
References llvm::ScalarEvolution::getAddExpr(), and getStepRecurrence().
Referenced by llvm::ScalarEvolution::isKnownPredicate().
| const SCEV* llvm::SCEVAddRecExpr::getStart | ( | ) | const [inline] |
Definition at line 298 of file ScalarEvolutionExpressions.h.
References llvm::SCEVNAryExpr::Operands.
Referenced by canBeCheaplyTransformed(), CollectSubexprs(), evaluateAtIteration(), FindLoopCounter(), genLoopLimit(), llvm::ScalarEvolution::getAddExpr(), getNumIterationsInRange(), getPreStartForSignExtend(), getSignExtendAddRecStart(), and llvm::ScalarEvolution::isKnownPredicate().
| const SCEV* llvm::SCEVAddRecExpr::getStepRecurrence | ( | ScalarEvolution & | SE | ) | const [inline] |
getStepRecurrence - This method constructs and returns the recurrence indicating how much this expression steps by. If this is a polynomial of degree N, it returns a chrec of degree N-1. We cannot determine whether the step recurrence has self-wraparound.
Definition at line 305 of file ScalarEvolutionExpressions.h.
References llvm::SCEV::FlagAnyWrap, llvm::ScalarEvolution::getAddRecExpr(), getLoop(), llvm::SCEVNAryExpr::getOperand(), isAffine(), llvm::SCEVNAryExpr::op_begin(), and llvm::SCEVNAryExpr::op_end().
Referenced by CollectSubexprs(), FindLoopCounter(), genLoopLimit(), getPostIncExpr(), getPreStartForSignExtend(), getSignExtendAddRecStart(), getStrideFromPointer(), isLikelyComplexAddressComputation(), and isStridedPtr().
| bool llvm::SCEVAddRecExpr::isAffine | ( | ) | const [inline] |
isAffine - Return true if this represents an expression A + B*x where A and B are loop invariant values.
Definition at line 314 of file ScalarEvolutionExpressions.h.
References llvm::SCEVNAryExpr::getNumOperands().
Referenced by computeAccessFunctions(), FindLoopCounter(), genLoopLimit(), getNumIterationsInRange(), getStepRecurrence(), and hasComputableBounds().
| bool llvm::SCEVAddRecExpr::isQuadratic | ( | ) | const [inline] |
isQuadratic - Return true if this represents an expression A + B*x + C*x^2 where A, B and C are loop invariant values. This corresponds to an addrec of the form {L,+,M,+,N}
Definition at line 323 of file ScalarEvolutionExpressions.h.
References llvm::SCEVNAryExpr::getNumOperands().
Referenced by getNumIterationsInRange().
| void llvm::SCEVAddRecExpr::setNoWrapFlags | ( | NoWrapFlags | Flags | ) | [inline] |
Set flags for a recurrence without clearing any previously set flags. For AddRec, either NUW or NSW implies NW. Keep track of this fact here to make it easier to propagate flags.
Definition at line 330 of file ScalarEvolutionExpressions.h.
References llvm::SCEV::FlagNSW, llvm::SCEV::FlagNUW, llvm::SCEV::FlagNW, llvm::ScalarEvolution::setFlags(), and llvm::SCEV::SubclassData.
Referenced by llvm::ScalarEvolution::getAddRecExpr().
Friends And Related Function Documentation
friend class ScalarEvolution [friend] |
Definition at line 289 of file ScalarEvolutionExpressions.h.
The documentation for this class was generated from the following files:
1.7.6.1