1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -indvars -S | FileCheck %s
3; RUN: opt < %s -S -passes='lcssa,loop-simplify,require<targetir>,require<scalar-evolution>,require<domtree>,loop(indvars)' | FileCheck %s
4
5; Provide legal integer types.
6target datalayout = "n8:16:32:64"
7
8
9target triple = "x86_64-apple-darwin"
10
11declare void @use(i64 %x)
12
13; Only one phi now.
14; One trunc for the gep.
15; One trunc for the dummy() call.
16define void @loop_0(i32* %a) {
17; CHECK-LABEL: @loop_0(
18; CHECK-NEXT:  Prologue:
19; CHECK-NEXT:    br i1 undef, label [[B18_PREHEADER:%.*]], label [[B6:%.*]]
20; CHECK:       B18.preheader:
21; CHECK-NEXT:    br label [[B18:%.*]]
22; CHECK:       B18:
23; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[B18_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[B24:%.*]] ]
24; CHECK-NEXT:    call void @use(i64 [[INDVARS_IV]])
25; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
26; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[INDVARS_IV]] to i32
27; CHECK-NEXT:    [[O:%.*]] = getelementptr i32, i32* [[A:%.*]], i32 [[TMP0]]
28; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[O]]
29; CHECK-NEXT:    [[T:%.*]] = icmp eq i32 [[V]], 0
30; CHECK-NEXT:    br i1 [[T]], label [[EXIT24:%.*]], label [[B24]]
31; CHECK:       B24:
32; CHECK-NEXT:    [[T2:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 20
33; CHECK-NEXT:    br i1 [[T2]], label [[B6_LOOPEXIT:%.*]], label [[B18]]
34; CHECK:       B6.loopexit:
35; CHECK-NEXT:    br label [[B6]]
36; CHECK:       B6:
37; CHECK-NEXT:    ret void
38; CHECK:       exit24:
39; CHECK-NEXT:    [[DOT02_LCSSA_WIDE:%.*]] = phi i64 [ [[INDVARS_IV]], [[B18]] ]
40; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[DOT02_LCSSA_WIDE]] to i32
41; CHECK-NEXT:    call void @dummy(i32 [[TMP1]])
42; CHECK-NEXT:    unreachable
43;
44Prologue:
45  br i1 undef, label %B18, label %B6
46
47B18:                                        ; preds = %B24, %Prologue
48  %.02 = phi i32 [ 0, %Prologue ], [ %tmp33, %B24 ]
49  %tmp23 = zext i32 %.02 to i64
50  call void @use(i64 %tmp23)
51  %tmp33 = add i32 %.02, 1
52  %o = getelementptr i32, i32* %a, i32 %.02
53  %v = load i32, i32* %o
54  %t = icmp eq i32 %v, 0
55  br i1 %t, label %exit24, label %B24
56
57B24:                                        ; preds = %B18
58  %t2 = icmp eq i32 %tmp33, 20
59  br i1 %t2, label %B6, label %B18
60
61B6:                                       ; preds = %Prologue
62  ret void
63
64exit24:                      ; preds = %B18
65  call void @dummy(i32 %.02)
66  unreachable
67}
68
69; Make sure that dead zext is removed and no widening happens.
70define void @loop_0_dead(i32* %a) {
71; CHECK-LABEL: @loop_0_dead(
72; CHECK-NEXT:  Prologue:
73; CHECK-NEXT:    br i1 undef, label [[B18_PREHEADER:%.*]], label [[B6:%.*]]
74; CHECK:       B18.preheader:
75; CHECK-NEXT:    br label [[B18:%.*]]
76; CHECK:       B18:
77; CHECK-NEXT:    [[DOT02:%.*]] = phi i32 [ [[TMP33:%.*]], [[B24:%.*]] ], [ 0, [[B18_PREHEADER]] ]
78; CHECK-NEXT:    [[TMP33]] = add nuw i32 [[DOT02]], 1
79; CHECK-NEXT:    [[O:%.*]] = getelementptr i32, i32* [[A:%.*]], i32 [[DOT02]]
80; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[O]]
81; CHECK-NEXT:    [[T:%.*]] = icmp eq i32 [[V]], 0
82; CHECK-NEXT:    br i1 [[T]], label [[EXIT24:%.*]], label [[B24]]
83; CHECK:       B24:
84; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[TMP33]], 20
85; CHECK-NEXT:    br i1 [[T2]], label [[B6_LOOPEXIT:%.*]], label [[B18]]
86; CHECK:       B6.loopexit:
87; CHECK-NEXT:    br label [[B6]]
88; CHECK:       B6:
89; CHECK-NEXT:    ret void
90; CHECK:       exit24:
91; CHECK-NEXT:    [[DOT02_LCSSA:%.*]] = phi i32 [ [[DOT02]], [[B18]] ]
92; CHECK-NEXT:    call void @dummy(i32 [[DOT02_LCSSA]])
93; CHECK-NEXT:    unreachable
94;
95Prologue:
96  br i1 undef, label %B18, label %B6
97
98B18:                                        ; preds = %B24, %Prologue
99  %.02 = phi i32 [ 0, %Prologue ], [ %tmp33, %B24 ]
100  %tmp23 = zext i32 %.02 to i64
101  %tmp33 = add i32 %.02, 1
102  %o = getelementptr i32, i32* %a, i32 %.02
103  %v = load i32, i32* %o
104  %t = icmp eq i32 %v, 0
105  br i1 %t, label %exit24, label %B24
106
107B24:                                        ; preds = %B18
108  %t2 = icmp eq i32 %tmp33, 20
109  br i1 %t2, label %B6, label %B18
110
111B6:                                       ; preds = %Prologue
112  ret void
113
114exit24:                      ; preds = %B18
115  call void @dummy(i32 %.02)
116  unreachable
117}
118
119define void @loop_1(i32 %lim) {
120; CHECK-LABEL: @loop_1(
121; CHECK-NEXT:  entry:
122; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp ne i32 [[LIM:%.*]], 0
123; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
124; CHECK:       loop.preheader:
125; CHECK-NEXT:    [[TMP0:%.*]] = icmp ugt i32 [[LIM]], 2
126; CHECK-NEXT:    [[UMAX:%.*]] = select i1 [[TMP0]], i32 [[LIM]], i32 2
127; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[UMAX]] to i64
128; CHECK-NEXT:    br label [[LOOP:%.*]]
129; CHECK:       loop:
130; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, [[LOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
131; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
132; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV]], -1
133; CHECK-NEXT:    call void @dummy.i64(i64 [[TMP1]])
134; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
135; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT:%.*]]
136; CHECK:       leave.loopexit:
137; CHECK-NEXT:    br label [[LEAVE]]
138; CHECK:       leave:
139; CHECK-NEXT:    ret void
140;
141  entry:
142  %entry.cond = icmp ne i32 %lim, 0
143  br i1 %entry.cond, label %loop, label %leave
144
145  loop:
146
147  %iv = phi i32 [ 1, %entry ], [ %iv.inc, %loop ]
148  %iv.inc = add i32 %iv, 1
149  %iv.inc.sub = add i32 %iv, -1
150  %iv.inc.sub.zext = zext i32 %iv.inc.sub to i64
151  call void @dummy.i64(i64 %iv.inc.sub.zext)
152  %be.cond = icmp ult i32 %iv.inc, %lim
153  br i1 %be.cond, label %loop, label %leave
154
155  leave:
156  ret void
157}
158
159declare void @dummy(i32)
160declare void @dummy.i64(i64)
161
162
163define void @loop_2(i32 %size, i32 %nsteps, i32 %hsize, i32* %lined, i8 %tmp1) {
164; CHECK-LABEL: @loop_2(
165; CHECK-NEXT:  entry:
166; CHECK-NEXT:    [[CMP215:%.*]] = icmp sgt i32 [[SIZE:%.*]], 1
167; CHECK-NEXT:    [[BC0:%.*]] = bitcast i32* [[LINED:%.*]] to i8*
168; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[SIZE]] to i64
169; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[HSIZE:%.*]] to i64
170; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[NSTEPS:%.*]], 1
171; CHECK-NEXT:    [[SMAX:%.*]] = select i1 [[TMP2]], i32 [[NSTEPS]], i32 1
172; CHECK-NEXT:    [[WIDE_TRIP_COUNT11:%.*]] = zext i32 [[SMAX]] to i64
173; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
174; CHECK:       for.body:
175; CHECK-NEXT:    [[INDVARS_IV7:%.*]] = phi i64 [ [[INDVARS_IV_NEXT8:%.*]], [[FOR_INC:%.*]] ], [ 0, [[ENTRY:%.*]] ]
176; CHECK-NEXT:    [[TMP3:%.*]] = mul nsw i64 [[INDVARS_IV7]], [[TMP0]]
177; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i64 [[TMP3]], [[TMP1]]
178; CHECK-NEXT:    br i1 [[CMP215]], label [[FOR_BODY2_PREHEADER:%.*]], label [[FOR_INC]]
179; CHECK:       for.body2.preheader:
180; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[SIZE]] to i64
181; CHECK-NEXT:    br label [[FOR_BODY2:%.*]]
182; CHECK:       for.body2:
183; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, [[FOR_BODY2_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY2]] ]
184; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i64 [[TMP4]], [[INDVARS_IV]]
185; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i8, i8* [[BC0]], i64 [[TMP5]]
186; CHECK-NEXT:    store i8 [[TMP1:%.*]], i8* [[ADD_PTR]], align 1
187; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
188; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
189; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY2]], label [[FOR_BODY3_PREHEADER:%.*]]
190; CHECK:       for.body3.preheader:
191; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[TMP4]] to i32
192; CHECK-NEXT:    [[TMP7:%.*]] = zext i32 [[TMP6]] to i64
193; CHECK-NEXT:    [[WIDE_TRIP_COUNT5:%.*]] = zext i32 [[SIZE]] to i64
194; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
195; CHECK:       for.body3:
196; CHECK-NEXT:    [[INDVARS_IV2:%.*]] = phi i64 [ 1, [[FOR_BODY3_PREHEADER]] ], [ [[INDVARS_IV_NEXT3:%.*]], [[FOR_BODY3]] ]
197; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw i64 [[TMP7]], [[INDVARS_IV2]]
198; CHECK-NEXT:    [[ADD_PTR2:%.*]] = getelementptr inbounds i8, i8* [[BC0]], i64 [[TMP8]]
199; CHECK-NEXT:    store i8 [[TMP1]], i8* [[ADD_PTR2]], align 1
200; CHECK-NEXT:    [[INDVARS_IV_NEXT3]] = add nuw nsw i64 [[INDVARS_IV2]], 1
201; CHECK-NEXT:    [[EXITCOND6:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT3]], [[WIDE_TRIP_COUNT5]]
202; CHECK-NEXT:    br i1 [[EXITCOND6]], label [[FOR_BODY3]], label [[FOR_INC_LOOPEXIT:%.*]]
203; CHECK:       for.inc.loopexit:
204; CHECK-NEXT:    br label [[FOR_INC]]
205; CHECK:       for.inc:
206; CHECK-NEXT:    [[INDVARS_IV_NEXT8]] = add nuw nsw i64 [[INDVARS_IV7]], 1
207; CHECK-NEXT:    [[EXITCOND12:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT8]], [[WIDE_TRIP_COUNT11]]
208; CHECK-NEXT:    br i1 [[EXITCOND12]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
209; CHECK:       for.end.loopexit:
210; CHECK-NEXT:    ret void
211;
212entry:
213  %cmp215 = icmp sgt i32 %size, 1
214  %bc0 = bitcast i32* %lined to i8*
215  br label %for.body
216
217for.body:
218  %j = phi i32 [ 0, %entry ], [ %inc6, %for.inc ]
219  %mul = mul nsw i32 %j, %size
220  %add = add nsw i32 %mul, %hsize
221  br i1 %cmp215, label %for.body2, label %for.inc
222
223; check that the induction variable of the inner loop has been widened after indvars.
224for.body2:
225  %k = phi i32 [ %inc, %for.body2 ], [ 1, %for.body ]
226  %add4 = add nsw i32 %add, %k
227  %idx.ext = sext i32 %add4 to i64
228  %add.ptr = getelementptr inbounds i8, i8* %bc0, i64 %idx.ext
229  store i8 %tmp1, i8* %add.ptr, align 1
230  %inc = add nsw i32 %k, 1
231  %cmp2 = icmp slt i32 %inc, %size
232  br i1 %cmp2, label %for.body2, label %for.body3
233
234; check that the induction variable of the inner loop has been widened after indvars.
235for.body3:
236  %l = phi i32 [ %inc2, %for.body3 ], [ 1, %for.body2 ]
237  %add5 = add nuw i32 %add, %l
238  %idx.ext2 = zext i32 %add5 to i64
239  %add.ptr2 = getelementptr inbounds i8, i8* %bc0, i64 %idx.ext2
240  store i8 %tmp1, i8* %add.ptr2, align 1
241  %inc2 = add nsw i32 %l, 1
242  %cmp3 = icmp slt i32 %inc2, %size
243  br i1 %cmp3, label %for.body3, label %for.inc
244
245for.inc:
246  %inc6 = add nsw i32 %j, 1
247  %cmp = icmp slt i32 %inc6, %nsteps
248  br i1 %cmp, label %for.body, label %for.end.loopexit
249
250for.end.loopexit:
251  ret void
252}
253