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