llvm / llvm/llvm-project

[LV][SLP] Failed to vectorize loops that GCC vectorized

Open
#205,737 0 comments 0 reactions 0 assignees View on GitHub
llvm:SLPVectorizer missed-optimization vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

found from https://github.com/gcc-mirror/gcc/commit/c2cdc43bc60b321c07ea6d6e85d3da94cab0177c

https://godbolt.org/z/WYoejrb9W

LV case:

```c
#define N 100000
long long a_long[N], b_long[N], c_long[N];
double a_double[N], b_double[N], c_double[N];

void f_v4di (long long d, long long e)
{
for (int i = 0; i < N; i++)
{
b_long[i] += a_long[i];
if (c_long[i] == e) continue;
if (a_long[i] != d) break;
}
}

void f_v4df (double d, double e)
{
for (int i = 0; i < N; i++)
{
b_double[i] += a_double[i];
if (c_double[i] == e) continue;
if (a_double[i] != d) break;
}
}
```
gcc:
```asm
"f_v4di":
vpbroadcastq zmm3, rdi
vpbroadcastq zmm2, rsi
xor eax, eax
xor edx, edx
jmp .L11
.L2:
vpaddq zmm0, zmm0, ZMMWORD PTR "b_long"[rax]
add edx, 8
add rax, 64
vmovdqa64 ZMMWORD PTR "b_long"[rax-64], zmm0
cmp edx, 100000
je .L41
.L11:
vmovdqa64 zmm0, ZMMWORD PTR "a_long"[rax]
vmovdqa64 zmm1, ZMMWORD PTR "c_long"[rax]
vpcmpq k1, zmm0, zmm3, 4
vpcmpq k0{k1}, zmm1, zmm2, 4
kortestb k0, k0
je .L2
mov eax, edx
mov rcx, QWORD PTR "a_long"[0+rax*8]
add QWORD PTR "b_long"[0+rax*8], rcx
cmp QWORD PTR "c_long"[0+rax*8], rsi
je .L12
cmp rcx, rdi
jne .L41
.L12:
lea eax, [rdx+1]
mov rcx, QWORD PTR "a_long"[0+rax*8]
add QWORD PTR "b_long"[0+rax*8], rcx
cmp QWORD PTR "c_long"[0+rax*8], rsi
je .L13
cmp rdi, rcx
jne .L41
.L13:
lea eax, [rdx+2]
mov rcx, QWORD PTR "a_long"[0+rax*8]
add QWORD PTR "b_long"[0+rax*8], rcx
cmp QWORD PTR "c_long"[0+rax*8], rsi
je .L14
cmp rcx, rdi
jne .L41
.L14:
lea eax, [rdx+3]
mov rcx, QWORD PTR "a_long"[0+rax*8]
add QWORD PTR "b_long"[0+rax*8], rcx
cmp QWORD PTR "c_long"[0+rax*8], rsi
je .L15
cmp rdi, rcx
jne .L41
.L15:
lea eax, [rdx+4]
mov rcx, QWORD PTR "a_long"[0+rax*8]
add QWORD PTR "b_long"[0+rax*8], rcx
cmp QWORD PTR "c_long"[0+rax*8], rsi
je .L16
cmp rdi, rcx
jne .L41
.L16:
lea eax, [rdx+5]
mov rcx, QWORD PTR "a_long"[0+rax*8]
add QWORD PTR "b_long"[0+rax*8], rcx
cmp QWORD PTR "c_long"[0+rax*8], rsi
je .L17
cmp rdi, rcx
jne .L41
.L17:
lea eax, [rdx+6]
mov rcx, QWORD PTR "a_long"[0+rax*8]
add QWORD PTR "b_long"[0+rax*8], rcx
cmp QWORD PTR "c_long"[0+rax*8], rsi
je .L18
cmp rdi, rcx
jne .L41
.L18:
lea eax, [rdx+7]
mov rdx, QWORD PTR "a_long"[0+rax*8]
add QWORD PTR "b_long"[0+rax*8], rdx
.L41:
vzeroupper
ret
"f_v4df":
vmovapd xmm5, xmm0
vbroadcastsd zmm4, xmm0
vbroadcastsd zmm3, xmm1
xor eax, eax
xor edx, edx
jmp .L53
.L44:
vaddpd zmm0, zmm0, ZMMWORD PTR "b_double"[rax]
add edx, 8
add rax, 64
vmovapd ZMMWORD PTR "b_double"[rax-64], zmm0
cmp edx, 100000
je .L83
.L53:
vmovapd zmm0, ZMMWORD PTR "a_double"[rax]
vmovapd zmm2, ZMMWORD PTR "c_double"[rax]
vcmppd k1, zmm0, zmm4, 4
vcmppd k0{k1}, zmm2, zmm3, 4
kortestb k0, k0
je .L44
mov eax, edx
vmovsd xmm0, QWORD PTR "a_double"[0+rax*8]
vaddsd xmm2, xmm0, QWORD PTR "b_double"[0+rax*8]
vcomisd xmm1, QWORD PTR "c_double"[0+rax*8]
vmovsd QWORD PTR "b_double"[0+rax*8], xmm2
je .L54
vcomisd xmm0, xmm5
jne .L83
.L54:
lea eax, [rdx+1]
vmovsd xmm0, QWORD PTR "a_double"[0+rax*8]
vaddsd xmm2, xmm0, QWORD PTR "b_double"[0+rax*8]
vcomisd xmm1, QWORD PTR "c_double"[0+rax*8]
vmovsd QWORD PTR "b_double"[0+rax*8], xmm2
je .L55
vcomisd xmm5, xmm0
jne .L83
.L55:
lea eax, [rdx+2]
vmovsd xmm0, QWORD PTR "a_double"[0+rax*8]
vaddsd xmm2, xmm0, QWORD PTR "b_double"[0+rax*8]
vcomisd xmm1, QWORD PTR "c_double"[0+rax*8]
vmovsd QWORD PTR "b_double"[0+rax*8], xmm2
je .L56
vcomisd xmm5, xmm0
jne .L83
.L56:
lea eax, [rdx+3]
vmovsd xmm0, QWORD PTR "a_double"[0+rax*8]
vaddsd xmm2, xmm0, QWORD PTR "b_double"[0+rax*8]
vcomisd xmm1, QWORD PTR "c_double"[0+rax*8]
vmovsd QWORD PTR "b_double"[0+rax*8], xmm2
je .L57
vcomisd xmm5, xmm0
jne .L83
.L57:
lea eax, [rdx+4]
vmovsd xmm0, QWORD PTR "a_double"[0+rax*8]
vaddsd xmm2, xmm0, QWORD PTR "b_double"[0+rax*8]
vcomisd xmm1, QWORD PTR "c_double"[0+rax*8]
vmovsd QWORD PTR "b_double"[0+rax*8], xmm2
je .L58
vcomisd xmm5, xmm0
jne .L83
.L58:
lea eax, [rdx+5]
vmovsd xmm0, QWORD PTR "a_double"[0+rax*8]
vaddsd xmm2, xmm0, QWORD PTR "b_double"[0+rax*8]
vcomisd xmm1, QWORD PTR "c_double"[0+rax*8]
vmovsd QWORD PTR "b_double"[0+rax*8], xmm2
je .L59
vcomisd xmm5, xmm0
jne .L83
.L59:
lea eax, [rdx+6]
vmovsd xmm0, QWORD PTR "a_double"[0+rax*8]
vaddsd xmm2, xmm0, QWORD PTR "b_double"[0+rax*8]
vcomisd xmm1, QWORD PTR "c_double"[0+rax*8]
vmovsd QWORD PTR "b_double"[0+rax*8], xmm2
je .L60
vcomisd xmm5, xmm0
jne .L83
.L60:
lea eax, [rdx+7]
vmovsd xmm0, QWORD PTR "b_double"[0+rax*8]
vaddsd xmm0, xmm0, QWORD PTR "a_double"[0+rax*8]
vmovsd QWORD PTR "b_double"[0+rax*8], xmm0
.L83:
vzeroupper
ret
```
clang:
```asm
f_v4di:
lea rcx, [rip + a_long]
lea rdx, [rip + b_long]
lea r8, [rip + c_long]
xor eax, eax
.LBB0_1:
mov r9, qword ptr [rax + rcx]
add qword ptr [rax + rdx], r9
cmp qword ptr [rax + r8], rsi
setne r10b
cmp r9, rdi
setne r9b
test r10b, r9b
jne .LBB0_3
cmp rax, 799992
lea rax, [rax + 8]
jne .LBB0_1
.LBB0_3:
ret

f_v4df:
lea rcx, [rip + a_double]
lea rdx, [rip + b_double]
lea rsi, [rip + c_double]
xor eax, eax
.LBB1_1:
vucomisd xmm1, qword ptr [rax + rsi]
vmovsd xmm2, qword ptr [rax + rcx]
vaddsd xmm3, xmm2, qword ptr [rax + rdx]
setne dil
vucomisd xmm0, xmm2
vmovsd qword ptr [rax + rdx], xmm3
setne r8b
test dil, r8b
jne .LBB1_3
cmp rax, 799992
lea rax, [rax + 8]
jne .LBB1_1
.LBB1_3:
ret
```
SLP case:
```c
long long a_long[5], b_long[5], c_long[5];
double a_double[5], b_double[5], c_double[5];

void f_v4di (long long d, long long e)
{
for (int i = 0; i < 5; i++)
{
b_long[i] += a_long[i];
if (c_long[i] == e) continue;
if (a_long[i] != d) break;
}
}

void f_v4df (double d, double e)
{
for (int i = 0; i < 5; i++)
{
b_double[i] += a_double[i];
if (c_double[i] == e) continue;
if (a_double[i] != d) break;
}
}
```
gcc:
```asm
"f_v4di":
vmovdqa ymm2, YMMWORD PTR "c_long"[rip]
vmovdqa ymm0, YMMWORD PTR "a_long"[rip]
vpbroadcastq ymm3, rsi
vpbroadcastq ymm1, rdi
vpcmpq k1, ymm2, ymm3, 4
vpcmpq k0{k1}, ymm1, ymm0, 4
kortestb k0, k0
jne .L2
vpaddq ymm0, ymm0, YMMWORD PTR "b_long"[rip]
mov rax, QWORD PTR "a_long"[rip+32]
add QWORD PTR "b_long"[rip+32], rax
vmovdqa YMMWORD PTR "b_long"[rip], ymm0
.L19:
vzeroupper
ret
.L2:
mov rax, QWORD PTR "a_long"[rip]
add QWORD PTR "b_long"[rip], rax
cmp QWORD PTR "c_long"[rip], rsi
je .L8
cmp rdi, rax
jne .L19
.L8:
mov rax, QWORD PTR "a_long"[rip+8]
add QWORD PTR "b_long"[rip+8], rax
cmp QWORD PTR "c_long"[rip+8], rsi
je .L6
cmp rdi, rax
jne .L19
.L6:
mov rax, QWORD PTR "a_long"[rip+16]
add QWORD PTR "b_long"[rip+16], rax
cmp QWORD PTR "c_long"[rip+16], rsi
je .L9
cmp rdi, rax
jne .L19
.L9:
mov rax, QWORD PTR "a_long"[rip+24]
add QWORD PTR "b_long"[rip+24], rax
vzeroupper
ret
"f_v4df":
vmovapd ymm4, YMMWORD PTR "c_double"[rip]
vmovapd xmm2, xmm0
vmovapd ymm0, YMMWORD PTR "a_double"[rip]
vbroadcastsd ymm5, xmm1
vbroadcastsd ymm3, xmm2
vcmppd k1, ymm4, ymm5, 4
vcmppd k0{k1}, ymm3, ymm0, 4
kortestb k0, k0
jne .L22
vaddpd ymm0, ymm0, YMMWORD PTR "b_double"[rip]
vmovapd YMMWORD PTR "b_double"[rip], ymm0
vmovsd xmm0, QWORD PTR "b_double"[rip+32]
vaddsd xmm0, xmm0, QWORD PTR "a_double"[rip+32]
vmovsd QWORD PTR "b_double"[rip+32], xmm0
.L39:
vzeroupper
ret
.L22:
vmovsd xmm0, QWORD PTR "a_double"[rip]
vaddsd xmm3, xmm0, QWORD PTR "b_double"[rip]
vcomisd xmm1, QWORD PTR "c_double"[rip]
vmovsd QWORD PTR "b_double"[rip], xmm3
je .L28
vcomisd xmm2, xmm0
jne .L39
.L28:
vmovsd xmm0, QWORD PTR "a_double"[rip+8]
vaddsd xmm3, xmm0, QWORD PTR "b_double"[rip+8]
vcomisd xmm1, QWORD PTR "c_double"[rip+8]
vmovsd QWORD PTR "b_double"[rip+8], xmm3
je .L26
vcomisd xmm2, xmm0
jne .L39
.L26:
vmovsd xmm0, QWORD PTR "a_double"[rip+16]
vaddsd xmm3, xmm0, QWORD PTR "b_double"[rip+16]
vcomisd xmm1, QWORD PTR "c_double"[rip+16]
vmovsd QWORD PTR "b_double"[rip+16], xmm3
je .L29
vcomisd xmm2, xmm0
jne .L39
.L29:
vmovsd xmm0, QWORD PTR "b_double"[rip+24]
vaddsd xmm0, xmm0, QWORD PTR "a_double"[rip+24]
vmovsd QWORD PTR "b_double"[rip+24], xmm0
vzeroupper
ret
```
clang:
```asm
f_v4di:
mov rax, qword ptr [rip + a_long]
add qword ptr [rip + b_long], rax
cmp qword ptr [rip + c_long], rsi
je .LBB0_2
cmp rax, rdi
je .LBB0_2
.LBB0_9:
ret
.LBB0_2:
mov rax, qword ptr [rip + a_long+8]
add qword ptr [rip + b_long+8], rax
cmp qword ptr [rip + c_long+8], rsi
je .LBB0_4
cmp rax, rdi
jne .LBB0_9
.LBB0_4:
mov rax, qword ptr [rip + a_long+16]
add qword ptr [rip + b_long+16], rax
cmp qword ptr [rip + c_long+16], rsi
je .LBB0_6
cmp rax, rdi
jne .LBB0_9
.LBB0_6:
mov rax, qword ptr [rip + a_long+24]
add qword ptr [rip + b_long+24], rax
cmp qword ptr [rip + c_long+24], rsi
je .LBB0_8
cmp rax, rdi
jne .LBB0_9
.LBB0_8:
mov rax, qword ptr [rip + a_long+32]
add qword ptr [rip + b_long+32], rax
ret

f_v4df:
vmovsd xmm2, qword ptr [rip + a_double]
vucomisd xmm1, qword ptr [rip + c_double]
vaddsd xmm3, xmm2, qword ptr [rip + b_double]
vmovsd qword ptr [rip + b_double], xmm3
je .LBB1_2
vucomisd xmm2, xmm0
je .LBB1_2
.LBB1_9:
ret
.LBB1_2:
vmovsd xmm2, qword ptr [rip + a_double+8]
vucomisd xmm1, qword ptr [rip + c_double+8]
vaddsd xmm3, xmm2, qword ptr [rip + b_double+8]
vmovsd qword ptr [rip + b_double+8], xmm3
je .LBB1_4
vucomisd xmm2, xmm0
jne .LBB1_9
.LBB1_4:
vmovsd xmm2, qword ptr [rip + a_double+16]
vucomisd xmm1, qword ptr [rip + c_double+16]
vaddsd xmm3, xmm2, qword ptr [rip + b_double+16]
vmovsd qword ptr [rip + b_double+16], xmm3
je .LBB1_6
vucomisd xmm2, xmm0
jne .LBB1_9
.LBB1_6:
vmovsd xmm2, qword ptr [rip + a_double+24]
vucomisd xmm1, qword ptr [rip + c_double+24]
vaddsd xmm3, xmm2, qword ptr [rip + b_double+24]
vmovsd qword ptr [rip + b_double+24], xmm3
je .LBB1_8
vucomisd xmm2, xmm0
jne .LBB1_9
.LBB1_8:
vmovsd xmm0, qword ptr [rip + b_double+32]
vaddsd xmm0, xmm0, qword ptr [rip + a_double+32]
vmovsd qword ptr [rip + b_double+32], xmm0
ret
```

Contributor guide

Open the contributing guide

Research direction

Reproduce the LV and SLP examples from the linked Godbolt case and compare the output with the referenced GCC commit. Trace the relevant LLVM vectorization implementation to determine why these loops are missed, then add regression coverage showing that both cases are vectorized.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers
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.