__builtin_unpredictable ignored
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Example code typing to serialize using a variable size encoding by directing some of the writes into the stack:
```c++
#include
#include
#include
#if !__has_builtin(__builtin_unpredictable)
#define __builtin_unpredictable(x) __builtin_expect_with_probability(x, 1, 0.5)
#endif
template
inline
void
write_be(char* p, T datum) noexcept {
datum = std::byteswap(datum);
std::copy_n(reinterpret_cast(&datum), sizeof(T), p);
}
static
unsigned serialized_size_from_first_byte(int8_t first_byte) {
return 1 + std::countl_zero(static_cast(~first_byte));
}
static uint64_t first_byte_value_mask(unsigned extra_bytes_size) {
// Include the sentinel zero bit in the mask.
return uint64_t(0xff) >> extra_bytes_size;
}
static
unsigned serialized_size(uint64_t value) noexcept {
// No need for the overhead of checking that all bits are zero.
//
// A signed quantity, to allow the case of `magnitude == 0` to result in a value of 9 below.
const auto magnitude = static_cast(std::countl_zero(value | uint64_t(1)));
return unsigned(9) - unsigned((magnitude - 1) / 7);
}
unsigned serialize(uint64_t value, char* out) {
const auto size = serialized_size(value);
// `size` is always in the range [1, 9].
auto extra_bytes_size = size - 1;
*out++ = ((value >> (extra_bytes_size * 8)) & 0xff) | ~first_byte_value_mask(extra_bytes_size);
char garbage[8];
// Encode the remaining bytes in big-endian order, directing unneeded bytes into a garbage array.
// This avoids conditional branches.
auto* dest64 = __builtin_unpredictable(extra_bytes_size == 8) ? out : garbage;
auto delta64 = __builtin_unpredictable(extra_bytes_size == 8) ? 8 : 0;
write_be(dest64, value);
extra_bytes_size -= delta64;
out += delta64;
auto* dest32 = __builtin_unpredictable(extra_bytes_size >= 4) ? out : garbage;
auto delta32 = __builtin_unpredictable(extra_bytes_size >= 4) ? 4 : 0;
write_be(dest32, value);
extra_bytes_size -= delta32;
out += delta32;
value >>= delta32 * 8;
auto* dest16 = __builtin_unpredictable(extra_bytes_size >= 2) ? out : garbage;
auto delta16 = __builtin_unpredictable(extra_bytes_size >= 2) ? 2 : 0;
write_be(dest16, value);
extra_bytes_size -= delta16;
out += delta16;
value >>= delta16 * 8;
auto* dest8 = __builtin_unpredictable(extra_bytes_size >= 1) ? out : garbage;
auto delta8 = __builtin_unpredictable(extra_bytes_size >= 1) ? 1 : 0;
write_be(dest8, value);
extra_bytes_size -= delta8;
out += delta8;
return size;
}
```
Generates (unreleased clang 23):
```asm
serialize(unsigned long, char*):
movq %rdi, %rax
orq $1, %rax
bsrq %rax, %rax
xorl $63, %eax
leal -1(%rax), %ecx
movsbl %cl, %ecx
imull $109, %ecx, %ecx
shrl $8, %ecx
subb %al, %cl
incb %cl
movl %ecx, %eax
shrb $7, %al
sarb $2, %cl
addb %al, %cl
addb $9, %cl
movzbl %cl, %eax
leal -1(%rax), %edx
leal -8(,%rax,8), %ecx
movq %rdi, %r9
shrq %cl, %r9
movq $-256, %r8
movl %edx, %ecx
sarq %cl, %r8
orl %r8d, %r9d
leaq 1(%rsi), %r8
xorl %ecx, %ecx
cmpl $8, %edx
sete %cl
shll $3, %ecx
movb %r9b, (%rsi)
cmpl $8, %edx
jne .LBB0_2
movq %rdi, %rsi
bswapq %rsi
movq %rsi, (%r8)
.LBB0_2:
subl %ecx, %edx
movl %ecx, %ecx
addq %rcx, %r8
xorl %ecx, %ecx
cmpl $4, %edx
setae %cl
shll $2, %ecx
cmpl $4, %edx
jb .LBB0_4
movl %edi, %esi
bswapl %esi
movl %esi, (%r8)
.LBB0_4:
subl %ecx, %edx
movl %ecx, %esi
addq %rsi, %r8
shll $3, %ecx
shrq %cl, %rdi
xorl %esi, %esi
cmpl $2, %edx
setae %sil
addl %esi, %esi
cmpl $2, %edx
jae .LBB0_5
cmpl %esi, %edx
jne .LBB0_7
.LBB0_8:
retq
.LBB0_5:
movl %edi, %ecx
rolw $8, %cx
movw %cx, (%r8)
cmpl %esi, %edx
je .LBB0_8
.LBB0_7:
leal (,%rsi,8), %ecx
shrq %cl, %rdi
movl %esi, %ecx
movb %dil, (%r8,%rcx)
retq
```
Notice the many jumps. I expected a couple of cmovs per iteration instead.
https://godbolt.org/z/q7dGeb9x9
Contributor guide
Research direction
The issue provides a C++ serialize reproducer and a Compiler Explorer link; start by compiling it with the cited unreleased Clang 23 configuration and comparing the generated assembly. Trace how __builtin_unpredictable is lowered for these branches, and consider the issue done when the generated code reflects the expected cmov-based form shown in the report.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 48/100