Add optimization rules for some shift operations (#3099)

Specifically, truncates constant shift values that are greater than the number of bits available and optimizes out explicit masking of the shift value that is redundant with the implicit masking performed by shift operations.

2 files changed, 42 insertions, 0 deletions

diff --git a/src/ir/abstract.h b/src/ir/abstract.h
index 1cd51b9ba..2bb764aeb 100644
--- a/src/ir/abstract.h
+++ b/src/ir/abstract.h
@@ -59,6 +59,13 @@ enum Op {
   GeU
 };
 
+inline bool hasAnyShift(BinaryOp op) {
+  return op == ShlInt32 || op == ShrSInt32 || op == ShrUInt32 ||
+         op == RotLInt32 || op == RotRInt32 || op == ShlInt64 ||
+         op == ShrSInt64 || op == ShrUInt64 || op == RotLInt64 ||
+         op == RotRInt64;
+}
+
 // Provide a wasm type and an abstract op and get the concrete one. For example,
 // you can provide i32 and Add and receive the specific opcode for a 32-bit
 // addition, AddInt32. If the op does not exist, it returns Invalid.
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index c54960079..59a38eeaa 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -350,6 +350,41 @@ struct OptimizeInstructions
           return inner;
         }
       }
+      {
+        // x <<>> (C & (31 | 63))   ==>   x <<>> C'
+        // x <<>> (y & (31 | 63))   ==>   x <<>> y
+        // where '<<>>':
+        //   '<<', '>>', '>>>'. 'rotl' or 'rotr'
+        BinaryOp op;
+        Const* c;
+        Expression *x, *y;
+
+        // x <<>> C
+        if (matches(curr, binary(&op, any(&x), ival(&c))) &&
+            Abstract::hasAnyShift(op)) {
+          // truncate RHS constant to effective size as:
+          // i32(x) <<>> const(C & 31))
+          // i64(x) <<>> const(C & 63))
+          c->value = c->value.and_(
+            Literal::makeFromInt32(c->type.getByteSize() * 8 - 1, c->type));
+          // x <<>> 0   ==>   x
+          if (c->value.isZero()) {
+            return x;
+          }
+        }
+        if (matches(
+              curr,
+              binary(&op, any(&x), binary(Abstract::And, any(&y), ival(&c)))) &&
+            Abstract::hasAnyShift(op)) {
+          // i32(x) <<>> (y & 31)   ==>   x <<>> y
+          // i64(x) <<>> (y & 63)   ==>   x <<>> y
+          if ((c->type == Type::i32 && (c->value.geti32() & 31) == 31) ||
+              (c->type == Type::i64 && (c->value.geti64() & 63LL) == 63LL)) {
+            curr->cast<Binary>()->right = y;
+            return curr;
+          }
+        }
+      }
     }
 
     if (auto* select = curr->dynCast<Select>()) {