llvm / llvm/llvm-project

[InstCombine][VectorCombine][DAG] missed "X div/rem/fdiv (select C, C1, C2) --> select C, (X div/rem/fdiv C1), (X div/rem/fdiv C2)"

Open
#214,466 6 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine llvm:SelectionDAG llvm:vectorcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

https://godbolt.org/z/W6Kajbcsr

originally found from https://github.com/gcc-mirror/gcc/commit/298071eb7e88b01adc6a88f9eba797edaedec170

```
expand: Split divisions with near-power-of-two divisors [PR middle-end/125708]
When range info proves that a TRUNC_DIV_EXPR divisor is either N or N
+ 1, and one value is a positive power of two, expand the operation as
two constant divisions selected by a conditional move.

Only do this for speed, when conditional moves are available. Cost
the split sequence against a plain DIV/UDIV and keep the original
expansion unless the split is cheaper.
```

```c
unsigned
foo3 (unsigned a, _Bool b)
{
return a / (4 + b);
}
```

gcc:
```asm
"foo3":
mov eax, edi
shr eax, 2
mov edx, 3435973837
mov edi, edi
imul rdi, rdx
shr rdi, 34
test sil, sil
cmovne eax, edi
ret
```
clang:
```asm
foo3:
mov eax, edi
or esi, 4
xor edx, edx
div esi
ret
```
gcc avoided the costly division.

Update:

The pattern can be generalized to `X div/rem/fdiv (select C, C1, C2) --> select C, (X div/rem/fdiv C1), (X div/rem/fdiv C2)`, since this exposes significantly lower cost division-by-constant patterns for autovectorization, even when the pairs are not pow2+nonpow2, it is highly meaningful.

Contributor guide

Open the contributing guide

Research direction

Start with the Godbolt reproducer and the InstCombine, VectorCombine, and DAG entry points named in the title. Compare the current clang output with the shown gcc output, then trace how the select and division, remainder, or floating-point division operands are represented. Done means the stated transformation is covered while preserving semantics and is backed by a regression test.

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
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.