llvm / llvm/llvm-project

missed optimization of some patterns of not-equal operation on x64 simd

Open
#207,362 1 comment 0 reactions 0 assignees View on GitHub
missed-optimization vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Consider the following code compiled with `clang++-trunk -O3 -march=x86-64-v4 -std=c++2c`: https://godbolt.org/z/Ez1zaPP6Y

They are variants of the same semantics: check whether two vectors are the same.

```c++
#include

using T = std::uint64_t;
constexpr int num = 8;
using v [[gnu::vector_size(num * sizeof(T))]] = T;
static_assert(sizeof(v) / sizeof(T) == num);

bool neq1(v x, v y) {
# pragma unroll num
for (int i = 0; i < num; ++i) {
if (x[i] != y[i]) return true;
}
return false;
}

bool neq1_2(v x, v y) {
v z = x != y;
# pragma unroll num
for (int i = 0; i < num; ++i) {
if (z[i]) return true;
}
return false;
}

bool neq2(v x, v y) {
T result = 0;
# pragma unroll num
for (int i = 0; i < num; ++i) {
result = result || (x[i] != y[i]);
}
return result;
}

bool neq2_2(v x, v y) {
T result = 0;
v z = x != y;
# pragma unroll num
for (int i = 0; i < num; ++i) {
result = result || z[i];
}
return result;
}

bool neq3(v x, v y) {
T result = 0;
# pragma unroll num
for (int i = 0; i < num; ++i) {
result = result | (x[i] != y[i]);
}
return result;
}

bool neq3_2(v x, v y) {
T result = 0;
v z = x != y;
# pragma unroll num
for (int i = 0; i < num; ++i) {
result = result | z[i];
}
return result;
}
```

However, they are not all properly optimized. In particular, `neq1`, `neq1_2` and `neq2` generate suboptimal assembly.

```asm
neq1(unsigned long vector[8], unsigned long vector[8]):
vpextrq $1, %xmm0, %rax
vpextrq $1, %xmm1, %rcx
xorq %rax, %rcx
vextracti128 $1, %ymm0, %xmm2
vmovq %xmm2, %rax
vextracti128 $1, %ymm1, %xmm3
vmovq %xmm3, %rdx
xorq %rax, %rdx
orq %rcx, %rdx
vpextrq $1, %xmm2, %rax
vpextrq $1, %xmm3, %rcx
xorq %rax, %rcx
orq %rdx, %rcx
vextracti32x4 $2, %zmm0, %xmm2
vmovq %xmm2, %rax
vextracti32x4 $2, %zmm1, %xmm3
vmovq %xmm3, %rdx
xorq %rax, %rdx
vpextrq $1, %xmm2, %rax
vpextrq $1, %xmm3, %rsi
xorq %rax, %rsi
orq %rdx, %rsi
orq %rcx, %rsi
vextracti32x4 $3, %zmm0, %xmm2
vmovq %xmm2, %rax
vextracti32x4 $3, %zmm1, %xmm3
vmovq %xmm3, %rdi
xorq %rax, %rdi
orq %rsi, %rdi
vpextrq $1, %xmm2, %rax
vpextrq $1, %xmm3, %rsi
xorq %rax, %rsi
vmovq %xmm0, %rcx
vmovq %xmm1, %rdx
orq %rdi, %rsi
sete %sil
movb $1, %dil
xorb $1, %sil
.LBB0_1:
movl %edi, %eax
cmpq %rdx, %rcx
sete %dil
andb %al, %dil
cmpb $1, %dil
jne .LBB0_3
xorl %edi, %edi
testb %sil, %sil
je .LBB0_1
.LBB0_3:
andb $1, %al
vzeroupper
retq

neq1_2(unsigned long vector[8], unsigned long vector[8]):
vpcmpneqq %zmm1, %zmm0, %k0
vpmovm2q %k0, %zmm0
vpextrq $1, %xmm0, %rax
vextracti128 $1, %ymm0, %xmm1
vmovq %xmm1, %rcx
vpextrq $1, %xmm1, %rdx
orq %rax, %rcx
orq %rcx, %rdx
vextracti32x4 $2, %zmm0, %xmm1
vmovq %xmm1, %rax
vpextrq $1, %xmm1, %rcx
orq %rax, %rcx
orq %rdx, %rcx
vextracti32x4 $3, %zmm0, %xmm1
vmovq %xmm1, %rax
vpextrq $1, %xmm1, %rdx
orq %rcx, %rax
vmovq %xmm0, %rcx
orq %rax, %rdx
sete %dl
movb $1, %sil
xorb $1, %dl
.LBB1_1:
movl %esi, %eax
testq %rcx, %rcx
sete %sil
andb %al, %sil
cmpb $1, %sil
jne .LBB1_3
xorl %esi, %esi
testb %dl, %dl
je .LBB1_1
.LBB1_3:
andb $1, %al
vzeroupper
retq

.LCPI2_0:
.quad 1
neq2(unsigned long vector[8], unsigned long vector[8]):
vpcmpneqq %zmm1, %zmm0, %k0
kshiftrb $7, %k0, %k1
kshiftrb $6, %k0, %k2
kmovd %k2, %eax
kmovd %k0, %ecx
testb $15, %cl
setne %cl
vmovd %ecx, %xmm0
vpinsrb $1, %eax, %xmm0, %xmm0
vpmovzxbq %xmm0, %xmm0
vptestmq .LCPI2_0(%rip){1to2}, %xmm0, %k2
kshiftrb $4, %k0, %k0
kmovd %k1, %ecx
korw %k0, %k2, %k0
kmovd %k0, %eax
testb $3, %al
setne %al
orb %cl, %al
andb $1, %al
vzeroupper
retq

neq2_2(unsigned long vector[8], unsigned long vector[8]):
vpcmpneqd %zmm1, %zmm0, %k0
kortestw %k0, %k0
setne %al
vzeroupper
retq

neq3(unsigned long vector[8], unsigned long vector[8]):
vpcmpneqd %zmm1, %zmm0, %k0
kortestw %k0, %k0
setne %al
vzeroupper
retq

neq3_2(unsigned long vector[8], unsigned long vector[8]):
vpcmpneqd %zmm1, %zmm0, %k0
kortestw %k0, %k0
setne %al
vzeroupper
retq
```

Similar problems can happen when changing the number of vectorized items to 4 or 2, and I think they should also be handled properly.

Contributor guide

Open the contributing guide

Research direction

Reproduce the issue using the provided Godbolt example with clang++-trunk -O3 -march=x86-64-v4 -std=c++2c, then compare the generated assembly for neq1 through neq3_2. Check the same patterns with vectors of 2, 4, and 8 items; done means the affected not-equal forms receive optimization comparable to the already efficient variants.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.