1; RUN: opt -passes='require<scalar-evolution>,require<aa>,loop(print-access-info)' -disable-output  < %s 2>&1 | FileCheck %s
2
3; This loop:
4;
5;   int **A;
6;   for (i)
7;     for (j) {
8;        A[i][j] = A[i-1][j] * B[j]
9;        B[j+1] = 2       // backward dep between this and the previous
10;     }
11;
12; is transformed by Load-PRE to stash away A[i] for the next iteration of the
13; outer loop:
14;
15;   Curr = A[0];          // Prev_0
16;   for (i: 1..N) {
17;     Prev = Curr;        // Prev = PHI (Prev_0, Curr)
18;     Curr = A[i];
19;     for (j: 0..N) {
20;        Curr[j] = Prev[j] * B[j]
21;        B[j+1] = 2       // backward dep between this and the previous
22;     }
23;   }
24;
25; Since A[i] and A[i-1] are likely to be independent, getUnderlyingObjects
26; should not assume that Curr and Prev share the same underlying object.
27;
28; If it did we would try to dependence-analyze Curr and Prev and the analysis
29; would fail with non-constant distance.
30;
31; To illustrate one of the negative consequences of this, if the loop has a
32; backward dependence we won't detect this but instead fully fall back on
33; memchecks (that is what LAA does after encountering a case of non-constant
34; distance).
35
36target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
37target triple = "x86_64-apple-macosx10.10.0"
38
39; CHECK-LABEL: function 'f'
40; CHECK: for_j.body:
41; CHECK-NEXT: Report: unsafe dependent memory operations in loop
42; CHECK-NEXT: Dependences:
43; CHECK-NEXT: Backward:
44; CHECK-NEXT: %loadB = load i8, i8* %gepB, align 1 ->
45; CHECK-NEXT: store i8 2, i8* %gepB_plus_one, align 1
46
47define void @f(i8** noalias %A, i8* noalias %B, i64 %N) {
48for_i.preheader:
49  %prev_0 = load i8*, i8** %A, align 8
50  br label %for_i.body
51
52for_i.body:
53  %i = phi i64 [1, %for_i.preheader], [%i.1, %for_j.end]
54  %prev = phi i8* [%prev_0, %for_i.preheader], [%curr, %for_j.end]
55  %gep = getelementptr inbounds i8*, i8** %A, i64 %i
56  %curr = load i8*, i8** %gep, align 8
57  br label %for_j.preheader
58
59for_j.preheader:
60  br label %for_j.body
61
62for_j.body:
63  %j = phi i64 [0, %for_j.preheader], [%j.1, %for_j.body]
64
65  %gepPrev = getelementptr inbounds i8, i8* %prev, i64 %j
66  %gepCurr = getelementptr inbounds i8, i8* %curr, i64 %j
67  %gepB = getelementptr inbounds i8, i8* %B, i64 %j
68
69  %loadPrev = load i8, i8* %gepPrev, align 1
70  %loadB = load i8, i8* %gepB, align 1
71
72  %mul = mul i8 %loadPrev, %loadB
73
74  store i8 %mul, i8* %gepCurr, align 1
75
76  %gepB_plus_one = getelementptr inbounds i8, i8* %gepB, i64 1
77  store i8 2, i8* %gepB_plus_one, align 1
78
79  %j.1 = add nuw i64 %j, 1
80  %exitcondj = icmp eq i64 %j.1, %N
81  br i1 %exitcondj, label %for_j.end, label %for_j.body
82
83for_j.end:
84
85  %i.1 = add nuw i64 %i, 1
86  %exitcond = icmp eq i64 %i.1, %N
87  br i1 %exitcond, label %for_i.end, label %for_i.body
88
89for_i.end:
90  ret void
91}
92
93; CHECK-LABEL: function 'f_deep'
94; CHECK: for_j.body:
95; FIXME: This is incorrect and is going to be fixed with D86669.
96; CHECK-NEXT: Memory dependences are safe with run-time checks
97; CHECK-NEXT: Dependences:
98
99define void @f_deep(i8** noalias %A, i8* noalias %B, i64 %N) {
100for_i.preheader:
101  %prev_0 = load i8*, i8** %A, align 8
102  br label %for_i.body
103
104for_i.body:
105  %i = phi i64 [1, %for_i.preheader], [%i.1, %for_j.end]
106  %prev = phi i8* [%prev_0, %for_i.preheader], [%curr, %for_j.end]
107  %gep = getelementptr inbounds i8*, i8** %A, i64 %i
108  %curr = load i8*, i8** %gep, align 8
109  br label %for_j.preheader
110
111for_j.preheader:
112  br label %for_j.body
113
114for_j.body:
115  %j = phi i64 [0, %for_j.preheader], [%j.1, %for_j.body]
116
117  %gepPrev = getelementptr inbounds i8, i8* %prev, i64 %j
118  %gepCurr = getelementptr inbounds i8, i8* %curr, i64 %j
119  %gepB = getelementptr inbounds i8, i8* %B, i64 %j
120  %gepB1 = getelementptr inbounds i8, i8* %gepB, i64 %j
121  %gepB2 = getelementptr inbounds i8, i8* %gepB1, i64 0
122  %gepB3 = getelementptr inbounds i8, i8* %gepB2, i64 0
123  %gepB4 = getelementptr inbounds i8, i8* %gepB3, i64 0
124  %gepB5 = getelementptr inbounds i8, i8* %gepB4, i64 0
125  %gepB6 = getelementptr inbounds i8, i8* %gepB5, i64 0
126  %gepB7 = getelementptr inbounds i8, i8* %gepB6, i64 0
127  %gepB8 = getelementptr inbounds i8, i8* %gepB7, i64 0
128  %gepB9 = getelementptr inbounds i8, i8* %gepB8, i64 0
129
130  %loadPrev = load i8, i8* %gepPrev, align 1
131  %loadB = load i8, i8* %gepB9, align 1
132
133  %mul = mul i8 %loadPrev, %loadB
134
135  store i8 %mul, i8* %gepCurr, align 1
136
137  %gepB_plus_one = getelementptr inbounds i8, i8* %gepB, i64 1
138  store i8 2, i8* %gepB_plus_one, align 1
139
140  %j.1 = add nuw i64 %j, 1
141  %exitcondj = icmp eq i64 %j.1, %N
142  br i1 %exitcondj, label %for_j.end, label %for_j.body
143
144for_j.end:
145
146  %i.1 = add nuw i64 %i, 1
147  %exitcond = icmp eq i64 %i.1, %N
148  br i1 %exitcond, label %for_i.end, label %for_i.body
149
150for_i.end:
151  ret void
152}
153