xref: /llvm-project/llvm/test/Transforms/IndVarSimplify/loop-predication.ll (revision 3ce360f15b5a790a5fd9dcab716bbed7b4d3a347) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -passes=indvars -indvars-predicate-loops=1 -S | FileCheck %s
3
4declare void @prevent_merging()
5
6; Base case
7define i32 @test1(ptr %array, i32 %length, i32 %n) {
8; CHECK-LABEL: @test1(
9; CHECK-NEXT:  loop.preheader:
10; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[N:%.*]], i32 1)
11; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[UMAX]], -1
12; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[TMP0]]
13; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[TMP1]], i32 [[LENGTH:%.*]])
14; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[LENGTH]], [[UMIN]]
15; CHECK-NEXT:    br label [[LOOP:%.*]]
16; CHECK:       loop:
17; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
18; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
19; CHECK-NEXT:    br i1 [[TMP2]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0:![0-9]+]]
20; CHECK:       deopt:
21; CHECK-NEXT:    call void @prevent_merging()
22; CHECK-NEXT:    ret i32 -1
23; CHECK:       guarded:
24; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
25; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I_I64]]
26; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
27; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
28; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
29; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
30; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
31; CHECK:       exit:
32; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
33; CHECK-NEXT:    ret i32 [[RESULT]]
34;
35loop.preheader:                                   ; preds = %entry
36  br label %loop
37
38loop:                                             ; preds = %guarded, %loop.preheader
39  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
40  %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
41  %within.bounds = icmp ult i32 %i, %length
42  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
43
44deopt:                                            ; preds = %loop
45  call void @prevent_merging()
46  ret i32 -1
47
48guarded:                                          ; preds = %loop
49  %i.i64 = zext i32 %i to i64
50  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i.i64
51  %array.i = load i32, ptr %array.i.ptr, align 4
52  %loop.acc.next = add i32 %loop.acc, %array.i
53  %i.next = add nuw i32 %i, 1
54  %continue = icmp ult i32 %i.next, %n
55  br i1 %continue, label %loop, label %exit
56
57exit:                                             ; preds = %guarded, %entry
58  %result = phi i32 [ %loop.acc.next, %guarded ]
59  ret i32 %result
60}
61
62; Has side effect which must be reflected
63define i32 @neg_store(ptr %array, i32 %length, i32 %n) {
64; CHECK-LABEL: @neg_store(
65; CHECK-NEXT:  loop.preheader:
66; CHECK-NEXT:    br label [[LOOP:%.*]]
67; CHECK:       loop:
68; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
69; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
70; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
71; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
72; CHECK:       deopt:
73; CHECK-NEXT:    call void @prevent_merging()
74; CHECK-NEXT:    ret i32 -1
75; CHECK:       guarded:
76; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
77; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I_I64]]
78; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
79; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
80; CHECK-NEXT:    store i32 0, ptr [[ARRAY_I_PTR]], align 4
81; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
82; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N:%.*]]
83; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
84; CHECK:       exit:
85; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
86; CHECK-NEXT:    ret i32 [[RESULT]]
87;
88loop.preheader:                                   ; preds = %entry
89  br label %loop
90
91loop:                                             ; preds = %guarded, %loop.preheader
92  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
93  %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
94  %within.bounds = icmp ult i32 %i, %length
95  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
96
97deopt:                                            ; preds = %loop
98  call void @prevent_merging()
99  ret i32 -1
100
101guarded:                                          ; preds = %loop
102  %i.i64 = zext i32 %i to i64
103  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i.i64
104  %array.i = load i32, ptr %array.i.ptr, align 4
105  %loop.acc.next = add i32 %loop.acc, %array.i
106  store i32 0, ptr %array.i.ptr
107  %i.next = add nuw i32 %i, 1
108  %continue = icmp ult i32 %i.next, %n
109  br i1 %continue, label %loop, label %exit
110
111exit:                                             ; preds = %guarded, %entry
112  %result = phi i32 [ %loop.acc.next, %guarded ]
113  ret i32 %result
114}
115
116declare void @maythrow()
117
118; May exit through implicit exception edge
119define i32 @neg_implicit_exit(ptr %array, i32 %length, i32 %n) {
120; CHECK-LABEL: @neg_implicit_exit(
121; CHECK-NEXT:  loop.preheader:
122; CHECK-NEXT:    br label [[LOOP:%.*]]
123; CHECK:       loop:
124; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
125; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
126; CHECK-NEXT:    call void @maythrow()
127; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
128; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
129; CHECK:       deopt:
130; CHECK-NEXT:    call void @prevent_merging()
131; CHECK-NEXT:    ret i32 -1
132; CHECK:       guarded:
133; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
134; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I_I64]]
135; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
136; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
137; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
138; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N:%.*]]
139; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
140; CHECK:       exit:
141; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
142; CHECK-NEXT:    ret i32 [[RESULT]]
143;
144loop.preheader:                                   ; preds = %entry
145  br label %loop
146
147loop:                                             ; preds = %guarded, %loop.preheader
148  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
149  %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
150  call void @maythrow()
151  %within.bounds = icmp ult i32 %i, %length
152  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
153
154deopt:                                            ; preds = %loop
155  call void @prevent_merging()
156  ret i32 -1
157
158guarded:                                          ; preds = %loop
159  %i.i64 = zext i32 %i to i64
160  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i.i64
161  %array.i = load i32, ptr %array.i.ptr, align 4
162  %loop.acc.next = add i32 %loop.acc, %array.i
163  %i.next = add nuw i32 %i, 1
164  %continue = icmp ult i32 %i.next, %n
165  br i1 %continue, label %loop, label %exit
166
167exit:                                             ; preds = %guarded, %entry
168  %result = phi i32 [ %loop.acc.next, %guarded ]
169  ret i32 %result
170}
171
172
173
174; Base case, but in LFTR form (just for basic correctness checking)
175define i32 @test2(ptr %array, i32 %length, i32 %n) {
176; CHECK-LABEL: @test2(
177; CHECK-NEXT:  loop.preheader:
178; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], -1
179; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[TMP0]]
180; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[TMP1]], i32 [[LENGTH:%.*]])
181; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[LENGTH]], [[UMIN]]
182; CHECK-NEXT:    br label [[LOOP:%.*]]
183; CHECK:       loop:
184; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
185; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
186; CHECK-NEXT:    br i1 [[TMP2]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
187; CHECK:       deopt:
188; CHECK-NEXT:    call void @prevent_merging()
189; CHECK-NEXT:    ret i32 -1
190; CHECK:       guarded:
191; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
192; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I_I64]]
193; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
194; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
195; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
196; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ne i32 [[I_NEXT]], [[N]]
197; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
198; CHECK:       exit:
199; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
200; CHECK-NEXT:    ret i32 [[RESULT]]
201;
202loop.preheader:                                   ; preds = %entry
203  br label %loop
204
205loop:                                             ; preds = %guarded, %loop.preheader
206  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
207  %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
208  %within.bounds = icmp ne i32 %i, %length
209  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
210
211deopt:                                            ; preds = %loop
212  call void @prevent_merging()
213  ret i32 -1
214
215guarded:                                          ; preds = %loop
216  %i.i64 = zext i32 %i to i64
217  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i.i64
218  %array.i = load i32, ptr %array.i.ptr, align 4
219  %loop.acc.next = add i32 %loop.acc, %array.i
220  %i.next = add nuw i32 %i, 1
221  %continue = icmp ne i32 %i.next, %n
222  br i1 %continue, label %loop, label %exit
223
224exit:                                             ; preds = %guarded, %entry
225  %result = phi i32 [ %loop.acc.next, %guarded ]
226  ret i32 %result
227}
228
229; br (and rcheck1, rcheck2)
230define i32 @two_range_checks(ptr %array.1, i32 %length.1, ptr %array.2, i32 %length.2, i32 %n) {
231; CHECK-LABEL: @two_range_checks(
232; CHECK-NEXT:  loop.preheader:
233; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[LENGTH_2:%.*]], i32 [[LENGTH_1:%.*]])
234; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[N:%.*]], i32 1)
235; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[UMAX]], -1
236; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[TMP0]]
237; CHECK-NEXT:    [[UMIN1:%.*]] = call i32 @llvm.umin.i32(i32 [[TMP1]], i32 [[UMIN]])
238; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[UMIN]], [[UMIN1]]
239; CHECK-NEXT:    br label [[LOOP:%.*]]
240; CHECK:       loop:
241; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
242; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
243; CHECK-NEXT:    br i1 [[TMP2]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
244; CHECK:       deopt:
245; CHECK-NEXT:    call void @prevent_merging()
246; CHECK-NEXT:    ret i32 -1
247; CHECK:       guarded:
248; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
249; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_1:%.*]], i64 [[I_I64]]
250; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, ptr [[ARRAY_1_I_PTR]], align 4
251; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
252; CHECK-NEXT:    [[ARRAY_2_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_2:%.*]], i64 [[I_I64]]
253; CHECK-NEXT:    [[ARRAY_2_I:%.*]] = load i32, ptr [[ARRAY_2_I_PTR]], align 4
254; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_1]], [[ARRAY_2_I]]
255; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
256; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
257; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
258; CHECK:       exit:
259; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
260; CHECK-NEXT:    ret i32 [[RESULT]]
261;
262loop.preheader:                                   ; preds = %entry
263  br label %loop
264
265loop:                                             ; preds = %guarded, %loop.preheader
266  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
267  %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
268  %within.bounds.1 = icmp ult i32 %i, %length.1
269  %within.bounds.2 = icmp ult i32 %i, %length.2
270  %within.bounds = and i1 %within.bounds.1, %within.bounds.2
271  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
272
273deopt:                                            ; preds = %loop
274  call void @prevent_merging()
275  ret i32 -1
276
277guarded:                                          ; preds = %loop
278  %i.i64 = zext i32 %i to i64
279  %array.1.i.ptr = getelementptr inbounds i32, ptr %array.1, i64 %i.i64
280  %array.1.i = load i32, ptr %array.1.i.ptr, align 4
281  %loop.acc.1 = add i32 %loop.acc, %array.1.i
282  %array.2.i.ptr = getelementptr inbounds i32, ptr %array.2, i64 %i.i64
283  %array.2.i = load i32, ptr %array.2.i.ptr, align 4
284  %loop.acc.next = add i32 %loop.acc.1, %array.2.i
285  %i.next = add nuw i32 %i, 1
286  %continue = icmp ult i32 %i.next, %n
287  br i1 %continue, label %loop, label %exit
288
289exit:                                             ; preds = %guarded, %entry
290  %result = phi i32 [ %loop.acc.next, %guarded ]
291  ret i32 %result
292}
293
294define i32 @three_range_checks(ptr %array.1, i32 %length.1, ptr %array.2, i32 %length.2, ptr %array.3, i32 %length.3, i32 %n) {
295; CHECK-LABEL: @three_range_checks(
296; CHECK-NEXT:  loop.preheader:
297; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[LENGTH_3:%.*]], i32 [[LENGTH_2:%.*]])
298; CHECK-NEXT:    [[UMIN1:%.*]] = call i32 @llvm.umin.i32(i32 [[UMIN]], i32 [[LENGTH_1:%.*]])
299; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[N:%.*]], i32 1)
300; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[UMAX]], -1
301; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[TMP0]]
302; CHECK-NEXT:    [[UMIN2:%.*]] = call i32 @llvm.umin.i32(i32 [[TMP1]], i32 [[UMIN1]])
303; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[UMIN1]], [[UMIN2]]
304; CHECK-NEXT:    br label [[LOOP:%.*]]
305; CHECK:       loop:
306; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
307; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
308; CHECK-NEXT:    br i1 [[TMP2]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
309; CHECK:       deopt:
310; CHECK-NEXT:    call void @prevent_merging()
311; CHECK-NEXT:    ret i32 -1
312; CHECK:       guarded:
313; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
314; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_1:%.*]], i64 [[I_I64]]
315; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, ptr [[ARRAY_1_I_PTR]], align 4
316; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
317; CHECK-NEXT:    [[ARRAY_2_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_2:%.*]], i64 [[I_I64]]
318; CHECK-NEXT:    [[ARRAY_2_I:%.*]] = load i32, ptr [[ARRAY_2_I_PTR]], align 4
319; CHECK-NEXT:    [[LOOP_ACC_2:%.*]] = add i32 [[LOOP_ACC_1]], [[ARRAY_2_I]]
320; CHECK-NEXT:    [[ARRAY_3_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_3:%.*]], i64 [[I_I64]]
321; CHECK-NEXT:    [[ARRAY_3_I:%.*]] = load i32, ptr [[ARRAY_3_I_PTR]], align 4
322; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_2]], [[ARRAY_3_I]]
323; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
324; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
325; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
326; CHECK:       exit:
327; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
328; CHECK-NEXT:    ret i32 [[RESULT]]
329;
330loop.preheader:                                   ; preds = %entry
331  br label %loop
332
333loop:                                             ; preds = %guarded, %loop.preheader
334  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
335  %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
336  %within.bounds.1 = icmp ult i32 %i, %length.1
337  %within.bounds.2 = icmp ult i32 %i, %length.2
338  %within.bounds.3 = icmp ult i32 %i, %length.3
339  %within.bounds.1.and.2 = and i1 %within.bounds.1, %within.bounds.2
340  %within.bounds = and i1 %within.bounds.1.and.2, %within.bounds.3
341  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
342
343deopt:                                            ; preds = %loop
344  call void @prevent_merging()
345  ret i32 -1
346
347guarded:                                          ; preds = %loop
348  %i.i64 = zext i32 %i to i64
349  %array.1.i.ptr = getelementptr inbounds i32, ptr %array.1, i64 %i.i64
350  %array.1.i = load i32, ptr %array.1.i.ptr, align 4
351  %loop.acc.1 = add i32 %loop.acc, %array.1.i
352  %array.2.i.ptr = getelementptr inbounds i32, ptr %array.2, i64 %i.i64
353  %array.2.i = load i32, ptr %array.2.i.ptr, align 4
354  %loop.acc.2 = add i32 %loop.acc.1, %array.2.i
355  %array.3.i.ptr = getelementptr inbounds i32, ptr %array.3, i64 %i.i64
356  %array.3.i = load i32, ptr %array.3.i.ptr, align 4
357  %loop.acc.next = add i32 %loop.acc.2, %array.3.i
358  %i.next = add nuw i32 %i, 1
359  %continue = icmp ult i32 %i.next, %n
360  br i1 %continue, label %loop, label %exit
361
362exit:                                             ; preds = %guarded, %entry
363  %result = phi i32 [ %loop.acc.next, %guarded ]
364  ret i32 %result
365}
366
367; Analogous to the above, but with two distinct branches (on different conditions)
368define i32 @distinct_checks(ptr %array.1, i32 %length.1, ptr %array.2, i32 %length.2, ptr %array.3, i32 %length.3, i32 %n) {
369; CHECK-LABEL: @distinct_checks(
370; CHECK-NEXT:  loop.preheader:
371; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[N:%.*]], i32 1)
372; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[UMAX]], -1
373; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[TMP0]]
374; CHECK-NEXT:    [[TMP2:%.*]] = freeze i32 [[LENGTH_2:%.*]]
375; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[TMP1]], i32 [[TMP2]])
376; CHECK-NEXT:    [[UMIN1:%.*]] = call i32 @llvm.umin.i32(i32 [[UMIN]], i32 [[LENGTH_1:%.*]])
377; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[LENGTH_1]], [[UMIN1]]
378; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[LENGTH_2]], [[UMIN1]]
379; CHECK-NEXT:    br label [[LOOP:%.*]]
380; CHECK:       loop:
381; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED1:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
382; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED1]] ], [ 0, [[LOOP_PREHEADER]] ]
383; CHECK-NEXT:    br i1 [[TMP3]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof [[PROF0]]
384; CHECK:       deopt:
385; CHECK-NEXT:    call void @prevent_merging()
386; CHECK-NEXT:    ret i32 -1
387; CHECK:       guarded:
388; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
389; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_1:%.*]], i64 [[I_I64]]
390; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, ptr [[ARRAY_1_I_PTR]], align 4
391; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
392; CHECK-NEXT:    br i1 [[TMP4]], label [[GUARDED1]], label [[DEOPT2:%.*]], !prof [[PROF0]]
393; CHECK:       deopt2:
394; CHECK-NEXT:    call void @prevent_merging()
395; CHECK-NEXT:    ret i32 -1
396; CHECK:       guarded1:
397; CHECK-NEXT:    [[ARRAY_3_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_3:%.*]], i64 [[I_I64]]
398; CHECK-NEXT:    [[ARRAY_3_I:%.*]] = load i32, ptr [[ARRAY_3_I_PTR]], align 4
399; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_1]], [[ARRAY_3_I]]
400; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
401; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
402; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
403; CHECK:       exit:
404; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED1]] ]
405; CHECK-NEXT:    ret i32 [[RESULT]]
406;
407loop.preheader:                                   ; preds = %entry
408  br label %loop
409
410loop:                                             ; preds = %guarded4, %loop.preheader
411  %loop.acc = phi i32 [ %loop.acc.next, %guarded1 ], [ 0, %loop.preheader ]
412  %i = phi i32 [ %i.next, %guarded1 ], [ 0, %loop.preheader ]
413  %within.bounds.1 = icmp ult i32 %i, %length.1
414  br i1 %within.bounds.1, label %guarded, label %deopt, !prof !0
415
416deopt:                                            ; preds = %loop
417  call void @prevent_merging()
418  ret i32 -1
419
420guarded:                                          ; preds = %loop
421  %i.i64 = zext i32 %i to i64
422  %array.1.i.ptr = getelementptr inbounds i32, ptr %array.1, i64 %i.i64
423  %array.1.i = load i32, ptr %array.1.i.ptr, align 4
424  %loop.acc.1 = add i32 %loop.acc, %array.1.i
425  %within.bounds.2 = icmp ult i32 %i, %length.2
426  br i1 %within.bounds.2, label %guarded1, label %deopt2, !prof !0
427
428deopt2:                                           ; preds = %guarded
429  call void @prevent_merging()
430  ret i32 -1
431
432guarded1:                                         ; preds = %guarded1
433  %array.3.i.ptr = getelementptr inbounds i32, ptr %array.3, i64 %i.i64
434  %array.3.i = load i32, ptr %array.3.i.ptr, align 4
435  %loop.acc.next = add i32 %loop.acc.1, %array.3.i
436  %i.next = add nuw i32 %i, 1
437  %continue = icmp ult i32 %i.next, %n
438  br i1 %continue, label %loop, label %exit
439
440exit:
441  %result = phi i32 [ %loop.acc.next, %guarded1 ]
442  ret i32 %result
443}
444
445define i32 @duplicate_checks(ptr %array.1, ptr %array.2, ptr %array.3, i32 %length, i32 %n) {
446; CHECK-LABEL: @duplicate_checks(
447; CHECK-NEXT:  loop.preheader:
448; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[N:%.*]], i32 1)
449; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[UMAX]], -1
450; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[TMP0]]
451; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[TMP1]], i32 [[LENGTH:%.*]])
452; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[LENGTH]], [[UMIN]]
453; CHECK-NEXT:    br label [[LOOP:%.*]]
454; CHECK:       loop:
455; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED1:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
456; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED1]] ], [ 0, [[LOOP_PREHEADER]] ]
457; CHECK-NEXT:    br i1 [[TMP2]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof [[PROF0]]
458; CHECK:       deopt:
459; CHECK-NEXT:    call void @prevent_merging()
460; CHECK-NEXT:    ret i32 -1
461; CHECK:       guarded:
462; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
463; CHECK-NEXT:    [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_1:%.*]], i64 [[I_I64]]
464; CHECK-NEXT:    [[ARRAY_1_I:%.*]] = load i32, ptr [[ARRAY_1_I_PTR]], align 4
465; CHECK-NEXT:    [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
466; CHECK-NEXT:    br i1 true, label [[GUARDED1]], label [[DEOPT2:%.*]], !prof [[PROF0]]
467; CHECK:       deopt2:
468; CHECK-NEXT:    call void @prevent_merging()
469; CHECK-NEXT:    ret i32 -1
470; CHECK:       guarded1:
471; CHECK-NEXT:    [[ARRAY_3_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY_3:%.*]], i64 [[I_I64]]
472; CHECK-NEXT:    [[ARRAY_3_I:%.*]] = load i32, ptr [[ARRAY_3_I_PTR]], align 4
473; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_1]], [[ARRAY_3_I]]
474; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
475; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
476; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
477; CHECK:       exit:
478; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED1]] ]
479; CHECK-NEXT:    ret i32 [[RESULT]]
480;
481loop.preheader:                                   ; preds = %entry
482  br label %loop
483
484loop:                                             ; preds = %guarded4, %loop.preheader
485  %loop.acc = phi i32 [ %loop.acc.next, %guarded1 ], [ 0, %loop.preheader ]
486  %i = phi i32 [ %i.next, %guarded1 ], [ 0, %loop.preheader ]
487  %within.bounds.1 = icmp ult i32 %i, %length
488  br i1 %within.bounds.1, label %guarded, label %deopt, !prof !0
489
490deopt:                                            ; preds = %loop
491  call void @prevent_merging()
492  ret i32 -1
493
494guarded:                                          ; preds = %loop
495  %i.i64 = zext i32 %i to i64
496  %array.1.i.ptr = getelementptr inbounds i32, ptr %array.1, i64 %i.i64
497  %array.1.i = load i32, ptr %array.1.i.ptr, align 4
498  %loop.acc.1 = add i32 %loop.acc, %array.1.i
499  %within.bounds.2 = icmp ult i32 %i, %length
500  br i1 %within.bounds.2, label %guarded1, label %deopt2, !prof !0
501
502deopt2:                                           ; preds = %guarded
503  call void @prevent_merging()
504  ret i32 -1
505
506guarded1:                                         ; preds = %guarded1
507  %array.3.i.ptr = getelementptr inbounds i32, ptr %array.3, i64 %i.i64
508  %array.3.i = load i32, ptr %array.3.i.ptr, align 4
509  %loop.acc.next = add i32 %loop.acc.1, %array.3.i
510  %i.next = add nuw i32 %i, 1
511  %continue = icmp ult i32 %i.next, %n
512  br i1 %continue, label %loop, label %exit
513
514exit:
515  %result = phi i32 [ %loop.acc.next, %guarded1 ]
516  ret i32 %result
517}
518
519
520define i32 @provably_taken(ptr %array, ptr %length.ptr) {
521; CHECK-LABEL: @provably_taken(
522; CHECK-NEXT:  loop.preheader:
523; CHECK-NEXT:    br label [[LOOP:%.*]]
524; CHECK:       loop:
525; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
526; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
527; CHECK-NEXT:    br i1 false, label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
528; CHECK:       deopt:
529; CHECK-NEXT:    call void @prevent_merging()
530; CHECK-NEXT:    ret i32 -1
531; CHECK:       guarded:
532; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
533; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I_I64]]
534; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
535; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
536; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
537; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT:%.*]]
538; CHECK:       exit:
539; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
540; CHECK-NEXT:    ret i32 [[RESULT]]
541;
542loop.preheader:
543  %length = load i32, ptr %length.ptr, !range !2
544  br label %loop
545
546loop:                                             ; preds = %guarded, %loop.preheader
547  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
548  %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
549  %within.bounds = icmp ult i32 %i, %length
550  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
551
552deopt:                                            ; preds = %loop
553  call void @prevent_merging()
554  ret i32 -1
555
556guarded:                                          ; preds = %loop
557  %i.i64 = zext i32 %i to i64
558  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i.i64
559  %array.i = load i32, ptr %array.i.ptr, align 4
560  %loop.acc.next = add i32 %loop.acc, %array.i
561  %i.next = add nuw i32 %i, 1
562  %continue = icmp slt i32 %i.next, 200
563  br i1 %continue, label %loop, label %exit
564
565exit:                                             ; preds = %guarded
566  %result = phi i32 [ %loop.acc.next, %guarded ]
567  ret i32 %result
568}
569
570; Non-latch exits can still be predicated
571define i32 @unconditional_latch(ptr %a, i32 %length) {
572; CHECK-LABEL: @unconditional_latch(
573; CHECK-NEXT:  loop.preheader:
574; CHECK-NEXT:    br label [[LOOP:%.*]]
575; CHECK:       loop:
576; CHECK-NEXT:    br i1 false, label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof [[PROF0]]
577; CHECK:       deopt:
578; CHECK-NEXT:    call void @prevent_merging()
579; CHECK-NEXT:    ret i32 -1
580; CHECK:       guarded:
581; CHECK-NEXT:    br label [[LOOP]]
582;
583loop.preheader:
584  br label %loop
585
586loop:                                             ; preds = %guarded, %loop.preheader
587  %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
588  %within.bounds = icmp ult i32 %i, %length
589  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
590
591deopt:                                            ; preds = %loop
592  call void @prevent_merging()
593  ret i32 -1
594
595guarded:                                          ; preds = %loop
596  %i.next = add i32 %i, 1
597  br label %loop
598}
599
600; Side effect in loop must run proper number of times
601define i32 @unconditional_latch_with_side_effect(ptr %a, i32 %length) {
602; CHECK-LABEL: @unconditional_latch_with_side_effect(
603; CHECK-NEXT:  loop.preheader:
604; CHECK-NEXT:    br label [[LOOP:%.*]]
605; CHECK:       loop:
606; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED:%.*]] ], [ 400, [[LOOP_PREHEADER:%.*]] ]
607; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
608; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
609; CHECK:       deopt:
610; CHECK-NEXT:    call void @prevent_merging()
611; CHECK-NEXT:    ret i32 -1
612; CHECK:       guarded:
613; CHECK-NEXT:    store volatile i32 0, ptr [[A:%.*]], align 4
614; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
615; CHECK-NEXT:    br label [[LOOP]]
616;
617loop.preheader:
618  br label %loop
619
620loop:                                             ; preds = %guarded, %loop.preheader
621  %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
622  %within.bounds = icmp ult i32 %i, %length
623  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
624
625deopt:                                            ; preds = %loop
626  call void @prevent_merging()
627  ret i32 -1
628
629guarded:                                          ; preds = %loop
630  store volatile i32 0, ptr %a
631  %i.next = add i32 %i, 1
632  br label %loop
633}
634
635; Demonstrate that this approach works with IVs of different steps, and types
636; This version uses a manually lftred exit condition to work around an issue described
637; in detail on next test.
638define i32 @different_ivs(ptr %array, i32 %length, i32 %n) {
639; CHECK-LABEL: @different_ivs(
640; CHECK-NEXT:  loop.preheader:
641; CHECK-NEXT:    [[N64:%.*]] = zext i32 [[N:%.*]] to i64
642; CHECK-NEXT:    [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[N64]], i64 1)
643; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[UMAX]], -1
644; CHECK-NEXT:    [[TMP1:%.*]] = freeze i64 [[TMP0]]
645; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[LENGTH:%.*]] to i64
646; CHECK-NEXT:    [[UMIN:%.*]] = call i64 @llvm.umin.i64(i64 [[TMP1]], i64 [[TMP2]])
647; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[LENGTH]] to i64
648; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i64 [[TMP3]], [[UMIN]]
649; CHECK-NEXT:    br label [[LOOP:%.*]]
650; CHECK:       loop:
651; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
652; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
653; CHECK-NEXT:    br i1 [[TMP4]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
654; CHECK:       deopt:
655; CHECK-NEXT:    call void @prevent_merging()
656; CHECK-NEXT:    ret i32 -1
657; CHECK:       guarded:
658; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I]]
659; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
660; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
661; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
662; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i64 [[I_NEXT]], [[N64]]
663; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
664; CHECK:       exit:
665; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
666; CHECK-NEXT:    ret i32 [[RESULT]]
667;
668loop.preheader:
669  %j.start = sub nuw nsw i32 %length, 1
670  %n64 = zext i32 %n to i64
671  br label %loop
672
673loop:
674  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
675  %i = phi i64 [ %i.next, %guarded ], [ 0, %loop.preheader ]
676  %j = phi i32 [ %j.next, %guarded ], [ %j.start, %loop.preheader ]
677  %within.bounds = icmp ne i32 %j, -1
678  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
679
680deopt:
681  call void @prevent_merging()
682  ret i32 -1
683
684guarded:
685  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i
686  %array.i = load i32, ptr %array.i.ptr, align 4
687  %loop.acc.next = add i32 %loop.acc, %array.i
688  %i.next = add nuw i64 %i, 1
689  %j.next = sub nuw i32 %j, 1
690  %continue = icmp ult i64 %i.next, %n64
691  br i1 %continue, label %loop, label %exit
692
693exit:
694  %result = phi i32 [ %loop.acc.next, %guarded ]
695  ret i32 %result
696}
697
698; TODO: We're failing to compute an exit count for the bounds check.
699; From some quick analysis, it looks like we don't handle -1 step
700; in howManyLessThans.  Should be a simple fix.
701define i32 @different_ivs2(ptr %array, i32 %length, i32 %n) {
702; CHECK-LABEL: @different_ivs2(
703; CHECK-NEXT:  entry:
704; CHECK-NEXT:    [[POS_LENGTH:%.*]] = icmp sgt i32 [[LENGTH:%.*]], 0
705; CHECK-NEXT:    br i1 [[POS_LENGTH]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
706; CHECK:       loop.preheader:
707; CHECK-NEXT:    [[J_START:%.*]] = sub nuw nsw i32 [[LENGTH]], 1
708; CHECK-NEXT:    [[N64:%.*]] = zext i32 [[N:%.*]] to i64
709; CHECK-NEXT:    br label [[LOOP:%.*]]
710; CHECK:       loop:
711; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
712; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
713; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[J_NEXT:%.*]], [[GUARDED]] ], [ [[J_START]], [[LOOP_PREHEADER]] ]
714; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[J]], [[LENGTH]]
715; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
716; CHECK:       deopt:
717; CHECK-NEXT:    call void @prevent_merging()
718; CHECK-NEXT:    ret i32 -1
719; CHECK:       guarded:
720; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I]]
721; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
722; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
723; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[I]], 1
724; CHECK-NEXT:    [[J_NEXT]] = sub nuw i32 [[J]], 1
725; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i64 [[I_NEXT]], [[N64]]
726; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
727; CHECK:       exit.loopexit:
728; CHECK-NEXT:    [[LOOP_ACC_NEXT_LCSSA:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
729; CHECK-NEXT:    br label [[EXIT]]
730; CHECK:       exit:
731; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_ACC_NEXT_LCSSA]], [[EXIT_LOOPEXIT]] ]
732; CHECK-NEXT:    ret i32 [[RESULT]]
733;
734entry:
735  %pos_length = icmp sgt i32 %length, 0
736  br i1 %pos_length, label %loop.preheader, label %exit
737
738loop.preheader:
739  %j.start = sub nuw nsw i32 %length, 1
740  %n64 = zext i32 %n to i64
741  br label %loop
742
743loop:
744  %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
745  %i = phi i64 [ %i.next, %guarded ], [ 0, %loop.preheader ]
746  %j = phi i32 [ %j.next, %guarded ], [ %j.start, %loop.preheader ]
747  %within.bounds = icmp ult i32 %j, %length
748  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
749
750deopt:
751  call void @prevent_merging()
752  ret i32 -1
753
754guarded:
755  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i
756  %array.i = load i32, ptr %array.i.ptr, align 4
757  %loop.acc.next = add i32 %loop.acc, %array.i
758  %i.next = add nuw i64 %i, 1
759  %j.next = sub nuw i32 %j, 1
760  %continue = icmp ult i64 %i.next, %n64
761  br i1 %continue, label %loop, label %exit
762
763exit:
764  %result = phi i32 [ %loop.acc.next, %guarded ], [0, %entry]
765  ret i32 %result
766}
767
768; If we have a dominating exit (exit1) which can't be itself rewritten, we
769; can't rewrite a later exit (exit2).  Doing so would cause the loop to exit
770; from the exit2 when it should have exited from exit1.
771define i32 @neg_dominating_exit(ptr %array, i32 %length, i32 %length2, i32 %n) {
772; CHECK-LABEL: @neg_dominating_exit(
773; CHECK-NEXT:  loop.preheader:
774; CHECK-NEXT:    br label [[LOOP:%.*]]
775; CHECK:       loop:
776; CHECK-NEXT:    [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED2:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
777; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED2]] ], [ 0, [[LOOP_PREHEADER]] ]
778; CHECK-NEXT:    [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
779; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof [[PROF0]]
780; CHECK:       deopt:
781; CHECK-NEXT:    [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC]], [[LOOP]] ]
782; CHECK-NEXT:    call void @prevent_merging()
783; CHECK-NEXT:    ret i32 [[RESULT]]
784; CHECK:       guarded:
785; CHECK-NEXT:    [[WITHIN_BOUNDS2:%.*]] = icmp ult i32 [[I]], [[LENGTH2:%.*]]
786; CHECK-NEXT:    br i1 [[WITHIN_BOUNDS2]], label [[GUARDED2]], label [[DEOPT2:%.*]], !prof [[PROF0]]
787; CHECK:       deopt2:
788; CHECK-NEXT:    call void @prevent_merging()
789; CHECK-NEXT:    ret i32 -1
790; CHECK:       guarded2:
791; CHECK-NEXT:    [[I_I64:%.*]] = zext i32 [[I]] to i64
792; CHECK-NEXT:    [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, ptr [[ARRAY:%.*]], i64 [[I_I64]]
793; CHECK-NEXT:    [[ARRAY_I:%.*]] = load i32, ptr [[ARRAY_I_PTR]], align 4
794; CHECK-NEXT:    [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
795; CHECK-NEXT:    [[I_NEXT]] = add nuw i32 [[I]], 1
796; CHECK-NEXT:    [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N:%.*]]
797; CHECK-NEXT:    br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
798; CHECK:       exit:
799; CHECK-NEXT:    [[RESULT2:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED2]] ]
800; CHECK-NEXT:    ret i32 [[RESULT2]]
801;
802loop.preheader:                                   ; preds = %entry
803  br label %loop
804
805loop:                                             ; preds = %guarded, %loop.preheader
806  %loop.acc = phi i32 [ %loop.acc.next, %guarded2 ], [ 0, %loop.preheader ]
807  %i = phi i32 [ %i.next, %guarded2 ], [ 0, %loop.preheader ]
808  %within.bounds = icmp ult i32 %i, %length
809  br i1 %within.bounds, label %guarded, label %deopt, !prof !0
810
811deopt:                                            ; preds = %loop
812  %result = phi i32 [ %loop.acc, %loop ]
813  call void @prevent_merging()
814  ret i32 %result
815
816guarded:                                          ; preds = %loop
817  %within.bounds2 = icmp ult i32 %i, %length2
818  br i1 %within.bounds2, label %guarded2, label %deopt2, !prof !0
819
820deopt2:                                            ; preds = %loop
821  call void @prevent_merging()
822  ret i32 -1
823
824guarded2:                                          ; preds = %loop
825  %i.i64 = zext i32 %i to i64
826  %array.i.ptr = getelementptr inbounds i32, ptr %array, i64 %i.i64
827  %array.i = load i32, ptr %array.i.ptr, align 4
828  %loop.acc.next = add i32 %loop.acc, %array.i
829  %i.next = add nuw i32 %i, 1
830  %continue = icmp ult i32 %i.next, %n
831  br i1 %continue, label %loop, label %exit
832
833exit:                                             ; preds = %guarded, %entry
834  %result2 = phi i32 [ %loop.acc.next, %guarded2 ]
835  ret i32 %result2
836}
837
838
839declare i32 @llvm.experimental.deoptimize.i32(...)
840
841!0 = !{!"branch_weights", i32 1048576, i32 1}
842!1 = !{i32 1, i32 -2147483648}
843!2 = !{i32 0, i32 50}
844