Changeset View
Changeset View
Standalone View
Standalone View
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 | |||||
} |