[SCEV] Use the number of steps of an IV to clamp max BTC (WIP).

[fhahn]

Summary

As discussed in D89381, we can use the range of an non-wrapping IV to
clamp down the max BTC in some cases.

This impacts a few other test cases that I still need to update and it
seems in some cases the new bound is more precise than the exact exit
count, which I still need to investigate. I just wanted to share this
early.

llvm/lib/Analysis/ScalarEvolution.cpp

if (AddRec->hasNoSignedWrap()) {
       bool AllNonNeg = true;
       bool AllNonPos = true;
       for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) {
         if (!isKnownNonNegative(AddRec->getOperand(i)))
           AllNonNeg = false;
         if (!isKnownNonPositive(AddRec->getOperand(i)))
           AllNonPos = false;
       }
-      if (AllNonNeg)
+      if (AllNonNeg) {
         ConservativeResult = ConservativeResult.intersectWith(
             ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
                                        APInt::getSignedMinValue(BitWidth)),
             RangeType);
-      else if (AllNonPos)
+      } else if (AllNonPos)
         ConservativeResult = ConservativeResult.intersectWith(
             ConstantRange::getNonEmpty(
                 APInt::getSignedMinValue(BitWidth),
                 getSignedRangeMax(AddRec->getStart()) + 1),
             RangeType);
     }
 
     // TODO: non-affine addrec
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
         // Form the constant range.
         ConstantRange CompRange =
             ConstantRange::makeExactICmpRegion(Pred, RHSC->getAPInt());
 
         const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
         if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
       }
 
+  auto ClampMaxBTCByIV = [this](const SCEV *IV, ExitLimit EL) {
+    auto AR = dyn_cast<SCEVAddRecExpr>(IV);
+    if (!AR)
+      return EL;
+
+    auto StepC = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this));
+    if (!StepC || StepC->getAPInt().isNonPositive())
+      return EL;
+
+    auto R = getUnsignedRange(AR);
+    if (R.isWrappedSet() || R.isFullSet())
+      return EL;
+    auto *IVBound = getUMinExpr(
+        getConstant((R.getUpper() - R.getLower()).udiv(StepC->getAPInt())),
+        EL.MaxNotTaken);
+    assert(isa<SCEVConstant>(IVBound) &&
+           "should have managed to simplify to a constant");
+    EL.MaxNotTaken = IVBound;
+    return EL;
+  };
   switch (Pred) {
   case ICmpInst::ICMP_NE: {                     // while (X != Y)
     // Convert to: while (X-Y != 0)
     ExitLimit EL = howFarToZero(getMinusSCEV(LHS, RHS), L, ControlsExit,
                                 AllowPredicates);
-    if (EL.hasAnyInfo()) return EL;
+    if (EL.hasAnyInfo())
+      return ClampMaxBTCByIV(LHS, EL);
     break;
   }
   case ICmpInst::ICMP_EQ: {                     // while (X == Y)
     // Convert to: while (X-Y == 0)
     ExitLimit EL = howFarToNonZero(getMinusSCEV(LHS, RHS), L);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_ULT: {                    // while (X < Y)
     bool IsSigned = Pred == ICmpInst::ICMP_SLT;
     ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit,
                                     AllowPredicates);
-    if (EL.hasAnyInfo()) return EL;
+    if (EL.hasAnyInfo())
+      return ClampMaxBTCByIV(LHS, EL);
     break;
   }
   case ICmpInst::ICMP_SGT:
   case ICmpInst::ICMP_UGT: {                    // while (X > Y)
     bool IsSigned = Pred == ICmpInst::ICMP_SGT;
     ExitLimit EL =
         howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit,
                             AllowPredicates);
-    if (EL.hasAnyInfo()) return EL;
+    if (EL.hasAnyInfo())
+      return ClampMaxBTCByIV(LHS, EL);
     break;
   }
   default:
     break;
   }
 
   auto *ExhaustiveCount =
       computeExitCountExhaustively(L, ExitCond, ExitIfTrue);

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll

 define void @test_guard_ule_12_step2(i32* nocapture %a, i64 %N) {
 ; CHECK-LABEL: 'test_guard_ule_12_step2'
 ; CHECK-NEXT:  Classifying expressions for: @test_guard_ule_12_step2
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ 0, %entry ]
 ; CHECK-NEXT:    --> {0,+,2}<nuw><nsw><%loop> U: [0,-9223372036854775808) S: [0,9223372036854775807) Exits: (2 * (%N /u 2))<nuw> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,8}<nsw><%loop> U: full-set S: full-set Exits: ((8 * (%N /u 2)) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 2
-; CHECK-NEXT:    --> {2,+,2}<nuw><%loop> U: [2,-1) S: [-9223372036854775808,9223372036854775807) Exits: (2 + (2 * (%N /u 2))<nuw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {2,+,2}<nuw><%loop> U: [2,-9223372036854775805) S: [-9223372036854775808,9223372036854775807) Exits: (2 + (2 * (%N /u 2))<nuw>) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_ule_12_step2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (%N /u 2)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 9223372036854775807
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4611686018427387904
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%N /u 2)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.1 = icmp ule i64 %N, 12
   br i1 %c.1, label %loop, label %exit
 

 define void @test_multiple_var_guards_order1(i32* nocapture %a, i64 %i, i64 %N) {
 ; CHECK-LABEL: 'test_multiple_var_guards_order1'
 ; CHECK-NEXT:  Classifying expressions for: @test_multiple_var_guards_order1
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ 0, %guardbb ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: %i LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nsw><%loop> U: full-set S: full-set Exits: ((4 * %i) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,-9223372036854775806) S: [1,-9223372036854775806) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_order1
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %i
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -9223372036854775808
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %i
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.1 = icmp ult i64 %N, 12
   br i1 %c.1, label %guardbb, label %exit
 

 define void @test_multiple_var_guards_order2(i32* nocapture %a, i64 %i, i64 %N) {
 ; CHECK-LABEL: 'test_multiple_var_guards_order2'
 ; CHECK-NEXT:  Classifying expressions for: @test_multiple_var_guards_order2
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ 0, %guardbb ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: %i LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nsw><%loop> U: full-set S: full-set Exits: ((4 * %i) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,-9223372036854775806) S: [1,-9223372036854775806) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_order2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %i
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -9223372036854775808
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %i
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.1 = icmp ult i64 %i, %N
   br i1 %c.1, label %guardbb, label %exit
 

 define void @test_multiple_var_guards_cycle(i32* nocapture %a, i64 %i, i64 %N) {
 ; CHECK-LABEL: 'test_multiple_var_guards_cycle'
 ; CHECK-NEXT:  Classifying expressions for: @test_multiple_var_guards_cycle
 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ 0, %guardbb ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: %N LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nsw><%loop> U: full-set S: full-set Exits: ((4 * %N) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %N) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,-9223372036854775806) S: [1,-9223372036854775806) Exits: (1 + %N) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_cycle
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %N
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -9223372036854775808
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %N
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.1 = icmp ult i64 %N, %i
   br i1 %c.1, label %guardbb, label %exit
 

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-limit-by-wrapping.ll

 ; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution -scalar-evolution-max-iterations=0  -scalar-evolution-classify-expressions=0  | FileCheck %s
 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-max-iterations=0  -scalar-evolution-classify-expressions=0  2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @max_backedge_taken_count_by_wrapping1_nsw_nuw(i8 %N, i8* %ptr) {
 ; CHECK-LABEL: Determining loop execution counts for: @max_backedge_taken_count_by_wrapping1_nsw_nuw
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (%N /u 4)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 63
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 32
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%N /u 4)
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop ]
   %gep = getelementptr i8, i8* %ptr, i8 %iv

 
 exit:
   ret void
 }
 
 define void @max_backedge_taken_count_by_wrapping2_nsw_nuw(i8 %N, i8* %ptr) {
 ; CHECK-LABEL: Determining loop execution counts for: @max_backedge_taken_count_by_wrapping2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-64 + %N) /u 4)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 63
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 16
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-64 + %N) /u 4)
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i8 [ 64, %entry ], [ %iv.next, %loop ]
   %gep = getelementptr i8, i8* %ptr, i8 %iv
   store i8 %iv, i8* %gep
   %iv.next = add nuw nsw i8 %iv, 4
   %ec = icmp ne i8 %iv, %N
   br i1 %ec, label %loop, label %exit
 
 exit:
   ret void
 }
 
 define void @max_backedge_taken_count_by_wrapping2_nuw(i8 %N, i8* %ptr) {
 ; CHECK-LABEL: Determining loop execution counts for: @max_backedge_taken_count_by_wrapping2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-64  + %N) /u 4)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 63
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 47
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-64 + %N) /u 4)
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i8 [ 64, %entry ], [ %iv.next, %loop ]
   %gep = getelementptr i8, i8* %ptr, i8 %iv
   store i8 %iv, i8* %gep
   %iv.next = add nuw i8 %iv, 4
   %ec = icmp ne i8 %iv, %N
   br i1 %ec, label %loop, label %exit
 
 exit:
   ret void
 }

llvm/test/Analysis/ScalarEvolution/trip-count.ll

for.inc.1:                                        ; preds = %for.body.1, %for.inc
   br i1 %exitcond.1, label %end, label %preheader
 }
 
 ; Function Attrs: nounwind
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i1) #0
 
 declare void @may_exit() nounwind
 
-define void @pr28012(i32 %n) {
+define void @pr28012(i8 %n) {
 ; CHECK-LABEL: 'pr28012'
 ; CHECK-NEXT:  Determining loop execution counts for: @pr28012
-; CHECK-NEXT:  Loop %loop: backedge-taken count is -1431655751
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1431655751
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is -1431655751
+; CHECK-NEXT:  Loop %loop: backedge-taken count is -71
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 84
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is -71
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %loop: Trip multiple is 2863311546
+; CHECK:       Loop %loop: Trip multiple is 186
 ;
 entry:
   br label %loop
 
 loop:
-  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
-  %iv.inc = add nsw i32 %iv, 3
+  %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i8 %iv, 3
   call void @may_exit()
-  %becond = icmp ne i32 %iv.inc, 46
+  %becond = icmp ne i8 %iv.inc, 46
   br i1 %becond, label %loop, label %leave
 
 leave:
   ret void
 }