missed optimization of some patterns of not-equal operation on x64 simd
- 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
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