<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/162376>162376</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [LLVM] Redesign Straight-Line Strength Reduction (SLSR)
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          fiigii
      </td>
    </tr>
</table>

<pre>
    
## 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.

</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJyUVl1v4zoO_TXKCxHDsZukechD-rUYYLoo2t15pyU65o4s-Upy0vz7BWWnH_fuPlygwGT0QVKH5xwaY-SjI9qr9Z1aPyxwTJ0P-5b5yLxovLnsVXlQVa2qGp594hMm9k6Vh391BG8pIB-7tPzJLv-P3DF18Epm1HIMVHX79vPtVVU7GDBGCLJDETBw6npKrPOSM-j0BdhBvEa0ElF7QxLDt4kcUM8pkYHmAqML3lp2R1XtCpBS9BgCuQTcD5Z6cinXCR1GiHSigBYs9zwtR1UfVHlY5puBhkDx4wZHaPmdDCQPdxhz_l9oR1LVTlX38MMZepfFe-9iQpfmdXRGEGDz7UYBPxJ4Zy8QaIwU4ezDbzh35KbgX271mHSXF1JHcxpDNqGUhKDndAX8cDAE1Ik1SeIcGPww-JBGx4kFXxu9gBzpSy4frqkMty0FAfIzrmzTiRwgnDAwNpaA3gWayN4VGa6X4FtO2LDlJC-ykss7iBl16GgMHBPrWMCThHtHWZci1abk-JaPxfTkQ682JQT6D-kUQaPzjjVa-MfjS4Rz5yMBZwA4wkru58pS58djB3HUHbQ-9MIjIUnfe5eBm3gyzFVaAmwThU-2TK-49_3AlpaJe5IE3A-oZ2IhCPEwQNTowJ8o5KWYwLdSp2GDiaKQo2VnAKHByFFKzPRid8zti4RBdxC1H6YmU9uSTnwiRzEWH-TLqhgC9xjYXiBhOFKK0I7WXllORqKPjuXJYL0foPGGKRbw7_lAXo1w5tRJPw0Lk9HO56DDE0mP2GL4n3RpxpShdD7BmayFDp2xWQMGL1KtKg-PUzehn13AHWHAlCi4SU1qU85_5aH1QVTAIkhQ9QOUqr7LP-_hn_mnqu7y3w7U9k6VBwBu5YqUL4oqD1L9RdWyqbYPf0pw-N7YjD_K0vzkHmfFCT2GcZY9tMH3QBgsfx7N1MoqkcZdN72jCMZnSIzv2WGifGBKI9szLrM5vgQ_-EgG7jt0R4rZIjlbHonHwpmthYZgHGIKhD0ZQBF2pD9GcpqEYbFHaydRn5jOmcMvr7NdrQp4fE_kzCcRgf4Y-YQ232_o4p356hyZp9kLROVsKPzFdaZzBTxM52dBDaPo4cQIbxothseTt-PV0dWmPFJ6ZjfGt_vHX9KQaidNTR1dMvINfbOVq58IYFUBrzRY1HRVWhbQVTCZwuhELqxZDN1wHiUYLvCbLpNK0yg-kn3BYSMEgBZjkoWpV07TEs_yGOv97_GqjSZ4FBCyLKWauoBsStxexHu-AJvrD_MYE2M4eTaSSG3KFnXy4RACXjLY4mWZQH9FRiKCocCniT2OyJCZUJ_6bEYtYfVXU5L-NIFTsh92cSO-n4KX-SmubQkDBdA-Jui9ISutDjOyaJad11_8OA8oa_15SuUixyTgDt8M3ZDmmHWCOvgY4WCy9zyP9jrhBKRsvVLTupAT8IIhMdr_M_9fpvGf_GwqH642Tfc_e1YUsDsvZbsjYBZxlsFEk-RnGDFQTFfvnwXqQ64x0DlMTjxGCh-Pcd4t54Ozd3X5FQuzr82u3uGC9qvtene7rcvbetHtqx2tN-sVbXVZ39S0Qmy2VVvV663B9QrLBe-rslqvynJbrerbsi62pbnZ7da7m9v69na9q9VNST2yLaw99YUPxwXHONJ-tanq7WZhsSEb86dXVTk6Q95VVSVfYmEvl5bNeIzqppQRFD_DJE42f7P9_PnrWa0fBPLJZf7GJ9liDHbfpTRkf6meVPV05NSNTaF9r6onyTb_sxyCl1mtqqdcY1TV0_yI0776bwAAAP__Pk-OXA">