Costs: Increase cost of casts (#4661)

Casts involve branches in the VM, so adding a cast in return for removing a branch
(like If=>Select) is not beneficial. We don't want to ever do any more casts than we
already are.

3 files changed, 136 insertions, 13 deletions

diff --git a/src/ir/cost.h b/src/ir/cost.h
index c0a8a76e9..276c3303f 100644
--- a/src/ir/cost.h
+++ b/src/ir/cost.h
@@ -31,6 +31,12 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, CostType> {
 
   CostType cost;
 
+  // A cost that is extremely high, something that is far, far more expensive
+  // than a fast operation like an add. This cost is so high it is unacceptable
+  // to add any more of it, say by an If=>Select operation (which would execute
+  // both arms; if either arm contains an unacceptable cost, we do not do it).
+  static const CostType Unacceptable = 100;
+
   CostType maybeVisit(Expression* curr) { return curr ? visit(curr) : 0; }
 
   CostType visitBlock(Block* curr) {
@@ -85,20 +91,20 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, CostType> {
     return 2 + visit(curr->ptr) + visit(curr->value) + 10 * curr->isAtomic;
   }
   CostType visitAtomicRMW(AtomicRMW* curr) {
-    return 100 + visit(curr->ptr) + visit(curr->value);
+    return Unacceptable + visit(curr->ptr) + visit(curr->value);
   }
   CostType visitAtomicCmpxchg(AtomicCmpxchg* curr) {
-    return 100 + visit(curr->ptr) + visit(curr->expected) +
+    return Unacceptable + visit(curr->ptr) + visit(curr->expected) +
            visit(curr->replacement);
   }
   CostType visitAtomicWait(AtomicWait* curr) {
-    return 100 + visit(curr->ptr) + visit(curr->expected) +
+    return Unacceptable + visit(curr->ptr) + visit(curr->expected) +
            visit(curr->timeout);
   }
   CostType visitAtomicNotify(AtomicNotify* curr) {
-    return 100 + visit(curr->ptr) + visit(curr->notifyCount);
+    return Unacceptable + visit(curr->ptr) + visit(curr->notifyCount);
   }
-  CostType visitAtomicFence(AtomicFence* curr) { return 100; }
+  CostType visitAtomicFence(AtomicFence* curr) { return Unacceptable; }
   CostType visitConst(Const* curr) { return 1; }
   CostType visitUnary(Unary* curr) {
     CostType ret = 0;
@@ -511,7 +517,7 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, CostType> {
   CostType visitReturn(Return* curr) { return maybeVisit(curr->value); }
   CostType visitMemorySize(MemorySize* curr) { return 1; }
   CostType visitMemoryGrow(MemoryGrow* curr) {
-    return 100 + visit(curr->delta);
+    return Unacceptable + visit(curr->delta);
   }
   CostType visitMemoryInit(MemoryInit* curr) {
     return 6 + visit(curr->dest) + visit(curr->offset) + visit(curr->size);
@@ -568,20 +574,20 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, CostType> {
   }
   CostType visitTableSize(TableSize* curr) { return 1; }
   CostType visitTableGrow(TableGrow* curr) {
-    return 100 + visit(curr->value) + visit(curr->delta);
+    return Unacceptable + visit(curr->value) + visit(curr->delta);
   }
   CostType visitTry(Try* curr) {
     // We assume no exception will be thrown in most cases
     return visit(curr->body);
   }
   CostType visitThrow(Throw* curr) {
-    CostType ret = 100;
+    CostType ret = Unacceptable;
     for (auto* child : curr->operands) {
       ret += visit(child);
     }
     return ret;
   }
-  CostType visitRethrow(Rethrow* curr) { return 100; }
+  CostType visitRethrow(Rethrow* curr) { return Unacceptable; }
   CostType visitTupleMake(TupleMake* curr) {
     CostType ret = 0;
     for (auto* child : curr->operands) {
@@ -597,16 +603,21 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, CostType> {
   CostType visitI31New(I31New* curr) { return 3 + visit(curr->value); }
   CostType visitI31Get(I31Get* curr) { return 2 + visit(curr->i31); }
   CostType visitRefTest(RefTest* curr) {
-    return 2 + nullCheckCost(curr->ref) + visit(curr->ref) +
+    // Casts have a very high cost because in the VM they end up implemented as
+    // a combination of loads and branches. Given they contain branches, we do
+    // not want to add any more such work.
+    return Unacceptable + nullCheckCost(curr->ref) + visit(curr->ref) +
            maybeVisit(curr->rtt);
   }
   CostType visitRefCast(RefCast* curr) {
-    return 2 + nullCheckCost(curr->ref) + visit(curr->ref) +
+    return Unacceptable + nullCheckCost(curr->ref) + visit(curr->ref) +
            maybeVisit(curr->rtt);
   }
   CostType visitBrOn(BrOn* curr) {
-    // BrOnCast has more work to do with the rtt, so add a little there.
-    CostType base = curr->op == BrOnCast ? 3 : 2;
+    // BrOn of a null can be fairly fast, but anything else is a cast check
+    // basically, and an unacceptable cost.
+    CostType base =
+      curr->op == BrOnNull || curr->op == BrOnNonNull ? 2 : Unacceptable;
     return base + nullCheckCost(curr->ref) + maybeVisit(curr->ref) +
            maybeVisit(curr->rtt);
   }
diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp
index f383f669a..3c4723c7f 100644
--- a/src/passes/RemoveUnusedBrs.cpp
+++ b/src/passes/RemoveUnusedBrs.cpp
@@ -85,6 +85,9 @@ static bool canTurnIfIntoBrIf(Expression* ifCondition,
 // It can be tuned more later.
 const Index TooCostlyToRunUnconditionally = 9;
 
+static_assert(TooCostlyToRunUnconditionally < CostAnalyzer::Unacceptable,
+              "We never run code unconditionally if it has unacceptable cost");
+
 // Check if it is not worth it to run code unconditionally. This
 // assumes we are trying to run two expressions where previously
 // only one of the two might have executed. We assume here that
diff --git a/test/lit/passes/remove-unused-brs-gc.wast b/test/lit/passes/remove-unused-brs-gc.wast
index 458958d62..33aa08af5 100644
--- a/test/lit/passes/remove-unused-brs-gc.wast
+++ b/test/lit/passes/remove-unused-brs-gc.wast
@@ -215,4 +215,113 @@
    (unreachable)
   )
  )
+
+ ;; CHECK:      (func $casts-are-costly (param $x i32)
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (if (result i32)
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:    (ref.test_static $struct
+ ;; CHECK-NEXT:     (ref.null any)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (i32.const 0)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (if (result anyref)
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:    (ref.null any)
+ ;; CHECK-NEXT:    (ref.cast_static $struct
+ ;; CHECK-NEXT:     (ref.null any)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (if (result anyref)
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:    (block $block (result anyref)
+ ;; CHECK-NEXT:     (block $something (result anyref)
+ ;; CHECK-NEXT:      (drop
+ ;; CHECK-NEXT:       (br_on_cast_static $something $struct
+ ;; CHECK-NEXT:        (ref.null $struct)
+ ;; CHECK-NEXT:       )
+ ;; CHECK-NEXT:      )
+ ;; CHECK-NEXT:      (ref.null any)
+ ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (ref.null any)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (select (result anyref)
+ ;; CHECK-NEXT:    (block $block3 (result anyref)
+ ;; CHECK-NEXT:     (block $nothing
+ ;; CHECK-NEXT:      (drop
+ ;; CHECK-NEXT:       (br_on_null $nothing
+ ;; CHECK-NEXT:        (ref.null $struct)
+ ;; CHECK-NEXT:       )
+ ;; CHECK-NEXT:      )
+ ;; CHECK-NEXT:     )
+ ;; CHECK-NEXT:     (ref.null any)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (ref.null any)
+ ;; CHECK-NEXT:    (local.get $x)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $casts-are-costly (param $x i32)
+  ;; We never turn an if into a select if an arm has a cast of any kind, as
+  ;; those things involve branches internally, so we'd be adding more than we
+  ;; save.
+  (drop
+   (if (result i32)
+    (local.get $x)
+    (ref.test_static $struct
+     (ref.null any)
+    )
+    (i32.const 0)
+   )
+  )
+  (drop
+   (if (result anyref)
+    (local.get $x)
+    (ref.null any)
+    (ref.cast_static $struct
+     (ref.null any)
+    )
+   )
+  )
+  (drop
+   (if (result anyref)
+    (local.get $x)
+    (block (result anyref)
+     (block $something (result anyref)
+      (drop
+       (br_on_cast_static $something $struct
+        (ref.null $struct)
+       )
+      )
+      (ref.null any)
+     )
+    )
+    (ref.null any)
+   )
+  )
+  ;; However, null checks are fairly fast, and we will emit a select here.
+  (drop
+   (if (result anyref)
+    (local.get $x)
+    (block (result anyref)
+     (block $nothing
+      (drop
+       (br_on_null $nothing
+        (ref.null $struct)
+       )
+      )
+     )
+     (ref.null any)
+    )
+    (ref.null any)
+   )
+  )
+ )
 )