Add a pass to lower sign-ext operations to MVP (#5254)

Fixes #5250

8 files changed, 153 insertions, 0 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index d6101dc67..51c49eab9 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -31,6 +31,7 @@ Current Trunk
 - The `sign-extension` and `mutable-globals` features are now both enabled by
   default in all tools. This is in order to match llvm's defaults (See
   https://reviews.llvm.org/D125728).
+- Add a pass to lower sign-extension operations to MVP.
 
 v110
 ----
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index 621a8e68a..8204f1070 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -83,6 +83,7 @@ set(passes_SOURCES
   StackIR.cpp
   SignaturePruning.cpp
   SignatureRefining.cpp
+  SignExtLowering.cpp
   Strip.cpp
   StripTargetFeatures.cpp
   RedundantSetElimination.cpp
diff --git a/src/passes/SignExtLowering.cpp b/src/passes/SignExtLowering.cpp
new file mode 100644
index 000000000..7d03046ea
--- /dev/null
+++ b/src/passes/SignExtLowering.cpp
@@ -0,0 +1,75 @@
+/*
+ * Copyright 2022 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+//
+// Lowers sign-ext operations into wasm MVP operations.
+//
+
+#include "pass.h"
+#include "wasm-builder.h"
+#include "wasm.h"
+
+namespace wasm {
+
+struct SignExtLowering : public WalkerPass<PostWalker<SignExtLowering>> {
+  template<typename T>
+  void lowerToShifts(Expression* value,
+                     BinaryOp leftShift,
+                     BinaryOp rightShift,
+                     T originalBits) {
+    // To sign-extend, we shift all the way left so the effective sign bit is
+    // where the actual sign bit is. For example, when sign-extending i8, the
+    // effective sign bit is at bit 8, and we shift it to the actual place of
+    // the sign bit, which is 32 for i32 or 64 for i64. Then we do a signed
+    // shift in the other direction, which fills with the proper bit all the
+    // way back, so e.g.
+    //
+    //  0x000000ff  =(shift left)=>  0xff000000  =(shift right)=>  0xffffffff
+    //
+    T shiftBits = (sizeof(T) * 8) - originalBits;
+    Builder builder(*getModule());
+    replaceCurrent(builder.makeBinary(
+      rightShift,
+      builder.makeBinary(leftShift, value, builder.makeConst(shiftBits)),
+      builder.makeConst(shiftBits)));
+  }
+
+  void visitUnary(Unary* curr) {
+    switch (curr->op) {
+      case ExtendS8Int32:
+        lowerToShifts(curr->value, ShlInt32, ShrSInt32, int32_t(8));
+        break;
+      case ExtendS16Int32:
+        lowerToShifts(curr->value, ShlInt32, ShrSInt32, int32_t(16));
+        break;
+      case ExtendS8Int64:
+        lowerToShifts(curr->value, ShlInt64, ShrSInt64, int64_t(8));
+        break;
+      case ExtendS16Int64:
+        lowerToShifts(curr->value, ShlInt64, ShrSInt64, int64_t(16));
+        break;
+      case ExtendS32Int64:
+        lowerToShifts(curr->value, ShlInt64, ShrSInt64, int64_t(32));
+        break;
+      default: {
+      }
+    }
+  }
+};
+
+Pass* createSignExtLoweringPass() { return new SignExtLowering(); }
+
+} // namespace wasm
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index b3bf80f8f..7f79313e2 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -394,6 +394,9 @@ void PassRegistry::registerPasses() {
   registerPass("signature-refining",
                "apply more specific subtypes to signature types where possible",
                createSignatureRefiningPass);
+  registerPass("signext-lowering",
+               "lower sign-ext operations to wasm mvp",
+               createSignExtLoweringPass);
   registerPass("simplify-globals",
                "miscellaneous globals-related optimizations",
                createSimplifyGlobalsPass);
diff --git a/src/passes/passes.h b/src/passes/passes.h
index ba60ade6f..65923cd25 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -125,6 +125,7 @@ Pass* createSafeHeapPass();
 Pass* createSetGlobalsPass();
 Pass* createSignaturePruningPass();
 Pass* createSignatureRefiningPass();
+Pass* createSignExtLoweringPass();
 Pass* createSimplifyLocalsPass();
 Pass* createSimplifyGlobalsPass();
 Pass* createSimplifyGlobalsOptimizingPass();
diff --git a/test/lit/help/wasm-opt.test b/test/lit/help/wasm-opt.test
index 4fd50abcc..2af38f982 100644
--- a/test/lit/help/wasm-opt.test
+++ b/test/lit/help/wasm-opt.test
@@ -386,6 +386,9 @@
 ;; CHECK-NEXT:   --signature-refining                          apply more specific subtypes to
 ;; CHECK-NEXT:                                                 signature types where possible
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --signext-lowering                            lower sign-ext operations to
+;; CHECK-NEXT:                                                 wasm mvp
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --simplify-globals                            miscellaneous globals-related
 ;; CHECK-NEXT:                                                 optimizations
 ;; CHECK-NEXT:
diff --git a/test/lit/help/wasm2js.test b/test/lit/help/wasm2js.test
index 7a782c872..e5669563d 100644
--- a/test/lit/help/wasm2js.test
+++ b/test/lit/help/wasm2js.test
@@ -345,6 +345,9 @@
 ;; CHECK-NEXT:   --signature-refining                          apply more specific subtypes to
 ;; CHECK-NEXT:                                                 signature types where possible
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --signext-lowering                            lower sign-ext operations to
+;; CHECK-NEXT:                                                 wasm mvp
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --simplify-globals                            miscellaneous globals-related
 ;; CHECK-NEXT:                                                 optimizations
 ;; CHECK-NEXT:
diff --git a/test/lit/passes/signext-lowering.wast b/test/lit/passes/signext-lowering.wast
new file mode 100644
index 000000000..f17479e53
--- /dev/null
+++ b/test/lit/passes/signext-lowering.wast
@@ -0,0 +1,66 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; RUN: wasm-opt %s --signext-lowering --enable-sign-ext -S -o - | filecheck %s
+
+(module
+ ;; CHECK:      (type $0 (func))
+ (type $0 (func))
+ ;; CHECK:      (func $signext
+ ;; CHECK-NEXT:  (local $0 i32)
+ ;; CHECK-NEXT:  (local $1 i64)
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (i32.shr_s
+ ;; CHECK-NEXT:    (i32.shl
+ ;; CHECK-NEXT:     (local.get $0)
+ ;; CHECK-NEXT:     (i32.const 24)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (i32.const 24)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (i32.shr_s
+ ;; CHECK-NEXT:    (i32.shl
+ ;; CHECK-NEXT:     (local.get $0)
+ ;; CHECK-NEXT:     (i32.const 16)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (i32.const 16)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (i64.shr_s
+ ;; CHECK-NEXT:    (i64.shl
+ ;; CHECK-NEXT:     (local.get $1)
+ ;; CHECK-NEXT:     (i64.const 56)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (i64.const 56)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (i64.shr_s
+ ;; CHECK-NEXT:    (i64.shl
+ ;; CHECK-NEXT:     (local.get $1)
+ ;; CHECK-NEXT:     (i64.const 48)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (i64.const 48)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (i64.shr_s
+ ;; CHECK-NEXT:    (i64.shl
+ ;; CHECK-NEXT:     (local.get $1)
+ ;; CHECK-NEXT:     (i64.const 32)
+ ;; CHECK-NEXT:    )
+ ;; CHECK-NEXT:    (i64.const 32)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $signext  (type $0)
+  (local $0 i32)
+  (local $1 i64)
+  (drop (i32.extend8_s (local.get $0)))
+  (drop (i32.extend16_s (local.get $0)))
+  (drop (i64.extend8_s (local.get $1)))
+  (drop (i64.extend16_s (local.get $1)))
+  (drop (i64.extend32_s (local.get $1)))
+ )
+)