1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -loop-deletion -S | FileCheck %s
3
4@G = external global i32
5
6define void @test_trivial() {
7; CHECK-LABEL: @test_trivial(
8; CHECK-NEXT:  entry:
9; CHECK-NEXT:    br label [[LOOP:%.*]]
10; CHECK:       loop:
11; CHECK-NEXT:    store i32 0, i32* @G, align 4
12; CHECK-NEXT:    br i1 false, label [[LOOP_LOOP_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
13; CHECK:       loop.loop_crit_edge:
14; CHECK-NEXT:    unreachable
15; CHECK:       exit:
16; CHECK-NEXT:    ret void
17;
18entry:
19  br label %loop
20
21loop:
22  store i32 0, i32* @G
23  br i1 false, label %loop, label %exit
24
25exit:
26  ret void
27}
28
29
30define void @test_bottom_tested() {
31; CHECK-LABEL: @test_bottom_tested(
32; CHECK-NEXT:  entry:
33; CHECK-NEXT:    br label [[LOOP:%.*]]
34; CHECK:       loop:
35; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
36; CHECK-NEXT:    store i32 0, i32* @G, align 4
37; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
38; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
39; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LOOP_LOOP_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
40; CHECK:       loop.loop_crit_edge:
41; CHECK-NEXT:    unreachable
42; CHECK:       exit:
43; CHECK-NEXT:    ret void
44;
45entry:
46  br label %loop
47
48loop:
49  %iv = phi i32 [ 0, %entry], [ %iv.inc, %loop ]
50  store i32 0, i32* @G
51  %iv.inc = add i32 %iv, 1
52  %be_taken = icmp ne i32 %iv.inc, 1
53  br i1 %be_taken, label %loop, label %exit
54
55exit:
56  ret void
57}
58
59define void @test_early_exit() {
60; CHECK-LABEL: @test_early_exit(
61; CHECK-NEXT:  entry:
62; CHECK-NEXT:    br label [[LOOP:%.*]]
63; CHECK:       loop:
64; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
65; CHECK-NEXT:    store i32 0, i32* @G, align 4
66; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
67; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
68; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]
69; CHECK:       latch:
70; CHECK-NEXT:    br label [[LATCH_SPLIT:%.*]]
71; CHECK:       latch.split:
72; CHECK-NEXT:    unreachable
73; CHECK:       exit:
74; CHECK-NEXT:    ret void
75;
76entry:
77  br label %loop
78
79loop:
80  %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
81  store i32 0, i32* @G
82  %iv.inc = add i32 %iv, 1
83  %be_taken = icmp ne i32 %iv.inc, 1
84  br i1 %be_taken, label %latch, label %exit
85latch:
86  br label %loop
87
88exit:
89  ret void
90}
91
92define void @test_multi_exit1() {
93; CHECK-LABEL: @test_multi_exit1(
94; CHECK-NEXT:  entry:
95; CHECK-NEXT:    br label [[LOOP:%.*]]
96; CHECK:       loop:
97; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
98; CHECK-NEXT:    store i32 0, i32* @G, align 4
99; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
100; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
101; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]
102; CHECK:       latch:
103; CHECK-NEXT:    store i32 1, i32* @G, align 4
104; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[IV_INC]], 30
105; CHECK-NEXT:    br i1 [[COND2]], label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT]]
106; CHECK:       latch.loop_crit_edge:
107; CHECK-NEXT:    unreachable
108; CHECK:       exit:
109; CHECK-NEXT:    ret void
110;
111entry:
112  br label %loop
113
114loop:
115  %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
116  store i32 0, i32* @G
117  %iv.inc = add i32 %iv, 1
118  %be_taken = icmp ne i32 %iv.inc, 1
119  br i1 %be_taken, label %latch, label %exit
120latch:
121  store i32 1, i32* @G
122  %cond2 = icmp ult i32 %iv.inc, 30
123  br i1 %cond2, label %loop, label %exit
124
125exit:
126  ret void
127}
128
129define void @test_multi_exit2() {
130; CHECK-LABEL: @test_multi_exit2(
131; CHECK-NEXT:  entry:
132; CHECK-NEXT:    br label [[LOOP:%.*]]
133; CHECK:       loop:
134; CHECK-NEXT:    store i32 0, i32* @G, align 4
135; CHECK-NEXT:    br i1 true, label [[LATCH:%.*]], label [[EXIT:%.*]]
136; CHECK:       latch:
137; CHECK-NEXT:    store i32 1, i32* @G, align 4
138; CHECK-NEXT:    br i1 false, label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT]]
139; CHECK:       latch.loop_crit_edge:
140; CHECK-NEXT:    unreachable
141; CHECK:       exit:
142; CHECK-NEXT:    ret void
143;
144entry:
145  br label %loop
146
147loop:
148  store i32 0, i32* @G
149  br i1 true, label %latch, label %exit
150latch:
151  store i32 1, i32* @G
152  br i1 false, label %loop, label %exit
153
154exit:
155  ret void
156}
157
158; TODO: SCEV seems not to recognize this as a zero btc loop
159define void @test_multi_exit3(i1 %cond1) {
160; CHECK-LABEL: @test_multi_exit3(
161; CHECK-NEXT:  entry:
162; CHECK-NEXT:    br label [[LOOP:%.*]]
163; CHECK:       loop:
164; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ]
165; CHECK-NEXT:    store i32 0, i32* @G, align 4
166; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LATCH]], label [[EXIT:%.*]]
167; CHECK:       latch:
168; CHECK-NEXT:    store i32 1, i32* @G, align 4
169; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
170; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
171; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LOOP]], label [[EXIT]]
172; CHECK:       exit:
173; CHECK-NEXT:    ret void
174;
175entry:
176  br label %loop
177
178loop:
179  %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
180  store i32 0, i32* @G
181  br i1 %cond1, label %latch, label %exit
182latch:
183  store i32 1, i32* @G
184  %iv.inc = add i32 %iv, 1
185  %be_taken = icmp ne i32 %iv.inc, 1
186  br i1 %be_taken, label %loop, label %exit
187
188exit:
189  ret void
190}
191
192; Subtle - This is either zero btc, or infinite, thus, can't break
193; backedge
194define void @test_multi_exit4(i1 %cond1, i1 %cond2) {
195; CHECK-LABEL: @test_multi_exit4(
196; CHECK-NEXT:  entry:
197; CHECK-NEXT:    br label [[LOOP:%.*]]
198; CHECK:       loop:
199; CHECK-NEXT:    store i32 0, i32* @G, align 4
200; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]]
201; CHECK:       latch:
202; CHECK-NEXT:    store i32 1, i32* @G, align 4
203; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP]], label [[EXIT]]
204; CHECK:       exit:
205; CHECK-NEXT:    ret void
206;
207entry:
208  br label %loop
209
210loop:
211  store i32 0, i32* @G
212  br i1 %cond1, label %latch, label %exit
213latch:
214  store i32 1, i32* @G
215  br i1 %cond2, label %loop, label %exit
216
217exit:
218  ret void
219}
220
221; A simple case with multiple exit blocks
222define void @test_multi_exit5() {
223; CHECK-LABEL: @test_multi_exit5(
224; CHECK-NEXT:  entry:
225; CHECK-NEXT:    br label [[LOOP:%.*]]
226; CHECK:       loop:
227; CHECK-NEXT:    store i32 0, i32* @G, align 4
228; CHECK-NEXT:    br i1 true, label [[LATCH:%.*]], label [[EXIT1:%.*]]
229; CHECK:       latch:
230; CHECK-NEXT:    store i32 1, i32* @G, align 4
231; CHECK-NEXT:    br i1 false, label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT2:%.*]]
232; CHECK:       latch.loop_crit_edge:
233; CHECK-NEXT:    unreachable
234; CHECK:       exit1:
235; CHECK-NEXT:    ret void
236; CHECK:       exit2:
237; CHECK-NEXT:    ret void
238;
239entry:
240  br label %loop
241
242loop:
243  store i32 0, i32* @G
244  br i1 true, label %latch, label %exit1
245latch:
246  store i32 1, i32* @G
247  br i1 false, label %loop, label %exit2
248
249exit1:
250  ret void
251exit2:
252  ret void
253}
254
255define void @test_live_inner() {
256; CHECK-LABEL: @test_live_inner(
257; CHECK-NEXT:  entry:
258; CHECK-NEXT:    br label [[LOOP:%.*]]
259; CHECK:       loop:
260; CHECK-NEXT:    store i32 0, i32* @G, align 4
261; CHECK-NEXT:    br label [[INNER:%.*]]
262; CHECK:       inner:
263; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[LOOP]] ], [ [[IV_INC:%.*]], [[INNER]] ]
264; CHECK-NEXT:    store i32 [[IV]], i32* @G, align 4
265; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
266; CHECK-NEXT:    [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200
267; CHECK-NEXT:    br i1 [[CND]], label [[INNER]], label [[LATCH:%.*]]
268; CHECK:       latch:
269; CHECK-NEXT:    br i1 false, label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
270; CHECK:       latch.loop_crit_edge:
271; CHECK-NEXT:    unreachable
272; CHECK:       exit:
273; CHECK-NEXT:    ret void
274;
275entry:
276  br label %loop
277
278loop:
279  store i32 0, i32* @G
280  br label %inner
281
282inner:
283  %iv = phi i32 [0, %loop], [%iv.inc, %inner]
284  store i32 %iv, i32* @G
285  %iv.inc = add i32 %iv, 1
286  %cnd = icmp ult i32 %iv.inc, 200
287  br i1 %cnd, label %inner, label %latch
288
289latch:
290  br i1 false, label %loop, label %exit
291
292exit:
293  ret void
294}
295
296define void @test_live_outer() {
297; CHECK-LABEL: @test_live_outer(
298; CHECK-NEXT:  entry:
299; CHECK-NEXT:    br label [[LOOP:%.*]]
300; CHECK:       loop:
301; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ]
302; CHECK-NEXT:    br label [[INNER:%.*]]
303; CHECK:       inner:
304; CHECK-NEXT:    store i32 0, i32* @G, align 4
305; CHECK-NEXT:    br i1 false, label [[INNER_INNER_CRIT_EDGE:%.*]], label [[LATCH]]
306; CHECK:       inner.inner_crit_edge:
307; CHECK-NEXT:    unreachable
308; CHECK:       latch:
309; CHECK-NEXT:    store i32 [[IV]], i32* @G, align 4
310; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
311; CHECK-NEXT:    [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200
312; CHECK-NEXT:    br i1 [[CND]], label [[LOOP]], label [[EXIT:%.*]]
313; CHECK:       exit:
314; CHECK-NEXT:    ret void
315;
316entry:
317  br label %loop
318
319loop:
320  %iv = phi i32 [0, %entry], [%iv.inc, %latch]
321  br label %inner
322
323inner:
324  store i32 0, i32* @G
325  br i1 false, label %inner, label %latch
326
327latch:
328  store i32 %iv, i32* @G
329  %iv.inc = add i32 %iv, 1
330  %cnd = icmp ult i32 %iv.inc, 200
331  br i1 %cnd, label %loop, label %exit
332
333exit:
334  ret void
335}
336
337; Key point is that inner_latch drops out of the outer loop when
338; the inner loop is deleted, and thus the lcssa phi needs to be
339; in the inner_latch block to preserve LCSSA.  We either have to
340; insert the LCSSA phi, or not break the inner backedge.
341define void @loop_nest_lcssa() {
342; CHECK-LABEL: @loop_nest_lcssa(
343; CHECK-NEXT:  entry:
344; CHECK-NEXT:    [[TMP0:%.*]] = add i32 1, 2
345; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
346; CHECK:       outer_header:
347; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
348; CHECK:       inner_header:
349; CHECK-NEXT:    br i1 false, label [[INNER_LATCH:%.*]], label [[OUTER_LATCH:%.*]]
350; CHECK:       inner_latch:
351; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ [[TMP0]], [[INNER_HEADER]] ]
352; CHECK-NEXT:    br i1 false, label [[INNER_LATCH_INNER_HEADER_CRIT_EDGE:%.*]], label [[LOOPEXIT:%.*]]
353; CHECK:       inner_latch.inner_header_crit_edge:
354; CHECK-NEXT:    unreachable
355; CHECK:       outer_latch:
356; CHECK-NEXT:    br label [[OUTER_HEADER]]
357; CHECK:       loopexit:
358; CHECK-NEXT:    [[DOTLCSSA32:%.*]] = phi i32 [ [[DOTLCSSA]], [[INNER_LATCH]] ]
359; CHECK-NEXT:    unreachable
360;
361entry:
362  br label %outer_header
363
364outer_header:
365  %0 = add i32 1, 2
366  br label %inner_header
367
368inner_header:
369  br i1 false, label %inner_latch, label %outer_latch
370
371inner_latch:
372  br i1 false, label %inner_header, label %loopexit
373
374outer_latch:
375  br label %outer_header
376
377loopexit:
378  %.lcssa32 = phi i32 [ %0, %inner_latch ]
379  unreachable
380}
381