Add support to simd_bitmask intrinsic

[celinval]

Requested feature: Add support to simd_bitmask intrinsic
Use case: This intrinsic is commonly found during the code generation of the top 100 crates. Harnesses that exercise this intrinsic will fail due to unimplemented feature.
Link to relevant documentation (Rust reference, Nomicon, RFC):

[celinval]

Here is the definition from the intrinsics documentation:

    // truncate integer vector to bitmask
    // `fn simd_bitmask(vector) -> unsigned integer` takes a vector of integers and
    // returns either an unsigned integer or array of `u8`.
    // Every element in the vector becomes a single bit in the returned bitmask.
    // If the vector has less than 8 lanes, a u8 is returned with zeroed trailing bits.
    // The bit order of the result depends on the byte endianness. LSB-first for little
    // endian and MSB-first for big endian.
    //
    // UB if called on a vector with values other than 0 and -1.

From the actual Masks specification, the integer to mask operation is documented as:

Converts a vector of integers to a mask, where 0 represents false and -1 represents true.
Safety

All lanes must be either 0 or -1.

[tautschnig]

Given this specification I believe that Kani should generate a "concatenation" expression where each operand will be an "if" with a condition of "lane notequal 0" and "1" and "0" as the two cases. (I still don't understand under which condition an array is to be produced as result.)

[celinval]

The array will be produced if the input vector has more than 128 lanes. You basically need one bit per lane.

[celinval]

Kani can do this, but it will be inefficient. CBMC can probably encode operations that result in a single bit, while Kani will have to generate the results for each lane first, then join them in different bytes.

[celinval]

This intrinsic seems to be used by string comparison and hash map / hash set functions such as insert.

[celinval]

After talking to @remi-delmas-3000, we decided to implement this on the Kani side since CBMC modeling happens before bitblasting. So we would still need to do this operation byte-wise.

[celinval]

I created a basic Rust implementation of simd_bitmask that we could potentially use as a stub for this. However, I bumped into an issue while trying to transmute a SIMD structure. I created rust-lang/rust#113465 to capture the issue.

It's not clear if this issue will affect the verification use flow since we will hook the implementation inside the kani-compiler. However, it would be really nice to be able to add tests to the library implementation itself.

[celinval]

This work is also blocked by #2590

[workingjubilee]

You can't just use tuple access. You instead have to replicate our insane pattern for a legal read of a Simd type, sorry:

    /// Converts a SIMD vector to an array.
    #[inline]
    pub const fn to_array(self) -> [T; N] {
        let mut tmp = core::mem::MaybeUninit::uninit();
        // SAFETY: writing to `tmp` is safe and initializes it.
        //
        // FIXME: We currently use a pointer store instead of `transmute_copy` because `repr(simd)`
        // results in padding for non-power-of-2 vectors (so vectors are larger than arrays).
        //
        // NOTE: This deliberately doesn't just use `self.0`, see the comment
        // on the struct definition for details.
        unsafe {
            self.store(tmp.as_mut_ptr());
            tmp.assume_init()
        }
    }

[celinval]

Thanks @workingjubilee ! I think rust-lang/portable-simd#339 also has another workaround that seems to work:

https://github.com/rust-lang/portable-simd/blob/7c7dbe0c505ccbc02ff30c1e37381ab1d47bf46f/crates/core_simd/src/vector.rs#L162-L170

    pub const fn as_array(&self) -> &[T; N] {
        // SAFETY: `Simd<T, N>` is just an overaligned `[T; N]` with
        // potential padding at the end, so pointer casting to a
        // `&[T; N]` is safe.
        //
        // NOTE: This deliberately doesn't just use `&self.0`, see the comment
        // on the struct definition for details.
        unsafe { &*(self as *const Self as *const [T; N]) }
    }