llvm / llvm/llvm-project

`loop-bound-split` computes a wrong pre-loop bound (miscompile)

Open
#207,360 1 comment 0 reactions 0 assignees View on GitHub
loopoptim miscompilation
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.