[SCEV] Limited support for unsigned preds in isImpliedViaOperations

[mkazantsev]

Summary

The logic there only considers SLT/SGT predicates. We can use the same logic
for proving ULT/UGT predicates if all involved values are non-negative.

Adding full-scale support for unsigned might be challenging because of code amount,
so we can consider this in the future.

[mkazantsev]

Added ULT check showing use of D87890

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

10158

I'm confused by this check, it seems overly complicated given the comment? Why is this simply not:
if (isKnownNonNegative(LHS) && isKnownNonNegative(RHS) &&

 isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS)) {
Pred = ICmpInst::getSignedPredicate(Pred);

}

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

10158

Because non-negativity of LHS and RHS is not known.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

10158

We need an extra fact SignedPred FoundLHS FoundRHS to prove it. And we only have this fact if we know Pred FoundLHS FoundRHS && isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS).

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

10158

If FoundLHS and FoundRHS are both non-negative, then all unsigned predicates are equivalent to their signed variants. There's no separate fact needed for that. Same for LHS and RHS.

Max, it may help if we talked offline here. I can't tell if you're saying my argument is wrong, or that the example your trying to optimize doesn't have sufficient information to establish the non-negative facts. Please either talk to me offline, or be very specific in your next response.

[lebedev.ri]

llvm/lib/Analysis/ScalarEvolution.cpp

10158

If FoundLHS and FoundRHS are both non-negative, then all unsigned predicates are equivalent to their signed variants. There's no separate fact needed for that. Same for LHS and RHS.

I agree. The actual rules are: (for any signed/unsigned pred, they just have to be identical)
https://rise4fun.com/Alive/P9Il

[mkazantsev]

Let me elaborate a bit.

We are trying to prove LHS >u RHS, knowing that FoundLHS >u FoundRHS. We want to somehow reduce this to an equivalent >s proof.

You are correct that if we know that all LHS, RHS, FoundLHS and FoundRHS are non-negative, we can simply call isImpliedViaOperations(>s, LHS, RHS, FoundLHS, FoundRHS).

However, we might not be able to prove isKnownNonNegative(LHS) or isKnownNonNegative(RHS). Imagine the case when we have proved isKnownNonNegative(FoundLHS) and isKnownNonNegative(FoundRHS), but cannot do so for neither LHS nor RHS. In this case (and this is what my patch is about), we should try to infer non-negativity of LHS and RHS from FoundLHS > FoundRHS. And the way to do it is to call isImpliedViaOperations(>s, LHS, -1, FoundLHS, FoundRHS) and isImpliedViaOperations(>s, RHS, -1, FoundLHS, FoundRHS). What you proposed is just a subset of what can be proved with implication.

I can split this change into two pieces: first piece with trivially provable non-negativity of LHS and RHS, and the second case is when we cannot prove this trivially and should use implication. Does it make sense now?

[mkazantsev]

..The only problem is that it is not possible to create a test for which isKnownNonNegative would actually return true for LHS beign a + b.

[mkazantsev]

• Simplified code, making it crystal clear that it only works for ULT/UGT;
• Simplified test to show what we are trying to prove without redundant entities;
• Checks with isKnownNonNegative(LHS/RHS) do not work, because if these facts are known, we never reach this code and prove the required fact with other means. But more commonly, it is just not known even in simplest cases. For example, for %x = load ... {1, SINT_MAX}, it cannot prove that add(x, -1) is non-negative. We could fix that, but it's a problem which has nothing to do with what I am trying to achieve here.

[reames]

I'd prefer to have this split, but not enough to insist on it. With improved explanation and comments, LGTM.

[xbolva00]

https://llvm-compile-time-tracker.com/compare.php?from=f29645e7afdbb8d1fc2dd603c0b128bac055625c&to=b8ac19cf1cca5faec8b4404bb0f666cb63c9e1de&stat=instructions

Compile time regressed a bit but I see no binary changes so.. how useful is this in practise? Any benchmark data to justify small regression?

[reames]

In D88087#2308077, @xbolva00 wrote:

https://llvm-compile-time-tracker.com/compare.php?from=f29645e7afdbb8d1fc2dd603c0b128bac055625c&to=b8ac19cf1cca5faec8b4404bb0f666cb63c9e1de&stat=instructions

Compile time regressed a bit but I see no binary changes so.. how useful is this in practise? Any benchmark data to justify small regression?

I'll assert this is justified. Only being able to handle signed predicates when we canonicalize to unsigned is a bit of a problem. :)

Can you be more specific about how much compile time regressed and on what?

[lebedev.ri]

llvm/lib/Analysis/ScalarEvolution.cpp

10172

I'll look into adding a method to ConstantRange to find compatible [un]signed predicate.

llvm/lib/Analysis/ScalarEvolution.cpp

assert(getTypeSizeInBits(LHS->getType()) ==
              getTypeSizeInBits(RHS->getType()) &&
          "LHS and RHS have different sizes?");
   assert(getTypeSizeInBits(FoundLHS->getType()) ==
              getTypeSizeInBits(FoundRHS->getType()) &&
          "FoundLHS and FoundRHS have different sizes?");
   // We want to avoid hurting the compile time with analysis of too big trees.
   if (Depth > MaxSCEVOperationsImplicationDepth)
     return false;
+
+  if (ICmpInst::isUnsigned(Pred))
+    // We can replace unsigned predicate with its signed counterpart if all
+    // involved values are non-negative.
+    // TODO: We could have better support for unsigned.
+    if (isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS)) {
+      const SCEV *MinusOne = getNegativeSCEV(getOne(LHS->getType()));
+      if (isImpliedCondOperands(ICmpInst::ICMP_SGT, LHS, MinusOne, FoundLHS,
+                                FoundRHS) &&
+          isImpliedCondOperands(ICmpInst::ICMP_SGT, RHS, MinusOne, FoundLHS,
+                                FoundRHS))
+        Pred = ICmpInst::getSignedPredicate(Pred);
+    }
+
   // We only want to work with ICMP_SGT comparison so far.
-  // TODO: Extend to ICMP_UGT?
   if (Pred == ICmpInst::ICMP_SLT) {
     Pred = ICmpInst::ICMP_SGT;
     std::swap(LHS, RHS);
     std::swap(FoundLHS, FoundRHS);
   }
   if (Pred != ICmpInst::ICMP_SGT)
     return false;
 
   auto GetOpFromSExt = [&](const SCEV *S) {
     if (auto *Ext = dyn_cast<SCEVSignExtendExpr>(S))
       return Ext->getOperand();
     // TODO: If S is a SCEVConstant then you can cheaply "strip" the sext off
     // the constant in some cases.
     return S;
   };

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

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));
   });
 }
 
+TEST_F(ScalarEvolutionsTest, UnsignedIsImpliedViaOperations) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M =
+      parseAssemblyString("define void @foo(i32* %p) { "
+                          "entry: "
+                          "  %x = load i32, i32* %p, !range !0 "
+                          "  %cond = icmp ne i32 %x, 0 "
+                          "  br i1 %cond, label %loop, label %exit "
+                          "loop: "
+                          "  %y = add i32 %x, -1 "
+                          "  br label %loop "
+                          "exit:"
+                          "  ret void "
+                          "} "
+                          "!0 = !{i32 0, i32 2147483647}",
+                          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(getInstructionByName(F, "x"));
+    auto *Y = SE.getSCEV(getInstructionByName(F, "y"));
+    auto *Loop = LI.getLoopFor(getInstructionByName(F, "y")->getParent());
+    ASSERT_TRUE(Loop);
+    EXPECT_TRUE(SE.isLoopEntryGuardedByCond(Loop, ICmpInst::ICMP_UGT, X, Y));
+    EXPECT_TRUE(SE.isLoopEntryGuardedByCond(Loop, ICmpInst::ICMP_ULT, Y, X));
+  });
+}
+
 }  // end namespace llvm