[IndVarSimplify] Missing freeze in turn-to-invariant transformation
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
## Summary
`IndVarSimplify`'s turn-to-invariant transformation can produce an
incorrect transformation when the induction variable's start value
may be `undef`.
The transformation re-materializes an expression derived from the IV
start value without freezing it first. Since `undef` may take different
values at different uses, the newly created use can observe a different
value from the original IV use.
Alive2 reports:
```
Transformation doesn't verify!
ERROR: Source is more defined than target
```
The issue disappears when the IV start value is frozen or constrained
to be `noundef`.
## Reproducer
The following is a reduced reproducer. Save it as
`BUG_indvars_umax_undef.ll` and run:
```llvm
; IndVars miscompile: turn-to-invariant with an undef IV start.
;
; Reproduce:
; opt -passes='indvars' \
; -mtriple=x86_64-unknown-linux-gnu \
; BUG_indvars_umax_undef.ll -S > tgt.ll
;
; Then verify with Alive2:
; alive-tv BUG_indvars_umax_undef.ll tgt.ll
;
; Alive2 reports:
; "Transformation doesn't verify!"
; "Source is more defined than target"
;
; Counterexample:
; %start = undef
; %len = 0
;
; The turn-to-invariant transformation rewrites the loop guard
; icmp ult %iv, %len
; into a condition involving umax(%len, %start), and also derives
; the exit value from %start + 1.
;
; If %start is undef, the original IV use and the newly introduced
; use of %start are allowed to observe different values. The
; transformation does not freeze the value before introducing the
; new use, resulting in a refinement violation.
;
; Adding freeze to the relevant %start value makes the transformation
; verify successfully.
;
; The transformation requires X86 TTI (-mtriple). Without -mtriple,
; this particular rewrite does not occur.
;
; The same issue occurs with a fresh SCEV pipeline, so this does not
; appear to be specific to stale SCEV state.
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
declare i1 @cond()
define i32 @test_predicated_backedge_with_side_exit_unknown_start(
i32 %start, i32 %len) {
entry:
br label %loop
loop:
%iv = phi i32 [ %start, %entry ], [ %iv.next, %backedge ]
%iv.next = add i32 %iv, 1
%check = icmp ult i32 %iv, %len
br i1 %check, label %inner_block, label %failed
inner_block:
%cond_1 = call i1 @cond()
br i1 %cond_1, label %backedge, label %failed
backedge:
%loop.cond = icmp ult i32 %iv.next, %len
br i1 %loop.cond, label %loop, label %exit
exit:
ret i32 %iv.next
failed:
ret i32 -1
}
```
Then run:
```bash
opt -passes='indvars' \
-mtriple=x86_64-unknown-linux-gnu \
BUG_indvars_umax_undef.ll -S > tgt.ll
alive-tv BUG_indvars_umax_undef.ll tgt.ll
```
## Observed behavior
The following variants were tested:
| Condition | Result |
|---|---|
| `%start` may be `undef` | Alive2 refinement failure |
| `%start` is frozen | Correct |
| `%start` is `noundef` | Correct |
| `%start` is `poison` | No equivalent miscompile |
| No `-mtriple` | Transformation does not trigger |
## Root cause
The relevant code is in `IndVarSimplify`, in the
turn-to-invariant path, around `createInvariantCond()`.
The transformation uses SCEV to construct an invariant expression and
then expands that expression back into IR.
The IV start value can therefore be used both by the original IV
computation and by the newly created expression.
If the start value is `undef`, these two uses are allowed to select
different values.
Conceptually:
```text
start = undef
/ \
/ \
IV newly-created expression
```
The transformation appears to rely on these uses observing the same
value, but no `freeze` is inserted before the value is reused.
Freezing the value makes the transformation verify successfully.
## Security impact
I also investigated whether this could lead to an actual memory-safety
violation.
I constructed an indexing-loop PoC and attempted to turn the changed
loop condition into an out-of-bounds access.
So far I have not been able to demonstrate a reliable OOB in generated
code. In the tested form, the backedge condition
```text
iv.next
Contributor guide
Research direction
Start with the IndVarSimplify turn-to-invariant path around createInvariantCond(), then reproduce the report using BUG_indvars_umax_undef.ll with opt and the x86_64 triple. Compare the generated tgt.ll with Alive2, including the frozen and noundef variants. Done means the undef-start transformation no longer produces an Alive2 refinement failure and has a regression test.
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
- Mostly clear
- Newbie friendliness
- 52/100