llvm / llvm/llvm-project

[InstCombine] Narrow signed min/max DAGs over sign-extended fixed-vector operands before truncation

Open
#214,224 0 comments 0 reactions 1 assignee Claimed by @mangsgi View on GitHub
llvm:instcombine missed-optimization
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.