[InstCombine] Narrow signed min/max DAGs over sign-extended fixed-vector operands before truncation
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
### Summary
InstCombine does not narrow fixed-vector `llvm.smin`/`llvm.smax` expression
graphs when every leaf is a sign extension from the same narrow vector type and
the final result is truncated back to that type.
Rebuilding the same min/max topology in the narrow type would remove the sign
extensions and the final truncation. The wide and narrow forms remain distinct
after `default` on LLVM `main`.
### Reduced IR
```llvm
declare <8 x i32> @llvm.smin.v8i32(<8 x i32>, <8 x i32>)
declare <8 x i32> @llvm.smax.v8i32(<8 x i32>, <8 x i32>)
define <8 x i16> @median3(<8 x i16> %a, <8 x i16> %b,
<8 x i16> %c) {
entry:
%aw = sext <8 x i16> %a to <8 x i32>
%bw = sext <8 x i16> %b to <8 x i32>
%cw = sext <8 x i16> %c to <8 x i32>
%lo = call <8 x i32> @llvm.smin.v8i32(<8 x i32> %aw, <8 x i32> %bw)
%hi = call <8 x i32> @llvm.smax.v8i32(<8 x i32> %aw, <8 x i32> %bw)
%mid = call <8 x i32> @llvm.smin.v8i32(<8 x i32> %cw, <8 x i32> %hi)
%wide = call <8 x i32> @llvm.smax.v8i32(<8 x i32> %mid, <8 x i32> %lo)
%result = trunc nsw <8 x i32> %wide to <8 x i16>
ret <8 x i16> %result
}
```
Current InstCombine and `default` both retain the complete wide graph:
three `sext` instructions, four wide `llvm.smin`/`llvm.smax` calls, and the
final `trunc nsw`.
Compiler Explorer:
https://godbolt.org/z/v8GaGG7Tq
### Expected result
```llvm
declare <8 x i16> @llvm.smin.v8i16(<8 x i16>, <8 x i16>)
declare <8 x i16> @llvm.smax.v8i16(<8 x i16>, <8 x i16>)
define <8 x i16> @median3(<8 x i16> %a, <8 x i16> %b,
<8 x i16> %c) {
entry:
%lo = call <8 x i16> @llvm.smin.v8i16(<8 x i16> %a, <8 x i16> %b)
%hi = call <8 x i16> @llvm.smax.v8i16(<8 x i16> %a, <8 x i16> %b)
%mid = call <8 x i16> @llvm.smin.v8i16(<8 x i16> %c, <8 x i16> %hi)
%result = call <8 x i16> @llvm.smax.v8i16(<8 x i16> %mid,
<8 x i16> %lo)
ret <8 x i16> %result
}
```
The reduced current form has eight SSA definitions, while the expected form
has four.
### Why the transform is legal
For signed integer widths `N < M`, signed minimum and maximum commute with sign
extension:
```text
smin(sext(a), sext(b)) = sext(smin(a, b))
smax(sext(a), sext(b)) = sext(smax(a, b))
```
Applying these identities through the DAG makes the wide root a sign extension
of the corresponding narrow root, so the final truncation produces the same
result.
Alive2:
- Full fixed-vector form (with `--disable-undef-input`):
https://alive2.llvm.org/ce/z/ngfMYZ
- Reduced scalar form of the same per-lane relation (without that option):
https://alive2.llvm.org/ce/z/7VtWe8
### Backend benefit
The expected form removes three sign extensions and the final truncation, and
performs the four min/max operations directly on `<8 x i16>`.
On x86-64-v4, the wide form lowers to 10 instructions, including three
`vpmovsxwd` extensions, a `vpmovdw` truncation, and `vzeroupper`. The narrow
form lowers to the four 16-bit min/max instructions and `ret`, for a total of
5 instructions.
Compiler Explorer assembly and `llvm-mca` comparison:
https://compiler-explorer.com/z/Y53b34zKT
cc @ParkHanbum
Contributor guide
Assessment
This issue has not been assessed yet.