| Issue |
243963
|
| Summary |
[SCEV] Invalid `nuw` propagated to shared _expression_ in `getAddExpr`
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
hawkinsp
|
`IndVarSimplify` incorrectly folds a conditional branch inside a loop to `br i1 true`, causing a guarded call to run even when the branch condition is `false`.
Tested at `c03c4571b1b00894a559a265baefe1924db73a27`. Godbolt link: https://godbolt.org/z/dE4Y3shxq
This issue appears to be the root cause of https://github.com/jax-ml/jax/issues/42589
```llvm
; repro.ll
; opt -S -passes=indvars repro.ll
;
; Pseudocode:
; start = cond ? 1 : 0 // uint8: 0 or 1
; for i in 0, 1:
; if i >= start:
; v = val() // uint8: 0 or 1
; add1 = (i - start) +nuw v
; add2 = add1 +nuw 1
; for j = 0; j != add2; j++ {}
declare range(i8 0, 2) i8 @val() nounwind willreturn
define void @repro(i1 %cond) {
entry:
%start = zext i1 %cond to i8
br label %outer
outer:
%i = phi i8 [ 0, %entry ], [ %i.next, %latch ]
%ge = icmp uge i8 %i, %start
br i1 %ge, label %guarded, label %latch
guarded:
%v = call i8 @val()
%sub = sub i8 %i, %start
%add1 = add nuw i8 %sub, %v
%add2 = add nuw i8 %add1, 1
br label %inner
inner:
%j = phi i8 [ 0, %guarded ], [ %j.next, %inner ]
%j.next = add i8 %j, 1
%j.cmp = icmp ne i8 %j, %add2
br i1 %j.cmp, label %inner, label %latch
latch:
%i.next = add i8 %i, 1
%cmp = icmp ult i8 %i.next, 2
br i1 %cmp, label %outer, label %exit
exit:
ret void
}
```
When `%cond` is `true`, `%start` is `1`, so iteration `0` skips `%guarded` and `@val()` should run once (no overflow or UB on any path). `IndVarSimplify` produces the following IR, folding `br i1 %ge` to `br i1 true`, leaving `%cond` unused, and calling `@val()` twice unconditionally:
```llvm
; Function Attrs: nounwind willreturn
declare range(i8 0, 2) i8 @val() #0
define void @repro(i1 %cond) {
entry:
br label %outer
outer: ; preds = %latch, %entry
%i = phi i8 [ 0, %entry ], [ %i.next, %latch ]
br i1 true, label %guarded, label %latch
guarded: ; preds = %outer
%v = call i8 @val()
br label %inner
inner: ; preds = %inner, %guarded
br i1 false, label %inner, label %latch.loopexit
latch.loopexit: ; preds = %inner
br label %latch
latch: ; preds = %latch.loopexit, %outer
%i.next = add nuw nsw i8 %i, 1
%cmp = icmp samesign ult i8 %i.next, 2
br i1 %cmp, label %outer, label %exit
exit: ; preds = %latch
ret void
}
attributes #0 = { nounwind willreturn }
```
`opt -disable-output -passes='print<scalar-evolution>' repro.ll` prints:
```text
%sub = sub i8 %i, %start
--> {(-1 * (zext i1 %cond to i8))<nuw><nsw>,+,1}<nw><%outer> U: [-1,2) S: [-1,2) Exits: (1 + (-1 * (zext i1 %cond to i8))<nuw><nsw>)<nsw> LoopDispositions: { %outer: Computable, %inner: Invariant }
%add1 = add nuw i8 %sub, %v
--> ({(-1 * (zext i1 %cond to i8))<nuw><nsw>,+,1}<nsw><%outer> + %v)<nuw> U: [-1,3) S: [-1,3) Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
%add2 = add nuw i8 %add1, 1
--> ({(1 + (-1 * (zext i1 %cond to i8))<nuw><nsw>)<nuw><nsw>,+,1}<nuw><nsw><%outer> + %v) U: [1,4) S: [1,4) Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
```
`(1 + (-1 * (zext i1 %cond to i8))<nuw><nsw>)` starts out with `<nsw>` only on `%sub`'s exit value, then gains `<nuw>` when `%add2` is classified. That outer `<nuw>` is invalid when `%cond` is `true`, because `1 + 255` wraps to `0` in unsigned `i8`. Removing `nuw` from either `%add1` or `%add2` prevents the miscompile.
## Possible fix
In `ScalarEvolution::getAddExpr` (`llvm/lib/Analysis/ScalarEvolution.cpp:2782–2818`), folding `1` into `{-start, +, 1}` leaves `%v` behind (`Ops.size() > 1`), yet still reuses the outer `ExprFlags` via `ComputeFlags(LIOps)`. Those flags may only hold inside a conditional block where a remaining non-invariant operand like `%v` is defined — not at the loop header, which is what the `isGuaranteedToTransferExecutionTo` check below assumes. Dropping operands is also invalid for `nsw`.
```diff
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -2784,7 +2784,10 @@ SCEVUse ScalarEvolution::getAddExpr(SmallVectorImpl<SCEVUse> &Ops,
// the addrec. Temporarily push it as an operand for that purpose. These
// flags are valid in the scope of the addrec only.
LIOps.push_back(AddRec);
- SCEVFlags Flags = ComputeFlags(LIOps);
+ SCEVFlags Flags =
+ Ops.size() == 1
+ ? ComputeFlags(LIOps)
+ : StrengthenNoWrapFlags(this, scAddExpr, LIOps, SCEV::FlagNone);
LIOps.pop_back();
// NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step}
```
Assisted-by: An unreleased version of Google Gemini.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs