Implement missing if restructuring (#3819)

The existing restructuring code could turn a block+br_if into an if in
simple cases, but it had some TODOs that I noticed were helpful on
GC benchmarks.

One limitation was that we need to reorder the condition and the value,

(block
  (br_if
    (value)
    (condition)
  )
  (...)
)
=>
(if
  (condition)
  (value)
  (...)
)
The old code checked for side effects in the condition. But it is ok for it
to have side effects if they can be reordered with the value (for example,
if the value is a constant then it definitely does not care about side effects
in the condition).

The other missing TODO is to use a select when we can't use an if:

(block
  (drop
    (br_if
      (value)
      (condition)
    )
  )
  (...)
)
=>
(select
  (value)
  (...)
  (condition)
)
In this case we do not reorder the condition and the value, but we do
reorder the condition with the rest of the block.

3 files changed, 266 insertions, 11 deletions

diff --git a/test/lit/passes/remove-unused-brs.wast b/test/lit/passes/remove-unused-brs.wast
index bd4d80bcd..a43601654 100644
--- a/test/lit/passes/remove-unused-brs.wast
+++ b/test/lit/passes/remove-unused-brs.wast
@@ -26,4 +26,260 @@
       )
     )
   )
+
+  ;; CHECK:      (func $restructure-br_if (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (if (result i32)
+  ;; CHECK-NEXT:   (local.get $x)
+  ;; CHECK-NEXT:   (i32.const 100)
+  ;; CHECK-NEXT:   (block $x (result i32)
+  ;; CHECK-NEXT:    (nop)
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 200)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.const 300)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $restructure-br_if (param $x i32) (result i32)
+    ;; this block+br_if can be turned into an if.
+    (block $x (result i32)
+      (drop
+        (br_if $x
+          (i32.const 100)
+          (local.get $x)
+        )
+      )
+      (drop (i32.const 200))
+      (i32.const 300)
+    )
+  )
+
+  (func $nothing)
+
+  ;; CHECK:      (func $restructure-br_if-condition-reorderable (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (if (result i32)
+  ;; CHECK-NEXT:   (block $block (result i32)
+  ;; CHECK-NEXT:    (call $nothing)
+  ;; CHECK-NEXT:    (local.get $x)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (i32.const 100)
+  ;; CHECK-NEXT:   (block $x (result i32)
+  ;; CHECK-NEXT:    (nop)
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 200)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.const 300)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $restructure-br_if-condition-reorderable (param $x i32) (result i32)
+    (block $x (result i32)
+      (drop
+        (br_if $x
+          (i32.const 100)
+          ;; the condition has side effects, but can be reordered with the value
+          (block (result i32)
+            (call $nothing)
+            (local.get $x)
+          )
+        )
+      )
+      (drop (i32.const 200))
+      (i32.const 300)
+    )
+  )
+
+  ;; CHECK:      (func $restructure-br_if-value-effectful (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (select
+  ;; CHECK-NEXT:   (block $block (result i32)
+  ;; CHECK-NEXT:    (call $nothing)
+  ;; CHECK-NEXT:    (i32.const 100)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (block $x (result i32)
+  ;; CHECK-NEXT:    (nop)
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (i32.const 200)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (i32.const 300)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (block $block0 (result i32)
+  ;; CHECK-NEXT:    (call $nothing)
+  ;; CHECK-NEXT:    (local.get $x)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $restructure-br_if-value-effectful (param $x i32) (result i32)
+    (block $x (result i32)
+      (drop
+        (br_if $x
+          ;; the value has side effects, but we can use a select instead
+          ;; of an if, which keeps the value first
+          (block (result i32)
+            (call $nothing)
+            (i32.const 100)
+          )
+          ;; the condition has side effects too, but can be be reordered
+          ;; to the end of the block
+          (block (result i32)
+            (call $nothing)
+            (local.get $x)
+          )
+        )
+      )
+      (drop (i32.const 200))
+      (i32.const 300)
+    )
+  )
+
+  ;; CHECK:      (func $restructure-br_if-value-effectful-corner-case-1 (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (block $x (result i32)
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (br_if $x
+  ;; CHECK-NEXT:     (block $block (result i32)
+  ;; CHECK-NEXT:      (call $nothing)
+  ;; CHECK-NEXT:      (i32.const 100)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (block $block1 (result i32)
+  ;; CHECK-NEXT:      (call $nothing)
+  ;; CHECK-NEXT:      (local.get $x)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (call $nothing)
+  ;; CHECK-NEXT:   (i32.const 300)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $restructure-br_if-value-effectful-corner-case-1 (param $x i32) (result i32)
+    (block $x (result i32)
+      (drop
+        (br_if $x
+          (block (result i32)
+            (call $nothing)
+            (i32.const 100)
+          )
+          (block (result i32)
+            (call $nothing)
+            (local.get $x)
+          )
+        )
+      )
+      ;; the condition cannot be reordered with this
+      (call $nothing)
+      (i32.const 300)
+    )
+  )
+
+  ;; CHECK:      (func $get-i32 (result i32)
+  ;; CHECK-NEXT:  (i32.const 400)
+  ;; CHECK-NEXT: )
+  (func $get-i32 (result i32)
+    (i32.const 400)
+  )
+
+  ;; CHECK:      (func $restructure-br_if-value-effectful-corner-case-2 (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (block $x (result i32)
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (br_if $x
+  ;; CHECK-NEXT:     (block $block (result i32)
+  ;; CHECK-NEXT:      (call $nothing)
+  ;; CHECK-NEXT:      (i32.const 100)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (block $block2 (result i32)
+  ;; CHECK-NEXT:      (call $nothing)
+  ;; CHECK-NEXT:      (local.get $x)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (i32.const 300)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (call $get-i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $restructure-br_if-value-effectful-corner-case-2 (param $x i32) (result i32)
+    (block $x (result i32)
+      (drop
+        (br_if $x
+          (block (result i32)
+            (call $nothing)
+            (i32.const 100)
+          )
+          (block (result i32)
+            (call $nothing)
+            (local.get $x)
+          )
+        )
+      )
+      (drop (i32.const 300))
+      ;; the condition cannot be reordered with this
+      (call $get-i32)
+    )
+  )
+  ;; CHECK:      (func $restructure-br_if-value-effectful-corner-case-3 (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (block $x (result i32)
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (br_if $x
+  ;; CHECK-NEXT:     (block $block (result i32)
+  ;; CHECK-NEXT:      (call $nothing)
+  ;; CHECK-NEXT:      (i32.const 100)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (local.get $x)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (call $nothing)
+  ;; CHECK-NEXT:   (i32.const 100)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $restructure-br_if-value-effectful-corner-case-3 (param $x i32) (result i32)
+    (block $x (result i32)
+      (drop
+        (br_if $x
+          ;; we can't do an if because of effects here
+          (block (result i32)
+            (call $nothing)
+            (i32.const 100)
+          )
+          (local.get $x)
+        )
+      )
+      ;; and we can't do a select because of effects here
+      (call $nothing)
+      (i32.const 100)
+    )
+  )
+
+  ;; CHECK:      (func $restructure-br_if-value-effectful-corner-case-4 (param $x i32) (result i32)
+  ;; CHECK-NEXT:  (block $x (result i32)
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (br_if $x
+  ;; CHECK-NEXT:     (block $block (result i32)
+  ;; CHECK-NEXT:      (call $nothing)
+  ;; CHECK-NEXT:      (i32.const 100)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (local.get $x)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (drop
+  ;; CHECK-NEXT:    (i32.const 300)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (call $get-i32)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $restructure-br_if-value-effectful-corner-case-4 (param $x i32) (result i32)
+    (block $x (result i32)
+      (drop
+        (br_if $x
+          ;; we can't do an if because of effects here
+          (block (result i32)
+            (call $nothing)
+            (i32.const 100)
+          )
+          (local.get $x)
+        )
+      )
+      (drop (i32.const 300))
+      ;; and we can't do a select because of effects here
+      (call $get-i32)
+    )
+  )
 )
diff --git a/test/passes/remove-unused-brs_enable-multivalue.txt b/test/passes/remove-unused-brs_enable-multivalue.txt
index f48f7b6af..45e6b4159 100644
--- a/test/passes/remove-unused-brs_enable-multivalue.txt
+++ b/test/passes/remove-unused-brs_enable-multivalue.txt
@@ -1988,17 +1988,16 @@
    )
   )
  )
- (func $drop-restructure-if-bad (param $x i32) (param $y i32) (result i32)
-  (block $label$2 (result i32)
-   (drop
-    (br_if $label$2
-     (local.tee $y
-      (local.get $x)
-     )
-     (local.get $y)
-    )
+ (func $drop-restructure-select (param $x i32) (param $y i32) (result i32)
+  (select
+   (local.tee $y
+    (local.get $x)
    )
-   (i32.const 0)
+   (block $label$2 (result i32)
+    (nop)
+    (i32.const 0)
+   )
+   (local.get $y)
   )
  )
  (func $drop-restructure-if-bad-2 (param $x i32) (param $y i32) (result i32)
diff --git a/test/passes/remove-unused-brs_enable-multivalue.wast b/test/passes/remove-unused-brs_enable-multivalue.wast
index 6b5b4b1a7..afc8c3836 100644
--- a/test/passes/remove-unused-brs_enable-multivalue.wast
+++ b/test/passes/remove-unused-brs_enable-multivalue.wast
@@ -1615,7 +1615,7 @@
     (i32.const 0)
    )
   )
-  (func $drop-restructure-if-bad (param $x i32) (param $y i32) (result i32)
+  (func $drop-restructure-select (param $x i32) (param $y i32) (result i32)
    (block $label$2 (result i32)
     (drop
      (br_if $label$2