llvm / llvm/llvm-project

__builtin_unpredictable ignored

Open
#204,979 2 comments 0 reactions 0 assignees View on GitHub
missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.