weaselbotandandrew
0b12a037c4
CI / release (arm64, , ubuntu-latest-arm64) (pull_request) Successful in 2m14s
CI / pre-commit (pull_request) Successful in 1m59s
CI / test (-DCMAKE_BUILD_TYPE=Debug -DMSAN_TOOLCHAIN_PATH=/opt/msan, debug) (pull_request) Successful in 3m47s
CI / test (-DCMAKE_CXX_FLAGS=-DUSE_64_BIT=1, 64-bit-versions) (pull_request) Successful in 3m14s
CI / test (-DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++, gcc) (pull_request) Successful in 3m13s
CI / test (-DUSE_SIMD_FALLBACK=ON, simd-fallback) (pull_request) Successful in 3m17s
CI / release (amd64, -DMSAN_TOOLCHAIN_PATH=/opt/msan, ubuntu-latest-amd64) (pull_request) Successful in 5m27s
CI / coverage (pull_request) Successful in 3m42s
The SIMD operations are written in assembly because loading and operating on indeterminate values is UB in C++ but well-defined in assembly. msan not tracking the loads is a side effect, not the reason. Closes #71
86 lines
3.3 KiB
ArmAsm
86 lines
3.3 KiB
ArmAsm
// SIMD operations on potentially-indeterminate Node16::index[16] bytes.
|
|
// Written in assembly because loading and operating on indeterminate values
|
|
// is UB in C++ but well-defined in assembly. (A side effect is that msan
|
|
// doesn't track the loads.) The caller is responsible for masking the
|
|
// returned bitfield to [0, numChildren) before using it.
|
|
//
|
|
// All functions return a 16-bit bitmask in %eax (bit i set = condition true
|
|
// at index i). The upper 16 bits of %eax are zero.
|
|
//
|
|
// System V AMD64 ABI:
|
|
// %rdi = const uint8_t *idx (16 bytes)
|
|
// %esi = uint8_t key (find_eq_16, find_ge_16)
|
|
// %sil = uint8_t begin (mask_in_range_16)
|
|
// %dl = uint8_t end (mask_in_range_16)
|
|
|
|
.text
|
|
|
|
// uint32_t find_eq_16(const uint8_t idx[16], uint8_t key)
|
|
// Returns bit i set if idx[i] == key
|
|
.globl find_eq_16
|
|
.type find_eq_16, @function
|
|
find_eq_16:
|
|
vmovd %esi, %xmm1 // broadcast key
|
|
vpbroadcastb %xmm1, %xmm1
|
|
vmovdqu (%rdi), %xmm0 // load 16 bytes (may contain indeterminate data)
|
|
vpcmpeqb %xmm0, %xmm1, %xmm0 // 0xff for each match
|
|
vpmovmskb %xmm0, %eax // 16-bit bitmask
|
|
movzwl %ax, %eax // zero-extend to 32 bits
|
|
ret
|
|
.size find_eq_16, .-find_eq_16
|
|
|
|
// uint32_t find_ge_16(const uint8_t idx[16], uint8_t child)
|
|
// Returns bit i set if idx[i] >= child
|
|
// x86 doesn't have a "compare unsigned >=" for bytes directly, so we use:
|
|
// min(key, idx[i]) == key iff idx[i] >= key
|
|
.globl find_ge_16
|
|
.type find_ge_16, @function
|
|
find_ge_16:
|
|
vmovd %esi, %xmm1
|
|
vpbroadcastb %xmm1, %xmm1 // key broadcast
|
|
vmovdqu (%rdi), %xmm0 // load 16 bytes
|
|
vpminub %xmm0, %xmm1, %xmm2 // min(key, idx[i])
|
|
vpcmpeqb %xmm2, %xmm1, %xmm0 // 0xff where min == key, i.e. idx[i] >= key
|
|
vpmovmskb %xmm0, %eax
|
|
movzwl %ax, %eax
|
|
ret
|
|
.size find_ge_16, .-find_ge_16
|
|
|
|
// uint32_t mask_in_range_16(const uint8_t idx[16], uint8_t begin, uint8_t end)
|
|
// Returns bit i set if begin <= idx[i] < end
|
|
// Logic: (idx[i] - begin) < (end - begin) [unsigned wrapping arithmetic]
|
|
// Equivalently: idx[i] - begin != max(idx[i] - begin, end - begin)
|
|
// i.e. idx[i] - begin is NOT equal to the saturated value.
|
|
// We compute: sub = idx - begin; result = (sub < (end-begin)) for each byte.
|
|
// Using: sub == max(sub, end-begin) means NOT in range.
|
|
// So: in_range = ~(movemask(cmpeq(sub, max(sub, range_size))))
|
|
.globl mask_in_range_16
|
|
.type mask_in_range_16, @function
|
|
mask_in_range_16:
|
|
vmovd %esi, %xmm1 // begin
|
|
vpbroadcastb %xmm1, %xmm1
|
|
vmovd %edx, %xmm2 // end
|
|
vpbroadcastb %xmm2, %xmm2
|
|
vmovdqu (%rdi), %xmm0 // load 16 bytes
|
|
vpsubb %xmm1, %xmm0, %xmm0 // idx - begin (wrapping)
|
|
vpsubb %xmm1, %xmm2, %xmm2 // end - begin (range size)
|
|
vpmaxub %xmm0, %xmm2, %xmm3 // max(idx-begin, range_size)
|
|
vpcmpeqb %xmm3, %xmm0, %xmm0 // 0xff where NOT in range
|
|
vpmovmskb %xmm0, %eax
|
|
not %eax // invert: 1 = in range
|
|
movzwl %ax, %eax
|
|
ret
|
|
.size mask_in_range_16, .-mask_in_range_16
|
|
|
|
.section .note.gnu.property,"a",@note
|
|
.p2align 3, 0x0
|
|
.long 4
|
|
.long 16
|
|
.long 5
|
|
.asciz "GNU"
|
|
.long 0xc0000002
|
|
.long 4
|
|
.long 0x3
|
|
.p2align 3, 0x0
|
|
|
|
.section .note.GNU-stack,"",@progbits
|