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