llvm / llvm/llvm-project

[x86-64] Intermediate llvm.clmul.i32 results get needlessly truncated

Open
#202,215 3 comments 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

[Godbolt](https://godbolt.org/z/4hrKddvah)

Given this LLVM IR
```llvm
define noundef i32 @mod_inv(i32 noundef %m) {
start:
%_2 = and i32 %m, 13
%_4 = and i32 %m, 2
%_3 = sub nsw i32 0, %_4
%0 = xor i32 %_2, %_3
%_8 = tail call i32 @llvm.clmul.i32(i32 %0, i32 %0)
%1 = tail call i32 @llvm.clmul.i32(i32 %_8, i32 %m)
%_8.1 = tail call i32 @llvm.clmul.i32(i32 %1, i32 %1)
%2 = tail call i32 @llvm.clmul.i32(i32 %_8.1, i32 %m)
%_8.2 = tail call i32 @llvm.clmul.i32(i32 %2, i32 %2)
%3 = tail call i32 @llvm.clmul.i32(i32 %_8.2, i32 %m)
ret i32 %3
}
```
the x86-64 backend currently generates this code:
```asm
mod_inv: # @mod_inv
mov eax, edi
and eax, 13
movd xmm0, edi
and edi, 2
neg edi
xor edi, eax
movd xmm1, edi
pclmulqdq xmm1, xmm1, 0
movq rax, xmm1
movd xmm1, eax
pclmulqdq xmm1, xmm0, 0
movq rax, xmm1
movd xmm1, eax
pclmulqdq xmm1, xmm1, 0
movq rax, xmm1
movd xmm1, eax
pclmulqdq xmm1, xmm0, 0
movq rax, xmm1
movd xmm1, eax
pclmulqdq xmm1, xmm1, 0
movq rax, xmm1
movd xmm1, eax
pclmulqdq xmm1, xmm0, 0
movq rax, xmm1
ret
```
However, the intermediate results do not need to be truncated, as any garbage bits can only influence the bits at the same or higher position (as it is with other arithmetic operations like addition or regular multiplication too).
I would expect assembly like this to be generated:
```asm
mod_inv: # @mod_inv
mov eax, edi
and eax, 13
movd xmm0, edi
and edi, 2
neg edi
xor edi, eax
movd xmm1, edi
pclmulqdq xmm1, xmm1, 0
pclmulqdq xmm1, xmm0, 0
pclmulqdq xmm1, xmm1, 0
pclmulqdq xmm1, xmm0, 0
pclmulqdq xmm1, xmm1, 0
pclmulqdq xmm1, xmm0, 0
movq rax, xmm1
ret
```

Contributor guide

Open the contributing guide

Research direction

Reproduce the LLVM IR example through the linked Godbolt case and compare the x86-64 assembly with the two outputs shown. Trace the x86-64 backend's handling of intermediate llvm.clmul.i32 values; done means eliminating unnecessary truncation while preserving the returned i32 result and validating the generated sequence with an appropriate regression test.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
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.