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/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -3264,23 +3264,171 @@ 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)); + + 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; +} + +static void +getIndexExpressionsFromGEP(const GetElementPtrInst *GEP, + SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes, ScalarEvolution &SE) { + 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 = 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; +} + +bool DependenceInfo::tryDelinearizeFixedSize( + Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, + const SCEV *DstAccessFn, SmallVectorImpl &SrcSubscripts, + SmallVectorImpl &DstSubscripts) { - // Below code mimics the code in Delinearization.cpp - const SCEV *SrcAccessFn = - SE->getSCEVAtScope(SrcPtr, SrcLoop); - const SCEV *DstAccessFn = - SE->getSCEVAtScope(DstPtr, DstLoop); + if (!DisableDelinearizationChecks) + 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; + getIndexExpressionsFromGEP(SrcGEP, SrcSubscripts, SrcSizes, *SE); + getIndexExpressionsFromGEP(DstGEP, DstSubscripts, DstSizes, *SE); + + // 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)) @@ -3304,7 +3452,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,8 +3460,6 @@ 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 @@ -3322,7 +3467,7 @@ // 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) { + for (size_t i = 1; i < SrcSubscripts.size(); ++i) { if (!isKnownNonNegative(SrcSubscripts[i], SrcPtr)) return false; @@ -3336,26 +3481,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/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 @@ -2,6 +2,9 @@ ; RUN: | FileCheck %s ; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ +; RUN: -da-disable-delinearization-checks | FileCheck %s --check-prefix=IN-RANGE + ; Test for a bug, which caused an assert when an invalid ; SCEVAddRecExpr is created in addToCoefficient. @@ -10,6 +13,11 @@ ; CHECK: da analyze - input [* *|<]! ; CHECK: da analyze - none! +; IN-RANGE-LABEL: foo +; IN-RANGE: da analyze - consistent input [S 0]! +; IN-RANGE: da analyze - input [* 0|<]! +; IN-RANGE: da analyze - none! + define float @foo(float %g, [40 x float]* %rr) nounwind { entry: br label %for.cond1.preheader 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 @@ -2,6 +2,9 @@ ; RUN: | FileCheck %s -check-prefix=DELIN ; RUN: opt < %s -analyze -basicaa -da | FileCheck %s -check-prefix=DELIN +; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ +; RUN: -da-disable-delinearization-checks | FileCheck %s -check-prefix=IN-RANGE + 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,6 +59,10 @@ entry: br label %for.cond +; IN-RANGE: da analyze - input [0 *]! +; IN-RANGE: da analyze - anti [1 *]! +; IN-RANGE: da analyze - none! + ; DELIN: da analyze - input [* *]! ; DELIN: da analyze - anti [* *|<]! ; DELIN: da analyze - none! 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 @@ -2,6 +2,9 @@ ; RUN: | FileCheck %s ; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ +; RUN: -da-disable-delinearization-checks | FileCheck %s --check-prefix=IN-RANGE + 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" @@ -57,6 +60,14 @@ %cmp10 = icmp sgt i64 %n, 0 br i1 %cmp10, label %for.cond1.preheader.preheader, label %for.end26 +; IN-RANGE-LABEL: p2 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - flow [-3 -2]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - output [* * *]! + ; CHECK-LABEL: p2 ; CHECK: da analyze - output [* * *]! ; CHECK: da analyze - flow [* *|<]! @@ -64,7 +75,6 @@ ; CHECK: da analyze - input [* * *]! ; CHECK: da analyze - confused! ; CHECK: da analyze - output [* * *]! - for.cond1.preheader.preheader: ; preds = %entry br label %for.cond1.preheader 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 @@ -2,6 +2,9 @@ ; RUN: | FileCheck %s ; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ +; RUN: -da-disable-delinearization-checks | FileCheck %s --check-prefix=IN-RANGE + 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" @@ -23,6 +26,14 @@ ; CHECK: da analyze - confused! ; CHECK: da analyze - none! +; IN-RANGE-LABEL: prop0 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - consistent flow [1 -1]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + for.cond1.preheader: ; preds = %entry, %for.inc9 %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ] %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ] @@ -66,6 +77,14 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop1 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - consistent flow [1 1 -1]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop1 ; CHECK: da analyze - output [* * *]! ; CHECK: da analyze - flow [<> <> *]! @@ -129,6 +148,14 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop2 +; IN-RANGE: da analyze - consistent output [0 S]! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop2 ; CHECK: da analyze - consistent output [0 S]! ; CHECK: da analyze - flow [> *]! @@ -180,6 +207,14 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop3 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop3 ; CHECK: da analyze - output [* *]! ; CHECK: da analyze - flow [<> *]! @@ -232,6 +267,14 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop4 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - consistent flow [2 -3]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop4 ; CHECK: da analyze - none! ; CHECK: da analyze - flow [< <>]! @@ -285,6 +328,14 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop5 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - flow [< -16] splitable! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop5 ; CHECK: da analyze - none! ; CHECK: da analyze - flow [* *|<]! @@ -339,6 +390,14 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop6 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - flow [=> -2]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop6 ; CHECK: da analyze - none! ; CHECK: da analyze - flow [=> <>]! @@ -393,6 +452,15 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop7 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - flow [* -38] splitable! +; IN-RANGE: da analyze - split level = 1, iteration = 4! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop7 ; CHECK: da analyze - none! ; CHECK: da analyze - flow [* <>]! @@ -449,6 +517,14 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop8 +; IN-RANGE: da analyze - consistent output [S 0]! +; IN-RANGE: da analyze - flow [p=> 2]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop8 ; CHECK: da analyze - consistent output [S 0]! ; CHECK: da analyze - flow [=> <]! @@ -501,6 +577,14 @@ entry: br label %for.cond1.preheader +; IN-RANGE-LABEL: prop9 +; IN-RANGE: da analyze - none! +; IN-RANGE: da analyze - flow [p<= 2]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - consistent input [S 0]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK-LABEL: prop9 ; CHECK: da analyze - none! ; CHECK: da analyze - flow [<= <]! 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 @@ -2,6 +2,9 @@ ; RUN: | FileCheck %s ; RUN: opt < %s -analyze -basicaa -da | FileCheck %s +; RUN: opt < %s -disable-output "-passes=print" -aa-pipeline=basic-aa 2>&1 \ +; RUN: -da-disable-delinearization-checks | FileCheck %s --check-prefix=IN-RANGE + 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,6 +20,13 @@ entry: br label %for.cond1.preheader +; IN-RANGE: da analyze - output [0 * * S]! +; IN-RANGE: da analyze - flow [-10 * * *]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - input [0 * S *]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK: da analyze - output [= * * S]! ; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - confused! @@ -92,6 +102,13 @@ entry: br label %for.cond1.preheader +; IN-RANGE: da analyze - output [0 * * S]! +; IN-RANGE: da analyze - flow [> * * *]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - input [0 * S *]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK: da analyze - output [= * * S]! ; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - confused! @@ -166,6 +183,13 @@ entry: br label %for.cond1.preheader +; IN-RANGE: da analyze - consistent output [0 S 0 0]! +; IN-RANGE: da analyze - flow [> * * -10]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - input [0 * * 0]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK: da analyze - output [= S = =]! ; CHECK: da analyze - flow [* * * <>]! ; CHECK: da analyze - confused! @@ -240,6 +264,13 @@ entry: br label %for.cond1.preheader +; IN-RANGE: da analyze - consistent output [0 S 0 0]! +; IN-RANGE: da analyze - flow [> * * *]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - input [0 * * 0]! +; IN-RANGE: da analyze - confused! +; IN-RANGE: da analyze - none! + ; CHECK: da analyze - output [= S = =]! ; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - confused! diff --git a/llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheckFixedSize.ll b/llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheckFixedSize.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheckFixedSize.ll @@ -0,0 +1,120 @@ +; 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 + +; CHECK-LABEL: t1 +; CHECK: da analyze - none! +; CHECK: da analyze - consistent anti [1 -2]! +; CHECK: da analyze - none! + +;; #define N 1024 +;; #define M 2048 +;; void t1(int a[N][M]) { +;; for (int i = 0; i < N-1; ++i) +;; for (int j = 2; j < M; ++j) +;; a[i][j] = a[i+1][j-2]; +;; } + +define void @t1([2048 x i32]* %a) { +entry: + br label %for.body + +for.body: ; preds = %entry, %for.inc11 + %indvars.iv4 = phi i64 [ 0, %entry ], [ %indvars.iv.next5, %for.inc11 ] + br label %for.body4 + +for.body4: ; preds = %for.body, %for.body4 + %indvars.iv = phi i64 [ 2, %for.body ], [ %indvars.iv.next, %for.body4 ] + %0 = add nuw nsw i64 %indvars.iv4, 1 + %1 = add nsw i64 %indvars.iv, -2 + %arrayidx6 = getelementptr inbounds [2048 x i32], [2048 x i32]* %a, i64 %0, i64 %1 + %2 = load i32, i32* %arrayidx6, align 4 + %arrayidx10 = getelementptr inbounds [2048 x i32], [2048 x i32]* %a, i64 %indvars.iv4, i64 %indvars.iv + store i32 %2, i32* %arrayidx10, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp ne i64 %indvars.iv.next, 2048 + br i1 %exitcond, label %for.body4, label %for.inc11 + +for.inc11: ; preds = %for.body4 + %indvars.iv.next5 = add nuw nsw i64 %indvars.iv4, 1 + %exitcond7 = icmp ne i64 %indvars.iv.next5, 1023 + br i1 %exitcond7, label %for.body, label %for.end13 + +for.end13: ; preds = %for.inc11 + ret void +} + + +; CHECK-LABEL: t2 +; CHECK: da analyze - none! +; CHECK: da analyze - consistent anti [1 -2 0 -3 2]! +; CHECK: da analyze - none! + +;; #define N 1024 +;; #define M 2048 +;; void t2(int a[][N][N][N][M]) { +;; for (int i1 = 0; i1 < N-1; ++i1) +;; for (int i2 = 2; i2 < N; ++i2) +;; for (int i3 = 0; i3 < N; ++i3) +;; for (int i4 = 3; i4 < N; ++i4) +;; for (int i5 = 0; i5 < M-2; ++i5) +;; a[i1][i2][i3][i4][i5] = a[i1+1][i2-2][i3][i4-3][i5+2]; +;; } + +define void @t2([1024 x [1024 x [1024 x [2048 x i32]]]]* %a) { +entry: + br label %for.body + +for.body: ; preds = %entry, %for.inc46 + %indvars.iv18 = phi i64 [ 0, %entry ], [ %indvars.iv.next19, %for.inc46 ] + br label %for.body4 + +for.body4: ; preds = %for.body, %for.inc43 + %indvars.iv14 = phi i64 [ 2, %for.body ], [ %indvars.iv.next15, %for.inc43 ] + br label %for.body8 + +for.body8: ; preds = %for.body4, %for.inc40 + %indvars.iv11 = phi i64 [ 0, %for.body4 ], [ %indvars.iv.next12, %for.inc40 ] + br label %for.body12 + +for.body12: ; preds = %for.body8, %for.inc37 + %indvars.iv7 = phi i64 [ 3, %for.body8 ], [ %indvars.iv.next8, %for.inc37 ] + br label %for.body16 + +for.body16: ; preds = %for.body12, %for.body16 + %indvars.iv = phi i64 [ 0, %for.body12 ], [ %indvars.iv.next, %for.body16 ] + %0 = add nuw nsw i64 %indvars.iv18, 1 + %1 = add nsw i64 %indvars.iv14, -2 + %2 = add nsw i64 %indvars.iv7, -3 + %3 = add nuw nsw i64 %indvars.iv, 2 + %arrayidx26 = getelementptr inbounds [1024 x [1024 x [1024 x [2048 x i32]]]], [1024 x [1024 x [1024 x [2048 x i32]]]]* %a, i64 %0, i64 %1, i64 %indvars.iv11, i64 %2, i64 %3 + %4 = load i32, i32* %arrayidx26, align 4 + %arrayidx36 = getelementptr inbounds [1024 x [1024 x [1024 x [2048 x i32]]]], [1024 x [1024 x [1024 x [2048 x i32]]]]* %a, i64 %indvars.iv18, i64 %indvars.iv14, i64 %indvars.iv11, i64 %indvars.iv7, i64 %indvars.iv + store i32 %4, i32* %arrayidx36, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp ne i64 %indvars.iv.next, 2046 + br i1 %exitcond, label %for.body16, label %for.inc37 + +for.inc37: ; preds = %for.body16 + %indvars.iv.next8 = add nuw nsw i64 %indvars.iv7, 1 + %exitcond10 = icmp ne i64 %indvars.iv.next8, 1024 + br i1 %exitcond10, label %for.body12, label %for.inc40 + +for.inc40: ; preds = %for.inc37 + %indvars.iv.next12 = add nuw nsw i64 %indvars.iv11, 1 + %exitcond13 = icmp ne i64 %indvars.iv.next12, 1024 + br i1 %exitcond13, label %for.body8, label %for.inc43 + +for.inc43: ; preds = %for.inc40 + %indvars.iv.next15 = add nuw nsw i64 %indvars.iv14, 1 + %exitcond17 = icmp ne i64 %indvars.iv.next15, 1024 + br i1 %exitcond17, label %for.body4, label %for.inc46 + +for.inc46: ; preds = %for.inc43 + %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1 + %exitcond21 = icmp ne i64 %indvars.iv.next19, 1023 + br i1 %exitcond21, label %for.body, label %for.end48 + +for.end48: ; preds = %for.inc46 + ret void +} 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-disable-delinearization-checks -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