`loop-bound-split` computes a wrong pre-loop bound (miscompile)
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
[issue1.ll.txt](https://github.com/user-attachments/files/29630372/issue1.ll.txt)
[issue2.ll.txt](https://github.com/user-attachments/files/29630371/issue2.ll.txt)
[issue3.ll.txt](https://github.com/user-attachments/files/29630370/issue3.ll.txt)
The `loop-bound-split` pass splits a counted loop into a pre-loop (where the
split condition is folded to `true`) and a post-loop. The boundary value
`new.bound` it emits is off by one induction step relative to where the split
condition actually flips, so the pre-loop runs the folded body over the wrong
iteration range and the program result changes.
Three self-contained reproducers below trigger this via three different code
paths. Each counts how many iterations satisfy the split condition, so the
expected value is obvious.
Run each with:
```bash
lli issueN.ll # expected
opt -passes=loop-bound-split -S issueN.ll -o a.ll && lli a.ll # after pass
```
Tested with `LLVM 23.0.0git`. All transformed modules pass
`opt -passes=verify -verify-dom-info -verify-loop-info`, so these are semantic
miscompiles, not structural errors.
| test | shape | call | expected | after pass |
|------|-------|------|:--------:|:----------:|
| `issue1.ll` | step = 2 (non-unit) | `f(7)` | 3 | **2** |
| `issue2.ll` | exit on `iv+1`, strict `>` | `f(5)` | 3 | **4** |
| `issue3.ll` | exit on raw `iv` (pre-increment) | `f(6)` | 3 | **4** |
### Why each differs
- **issue1 (step = 2):** the bound is derived by dividing by the step
(`%new.bound = smin(lshr(...), 6)`). The truncating division lands between
real induction values (`1,3,5,…`), so the pre-loop stops a grid-point early
and one iteration is **dropped** (3 → 2).
- **issue2 (exit on `inc`, strict `>`):** `%new.bound = smin(smax(n,0), 3)` = 3,
and the exit is `icmp sgt %inc, %new.bound` with `%inc = %iv+1`. The strict
compare on the incremented value keeps the pre-loop going through `iv = 3`, so
the folded-`true` body runs **one iteration too many** (3 → 4).
- **issue3 (exit on raw `iv`):** `%new.bound = umin(n, 3)` = 3, exit is
`icmp uge %iv, %new.bound` on the pre-increment PHI. `iv = 3` executes the
folded-`true` body at the latch *before* the exit fires, so it also runs **one
too many** (3 → 4) — even though the predicate is non-strict (this is what
distinguishes it from issue2).
**Common cause:** `new.bound` is not aligned to the last induction value for
which the split condition holds — off by the step (issue1), or off by one
because of which value/predicate the exit test uses (issue2/issue3).
Contributor guide
Research direction
Start by running the three attached issueN.ll reproducers with lli and with opt -passes=loop-bound-split, then compare the iteration counts shown in the table. Read the loop-bound-split pass implementation around its new.bound calculation and trace the three induction-variable and exit-condition shapes; done means all three transformed modules produce their expected results while still passing the listed verification checks.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 52/100