llvm / llvm/llvm-project

[LSR] SSA use-list order affects assembly on cost ties between non-free constant IV starts

Open
#215,260 0 comments 0 reactions 0 assignees View on GitHub
loopoptim
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.