1; RUN: opt < %s -analyze -basicaa -da -da-delinearize=false | FileCheck %s
2; RUN: opt < %s -analyze -basicaa -da -da-delinearize | FileCheck %s -check-prefix=DELIN
3
4; ModuleID = 'GCD.bc'
5target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
6target triple = "x86_64-apple-macosx10.6.0"
7
8
9;;  for (long int i = 0; i < 100; i++)
10;;    for (long int j = 0; j < 100; j++) {
11;;      A[2*i - 4*j] = i;
12;;      *B++ = A[6*i + 8*j];
13
14define void @gcd0(i32* %A, i32* %B) nounwind uwtable ssp {
15entry:
16  br label %for.cond1.preheader
17
18; CHECK: 'Dependence Analysis' for function 'gcd0'
19; CHECK: da analyze - output [* *]!
20; CHECK: da analyze - flow [=> *|<]!
21; CHECK: da analyze - confused!
22; CHECK: da analyze - input [* *]!
23; CHECK: da analyze - confused!
24; CHECK: da analyze - none!
25
26; DELIN: 'Dependence Analysis' for function 'gcd0'
27; DELIN: da analyze - output [* *]!
28; DELIN: da analyze - flow [=> *|<]!
29; DELIN: da analyze - confused!
30; DELIN: da analyze - input [* *]!
31; DELIN: da analyze - confused!
32; DELIN: da analyze - none!
33
34for.cond1.preheader:                              ; preds = %entry, %for.inc8
35  %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc8 ]
36  %i.03 = phi i64 [ 0, %entry ], [ %inc9, %for.inc8 ]
37  br label %for.body3
38
39for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
40  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
41  %B.addr.11 = phi i32* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
42  %conv = trunc i64 %i.03 to i32
43  %mul = shl nsw i64 %i.03, 1
44  %mul4 = shl nsw i64 %j.02, 2
45  %sub = sub nsw i64 %mul, %mul4
46  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %sub
47  store i32 %conv, i32* %arrayidx, align 4
48  %mul5 = mul nsw i64 %i.03, 6
49  %mul6 = shl nsw i64 %j.02, 3
50  %add = add nsw i64 %mul5, %mul6
51  %arrayidx7 = getelementptr inbounds i32, i32* %A, i64 %add
52  %0 = load i32, i32* %arrayidx7, align 4
53  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.11, i64 1
54  store i32 %0, i32* %B.addr.11, align 4
55  %inc = add nsw i64 %j.02, 1
56  %exitcond = icmp ne i64 %inc, 100
57  br i1 %exitcond, label %for.body3, label %for.inc8
58
59for.inc8:                                         ; preds = %for.body3
60  %scevgep = getelementptr i32, i32* %B.addr.04, i64 100
61  %inc9 = add nsw i64 %i.03, 1
62  %exitcond5 = icmp ne i64 %inc9, 100
63  br i1 %exitcond5, label %for.cond1.preheader, label %for.end10
64
65for.end10:                                        ; preds = %for.inc8
66  ret void
67}
68
69
70;;  for (long int i = 0; i < 100; i++)
71;;    for (long int j = 0; j < 100; j++) {
72;;      A[2*i - 4*j] = i;
73;;      *B++ = A[6*i + 8*j + 1];
74
75define void @gcd1(i32* %A, i32* %B) nounwind uwtable ssp {
76entry:
77  br label %for.cond1.preheader
78
79; CHECK: 'Dependence Analysis' for function 'gcd1'
80; CHECK: da analyze - output [* *]!
81; CHECK: da analyze - none!
82; CHECK: da analyze - confused!
83; CHECK: da analyze - input [* *]!
84; CHECK: da analyze - confused!
85; CHECK: da analyze - none!
86
87; DELIN: 'Dependence Analysis' for function 'gcd1'
88; DELIN: da analyze - output [* *]!
89; DELIN: da analyze - none!
90; DELIN: da analyze - confused!
91; DELIN: da analyze - input [* *]!
92; DELIN: da analyze - confused!
93; DELIN: da analyze - none!
94
95for.cond1.preheader:                              ; preds = %entry, %for.inc9
96  %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ]
97  %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ]
98  br label %for.body3
99
100for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
101  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
102  %B.addr.11 = phi i32* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
103  %conv = trunc i64 %i.03 to i32
104  %mul = shl nsw i64 %i.03, 1
105  %mul4 = shl nsw i64 %j.02, 2
106  %sub = sub nsw i64 %mul, %mul4
107  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %sub
108  store i32 %conv, i32* %arrayidx, align 4
109  %mul5 = mul nsw i64 %i.03, 6
110  %mul6 = shl nsw i64 %j.02, 3
111  %add = add nsw i64 %mul5, %mul6
112  %add7 = or i64 %add, 1
113  %arrayidx8 = getelementptr inbounds i32, i32* %A, i64 %add7
114  %0 = load i32, i32* %arrayidx8, align 4
115  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.11, i64 1
116  store i32 %0, i32* %B.addr.11, align 4
117  %inc = add nsw i64 %j.02, 1
118  %exitcond = icmp ne i64 %inc, 100
119  br i1 %exitcond, label %for.body3, label %for.inc9
120
121for.inc9:                                         ; preds = %for.body3
122  %scevgep = getelementptr i32, i32* %B.addr.04, i64 100
123  %inc10 = add nsw i64 %i.03, 1
124  %exitcond5 = icmp ne i64 %inc10, 100
125  br i1 %exitcond5, label %for.cond1.preheader, label %for.end11
126
127for.end11:                                        ; preds = %for.inc9
128  ret void
129}
130
131
132;;  for (long int i = 0; i < 100; i++)
133;;    for (long int j = 0; j < 100; j++) {
134;;      A[2*i - 4*j + 1] = i;
135;;      *B++ = A[6*i + 8*j];
136
137define void @gcd2(i32* %A, i32* %B) nounwind uwtable ssp {
138entry:
139  br label %for.cond1.preheader
140
141; CHECK: 'Dependence Analysis' for function 'gcd2'
142; CHECK: da analyze - output [* *]!
143; CHECK: da analyze - none!
144; CHECK: da analyze - confused!
145; CHECK: da analyze - input [* *]!
146; CHECK: da analyze - confused!
147; CHECK: da analyze - none!
148
149; DELIN: 'Dependence Analysis' for function 'gcd2'
150; DELIN: da analyze - output [* *]!
151; DELIN: da analyze - none!
152; DELIN: da analyze - confused!
153; DELIN: da analyze - input [* *]!
154; DELIN: da analyze - confused!
155; DELIN: da analyze - none!
156
157for.cond1.preheader:                              ; preds = %entry, %for.inc9
158  %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc9 ]
159  %i.03 = phi i64 [ 0, %entry ], [ %inc10, %for.inc9 ]
160  br label %for.body3
161
162for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
163  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
164  %B.addr.11 = phi i32* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
165  %conv = trunc i64 %i.03 to i32
166  %mul = shl nsw i64 %i.03, 1
167  %mul4 = shl nsw i64 %j.02, 2
168  %sub = sub nsw i64 %mul, %mul4
169  %add5 = or i64 %sub, 1
170  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %add5
171  store i32 %conv, i32* %arrayidx, align 4
172  %mul5 = mul nsw i64 %i.03, 6
173  %mul6 = shl nsw i64 %j.02, 3
174  %add7 = add nsw i64 %mul5, %mul6
175  %arrayidx8 = getelementptr inbounds i32, i32* %A, i64 %add7
176  %0 = load i32, i32* %arrayidx8, align 4
177  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.11, i64 1
178  store i32 %0, i32* %B.addr.11, align 4
179  %inc = add nsw i64 %j.02, 1
180  %exitcond = icmp ne i64 %inc, 100
181  br i1 %exitcond, label %for.body3, label %for.inc9
182
183for.inc9:                                         ; preds = %for.body3
184  %scevgep = getelementptr i32, i32* %B.addr.04, i64 100
185  %inc10 = add nsw i64 %i.03, 1
186  %exitcond6 = icmp ne i64 %inc10, 100
187  br i1 %exitcond6, label %for.cond1.preheader, label %for.end11
188
189for.end11:                                        ; preds = %for.inc9
190  ret void
191}
192
193
194;;  for (long int i = 0; i < 100; i++)
195;;    for (long int j = 0; j < 100; j++) {
196;;      A[i + 2*j] = i;
197;;      *B++ = A[i + 2*j - 1];
198
199define void @gcd3(i32* %A, i32* %B) nounwind uwtable ssp {
200entry:
201  br label %for.cond1.preheader
202
203; CHECK: 'Dependence Analysis' for function 'gcd3'
204; CHECK: da analyze - output [* *]!
205; CHECK: da analyze - flow [<> *]!
206; CHECK: da analyze - confused!
207; CHECK: da analyze - input [* *]!
208; CHECK: da analyze - confused!
209; CHECK: da analyze - none!
210
211; DELIN: 'Dependence Analysis' for function 'gcd3'
212; DELIN: da analyze - output [* *]!
213; DELIN: da analyze - flow [<> *]!
214; DELIN: da analyze - confused!
215; DELIN: da analyze - input [* *]!
216; DELIN: da analyze - confused!
217; DELIN: da analyze - none!
218
219for.cond1.preheader:                              ; preds = %entry, %for.inc7
220  %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc7 ]
221  %i.03 = phi i64 [ 0, %entry ], [ %inc8, %for.inc7 ]
222  br label %for.body3
223
224for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
225  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
226  %B.addr.11 = phi i32* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
227  %conv = trunc i64 %i.03 to i32
228  %mul = shl nsw i64 %j.02, 1
229  %add = add nsw i64 %i.03, %mul
230  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %add
231  store i32 %conv, i32* %arrayidx, align 4
232  %mul4 = shl nsw i64 %j.02, 1
233  %add5 = add nsw i64 %i.03, %mul4
234  %sub = add nsw i64 %add5, -1
235  %arrayidx6 = getelementptr inbounds i32, i32* %A, i64 %sub
236  %0 = load i32, i32* %arrayidx6, align 4
237  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.11, i64 1
238  store i32 %0, i32* %B.addr.11, align 4
239  %inc = add nsw i64 %j.02, 1
240  %exitcond = icmp ne i64 %inc, 100
241  br i1 %exitcond, label %for.body3, label %for.inc7
242
243for.inc7:                                         ; preds = %for.body3
244  %scevgep = getelementptr i32, i32* %B.addr.04, i64 100
245  %inc8 = add nsw i64 %i.03, 1
246  %exitcond5 = icmp ne i64 %inc8, 100
247  br i1 %exitcond5, label %for.cond1.preheader, label %for.end9
248
249for.end9:                                         ; preds = %for.inc7
250  ret void
251}
252
253
254;;  for (long int i = 0; i < 100; i++)
255;;    for (long int j = 0; j < 100; j++) {
256;;      A[5*i + 10*j*M + 9*M*N] = i;
257;;      *B++ = A[15*i + 20*j*M - 21*N*M + 4];
258
259define void @gcd4(i32* %A, i32* %B, i64 %M, i64 %N) nounwind uwtable ssp {
260entry:
261  br label %for.cond1.preheader
262
263; CHECK: 'Dependence Analysis' for function 'gcd4'
264; CHECK: da analyze - output [* *]!
265; CHECK: da analyze - none!
266; CHECK: da analyze - confused!
267; CHECK: da analyze - input [* *]!
268; CHECK: da analyze - confused!
269; CHECK: da analyze - none!
270
271; DELIN: 'Dependence Analysis' for function 'gcd4'
272; DELIN: da analyze - output [* *]!
273; DELIN: da analyze - none!
274; DELIN: da analyze - confused!
275; DELIN: da analyze - input [* *]!
276; DELIN: da analyze - confused!
277; DELIN: da analyze - none!
278
279for.cond1.preheader:                              ; preds = %entry, %for.inc17
280  %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc17 ]
281  %i.03 = phi i64 [ 0, %entry ], [ %inc18, %for.inc17 ]
282  br label %for.body3
283
284for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
285  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
286  %B.addr.11 = phi i32* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
287  %conv = trunc i64 %i.03 to i32
288  %mul = mul nsw i64 %i.03, 5
289  %mul4 = mul nsw i64 %j.02, 10
290  %mul5 = mul nsw i64 %mul4, %M
291  %add = add nsw i64 %mul, %mul5
292  %mul6 = mul nsw i64 %M, 9
293  %mul7 = mul nsw i64 %mul6, %N
294  %add8 = add nsw i64 %add, %mul7
295  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %add8
296  store i32 %conv, i32* %arrayidx, align 4
297  %mul9 = mul nsw i64 %i.03, 15
298  %mul10 = mul nsw i64 %j.02, 20
299  %mul11 = mul nsw i64 %mul10, %M
300  %add12 = add nsw i64 %mul9, %mul11
301  %mul13 = mul nsw i64 %N, 21
302  %mul14 = mul nsw i64 %mul13, %M
303  %sub = sub nsw i64 %add12, %mul14
304  %add15 = add nsw i64 %sub, 4
305  %arrayidx16 = getelementptr inbounds i32, i32* %A, i64 %add15
306  %0 = load i32, i32* %arrayidx16, align 4
307  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.11, i64 1
308  store i32 %0, i32* %B.addr.11, align 4
309  %inc = add nsw i64 %j.02, 1
310  %exitcond = icmp ne i64 %inc, 100
311  br i1 %exitcond, label %for.body3, label %for.inc17
312
313for.inc17:                                        ; preds = %for.body3
314  %scevgep = getelementptr i32, i32* %B.addr.04, i64 100
315  %inc18 = add nsw i64 %i.03, 1
316  %exitcond5 = icmp ne i64 %inc18, 100
317  br i1 %exitcond5, label %for.cond1.preheader, label %for.end19
318
319for.end19:                                        ; preds = %for.inc17
320  ret void
321}
322
323
324;;  for (long int i = 0; i < 100; i++)
325;;    for (long int j = 0; j < 100; j++) {
326;;      A[5*i + 10*j*M + 9*M*N] = i;
327;;      *B++ = A[15*i + 20*j*M - 21*N*M + 5];
328
329define void @gcd5(i32* %A, i32* %B, i64 %M, i64 %N) nounwind uwtable ssp {
330entry:
331  br label %for.cond1.preheader
332
333; CHECK: 'Dependence Analysis' for function 'gcd5'
334; CHECK: da analyze - output [* *]!
335; CHECK: da analyze - flow [<> *]!
336; CHECK: da analyze - confused!
337; CHECK: da analyze - input [* *]!
338; CHECK: da analyze - confused!
339; CHECK: da analyze - none!
340
341; DELIN: 'Dependence Analysis' for function 'gcd5'
342; DELIN: da analyze - output [* *]!
343; DELIN: da analyze - flow [<> *]!
344; DELIN: da analyze - confused!
345; DELIN: da analyze - input [* *]!
346; DELIN: da analyze - confused!
347; DELIN: da analyze - none!
348
349for.cond1.preheader:                              ; preds = %entry, %for.inc17
350  %B.addr.04 = phi i32* [ %B, %entry ], [ %scevgep, %for.inc17 ]
351  %i.03 = phi i64 [ 0, %entry ], [ %inc18, %for.inc17 ]
352  br label %for.body3
353
354for.body3:                                        ; preds = %for.cond1.preheader, %for.body3
355  %j.02 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body3 ]
356  %B.addr.11 = phi i32* [ %B.addr.04, %for.cond1.preheader ], [ %incdec.ptr, %for.body3 ]
357  %conv = trunc i64 %i.03 to i32
358  %mul = mul nsw i64 %i.03, 5
359  %mul4 = mul nsw i64 %j.02, 10
360  %mul5 = mul nsw i64 %mul4, %M
361  %add = add nsw i64 %mul, %mul5
362  %mul6 = mul nsw i64 %M, 9
363  %mul7 = mul nsw i64 %mul6, %N
364  %add8 = add nsw i64 %add, %mul7
365  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %add8
366  store i32 %conv, i32* %arrayidx, align 4
367  %mul9 = mul nsw i64 %i.03, 15
368  %mul10 = mul nsw i64 %j.02, 20
369  %mul11 = mul nsw i64 %mul10, %M
370  %add12 = add nsw i64 %mul9, %mul11
371  %mul13 = mul nsw i64 %N, 21
372  %mul14 = mul nsw i64 %mul13, %M
373  %sub = sub nsw i64 %add12, %mul14
374  %add15 = add nsw i64 %sub, 5
375  %arrayidx16 = getelementptr inbounds i32, i32* %A, i64 %add15
376  %0 = load i32, i32* %arrayidx16, align 4
377  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.11, i64 1
378  store i32 %0, i32* %B.addr.11, align 4
379  %inc = add nsw i64 %j.02, 1
380  %exitcond = icmp ne i64 %inc, 100
381  br i1 %exitcond, label %for.body3, label %for.inc17
382
383for.inc17:                                        ; preds = %for.body3
384  %scevgep = getelementptr i32, i32* %B.addr.04, i64 100
385  %inc18 = add nsw i64 %i.03, 1
386  %exitcond5 = icmp ne i64 %inc18, 100
387  br i1 %exitcond5, label %for.cond1.preheader, label %for.end19
388
389for.end19:                                        ; preds = %for.inc17
390  ret void
391}
392
393
394;;  for (long int i = 0; i < n; i++)
395;;    for (long int j = 0; j < n; j++) {
396;;      A[2*i][4*j] = i;
397;;      *B++ = A[8*i][6*j + 1];
398
399define void @gcd6(i64 %n, i32* %A, i32* %B) nounwind uwtable ssp {
400entry:
401  %cmp4 = icmp sgt i64 %n, 0
402  br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end12
403
404; CHECK: 'Dependence Analysis' for function 'gcd6'
405; CHECK: da analyze - output [* *]!
406; CHECK: da analyze - none!
407; CHECK: da analyze - confused!
408; CHECK: da analyze - input [* *]!
409; CHECK: da analyze - confused!
410; CHECK: da analyze - output [* *]!
411
412; DELIN: 'Dependence Analysis' for function 'gcd6'
413; DELIN: da analyze - output [* *]!
414; DELIN: da analyze - none!
415; DELIN: da analyze - confused!
416; DELIN: da analyze - input [* *]!
417; DELIN: da analyze - confused!
418; DELIN: da analyze - output [* *]!
419
420for.cond1.preheader.preheader:                    ; preds = %entry
421  br label %for.cond1.preheader
422
423for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc10
424  %i.06 = phi i64 [ %inc11, %for.inc10 ], [ 0, %for.cond1.preheader.preheader ]
425  %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc10 ], [ %B, %for.cond1.preheader.preheader ]
426  %cmp21 = icmp sgt i64 %n, 0
427  br i1 %cmp21, label %for.body3.preheader, label %for.inc10
428
429for.body3.preheader:                              ; preds = %for.cond1.preheader
430  br label %for.body3
431
432for.body3:                                        ; preds = %for.body3.preheader, %for.body3
433  %j.03 = phi i64 [ %inc, %for.body3 ], [ 0, %for.body3.preheader ]
434  %B.addr.12 = phi i32* [ %incdec.ptr, %for.body3 ], [ %B.addr.05, %for.body3.preheader ]
435  %conv = trunc i64 %i.06 to i32
436  %mul = shl nsw i64 %j.03, 2
437  %mul4 = shl nsw i64 %i.06, 1
438  %0 = mul nsw i64 %mul4, %n
439  %arrayidx.sum = add i64 %0, %mul
440  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %arrayidx.sum
441  store i32 %conv, i32* %arrayidx5, align 4
442  %mul6 = mul nsw i64 %j.03, 6
443  %add7 = or i64 %mul6, 1
444  %mul7 = shl nsw i64 %i.06, 3
445  %1 = mul nsw i64 %mul7, %n
446  %arrayidx8.sum = add i64 %1, %add7
447  %arrayidx9 = getelementptr inbounds i32, i32* %A, i64 %arrayidx8.sum
448  %2 = load i32, i32* %arrayidx9, align 4
449  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.12, i64 1
450  store i32 %2, i32* %B.addr.12, align 4
451  %inc = add nsw i64 %j.03, 1
452  %exitcond = icmp ne i64 %inc, %n
453  br i1 %exitcond, label %for.body3, label %for.inc10.loopexit
454
455for.inc10.loopexit:                               ; preds = %for.body3
456  %scevgep = getelementptr i32, i32* %B.addr.05, i64 %n
457  br label %for.inc10
458
459for.inc10:                                        ; preds = %for.inc10.loopexit, %for.cond1.preheader
460  %B.addr.1.lcssa = phi i32* [ %B.addr.05, %for.cond1.preheader ], [ %scevgep, %for.inc10.loopexit ]
461  %inc11 = add nsw i64 %i.06, 1
462  %exitcond8 = icmp ne i64 %inc11, %n
463  br i1 %exitcond8, label %for.cond1.preheader, label %for.end12.loopexit
464
465for.end12.loopexit:                               ; preds = %for.inc10
466  br label %for.end12
467
468for.end12:                                        ; preds = %for.end12.loopexit, %entry
469  ret void
470}
471
472
473;;  for (int i = 0; i < n; i++)
474;;   for (int j = 0; j < n; j++) {
475;;    A[2*i][4*j] = i;
476;;   *B++ = A[8*i][6*j + 1];
477
478define void @gcd7(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
479entry:
480  %0 = zext i32 %n to i64
481  %cmp4 = icmp sgt i32 %n, 0
482  br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15
483
484; CHECK: 'Dependence Analysis' for function 'gcd7'
485; CHECK: da analyze - output [* *]!
486; CHECK: da analyze - flow [* *|<]!
487; CHECK: da analyze - confused!
488; CHECK: da analyze - input [* *]!
489; CHECK: da analyze - confused!
490; CHECK: da analyze - output [* *]!
491
492; DELIN: 'Dependence Analysis' for function 'gcd7'
493; DELIN: da analyze - output [* *]!
494; DELIN: da analyze - flow [* *|<]!
495; DELIN: da analyze - confused!
496; DELIN: da analyze - input [* *]!
497; DELIN: da analyze - confused!
498; DELIN: da analyze - output [* *]!
499
500for.cond1.preheader.preheader:                    ; preds = %entry
501  br label %for.cond1.preheader
502
503for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc13
504  %indvars.iv8 = phi i64 [ 0, %for.cond1.preheader.preheader ], [ %indvars.iv.next9, %for.inc13 ]
505  %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
506  %1 = add i32 %n, -1
507  %2 = zext i32 %1 to i64
508  %3 = add i64 %2, 1
509  %cmp21 = icmp sgt i32 %n, 0
510  br i1 %cmp21, label %for.body3.preheader, label %for.inc13
511
512for.body3.preheader:                              ; preds = %for.cond1.preheader
513  br label %for.body3
514
515for.body3:                                        ; preds = %for.body3.preheader, %for.body3
516  %indvars.iv = phi i64 [ 0, %for.body3.preheader ], [ %indvars.iv.next, %for.body3 ]
517  %B.addr.12 = phi i32* [ %incdec.ptr, %for.body3 ], [ %B.addr.05, %for.body3.preheader ]
518  %4 = trunc i64 %indvars.iv to i32
519  %mul = shl nsw i32 %4, 2
520  %idxprom = sext i32 %mul to i64
521  %5 = trunc i64 %indvars.iv8 to i32
522  %mul4 = shl nsw i32 %5, 1
523  %idxprom5 = sext i32 %mul4 to i64
524  %6 = mul nsw i64 %idxprom5, %0
525  %arrayidx.sum = add i64 %6, %idxprom
526  %arrayidx6 = getelementptr inbounds i32, i32* %A, i64 %arrayidx.sum
527  %7 = trunc i64 %indvars.iv8 to i32
528  store i32 %7, i32* %arrayidx6, align 4
529  %8 = trunc i64 %indvars.iv to i32
530  %mul7 = mul nsw i32 %8, 6
531  %add7 = or i32 %mul7, 1
532  %idxprom8 = sext i32 %add7 to i64
533  %9 = trunc i64 %indvars.iv8 to i32
534  %mul9 = shl nsw i32 %9, 3
535  %idxprom10 = sext i32 %mul9 to i64
536  %10 = mul nsw i64 %idxprom10, %0
537  %arrayidx11.sum = add i64 %10, %idxprom8
538  %arrayidx12 = getelementptr inbounds i32, i32* %A, i64 %arrayidx11.sum
539  %11 = load i32, i32* %arrayidx12, align 4
540  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.12, i64 1
541  store i32 %11, i32* %B.addr.12, align 4
542  %indvars.iv.next = add i64 %indvars.iv, 1
543  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
544  %exitcond = icmp ne i32 %lftr.wideiv, %n
545  br i1 %exitcond, label %for.body3, label %for.inc13.loopexit
546
547for.inc13.loopexit:                               ; preds = %for.body3
548  %scevgep = getelementptr i32, i32* %B.addr.05, i64 %3
549  br label %for.inc13
550
551for.inc13:                                        ; preds = %for.inc13.loopexit, %for.cond1.preheader
552  %B.addr.1.lcssa = phi i32* [ %B.addr.05, %for.cond1.preheader ], [ %scevgep, %for.inc13.loopexit ]
553  %indvars.iv.next9 = add i64 %indvars.iv8, 1
554  %lftr.wideiv10 = trunc i64 %indvars.iv.next9 to i32
555  %exitcond11 = icmp ne i32 %lftr.wideiv10, %n
556  br i1 %exitcond11, label %for.cond1.preheader, label %for.end15.loopexit
557
558for.end15.loopexit:                               ; preds = %for.inc13
559  br label %for.end15
560
561for.end15:                                        ; preds = %for.end15.loopexit, %entry
562  ret void
563}
564
565
566;;  for (int i = 0; i < n; i++)
567;;    for (int j = 0; j < n; j++) {
568;;      A[n*2*i + 4*j] = i;
569;;      *B++ = A[n*8*i + 6*j + 1];
570
571define void @gcd8(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
572entry:
573  %cmp4 = icmp sgt i32 %n, 0
574  br i1 %cmp4, label %for.cond1.preheader.preheader, label %for.end15
575
576; CHECK: 'Dependence Analysis' for function 'gcd8'
577; CHECK: da analyze - output [* *]!
578; CHECK: da analyze - none!
579; CHECK: da analyze - confused!
580; CHECK: da analyze - input [* *]!
581; CHECK: da analyze - confused!
582; CHECK: da analyze - output [* *]!
583
584; DELIN: 'Dependence Analysis' for function 'gcd8'
585; DELIN: da analyze - output [* *]!
586; DELIN: da analyze - none!
587; DELIN: da analyze - confused!
588; DELIN: da analyze - input [* *]!
589; DELIN: da analyze - confused!
590; DELIN: da analyze - output [* *]!
591
592for.cond1.preheader.preheader:                    ; preds = %entry
593  br label %for.cond1.preheader
594
595for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc13
596  %i.06 = phi i32 [ %inc14, %for.inc13 ], [ 0, %for.cond1.preheader.preheader ]
597  %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
598  %0 = add i32 %n, -1
599  %1 = zext i32 %0 to i64
600  %2 = add i64 %1, 1
601  %cmp21 = icmp sgt i32 %n, 0
602  br i1 %cmp21, label %for.body3.preheader, label %for.inc13
603
604for.body3.preheader:                              ; preds = %for.cond1.preheader
605  br label %for.body3
606
607for.body3:                                        ; preds = %for.body3.preheader, %for.body3
608  %indvars.iv = phi i64 [ 0, %for.body3.preheader ], [ %indvars.iv.next, %for.body3 ]
609  %B.addr.12 = phi i32* [ %incdec.ptr, %for.body3 ], [ %B.addr.05, %for.body3.preheader ]
610  %mul = shl nsw i32 %n, 1
611  %mul4 = mul nsw i32 %mul, %i.06
612  %3 = trunc i64 %indvars.iv to i32
613  %mul5 = shl nsw i32 %3, 2
614  %add = add nsw i32 %mul4, %mul5
615  %idxprom = sext i32 %add to i64
616  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
617  store i32 %i.06, i32* %arrayidx, align 4
618  %mul6 = shl nsw i32 %n, 3
619  %mul7 = mul nsw i32 %mul6, %i.06
620  %4 = trunc i64 %indvars.iv to i32
621  %mul8 = mul nsw i32 %4, 6
622  %add9 = add nsw i32 %mul7, %mul8
623  %add10 = or i32 %add9, 1
624  %idxprom11 = sext i32 %add10 to i64
625  %arrayidx12 = getelementptr inbounds i32, i32* %A, i64 %idxprom11
626  %5 = load i32, i32* %arrayidx12, align 4
627  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.12, i64 1
628  store i32 %5, i32* %B.addr.12, align 4
629  %indvars.iv.next = add i64 %indvars.iv, 1
630  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
631  %exitcond = icmp ne i32 %lftr.wideiv, %n
632  br i1 %exitcond, label %for.body3, label %for.inc13.loopexit
633
634for.inc13.loopexit:                               ; preds = %for.body3
635  %scevgep = getelementptr i32, i32* %B.addr.05, i64 %2
636  br label %for.inc13
637
638for.inc13:                                        ; preds = %for.inc13.loopexit, %for.cond1.preheader
639  %B.addr.1.lcssa = phi i32* [ %B.addr.05, %for.cond1.preheader ], [ %scevgep, %for.inc13.loopexit ]
640  %inc14 = add nsw i32 %i.06, 1
641  %exitcond7 = icmp ne i32 %inc14, %n
642  br i1 %exitcond7, label %for.cond1.preheader, label %for.end15.loopexit
643
644for.end15.loopexit:                               ; preds = %for.inc13
645  br label %for.end15
646
647for.end15:                                        ; preds = %for.end15.loopexit, %entry
648  ret void
649}
650
651
652;;  for (unsigned i = 0; i < n; i++)
653;;    for (unsigned j = 0; j < n; j++) {
654;;      A[2*i][4*j] = i;
655;;      *B++ = A[8*i][6*j + 1];
656
657define void @gcd9(i32 %n, i32* %A, i32* %B) nounwind uwtable ssp {
658entry:
659  %0 = zext i32 %n to i64
660  %cmp4 = icmp eq i32 %n, 0
661  br i1 %cmp4, label %for.end15, label %for.cond1.preheader.preheader
662
663; CHECK: 'Dependence Analysis' for function 'gcd9'
664; CHECK: da analyze - output [* *]!
665; CHECK: da analyze - flow [* *|<]!
666; CHECK: da analyze - confused!
667; CHECK: da analyze - input [* *]!
668; CHECK: da analyze - confused!
669; CHECK: da analyze - output [* *]!
670
671; DELIN: 'Dependence Analysis' for function 'gcd9'
672; DELIN: da analyze - output [* *]!
673; DELIN: da analyze - flow [* *|<]!
674; DELIN: da analyze - confused!
675; DELIN: da analyze - input [* *]!
676; DELIN: da analyze - confused!
677; DELIN: da analyze - output [* *]!
678
679for.cond1.preheader.preheader:                    ; preds = %entry
680  br label %for.cond1.preheader
681
682for.cond1.preheader:                              ; preds = %for.cond1.preheader.preheader, %for.inc13
683  %indvars.iv8 = phi i64 [ 0, %for.cond1.preheader.preheader ], [ %indvars.iv.next9, %for.inc13 ]
684  %B.addr.05 = phi i32* [ %B.addr.1.lcssa, %for.inc13 ], [ %B, %for.cond1.preheader.preheader ]
685  %1 = add i32 %n, -1
686  %2 = zext i32 %1 to i64
687  %3 = add i64 %2, 1
688  %cmp21 = icmp eq i32 %n, 0
689  br i1 %cmp21, label %for.inc13, label %for.body3.preheader
690
691for.body3.preheader:                              ; preds = %for.cond1.preheader
692  br label %for.body3
693
694for.body3:                                        ; preds = %for.body3.preheader, %for.body3
695  %indvars.iv = phi i64 [ 0, %for.body3.preheader ], [ %indvars.iv.next, %for.body3 ]
696  %B.addr.12 = phi i32* [ %incdec.ptr, %for.body3 ], [ %B.addr.05, %for.body3.preheader ]
697  %4 = trunc i64 %indvars.iv to i32
698  %mul = shl i32 %4, 2
699  %idxprom = zext i32 %mul to i64
700  %5 = trunc i64 %indvars.iv8 to i32
701  %mul4 = shl i32 %5, 1
702  %idxprom5 = zext i32 %mul4 to i64
703  %6 = mul nsw i64 %idxprom5, %0
704  %arrayidx.sum = add i64 %6, %idxprom
705  %arrayidx6 = getelementptr inbounds i32, i32* %A, i64 %arrayidx.sum
706  %7 = trunc i64 %indvars.iv8 to i32
707  store i32 %7, i32* %arrayidx6, align 4
708  %8 = trunc i64 %indvars.iv to i32
709  %mul7 = mul i32 %8, 6
710  %add7 = or i32 %mul7, 1
711  %idxprom8 = zext i32 %add7 to i64
712  %9 = trunc i64 %indvars.iv8 to i32
713  %mul9 = shl i32 %9, 3
714  %idxprom10 = zext i32 %mul9 to i64
715  %10 = mul nsw i64 %idxprom10, %0
716  %arrayidx11.sum = add i64 %10, %idxprom8
717  %arrayidx12 = getelementptr inbounds i32, i32* %A, i64 %arrayidx11.sum
718  %11 = load i32, i32* %arrayidx12, align 4
719  %incdec.ptr = getelementptr inbounds i32, i32* %B.addr.12, i64 1
720  store i32 %11, i32* %B.addr.12, align 4
721  %indvars.iv.next = add i64 %indvars.iv, 1
722  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
723  %exitcond = icmp ne i32 %lftr.wideiv, %n
724  br i1 %exitcond, label %for.body3, label %for.inc13.loopexit
725
726for.inc13.loopexit:                               ; preds = %for.body3
727  %scevgep = getelementptr i32, i32* %B.addr.05, i64 %3
728  br label %for.inc13
729
730for.inc13:                                        ; preds = %for.inc13.loopexit, %for.cond1.preheader
731  %B.addr.1.lcssa = phi i32* [ %B.addr.05, %for.cond1.preheader ], [ %scevgep, %for.inc13.loopexit ]
732  %indvars.iv.next9 = add i64 %indvars.iv8, 1
733  %lftr.wideiv10 = trunc i64 %indvars.iv.next9 to i32
734  %exitcond11 = icmp ne i32 %lftr.wideiv10, %n
735  br i1 %exitcond11, label %for.cond1.preheader, label %for.end15.loopexit
736
737for.end15.loopexit:                               ; preds = %for.inc13
738  br label %for.end15
739
740for.end15:                                        ; preds = %for.end15.loopexit, %entry
741  ret void
742}
743