OptimizeInstructions: Select => and/or in more cases (#4154)

x ? 0 : y  ==>   z & y   where z = !x

x ? y : 1  ==>   z | y   where z = !x

Only do this when we have z = !x, that is, we can invert x without adding
an actual eqz (which would add work).

To do this, canonicalize selects to prefer to flip the arms, when
possible, if it would move a constant to a location that the existing
optimizations already turn into an and/or. That is,

x >= 5 ? 0 : y != 42

would be canonicalized into

x < 5 ? y != 42 : 0

and existing opts turn that into

(x < 5) & (y != 42)

The canonicalization does not always help this optimization, as we need
the values to be boolean to do this, but canonicalizing is still nice to get
more regular code which might compress slightly better.

4 files changed, 150 insertions, 17 deletions

diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 42d92751f..047ed8551 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -2418,6 +2418,26 @@ private:
         return curr->type == Type::i64 ? builder.makeUnary(ExtendUInt32, c) : c;
       }
     }
+    // Flip the arms if doing so might help later optimizations here.
+    if (auto* binary = curr->condition->dynCast<Binary>()) {
+      auto inv = invertBinaryOp(binary->op);
+      if (inv != InvalidBinary) {
+        // For invertible binary operations, we prefer to have non-zero values
+        // in the ifTrue, and zero values in the ifFalse, due to the
+        // optimization right after us. Even if this does not help there, it is
+        // a nice canonicalization. (To ensure convergence - that we don't keep
+        // doing work each time we get here - do nothing if both are zero, or
+        // if both are nonzero.)
+        Const* c;
+        if ((matches(curr->ifTrue, ival(0)) &&
+             !matches(curr->ifFalse, ival(0))) ||
+            (!matches(curr->ifTrue, ival()) &&
+             matches(curr->ifFalse, ival(&c)) && !c->value.isZero())) {
+          binary->op = inv;
+          std::swap(curr->ifTrue, curr->ifFalse);
+        }
+      }
+    }
     if (curr->type == Type::i32 &&
         Bits::getMaxBits(curr->condition, this) <= 1 &&
         Bits::getMaxBits(curr->ifTrue, this) <= 1 &&
@@ -4168,8 +4188,9 @@ private:
     }
   }
 
+  // Invert (negate) the opcode, so that it has the exact negative meaning as it
+  // had before.
   BinaryOp invertBinaryOp(BinaryOp op) {
-    // use de-morgan's laws
     switch (op) {
       case EqInt32:
         return NeInt32;
@@ -4228,6 +4249,9 @@ private:
     }
   }
 
+  // Change the opcode so it is correct after reversing the operands. That is,
+  // we had  X OP  Y  and we need OP' so that this is equivalent to that:
+  //         Y OP' X
   BinaryOp reverseRelationalOp(BinaryOp op) {
     switch (op) {
       case EqInt32:
diff --git a/test/lit/passes/O4_disable-bulk-memory.wast b/test/lit/passes/O4_disable-bulk-memory.wast
index 8200df5a3..c0bcc07a9 100644
--- a/test/lit/passes/O4_disable-bulk-memory.wast
+++ b/test/lit/passes/O4_disable-bulk-memory.wast
@@ -236,9 +236,9 @@
  ;; CHECK-NEXT:      (i32.add
  ;; CHECK-NEXT:       (i32.add
  ;; CHECK-NEXT:        (select
- ;; CHECK-NEXT:         (local.get $0)
  ;; CHECK-NEXT:         (i32.const 1)
- ;; CHECK-NEXT:         (i32.gt_u
+ ;; CHECK-NEXT:         (local.get $0)
+ ;; CHECK-NEXT:         (i32.le_u
  ;; CHECK-NEXT:          (local.get $0)
  ;; CHECK-NEXT:          (i32.const 1)
  ;; CHECK-NEXT:         )
diff --git a/test/lit/passes/inlining-optimizing_optimize-level=3.wast b/test/lit/passes/inlining-optimizing_optimize-level=3.wast
index d8157d9a1..4fa8e1936 100644
--- a/test/lit/passes/inlining-optimizing_optimize-level=3.wast
+++ b/test/lit/passes/inlining-optimizing_optimize-level=3.wast
@@ -5413,9 +5413,9 @@
  ;; CHECK-NEXT:                                   )
  ;; CHECK-NEXT:                                   (local.set $6
  ;; CHECK-NEXT:                                    (select
- ;; CHECK-NEXT:                                     (local.get $6)
  ;; CHECK-NEXT:                                     (i32.const 8)
- ;; CHECK-NEXT:                                     (i32.gt_u
+ ;; CHECK-NEXT:                                     (local.get $6)
+ ;; CHECK-NEXT:                                     (i32.le_u
  ;; CHECK-NEXT:                                      (local.get $6)
  ;; CHECK-NEXT:                                      (i32.const 8)
  ;; CHECK-NEXT:                                     )
@@ -7473,14 +7473,14 @@
  ;; CHECK-NEXT:                                       (local.get $19)
  ;; CHECK-NEXT:                                       (local.tee $5
  ;; CHECK-NEXT:                                        (select
- ;; CHECK-NEXT:                                         (i32.const 0)
  ;; CHECK-NEXT:                                         (local.tee $5
  ;; CHECK-NEXT:                                          (i32.sub
  ;; CHECK-NEXT:                                           (local.get $6)
  ;; CHECK-NEXT:                                           (local.get $5)
  ;; CHECK-NEXT:                                          )
  ;; CHECK-NEXT:                                         )
- ;; CHECK-NEXT:                                         (i32.lt_s
+ ;; CHECK-NEXT:                                         (i32.const 0)
+ ;; CHECK-NEXT:                                         (i32.ge_s
  ;; CHECK-NEXT:                                          (local.get $5)
  ;; CHECK-NEXT:                                          (i32.const 0)
  ;; CHECK-NEXT:                                         )
@@ -7500,7 +7500,6 @@
  ;; CHECK-NEXT:                                       (local.get $19)
  ;; CHECK-NEXT:                                       (local.tee $5
  ;; CHECK-NEXT:                                        (select
- ;; CHECK-NEXT:                                         (i32.const 0)
  ;; CHECK-NEXT:                                         (local.tee $5
  ;; CHECK-NEXT:                                          (i32.sub
  ;; CHECK-NEXT:                                           (i32.add
@@ -7510,7 +7509,8 @@
  ;; CHECK-NEXT:                                           (local.get $5)
  ;; CHECK-NEXT:                                          )
  ;; CHECK-NEXT:                                         )
- ;; CHECK-NEXT:                                         (i32.lt_s
+ ;; CHECK-NEXT:                                         (i32.const 0)
+ ;; CHECK-NEXT:                                         (i32.ge_s
  ;; CHECK-NEXT:                                          (local.get $5)
  ;; CHECK-NEXT:                                          (i32.const 0)
  ;; CHECK-NEXT:                                         )
diff --git a/test/lit/passes/optimize-instructions.wast b/test/lit/passes/optimize-instructions.wast
index 3c9cfb2be..71d4e7fe3 100644
--- a/test/lit/passes/optimize-instructions.wast
+++ b/test/lit/passes/optimize-instructions.wast
@@ -893,9 +893,35 @@
       )
     )
   )
+  ;; CHECK:      (func $select-or-negation (param $x i32) (param $y i32) (result i32)
+  ;; CHECK-NEXT:  (i32.and
+  ;; CHECK-NEXT:   (i32.eq
+  ;; CHECK-NEXT:    (local.get $y)
+  ;; CHECK-NEXT:    (i32.const 1337)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (i32.ge_u
+  ;; CHECK-NEXT:    (local.get $x)
+  ;; CHECK-NEXT:    (i32.const 20)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $select-or-negation (param $x i32) (param $y i32) (result i32)
+    (select
+      ;; We can turn this select into an and by negating the condition.
+      (i32.const 0)
+      (i32.eq
+        (local.get $y)
+        (i32.const 1337)
+      )
+      (i32.lt_u
+        (local.get $x)
+        (i32.const 20)
+      )
+    )
+  )
   ;; CHECK:      (func $select-or-no-const (param $x i32) (param $y i32) (result i32)
   ;; CHECK-NEXT:  (select
-  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:   (i32.const 2)
   ;; CHECK-NEXT:   (i32.eq
   ;; CHECK-NEXT:    (local.get $y)
   ;; CHECK-NEXT:    (i32.const 1337)
@@ -908,8 +934,8 @@
   ;; CHECK-NEXT: )
   (func $select-or-no-const (param $x i32) (param $y i32) (result i32)
     (select
-      ;; The wrong const (should be 1).
-      (i32.const 0)
+      ;; The wrong const (should be 0 or 1).
+      (i32.const 2)
       (i32.eq
         (local.get $y)
         (i32.const 1337)
@@ -945,14 +971,97 @@
       )
     )
   )
-  ;; CHECK:      (func $select-and-no-const (param $x i32) (param $y i32) (result i32)
+  ;; CHECK:      (func $select-and-negation (param $x i32) (param $y i32) (result i32)
+  ;; CHECK-NEXT:  (i32.or
+  ;; CHECK-NEXT:   (i32.eq
+  ;; CHECK-NEXT:    (local.get $y)
+  ;; CHECK-NEXT:    (i32.const 1337)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (i32.ne
+  ;; CHECK-NEXT:    (local.get $x)
+  ;; CHECK-NEXT:    (i32.const 42)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $select-and-negation (param $x i32) (param $y i32) (result i32)
+    (select
+      (i32.eq
+        (local.get $y)
+        (i32.const 1337)
+      )
+      ;; With a 1 here, we negate the condition.
+      (i32.const 1)
+      (i32.eq
+        (local.get $x)
+        (i32.const 42)
+      )
+    )
+  )
+  ;; CHECK:      (func $select-and-negation-impossible (param $x i32) (param $y i32) (result i32)
+  ;; CHECK-NEXT:  (select
+  ;; CHECK-NEXT:   (i32.eq
+  ;; CHECK-NEXT:    (local.get $y)
+  ;; CHECK-NEXT:    (i32.const 1337)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:   (i32.shr_u
+  ;; CHECK-NEXT:    (local.get $x)
+  ;; CHECK-NEXT:    (i32.const 31)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $select-and-negation-impossible (param $x i32) (param $y i32) (result i32)
+    (select
+      (i32.eq
+        (local.get $y)
+        (i32.const 1337)
+      )
+      ;; With a 1 here, we must negate the condition, but the condition here
+      ;; cannot be negated in a simple way, so skip.
+      (i32.const 1)
+      (i32.shr_u
+        (local.get $x)
+        (i32.const 31)
+      )
+    )
+  )
+  ;; CHECK:      (func $select-and-negation-impossible-float (param $x f64) (param $y i32) (result i32)
   ;; CHECK-NEXT:  (select
   ;; CHECK-NEXT:   (i32.eq
   ;; CHECK-NEXT:    (local.get $y)
   ;; CHECK-NEXT:    (i32.const 1337)
   ;; CHECK-NEXT:   )
   ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:   (f64.le
+  ;; CHECK-NEXT:    (local.get $x)
+  ;; CHECK-NEXT:    (f64.const 3.14159)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $select-and-negation-impossible-float (param $x f64) (param $y i32) (result i32)
+    (select
+      (i32.eq
+        (local.get $y)
+        (i32.const 1337)
+      )
+      ;; With a 1 here, we must negate the condition, but the condition here
+      ;; cannot be negated due to it operating on floats (where NaNs cause
+      ;; difficulties), so we skip.
+      (i32.const 1)
+      (f64.le
+        (local.get $x)
+        (f64.const 3.14159)
+      )
+    )
+  )
+  ;; CHECK:      (func $select-and-no-const (param $x i32) (param $y i32) (result i32)
+  ;; CHECK-NEXT:  (select
+  ;; CHECK-NEXT:   (i32.const 2)
   ;; CHECK-NEXT:   (i32.eq
+  ;; CHECK-NEXT:    (local.get $y)
+  ;; CHECK-NEXT:    (i32.const 1337)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (i32.ne
   ;; CHECK-NEXT:    (local.get $x)
   ;; CHECK-NEXT:    (i32.const 42)
   ;; CHECK-NEXT:   )
@@ -964,8 +1073,8 @@
         (local.get $y)
         (i32.const 1337)
       )
-      ;; The wrong constant (should be 0).
-      (i32.const 1)
+      ;; The wrong constant (should be 0 or 1).
+      (i32.const 2)
       (i32.eq
         (local.get $x)
         (i32.const 42)
@@ -11271,9 +11380,9 @@
   ;; CHECK-NEXT:  )
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (select
-  ;; CHECK-NEXT:    (i64.const 0)
   ;; CHECK-NEXT:    (local.get $y)
-  ;; CHECK-NEXT:    (i64.ne
+  ;; CHECK-NEXT:    (i64.const 0)
+  ;; CHECK-NEXT:    (i64.eq
   ;; CHECK-NEXT:     (local.get $y)
   ;; CHECK-NEXT:     (i64.const 1)
   ;; CHECK-NEXT:    )