Gitiles
Code Review Sign In
gerrit-public.fairphone.software / toolchain / llvm-project / 00bb397b0dc79fcad27bfe63456a2100039706f2 / . / llvm / test / Transforms / IndVarSimplify / loop-predication.ll
blob: 77c18ef23d7dfc75027bcbe910f2fceae5aa258d [file] [log] [blame]
Philip Reames02006262019-10-01 17:03:44 +0000[diff] [blame]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]]
Philip Reames02006262019-10-01 17:03:44 +0000[diff] [blame]467; CHECK-NEXT: br label [[LOOP:%.*]]
468; CHECK: loop:
469; CHECK-NEXT: [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED1:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
470; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED1]] ], [ 0, [[LOOP_PREHEADER]] ]
471; CHECK-NEXT: br i1 [[TMP3]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
472; CHECK: deopt:
473; CHECK-NEXT: call void @prevent_merging()
474; CHECK-NEXT: ret i32 -1
475; CHECK: guarded:
476; CHECK-NEXT: [[I_I64:%.*]] = zext i32 [[I]] to i64
477; CHECK-NEXT: [[ARRAY_1_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_1:%.*]], i64 [[I_I64]]
478; CHECK-NEXT: [[ARRAY_1_I:%.*]] = load i32, i32* [[ARRAY_1_I_PTR]], align 4
479; CHECK-NEXT: [[LOOP_ACC_1:%.*]] = add i32 [[LOOP_ACC]], [[ARRAY_1_I]]
Philip Reames8cbcd2f2019-10-20 23:38:02 +0000[diff] [blame]480; CHECK-NEXT: br i1 true, label [[GUARDED1]], label [[DEOPT2:%.*]], !prof !0
Philip Reames02006262019-10-01 17:03:44 +0000[diff] [blame]481; CHECK: deopt2:
482; CHECK-NEXT: call void @prevent_merging()
483; CHECK-NEXT: ret i32 -1
484; CHECK: guarded1:
485; CHECK-NEXT: [[ARRAY_3_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY_3:%.*]], i64 [[I_I64]]
486; CHECK-NEXT: [[ARRAY_3_I:%.*]] = load i32, i32* [[ARRAY_3_I_PTR]], align 4
487; CHECK-NEXT: [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC_1]], [[ARRAY_3_I]]
488; CHECK-NEXT: [[I_NEXT]] = add nuw i32 [[I]], 1
489; CHECK-NEXT: [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N]]
490; CHECK-NEXT: br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
491; CHECK: exit:
492; CHECK-NEXT: [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED1]] ]
493; CHECK-NEXT: ret i32 [[RESULT]]
494;
495loop.preheader: ; preds = %entry
496 br label %loop
497
498loop: ; preds = %guarded4, %loop.preheader
499 %loop.acc = phi i32 [ %loop.acc.next, %guarded1 ], [ 0, %loop.preheader ]
500 %i = phi i32 [ %i.next, %guarded1 ], [ 0, %loop.preheader ]
501 %within.bounds.1 = icmp ult i32 %i, %length
502 br i1 %within.bounds.1, label %guarded, label %deopt, !prof !0
503
504deopt: ; preds = %loop
505 call void @prevent_merging()
506 ret i32 -1
507
508guarded: ; preds = %loop
509 %i.i64 = zext i32 %i to i64
510 %array.1.i.ptr = getelementptr inbounds i32, i32* %array.1, i64 %i.i64
511 %array.1.i = load i32, i32* %array.1.i.ptr, align 4
512 %loop.acc.1 = add i32 %loop.acc, %array.1.i
513 %within.bounds.2 = icmp ult i32 %i, %length
514 br i1 %within.bounds.2, label %guarded1, label %deopt2, !prof !0
515
516deopt2: ; preds = %guarded
517 call void @prevent_merging()
518 ret i32 -1
519
520guarded1: ; preds = %guarded1
521 %array.3.i.ptr = getelementptr inbounds i32, i32* %array.3, i64 %i.i64
522 %array.3.i = load i32, i32* %array.3.i.ptr, align 4
523 %loop.acc.next = add i32 %loop.acc.1, %array.3.i
524 %i.next = add nuw i32 %i, 1
525 %continue = icmp ult i32 %i.next, %n
526 br i1 %continue, label %loop, label %exit
527
528exit:
529 %result = phi i32 [ %loop.acc.next, %guarded1 ]
530 ret i32 %result
531}
532
533
534define i32 @provably_taken(i32* %array, i32* %length.ptr) {
535; CHECK-LABEL: @provably_taken(
536; CHECK-NEXT: loop.preheader:
537; CHECK-NEXT: br label [[LOOP:%.*]]
538; CHECK: loop:
539; CHECK-NEXT: [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
540; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
541; CHECK-NEXT: br i1 false, label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
542; CHECK: deopt:
543; CHECK-NEXT: call void @prevent_merging()
544; CHECK-NEXT: ret i32 -1
545; CHECK: guarded:
546; CHECK-NEXT: [[I_I64:%.*]] = zext i32 [[I]] to i64
547; CHECK-NEXT: [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
548; CHECK-NEXT: [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
549; CHECK-NEXT: [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
550; CHECK-NEXT: [[I_NEXT]] = add nuw nsw i32 [[I]], 1
551; CHECK-NEXT: br i1 true, label [[LOOP]], label [[EXIT:%.*]]
552; CHECK: exit:
553; CHECK-NEXT: [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
554; CHECK-NEXT: ret i32 [[RESULT]]
555;
556loop.preheader:
557 %length = load i32, i32* %length.ptr, !range !2
558 br label %loop
559
560loop: ; preds = %guarded, %loop.preheader
561 %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
562 %i = phi i32 [ %i.next, %guarded ], [ 0, %loop.preheader ]
563 %within.bounds = icmp ult i32 %i, %length
564 br i1 %within.bounds, label %guarded, label %deopt, !prof !0
565
566deopt: ; preds = %loop
567 call void @prevent_merging()
568 ret i32 -1
569
570guarded: ; preds = %loop
571 %i.i64 = zext i32 %i to i64
572 %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
573 %array.i = load i32, i32* %array.i.ptr, align 4
574 %loop.acc.next = add i32 %loop.acc, %array.i
575 %i.next = add nuw i32 %i, 1
576 %continue = icmp slt i32 %i.next, 200
577 br i1 %continue, label %loop, label %exit
578
579exit: ; preds = %guarded
580 %result = phi i32 [ %loop.acc.next, %guarded ]
581 ret i32 %result
582}
583
584; Non-latch exits can still be predicated
585define i32 @unconditional_latch(i32* %a, i32 %length) {
586; CHECK-LABEL: @unconditional_latch(
587; CHECK-NEXT: loop.preheader:
588; CHECK-NEXT: br label [[LOOP:%.*]]
589; CHECK: loop:
590; CHECK-NEXT: br i1 false, label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
591; CHECK: deopt:
592; CHECK-NEXT: call void @prevent_merging()
593; CHECK-NEXT: ret i32 -1
594; CHECK: guarded:
595; CHECK-NEXT: br label [[LOOP]]
596;
597loop.preheader:
598 br label %loop
599
600loop: ; preds = %guarded, %loop.preheader
601 %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
602 %within.bounds = icmp ult i32 %i, %length
603 br i1 %within.bounds, label %guarded, label %deopt, !prof !0
604
605deopt: ; preds = %loop
606 call void @prevent_merging()
607 ret i32 -1
608
609guarded: ; preds = %loop
610 %i.next = add i32 %i, 1
611 br label %loop
612}
613
614; Side effect in loop must run proper number of times
615define i32 @unconditional_latch_with_side_effect(i32* %a, i32 %length) {
616; CHECK-LABEL: @unconditional_latch_with_side_effect(
617; CHECK-NEXT: loop.preheader:
618; CHECK-NEXT: br label [[LOOP:%.*]]
619; CHECK: loop:
620; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED:%.*]] ], [ 400, [[LOOP_PREHEADER:%.*]] ]
621; CHECK-NEXT: [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
622; CHECK-NEXT: br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
623; CHECK: deopt:
624; CHECK-NEXT: call void @prevent_merging()
625; CHECK-NEXT: ret i32 -1
626; CHECK: guarded:
627; CHECK-NEXT: store volatile i32 0, i32* [[A:%.*]]
628; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1
629; CHECK-NEXT: br label [[LOOP]]
630;
631loop.preheader:
632 br label %loop
633
634loop: ; preds = %guarded, %loop.preheader
635 %i = phi i32 [ %i.next, %guarded ], [ 400, %loop.preheader ]
636 %within.bounds = icmp ult i32 %i, %length
637 br i1 %within.bounds, label %guarded, label %deopt, !prof !0
638
639deopt: ; preds = %loop
640 call void @prevent_merging()
641 ret i32 -1
642
643guarded: ; preds = %loop
644 store volatile i32 0, i32* %a
645 %i.next = add i32 %i, 1
646 br label %loop
647}
648
649; Demonstrate that this approach works with IVs of different steps, and types
650; This version uses a manually lftred exit condition to work around an issue described
651; in detail on next test.
652define i32 @different_ivs(i32* %array, i32 %length, i32 %n) {
653; CHECK-LABEL: @different_ivs(
654; CHECK-NEXT: loop.preheader:
655; CHECK-NEXT: [[N64:%.*]] = zext i32 [[N:%.*]] to i64
656; CHECK-NEXT: [[TMP0:%.*]] = icmp ugt i64 [[N64]], 1
657; CHECK-NEXT: [[UMAX:%.*]] = select i1 [[TMP0]], i64 [[N64]], i64 1
658; CHECK-NEXT: [[TMP1:%.*]] = add nsw i64 [[UMAX]], -1
659; CHECK-NEXT: [[TMP2:%.*]] = zext i32 [[LENGTH:%.*]] to i64
660; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i64 [[TMP1]], [[TMP2]]
661; CHECK-NEXT: [[UMIN:%.*]] = select i1 [[TMP3]], i64 [[TMP1]], i64 [[TMP2]]
662; CHECK-NEXT: [[TMP4:%.*]] = zext i32 [[LENGTH]] to i64
663; CHECK-NEXT: [[TMP5:%.*]] = icmp ne i64 [[TMP4]], [[UMIN]]
664; CHECK-NEXT: br label [[LOOP:%.*]]
665; CHECK: loop:
666; CHECK-NEXT: [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
667; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
668; CHECK-NEXT: br i1 [[TMP5]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
669; CHECK: deopt:
670; CHECK-NEXT: call void @prevent_merging()
671; CHECK-NEXT: ret i32 -1
672; CHECK: guarded:
673; CHECK-NEXT: [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I]]
674; CHECK-NEXT: [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
675; CHECK-NEXT: [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
676; CHECK-NEXT: [[I_NEXT]] = add nuw nsw i64 [[I]], 1
677; CHECK-NEXT: [[CONTINUE:%.*]] = icmp ult i64 [[I_NEXT]], [[N64]]
678; CHECK-NEXT: br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
679; CHECK: exit:
680; CHECK-NEXT: [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
681; CHECK-NEXT: ret i32 [[RESULT]]
682;
683loop.preheader:
684 %j.start = sub nuw nsw i32 %length, 1
685 %n64 = zext i32 %n to i64
686 br label %loop
687
688loop:
689 %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
690 %i = phi i64 [ %i.next, %guarded ], [ 0, %loop.preheader ]
691 %j = phi i32 [ %j.next, %guarded ], [ %j.start, %loop.preheader ]
692 %within.bounds = icmp ne i32 %j, -1
693 br i1 %within.bounds, label %guarded, label %deopt, !prof !0
694
695deopt:
696 call void @prevent_merging()
697 ret i32 -1
698
699guarded:
700 %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i
701 %array.i = load i32, i32* %array.i.ptr, align 4
702 %loop.acc.next = add i32 %loop.acc, %array.i
703 %i.next = add nuw i64 %i, 1
704 %j.next = sub nuw i32 %j, 1
705 %continue = icmp ult i64 %i.next, %n64
706 br i1 %continue, label %loop, label %exit
707
708exit:
709 %result = phi i32 [ %loop.acc.next, %guarded ]
710 ret i32 %result
711}
712
713; TODO: We're failing to compute an exit count for the bounds check.
714; From some quick analysis, it looks like we don't handle -1 step
715; in howManyLessThans. Should be a simple fix.
716define i32 @different_ivs2(i32* %array, i32 %length, i32 %n) {
717; CHECK-LABEL: @different_ivs2(
718; CHECK-NEXT: entry:
719; CHECK-NEXT: [[POS_LENGTH:%.*]] = icmp sgt i32 [[LENGTH:%.*]], 0
720; CHECK-NEXT: br i1 [[POS_LENGTH]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
721; CHECK: loop.preheader:
722; CHECK-NEXT: [[J_START:%.*]] = sub nuw nsw i32 [[LENGTH]], 1
723; CHECK-NEXT: [[N64:%.*]] = zext i32 [[N:%.*]] to i64
724; CHECK-NEXT: br label [[LOOP:%.*]]
725; CHECK: loop:
726; CHECK-NEXT: [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
727; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[GUARDED]] ], [ 0, [[LOOP_PREHEADER]] ]
728; CHECK-NEXT: [[J:%.*]] = phi i32 [ [[J_NEXT:%.*]], [[GUARDED]] ], [ [[J_START]], [[LOOP_PREHEADER]] ]
729; CHECK-NEXT: [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[J]], [[LENGTH]]
730; CHECK-NEXT: br i1 [[WITHIN_BOUNDS]], label [[GUARDED]], label [[DEOPT:%.*]], !prof !0
731; CHECK: deopt:
732; CHECK-NEXT: call void @prevent_merging()
733; CHECK-NEXT: ret i32 -1
734; CHECK: guarded:
735; CHECK-NEXT: [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I]]
736; CHECK-NEXT: [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
737; CHECK-NEXT: [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
738; CHECK-NEXT: [[I_NEXT]] = add nuw nsw i64 [[I]], 1
739; CHECK-NEXT: [[J_NEXT]] = sub nuw i32 [[J]], 1
740; CHECK-NEXT: [[CONTINUE:%.*]] = icmp ult i64 [[I_NEXT]], [[N64]]
741; CHECK-NEXT: br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
742; CHECK: exit.loopexit:
743; CHECK-NEXT: [[LOOP_ACC_NEXT_LCSSA:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED]] ]
744; CHECK-NEXT: br label [[EXIT]]
745; CHECK: exit:
746; CHECK-NEXT: [[RESULT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_ACC_NEXT_LCSSA]], [[EXIT_LOOPEXIT]] ]
747; CHECK-NEXT: ret i32 [[RESULT]]
748;
749entry:
750 %pos_length = icmp sgt i32 %length, 0
751 br i1 %pos_length, label %loop.preheader, label %exit
752
753loop.preheader:
754 %j.start = sub nuw nsw i32 %length, 1
755 %n64 = zext i32 %n to i64
756 br label %loop
757
758loop:
759 %loop.acc = phi i32 [ %loop.acc.next, %guarded ], [ 0, %loop.preheader ]
760 %i = phi i64 [ %i.next, %guarded ], [ 0, %loop.preheader ]
761 %j = phi i32 [ %j.next, %guarded ], [ %j.start, %loop.preheader ]
762 %within.bounds = icmp ult i32 %j, %length
763 br i1 %within.bounds, label %guarded, label %deopt, !prof !0
764
765deopt:
766 call void @prevent_merging()
767 ret i32 -1
768
769guarded:
770 %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i
771 %array.i = load i32, i32* %array.i.ptr, align 4
772 %loop.acc.next = add i32 %loop.acc, %array.i
773 %i.next = add nuw i64 %i, 1
774 %j.next = sub nuw i32 %j, 1
775 %continue = icmp ult i64 %i.next, %n64
776 br i1 %continue, label %loop, label %exit
777
778exit:
779 %result = phi i32 [ %loop.acc.next, %guarded ], [0, %entry]
780 ret i32 %result
781}
782
Philip Reames2b161cd2019-10-14 19:49:40 +0000[diff] [blame]783; If we have a dominating exit (exit1) which can't be itself rewritten, we
784; can't rewrite a later exit (exit2). Doing so would cause the loop to exit
785; from the exit2 when it should have exited from exit1.
Philip Reames8cbcd2f2019-10-20 23:38:02 +0000[diff] [blame]786define i32 @neg_dominating_exit(i32* %array, i32 %length, i32 %length2, i32 %n) {
Philip Reames2b161cd2019-10-14 19:49:40 +0000[diff] [blame]787; CHECK-LABEL: @neg_dominating_exit(
788; CHECK-NEXT: loop.preheader:
Philip Reames2b161cd2019-10-14 19:49:40 +0000[diff] [blame]789; CHECK-NEXT: br label [[LOOP:%.*]]
790; CHECK: loop:
791; CHECK-NEXT: [[LOOP_ACC:%.*]] = phi i32 [ [[LOOP_ACC_NEXT:%.*]], [[GUARDED2:%.*]] ], [ 0, [[LOOP_PREHEADER:%.*]] ]
792; CHECK-NEXT: [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[GUARDED2]] ], [ 0, [[LOOP_PREHEADER]] ]
Philip Reamesd4346582019-10-16 19:58:26 +0000[diff] [blame]793; CHECK-NEXT: [[WITHIN_BOUNDS:%.*]] = icmp ult i32 [[I]], [[LENGTH:%.*]]
Philip Reames2b161cd2019-10-14 19:49:40 +0000[diff] [blame]794; CHECK-NEXT: br i1 [[WITHIN_BOUNDS]], label [[GUARDED:%.*]], label [[DEOPT:%.*]], !prof !0
795; CHECK: deopt:
796; CHECK-NEXT: [[RESULT:%.*]] = phi i32 [ [[LOOP_ACC]], [[LOOP]] ]
797; CHECK-NEXT: call void @prevent_merging()
798; CHECK-NEXT: ret i32 [[RESULT]]
799; CHECK: guarded:
Philip Reames8cbcd2f2019-10-20 23:38:02 +0000[diff] [blame]800; CHECK-NEXT: [[WITHIN_BOUNDS2:%.*]] = icmp ult i32 [[I]], [[LENGTH2:%.*]]
Philip Reamesd4346582019-10-16 19:58:26 +0000[diff] [blame]801; CHECK-NEXT: br i1 [[WITHIN_BOUNDS2]], label [[GUARDED2]], label [[DEOPT2:%.*]], !prof !0
Philip Reames2b161cd2019-10-14 19:49:40 +0000[diff] [blame]802; CHECK: deopt2:
803; CHECK-NEXT: call void @prevent_merging()
804; CHECK-NEXT: ret i32 -1
805; CHECK: guarded2:
806; CHECK-NEXT: [[I_I64:%.*]] = zext i32 [[I]] to i64
807; CHECK-NEXT: [[ARRAY_I_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARRAY:%.*]], i64 [[I_I64]]
808; CHECK-NEXT: [[ARRAY_I:%.*]] = load i32, i32* [[ARRAY_I_PTR]], align 4
809; CHECK-NEXT: [[LOOP_ACC_NEXT]] = add i32 [[LOOP_ACC]], [[ARRAY_I]]
810; CHECK-NEXT: [[I_NEXT]] = add nuw i32 [[I]], 1
Philip Reamesd4346582019-10-16 19:58:26 +0000[diff] [blame]811; CHECK-NEXT: [[CONTINUE:%.*]] = icmp ult i32 [[I_NEXT]], [[N:%.*]]
Philip Reames2b161cd2019-10-14 19:49:40 +0000[diff] [blame]812; CHECK-NEXT: br i1 [[CONTINUE]], label [[LOOP]], label [[EXIT:%.*]]
813; CHECK: exit:
814; CHECK-NEXT: [[RESULT2:%.*]] = phi i32 [ [[LOOP_ACC_NEXT]], [[GUARDED2]] ]
815; CHECK-NEXT: ret i32 [[RESULT2]]
816;
817loop.preheader: ; preds = %entry
818 br label %loop
819
820loop: ; preds = %guarded, %loop.preheader
821 %loop.acc = phi i32 [ %loop.acc.next, %guarded2 ], [ 0, %loop.preheader ]
822 %i = phi i32 [ %i.next, %guarded2 ], [ 0, %loop.preheader ]
823 %within.bounds = icmp ult i32 %i, %length
824 br i1 %within.bounds, label %guarded, label %deopt, !prof !0
825
826deopt: ; preds = %loop
827 %result = phi i32 [ %loop.acc, %loop ]
828 call void @prevent_merging()
829 ret i32 %result
830
831guarded: ; preds = %loop
Philip Reames8cbcd2f2019-10-20 23:38:02 +0000[diff] [blame]832 %within.bounds2 = icmp ult i32 %i, %length2
Philip Reames2b161cd2019-10-14 19:49:40 +0000[diff] [blame]833 br i1 %within.bounds2, label %guarded2, label %deopt2, !prof !0
834
835deopt2: ; preds = %loop
836 call void @prevent_merging()
837 ret i32 -1
838
839guarded2: ; preds = %loop
840 %i.i64 = zext i32 %i to i64
841 %array.i.ptr = getelementptr inbounds i32, i32* %array, i64 %i.i64
842 %array.i = load i32, i32* %array.i.ptr, align 4
843 %loop.acc.next = add i32 %loop.acc, %array.i
844 %i.next = add nuw i32 %i, 1
845 %continue = icmp ult i32 %i.next, %n
846 br i1 %continue, label %loop, label %exit
847
848exit: ; preds = %guarded, %entry
849 %result2 = phi i32 [ %loop.acc.next, %guarded2 ]
850 ret i32 %result2
851}
Philip Reames02006262019-10-01 17:03:44 +0000[diff] [blame]852
853
854declare i32 @llvm.experimental.deoptimize.i32(...)
855
856!0 = !{!"branch_weights", i32 1048576, i32 1}
857!1 = !{i32 1, i32 -2147483648}
858!2 = !{i32 0, i32 50}