[SCEV] Compute exit counts for unsigned IVs using mustprogress semantics

[reames]

Summary

The motivation here is simple loops with unsigned induction variables w/non-one steps. A toy example would be:
for (unsigned i = 0; i < N; i += 2) { body; }

Given C/C++ semantics, we do not get the nuw flag on the induction variable. Given that lack, we currently can't compute a bound for this loop. We can do better for many cases, depending on the contents of "body".

The basic intuition behind this patch is as follows:

• A step which evenly divides the iteration space must wrap through the same numbers repeatedly. And thus, we can ignore potential cornercases where we exit after the n-th wrap through uint32_max.
• Per C++ rules, infinite loops without side effects are UB. We already have code in SCEV which relies on this.

Together, these let us conclude that the trip count of this loop must come before unsigned overflow unless the body would form a well defined infinite loop.

A couple notes for reviewers:

• I reused the loop properties code which is overly conservative for this case. I'll follow up in another patch to generalize it for the actual UB rules.
• We could cache the n(s/u)w facts. I left that out because doing a pre-patch which cached existing inference showed a lot of diffs I had trouble fully explaining. I plan to get back to this, but I don't want it on the critical path.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6499

Is this actually true? For C++, I was able to find that

In a valid C++ program, every thread eventually does one of the following:

terminate
makes a call to an I/O library function
reads or modifies a volatile object [!!!]
performs an atomic operation or a synchronization operation

Is it different in LLVM? A loop that only reads volatile memory is non-side-effecting, but I'd be surprised if we considered it finite.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

6499

A volatile read is considered a side effecting instruction, so the presence of a volatile load in the loop will be enough to prevent it from being considered presumed finite.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

11398

Could you just check that Stride is a power of 2 here? This seems overly complicated.

Could you separate out checking "there must be some value of LHS that forces the loop to exit" from "the IV can't wrap"? We can use the former to compute a max backedge taken count even if we can't prove the IV doesn't wrap.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

11398

Could you just check that Stride is a power of 2 here? This seems overly complicated.

Sure, don't really care here, but I'll make the change.

Could you separate out checking "there must be some value of LHS that forces the loop to exit" from "the IV can't wrap"? We can use the former to compute a max backedge taken count even if we can't prove the IV doesn't wrap.

I'm not really following here. I *think* you're asking if we can simply save the no-self-wrap somewhere right?

I agree that in principal, no-self-wrap is enough to prove a max exit count, but in practice, the current code can't do that. I would strongly prefer to work incrementally here if that is what you're suggesting. :)

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

11398

I'm not really following here. I *think* you're asking if we can simply save the no-self-wrap somewhere right?

I was more thinking of computing a max backedge taken count in the case where we can't prove no-self-wrap (i.e. Stride=3).

What you're describing might be useful too.

[reames]

Address reviewer suggestion.

[mkazantsev]

Fine by me if you add a unit test which shows that it works as expected with volatile load.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   bool loopHasNoSideEffects(const Loop *L) {
     return getLoopProperties(L).HasNoSideEffects;
   }
 
   bool loopHasNoAbnormalExits(const Loop *L) {
     return getLoopProperties(L).HasNoAbnormalExits;
   }
 
+  /// Return true if this loop is finite by assumption.  That is,
+  /// to be infinite, it must also be undefined.
+  bool loopIsFiniteByAssumption(const Loop *L);
+
   /// Compute a LoopDisposition value.
   LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
 
   /// Memoized computeBlockDisposition results.
   DenseMap<
       const SCEV *,
       SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
       BlockDispositions;

llvm/lib/Analysis/ScalarEvolution.cpp

if (Itr == LoopPropertiesCache.end()) {
     auto InsertPair = LoopPropertiesCache.insert({L, LP});
     assert(InsertPair.second && "We just checked!");
     Itr = InsertPair.first;
   }
 
   return Itr->second;
 }
 
+bool ScalarEvolution::loopIsFiniteByAssumption(const Loop *L) {
+  // TODO: Use the loop metadata form of mustprogress as well.
+  if (!L->getHeader()->getParent()->mustProgress())
+    return false;
+
+  // A loop without side effects must be finite.
+  // TODO: The check used here is very conservative.  It's only *specific*
+  // side effects which are well defined in infinite loops.
+  return loopHasNoSideEffects(L);
+}
+
 const SCEV *ScalarEvolution::createSCEV(Value *V) {
   if (!isSCEVable(V->getType()))
     return getUnknown(V);
 
   if (Instruction *I = dyn_cast<Instruction>(V)) {
     // Don't attempt to analyze instructions in blocks that aren't
     // reachable. Such instructions don't matter, and they aren't required
     // to obey basic rules for definitions dominating uses which this
if (!PositiveStride) {
     // unsigned char i;
     // for(i=127; i<128; i+=129)
     //   A[i] = i;
     //
     if (PredicatedIV || !NoWrap || isKnownNonPositive(Stride) ||
         !loopHasNoSideEffects(L))
       return getCouldNotCompute();
   } else if (!Stride->isOne() && !NoWrap) {
+    auto isUBOnWrap = [&]() {
+      // Can we prove this loop *must* be UB if overflow of IV occurs?
+      // Reasoning goes as follows:
+      // * Suppose the IV did self wrap.
+      // * If Stride evenly divides the iteration space, then once wrap
+      //   occurs, the loop must revisit the same values.
+      // * We know that RHS is invariant, and that none of those values
+      //   caused this exit to be taken previously.  Thus, this exit is
+      //   dynamically dead.
+      // * If this is the sole exit, then a dead exit implies the loop
+      //   must be infinite if there are no abnormal exits.
+      // * If the loop were infinite, then it must either not be mustprogress
+      //   or have side effects. Otherwise, it must be UB.
+      // * It can't (by assumption), be UB so we have contradicted our
+      //   premise and can conclude the IV did not in fact self-wrap.
+      // From no-self-wrap, we need to then prove no-(un)signed-wrap.  This
+      // follows trivially from the fact that every (un)signed-wrapped, but
+      // not self-wrapped value must be LT than the last value before
+      // (un)signed wrap.  Since we know that last value didn't exit, nor
+      // will any smaller one.
+
+      if (!isLoopInvariant(RHS, L))
+        return false;
+
+      unsigned BitWidth = getTypeSizeInBits(LHS->getType());
+      const SCEV *MaxVal = getConstant(APInt::getMaxValue(BitWidth));
+      const SCEV *StrideMinusOne = getMinusSCEV(Stride,
+                                                getOne(LHS->getType()));
+      if (getURemExpr(MaxVal, Stride) != StrideMinusOne)
+        return false;
+
+      if (!ControlsExit || !loopHasNoAbnormalExits(L))
+        return false;
+
+      return loopIsFiniteByAssumption(L);
+    };
+
     // Avoid proven overflow cases: this will ensure that the backedge taken
     // count will not generate any unsigned overflow. Relaxed no-overflow
     // conditions exploit NoWrapFlags, allowing to optimize in presence of
     // undefined behaviors like the case of C language.
-    if (canIVOverflowOnLT(RHS, Stride, IsSigned))
+    if (canIVOverflowOnLT(RHS, Stride, IsSigned) && !isUBOnWrap())
       return getCouldNotCompute();
   }
 
   ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT
                                       : ICmpInst::ICMP_ULT;
   const SCEV *Start = IV->getStart();
   const SCEV *End = RHS;
   // When the RHS is not invariant, we do not know the end bound of the loop and

llvm/test/Analysis/ScalarEvolution/lt-overflow.ll

+; RUN: opt %s -analyze -scalar-evolution -enable-new-pm=0 -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; A collection of tests focused on exercising logic to prove no-unsigned wrap
+; from mustprogress semantics of loops.
+
+; CHECK: Determining loop execution counts for: @test
+; CHECK: Loop %for.body: backedge-taken count is ((-1 + (2 umax %N)) /u 2)
+; CHECK: Determining loop execution counts for: @test_preinc
+; CHECK: Loop %for.body: backedge-taken count is ((1 + %N) /u 2)
+; CHECK: Determining loop execution counts for: @test_well_defined_infinite
+; CHECK: Loop %for.body: Unpredictable backedge-taken count.
+; CHECK: Determining loop execution counts for: @test_no_mustprogress
+; CHECK: Loop %for.body: Unpredictable backedge-taken count.
+; CHECK: Determining loop execution counts for: @test_1024
+; CHECK: Loop %for.body: backedge-taken count is ((-1 + (1024 umax %N)) /u 1024)
+; CHECK: Determining loop execution counts for: @test_uneven_divide
+; CHECK: Loop %for.body: Unpredictable backedge-taken count.
+; CHECK: Determining loop execution counts for: @test_non_invariant_rhs
+; CHECK: Loop %for.body: Unpredictable backedge-taken count.
+; CHECK: Determining loop execution counts for: @test_abnormal_exit
+; CHECK: Loop %for.body: Unpredictable backedge-taken count.
+; CHECK: Determining loop execution counts for: @test_other_exit
+; CHECK: Loop %for.body: <multiple exits> Unpredictable backedge-taken count.
+
+define void @test(i32 %N) mustprogress {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 2
+  %cmp = icmp ult i32 %iv.next, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+}
+
+define void @test_preinc(i32 %N) mustprogress {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 2
+  %cmp = icmp ult i32 %iv, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+}
+
+@G = external global i32
+
+define void @test_well_defined_infinite(i32 %N) mustprogress {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 2
+  store volatile i32 0, i32* @G
+  %cmp = icmp ult i32 %iv.next, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+}
+
+define void @test_no_mustprogress(i32 %N) {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 2
+  %cmp = icmp ult i32 %iv.next, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+}
+
+
+define void @test_1024(i32 %N) mustprogress {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 1024
+  %cmp = icmp ult i32 %iv.next, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+}
+
+define void @test_uneven_divide(i32 %N) mustprogress {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 3
+  %cmp = icmp ult i32 %iv.next, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+}
+
+define void @test_non_invariant_rhs() mustprogress {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 2
+  %N = load i32, i32* @G
+  %cmp = icmp ult i32 %iv.next, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+}
+
+declare void @mayexit()
+
+define void @test_abnormal_exit(i32 %N) mustprogress {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.body ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 2
+  call void @mayexit()
+  %cmp = icmp ult i32 %iv.next, %N
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+}
+
+
+define void @test_other_exit(i32 %N) mustprogress {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %iv.next, %for.latch ], [ 0, %entry ]
+  %iv.next = add i32 %iv, 2
+  %cmp1 = icmp ult i32 %iv.next, 20
+  br i1 %cmp1, label %for.latch, label %for.cond.cleanup
+
+for.latch:
+  %cmp2 = icmp ult i32 %iv.next, %N
+  br i1 %cmp2, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+}
+
+