1; RUN: llc < %s -O0 -asm-verbose=false -verify-machineinstrs -disable-block-placement -wasm-disable-explicit-locals -wasm-keep-registers | FileCheck %s
2
3; Test irreducible CFG handling.
4
5target triple = "wasm32-unknown-unknown"
6
7; A simple loop with two entries.
8
9; CHECK-LABEL: test0:
10; CHECK: f64.load
11; CHECK: i32.const $[[REG:[^,]+]]=
12; CHECK: br_table  $[[REG]],
13define void @test0(double* %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
14bb:
15  %tmp = icmp eq i32 %arg2, 0
16  br i1 %tmp, label %bb6, label %bb3
17
18bb3:                                              ; preds = %bb
19  %tmp4 = getelementptr double, double* %arg, i32 %arg3
20  %tmp5 = load double, double* %tmp4, align 4
21  br label %bb13
22
23bb6:                                              ; preds = %bb13, %bb
24  %tmp7 = phi i32 [ %tmp18, %bb13 ], [ 0, %bb ]
25  %tmp8 = icmp slt i32 %tmp7, %arg1
26  br i1 %tmp8, label %bb9, label %bb19
27
28bb9:                                              ; preds = %bb6
29  %tmp10 = getelementptr double, double* %arg, i32 %tmp7
30  %tmp11 = load double, double* %tmp10, align 4
31  %tmp12 = fmul double %tmp11, 2.300000e+00
32  store double %tmp12, double* %tmp10, align 4
33  br label %bb13
34
35bb13:                                             ; preds = %bb9, %bb3
36  %tmp14 = phi double [ %tmp5, %bb3 ], [ %tmp12, %bb9 ]
37  %tmp15 = phi i32 [ undef, %bb3 ], [ %tmp7, %bb9 ]
38  %tmp16 = getelementptr double, double* %arg, i32 %tmp15
39  %tmp17 = fadd double %tmp14, 1.300000e+00
40  store double %tmp17, double* %tmp16, align 4
41  %tmp18 = add nsw i32 %tmp15, 1
42  br label %bb6
43
44bb19:                                             ; preds = %bb6
45  ret void
46}
47
48; A simple loop with two entries and an inner natural loop.
49
50; CHECK-LABEL: test1:
51; CHECK: f64.load
52; CHECK: i32.const $[[REG:[^,]+]]=
53; CHECK: br_table  $[[REG]],
54define void @test1(double* %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
55bb:
56  %tmp = icmp eq i32 %arg2, 0
57  br i1 %tmp, label %bb6, label %bb3
58
59bb3:                                              ; preds = %bb
60  %tmp4 = getelementptr double, double* %arg, i32 %arg3
61  %tmp5 = load double, double* %tmp4, align 4
62  br label %bb13
63
64bb6:                                              ; preds = %bb13, %bb
65  %tmp7 = phi i32 [ %tmp18, %bb13 ], [ 0, %bb ]
66  %tmp8 = icmp slt i32 %tmp7, %arg1
67  br i1 %tmp8, label %bb9, label %bb19
68
69bb9:                                              ; preds = %bb6
70  %tmp10 = getelementptr double, double* %arg, i32 %tmp7
71  %tmp11 = load double, double* %tmp10, align 4
72  %tmp12 = fmul double %tmp11, 2.300000e+00
73  store double %tmp12, double* %tmp10, align 4
74  br label %bb10
75
76bb10:                                             ; preds = %bb10, %bb9
77  %p = phi i32 [ 0, %bb9 ], [ %pn, %bb10 ]
78  %pn = add i32 %p, 1
79  %c = icmp slt i32 %pn, 256
80  br i1 %c, label %bb10, label %bb13
81
82bb13:                                             ; preds = %bb10, %bb3
83  %tmp14 = phi double [ %tmp5, %bb3 ], [ %tmp12, %bb10 ]
84  %tmp15 = phi i32 [ undef, %bb3 ], [ %tmp7, %bb10 ]
85  %tmp16 = getelementptr double, double* %arg, i32 %tmp15
86  %tmp17 = fadd double %tmp14, 1.300000e+00
87  store double %tmp17, double* %tmp16, align 4
88  %tmp18 = add nsw i32 %tmp15, 1
89  br label %bb6
90
91bb19:                                             ; preds = %bb6
92  ret void
93}
94
95; A simple loop 2 blocks that are both entries: A1 and A2.
96; Even though A1 and A2 both have 3 predecessors (A0, A1, and A2), not 6 but
97; only 4 new routing blocks to the dispatch block should be generated.
98
99; CHECK-LABEL: test2:
100; CHECK: br_if
101; CHECK: i32.const $[[REG:[^,]+]]=
102; CHECK: i32.const $[[REG]]=
103; CHECK: br_table  $[[REG]],
104; CHECK: i32.const $[[REG]]=
105; CHECK: i32.const $[[REG]]=
106; CHECK-NOT: i32.const $[[REG]]=
107define i32 @test2(i32) {
108entry:
109  br label %A0
110
111A0:                                               ; preds = %entry
112  %a0a = tail call i32 @test2(i32 1)
113  %a0b = icmp eq i32 %a0a, 0
114  br i1 %a0b, label %A1, label %A2
115
116A1:                                               ; preds = %A2, %A1, %A0
117  %a1a = tail call i32 @test2(i32 2)
118  %a1b = icmp eq i32 %a1a, 0
119  br i1 %a1b, label %A1, label %A2
120
121A2:                                               ; preds = %A2, %A1, %A0
122  %a2a = tail call i32 @test2(i32 3)
123  %a2b = icmp eq i32 %a2a, 0
124  br i1 %a2b, label %A1, label %A2
125}
126
127; An interesting loop with inner loop and if-else structure too.
128
129; CHECK-LABEL: test3:
130; CHECK: br_if
131define void @test3(i32 %ws) {
132entry:
133  %ws.addr = alloca i32, align 4
134  store volatile i32 %ws, i32* %ws.addr, align 4
135  %0 = load volatile i32, i32* %ws.addr, align 4
136  %tobool = icmp ne i32 %0, 0
137  br i1 %tobool, label %if.then, label %if.end
138
139if.then:                                          ; preds = %entry
140  br label %wynn
141
142if.end:                                           ; preds = %entry
143  %1 = load volatile i32, i32* %ws.addr, align 4
144  %tobool1 = icmp ne i32 %1, 0
145  br i1 %tobool1, label %if.end9, label %if.then2
146
147if.then2:                                         ; preds = %if.end
148  br label %for.cond
149
150for.cond:                                         ; preds = %wynn, %if.then7, %if.then2
151  %2 = load volatile i32, i32* %ws.addr, align 4
152  %tobool3 = icmp ne i32 %2, 0
153  br i1 %tobool3, label %if.then4, label %if.end5
154
155if.then4:                                         ; preds = %for.cond
156  br label %if.end5
157
158if.end5:                                          ; preds = %if.then4, %for.cond
159  %3 = load volatile i32, i32* %ws.addr, align 4
160  %tobool6 = icmp ne i32 %3, 0
161  br i1 %tobool6, label %if.then7, label %if.end8
162
163if.then7:                                         ; preds = %if.end5
164  br label %for.cond
165
166if.end8:                                          ; preds = %if.end5
167  br label %wynn
168
169wynn:                                             ; preds = %if.end8, %if.then
170  br label %for.cond
171
172if.end9:                                          ; preds = %if.end
173  ret void
174}
175
176; Multi-level irreducibility, after reducing in the main scope we must then
177; reduce in the inner loop that we just created.
178; CHECK: br_table
179; CHECK: br_table
180define void @pi_next() {
181entry:
182  br i1 undef, label %sw.bb5, label %return
183
184sw.bb5:                                           ; preds = %entry
185  br i1 undef, label %if.then.i49, label %if.else.i52
186
187if.then.i49:                                      ; preds = %sw.bb5
188  br label %for.inc197.i
189
190if.else.i52:                                      ; preds = %sw.bb5
191  br label %for.cond57.i
192
193for.cond57.i:                                     ; preds = %for.inc205.i, %if.else.i52
194  store i32 0, i32* undef, align 4
195  br label %for.cond65.i
196
197for.cond65.i:                                     ; preds = %for.inc201.i, %for.cond57.i
198  br i1 undef, label %for.body70.i, label %for.inc205.i
199
200for.body70.i:                                     ; preds = %for.cond65.i
201  br label %for.cond76.i
202
203for.cond76.i:                                     ; preds = %for.inc197.i, %for.body70.i
204  %0 = phi i32 [ %inc199.i, %for.inc197.i ], [ 0, %for.body70.i ]
205  %cmp81.i = icmp slt i32 %0, 0
206  br i1 %cmp81.i, label %for.body82.i, label %for.inc201.i
207
208for.body82.i:                                     ; preds = %for.cond76.i
209  br label %for.inc197.i
210
211for.inc197.i:                                     ; preds = %for.body82.i, %if.then.i49
212  %inc199.i = add nsw i32 undef, 1
213  br label %for.cond76.i
214
215for.inc201.i:                                     ; preds = %for.cond76.i
216  br label %for.cond65.i
217
218for.inc205.i:                                     ; preds = %for.cond65.i
219  br label %for.cond57.i
220
221return:                                           ; preds = %entry
222  ret void
223}
224
225; A more complx case of irreducible control flow, two interacting loops.
226; CHECK: ps_hints_apply
227; CHECK: br_table
228define void @ps_hints_apply() {
229entry:
230  br label %psh
231
232psh:                                              ; preds = %entry
233  br i1 undef, label %for.cond, label %for.body
234
235for.body:                                         ; preds = %psh
236  br label %do.body
237
238do.body:                                          ; preds = %do.cond, %for.body
239  %cmp118 = icmp eq i32* undef, undef
240  br i1 %cmp118, label %Skip, label %do.cond
241
242do.cond:                                          ; preds = %do.body
243  br label %do.body
244
245for.cond:                                         ; preds = %Skip, %psh
246  br label %for.body39
247
248for.body39:                                       ; preds = %for.cond
249  br i1 undef, label %Skip, label %do.body45
250
251do.body45:                                        ; preds = %for.body39
252  unreachable
253
254Skip:                                             ; preds = %for.body39, %do.body
255  br label %for.cond
256}
257
258; A simple sequence of loops with blocks in between, that should not be
259; misinterpreted as irreducible control flow.
260; CHECK: fannkuch_worker
261; CHECK-NOT: br_table
262define i32 @fannkuch_worker(i8* %_arg) {
263for.cond:
264  br label %do.body
265
266do.body:                                          ; preds = %do.cond, %for.cond
267  br label %for.cond1
268
269for.cond1:                                        ; preds = %for.cond1, %do.body
270  br i1 true, label %for.cond1, label %for.end
271
272for.end:                                          ; preds = %for.cond1
273  br label %do.cond
274
275do.cond:                                          ; preds = %for.end
276  br i1 true, label %do.body, label %do.end
277
278do.end:                                           ; preds = %do.cond
279  br label %for.cond2
280
281for.cond2:                                        ; preds = %for.end6, %do.end
282  br label %for.cond3
283
284for.cond3:                                        ; preds = %for.cond3, %for.cond2
285  br i1 true, label %for.cond3, label %for.end6
286
287for.end6:                                         ; preds = %for.cond3
288  br label %for.cond2
289
290return:                                           ; No predecessors!
291  ret i32 1
292}
293
294; Test an interesting pattern of nested irreducibility.
295
296; CHECK: func_2:
297; CHECK: br_table
298define void @func_2() {
299entry:
300  br i1 undef, label %lbl_937, label %if.else787
301
302lbl_937:                                          ; preds = %for.body978, %entry
303  br label %if.end965
304
305if.else787:                                       ; preds = %entry
306  br label %if.end965
307
308if.end965:                                        ; preds = %if.else787, %lbl_937
309  br label %for.cond967
310
311for.cond967:                                      ; preds = %for.end1035, %if.end965
312  br label %for.cond975
313
314for.cond975:                                      ; preds = %if.end984, %for.cond967
315  br i1 undef, label %for.body978, label %for.end1035
316
317for.body978:                                      ; preds = %for.cond975
318  br i1 undef, label %lbl_937, label %if.end984
319
320if.end984:                                        ; preds = %for.body978
321  br label %for.cond975
322
323for.end1035:                                      ; preds = %for.cond975
324  br label %for.cond967
325}
326