br_table optimizations (#1502)

Inspired by #1501

 * remove unneeded appearances of the default switch target (at the front or back of the list of targets)
 * optimize a switch with 0, 1 or 2 targets into an if or if-chain
 * optimize a br_if br pair when they have the same target

Makes e.g. fastcomp libc++ 2% smaller. Noticeable improvements on other things like box2d etc.

5 files changed, 437 insertions, 6 deletions

diff --git a/test/passes/1.txt b/test/passes/1.txt
index f46805f2e..72d0c87b8 100644
--- a/test/passes/1.txt
+++ b/test/passes/1.txt
@@ -187,10 +187,9 @@
   )
  )
  (func $switch (; 10 ;) (type $3) (param $0 i32)
-  (block $switch$1$case$3
-   (br_table $switch$1$case$3 $switch$1$case$3
-    (get_local $0)
-   )
+  (if
+   (get_local $0)
+   (nop)
   )
   (block $block$6$break
    (call $switch
diff --git a/test/passes/remove-unused-brs.txt b/test/passes/remove-unused-brs.txt
index 8fc58887a..8259864b9 100644
--- a/test/passes/remove-unused-brs.txt
+++ b/test/passes/remove-unused-brs.txt
@@ -677,7 +677,7 @@
   )
   (loop $in85
    (block $out86
-    (br_if $in85
+    (drop
      (i32.const 0)
     )
     (br $in85)
@@ -714,7 +714,7 @@
  (func $br_if_in_block (; 26 ;) (type $2) (result i32)
   (block $outval (result i32)
    (block $in
-    (br_if $in
+    (drop
      (i32.const 1)
     )
     (br $in)
@@ -1658,4 +1658,160 @@
   )
   (unreachable)
  )
+ (func $tiny-switch (; 65 ;) (type $1)
+  (block $x
+   (block $y
+    (drop
+     (i32.const 0)
+    )
+    (br $x)
+   )
+  )
+  (block $z
+   (block
+    (drop
+     (i32.const 0)
+    )
+    (br $z)
+   )
+  )
+ )
+ (func $trim-switch (; 66 ;) (type $1)
+  (block $A
+   (block $y
+    (br_table $A $y $A $y $A $y
+     (i32.sub
+      (i32.const 0)
+      (i32.const 2)
+     )
+    )
+   )
+  )
+ )
+ (func $same-target-br_if-and-br (; 67 ;) (type $1)
+  (block $x
+   (drop
+    (i32.const 0)
+   )
+   (br $x)
+   (unreachable)
+  )
+ )
+ (func $simple-switch (; 68 ;) (type $2) (result i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_table $A $y $y $y $y $y $A $y $y $y $y $A $y
+      (i32.const 0)
+     )
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
+ (func $simple-switch-2 (; 69 ;) (type $2) (result i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_table $A $y $y $y $y $y $y $y $y $y $y $y $A $y
+      (i32.const 0)
+     )
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
+ (func $simple-switch-3 (; 70 ;) (type $2) (result i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_table $A $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $B $y
+      (i32.const 0)
+     )
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
+ (func $simple-switch43 (; 71 ;) (type $2) (result i32)
+  (local $0 i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_if $A
+      (i32.eqz
+       (tee_local $0
+        (i32.const 0)
+       )
+      )
+     )
+     (br_if $B
+      (i32.eq
+       (get_local $0)
+       (i32.const 127)
+      )
+     )
+     (br $y)
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
+ (func $simple-switch-5 (; 72 ;) (type $2) (result i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_table $A $y $y $y $y $y $A $y $y $y $y $y $A $y
+      (i32.const 0)
+     )
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
 )
diff --git a/test/passes/remove-unused-brs.wast b/test/passes/remove-unused-brs.wast
index dac03c1d9..0d4bbf226 100644
--- a/test/passes/remove-unused-brs.wast
+++ b/test/passes/remove-unused-brs.wast
@@ -1334,5 +1334,112 @@
     )
     (unreachable)
   )
+  (func $tiny-switch
+    (block $x
+      (block $y
+        (br_table $x $y
+          (i32.const 0)
+        )
+      )
+    )
+    (block $z
+      (br_table $z
+        (i32.const 0)
+      )
+    )
+  )
+  (func $trim-switch
+    (block $A
+      (block $y
+        (br_table $y $y $A $y $A $y $A $y $y $y $y $y $y $y $y $y $y $y
+          (i32.const 0)
+        )
+      )
+    )
+  )
+  (func $same-target-br_if-and-br
+    (block $x
+      (br_if $x
+        (i32.const 0)
+      )
+      (br $x)
+      (unreachable)
+    )
+  )
+  (func $simple-switch (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $A $y $y $y $y $A $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
+  (func $simple-switch-2 (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $y $y $y $y $y $y $A $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
+  (func $simple-switch-3 (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $B $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
+  (func $simple-switch43 (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $B $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
+  (func $simple-switch-5 (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $A $y $y $y $y $y $A $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
 )
 
diff --git a/test/passes/remove-unused-brs_shrink-level=1.txt b/test/passes/remove-unused-brs_shrink-level=1.txt
index ac47d9f0e..e07844cf9 100644
--- a/test/passes/remove-unused-brs_shrink-level=1.txt
+++ b/test/passes/remove-unused-brs_shrink-level=1.txt
@@ -159,4 +159,113 @@
    )
   )
  )
+ (func $simple-switch (; 5 ;) (type $2) (result i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_table $A $y $y $y $y $y $A $y $y $y $y $A $y
+      (i32.const 0)
+     )
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
+ (func $simple-switch-2 (; 6 ;) (type $2) (result i32)
+  (local $0 i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_if $A
+      (i32.or
+       (i32.eqz
+        (tee_local $0
+         (i32.const 0)
+        )
+       )
+       (i32.eq
+        (get_local $0)
+        (i32.const 12)
+       )
+      )
+     )
+     (nop)
+     (br $y)
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
+ (func $simple-switch-3 (; 7 ;) (type $2) (result i32)
+  (local $0 i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_if $A
+      (i32.eqz
+       (tee_local $0
+        (i32.const 0)
+       )
+      )
+     )
+     (br_if $B
+      (i32.eq
+       (get_local $0)
+       (i32.const 1025)
+      )
+     )
+     (br $y)
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
+ (func $simple-switch-4 (; 8 ;) (type $2) (result i32)
+  (block $A
+   (block $B
+    (block $y
+     (br_table $A $y $y $y $y $y $A $y $y $y $y $y $A $y
+      (i32.const 0)
+     )
+     (return
+      (i32.const 0)
+     )
+    )
+    (return
+     (i32.const 1)
+    )
+   )
+   (return
+    (i32.const 2)
+   )
+  )
+  (i32.const 3)
+ )
 )
diff --git a/test/passes/remove-unused-brs_shrink-level=1.wast b/test/passes/remove-unused-brs_shrink-level=1.wast
index 11510dea7..a198d5e11 100644
--- a/test/passes/remove-unused-brs_shrink-level=1.wast
+++ b/test/passes/remove-unused-brs_shrink-level=1.wast
@@ -113,5 +113,65 @@
     )
    )
   )
+  (func $simple-switch (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $A $y $y $y $y $A $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
+  (func $simple-switch-2 (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $y $y $y $y $y $y $A $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
+  (func $simple-switch-3 (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $y $B $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
+  (func $simple-switch-4 (result i32)
+    (block $A
+      (block $B
+        (block $y
+          (br_table $A $y $y $y $y $y $A $y $y $y $y $y $A $y
+            (i32.const 0)
+          )
+          (return (i32.const 0))
+        )
+        (return (i32.const 1))
+      )
+      (return (i32.const 2))
+    )
+    (return (i32.const 3))
+  )
 )