diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h b/llvm/include/llvm/Analysis/DependenceAnalysis.h --- a/llvm/include/llvm/Analysis/DependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h @@ -924,10 +924,26 @@ void updateDirection(Dependence::DVEntry &Level, const Constraint &CurConstraint) const; + /// Given a linear access function, tries to recover subscripts + /// for each dimension of the array element access. bool tryDelinearize(Instruction *Src, Instruction *Dst, SmallVectorImpl &Pair); - private: + /// Tries to delinearize access function for a fixed size multi-dimensional + /// array. Returns true upon success and false otherwise. + bool tryDelinearizeFixedSize(Instruction *Src, Instruction *Dst, + const SCEV *SrcAccessFn, const SCEV *DstAccessFn, + SmallVectorImpl &SrcSubscripts, + SmallVectorImpl &DstSubscripts); + + /// Tries to delinearize access function for a multi-dimensional array with + /// symbolic runtime sizes. + /// Returns true upon success and false otherwise. + bool tryDelinearizeParametricSize(Instruction *Src, Instruction *Dst, + const SCEV *SrcAccessFn, const SCEV *DstAccessFn, + SmallVectorImpl &SrcSubscripts, + SmallVectorImpl &DstSubscripts); + /// checkSubscript - Helper function for checkSrcSubscript and /// checkDstSubscript to avoid duplicate code bool checkSubscript(const SCEV *Expr, const Loop *LoopNest, diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -998,6 +998,18 @@ SmallVectorImpl &Subscripts, SmallVectorImpl &Sizes); + /// Gathers the individual index expressions from a GEP instruction. + /// + /// This function optimistically assumes the GEP references into a fixed size + /// array. If this is actually true, this function returns a list of array + /// subscript expressions as SCEV as well as a list of integers describing + /// the size of the individual array dimensions. Both lists have either equal + /// length or the size list is one element shorter in case there is no known + /// size available for the outermost array dimension. + void getIndexExpressionsFromGEP(const GetElementPtrInst *GEP, + SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes); + /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the /// subscripts and sizes of an array access. /// diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -110,14 +110,11 @@ static cl::opt Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore, cl::desc("Try to delinearize array references.")); -static cl::opt DisableDelinearizationChecks( - "da-disable-delinearization-checks", cl::init(false), cl::Hidden, - cl::ZeroOrMore, - cl::desc( - "Disable checks that try to statically verify validity of " - "delinearized subscripts. Enabling this option may result in incorrect " - "dependence vectors for languages that allow the subscript of one " - "dimension to underflow or overflow into another dimension.")); +static cl::opt AssumeInRangeSubscripts( + "da-assume-inrange-subscripts", cl::init(false), cl::Hidden, cl::ZeroOrMore, + cl::desc("Assume that all subscripts in a multi-dimensional array access " + "are inrange, meaning that they do not underflow or overflow into " + "another dimension.")); //===----------------------------------------------------------------------===// // basics @@ -3264,24 +3261,128 @@ assert(isLoadOrStore(Dst) && "instruction is not load or store"); Value *SrcPtr = getLoadStorePointerOperand(Src); Value *DstPtr = getLoadStorePointerOperand(Dst); - Loop *SrcLoop = LI->getLoopFor(Src->getParent()); Loop *DstLoop = LI->getLoopFor(Dst->getParent()); + const SCEV *SrcAccessFn = SE->getSCEVAtScope(SrcPtr, SrcLoop); + const SCEV *DstAccessFn = SE->getSCEVAtScope(DstPtr, DstLoop); + const SCEVUnknown *SrcBase = + dyn_cast(SE->getPointerBase(SrcAccessFn)); + const SCEVUnknown *DstBase = + dyn_cast(SE->getPointerBase(DstAccessFn)); - // Below code mimics the code in Delinearization.cpp - const SCEV *SrcAccessFn = - SE->getSCEVAtScope(SrcPtr, SrcLoop); - const SCEV *DstAccessFn = - SE->getSCEVAtScope(DstPtr, DstLoop); + if (!SrcBase || !DstBase || SrcBase != DstBase) + return false; + + SmallVector SrcSubscripts, DstSubscripts; + + if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn, + SrcSubscripts, DstSubscripts) && + !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn, + SrcSubscripts, DstSubscripts)) + return false; + + int size = SrcSubscripts.size(); + LLVM_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 + // resize Pair to contain as many pairs of subscripts as the delinearization + // has found, and then initialize the pairs following the delinearization. + Pair.resize(size); + for (int i = 0; i < size; ++i) { + Pair[i].Src = SrcSubscripts[i]; + Pair[i].Dst = DstSubscripts[i]; + unifySubscriptType(&Pair[i]); + } + + return true; +} + +bool DependenceInfo::tryDelinearizeFixedSize( + Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, + const SCEV *DstAccessFn, SmallVectorImpl &SrcSubscripts, + SmallVectorImpl &DstSubscripts) { + + if (!AssumeInRangeSubscripts) + return false; + + Value *SrcPtr = getLoadStorePointerOperand(Src); + Value *DstPtr = getLoadStorePointerOperand(Dst); const SCEVUnknown *SrcBase = dyn_cast(SE->getPointerBase(SrcAccessFn)); const SCEVUnknown *DstBase = dyn_cast(SE->getPointerBase(DstAccessFn)); + assert(SrcBase && DstBase && SrcBase == DstBase && + "expected src and dst scev unknowns to be equal"); - if (!SrcBase || !DstBase || SrcBase != DstBase) + // Check the simple case where the array dimensions are fixed size. + auto *SrcGEP = dyn_cast(SrcPtr); + auto *DstGEP = dyn_cast(DstPtr); + if (!SrcGEP || !DstGEP) return false; + SmallVector SrcSizes, DstSizes; + SE->getIndexExpressionsFromGEP(SrcGEP, SrcSubscripts, SrcSizes); + SE->getIndexExpressionsFromGEP(DstGEP, DstSubscripts, DstSizes); + + // Check that the two size arrays are non-empty and equal in length and + // value. + if (SrcSizes.empty() || SrcSubscripts.size() <= 1 || SrcSizes.size() != DstSizes.size() || + !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) { + SrcSubscripts.clear(); + DstSubscripts.clear(); + return false; + } + + auto *SrcBasePtr = SrcGEP->getOperand(0); + auto *DstBasePtr = DstGEP->getOperand(0); + while (auto *PCast = dyn_cast(SrcBasePtr)) + SrcBasePtr = PCast->getOperand(0); + while (auto *PCast = dyn_cast(DstBasePtr)) + DstBasePtr = PCast->getOperand(0); + + // Check that for identical base pointers we do not miss index offsets + // that have been added before this GEP is applied. + if (SrcBasePtr == SrcBase->getValue() && + DstBasePtr == DstBase->getValue()) { + assert(SrcSubscripts.size() == DstSubscripts.size() && + SrcSubscripts.size() == SrcSizes.size() + 1 && + "Expected equal number of entries in the list of sizes and " + "subscripts."); + LLVM_DEBUG({ + dbgs() << "Delinearized subscripts of fixed-size array\n" + << "SrcGEP:" << *SrcGEP << "\n" + << "DstGEP:" << *DstGEP << "\n"; + }); + return true; + } + + SrcSubscripts.clear(); + DstSubscripts.clear(); + return false; +} + +bool DependenceInfo::tryDelinearizeParametricSize( + Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, + const SCEV *DstAccessFn, SmallVectorImpl &SrcSubscripts, + SmallVectorImpl &DstSubscripts) { + + Value *SrcPtr = getLoadStorePointerOperand(Src); + Value *DstPtr = getLoadStorePointerOperand(Dst); + const SCEVUnknown *SrcBase = + dyn_cast(SE->getPointerBase(SrcAccessFn)); + const SCEVUnknown *DstBase = + dyn_cast(SE->getPointerBase(DstAccessFn)); + assert(SrcBase && DstBase && SrcBase == DstBase && + "expected src and dst scev unknowns to be equal"); + const SCEV *ElementSize = SE->getElementSize(Src); if (ElementSize != SE->getElementSize(Dst)) return false; @@ -3304,7 +3405,6 @@ SE->findArrayDimensions(Terms, Sizes, ElementSize); // Third step: compute the access functions for each subscript. - SmallVector SrcSubscripts, DstSubscripts; SE->computeAccessFunctions(SrcAR, SrcSubscripts, Sizes); SE->computeAccessFunctions(DstAR, DstSubscripts, Sizes); @@ -3313,16 +3413,14 @@ SrcSubscripts.size() != DstSubscripts.size()) return false; - int size = SrcSubscripts.size(); - // Statically check that the array bounds are in-range. The first subscript we // don't have a size for and it cannot overflow into another subscript, so is // always safe. The others need to be 0 <= subscript[i] < bound, for both src // and dst. // FIXME: It may be better to record these sizes and add them as constraints // to the dependency checks. - if (!DisableDelinearizationChecks) - for (int i = 1; i < size; ++i) { + if (!AssumeInRangeSubscripts) + for (size_t i = 1; i < SrcSubscripts.size(); ++i) { if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr)) return false; @@ -3336,26 +3434,6 @@ return false; } - LLVM_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 - // resize Pair to contain as many pairs of subscripts as the delinearization - // has found, and then initialize the pairs following the delinearization. - Pair.resize(size); - for (int i = 0; i < size; ++i) { - Pair[i].Src = SrcSubscripts[i]; - Pair[i].Dst = DstSubscripts[i]; - unifySubscriptType(&Pair[i]); - } - return true; } diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -11389,6 +11389,49 @@ }); } +void ScalarEvolution::getIndexExpressionsFromGEP( + const GetElementPtrInst *GEP, SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes) { + assert(GEP && "getIndexExpressionsFromGEP called with a null GEP"); + Type *Ty = GEP->getPointerOperandType(); + bool DroppedFirstDim = false; + for (unsigned i = 1; i < GEP->getNumOperands(); i++) { + const SCEV *Expr = getSCEV(GEP->getOperand(i)); + if (i == 1) { + if (auto *PtrTy = dyn_cast(Ty)) { + Ty = PtrTy->getElementType(); + } else if (auto *ArrayTy = dyn_cast(Ty)) { + Ty = ArrayTy->getElementType(); + } else { + Subscripts.clear(); + Sizes.clear(); + break; + } + if (auto *Const = dyn_cast(Expr)) + if (Const->getValue()->isZero()) { + DroppedFirstDim = true; + continue; + } + Subscripts.push_back(Expr); + continue; + } + + auto *ArrayTy = dyn_cast(Ty); + if (!ArrayTy) { + Subscripts.clear(); + Sizes.clear(); + break; + } + + Subscripts.push_back(Expr); + if (!(DroppedFirstDim && i == 2)) + Sizes.push_back(ArrayTy->getNumElements()); + + Ty = ArrayTy->getElementType(); + } + return; +} + //===----------------------------------------------------------------------===// // SCEVCallbackVH Class Implementation //===----------------------------------------------------------------------===// diff --git a/llvm/test/Analysis/DependenceAnalysis/Coupled.ll b/llvm/test/Analysis/DependenceAnalysis/Coupled.ll --- a/llvm/test/Analysis/DependenceAnalysis/Coupled.ll +++ b/llvm/test/Analysis/DependenceAnalysis/Coupled.ll @@ -1,6 +1,6 @@ ; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ -; RUN: | FileCheck %s -; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: -da-assume-inrange-subscripts | FileCheck %s +; RUN: opt < %s -analyze -basicaa -da -da-assume-inrange-subscripts | FileCheck %s 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-apple-macosx10.6.0" @@ -90,7 +90,7 @@ ; CHECK-LABEL: couple2 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [<]! +; CHECK: da analyze - flow [*|<]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -250,7 +250,7 @@ ; CHECK-LABEL: couple6 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [<]! +; CHECK: da analyze - flow [=|<]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -400,7 +400,7 @@ ; CHECK-LABEL: couple10 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [>]! +; CHECK: da analyze - flow [>] splitable! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -438,7 +438,8 @@ ; CHECK-LABEL: couple11 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [>]! +; CHECK: da analyze - flow [=|<] splitable! +; CHECK: da analyze - split level = 1, iteration = 9! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -476,7 +477,7 @@ ; CHECK-LABEL: couple12 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [>]! +; CHECK: da analyze - flow [<] splitable! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -551,7 +552,8 @@ ; CHECK-LABEL: couple14 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [<]! +; CHECK: da analyze - flow [=|<] splitable! +; CHECK: da analyze - split level = 1, iteration = 9! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! diff --git a/llvm/test/Analysis/DependenceAnalysis/FixedSizeArray.ll b/llvm/test/Analysis/DependenceAnalysis/FixedSizeArray.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/DependenceAnalysis/FixedSizeArray.ll @@ -0,0 +1,40 @@ +; RUN: opt < %s -da -analyze -da-assume-inrange-subscripts | FileCheck %s +; CHECK: da analyze - consistent anti [1 -2]! + +;; #define N 1024l +;; #define M 2048l +;; void foo(int a[N][M]) { +;; for (long i = 0; i < N-1; ++i) +;; for (long j = 2; j < M; ++j) { +;; a[i][j] = a[i+1][j-2]; +;; } +;;} + +define void @test([2048 x i32]* nocapture %a) { +entry: + br label %for.cond1.preheader + +for.cond.loopexit: ; preds = %for.body4 + %exitcond4 = icmp eq i64 %add, 1023 + br i1 %exitcond4, label %for.end10, label %for.cond1.preheader + +for.cond1.preheader: ; preds = %for.cond.loopexit, %entry + %i.02 = phi i64 [ 0, %entry ], [ %add, %for.cond.loopexit ] + %add = add nuw nsw i64 %i.02, 1 + br label %for.body4 + +for.body4: ; preds = %for.body4, %for.cond1.preheader + %j.01 = phi i64 [ 2, %for.cond1.preheader ], [ %inc, %for.body4 ] + %sub = add nsw i64 %j.01, -2 + %arrayidx5 = getelementptr inbounds [2048 x i32], [2048 x i32]* %a, i64 %add, i64 %sub + %0 = load i32, i32* %arrayidx5, align 4 + %arrayidx7 = getelementptr inbounds [2048 x i32], [2048 x i32]* %a, i64 %i.02, i64 %j.01 + store i32 %0, i32* %arrayidx7, align 4 + %inc = add nuw nsw i64 %j.01, 1 + %exitcond = icmp eq i64 %inc, 2048 + br i1 %exitcond, label %for.cond.loopexit, label %for.body4 + +for.end10: ; preds = %for.cond.loopexit + ret void +} + diff --git a/llvm/test/Analysis/DependenceAnalysis/Invariant.ll b/llvm/test/Analysis/DependenceAnalysis/Invariant.ll --- a/llvm/test/Analysis/DependenceAnalysis/Invariant.ll +++ b/llvm/test/Analysis/DependenceAnalysis/Invariant.ll @@ -1,13 +1,13 @@ ; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ -; RUN: | FileCheck %s -; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: -da-assume-inrange-subscripts | FileCheck %s +; RUN: opt < %s -analyze -basicaa -da -da-assume-inrange-subscripts | FileCheck %s ; Test for a bug, which caused an assert when an invalid ; SCEVAddRecExpr is created in addToCoefficient. ; CHECK-LABEL: foo ; CHECK: da analyze - consistent input [S 0]! -; CHECK: da analyze - input [* *|<]! +; CHECK: da analyze - input [* 0|<]! ; CHECK: da analyze - none! define float @foo(float %g, [40 x float]* %rr) nounwind { diff --git a/llvm/test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll b/llvm/test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll --- a/llvm/test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll +++ b/llvm/test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll @@ -1,6 +1,7 @@ ; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ -; RUN: | FileCheck %s -check-prefix=DELIN -; RUN: opt < %s -analyze -basicaa -da | FileCheck %s -check-prefix=DELIN +; RUN: -da-assume-inrange-subscripts | FileCheck %s -check-prefix=DELIN +; RUN: opt < %s -analyze -basicaa -da -da-assume-inrange-subscripts | \ +; RUN: FileCheck %s -check-prefix=DELIN 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-apple-macosx10.6.0" @@ -56,8 +57,8 @@ entry: br label %for.cond -; DELIN: da analyze - input [* *]! -; DELIN: da analyze - anti [* *|<]! +; DELIN: da analyze - input [0 *]! +; DELIN: da analyze - anti [1 *]! ; DELIN: da analyze - none! for.cond: ; preds = %for.inc11, %entry %indvars.iv11 = phi i64 [ %indvars.iv.next12, %for.inc11 ], [ 1, %entry ] diff --git a/llvm/test/Analysis/DependenceAnalysis/Preliminary.ll b/llvm/test/Analysis/DependenceAnalysis/Preliminary.ll --- a/llvm/test/Analysis/DependenceAnalysis/Preliminary.ll +++ b/llvm/test/Analysis/DependenceAnalysis/Preliminary.ll @@ -1,6 +1,6 @@ ; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ -; RUN: | FileCheck %s -; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: -da-assume-inrange-subscripts | FileCheck %s +; RUN: opt < %s -analyze -basicaa -da -da-assume-inrange-subscripts | FileCheck %s 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-apple-macosx10.6.0" @@ -58,10 +58,10 @@ br i1 %cmp10, label %for.cond1.preheader.preheader, label %for.end26 ; CHECK-LABEL: p2 -; CHECK: da analyze - output [* * *]! -; CHECK: da analyze - flow [* *|<]! +; CHECK: da analyze - none! +; CHECK: da analyze - flow [-3 -2]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* * *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - output [* * *]! diff --git a/llvm/test/Analysis/DependenceAnalysis/Propagating.ll b/llvm/test/Analysis/DependenceAnalysis/Propagating.ll --- a/llvm/test/Analysis/DependenceAnalysis/Propagating.ll +++ b/llvm/test/Analysis/DependenceAnalysis/Propagating.ll @@ -1,6 +1,6 @@ ; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ -; RUN: | FileCheck %s -; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: -da-assume-inrange-subscripts | FileCheck %s +; RUN: opt < %s -analyze -basicaa -da -da-assume-inrange-subscripts | FileCheck %s 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-apple-macosx10.6.0" @@ -17,7 +17,7 @@ ; CHECK-LABEL: prop0 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [< >]! +; CHECK: da analyze - consistent flow [1 -1]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -67,10 +67,10 @@ br label %for.cond1.preheader ; CHECK-LABEL: prop1 -; CHECK: da analyze - output [* * *]! -; CHECK: da analyze - flow [<> <> *]! +; CHECK: da analyze - none! +; CHECK: da analyze - consistent flow [1 1 -1]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* * *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -131,7 +131,7 @@ ; CHECK-LABEL: prop2 ; CHECK: da analyze - consistent output [0 S]! -; CHECK: da analyze - flow [> *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -181,10 +181,10 @@ br label %for.cond1.preheader ; CHECK-LABEL: prop3 -; CHECK: da analyze - output [* *]! -; CHECK: da analyze - flow [<> *]! +; CHECK: da analyze - none! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -234,7 +234,7 @@ ; CHECK-LABEL: prop4 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [< <>]! +; CHECK: da analyze - consistent flow [2 -3]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -287,7 +287,7 @@ ; CHECK-LABEL: prop5 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [* *|<]! +; CHECK: da analyze - flow [< -16] splitable! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -341,7 +341,7 @@ ; CHECK-LABEL: prop6 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [=> <>]! +; CHECK: da analyze - flow [=> -2]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -395,7 +395,8 @@ ; CHECK-LABEL: prop7 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [* <>]! +; CHECK: da analyze - flow [* -38] splitable! +; CHECK: da analyze - split level = 1, iteration = 4! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -451,7 +452,7 @@ ; CHECK-LABEL: prop8 ; CHECK: da analyze - consistent output [S 0]! -; CHECK: da analyze - flow [=> <]! +; CHECK: da analyze - flow [p=> 2]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! @@ -503,7 +504,7 @@ ; CHECK-LABEL: prop9 ; CHECK: da analyze - none! -; CHECK: da analyze - flow [<= <]! +; CHECK: da analyze - flow [p<= 2]! ; CHECK: da analyze - confused! ; CHECK: da analyze - consistent input [S 0]! ; CHECK: da analyze - confused! diff --git a/llvm/test/Analysis/DependenceAnalysis/Separability.ll b/llvm/test/Analysis/DependenceAnalysis/Separability.ll --- a/llvm/test/Analysis/DependenceAnalysis/Separability.ll +++ b/llvm/test/Analysis/DependenceAnalysis/Separability.ll @@ -1,6 +1,6 @@ ; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ -; RUN: | FileCheck %s -; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: -da-assume-inrange-subscripts | FileCheck %s +; RUN: opt < %s -analyze -basicaa -da -da-assume-inrange-subscripts | FileCheck %s 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-apple-macosx10.6.0" @@ -17,10 +17,10 @@ entry: br label %for.cond1.preheader -; CHECK: da analyze - output [= * * S]! -; CHECK: da analyze - flow [* * * *|<]! +; CHECK: da analyze - output [0 * * S]! +; CHECK: da analyze - flow [-10 * * *]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* * S *]! +; CHECK: da analyze - input [0 * S *]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -92,10 +92,10 @@ entry: br label %for.cond1.preheader -; CHECK: da analyze - output [= * * S]! -; CHECK: da analyze - flow [* * * *|<]! +; CHECK: da analyze - output [0 * * S]! +; CHECK: da analyze - flow [> * * *]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* * S *]! +; CHECK: da analyze - input [0 * S *]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -166,10 +166,10 @@ entry: br label %for.cond1.preheader -; CHECK: da analyze - output [= S = =]! -; CHECK: da analyze - flow [* * * <>]! +; CHECK: da analyze - consistent output [0 S 0 0]! +; CHECK: da analyze - flow [> * * -10]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [= * * *]! +; CHECK: da analyze - input [0 * * 0]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -240,10 +240,10 @@ entry: br label %for.cond1.preheader -; CHECK: da analyze - output [= S = =]! -; CHECK: da analyze - flow [* * * *|<]! +; CHECK: da analyze - consistent output [0 S 0 0]! +; CHECK: da analyze - flow [> * * *]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [= * * *]! +; CHECK: da analyze - input [0 * * 0]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! diff --git a/llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheck.ll b/llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheck.ll --- a/llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheck.ll +++ b/llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheck.ll @@ -1,6 +1,6 @@ ; RUN: opt < %s -disable-output -passes="print" \ -; RUN: -da-disable-delinearization-checks 2>&1 | FileCheck %s -; RUN: opt < %s -da -analyze -da-disable-delinearization-checks | FileCheck %s +; RUN: -da-assume-inrange-subscripts 2>&1 | FileCheck %s +; RUN: opt < %s -da -analyze -da-assume-inrange-subscripts | FileCheck %s ; CHECK-LABEL: t1 ; CHECK: da analyze - none! diff --git a/llvm/test/Transforms/LoopInterchange/currentLimitation.ll b/llvm/test/Transforms/LoopInterchange/currentLimitation.ll --- a/llvm/test/Transforms/LoopInterchange/currentLimitation.ll +++ b/llvm/test/Transforms/LoopInterchange/currentLimitation.ll @@ -1,5 +1,6 @@ ; RUN: opt < %s -basicaa -loop-interchange -pass-remarks-missed='loop-interchange' \ -; RUN: -pass-remarks-output=%t -verify-loop-info -verify-dom-info -S | FileCheck -check-prefix=IR %s +; RUN: -da-assume-inrange-subscripts -pass-remarks-output=%t -verify-loop-info \ +; RUN: -verify-dom-info -S | FileCheck -check-prefix=IR %s ; RUN: FileCheck --input-file=%t %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" @@ -16,11 +17,10 @@ ;; for(int j=1;j, std::vector> -getIndexExpressionsFromGEP(llvm::GetElementPtrInst *GEP, - llvm::ScalarEvolution &SE); - // If the loop is nonaffine/boxed, return the first non-boxed surrounding loop // for Polly. If the loop is affine, return the loop itself. // diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp --- a/polly/lib/Analysis/ScopBuilder.cpp +++ b/polly/lib/Analysis/ScopBuilder.cpp @@ -1627,9 +1627,9 @@ if (!GEP) return false; - std::vector Subscripts; - std::vector Sizes; - std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE); + SmallVector Subscripts; + SmallVector Sizes; + SE.getIndexExpressionsFromGEP(GEP, Subscripts, Sizes); auto *BasePtr = GEP->getOperand(0); if (auto *BasePtrCast = dyn_cast(BasePtr)) diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp --- a/polly/lib/Support/ScopHelper.cpp +++ b/polly/lib/Support/ScopHelper.cpp @@ -658,55 +658,6 @@ return UI->getParent(); } -std::tuple, std::vector> -polly::getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) { - std::vector Subscripts; - std::vector Sizes; - - Type *Ty = GEP->getPointerOperandType(); - - bool DroppedFirstDim = false; - - for (unsigned i = 1; i < GEP->getNumOperands(); i++) { - - const SCEV *Expr = SE.getSCEV(GEP->getOperand(i)); - - if (i == 1) { - if (auto *PtrTy = dyn_cast(Ty)) { - Ty = PtrTy->getElementType(); - } else if (auto *ArrayTy = dyn_cast(Ty)) { - Ty = ArrayTy->getElementType(); - } else { - Subscripts.clear(); - Sizes.clear(); - break; - } - if (auto *Const = dyn_cast(Expr)) - if (Const->getValue()->isZero()) { - DroppedFirstDim = true; - continue; - } - Subscripts.push_back(Expr); - continue; - } - - auto *ArrayTy = dyn_cast(Ty); - if (!ArrayTy) { - Subscripts.clear(); - Sizes.clear(); - break; - } - - Subscripts.push_back(Expr); - if (!(DroppedFirstDim && i == 2)) - Sizes.push_back(ArrayTy->getNumElements()); - - Ty = ArrayTy->getElementType(); - } - - return std::make_tuple(Subscripts, Sizes); -} - llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI, const BoxedLoopsSetTy &BoxedLoops) { while (BoxedLoops.count(L))