Optimize "clear bit mask" combination to cyclic rotation over preinverted mask (#3184)

4 files changed, 56 insertions, 0 deletions

diff --git a/src/ir/abstract.h b/src/ir/abstract.h
index ac67a59b3..1cd51b9ba 100644
--- a/src/ir/abstract.h
+++ b/src/ir/abstract.h
@@ -40,6 +40,8 @@ enum Op {
   Shl,
   ShrU,
   ShrS,
+  RotL,
+  RotR,
   And,
   Or,
   Xor,
@@ -137,6 +139,10 @@ inline BinaryOp getBinary(Type type, Op op) {
           return ShrUInt32;
         case ShrS:
           return ShrSInt32;
+        case RotL:
+          return RotLInt32;
+        case RotR:
+          return RotRInt32;
         case And:
           return AndInt32;
         case Or:
@@ -190,6 +196,10 @@ inline BinaryOp getBinary(Type type, Op op) {
           return ShrUInt64;
         case ShrS:
           return ShrSInt64;
+        case RotL:
+          return RotLInt64;
+        case RotR:
+          return RotRInt64;
         case And:
           return AndInt64;
         case Or:
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 3b7a9dc6d..869512774 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -1397,6 +1397,20 @@ private:
       return right;
     }
     {
+      // ~(1 << x) aka (1 << x) ^ -1  ==>  rotl(-2, x)
+      Expression* x;
+      if (matches(curr,
+                  binary(Abstract::Xor,
+                         binary(Abstract::Shl, ival(1), any(&x)),
+                         ival(-1)))) {
+        curr->op = Abstract::getBinary(type, Abstract::RotL);
+        right->value = Literal::makeFromInt32(-2, type);
+        curr->left = right;
+        curr->right = x;
+        return curr;
+      }
+    }
+    {
       // Wasm binary encoding uses signed LEBs, which slightly favor negative
       // numbers: -64 is more efficient than +64 etc., as well as other powers
       // of two 7 bits etc. higher. we therefore prefer x - -64 over x + 64. in
diff --git a/test/passes/optimize-instructions_all-features.txt b/test/passes/optimize-instructions_all-features.txt
index 5babd75de..5bbaccfea 100644
--- a/test/passes/optimize-instructions_all-features.txt
+++ b/test/passes/optimize-instructions_all-features.txt
@@ -13,6 +13,7 @@
  (type $none_=>_anyref (func (result anyref)))
  (type $i32_i32_i32_=>_none (func (param i32 i32 i32)))
  (type $i32_i32_i32_f64_=>_none (func (param i32 i32 i32 f64)))
+ (type $i32_i32_i64_i64_=>_none (func (param i32 i32 i64 i64)))
  (type $i32_i32_f64_f64_=>_none (func (param i32 i32 f64 f64)))
  (type $i32_i64_f64_i32_=>_none (func (param i32 i64 f64 i32)))
  (type $f32_f64_=>_none (func (param f32 f64)))
@@ -3598,6 +3599,20 @@
    (i64.const 1)
   )
  )
+ (func $optimize-bitwise-oprations (param $x i32) (param $y i32) (param $z i64) (param $w i64)
+  (drop
+   (i32.rotl
+    (i32.const -2)
+    (local.get $x)
+   )
+  )
+  (drop
+   (i64.rotl
+    (i64.const -2)
+    (local.get $z)
+   )
+  )
+ )
  (func $getFallthrough
   (local $x0 i32)
   (local $x1 i32)
diff --git a/test/passes/optimize-instructions_all-features.wast b/test/passes/optimize-instructions_all-features.wast
index 246fd41a2..c8a48391c 100644
--- a/test/passes/optimize-instructions_all-features.wast
+++ b/test/passes/optimize-instructions_all-features.wast
@@ -4163,6 +4163,23 @@
       (i64.const 1)
     ))
   )
+  (func $optimize-bitwise-oprations (param $x i32) (param $y i32) (param $z i64) (param $w i64)
+    ;; ~(1 << x)  ->  rotl(-2, x)
+    (drop (i32.xor
+      (i32.shl
+        (i32.const 1)
+        (local.get $x)
+      )
+      (i32.const -1)
+    ))
+    (drop (i64.xor
+      (i64.shl
+        (i64.const 1)
+        (local.get $z)
+      )
+      (i64.const -1)
+    ))
+  )
   (func $getFallthrough ;; unit tests for Properties::getFallthrough
     (local $x0 i32)
     (local $x1 i32)