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

Reply via email to