RFC 1199: simd-infrastructure

lang (repr | simd | intrinsic)

Summary

Lay the ground work for building powerful SIMD functionality.

Motivation

SIMD (Single-Instruction Multiple-Data) is an important part of performant modern applications. Most CPUs used for that sort of task provide dedicated hardware and instructions for operating on multiple values in a single instruction, and exposing this is an important part of being a low-level language.

This RFC lays the ground-work for building nice SIMD functionality, but doesn't fill everything out. The goal here is to provide the raw types and access to the raw instructions on each platform.

(An earlier variant of this RFC was discussed as a pre-RFC.)

Where does this code go? Aka. why not in std?

This RFC is focused on building stable, powerful SIMD functionality in external crates, not std.

This makes it much easier to support functionality only "occasionally" available with Rust's preexisting cfg system. There's no way for std to conditionally provide an API based on the target features used for the final artifact. Building std in every configuration is certainly untenable. Hence, if it were to be in std, there would need to be some highly delayed cfg system to support that sort of conditional API exposure.

With an external crate, we can leverage cargo's existing build infrastructure: compiling with some target features will rebuild with those features enabled.

Detailed design

The design comes in three parts, all on the path to stabilisation:

The general idea is to avoid bad performance cliffs, so that an intrinsic call in Rust maps to preferably one CPU instruction, or, if not, the "optimal" sequence required to do the given operation anyway. This means exposing a lot of platform specific details, since platforms behave very differently: both across architecture families (x86, x86-64, ARM, MIPS, ...), and even within a family (x86-64's Skylake, Haswell, Nehalem, ...).

There is definitely a common core of SIMD functionality shared across many platforms, but this RFC doesn't try to extract that, it is just building tools that can be wrapped into a more uniform API later.

Types

There is a new attribute: repr(simd).

#[repr(simd)]
struct f32x4(f32, f32, f32, f32);

#[repr(simd)]
struct Simd2<T>(T, T);

The simd repr can be attached to a struct and will cause such a struct to be compiled to a SIMD vector. It can be generic, but it is required that any fully monomorphised instance of the type consist of only a single "primitive" type, repeated some number of times.

The repr(simd) may not enforce that any trait bounds exists/does the right thing at the type checking level for generic repr(simd) types. As such, it will be possible to get the code-generator to error out (ala the old transmute size errors), however, this shouldn't cause problems in practice: libraries wrapping this functionality would layer type-safety on top (i.e. generic repr(simd) types would use some unsafe trait as a bound that is designed to only be implemented by types that will work).

Adding repr(simd) to a type may increase its minimum/preferred alignment, based on platform behaviour. (E.g. x86 wants its 128-bit SSE vectors to be 128-bit aligned.)

Operations

CPU vendors usually offer "standard" C headers for their CPU specific operations, such as arm_neon.h and the ...mmintrin.h headers for x86(-64).

All of these would be exposed as compiler intrinsics with names very similar to those that the vendor suggests (only difference would be some form of manual namespacing, e.g. prefixing with the CPU target), loadable via an extern block with an appropriate ABI. This subset of intrinsics would be on the path to stabilisation (that is, one can "import" them with extern in stable code), and would not be exported by std.

Example:

extern "platform-intrinsic" {
    fn x86_mm_abs_epi16(a: Simd8<i16>) -> Simd8<i16>;
    // ...
}

These all use entirely concrete types, and this is the core interface to these intrinsics: essentially it is just allowing code to exactly specify a CPU instruction to use. These intrinsics only actually work on a subset of the CPUs that Rust targets, and will result in compile time errors if they are called on platforms that do not support them. The signatures are typechecked, but in a "duck-typed" manner: it will just ensure that the types are SIMD vectors with the appropriate length and element type, it will not enforce a specific nominal type.

NB. The structural typing is just for the declaration: if a SIMD intrinsic is declared to take a type X, it must always be called with X, even if other types are structurally equal to X. Also, within a signature, SIMD types that must be structurally equal must be nominally equal. I.e. if the add_... all refer to the same intrinsic to add a SIMD vector of bytes,

// (same length)
struct A(u8, u8, ..., u8);
struct B(u8, u8, ..., u8);

extern "platform-intrinsic" {
    fn add_aaa(x: A, y: A) -> A; // ok
    fn add_bbb(x: B, y: B) -> B; // ok
    fn add_aab(x: A, y: A) -> B; // error, expected B, found A
    fn add_bab(x: B, y: A) -> B; // error, expected A, found B
}

fn double_a(x: A) -> A {
    add_aaa(x, x)
}
fn double_b(x: B) -> B {
    add_aaa(x, x) // error, expected A, found B
}

There would additionally be a small set of cross-platform operations that are either generally efficiently supported everywhere or are extremely useful. These won't necessarily map to a single instruction, but will be shimmed as efficiently as possible.

All of these intrinsics are imported via an extern directive similar to the process for pre-existing intrinsics like transmute, however, the SIMD operations are provided under a special ABI: platform-intrinsic. Use of this ABI (and hence the intrinsics) is initially feature-gated under the platform_intrinsics feature name. Why platform-intrinsic rather than say simd-intrinsic? There are non-SIMD platform-specific instructions that may be nice to expose (for example, Intel defines an _addcarry_u32 intrinsic corresponding to the ADC instruction).

Shuffles & element operations

One of the most powerful features of SIMD is the ability to rearrange data within vectors, giving super-linear speed-ups sometimes. As such, shuffles are exposed generally: intrinsics that represent arbitrary shuffles.

This may violate the "one instruction per instrinsic" principal depending on the shuffle, but rearranging SIMD vectors is extremely useful, and providing a direct intrinsic lets the compiler (a) do the programmers work in synthesising the optimal (short) sequence of instructions to get a given shuffle and (b) track data through shuffles without having to understand all the details of every platform specific intrinsic for shuffling.

extern "platform-intrinsic" {
    fn simd_shuffle2<T, U>(v: T, w: T, idx: [i32; 2]) -> U;
    fn simd_shuffle4<T, U>(v: T, w: T, idx: [i32; 4]) -> U;
    fn simd_shuffle8<T, U>(v: T, w: T, idx: [i32; 8]) -> U;
    fn simd_shuffle16<T, U>(v: T, w: T, idx: [i32; 16]) -> U;
    // ...
}

The raw definitions are only checked for validity at monomorphisation time, ensure that T and U are SIMD vector with the same element type, U has the appropriate length etc. Libraries can use traits to ensure that these will be enforced by the type checker too.

This approach has similar type "safety"/code-generation errors to the vectors themselves.

These operations are semantically:

// vector of double length
let z = concat(v, w);

return [z[idx[0]], z[idx[1]], z[idx[2]], ...]

The index array idx has to be compile time constants. Out of bounds indices yield errors.

Similarly, intrinsics for inserting/extracting elements into/out of vectors are provided, to allow modelling the SIMD vectors as actual CPU registers as much as possible:

extern "platform-intrinsic" {
    fn simd_insert<T, Elem>(v: T, i0: u32, elem: Elem) -> T;
    fn simd_extract<T, Elem>(v: T, i0: u32) -> Elem;
}

The i0 indices do not have to be constant. These are equivalent to v[i0] = elem and v[i0] respectively. They are type checked similarly to the shuffles.

Comparisons

Comparisons are implemented via intrinsics. The raw signatures would look like:

extern "platform-intrinsic" {
    fn simd_eq<T, U>(v: T, w: T) -> U;
    fn simd_ne<T, U>(v: T, w: T) -> U;
    fn simd_lt<T, U>(v: T, w: T) -> U;
    fn simd_le<T, U>(v: T, w: T) -> U;
    fn simd_gt<T, U>(v: T, w: T) -> U;
    fn simd_ge<T, U>(v: T, w: T) -> U;
}

These are type checked during code-generation similarly to the shuffles: ensuring that T and U have the same length, and that U is appropriately "boolean"-y. Libraries can use traits to ensure that these will be enforced by the type checker too.

Arithmetic

Intrinsics will be provided for arithmetic operations like addition and multiplication.

extern "platform-intrinsic" {
    fn simd_add<T>(x: T, y: T) -> T;
    fn simd_mul<T>(x: T, y: T) -> T;
    // ...
}

These will have codegen time checks that the element type is correct:

(The integer types are i8, ..., i64, u8, ..., u64 and the float types are f32 and f64.)

Why not inline asm?

One alternative to providing intrinsics is to instead just use inline-asm to expose each CPU instruction. However, this approach has essentially only one benefit (avoiding defining the intrinsics), but several downsides, e.g.

Benefits of manual assembly writing, like instruction scheduling and register allocation don't apply to the (generally) one-instruction asm! blocks that replace the intrinsics (they need to be designed so that the compiler has full control over register allocation, or else the result will be strictly worse). Those possible advantages of hand written assembly over intrinsics only come in to play when writing longer blocks of raw assembly, i.e. some inner loop might be faster when written as a single chunk of asm rather than as intrinsics.

Platform Detection

The availability of efficient SIMD functionality is very fine-grained, and our current cfg(target_arch = "...") is not precise enough. This RFC proposes a target_feature cfg, that would be set to the features of the architecture that are known to be supported by the exact target e.g.

The possible values of target_feature will be a selected whitelist, not necessarily just everything LLVM understands. There are other non-SIMD features that might have target_features set too, such as popcnt and rdrnd on x86/x86-64.)

With a cfg_if! macro that expands to the first cfg that is satisfied (ala @alexcrichton's cfg-if), code might look like:

cfg_if_else! {
    if #[cfg(target_feature = "avx")] {
        fn foo() { /* use AVX things */ }
    } else if #[cfg(target_feature = "sse4.1")] {
        fn foo() { /* use SSE4.1 things */ }
    } else if #[cfg(target_feature = "sse2")] {
        fn foo() { /* use SSE2 things */ }
    } else if #[cfg(target_feature = "neon")] {
        fn foo() { /* use NEON things */ }
    } else {
        fn foo() { /* universal fallback */ }
    }
}

Extensions

Alternatives

Unresolved questions

Copyright 2022 Nick Cameron and the RFC authors.