[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

9322–9323

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; }).

9331

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

9322–9323

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/unittests/Analysis/ScalarEvolutionTest.cpp

runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
     auto *AR = dyn_cast<SCEVAddRecExpr>(WithUMin);
     EXPECT_TRUE(AR);
     EXPECT_EQ(AR->getStart(),
               SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)));
     EXPECT_EQ(AR->getStepRecurrence(SE),
               cast<SCEVAddRecExpr>(ScevIV)->getStepRecurrence(SE));
   });
 }
+
+TEST_F(ScalarEvolutionsTest, SCEVAddNUW) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString("define void @foo(i32 %x) { "
+                                                  "  ret void "
+                                                  "} ",
+                                                  Err, C);
+
+  ASSERT_TRUE(M && "Could not parse module?");
+  ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+    auto *X = SE.getSCEV(getArgByName(F, "x"));
+    auto *One = SE.getOne(X->getType());
+    auto *Sum = SE.getAddExpr(X, One, SCEV::FlagNUW);
+    EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGE, Sum, X));
+    EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGT, Sum, X));
+  });
+}
+
 }  // end namespace llvm