| Issue |
162376
|
| Summary |
[LLVM] Redesign Straight-Line Strength Reduction (SLSR)
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
fiigii
|
## Motivation
The Straight-Line Strength Reduction (SLSR) pass reduces arithmetic redundancy in straight-line code (often emitted by unrolling). The current implementation has several limitations:
- The representation is fixed to Base (Value), Index (Constant), and Stride (Value). It only reuses work when Base and Stride match and the Index delta is a constant. In practice, reuse opportunities also arise when Base or Stride differ by a constant or even a variable _expression_.
- Profitability relies on simple heuristics. For example, `isSimplestForm` rejects canonical GEPs whose index is 1, even though such forms are common and often profitable after unrolling.
- Compile-time is impacted by a linear scan over a list of candidates to find a basis, limiting the search scope and effectiveness.
- The pass primarily targets fully unrolled, uniform loop bodies. Unrolled loops with conditional bodies have similar reuse opportunities but are not well handled today.
Example motivating pattern:
```
for (int i = 0; i < N; i++) {
if (cond)
body;
}
```
After unrolling, later bodies may reuse computations from earlier bodies even when the earlier ones do not dominate the later ones.
## Proposed Changes
This redesign will be upstreamed as a sequence of small, reviewable PRs:
1. Extend candidate equivalence beyond Index deltas to also consider Base and Stride deltas. Deltas are computed via ScalarEvolution (`getMinusSCEV`); they may be constant or variable.
2. Replace linear basis search with an efficient dictionary keyed by tuples, enabling fast, dominance-aware lookups with broader scope.
3. Simplify GEP candidate construction by avoiding `factorArrayIndex` when `getMinusSCEV` can derive the needed delta, reducing compile-time and brittleness.
4. Introduce a clearer cost model to replace ad-hoc heuristics, allowing consistent profitability decisions across Add, Mul, and GEP forms.
5. Add Partial Strength Reduction (PSR) to handle unrolled code with conditionals by hoisting a reusable basis to the nearest common dominator and rewriting users across non-dominating paths.
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
