llvm / llvm/llvm-project

[SLP] Regression: dependent seeds block vectorization of later independent operations

Open
#224,286 1 comment 0 reactions 1 assignee Assigned to @purnima-nlp View on GitHub
llvm:SLPVectorizer missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.