Repository: bytecodealliance/wasmtime
Pull request #5673 (2023-01-31 18:58:13)

Cranelift: Rewrite `(x>>k)<<k` into masking off the bottom `k` bits
Thanks to Souper for pointing this one out! cc @regehr (let me know if you aren't interested in being cc'd on these!)

<!--

Please ensure that the following steps are all taken care of before submitting
the PR.

- [ ] This has been discussed in issue #..., or if not, please tell us why
  here.
- [ ] A short description of what this does, why it is needed; if the
  description becomes long, the matter should probably be discussed in an issue
  first.
- [ ] This PR contains test cases, if meaningful.
- [ ] A reviewer from the core maintainer team has been assigned for this PR.
  If you don't know who could review this, please indicate so. The list of
  suggested reviewers on the right can help you.

Please ensure all communication adheres to the [code of
conduct](https://github.com/bytecodealliance/wasmtime/blob/master/CODE_OF_CONDUCT.md).
-->



Patch:
diff --git a/cranelift/codegen/src/opts/algebraic.isle b/cranelift/codegen/src/opts/algebraic.isle
index 865c773bd..64a64a3a1 100644
--- a/cranelift/codegen/src/opts/algebraic.isle
+++ b/cranelift/codegen/src/opts/algebraic.isle
@@ -160,6 +160,19 @@
 ;; TODO: strength reduction: div to shifts
 ;; TODO: div/rem by constants -> magic multiplications
 
+;; `(x >> k) << k` is the same as masking off the bottom `k` bits (regardless if
+;; this is a signed or unsigned shift right).
+(rule (simplify (ishl (fits_in_64 ty)
+                      (ushr ty x (iconst _ (u64_from_imm64 k)))
+                      (iconst _ (u64_from_imm64 k))))
+      (let ((mask u64 (u64_shl 0xFFFFFFFFFFFFFFFF k)))
+        (band ty x (iconst ty (imm64_masked ty mask)))))
+(rule (simplify (ishl (fits_in_64 ty)
+                      (sshr ty x (iconst _ (u64_from_imm64 k)))
+                      (iconst _ (u64_from_imm64 k))))
+      (let ((mask u64 (u64_shl 0xFFFFFFFFFFFFFFFF k)))
+        (band ty x (iconst ty (imm64_masked ty mask)))))
+
 ;; Rematerialize ALU-op-with-imm and iconsts in each block where they're
 ;; used. This is neutral (add-with-imm) or positive (iconst) for
 ;; register pressure, and these ops are very cheap.
diff --git a/cranelift/frontend/Cargo.toml b/cranelift/frontend/Cargo.toml
index bb68f5e8d..eafcf74e9 100644
--- a/cranelift/frontend/Cargo.toml
+++ b/cranelift/frontend/Cargo.toml
@@ -11,7 +11,7 @@ readme = "README.md"
 edition.workspace = true
 
 [dependencies]
-cranelift-codegen = { workspace = true, default-features = false }
+cranelift-codegen = { workspace = true }
 target-lexicon = { workspace = true }
 log = { workspace = true }
 hashbrown = { workspace = true, optional = true }
diff --git a/cranelift/jit/Cargo.toml b/cranelift/jit/Cargo.toml
index 34114cf52..554e449ec 100644
--- a/cranelift/jit/Cargo.toml
+++ b/cranelift/jit/Cargo.toml
@@ -12,7 +12,7 @@ edition.workspace = true
 [dependencies]
 cranelift-module = { workspace = true }
 cranelift-native = { workspace = true }
-cranelift-codegen = { workspace = true, default-features = false, features = ["std"] }
+cranelift-codegen = { workspace = true, features = ["std"] }
 cranelift-entity = { workspace = true }
 anyhow = { workspace = true }
 region = "2.2.0"
diff --git a/cranelift/module/Cargo.toml b/cranelift/module/Cargo.toml
index 4e27af4b1..036a84e98 100644
--- a/cranelift/module/Cargo.toml
+++ b/cranelift/module/Cargo.toml
@@ -11,7 +11,7 @@ readme = "README.md"
 edition.workspace = true
 
 [dependencies]
-cranelift-codegen = { workspace = true, default-features = false }
+cranelift-codegen = { workspace = true }
 hashbrown = { workspace = true, optional = true }
 anyhow = { workspace = true }
 
diff --git a/cranelift/native/Cargo.toml b/cranelift/native/Cargo.toml
index 3e7c53106..776d3eb4b 100644
--- a/cranelift/native/Cargo.toml
+++ b/cranelift/native/Cargo.toml
@@ -11,7 +11,7 @@ readme = "README.md"
 edition.workspace = true
 
 [dependencies]
-cranelift-codegen = { workspace = true, default-features = false }
+cranelift-codegen = { workspace = true }
 target-lexicon = { workspace = true }
 
 [target.'cfg(any(target_arch = "s390x", target_arch = "riscv64"))'.dependencies]
@@ -24,4 +24,4 @@ core = ["cranelift-codegen/core"]
 
 [badges]
 maintenance = { status = "experimental" }
- 
+
diff --git a/cranelift/object/Cargo.toml b/cranelift/object/Cargo.toml
index c9f7ac1c3..e0d71aa41 100644
--- a/cranelift/object/Cargo.toml
+++ b/cranelift/object/Cargo.toml
@@ -11,7 +11,7 @@ edition.workspace = true
 
 [dependencies]
 cranelift-module = { workspace = true }
-cranelift-codegen = { workspace = true, default-features = false, features = ["std"] }
+cranelift-codegen = { workspace = true, features = ["std"] }
 object = { workspace = true, features = ["write"] }
 target-lexicon = { workspace = true }
 anyhow = { workspace = true }
diff --git a/cranelift/wasm/Cargo.toml b/cranelift/wasm/Cargo.toml
index af92764fc..671aa9e57 100644
--- a/cranelift/wasm/Cargo.toml
+++ b/cranelift/wasm/Cargo.toml
@@ -13,9 +13,9 @@ edition.workspace = true
 
 [dependencies]
 wasmparser = { workspace = true }
-cranelift-codegen = { workspace = true, default-features = false }
+cranelift-codegen = { workspace = true }
 cranelift-entity = { workspace = true }
-cranelift-frontend = { workspace = true, default-features = false }
+cranelift-frontend = { workspace = true }
 wasmtime-types = { workspace = true }
 hashbrown = { workspace = true, optional = true }
 itertools = "0.10.0"


Test patch:
diff --git a/cranelift/filetests/filetests/egraph/algebraic.clif b/cranelift/filetests/filetests/egraph/algebraic.clif
index 409788ce8..33e83936c 100644
--- a/cranelift/filetests/filetests/egraph/algebraic.clif
+++ b/cranelift/filetests/filetests/egraph/algebraic.clif
@@ -20,3 +20,69 @@ block0:
   ; check: v2 = iconst.i64 0x9876_5432
   ; check: return v2  ; v2 = 0x9876_5432
 }
+
+function %unsigned_shift_right_shift_left_i8(i8) -> i8 {
+block0(v0: i8):
+    v1 = iconst.i8 5
+    v2 = ushr v0, v1
+    v3 = ishl v2, v1
+    return v3
+    ; check: v4 = iconst.i8 224
+    ; check: v5 = band v0, v4
+    ; return v5
+}
+
+function %unsigned_shift_right_shift_left_i32(i32) -> i32 {
+block0(v0: i32):
+    v1 = iconst.i32 5
+    v2 = ushr v0, v1
+    v3 = ishl v2, v1
+    return v3
+    ; check: v4 = iconst.i32 0xffff_ffe0
+    ; check: v5 = band v0, v4
+    ; return v5
+}
+
+function %unsigned_shift_right_shift_left_i64(i64) -> i64 {
+block0(v0: i64):
+    v1 = iconst.i64 5
+    v2 = ushr v0, v1
+    v3 = ishl v2, v1
+    return v3
+    ; check: v4 = iconst.i64 -32
+    ; check: v5 = band v0, v4
+    ; return v5
+}
+
+function %signed_shift_right_shift_left_i8(i8) -> i8 {
+block0(v0: i8):
+    v1 = iconst.i8 5
+    v2 = sshr v0, v1
+    v3 = ishl v2, v1
+    return v3
+    ; check: v4 = iconst.i8 224
+    ; check: v5 = band v0, v4
+    ; return v5
+}
+
+function %signed_shift_right_shift_left_i32(i32) -> i32 {
+block0(v0: i32):
+    v1 = iconst.i32 5
+    v2 = sshr v0, v1
+    v3 = ishl v2, v1
+    return v3
+    ; check: v4 = iconst.i32 0xffff_ffe0
+    ; check: v5 = band v0, v4
+    ; return v5
+}
+
+function %signed_shift_right_shift_left_i64(i64) -> i64 {
+block0(v0: i64):
+    v1 = iconst.i64 5
+    v2 = sshr v0, v1
+    v3 = ishl v2, v1
+    return v3
+    ; check: v4 = iconst.i64 -32
+    ; check: v5 = band v0, v4
+    ; return v5
+}
diff --git a/cranelift/filetests/filetests/runtests/shift-right-left.clif b/cranelift/filetests/filetests/runtests/shift-right-left.clif
new file mode 100644
index 000000000..258ae78d4
--- /dev/null
+++ b/cranelift/filetests/filetests/runtests/shift-right-left.clif
@@ -0,0 +1,74 @@
+;; Test that our rewrite of `(x >> k) << k` into masking is correct.
+
+test interpret
+test run
+target aarch64
+target x86_64
+target riscv64
+target s390x
+
+function %unsigned_shift_right_shift_left_i8(i8) -> i8 {
+block0(v0: i8):
+    v1 = iconst.i8 5
+    v2 = ushr v0, v1
+    v3 = ishl v2, v1
+    return v3
+}
+; run: %unsigned_shift_right_shift_left_i8(-1) == 0xe0
+; run: %unsigned_shift_right_shift_left_i8(0) == 0
+; run: %unsigned_shift_right_shift_left_i8(0xaa) == 0xa0
+
+function %unsigned_shift_right_shift_left_i32(i32) -> i32 {
+block0(v0: i32):
+    v1 = iconst.i32 5
+    v2 = ushr v0, v1
+    v3 = ishl v2, v1
+    return v3
+}
+; run: %unsigned_shift_right_shift_left_i32(-1) == 0xffffffe0
+; run: %unsigned_shift_right_shift_left_i32(0) == 0
+; run: %unsigned_shift_right_shift_left_i32(0xaaaaaaaa) == 0xaaaaaaa0
+
+function %unsigned_shift_right_shift_left_i64(i64) -> i64 {
+block0(v0: i64):
+    v1 = iconst.i64 5
+    v2 = ushr v0, v1
+    v3 = ishl v2, v1
+    return v3
+}
+; run: %unsigned_shift_right_shift_left_i64(-1) == 0xffffffffffffffe0
+; run: %unsigned_shift_right_shift_left_i64(0) == 0
+; run: %unsigned_shift_right_shift_left_i64(0xaaaaaaaaaaaaaaaa) == 0xaaaaaaaaaaaaaaa0
+
+function %signed_shift_right_shift_left_i8(i8) -> i8 {
+block0(v0: i8):
+    v1 = iconst.i8 5
+    v2 = sshr v0, v1
+    v3 = ishl v2, v1
+    return v3
+}
+; run: %signed_shift_right_shift_left_i8(-1) == 0xe0
+; run: %signed_shift_right_shift_left_i8(0) == 0
+; run: %signed_shift_right_shift_left_i8(0xaa) == 0xa0
+
+function %signed_shift_right_shift_left_i32(i32) -> i32 {
+block0(v0: i32):
+    v1 = iconst.i32 5
+    v2 = sshr v0, v1
+    v3 = ishl v2, v1
+    return v3
+}
+; run: %signed_shift_right_shift_left_i32(-1) == 0xffffffe0
+; run: %signed_shift_right_shift_left_i32(0) == 0
+; run: %signed_shift_right_shift_left_i32(0xaaaaaaaa) == 0xaaaaaaa0
+
+function %signed_shift_right_shift_left_i64(i64) -> i64 {
+block0(v0: i64):
+    v1 = iconst.i64 5
+    v2 = sshr v0, v1
+    v3 = ishl v2, v1
+    return v3
+}
+; run: %signed_shift_right_shift_left_i64(-1) == 0xffffffffffffffe0
+; run: %signed_shift_right_shift_left_i64(0) == 0
+; run: %signed_shift_right_shift_left_i64(0xaaaaaaaaaaaaaaaa) == 0xaaaaaaaaaaaaaaa0