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.
1​; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
2​
3​; void no_deps_interchange(unsigned **Arr) {
4​; for (int i = 0; i < 1024; ++i)
5​; for(int j = 0; j < 1024; ++j)
6​; Arr[j][i] += Arr[j][i] + 10;
7​; }
8​; CHECK-LABEL: 'Dependence Analysis' for function 'test1'
9​; CHECK: da analyze - none!
10​; CHECK: da analyze - confused!
11​; CHECK: da analyze - confused!
12​; CHECK: da analyze - input [* *]!
13​; CHECK: da analyze - anti [* *|<]!
14​; CHECK: da analyze - output [* *]!
15​
16​define void @test1(i64** %Arr) {
17​entry:
18​ br label %for.cond1.preheader
19​
20​for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry
21​ %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.cond.cleanup3 ]
22​ br label %for.body4
23​
24​for.cond.cleanup: ; preds = %for.cond.cleanup3
25​ ret void
26​
27​for.cond.cleanup3: ; preds = %for.body4
28​ %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
29​ %exitcond25 = icmp eq i64 %indvars.iv.next24, 1024
30​ br i1 %exitcond25, label %for.cond.cleanup, label %for.cond1.preheader
31​
32​for.body4: ; preds = %for.body4, %for.cond1.preheader
33​ %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next.3, %for.body4 ]
34​ %arrayidx = getelementptr inbounds i64*, i64** %Arr, i64 %indvars.iv
35​ %0 = load i64*, i64** %arrayidx, align 8
36​ %arrayidx6 = getelementptr inbounds i64, i64* %0, i64 %indvars.iv23
37​ %1 = load i64, i64* %arrayidx6, align 4
38​ %add7 = add i64 %1, 10
39​ store i64 %add7, i64* %arrayidx6
40​ %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
41​ %exitcond.3 = icmp eq i64 %indvars.iv.next.3, 1024
42​ br i1 %exitcond.3, label %for.cond.cleanup3, label %for.body4
43​}
44​
45​; void no_deps_interchange(unsigned **Arr) {
46​; for (int i = 0; i < 1024; ++i)
47​; for(int j = 0; j < 1024; ++j)
48​; Arr[i][j] += Arr[i][j] + 10;
49​; }
50​; CHECK-LABEL: 'Dependence Analysis' for function 'test2'
51​; CHECK: da analyze - consistent input [0 S]!
52​; CHECK: da analyze - confused!
53​; CHECK: da analyze - confused!
54​; CHECK: da analyze - none!
55​; CHECK: da analyze - anti [= =|<]!
56​; CHECK: da analyze - none!
57​
58​define void @test2(i64** %Arr) {
59​entry:
60​ br label %for.cond1.preheader
61​
62​for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry
63​ %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.cond.cleanup3 ]
64​ br label %for.body4
65​
66​for.cond.cleanup: ; preds = %for.cond.cleanup3
67​ ret void
68​
69​for.cond.cleanup3: ; preds = %for.body4
70​ %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
71​ %exitcond25 = icmp eq i64 %indvars.iv.next24, 1024
72​ br i1 %exitcond25, label %for.cond.cleanup, label %for.cond1.preheader
73​
74​for.body4: ; preds = %for.body4, %for.cond1.preheader
75​ %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next.3, %for.body4 ]
76​ %arrayidx = getelementptr inbounds i64*, i64** %Arr, i64 %indvars.iv23
77​ %0 = load i64*, i64** %arrayidx, align 8
78​ %arrayidx6 = getelementptr inbounds i64, i64* %0, i64 %indvars.iv
79​ %1 = load i64, i64* %arrayidx6, align 4
80​ %add7 = add i64 %1, 10
81​ store i64 %add7, i64* %arrayidx6
82​ %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
83​ %exitcond.3 = icmp eq i64 %indvars.iv.next.3, 1024
84​ br i1 %exitcond.3, label %for.cond.cleanup3, label %for.body4
85​}
86​
87​; Array index may be loop invariant (if N is 0), we cannot deduce a EQ
88​; dependence.
89​; void test3(unsigned *Arr, unsigned N) {
90​; for (int i = 0; i < 1024; ++i)
91​; for(int j = 0; j < 1024; ++j)
92​; Arr[(i + j) * N] += Arr[(i + j) * N] + 10;
93​; }
94​;
95​; CHECK-LABEL: 'Dependence Analysis' for function 'test3'
96​; CHECK:da analyze - input [* *]!
97​; CHECK-NEXT: da analyze - anti [* *|<]!
98​; CHECK-NEXT: da analyze - output [* *]!
99​
100​define void @test3(i64* nocapture %Arr, i64 %N) {
101​entry:
102​ br label %for.cond1.preheader
103​
104​for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry
105​ %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ]
106​ br label %for.body4
107​
108​for.cond.cleanup: ; preds = %for.cond.cleanup3
109​ ret void
110​
111​for.cond.cleanup3: ; preds = %for.body4
112​ %inc12 = add nuw nsw i64 %i.025, 1
113​ %exitcond26 = icmp eq i64 %inc12, 1024
114​ br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader
115​
116​for.body4: ; preds = %for.body4, %for.cond1.preheader
117​ %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
118​ %add = add i64 %indvars.iv, %i.025
119​ %idxprom = mul i64 %add, %N
120​ %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
121​ %lv = load i64, i64* %arrayidx, align 4
122​ %add10 = add i64 %lv, 10
123​ store i64 %add10, i64* %arrayidx, align 4
124​ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
125​ %exitcond = icmp eq i64 %indvars.iv.next, 1024
126​ br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
127​}
128​
129​; Array index is guaranteed to not be loop invariant, we can deduce there is a
130​; EQ dependence.
131​; void test4(unsigned *Arr) {
132​; for (int i = 0; i < 1024; ++i)
133​; for(int j = 0; j < 1024; ++j)
134​; Arr[(i + j) * 1024] += Arr[(i + j) * 1024] + 10;
135​; }
136​;
137​; CHECK-LABEL: 'Dependence Analysis' for function 'test4'
138​; CHECK: da analyze - none!
139​; CHECK-NEXT: da analyze - anti [= =|<]!
140​; CHECK-NEXT: da analyze - none!
141​define void @test4(i64* nocapture %Arr) {
142​entry:
143​ br label %for.cond1.preheader
144​
145​for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry
146​ %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ]
147​ br label %for.body4
148​
149​for.cond.cleanup: ; preds = %for.cond.cleanup3
150​ ret void
151​
152​for.cond.cleanup3: ; preds = %for.body4
153​ %inc12 = add nuw nsw i64 %i.025, 1
154​ %exitcond26 = icmp eq i64 %inc12, 1024
155​ br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader
156​
157​for.body4: ; preds = %for.body4, %for.cond1.preheader
158​ %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
159​ %add = add i64 %indvars.iv, %i.025
160​ %idxprom = mul i64 %add, 1024
161​ %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
162​ %lv = load i64, i64* %arrayidx, align 4
163​ %add10 = add i64 %lv, 10
164​ store i64 %add10, i64* %arrayidx, align 4
165​ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
166​ %exitcond = icmp eq i64 %indvars.iv.next, 1024
167​ br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
168​}
169​
170​; Array index is guaranteed to not be loop invariant, we can deduce there is a
171​; EQ dependence.
172​; void test5(unsigned *Arr) {
173​; for (int i = 0; i < 1024; ++i)
174​; for(int j = 0; j < 1024; ++j)
175​; Arr[i * N + j] += Arr[i *N + j] + 10;
176​; }
177​;
178​; CHECK-LABEL: 'Dependence Analysis' for function 'test5'
179​; CHECK: da analyze - none!
180​; CHECK-NEXT: da analyze - anti [= =|<]!
181​; CHECK-NEXT: da analyze - none!
182​
183​define void @test5(i64* nocapture %Arr, i64 %N) {
184​entry:
185​ br label %for.cond1.preheader
186​
187​for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry
188​ %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ]
189​ br label %for.body4
190​
191​for.cond.cleanup: ; preds = %for.cond.cleanup3
192​ ret void
193​
194​for.cond.cleanup3: ; preds = %for.body4
195​ %inc12 = add nuw nsw i64 %i.025, 1
196​ %exitcond26 = icmp eq i64 %inc12, 1024
197​ br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader
198​
199​for.body4: ; preds = %for.body4, %for.cond1.preheader
200​ %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
201​ %mul = mul i64 %i.025, %N
202​ %idxprom = add i64 %indvars.iv, %mul
203​ %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
204​ %lv = load i64, i64* %arrayidx, align 4
205​ %add10 = add i64 %lv, 10
206​ store i64 %add10, i64* %arrayidx, align 4
207​ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
208​ %exitcond = icmp eq i64 %indvars.iv.next, 1024
209​ br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
210​}
211​
212​; Array index may be loop invariant (if N is 0), we cannot deduce there is a
213​; EQ dependence.
214​; void test6(unsigned *Arr, unsigned N) {
215​; for (int i = 0; i < 1024; ++i)
216​; for(int j = 0; j < 1024; ++j)
217​; Arr[i + j * N] += Arr[i + j * N] + 10;
218​; }
219​;
220​;
221​; CHECK-LABEL: 'Dependence Analysis' for function 'test6'
222​; CHECK:da analyze - input [* *]!
223​; CHECK-NEXT: da analyze - anti [* *|<]!
224​; CHECK-NEXT: da analyze - output [* *]!
225​
226​define void @test6(i64* nocapture %Arr, i64 %N) {
227​entry:
228​ br label %for.cond1.preheader
229​
230​for.cond1.preheader: ; preds = %for.cond.cleanup3, %entry
231​ %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.cond.cleanup3 ]
232​ br label %for.body4
233​
234​for.cond.cleanup: ; preds = %for.cond.cleanup3
235​ ret void
236​
237​for.cond.cleanup3: ; preds = %for.body4
238​ %inc12 = add nuw nsw i64 %i.025, 1
239​ %exitcond26 = icmp eq i64 %inc12, 1024
240​ br i1 %exitcond26, label %for.cond.cleanup, label %for.cond1.preheader
241​
242​for.body4: ; preds = %for.body4, %for.cond1.preheader
243​ %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
244​ %mul = mul i64 %indvars.iv, %N
245​ %idxprom = add i64 %mul, %i.025
246​ %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
247​ %lv = load i64, i64* %arrayidx, align 4
248​ %add10 = add i64 %lv, 10
249​ store i64 %add10, i64* %arrayidx, align 4
250​ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
251​ %exitcond = icmp eq i64 %indvars.iv.next, 1024
252​ br i1 %exitcond, label %for.cond.cleanup3, label %for.body4
253​}
254​
255​; Cannot deduce EQ dependence here, because subtracting induction variables
256​; from the same loop might yield a constant.
257​; void test7(unsigned *Arr) {
258​; unsigned j = 0;
259​; for (int i = 0; i < 1024; ++i) {
260​; Arr[1024 + (i - j)] += Arr[1024 + (i - j)] + 10;
261​; j++;
262​; }
263​; }
264​;
265​; CHECK-LABEL: 'Dependence Analysis' for function 'test7'
266​; CHECK: da analyze - consistent input [S]!
267​; CHECK-NEXT: da analyze - consistent anti [S|<]!
268​; CHECK-NEXT: da analyze - consistent output [S]!
269​
270​define void @test7(i64* nocapture %Arr, i64 %N) {
271​entry:
272​ br label %for.body4
273​
274​for.cond.cleanup: ; preds = %for.cond.cleanup3
275​ ret void
276​
277​for.body4: ; preds = %for.body4, %for.cond1.preheader
278​ %indvars.iv = phi i64 [ 0, %entry], [ %indvars.iv.next, %for.body4 ]
279​ %i.025 = phi i64 [ 0, %entry ], [ %inc12, %for.body4 ]
280​ %idxsub = sub i64 %i.025, %indvars.iv
281​ %idxprom = add i64 1024, %idxsub
282​ %arrayidx = getelementptr inbounds i64, i64* %Arr, i64 %idxprom
283​ %lv = load i64, i64* %arrayidx, align 4
284​ %add10 = add i64 %lv, 10
285​ store i64 %add10, i64* %arrayidx, align 4
286​ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
287​ %exitcond = icmp eq i64 %indvars.iv.next, 1024
288​ %inc12 = add nuw nsw i64 %i.025, 1
289​ br i1 %exitcond, label %for.cond.cleanup, label %for.body4
290​}
291​
292​; We can deduce there is EQ dependence between accesses to c.
293​; unsigned a[1024][1024];
294​; unsigned b[1024][1024];
295​; unsigned c[1024][1024];
296​;
297​; void test9(unsigned N) {
298​; for (unsigned j = 0; j < N; j++)
299​; for (unsigned k = 0; k < N; k++)
300​; for (unsigned i = 0; i < N; i++)
301​; c[i][j] = c[i][j] + a[i+1][k];
302​; a[i][k] = a[i+1][k];
303​; b[i][k] = b[j][k-1];
304​; }
305​
306​; CHECK-LABEL: 'Dependence Analysis' for function 'test9'
307​; CHECK: da analyze - none!
308​; CHECK-NEXT: da analyze - none!
309​; CHECK-NEXT: da analyze - none!
310​; CHECK-NEXT: da analyze - anti [= S =|<]!
311​; CHECK-NEXT: da analyze - none!
312​; CHECK-NEXT: da analyze - none!
313​; CHECK-NEXT: da analyze - none!
314​; CHECK-NEXT: da analyze - none!
315​; CHECK-NEXT: da analyze - none!
316​; CHECK-NEXT: da analyze - anti [S * *|<]!
317​; CHECK-NEXT: da analyze - none!
318​; CHECK-NEXT: da analyze - none!
319​; CHECK-NEXT: da analyze - none!
320​; CHECK-NEXT: da analyze - none!
321​; CHECK-NEXT: da analyze - anti [S <> *]!
322​; CHECK-NEXT: da analyze - none!
323​; CHECK-NEXT: da analyze - none!
324​; CHECK-NEXT: da analyze - none!
325​; CHECK-NEXT: da analyze - none!
326​; CHECK-NEXT: da analyze - none!
327​; CHECK-NEXT: da analyze - none!
328​;
329​@a = global [1024 x [1024 x i64]] zeroinitializer, align 16
330​@b = global [1024 x [1024 x i64]] zeroinitializer, align 16
331​@c = global [1024 x [1024 x i64]] zeroinitializer, align 16
332​
333​define dso_local void @test9(i64 %N) local_unnamed_addr {
334​entry:
335​ %cmp49 = icmp sgt i64 %N, 0
336​ br i1 %cmp49, label %for.cond5.preheader.lr.ph, label %for.cond.cleanup
337​
338​for.cond5.preheader.lr.ph: ; preds = %entry, %for.cond.cleanup3
339​ %indvars.iv55 = phi i64 [ %indvars.iv.next56, %for.cond.cleanup3 ], [ 0, %entry ]
340​ br label %for.body8.lr.ph
341​
342​for.cond.cleanup: ; preds = %for.cond.cleanup3, %entry
343​ ret void
344​
345​for.body8.lr.ph: ; preds = %for.cond.cleanup7, %for.cond5.preheader.lr.ph
346​ %indvars.iv51 = phi i64 [ 0, %for.cond5.preheader.lr.ph ], [ %indvars.iv.next52, %for.cond.cleanup7 ]
347​ br label %for.body8
348​
349​for.cond.cleanup3: ; preds = %for.cond.cleanup7
350​ %indvars.iv.next56 = add nuw nsw i64 %indvars.iv55, 1
351​ %exitcond58 = icmp eq i64 %indvars.iv.next56, %N
352​ br i1 %exitcond58, label %for.cond.cleanup, label %for.cond5.preheader.lr.ph
353​
354​for.cond.cleanup7: ; preds = %for.body8
355​ %indvars.iv.next52 = add nuw nsw i64 %indvars.iv51, 1
356​ %exitcond54 = icmp eq i64 %indvars.iv.next52, %N
357​ br i1 %exitcond54, label %for.cond.cleanup3, label %for.body8.lr.ph
358​
359​for.body8: ; preds = %for.body8, %for.body8.lr.ph
360​ %indvars.iv = phi i64 [ 0, %for.body8.lr.ph ], [ %indvars.iv.next, %for.body8 ]
361​ %arrayidx10 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @c, i64 0, i64 %indvars.iv, i64 %indvars.iv55
362​ %arrayidx14 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @a, i64 0, i64 %indvars.iv, i64 %indvars.iv51
363​ %i_next = add i64 %indvars.iv, 1
364​ %arrayidx16 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @a, i64 0, i64 %i_next, i64 %indvars.iv51
365​ %k_sub = sub i64 %indvars.iv51, 1
366​ %arrayidx18 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @b, i64 0, i64 %indvars.iv, i64 %k_sub
367​ %arrayidx20 = getelementptr inbounds [1024 x [1024 x i64]], [1024 x [1024 x i64]]* @b, i64 0, i64 %indvars.iv, i64 %indvars.iv51
368​ %vc = load i64, i64* %arrayidx10, align 4
369​ %va = load i64, i64* %arrayidx16, align 4
370​ %vb = load i64, i64* %arrayidx18, align 4
371​ %add = add nsw i64 %vc, %va
372​ store i64 %add, i64* %arrayidx10, align 4
373​ store i64 %va, i64* %arrayidx14, align 4
374​ store i64 %vb, i64* %arrayidx20, align 4
375​ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
376​ %exitcond = icmp eq i64 %indvars.iv.next, %N
377​ br i1 %exitcond, label %for.cond.cleanup7, label %for.body8
378​}