[SCEV] Support signed predicates in applyLoopGuards.

[fhahn]

Summary

This adds handling for signed predicates, similar to how unsigned
predicates are already handled.

[lebedev.ri]

Seems fine to me.

[nikic]

LGTM

[leonardchan]

Hi. It looks like this is causing the polly test failure we're seeing on our builders (https://luci-milo.appspot.com/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8843641688849975440?). Could you take a look and send out a fix or revert? Thanks.

******************** TEST 'Polly :: ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   opt  -polly-process-unprofitable  -polly-remarks-minimal  -polly-use-llvm-names  -polly-import-jscop-dir=/b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo  -polly-codegen-verify  -analyze -polly-detect-fortran-arrays  -polly-scops -polly-allow-nonaffine -polly-invariant-load-hoisting < /b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll | FileCheck /b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll
--
Exit Code: 1

Command Output (stderr):
--
/b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll:68:10: error: CHECK: expected string not found in input
; CHECK: MayWriteAccess := [Reduction Type: NONE] [Fortran array descriptor: xs] [Scalar: 0]
         ^
<stdin>:1:1: note: scanning from here
Printing analysis 'Polly - Create polyhedral description of Scops' for region: '6 => return.loopexit' in function 'testfunc':
^
<stdin>:46:3: note: possible intended match here
 MustWriteAccess := [Reduction Type: NONE] [Fortran array descriptor: xs] [Scalar: 0]
  ^

Input file: <stdin>
Check file: /b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
            1: Printing analysis 'Polly - Create polyhedral description of Scops' for region: '6 => return.loopexit' in function 'testfunc': 
check:68'0     X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
            2: Invalid Scop! 
check:68'0     ~~~~~~~~~~~~~~
            3: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry.split => return' in function 'testfunc': 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            4:  Function: testfunc 
check:68'0     ~~~~~~~~~~~~~~~~~~~~
            5:  Region: %entry.split---%return 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            6:  Max Loop Depth: 1 
check:68'0     ~~~~~~~~~~~~~~~~~~~
            .
            .
            .
           41:  Stmt_6 
check:68'0     ~~~~~~~~
           42:  Domain := 
check:68'0     ~~~~~~~~~~~
           43:  [tmp6, p_1, MemRef_tmp5_fortranarr_size] -> { Stmt_6[i0] : 0 <= i0 < tmp6 }; 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           44:  Schedule := 
check:68'0     ~~~~~~~~~~~~~
           45:  [tmp6, p_1, MemRef_tmp5_fortranarr_size] -> { Stmt_6[i0] -> [i0] }; 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           46:  MustWriteAccess := [Reduction Type: NONE] [Fortran array descriptor: xs] [Scalar: 0] 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
check:68'1       ?                                                                                    possible intended match
           47:  [tmp6, p_1, MemRef_tmp5_fortranarr_size] -> { Stmt_6[i0] -> MemRef_tmp5[i0, 0] }; 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           48:  } 
check:68'0     ~~~
           49: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'testfunc': 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           50: Invalid Scop! 
check:68'0     ~~~~~~~~~~~~~~
>>>>>>

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 
********************
Failed Tests (1):
  Polly :: ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll

[lebedev.ri]

In D104732#2836564, @leonardchan wrote:

Hi. It looks like this is causing the polly test failure we're seeing on our builders (https://luci-milo.appspot.com/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8843641688849975440?). Could you take a look and send out a fix or revert? Thanks.

******************** TEST 'Polly :: ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   opt  -polly-process-unprofitable  -polly-remarks-minimal  -polly-use-llvm-names  -polly-import-jscop-dir=/b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo  -polly-codegen-verify  -analyze -polly-detect-fortran-arrays  -polly-scops -polly-allow-nonaffine -polly-invariant-load-hoisting < /b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll | FileCheck /b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll
--
Exit Code: 1

Command Output (stderr):
--
/b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll:68:10: error: CHECK: expected string not found in input
; CHECK: MayWriteAccess := [Reduction Type: NONE] [Fortran array descriptor: xs] [Scalar: 0]
         ^
<stdin>:1:1: note: scanning from here
Printing analysis 'Polly - Create polyhedral description of Scops' for region: '6 => return.loopexit' in function 'testfunc':
^
<stdin>:46:3: note: possible intended match here
 MustWriteAccess := [Reduction Type: NONE] [Fortran array descriptor: xs] [Scalar: 0]
  ^

Input file: <stdin>
Check file: /b/s/w/ir/x/w/llvm-project/polly/test/ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll

-dump-input=help explains the following input dump.

Input was:
<<<<<<
            1: Printing analysis 'Polly - Create polyhedral description of Scops' for region: '6 => return.loopexit' in function 'testfunc': 
check:68'0     X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
            2: Invalid Scop! 
check:68'0     ~~~~~~~~~~~~~~
            3: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry.split => return' in function 'testfunc': 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            4:  Function: testfunc 
check:68'0     ~~~~~~~~~~~~~~~~~~~~
            5:  Region: %entry.split---%return 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            6:  Max Loop Depth: 1 
check:68'0     ~~~~~~~~~~~~~~~~~~~
            .
            .
            .
           41:  Stmt_6 
check:68'0     ~~~~~~~~
           42:  Domain := 
check:68'0     ~~~~~~~~~~~
           43:  [tmp6, p_1, MemRef_tmp5_fortranarr_size] -> { Stmt_6[i0] : 0 <= i0 < tmp6 }; 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           44:  Schedule := 
check:68'0     ~~~~~~~~~~~~~
           45:  [tmp6, p_1, MemRef_tmp5_fortranarr_size] -> { Stmt_6[i0] -> [i0] }; 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           46:  MustWriteAccess := [Reduction Type: NONE] [Fortran array descriptor: xs] [Scalar: 0] 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
check:68'1       ?                                                                                    possible intended match
           47:  [tmp6, p_1, MemRef_tmp5_fortranarr_size] -> { Stmt_6[i0] -> MemRef_tmp5[i0, 0] }; 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           48:  } 
check:68'0     ~~~
           49: Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'entry => <Function Return>' in function 'testfunc': 
check:68'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           50: Invalid Scop! 
check:68'0     ~~~~~~~~~~~~~~
>>>>>>

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 
********************
Failed Tests (1):
  Polly :: ScopInfo/fortran_array_param_nonmalloc_nonvectored.ll

I'm pretty sure polly is documented as not being the first-tier project, and is excluded from being the reason for reverts.
If i'm wrong i would like to be corrected.

[fhahn]

In D104732#2836564, @leonardchan wrote:

Hi. It looks like this is causing the polly test failure we're seeing on our builders (https://luci-milo.appspot.com/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8843641688849975440?). Could you take a look and send out a fix or revert? Thanks.

Thanks for the heads-up. It looks like the polly test just needs updating. I won't be able to do that in the next 12 hours or so. I'm not sure about the policy with respect to Polly, but if it is blocking you, it would be great if you could revert it in the meantime.

[Meinersbur]

In D104732#2836630, @lebedev.ri wrote:

I'm pretty sure polly is documented as not being the first-tier project, and is excluded from being the reason for reverts.
If i'm wrong i would like to be corrected.

I hereby correct you.

It was originally proposed by Renato, but in a followup [2] it is made clear that "we should not break it" [3].

[1] https://lists.llvm.org/pipermail/llvm-dev/2020-November/146337.html
[2] https://lists.llvm.org/pipermail/llvm-dev/2020-November/146349.html
[3] https://lists.llvm.org/pipermail/llvm-dev/2020-November/146357.html

In D104732#2836854, @fhahn wrote:

Thanks for the heads-up. It looks like the polly test just needs updating. I won't be able to do that in the next 12 hours or so. I'm not sure about the policy with respect to Polly, but if it is blocking you, it would be great if you could revert it in the meantime.

Fixed in https://reviews.llvm.org/rG84046ebd9543d60832d9a580bcbe2e3e5acc3217

[fhahn]

In D104732#2836961, @Meinersbur wrote:

In D104732#2836630, @lebedev.ri wrote:

I'm pretty sure polly is documented as not being the first-tier project, and is excluded from being the reason for reverts.
If i'm wrong i would like to be corrected.

I hereby correct you.

It was originally proposed by Renato, but in a followup [2] it is made clear that "we should not break it" [3].

[1] https://lists.llvm.org/pipermail/llvm-dev/2020-November/146337.html
[2] https://lists.llvm.org/pipermail/llvm-dev/2020-November/146349.html
[3] https://lists.llvm.org/pipermail/llvm-dev/2020-November/146357.html

In D104732#2836854, @fhahn wrote:

Thanks for the heads-up. It looks like the polly test just needs updating. I won't be able to do that in the next 12 hours or so. I'm not sure about the policy with respect to Polly, but if it is blocking you, it would be great if you could revert it in the meantime.

Fixed in https://reviews.llvm.org/rG84046ebd9543d60832d9a580bcbe2e3e5acc3217

Thank you very much Michael!

llvm/lib/Analysis/ScalarEvolution.cpp

auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,
     if (!LHSUnknown || containsAddRecurrence(RHS))
       return;
 
     // Check whether LHS has already been rewritten. In that case we want to
     // chain further rewrites onto the already rewritten value.
     auto I = RewriteMap.find(LHSUnknown->getValue());
     const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHS;
     const SCEV *RewrittenRHS = nullptr;
-    // TODO: use information from more predicates.
     switch (Predicate) {
     case CmpInst::ICMP_ULT:
       RewrittenRHS =
           getUMinExpr(RewrittenLHS, getMinusSCEV(RHS, getOne(RHS->getType())));
       break;
+    case CmpInst::ICMP_SLT:
+      RewrittenRHS =
+          getSMinExpr(RewrittenLHS, getMinusSCEV(RHS, getOne(RHS->getType())));
+      break;
     case CmpInst::ICMP_ULE:
       RewrittenRHS = getUMinExpr(RewrittenLHS, RHS);
       break;
+    case CmpInst::ICMP_SLE:
+      RewrittenRHS = getSMinExpr(RewrittenLHS, RHS);
+      break;
     case CmpInst::ICMP_UGT:
       RewrittenRHS =
           getUMaxExpr(RewrittenLHS, getAddExpr(RHS, getOne(RHS->getType())));
       break;
+    case CmpInst::ICMP_SGT:
+      RewrittenRHS =
+          getSMaxExpr(RewrittenLHS, getAddExpr(RHS, getOne(RHS->getType())));
+      break;
     case CmpInst::ICMP_UGE:
       RewrittenRHS = getUMaxExpr(RewrittenLHS, RHS);
       break;
+    case CmpInst::ICMP_SGE:
+      RewrittenRHS = getSMaxExpr(RewrittenLHS, RHS);
+      break;
     case CmpInst::ICMP_EQ:
       if (isa<SCEVConstant>(RHS))
         RewrittenRHS = RHS;
       break;
     case CmpInst::ICMP_NE:
       if (isa<SCEVConstant>(RHS) &&
           cast<SCEVConstant>(RHS)->getValue()->isNullValue())
         RewrittenRHS = getUMaxExpr(RewrittenLHS, getOne(RHS->getType()));

llvm/test/Analysis/Delinearization/a.ll

 ; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s
 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 ;
 ; void foo(long n, long m, long o, int A[n][m][o]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[2*i+3][3*j-4][5*k+7] = 1;
 ; }
 
 ; AddRec: {{{(28 + (4 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(12 * %o)}<%for.j>,+,20}<%for.k>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 4 bytes.
-; CHECK: ArrayRef[{3,+,2}<nw><%for.i>][{-4,+,3}<nw><%for.j>][{7,+,5}<nw><%for.k>]
+; CHECK: ArrayRef[{3,+,2}<nuw><%for.i>][{-4,+,3}<nw><%for.j>][{7,+,5}<nw><%for.k>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, i32* nocapture %A) #0 {
 entry:
   %cmp32 = icmp sgt i64 %n, 0
   br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end17
 
 for.cond1.preheader.lr.ph:                        ; preds = %entry
   %cmp230 = icmp sgt i64 %m, 0

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

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

 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ %i, %entry ]
 ; CHECK-NEXT:    --> {%i,+,1}<nuw><nsw><%loop> U: full-set S: full-set Exits: 17 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {((4 * %i) + %a),+,4}<nw><%loop> U: full-set S: full-set Exits: (68 + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
 ; CHECK-NEXT:    --> {(1 + %i),+,1}<nuw><nsw><%loop> U: full-set S: full-set Exits: 18 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_slt_sgt_2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (17 + (-1 * %i))
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 12
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (17 + (-1 * %i))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.0 = icmp slt i64 %i, 16
   %c.1 = icmp sgt i64 %i, 4
   %and = and i1 %c.0, %c.1

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

 ; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %loop ], [ %i, %entry ]
 ; CHECK-NEXT:    --> {%i,+,1}<nuw><nsw><%loop> U: full-set S: full-set Exits: 17 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {((4 * %i) + %a),+,4}<nw><%loop> U: full-set S: full-set Exits: (68 + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
 ; CHECK-NEXT:    --> {(1 + %i),+,1}<nuw><nsw><%loop> U: full-set S: full-set Exits: 18 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_sle_sge_2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (17 + (-1 * %i))
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 13
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (17 + (-1 * %i))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %c.0 = icmp sle i64 %i, 16
   %c.1 = icmp sge i64 %i, 4
   %and = and i1 %c.0, %c.1

llvm/test/Analysis/ScalarEvolution/max-trip-count-address-space.ll

for.cond.for.end_crit_edge:                       ; preds = %for.body
   br label %for.end
 
 for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @test
 ; CHECK-NEXT: backedge-taken count is
-; CHECK-NEXT: max backedge-taken count is 4294967294
+; CHECK-NEXT: max backedge-taken count is 2147483646

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

for.cond.for.end_crit_edge:                       ; preds = %for.body
   br label %for.end
 
 for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
   ret void
 }
 
 ; CHECK: Determining loop execution counts for: @test
 ; CHECK-NEXT: backedge-taken count is
-; CHECK-NEXT: max backedge-taken count is 4294967294
+; CHECK-NEXT: max backedge-taken count is 2147483646
 
 ; PR19799: Indvars miscompile due to an incorrect max backedge taken count from SCEV.
 ; CHECK-LABEL: @pr19799
 ; CHECK: Loop %for.body.i: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK: Loop %for.body.i: max backedge-taken count is 1
 @a = common global i32 0, align 4
 
 define i32 @pr19799() {

llvm/test/Analysis/ScalarEvolution/sext-mul.ll

 ; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution | FileCheck %s
 ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 ; CHECK: %tmp9 = shl i64 %tmp8, 33
 ; CHECK-NEXT: --> {{.*}} Exits: (-8589934592 + (8589934592 * (zext i32 %arg2 to i64)))
 ; CHECK: %tmp10 = ashr exact i64 %tmp9, 32
 ; CHECK-NEXT: --> {{.*}} Exits: (sext i32 (-2 + (2 * %arg2)) to i64)
 ; CHECK: %tmp11 = getelementptr inbounds i32, i32* %arg, i64 %tmp10
 ; CHECK-NEXT: --> {{.*}} Exits: ((4 * (sext i32 (-2 + (2 * %arg2)) to i64))<nsw> + %arg)
 ; CHECK:  %tmp14 = or i64 %tmp10, 1
 ; CHECK-NEXT: --> {{.*}} Exits: (1 + (sext i32 (-2 + (2 * %arg2)) to i64))<nuw><nsw>
 ; CHECK: %tmp15 = getelementptr inbounds i32, i32* %arg, i64 %tmp14
 ; CHECK-NEXT: --> {{.*}} Exits: (4 + (4 * (sext i32 (-2 + (2 * %arg2)) to i64))<nsw> + %arg)
 ; CHECK:Loop %bb7: backedge-taken count is (-1 + (zext i32 %arg2 to i64))<nsw>
-; CHECK-NEXT:Loop %bb7: max backedge-taken count is 4294967294
+; CHECK-NEXT:Loop %bb7: max backedge-taken count is 2147483646
 ; CHECK-NEXT:Loop %bb7: Predicated backedge-taken count is (-1 + (zext i32 %arg2 to i64))<nsw>
 
 define void @foo(i32* nocapture %arg, i32 %arg1, i32 %arg2) {
 bb:
   %tmp = icmp sgt i32 %arg2, 0
   br i1 %tmp, label %bb3, label %bb6
 
 bb3:                                              ; preds = %bb
bb7:                                              ; preds = %bb7, %bb3
   br i1 %tmp19, label %bb5, label %bb7
 }
 
 ; CHECK: %t10 = ashr exact i128 %t9, 1
 ; CHECK-NEXT: --> {{.*}} Exits: (sext i127 (-633825300114114700748351602688 + (633825300114114700748351602688 * (zext i32 %arg5 to i127))) to i128)
 ; CHECK: %t14 = or i128 %t10, 1
 ; CHECK-NEXT: --> {{.*}} Exits: (1 + (sext i127 (-633825300114114700748351602688 + (633825300114114700748351602688 * (zext i32 %arg5 to i127))) to i128))<nuw><nsw>
 ; CHECK: Loop %bb7: backedge-taken count is (-1 + (zext i32 %arg5 to i128))<nsw>
-; CHECK-NEXT: Loop %bb7: max backedge-taken count is 4294967294
+; CHECK-NEXT: Loop %bb7: max backedge-taken count is 2147483646
 ; CHECK-NEXT: Loop %bb7: Predicated backedge-taken count is (-1 + (zext i32 %arg5 to i128))<nsw>
 
 define void @goo(i32* nocapture %arg3, i32 %arg4, i32 %arg5) {
 bb:
   %t = icmp sgt i32 %arg5, 0
   br i1 %t, label %bb3, label %bb6
 
 bb3:                                              ; preds = %bb