[IRCE] Fix corner case with Start = INT_MAX

[mkazantsev]

Summary

When iterating through loop

for (int i = INT_MAX; i > 0; i--)

We fail to generate the pre-loop for it. It happens because we use the overflown value
in a comparison predicate when identifying whether or not we need it.

In old logic, we used SLE predicate against Greatest value which exceeds all seen values
of the IV and might be overflown. Now we use the GreatestSeen value of this IV with SLT
predicate.

Also added a test that ensures that a pre-loop is generated for such loops.

[anna]

LGTM w/ comments inline.

test/Transforms/IRCE/pre_post_loops.ll

20

I don't think the branch weight really needed here? Pls remove if so.

Same for one below.

38

Could you pls add some statements here regarding what's the expected terminating condition of the preloop. Similar for the test above.

45

Could you please state in the comment above the test that this tests the case where START = INT_MAX.

[sanjoy]

llvm/trunk/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

948 ↗

(On Diff #106582)

Please update this comment.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

LoopConstrainer::calculateSubRanges() const {
   // I think we can be more aggressive here and make this nuw / nsw if the
   // addition that feeds into the icmp for the latch's terminating branch is nuw
   // / nsw.  In any case, a wrapping 2's complement addition is safe.
   const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
   const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
 
   bool Increasing = MainLoopStructure.IndVarIncreasing;
 
-  // We compute `Smallest` and `Greatest` such that [Smallest, Greatest) is the
-  // range of values the induction variable takes.
+  // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
+  // [Smallest, GreatestSeen] is the range of values the induction variable
+  // takes.
 
-  const SCEV *Smallest = nullptr, *Greatest = nullptr;
+  const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
 
+  const SCEV *One = SE.getOne(Ty);
   if (Increasing) {
     Smallest = Start;
     Greatest = End;
+    // No overflow, because the range [Smallest, GreatestSeen] is not empty.
+    GreatestSeen = SE.getMinusSCEV(End, One);
   } else {
     // These two computations may sign-overflow.  Here is why that is okay:
     //
     // We know that the induction variable does not sign-overflow on any
     // iteration except the last one, and it starts at `Start` and ends at
     // `End`, decrementing by one every time.
     //
     //  * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the
     //    induction variable is decreasing we know that that the smallest value
     //    the loop body is actually executed with is `INT_SMIN` == `Smallest`.
     //
     //  * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`.  In
     //    that case, `Clamp` will always return `Smallest` and
     //    [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`)
     //    will be an empty range.  Returning an empty range is always safe.
     //
 
-    const SCEV *One = SE.getOne(Ty);
     Smallest = SE.getAddExpr(End, One);
     Greatest = SE.getAddExpr(Start, One);
+    GreatestSeen = Start;
   }
 
   auto Clamp = [this, Smallest, Greatest](const SCEV *S) {
     return SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S));
   };
 
   // In some cases we can prove that we don't need a pre or post loop
 
   bool ProvablyNoPreloop =
       SE.isKnownPredicate(ICmpInst::ICMP_SLE, Range.getBegin(), Smallest);
   if (!ProvablyNoPreloop)
     Result.LowLimit = Clamp(Range.getBegin());
 
   bool ProvablyNoPostLoop =
-      SE.isKnownPredicate(ICmpInst::ICMP_SLE, Greatest, Range.getEnd());
+      SE.isKnownPredicate(ICmpInst::ICMP_SLT, GreatestSeen, Range.getEnd());
   if (!ProvablyNoPostLoop)
     Result.HighLimit = Clamp(Range.getEnd());
 
   return Result;
 }
 
 void LoopConstrainer::cloneLoop(LoopConstrainer::ClonedLoop &Result,
                                 const char *Tag) const {

test/Transforms/IRCE/pre_post_loops.ll

+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
+
+; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
+; CHECK: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
+
+; Iterate from 0 to SINT_MAX, check that the post-loop is generated.
+define void @test_01(i32* %arr, i32* %a_len_ptr) {
+
+; CHECK:       test_01(
+; CHECK:       entry:
+; CHECK-NEXT:    %exit.mainloop.at = load i32, i32* %a_len_ptr
+; CHECK:       loop:
+; CHECK-NEXT:    %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
+; CHECK-NEXT:    %idx.next = add i32 %idx, 1
+; CHECK-NEXT:    %abc = icmp slt i32 %idx, %exit.mainloop.at
+; CHECK-NEXT:    br i1 true, label %in.bounds,
+; CHECK:       in.bounds:
+; CHECK-NEXT:    %addr = getelementptr i32, i32* %arr, i32 %idx
+; CHECK-NEXT:    store i32 0, i32* %addr
+; CHECK-NEXT:    %next = icmp slt i32 %idx.next, 2147483647
+; CHECK-NEXT:    [[COND:%[^ ]+]] = icmp slt i32 %idx.next, %exit.mainloop.at
+; CHECK-NEXT:    br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       main.pseudo.exit:
+; CHECK-NEXT:    %idx.copy = phi i32 [ 0, %entry ], [ %idx.next.lcssa, %main.exit.selector ]
+; CHECK-NEXT:    %indvar.end = phi i32 [ 0, %entry ], [ %idx.next.lcssa, %main.exit.selector ]
+; CHECK-NEXT:    br label %postloop
+; CHECK:       postloop:
+; CHECK-NEXT:    br label %loop.postloop
+; CHECK:       loop.postloop:
+; CHECK-NEXT:    %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
+; CHECK-NEXT:    %idx.next.postloop = add i32 %idx.postloop, 1
+; CHECK-NEXT:    %abc.postloop = icmp slt i32 %idx.postloop, %exit.mainloop.at
+; CHECK-NEXT:    br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
+; CHECK:       in.bounds.postloop:
+; CHECK-NEXT:    %addr.postloop = getelementptr i32, i32* %arr, i32 %idx.postloop
+; CHECK-NEXT:    store i32 0, i32* %addr.postloop
+; CHECK-NEXT:    %next.postloop = icmp slt i32 %idx.next.postloop, 2147483647
+; CHECK-NEXT:    br i1 %next.postloop, label %loop.postloop, label %exit.loopexit
+
+entry:
+  %len = load i32, i32* %a_len_ptr, !range !0
+  br label %loop
+
+loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
+  %idx.next = add i32 %idx, 1
+  %abc = icmp slt i32 %idx, %len
+  br i1 %abc, label %in.bounds, label %out.of.bounds
+
+in.bounds:
+  %addr = getelementptr i32, i32* %arr, i32 %idx
+  store i32 0, i32* %addr
+  %next = icmp slt i32 %idx.next, 2147483647
+  br i1 %next, label %loop, label %exit
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+; Iterate from SINT_MAX to 0, check that the pre-loop is generated.
+define void @test_02(i32* %arr, i32* %a_len_ptr) {
+
+; CHECK:      test_02(
+; CHECK:      entry:
+; CHECK-NEXT:   %len = load i32, i32* %a_len_ptr, !range !0
+; CHECH-NEXT:    br i1 true, label %loop.preloop.preheader
+; CHECK:      mainloop:
+; CHECK-NEXT:   br label %loop
+; CHECK:      loop:
+; CHECK-NEXT:   %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
+; CHECK-NEXT:   %idx.next = add i32 %idx, -1
+; CHECK-NEXT:   %abc = icmp slt i32 %idx, %len
+; CHECK-NEXT:   br i1 true, label %in.bounds
+; CHECK:      in.bounds:
+; CHECK-NEXT:   %addr = getelementptr i32, i32* %arr, i32 %idx
+; CHECK-NEXT:   store i32 0, i32* %addr
+; CHECK-NEXT:   %next = icmp sgt i32 %idx.next, -1
+; CHECK-NEXT:   br i1 %next, label %loop, label %exit.loopexit
+; CHECK:      loop.preloop:
+; CHECK-NEXT:   %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 2147483647, %loop.preloop.preheader ]
+; CHECK-NEXT:   %idx.next.preloop = add i32 %idx.preloop, -1
+; CHECK-NEXT:   %abc.preloop = icmp slt i32 %idx.preloop, %len
+; CHECK-NEXT:   br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
+; CHECK:      in.bounds.preloop:
+; CHECK-NEXT:   %addr.preloop = getelementptr i32, i32* %arr, i32 %idx.preloop
+; CHECK-NEXT:   store i32 0, i32* %addr.preloop
+; CHECK-NEXT:   %next.preloop = icmp sgt i32 %idx.next.preloop, -1
+; CHECK-NEXT:   [[COND:%[^ ]+]] = icmp sgt i32 %idx.next.preloop, -1
+; CHECK-NEXT:   br i1 [[COND]], label %loop.preloop, label %preloop.exit.selector
+
+entry:
+  %len = load i32, i32* %a_len_ptr, !range !0
+  br label %loop
+
+loop:
+  %idx = phi i32 [ 2147483647, %entry ], [ %idx.next, %in.bounds ]
+  %idx.next = add i32 %idx, -1
+  %abc = icmp slt i32 %idx, %len
+  br i1 %abc, label %in.bounds, label %out.of.bounds
+
+in.bounds:
+  %addr = getelementptr i32, i32* %arr, i32 %idx
+  store i32 0, i32* %addr
+  %next = icmp sgt i32 %idx.next, -1
+  br i1 %next, label %loop, label %exit
+
+out.of.bounds:
+  ret void
+
+exit:
+  ret void
+}
+
+!0 = !{i32 0, i32 50}