llvm / llvm/llvm-project

[LLVM] Redesign Straight-Line Strength Reduction (SLSR)

Open
#162,376 3 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

## 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 contributed as a sequence of 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.

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing Straight-Line Strength Reduction pass and the ScalarEvolution APIs, especially getMinusSCEV and the current candidate and basis handling. Trace how Add, Mul, and GEP candidates are evaluated, then determine how the proposed dictionary lookup, cost model, and Partial Strength Reduction should be implemented and validated across the redesign sequence.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.