This is an archive of the discontinued LLVM Phabricator instance.

Differential D46201

[DA] Use SCEV to conclude DVEntry::EQ in some cases.
Changes PlannedPublic

Authored by fhahn on Apr 27 2018, 11:12 AM.

Details

Reviewers
hfinkel
sebpop
grosser
dmgreen
philip.pfaffe
sanjoy
Summary

This is a very naive approach to conclude that both accesses to Arr1 in the
loop below access the same memory location.

void foo(unsigned **Arr1) {
  for (int i = 0; i < 1024; ++i)
    for(int j = 0; j < 1024; ++j)
      Arr1[j][i] = Arr1[j][i] 10;
}

By using SCEV, we can conclude that both accesses to Arr1 access the
same location in each loop iteration. I am probably missing something,
but this seems to work for loop variant accesses in the same loop.

It would be great if you could have a look and let me know what I am
missing :)

For SPEC2006 and the test-suite with LTO, this triggers in around 1100
cases. It also helps LoopInterchange to interchange a few more loops.

Diff Detail

Event Timeline

fhahn created this revision.Apr 27 2018, 11:12 AM
Herald added subscribers: javed.absar, mehdi_amini. · View Herald TranscriptApr 27 2018, 11:12 AM
dmgreen added a subscriber: dmgreen.Apr 28 2018, 3:19 AM
fhahn added a reviewer: dmgreen.May 1 2018, 2:56 AM
tvvikram added a subscriber: tvvikram.May 3 2018, 4:10 AM
tvvikram added inline comments.
lib/Analysis/DependenceAnalysis.cpp
3654

Even I am facing a similar issue. What happens if the access is something like A[(i + j) * n] = A[(i + j) * n] + 10, where n can be 0. In this case, the dependence would be "*" and not "=" right? Maybe just checking if difference is zero wouldn't be enough but traversing the SCEV to see that it is simple/understandable would be necessary.

fhahn planned changes to this revision.May 4 2018, 10:24 AM
fhahn added inline comments.
lib/Analysis/DependenceAnalysis.cpp
3654

Right, thanks for having a look! isLoopInvariant is not enough, looks like we need something like "may be loop invariant" :) I'll update the patch.

fhahn updated this revision to Diff 149977.Jun 5 2018, 7:22 AM
fhahn added reviewers: philip.pfaffe, sanjoy.

Added IsNotLoopInvariant helper to make sure the expressions we are comparing are not loop invariant, to avoid deducing EQ for scalar dependencies.

philip.pfaffe added a comment.Jun 6 2018, 3:22 AM

This does not look correct. Consider the AA.ll testcase. Your change makes DA claim there is no output dependency on the load in %for.inner, but there is! Carried over the outer loop. So the result should be input[* =] (don't quote me on the syntax though).

fhahn planned changes to this revision.Jun 7 2018, 8:23 AM
In D46201#1123382, @philip.pfaffe wrote:

This does not look correct. Consider the AA.ll testcase. Your change makes DA claim there is no output dependency on the load in %for.inner, but there is! Carried over the outer loop. So the result should be input[* =] (don't quote me on the syntax though).

Right, we should only set EQ for levels that with induction variables involved. I will update the patch

sanjoy resigned from this revision.Jan 29 2022, 5:43 PM
Herald added a subscriber: bmahjour. · View Herald TranscriptJan 29 2022, 5:43 PM

Revision Contents

PathSize
lib/
Analysis/
15 lines
test/
Analysis/
DependenceAnalysis/
6 lines
16 lines
36 lines
2 lines
2 lines
12 lines
14 lines
12 lines
12 lines
85 lines
4 lines
2 lines
Transforms/
LoopInterchange/
15 lines
15 lines

Diff 144371

lib/Analysis/DependenceAnalysis.cpp

Show First 20 Lines • Show All 99 Lines • ▼ Show 20 Lines
STATISTIC(DeltaIndependence, "Delta independence"); STATISTIC(DeltaIndependence, "Delta independence");
STATISTIC(DeltaPropagations, "Delta propagations"); STATISTIC(DeltaPropagations, "Delta propagations");
STATISTIC(GCDapplications, "GCD applications"); STATISTIC(GCDapplications, "GCD applications");
STATISTIC(GCDsuccesses, "GCD successes"); STATISTIC(GCDsuccesses, "GCD successes");
STATISTIC(GCDindependence, "GCD independence"); STATISTIC(GCDindependence, "GCD independence");
STATISTIC(BanerjeeApplications, "Banerjee applications"); STATISTIC(BanerjeeApplications, "Banerjee applications");
STATISTIC(BanerjeeIndependence, "Banerjee independence"); STATISTIC(BanerjeeIndependence, "Banerjee independence");
STATISTIC(BanerjeeSuccesses, "Banerjee successes"); STATISTIC(BanerjeeSuccesses, "Banerjee successes");
STATISTIC(SymbolicEQSuccesses, "Symbolic EQ successes");
static cl::opt<bool> static cl::opt<bool>
Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore,
cl::desc("Try to delinearize array references.")); cl::desc("Try to delinearize array references."));
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// basics // basics
▲ Show 20 Lines • Show All 3,523 Lines • ▼ Show 20 Lines for (unsigned SI : Coupled.set_bits()) {
break; break;
updateDirection(Result.DV[SJ - 1], Constraints[SJ]); updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
return nullptr; return nullptr;
} }
} }
} }
// 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);
tvvikramUnsubmitted
Not Done
ReplyInline Actions

Even I am facing a similar issue. What happens if the access is something like A[(i + j) * n] = A[(i + j) * n] + 10, where n can be 0. In this case, the dependence would be "*" and not "=" right? Maybe just checking if difference is zero wouldn't be enough but traversing the SCEV to see that it is simple/understandable would be necessary.

tvvikram: Even I am facing a similar issue. What happens if the access is something like A[(i + j) * n] =…
fhahnAuthorUnsubmitted
Not Done
ReplyInline Actions

Right, thanks for having a look! isLoopInvariant is not enough, looks like we need something like "may be loop invariant" :) I'll update the patch.

fhahn: Right, thanks for having a look! `isLoopInvariant` is not enough, looks like we need something…
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. // Make sure the Scalar flags are set correctly.
SmallBitVector CompleteLoops(MaxLevels + 1); SmallBitVector CompleteLoops(MaxLevels + 1);
for (unsigned SI = 0; SI < Pairs; ++SI) for (unsigned SI = 0; SI < Pairs; ++SI)
CompleteLoops |= Pair[SI].Loops; CompleteLoops |= Pair[SI].Loops;
for (unsigned II = 1; II <= CommonLevels; ++II) for (unsigned II = 1; II <= CommonLevels; ++II)
if (CompleteLoops[II]) if (CompleteLoops[II])
Result.DV[II - 1].Scalar = false; Result.DV[II - 1].Scalar = false;
▲ Show 20 Lines • Show All 255 Lines • Show Last 20 Lines

test/Analysis/DependenceAnalysis/AA.ll

Show First 20 Lines • Show All 83 Lines • ▼ Show 20 Lines
; CHECK: da analyze - none! ; CHECK: da analyze - none!
define void @test_tbaa_diff(i32* %A, i16* %B) { define void @test_tbaa_diff(i32* %A, i16* %B) {
store i32 1, i32* %A, !tbaa !5 store i32 1, i32* %A, !tbaa !5
store i16 2, i16* %B, !tbaa !9 store i16 2, i16* %B, !tbaa !9
ret void ret void
} }
; CHECK-LABEL: tbaa_loop ; CHECK-LABEL: tbaa_loop
; CHECK: da analyze - input ; CHECK: da analyze - none!
; CHECK: da analyze - none ; CHECK: da analyze - none!
; CHECK: da analyze - output ; CHECK: da analyze - none!
define void @tbaa_loop(i32 %I, i32 %J, i32* nocapture %A, i16* nocapture readonly %B) { define void @tbaa_loop(i32 %I, i32 %J, i32* nocapture %A, i16* nocapture readonly %B) {
entry: entry:
%cmp = icmp ne i32 %J, 0 %cmp = icmp ne i32 %J, 0
%cmp122 = icmp ne i32 %I, 0 %cmp122 = icmp ne i32 %I, 0
%or.cond = and i1 %cmp, %cmp122 %or.cond = and i1 %cmp, %cmp122
br i1 %or.cond, label %for.outer.preheader, label %for.end br i1 %or.cond, label %for.outer.preheader, label %for.end
for.outer.preheader: for.outer.preheader:
Show All 38 Lines

test/Analysis/DependenceAnalysis/Banerjee.ll

Show First 20 Lines • Show All 69 Lines • ▼ Show 20 Lines
;; *B++ = A[10*i + j - 1]; ;; *B++ = A[10*i + j - 1];
define void @banerjee1(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp { define void @banerjee1(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
entry: entry:
%cmp4 = icmp sgt i64 %n, 0 %cmp4 = icmp sgt i64 %n, 0
br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end9 br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end9
; CHECK: 'Dependence Analysis' for function 'banerjee1': ; CHECK: 'Dependence Analysis' for function 'banerjee1':
; CHECK: da analyze - output [* *]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [* <>]! ; CHECK: da analyze - flow [* <>]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [* *]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - output [* *]! ; CHECK: da analyze - none!
; DELIN: 'Dependence Analysis' for function 'banerjee1': ; DELIN: 'Dependence Analysis' for function 'banerjee1':
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - flow [* <>]! ; DELIN: da analyze - flow [* <>]!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
for.cond1.preheader.preheader: ; preds = %entry for.cond1.preheader.preheader: ; preds = %entry
%0 = add i64 %n, 1 %0 = add i64 %n, 1
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc7 for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc7
%B.addr.06 = phi i64* [ %B.addr.1.lcssa, %for.inc7 ], [ %B, %for.cond1.preheader.preheader ] %B.addr.06 = phi i64* [ %B.addr.1.lcssa, %for.inc7 ], [ %B, %for.cond1.preheader.preheader ]
%i.05 = phi i64 [ %inc8, %for.inc7 ], [ 1, %for.cond1.preheader.preheader ] %i.05 = phi i64 [ %inc8, %for.inc7 ], [ 1, %for.cond1.preheader.preheader ]
▲ Show 20 Lines • Show All 458 Lines • ▼ Show 20 Lines
;; A[30*i + 500*j] = 0; ;; A[30*i + 500*j] = 0;
;; *B++ = A[i - 500*j + 11]; ;; *B++ = A[i - 500*j + 11];
define void @banerjee9(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp { define void @banerjee9(i64* %A, i64* %B, i64 %m, i64 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK: 'Dependence Analysis' for function 'banerjee9': ; CHECK: 'Dependence Analysis' for function 'banerjee9':
; CHECK: da analyze - output [* *]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [<= =|<]! ; CHECK: da analyze - flow [<= =|<]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
; DELIN: 'Dependence Analysis' for function 'banerjee9': ; DELIN: 'Dependence Analysis' for function 'banerjee9':
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - flow [<= =|<]! ; DELIN: da analyze - flow [<= =|<]!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc8 for.cond1.preheader: ; preds = %entry, %for.inc8
%B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ] %B.addr.04 = phi i64* [ %B, %entry ], [ %scevgep, %for.inc8 ]
▲ Show 20 Lines • Show All 208 Lines • Show Last 20 Lines

test/Analysis/DependenceAnalysis/GCD.ll

Show All 9 Lines
;; A[2*i - 4*j] = i; ;; A[2*i - 4*j] = i;
;; *B++ = A[6*i + 8*j]; ;; *B++ = A[6*i + 8*j];
define void @gcd0(i32* %A, i32* %B) nounwind uwtable ssp { define void @gcd0(i32* %A, i32* %B) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; DELIN-LABEL: gcd0 ; DELIN-LABEL: gcd0
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - flow [=> *|<]! ; DELIN: da analyze - flow [=> *|<]!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc8 for.cond1.preheader: ; preds = %entry, %for.inc8
%B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc8 ] %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc8 ]
%i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ] %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
br label %for.body3 br label %for.body3
Show All 33 Lines
;; A[2*i - 4*j] = i; ;; A[2*i - 4*j] = i;
;; *B++ = A[6*i + 8*j + 1]; ;; *B++ = A[6*i + 8*j + 1];
define void @gcd1(i32* %A, i32* %B) nounwind uwtable ssp { define void @gcd1(i32* %A, i32* %B) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; DELIN-LABEL: gcd1 ; DELIN-LABEL: gcd1
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc9 for.cond1.preheader: ; preds = %entry, %for.inc9
%B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ] %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ]
%i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ] %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ]
br label %for.body3 br label %for.body3
Show All 34 Lines
;; A[2*i - 4*j + 1] = i; ;; A[2*i - 4*j + 1] = i;
;; *B++ = A[6*i + 8*j]; ;; *B++ = A[6*i + 8*j];
define void @gcd2(i32* %A, i32* %B) nounwind uwtable ssp { define void @gcd2(i32* %A, i32* %B) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; DELIN-LABEL: gcd2 ; DELIN-LABEL: gcd2
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc9 for.cond1.preheader: ; preds = %entry, %for.inc9
%B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ] %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ]
%i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ] %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ]
br label %for.body3 br label %for.body3
Show All 34 Lines
;; A[i + 2*j] = i; ;; A[i + 2*j] = i;
;; *B++ = A[i + 2*j - 1]; ;; *B++ = A[i + 2*j - 1];
define void @gcd3(i32* %A, i32* %B) nounwind uwtable ssp { define void @gcd3(i32* %A, i32* %B) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; DELIN-LABEL: gcd3 ; DELIN-LABEL: gcd3
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - flow [<> *]! ; DELIN: da analyze - flow [<> *]!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc7 for.cond1.preheader: ; preds = %entry, %for.inc7
%B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc7 ] %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc7 ]
%i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ] %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
br label %for.body3 br label %for.body3
▲ Show 20 Lines • Show All 162 Lines • ▼ Show 20 Linesentry:
br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end12 br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end12
; DELIN-LABEL: gcd6 ; DELIN-LABEL: gcd6
; DELIN: da analyze - none! ; DELIN: da analyze - none!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
for.cond1.preheader.preheader: ; preds = %entry for.cond1.preheader.preheader: ; preds = %entry
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc10 for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc10
%i.06 = phi i64 [ %inc11, %for.inc10 ], [ 0, %for.cond1.preheader.preheader ] %i.06 = phi i64 [ %inc11, %for.inc10 ], [ 0, %for.cond1.preheader.preheader ]
%B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc10 ], [ %B, %for.cond1.preheader.preheader ] %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc10 ], [ %B, %for.cond1.preheader.preheader ]
%cmp21 = icmp sgt i64 %n, 0 %cmp21 = icmp sgt i64 %n, 0
▲ Show 20 Lines • Show All 50 Lines • ▼ Show 20 Lines
define void @gcd7(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp { define void @gcd7(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
entry: entry:
%0 = zext i32 %n to i64 %0 = zext i32 %n to i64
%cmp4 = icmp sgt i32 %n, 0 %cmp4 = icmp sgt i32 %n, 0
br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15 br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15
; DELIN-LABEL: gcd7 ; DELIN-LABEL: gcd7
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - flow [* *|<]! ; DELIN: da analyze - flow [* *|<]!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
for.cond1.preheader.preheader: ; preds = %entry for.cond1.preheader.preheader: ; preds = %entry
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc13 for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc13
%indvars.iv8 = phi i64 [ 0, %for.cond1.preheader.preheader ], [ %indvars.iv.next9, %for.inc13 ] %indvars.iv8 = phi i64 [ 0, %for.cond1.preheader.preheader ], [ %indvars.iv.next9, %for.inc13 ]
%B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ] %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
%1 = add i32 %n, -1 %1 = add i32 %n, -1
▲ Show 20 Lines • Show All 62 Lines • ▼ Show 20 Lines
;; *B++ = A[n*8*i + 6*j + 1]; ;; *B++ = A[n*8*i + 6*j + 1];
define void @gcd8(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp { define void @gcd8(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
entry: entry:
%cmp4 = icmp sgt i32 %n, 0 %cmp4 = icmp sgt i32 %n, 0
br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15 br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15
; DELIN-LABEL: gcd8 ; DELIN-LABEL: gcd8
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - flow [* *|<]! ; DELIN: da analyze - flow [* *|<]!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
for.cond1.preheader.preheader: ; preds = %entry for.cond1.preheader.preheader: ; preds = %entry
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc13 for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc13
%i.06 = phi i32 [ %inc14, %for.inc13 ], [ 0, %for.cond1.preheader.preheader ] %i.06 = phi i32 [ %inc14, %for.inc13 ], [ 0, %for.cond1.preheader.preheader ]
%B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ] %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
%0 = add i32 %n, -1 %0 = add i32 %n, -1
▲ Show 20 Lines • Show All 57 Lines • ▼ Show 20 Lines
define void @gcd9(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp { define void @gcd9(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
entry: entry:
%0 = zext i32 %n to i64 %0 = zext i32 %n to i64
%cmp4 = icmp eq i32 %n, 0 %cmp4 = icmp eq i32 %n, 0
br i1 %cmp4, label %for.end15, label %for.cond1.preheader.preheader br i1 %cmp4, label %for.end15, label %for.cond1.preheader.preheader
; DELIN-LABEL: gcd9 ; DELIN-LABEL: gcd9
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - flow [* *|<]! ; DELIN: da analyze - flow [* *|<]!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - confused! ; DELIN: da analyze - confused!
; DELIN: da analyze - output [* *]! ; DELIN: da analyze - none!
for.cond1.preheader.preheader: ; preds = %entry for.cond1.preheader.preheader: ; preds = %entry
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc13 for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc13
%indvars.iv8 = phi i64 [ 0, %for.cond1.preheader.preheader ], [ %indvars.iv.next9, %for.inc13 ] %indvars.iv8 = phi i64 [ 0, %for.cond1.preheader.preheader ], [ %indvars.iv.next9, %for.inc13 ]
%B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ] %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
%1 = add i32 %n, -1 %1 = add i32 %n, -1
▲ Show 20 Lines • Show All 57 Lines • Show Last 20 Lines

test/Analysis/DependenceAnalysis/Invariant.ll

; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s ; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s
; Test for a bug, which caused an assert when an invalid ; Test for a bug, which caused an assert when an invalid
; SCEVAddRecExpr is created in addToCoefficient. ; SCEVAddRecExpr is created in addToCoefficient.
; CHECK-LABEL: foo ; CHECK-LABEL: foo
; CHECK: da analyze - consistent input [S 0]! ; CHECK: da analyze - none!
; CHECK: da analyze - input [* *|<]! ; CHECK: da analyze - input [* *|<]!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
define float @foo(float %g, [40 x float]* %rr) nounwind { define float @foo(float %g, [40 x float]* %rr) nounwind {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond1.preheader: for.cond1.preheader:
Show All 26 Lines

test/Analysis/DependenceAnalysis/NonCanonicalizedSubscript.ll

Show First 20 Lines • Show All 48 Lines • ▼ Show 20 Lines
@a = global [10004 x [10004 x i32]] zeroinitializer, align 16 @a = global [10004 x [10004 x i32]] zeroinitializer, align 16
; Function Attrs: nounwind uwtable ; Function Attrs: nounwind uwtable
define void @coupled_miv_type_mismatch(i32 %n) #0 { define void @coupled_miv_type_mismatch(i32 %n) #0 {
; DELIN-LABEL: 'Dependence Analysis' for function 'coupled_miv_type_mismatch' ; DELIN-LABEL: 'Dependence Analysis' for function 'coupled_miv_type_mismatch'
entry: entry:
br label %for.cond br label %for.cond
; DELIN: da analyze - input [* *]! ; DELIN: da analyze - none!
; DELIN: da analyze - anti [* *|<]! ; DELIN: da analyze - anti [* *|<]!
; DELIN: da analyze - none! ; DELIN: da analyze - none!
for.cond: ; preds = %for.inc11, %entry for.cond: ; preds = %for.inc11, %entry
%indvars.iv11 = phi i64 [ %indvars.iv.next12, %for.inc11 ], [ 1, %entry ] %indvars.iv11 = phi i64 [ %indvars.iv.next12, %for.inc11 ], [ 1, %entry ]
%exitcond14 = icmp ne i64 %indvars.iv11, 10000 %exitcond14 = icmp ne i64 %indvars.iv11, 10000
br i1 %exitcond14, label %for.cond1.preheader, label %for.end13 br i1 %exitcond14, label %for.cond1.preheader, label %for.end13
for.cond1.preheader: ; preds = %for.cond for.cond1.preheader: ; preds = %for.cond
Show All 36 Lines

test/Analysis/DependenceAnalysis/PR21585.ll

Show All 14 Linesfor.body:
%exitcond = icmp ne i64 %i.inc.ext, 100 %exitcond = icmp ne i64 %i.inc.ext, 100
br i1 %exitcond, label %for.body, label %for.end br i1 %exitcond, label %for.body, label %for.end
for.end: for.end:
ret void ret void
} }
; CHECK: none ; CHECK: none
; CHECK: anti ; CHECK: anti
; CHECK: output ; CHECK: da analyze - consistent output [S]!
; Test for a bug, which caused an assert in ScalarEvolution because ; Test for a bug, which caused an assert in ScalarEvolution because
; the Dependence Analyzer attempted to zero extend a type to a smaller ; the Dependence Analyzer attempted to zero extend a type to a smaller
; type. ; type.
; void t(unsigned int *a, unsigned int n) { ; void t(unsigned int *a, unsigned int n) {
; for (unsigned int i = 0; i != n; i++) { ; for (unsigned int i = 0; i != n; i++) {
Show All 15 Linesfor.body:
store i32 %0, i32* %arrayidx, align 4 store i32 %0, i32* %arrayidx, align 4
%inc = add i32 %i.02, 1 %inc = add i32 %i.02, 1
%cmp = icmp eq i32 %inc, %n %cmp = icmp eq i32 %inc, %n
br i1 %cmp, label %for.end, label %for.body br i1 %cmp, label %for.end, label %for.body
for.end: for.end:
ret void ret void
} }
; CHECK: input ; CHECK: da analyze - consistent input [S]!
; CHECK: none
; CHECK: none ; CHECK: none
; CHECK: output
define void @i16_wrap(i64* %a) { define void @i16_wrap(i64* %a) {
entry: entry:
br label %for.body br label %for.body
for.body: for.body:
%i = phi i64 [0, %entry], [%i.inc, %for.inc] %i = phi i64 [0, %entry], [%i.inc, %for.inc]
%i.tr = trunc i64 %i to i16 %i.tr = trunc i64 %i to i16
%idx = getelementptr i64, i64* %a, i16 %i.tr %idx = getelementptr i64, i64* %a, i16 %i.tr
%0 = load i64, i64* %idx %0 = load i64, i64* %idx
%1 = add i64 %0, 1 %1 = add i64 %0, 1
store i64 %1, i64* %idx store i64 %1, i64* %idx
br label %for.inc br label %for.inc
for.inc: for.inc:
%i.inc = add nuw i64 %i, 1 %i.inc = add nuw i64 %i, 1
%cmp = icmp ult i64 %i.inc, 17179869184 %cmp = icmp ult i64 %i.inc, 17179869184
br i1 %cmp, label %for.body, label %for.end br i1 %cmp, label %for.body, label %for.end
for.end: for.end:
ret void ret void
} }
; CHECK: input ; CHECK: none
; CHECK: anti ; CHECK: anti
; CHECK: output ; CHECK: none
define void @i8_stride_wrap(i32* noalias %a, i32* noalias %b) { define void @i8_stride_wrap(i32* noalias %a, i32* noalias %b) {
entry: entry:
br label %for.body br label %for.body
for.body: for.body:
%i = phi i32 [1,%entry], [%i.inc, %for.inc] %i = phi i32 [1,%entry], [%i.inc, %for.inc]
%i.tr = trunc i32 %i to i8 %i.tr = trunc i32 %i to i8
%idx = getelementptr i32, i32* %a, i8 %i.tr %idx = getelementptr i32, i32* %a, i8 %i.tr
%idx.2 = getelementptr i32, i32* %b, i32 %i %idx.2 = getelementptr i32, i32* %b, i32 %i
%0 = load i32, i32* %idx, align 4 %0 = load i32, i32* %idx, align 4
%1 = add i32 %0, 1 %1 = add i32 %0, 1
store i32 %1, i32* %idx.2, align 4 store i32 %1, i32* %idx.2, align 4
br label %for.inc br label %for.inc
for.inc: for.inc:
%i.inc = add nsw i32 %i, 256 %i.inc = add nsw i32 %i, 256
%exitcond = icmp ult i32 %i, 65536 %exitcond = icmp ult i32 %i, 65536
br i1 %exitcond, label %for.body, label %for.end br i1 %exitcond, label %for.body, label %for.end
for.end: for.end:
ret void ret void
} }
; CHECK: input ; CHECK: da analyze - consistent input [S]!
; CHECK: none ; CHECK: none
; CHECK: none ; CHECK: none

test/Analysis/DependenceAnalysis/Preliminary.ll

Show First 20 Lines • Show All 51 Lines • ▼ Show 20 Lines
;; *B++ = A[i + 3][j + 2][k + 1]; ;; *B++ = A[i + 3][j + 2][k + 1];
define void @p2(i64 %n, [100 x [100 x i64]]* %A, i64* %B) nounwind uwtable ssp { define void @p2(i64 %n, [100 x [100 x i64]]* %A, i64* %B) nounwind uwtable ssp {
entry: entry:
%cmp10 = icmp sgt i64 %n, 0 %cmp10 = icmp sgt i64 %n, 0
br i1 %cmp10, label %for.cond1.preheader.preheader, label %for.end26 br i1 %cmp10, label %for.cond1.preheader.preheader, label %for.end26
; CHECK-LABEL: p2 ; CHECK-LABEL: p2
; CHECK: da analyze - output [* * *]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [* *|<]! ; CHECK: da analyze - flow [* *|<]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [* * *]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - output [* * *]! ; CHECK: da analyze - none!
for.cond1.preheader.preheader: ; preds = %entry for.cond1.preheader.preheader: ; preds = %entry
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc24 for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc24
%B.addr.012 = phi i64* [ %B.addr.1.lcssa, %for.inc24 ], [ %B, %for.cond1.preheader.preheader ] %B.addr.012 = phi i64* [ %B.addr.1.lcssa, %for.inc24 ], [ %B, %for.cond1.preheader.preheader ]
%i.011 = phi i64 [ %inc25, %for.inc24 ], [ 0, %for.cond1.preheader.preheader ] %i.011 = phi i64 [ %inc25, %for.inc24 ], [ 0, %for.cond1.preheader.preheader ]
%cmp26 = icmp sgt i64 %n, 0 %cmp26 = icmp sgt i64 %n, 0
▲ Show 20 Lines • Show All 351 Lines • ▼ Show 20 Lines
;; *B++ = A[i]; ;; *B++ = A[i];
define void @p4(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp { define void @p4(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
entry: entry:
%cmp1 = icmp sgt i64 %n, 0 %cmp1 = icmp sgt i64 %n, 0
br i1 %cmp1, label %for.body.preheader, label %for.end br i1 %cmp1, label %for.body.preheader, label %for.end
; CHECK-LABEL: p4 ; CHECK-LABEL: p4
; CHECK: da analyze - output [*]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [*|<]! ; CHECK: da analyze - flow [*|<]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [*]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.body.preheader: ; preds = %entry for.body.preheader: ; preds = %entry
br label %for.body br label %for.body
for.body: ; preds = %for.body.preheader, %for.body for.body: ; preds = %for.body.preheader, %for.body
%i.03 = phi i8 [ %inc, %for.body ], [ 0, %for.body.preheader ] %i.03 = phi i8 [ %inc, %for.body ], [ 0, %for.body.preheader ]
Show All 27 Lines
;; *B++ = A[i]; ;; *B++ = A[i];
define void @p5(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp { define void @p5(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
entry: entry:
%cmp1 = icmp sgt i64 %n, 0 %cmp1 = icmp sgt i64 %n, 0
br i1 %cmp1, label %for.body.preheader, label %for.end br i1 %cmp1, label %for.body.preheader, label %for.end
; CHECK-LABEL: p5 ; CHECK-LABEL: p5
; CHECK: da analyze - output [*]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [*|<]! ; CHECK: da analyze - flow [*|<]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [*]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.body.preheader: ; preds = %entry for.body.preheader: ; preds = %entry
br label %for.body br label %for.body
for.body: ; preds = %for.body.preheader, %for.body for.body: ; preds = %for.body.preheader, %for.body
%i.03 = phi i16 [ %inc, %for.body ], [ 0, %for.body.preheader ] %i.03 = phi i16 [ %inc, %for.body ], [ 0, %for.body.preheader ]
▲ Show 20 Lines • Show All 220 Lines • Show Last 20 Lines

test/Analysis/DependenceAnalysis/Propagating.ll

Show First 20 Lines • Show All 60 Lines • ▼ Show 20 Lines
;; A[j - i][i + 1][j + k] = i; ;; A[j - i][i + 1][j + k] = i;
;; *B++ = A[j - i][i][j + k]; ;; *B++ = A[j - i][i][j + k];
define void @prop1([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp { define void @prop1([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK-LABEL: prop1 ; CHECK-LABEL: prop1
; CHECK: da analyze - output [* * *]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [<> <> *]! ; CHECK: da analyze - flow [<> <> *]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [* * *]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc18 for.cond1.preheader: ; preds = %entry, %for.inc18
%B.addr.06 = phi i32* [ %B, %entry ], [ %scevgep7, %for.inc18 ] %B.addr.06 = phi i32* [ %B, %entry ], [ %scevgep7, %for.inc18 ]
%i.05 = phi i64 [ 0, %entry ], [ %inc19, %for.inc18 ] %i.05 = phi i64 [ 0, %entry ], [ %inc19, %for.inc18 ]
br label %for.cond4.preheader br label %for.cond4.preheader
▲ Show 20 Lines • Show All 94 Lines • ▼ Show 20 Lines
;; A[i][2*j + i] = i; ;; A[i][2*j + i] = i;
;; *B++ = A[i][2*j - i + 5]; ;; *B++ = A[i][2*j - i + 5];
define void @prop3([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp { define void @prop3([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK-LABEL: prop3 ; CHECK-LABEL: prop3
; CHECK: da analyze - output [* *]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [<> *]! ; CHECK: da analyze - flow [<> *]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [* *]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc9 for.cond1.preheader: ; preds = %entry, %for.inc9
%B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ] %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ]
%i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ] %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ]
br label %for.body3 br label %for.body3
▲ Show 20 Lines • Show All 249 Lines • ▼ Show 20 Lines
;; A[4][j + 2] = i; ;; A[4][j + 2] = i;
;; *B++ = A[-2*i + 4][5*i + j]; ;; *B++ = A[-2*i + 4][5*i + j];
define void @prop8([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp { define void @prop8([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK-LABEL: prop8 ; CHECK-LABEL: prop8
; CHECK: da analyze - consistent output [S 0]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [=> <]! ; CHECK: da analyze - flow [=> <]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc10 for.cond1.preheader: ; preds = %entry, %for.inc10
%B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc10 ] %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc10 ]
Show All 38 Lines
define void @prop9([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp { define void @prop9([100 x i32]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK-LABEL: prop9 ; CHECK-LABEL: prop9
; CHECK: da analyze - none! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [<= <]! ; CHECK: da analyze - flow [<= <]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - consistent input [S 0]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc10 for.cond1.preheader: ; preds = %entry, %for.inc10
%B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc10 ] %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc10 ]
%i.03 = phi i64 [ 0, %entry ], [ %inc11, %for.inc10 ] %i.03 = phi i64 [ 0, %entry ], [ %inc11, %for.inc10 ]
br label %for.body3 br label %for.body3
Show All 28 Lines

test/Analysis/DependenceAnalysis/Separability.ll

Show All 13 Lines
define void @sep0([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp { define void @sep0([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK: da analyze - output [= * * S]! ; CHECK: da analyze - output [= * * S]!
; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - flow [* * * *|<]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [* * S *]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc22 for.cond1.preheader: ; preds = %entry, %for.inc22
%B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc22 ] %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc22 ]
%i.07 = phi i64 [ 0, %entry ], [ %inc23, %for.inc22 ] %i.07 = phi i64 [ 0, %entry ], [ %inc23, %for.inc22 ]
br label %for.cond4.preheader br label %for.cond4.preheader
▲ Show 20 Lines • Show All 58 Lines • ▼ Show 20 Lines
define void @sep1([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp { define void @sep1([100 x [100 x i32]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK: da analyze - output [= * * S]! ; CHECK: da analyze - output [= * * S]!
; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - flow [* * * *|<]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [* * S *]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc22 for.cond1.preheader: ; preds = %entry, %for.inc22
%B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc22 ] %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc22 ]
%i.07 = phi i64 [ 0, %entry ], [ %inc23, %for.inc22 ] %i.07 = phi i64 [ 0, %entry ], [ %inc23, %for.inc22 ]
br label %for.cond4.preheader br label %for.cond4.preheader
▲ Show 20 Lines • Show All 54 Lines • ▼ Show 20 Lines
;; for (long int l = 0; l < 50; l++) { ;; for (long int l = 0; l < 50; l++) {
;; A[i][i][i + k][l] = i; ;; A[i][i][i + k][l] = i;
;; *B++ = A[10][i + 10][j + k][l + 10]; ;; *B++ = A[10][i + 10][j + k][l + 10];
define void @sep2([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp { define void @sep2([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK: da analyze - output [= S = =]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [* * * <>]! ; CHECK: da analyze - flow [* * * <>]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [= * * *]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc26 for.cond1.preheader: ; preds = %entry, %for.inc26
%B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc26 ] %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc26 ]
%i.07 = phi i64 [ 0, %entry ], [ %inc27, %for.inc26 ] %i.07 = phi i64 [ 0, %entry ], [ %inc27, %for.inc26 ]
br label %for.cond4.preheader br label %for.cond4.preheader
▲ Show 20 Lines • Show All 54 Lines • ▼ Show 20 Lines
;; for (long int l = 0; l < 50; l++) { ;; for (long int l = 0; l < 50; l++) {
;; A[i][i][i + k][l + k] = i; ;; A[i][i][i + k][l + k] = i;
;; *B++ = A[10][i + 10][j + k][l + 10]; ;; *B++ = A[10][i + 10][j + k][l + 10];
define void @sep3([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp { define void @sep3([100 x [100 x [100 x i32]]]* %A, i32* %B, i32 %n) nounwind uwtable ssp {
entry: entry:
br label %for.cond1.preheader br label %for.cond1.preheader
; CHECK: da analyze - output [= S = =]! ; CHECK: da analyze - none!
; CHECK: da analyze - flow [* * * *|<]! ; CHECK: da analyze - flow [* * * *|<]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - input [= * * *]! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.cond1.preheader: ; preds = %entry, %for.inc27 for.cond1.preheader: ; preds = %entry, %for.inc27
%B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc27 ] %B.addr.08 = phi i32* [ %B, %entry ], [ %scevgep11, %for.inc27 ]
%i.07 = phi i64 [ 0, %entry ], [ %inc28, %for.inc27 ] %i.07 = phi i64 [ 0, %entry ], [ %inc28, %for.inc27 ]
br label %for.cond4.preheader br label %for.cond4.preheader
▲ Show 20 Lines • Show All 50 Lines • Show Last 20 Lines

test/Analysis/DependenceAnalysis/Symbolic.ll

  • This file was added.
; 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
}

test/Analysis/DependenceAnalysis/SymbolicRDIV.ll

Show First 20 Lines • Show All 386 Lines • ▼ Show 20 Lines
;; *B++ = A[2*n2]; ;; *B++ = A[2*n2];
define void @symbolicrdiv6(i32* %A, i32* %B, i64 %n1, i64 %n2) nounwind uwtable ssp { define void @symbolicrdiv6(i32* %A, i32* %B, i64 %n1, i64 %n2) nounwind uwtable ssp {
entry: entry:
%cmp4 = icmp eq i64 %n1, 0 %cmp4 = icmp eq i64 %n1, 0
br i1 %cmp4, label %for.end7, label %for.cond1.preheader.preheader br i1 %cmp4, label %for.end7, label %for.cond1.preheader.preheader
; CHECK: 'Dependence Analysis' for function 'symbolicrdiv6' ; CHECK: 'Dependence Analysis' for function 'symbolicrdiv6'
; CHECK: da analyze - output [* *]! ; CHECK: da analyze - none!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - consistent input [S S]! ; CHECK: da analyze - consistent input [S S]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - output [* *]! ; CHECK: da analyze - none!
for.cond1.preheader.preheader: ; preds = %entry for.cond1.preheader.preheader: ; preds = %entry
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc5 for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc5
%B.addr.06 = phi i32* [ %B.addr.1.lcssa, %for.inc5 ], [ %B, %for.cond1.preheader.preheader ] %B.addr.06 = phi i32* [ %B.addr.1.lcssa, %for.inc5 ], [ %B, %for.cond1.preheader.preheader ]
%i.05 = phi i64 [ %inc6, %for.inc5 ], [ 0, %for.cond1.preheader.preheader ] %i.05 = phi i64 [ %inc6, %for.inc5 ], [ 0, %for.cond1.preheader.preheader ]
%cmp21 = icmp eq i64 %n2, 0 %cmp21 = icmp eq i64 %n2, 0
Show All 38 Lines

test/Analysis/DependenceAnalysis/WeakZeroSrcSIV.ll

Show First 20 Lines • Show All 44 Lines • ▼ Show 20 Lines
;; A[10] = i; ;; A[10] = i;
;; *B++ = A[n*i + 10]; ;; *B++ = A[n*i + 10];
define void @weakzerosrc1(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp { define void @weakzerosrc1(i32* %A, i32* %B, i64 %n) nounwind uwtable ssp {
entry: entry:
%cmp1 = icmp eq i64 %n, 0 %cmp1 = icmp eq i64 %n, 0
br i1 %cmp1, label %for.end, label %for.body.preheader 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 - flow [p<=|<]!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
; CHECK: da analyze - confused! ; CHECK: da analyze - confused!
; CHECK: da analyze - none! ; CHECK: da analyze - none!
for.body.preheader: ; preds = %entry for.body.preheader: ; preds = %entry
br label %for.body br label %for.body
▲ Show 20 Lines • Show All 205 Lines • Show Last 20 Lines

test/Transforms/LoopInterchange/currentLimitation.ll

Show All 10 Lines
;;--------------------------------------Test case 01------------------------------------ ;;--------------------------------------Test case 01------------------------------------
;; [FIXME] This loop though valid is currently not interchanged due to the limitation that we cannot split the inner loop latch due to multiple use of inner induction ;; [FIXME] This loop though valid is currently not interchanged due to the limitation that we cannot split the inner loop latch due to multiple use of inner induction
;; variable.(used to increment the loop counter and to access A[j+1][i+1] ;; variable.(used to increment the loop counter and to access A[j+1][i+1]
;; for(int i=0;i<N-1;i++) ;; for(int i=0;i<N-1;i++)
;; for(int j=1;j<N-1;j++) ;; for(int j=1;j<N-1;j++)
;; A[j+1][i+1] = A[j+1][i+1] + k; ;; A[j+1][i+1] = A[j+1][i+1] + k;
; FIXME: Currently fails because of DA changes.
; IR-LABEL: @interchange_01 ; IR-LABEL: @interchange_01
; IR-NOT: split ; IR-NOT: split
; CHECK: Name: Dependence ; CHECK: Name: UnsupportedInsBetweenInduction
; CHECK-NEXT: Function: interchange_01 ; CHECK-NEXT: Function: interchange_01
define void @interchange_01(i32 %k, i32 %N) { define void @interchange_01(i32 %k, i32 %N) {
entry: entry:
%sub = add nsw i32 %N, -1 %sub = add nsw i32 %N, -1
%cmp26 = icmp sgt i32 %N, 1 %cmp26 = icmp sgt i32 %N, 1
br i1 %cmp26, label %for.cond1.preheader.lr.ph, label %for.end17 br i1 %cmp26, label %for.cond1.preheader.lr.ph, label %for.end17
for.cond1.preheader.lr.ph: for.cond1.preheader.lr.ph:
%cmp324 = icmp sgt i32 %sub, 1 %cmp324 = icmp sgt i32 %sub, 1
%0 = add i32 %N, -2 %0 = add i32 %N, -2
%1 = sext i32 %sub to i64 %1 = sext i32 %sub to i64
br label %for.cond1.preheader br label %for.cond1.preheader
for.cond.loopexit: for.cond.loopexit:
%cmp = icmp slt i64 %indvars.iv.next29, %1 %cmp = icmp slt i64 %indvars.iv.next29, %1
br i1 %cmp, label %for.cond1.preheader, label %for.end17 br i1 %cmp, label %for.cond1.preheader, label %for.end17
for.cond1.preheader: for.cond1.preheader:
%indvars.iv28 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next29, %for.cond.loopexit ] %indvars.iv28 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next29, %for.cond.loopexit ]
%indvars.iv.next29 = add nuw nsw i64 %indvars.iv28, 1 %indvars.iv.next29 = add nuw nsw i64 %indvars.iv28, 1
br i1 %cmp324, label %for.body4, label %for.cond.loopexit br i1 %cmp324, label %for.body4, label %for.cond.loopexit
for.body4: for.body4:
%indvars.iv = phi i64 [ %indvars.iv.next, %for.body4 ], [ 1, %for.cond1.preheader ] %indvars.iv = phi i64 [ %indvars.iv.next, %for.body4 ], [ 1, %for.cond1.preheader ]
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%arrayidx7 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv.next, i64 %indvars.iv.next29 %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv.next, i64 %indvars.iv.next29
%2 = load i32, i32* %arrayidx7 %2 = load i32, i32* %arrayidx7
%add8 = add nsw i32 %2, %k %add8 = add nsw i32 %2, %k
store i32 %add8, i32* %arrayidx7 store i32 %add8, i32* %arrayidx7
%lftr.wideiv = trunc i64 %indvars.iv to i32 %lftr.wideiv = trunc i64 %indvars.iv to i32
%exitcond = icmp eq i32 %lftr.wideiv, %0 %exitcond = icmp eq i32 %lftr.wideiv, %0
br i1 %exitcond, label %for.cond.loopexit, label %for.body4 br i1 %exitcond, label %for.cond.loopexit, label %for.body4
for.end17: for.end17:
ret void ret void
} }
; When currently cannot interchange this loop, because transform currently ; When currently cannot interchange this loop, because transform currently
; expects the latches to be the exiting blocks too. ; expects the latches to be the exiting blocks too.
; IR-LABEL: @interchange_02 ; IR-LABEL: @interchange_02
; IR-NOT: split ; IR-NOT: split
Show All 31 Lines

test/Transforms/LoopInterchange/loop-interchange-optimization-remarks.ll

Show First 20 Lines • Show All 49 Lines • ▼ Show 20 Linesfor.inc17:
br i1 %exitcond38, label %for.end19, label %for.body3.lr.ph br i1 %exitcond38, label %for.end19, label %for.body3.lr.ph
for.end19: for.end19:
ret void ret void
} }
; CHECK: --- !Missed ; CHECK: --- !Missed
; CHECK-NEXT: Pass: loop-interchange ; CHECK-NEXT: Pass: loop-interchange
; CHECK-NEXT: Name: Dependence ; CHECK-NEXT: Name: InterchangeNotProfitable
; CHECK-NEXT: Function: test01 ; CHECK-NEXT: Function: test01
; CHECK-NEXT: Args:
; CHECK-NEXT: - String: Cannot interchange loops due to dependences.
; CHECK-NEXT: ...
;;--------------------------------------Test case 02------------------------------------ ;;--------------------------------------Test case 02------------------------------------
;; [FIXME] This loop though valid is currently not interchanged due to the ;; [FIXME] This loop though valid is currently not interchanged due to the
;; limitation that we cannot split the inner loop latch due to multiple use of inner induction ;; limitation that we cannot split the inner loop latch due to multiple use of inner induction
;; variable.(used to increment the loop counter and to access A[j+1][i+1] ;; variable.(used to increment the loop counter and to access A[j+1][i+1]
;; for(int i=0;i<N-1;i++) ;; for(int i=0;i<N-1;i++)
;; for(int j=1;j<N-1;j++) ;; for(int j=1;j<N-1;j++)
;; A[j+1][i+1] = A[j+1][i+1] + k; ;; A[j+1][i+1] = A[j+1][i+1] + k;
Show All 31 Lines for.body4:
br i1 %exitcond, label %for.cond.loopexit, label %for.body4 br i1 %exitcond, label %for.cond.loopexit, label %for.body4
for.end17: for.end17:
ret void ret void
} }
; CHECK: --- !Missed ; CHECK: --- !Missed
; CHECK-NEXT: Pass: loop-interchange ; CHECK-NEXT: Pass: loop-interchange
; CHECK-NEXT: Name: Dependence ; CHECK-NEXT: Name: UnsupportedInsBetweenInduction
; CHECK-NEXT: Function: test02 ; CHECK-NEXT: Function: test02
; CHECK-NEXT: Args:
; CHECK-NEXT: - String: Cannot interchange loops due to dependences.
; CHECK-NEXT: ...
;;-----------------------------------Test case 03------------------------------- ;;-----------------------------------Test case 03-------------------------------
;; Test to make sure we can handle output dependencies. ;; Test to make sure we can handle output dependencies.
;; ;;
;; for (int i = 0; i < 2; ++i) ;; for (int i = 0; i < 2; ++i)
;; for(int j = 0; j < 3; ++j) { ;; for(int j = 0; j < 3; ++j) {
;; A[j][i] = i; ;; A[j][i] = i;
;; A[j][i+1] = j; ;; A[j][i+1] = j;
▲ Show 20 Lines • Show All 82 Lines • ▼ Show 20 Linesfor.inc15:
br i1 %exitcond36, label %for.end17, label %for.body br i1 %exitcond36, label %for.end17, label %for.body
for.end17: for.end17:
ret void ret void
} }
; CHECK: --- !Missed ; CHECK: --- !Missed
; CHECK-NEXT: Pass: loop-interchange ; CHECK-NEXT: Pass: loop-interchange
; CHECK-NEXT: Name: Dependence ; CHECK-NEXT: Name: NotTightlyNested
; CHECK-NEXT: Function: test04 ; CHECK-NEXT: Function: test04
; CHECK-NEXT: Args:
; CHECK-NEXT: - String: Cannot interchange loops due to dependences.
; CHECK-NEXT: ...