[SCEV] Infer no-self-wrap via constant ranges

[reames]

Summary

Without this, pointer IVs in loops with small constant trip counts couldn't be proven no-self-wrap. This came up in a new LSR transform, but may also benefit other SCEV consumers as well.

[reames]

llvm/test/Transforms/LoopVersioning/lcssa.ll

59

FYI, this gep is unused in the code before the change. No idea why the SCEV change causes the pause to realize it's dead, nor do I really care.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

4995

I think it would make more sense to use the constant max BECount here, rather than the range of the exact BECount. That should be strictly more powerful and is also more in line with how we infer nuw/nsw on affine addrecs.

[reames]

Address review comment.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

4995

const &

llvm/lib/Analysis/ScalarEvolution.cpp

 ScalarEvolution::proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR) {
   if (!AR->isAffine())
     return SCEV::FlagAnyWrap;
 
   using OBO = OverflowingBinaryOperator;
 
   SCEV::NoWrapFlags Result = SCEV::FlagAnyWrap;
 
+  if (!AR->hasNoSelfWrap()) {
+    const SCEV *BECount = getConstantMaxBackedgeTakenCount(AR->getLoop());
+    if (const SCEVConstant *BECountMax = dyn_cast<SCEVConstant>(BECount)) {
+      ConstantRange StepCR = getSignedRange(AR->getStepRecurrence(*this));
+      const APInt &BECountAP = BECountMax->getAPInt();
+      unsigned NoOverflowBitWidth =
+        BECountAP.getActiveBits() + StepCR.getMinSignedBits();
+      if (NoOverflowBitWidth <= getTypeSizeInBits(AR->getType()))
+        Result = ScalarEvolution::setFlags(Result, SCEV::FlagNW);
+    }
+  }
+
   if (!AR->hasNoSignedWrap()) {
     ConstantRange AddRecRange = getSignedRange(AR);
     ConstantRange IncRange = getSignedRange(AR->getStepRecurrence(*this));
 
     auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
         Instruction::Add, IncRange, OBO::NoSignedWrap);
     if (NSWRegion.contains(AddRecRange))
       Result = ScalarEvolution::setFlags(Result, SCEV::FlagNSW);

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

for (PHINode &PN : L->getHeader()->phis()) {
     // without soundness problems.  evaluateAtIteration internally needs
     // to multiply the stride of the iteration number - which may wrap around.
     // The issue here is subtle because computing the result accounting for
     // wrap is insufficient. In order to use the result in an exit test, we
     // must also know that AddRec doesn't take the same value on any previous
     // iteration. The simplest case to consider is a candidate IV which is
     // narrower than the trip count (and thus original IV), but this can
     // also happen due to non-unit strides on the candidate IVs.
-    // TODO: This check should be replaceable with PostInc->hasNoSelfWrap(),
-    // but in practice we appear to be missing inference for cases we should
-    // be able to catch.
-    ConstantRange StepCR = SE.getSignedRange(AddRec->getStepRecurrence(SE));
-    ConstantRange BECountCR = SE.getUnsignedRange(BECount);
-    unsigned NoOverflowBitWidth = BECountCR.getActiveBits() + StepCR.getMinSignedBits();
-    unsigned ARBitWidth = SE.getTypeSizeInBits(AddRec->getType());
-    if (NoOverflowBitWidth > ARBitWidth)
+    if (!AddRec->hasNoSelfWrap())
       continue;
 
     const SCEVAddRecExpr *PostInc = AddRec->getPostIncExpr(SE);
     const SCEV *TermValueSLocal = PostInc->evaluateAtIteration(BECount, SE);
     if (!Expander.isSafeToExpand(TermValueSLocal)) {
       LLVM_DEBUG(
           dbgs() << "Is not safe to expand terminating value for phi node" << PN
                  << "\n");

llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll

 ; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
 ; CHECK:       %s1 = add i32 %phi1, %is1
 ; CHECK-NEXT:  -->  {(6 + (3 * %a) + %b),+,7}<%loop1>
 ; CHECK:       %s2 = add i32 %is2, %phi4
 ; CHECK-NEXT:  -->  {(222 + %b),+,7}<%loop2>
 ; CHECK:       %s3 = add i32 %is1, %phi5
 ; CHECK-NEXT:  -->  {{{{}}(59 + (2 * %a) + %b),+,6}<%loop1>,+,2}<nw><%loop2>
 ; CHECK:       %s4 = add i32 %phi2, %is2
-; CHECK-NEXT:  -->  {{{{}}(159 + (2 * %b)),+,2}<%loop1>,+,6}<%loop2>
+; CHECK-NEXT:  -->  {{{{}}(159 + (2 * %b)),+,2}<nw><%loop1>,+,6}<%loop2>
 ; CHECK:       %s5 = add i32 %is1, %is2
 ; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
 ; CHECK:       %s6 = add i32 %is2, %is1
 ; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
 
 entry:
   br label %loop1
 

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

 exit:
   ret i32 0
 }
 
 define i32 @ptr_induction_ult_1(ptr %a, ptr %b) {
 ; CHECK-LABEL: 'ptr_induction_ult_1'
 ; CHECK-NEXT:  Classifying expressions for: @ptr_induction_ult_1
 ; CHECK-NEXT:    %ptr.iv = phi ptr [ %ptr.iv.next, %loop ], [ %a, %entry ]
-; CHECK-NEXT:    --> {%a,+,4}<%loop> U: full-set S: full-set Exits: %a LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {%a,+,4}<nw><%loop> U: full-set S: full-set Exits: %a LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %ptr.iv.next = getelementptr i32, ptr %ptr.iv, i64 1
-; CHECK-NEXT:    --> {(4 + %a),+,4}<%loop> U: full-set S: full-set Exits: (4 + %a) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(4 + %a),+,4}<nw><%loop> U: full-set S: full-set Exits: (4 + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @ptr_induction_ult_1
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 0
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 0
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 0
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
loop:
   %ptr.iv.next = getelementptr i32, ptr %ptr.iv, i64 1
   %exitcond = icmp eq ptr %ptr.iv, %b
   br i1 %exitcond, label %exit, label %loop
 
 exit:
   ret i32 0
 }
 
-; TODO: The pointer induction variable can be implied No Self Wrap.
 define void @gep_addrec_nw(ptr %a) {
 ; CHECK-LABEL: 'gep_addrec_nw'
 ; CHECK-NEXT:  Classifying expressions for: @gep_addrec_nw
 ; CHECK-NEXT:    %lsr.iv1 = phi ptr [ %uglygep2, %for.body ], [ %a, %entry ]
-; CHECK-NEXT:    --> {%a,+,4}<%for.body> U: full-set S: full-set Exits: (1512 + %a) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    --> {%a,+,4}<nw><%for.body> U: full-set S: full-set Exits: (1512 + %a) LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %lsr.iv = phi i64 [ %lsr.iv.next, %for.body ], [ 379, %entry ]
 ; CHECK-NEXT:    --> {379,+,-1}<nsw><%for.body> U: [1,380) S: [1,380) Exits: 1 LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %lsr.iv.next = add nsw i64 %lsr.iv, -1
 ; CHECK-NEXT:    --> {378,+,-1}<nsw><%for.body> U: [0,379) S: [0,379) Exits: 0 LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %uglygep2 = getelementptr i8, ptr %lsr.iv1, i64 4
-; CHECK-NEXT:    --> {(4 + %a),+,4}<%for.body> U: full-set S: full-set Exits: (1516 + %a) LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    --> {(4 + %a),+,4}<nw><%for.body> U: full-set S: full-set Exits: (1516 + %a) LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @gep_addrec_nw
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is 378
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 378
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is 378
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 378
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 379
 ;

llvm/test/Transforms/LoopRotate/pr51981-scev-problem.ll

 ; %div2102 to i16).
 ;
 ; CHECK-SCEV: Classifying expressions for: @test_function
 ; CHECK-SCEV:   %wide = load i32, ptr @offset, align 1
 ; CHECK-SCEV:   -->  %wide U: full-set S: full-set          Exits: <<Unknown>>              LoopDispositions: { %loop.outer.header: Variant, %loop.inner: Invariant }
 ; CHECK-SCEV:   %narrow = trunc i32 %wide to i16
 ; CHECK-SCEV:   -->  (trunc i32 %wide to i16) U: full-set S: full-set               Exits: <<Unknown>>              LoopDispositions: { %loop.outer.header: Variant, %loop.inner: Invariant }
 ; CHECK-SCEV:   %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
-; CHECK-SCEV:   -->  {(trunc i32 %wide to i16),+,1}<%loop.inner> U: full-set S: full-set           Exits: (-1 + (700 umax (1 + (trunc i32 %wide to i16))))               LoopDispositions: { %loop.inner: Computable, %loop.outer.header: Variant }
+; CHECK-SCEV:   -->  {(trunc i32 %wide to i16),+,1}<nw><%loop.inner> U: full-set S: full-set           Exits: (-1 + (700 umax (1 + (trunc i32 %wide to i16))))               LoopDispositions: { %loop.inner: Computable, %loop.outer.header: Variant }
 ;
 ; CHECK-SCEV: Classifying expressions for: @test_function
 ; CHECK-SCEV:   %wide1 = load i32, ptr @offset, align 1
 ; CHECK-SCEV:   -->  %wide1 U: full-set S: full-set
 ; CHECK-SCEV:   %wide2 = phi i32 [ %wide1, %loop.inner.ph.lr.ph ], [ %wide, %loop.outer.latch ]
 ; CHECK-SCEV:   -->  %wide2 U: full-set S: full-set         Exits: <<Unknown>>              LoopDispositions: { %loop.inner.ph: Variant, %loop.inner: Invariant }
 ; CHECK-SCEV:   %narrow = trunc i32 %wide2 to i16
 ; CHECK-SCEV:   -->  (trunc i32 %wide2 to i16) U: full-set S: full-set               Exits: <<Unknown>>              LoopDispositions: { %loop.inner.ph: Variant, %loop.inner: Invariant }
 ; CHECK-SCEV:   %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
-; CHECK-SCEV:   -->  {(trunc i32 %wide2 to i16),+,1}<%loop.inner> U: full-set S: full-set           Exits: (-1 + (700 umax (1 + (trunc i32 %wide2 to i16))))               LoopDispositions: { %loop.inner: Computable, %loop.inner.ph: Variant }
+; CHECK-SCEV:   -->  {(trunc i32 %wide2 to i16),+,1}<nw><%loop.inner> U: full-set S: full-set           Exits: (-1 + (700 umax (1 + (trunc i32 %wide2 to i16))))               LoopDispositions: { %loop.inner: Computable, %loop.inner.ph: Variant }
 
 
 @offset = external dso_local global i32, align 1
 @array = internal global [11263 x i32] zeroinitializer, align 1
 
 define void @test_function(i1 %cond) {
 entry:
   br label %loop.outer.header

llvm/test/Transforms/LoopVersioning/lcssa.ll

 ; CHECK-NEXT:    [[LS1_20_PROMOTED:%.*]] = load i8*, i8** [[LS1_20:%.*]], align 8
 ; CHECK-NEXT:    [[LS2_21_PROMOTED:%.*]] = load i8*, i8** [[LS2_21:%.*]], align 8
 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, i8* [[LS1_20_PROMOTED]], i64 -1
 ; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i8, i8* [[LS1_20_PROMOTED]], i64 1
 ; CHECK-NEXT:    [[SCEVGEP2:%.*]] = getelementptr i8, i8* [[LS2_21_PROMOTED]], i64 1
 ; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ult i8* [[SCEVGEP]], [[SCEVGEP2]]
 ; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ult i8* [[LS2_21_PROMOTED]], [[SCEVGEP1]]
 ; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
-; CHECK-NEXT:    [[SCEVGEP3:%.*]] = getelementptr i8, i8* [[LS1_20_PROMOTED]], i64 -1
 ; CHECK-NEXT:    br i1 [[FOUND_CONFLICT]], label %bb1.ph.lver.orig, label %bb1.ph
 ; CHECK:       bb1.ph.lver.orig:
 ;
 bb1.ph:
   %ls1.20.promoted = load i8*, i8** %ls1.20
   %ls2.21.promoted = load i8*, i8** %ls2.21
   br label %bb1