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

[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 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.

[jmmartinez]

Hello,
These past months I've been working on something related for handling the f(a*k), f((a+b)*k), f((a+b+c+...)*k) case when none of them are constants. main...jmmartinez:llvm-project:redistribute/base

I wish I've seen the SLSR pass before, I would worked directly inside it.

I'll start to review #162930 to help with this effort.

[fiigii]

Thanks, @jmmartinez , feel free to let me know if you have questions or more cases that you want SLSR to cover.

[fiigii]

@jmmartinez I briefly looked at your tests and comments. You seem to want something related to https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/NaryReassociate.cpp

You can try to improve NaryReassociate to cover your cases.