[LoopUnroll][SCEV] Runtime unroll blocked by non‑computable exit block SCEV unless IV add has NUW

[forandom]

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<scalar-evolution>,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))<nsw>
       + ((zext i32 (1 + %S) to i64)
          umax (1 + (zext i32 %E to i64))<nuw><nsw>))
    Predicates:
      {(1 + %S),+,1}<%loop> Added Flags: <nusw>

• 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?

[forandom]

CC @nikic @fhahn

[nikic]

It's possible in principle, but runtime unrolling does not really have any sensible cost model right now, so it wouldn't be able to model whether introducing additional predication is worthwhile.

[forandom]

It's possible in principle, but runtime unrolling does not really have any sensible cost model right now, so it wouldn't be able to model whether introducing additional predication is worthwhile.

Thanks @nikic for your quick response.

What I'm trying to understand at first place is the reason that SE->getExitCount(L, Latch) returns SCEVCouldNotCompute after it already computed a predicated backedge-taken count. Or is there another SCEV interface that can return the predicated backedge-taken count?

[nikic]

Yes, that would be getPredicatedExitCount().