CbC/CbC_llvm: include/llvm/Analysis/ScalarEvolutionExpressions.h comparison

comparison include/llvm/Analysis/ScalarEvolutionExpressions.h @ 77:54457678186b LLVM3.6

LLVM 3.6

author	Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date	Mon, 08 Sep 2014 22:06:00 +0900
parents	95c75e76d11b
children	60c9769439b8

comparison

equal deleted inserted replaced

-:e874dbf0ad9d
+:54457678186b
 //===----------------------------------------------------------------------===//
 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
 #define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Support/ErrorHandling.h"
 namespace llvm {
 assert(i < NumOperands && "Operand index out of range!");
 return Operands[i];
 }
 typedef const SCEV *const *op_iterator;
+typedef iterator_range<op_iterator> op_range;
 op_iterator op_begin() const { return Operands; }
 op_iterator op_end() const { return Operands + NumOperands; }
+op_range operands() const {
+return make_range(op_begin(), op_end());
+}
 Type *getType() const { return getOperand(0)->getType(); }
 NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const {
 return (NoWrapFlags)(SubclassData & Mask);
 return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
 op_end()),
 getLoop(), FlagAnyWrap);
 }
-/// isAffine - Return true if this is an affine AddRec (i.e., it represents
+/// isAffine - Return true if this represents an expression
-/// an expressions A+B*x where A and B are loop invariant values.
+/// 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
+/// isQuadratic - Return true if this represents an expression
-/// represents an expressions A+B*x+C*x^2 where A, B and C are loop
+/// A + B*x + C*x^2 where A, B and C are loop invariant values.
-/// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
+/// This corresponds to an addrec of the form {L,+,M,+,N}
 bool isQuadratic() const {
 return getNumOperands() == 3;
 }
 /// Set flags for a recurrence without clearing any previously set flags.
 /// Methods for support type inquiry through isa, cast, and dyn_cast:
 static inline bool classof(const SCEV *S) {
 return S->getSCEVType() == scAddRecExpr;
 }
-/// Splits the SCEV into two vectors of SCEVs representing the subscripts
+/// Collect parametric terms occurring in step expressions.
-/// and sizes of an array access. Returns the remainder of the
+void collectParametricTerms(ScalarEvolution &SE,
-/// delinearization that is the offset start of the array.
+SmallVectorImpl<const SCEV *> &Terms) const;
-const SCEV *delinearize(ScalarEvolution &SE,
-SmallVectorImpl<const SCEV *> &Subscripts,
+/// Return in Subscripts the access functions for each dimension in Sizes.
-SmallVectorImpl<const SCEV *> &Sizes) const;
+void 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.
+///
+/// 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].
+void delinearize(ScalarEvolution &SE,
+SmallVectorImpl<const SCEV *> &Subscripts,
+SmallVectorImpl<const SCEV *> &Sizes,
+const SCEV *ElementSize) const;
 };
 //===--------------------------------------------------------------------===//
 /// SCEVSMaxExpr - This class represents a signed maximum selection.
 ///
 ///
 class SCEVUnknown : public SCEV, private CallbackVH {
 friend class ScalarEvolution;
 // Implement CallbackVH.
-virtual void deleted();
+void deleted() override;
-virtual void allUsesReplacedWith(Value *New);
+void allUsesReplacedWith(Value *New) override;
 /// SE - The parent ScalarEvolution value. This is used to update
 /// the parent's maps when the value associated with a SCEVUnknown
 /// is deleted or RAUW'd.
 ScalarEvolution *SE;
 /// the SCEVUnknown components following the Map (Value -> Value).
 struct SCEVParameterRewriter
 : public SCEVVisitor<SCEVParameterRewriter, const SCEV*> {
 public:
 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE,
-ValueToValueMap &Map) {
+ValueToValueMap &Map,
-SCEVParameterRewriter Rewriter(SE, Map);
+bool InterpretConsts = false) {
+SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts);
 return Rewriter.visit(Scev);
 }
-SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M)
+SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M, bool C)
-: SE(S), Map(M) {}
+: SE(S), Map(M), InterpretConsts(C) {}
 const SCEV *visitConstant(const SCEVConstant *Constant) {
 return Constant;
 }
 return SE.getUMaxExpr(Operands);
 }
 const SCEV *visitUnknown(const SCEVUnknown *Expr) {
 Value *V = Expr->getValue();
-if (Map.count(V))
+if (Map.count(V)) {
-return SE.getUnknown(Map[V]);
+Value *NV = Map[V];
+if (InterpretConsts && isa<ConstantInt>(NV))
+return SE.getConstant(cast<ConstantInt>(NV));
+return SE.getUnknown(NV);
+}
 return Expr;
 }
 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
 return Expr;
 }
 private:
 ScalarEvolution &SE;
 ValueToValueMap &Map;
+bool InterpretConsts;
 };
 typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT;
 /// The SCEVApplyRewriter takes a scalar evolution expression and applies

Mercurial > hg > CbC > CbC_llvm

comparison include/llvm/Analysis/ScalarEvolutionExpressions.h @ 77:54457678186b LLVM3.6