[SCEV] Handle uge/ugt predicates in applyLoopGuards()

[nikic]

Summary

These can be handled the same way as ule/ult, just using umax instead of umin. This is useful in cases where the umax prevents the upper bound from overflowing.

[nikic]

Rebase over some implementation cleanup.

[fhahn]

LGTM, thanks!

Would it be possible to have a test which requires multiple re-writes, by limiting the IV in both directions?

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

635–636

IMO it would slightly increase the readability of the test here if we would use the uge predicate, as in the test name :)

[nikic]

Rebase over added/improved tests.

[nikic]

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

635–636

Yeah, that makes a lot more sense :) I just picked picked the order from the original test case...

llvm/lib/Analysis/ScalarEvolution.cpp

case CmpInst::ICMP_ULT:
       if (!containsAddRecurrence(RHS))
         RewriteMap[LHSUnknown->getValue()] = getUMinExpr(
             RewrittenLHS, getMinusSCEV(RHS, getOne(RHS->getType())));
       break;
     case CmpInst::ICMP_ULE:
       if (!containsAddRecurrence(RHS))
         RewriteMap[LHSUnknown->getValue()] = getUMinExpr(RewrittenLHS, RHS);
       break;
+    case CmpInst::ICMP_UGT:
+      if (!containsAddRecurrence(RHS))
+        RewriteMap[LHSUnknown->getValue()] =
+            getUMaxExpr(RewrittenLHS, getAddExpr(RHS, getOne(RHS->getType())));
+      break;
+    case CmpInst::ICMP_UGE:
+      if (!containsAddRecurrence(RHS))
+        RewriteMap[LHSUnknown->getValue()] = getUMaxExpr(RewrittenLHS, RHS);
+      break;
     case CmpInst::ICMP_EQ:
       if (isa<SCEVConstant>(RHS))
         RewriteMap[LHSUnknown->getValue()] = RHS;
       break;
     case CmpInst::ICMP_NE:
       if (isa<SCEVConstant>(RHS) &&
           cast<SCEVConstant>(RHS)->getValue()->isNullValue())
         RewriteMap[LHSUnknown->getValue()] =

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

 }
 
 define void @test_guard_uge(i32 %blockSize) {
 ; CHECK-LABEL: 'test_guard_uge'
 ; CHECK-NEXT:  Classifying expressions for: @test_guard_uge
 ; CHECK-NEXT:    %shr = lshr i32 %blockSize, 2
 ; CHECK-NEXT:    --> (%blockSize /u 4) U: [0,1073741824) S: [0,1073741824)
 ; CHECK-NEXT:    %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ]
-; CHECK-NEXT:    --> {(%blockSize /u 4),+,-1}<%while.body> U: full-set S: full-set Exits: 1 LoopDispositions: { %while.body: Computable }
+; CHECK-NEXT:    --> {(%blockSize /u 4),+,-1}<%while.body> U: [-1073741822,1073741824) S: [-1073741822,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable }
 ; CHECK-NEXT:    %dec = add i32 %iv, -1
-; CHECK-NEXT:    --> {(-1 + (%blockSize /u 4))<nsw>,+,-1}<%while.body> U: full-set S: full-set Exits: 0 LoopDispositions: { %while.body: Computable }
+; CHECK-NEXT:    --> {(-1 + (%blockSize /u 4))<nsw>,+,-1}<%while.body> U: [-1073741823,1073741823) S: [-1073741823,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_uge
 ; CHECK-NEXT:  Loop %while.body: backedge-taken count is (-1 + (%blockSize /u 4))<nsw>
-; CHECK-NEXT:  Loop %while.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %while.body: max backedge-taken count is 1073741822
 ; CHECK-NEXT:  Loop %while.body: Predicated backedge-taken count is (-1 + (%blockSize /u 4))<nsw>
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %while.body: Trip multiple is 1
 ;
   %shr = lshr i32 %blockSize, 2
   %guard = icmp uge i32 %blockSize, 4
   br i1 %guard, label %while.body.preheader, label %while.end
 
 while.body.preheader:
   br label %while.body
 
 while.body:
   %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ]
   %dec = add i32 %iv, -1
   %cmp.not = icmp eq i32 %dec, 0
   br i1 %cmp.not, label %while.end.loopexit, label %while.body
 
 while.end.loopexit:
   br label %while.end
 
 while.end:
   ret void
 }
 
 define void @test_guard_ugt(i32 %blockSize) {
 ; CHECK-LABEL: 'test_guard_ugt'
 ; CHECK-NEXT:  Classifying expressions for: @test_guard_ugt
 ; CHECK-NEXT:    %shr = lshr i32 %blockSize, 2
 ; CHECK-NEXT:    --> (%blockSize /u 4) U: [0,1073741824) S: [0,1073741824)
 ; CHECK-NEXT:    %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ]
-; CHECK-NEXT:    --> {(%blockSize /u 4),+,-1}<%while.body> U: full-set S: full-set Exits: 1 LoopDispositions: { %while.body: Computable }
+; CHECK-NEXT:    --> {(%blockSize /u 4),+,-1}<%while.body> U: [-1073741822,1073741824) S: [-1073741822,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable }
 ; CHECK-NEXT:    %dec = add i32 %iv, -1
-; CHECK-NEXT:    --> {(-1 + (%blockSize /u 4))<nsw>,+,-1}<%while.body> U: full-set S: full-set Exits: 0 LoopDispositions: { %while.body: Computable }
+; CHECK-NEXT:    --> {(-1 + (%blockSize /u 4))<nsw>,+,-1}<%while.body> U: [-1073741823,1073741823) S: [-1073741823,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_ugt
 ; CHECK-NEXT:  Loop %while.body: backedge-taken count is (-1 + (%blockSize /u 4))<nsw>
-; CHECK-NEXT:  Loop %while.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %while.body: max backedge-taken count is 1073741822
 ; CHECK-NEXT:  Loop %while.body: Predicated backedge-taken count is (-1 + (%blockSize /u 4))<nsw>
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %while.body: Trip multiple is 1
 ;
   %shr = lshr i32 %blockSize, 2
   %guard = icmp ugt i32 %blockSize, 3
   br i1 %guard, label %while.body.preheader, label %while.end
 

 }
 
 define void @test_guard_uge_and_ule(i32 %blockSize) {
 ; CHECK-LABEL: 'test_guard_uge_and_ule'
 ; CHECK-NEXT:  Classifying expressions for: @test_guard_uge_and_ule
 ; CHECK-NEXT:    %shr = lshr i32 %blockSize, 2
 ; CHECK-NEXT:    --> (%blockSize /u 4) U: [0,1073741824) S: [0,1073741824)
 ; CHECK-NEXT:    %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ]
-; CHECK-NEXT:    --> {(%blockSize /u 4),+,-1}<%while.body> U: full-set S: full-set Exits: 1 LoopDispositions: { %while.body: Computable }
+; CHECK-NEXT:    --> {(%blockSize /u 4),+,-1}<%while.body> U: [-255,1073741824) S: [-255,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable }
 ; CHECK-NEXT:    %dec = add i32 %iv, -1
-; CHECK-NEXT:    --> {(-1 + (%blockSize /u 4))<nsw>,+,-1}<%while.body> U: full-set S: full-set Exits: 0 LoopDispositions: { %while.body: Computable }
+; CHECK-NEXT:    --> {(-1 + (%blockSize /u 4))<nsw>,+,-1}<%while.body> U: [-256,1073741823) S: [-256,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_uge_and_ule
 ; CHECK-NEXT:  Loop %while.body: backedge-taken count is (-1 + (%blockSize /u 4))<nsw>
-; CHECK-NEXT:  Loop %while.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %while.body: max backedge-taken count is 255
 ; CHECK-NEXT:  Loop %while.body: Predicated backedge-taken count is (-1 + (%blockSize /u 4))<nsw>
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %while.body: Trip multiple is 1
 ;
   %shr = lshr i32 %blockSize, 2
   %guard1 = icmp uge i32 %blockSize, 4
   br i1 %guard1, label %while.guard, label %while.end
 

 }
 
 define void @test_guard_ugt_and_ult(i32 %blockSize) {
 ; CHECK-LABEL: 'test_guard_ugt_and_ult'
 ; CHECK-NEXT:  Classifying expressions for: @test_guard_ugt_and_ult
 ; CHECK-NEXT:    %shr = lshr i32 %blockSize, 2
 ; CHECK-NEXT:    --> (%blockSize /u 4) U: [0,1073741824) S: [0,1073741824)
 ; CHECK-NEXT:    %iv = phi i32 [ %dec, %while.body ], [ %shr, %while.body.preheader ]
-; CHECK-NEXT:    --> {(%blockSize /u 4),+,-1}<%while.body> U: full-set S: full-set Exits: 1 LoopDispositions: { %while.body: Computable }
+; CHECK-NEXT:    --> {(%blockSize /u 4),+,-1}<%while.body> U: [-255,1073741824) S: [-255,1073741824) Exits: 1 LoopDispositions: { %while.body: Computable }
 ; CHECK-NEXT:    %dec = add i32 %iv, -1
-; CHECK-NEXT:    --> {(-1 + (%blockSize /u 4))<nsw>,+,-1}<%while.body> U: full-set S: full-set Exits: 0 LoopDispositions: { %while.body: Computable }
+; CHECK-NEXT:    --> {(-1 + (%blockSize /u 4))<nsw>,+,-1}<%while.body> U: [-256,1073741823) S: [-256,1073741823) Exits: 0 LoopDispositions: { %while.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_ugt_and_ult
 ; CHECK-NEXT:  Loop %while.body: backedge-taken count is (-1 + (%blockSize /u 4))<nsw>
-; CHECK-NEXT:  Loop %while.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %while.body: max backedge-taken count is 255
 ; CHECK-NEXT:  Loop %while.body: Predicated backedge-taken count is (-1 + (%blockSize /u 4))<nsw>
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %while.body: Trip multiple is 1
 ;
   %shr = lshr i32 %blockSize, 2
   %guard1 = icmp ugt i32 %blockSize, 3
   br i1 %guard1, label %while.guard, label %while.end