[SCEV] Prove isKnown(Non)Negative using CtxI when possible

[mkazantsev]

Summary

Sometimes the (non)negativity of something may only be inferred via context.
Use it when it is available.

[mkazantsev]

Theoretically can be costly in terms of CT. Nikita, could you pls check?

[nikic]

In D110518#3023518, @mkazantsev wrote:

Theoretically can be costly in terms of CT. Nikita, could you pls check?

Yeah, it is: https://llvm-compile-time-tracker.com/compare.php?from=02d425d09d9da6786500f7bc620fe615c1c2dbf6&to=6373f1816403f66a10407d4227895aaa3b3b85b2&stat=instructions +50% on ClamAV

I think we ran into this with pretty much all attempts to use more context-sensitive reasoning in SCEV, though this is probably the worst impact yet. Probably because this is doing a context-sensitive walk inside another context-sensitive walk.

[mkazantsev]

Ok that's not good, I'll try to figure something out... Thanks for checking!

[mkazantsev]

Too expensive, not gonna happen, at least not in current implementation.

llvm/lib/Analysis/ScalarEvolution.cpp

auto IsSignFlippedPredicate = [](CmpInst::Predicate P1,
                                    CmpInst::Predicate P2) {
     assert(P1 != P2 && "Handled earlier!");
     return CmpInst::isRelational(P2) &&
            P1 == CmpInst::getFlippedSignednessPredicate(P2);
   };
   if (IsSignFlippedPredicate(Pred, FoundPred)) {
     // Unsigned comparison is the same as signed comparison when both the
     // operands are non-negative or negative.
-    if ((isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS)) ||
-        (isKnownNegative(FoundLHS) && isKnownNegative(FoundRHS)))
+    auto IsKnownNonNegative = [&](const SCEV *S) {
+      if (CtxI)
+        return isKnownPredicateAt(ICmpInst::ICMP_SGE, S, getZero(S->getType()),
+                                  CtxI);
+      return isKnownNonNegative(S);
+    };
+    auto IsKnownNegative = [&](const SCEV *S) {
+      if (CtxI)
+        return isKnownPredicateAt(ICmpInst::ICMP_SLT, S, getZero(S->getType()),
+                                  CtxI);
+      return isKnownNegative(S);
+    };
+    if ((IsKnownNonNegative(FoundLHS) && IsKnownNonNegative(FoundRHS)) ||
+        (IsKnownNegative(FoundLHS) && IsKnownNegative(FoundRHS)))
       return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS, CtxI);
     // TODO: A symmetrical fact should be provable for replacing an unsigned
     // predicate with signed.
     if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE)
-      if (isKnownNonNegative(RHS))
+      if (IsKnownNonNegative(RHS))
         // We need to prove that LHS <s RHS. Knowing that RHS is non-negative,
         // if we can prove that LHS <u RHS, this will automatically imply the
         // fact we need.
         return isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS);
   }
 
   // Check if we can make progress by sharpening ranges.
   if (FoundPred == ICmpInst::ICMP_NE &&

llvm/test/Transforms/IndVarSimplify/outer_phi.ll

 
 side.exit:
   ret i32 0
 
 exit:
   ret i32 1
 }
 
-; FIXME: iv <u b, b >=s 0 --> iv <s b. We should be able to remove the 2nd check.
 define i32 @test_01a(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_01a(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0
 ; CHECK-NEXT:    br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]]
 ; CHECK:       outer.preheader:
 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 ; CHECK:       outer:
 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ]
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
 ; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       inner.1:
-; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
-; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
+; CHECK-NEXT:    br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
 ; CHECK:       inner.backedge:
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer.backedge:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
 ; CHECK-NEXT:    [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]