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