br_if-to-table (#1313)

Implements #1309: subsequent br_ifs that compare the same value to various constants are converted into a br_table in a block,

(br_if $x (i32.eq (get_local $a) (i32.const 0)))
(br_if $y (i32.eq (get_local $a) (i32.const 1)))
(br_if $z (i32.eq (get_local $a) (i32.const 2)))
  ==>
(block $tablify
 (br_table $x $y $z $tablify
  (get_local $a)
 )
)

The constants for when to apply this (e.g., not if the range of values would make a huge jump table) are fairly conservative, I think, but hard to tell. Probably should be tweaked based on our experience with the pass in practice later on.

2 files changed, 797 insertions, 0 deletions

diff --git a/test/passes/remove-unused-brs.txt b/test/passes/remove-unused-brs.txt
index 529fa6152..8fc58887a 100644
--- a/test/passes/remove-unused-brs.txt
+++ b/test/passes/remove-unused-brs.txt
@@ -9,6 +9,7 @@
  (type $7 (func (result i64)))
  (type $8 (func (result f32)))
  (type $9 (func (param i32) (result f32)))
+ (type $10 (func (param i32) (result i32)))
  (memory $0 256 256)
  (func $b0-yes (; 0 ;) (type $0) (param $i1 i32)
   (block $topmost
@@ -1156,4 +1157,505 @@
    )
   )
  )
+ (func $br-to-table (; 46 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (nop)
+     (nop)
+     (block $tablify|0
+      (br_table $x $y $z $tablify|0
+       (get_local $a)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-too-few (; 47 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (get_local $a)
+       (i32.const 0)
+      )
+     )
+     (br_if $x
+      (i32.eq
+       (get_local $a)
+       (i32.const 1)
+      )
+     )
+    )
+   )
+  )
+ )
+ (func $br-to-table-one-more (; 48 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (nop)
+     (nop)
+     (nop)
+     (block $tablify|0
+      (br_table $x $y $z $x $tablify|0
+       (get_local $a)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-overlap (; 49 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (get_local $a)
+       (i32.const 0)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (get_local $a)
+       (i32.const 1)
+      )
+     )
+     (br_if $z
+      (i32.eq
+       (get_local $a)
+       (i32.const 1)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-overlap-start (; 50 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (get_local $a)
+       (i32.const 0)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (get_local $a)
+       (i32.const 0)
+      )
+     )
+     (br_if $z
+      (i32.eq
+       (get_local $a)
+       (i32.const 1)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-offset (; 51 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (nop)
+     (nop)
+     (block $tablify|0
+      (br_table $x $y $z $tablify|0
+       (i32.sub
+        (get_local $a)
+        (i32.const 15)
+       )
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-RANGE-high (; 52 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (get_local $a)
+       (i32.const 0)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (get_local $a)
+       (i32.const 1)
+      )
+     )
+     (br_if $z
+      (i32.eq
+       (get_local $a)
+       (i32.const 10)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-RANGE-low (; 53 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (nop)
+     (nop)
+     (block $tablify|0
+      (br_table $x $tablify|0 $tablify|0 $y $tablify|0 $tablify|0 $tablify|0 $tablify|0 $tablify|0 $z $tablify|0
+       (get_local $a)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-bad (; 54 ;) (type $10) (param $a i32) (result i32)
+  (block $value (result i32)
+   (block $x
+    (block $y
+     (block $z
+      (nop)
+      (br $x)
+      (nop)
+      (nop)
+      (block $tablify|0
+       (br_table $x $y $z $tablify|0
+        (get_local $a)
+       )
+      )
+      (unreachable)
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (i32.const 2000)
+  )
+ )
+ (func $br-to-table-bad2 (; 55 ;) (type $10) (param $a i32) (result i32)
+  (block $value (result i32)
+   (block $x
+    (block $y
+     (block $z
+      (nop)
+      (drop
+       (br_if $value
+        (i32.const 1000)
+        (i32.eq
+         (get_local $a)
+         (i32.const 0)
+        )
+       )
+      )
+      (nop)
+      (nop)
+      (block $tablify|0
+       (br_table $x $y $z $tablify|0
+        (get_local $a)
+       )
+      )
+      (unreachable)
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (i32.const 2000)
+  )
+ )
+ (func $br-to-table-bad3 (; 56 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (i32.const 10)
+       (i32.const 0)
+      )
+     )
+     (nop)
+     (nop)
+     (block $tablify|0
+      (br_table $x $y $z $tablify|0
+       (get_local $a)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-multi (; 57 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (nop)
+     (nop)
+     (block $tablify|0
+      (br_table $z $y $x $tablify|0
+       (i32.sub
+        (i32.const 10)
+        (i32.const 5)
+       )
+      )
+     )
+     (nop)
+     (nop)
+     (block $tablify|00
+      (br_table $x $y $z $tablify|00
+       (get_local $a)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-bad4 (; 58 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.ne
+       (get_local $a)
+       (i32.const 0)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (get_local $a)
+       (i32.const 1)
+      )
+     )
+     (br_if $z
+      (i32.eq
+       (get_local $a)
+       (i32.const 2)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-bad5 (; 59 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (get_local $a)
+       (get_local $a)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (get_local $a)
+       (get_local $a)
+      )
+     )
+     (br_if $z
+      (i32.eq
+       (get_local $a)
+       (get_local $a)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-bad6 (; 60 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (call $b13)
+       (i32.const 0)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (call $b13)
+       (i32.const 1)
+      )
+     )
+     (br_if $z
+      (i32.eq
+       (call $b13)
+       (i32.const 2)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-bad7 (; 61 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (get_local $a)
+       (i32.const -1)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (get_local $a)
+       (i32.const -1)
+      )
+     )
+     (br_if $z
+      (i32.eq
+       (get_local $a)
+       (i32.const -1)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-defaultNameOverlaps (; 62 ;) (type $0) (param $a i32)
+  (block $x
+   (block $tablify|0
+    (block $z
+     (nop)
+     (nop)
+     (block $tablify|1
+      (br_table $x $tablify|0 $z $tablify|1
+       (get_local $a)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-unreach (; 63 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (unreachable)
+       (i32.const 0)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (unreachable)
+       (i32.const 1)
+      )
+     )
+     (br_if $z
+      (i32.eq
+       (unreachable)
+       (i32.const 2)
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
+ (func $br-to-table-overlap-but-later (; 64 ;) (type $0) (param $a i32)
+  (block $x
+   (block $y
+    (block $z
+     (br_if $x
+      (i32.eq
+       (get_local $a)
+       (i32.const 0)
+      )
+     )
+     (br_if $y
+      (i32.eq
+       (get_local $a)
+       (i32.const 1)
+      )
+     )
+     (nop)
+     (nop)
+     (block $tablify|0
+      (br_table $z $x $y $tablify|0
+       (i32.sub
+        (get_local $a)
+        (i32.const 1)
+       )
+      )
+     )
+     (unreachable)
+    )
+    (unreachable)
+   )
+   (unreachable)
+  )
+  (unreachable)
+ )
 )
diff --git a/test/passes/remove-unused-brs.wast b/test/passes/remove-unused-brs.wast
index 731a9f88f..dac03c1d9 100644
--- a/test/passes/remove-unused-brs.wast
+++ b/test/passes/remove-unused-brs.wast
@@ -1039,5 +1039,300 @@
     )
    )
   )
+  (func $br-to-table (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 2)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-too-few (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+        )
+      )
+    )
+  )
+  (func $br-to-table-one-more (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 2)))
+          (br_if $x (i32.eq (get_local $a) (i32.const 3)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-overlap (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 1)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-overlap-start (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 1)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-offset (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 15)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 16)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 17)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-RANGE-high (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 10)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-RANGE-low (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 3)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 9)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-bad (param $a i32) (result i32)
+    (block $value (result i32)
+      (block $x
+        (block $y
+          (block $z
+            (nop)
+            (br $x)
+            (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+            (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+            (br_if $z (i32.eq (get_local $a) (i32.const 2)))
+            (unreachable)
+          )
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (i32.const 2000)
+    )
+  )
+  (func $br-to-table-bad2 (param $a i32) (result i32)
+    (block $value (result i32)
+      (block $x
+        (block $y
+          (block $z
+            (nop)
+            (drop (br_if $value (i32.const 1000) (i32.eq (get_local $a) (i32.const 0))))
+            (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+            (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+            (br_if $z (i32.eq (get_local $a) (i32.const 2)))
+            (unreachable)
+          )
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (i32.const 2000)
+    )
+  )
+  (func $br-to-table-bad3 (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (i32.const 10) (i32.const 0)))
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 2)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-multi (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $z (i32.eq (i32.const 10) (i32.const 5)))
+          (br_if $y (i32.eq (i32.const 10) (i32.const 6)))
+          (br_if $x (i32.eq (i32.const 10) (i32.const 7)))
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 2)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-bad4 (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.ne (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 2)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-bad5 (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (get_local $a)))
+          (br_if $y (i32.eq (get_local $a) (get_local $a)))
+          (br_if $z (i32.eq (get_local $a) (get_local $a)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-bad6 (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (call $b13) (i32.const 0)))
+          (br_if $y (i32.eq (call $b13) (i32.const 1)))
+          (br_if $z (i32.eq (call $b13) (i32.const 2)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-bad7 (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const -1))) ;; negative, we support only positive up to int32_max
+          (br_if $y (i32.eq (get_local $a) (i32.const -1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const -1)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-defaultNameOverlaps (param $a i32)
+    (block $x
+      (block $tablify|0
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $tablify|0 (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 2)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-unreach (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (unreachable) (i32.const 0)))
+          (br_if $y (i32.eq (unreachable) (i32.const 1)))
+          (br_if $z (i32.eq (unreachable) (i32.const 2)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
+  (func $br-to-table-overlap-but-later (param $a i32)
+    (block $x
+      (block $y
+        (block $z
+          (br_if $x (i32.eq (get_local $a) (i32.const 0)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $z (i32.eq (get_local $a) (i32.const 1)))
+          (br_if $x (i32.eq (get_local $a) (i32.const 2)))
+          (br_if $y (i32.eq (get_local $a) (i32.const 3)))
+          (unreachable)
+        )
+        (unreachable)
+      )
+      (unreachable)
+    )
+    (unreachable)
+  )
 )