Index: lib/Analysis/DependenceAnalysis.cpp =================================================================== --- lib/Analysis/DependenceAnalysis.cpp +++ lib/Analysis/DependenceAnalysis.cpp @@ -105,6 +105,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, @@ -3644,6 +3645,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 && !SE->isLoopInvariant(SrcSCEV, SrcL) && + !SE->isLoopInvariant(DstSCEV, DstL)) { + 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,85 @@ +; 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 - none! +; CHECK: da analyze - anti [= =|<]! +; CHECK: da analyze - none! + +define void @test1(i32** %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 i32*, i32** %Arr, i64 %indvars.iv + %0 = load i32*, i32** %arrayidx, align 8 + %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %indvars.iv23 + %1 = load i32, i32* %arrayidx6, align 4 + %add7 = add i32 %1, 10 + store i32 %add7, i32* %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(i32** %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 i32*, i32** %Arr, i64 %indvars.iv23 + %0 = load i32*, i32** %arrayidx, align 8 + %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %indvars.iv + %1 = load i32, i32* %arrayidx6, align 4 + %add7 = add i32 %1, 10 + store i32 %add7, i32* %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 +} 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 @@ -50,7 +50,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