1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-attributes
2; RUN: opt -indvars -S %s | FileCheck %s
3
4; Test cases inspired by PR48965.
5
6; %len is zero-extended before being used to compute %p.end, which guarantees
7; the offset is positive. %i.ult.ext can be simplified.
8define i1 @can_simplify_ult_i32_ptr_len_zext(i32* %p.base, i32 %len) {
9; CHECK-LABEL: @can_simplify_ult_i32_ptr_len_zext(
10; CHECK-NEXT:  entry:
11; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[LEN:%.*]] to i64
12; CHECK-NEXT:    [[P_END:%.*]] = getelementptr inbounds i32, i32* [[P_BASE:%.*]], i64 [[EXT]]
13; CHECK-NEXT:    [[LEN_NONZERO:%.*]] = icmp ne i32 [[LEN]], 0
14; CHECK-NEXT:    br i1 [[LEN_NONZERO]], label [[HEADER_PREHEADER:%.*]], label [[TRAP:%.*]]
15; CHECK:       header.preheader:
16; CHECK-NEXT:    br label [[HEADER:%.*]]
17; CHECK:       trap.loopexit:
18; CHECK-NEXT:    br label [[TRAP]]
19; CHECK:       trap:
20; CHECK-NEXT:    ret i1 false
21; CHECK:       header:
22; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
23; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 0, [[HEADER_PREHEADER]] ]
24; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
25; CHECK-NEXT:    [[I_ULT_EXT:%.*]] = icmp ult i64 [[I]], [[EXT]]
26; CHECK-NEXT:    br i1 [[I_ULT_EXT]], label [[LATCH]], label [[TRAP_LOOPEXIT:%.*]]
27; CHECK:       latch:
28; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
29; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
30; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
31; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
32; CHECK:       exit:
33; CHECK-NEXT:    ret i1 true
34;
35entry:
36  %ext = zext i32 %len to i64
37  %p.end = getelementptr inbounds i32, i32* %p.base, i64 %ext
38  %len.nonzero = icmp ne i32 %len, 0
39  br i1 %len.nonzero, label %header, label %trap
40
41trap:
42  ret i1 false
43
44header:
45  %p = phi i32* [ %p.base, %entry ], [ %p.inc, %latch ]
46  %i = phi i64 [ 0, %entry ], [ %i.inc, %latch]
47  %i.inc = add nsw nuw i64 %i, 1
48  %i.ult.ext = icmp ult i64 %i, %ext
49  br i1 %i.ult.ext, label %latch, label %trap
50
51latch:
52  %p.inc = getelementptr inbounds i32, i32* %p, i64 1
53  %c = icmp ne i32* %p.inc, %p.end
54  store i32 0, i32* %p
55  br i1 %c, label %header, label %exit
56
57exit:
58  ret i1 true
59}
60
61; %len may be (signed) negative, %i.ult.ext cannot be simplified.
62define i1 @cannot_simplify_ult_i32_ptr_len_ult(i32* %p.base, i64 %len) {
63; CHECK-LABEL: @cannot_simplify_ult_i32_ptr_len_ult(
64; CHECK-NEXT:  entry:
65; CHECK-NEXT:    [[P_END:%.*]] = getelementptr inbounds i32, i32* [[P_BASE:%.*]], i64 [[LEN:%.*]]
66; CHECK-NEXT:    [[LEN_NONZERO:%.*]] = icmp ne i64 [[LEN]], 0
67; CHECK-NEXT:    br i1 [[LEN_NONZERO]], label [[HEADER_PREHEADER:%.*]], label [[TRAP:%.*]]
68; CHECK:       header.preheader:
69; CHECK-NEXT:    br label [[HEADER:%.*]]
70; CHECK:       trap.loopexit:
71; CHECK-NEXT:    br label [[TRAP]]
72; CHECK:       trap:
73; CHECK-NEXT:    ret i1 false
74; CHECK:       header:
75; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
76; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 0, [[HEADER_PREHEADER]] ]
77; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
78; CHECK-NEXT:    [[I_ULT_EXT:%.*]] = icmp ult i64 [[I]], [[LEN]]
79; CHECK-NEXT:    br i1 [[I_ULT_EXT]], label [[LATCH]], label [[TRAP_LOOPEXIT:%.*]]
80; CHECK:       latch:
81; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
82; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
83; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
84; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
85; CHECK:       exit:
86; CHECK-NEXT:    ret i1 true
87;
88entry:
89  %p.end = getelementptr inbounds i32, i32* %p.base, i64 %len
90  %len.nonzero = icmp ne i64 %len, 0
91  br i1 %len.nonzero, label %header, label %trap
92
93trap:
94  ret i1 false
95
96header:
97  %p = phi i32* [ %p.base, %entry ], [ %p.inc, %latch ]
98  %i = phi i64 [ 0, %entry ], [ %i.inc, %latch]
99  %i.inc = add nsw nuw i64 %i, 1
100  %i.ult.ext = icmp ult i64 %i, %len
101  br i1 %i.ult.ext, label %latch, label %trap
102
103latch:
104  %p.inc = getelementptr inbounds i32, i32* %p, i64 1
105  %c = icmp ne i32* %p.inc, %p.end
106  store i32 0, i32* %p
107  br i1 %c, label %header, label %exit
108
109exit:
110  ret i1 true
111}
112
113; Similar to can_simplify_ult_i32_ptr_len_zext, but %i has 1 as start value. %i.ult.ext cannot be simplified.
114define i1 @cannot_simplify_ult_i32_ptr_len_zext(i32* %p.base, i32 %len) {
115; CHECK-LABEL: @cannot_simplify_ult_i32_ptr_len_zext(
116; CHECK-NEXT:  entry:
117; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[LEN:%.*]] to i64
118; CHECK-NEXT:    [[P_END:%.*]] = getelementptr inbounds i32, i32* [[P_BASE:%.*]], i64 [[EXT]]
119; CHECK-NEXT:    [[LEN_NONZERO:%.*]] = icmp ne i32 [[LEN]], 0
120; CHECK-NEXT:    br i1 [[LEN_NONZERO]], label [[HEADER_PREHEADER:%.*]], label [[TRAP:%.*]]
121; CHECK:       header.preheader:
122; CHECK-NEXT:    br label [[HEADER:%.*]]
123; CHECK:       trap.loopexit:
124; CHECK-NEXT:    br label [[TRAP]]
125; CHECK:       trap:
126; CHECK-NEXT:    ret i1 false
127; CHECK:       header:
128; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
129; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 1, [[HEADER_PREHEADER]] ]
130; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
131; CHECK-NEXT:    [[I_ULT_EXT:%.*]] = icmp ult i64 [[I]], [[EXT]]
132; CHECK-NEXT:    br i1 [[I_ULT_EXT]], label [[LATCH]], label [[TRAP_LOOPEXIT:%.*]]
133; CHECK:       latch:
134; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
135; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
136; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
137; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
138; CHECK:       exit:
139; CHECK-NEXT:    ret i1 true
140;
141entry:
142  %ext = zext i32 %len to i64
143  %p.end = getelementptr inbounds i32, i32* %p.base, i64 %ext
144  %len.nonzero = icmp ne i32 %len, 0
145  br i1 %len.nonzero, label %header, label %trap
146
147trap:
148  ret i1 false
149
150header:
151  %p = phi i32* [ %p.base, %entry ], [ %p.inc, %latch ]
152  %i = phi i64 [ 1, %entry ], [ %i.inc, %latch]
153  %i.inc = add nsw nuw i64 %i, 1
154  %i.ult.ext = icmp ult i64 %i, %ext
155  br i1 %i.ult.ext, label %latch, label %trap
156
157latch:
158  %p.inc = getelementptr inbounds i32, i32* %p, i64 1
159  %c = icmp ne i32* %p.inc, %p.end
160  store i32 0, i32* %p
161  br i1 %c, label %header, label %exit
162
163exit:
164  ret i1 true
165}
166
167define i1 @can_simplify_ule_i32_ptr_len_zext(i32* %p.base, i32 %len) {
168; CHECK-LABEL: @can_simplify_ule_i32_ptr_len_zext(
169; CHECK-NEXT:  entry:
170; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[LEN:%.*]] to i64
171; CHECK-NEXT:    [[P_END:%.*]] = getelementptr inbounds i32, i32* [[P_BASE:%.*]], i64 [[EXT]]
172; CHECK-NEXT:    [[LEN_NONZERO:%.*]] = icmp ne i32 [[LEN]], 0
173; CHECK-NEXT:    br i1 [[LEN_NONZERO]], label [[HEADER_PREHEADER:%.*]], label [[TRAP:%.*]]
174; CHECK:       header.preheader:
175; CHECK-NEXT:    br label [[HEADER:%.*]]
176; CHECK:       trap.loopexit:
177; CHECK-NEXT:    br label [[TRAP]]
178; CHECK:       trap:
179; CHECK-NEXT:    ret i1 false
180; CHECK:       header:
181; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
182; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 1, [[HEADER_PREHEADER]] ]
183; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
184; CHECK-NEXT:    [[I_ULT_EXT:%.*]] = icmp ule i64 [[I]], [[EXT]]
185; CHECK-NEXT:    br i1 [[I_ULT_EXT]], label [[LATCH]], label [[TRAP_LOOPEXIT:%.*]]
186; CHECK:       latch:
187; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
188; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
189; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
190; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
191; CHECK:       exit:
192; CHECK-NEXT:    ret i1 true
193;
194entry:
195  %ext = zext i32 %len to i64
196  %p.end = getelementptr inbounds i32, i32* %p.base, i64 %ext
197  %len.nonzero = icmp ne i32 %len, 0
198  br i1 %len.nonzero, label %header, label %trap
199
200trap:
201  ret i1 false
202
203header:
204  %p = phi i32* [ %p.base, %entry ], [ %p.inc, %latch ]
205  %i = phi i64 [ 1, %entry ], [ %i.inc, %latch]
206  %i.inc = add nsw nuw i64 %i, 1
207  %i.ult.ext = icmp ule i64 %i, %ext
208  br i1 %i.ult.ext, label %latch, label %trap
209
210latch:
211  %p.inc = getelementptr inbounds i32, i32* %p, i64 1
212  %c = icmp ne i32* %p.inc, %p.end
213  store i32 0, i32* %p
214  br i1 %c, label %header, label %exit
215
216exit:
217  ret i1 true
218}
219
220; %len is zero-extended before being used to compute %p.end, which guarantees
221; the offset is positive. %i.uge.ext can be simplified.
222define i1 @can_simplify_uge_i32_ptr_len_zext(i32* %p.base, i32 %len) {
223; CHECK-LABEL: @can_simplify_uge_i32_ptr_len_zext(
224; CHECK-NEXT:  entry:
225; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[LEN:%.*]] to i64
226; CHECK-NEXT:    [[P_END:%.*]] = getelementptr inbounds i32, i32* [[P_BASE:%.*]], i64 [[EXT]]
227; CHECK-NEXT:    [[LEN_NONZERO:%.*]] = icmp ne i32 [[LEN]], 0
228; CHECK-NEXT:    br i1 [[LEN_NONZERO]], label [[HEADER_PREHEADER:%.*]], label [[TRAP:%.*]]
229; CHECK:       header.preheader:
230; CHECK-NEXT:    br label [[HEADER:%.*]]
231; CHECK:       trap.loopexit:
232; CHECK-NEXT:    br label [[TRAP]]
233; CHECK:       trap:
234; CHECK-NEXT:    ret i1 false
235; CHECK:       header:
236; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
237; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 0, [[HEADER_PREHEADER]] ]
238; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
239; CHECK-NEXT:    [[I_UGE_EXT:%.*]] = icmp uge i64 [[I]], [[EXT]]
240; CHECK-NEXT:    br i1 [[I_UGE_EXT]], label [[TRAP_LOOPEXIT:%.*]], label [[LATCH]]
241; CHECK:       latch:
242; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
243; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
244; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
245; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
246; CHECK:       exit:
247; CHECK-NEXT:    ret i1 true
248;
249entry:
250  %ext = zext i32 %len to i64
251  %p.end = getelementptr inbounds i32, i32* %p.base, i64 %ext
252  %len.nonzero = icmp ne i32 %len, 0
253  br i1 %len.nonzero, label %header, label %trap
254
255trap:
256  ret i1 false
257
258header:
259  %p = phi i32* [ %p.base, %entry ], [ %p.inc, %latch ]
260  %i = phi i64 [ 0, %entry ], [ %i.inc, %latch]
261  %i.inc = add nsw nuw i64 %i, 1
262  %i.uge.ext = icmp uge i64 %i, %ext
263  br i1 %i.uge.ext, label %trap, label %latch
264
265latch:
266  %p.inc = getelementptr inbounds i32, i32* %p, i64 1
267  %c = icmp ne i32* %p.inc, %p.end
268  store i32 0, i32* %p
269  br i1 %c, label %header, label %exit
270
271exit:
272  ret i1 true
273}
274
275define i1 @cannot_simplify_uge_i32_ptr_len(i32* %p.base, i64 %len) {
276; CHECK-LABEL: @cannot_simplify_uge_i32_ptr_len(
277; CHECK-NEXT:  entry:
278; CHECK-NEXT:    [[P_END:%.*]] = getelementptr inbounds i32, i32* [[P_BASE:%.*]], i64 [[LEN:%.*]]
279; CHECK-NEXT:    [[LEN_NONZERO:%.*]] = icmp ne i64 [[LEN]], 0
280; CHECK-NEXT:    br i1 [[LEN_NONZERO]], label [[HEADER_PREHEADER:%.*]], label [[TRAP:%.*]]
281; CHECK:       header.preheader:
282; CHECK-NEXT:    br label [[HEADER:%.*]]
283; CHECK:       trap.loopexit:
284; CHECK-NEXT:    br label [[TRAP]]
285; CHECK:       trap:
286; CHECK-NEXT:    ret i1 false
287; CHECK:       header:
288; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
289; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 0, [[HEADER_PREHEADER]] ]
290; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
291; CHECK-NEXT:    [[I_UGE_EXT:%.*]] = icmp uge i64 [[I]], [[LEN]]
292; CHECK-NEXT:    br i1 [[I_UGE_EXT]], label [[TRAP_LOOPEXIT:%.*]], label [[LATCH]]
293; CHECK:       latch:
294; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
295; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
296; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
297; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
298; CHECK:       exit:
299; CHECK-NEXT:    ret i1 true
300;
301entry:
302  %p.end = getelementptr inbounds i32, i32* %p.base, i64 %len
303  %len.nonzero = icmp ne i64 %len, 0
304  br i1 %len.nonzero, label %header, label %trap
305
306trap:
307  ret i1 false
308
309header:
310  %p = phi i32* [ %p.base, %entry ], [ %p.inc, %latch ]
311  %i = phi i64 [ 0, %entry ], [ %i.inc, %latch]
312  %i.inc = add nsw nuw i64 %i, 1
313  %i.uge.ext = icmp uge i64 %i, %len
314  br i1 %i.uge.ext, label %trap, label %latch
315
316latch:
317  %p.inc = getelementptr inbounds i32, i32* %p, i64 1
318  %c = icmp ne i32* %p.inc, %p.end
319  store i32 0, i32* %p
320  br i1 %c, label %header, label %exit
321
322exit:
323  ret i1 true
324}
325
326define i1 @cannot_simplify_uge_i32_ptr_len_zext_step_2(i32* %p.base, i32 %len) {
327; CHECK-LABEL: @cannot_simplify_uge_i32_ptr_len_zext_step_2(
328; CHECK-NEXT:  entry:
329; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[LEN:%.*]] to i64
330; CHECK-NEXT:    [[P_END:%.*]] = getelementptr inbounds i32, i32* [[P_BASE:%.*]], i64 [[EXT]]
331; CHECK-NEXT:    [[LEN_NONZERO:%.*]] = icmp ne i32 [[LEN]], 0
332; CHECK-NEXT:    br i1 [[LEN_NONZERO]], label [[HEADER_PREHEADER:%.*]], label [[TRAP:%.*]]
333; CHECK:       header.preheader:
334; CHECK-NEXT:    br label [[HEADER:%.*]]
335; CHECK:       trap.loopexit:
336; CHECK-NEXT:    br label [[TRAP]]
337; CHECK:       trap:
338; CHECK-NEXT:    ret i1 false
339; CHECK:       header:
340; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
341; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 0, [[HEADER_PREHEADER]] ]
342; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 2
343; CHECK-NEXT:    [[I_UGE_EXT:%.*]] = icmp uge i64 [[I]], [[EXT]]
344; CHECK-NEXT:    br i1 [[I_UGE_EXT]], label [[TRAP_LOOPEXIT:%.*]], label [[LATCH]]
345; CHECK:       latch:
346; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
347; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
348; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
349; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
350; CHECK:       exit:
351; CHECK-NEXT:    ret i1 true
352;
353entry:
354  %ext = zext i32 %len to i64
355  %p.end = getelementptr inbounds i32, i32* %p.base, i64 %ext
356  %len.nonzero = icmp ne i32 %len, 0
357  br i1 %len.nonzero, label %header, label %trap
358
359trap:
360  ret i1 false
361
362header:
363  %p = phi i32* [ %p.base, %entry ], [ %p.inc, %latch ]
364  %i = phi i64 [ 0, %entry ], [ %i.inc, %latch]
365  %i.inc = add nsw nuw i64 %i, 2
366  %i.uge.ext = icmp uge i64 %i, %ext
367  br i1 %i.uge.ext, label %trap, label %latch
368
369latch:
370  %p.inc = getelementptr inbounds i32, i32* %p, i64 1
371  %c = icmp ne i32* %p.inc, %p.end
372  store i32 0, i32* %p
373  br i1 %c, label %header, label %exit
374
375exit:
376  ret i1 true
377}
378