llvm / llvm/llvm-project

[LV][X64] Loop vectorizer generates much slower and bloated code

Open
#217,830 15 comments 0 reactions 0 assignees View on GitHub
backend:X86 Scheduler Models missed-optimization vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

### How to reproduce

Consider this code snippet:
https://godbolt.org/z/o5qGv38bv

Or here if the link is down:

```c
#include
#include

typedef struct f16 {
_Alignas(64) float dat[16];
} f16;

int f(const f16 *const x) {
int ret = 0;
for (int t = 0; t < 16; ++t)
if (x->dat[t] >= 0x1p10f)
++ret;
return ret;
}

typedef struct u16 {
_Alignas(64) uint16_t dat[32];
} u16;

int g(const u16 *const x) {
int ret = 0;
for (int t = 0; t < 32; ++t)
if (x->dat[t] >= 0x100)
++ret;
return ret;
}
```

Using clang 22.1.8-msvc with `-march=znver5` (or may equivalently, `-mavx512f -mavx512bw`), under `-Os`, both function `f` and `g` generate quality code, utilizing avx512 correctly:

```asm
@feat.00 = 0

__real@44800000:
.long 0x44800000

f:
vbroadcastss __real@44800000(%rip), %zmm0
vcmpleps (%rcx), %zmm0, %k0
kmovw %k0, %eax
popcntl %eax, %eax
vzeroupper
retq
.LCPI1_0:
.short 255
.LCPI1_1:
.byte 1

g:
vpbroadcastw .LCPI1_0(%rip), %ymm0
vpcmpltuw 32(%rcx), %ymm0, %k1
vpcmpltuw (%rcx), %ymm0, %k0
vpbroadcastb .LCPI1_1(%rip), %xmm1 {%k1} {z}
vpmovm2b %k0, %xmm0
vpsubb %xmm0, %xmm1, %xmm0
vpxor %xmm1, %xmm1, %xmm1
vpsadbw %xmm1, %xmm0, %xmm0
vpshufd $238, %xmm0, %xmm1
vpaddq %xmm1, %xmm0, %xmm0
vmovd %xmm0, %eax
vzeroupper
retq
.ascii " /DEFAULTLIB:msvcrt.lib"
```

Things becomes interesting while we use `-O2`, function `f` bloats:

```asm
@feat.00 = 0

__real@44800000:
.long 0x44800000

f:
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rsi
pushq %rdi
pushq %rbp
pushq %rbx
vbroadcastss __real@44800000(%rip), %zmm0
vcmpleps (%rcx), %zmm0, %k0
kshiftrw $1, %k0, %k1
kmovd %k0, %eax
kmovd %k1, %ecx
kshiftrw $2, %k0, %k1
andl $1, %eax
kmovd %k1, %r8d
kshiftrw $3, %k0, %k1
andl $1, %ecx
kmovd %k1, %edx
# ###
# so many repeating kshiftrw and kmovd... omitted.
# ###
kshiftrw $15, %k0, %k0
addl %r9d, %esi
kmovd %k1, %r13d
addl %r14d, %r15d
andl $1, %r12d
kmovd %k0, %eax
addl %r15d, %r12d
andl $1, %r13d
andl $1, %eax
addl %r12d, %r13d
addl %r13d, %eax
addl %esi, %eax
popq %rbx
popq %rbp
popq %rdi
popq %rsi
popq %r12
popq %r13
popq %r14
popq %r15
vzeroupper
retq

__ymm@00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff:
.short 255
# repeating lines omitted
.short 255

__xmm@01010101010101010101010101010101:
.zero 16,1

__xmm@00ff00ff00ff00ff00ff00ff00ff00ff:
.short 255
# repeating lines omitted
.short 255

g:
# essentially the same as its -Os version
```

And when it comes to `-O3`, function `g` bloats:

```asm
@feat.00 = 0

__real@44800000:
.long 0x44800000

f:
# essentially the same as its -O2 version
g:
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rsi
pushq %rdi
pushq %rbp
pushq %rbx
subq $16, %rsp
vmovdqu64 (%rcx), %zmm0
vpcmpnleuw .LCPI1_0(%rip), %zmm0, %k0
kshiftrd $1, %k0, %k1
kmovd %k0, %r11d
kmovd %k1, %ecx
kshiftrd $2, %k0, %k1
andl $1, %r11d
kmovd %k1, %r13d
kshiftrd $3, %k0, %k1
andl $1, %ecx
kmovd %k1, %r8d
kshiftrd $4, %k0, %k1
addl %r11d, %ecx
andl $1, %r13d
kmovd %k1, %ebx
# ###
# tons of kshiftrd, kmovd and many other repeating instructions...
# ###
kshiftrd $30, %k0, %k1
kshiftrd $31, %k0, %k0
andl $1, %r9d
kmovd %k1, %ecx
andl $1, %r12d
andl $1, %ecx
addl %r12d, %ecx
andl $1, %eax
addl %eax, %esi
kmovd %k0, %eax
addl %esi, %ebx
movl 4(%rsp), %esi
andl $1, %eax
addl %ebx, %r15d
addl %ecx, %eax
addl %r15d, %r13d
addl %r13d, %r8d
addl %r11d, %r8d
andl $1, %esi
addl %esi, %r14d
addl %r14d, %edx
addl %edx, %ebp
addl %ebp, %edi
addl %edi, %r10d
addl %r10d, %r9d
addl %r8d, %r9d
addl %r9d, %eax
addq $16, %rsp
popq %rbx
popq %rbp
popq %rdi
popq %rsi
popq %r12
popq %r13
popq %r14
popq %r15
vzeroupper
retq
```

### Simple perf test
To measure how slow the bloated code is, I wrote the following simple test and compile it using `-Os`, `-O2` and `-O3`. Note I'm using AMD Ryzen 9 9950X3D CPU, with dual channel DDR5 memory, 2*48=96GB, 6400MT/s.

```c++
#include
#include
#include

struct f32x16 {
alignas(64) float dat[16];
};

int f(const f32x16 &x) {
int ret = 0;
for (const auto &y: x.dat)
if (y >= 0x1p10f)
++ret;
return ret;
}

struct u16x32 {
alignas(64) uint16_t dat[32];
};

int g(const u16x32 &x) {
int ret = 0;
for (const auto &y: x.dat)
if (y >= 0x100)
++ret;
return ret;
}

int main() {
constexpr unsigned len = 1e8;
auto *const p1 = new(std::align_val_t{64}, std::nothrow) f32x16[len];
unsigned seed;
std::cin >> seed;
std::mt19937_64 gen{seed};
auto *q = reinterpret_cast(p1);
while (q < reinterpret_cast(p1 + len))
*q++ = gen();
unsigned r = 0;
const auto t1 = std::chrono::steady_clock::now();
for (unsigned t = 0; t < len; ++t)
r += f(p1[t]);
const auto t2 = std::chrono::steady_clock::now();
std::cout << r << std::endl;
std::cout << std::chrono::duration_cast(t2 - t1).count() << std::endl;
r = 0;
q = reinterpret_cast(p1);
while (q < reinterpret_cast(p1 + len))
*q++ = gen();
auto *const p2 = reinterpret_cast(p1);
const auto t3 = std::chrono::steady_clock::now();
for (unsigned t = 0; t < len; ++t)
r += g(p2[t]);
const auto t4 = std::chrono::steady_clock::now();
std::cout << r << std::endl;
std::cout << std::chrono::duration_cast(t4 - t3).count() << std::endl;
return 0;
}
```

With `-Os -march=znver5`:

```
20230205

368778190
109
3187499226
111
```

There are 1e8*64B = 6.4GB data should be read per loop, which processes about 58GB data per second. Typically the memory read speed is about 60~80GB/s on my platform, so I conclude the `-Os` version hits the memory bound. It's optimal.

And '-O2 -march=znver5`:

```
20230205

368778190
1025
3187499226
110
```

Sadly, function `f` becomes much slower now.

Finally, `-O3 -march=znver5`:

```
20230205

368778190
1024
3187499226
477
```

Oh no function `g` also becomes worse here.

### My conclusion:
**LLVM may incorrectly optimize the code provided above with `-mavx512f -mavx512bw` flags, causing `-O2` and `-O3` generates both bigger and about 4~10x slower code compared with `-Os`.**

Contributor guide

Open the contributing guide

Research direction

Reproduce the C and C++ functions f and g from the issue with clang at -Os, -O2, and -O3 using -march=znver5 or -mavx512f -mavx512bw. Compare the generated assembly and benchmark results, focusing on the loop vectorizer's handling of AVX-512 masks. Done means the optimized versions avoid the reported bloated, substantially slower code while preserving the counting behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, cpp
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
50/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.