RemoveUnusedBrs: Allow less unconditional work and in particular division (#5989)

Fixes #5983: The testcase from there is used here in a new testcase
remove-unused-brs_levels in which we check if we are willing to unconditionally
do a division operation. Turning an if with an arm that does a division into a
select, which always does the division, is almost 5x slower, so we should probably
be extremely careful about doing that.

I took some measurements and have some suggestions for changes in this PR:

*   Raise the cost of div/rem to what I measure on my machine, which is 5x slower
    than an add, or worse.
*   For some reason we added the if arms rather than take the max of them, so
    fix that. This does not help the issue, but was confusing.
*   Adjust TooCostlyToRunUnconditionally in the pass from 9 to 8 (this helps
    balance the last point).
*   Use half that value when not optimizing for size. That is, we allow only 4 extra
    unconditional work normally, and 8 in -Os, and when -Oz then we allow any
    extra amount.

Aside from the new testcases, some existing ones changed. They all appear to
change in a reasonable way, to me.

We should perhaps go even further than this, and not even run a division
unconditionally in -Os, but I wasn't sure it makes sense to go that far as
other benchmarks may be affected. For now, this makes the benchmark in
#5983 run at full speed in -O3 or -Os, and it remains slow in -Oz. The
modified version of the benchmark that only divides in the if (no other
operations) is still fast in -O3, but it become slow in -Os as we do turn that
if into a select (but again, I didn't want to go that far as to overfit on that one
benchmark).

6 files changed, 177 insertions, 29 deletions

diff --git a/test/lit/passes/remove-unused-brs-gc.wast b/test/lit/passes/remove-unused-brs-gc.wast
index 53100cc91..7a620193e 100644
--- a/test/lit/passes/remove-unused-brs-gc.wast
+++ b/test/lit/passes/remove-unused-brs-gc.wast
@@ -655,22 +655,20 @@
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
- ;; CHECK-NEXT:   (select (result (ref null $struct))
- ;; CHECK-NEXT:    (block (result (ref null $struct))
- ;; CHECK-NEXT:     (block $something (result (ref null $struct))
- ;; CHECK-NEXT:      (drop
- ;; CHECK-NEXT:       (block (result nullref)
- ;; CHECK-NEXT:        (br_on_non_null $something
- ;; CHECK-NEXT:         (local.get $struct)
- ;; CHECK-NEXT:        )
- ;; CHECK-NEXT:        (ref.null none)
+ ;; CHECK-NEXT:   (if (result (ref null $struct))
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:    (block $something (result (ref null $struct))
+ ;; CHECK-NEXT:     (drop
+ ;; CHECK-NEXT:      (block (result nullref)
+ ;; CHECK-NEXT:       (br_on_non_null $something
+ ;; CHECK-NEXT:        (local.get $struct)
  ;; CHECK-NEXT:       )
+ ;; CHECK-NEXT:       (ref.null none)
  ;; CHECK-NEXT:      )
- ;; CHECK-NEXT:      (ref.null none)
  ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:     (ref.null none)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:    (ref.null none)
- ;; CHECK-NEXT:    (local.get $x)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
@@ -716,6 +714,8 @@
     )
    )
   )
+  ;; We do not selectify here because the amount of work in the if is
+  ;; significant (there is a cast and a branch).
   (drop
    (if (result anyref)
     (local.get $x)
diff --git a/test/lit/passes/remove-unused-brs.wast b/test/lit/passes/remove-unused-brs.wast
index 82963f792..93cf4cbd2 100644
--- a/test/lit/passes/remove-unused-brs.wast
+++ b/test/lit/passes/remove-unused-brs.wast
@@ -31,10 +31,7 @@
   ;; CHECK-NEXT:   (i32.const 1)
   ;; CHECK-NEXT:   (i32.lt_u
   ;; CHECK-NEXT:    (i32.sub
-  ;; CHECK-NEXT:     (i32.or
-  ;; CHECK-NEXT:      (local.get $0)
-  ;; CHECK-NEXT:      (i32.const 32)
-  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (local.get $0)
   ;; CHECK-NEXT:     (i32.const 97)
   ;; CHECK-NEXT:    )
   ;; CHECK-NEXT:    (i32.const 6)
@@ -60,10 +57,7 @@
       (i32.const 1)
       (i32.lt_u
         (i32.sub
-          (i32.or
-            (local.get $0)
-            (i32.const 32)
-          )
+          (local.get $0)
           (i32.const 97)
         )
         (i32.const 6)
diff --git a/test/lit/passes/remove-unused-brs_levels.wast b/test/lit/passes/remove-unused-brs_levels.wast
new file mode 100644
index 000000000..f4737627e
--- /dev/null
+++ b/test/lit/passes/remove-unused-brs_levels.wast
@@ -0,0 +1,129 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited.
+;; RUN: wasm-opt %s --remove-unused-brs -all -S --shrink-level=0 -o - | filecheck %s --check-prefix=SHRINK_0
+;; RUN: wasm-opt %s --remove-unused-brs -all -S --shrink-level=1 -o - | filecheck %s --check-prefix=SHRINK_1
+;; RUN: wasm-opt %s --remove-unused-brs -all -S --shrink-level=2 -o - | filecheck %s --check-prefix=SHRINK_2
+
+
+(module
+  ;; SHRINK_0:      (func $selectify-division (type $0) (param $x i32) (result i32)
+  ;; SHRINK_0-NEXT:  (if (result i32)
+  ;; SHRINK_0-NEXT:   (i32.eq
+  ;; SHRINK_0-NEXT:    (local.get $x)
+  ;; SHRINK_0-NEXT:    (i32.const 53498923)
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:   (i32.div_s
+  ;; SHRINK_0-NEXT:    (local.get $x)
+  ;; SHRINK_0-NEXT:    (i32.const 13)
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:   (local.get $x)
+  ;; SHRINK_0-NEXT:  )
+  ;; SHRINK_0-NEXT: )
+  ;; SHRINK_1:      (func $selectify-division (type $0) (param $x i32) (result i32)
+  ;; SHRINK_1-NEXT:  (select
+  ;; SHRINK_1-NEXT:   (i32.div_s
+  ;; SHRINK_1-NEXT:    (local.get $x)
+  ;; SHRINK_1-NEXT:    (i32.const 13)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:   (local.get $x)
+  ;; SHRINK_1-NEXT:   (i32.eq
+  ;; SHRINK_1-NEXT:    (local.get $x)
+  ;; SHRINK_1-NEXT:    (i32.const 53498923)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:  )
+  ;; SHRINK_1-NEXT: )
+  ;; SHRINK_2:      (func $selectify-division (type $0) (param $x i32) (result i32)
+  ;; SHRINK_2-NEXT:  (select
+  ;; SHRINK_2-NEXT:   (i32.div_s
+  ;; SHRINK_2-NEXT:    (local.get $x)
+  ;; SHRINK_2-NEXT:    (i32.const 13)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:   (local.get $x)
+  ;; SHRINK_2-NEXT:   (i32.eq
+  ;; SHRINK_2-NEXT:    (local.get $x)
+  ;; SHRINK_2-NEXT:    (i32.const 53498923)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:  )
+  ;; SHRINK_2-NEXT: )
+  (func $selectify-division (param $x i32) (result i32)
+    ;; See #5983: this if, if turned into a select, becomes almost 5x slower.
+    ;; We only want to selectify here when the shrink level is 1 or 2.
+    (if (result i32)
+      (i32.eq
+        (local.get $x)
+        (i32.const 53498923)
+      )
+      (i32.div_s
+        (local.get $x)
+        (i32.const 13)
+      )
+      (local.get $x)
+    )
+  )
+
+  ;; SHRINK_0:      (func $selectify-division2 (type $0) (param $x i32) (result i32)
+  ;; SHRINK_0-NEXT:  (if (result i32)
+  ;; SHRINK_0-NEXT:   (i32.eq
+  ;; SHRINK_0-NEXT:    (local.get $x)
+  ;; SHRINK_0-NEXT:    (i32.const 53498923)
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:   (i32.div_s
+  ;; SHRINK_0-NEXT:    (i32.div_s
+  ;; SHRINK_0-NEXT:     (local.get $x)
+  ;; SHRINK_0-NEXT:     (i32.const 13)
+  ;; SHRINK_0-NEXT:    )
+  ;; SHRINK_0-NEXT:    (i32.const 13)
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:   (local.get $x)
+  ;; SHRINK_0-NEXT:  )
+  ;; SHRINK_0-NEXT: )
+  ;; SHRINK_1:      (func $selectify-division2 (type $0) (param $x i32) (result i32)
+  ;; SHRINK_1-NEXT:  (if (result i32)
+  ;; SHRINK_1-NEXT:   (i32.eq
+  ;; SHRINK_1-NEXT:    (local.get $x)
+  ;; SHRINK_1-NEXT:    (i32.const 53498923)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:   (i32.div_s
+  ;; SHRINK_1-NEXT:    (i32.div_s
+  ;; SHRINK_1-NEXT:     (local.get $x)
+  ;; SHRINK_1-NEXT:     (i32.const 13)
+  ;; SHRINK_1-NEXT:    )
+  ;; SHRINK_1-NEXT:    (i32.const 13)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:   (local.get $x)
+  ;; SHRINK_1-NEXT:  )
+  ;; SHRINK_1-NEXT: )
+  ;; SHRINK_2:      (func $selectify-division2 (type $0) (param $x i32) (result i32)
+  ;; SHRINK_2-NEXT:  (select
+  ;; SHRINK_2-NEXT:   (i32.div_s
+  ;; SHRINK_2-NEXT:    (i32.div_s
+  ;; SHRINK_2-NEXT:     (local.get $x)
+  ;; SHRINK_2-NEXT:     (i32.const 13)
+  ;; SHRINK_2-NEXT:    )
+  ;; SHRINK_2-NEXT:    (i32.const 13)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:   (local.get $x)
+  ;; SHRINK_2-NEXT:   (i32.eq
+  ;; SHRINK_2-NEXT:    (local.get $x)
+  ;; SHRINK_2-NEXT:    (i32.const 53498923)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:  )
+  ;; SHRINK_2-NEXT: )
+  (func $selectify-division2 (param $x i32) (result i32)
+    ;; As above, but now only with a shrink level of 2 should we selectify, as
+    ;; there are two divisions.
+    (if (result i32)
+      (i32.eq
+        (local.get $x)
+        (i32.const 53498923)
+      )
+      (i32.div_s
+        (i32.div_s
+          (local.get $x)
+          (i32.const 13)
+        )
+        (i32.const 13)
+      )
+      (local.get $x)
+    )
+  )
+)
diff --git a/test/passes/remove-unused-brs_enable-multivalue.txt b/test/passes/remove-unused-brs_enable-multivalue.txt
index 9df644daa..0a66153e9 100644
--- a/test/passes/remove-unused-brs_enable-multivalue.txt
+++ b/test/passes/remove-unused-brs_enable-multivalue.txt
@@ -2502,8 +2502,9 @@
   (i32.const 0)
  )
  (func $ifs-copies-recursive (param $20 i32) (result i32)
-  (local.set $20
-   (select
+  (if
+   (i32.const 1)
+   (local.set $20
     (select
      (select
       (i32.const 4)
@@ -2513,8 +2514,6 @@
      (local.get $20)
      (i32.const 2)
     )
-    (local.get $20)
-    (i32.const 1)
    )
   )
   (local.get $20)
diff --git a/test/wasm2js/conversions-modified.2asm.js.opt b/test/wasm2js/conversions-modified.2asm.js.opt
index 811845f9d..5eb7435ee 100644
--- a/test/wasm2js/conversions-modified.2asm.js.opt
+++ b/test/wasm2js/conversions-modified.2asm.js.opt
@@ -121,15 +121,29 @@ function asmFunc(imports) {
  }
  
  function legalstub$7($0) {
-  i64toi32_i32$HIGH_BITS = Math_fround(Math_abs($0)) >= Math_fround(1.0) ? ~~($0 > Math_fround(0.0) ? Math_fround(Math_min(Math_fround(Math_floor(Math_fround($0 * Math_fround(2.3283064365386963e-10)))), Math_fround(4294967296.0))) : Math_fround(Math_ceil(Math_fround(Math_fround($0 - Math_fround(~~$0 >>> 0 >>> 0)) * Math_fround(2.3283064365386963e-10))))) >>> 0 : 0;
+  var $1 = 0, $2 = 0;
+  $2 = ~~$0 >>> 0;
+  if (Math_fround(Math_abs($0)) >= Math_fround(1.0)) {
+   $1 = ~~($0 > Math_fround(0.0) ? Math_fround(Math_min(Math_fround(Math_floor(Math_fround($0 * Math_fround(2.3283064365386963e-10)))), Math_fround(4294967296.0))) : Math_fround(Math_ceil(Math_fround(Math_fround($0 - Math_fround(~~$0 >>> 0 >>> 0)) * Math_fround(2.3283064365386963e-10))))) >>> 0
+  } else {
+   $1 = 0
+  }
+  i64toi32_i32$HIGH_BITS = $1;
   setTempRet0(i64toi32_i32$HIGH_BITS | 0);
-  return ~~$0 >>> 0;
+  return $2;
  }
  
  function legalstub$9($0) {
-  i64toi32_i32$HIGH_BITS = Math_abs($0) >= 1.0 ? ~~($0 > 0.0 ? Math_min(Math_floor($0 * 2.3283064365386963e-10), 4294967295.0) : Math_ceil(($0 - +(~~$0 >>> 0 >>> 0)) * 2.3283064365386963e-10)) >>> 0 : 0;
+  var $1 = 0, $2 = 0;
+  $2 = ~~$0 >>> 0;
+  if (Math_abs($0) >= 1.0) {
+   $1 = ~~($0 > 0.0 ? Math_min(Math_floor($0 * 2.3283064365386963e-10), 4294967295.0) : Math_ceil(($0 - +(~~$0 >>> 0 >>> 0)) * 2.3283064365386963e-10)) >>> 0
+  } else {
+   $1 = 0
+  }
+  i64toi32_i32$HIGH_BITS = $1;
   setTempRet0(i64toi32_i32$HIGH_BITS | 0);
-  return ~~$0 >>> 0;
+  return $2;
  }
  
  function legalstub$12($0, $1) {
diff --git a/test/wasm2js/float-ops.2asm.js.opt b/test/wasm2js/float-ops.2asm.js.opt
index 204774e5c..e00c51801 100644
--- a/test/wasm2js/float-ops.2asm.js.opt
+++ b/test/wasm2js/float-ops.2asm.js.opt
@@ -236,12 +236,24 @@ function asmFunc(imports) {
  
  function $47($0) {
   $0 = Math_fround($0);
-  return !(~~$0 >>> 0 | (Math_fround(Math_abs($0)) >= Math_fround(1.0) ? ~~($0 > Math_fround(0.0) ? Math_fround(Math_min(Math_fround(Math_floor(Math_fround($0 * Math_fround(2.3283064365386963e-10)))), Math_fround(4294967296.0))) : Math_fround(Math_ceil(Math_fround(Math_fround($0 - Math_fround(~~$0 >>> 0 >>> 0)) * Math_fround(2.3283064365386963e-10))))) >>> 0 : 0)) | 0;
+  var $1_1 = 0;
+  if (Math_fround(Math_abs($0)) >= Math_fround(1.0)) {
+   $1_1 = ~~($0 > Math_fround(0.0) ? Math_fround(Math_min(Math_fround(Math_floor(Math_fround($0 * Math_fround(2.3283064365386963e-10)))), Math_fround(4294967296.0))) : Math_fround(Math_ceil(Math_fround(Math_fround($0 - Math_fround(~~$0 >>> 0 >>> 0)) * Math_fround(2.3283064365386963e-10))))) >>> 0
+  } else {
+   $1_1 = 0
+  }
+  return !($1_1 | ~~$0 >>> 0) | 0;
  }
  
  function $48($0) {
   $0 = +$0;
-  return !(~~$0 >>> 0 | (Math_abs($0) >= 1.0 ? ~~($0 > 0.0 ? Math_min(Math_floor($0 * 2.3283064365386963e-10), 4294967295.0) : Math_ceil(($0 - +(~~$0 >>> 0 >>> 0)) * 2.3283064365386963e-10)) >>> 0 : 0)) | 0;
+  var $1_1 = 0;
+  if (Math_abs($0) >= 1.0) {
+   $1_1 = ~~($0 > 0.0 ? Math_min(Math_floor($0 * 2.3283064365386963e-10), 4294967295.0) : Math_ceil(($0 - +(~~$0 >>> 0 >>> 0)) * 2.3283064365386963e-10)) >>> 0
+  } else {
+   $1_1 = 0
+  }
+  return !($1_1 | ~~$0 >>> 0) | 0;
  }
  
  function legalstub$43($0, $1_1) {