llvm/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 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]],
  13 define void @test0(ptr %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
  14 bb:
  15   %tmp = icmp eq i32 %arg2, 0
  16   br i1 %tmp, label %bb6, label %bb3
  17
  18 bb3:                                              ; preds = %bb
  19   %tmp4 = getelementptr double, ptr %arg, i32 %arg3
  20   %tmp5 = load double, ptr %tmp4, align 4
  21   br label %bb13
  22
  23 bb6:                                              ; 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
  28 bb9:                                              ; preds = %bb6
  29   %tmp10 = getelementptr double, ptr %arg, i32 %tmp7
  30   %tmp11 = load double, ptr %tmp10, align 4
  31   %tmp12 = fmul double %tmp11, 2.300000e+00
  32   store double %tmp12, ptr %tmp10, align 4
  33   br label %bb13
  34
  35 bb13:                                             ; preds = %bb9, %bb3
  36   %tmp14 = phi double [ %tmp5, %bb3 ], [ %tmp12, %bb9 ]
  37   %tmp15 = phi i32 [ undef, %bb3 ], [ %tmp7, %bb9 ]
  38   %tmp16 = getelementptr double, ptr %arg, i32 %tmp15
  39   %tmp17 = fadd double %tmp14, 1.300000e+00
  40   store double %tmp17, ptr %tmp16, align 4
  41   %tmp18 = add nsw i32 %tmp15, 1
  42   br label %bb6
  43
  44 bb19:                                             ; 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]],
  54 define void @test1(ptr %arg, i32 %arg1, i32 %arg2, i32 %arg3) {
  55 bb:
  56   %tmp = icmp eq i32 %arg2, 0
  57   br i1 %tmp, label %bb6, label %bb3
  58
  59 bb3:                                              ; preds = %bb
  60   %tmp4 = getelementptr double, ptr %arg, i32 %arg3
  61   %tmp5 = load double, ptr %tmp4, align 4
  62   br label %bb13
  63
  64 bb6:                                              ; 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
  69 bb9:                                              ; preds = %bb6
  70   %tmp10 = getelementptr double, ptr %arg, i32 %tmp7
  71   %tmp11 = load double, ptr %tmp10, align 4
  72   %tmp12 = fmul double %tmp11, 2.300000e+00
  73   store double %tmp12, ptr %tmp10, align 4
  74   br label %bb10
  75
  76 bb10:                                             ; 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
  82 bb13:                                             ; preds = %bb10, %bb3
  83   %tmp14 = phi double [ %tmp5, %bb3 ], [ %tmp12, %bb10 ]
  84   %tmp15 = phi i32 [ undef, %bb3 ], [ %tmp7, %bb10 ]
  85   %tmp16 = getelementptr double, ptr %arg, i32 %tmp15
  86   %tmp17 = fadd double %tmp14, 1.300000e+00
  87   store double %tmp17, ptr %tmp16, align 4
  88   %tmp18 = add nsw i32 %tmp15, 1
  89   br label %bb6
  90
  91 bb19:                                             ; 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]]=
 107 define i32 @test2(i32) {
 108 entry:
 109   br label %A0
 110
 111 A0:                                               ; 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
 116 A1:                                               ; 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
 121 A2:                                               ; 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
 131 define void @test3(i32 %ws) {
 132 entry:
 133   %ws.addr = alloca i32, align 4
 134   store volatile i32 %ws, ptr %ws.addr, align 4
 135   %0 = load volatile i32, ptr %ws.addr, align 4
 136   %tobool = icmp ne i32 %0, 0
 137   br i1 %tobool, label %if.then, label %if.end
 138
 139 if.then:                                          ; preds = %entry
 140   br label %wynn
 141
 142 if.end:                                           ; preds = %entry
 143   %1 = load volatile i32, ptr %ws.addr, align 4
 144   %tobool1 = icmp ne i32 %1, 0
 145   br i1 %tobool1, label %if.end9, label %if.then2
 146
 147 if.then2:                                         ; preds = %if.end
 148   br label %for.cond
 149
 150 for.cond:                                         ; preds = %wynn, %if.then7, %if.then2
 151   %2 = load volatile i32, ptr %ws.addr, align 4
 152   %tobool3 = icmp ne i32 %2, 0
 153   br i1 %tobool3, label %if.then4, label %if.end5
 154
 155 if.then4:                                         ; preds = %for.cond
 156   br label %if.end5
 157
 158 if.end5:                                          ; preds = %if.then4, %for.cond
 159   %3 = load volatile i32, ptr %ws.addr, align 4
 160   %tobool6 = icmp ne i32 %3, 0
 161   br i1 %tobool6, label %if.then7, label %if.end8
 162
 163 if.then7:                                         ; preds = %if.end5
 164   br label %for.cond
 165
 166 if.end8:                                          ; preds = %if.end5
 167   br label %wynn
 168
 169 wynn:                                             ; preds = %if.end8, %if.then
 170   br label %for.cond
 171
 172 if.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
 180 define void @pi_next() {
 181 entry:
 182   br i1 undef, label %sw.bb5, label %return
 183
 184 sw.bb5:                                           ; preds = %entry
 185   br i1 undef, label %if.then.i49, label %if.else.i52
 186
 187 if.then.i49:                                      ; preds = %sw.bb5
 188   br label %for.inc197.i
 189
 190 if.else.i52:                                      ; preds = %sw.bb5
 191   br label %for.cond57.i
 192
 193 for.cond57.i:                                     ; preds = %for.inc205.i, %if.else.i52
 194   store i32 0, ptr undef, align 4
 195   br label %for.cond65.i
 196
 197 for.cond65.i:                                     ; preds = %for.inc201.i, %for.cond57.i
 198   br i1 undef, label %for.body70.i, label %for.inc205.i
 199
 200 for.body70.i:                                     ; preds = %for.cond65.i
 201   br label %for.cond76.i
 202
 203 for.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
 208 for.body82.i:                                     ; preds = %for.cond76.i
 209   br label %for.inc197.i
 210
 211 for.inc197.i:                                     ; preds = %for.body82.i, %if.then.i49
 212   %inc199.i = add nsw i32 undef, 1
 213   br label %for.cond76.i
 214
 215 for.inc201.i:                                     ; preds = %for.cond76.i
 216   br label %for.cond65.i
 217
 218 for.inc205.i:                                     ; preds = %for.cond65.i
 219   br label %for.cond57.i
 220
 221 return:                                           ; 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
 228 define void @ps_hints_apply() {
 229 entry:
 230   br label %psh
 231
 232 psh:                                              ; preds = %entry
 233   br i1 undef, label %for.cond, label %for.body
 234
 235 for.body:                                         ; preds = %psh
 236   br label %do.body
 237
 238 do.body:                                          ; preds = %do.cond, %for.body
 239   %cmp118 = icmp eq ptr undef, undef
 240   br i1 %cmp118, label %Skip, label %do.cond
 241
 242 do.cond:                                          ; preds = %do.body
 243   br label %do.body
 244
 245 for.cond:                                         ; preds = %Skip, %psh
 246   br label %for.body39
 247
 248 for.body39:                                       ; preds = %for.cond
 249   br i1 undef, label %Skip, label %do.body45
 250
 251 do.body45:                                        ; preds = %for.body39
 252   unreachable
 253
 254 Skip:                                             ; 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
 262 define i32 @fannkuch_worker(ptr %_arg) {
 263 for.cond:
 264   br label %do.body
 265
 266 do.body:                                          ; preds = %do.cond, %for.cond
 267   br label %for.cond1
 268
 269 for.cond1:                                        ; preds = %for.cond1, %do.body
 270   br i1 true, label %for.cond1, label %for.end
 271
 272 for.end:                                          ; preds = %for.cond1
 273   br label %do.cond
 274
 275 do.cond:                                          ; preds = %for.end
 276   br i1 true, label %do.body, label %do.end
 277
 278 do.end:                                           ; preds = %do.cond
 279   br label %for.cond2
 280
 281 for.cond2:                                        ; preds = %for.end6, %do.end
 282   br label %for.cond3
 283
 284 for.cond3:                                        ; preds = %for.cond3, %for.cond2
 285   br i1 true, label %for.cond3, label %for.end6
 286
 287 for.end6:                                         ; preds = %for.cond3
 288   br label %for.cond2
 289
 290 return:                                           ; 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
 298 define void @func_2() {
 299 entry:
 300   br i1 undef, label %lbl_937, label %if.else787
 301
 302 lbl_937:                                          ; preds = %for.body978, %entry
 303   br label %if.end965
 304
 305 if.else787:                                       ; preds = %entry
 306   br label %if.end965
 307
 308 if.end965:                                        ; preds = %if.else787, %lbl_937
 309   br label %for.cond967
 310
 311 for.cond967:                                      ; preds = %for.end1035, %if.end965
 312   br label %for.cond975
 313
 314 for.cond975:                                      ; preds = %if.end984, %for.cond967
 315   br i1 undef, label %for.body978, label %for.end1035
 316
 317 for.body978:                                      ; preds = %for.cond975
 318   br i1 undef, label %lbl_937, label %if.end984
 319
 320 if.end984:                                        ; preds = %for.body978
 321   br label %for.cond975
 322
 323 for.end1035:                                      ; preds = %for.cond975
 324   br label %for.cond967
 325 }