[LoopUnroll] Preserving `ScalarEvolution` after runtime unrolling leaves stale flagless SCEV, so sound `nuw`/`nsw` are later stripped from the IR
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
After runtime unrolling, `LoopUnrollPass` reports `ScalarEvolution` preserved, but the surviving SCEV does not learn the no-wrap facts that were proved and added to the IR. The unrolled increment is `add nuw nsw`, while the corresponding cached `SCEVAddRecExpr` remains flagless.
Later in the same `opt` invocation, when passes that use `SCEVExpander` such as `loop(indvars)` and `loop-reduce` process the instruction, the cached `SCEVAddRecExpr` is treated authoritative over the code and the `nuw`/`nsw` flags are dropped. Downstream optimizations that depend on the flags are consequently missed. Recomputing `ScalarEvolution` after `LoopUnrollPass` prevents this.
Briefly, computed results are discarded which causes missed optimizations.
The testcase `test.ll` is the function `@pragma_unroll_count1` from `llvm/test/Transforms/LoopUnroll/full-unroll-avoid-partial.ll`, having a loop with an unknown trip count and specified unroll count of 5:
```llvm
%struct.HIP_vector_type = type { %union.anon }
%union.anon = type { <2 x float> }
define void @pragma_unroll_count1(ptr %queue, i32 %num_elements) {
entry:
%cmp5 = icmp sgt i32 %num_elements, 0
br i1 %cmp5, label %for.body.preheader, label %for.cond.cleanup
for.body.preheader: ; preds = %entry
br label %for.body
for.cond.cleanup.loopexit: ; preds = %for.body
br label %for.cond.cleanup
for.cond.cleanup: ; preds = %for.cond.cleanup.loopexit, %entry
ret void
for.body: ; preds = %for.body, %for.body.preheader
%i.06 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]
%add = add nuw nsw i32 %i.06, 1
%idxprom = zext i32 %add to i64
%arrayidx = getelementptr inbounds %struct.HIP_vector_type, ptr %queue, i64 %idxprom
%idxprom1 = zext i32 %i.06 to i64
%arrayidx2 = getelementptr inbounds %struct.HIP_vector_type, ptr %queue, i64 %idxprom1
%0 = load i64, ptr %arrayidx, align 8
store i64 %0, ptr %arrayidx2, align 8
%exitcond = icmp ne i32 %add, %num_elements
br i1 %exitcond, label %for.body, label %for.cond.cleanup.loopexit, !llvm.loop !0
}
!0 = distinct !{!0, !1}
!1 = !{!"llvm.loop.unroll.count", i32 5}
```
(Similar behavior is also reproduced on another function `@pragma_unroll` from the same file.)
Versions: reproduced with LLVM 23.1.0 and 20.1.2.
Running `loop-unroll` on `test.ll` gives ` %add.4 = add nuw nsw i32 %i.06, 5`, but running `loop(indvars)` or `loop-reduce` (`SCEVExpander`-related passes) subsequently strips the `nuw nsw`. Later IR and backend passes depend on these flags; running the `opt -O2` and `llc -O3` pipelines with and without these flags in the IR gives measurably different performance (>10% slower without no-wrap flags on x86-64, tested on an Intel Core i9-11900K and a 1-vCPU cloud Xeon Emerald Rapids). Invalidating SCEV after loop-unroll to force recomputation and running `loop(indvars)` and `loop-reduce` afterwards does not strip these flags.
```console
$ opt -S -passes='loop-unroll' test.ll | grep '%add.4 = '
%add.4 = add nuw nsw i32 %i.06, 5
$ opt -S -passes='loop-unroll,loop(indvars)' test.ll | grep '%add.4 = '
%add.4 = add i32 %i.06, 5
$ opt -S -passes='loop-unroll,loop(loop-reduce)' test.ll | grep '%add.4 = '
%add.4 = add i32 %i.06, 5
$ opt -S -passes='loop-unroll,invalidate,loop(indvars)' test.ll | grep '%add.4 = '
%add.4 = add nuw nsw i32 %i.06, 5
```
The hidden flag `forget-scev-loop-unroll` does not fix this issue.
```console
$ opt -S -passes='loop-unroll,loop(indvars)' --forget-scev-loop-unroll test.ll | grep '%add.4 = '
%add.4 = add i32 %i.06, 5
```
Suggested fix: [SCEV invalidation is generally expensive](https://www.npopov.com/2023/10/03/LLVM-Scalar-evolution.html), but here the affected expressions are add recurrences (`SCEVAddRecExpr`), which can be updated after creation with the existing `ScalarEvolution::setNoWrapFlags`. `LoopUnrollPass` could therefore update the `ScalarEvolution` it preserves directly, requiring no recomputation, in the case where runtime unrolling with an epilogue occurs. This sort of special-case fix seems to be similar to that proposed for [Issue #213872](https://github.com/llvm/llvm-project/issues/213872), except my issue may be more directly fixable at little or no cost because the no-wrap facts were already computed in `LoopUnrollPass` (they are in the IR it emitted) and can write them into the preserved analysis.
The cached SCEV is also imprecise in other ways (e.g. the `max backedge-taken count`), but [Issue #214665](https://github.com/llvm/llvm-project/issues/214665) clarifies that maximal precision is not a goal.
I also found some strange ordering dependence in how the no-wrap flags are recovered: `loop-unroll,invalidate,loop(indvars)` recovers both flags, but `loop-unroll,invalidate,invalidate,loop(indvars)` recovers only `nuw`, not `nsw`. `invalidate` and running the two passes as separate `opt` invocations behave like the latter. This does not happen when `loop(indvars)` is replaced with `loop-reduce`. Why a freshly recomputed LoopInfo leads to less precise flags than the cached one is strange and undesirable when it could affect downstream optimizations.
Contributor guide
Research direction
Start with LoopUnrollPass and ScalarEvolution::setNoWrapFlags, using the @pragma_unroll_count1 testcase in llvm/test/Transforms/LoopUnroll/full-unroll-avoid-partial.ll. Run the listed opt pipelines with loop(indvars) and loop-reduce to reproduce the flag loss. Done means the regression test keeps nuw/nsw on the unrolled increment after those follow-up passes without unnecessary SCEV recomputation.
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
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100