1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -basic-aa -loop-idiom < %s -S | FileCheck %s
3target 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"
4
5target triple = "x86_64-apple-darwin10.0.0"
6
7%struct.foo = type { i32, i32 }
8%struct.foo1 = type { i32, i32, i32 }
9%struct.foo2 = type { i32, i16, i16 }
10
11;void bar1(foo_t *f, unsigned n) {
12;  for (unsigned i = 0; i < n; ++i) {
13;    f[i].a = 0;
14;    f[i].b = 0;
15;  }
16;}
17define void @bar1(%struct.foo* %f, i32 %n) nounwind ssp {
18; CHECK-LABEL: @bar1(
19; CHECK-NEXT:  entry:
20; CHECK-NEXT:    [[F1:%.*]] = bitcast %struct.foo* [[F:%.*]] to i8*
21; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[N:%.*]], 0
22; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
23; CHECK:       for.body.preheader:
24; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N]] to i64
25; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i64 [[TMP0]], 3
26; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[F1]], i8 0, i64 [[TMP1]], i1 false)
27; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
28; CHECK:       for.body:
29; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
30; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds [[STRUCT_FOO:%.*]], %struct.foo* [[F]], i64 [[INDVARS_IV]], i32 0
31; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [[STRUCT_FOO]], %struct.foo* [[F]], i64 [[INDVARS_IV]], i32 1
32; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
33; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
34; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[N]]
35; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
36; CHECK:       for.end.loopexit:
37; CHECK-NEXT:    br label [[FOR_END]]
38; CHECK:       for.end:
39; CHECK-NEXT:    ret void
40;
41entry:
42  %cmp1 = icmp eq i32 %n, 0
43  br i1 %cmp1, label %for.end, label %for.body.preheader
44
45for.body.preheader:                               ; preds = %entry
46  br label %for.body
47
48for.body:                                         ; preds = %for.body.preheader, %for.body
49  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
50  %a = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
51  store i32 0, i32* %a, align 4
52  %b = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 1
53  store i32 0, i32* %b, align 4
54  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
55  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
56  %exitcond = icmp ne i32 %lftr.wideiv, %n
57  br i1 %exitcond, label %for.body, label %for.end.loopexit
58
59for.end.loopexit:                                 ; preds = %for.body
60  br label %for.end
61
62for.end:                                          ; preds = %for.end.loopexit, %entry
63  ret void
64}
65
66;void bar2(foo_t *f, unsigned n) {
67;  for (unsigned i = 0; i < n; ++i) {
68;    f[i].b = 0;
69;    f[i].a = 0;
70;  }
71;}
72define void @bar2(%struct.foo* %f, i32 %n) nounwind ssp {
73; CHECK-LABEL: @bar2(
74; CHECK-NEXT:  entry:
75; CHECK-NEXT:    [[F1:%.*]] = bitcast %struct.foo* [[F:%.*]] to i8*
76; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[N:%.*]], 0
77; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
78; CHECK:       for.body.preheader:
79; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N]] to i64
80; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i64 [[TMP0]], 3
81; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[F1]], i8 0, i64 [[TMP1]], i1 false)
82; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
83; CHECK:       for.body:
84; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
85; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [[STRUCT_FOO:%.*]], %struct.foo* [[F]], i64 [[INDVARS_IV]], i32 1
86; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds [[STRUCT_FOO]], %struct.foo* [[F]], i64 [[INDVARS_IV]], i32 0
87; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
88; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
89; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[N]]
90; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
91; CHECK:       for.end.loopexit:
92; CHECK-NEXT:    br label [[FOR_END]]
93; CHECK:       for.end:
94; CHECK-NEXT:    ret void
95;
96entry:
97  %cmp1 = icmp eq i32 %n, 0
98  br i1 %cmp1, label %for.end, label %for.body.preheader
99
100for.body.preheader:                               ; preds = %entry
101  br label %for.body
102
103for.body:                                         ; preds = %for.body.preheader, %for.body
104  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
105  %b = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 1
106  store i32 0, i32* %b, align 4
107  %a = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
108  store i32 0, i32* %a, align 4
109  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
110  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
111  %exitcond = icmp ne i32 %lftr.wideiv, %n
112  br i1 %exitcond, label %for.body, label %for.end.loopexit
113
114for.end.loopexit:                                 ; preds = %for.body
115  br label %for.end
116
117for.end:                                          ; preds = %for.end.loopexit, %entry
118  ret void
119}
120
121;void bar3(foo_t *f, unsigned n) {
122;  for (unsigned i = n; i > 0; --i) {
123;    f[i].a = 0;
124;    f[i].b = 0;
125;  }
126;}
127define void @bar3(%struct.foo* nocapture %f, i32 %n) nounwind ssp {
128; CHECK-LABEL: @bar3(
129; CHECK-NEXT:  entry:
130; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[N:%.*]], 0
131; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
132; CHECK:       for.body.preheader:
133; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N]] to i64
134; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[N]], -1
135; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[TMP1]] to i64
136; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP0]], [[TMP2]]
137; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr [[STRUCT_FOO:%.*]], %struct.foo* [[F:%.*]], i64 [[TMP3]]
138; CHECK-NEXT:    [[SCEVGEP1:%.*]] = bitcast %struct.foo* [[SCEVGEP]] to i8*
139; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i64 [[TMP0]], 3
140; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[SCEVGEP1]], i8 0, i64 [[TMP4]], i1 false)
141; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
142; CHECK:       for.body:
143; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP0]], [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
144; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds [[STRUCT_FOO]], %struct.foo* [[F]], i64 [[INDVARS_IV]], i32 0
145; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [[STRUCT_FOO]], %struct.foo* [[F]], i64 [[INDVARS_IV]], i32 1
146; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[INDVARS_IV]] to i32
147; CHECK-NEXT:    [[DEC:%.*]] = add i32 [[TMP5]], -1
148; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[DEC]], 0
149; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
150; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY]]
151; CHECK:       for.end.loopexit:
152; CHECK-NEXT:    br label [[FOR_END]]
153; CHECK:       for.end:
154; CHECK-NEXT:    ret void
155;
156entry:
157  %cmp1 = icmp eq i32 %n, 0
158  br i1 %cmp1, label %for.end, label %for.body.preheader
159
160for.body.preheader:                               ; preds = %entry
161  %0 = zext i32 %n to i64
162  br label %for.body
163
164for.body:                                         ; preds = %for.body.preheader, %for.body
165  %indvars.iv = phi i64 [ %0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
166  %a = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
167  store i32 0, i32* %a, align 4
168  %b = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 1
169  store i32 0, i32* %b, align 4
170  %1 = trunc i64 %indvars.iv to i32
171  %dec = add i32 %1, -1
172  %cmp = icmp eq i32 %dec, 0
173  %indvars.iv.next = add nsw i64 %indvars.iv, -1
174  br i1 %cmp, label %for.end.loopexit, label %for.body
175
176for.end.loopexit:                                 ; preds = %for.body
177  br label %for.end
178
179for.end:                                          ; preds = %for.end.loopexit, %entry
180  ret void
181}
182
183;void bar4(foo_t *f, unsigned n) {
184;  for (unsigned i = 0; i < n; ++i) {
185;    f[i].a = 0;
186;    f[i].b = 1;
187;  }
188;}
189define void @bar4(%struct.foo* nocapture %f, i32 %n) nounwind ssp {
190; CHECK-LABEL: @bar4(
191; CHECK-NEXT:  entry:
192; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[N:%.*]], 0
193; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
194; CHECK:       for.body.preheader:
195; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
196; CHECK:       for.body:
197; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
198; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds [[STRUCT_FOO:%.*]], %struct.foo* [[F:%.*]], i64 [[INDVARS_IV]], i32 0
199; CHECK-NEXT:    store i32 0, i32* [[A]], align 4
200; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [[STRUCT_FOO]], %struct.foo* [[F]], i64 [[INDVARS_IV]], i32 1
201; CHECK-NEXT:    store i32 1, i32* [[B]], align 4
202; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
203; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
204; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[N]]
205; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
206; CHECK:       for.end.loopexit:
207; CHECK-NEXT:    br label [[FOR_END]]
208; CHECK:       for.end:
209; CHECK-NEXT:    ret void
210;
211entry:
212  %cmp1 = icmp eq i32 %n, 0
213  br i1 %cmp1, label %for.end, label %for.body.preheader
214
215for.body.preheader:                               ; preds = %entry
216  br label %for.body
217
218for.body:                                         ; preds = %for.body.preheader, %for.body
219  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
220  %a = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 0
221  store i32 0, i32* %a, align 4
222  %b = getelementptr inbounds %struct.foo, %struct.foo* %f, i64 %indvars.iv, i32 1
223  store i32 1, i32* %b, align 4
224  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
225  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
226  %exitcond = icmp ne i32 %lftr.wideiv, %n
227  br i1 %exitcond, label %for.body, label %for.end.loopexit
228
229for.end.loopexit:                                 ; preds = %for.body
230  br label %for.end
231
232for.end:                                          ; preds = %for.end.loopexit, %entry
233  ret void
234}
235
236;void bar5(foo1_t *f, unsigned n) {
237;  for (unsigned i = 0; i < n; ++i) {
238;    f[i].a = 0;
239;    f[i].b = 0;
240;  }
241;}
242define void @bar5(%struct.foo1* nocapture %f, i32 %n) nounwind ssp {
243; CHECK-LABEL: @bar5(
244; CHECK-NEXT:  entry:
245; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[N:%.*]], 0
246; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
247; CHECK:       for.body.preheader:
248; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
249; CHECK:       for.body:
250; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
251; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds [[STRUCT_FOO1:%.*]], %struct.foo1* [[F:%.*]], i64 [[INDVARS_IV]], i32 0
252; CHECK-NEXT:    store i32 0, i32* [[A]], align 4
253; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [[STRUCT_FOO1]], %struct.foo1* [[F]], i64 [[INDVARS_IV]], i32 1
254; CHECK-NEXT:    store i32 0, i32* [[B]], align 4
255; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
256; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
257; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[N]]
258; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
259; CHECK:       for.end.loopexit:
260; CHECK-NEXT:    br label [[FOR_END]]
261; CHECK:       for.end:
262; CHECK-NEXT:    ret void
263;
264entry:
265  %cmp1 = icmp eq i32 %n, 0
266  br i1 %cmp1, label %for.end, label %for.body.preheader
267
268for.body.preheader:                               ; preds = %entry
269  br label %for.body
270
271for.body:                                         ; preds = %for.body.preheader, %for.body
272  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
273  %a = getelementptr inbounds %struct.foo1, %struct.foo1* %f, i64 %indvars.iv, i32 0
274  store i32 0, i32* %a, align 4
275  %b = getelementptr inbounds %struct.foo1, %struct.foo1* %f, i64 %indvars.iv, i32 1
276  store i32 0, i32* %b, align 4
277  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
278  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
279  %exitcond = icmp ne i32 %lftr.wideiv, %n
280  br i1 %exitcond, label %for.body, label %for.end.loopexit
281
282for.end.loopexit:                                 ; preds = %for.body
283  br label %for.end
284
285for.end:                                          ; preds = %for.end.loopexit, %entry
286  ret void
287}
288
289;void bar6(foo2_t *f, unsigned n) {
290;  for (unsigned i = 0; i < n; ++i) {
291;    f[i].a = 0;
292;    f[i].b = 0;
293;    f[i].c = 0;
294;  }
295;}
296define void @bar6(%struct.foo2* nocapture %f, i32 %n) nounwind ssp {
297; CHECK-LABEL: @bar6(
298; CHECK-NEXT:  entry:
299; CHECK-NEXT:    [[F1:%.*]] = bitcast %struct.foo2* [[F:%.*]] to i8*
300; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[N:%.*]], 0
301; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
302; CHECK:       for.body.preheader:
303; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[N]] to i64
304; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i64 [[TMP0]], 3
305; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[F1]], i8 0, i64 [[TMP1]], i1 false)
306; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
307; CHECK:       for.body:
308; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
309; CHECK-NEXT:    [[A:%.*]] = getelementptr inbounds [[STRUCT_FOO2:%.*]], %struct.foo2* [[F]], i64 [[INDVARS_IV]], i32 0
310; CHECK-NEXT:    [[B:%.*]] = getelementptr inbounds [[STRUCT_FOO2]], %struct.foo2* [[F]], i64 [[INDVARS_IV]], i32 1
311; CHECK-NEXT:    [[C:%.*]] = getelementptr inbounds [[STRUCT_FOO2]], %struct.foo2* [[F]], i64 [[INDVARS_IV]], i32 2
312; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
313; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
314; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[LFTR_WIDEIV]], [[N]]
315; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
316; CHECK:       for.end.loopexit:
317; CHECK-NEXT:    br label [[FOR_END]]
318; CHECK:       for.end:
319; CHECK-NEXT:    ret void
320;
321entry:
322  %cmp1 = icmp eq i32 %n, 0
323  br i1 %cmp1, label %for.end, label %for.body.preheader
324
325for.body.preheader:                               ; preds = %entry
326  br label %for.body
327
328for.body:                                         ; preds = %for.body.preheader, %for.body
329  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
330  %a = getelementptr inbounds %struct.foo2, %struct.foo2* %f, i64 %indvars.iv, i32 0
331  store i32 0, i32* %a, align 4
332  %b = getelementptr inbounds %struct.foo2, %struct.foo2* %f, i64 %indvars.iv, i32 1
333  store i16 0, i16* %b, align 4
334  %c = getelementptr inbounds %struct.foo2, %struct.foo2* %f, i64 %indvars.iv, i32 2
335  store i16 0, i16* %c, align 2
336  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
337  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
338  %exitcond = icmp ne i32 %lftr.wideiv, %n
339  br i1 %exitcond, label %for.body, label %for.end.loopexit
340
341for.end.loopexit:                                 ; preds = %for.body
342  br label %for.end
343
344for.end:                                          ; preds = %for.end.loopexit, %entry
345  ret void
346}
347