From 5026b2cc8b1e49412a4dcf29dab578a8a297a172 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Wed, 7 May 2014 18:01:20 +0000 Subject: [PATCH] split delinearization pass in 3 steps To compute the dimensions of the array in a unique way, we split the delinearization analysis in three steps: - find parametric terms in all memory access functions - compute the array dimensions from the set of terms - compute the delinearized access functions for each dimension The first step is executed on all the memory access functions such that we gather all the patterns in which an array is accessed. The second step reduces all this information in a unique description of the sizes of the array. The third step is delinearizing each memory access function following the common description of the shape of the array computed in step 2. This rewrite of the delinearization pass also solves a problem we had with the previous implementation: because the previous algorithm was by induction on the structure of the SCEV, it would not correctly recognize the shape of the array when the memory access was not following the nesting of the loops: for example, see polly/test/ScopInfo/multidim_only_ivs_3d_reverse.ll ; 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][k][j] = 1.0; Starting with this patch we no longer delinearize access functions that do not contain parameters, for example in test/Analysis/DependenceAnalysis/GCD.ll ;; for (long int i = 0; i < 100; i++) ;; for (long int j = 0; j < 100; j++) { ;; A[2*i - 4*j] = i; ;; *B++ = A[6*i + 8*j]; these accesses will not be delinearized as the upper bound of the loops are constants, and their access functions do not contain SCEVUnknown parameters. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208232 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Analysis/ScalarEvolutionExpressions.h | 82 +- lib/Analysis/Delinearization.cpp | 5 +- lib/Analysis/DependenceAnalysis.cpp | 58 +- lib/Analysis/ScalarEvolution.cpp | 818 ++++++++++-------- test/Analysis/Delinearization/a.ll | 11 - test/Analysis/Delinearization/himeno_1.ll | 10 - test/Analysis/Delinearization/himeno_2.ll | 10 - .../multidim_ivs_and_integer_offsets_3d.ll | 10 - ...multidim_ivs_and_integer_offsets_nts_3d.ll | 10 - ...multidim_ivs_and_parameteric_offsets_3d.ll | 10 - .../Delinearization/multidim_only_ivs_2d.ll | 5 - .../multidim_only_ivs_2d_nested.ll | 2 + .../Delinearization/multidim_only_ivs_3d.ll | 10 - .../multidim_only_ivs_3d_cast.ll | 10 - test/Analysis/DependenceAnalysis/Banerjee.ll | 22 +- test/Analysis/DependenceAnalysis/GCD.ll | 22 +- 16 files changed, 588 insertions(+), 507 deletions(-) diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 985fc74a719..0a8a03076ac 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -357,9 +357,87 @@ namespace llvm { return S->getSCEVType() == scAddRecExpr; } - /// Splits the SCEV into two vectors of SCEVs representing the subscripts - /// and sizes of an array access. Returns the remainder of the + /// Collect parametric terms occurring in step expressions. + void collectParametricTerms(ScalarEvolution &SE, + SmallVectorImpl &Terms) const; + + /// Compute the array dimensions Sizes from the set of Terms extracted from + /// the memory access function of this SCEVAddRecExpr. + void findArrayDimensions(ScalarEvolution &SE, + SmallVectorImpl &Terms, + SmallVectorImpl &Sizes) const; + + /// Return in Subscripts the access functions for each dimension in Sizes. + const SCEV * + computeAccessFunctions(ScalarEvolution &SE, + SmallVectorImpl &Subscripts, + SmallVectorImpl &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 &Subscripts, SmallVectorImpl &Sizes) const; diff --git a/lib/Analysis/Delinearization.cpp b/lib/Analysis/Delinearization.cpp index 3623f30e52e..1a588211a23 100644 --- a/lib/Analysis/Delinearization.cpp +++ b/lib/Analysis/Delinearization.cpp @@ -109,13 +109,14 @@ void Delinearization::print(raw_ostream &O, const Module *) const { SmallVector Subscripts, Sizes; const SCEV *Res = AR->delinearize(*SE, Subscripts, Sizes); - int Size = Subscripts.size(); - if (Res == AR || Size == 0) { + if (Res == AR || Subscripts.size() == 0 || Sizes.size() == 0 || + Subscripts.size() != Sizes.size()) { O << "failed to delinearize\n"; continue; } O << "Base offset: " << *Res << "\n"; O << "ArrayDecl[UnknownSize]"; + int Size = Subscripts.size(); for (int i = 0; i < Size - 1; i++) O << "[" << *Sizes[i] << "]"; O << " with elements of " << *Sizes[Size - 1] << " bytes.\n"; diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp index 489396c460b..96acda3f45c 100644 --- a/lib/Analysis/DependenceAnalysis.cpp +++ b/lib/Analysis/DependenceAnalysis.cpp @@ -3188,27 +3188,24 @@ DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine()) return false; - SmallVector SrcSubscripts, DstSubscripts, SrcSizes, DstSizes; - const SCEV *RemainderS = SrcAR->delinearize(*SE, SrcSubscripts, SrcSizes); - const SCEV *RemainderD = DstAR->delinearize(*SE, DstSubscripts, DstSizes); + // First step: collect parametric terms in both array references. + SmallVector Terms; + SrcAR->collectParametricTerms(*SE, Terms); + DstAR->collectParametricTerms(*SE, Terms); - int size = SrcSubscripts.size(); - // Fail when there is only a subscript: that's a linearized access function. - if (size < 2) - return false; + // Second step: find subscript sizes. + SmallVector Sizes; + SrcAR->findArrayDimensions(*SE, Terms, Sizes); - int dstSize = DstSubscripts.size(); - // Fail when the number of subscripts in Src and Dst differ. - if (size != dstSize) - return false; + // Third step: compute the access functions for each subscript. + SmallVector SrcSubscripts, DstSubscripts; + const SCEV *RemainderS = SrcAR->computeAccessFunctions(*SE, SrcSubscripts, Sizes); + const SCEV *RemainderD = DstAR->computeAccessFunctions(*SE, DstSubscripts, Sizes); - // Fail when the size of any of the subscripts in Src and Dst differs: the - // dependence analysis assumes that elements in the same array have same size. - // SCEV delinearization does not have a context based on which it would decide - // globally the size of subscripts that would best fit all the array accesses. - for (int i = 0; i < size; ++i) - if (SrcSizes[i] != DstSizes[i]) - return false; + // Fail when there is only a subscript: that's a linearized access function. + if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 || + SrcSubscripts.size() != DstSubscripts.size()) + return false; // When the difference in remainders is different than a constant it might be // that the base address of the arrays is not the same. @@ -3216,23 +3213,16 @@ DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, if (!isa(DiffRemainders)) return false; - // Normalize the last dimension: integrate the size of the "scalar dimension" - // and the remainder of the delinearization. - DstSubscripts[size-1] = SE->getMulExpr(DstSubscripts[size-1], - DstSizes[size-1]); - SrcSubscripts[size-1] = SE->getMulExpr(SrcSubscripts[size-1], - SrcSizes[size-1]); - SrcSubscripts[size-1] = SE->getAddExpr(SrcSubscripts[size-1], RemainderS); - DstSubscripts[size-1] = SE->getAddExpr(DstSubscripts[size-1], RemainderD); + int size = SrcSubscripts.size(); -#ifndef NDEBUG - DEBUG(errs() << "\nSrcSubscripts: "); - for (int i = 0; i < size; i++) - DEBUG(errs() << *SrcSubscripts[i]); - DEBUG(errs() << "\nDstSubscripts: "); - for (int i = 0; i < size; i++) - DEBUG(errs() << *DstSubscripts[i]); -#endif + DEBUG({ + dbgs() << "\nSrcSubscripts: "; + for (int i = 0; i < size; i++) + dbgs() << *SrcSubscripts[i]; + dbgs() << "\nDstSubscripts: "; + for (int i = 0; i < size; i++) + dbgs() << *DstSubscripts[i]; + }); // The delinearization transforms a single-subscript MIV dependence test into // a multi-subscript SIV dependence test that is easier to compute. So we diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 28f0a8c5cfb..7d84dbee5c5 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -6815,6 +6815,70 @@ const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, return SE.getCouldNotCompute(); } +namespace { +// Collect all steps of SCEV expressions. +struct SCEVCollectStrides { + ScalarEvolution &SE; + SmallVectorImpl &Strides; + + SCEVCollectStrides(ScalarEvolution &SE, SmallVectorImpl &S) + : SE(SE), Strides(S) {} + + bool follow(const SCEV *S) { + if (const SCEVAddRecExpr *AR = dyn_cast(S)) + Strides.push_back(AR->getStepRecurrence(SE)); + return true; + } + bool isDone() const { return false; } +}; + +// Collect all SCEVUnknown and SCEVMulExpr expressions. +struct SCEVCollectTerms { + SmallVectorImpl &Terms; + + SCEVCollectTerms(SmallVectorImpl &T) + : Terms(T) {} + + bool follow(const SCEV *S) { + if (isa(S) || isa(S) || isa(S)) { + Terms.push_back(S); + + // Stop recursion: once we collected a term, do not walk its operands. + return false; + } + + // Keep looking. + return true; + } + bool isDone() const { return false; } +}; +} + +/// Find parametric terms in this SCEVAddRecExpr. +void SCEVAddRecExpr::collectParametricTerms( + ScalarEvolution &SE, SmallVectorImpl &Terms) const { + SmallVector Strides; + SCEVCollectStrides StrideCollector(SE, Strides); + visitAll(this, StrideCollector); + + DEBUG({ + dbgs() << "Strides:\n"; + for (const SCEV *S : Strides) + dbgs() << *S << "\n"; + }); + + for (const SCEV *S : Strides) { + SCEVCollectTerms TermCollector(Terms); + visitAll(S, TermCollector); + } + + DEBUG({ + dbgs() << "Terms:\n"; + for (const SCEV *T : Terms) + dbgs() << *T << "\n"; + }); +} + static const APInt srem(const SCEVConstant *C1, const SCEVConstant *C2) { APInt A = C1->getValue()->getValue(); APInt B = C2->getValue()->getValue(); @@ -6844,358 +6908,441 @@ static const APInt sdiv(const SCEVConstant *C1, const SCEVConstant *C2) { } namespace { -struct SCEVGCD : public SCEVVisitor { -public: - // Pattern match Step into Start. When Step is a multiply expression, find - // the largest subexpression of Step that appears in Start. When Start is an - // add expression, try to match Step in the subexpressions of Start, non - // matching subexpressions are returned under Remainder. - static const SCEV *findGCD(ScalarEvolution &SE, const SCEV *Start, - const SCEV *Step, const SCEV **Remainder) { - assert(Remainder && "Remainder should not be NULL"); - SCEVGCD R(SE, Step, SE.getConstant(Step->getType(), 0)); - const SCEV *Res = R.visit(Start); - *Remainder = R.Remainder; - return Res; - } - - SCEVGCD(ScalarEvolution &S, const SCEV *G, const SCEV *R) - : SE(S), GCD(G), Remainder(R) { - Zero = SE.getConstant(GCD->getType(), 0); - One = SE.getConstant(GCD->getType(), 1); - } - - const SCEV *visitConstant(const SCEVConstant *Constant) { - if (GCD == Constant || Constant == Zero) - return GCD; - - if (const SCEVConstant *CGCD = dyn_cast(GCD)) { - const SCEV *Res = SE.getConstant(gcd(Constant, CGCD)); - if (Res != One) - return Res; - - Remainder = SE.getConstant(srem(Constant, CGCD)); - Constant = cast(SE.getMinusSCEV(Constant, Remainder)); - Res = SE.getConstant(gcd(Constant, CGCD)); - return Res; - } - - // When GCD is not a constant, it could be that the GCD is an Add, Mul, - // AddRec, etc., in which case we want to find out how many times the - // Constant divides the GCD: we then return that as the new GCD. - const SCEV *Rem = Zero; - const SCEV *Res = findGCD(SE, GCD, Constant, &Rem); +struct FindSCEVSize { + int Size; + FindSCEVSize() : Size(0) {} - if (Res == One || Rem != Zero) { - Remainder = Constant; - return One; - } - - assert(isa(Res) && "Res should be a constant"); - Remainder = SE.getConstant(srem(Constant, cast(Res))); - return Res; - } - - const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { - if (GCD != Expr) - Remainder = Expr; - return GCD; - } - - const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { - if (GCD != Expr) - Remainder = Expr; - return GCD; + bool follow(const SCEV *S) { + ++Size; + // Keep looking at all operands of S. + return true; } - - const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { - if (GCD != Expr) - Remainder = Expr; - return GCD; + bool isDone() const { + return false; } +}; +} - const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { - if (GCD == Expr) - return GCD; +// Returns the size of the SCEV S. +static inline int sizeOfSCEV(const SCEV *S) { + FindSCEVSize F; + SCEVTraversal ST(F); + ST.visitAll(S); + return F.Size; +} - for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { - const SCEV *Rem = Zero; - const SCEV *Res = findGCD(SE, Expr->getOperand(e - 1 - i), GCD, &Rem); +namespace { - // FIXME: There may be ambiguous situations: for instance, - // GCD(-4 + (3 * %m), 2 * %m) where 2 divides -4 and %m divides (3 * %m). - // The order in which the AddExpr is traversed computes a different GCD - // and Remainder. - if (Res != One) - GCD = Res; - if (Rem != Zero) - Remainder = SE.getAddExpr(Remainder, Rem); +struct SCEVDivision : public SCEVVisitor { +public: + // Computes the Quotient and Remainder of the division of Numerator by + // Denominator. + static void divide(ScalarEvolution &SE, const SCEV *Numerator, + const SCEV *Denominator, const SCEV **Quotient, + const SCEV **Remainder) { + assert(Numerator && Denominator && *Quotient && *Remainder && + "Uninitialized SCEV"); + + SCEVDivision D(SE, Numerator, Denominator); + + // Check for the trivial case here to avoid having to check for it in the + // rest of the code. + if (Numerator == Denominator) { + *Quotient = D.One; + *Remainder = D.Zero; + return; } - return GCD; - } - - const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { - if (GCD == Expr) - return GCD; + if (Numerator == D.Zero) { + *Quotient = D.Zero; + *Remainder = D.Zero; + return; + } - for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { - if (Expr->getOperand(i) == GCD) - return GCD; + // Split the Denominator when it is a product. + if (const SCEVMulExpr *T = dyn_cast(Denominator)) { + const SCEV *Q, *R; + *Quotient = Numerator; + for (const SCEV *Op : T->operands()) { + divide(SE, *Quotient, Op, &Q, &R); + *Quotient = Q; + + // Bail out when the Numerator is not divisible by one of the terms of + // the Denominator. + if (R != D.Zero) { + *Quotient = D.Zero; + *Remainder = Numerator; + return; + } + } + *Remainder = D.Zero; + return; } - // If we have not returned yet, it means that GCD is not part of Expr. - const SCEV *PartialGCD = One; - for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { - const SCEV *Rem = Zero; - const SCEV *Res = findGCD(SE, Expr->getOperand(i), GCD, &Rem); - if (Rem != Zero) - // GCD does not divide Expr->getOperand(i). - continue; + D.visit(Numerator); + *Quotient = D.Quotient; + *Remainder = D.Remainder; + } + + SCEVDivision(ScalarEvolution &S, const SCEV *Numerator, const SCEV *Denominator) + : SE(S), Denominator(Denominator) { + Zero = SE.getConstant(Denominator->getType(), 0); + One = SE.getConstant(Denominator->getType(), 1); + + // By default, we don't know how to divide Expr by Denominator. + // Providing the default here simplifies the rest of the code. + Quotient = Zero; + Remainder = Numerator; + } + + // Except in the trivial case described above, we do not know how to divide + // Expr by Denominator for the following functions with empty implementation. + void visitTruncateExpr(const SCEVTruncateExpr *Numerator) {} + void visitZeroExtendExpr(const SCEVZeroExtendExpr *Numerator) {} + void visitSignExtendExpr(const SCEVSignExtendExpr *Numerator) {} + void visitUDivExpr(const SCEVUDivExpr *Numerator) {} + void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {} + void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {} + void visitUnknown(const SCEVUnknown *Numerator) {} + void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {} + + void visitConstant(const SCEVConstant *Numerator) { + if (const SCEVConstant *D = dyn_cast(Denominator)) { + Quotient = SE.getConstant(sdiv(Numerator, D)); + Remainder = SE.getConstant(srem(Numerator, D)); + return; + } + } - if (Res == GCD) - return GCD; - PartialGCD = SE.getMulExpr(PartialGCD, Res); - if (PartialGCD == GCD) - return GCD; + void visitAddRecExpr(const SCEVAddRecExpr *Numerator) { + const SCEV *StartQ, *StartR, *StepQ, *StepR; + assert(Numerator->isAffine() && "Numerator should be affine"); + divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR); + divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR); + Quotient = SE.getAddRecExpr(StartQ, StepQ, Numerator->getLoop(), + Numerator->getNoWrapFlags()); + Remainder = SE.getAddRecExpr(StartR, StepR, Numerator->getLoop(), + Numerator->getNoWrapFlags()); + } + + void visitAddExpr(const SCEVAddExpr *Numerator) { + SmallVector Qs, Rs; + for (const SCEV *Op : Numerator->operands()) { + const SCEV *Q, *R; + divide(SE, Op, Denominator, &Q, &R); + Qs.push_back(Q); + Rs.push_back(R); } - if (PartialGCD != One) - return PartialGCD; - - // Failed to find a PartialGCD: set the Remainder to the full expression, - // and return the GCD. - Remainder = Expr; - const SCEVMulExpr *Mul = dyn_cast(GCD); - if (!Mul) - return GCD; - - // When the GCD is a multiply expression, try to decompose it: - // this occurs when Step does not divide the Start expression - // as in: {(-4 + (3 * %m)),+,(2 * %m)} - for (int i = 0, e = Mul->getNumOperands(); i < e; ++i) { - const SCEV *Rem = Zero; - const SCEV *Res = findGCD(SE, Expr, Mul->getOperand(i), &Rem); - if (Rem == Zero) { - Remainder = Rem; - return Res; - } + if (Qs.size() == 1) { + Quotient = Qs[0]; + Remainder = Rs[0]; + return; } - return GCD; + Quotient = SE.getAddExpr(Qs); + Remainder = SE.getAddExpr(Rs); } - const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { - if (GCD != Expr) - Remainder = Expr; - return GCD; - } + void visitMulExpr(const SCEVMulExpr *Numerator) { + SmallVector Qs; - const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { - if (GCD == Expr) - return GCD; + bool FoundDenominatorTerm = false; + for (const SCEV *Op : Numerator->operands()) { + if (FoundDenominatorTerm) { + Qs.push_back(Op); + continue; + } - if (!Expr->isAffine()) { - Remainder = Expr; - return GCD; + // Check whether Denominator divides one of the product operands. + const SCEV *Q, *R; + divide(SE, Op, Denominator, &Q, &R); + if (R != Zero) { + Qs.push_back(Op); + continue; + } + FoundDenominatorTerm = true; + Qs.push_back(Q); } - const SCEV *Rem = Zero; - const SCEV *Res = findGCD(SE, Expr->getOperand(0), GCD, &Rem); - if (Res == One || Res->isAllOnesValue()) { - Remainder = Expr; - return GCD; + if (FoundDenominatorTerm) { + Remainder = Zero; + if (Qs.size() == 1) + Quotient = Qs[0]; + else + Quotient = SE.getMulExpr(Qs); + return; } - if (Rem != Zero) - Remainder = SE.getAddExpr(Remainder, Rem); - - Rem = Zero; - Res = findGCD(SE, Expr->getOperand(1), Res, &Rem); - if (Rem != Zero || Res == One || Res->isAllOnesValue()) { - Remainder = Expr; - return GCD; + if (!isa(Denominator)) { + Quotient = Zero; + Remainder = Numerator; + return; } - return Res; + // The Remainder is obtained by replacing Denominator by 0 in Numerator. + ValueToValueMap RewriteMap; + RewriteMap[cast(Denominator)->getValue()] = + cast(Zero)->getValue(); + Remainder = SCEVParameterRewriter::rewrite(Numerator, SE, RewriteMap, true); + + // Quotient is (Numerator - Remainder) divided by Denominator. + const SCEV *Q, *R; + const SCEV *Diff = SE.getMinusSCEV(Numerator, Remainder); + if (sizeOfSCEV(Diff) > sizeOfSCEV(Numerator)) { + // This SCEV does not seem to simplify: fail the division here. + Quotient = Zero; + Remainder = Numerator; + return; + } + divide(SE, Diff, Denominator, &Q, &R); + assert(R == Zero && + "(Numerator - Remainder) should evenly divide Denominator"); + Quotient = Q; } - const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { - if (GCD != Expr) - Remainder = Expr; - return GCD; - } +private: + ScalarEvolution &SE; + const SCEV *Denominator, *Quotient, *Remainder, *Zero, *One; +}; +} - const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { - if (GCD != Expr) - Remainder = Expr; - return GCD; - } +// Find the Greatest Common Divisor of A and B. +static const SCEV * +findGCD(ScalarEvolution &SE, const SCEV *A, const SCEV *B) { - const SCEV *visitUnknown(const SCEVUnknown *Expr) { - if (GCD != Expr) - Remainder = Expr; - return GCD; - } + if (const SCEVConstant *CA = dyn_cast(A)) + if (const SCEVConstant *CB = dyn_cast(B)) + return SE.getConstant(gcd(CA, CB)); - const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { + const SCEV *One = SE.getConstant(A->getType(), 1); + if (isa(A) && isa(B)) + return One; + if (isa(A) && isa(B)) return One; + + const SCEV *Q, *R; + if (const SCEVMulExpr *M = dyn_cast(A)) { + SmallVector Qs; + for (const SCEV *Op : M->operands()) + Qs.push_back(findGCD(SE, Op, B)); + return SE.getMulExpr(Qs); + } + if (const SCEVMulExpr *M = dyn_cast(B)) { + SmallVector Qs; + for (const SCEV *Op : M->operands()) + Qs.push_back(findGCD(SE, A, Op)); + return SE.getMulExpr(Qs); } -private: - ScalarEvolution &SE; - const SCEV *GCD, *Remainder, *Zero, *One; -}; + const SCEV *Zero = SE.getConstant(A->getType(), 0); + SCEVDivision::divide(SE, A, B, &Q, &R); + if (R == Zero) + return B; -struct SCEVDivision : public SCEVVisitor { -public: - // Remove from Start all multiples of Step. - static const SCEV *divide(ScalarEvolution &SE, const SCEV *Start, - const SCEV *Step) { - SCEVDivision D(SE, Step); - const SCEV *Rem = D.Zero; - (void)Rem; - // The division is guaranteed to succeed: Step should divide Start with no - // remainder. - assert(Step == SCEVGCD::findGCD(SE, Start, Step, &Rem) && Rem == D.Zero && - "Step should divide Start with no remainder."); - return D.visit(Start); - } + SCEVDivision::divide(SE, B, A, &Q, &R); + if (R == Zero) + return A; - SCEVDivision(ScalarEvolution &S, const SCEV *G) : SE(S), GCD(G) { - Zero = SE.getConstant(GCD->getType(), 0); - One = SE.getConstant(GCD->getType(), 1); - } + return One; +} - const SCEV *visitConstant(const SCEVConstant *Constant) { - if (GCD == Constant) - return One; +// Find the Greatest Common Divisor of all the SCEVs in Terms. +static const SCEV * +findGCD(ScalarEvolution &SE, SmallVectorImpl &Terms) { + assert(Terms.size() > 0 && "Terms vector is empty"); - if (const SCEVConstant *CGCD = dyn_cast(GCD)) - return SE.getConstant(sdiv(Constant, CGCD)); - return Constant; - } + const SCEV *GCD = Terms[0]; + for (const SCEV *T : Terms) + GCD = findGCD(SE, GCD, T); - const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { - if (GCD == Expr) - return One; - return Expr; - } + return GCD; +} + +static void findArrayDimensionsRec(ScalarEvolution &SE, + SmallVectorImpl &Terms, + SmallVectorImpl &Sizes, + const SCEV *Zero, const SCEV *One) { + // The GCD of all Terms is the dimension of the innermost dimension. + const SCEV *GCD = findGCD(SE, Terms); + + // End of recursion. + if (Terms.size() == 1) { + if (const SCEVMulExpr *M = dyn_cast(GCD)) { + SmallVector Qs; + for (const SCEV *Op : M->operands()) + if (!isa(Op)) + Qs.push_back(Op); + + GCD = SE.getMulExpr(Qs); + } - const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { - if (GCD == Expr) - return One; - return Expr; + Sizes.push_back(GCD); + return; } - const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { - if (GCD == Expr) - return One; - return Expr; + for (unsigned I = 0; I < Terms.size(); ++I) { + // Normalize the terms before the next call to findArrayDimensionsRec. + const SCEV *Q, *R; + SCEVDivision::divide(SE, Terms[I], GCD, &Q, &R); + assert(R == Zero && "GCD does not evenly divide one of the terms"); + Terms[I] = Q; } - const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { - if (GCD == Expr) - return One; + // Remove all SCEVConstants. + for (unsigned I = 0; I < Terms.size();) + if (isa(Terms[I])) + Terms.erase(Terms.begin() + I); + else + ++I; - SmallVector Operands; - for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) - Operands.push_back(divide(SE, Expr->getOperand(i), GCD)); + if (Terms.size() > 0) + findArrayDimensionsRec(SE, Terms, Sizes, Zero, One); + Sizes.push_back(GCD); +} + +namespace { +struct FindParameter { + bool FoundParameter; + FindParameter() : FoundParameter(false) {} - if (Operands.size() == 1) - return Operands[0]; - return SE.getAddExpr(Operands); + bool follow(const SCEV *S) { + if (isa(S)) { + FoundParameter = true; + // Stop recursion: we found a parameter. + return false; + } + // Keep looking. + return true; + } + bool isDone() const { + // Stop recursion if we have found a parameter. + return FoundParameter; } +}; +} - const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { - if (GCD == Expr) - return One; +// Returns true when S contains at least a SCEVUnknown parameter. +static inline bool +containsParameters(const SCEV *S) { + FindParameter F; + SCEVTraversal ST(F); + ST.visitAll(S); - bool FoundGCDTerm = false; - for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) - if (Expr->getOperand(i) == GCD) - FoundGCDTerm = true; + return F.FoundParameter; +} - SmallVector Operands; - if (FoundGCDTerm) { - FoundGCDTerm = false; - for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { - if (FoundGCDTerm) - Operands.push_back(Expr->getOperand(i)); - else if (Expr->getOperand(i) == GCD) - FoundGCDTerm = true; - else - Operands.push_back(Expr->getOperand(i)); - } - } else { - const SCEV *PartialGCD = One; - for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { - if (PartialGCD == GCD) { - Operands.push_back(Expr->getOperand(i)); - continue; - } +// Returns true when one of the SCEVs of Terms contains a SCEVUnknown parameter. +static inline bool +containsParameters(SmallVectorImpl &Terms) { + for (const SCEV *T : Terms) + if (containsParameters(T)) + return true; + return false; +} - const SCEV *Rem = Zero; - const SCEV *Res = SCEVGCD::findGCD(SE, Expr->getOperand(i), GCD, &Rem); - if (Rem == Zero) { - PartialGCD = SE.getMulExpr(PartialGCD, Res); - Operands.push_back(divide(SE, Expr->getOperand(i), Res)); - } else { - Operands.push_back(Expr->getOperand(i)); - } - } - } +// Return the number of product terms in S. +static inline int numberOfTerms(const SCEV *S) { + if (const SCEVMulExpr *Expr = dyn_cast(S)) + return Expr->getNumOperands(); + return 1; +} - if (Operands.size() == 1) - return Operands[0]; - return SE.getMulExpr(Operands); - } +/// Second step of delinearization: compute the array dimensions Sizes from the +/// set of Terms extracted from the memory access function of this SCEVAddRec. +void SCEVAddRecExpr::findArrayDimensions( + ScalarEvolution &SE, SmallVectorImpl &Terms, + SmallVectorImpl &Sizes) const { - const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { - if (GCD == Expr) - return One; - return Expr; - } + if (Terms.size() < 2) + return; - const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { - if (GCD == Expr) - return One; + // Early return when Terms do not contain parameters: we do not delinearize + // non parametric SCEVs. + if (!containsParameters(Terms)) + return; - assert(Expr->isAffine() && "Expr should be affine"); + DEBUG({ + dbgs() << "Terms:\n"; + for (const SCEV *T : Terms) + dbgs() << *T << "\n"; + }); - const SCEV *Start = divide(SE, Expr->getStart(), GCD); - const SCEV *Step = divide(SE, Expr->getStepRecurrence(SE), GCD); + // Remove duplicates. + std::sort(Terms.begin(), Terms.end()); + Terms.erase(std::unique(Terms.begin(), Terms.end()), Terms.end()); - return SE.getAddRecExpr(Start, Step, Expr->getLoop(), - Expr->getNoWrapFlags()); - } + // Put larger terms first. + std::sort(Terms.begin(), Terms.end(), [](const SCEV *LHS, const SCEV *RHS) { + return numberOfTerms(LHS) > numberOfTerms(RHS); + }); - const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { - if (GCD == Expr) - return One; - return Expr; - } + DEBUG({ + dbgs() << "Terms after sorting:\n"; + for (const SCEV *T : Terms) + dbgs() << *T << "\n"; + }); - const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { - if (GCD == Expr) - return One; - return Expr; - } + const SCEV *Zero = SE.getConstant(this->getType(), 0); + const SCEV *One = SE.getConstant(this->getType(), 1); + findArrayDimensionsRec(SE, Terms, Sizes, Zero, One); - const SCEV *visitUnknown(const SCEVUnknown *Expr) { - if (GCD == Expr) - return One; - return Expr; - } + DEBUG({ + dbgs() << "Sizes:\n"; + for (const SCEV *S : Sizes) + dbgs() << *S << "\n"; + }); +} - const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { - return Expr; +/// Third step of delinearization: compute the access functions for the +/// Subscripts based on the dimensions in Sizes. +const SCEV *SCEVAddRecExpr::computeAccessFunctions( + ScalarEvolution &SE, SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes) const { + // Early exit in case this SCEV is not an affine multivariate function. + const SCEV *Zero = SE.getConstant(this->getType(), 0); + if (!this->isAffine()) + return Zero; + + const SCEV *Res = this, *Remainder = Zero; + int Last = Sizes.size() - 1; + for (int i = Last; i >= 0; i--) { + const SCEV *Q, *R; + SCEVDivision::divide(SE, Res, Sizes[i], &Q, &R); + + DEBUG({ + dbgs() << "Res: " << *Res << "\n"; + dbgs() << "Sizes[i]: " << *Sizes[i] << "\n"; + dbgs() << "Res divided by Sizes[i]:\n"; + dbgs() << "Quotient: " << *Q << "\n"; + dbgs() << "Remainder: " << *R << "\n"; + }); + + Res = Q; + + if (i == Last) { + // Do not record the last subscript corresponding to the size of elements + // in the array. + Remainder = R; + continue; + } + + // Record the access function for the current subscript. + Subscripts.push_back(R); } -private: - ScalarEvolution &SE; - const SCEV *GCD, *Zero, *One; -}; + // Also push in last position the remainder of the last division: it will be + // the access function of the innermost dimension. + Subscripts.push_back(Res); + + std::reverse(Subscripts.begin(), Subscripts.end()); + + DEBUG({ + dbgs() << "Subscripts:\n"; + for (const SCEV *S : Subscripts) + dbgs() << *S << "\n"; + }); + return Remainder; } /// Splits the SCEV into two vectors of SCEVs representing the subscripts and @@ -7251,78 +7398,27 @@ const SCEV * SCEVAddRecExpr::delinearize(ScalarEvolution &SE, SmallVectorImpl &Subscripts, SmallVectorImpl &Sizes) const { - // Early exit in case this SCEV is not an affine multivariate function. - if (!this->isAffine()) - return this; - - const SCEV *Start = this->getStart(); - const SCEV *Step = this->getStepRecurrence(SE); - - // Build the SCEV representation of the canonical induction variable in the - // loop of this SCEV. - const SCEV *Zero = SE.getConstant(this->getType(), 0); - const SCEV *One = SE.getConstant(this->getType(), 1); - const SCEV *IV = - SE.getAddRecExpr(Zero, One, this->getLoop(), this->getNoWrapFlags()); - - DEBUG(dbgs() << "(delinearize: " << *this << "\n"); - - // When the stride of this SCEV is 1, do not compute the GCD: the size of this - // subscript is 1, and this same SCEV for the access function. - const SCEV *Remainder = Zero; - const SCEV *GCD = One; - - // Find the GCD and Remainder of the Start and Step coefficients of this SCEV. - if (Step != One && !Step->isAllOnesValue()) - GCD = SCEVGCD::findGCD(SE, Start, Step, &Remainder); - - DEBUG(dbgs() << "GCD: " << *GCD << "\n"); - DEBUG(dbgs() << "Remainder: " << *Remainder << "\n"); - - const SCEV *Quotient = Start; - if (GCD != One && !GCD->isAllOnesValue()) - // As findGCD computed Remainder, GCD divides "Start - Remainder." The - // Quotient is then this SCEV without Remainder, scaled down by the GCD. The - // Quotient is what will be used in the next subscript delinearization. - Quotient = SCEVDivision::divide(SE, SE.getMinusSCEV(Start, Remainder), GCD); - - DEBUG(dbgs() << "Quotient: " << *Quotient << "\n"); - - const SCEV *Rem = Quotient; - if (const SCEVAddRecExpr *AR = dyn_cast(Quotient)) - // Recursively call delinearize on the Quotient until there are no more - // multiples that can be recognized. - Rem = AR->delinearize(SE, Subscripts, Sizes); - - // Scale up the canonical induction variable IV by whatever remains from the - // Step after division by the GCD: the GCD is the size of all the sub-array. - if (Step != One && !Step->isAllOnesValue() && GCD != One && - !GCD->isAllOnesValue() && Step != GCD) { - Step = SCEVDivision::divide(SE, Step, GCD); - IV = SE.getMulExpr(IV, Step); - } - // The access function in the current subscript is computed as the canonical - // induction variable IV (potentially scaled up by the step) and offset by - // Rem, the offset of delinearization in the sub-array. - const SCEV *Index = SE.getAddExpr(IV, Rem); - - // Record the access function and the size of the current subscript. - Subscripts.push_back(Index); - Sizes.push_back(GCD); - -#ifndef NDEBUG - int Size = Sizes.size(); - DEBUG(dbgs() << "succeeded to delinearize " << *this << "\n"); - DEBUG(dbgs() << "ArrayDecl[UnknownSize]"); - for (int i = 0; i < Size - 1; i++) - DEBUG(dbgs() << "[" << *Sizes[i] << "]"); - DEBUG(dbgs() << " with elements of " << *Sizes[Size - 1] << " bytes.\n"); - - DEBUG(dbgs() << "ArrayRef"); - for (int i = 0; i < Size; i++) - DEBUG(dbgs() << "[" << *Subscripts[i] << "]"); - DEBUG(dbgs() << "\n)\n"); -#endif + // First step: collect parametric terms. + SmallVector Terms; + collectParametricTerms(SE, Terms); + + // Second step: find subscript sizes. + findArrayDimensions(SE, Terms, Sizes); + + // Third step: compute the access functions for each subscript. + const SCEV *Remainder = computeAccessFunctions(SE, Subscripts, Sizes); + + DEBUG({ + dbgs() << "succeeded to delinearize " << *this << "\n"; + dbgs() << "ArrayDecl[UnknownSize]"; + for (const SCEV *S : Sizes) + dbgs() << "[" << *S << "]"; + + dbgs() << "ArrayRef"; + for (const SCEV *S : Sizes) + dbgs() << "[" << *S << "]"; + dbgs() << "\n"; + }); return Remainder; } diff --git a/test/Analysis/Delinearization/a.ll b/test/Analysis/Delinearization/a.ll index 9308749b279..efebcc42ea2 100644 --- a/test/Analysis/Delinearization/a.ll +++ b/test/Analysis/Delinearization/a.ll @@ -12,17 +12,6 @@ ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(i32) bytes. ; CHECK: ArrayRef[{3,+,2}<%for.i>][{-4,+,3}<%for.j>][{7,+,5}<%for.k>] -; AddRec: {{(8 + ((4 + (12 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(12 * %o)}<%for.j> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize][%o] with elements of sizeof(i32) bytes. -; CHECK: ArrayRef[{(1 + (3 * %m)),+,(2 * %m)}<%for.i>][{2,+,(3 * %o)}<%for.j>] - -; AddRec: {(8 + ((-8 + (24 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize] with elements of 2 bytes. -; CHECK: ArrayRef[{((1 + ((-1 + (3 * %m)) * %o)) * sizeof(i32)),+,(%m * %o * sizeof(i32))}<%for.i>] - -; Function Attrs: nounwind uwtable define void @foo(i64 %n, i64 %m, i64 %o, i32* nocapture %A) #0 { entry: %cmp32 = icmp sgt i64 %n, 0 diff --git a/test/Analysis/Delinearization/himeno_1.ll b/test/Analysis/Delinearization/himeno_1.ll index 9458bd2e526..c94ca7aff75 100644 --- a/test/Analysis/Delinearization/himeno_1.ll +++ b/test/Analysis/Delinearization/himeno_1.ll @@ -31,16 +31,6 @@ ; CHECK: ArrayDecl[UnknownSize][(sext i32 %a.cols to i64)][(sext i32 %a.deps to i64)] with elements of sizeof(float) bytes. ; CHECK: ArrayRef[{1,+,1}<%for.i>][{1,+,1}<%for.j>][{1,+,1}<%for.k>] -; AddRec: {{(-4 + (4 * (sext i32 (-1 + %p.deps) to i64)) + (4 * (sext i32 %a.deps to i64) * (1 + (sext i32 %a.cols to i64))) + %a.base),+,(4 * (sext i32 %a.deps to i64) * (sext i32 %a.cols to i64))}<%for.i>,+,(4 * (sext i32 %a.deps to i64))}<%for.j> -; CHECK: Base offset: %a.base -; CHECK: ArrayDecl[UnknownSize][(sext i32 %a.deps to i64)] with elements of sizeof(float) bytes. -; CHECK: ArrayRef[{(1 + (sext i32 %a.cols to i64)),+,(sext i32 %a.cols to i64)}<%for.i>][{(-1 + (sext i32 (-1 + %p.deps) to i64)),+,(sext i32 %a.deps to i64)}<%for.j>] - -; AddRec: {(-4 + (4 * (sext i32 (-1 + %p.deps) to i64)) + ((sext i32 %a.deps to i64) * (-4 + (4 * (sext i32 (-1 + %p.cols) to i64)) + (4 * (sext i32 %a.cols to i64)))) + %a.base),+,(4 * (sext i32 %a.deps to i64) * (sext i32 %a.cols to i64))}<%for.i> -; CHECK: Base offset: %a.base -; CHECK: ArrayDecl[UnknownSize] with elements of sizeof(float) bytes. -; CHECK: ArrayRef[{(-1 + (sext i32 (-1 + %p.deps) to i64) + ((sext i32 %a.deps to i64) * (-1 + (sext i32 (-1 + %p.cols) to i64) + (sext i32 %a.cols to i64)))),+,((sext i32 %a.deps to i64) * (sext i32 %a.cols to i64))}<%for.i>] - %struct.Mat = type { float*, i32, i32, i32, i32 } define void @jacobi(i32 %nn, %struct.Mat* nocapture %a, %struct.Mat* nocapture %p) nounwind uwtable { diff --git a/test/Analysis/Delinearization/himeno_2.ll b/test/Analysis/Delinearization/himeno_2.ll index a29006606fa..c256384f201 100644 --- a/test/Analysis/Delinearization/himeno_2.ll +++ b/test/Analysis/Delinearization/himeno_2.ll @@ -31,16 +31,6 @@ ; CHECK: ArrayDecl[UnknownSize][(sext i32 %a.cols to i64)][(sext i32 %a.deps to i64)] with elements of sizeof(float) bytes. ; CHECK: ArrayRef[{1,+,1}<%for.i>][{1,+,1}<%for.j>][{1,+,1}<%for.k>] -; AddRec: {{(-4 + (4 * (sext i32 (-1 + %p.deps) to i64)) + (4 * (sext i32 %a.deps to i64) * (1 + (sext i32 %a.cols to i64))) + %a.base),+,(4 * (sext i32 %a.deps to i64) * (sext i32 %a.cols to i64))}<%for.i>,+,(4 * (sext i32 %a.deps to i64))}<%for.j> -; CHECK: Base offset: %a.base -; CHECK: ArrayDecl[UnknownSize][(sext i32 %a.deps to i64)] with elements of sizeof(float) bytes. -; CHECK: ArrayRef[{(1 + (sext i32 %a.cols to i64)),+,(sext i32 %a.cols to i64)}<%for.i>][{(-1 + (sext i32 (-1 + %p.deps) to i64)),+,(sext i32 %a.deps to i64)}<%for.j>] - -; AddRec: {(-4 + (4 * (sext i32 (-1 + %p.deps) to i64)) + ((sext i32 %a.deps to i64) * (-4 + (4 * (sext i32 (-1 + %p.cols) to i64)) + (4 * (sext i32 %a.cols to i64)))) + %a.base),+,(4 * (sext i32 %a.deps to i64) * (sext i32 %a.cols to i64))}<%for.i> -; CHECK: Base offset: %a.base -; CHECK: ArrayDecl[UnknownSize] with elements of sizeof(float) bytes. -; CHECK: ArrayRef[{(-1 + (sext i32 (-1 + %p.deps) to i64) + ((sext i32 %a.deps to i64) * (-1 + (sext i32 (-1 + %p.cols) to i64) + (sext i32 %a.cols to i64)))),+,((sext i32 %a.deps to i64) * (sext i32 %a.cols to i64))}<%for.i>] - %struct.Mat = type { float*, i32, i32, i32, i32 } define void @jacobi(i32 %nn, %struct.Mat* nocapture %a, %struct.Mat* nocapture %p) nounwind uwtable { diff --git a/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll b/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll index 82cab167c74..ae80ebc5227 100644 --- a/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll +++ b/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll @@ -13,16 +13,6 @@ ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double) bytes. ; CHECK: ArrayRef[{3,+,1}<%for.i>][{-4,+,1}<%for.j>][{7,+,1}<%for.k>] -; AddRec: {{(48 + ((-24 + (24 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize][%o] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{(-3 + (3 * %m)),+,%m}<%for.i>][{6,+,%o}<%for.j>] - -; AddRec: {(48 + ((-32 + (32 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{(6 + ((-4 + (4 * %m)) * %o)),+,(%m * %o)}<%for.i>] - define void @foo(i64 %n, i64 %m, i64 %o, double* %A) { entry: br label %for.i diff --git a/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll b/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll index a1e779fff6c..75080dad3af 100644 --- a/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll +++ b/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll @@ -13,16 +13,6 @@ ; CHECK: ArrayDecl[UnknownSize][%m][(%o + %p)] with elements of sizeof(double) bytes. ; CHECK: ArrayRef[{3,+,1}<%for.cond4.preheader.lr.ph.us>][{-4,+,1}<%for.body6.lr.ph.us.us>][{7,+,1}<%for.body6.us.us>] -; AddRec: {{(48 + (8 * %o) + (8 * (-4 + (3 * %m)) * (%o + %p)) + %A),+,(8 * (%o + %p) * %m)}<%for.cond4.preheader.lr.ph.us>,+,(8 * (%o + %p))}<%for.body6.lr.ph.us.us> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize][(%o + %p)] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{(-4 + (3 * %m)),+,%m}<%for.cond4.preheader.lr.ph.us>][{(6 + %o),+,(%o + %p)}<%for.body6.lr.ph.us.us>] - -; AddRec: {(48 + (8 * %o) + ((-40 + (32 * %m)) * (%o + %p)) + %A),+,(8 * (%o + %p) * %m)}<%for.cond4.preheader.lr.ph.us> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{(6 + ((-5 + (4 * %m)) * (%o + %p)) + %o),+,((%o + %p) * %m)}<%for.cond4.preheader.lr.ph.us>] - define void @foo(i64 %n, i64 %m, i64 %o, i64 %p, double* nocapture %A) nounwind uwtable { entry: %add = add nsw i64 %p, %o diff --git a/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll b/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll index a52a4c93ce2..e921444668d 100644 --- a/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll +++ b/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll @@ -13,16 +13,6 @@ ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double) bytes. ; CHECK: ArrayRef[{%p,+,1}<%for.i>][{%q,+,1}<%for.j>][{%r,+,1}<%for.k>] -; AddRec: {{(-8 + (8 * ((((%m * %p) + %q) * %o) + %r)) + (8 * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize][%o] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{(1 + (%m * %p) + %q),+,%m}<%for.i>][{(-1 + %r),+,%o}<%for.j>] - -; AddRec: {(-8 + (8 * ((((%m * %p) + %q) * %o) + %r)) + (8 * %m * %o) + %A),+,(8 * %m * %o)}<%for.i> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{(-1 + ((((1 + %p) * %m) + %q) * %o) + %r),+,(%m * %o)}<%for.i>] - define void @foo(i64 %n, i64 %m, i64 %o, double* %A, i64 %p, i64 %q, i64 %r) { entry: br label %for.i diff --git a/test/Analysis/Delinearization/multidim_only_ivs_2d.ll b/test/Analysis/Delinearization/multidim_only_ivs_2d.ll index d68a1588394..48bec08190d 100644 --- a/test/Analysis/Delinearization/multidim_only_ivs_2d.ll +++ b/test/Analysis/Delinearization/multidim_only_ivs_2d.ll @@ -13,11 +13,6 @@ ; CHECK: ArrayDecl[UnknownSize][%m] with elements of sizeof(double) bytes. ; CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>] -; AddRec: {(-8 + (8 * %m) + %A),+,(8 * %m)}<%for.i> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{(-1 + %m),+,%m}<%for.i>] - define void @foo(i64 %n, i64 %m, double* %A) { entry: br label %for.i diff --git a/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll b/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll index 7207420205a..810188f7d55 100644 --- a/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll +++ b/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll @@ -1,4 +1,6 @@ ; RUN: opt < %s -analyze -delinearize | FileCheck %s +; XFAIL: * +; We do not recognize anymore variable size arrays. ; extern void bar(long n, long m, double A[n][m]); ; diff --git a/test/Analysis/Delinearization/multidim_only_ivs_3d.ll b/test/Analysis/Delinearization/multidim_only_ivs_3d.ll index 24f95837c86..aad0f094084 100644 --- a/test/Analysis/Delinearization/multidim_only_ivs_3d.ll +++ b/test/Analysis/Delinearization/multidim_only_ivs_3d.ll @@ -13,16 +13,6 @@ ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double) bytes. ; CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>] -; AddRec: {{(-8 + (8 * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize][(%m * %o)] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{0,+,1}<%for.i>][{(-1 + %o),+,%o}<%for.j>] - -; AddRec: {(-8 + (8 * %m * %o) + %A),+,(8 * %m * %o)}<%for.i> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize] with elements of sizeof(double) bytes. -; CHECK: ArrayRef[{(-1 + (%m * %o)),+,(%m * %o)}<%for.i>] - define void @foo(i64 %n, i64 %m, i64 %o, double* %A) { entry: br label %for.i diff --git a/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll b/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll index e1516104ddf..9e406d125f4 100644 --- a/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll +++ b/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll @@ -12,16 +12,6 @@ ; CHECK: ArrayDecl[UnknownSize][(zext i32 %m to i64)][(zext i32 %o to i64)] with elements of 8 bytes. ; CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>] -; AddRec: {{((8 * (zext i32 (-1 + %o) to i64)) + %A),+,(8 * (zext i32 %m to i64) * (zext i32 %o to i64))}<%for.i>,+,(8 * (zext i32 %o to i64))}<%for.j> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize][((zext i32 %m to i64) * (zext i32 %o to i64))] with elements of 8 bytes. -; CHECK: ArrayRef[{0,+,1}<%for.i>][{(zext i32 (-1 + %o) to i64),+,(zext i32 %o to i64)}<%for.j>] - -; AddRec: {((8 * (zext i32 (-1 + %o) to i64)) + (8 * (zext i32 (-1 + %m) to i64) * (zext i32 %o to i64)) + %A),+,(8 * (zext i32 %m to i64) * (zext i32 %o to i64))}<%for.i> -; CHECK: Base offset: %A -; CHECK: ArrayDecl[UnknownSize] with elements of 8 bytes. -; CHECK: ArrayRef[{((zext i32 (-1 + %o) to i64) + ((zext i32 (-1 + %m) to i64) * (zext i32 %o to i64))),+,((zext i32 %m to i64) * (zext i32 %o to i64))}<%for.i>] - target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" diff --git a/test/Analysis/DependenceAnalysis/Banerjee.ll b/test/Analysis/DependenceAnalysis/Banerjee.ll index 5c17064f7e8..883a06d0bed 100644 --- a/test/Analysis/DependenceAnalysis/Banerjee.ll +++ b/test/Analysis/DependenceAnalysis/Banerjee.ll @@ -24,7 +24,7 @@ entry: ; DELIN: 'Dependence Analysis' for function 'banerjee0': ; DELIN: da analyze - none! -; DELIN: da analyze - consistent flow [0 1]! +; DELIN: da analyze - flow [<= <>]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! @@ -83,10 +83,10 @@ entry: ; CHECK: da analyze - output [* *]! ; DELIN: 'Dependence Analysis' for function 'banerjee1': -; DELIN: da analyze - none -; DELIN: da analyze - consistent flow [0 1]! +; DELIN: da analyze - output [* *]! +; DELIN: da analyze - flow [* <>]! ; DELIN: da analyze - confused! -; DELIN: da analyze - none +; DELIN: da analyze - input [* *]! ; DELIN: da analyze - confused! ; DELIN: da analyze - output [* *]! @@ -218,7 +218,7 @@ entry: ; DELIN: 'Dependence Analysis' for function 'banerjee3': ; DELIN: da analyze - none! -; DELIN: da analyze - consistent flow [-9 -9]! +; DELIN: da analyze - flow [> >]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! @@ -336,7 +336,7 @@ entry: ; DELIN: 'Dependence Analysis' for function 'banerjee5': ; DELIN: da analyze - none! -; DELIN: da analyze - consistent flow [9 9]! +; DELIN: da analyze - flow [< <]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! @@ -395,7 +395,7 @@ entry: ; DELIN: 'Dependence Analysis' for function 'banerjee6': ; DELIN: da analyze - none! -; DELIN: da analyze - consistent flow [0 -9]! +; DELIN: da analyze - flow [=> <>]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! @@ -454,7 +454,7 @@ entry: ; DELIN: 'Dependence Analysis' for function 'banerjee7': ; DELIN: da analyze - none! -; DELIN: da analyze - consistent flow [-1 0]! +; DELIN: da analyze - flow [> <=]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! @@ -513,7 +513,7 @@ entry: ; DELIN: 'Dependence Analysis' for function 'banerjee8': ; DELIN: da analyze - none! -; DELIN: da analyze - consistent flow [-1 -1]! +; DELIN: da analyze - flow [> <>]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! @@ -571,7 +571,7 @@ entry: ; CHECK: da analyze - none! ; DELIN: 'Dependence Analysis' for function 'banerjee9': -; DELIN: da analyze - none! +; DELIN: da analyze - output [* *]! ; DELIN: da analyze - flow [<= =|<]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! @@ -750,7 +750,7 @@ entry: ; DELIN: 'Dependence Analysis' for function 'banerjee12': ; DELIN: da analyze - none! -; DELIN: da analyze - consistent flow [0 -11]! +; DELIN: da analyze - flow [= <>]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! diff --git a/test/Analysis/DependenceAnalysis/GCD.ll b/test/Analysis/DependenceAnalysis/GCD.ll index 7efa8b50190..fd9173b924c 100644 --- a/test/Analysis/DependenceAnalysis/GCD.ll +++ b/test/Analysis/DependenceAnalysis/GCD.ll @@ -24,10 +24,10 @@ entry: ; CHECK: da analyze - none! ; DELIN: 'Dependence Analysis' for function 'gcd0' -; DELIN: da analyze - none! +; DELIN: da analyze - output [* *]! ; DELIN: da analyze - flow [=> *|<]! ; DELIN: da analyze - confused! -; DELIN: da analyze - none! +; DELIN: da analyze - input [* *]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! @@ -85,10 +85,10 @@ entry: ; CHECK: da analyze - none! ; DELIN: 'Dependence Analysis' for function 'gcd1' -; DELIN: da analyze - none! +; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! -; DELIN: da analyze - none! +; DELIN: da analyze - input [* *]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! @@ -147,10 +147,10 @@ entry: ; CHECK: da analyze - none! ; DELIN: 'Dependence Analysis' for function 'gcd2' -; DELIN: da analyze - none! +; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! -; DELIN: da analyze - none! +; DELIN: da analyze - input [* *]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! @@ -269,10 +269,10 @@ entry: ; CHECK: da analyze - none! ; DELIN: 'Dependence Analysis' for function 'gcd4' -; DELIN: da analyze - output [* *]! +; DELIN: da analyze - none! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! -; DELIN: da analyze - input [* *]! +; DELIN: da analyze - none! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! @@ -339,10 +339,10 @@ entry: ; CHECK: da analyze - none! ; DELIN: 'Dependence Analysis' for function 'gcd5' -; DELIN: da analyze - output [* *]! +; DELIN: da analyze - none! ; DELIN: da analyze - flow [<> *]! ; DELIN: da analyze - confused! -; DELIN: da analyze - input [* *]! +; DELIN: da analyze - none! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! @@ -411,7 +411,7 @@ entry: ; DELIN: 'Dependence Analysis' for function 'gcd6' ; DELIN: da analyze - none! -; DELIN: da analyze - none! +; DELIN: da analyze - flow [=> =>|<]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! -- 2.34.1