#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
-#include "llvm/ADT/iterator_range.h"
#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Support/ErrorHandling.h"
getLoop(), FlagAnyWrap);
}
- /// isAffine - Return true if this is an affine AddRec (i.e., it represents
- /// an expressions A+B*x where A and B are loop invariant values.
+ /// isAffine - Return true if this represents an expression
+ /// A + B*x where A and B are loop invariant values.
bool isAffine() const {
// We know that the start value is invariant. This expression is thus
// affine iff the step is also invariant.
return getNumOperands() == 2;
}
- /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
- /// represents an expressions 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}
+ /// 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}
bool isQuadratic() const {
return getNumOperands() == 3;
}
static inline bool classof(const SCEV *S) {
return S->getSCEVType() == scAddRecExpr;
}
-
- /// Collect parametric terms occurring in step expressions.
- void collectParametricTerms(ScalarEvolution &SE,
- SmallVectorImpl<const SCEV *> &Terms) const;
-
- /// Return in Subscripts the access functions for each dimension in Sizes.
- const SCEV *
- computeAccessFunctions(ScalarEvolution &SE,
- SmallVectorImpl<const SCEV *> &Subscripts,
- SmallVectorImpl<const SCEV *> &Sizes) const;
-
- /// Split this SCEVAddRecExpr 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 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].
- const SCEV *delinearize(ScalarEvolution &SE,
- SmallVectorImpl<const SCEV *> &Subscripts,
- SmallVectorImpl<const SCEV *> &Sizes) const;
};
//===--------------------------------------------------------------------===//
/// value, and only represent it as its LLVM Value. This is the "bottom"
/// value for the analysis.
///
- class SCEVUnknown : public SCEV, private CallbackVH {
+ class SCEVUnknown final : public SCEV, private CallbackVH {
friend class ScalarEvolution;
// Implement CallbackVH.
SmallPtrSet<const SCEV *, 8> Visited;
void push(const SCEV *S) {
- if (Visited.insert(S) && Visitor.follow(S))
+ if (Visited.insert(S).second && Visitor.follow(S))
Worklist.push_back(S);
}
public:
}
};
- /// Use SCEVTraversal to visit all nodes in the givien expression tree.
+ /// Use SCEVTraversal to visit all nodes in the given expression tree.
template<typename SV>
void visitAll(const SCEV *Root, SV& Visitor) {
SCEVTraversal<SV> T(Visitor);
projects / oota-llvm.git / blobdiff