[LoopUnroll][SCEV] Runtime unroll blocked by non‑computable exit block SCEV unless IV add has NUW
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Hi folks,
I’m seeing a loop fail runtime unrolling because SCEV can’t compute the exiting block’s exit count unless the induction increment has NUW. I’d appreciate guidance on whether this is expected, and if SCEV/Unroll could rely on the predicated backedge count here.
The loop iterates between range [S, E] with step 1 where S and E are compile-time unknown values.
Here's the minimal IR:
```
define void @test(i32 %S, i32 %E, ptr %arr) {
entry:
br label %loop
loop:
%i = phi i32 [ %S, %entry ], [ %inc, %latch ]
%idx.ext = zext i32 %i to i64
%ptr = getelementptr i32, ptr %arr, i64 %idx.ext
%x = load i32, ptr %ptr, align 4
store i32 %x, ptr %ptr, align 4
%inc = add i32 %i, 1
%exit = icmp ult i32 %E, %inc
br i1 %exit, label %exitBB, label %latch
latch:
br label %loop
exitBB:
ret void
}
```
Command to reproduce:
```
opt -S -passes='loop-rotate,indvar,loop-simplify,print,loop-unroll' -debug-only=loop-unroll -unroll-runtime -print-after-all a.ll
```
What I observe
SCEV without nuw
- %i is {%S,+,1}<%loop> with Exits: <>.
- SCEV reports “Unpredictable [symbolic] backedge‑taken count,” but does compute a predicated backedge‑taken count:
```
Predicated backedge-taken count:
((-1 * (zext i32 (1 + %S) to i64))
+ ((zext i32 (1 + %S) to i64)
umax (1 + (zext i32 %E to i64))))
Predicates:
{(1 + %S),+,1}<%loop> Added Flags:
```
- LoopUnroll bails early due to non‑computable exiting block SCEV.
SCEV with nuw on %inc
- %i becomes {%S,+,1}<%loop> with Exits: (%S umax %E).
- Backedge‑taken count is ((-1 * %S) + (%S umax %E)).
- Runtime unrolling proceeds.
Questions
- SCEV reasoning: In this pattern, S/E are unknown at compile time and the exit is unsigned (icmp ult %E, %inc). Without nuw on the IV, wrap‑around can’t be excluded, so I understand why SCEV won’t produce an exit count. But SCEV does compute a predicated backedge count that assumes . Would it be acceptable for the unroller to use that predicated count (with appropriate guards/epilogue) or is this considered unsafe/undesirable?
Contributor guide
Research direction
Start with the minimal IR and reproduce it using the provided opt pipeline, especially print and loop-unroll with -unroll-runtime. Read the ScalarEvolution and LoopUnroll handling of non-computable exit counts and predicated backedge counts. Done means establishing whether the predicated count is safe and suitable for runtime unrolling, with the behavior or required change clearly documented.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100