[SCEV] Make use of non-null pointers for range calculation

[nikic]

Summary

We know that certain pointers (e.g. non-extern-weak globals or allocas in default address space) are not null, in which case the lowest address they can be allocated at is their alignment.

This allows us to calculate better exit counts for loops that have an additional null check in the guarding condition (see @alloca_icmp_null_exit_count).

[arichardson]

llvm/test/Analysis/ScalarEvolution/alloca.ll

27

Not related to this patch but I wonder if we could add a way to treat address spaces other than zero as also having non null allocas. For example for the CHERI targets AS200 has almost exactly the same semantics as as0 (other than pointers having additional metadata) and these AS0 only optimizations result in worse codegen. Maybe the allocas can be null should be opt-in rather than the default?

[nikic]

llvm/test/Analysis/ScalarEvolution/alloca.ll

27

Sure -- you would have to add a new per-AS DataLayout property for this.

[aeubanks]

lgtm

llvm/lib/Analysis/ScalarEvolution.cpp

if (U->getType()->isPointerTy() && SignHint == HINT_RANGE_UNSIGNED) {
         // alignment, the last possible start value is the next lowest multiple
         // of the alignment. Note: The computations below cannot overflow,
         // because if they would there's no possible start address for the
         // object.
         APInt MaxVal = APInt::getMaxValue(BitWidth) - APInt(BitWidth, ObjSize);
         uint64_t Align = U->getValue()->getPointerAlignment(DL).value();
         uint64_t Rem = MaxVal.urem(Align);
         MaxVal -= APInt(BitWidth, Rem);
+        APInt MinVal = APInt::getZero(BitWidth);
+        if (llvm::isKnownNonZero(V, DL))
+          MinVal = Align;
         ConservativeResult = ConservativeResult.intersectWith(
-            {ConservativeResult.getUnsignedMin(), MaxVal + 1}, RangeType);
+            {MinVal, MaxVal + 1}, RangeType);
       }
     }
 
     // A range of Phi is a subset of union of all ranges of its input.
     if (PHINode *Phi = dyn_cast<PHINode>(V)) {
       // Make sure that we do not run over cycled Phis.
       if (PendingPhiRanges.insert(Phi).second) {
         ConstantRange RangeFromOps(BitWidth, /*isFullSet=*/false);

llvm/test/Analysis/ScalarEvolution/alloca.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
 
 define i64 @alloca_non_null() {
 ; CHECK-LABEL: 'alloca_non_null'
 ; CHECK-NEXT:  Classifying expressions for: @alloca_non_null
 ; CHECK-NEXT:    %alloca = alloca i32, align 4
-; CHECK-NEXT:    --> %alloca U: [0,-7) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> %alloca U: [4,-7) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %int = ptrtoint ptr %alloca to i64
-; CHECK-NEXT:    --> (ptrtoint ptr %alloca to i64) U: [0,-7) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> (ptrtoint ptr %alloca to i64) U: [4,-7) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:  Determining loop execution counts for: @alloca_non_null
 ;
   %alloca = alloca i32, align 4
   %int = ptrtoint ptr %alloca to i64
   ret i64 %int
 }
 
 define i64 @alloca_maybe_null() {
 ; CHECK-LABEL: 'alloca_maybe_null'
 ; CHECK-NEXT:  Classifying expressions for: @alloca_maybe_null
 ; CHECK-NEXT:    %alloca = alloca i32, align 4, addrspace(1)
 ; CHECK-NEXT:    --> %alloca U: [0,-7) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %int = ptrtoint ptr addrspace(1) %alloca to i64
 ; CHECK-NEXT:    --> (ptrtoint ptr addrspace(1) %alloca to i64) U: [0,-7) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:  Determining loop execution counts for: @alloca_maybe_null
 ;
   %alloca = alloca i32, align 4, addrspace(1)
   %int = ptrtoint ptr addrspace(1) %alloca to i64
   ret i64 %int
 }
 
 define void @alloca_icmp_null_exit_count() {
 ; CHECK-LABEL: 'alloca_icmp_null_exit_count'
 ; CHECK-NEXT:  Classifying expressions for: @alloca_icmp_null_exit_count
 ; CHECK-NEXT:    %alloca = alloca [3 x i32], align 4
-; CHECK-NEXT:    --> %alloca U: [0,-15) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> %alloca U: [4,-15) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %alloca.end = getelementptr inbounds i32, ptr %alloca, i64 3
-; CHECK-NEXT:    --> (12 + %alloca)<nuw> U: [12,-3) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> (12 + %alloca)<nuw> U: [16,-3) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %ptr = phi ptr [ %ptr.next, %loop ], [ %alloca, %entry ]
-; CHECK-NEXT:    --> {%alloca,+,4}<nuw><%loop> U: [0,-7) S: [-9223372036854775808,9223372036854775805) Exits: ((4 * (2 umin ((-4 + (-1 * (ptrtoint ptr %alloca to i64))) /u 4)))<nuw><nsw> + %alloca) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {%alloca,+,4}<nuw><%loop> U: [4,-7) S: [-9223372036854775808,9223372036854775805) Exits: (8 + %alloca)<nuw> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %ptr.next = getelementptr i32, ptr %ptr, i64 1
-; CHECK-NEXT:    --> {(4 + %alloca)<nuw>,+,4}<nuw><%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * (2 umin ((-4 + (-1 * (ptrtoint ptr %alloca to i64))) /u 4)))<nuw><nsw> + %alloca) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(4 + %alloca)<nuw>,+,4}<nuw><%loop> U: [8,-3) S: [-9223372036854775808,9223372036854775805) Exits: (12 + %alloca)<nuw> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %and = and i1 %cmp1, %cmp2
 ; CHECK-NEXT:    --> (%cmp2 umin %cmp1) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @alloca_icmp_null_exit_count
-; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin ((-4 + (-1 * (ptrtoint ptr %alloca to i64))) /u 4))
+; CHECK-NEXT:  Loop %loop: backedge-taken count is 2
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 2
-; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (2 umin ((-4 + (-1 * (ptrtoint ptr %alloca to i64))) /u 4))
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 umin ((-4 + (-1 * (ptrtoint ptr %alloca to i64))) /u 4))
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 2
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 2
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %loop: Trip multiple is 1
+; CHECK:       Loop %loop: Trip multiple is 3
 ;
 entry:
   %alloca = alloca [3 x i32], align 4
   %alloca.end = getelementptr inbounds i32, ptr %alloca, i64 3
   br label %loop
 
 loop:
   %ptr = phi ptr [ %ptr.next, %loop ], [ %alloca, %entry ]

llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll

 ; CHECK-NEXT:  Classifying expressions for: @f
 ; CHECK-NEXT:    %storemerge23 = phi i32 [ 3, %entry ], [ %dec16, %for.inc13.3 ]
 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%outer.loop> U: [1,4) S: [1,4) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Computable, %for.cond6: Invariant, %inner.loop: Invariant }
 ; CHECK-NEXT:    %storemerge1921 = phi i32 [ 3, %outer.loop ], [ %dec, %for.end ]
 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%for.cond6> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %idxprom20 = zext i32 %storemerge1921 to i64
 ; CHECK-NEXT:    --> (zext i32 {3,+,-1}<nsw><%for.cond6> to i64) U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %arrayidx7 = getelementptr inbounds [1 x [4 x i16]], ptr @__const.f.g, i64 0, i64 0, i64 %idxprom20
-; CHECK-NEXT:    --> ((2 * (zext i32 {3,+,-1}<nsw><%for.cond6> to i64))<nuw><nsw> + @__const.f.g)<nuw> U: [6,-3) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
+; CHECK-NEXT:    --> ((2 * (zext i32 {3,+,-1}<nsw><%for.cond6> to i64))<nuw><nsw> + @__const.f.g)<nuw> U: [8,-3) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %i = load i16, ptr %arrayidx7, align 2
 ; CHECK-NEXT:    --> %i U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond6: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %storemerge1822.lcssa.ph = phi i32 [ 0, %for.cond6 ]
 ; CHECK-NEXT:    --> 0 U: [0,1) S: [0,1)
 ; CHECK-NEXT:    %storemerge1822.lcssa.ph32 = phi i32 [ 3, %inner.loop ]
 ; CHECK-NEXT:    --> 3 U: [3,4) S: [3,4)
 ; CHECK-NEXT:    %storemerge1822.lcssa = phi i32 [ %storemerge1822.lcssa.ph, %if.end.loopexit ], [ %storemerge1822.lcssa.ph32, %if.end.loopexit31 ]
 ; CHECK-NEXT:    --> %storemerge1822.lcssa U: [0,4) S: [0,4)
 ; CHECK-NEXT:    %i1 = load i32, ptr @e, align 4
 ; CHECK-NEXT:    --> %i1 U: full-set S: full-set
 ; CHECK-NEXT:    %i2 = load volatile i32, ptr @b, align 4
 ; CHECK-NEXT:    --> %i2 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond6: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %dec = add nsw i32 %storemerge1921, -1
 ; CHECK-NEXT:    --> {2,+,-1}<nsw><%for.cond6> U: [2,3) S: [2,3) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %inc.lcssa.lcssa = phi i32 [ 4, %for.inc13.3 ]
 ; CHECK-NEXT:    --> 4 U: [4,5) S: [4,5)
 ; CHECK-NEXT:    %retval.0 = phi i32 [ %i1, %if.end ], [ 0, %cleanup.loopexit ]
 ; CHECK-NEXT:    --> %retval.0 U: full-set S: full-set
 ; CHECK-NEXT:    %storemerge1921.3 = phi i32 [ 3, %for.end ], [ %dec.3, %for.end.3 ]
 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%inner.loop> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %idxprom20.3 = zext i32 %storemerge1921.3 to i64
 ; CHECK-NEXT:    --> (zext i32 {3,+,-1}<nsw><%inner.loop> to i64) U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %arrayidx7.3 = getelementptr inbounds [1 x [4 x i16]], ptr @__const.f.g, i64 0, i64 0, i64 %idxprom20.3
-; CHECK-NEXT:    --> ((2 * (zext i32 {3,+,-1}<nsw><%inner.loop> to i64))<nuw><nsw> + @__const.f.g)<nuw> U: [6,-3) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
+; CHECK-NEXT:    --> ((2 * (zext i32 {3,+,-1}<nsw><%inner.loop> to i64))<nuw><nsw> + @__const.f.g)<nuw> U: [8,-3) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %i7 = load i16, ptr %arrayidx7.3, align 2
 ; CHECK-NEXT:    --> %i7 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner.loop: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %i8 = load volatile i32, ptr @b, align 4
 ; CHECK-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner.loop: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %dec.3 = add nsw i32 %storemerge1921.3, -1
 ; CHECK-NEXT:    --> {2,+,-1}<nsw><%inner.loop> U: [2,3) S: [2,3) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %storemerge1921.lcssa25.3 = phi i32 [ %storemerge1921.3, %for.end.3 ]
 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%inner.loop> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Variant, %for.cond6: Variant, %inner.loop: Computable }

llvm/test/Analysis/ScalarEvolution/load.ll

 define i32 @test1() nounwind readnone {
 ; CHECK-LABEL: 'test1'
 ; CHECK-NEXT:  Classifying expressions for: @test1
 ; CHECK-NEXT:    %sum.04 = phi i32 [ 0, %entry ], [ %add2, %for.body ]
 ; CHECK-NEXT:    --> %sum.04 U: full-set S: full-set Exits: 2450 LoopDispositions: { %for.body: Variant }
 ; CHECK-NEXT:    %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,50) S: [0,50) Exits: 49 LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds [50 x i32], ptr @arr1, i32 0, i32 %i.03
-; CHECK-NEXT:    --> {@arr1,+,4}<nuw><%for.body> U: [0,-7) S: [-2147483648,2147483645) Exits: (196 + @arr1)<nuw> LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    --> {@arr1,+,4}<nuw><%for.body> U: [4,-7) S: [-2147483648,2147483645) Exits: (196 + @arr1)<nuw> LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %0 = load i32, ptr %arrayidx, align 4
 ; CHECK-NEXT:    --> %0 U: full-set S: full-set Exits: 50 LoopDispositions: { %for.body: Variant }
 ; CHECK-NEXT:    %arrayidx1 = getelementptr inbounds [50 x i32], ptr @arr2, i32 0, i32 %i.03
-; CHECK-NEXT:    --> {@arr2,+,4}<nuw><%for.body> U: [0,-7) S: [-2147483648,2147483645) Exits: (196 + @arr2)<nuw> LoopDispositions: { %for.body: Computable }
+; CHECK-NEXT:    --> {@arr2,+,4}<nuw><%for.body> U: [4,-7) S: [-2147483648,2147483645) Exits: (196 + @arr2)<nuw> LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %1 = load i32, ptr %arrayidx1, align 4
 ; CHECK-NEXT:    --> %1 U: full-set S: full-set Exits: 0 LoopDispositions: { %for.body: Variant }
 ; CHECK-NEXT:    %add = add i32 %0, %sum.04
 ; CHECK-NEXT:    --> (%0 + %sum.04) U: full-set S: full-set Exits: 2500 LoopDispositions: { %for.body: Variant }
 ; CHECK-NEXT:    %add2 = add i32 %add, %1
 ; CHECK-NEXT:    --> (%1 + %0 + %sum.04) U: full-set S: full-set Exits: 2500 LoopDispositions: { %for.body: Variant }
 ; CHECK-NEXT:    %inc = add nsw i32 %i.03, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,51) S: [1,51) Exits: 50 LoopDispositions: { %for.body: Computable }

llvm/test/Analysis/ScalarEvolution/nsw.ll

for.end:
   ret void
 }
 
 ; This test checks if no-wrap flags are propagated when folding {S,+,X}+T ==> {S+T,+,X}
 define void @test4(i32 %arg) {
 ; CHECK-LABEL: 'test4'
 ; CHECK-NEXT:  Classifying expressions for: @test4
 ; CHECK-NEXT:    %array = alloca [10 x i32], align 4
-; CHECK-NEXT:    --> %array U: [0,-43) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> %array U: [4,-43) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %index = phi i32 [ %inc5, %for.body ], [ %arg, %entry ]
 ; CHECK-NEXT:    --> {%arg,+,1}<nsw><%for.body> U: full-set S: full-set Exits: (-1 + (10 smax (1 + %arg)<nsw>))<nsw> LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %sub = add nsw i32 %index, -2
 ; CHECK-NEXT:    --> {(-2 + %arg)<nsw>,+,1}<nsw><%for.body> U: full-set S: full-set Exits: (-3 + (10 smax (1 + %arg)<nsw>))<nsw> LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %idxprom = sext i32 %sub to i64
 ; CHECK-NEXT:    --> {(-2 + (sext i32 %arg to i64))<nsw>,+,1}<nsw><%for.body> U: [-2147483650,4294967303) S: [-2147483650,4294967303) Exits: (-2 + (zext i32 (-1 + (-1 * %arg) + (10 smax (1 + %arg)<nsw>)) to i64) + (sext i32 %arg to i64)) LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds [10 x i32], ptr %array, i64 0, i64 %idxprom
 ; CHECK-NEXT:    --> {(-8 + (4 * (sext i32 %arg to i64))<nsw> + %array),+,4}<nw><%for.body> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (-8 + (4 * (zext i32 (-1 + (-1 * %arg) + (10 smax (1 + %arg)<nsw>)) to i64))<nuw><nsw> + (4 * (sext i32 %arg to i64))<nsw> + %array) LoopDispositions: { %for.body: Computable }

llvm/test/Analysis/ScalarEvolution/ptrtoint-global.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
 
 @glob.i32.align2 = global i32 zeroinitializer, align 2
 @glob.i32.align8 = global i32 zeroinitializer, align 8
 @glob.i32.align16 = global i32 zeroinitializer, align 16
 @array4xi32 = global [4 x i32] zeroinitializer, align 16
 
 define i64 @ptrtoint_align_2_size_4_add_5() {
 ; CHECK-LABEL: 'ptrtoint_align_2_size_4_add_5'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_2_size_4_add_5
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @glob.i32.align2 to i64), 5
-; CHECK-NEXT:    --> (5 + (ptrtoint ptr @glob.i32.align2 to i64))<nuw> U: [5,0) S: [5,0)
+; CHECK-NEXT:    --> (5 + (ptrtoint ptr @glob.i32.align2 to i64))<nuw> U: [7,0) S: [5,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_2_size_4_add_5
 ;
 entry:
   %add = add i64 ptrtoint (ptr @glob.i32.align2 to i64), 5
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_2_size_4_add_6() {
 ; CHECK-LABEL: 'ptrtoint_align_2_size_4_add_6'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_2_size_4_add_6
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @glob.i32.align2 to i64), 6
 ; CHECK-NEXT:    --> (6 + (ptrtoint ptr @glob.i32.align2 to i64)) U: [0,-1) S: [-9223372036854775808,9223372036854775807)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_2_size_4_add_6
 ;
 entry:
   %add = add i64 ptrtoint (ptr @glob.i32.align2 to i64), 6
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_8_size_4_add_7() {
 ; CHECK-LABEL: 'ptrtoint_align_8_size_4_add_7'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_8_size_4_add_7
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @glob.i32.align8 to i64), 7
-; CHECK-NEXT:    --> (7 + (ptrtoint ptr @glob.i32.align8 to i64))<nuw><nsw> U: [7,0) S: [-9223372036854775801,-9223372036854775808)
+; CHECK-NEXT:    --> (7 + (ptrtoint ptr @glob.i32.align8 to i64))<nuw><nsw> U: [15,0) S: [-9223372036854775801,-9223372036854775808)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_8_size_4_add_7
 ;
 entry:
   %add = add i64 ptrtoint (ptr @glob.i32.align8 to i64), 7
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_8_size_4_add_8() {
 ; CHECK-LABEL: 'ptrtoint_align_8_size_4_add_8'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_8_size_4_add_8
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @glob.i32.align8 to i64), 8
 ; CHECK-NEXT:    --> (8 + (ptrtoint ptr @glob.i32.align8 to i64)) U: [0,-7) S: [-9223372036854775808,9223372036854775801)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_8_size_4_add_8
 ;
 entry:
   %add = add i64 ptrtoint (ptr @glob.i32.align8 to i64), 8
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_16_size_4_add_15() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_4_add_15'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_4_add_15
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @glob.i32.align16 to i64), 15
-; CHECK-NEXT:    --> (15 + (ptrtoint ptr @glob.i32.align16 to i64))<nuw><nsw> U: [15,0) S: [-9223372036854775793,-9223372036854775808)
+; CHECK-NEXT:    --> (15 + (ptrtoint ptr @glob.i32.align16 to i64))<nuw><nsw> U: [31,0) S: [-9223372036854775793,-9223372036854775808)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_4_add_15
 ;
 entry:
   %add = add i64 ptrtoint (ptr @glob.i32.align16 to i64), 15
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_16_size_4_add_16() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_4_add_16'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_4_add_16
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @glob.i32.align16 to i64), 16
 ; CHECK-NEXT:    --> (16 + (ptrtoint ptr @glob.i32.align16 to i64)) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_4_add_16
 ;
 entry:
   %add = add i64 ptrtoint (ptr @glob.i32.align16 to i64), 16
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_16_size_16_add_16() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_16_add_16'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_16_add_16
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @array4xi32 to i64), 16
-; CHECK-NEXT:    --> (16 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [16,-15) S: [-9223372036854775808,9223372036854775793)
+; CHECK-NEXT:    --> (16 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [32,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_16_add_16
 ;
 entry:
   %add = add i64 ptrtoint (ptr @array4xi32 to i64), 16
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_16_size_16_add_31() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_16_add_31'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_16_add_31
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @array4xi32 to i64), 31
-; CHECK-NEXT:    --> (31 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [31,0) S: [31,0)
+; CHECK-NEXT:    --> (31 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [47,0) S: [31,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_16_add_31
 ;
 entry:
   %add = add i64 ptrtoint (ptr @array4xi32 to i64), 31
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_16_size_16_add_32() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_16_add_32'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_16_add_32
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @array4xi32 to i64), 32
 ; CHECK-NEXT:    --> (32 + (ptrtoint ptr @array4xi32 to i64)) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_16_add_32
 ;
 entry:
   %add = add i64 ptrtoint (ptr @array4xi32 to i64), 32
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_16_size_16_add_33() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_16_add_33'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_16_add_33
 ; CHECK-NEXT:    %add = add i64 ptrtoint (ptr @array4xi32 to i64), 33
-; CHECK-NEXT:    --> (33 + (ptrtoint ptr @array4xi32 to i64)) U: [33,2) S: [-9223372036854775775,-9223372036854775790)
+; CHECK-NEXT:    --> (33 + (ptrtoint ptr @array4xi32 to i64)) U: [49,2) S: [-9223372036854775775,-9223372036854775790)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_16_add_33
 ;
 entry:
   %add = add i64 ptrtoint (ptr @array4xi32 to i64), 33
   ret i64 %add
 }
 
 define i64 @ptrtoint_align_16_size_16_add_16_umax_sub() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_16_add_16_umax_sub'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_16_add_16_umax_sub
 ; CHECK-NEXT:    %add.16 = add i64 ptrtoint (ptr @array4xi32 to i64), 16
-; CHECK-NEXT:    --> (16 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [16,-15) S: [-9223372036854775808,9223372036854775793)
+; CHECK-NEXT:    --> (16 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [32,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:    %umax = call i64 @llvm.umax.i64(i64 ptrtoint (ptr @array4xi32 to i64), i64 %add.16)
-; CHECK-NEXT:    --> (16 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [16,-15) S: [-9223372036854775808,9223372036854775793)
+; CHECK-NEXT:    --> (16 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [32,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:    %add = add i64 %umax, 16
 ; CHECK-NEXT:    --> (32 + (ptrtoint ptr @array4xi32 to i64)) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:    %sub = sub i64 %add, ptrtoint (ptr @array4xi32 to i64)
 ; CHECK-NEXT:    --> 32 U: [32,33) S: [32,33)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_16_add_16_umax_sub
 ;
 entry:
   %add.16 = add i64 ptrtoint (ptr @array4xi32 to i64), 16
   %umax = call i64 @llvm.umax.i64(i64 ptrtoint (ptr @array4xi32 to i64), i64 %add.16)
   %add = add i64 %umax, 16
   %sub = sub i64 %add, ptrtoint (ptr @array4xi32 to i64)
   ret i64 %sub
 }
 
 define i64 @ptrtoint_align_16_size_16_add_31_umax_sub() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_16_add_31_umax_sub'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_16_add_31_umax_sub
 ; CHECK-NEXT:    %add.31 = add i64 ptrtoint (ptr @array4xi32 to i64), 31
-; CHECK-NEXT:    --> (31 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [31,0) S: [31,0)
+; CHECK-NEXT:    --> (31 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [47,0) S: [31,0)
 ; CHECK-NEXT:    %umax = call i64 @llvm.umax.i64(i64 ptrtoint (ptr @array4xi32 to i64), i64 %add.31)
-; CHECK-NEXT:    --> (31 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [31,0) S: [31,0)
+; CHECK-NEXT:    --> (31 + (ptrtoint ptr @array4xi32 to i64))<nuw> U: [47,0) S: [31,0)
 ; CHECK-NEXT:    %add = add i64 %umax, 16
-; CHECK-NEXT:    --> (47 + (ptrtoint ptr @array4xi32 to i64)) U: [47,16) S: [-9223372036854775761,-9223372036854775776)
+; CHECK-NEXT:    --> (47 + (ptrtoint ptr @array4xi32 to i64)) U: [63,16) S: [-9223372036854775761,-9223372036854775776)
 ; CHECK-NEXT:    %sub = sub i64 %add, ptrtoint (ptr @array4xi32 to i64)
 ; CHECK-NEXT:    --> 47 U: [47,48) S: [47,48)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_16_add_31_umax_sub
 ;
 entry:
   %add.31 = add i64 ptrtoint (ptr @array4xi32 to i64), 31
   %umax = call i64 @llvm.umax.i64(i64 ptrtoint (ptr @array4xi32 to i64), i64 %add.31)
   %add = add i64 %umax, 16
   %sub = sub i64 %add, ptrtoint (ptr @array4xi32 to i64)
   ret i64 %sub
 }
 
 define i64 @ptrtoint_align_16_size_16_add_32_umax_sub() {
 ; CHECK-LABEL: 'ptrtoint_align_16_size_16_add_32_umax_sub'
 ; CHECK-NEXT:  Classifying expressions for: @ptrtoint_align_16_size_16_add_32_umax_sub
 ; CHECK-NEXT:    %add.32 = add i64 ptrtoint (ptr @array4xi32 to i64), 32
 ; CHECK-NEXT:    --> (32 + (ptrtoint ptr @array4xi32 to i64)) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:    %umax = call i64 @llvm.umax.i64(i64 ptrtoint (ptr @array4xi32 to i64), i64 %add.32)
-; CHECK-NEXT:    --> ((32 + (ptrtoint ptr @array4xi32 to i64)) umax (ptrtoint ptr @array4xi32 to i64)) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
+; CHECK-NEXT:    --> ((32 + (ptrtoint ptr @array4xi32 to i64)) umax (ptrtoint ptr @array4xi32 to i64)) U: [16,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:    %add = add i64 %umax, 16
 ; CHECK-NEXT:    --> (16 + ((32 + (ptrtoint ptr @array4xi32 to i64)) umax (ptrtoint ptr @array4xi32 to i64))) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:    %sub = sub i64 %add, ptrtoint (ptr @array4xi32 to i64)
 ; CHECK-NEXT:    --> (16 + (-1 * (ptrtoint ptr @array4xi32 to i64)) + ((32 + (ptrtoint ptr @array4xi32 to i64)) umax (ptrtoint ptr @array4xi32 to i64))) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:  Determining loop execution counts for: @ptrtoint_align_16_size_16_add_32_umax_sub
 ;
 entry:
   %add.32 = add i64 ptrtoint (ptr @array4xi32 to i64), 32
   %umax = call i64 @llvm.umax.i64(i64 ptrtoint (ptr @array4xi32 to i64), i64 %add.32)
   %add = add i64 %umax, 16
   %sub = sub i64 %add, ptrtoint (ptr @array4xi32 to i64)
   ret i64 %sub
 }
 
 declare i64 @llvm.umax.i64(i64, i64)

llvm/test/Analysis/ScalarEvolution/sdiv.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s "-passes=print<scalar-evolution>" -disable-output 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"
 
 define dso_local void @_Z4loopi(i32 %width) local_unnamed_addr #0 {
 ; CHECK-LABEL: '_Z4loopi'
 ; CHECK-NEXT:  Classifying expressions for: @_Z4loopi
 ; CHECK-NEXT:    %storage = alloca [2 x i32], align 4
-; CHECK-NEXT:    --> %storage U: [0,-11) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> %storage U: [4,-11) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %0 = bitcast ptr %storage to ptr
-; CHECK-NEXT:    --> %storage U: [0,-11) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> %storage U: [4,-11) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.cond> U: [0,-2147483648) S: [0,-2147483648) Exits: %width LoopDispositions: { %for.cond: Computable }
 ; CHECK-NEXT:    %rem = sdiv i32 %i.0, 2
 ; CHECK-NEXT:    --> ({0,+,1}<nuw><nsw><%for.cond> /u 2) U: [0,1073741824) S: [0,1073741824) Exits: (%width /u 2) LoopDispositions: { %for.cond: Computable }
 ; CHECK-NEXT:    %idxprom = sext i32 %rem to i64
 ; CHECK-NEXT:    --> ({0,+,1}<nuw><nsw><%for.cond> /u 2) U: [0,2147483648) S: [0,2147483648) Exits: ((zext i32 %width to i64) /u 2) LoopDispositions: { %for.cond: Computable }
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds [2 x i32], ptr %storage, i64 0, i64 %idxprom
 ; CHECK-NEXT:    --> ((4 * ({0,+,1}<nuw><nsw><%for.cond> /u 2))<nuw><nsw> + %storage) U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: ((4 * ((zext i32 %width to i64) /u 2))<nuw><nsw> + %storage) LoopDispositions: { %for.cond: Computable }

llvm/test/Analysis/ScalarEvolution/srem.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s "-passes=print<scalar-evolution>" -disable-output 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"
 
 define dso_local void @_Z4loopi(i32 %width) local_unnamed_addr #0 {
 ; CHECK-LABEL: '_Z4loopi'
 ; CHECK-NEXT:  Classifying expressions for: @_Z4loopi
 ; CHECK-NEXT:    %storage = alloca [2 x i32], align 4
-; CHECK-NEXT:    --> %storage U: [0,-11) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> %storage U: [4,-11) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %0 = bitcast ptr %storage to ptr
-; CHECK-NEXT:    --> %storage U: [0,-11) S: [-9223372036854775808,9223372036854775805)
+; CHECK-NEXT:    --> %storage U: [4,-11) S: [-9223372036854775808,9223372036854775805)
 ; CHECK-NEXT:    %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.cond> U: [0,-2147483648) S: [0,-2147483648) Exits: %width LoopDispositions: { %for.cond: Computable }
 ; CHECK-NEXT:    %rem = srem i32 %i.0, 2
 ; CHECK-NEXT:    --> (zext i1 {false,+,true}<%for.cond> to i32) U: [0,2) S: [0,2) Exits: (zext i1 (trunc i32 %width to i1) to i32) LoopDispositions: { %for.cond: Computable }
 ; CHECK-NEXT:    %idxprom = sext i32 %rem to i64
 ; CHECK-NEXT:    --> (zext i1 {false,+,true}<%for.cond> to i64) U: [0,2) S: [0,2) Exits: (zext i1 (trunc i32 %width to i1) to i64) LoopDispositions: { %for.cond: Computable }
 ; CHECK-NEXT:    %arrayidx = getelementptr inbounds [2 x i32], ptr %storage, i64 0, i64 %idxprom
-; CHECK-NEXT:    --> ((4 * (zext i1 {false,+,true}<%for.cond> to i64))<nuw><nsw> + %storage) U: [0,-7) S: [-9223372036854775808,9223372036854775805) Exits: ((4 * (zext i1 (trunc i32 %width to i1) to i64))<nuw><nsw> + %storage) LoopDispositions: { %for.cond: Computable }
+; CHECK-NEXT:    --> ((4 * (zext i1 {false,+,true}<%for.cond> to i64))<nuw><nsw> + %storage) U: [4,-7) S: [-9223372036854775808,9223372036854775805) Exits: ((4 * (zext i1 (trunc i32 %width to i1) to i64))<nuw><nsw> + %storage) LoopDispositions: { %for.cond: Computable }
 ; CHECK-NEXT:    %1 = load i32, ptr %arrayidx, align 4
 ; CHECK-NEXT:    --> %1 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
 ; CHECK-NEXT:    %call = call i32 @_Z3adji(i32 %1)
 ; CHECK-NEXT:    --> %call U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
 ; CHECK-NEXT:    %2 = load i32, ptr %arrayidx, align 4
 ; CHECK-NEXT:    --> %2 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
 ; CHECK-NEXT:    %add = add nsw i32 %2, %call
 ; CHECK-NEXT:    --> (%2 + %call) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }