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