ruby-changes:73169
From: Kevin <ko1@a...>
Date: Tue, 30 Aug 2022 00:57:53 +0900 (JST)
Subject: [ruby-changes:73169] b272c57f27 (master): LSL, LSR, B.cond (https://github.com/Shopify/ruby/pull/303)
https://git.ruby-lang.org/ruby.git/commit/?id=b272c57f27 From b272c57f27628ab114206c777d5b274713d31079 Mon Sep 17 00:00:00 2001 From: Kevin Newton <kddnewton@g...> Date: Wed, 22 Jun 2022 12:27:59 -0400 Subject: LSL, LSR, B.cond (https://github.com/Shopify/ruby/pull/303) * LSL and LSR * B.cond * Move A64 files around to make more sense * offset -> byte_offset for bcond --- yjit/src/asm/arm64/README.md | 6 +- yjit/src/asm/arm64/arg/bitmask_imm.rs | 250 ++++++++++++++++ yjit/src/asm/arm64/arg/condition.rs | 20 ++ yjit/src/asm/arm64/arg/mod.rs | 10 + yjit/src/asm/arm64/arg/sf.rs | 19 ++ yjit/src/asm/arm64/inst/bitmask_imm.rs | 250 ---------------- yjit/src/asm/arm64/inst/branch_cond.rs | 73 +++++ yjit/src/asm/arm64/inst/data_imm.rs | 2 +- yjit/src/asm/arm64/inst/data_reg.rs | 2 +- yjit/src/asm/arm64/inst/logical_imm.rs | 3 +- yjit/src/asm/arm64/inst/logical_reg.rs | 2 +- yjit/src/asm/arm64/inst/mod.rs | 494 ++---------------------------- yjit/src/asm/arm64/inst/mov.rs | 2 +- yjit/src/asm/arm64/inst/sf.rs | 19 -- yjit/src/asm/arm64/inst/shift_imm.rs | 147 +++++++++ yjit/src/asm/arm64/mod.rs | 527 +++++++++++++++++++++++++++++++++ 16 files changed, 1070 insertions(+), 756 deletions(-) create mode 100644 yjit/src/asm/arm64/arg/bitmask_imm.rs create mode 100644 yjit/src/asm/arm64/arg/condition.rs create mode 100644 yjit/src/asm/arm64/arg/mod.rs create mode 100644 yjit/src/asm/arm64/arg/sf.rs delete mode 100644 yjit/src/asm/arm64/inst/bitmask_imm.rs create mode 100644 yjit/src/asm/arm64/inst/branch_cond.rs delete mode 100644 yjit/src/asm/arm64/inst/sf.rs create mode 100644 yjit/src/asm/arm64/inst/shift_imm.rs diff --git a/yjit/src/asm/arm64/README.md b/yjit/src/asm/arm64/README.md index 3d0ec57d34..edae5773e8 100644 --- a/yjit/src/asm/arm64/README.md +++ b/yjit/src/asm/arm64/README.md @@ -4,11 +4,9 @@ This module is responsible for encoding YJIT operands into an appropriate Arm64 https://github.com/ruby/ruby/blob/trunk/yjit/src/asm/arm64/README.md#L4 ## Architecture -Every instruction in the Arm64 instruction set is 32 bits wide and is represented in little-endian order. Because they're all going to the same size, we represent each instruction by a struct that implements `From<T> for u32`, which contains the mechanism for encoding each instruction. +Every instruction in the Arm64 instruction set is 32 bits wide and is represented in little-endian order. Because they're all going to the same size, we represent each instruction by a struct that implements `From<T> for u32`, which contains the mechanism for encoding each instruction. The encoding for each instruction is shown in the documentation for the struct that ends up being created. -Generally each set of instructions falls under a certain family (like data processing -- register). These instructions are encoded similarly, so we group them into their own submodules. The encoding for each type is shown in the documentation for the struct that ends up being created. - -In general each set of bytes inside of the struct has either a direct value (usually a `u8`/`u16`) or some kind of `enum` that can be converted directly into a `u32`. +In general each set of bytes inside of the struct has either a direct value (usually a `u8`/`u16`) or some kind of `enum` that can be converted directly into a `u32`. For more complicated pieces of encoding (e.g., bitmask immediates) a corresponding module under the `arg` namespace is available. ## Helpful links diff --git a/yjit/src/asm/arm64/arg/bitmask_imm.rs b/yjit/src/asm/arm64/arg/bitmask_imm.rs new file mode 100644 index 0000000000..7e5a21c7b4 --- /dev/null +++ b/yjit/src/asm/arm64/arg/bitmask_imm.rs @@ -0,0 +1,250 @@ https://github.com/ruby/ruby/blob/trunk/yjit/src/asm/arm64/arg/bitmask_imm.rs#L1 +/// Immediates used by the logical immediate instructions are not actually the +/// immediate value, but instead are encoded into a 13-bit wide mask of 3 +/// elements. This allows many more values to be represented than 13 bits would +/// normally allow, at the expense of not being able to represent every possible +/// value. +/// +/// In order for a number to be encodeable in this form, the binary +/// representation must consist of a single set of contiguous 1s. That pattern +/// must then be replicatable across all of the bits either 1, 2, 4, 8, 16, or +/// 32 times (rotated or not). +/// +/// For example, 1 (0b1), 2 (0b10), 3 (0b11), and 4 (0b100) are all valid. +/// However, 5 (0b101) is invalid, because it contains 2 sets of 1s and cannot +/// be replicated across 64 bits. +/// +/// Some more examples to illustrate the idea of replication: +/// * 0x5555555555555555 is a valid value (0b0101...) because it consists of a +/// single set of 1s which can be replicated across all of the bits 32 times. +/// * 0xf0f0f0f0f0f0f0f0 is a valid value (0b1111000011110000...) because it +/// consists of a single set of 1s which can be replicated across all of the +/// bits 8 times (rotated by 4 bits). +/// * 0x0ff00ff00ff00ff0 is a valid value (0000111111110000...) because it +/// consists of a single set of 1s which can be replicated across all of the +/// bits 4 times (rotated by 12 bits). +/// +/// To encode the values, there are 3 elements: +/// * n = 1 if the pattern is 64-bits wide, 0 otherwise +/// * imms = the size of the pattern, a 0, and then one less than the number of +/// sequential 1s +/// * immr = the number of right rotations to apply to the pattern to get the +/// target value +/// +pub struct BitmaskImmediate { + n: u8, + imms: u8, + immr: u8 +} + +impl TryFrom<u64> for BitmaskImmediate { + type Error = (); + + /// Attempt to convert a u64 into a BitmaskImm. + fn try_from(value: u64) -> Result<Self, Self::Error> { + /// Is this number's binary representation all 1s? + fn is_mask(imm: u64) -> bool { + if imm == u64::MAX { true } else { ((imm + 1) & imm) == 0 } + } + + /// Is this number's binary representation one or more 1s followed by one or + /// more 0s? + fn is_shifted_mask(imm: u64) -> bool { + is_mask((imm - 1) | imm) + } + + let mut imm = value; + let mut size = 64; + + // First, determine the element size. + loop { + size >>= 1; + let mask = (1 << size) - 1; + + if (imm & mask) != ((imm >> size) & mask) { + size <<= 1; + break; + } + + if size <= 2 { + break; + } + } + + // Second, determine the rotation to make the pattern be aligned such + // that all of the least significant bits are 1. + let trailing_ones: u32; + let left_rotations: u32; + + let mask = u64::MAX >> (64 - size); + imm &= mask; + + if is_shifted_mask(imm) { + left_rotations = imm.trailing_zeros(); + assert!(left_rotations < 64); + trailing_ones = (imm >> left_rotations).trailing_ones(); + } else { + imm |= !mask; + if !is_shifted_mask(!imm) { + return Err(()); + } + + let leading_ones = imm.leading_ones(); + left_rotations = 64 - leading_ones; + trailing_ones = leading_ones + imm.trailing_ones() - (64 - size); + } + + // immr is the number of right rotations it takes to get from the + // matching unrotated pattern to the target value. + let immr = (size - left_rotations) & (size - 1); + assert!(size > left_rotations); + + // imms is encoded as the size of the pattern, a 0, and then one less + // than the number of sequential 1s. The table below shows how this is + // encoded. (Note that the way it works out, it's impossible for every x + // in a row to be 1 at the same time). + // +-------------+--------------+--------------+ + // | imms | element size | number of 1s | + // +-------------+--------------+--------------+ + // | 1 1 1 1 0 x | 2 bits | 1 | + // | 1 1 1 0 x x | 4 bits | 1-3 | + // | 1 1 0 x x x | 8 bits | 1-7 | + // | 1 0 x x x x | 16 bits | 1-15 | + // | 0 x x x x x | 32 bits | 1-31 | + // | x x x x x x | 64 bits | 1-63 | + // +-------------+--------------+--------------+ + let imms = (!(size - 1) << 1) | (trailing_ones - 1); + + // n is 1 if the element size is 64-bits, and 0 otherwise. + let n = ((imms >> 6) & 1) ^ 1; + + Ok(BitmaskImmediate { + n: n as u8, + imms: (imms & 0x3f) as u8, + immr: (immr & 0x3f) as u8 + }) + } +} + +impl From<BitmaskImmediate> for u32 { + /// Encode a bitmask immediate into a 32-bit value. + fn from(bitmask: BitmaskImmediate) -> Self { + 0 + | (((bitmask.n as u32) & 1) << 12) + | (bitmask.immr << 6) as u32 + | bitmask.imms as u32 + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_failures() { + vec![5, 9, 10, 11, 13, 17, 18, 19].iter().for_each(|&imm| { + assert!(BitmaskImmediate::try_from(imm).is_err()); + }); + } + + #[test] + fn test_size_2_minimum() { + let bitmask = BitmaskImmediate::try_from(0x5555555555555555); + assert!(matches!(bitmask, Ok(BitmaskImmediate { n: 0, immr: 0b000000, imms: 0b111100 }))); + } + + #[test] + fn test_size_2_maximum() { + let bitmask = BitmaskImmediate::try_from(0xaaaaaaaaaaaaaaaa); + assert!(matches!(bitmask, Ok(BitmaskImmediate { n: 0, immr: 0b000001, imms: 0b111100 }))); + } + + #[test] + fn test_size_4_minimum() { + let bitmask = BitmaskImmediate::try_from(0x1111111111111111); + assert!(matches!(bitmask, Ok(BitmaskImmediate { n: (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/