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