[SLP] Regression: dependent seeds block vectorization of later independent operations
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
# Background
Here is a reduced regression case I recently encountered (https://godbolt.org/z/ss6TdjnGf):
```llvm
%q0 = fdiv float %x0, 3.000000e+00
%q1 = fdiv float %x1, %q0
%q2 = fdiv float %x2, 5.000000e+00
%q3 = fdiv float %x3, 7.000000e+00
```
#212579 adds single-use seeds, but the new dependency check in tryToVectorizeList also applies to existing seeds
```c++
if (StandaloneSeeds && Inst &&
any_of(Inst->operand_values(),
[&](const Value *Op) { return Taken.contains(Op); }))
continue;
```
This skips an instruction when one of its operands is already among the selected seeds. Take the code below as example, the seeds are [q0, q1, q2, q3], where q1 uses q0:
After selecting q0, the check skips q1: these two divisions cannot be independent lanes of the same vector division. It then selects q2 and q3, leaving only three seeds for the first four-lane window. This reaches the existing break:
```c++
if (Idx != ActualVF)
break;
```
this exit prevents the scan from trying later starting positions:
| Start | Candidates | ActualVF | Current behavior | behavior before #212579 |
|---:|---|---:|---|---|
| 0 | [q0, q1, q2, q3] | 4 | Skip q1, then **break** | try all four; scheduling fails, then continue |
| 1 | [q1, q2, q3] | 3 | — | Skip: fails the width check |
| 2 | [q2, q3] | 2 | — | Vectorize the pair |
The difference is where the first attempt stops: previously, only the four-lane bundle was rejected; now, the incomplete window ends the scan for this VF. Since VF = MinVF = 4, there is no smaller-VF retry in the outer loop, so the later two-lane pair is missed.
# Reproduce
opt -passes=slp-vectorizer
reproducer:
```llvm
define { float, float, float } @dependent_seed(float %x0, float %x1, float %x2, float %x3) {
%q0 = fdiv float %x0, 3.000000e+00
%q1 = fdiv float %x1, %q0
%q2 = fdiv float %x2, 5.000000e+00
%q3 = fdiv float %x3, 7.000000e+00
%r0 = insertvalue { float, float, float } poison, float %q1, 0
%r1 = insertvalue { float, float, float } %r0, float %q2, 1
%r2 = insertvalue { float, float, float } %r1, float %q3, 2
ret { float, float, float } %r2
}
```
llvm23.1.0:
```llvm
define { float, float, float } @dependent_seed(float %x0, float %x1, float %x2, float %x3) {
%q0 = fdiv float %x0, 3.000000e+00
%q1 = fdiv float %x1, %q0
%1 = insertelement <2 x float> poison, float %x2, i64 0
%2 = insertelement <2 x float> %1, float %x3, i64 1
%3 = fdiv <2 x float> %2,
%r0 = insertvalue { float, float, float } poison, float %q1, 0
%4 = extractelement <2 x float> %3, i64 0
%r1 = insertvalue { float, float, float } %r0, float %4, 1
%5 = extractelement <2 x float> %3, i64 1
%r2 = insertvalue { float, float, float } %r1, float %5, 2
ret { float, float, float } %r2
}
```
main:
```llvm
define { float, float, float } @dependent_seed(float %x0, float %x1, float %x2, float %x3) {
%q0 = fdiv float %x0, 3.000000e+00
%q1 = fdiv float %x1, %q0
%q2 = fdiv float %x2, 5.000000e+00
%q3 = fdiv float %x3, 7.000000e+00
%r0 = insertvalue { float, float, float } poison, float %q1, 0
%r1 = insertvalue { float, float, float } %r0, float %q2, 1
%r2 = insertvalue { float, float, float } %r1, float %q3, 2
ret { float, float, float } %r2
}
```
Contributor guide
Research direction
Start with the SLP vectorizer's tryToVectorizeList logic and reproduce the case with opt -passes=slp-vectorizer using the provided LLVM IR. Compare the output with the expected two-lane vectorization of q2 and q3, and verify that later candidate windows are considered despite the dependent seed.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 72/100