Page MenuHomePhabricator
Differential D46201 Diff 149977 test/Analysis/DependenceAnalysis/Symbolic.ll

Changeset View

Standalone View

View Options

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 - 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
}