test/CodeGen/WebAssembly/irreducible-cfg.ll

   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
   5 target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
   6 target 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]],
  14 define void @test0(double* %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
  15 bb:
  16   %tmp = icmp eq i32 %arg2, 0
  17   br i1 %tmp, label %bb6, label %bb3
  18
  19 bb3:                                              ; preds = %bb
  20   %tmp4 = getelementptr double, double* %arg, i32 %arg3
  21   %tmp5 = load double, double* %tmp4, align 4
  22   br label %bb13
  23
  24 bb6:                                              ; 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
  29 bb9:                                              ; 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
  36 bb13:                                             ; 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
  45 bb19:                                             ; 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]],
  55 define void @test1(double* %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
  56 bb:
  57   %tmp = icmp eq i32 %arg2, 0
  58   br i1 %tmp, label %bb6, label %bb3
  59
  60 bb3:                                              ; preds = %bb
  61   %tmp4 = getelementptr double, double* %arg, i32 %arg3
  62   %tmp5 = load double, double* %tmp4, align 4
  63   br label %bb13
  64
  65 bb6:                                              ; 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
  70 bb9:                                              ; 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
  77 bb10:                                             ; 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
  83 bb13:                                             ; 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
  92 bb19:                                             ; 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]]=
 108 define i32 @test2(i32) {
 109 entry:
 110   br label %A0
 111
 112 A0:                                               ; 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
 117 A1:                                               ; 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
 122 A2:                                               ; 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
 132 define void @test3(i32 %ws) {
 133 entry:
 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
 140 if.then:                                          ; preds = %entry
 141   br label %wynn
 142
 143 if.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
 148 if.then2:                                         ; preds = %if.end
 149   br label %for.cond
 150
 151 for.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
 156 if.then4:                                         ; preds = %for.cond
 157   br label %if.end5
 158
 159 if.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
 164 if.then7:                                         ; preds = %if.end5
 165   br label %for.cond
 166
 167 if.end8:                                          ; preds = %if.end5
 168   br label %wynn
 169
 170 wynn:                                             ; preds = %if.end8, %if.then
 171   br label %for.cond
 172
 173 if.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
 181 define void @pi_next() {
 182 entry:
 183   br i1 undef, label %sw.bb5, label %return
 184
 185 sw.bb5:                                           ; preds = %entry
 186   br i1 undef, label %if.then.i49, label %if.else.i52
 187
 188 if.then.i49:                                      ; preds = %sw.bb5
 189   br label %for.inc197.i
 190
 191 if.else.i52:                                      ; preds = %sw.bb5
 192   br label %for.cond57.i
 193
 194 for.cond57.i:                                     ; preds = %for.inc205.i, %if.else.i52
 195   store i32 0, i32* undef, align 4
 196   br label %for.cond65.i
 197
 198 for.cond65.i:                                     ; preds = %for.inc201.i, %for.cond57.i
 199   br i1 undef, label %for.body70.i, label %for.inc205.i
 200
 201 for.body70.i:                                     ; preds = %for.cond65.i
 202   br label %for.cond76.i
 203
 204 for.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
 209 for.body82.i:                                     ; preds = %for.cond76.i
 210   br label %for.inc197.i
 211
 212 for.inc197.i:                                     ; preds = %for.body82.i, %if.then.i49
 213   %inc199.i = add nsw i32 undef, 1
 214   br label %for.cond76.i
 215
 216 for.inc201.i:                                     ; preds = %for.cond76.i
 217   br label %for.cond65.i
 218
 219 for.inc205.i:                                     ; preds = %for.cond65.i
 220   br label %for.cond57.i
 221
 222 return:                                           ; 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
 229 define void @ps_hints_apply() {
 230 entry:
 231   br label %psh
 232
 233 psh:                                              ; preds = %entry
 234   br i1 undef, label %for.cond, label %for.body
 235
 236 for.body:                                         ; preds = %psh
 237   br label %do.body
 238
 239 do.body:                                          ; preds = %do.cond, %for.body
 240   %cmp118 = icmp eq i32* undef, undef
 241   br i1 %cmp118, label %Skip, label %do.cond
 242
 243 do.cond:                                          ; preds = %do.body
 244   br label %do.body
 245
 246 for.cond:                                         ; preds = %Skip, %psh
 247   br label %for.body39
 248
 249 for.body39:                                       ; preds = %for.cond
 250   br i1 undef, label %Skip, label %do.body45
 251
 252 do.body45:                                        ; preds = %for.body39
 253   unreachable
 254
 255 Skip:                                             ; 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
 263 define i32 @fannkuch_worker(i8* %_arg) {
 264 for.cond:
 265   br label %do.body
 266
 267 do.body:                                          ; preds = %do.cond, %for.cond
 268   br label %for.cond1
 269
 270 for.cond1:                                        ; preds = %for.cond1, %do.body
 271   br i1 true, label %for.cond1, label %for.end
 272
 273 for.end:                                          ; preds = %for.cond1
 274   br label %do.cond
 275
 276 do.cond:                                          ; preds = %for.end
 277   br i1 true, label %do.body, label %do.end
 278
 279 do.end:                                           ; preds = %do.cond
 280   br label %for.cond2
 281
 282 for.cond2:                                        ; preds = %for.end6, %do.end
 283   br label %for.cond3
 284
 285 for.cond3:                                        ; preds = %for.cond3, %for.cond2
 286   br i1 true, label %for.cond3, label %for.end6
 287
 288 for.end6:                                         ; preds = %for.cond3
 289   br label %for.cond2
 290
 291 return:                                           ; 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
 299 define void @func_2() {
 300 entry:
 301   br i1 undef, label %lbl_937, label %if.else787
 302
 303 lbl_937:                                          ; preds = %for.body978, %entry
 304   br label %if.end965
 305
 306 if.else787:                                       ; preds = %entry
 307   br label %if.end965
 308
 309 if.end965:                                        ; preds = %if.else787, %lbl_937
 310   br label %for.cond967
 311
 312 for.cond967:                                      ; preds = %for.end1035, %if.end965
 313   br label %for.cond975
 314
 315 for.cond975:                                      ; preds = %if.end984, %for.cond967
 316   br i1 undef, label %for.body978, label %for.end1035
 317
 318 for.body978:                                      ; preds = %for.cond975
 319   br i1 undef, label %lbl_937, label %if.end984
 320
 321 if.end984:                                        ; preds = %for.body978
 322   br label %for.cond975
 323
 324 for.end1035:                                      ; preds = %for.cond975
 325   br label %for.cond967
 326 }