[VectorCombine][SLP] Recognize zero-tests of vector reductions
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
There appear to be related missed-optimization cases around zero-tests of
vector reduction results.
For example:
```llvm
%r = call i8 @llvm.vector.reduce.or.v16i8(<16 x i8> %x)
%c = icmp ne i8 %r, 0
and:
%r = call i8 @llvm.vector.reduce.umax.v16i8(<16 x i8> %x)
%c = icmp ne i8 %r, 0
```
Both patterns are scalar comparisons of a vector reduction result, but they are
really vector zero/non-zero tests.
For integer vectors:
```llvm
icmp ne (vector.reduce.or X), 0
<=> any lane of X is non-zero
icmp eq (vector.reduce.or X), 0
<=> all lanes of X are zero
```
For unsigned max reductions:
```llvm
icmp ne (vector.reduce.umax X), 0
<=> any lane of X is non-zero
icmp eq (vector.reduce.umax X), 0
<=> all lanes of X are zero
```
This matters because keeping the operation as a scalar reduction followed by a
scalar compare can hide the vector zero-test idiom from the middle-end and from
targets.
For example:
X86 may miss efficient ptest / vptest lowering.
WebAssembly may need the operation to be recognized as a vector comparison /
any_true-style idiom.
SLP may estimate or generate a scalar reduction form even though a vector
comparison plus boolean reduction would better represent the operation.
A previous target-specific approach attempted to model this in WebAssembly TTI
by adding a reduction use kind for non-zero tests. However, this seems more like
a general middle-end canonicalization / SLP recognition issue than a
target-specific cost-model issue.
A possible canonical form would be:
```llvm
icmp ne (vector.reduce.or X), 0
->
%cmp = icmp ne X, zeroinitializer
%r = call i1 @llvm.vector.reduce.or.vNi1(%cmp)
and:
icmp eq (vector.reduce.or X), 0
->
%cmp = icmp eq X, zeroinitializer
%r = call i1 @llvm.vector.reduce.and.vNi1(%cmp)
```
The same idea should apply to vector.reduce.umax when comparing the result
against zero.
This could be handled in two places:
VectorCombine, for already-formed reduction zero-tests.
SLPVectorizer, so SLP can estimate/generate the vector zero-test form
directly instead of modeling it as a scalar reduction plus scalar compare.
The initial scope could be limited to integer vectors, zero constants, and
eq/ne comparisons of vector.reduce.or and vector.reduce.umax.
Contributor guide
Research direction
Start by reading the VectorCombine and SLPVectorizer entry points for vector reduction results compared with zero, using the LLVM IR examples in the issue as the reproducer. Check how the existing scalar reduction form is represented and whether the vector zero-test form is recognized; done means the listed integer eq/ne cases are handled without regressing the intended reduction behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- wasm
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100