[LSR] SSA use-list order affects assembly on cost ties between non-free constant IV starts
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
## Description
When two complete LSR solutions have exactly equal cost, `SolveRecurse` keeps the first one it enumerates (it only replaces the incumbent [on strictly smaller cost](https://github.com/llvm/llvm-project/blob/5ea218a153f4d2f815b8244eab3e4b4ba5e00e6c/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp#L5491)). The enumeration order derives from walking SSA use-lists, and according to the [LangRef](https://github.com/llvm/llvm-project/blob/5ea218a153f4d2f815b8244eab3e4b4ba5e00e6c/llvm/docs/LangRef.rst#L4227), the use-list order has *"no effect on the semantics of the IR"*, but on these ties it decides which solution LSR picks, which affects the generated assembly.
[PR #190587](https://github.com/llvm/llvm-project/pull/190587) fixed the more common scenario where a constant IV start is `TCC_Free` (e.g. the RISC-V zero register, where a zero-start candidate now strictly beats its non-zero-start mirror, i.e. no ties).
However, when the competing candidates' constant starts are both non-free (e.g. `{1,+,1}` vs `{2,+,1}`), all cost fields still tie and the winner is still decided by use-list order.
**Proposed fix:**
* [PR 215261](https://github.com/llvm/llvm-project/pull/215261)
* Makes `IVUsers` independent of use-list order
## Impact
Use-list-order dependence breaks reproducible builds for in-process users of LLVM.
Our compiler uses LLVM as a library targeting RISC-V, and we encountered the zero-start instance of this tie in production on LLVM 22 (our MS-ABI Windows build of LLVM reached LSR with a different in-memory use-list order than our Itanium Linux/macOS builds on byte-identical IR, deterministically emitting different bytecode on Windows).
The non-free tie is the same loop shape with the accesses shifted by one element (`get(i + 1)`/`get(i + 2)` instead of `get(i)`/`get(i + 1)`), equally reachable from ordinary source code.
## Environment
* **LLVM version**: 22.1.5 and current `main` on commit `8ea1b9d`
* **Target**: `riscv64` (bare `-mtriple=riscv64` suffices)
* **Reproducer uses the official LLVM release** (from https://github.com/llvm/llvm-project/releases/tag/llvmorg-22.1.5):
* Linux: [LLVM-22.1.5-Linux-ARM64.tar.xz](https://github.com/llvm/llvm-project/releases/download/llvmorg-22.1.5/LLVM-22.1.5-Linux-ARM64.tar.xz)
* (Also reproduced with a custom build of `release/22.x` @ `ca069859` with the aforementioned [PR #190587](https://github.com/llvm/llvm-project/pull/190587) cherry-picked (assertions enabled, for `-debug-only`))
## Reproducer
This can be reproduced with a single llc binary by using the `uselistorder` directive to recreate an in-memory use-list order:
**A)**
`lsr-tie.ll`:
* A loop that calls `get(i + 1)` and `get(i + 2)`.
* The three uses of `i + 1` (two calls plus the exit compare) become one `LSRUse`, the single `i + 2` call the other, and LSR's cross-use constant-offset reuse gives each use a formula based on the other's register plus a compensating immediate:
```ll
declare i64 @get(i32) #0
define i64 @f(i32 %n) #0 {
entry:
br label %for_cond
for_cond:
%iv32 = phi i32 [ %iv32.next, %latch ], [ 0, %entry ]
%i.plus.1 = add i32 %iv32, 1
%exit.cmp = icmp ult i32 %i.plus.1, %n
br i1 %exit.cmp, label %body, label %exit
exit:
ret i64 0
body:
%ra = tail call i64 @get(i32 %i.plus.1)
%i.plus.2 = add i32 %iv32, 2
%rb = tail call i64 @get(i32 %i.plus.2)
%cmp = icmp ult i64 %ra, %rb
br i1 %cmp, label %swap, label %latch
swap:
%rc = tail call i64 @get(i32 %i.plus.1)
br label %latch
latch:
%iv32.next = add nuw nsw i32 %iv32, 1
br label %for_cond
}
attributes #0 = { nounwind }
```
**B)**
`lsr-tie-flipped.ll`:
* Identical to (A) except for one added `uselistorder` line before the closing brace, modifying the order of `%iv32`'s three uses:
```diff
...
latch:
%iv32.next = add nuw nsw i32 %iv32, 1
br label %for_cond
+ uselistorder i32 %iv32, { 0, 2, 1 }
}
...
```
**Compile:**
```sh
llc -O3 -mtriple=riscv64 lsr-tie.ll -o lsr-tie.s
llc -O3 -mtriple=riscv64 lsr-tie-flipped.ll -o lsr-tie-flipped.s
diff lsr-tie.s lsr-tie-flipped.s
```
### Expected
Identical assembly (modulo the `.file` directive), since use-list order carries no semantics.
### Actual
```diff
- li s0, 2
+ li s0, 1
...
- addiw s0, s0, 1
+ mv s0, s1
...
- addiw s1, s0, -1
- bgeu s1, s3, .LBB0_5
+ bgeu s0, s3, .LBB0_5
...
- mv a0, s0
+ addiw s1, s0, 1
+ mv a0, s1
...
```
## Analysis
`-debug-only=loop-reduce` (using another assertions-enabled build) shows both compilations generate identical formula sets (the flipped one lists the same two uses in the opposite order):
```
LSR is examining the following uses:
LSR Use: Kind=Basic, Offsets={0}, all-fixups-unconditional, widest fixup type: i32
reg({2,+,1}<%for_cond>)
reg({0,+,1}<%for_cond>) + imm(2)
reg({1,+,1}<%for_cond>) + imm(1)
LSR Use: Kind=Basic, Offsets={0,0,0}, widest fixup type: i32
reg({1,+,1}<%for_cond>)
reg({0,+,1}<%for_cond>) + imm(1)
reg({2,+,1}<%for_cond>) + imm(-1)
```
Both compilations report the identical chosen cost, only the winner differs:
```
# lsr-tie.ll
The chosen solution requires 2 instructions 1 reg, with addrec cost 1, plus 1 base add, plus 1 setup cost:
LSR Use: Kind=Basic, Offsets={0}, all-fixups-unconditional, widest fixup type: i32
reg({2,+,1}<%for_cond>)
LSR Use: Kind=Basic, Offsets={0,0,0}, widest fixup type: i32
reg({2,+,1}<%for_cond>) + imm(-1)
# lsr-tie-flipped.ll
The chosen solution requires 2 instructions 1 reg, with addrec cost 1, plus 1 base add, plus 1 setup cost:
LSR Use: Kind=Basic, Offsets={0,0,0}, widest fixup type: i32
reg({1,+,1}<%for_cond>)
LSR Use: Kind=Basic, Offsets={0}, all-fixups-unconditional, widest fixup type: i32
reg({1,+,1}<%for_cond>) + imm(1)
```
`getSetupCost()` rates the constant starts 1 and 2 equally, so the two mirror solutions tie, and `SolveRecurse`'s strict `isLess()` keeps whichever the use-list walk enumerated first.
Contributor guide
Research direction
Start with llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp, especially SolveRecurse and IVUsers, then reproduce the issue with lsr-tie.ll and lsr-tie-flipped.ll using llc -O3 -mtriple=riscv64. Compare the generated assembly and the loop-reduce debug output; done means both use-list orders produce identical assembly apart from the .file directive.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 25/100