[SCEV] Support unsigned predicates in isKnownPredicateViaNoOverflow

[mkazantsev]

Summary

SCEV should be able to prove facts like x <u x+1<nuw>.

[lebedev.ri]

What about swapped cases, like (X + C)<nuw> u<= X?

[lebedev.ri]

In D88015#2285077, @lebedev.ri wrote:

What about swapped cases, like (X + C)<nuw> u<= X?

Disregard. We return true if the predicate is known-true, and false in all other cases.
Looks reasonable to me.

llvm/lib/Analysis/ScalarEvolution.cpp

9302–9303

It is unclear how much it matters in practice, but
i don't think C needs to be a constant,
which means that we only need to check that RHS is an NUW SCEVAddExpr, and that
any_of(AE->operands(), [L](SCEV*Op){ return Op == L; }).

9311

Likely even less real-world, but likewise, i'd think we want to check
that RHS is a NUW SCEVAddExpr, any_of(AE->operands(), [L](SCEV*Op){ return Op == L; }),
and that (AE - L) != 0.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9302–9303

I think such cases are handled in different aux functions of isKnownViaNonRecursiveReasoning. This one is specifically for constant offset.

[mkazantsev]

Reloaded with dedicated unit test to make it independent on underlying patches (the only dependency was test).

llvm/lib/Analysis/ScalarEvolution.cpp

case ICmpInst::ICMP_SLT:
     if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNSW) &&
         C.isStrictlyPositive())
       return true;
 
     // (X + C)<nsw> s< X if C < 0
     if (MatchBinaryAddToConst(LHS, RHS, C, SCEV::FlagNSW) && C.isNegative())
       return true;
     break;
+
+  case ICmpInst::ICMP_UGE:
+    std::swap(LHS, RHS);
+    LLVM_FALLTHROUGH;
+  case ICmpInst::ICMP_ULE:
+    // X u<= (X + C)<nuw> for any C
+    if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNUW))
+      return true;
+    break;
+
+  case ICmpInst::ICMP_UGT:
+    std::swap(LHS, RHS);
+    LLVM_FALLTHROUGH;
+  case ICmpInst::ICMP_ULT:
+    // X u< (X + C)<nuw> if C != 0
+    if (MatchBinaryAddToConst(RHS, LHS, C, SCEV::FlagNUW) && !C.isNullValue())
+      return true;
+    break;
   }
 
   return false;
 }
 
 bool ScalarEvolution::isKnownPredicateViaSplitting(ICmpInst::Predicate Pred,
                                                    const SCEV *LHS,
                                                    const SCEV *RHS) {

llvm/test/Transforms/IndVarSimplify/monotonic_checks.ll

 define i32 @test_03(i32* %p) {
 ; CHECK-LABEL: @test_03(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[P:%.*]], align 4, [[RNG2:!range !.*]]
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
-; CHECK-NEXT:    [[RC:%.*]] = icmp ugt i32 [[IV_NEXT]], [[LEN]]
-; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       fail:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0
 ;