[ValueTracking] Add logic for `isKnownNonZero(usub.sat X, Y)`

[goldstein.w.n]

Summary

(usub X, Y) != 0 -> X u> Y

Alive2 Link:

https://alive2.llvm.org/ce/z/o29DK4

[nikic]

This case looks unnecessary. If %x >= %y we will fold the usub.sat to sub nuw %x, %y and not hit this pattern.

[goldstein.w.n]

In D149413#4304537, @nikic wrote:

This case looks unnecessary. If %x >= %y we will fold the usub.sat to sub nuw %x, %y and not hit this pattern.

Most likely yeah. My feeling is it might exist outside of InstCombine and need to be analyzed. I.e if its analyzable in InstSimplify
it may enable further simplifications of patterns we don't want to have to duplicate in InstCombine.

But if you're not convinced ill abandon.

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[nikic]

In D149413#4306606, @goldstein.w.n wrote:

In D149413#4304537, @nikic wrote:

This case looks unnecessary. If %x >= %y we will fold the usub.sat to sub nuw %x, %y and not hit this pattern.

Most likely yeah. My feeling is it might exist outside of InstCombine and need to be analyzed. I.e if its analyzable in InstSimplify
it may enable further simplifications of patterns we don't want to have to duplicate in InstCombine.

But if you're not convinced ill abandon.

I'd generally say that we should only handle non-canonical patterns in ValueTracking/InstSimplify if there is some special motivation to do so, which probably doesn't exist here.

I guess I'd be okay with handling it as a matter of "we handle all the other saturating intrinsics, why is this one missing?"

However, I'd prefer to see this implemented by extending isNonZeroSub() with a NUW flag that basically contains the logic you have here: https://alive2.llvm.org/ce/z/ZYDjCw That way the pattern will actually get handled after the usub.sat is replaced by sub nuw, and we're not just lying to ourselves about it working when it effectively doesn't.

[goldstein.w.n]

In D149413#4307948, @nikic wrote:

In D149413#4306606, @goldstein.w.n wrote:

In D149413#4304537, @nikic wrote:

This case looks unnecessary. If %x >= %y we will fold the usub.sat to sub nuw %x, %y and not hit this pattern.

Most likely yeah. My feeling is it might exist outside of InstCombine and need to be analyzed. I.e if its analyzable in InstSimplify
it may enable further simplifications of patterns we don't want to have to duplicate in InstCombine.

But if you're not convinced ill abandon.

I'd generally say that we should only handle non-canonical patterns in ValueTracking/InstSimplify if there is some special motivation to do so, which probably doesn't exist here.

I guess I'd be okay with handling it as a matter of "we handle all the other saturating intrinsics, why is this one missing?"

Yeah thats more my thinking.

However, I'd prefer to see this implemented by extending isNonZeroSub() with a NUW flag that basically contains the logic you have here: https://alive2.llvm.org/ce/z/ZYDjCw That way the pattern will actually get handled after the usub.sat is replaced by sub nuw, and we're not just lying to ourselves about it working when it effectively doesn't.

Although its a pretty meaningless pattern to have for sub. ugt implies ne so the current sub pattern works just as well/better for nuw or no nuw.

I'll drop. I guess if you were to take my argument to the extreme we would have all the logic for reproducing nsw/nuw flags for add/mul/etc.... which is clearly
a bad idea.

llvm/lib/Analysis/ValueTracking.cpp

if (auto *II = dyn_cast<IntrinsicInst>(I)) {
       case Intrinsic::abs:
       case Intrinsic::bitreverse:
       case Intrinsic::bswap:
       case Intrinsic::ctpop:
         if (isKnownNonZero(II->getArgOperand(0), DemandedElts, Depth, Q))
           return true;
         break;
       case Intrinsic::ssub_sat:
-        return isNonZeroSub(DemandedElts, Depth, Q, BitWidth, II->getArgOperand(0),
-                            II->getArgOperand(1));
-
+        return isNonZeroSub(DemandedElts, Depth, Q, BitWidth,
+                            II->getArgOperand(0), II->getArgOperand(1));
+      case Intrinsic::usub_sat: {
+        KnownBits XKnown =
+            computeKnownBits(II->getArgOperand(0), DemandedElts, Depth, Q);
+        if (XKnown.isUnknown())
+          return false;
+        KnownBits YKnown =
+            computeKnownBits(II->getArgOperand(1), DemandedElts, Depth, Q);
+        std::optional<bool> ugt = KnownBits::ugt(XKnown, YKnown);
+        return ugt && *ugt;
+      }
       case Intrinsic::uadd_sat:
         if (isKnownNonZero(II->getArgOperand(0), DemandedElts, Depth, Q) ||
             isKnownNonZero(II->getArgOperand(1), DemandedElts, Depth, Q))
           return true;
         break;
       case Intrinsic::cttz:
         return computeKnownBits(II->getArgOperand(0), DemandedElts, Depth, Q)
             .Zero[0];

llvm/test/Analysis/ValueTracking/known-non-zero.ll

;
   %r = icmp eq i8 %z, 0
   ret i1 %r
 }
 
 define i1 @usub_sat_nonzero(i8 %xx, i8 %yy, i8 %ind) {
 ; CHECK-LABEL: @usub_sat_nonzero(
 ; CHECK-NEXT:    [[Y_ULT_31:%.*]] = icmp ult i8 [[YY:%.*]], 31
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[Y_ULT_31]])
-; CHECK-NEXT:    [[XO:%.*]] = or i8 [[XX:%.*]], 34
-; CHECK-NEXT:    [[X:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[XO]], i8 [[YY]])
-; CHECK-NEXT:    [[Z:%.*]] = or i8 [[X]], [[IND:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[Z]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %y_ult_31 = icmp ult i8 %yy, 31
   call void @llvm.assume(i1 %y_ult_31)
   %xo = or i8 %xx, 34
   %x = call i8 @llvm.usub.sat.i8(i8 %xo, i8 %yy)
   %z = or i8 %x, %ind
   %r = icmp eq i8 %z, 0
   ret i1 %r