Index: lib/Analysis/DependenceAnalysis.cpp =================================================================== --- lib/Analysis/DependenceAnalysis.cpp +++ lib/Analysis/DependenceAnalysis.cpp @@ -106,6 +106,7 @@ STATISTIC(BanerjeeApplications, "Banerjee applications"); STATISTIC(BanerjeeIndependence, "Banerjee independence"); STATISTIC(BanerjeeSuccesses, "Banerjee successes"); +STATISTIC(SymbolicEQSuccesses, "Symbolic EQ successes"); static cl::opt Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, @@ -3298,6 +3299,51 @@ } #endif +// Returns true if expression S is proven to be not loop invariant in loop +// L. This stronger than just checking !SE->isLoopInvariant(), as +// isLoopInvariant only returns true if the expression can be proven to be +// loop invariant, but there are loop invariant expression that isLoopInvariant +// might not be able to prove. +static bool IsNotLoopInvariant(const SCEV *S, const Loop *L, + ScalarEvolution *SE) { + switch (static_cast(S->getSCEVType())) { + case scConstant: + return false; + case scTruncate: + case scZeroExtend: + case scSignExtend: + return IsNotLoopInvariant(cast(S)->getOperand(), L, SE); + case scAddRecExpr: { + const SCEVAddRecExpr *AR = cast(S); + // If L is the addrec's loop and it has a non-zero step, it is not loop + // invariant. + if (AR->getLoop() == L) + return SE->isKnownNonZero(AR->getStepRecurrence(*SE)); + return false; + } + case scAddExpr: + // AddExpr are not loop invariant if any of the terms is not loop invariant. + return any_of(cast(S)->operands(), [L, SE](const SCEV *S) { + return IsNotLoopInvariant(S, L, SE); + }); + case scMulExpr: { + // MulExpr is are not loop invariant if any of the terms is not loop + // invariant and we do not multiply with 0. + bool AnyNotInvariant = false; + bool AllInvariantNonZero = true; + for (const SCEV *Op : cast(S)->operands()) { + bool NotInvariant = IsNotLoopInvariant(Op, L, SE); + AnyNotInvariant |= NotInvariant; + AllInvariantNonZero &= NotInvariant || SE->isKnownNonZero(Op); + } + + return AllInvariantNonZero && AnyNotInvariant; + } + default: + return false; + } +} + // depends - // Returns NULL if there is no dependence. // Otherwise, return a Dependence with as many details as possible. @@ -3652,6 +3698,20 @@ } } + // Try to conclude DVEntry::EQ, in case Src and Dst access the same memory + // location for loop dependent locations in the same loop. + Loop *SrcL = LI->getLoopFor(Src->getParent()); + Loop *DstL = LI->getLoopFor(Dst->getParent()); + if (SrcL == DstL && IsNotLoopInvariant(SrcSCEV, SrcL, SE) && + IsNotLoopInvariant(DstSCEV, DstL, SE)) { + const SCEV *DiffSCEV = SE->getMinusSCEV(SrcSCEV, DstSCEV); + if (DiffSCEV->isZero()) { + for (unsigned i = 0; i < Result.Levels; i++) + Result.DV[i].Direction = Dependence::DVEntry::EQ; + SymbolicEQSuccesses++; + } + } + // Make sure the Scalar flags are set correctly. SmallBitVector CompleteLoops(MaxLevels + 1); for (unsigned SI = 0; SI < Pairs; ++SI) Index: test/Analysis/DependenceAnalysis/AA.ll =================================================================== --- test/Analysis/DependenceAnalysis/AA.ll +++ test/Analysis/DependenceAnalysis/AA.ll @@ -89,9 +89,9 @@ } ; CHECK-LABEL: tbaa_loop -; CHECK: da analyze - input -; CHECK: da analyze - none -; CHECK: da analyze - output +; CHECK: da analyze - none! +; CHECK: da analyze - none! +; CHECK: da analyze - none! define void @tbaa_loop(i32 %I, i32 %J, i32* nocapture %A, i16* nocapture readonly %B) { entry: %cmp = icmp ne i32 %J, 0 Index: test/Analysis/DependenceAnalysis/Banerjee.ll =================================================================== --- test/Analysis/DependenceAnalysis/Banerjee.ll +++ test/Analysis/DependenceAnalysis/Banerjee.ll @@ -75,20 +75,20 @@ br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end9 ; CHECK: 'Dependence Analysis' for function 'banerjee1': -; CHECK: da analyze - output [* *]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [* <>]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! -; CHECK: da analyze - output [* *]! +; CHECK: da analyze - none! ; DELIN: 'Dependence Analysis' for function 'banerjee1': -; 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 - output [* *]! +; DELIN: da analyze - none! for.cond1.preheader.preheader: ; preds = %entry %0 = add i64 %n, 1 @@ -563,7 +563,7 @@ br label %for.cond1.preheader ; CHECK: 'Dependence Analysis' for function 'banerjee9': -; CHECK: da analyze - output [* *]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [<= =|<]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -571,7 +571,7 @@ ; CHECK: da analyze - none! ; DELIN: 'Dependence Analysis' for function 'banerjee9': -; DELIN: da analyze - output [* *]! +; DELIN: da analyze - none! ; DELIN: da analyze - flow [<= =|<]! ; DELIN: da analyze - confused! ; DELIN: da analyze - none! Index: test/Analysis/DependenceAnalysis/GCD.ll =================================================================== --- test/Analysis/DependenceAnalysis/GCD.ll +++ test/Analysis/DependenceAnalysis/GCD.ll @@ -15,10 +15,10 @@ br label %for.cond1.preheader ; DELIN-LABEL: gcd0 -; 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! @@ -68,10 +68,10 @@ br label %for.cond1.preheader ; DELIN-LABEL: gcd1 -; 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! @@ -122,10 +122,10 @@ br label %for.cond1.preheader ; DELIN-LABEL: gcd2 -; 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! @@ -176,10 +176,10 @@ br label %for.cond1.preheader ; DELIN-LABEL: gcd3 -; 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! @@ -358,7 +358,7 @@ ; DELIN: da analyze - confused! ; DELIN: da analyze - none! ; DELIN: da analyze - confused! -; DELIN: da analyze - output [* *]! +; DELIN: da analyze - none! for.cond1.preheader.preheader: ; preds = %entry br label %for.cond1.preheader @@ -425,12 +425,12 @@ br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15 ; DELIN-LABEL: gcd7 -; 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 - output [* *]! +; DELIN: da analyze - none! for.cond1.preheader.preheader: ; preds = %entry br label %for.cond1.preheader @@ -509,12 +509,12 @@ br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15 ; DELIN-LABEL: gcd8 -; 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 - output [* *]! +; DELIN: da analyze - none! for.cond1.preheader.preheader: ; preds = %entry br label %for.cond1.preheader @@ -588,12 +588,12 @@ br i1 %cmp4, label %for.end15, label %for.cond1.preheader.preheader ; DELIN-LABEL: gcd9 -; 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 - output [* *]! +; DELIN: da analyze - none! for.cond1.preheader.preheader: ; preds = %entry br label %for.cond1.preheader Index: test/Analysis/DependenceAnalysis/Invariant.ll =================================================================== --- test/Analysis/DependenceAnalysis/Invariant.ll +++ test/Analysis/DependenceAnalysis/Invariant.ll @@ -4,7 +4,7 @@ ; SCEVAddRecExpr is created in addToCoefficient. ; CHECK-LABEL: foo -; CHECK: da analyze - consistent input [S 0]! +; CHECK: da analyze - none! ; CHECK: da analyze - input [* *|<]! ; CHECK: da analyze - none! Index: test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll =================================================================== --- test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll +++ test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll @@ -54,7 +54,7 @@ entry: br label %for.cond -; DELIN: da analyze - input [* *]! +; DELIN: da analyze - none! ; DELIN: da analyze - anti [* *|<]! ; DELIN: da analyze - none! for.cond: ; preds = %for.inc11, %entry Index: test/Analysis/DependenceAnalysis/PR21585.ll =================================================================== --- test/Analysis/DependenceAnalysis/PR21585.ll +++ test/Analysis/DependenceAnalysis/PR21585.ll @@ -20,7 +20,7 @@ } ; CHECK: none ; CHECK: anti -; CHECK: output +; CHECK: da analyze - consistent output [S]! ; Test for a bug, which caused an assert in ScalarEvolution because @@ -52,9 +52,9 @@ for.end: ret void } -; CHECK: input +; CHECK: da analyze - consistent input [S]! +; CHECK: none ; CHECK: none -; CHECK: output define void @i16_wrap(i64* %a) { entry: @@ -75,9 +75,9 @@ for.end: ret void } -; CHECK: input +; CHECK: none ; CHECK: anti -; CHECK: output +; CHECK: none define void @i8_stride_wrap(i32* noalias %a, i32* noalias %b) { entry: @@ -100,6 +100,6 @@ for.end: ret void } -; CHECK: input +; CHECK: da analyze - consistent input [S]! ; CHECK: none ; CHECK: none Index: test/Analysis/DependenceAnalysis/Preliminary.ll =================================================================== --- test/Analysis/DependenceAnalysis/Preliminary.ll +++ test/Analysis/DependenceAnalysis/Preliminary.ll @@ -57,12 +57,12 @@ br i1 %cmp10, label %for.cond1.preheader.preheader, label %for.end26 ; CHECK-LABEL: p2 -; CHECK: da analyze - output [* * *]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [* *|<]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* * *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! -; CHECK: da analyze - output [* * *]! +; CHECK: da analyze - none! for.cond1.preheader.preheader: ; preds = %entry br label %for.cond1.preheader @@ -430,10 +430,10 @@ br i1 %cmp1, label %for.body.preheader, label %for.end ; CHECK-LABEL: p4 -; CHECK: da analyze - output [*]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [*|<]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [*]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -477,10 +477,10 @@ br i1 %cmp1, label %for.body.preheader, label %for.end ; CHECK-LABEL: p5 -; CHECK: da analyze - output [*]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [*|<]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [*]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! Index: test/Analysis/DependenceAnalysis/Propagating.ll =================================================================== --- test/Analysis/DependenceAnalysis/Propagating.ll +++ test/Analysis/DependenceAnalysis/Propagating.ll @@ -66,10 +66,10 @@ br label %for.cond1.preheader ; CHECK-LABEL: prop1 -; CHECK: da analyze - output [* * *]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [<> <> *]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* * *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -180,10 +180,10 @@ br label %for.cond1.preheader ; CHECK-LABEL: prop3 -; CHECK: da analyze - output [* *]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [<> *]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -449,7 +449,7 @@ br label %for.cond1.preheader ; CHECK-LABEL: prop8 -; CHECK: da analyze - consistent output [S 0]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [=> <]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -504,7 +504,7 @@ ; CHECK: da analyze - none! ; CHECK: da analyze - flow [<= <]! ; CHECK: da analyze - confused! -; CHECK: da analyze - consistent input [S 0]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! Index: test/Analysis/DependenceAnalysis/Separability.ll =================================================================== --- test/Analysis/DependenceAnalysis/Separability.ll +++ test/Analysis/DependenceAnalysis/Separability.ll @@ -19,7 +19,7 @@ ; CHECK: da analyze - output [= * * S]! ; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* * S *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -94,7 +94,7 @@ ; CHECK: da analyze - output [= * * S]! ; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [* * S *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -165,10 +165,10 @@ entry: br label %for.cond1.preheader -; CHECK: da analyze - output [= S = =]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [* * * <>]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [= * * *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! @@ -239,10 +239,10 @@ entry: br label %for.cond1.preheader -; CHECK: da analyze - output [= S = =]! +; CHECK: da analyze - none! ; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - confused! -; CHECK: da analyze - input [= * * *]! +; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! Index: test/Analysis/DependenceAnalysis/Symbolic.ll =================================================================== --- /dev/null +++ test/Analysis/DependenceAnalysis/Symbolic.ll @@ -0,0 +1,378 @@ +; RUN: opt < %s -analyze -basicaa -da | FileCheck %s + +; void no_deps_interchange(unsigned **Arr) { +; for (int i = 0; i < 1024; ++i) +; for(int j = 0; j < 1024; ++j) +; Arr[j][i] += Arr[j][i] + 10; +; } +; CHECK-LABEL: 'Dependence Analysis' for function 'test1' +; CHECK: da analyze - none! +; CHECK: da analyze - confused! +; CHECK: da analyze - confused! +; CHECK: da analyze - input [* *]! +; CHECK: da analyze - anti [* *|<]! +; CHECK: da analyze - output [* *]! + +define void @test1(i64** %Arr) { +entry: + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry + %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.cond.cleanup3 ] + br label %for.body4 + +for.cond.cleanup: ; preds = %for.cond.cleanup3 + ret void + +for.cond.cleanup3: ; preds = %for.body4 + %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1 + %exitcond25 = icmp eq i64 %indvars.iv.next24, 1024 + br i1 %exitcond25, label %for.cond.cleanup, label %for.cond1.preheader + +for.body4: ; preds = %for.body4, %for.cond1.preheader + %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next.3, %for.body4 ] + %arrayidx = getelementptr inbounds i64*, i64** %Arr, i64 %indvars.iv + %0 = load i64*, i64** %arrayidx, align 8 + %arrayidx6 = getelementptr inbounds i64, i64* %0, i64 %indvars.iv23 + %1 = load i64, i64* %arrayidx6, align 4 + %add7 = add i64 %1, 10 + store i64 %add7, i64* %arrayidx6 + %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1 + %exitcond.3 = icmp eq i64 %indvars.iv.next.3, 1024 + br i1 %exitcond.3, label %for.cond.cleanup3, label %for.body4 +} + +; void no_deps_interchange(unsigned **Arr) { +; for (int i = 0; i < 1024; ++i) +; for(int j = 0; j < 1024; ++j) +; Arr[i][j] += Arr[i][j] + 10; +; } +; CHECK-LABEL: 'Dependence Analysis' for function 'test2' +; CHECK: da analyze - consistent input [0 S]! +; CHECK: da analyze - confused! +; CHECK: da analyze - confused! +; CHECK: da analyze - none! +; CHECK: da analyze - anti [= =|<]! +; CHECK: da analyze - none! + +define void @test2(i64** %Arr) { +entry: + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry + %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.cond.cleanup3 ] + br label %for.body4 + +for.cond.cleanup: ; preds = %for.cond.cleanup3 + ret void + +for.cond.cleanup3: ; preds = %for.body4 + %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1 + %exitcond25 = icmp eq i64 %indvars.iv.next24, 1024 + br i1 %exitcond25, label %for.cond.cleanup, label %for.cond1.preheader + +for.body4: ; preds = %for.body4, %for.cond1.preheader + %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next.3, %for.body4 ] + %arrayidx = getelementptr inbounds i64*, i64** %Arr, i64 %indvars.iv23 + %0 = load i64*, i64** %arrayidx, align 8 + %arrayidx6 = getelementptr inbounds i64, i64* %0, i64 %indvars.iv + %1 = load i64, i64* %arrayidx6, align 4 + %add7 = add i64 %1, 10 + store i64 %add7, i64* %arrayidx6 + %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1 + %exitcond.3 = icmp eq i64 %indvars.iv.next.3, 1024 + br i1 %exitcond.3, label %for.cond.cleanup3, label %for.body4 +} + +; Array index may be loop invariant (if N is 0), we cannot deduce a EQ +; dependence. +; void test3(unsigned *Arr, unsigned N) { +; for (int i = 0; i < 1024; ++i) +; for(int j = 0; j < 1024; ++j) +; Arr[(i + j) * N] += Arr[(i + j) * N] + 10; +; } +; +; CHECK-LABEL: 'Dependence Analysis' for function 'test3' +; CHECK:da analyze - input [* *]! +; CHECK-NEXT: da analyze - anti [* *|<]! +; CHECK-NEXT: da analyze - output [* *]! + +define void @test3(i64* nocapture %Arr, i64 %N) { +entry: + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry + %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ] + br label %for.body4 + +for.cond.cleanup: ; preds = %for.cond.cleanup3 + ret void + +for.cond.cleanup3: ; preds = %for.body4 + %inc12 = add nuw nsw i64 %i.025, 1 + %exitcond26 = icmp eq i64 %inc12, 1024 + br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader + +for.body4: ; preds = %for.body4, %for.cond1.preheader + %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ] + %add = add i64 %indvars.iv, %i.025 + %idxprom = mul i64 %add, %N + %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom + %lv = load i64, i64* %arrayidx, align 4 + %add10 = add i64 %lv, 10 + store i64 %add10, i64* %arrayidx, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1024 + br i1 %exitcond, label %for.cond.cleanup3, label %for.body4 +} + +; Array index is guaranteed to not be loop invariant, we can deduce there is a +; EQ dependence. +; void test4(unsigned *Arr) { +; for (int i = 0; i < 1024; ++i) +; for(int j = 0; j < 1024; ++j) +; Arr[(i + j) * 1024] += Arr[(i + j) * 1024] + 10; +; } +; +; CHECK-LABEL: 'Dependence Analysis' for function 'test4' +; CHECK: da analyze - none! +; CHECK-NEXT: da analyze - anti [= =|<]! +; CHECK-NEXT: da analyze - none! +define void @test4(i64* nocapture %Arr) { +entry: + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry + %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ] + br label %for.body4 + +for.cond.cleanup: ; preds = %for.cond.cleanup3 + ret void + +for.cond.cleanup3: ; preds = %for.body4 + %inc12 = add nuw nsw i64 %i.025, 1 + %exitcond26 = icmp eq i64 %inc12, 1024 + br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader + +for.body4: ; preds = %for.body4, %for.cond1.preheader + %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ] + %add = add i64 %indvars.iv, %i.025 + %idxprom = mul i64 %add, 1024 + %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom + %lv = load i64, i64* %arrayidx, align 4 + %add10 = add i64 %lv, 10 + store i64 %add10, i64* %arrayidx, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1024 + br i1 %exitcond, label %for.cond.cleanup3, label %for.body4 +} + +; Array index is guaranteed to not be loop invariant, we can deduce there is a +; EQ dependence. +; void test5(unsigned *Arr) { +; for (int i = 0; i < 1024; ++i) +; for(int j = 0; j < 1024; ++j) +; Arr[i * N + j] += Arr[i *N + j] + 10; +; } +; +; CHECK-LABEL: 'Dependence Analysis' for function 'test5' +; CHECK: da analyze - none! +; CHECK-NEXT: da analyze - anti [= =|<]! +; CHECK-NEXT: da analyze - none! + +define void @test5(i64* nocapture %Arr, i64 %N) { +entry: + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry + %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ] + br label %for.body4 + +for.cond.cleanup: ; preds = %for.cond.cleanup3 + ret void + +for.cond.cleanup3: ; preds = %for.body4 + %inc12 = add nuw nsw i64 %i.025, 1 + %exitcond26 = icmp eq i64 %inc12, 1024 + br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader + +for.body4: ; preds = %for.body4, %for.cond1.preheader + %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ] + %mul = mul i64 %i.025, %N + %idxprom = add i64 %indvars.iv, %mul + %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom + %lv = load i64, i64* %arrayidx, align 4 + %add10 = add i64 %lv, 10 + store i64 %add10, i64* %arrayidx, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1024 + br i1 %exitcond, label %for.cond.cleanup3, label %for.body4 +} + +; Array index may be loop invariant (if N is 0), we cannot deduce there is a +; EQ dependence. +; void test6(unsigned *Arr, unsigned N) { +; for (int i = 0; i < 1024; ++i) +; for(int j = 0; j < 1024; ++j) +; Arr[i + j * N] += Arr[i + j * N] + 10; +; } +; +; +; CHECK-LABEL: 'Dependence Analysis' for function 'test6' +; CHECK:da analyze - input [* *]! +; CHECK-NEXT: da analyze - anti [* *|<]! +; CHECK-NEXT: da analyze - output [* *]! + +define void @test6(i64* nocapture %Arr, i64 %N) { +entry: + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry + %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ] + br label %for.body4 + +for.cond.cleanup: ; preds = %for.cond.cleanup3 + ret void + +for.cond.cleanup3: ; preds = %for.body4 + %inc12 = add nuw nsw i64 %i.025, 1 + %exitcond26 = icmp eq i64 %inc12, 1024 + br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader + +for.body4: ; preds = %for.body4, %for.cond1.preheader + %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ] + %mul = mul i64 %indvars.iv, %N + %idxprom = add i64 %mul, %i.025 + %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom + %lv = load i64, i64* %arrayidx, align 4 + %add10 = add i64 %lv, 10 + store i64 %add10, i64* %arrayidx, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1024 + br i1 %exitcond, label %for.cond.cleanup3, label %for.body4 +} + +; Cannot deduce EQ dependence here, because subtracting induction variables +; from the same loop might yield a constant. +; void test7(unsigned *Arr) { +; unsigned j = 0; +; for (int i = 0; i < 1024; ++i) { +; Arr[1024 + (i - j)] += Arr[1024 + (i - j)] + 10; +; j++; +; } +; } +; +; CHECK-LABEL: 'Dependence Analysis' for function 'test7' +; CHECK: da analyze - consistent input [S]! +; CHECK-NEXT: da analyze - consistent anti [S|<]! +; CHECK-NEXT: da analyze - consistent output [S]! + +define void @test7(i64* nocapture %Arr, i64 %N) { +entry: + br label %for.body4 + +for.cond.cleanup: ; preds = %for.cond.cleanup3 + ret void + +for.body4: ; preds = %for.body4, %for.cond1.preheader + %indvars.iv = phi i64 [ 0, %entry], [ %indvars.iv.next, %for.body4 ] + %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.body4 ] + %idxsub = sub i64 %i.025, %indvars.iv + %idxprom = add i64 1024, %idxsub + %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom + %lv = load i64, i64* %arrayidx, align 4 + %add10 = add i64 %lv, 10 + store i64 %add10, i64* %arrayidx, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 1024 + %inc12 = add nuw nsw i64 %i.025, 1 + br i1 %exitcond, label %for.cond.cleanup, label %for.body4 +} + +; We can deduce there is EQ dependence between accesses to c. +; unsigned a[1024][1024]; +; unsigned b[1024][1024]; +; unsigned c[1024][1024]; +; +; void test9(unsigned N) { +; for (unsigned j = 0; j < N; j++) +; for (unsigned k = 0; k < N; k++) +; for (unsigned i = 0; i < N; i++) +; c[i][j] = c[i][j] + a[i+1][k]; +; a[i][k] = a[i+1][k]; +; b[i][k] = b[j][k-1]; +; } + +; CHECK-LABEL: 'Dependence Analysis' for function 'test9' +; CHECK: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - anti [= S =|<]! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - anti [S * *|<]! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - anti [S <> *]! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - none! +; +@a = global [1024 x [1024 x i64]] zeroinitializer, align 16 +@b = global [1024 x [1024 x i64]] zeroinitializer, align 16 +@c = global [1024 x [1024 x i64]] zeroinitializer, align 16 + +define dso_local void @test9(i64 %N) local_unnamed_addr { +entry: + %cmp49 = icmp sgt i64 %N, 0 + br i1 %cmp49, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup + +for.cond5.preheader.lr.ph: ; preds = %entry, %for.cond.cleanup3 + %indvars.iv55 = phi i64 [ %indvars.iv.next56, %for.cond.cleanup3 ], [ 0, %entry ] + br label %for.body8.lr.ph + +for.cond.cleanup: ; preds = %for.cond.cleanup3, %entry + ret void + +for.body8.lr.ph: ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph + %indvars.iv51 = phi i64 [ 0, %for.cond5.preheader.lr.ph ], [ %indvars.iv.next52, %for.cond.cleanup7 ] + br label %for.body8 + +for.cond.cleanup3: ; preds = %for.cond.cleanup7 + %indvars.iv.next56 = add nuw nsw i64 %indvars.iv55, 1 + %exitcond58 = icmp eq i64 %indvars.iv.next56, %N + br i1 %exitcond58, label %for.cond.cleanup, label %for.cond5.preheader.lr.ph + +for.cond.cleanup7: ; preds = %for.body8 + %indvars.iv.next52 = add nuw nsw i64 %indvars.iv51, 1 + %exitcond54 = icmp eq i64 %indvars.iv.next52, %N + br i1 %exitcond54, label %for.cond.cleanup3, label %for.body8.lr.ph + +for.body8: ; preds = %for.body8, %for.body8.lr.ph + %indvars.iv = phi i64 [ 0, %for.body8.lr.ph ], [ %indvars.iv.next, %for.body8 ] + %arrayidx10 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @c, i64 0, i64 %indvars.iv, i64 %indvars.iv55 + %arrayidx14 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @a, i64 0, i64 %indvars.iv, i64 %indvars.iv51 + %i_next = add i64 %indvars.iv, 1 + %arrayidx16 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @a, i64 0, i64 %i_next, i64 %indvars.iv51 + %k_sub = sub i64 %indvars.iv51, 1 + %arrayidx18 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @b, i64 0, i64 %indvars.iv, i64 %k_sub + %arrayidx20 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @b, i64 0, i64 %indvars.iv, i64 %indvars.iv51 + %vc = load i64, i64* %arrayidx10, align 4 + %va = load i64, i64* %arrayidx16, align 4 + %vb = load i64, i64* %arrayidx18, align 4 + %add = add nsw i64 %vc, %va + store i64 %add, i64* %arrayidx10, align 4 + store i64 %va, i64* %arrayidx14, align 4 + store i64 %vb, i64* %arrayidx20, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, %N + br i1 %exitcond, label %for.cond.cleanup7, label %for.body8 +} Index: test/Analysis/DependenceAnalysis/SymbolicRDIV.ll =================================================================== --- test/Analysis/DependenceAnalysis/SymbolicRDIV.ll +++ test/Analysis/DependenceAnalysis/SymbolicRDIV.ll @@ -392,12 +392,12 @@ br i1 %cmp4, label %for.end7, label %for.cond1.preheader.preheader ; CHECK: 'Dependence Analysis' for function 'symbolicrdiv6' -; CHECK: da analyze - output [* *]! +; CHECK: da analyze - none! ; CHECK: da analyze - none! ; CHECK: da analyze - confused! ; CHECK: da analyze - consistent input [S S]! ; CHECK: da analyze - confused! -; CHECK: da analyze - output [* *]! +; CHECK: da analyze - none! for.cond1.preheader.preheader: ; preds = %entry br label %for.cond1.preheader Index: test/Analysis/DependenceAnalysis/WeakZeroSrcSIV.ll =================================================================== --- test/Analysis/DependenceAnalysis/WeakZeroSrcSIV.ll +++ test/Analysis/DependenceAnalysis/WeakZeroSrcSIV.ll @@ -77,7 +77,7 @@ %cmp1 = icmp eq i64 %n, 0 br i1 %cmp1, label %for.end, label %for.body.preheader -; CHECK: da analyze - consistent output [S]! +; CHECK: da analyze - consistent output [S] ; CHECK: da analyze - flow [p=>|<]! ; CHECK: da analyze - confused! ; CHECK: da analyze - none! Index: test/Transforms/LoopInterchange/currentLimitation.ll =================================================================== --- test/Transforms/LoopInterchange/currentLimitation.ll +++ test/Transforms/LoopInterchange/currentLimitation.ll @@ -16,11 +16,10 @@ ;; for(int j=1;j