llvm / llvm/llvm-project

Hundreds of unnecessary instructions generated during unrolling

Open
#205,167 1 comment 0 reactions 0 assignees View on GitHub
loopoptim
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

godbolt: https://godbolt.org/z/GeqbhhTnP

With the unroll pragma commented out, clang 22.1 generates hundreds of instruction for the vint encoder below.

With the unroll pragma in, about 34 instructions are generated.

Yes, the branch mispredict penalty is bad. But is it worth hundreds of instructions? And ~900 bytes of icache footprint?

```c++

#include
#include

// Mask for extracting from the first byte the part that is not used for indicating the total number of bytes.
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;
}

// The number of additional bytes that we need to read.
static unsigned count_extra_bytes(int8_t first_byte) {
return std::countl_zero(static_cast(~first_byte));
}

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);
}

static void encode(uint64_t value, unsigned size, char* out) {
// `size` is always in the range [1, 9].
const auto extra_bytes_size = size - 1;
__builtin_assume(extra_bytes_size <= 8);
auto value_mask = first_byte_value_mask(extra_bytes_size);

// Prevent unrolling of clang goes crazy trying to vectorize
//#pragma GCC unroll 1
for (unsigned i = 0; i <= extra_bytes_size; ++i) {
auto msb_shift = (8 * (extra_bytes_size - i)) & 63; // prevent undefined behavior on 64-bit shift
*out++ = ((value >> msb_shift) & value_mask) | ~value_mask;
value_mask = 0xff;
}

}

unsigned serialize(uint64_t value, char* out) {
const auto size = serialized_size(value);

encode(value, size, out);
return size;
}

```

Contributor guide

Open the contributing guide

Research direction

Start with the Godbolt reproducer and compare Clang 22.1 assembly for encode with and without the unroll pragma. Trace the loop-unrolling and vectorization decisions responsible for the large instruction sequence, then identify relevant compiler tests or add a focused regression test. Done means the reproducer no longer produces the unnecessary code without changing serialization behavior.

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
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.