llvm / llvm/llvm-project

[X86] improve llvm.experimental.vector.histogram codegen on avx512

Open
#216,070 1 comment 0 reactions 0 assignees View on GitHub
backend:X86 missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

see https://github.com/llvm/llvm-project/pull/158292#issuecomment-5281939175

> Hmm. Perhaps the default costs need to be increased to avoid it? (It's possible to use vpconflict for this, but the X86 backend isn't my area of expertise)

```c
void simple_histogram(int *restrict buckets, unsigned *indices, int N, int inc) {
for (int i = 0; i < N; ++i)
buckets[indices[i]] += inc;
}
```
-O3 -march=znver5 -mllvm -enable-histogram-loop-vectorization
```asm
simple_histogram:
testl %edx, %edx
jle .LBB0_13
movl %edx, %eax
cmpl $8, %edx
jae .LBB0_3
xorl %edx, %edx
jmp .LBB0_12
.LBB0_3:
vpbroadcastq %rdi, %zmm0
cmpl $16, %edx
jae .LBB0_5
xorl %edx, %edx
.LBB0_9:
movq %rdx, %r8
movl %eax, %edx
andl $2147483640, %edx
.LBB0_10:
vpmovzxdq (%rsi,%r8,4), %zmm1
addq $8, %r8
vpsllq $2, %zmm1, %zmm1
vpaddq %zmm1, %zmm0, %zmm1
vmovq %xmm1, %r9
vextracti128 $1, %ymm1, %xmm2
vpextrq $1, %xmm1, %r10
addl %ecx, (%r9)
addl %ecx, (%r10)
vmovq %xmm2, %r11
vpextrq $1, %xmm2, %r10
vextracti32x4 $2, %zmm1, %xmm2
vextracti32x4 $3, %zmm1, %xmm1
addl %ecx, (%r11)
addl %ecx, (%r10)
vmovq %xmm2, %r11
vpextrq $1, %xmm2, %r10
addl %ecx, (%r11)
addl %ecx, (%r10)
vmovq %xmm1, %r11
vpextrq $1, %xmm1, %r10
addl %ecx, (%r11)
addl %ecx, (%r10)
cmpq %r8, %rdx
jne .LBB0_10
cmpl %eax, %edx
jne .LBB0_12
jmp .LBB0_13
.LBB0_5:
movl $6916, %r8d
movl %eax, %edx
andl $2147483632, %edx
xorl %r9d, %r9d
bextrl %r8d, %eax, %r8d
shlq $6, %r8
.LBB0_6:
vpmovzxdq (%rsi,%r9), %zmm1
vpmovzxdq 32(%rsi,%r9), %zmm2
addq $64, %r9
vpsllq $2, %zmm1, %zmm1
vpsllq $2, %zmm2, %zmm2
vpaddq %zmm1, %zmm0, %zmm1
vpaddq %zmm2, %zmm0, %zmm2
vmovq %xmm1, %r10
vextracti128 $1, %ymm1, %xmm3
addl %ecx, (%r10)
vpextrq $1, %xmm1, %r10
addl %ecx, (%r10)
vmovq %xmm3, %r10
addl %ecx, (%r10)
vpextrq $1, %xmm3, %r10
vextracti32x4 $2, %zmm1, %xmm3
vextracti32x4 $3, %zmm1, %xmm1
addl %ecx, (%r10)
vmovq %xmm3, %r10
addl %ecx, (%r10)
vpextrq $1, %xmm3, %r10
addl %ecx, (%r10)
vmovq %xmm1, %r10
addl %ecx, (%r10)
vpextrq $1, %xmm1, %r10
vextracti128 $1, %ymm2, %xmm1
addl %ecx, (%r10)
vmovq %xmm2, %r10
addl %ecx, (%r10)
vpextrq $1, %xmm2, %r10
addl %ecx, (%r10)
vmovq %xmm1, %r10
addl %ecx, (%r10)
vpextrq $1, %xmm1, %r10
vextracti32x4 $2, %zmm2, %xmm1
addl %ecx, (%r10)
vmovq %xmm1, %r10
addl %ecx, (%r10)
vpextrq $1, %xmm1, %r10
vextracti32x4 $3, %zmm2, %xmm1
addl %ecx, (%r10)
vmovq %xmm1, %r10
vpextrq $1, %xmm1, %r11
addl %ecx, (%r10)
addl %ecx, (%r11)
cmpq %r9, %r8
jne .LBB0_6
cmpl %eax, %edx
je .LBB0_13
testb $8, %al
jne .LBB0_9
.LBB0_12:
movl (%rsi,%rdx,4), %r8d
incq %rdx
addl %ecx, (%rdi,%r8,4)
cmpq %rdx, %rax
jne .LBB0_12
.LBB0_13:
vzeroupper
retq
```
https://godbolt.org/z/jesqYadr6

Contributor guide

Open the contributing guide

Research direction

Start with the linked LLVM pull-request discussion and reproduce the C example using -O3 -march=znver5 -mllvm -enable-histogram-loop-vectorization, then inspect the output on Compiler Explorer. No source file or test is named; done means demonstrating better AVX512 histogram codegen than the assembly shown, with a focused LLVM regression test if the relevant location can be identified.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.