1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -indvars -S < %s | FileCheck %s
3
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"
5
6@X = external global [0 x double]
7
8; Indvars should be able to simplify simple comparisons involving
9; induction variables.
10
11define void @foo(i64 %n, i32* nocapture %p) nounwind {
12; CHECK-LABEL: @foo(
13; CHECK-NEXT:  entry:
14; CHECK-NEXT:    [[CMP9:%.*]] = icmp sgt i64 [[N:%.*]], 0
15; CHECK-NEXT:    br i1 [[CMP9]], label [[PRE:%.*]], label [[RETURN:%.*]]
16; CHECK:       pre:
17; CHECK-NEXT:    [[T3:%.*]] = load i32, i32* [[P:%.*]], align 4
18; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp ne i32 [[T3]], 0
19; CHECK-NEXT:    br label [[LOOP:%.*]]
20; CHECK:       loop:
21; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 0, [[PRE]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
22; CHECK-NEXT:    [[COND:%.*]] = and i1 [[TOBOOL_NOT]], true
23; CHECK-NEXT:    br i1 [[COND]], label [[IF_THEN:%.*]], label [[FOR_INC]]
24; CHECK:       if.then:
25; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr [0 x double], [0 x double]* @X, i64 0, i64 [[I]]
26; CHECK-NEXT:    store double 3.200000e+00, double* [[ARRAYIDX]], align 8
27; CHECK-NEXT:    br label [[FOR_INC]]
28; CHECK:       for.inc:
29; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[I]], 1
30; CHECK-NEXT:    [[EXITCOND1:%.*]] = icmp eq i64 [[INC]], [[N]]
31; CHECK-NEXT:    br i1 [[EXITCOND1]], label [[RETURN_LOOPEXIT:%.*]], label [[LOOP]]
32; CHECK:       return.loopexit:
33; CHECK-NEXT:    br label [[RETURN]]
34; CHECK:       return:
35; CHECK-NEXT:    ret void
36;
37entry:
38  %cmp9 = icmp sgt i64 %n, 0
39  br i1 %cmp9, label %pre, label %return
40
41pre:
42  %t3 = load i32, i32* %p
43  %tobool.not = icmp ne i32 %t3, 0
44  br label %loop
45
46loop:
47  %i = phi i64 [ 0, %pre ], [ %inc, %for.inc ]
48  %cmp6 = icmp slt i64 %i, %n
49  %cond = and i1 %tobool.not, %cmp6
50  br i1 %cond, label %if.then, label %for.inc
51
52if.then:
53  %arrayidx = getelementptr [0 x double], [0 x double]* @X, i64 0, i64 %i
54  store double 3.200000e+00, double* %arrayidx
55  br label %for.inc
56
57for.inc:
58  %inc = add nsw i64 %i, 1
59  %exitcond = icmp sge i64 %inc, %n
60  br i1 %exitcond, label %return, label %loop
61
62return:
63  ret void
64}
65
66; Don't eliminate an icmp that's contributing to the loop exit test though.
67
68define i32 @_ZNK4llvm5APInt3ultERKS0_(i32 %tmp2.i1, i64** %tmp65, i64** %tmp73, i64** %tmp82, i64** %tmp90) {
69; CHECK-LABEL: @_ZNK4llvm5APInt3ultERKS0_(
70; CHECK-NEXT:  entry:
71; CHECK-NEXT:    br label [[BB18:%.*]]
72; CHECK:       bb13:
73; CHECK-NEXT:    [[TMP66:%.*]] = load i64*, i64** [[TMP65:%.*]], align 4
74; CHECK-NEXT:    [[TMP68:%.*]] = getelementptr inbounds i64, i64* [[TMP66]], i32 [[I:%.*]]
75; CHECK-NEXT:    [[TMP69:%.*]] = load i64, i64* [[TMP68]], align 4
76; CHECK-NEXT:    [[TMP74:%.*]] = load i64*, i64** [[TMP73:%.*]], align 4
77; CHECK-NEXT:    [[TMP76:%.*]] = getelementptr inbounds i64, i64* [[TMP74]], i32 [[I]]
78; CHECK-NEXT:    [[TMP77:%.*]] = load i64, i64* [[TMP76]], align 4
79; CHECK-NEXT:    [[TMP78:%.*]] = icmp ugt i64 [[TMP69]], [[TMP77]]
80; CHECK-NEXT:    br i1 [[TMP78]], label [[BB20_LOOPEXIT:%.*]], label [[BB15:%.*]]
81; CHECK:       bb15:
82; CHECK-NEXT:    [[TMP83:%.*]] = load i64*, i64** [[TMP82:%.*]], align 4
83; CHECK-NEXT:    [[TMP85:%.*]] = getelementptr inbounds i64, i64* [[TMP83]], i32 [[I]]
84; CHECK-NEXT:    [[TMP86:%.*]] = load i64, i64* [[TMP85]], align 4
85; CHECK-NEXT:    [[TMP91:%.*]] = load i64*, i64** [[TMP90:%.*]], align 4
86; CHECK-NEXT:    [[TMP93:%.*]] = getelementptr inbounds i64, i64* [[TMP91]], i32 [[I]]
87; CHECK-NEXT:    [[TMP94:%.*]] = load i64, i64* [[TMP93]], align 4
88; CHECK-NEXT:    [[TMP95:%.*]] = icmp ult i64 [[TMP86]], [[TMP94]]
89; CHECK-NEXT:    br i1 [[TMP95]], label [[BB20_LOOPEXIT]], label [[BB17:%.*]]
90; CHECK:       bb17:
91; CHECK-NEXT:    [[TMP97:%.*]] = add nsw i32 [[I]], -1
92; CHECK-NEXT:    br label [[BB18]]
93; CHECK:       bb18:
94; CHECK-NEXT:    [[I]] = phi i32 [ [[TMP2_I1:%.*]], [[ENTRY:%.*]] ], [ [[TMP97]], [[BB17]] ]
95; CHECK-NEXT:    [[TMP99:%.*]] = icmp sgt i32 [[I]], -1
96; CHECK-NEXT:    br i1 [[TMP99]], label [[BB13:%.*]], label [[BB20_LOOPEXIT]]
97; CHECK:       bb20.loopexit:
98; CHECK-NEXT:    [[TMP_0_PH:%.*]] = phi i32 [ 0, [[BB18]] ], [ 1, [[BB15]] ], [ 0, [[BB13]] ]
99; CHECK-NEXT:    ret i32 [[TMP_0_PH]]
100;
101entry:
102  br label %bb18
103
104bb13:
105  %tmp66 = load i64*, i64** %tmp65, align 4
106  %tmp68 = getelementptr inbounds i64, i64* %tmp66, i32 %i
107  %tmp69 = load i64, i64* %tmp68, align 4
108  %tmp74 = load i64*, i64** %tmp73, align 4
109  %tmp76 = getelementptr inbounds i64, i64* %tmp74, i32 %i
110  %tmp77 = load i64, i64* %tmp76, align 4
111  %tmp78 = icmp ugt i64 %tmp69, %tmp77
112  br i1 %tmp78, label %bb20.loopexit, label %bb15
113
114bb15:
115  %tmp83 = load i64*, i64** %tmp82, align 4
116  %tmp85 = getelementptr inbounds i64, i64* %tmp83, i32 %i
117  %tmp86 = load i64, i64* %tmp85, align 4
118  %tmp91 = load i64*, i64** %tmp90, align 4
119  %tmp93 = getelementptr inbounds i64, i64* %tmp91, i32 %i
120  %tmp94 = load i64, i64* %tmp93, align 4
121  %tmp95 = icmp ult i64 %tmp86, %tmp94
122  br i1 %tmp95, label %bb20.loopexit, label %bb17
123
124bb17:
125  %tmp97 = add nsw i32 %i, -1
126  br label %bb18
127
128bb18:
129  %i = phi i32 [ %tmp2.i1, %entry ], [ %tmp97, %bb17 ]
130  %tmp99 = icmp sgt i32 %i, -1
131  br i1 %tmp99, label %bb13, label %bb20.loopexit
132
133bb20.loopexit:
134  %tmp.0.ph = phi i32 [ 0, %bb18 ], [ 1, %bb15 ], [ 0, %bb13 ]
135  ret i32 %tmp.0.ph
136}
137
138; Indvars should eliminate the icmp here.
139
140
141define void @func_10() nounwind {
142; CHECK-LABEL: @func_10(
143; CHECK-NEXT:  entry:
144; CHECK-NEXT:    br label [[LOOP:%.*]]
145; CHECK:       loop:
146; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
147; CHECK-NEXT:    store i64 [[INDVARS_IV]], i64* null, align 8
148; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
149; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[RETURN:%.*]]
150; CHECK:       return:
151; CHECK-NEXT:    ret void
152;
153entry:
154  br label %loop
155
156loop:
157  %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
158  %t0 = icmp slt i32 %i, 0
159  %t1 = zext i1 %t0 to i32
160  %t2 = add i32 %t1, %i
161  %u3 = zext i32 %t2 to i64
162  store i64 %u3, i64* null
163  %i.next = add i32 %i, 1
164  br i1 undef, label %loop, label %return
165
166return:
167  ret void
168}
169
170; PR14432
171; Indvars should not turn the second loop into an infinite one.
172
173
174define i32 @func_11() nounwind uwtable {
175; CHECK-LABEL: @func_11(
176; CHECK-NEXT:  entry:
177; CHECK-NEXT:    br label [[FORCOND:%.*]]
178; CHECK:       forcond:
179; CHECK-NEXT:    br i1 false, label [[NOASSERT:%.*]], label [[FORCOND38_PREHEADER:%.*]]
180; CHECK:       forcond38.preheader:
181; CHECK-NEXT:    br label [[FORCOND38:%.*]]
182; CHECK:       noassert:
183; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
184; CHECK:       assert33:
185; CHECK-NEXT:    tail call void @llvm.trap()
186; CHECK-NEXT:    unreachable
187; CHECK:       forcond38:
188; CHECK-NEXT:    br i1 false, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
189; CHECK:       noassert68:
190; CHECK-NEXT:    br i1 true, label [[FORCOND38]], label [[ASSERT77:%.*]]
191; CHECK:       assert77:
192; CHECK-NEXT:    tail call void @llvm.trap()
193; CHECK-NEXT:    unreachable
194; CHECK:       unrolledend:
195; CHECK-NEXT:    ret i32 0
196;
197entry:
198  br label %forcond
199
200forcond:                                          ; preds = %noassert, %entry
201  %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
202  %tmp5 = icmp slt i32 %__key6.0, 10
203  br i1 %tmp5, label %noassert, label %forcond38.preheader
204
205forcond38.preheader:                              ; preds = %forcond
206  br label %forcond38
207
208noassert:                                         ; preds = %forbody
209  %tmp13 = sdiv i32 -32768, %__key6.0
210  %tmp2936 = shl i32 %tmp13, 24
211  %sext23 = shl i32 %tmp13, 24
212  %tmp32 = icmp eq i32 %tmp2936, %sext23
213  %tmp37 = add i32 %__key6.0, 1
214  br i1 %tmp32, label %forcond, label %assert33
215
216assert33:                                         ; preds = %noassert
217  tail call void @llvm.trap()
218  unreachable
219
220forcond38:                                        ; preds = %noassert68, %forcond38.preheader
221  %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
222  %tmp46 = icmp slt i32 %__key8.0, 10
223  br i1 %tmp46, label %noassert68, label %unrolledend
224
225noassert68:                                       ; preds = %forbody39
226  %tmp57 = sdiv i32 -32768, %__key8.0
227  %sext34 = shl i32 %tmp57, 16
228  %sext21 = shl i32 %tmp57, 16
229  %tmp76 = icmp eq i32 %sext34, %sext21
230  %tmp81 = add i32 %__key8.0, 1
231  br i1 %tmp76, label %forcond38, label %assert77
232
233assert77:                                         ; preds = %noassert68
234  tail call void @llvm.trap()
235  unreachable
236
237unrolledend:                                      ; preds = %forcond38
238  ret i32 0
239}
240
241define i32 @func_11_flipped() nounwind uwtable {
242; CHECK-LABEL: @func_11_flipped(
243; CHECK-NEXT:  entry:
244; CHECK-NEXT:    br label [[FORCOND:%.*]]
245; CHECK:       forcond:
246; CHECK-NEXT:    br i1 true, label [[FORCOND38_PREHEADER:%.*]], label [[NOASSERT:%.*]]
247; CHECK:       forcond38.preheader:
248; CHECK-NEXT:    br label [[FORCOND38:%.*]]
249; CHECK:       noassert:
250; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
251; CHECK:       assert33:
252; CHECK-NEXT:    tail call void @llvm.trap()
253; CHECK-NEXT:    unreachable
254; CHECK:       forcond38:
255; CHECK-NEXT:    br i1 false, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
256; CHECK:       noassert68:
257; CHECK-NEXT:    br i1 true, label [[FORCOND38]], label [[ASSERT77:%.*]]
258; CHECK:       assert77:
259; CHECK-NEXT:    tail call void @llvm.trap()
260; CHECK-NEXT:    unreachable
261; CHECK:       unrolledend:
262; CHECK-NEXT:    ret i32 0
263;
264entry:
265  br label %forcond
266
267forcond:                                          ; preds = %noassert, %entry
268  %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
269  %tmp5 = icmp sge i32 %__key6.0, 10
270  br i1 %tmp5, label %forcond38.preheader, label %noassert
271
272forcond38.preheader:                              ; preds = %forcond
273  br label %forcond38
274
275noassert:                                         ; preds = %forbody
276  %tmp13 = sdiv i32 -32768, %__key6.0
277  %tmp2936 = shl i32 %tmp13, 24
278  %sext23 = shl i32 %tmp13, 24
279  %tmp32 = icmp eq i32 %tmp2936, %sext23
280  %tmp37 = add i32 %__key6.0, 1
281  br i1 %tmp32, label %forcond, label %assert33
282
283assert33:                                         ; preds = %noassert
284  tail call void @llvm.trap()
285  unreachable
286
287forcond38:                                        ; preds = %noassert68, %forcond38.preheader
288  %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
289  %tmp46 = icmp slt i32 %__key8.0, 10
290  br i1 %tmp46, label %noassert68, label %unrolledend
291
292noassert68:                                       ; preds = %forbody39
293  %tmp57 = sdiv i32 -32768, %__key8.0
294  %sext34 = shl i32 %tmp57, 16
295  %sext21 = shl i32 %tmp57, 16
296  %tmp76 = icmp eq i32 %sext34, %sext21
297  %tmp81 = add i32 %__key8.0, 1
298  br i1 %tmp76, label %forcond38, label %assert77
299
300assert77:                                         ; preds = %noassert68
301  tail call void @llvm.trap()
302  unreachable
303
304unrolledend:                                      ; preds = %forcond38
305  ret i32 0
306}
307
308declare void @llvm.trap() noreturn nounwind
309
310; In this case the second loop only has a single iteration, fold the header away
311define i32 @func_12() nounwind uwtable {
312; CHECK-LABEL: @func_12(
313; CHECK-NEXT:  entry:
314; CHECK-NEXT:    br label [[FORCOND:%.*]]
315; CHECK:       forcond:
316; CHECK-NEXT:    br i1 false, label [[NOASSERT:%.*]], label [[FORCOND38_PREHEADER:%.*]]
317; CHECK:       forcond38.preheader:
318; CHECK-NEXT:    br label [[FORCOND38:%.*]]
319; CHECK:       noassert:
320; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
321; CHECK:       assert33:
322; CHECK-NEXT:    tail call void @llvm.trap()
323; CHECK-NEXT:    unreachable
324; CHECK:       forcond38:
325; CHECK-NEXT:    br i1 true, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
326; CHECK:       noassert68:
327; CHECK-NEXT:    br i1 false, label [[FORCOND38]], label [[ASSERT77:%.*]]
328; CHECK:       assert77:
329; CHECK-NEXT:    tail call void @llvm.trap()
330; CHECK-NEXT:    unreachable
331; CHECK:       unrolledend:
332; CHECK-NEXT:    ret i32 0
333;
334entry:
335  br label %forcond
336
337forcond:                                          ; preds = %noassert, %entry
338  %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
339  %tmp5 = icmp slt i32 %__key6.0, 10
340  br i1 %tmp5, label %noassert, label %forcond38.preheader
341
342forcond38.preheader:                              ; preds = %forcond
343  br label %forcond38
344
345noassert:                                         ; preds = %forbody
346  %tmp13 = sdiv i32 -32768, %__key6.0
347  %tmp2936 = shl i32 %tmp13, 24
348  %sext23 = shl i32 %tmp13, 24
349  %tmp32 = icmp eq i32 %tmp2936, %sext23
350  %tmp37 = add i32 %__key6.0, 1
351  br i1 %tmp32, label %forcond, label %assert33
352
353assert33:                                         ; preds = %noassert
354  tail call void @llvm.trap()
355  unreachable
356
357forcond38:                                        ; preds = %noassert68, %forcond38.preheader
358  %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
359  %tmp46 = icmp slt i32 %__key8.0, 10
360  br i1 %tmp46, label %noassert68, label %unrolledend
361
362noassert68:                                       ; preds = %forbody39
363  %tmp57 = sdiv i32 -32768, %__key8.0
364  %sext34 = shl i32 %tmp57, 16
365  %sext21 = shl i32 %tmp57, 16
366  %tmp76 = icmp ne i32 %sext34, %sext21
367  %tmp81 = add i32 %__key8.0, 1
368  br i1 %tmp76, label %forcond38, label %assert77
369
370assert77:                                         ; preds = %noassert68
371  tail call void @llvm.trap()
372  unreachable
373
374unrolledend:                                      ; preds = %forcond38
375  ret i32 0
376}
377
378declare void @side_effect()
379
380define void @func_13(i32* %len.ptr) {
381; CHECK-LABEL: @func_13(
382; CHECK-NEXT:  entry:
383; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0:![0-9]+]]
384; CHECK-NEXT:    [[LEN_IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0
385; CHECK-NEXT:    br i1 [[LEN_IS_ZERO]], label [[LEAVE:%.*]], label [[LOOP_PREHEADER:%.*]]
386; CHECK:       loop.preheader:
387; CHECK-NEXT:    br label [[LOOP:%.*]]
388; CHECK:       loop:
389; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
390; CHECK-NEXT:    call void @side_effect()
391; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
392; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
393; CHECK:       be:
394; CHECK-NEXT:    call void @side_effect()
395; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LEN]]
396; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
397; CHECK:       leave.loopexit:
398; CHECK-NEXT:    br label [[LEAVE]]
399; CHECK:       leave:
400; CHECK-NEXT:    ret void
401;
402entry:
403  %len = load i32, i32* %len.ptr, !range !0
404  %len.sub.1 = add i32 %len, -1
405  %len.is.zero = icmp eq i32 %len, 0
406  br i1 %len.is.zero, label %leave, label %loop
407
408loop:
409  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
410  call void @side_effect()
411  %iv.inc = add i32 %iv, 1
412  %iv.cmp = icmp ult i32 %iv, %len
413  br i1 %iv.cmp, label %be, label %leave
414
415be:
416  call void @side_effect()
417  %be.cond = icmp ult i32 %iv, %len.sub.1
418  br i1 %be.cond, label %loop, label %leave
419
420leave:
421  ret void
422}
423
424define void @func_14(i32* %len.ptr) {
425; CHECK-LABEL: @func_14(
426; CHECK-NEXT:  entry:
427; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
428; CHECK-NEXT:    [[LEN_IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0
429; CHECK-NEXT:    [[LEN_IS_INT_MIN:%.*]] = icmp eq i32 [[LEN]], -2147483648
430; CHECK-NEXT:    [[NO_ENTRY:%.*]] = or i1 [[LEN_IS_ZERO]], [[LEN_IS_INT_MIN]]
431; CHECK-NEXT:    br i1 [[NO_ENTRY]], label [[LEAVE:%.*]], label [[LOOP_PREHEADER:%.*]]
432; CHECK:       loop.preheader:
433; CHECK-NEXT:    br label [[LOOP:%.*]]
434; CHECK:       loop:
435; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
436; CHECK-NEXT:    call void @side_effect()
437; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
438; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
439; CHECK:       be:
440; CHECK-NEXT:    call void @side_effect()
441; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LEN]]
442; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
443; CHECK:       leave.loopexit:
444; CHECK-NEXT:    br label [[LEAVE]]
445; CHECK:       leave:
446; CHECK-NEXT:    ret void
447;
448entry:
449  %len = load i32, i32* %len.ptr, !range !0
450  %len.sub.1 = add i32 %len, -1
451  %len.is.zero = icmp eq i32 %len, 0
452  %len.is.int_min = icmp eq i32 %len, 2147483648
453  %no.entry = or i1 %len.is.zero, %len.is.int_min
454  br i1 %no.entry, label %leave, label %loop
455
456loop:
457  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
458  call void @side_effect()
459  %iv.inc = add i32 %iv, 1
460  %iv.cmp = icmp slt i32 %iv, %len
461  br i1 %iv.cmp, label %be, label %leave
462
463be:
464  call void @side_effect()
465  %be.cond = icmp slt i32 %iv, %len.sub.1
466  br i1 %be.cond, label %loop, label %leave
467
468leave:
469  ret void
470}
471
472define void @func_15(i32* %len.ptr) {
473; CHECK-LABEL: @func_15(
474; CHECK-NEXT:  entry:
475; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
476; CHECK-NEXT:    [[LEN_ADD_1:%.*]] = add i32 [[LEN]], 1
477; CHECK-NEXT:    [[LEN_ADD_1_IS_ZERO:%.*]] = icmp eq i32 [[LEN_ADD_1]], 0
478; CHECK-NEXT:    br i1 [[LEN_ADD_1_IS_ZERO]], label [[LEAVE:%.*]], label [[LOOP_PREHEADER:%.*]]
479; CHECK:       loop.preheader:
480; CHECK-NEXT:    br label [[LOOP:%.*]]
481; CHECK:       loop:
482; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
483; CHECK-NEXT:    call void @side_effect()
484; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
485; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
486; CHECK:       be:
487; CHECK-NEXT:    call void @side_effect()
488; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LEN_ADD_1]]
489; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
490; CHECK:       leave.loopexit:
491; CHECK-NEXT:    br label [[LEAVE]]
492; CHECK:       leave:
493; CHECK-NEXT:    ret void
494;
495entry:
496  %len = load i32, i32* %len.ptr, !range !0
497  %len.add.1 = add i32 %len, 1
498  %len.add.1.is.zero = icmp eq i32 %len.add.1, 0
499  br i1 %len.add.1.is.zero, label %leave, label %loop
500
501loop:
502  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
503  call void @side_effect()
504  %iv.inc = add i32 %iv, 1
505  %iv.cmp = icmp ult i32 %iv, %len.add.1
506  br i1 %iv.cmp, label %be, label %leave
507
508be:
509  call void @side_effect()
510  %be.cond = icmp ult i32 %iv, %len
511  br i1 %be.cond, label %loop, label %leave
512
513leave:
514  ret void
515}
516
517define void @func_16(i32* %len.ptr) {
518; CHECK-LABEL: @func_16(
519; CHECK-NEXT:  entry:
520; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
521; CHECK-NEXT:    [[LEN_ADD_5:%.*]] = add i32 [[LEN]], 5
522; CHECK-NEXT:    [[ENTRY_COND_0:%.*]] = icmp slt i32 [[LEN]], 2147483643
523; CHECK-NEXT:    [[ENTRY_COND_1:%.*]] = icmp slt i32 4, [[LEN_ADD_5]]
524; CHECK-NEXT:    [[ENTRY_COND:%.*]] = and i1 [[ENTRY_COND_0]], [[ENTRY_COND_1]]
525; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
526; CHECK:       loop.preheader:
527; CHECK-NEXT:    [[TMP0:%.*]] = add nuw nsw i32 [[LEN]], 1
528; CHECK-NEXT:    br label [[LOOP:%.*]]
529; CHECK:       loop:
530; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
531; CHECK-NEXT:    call void @side_effect()
532; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
533; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
534; CHECK:       be:
535; CHECK-NEXT:    call void @side_effect()
536; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[TMP0]]
537; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
538; CHECK:       leave.loopexit:
539; CHECK-NEXT:    br label [[LEAVE]]
540; CHECK:       leave:
541; CHECK-NEXT:    ret void
542;
543entry:
544  %len = load i32, i32* %len.ptr, !range !0
545  %len.add.5 = add i32 %len, 5
546  %entry.cond.0 = icmp slt i32 %len, 2147483643
547  %entry.cond.1 = icmp slt i32 4, %len.add.5
548  %entry.cond = and i1 %entry.cond.0, %entry.cond.1
549  br i1 %entry.cond, label %loop, label %leave
550
551loop:
552  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
553  call void @side_effect()
554  %iv.inc = add i32 %iv, 1
555  %iv.add.4 = add i32 %iv, 4
556  %iv.cmp = icmp slt i32 %iv.add.4, %len.add.5
557  br i1 %iv.cmp, label %be, label %leave
558
559be:
560  call void @side_effect()
561  %be.cond = icmp slt i32 %iv, %len
562  br i1 %be.cond, label %loop, label %leave
563
564leave:
565  ret void
566}
567
568define void @func_17(i32* %len.ptr) {
569; CHECK-LABEL: @func_17(
570; CHECK-NEXT:  entry:
571; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4
572; CHECK-NEXT:    [[LEN_ADD_5:%.*]] = add i32 [[LEN]], -5
573; CHECK-NEXT:    [[ENTRY_COND_0:%.*]] = icmp slt i32 [[LEN]], -2147483643
574; CHECK-NEXT:    [[ENTRY_COND_1:%.*]] = icmp slt i32 -6, [[LEN_ADD_5]]
575; CHECK-NEXT:    [[ENTRY_COND:%.*]] = and i1 [[ENTRY_COND_0]], [[ENTRY_COND_1]]
576; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
577; CHECK:       loop.preheader:
578; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LEN]], i32 0)
579; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[SMAX]], -5
580; CHECK-NEXT:    br label [[LOOP:%.*]]
581; CHECK:       loop:
582; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ -6, [[LOOP_PREHEADER]] ]
583; CHECK-NEXT:    call void @side_effect()
584; CHECK-NEXT:    [[IV_INC]] = add nsw i32 [[IV]], 1
585; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
586; CHECK:       be:
587; CHECK-NEXT:    call void @side_effect()
588; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[TMP0]]
589; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
590; CHECK:       leave.loopexit:
591; CHECK-NEXT:    br label [[LEAVE]]
592; CHECK:       leave:
593; CHECK-NEXT:    ret void
594;
595entry:
596  %len = load i32, i32* %len.ptr
597  %len.add.5 = add i32 %len, -5
598  %entry.cond.0 = icmp slt i32 %len, 2147483653 ;; 2147483653 == INT_MIN - (-5)
599  %entry.cond.1 = icmp slt i32 -6, %len.add.5
600  %entry.cond = and i1 %entry.cond.0, %entry.cond.1
601  br i1 %entry.cond, label %loop, label %leave
602
603loop:
604  %iv.2 = phi i32 [ 0, %entry ], [ %iv.2.inc, %be ]
605  %iv = phi i32 [ -6, %entry ], [ %iv.inc, %be ]
606  call void @side_effect()
607  %iv.inc = add i32 %iv, 1
608  %iv.2.inc = add i32 %iv.2, 1
609  %iv.cmp = icmp slt i32 %iv, %len.add.5
610
611; Deduces {-5,+,1} s< (-5 + %len) from {0,+,1} < %len
612; since %len s< INT_MIN - (-5) from the entry condition
613  br i1 %iv.cmp, label %be, label %leave
614
615be:
616  call void @side_effect()
617  %be.cond = icmp slt i32 %iv.2, %len
618  br i1 %be.cond, label %loop, label %leave
619
620leave:
621  ret void
622}
623
624define i1 @func_18(i16* %tmp20, i32* %len.addr) {
625; CHECK-LABEL: @func_18(
626; CHECK-NEXT:  entry:
627; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_ADDR:%.*]], align 4, !range [[RNG0]]
628; CHECK-NEXT:    [[TMP18:%.*]] = icmp eq i32 [[LEN]], 0
629; CHECK-NEXT:    br i1 [[TMP18]], label [[BB2:%.*]], label [[BB0_PREHEADER:%.*]]
630; CHECK:       bb0.preheader:
631; CHECK-NEXT:    br label [[BB0:%.*]]
632; CHECK:       bb0:
633; CHECK-NEXT:    [[VAR_0_IN:%.*]] = phi i32 [ [[VAR_0:%.*]], [[BB1:%.*]] ], [ [[LEN]], [[BB0_PREHEADER]] ]
634; CHECK-NEXT:    [[VAR_1:%.*]] = phi i32 [ [[TMP30:%.*]], [[BB1]] ], [ 0, [[BB0_PREHEADER]] ]
635; CHECK-NEXT:    [[VAR_0]] = add nsw i32 [[VAR_0_IN]], -1
636; CHECK-NEXT:    br i1 true, label [[STAY:%.*]], label [[BB2_LOOPEXIT:%.*]]
637; CHECK:       stay:
638; CHECK-NEXT:    [[TMP25:%.*]] = getelementptr inbounds i16, i16* [[TMP20:%.*]], i32 [[VAR_1]]
639; CHECK-NEXT:    [[TMP26:%.*]] = load i16, i16* [[TMP25]], align 2
640; CHECK-NEXT:    [[TMP29:%.*]] = icmp eq i16 [[TMP26]], 0
641; CHECK-NEXT:    br i1 [[TMP29]], label [[BB1]], label [[BB2_LOOPEXIT]]
642; CHECK:       bb1:
643; CHECK-NEXT:    [[TMP30]] = add nuw i32 [[VAR_1]], 1
644; CHECK-NEXT:    [[TMP31:%.*]] = icmp eq i32 [[VAR_0]], 0
645; CHECK-NEXT:    br i1 [[TMP31]], label [[BB3:%.*]], label [[BB0]]
646; CHECK:       bb2.loopexit:
647; CHECK-NEXT:    br label [[BB2]]
648; CHECK:       bb2:
649; CHECK-NEXT:    ret i1 false
650; CHECK:       bb3:
651; CHECK-NEXT:    ret i1 true
652;
653entry:
654  %len = load i32, i32* %len.addr, !range !0
655  %tmp18 = icmp eq i32 %len, 0
656  br i1 %tmp18, label %bb2, label %bb0.preheader
657
658bb0.preheader:
659  br label %bb0
660
661bb0:
662  %var_0.in = phi i32 [ %var_0, %bb1 ], [ %len, %bb0.preheader ]
663  %var_1 = phi i32 [ %tmp30, %bb1 ], [ 0, %bb0.preheader ]
664  %var_0 = add nsw i32 %var_0.in, -1
665  %tmp23 = icmp ult i32 %var_1, %len
666  br i1 %tmp23, label %stay, label %bb2
667
668stay:
669  %tmp25 = getelementptr inbounds i16, i16* %tmp20, i32 %var_1
670  %tmp26 = load i16, i16* %tmp25
671  %tmp29 = icmp eq i16 %tmp26, 0
672  br i1 %tmp29, label %bb1, label %bb2
673
674bb1:
675  %tmp30 = add i32 %var_1, 1
676  %tmp31 = icmp eq i32 %var_0, 0
677  br i1 %tmp31, label %bb3, label %bb0
678
679bb2:
680  ret i1 false
681
682bb3:
683  ret i1 true
684}
685
686define void @func_19(i32* %length.ptr) {
687; CHECK-LABEL: @func_19(
688; CHECK-NEXT:  entry:
689; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
690; CHECK-NEXT:    [[LENGTH_IS_NONZERO:%.*]] = icmp ne i32 [[LENGTH]], 0
691; CHECK-NEXT:    br i1 [[LENGTH_IS_NONZERO]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
692; CHECK:       loop.preheader:
693; CHECK-NEXT:    br label [[LOOP:%.*]]
694; CHECK:       loop:
695; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
696; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
697; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
698; CHECK:       be:
699; CHECK-NEXT:    call void @side_effect()
700; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LENGTH]]
701; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
702; CHECK:       leave.loopexit:
703; CHECK-NEXT:    br label [[LEAVE]]
704; CHECK:       leave:
705; CHECK-NEXT:    ret void
706;
707entry:
708  %length = load i32, i32* %length.ptr, !range !0
709  %length.is.nonzero = icmp ne i32 %length, 0
710  br i1 %length.is.nonzero, label %loop, label %leave
711
712loop:
713  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
714  %iv.inc = add i32 %iv, 1
715  %range.check = icmp ult i32 %iv, %length
716  br i1 %range.check, label %be, label %leave
717
718be:
719  call void @side_effect()
720  %be.cond = icmp slt i32 %iv.inc, %length
721  br i1 %be.cond, label %loop, label %leave
722
723leave:
724  ret void
725}
726
727; Like @func_19, but %length is no longer provably positive, so
728; %range.check cannot be proved to be always true.
729define void @func_20(i32* %length.ptr) {
730; CHECK-LABEL: @func_20(
731; CHECK-NEXT:  entry:
732; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4
733; CHECK-NEXT:    [[LENGTH_IS_NONZERO:%.*]] = icmp ne i32 [[LENGTH]], 0
734; CHECK-NEXT:    br i1 [[LENGTH_IS_NONZERO]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
735; CHECK:       loop.preheader:
736; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LENGTH]], i32 1)
737; CHECK-NEXT:    br label [[LOOP:%.*]]
738; CHECK:       loop:
739; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
740; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
741; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV]], [[LENGTH]]
742; CHECK-NEXT:    br i1 [[EXITCOND]], label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
743; CHECK:       be:
744; CHECK-NEXT:    call void @side_effect()
745; CHECK-NEXT:    [[EXITCOND1:%.*]] = icmp ne i32 [[IV_INC]], [[SMAX]]
746; CHECK-NEXT:    br i1 [[EXITCOND1]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
747; CHECK:       leave.loopexit:
748; CHECK-NEXT:    br label [[LEAVE]]
749; CHECK:       leave:
750; CHECK-NEXT:    ret void
751;
752entry:
753  %length = load i32, i32* %length.ptr
754  %length.is.nonzero = icmp ne i32 %length, 0
755  br i1 %length.is.nonzero, label %loop, label %leave
756
757loop:
758  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
759  %iv.inc = add i32 %iv, 1
760  %range.check = icmp ult i32 %iv, %length
761  br i1 %range.check, label %be, label %leave
762
763be:
764  call void @side_effect()
765  %be.cond = icmp slt i32 %iv.inc, %length
766  br i1 %be.cond, label %loop, label %leave
767
768leave:
769  ret void
770}
771
772; This checks that the backedge condition, (I + 1) < Length - 1 implies
773; (I + 1) < Length
774define void @func_21(i32* %length.ptr) {
775; CHECK-LABEL: @func_21(
776; CHECK-NEXT:  entry:
777; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
778; CHECK-NEXT:    [[LIM:%.*]] = sub i32 [[LENGTH]], 1
779; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp sgt i32 [[LENGTH]], 1
780; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
781; CHECK:       loop.preheader:
782; CHECK-NEXT:    br label [[LOOP:%.*]]
783; CHECK:       loop:
784; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
785; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
786; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
787; CHECK:       be:
788; CHECK-NEXT:    call void @side_effect()
789; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LIM]]
790; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
791; CHECK:       leave.loopexit:
792; CHECK-NEXT:    br label [[LEAVE]]
793; CHECK:       leave:
794; CHECK-NEXT:    ret void
795;
796entry:
797  %length = load i32, i32* %length.ptr, !range !0
798  %lim = sub i32 %length, 1
799  %entry.cond = icmp sgt i32 %length, 1
800  br i1 %entry.cond, label %loop, label %leave
801
802loop:
803  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
804  %iv.inc = add i32 %iv, 1
805  %range.check = icmp slt i32 %iv, %length
806  br i1 %range.check, label %be, label %leave
807
808be:
809  call void @side_effect()
810  %be.cond = icmp slt i32 %iv.inc, %lim
811  br i1 %be.cond, label %loop, label %leave
812
813leave:
814  ret void
815}
816
817; This checks that the backedge condition, (I + 1) < Length - 1 implies
818; (I + 1) < Length
819define void @func_22(i32* %length.ptr) {
820; CHECK-LABEL: @func_22(
821; CHECK-NEXT:  entry:
822; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
823; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp sgt i32 [[LENGTH]], 1
824; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
825; CHECK:       loop.preheader:
826; CHECK-NEXT:    br label [[LOOP:%.*]]
827; CHECK:       loop:
828; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
829; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
830; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
831; CHECK:       be:
832; CHECK-NEXT:    call void @side_effect()
833; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LENGTH]]
834; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
835; CHECK:       leave.loopexit:
836; CHECK-NEXT:    br label [[LEAVE]]
837; CHECK:       leave:
838; CHECK-NEXT:    ret void
839;
840entry:
841  %length = load i32, i32* %length.ptr, !range !0
842  %lim = sub i32 %length, 1
843  %entry.cond = icmp sgt i32 %length, 1
844  br i1 %entry.cond, label %loop, label %leave
845
846loop:
847  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
848  %iv.inc = add i32 %iv, 1
849  %range.check = icmp sle i32 %iv, %length
850  br i1 %range.check, label %be, label %leave
851
852be:
853  call void @side_effect()
854  %be.cond = icmp sle i32 %iv.inc, %lim
855  br i1 %be.cond, label %loop, label %leave
856
857leave:
858  ret void
859}
860
861define void @func_23(i32* %length.ptr) {
862; CHECK-LABEL: @func_23(
863; CHECK-NEXT:  entry:
864; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
865; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp ult i32 4, [[LENGTH]]
866; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
867; CHECK:       loop.preheader:
868; CHECK-NEXT:    br label [[LOOP:%.*]]
869; CHECK:       loop:
870; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 4, [[LOOP_PREHEADER]] ]
871; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
872; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
873; CHECK:       be:
874; CHECK-NEXT:    call void @side_effect()
875; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LENGTH]]
876; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
877; CHECK:       leave.loopexit:
878; CHECK-NEXT:    br label [[LEAVE]]
879; CHECK:       leave:
880; CHECK-NEXT:    ret void
881;
882entry:
883  %length = load i32, i32* %length.ptr, !range !0
884  %entry.cond = icmp ult i32 4, %length
885  br i1 %entry.cond, label %loop, label %leave
886
887loop:
888  %iv = phi i32 [ 4, %entry ], [ %iv.inc, %be ]
889  %iv.inc = add i32 %iv, 1
890  %range.check = icmp slt i32 %iv, %length
891  br i1 %range.check, label %be, label %leave
892
893be:
894  call void @side_effect()
895  %be.cond = icmp slt i32 %iv.inc, %length
896  br i1 %be.cond, label %loop, label %leave
897
898leave:
899  ret void
900}
901
902define void @func_24(i32* %init.ptr) {
903; CHECK-LABEL: @func_24(
904; CHECK-NEXT:  entry:
905; CHECK-NEXT:    [[INIT:%.*]] = load i32, i32* [[INIT_PTR:%.*]], align 4, !range [[RNG0]]
906; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp ugt i32 [[INIT]], 4
907; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
908; CHECK:       loop.preheader:
909; CHECK-NEXT:    br label [[LOOP:%.*]]
910; CHECK:       loop:
911; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_DEC:%.*]], [[BE:%.*]] ], [ [[INIT]], [[LOOP_PREHEADER]] ]
912; CHECK-NEXT:    [[IV_DEC]] = add nsw i32 [[IV]], -1
913; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
914; CHECK:       be:
915; CHECK-NEXT:    call void @side_effect()
916; CHECK-NEXT:    [[BE_COND:%.*]] = icmp sgt i32 [[IV_DEC]], 4
917; CHECK-NEXT:    br i1 [[BE_COND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
918; CHECK:       leave.loopexit:
919; CHECK-NEXT:    br label [[LEAVE]]
920; CHECK:       leave:
921; CHECK-NEXT:    ret void
922;
923entry:
924  %init = load i32, i32* %init.ptr, !range !0
925  %entry.cond = icmp ugt i32 %init, 4
926  br i1 %entry.cond, label %loop, label %leave
927
928loop:
929  %iv = phi i32 [ %init, %entry ], [ %iv.dec, %be ]
930  %iv.dec = add i32 %iv, -1
931  %range.check = icmp sgt i32 %iv, 4
932  br i1 %range.check, label %be, label %leave
933
934be:
935  call void @side_effect()
936  %be.cond = icmp sgt i32 %iv.dec, 4
937  br i1 %be.cond, label %loop, label %leave
938
939leave:
940  ret void
941}
942
943declare i1 @cond_func()
944
945define i32 @func_25(i32 %start) {
946; CHECK-LABEL: @func_25(
947; CHECK-NEXT:  entry:
948; CHECK-NEXT:    br label [[LOOP:%.*]]
949; CHECK:       loop:
950; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
951; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32 [[IV]], 0
952; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
953; CHECK:       checked.1:
954; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
955; CHECK:       checked.2:
956; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
957; CHECK:       backedge:
958; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
959; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
960; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
961; CHECK:       fail:
962; CHECK-NEXT:    unreachable
963; CHECK:       exit:
964; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
965; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
966;
967entry:
968  br label %loop
969
970loop:
971  %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
972  %c1 = icmp ne i32 %iv, 0
973  br i1 %c1, label %checked.1, label %fail
974
975checked.1:
976  %c2 = icmp ne i32 %iv, 0
977  br i1 %c2, label %checked.2, label %fail
978
979checked.2:
980  %c3 = icmp ne i32 %iv, 0
981  br i1 %c3, label %backedge, label %fail
982
983backedge:
984  %iv.next = add i32 %iv, 758394
985  %loop.cond = call i1 @cond_func()
986  br i1 %loop.cond, label %loop, label %exit
987
988fail:
989  unreachable
990
991exit:
992  ret i32 %iv
993}
994
995define i32 @func_26(i32 %start) {
996; CHECK-LABEL: @func_26(
997; CHECK-NEXT:  entry:
998; CHECK-NEXT:    br label [[LOOP:%.*]]
999; CHECK:       loop:
1000; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
1001; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[IV]], 0
1002; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
1003; CHECK:       checked.1:
1004; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
1005; CHECK:       checked.2:
1006; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
1007; CHECK:       backedge:
1008; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
1009; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
1010; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
1011; CHECK:       fail:
1012; CHECK-NEXT:    unreachable
1013; CHECK:       exit:
1014; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
1015; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
1016;
1017entry:
1018  br label %loop
1019
1020loop:
1021  %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
1022  %c1 = icmp slt i32 %iv, 0
1023  br i1 %c1, label %checked.1, label %fail
1024
1025checked.1:
1026  %c2 = icmp slt i32 %iv, 1
1027  br i1 %c2, label %checked.2, label %fail
1028
1029checked.2:
1030  %c3 = icmp slt i32 %iv, 2
1031  br i1 %c3, label %backedge, label %fail
1032
1033backedge:
1034  %iv.next = add i32 %iv, 758394
1035  %loop.cond = call i1 @cond_func()
1036  br i1 %loop.cond, label %loop, label %exit
1037
1038fail:
1039  unreachable
1040
1041exit:
1042  ret i32 %iv
1043}
1044
1045define i32 @func_27(i32 %start) {
1046; CHECK-LABEL: @func_27(
1047; CHECK-NEXT:  entry:
1048; CHECK-NEXT:    br label [[LOOP:%.*]]
1049; CHECK:       loop:
1050; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
1051; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[IV]], 2
1052; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[IV]], 1
1053; CHECK-NEXT:    [[C3:%.*]] = icmp slt i32 [[IV]], 0
1054; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
1055; CHECK:       checked.1:
1056; CHECK-NEXT:    br i1 [[C2]], label [[CHECKED_2:%.*]], label [[FAIL]]
1057; CHECK:       checked.2:
1058; CHECK-NEXT:    br i1 [[C3]], label [[BACKEDGE]], label [[FAIL]]
1059; CHECK:       backedge:
1060; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
1061; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
1062; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
1063; CHECK:       fail:
1064; CHECK-NEXT:    unreachable
1065; CHECK:       exit:
1066; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
1067; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
1068;
1069entry:
1070  br label %loop
1071
1072loop:
1073  %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
1074  %c1 = icmp slt i32 %iv, 2
1075  %c2 = icmp slt i32 %iv, 1
1076  %c3 = icmp slt i32 %iv, 0
1077  br i1 %c1, label %checked.1, label %fail
1078
1079checked.1:
1080  br i1 %c2, label %checked.2, label %fail
1081
1082checked.2:
1083  br i1 %c3, label %backedge, label %fail
1084
1085backedge:
1086  %iv.next = add i32 %iv, 758394
1087  %loop.cond = call i1 @cond_func()
1088  br i1 %loop.cond, label %loop, label %exit
1089
1090fail:
1091  unreachable
1092
1093exit:
1094  ret i32 %iv
1095}
1096
1097define i32 @func_28(i32 %start) {
1098; CHECK-LABEL: @func_28(
1099; CHECK-NEXT:  entry:
1100; CHECK-NEXT:    br label [[LOOP:%.*]]
1101; CHECK:       loop:
1102; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
1103; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32 [[IV]], 0
1104; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
1105; CHECK:       checked.1:
1106; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
1107; CHECK:       checked.2:
1108; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
1109; CHECK:       backedge:
1110; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
1111; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
1112; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
1113; CHECK:       fail:
1114; CHECK-NEXT:    unreachable
1115; CHECK:       exit:
1116; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
1117; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
1118;
1119entry:
1120  br label %loop
1121
1122loop:
1123  %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
1124  %c1 = icmp ne i32 %iv, 0
1125  %c2 = icmp ne i32 %iv, 0
1126  %c3 = icmp ne i32 %iv, 0
1127  br i1 %c1, label %checked.1, label %fail
1128
1129checked.1:
1130  br i1 %c2, label %checked.2, label %fail
1131
1132checked.2:
1133  br i1 %c3, label %backedge, label %fail
1134
1135backedge:
1136  %iv.next = add i32 %iv, 758394
1137  %loop.cond = call i1 @cond_func()
1138  br i1 %loop.cond, label %loop, label %exit
1139
1140fail:
1141  unreachable
1142
1143exit:
1144  ret i32 %iv
1145}
1146
1147!0 = !{i32 0, i32 2147483647}
1148