Cost analysis: Remove "Unacceptable" hack (#6782)

We marked various expressions as having cost "Unacceptable", fixed at 100, to
ensure we never moved them out from an If arm, etc. Giving them such a high
cost avoids that problem - the cost is higher than the limit we have for moving
code from conditional to unconditional execution - but it also means the total
cost is unrealistic. For example, a function with one such instruction + an add
(cost 1) would end up with cost 101, and removing the add would look
insignificant, which causes issues for things that want to compare costs
(like Monomorphization).

To fix this, adjust some costs. The main change here is to give casts a cost of 5.
I measured this in depth, see the attached benchmark scripts, and it looks
clear that in both V8 and SpiderMonkey the cost of a cast is high enough to
make it not worth turning an if with ref.test arm into a select (which would
always execute the test).

Other costs adjusted here matter a lot less, because they are on operations
that have side effects and so the optimizer will anyhow not move them from
conditional to unconditional execution, but I tried to make them a bit more
realistic while I was removing "Unacceptable":

*   Give most atomic operations the 10 cost we've been using for atomic loads/
    stores. Perhaps wait and notify should be slower, however, but it seems like
    assuming fast switching might be more relevant.
*   Give growth operations a cost of 20, and throw operations a cost of 10. These
    numbers are entirely made up as I am not even sure how to measure them in
    a useful way (but, again, this should not matter much as they have side
    effects).

1 files changed, 136 insertions, 7 deletions

diff --git a/test/lit/passes/remove-unused-brs_levels.wast b/test/lit/passes/remove-unused-brs_levels.wast
index 927cce867..6e521aa16 100644
--- a/test/lit/passes/remove-unused-brs_levels.wast
+++ b/test/lit/passes/remove-unused-brs_levels.wast
@@ -3,9 +3,17 @@
 ;; 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:      (type $struct (sub (struct)))
+  ;; SHRINK_1:      (type $struct (sub (struct)))
+  ;; SHRINK_2:      (type $struct (sub (struct)))
+  (type $struct (sub (struct)))
+  ;; SHRINK_0:      (type $substruct (sub $struct (struct)))
+  ;; SHRINK_1:      (type $substruct (sub $struct (struct)))
+  ;; SHRINK_2:      (type $substruct (sub $struct (struct)))
+  (type $substruct (sub $struct (struct)))
+
+  ;; SHRINK_0:      (func $selectify-division (type $2) (param $x i32) (result i32)
   ;; SHRINK_0-NEXT:  (if (result i32)
   ;; SHRINK_0-NEXT:   (i32.eq
   ;; SHRINK_0-NEXT:    (local.get $x)
@@ -22,7 +30,7 @@
   ;; SHRINK_0-NEXT:   )
   ;; SHRINK_0-NEXT:  )
   ;; SHRINK_0-NEXT: )
-  ;; SHRINK_1:      (func $selectify-division (type $0) (param $x i32) (result i32)
+  ;; SHRINK_1:      (func $selectify-division (type $2) (param $x i32) (result i32)
   ;; SHRINK_1-NEXT:  (select
   ;; SHRINK_1-NEXT:   (i32.div_s
   ;; SHRINK_1-NEXT:    (local.get $x)
@@ -35,7 +43,7 @@
   ;; SHRINK_1-NEXT:   )
   ;; SHRINK_1-NEXT:  )
   ;; SHRINK_1-NEXT: )
-  ;; SHRINK_2:      (func $selectify-division (type $0) (param $x i32) (result i32)
+  ;; SHRINK_2:      (func $selectify-division (type $2) (param $x i32) (result i32)
   ;; SHRINK_2-NEXT:  (select
   ;; SHRINK_2-NEXT:   (i32.div_s
   ;; SHRINK_2-NEXT:    (local.get $x)
@@ -68,7 +76,7 @@
     )
   )
 
-  ;; SHRINK_0:      (func $selectify-division2 (type $0) (param $x i32) (result i32)
+  ;; SHRINK_0:      (func $selectify-division2 (type $2) (param $x i32) (result i32)
   ;; SHRINK_0-NEXT:  (if (result i32)
   ;; SHRINK_0-NEXT:   (i32.eq
   ;; SHRINK_0-NEXT:    (local.get $x)
@@ -88,7 +96,7 @@
   ;; SHRINK_0-NEXT:   )
   ;; SHRINK_0-NEXT:  )
   ;; SHRINK_0-NEXT: )
-  ;; SHRINK_1:      (func $selectify-division2 (type $0) (param $x i32) (result i32)
+  ;; SHRINK_1:      (func $selectify-division2 (type $2) (param $x i32) (result i32)
   ;; SHRINK_1-NEXT:  (if (result i32)
   ;; SHRINK_1-NEXT:   (i32.eq
   ;; SHRINK_1-NEXT:    (local.get $x)
@@ -108,7 +116,7 @@
   ;; SHRINK_1-NEXT:   )
   ;; SHRINK_1-NEXT:  )
   ;; SHRINK_1-NEXT: )
-  ;; SHRINK_2:      (func $selectify-division2 (type $0) (param $x i32) (result i32)
+  ;; SHRINK_2:      (func $selectify-division2 (type $2) (param $x i32) (result i32)
   ;; SHRINK_2-NEXT:  (select
   ;; SHRINK_2-NEXT:   (i32.div_s
   ;; SHRINK_2-NEXT:    (i32.div_s
@@ -146,4 +154,125 @@
       )
     )
   )
+
+  ;; SHRINK_0:      (func $if-tests (type $3) (param $x (ref $struct)) (param $y (ref $struct)) (result i32)
+  ;; SHRINK_0-NEXT:  (if (result i32)
+  ;; SHRINK_0-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_0-NEXT:    (local.get $x)
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:   (then
+  ;; SHRINK_0-NEXT:    (ref.test (ref $substruct)
+  ;; SHRINK_0-NEXT:     (local.get $y)
+  ;; SHRINK_0-NEXT:    )
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:   (else
+  ;; SHRINK_0-NEXT:    (i32.const 0)
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:  )
+  ;; SHRINK_0-NEXT: )
+  ;; SHRINK_1:      (func $if-tests (type $3) (param $x (ref $struct)) (param $y (ref $struct)) (result i32)
+  ;; SHRINK_1-NEXT:  (select
+  ;; SHRINK_1-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_1-NEXT:    (local.get $y)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:   (i32.const 0)
+  ;; SHRINK_1-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_1-NEXT:    (local.get $x)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:  )
+  ;; SHRINK_1-NEXT: )
+  ;; SHRINK_2:      (func $if-tests (type $3) (param $x (ref $struct)) (param $y (ref $struct)) (result i32)
+  ;; SHRINK_2-NEXT:  (select
+  ;; SHRINK_2-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_2-NEXT:    (local.get $y)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:   (i32.const 0)
+  ;; SHRINK_2-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_2-NEXT:    (local.get $x)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:  )
+  ;; SHRINK_2-NEXT: )
+  (func $if-tests (param $x (ref $struct)) (param $y (ref $struct)) (result i32)
+    ;; An If with a test in one arm (and also in a condition). We do not
+    ;; normally turn this into a Select, as the test is more costly than the If.
+    ;; But we do so when optimizing for size.
+    ;;
+    ;; TODO: Consider optimizing this because the other arm is a 0, which means
+    ;;       the Select can turn into an And later.
+    (if (result i32)
+      (ref.test (ref $substruct)
+        (local.get $x)
+      )
+      (then
+        (ref.test (ref $substruct)
+          (local.get $y)
+        )
+      )
+      (else
+        (i32.const 0)
+      )
+    )
+  )
+
+  ;; SHRINK_0:      (func $if-tests-arms (type $4) (param $x (ref $struct)) (param $y (ref $struct)) (param $z (ref $struct)) (result i32)
+  ;; SHRINK_0-NEXT:  (if (result i32)
+  ;; SHRINK_0-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_0-NEXT:    (local.get $x)
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:   (then
+  ;; SHRINK_0-NEXT:    (ref.test (ref $substruct)
+  ;; SHRINK_0-NEXT:     (local.get $y)
+  ;; SHRINK_0-NEXT:    )
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:   (else
+  ;; SHRINK_0-NEXT:    (ref.test (ref $substruct)
+  ;; SHRINK_0-NEXT:     (local.get $z)
+  ;; SHRINK_0-NEXT:    )
+  ;; SHRINK_0-NEXT:   )
+  ;; SHRINK_0-NEXT:  )
+  ;; SHRINK_0-NEXT: )
+  ;; SHRINK_1:      (func $if-tests-arms (type $4) (param $x (ref $struct)) (param $y (ref $struct)) (param $z (ref $struct)) (result i32)
+  ;; SHRINK_1-NEXT:  (select
+  ;; SHRINK_1-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_1-NEXT:    (local.get $y)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_1-NEXT:    (local.get $z)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_1-NEXT:    (local.get $x)
+  ;; SHRINK_1-NEXT:   )
+  ;; SHRINK_1-NEXT:  )
+  ;; SHRINK_1-NEXT: )
+  ;; SHRINK_2:      (func $if-tests-arms (type $4) (param $x (ref $struct)) (param $y (ref $struct)) (param $z (ref $struct)) (result i32)
+  ;; SHRINK_2-NEXT:  (select
+  ;; SHRINK_2-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_2-NEXT:    (local.get $y)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_2-NEXT:    (local.get $z)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:   (ref.test (ref $substruct)
+  ;; SHRINK_2-NEXT:    (local.get $x)
+  ;; SHRINK_2-NEXT:   )
+  ;; SHRINK_2-NEXT:  )
+  ;; SHRINK_2-NEXT: )
+  (func $if-tests-arms (param $x (ref $struct)) (param $y (ref $struct)) (param $z (ref $struct)) (result i32)
+    ;; As above but now with a test in both arms. The outcomes are the same.
+    (if (result i32)
+      (ref.test (ref $substruct)
+        (local.get $x)
+      )
+      (then
+        (ref.test (ref $substruct)
+          (local.get $y)
+        )
+      )
+      (else
+        (ref.test (ref $substruct)
+          (local.get $z)
+        )
+      )
+    )
+  )
 )