[InstSimplify] simplifyUnsignedRangeCheck(): handle more cases (PR43251)

[lebedev.ri]

Summary

I don't have a direct motivational case for this,
but it would be good to have this for completeness/symmetry.

This pattern is basically the motivational pattern from
https://bugs.llvm.org/show_bug.cgi?id=43251
but with different predicate that requires that the offset is non-zero.

The completeness bit comes from the fact that a similar pattern (offset != zero)
will be needed for https://bugs.llvm.org/show_bug.cgi?id=43259,
so it'd seem to be good to not overlook very similar patterns..

Proofs: https://rise4fun.com/Alive/21b

Also, there is something odd with isKnownNonZero(), if the non-zero
knowledge was specified as an assumption, it didn't pick it up (PR43267)

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

1774–1775

Can the diffs to thread the full SimplifyQuery through the calls be done as a preliminary step?
I'm not sure how to expose a diff in a test, but I'd think it's not quite 'NFC', so it should be an independent change.

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

1774–1775

I actually messed up in D67332, i didn't actually mean to *only* pass DL, it just kind-of fell through cracks :/
So passing SimplifyQuery is actually *intended* as NFC, but then i'm trying to balance
between having too much patches, and having too big patches.
Let me see if i can come up with a test.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

1774–1775

I'm fine with just changing the code by inspection as a preliminary to this patch; it's clearly an improvement.

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

1774–1775

Done in rL371630, will rebase in a sec.

[lebedev.ri]

Rebased to only contain the actual change itself and none of the SimplifyQuery threading-in.

[spatel]

LGTM

[lebedev.ri]

In D67411#1666771, @spatel wrote:

LGTM

Thank you for the review.

llvm/lib/Analysis/InstructionSimplify.cpp

Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
                               const SimplifyQuery &Q) {
   return ::SimplifyAShrInst(Op0, Op1, isExact, Q, RecursionLimit);
 }
 
 /// Commuted variants are assumed to be handled by calling this function again
 /// with the parameters swapped.
 static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
                                          ICmpInst *UnsignedICmp, bool IsAnd,
-                                         const DataLayout &DL) {
+                                         const SimplifyQuery &Q) {
   Value *X, *Y;
 
   ICmpInst::Predicate EqPred;
   if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
       !ICmpInst::isEquality(EqPred))
     return nullptr;
 
   ICmpInst::Predicate UnsignedPred;
+
+  // Y = (A - B);  Y >= A && Y != 0  --> Y >= A  iff B != 0
+  // Y = (A - B);  Y <  A || Y == 0  --> Y <  A  iff B != 0
+  Value *A, *B;
+  if (match(Y, m_Sub(m_Value(A), m_Value(B))) &&
+      match(UnsignedICmp,
+            m_c_ICmp(UnsignedPred, m_Specific(Y), m_Specific(A)))) {
+    if (UnsignedICmp->getOperand(0) != Y)
+      UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
+
+    if (UnsignedPred == ICmpInst::ICMP_UGE && IsAnd &&
+        EqPred == ICmpInst::ICMP_NE &&
+        isKnownNonZero(B, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
+      return UnsignedICmp;
+    if (UnsignedPred == ICmpInst::ICMP_ULT && !IsAnd &&
+        EqPred == ICmpInst::ICMP_EQ &&
+        isKnownNonZero(B, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
+      return UnsignedICmp;
+  }
+
   if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
       ICmpInst::isUnsigned(UnsignedPred))
     ;
   else if (match(UnsignedICmp,
                  m_ICmp(UnsignedPred, m_Specific(Y), m_Value(X))) &&
            ICmpInst::isUnsigned(UnsignedPred))
     UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
   else
     return nullptr;
 
   // X < Y && Y != 0  -->  X < Y
   // X < Y || Y != 0  -->  Y != 0
   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)
     return IsAnd ? UnsignedICmp : ZeroICmp;
 
   // X <= Y && Y != 0  -->  X <= Y  iff X != 0
   // X <= Y || Y != 0  -->  Y != 0  iff X != 0
   if (UnsignedPred == ICmpInst::ICMP_ULE && EqPred == ICmpInst::ICMP_NE &&
-      isKnownNonZero(X, DL))
+      isKnownNonZero(X, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
     return IsAnd ? UnsignedICmp : ZeroICmp;
 
   // X > Y && Y == 0  -->  Y == 0  iff X != 0
   // X > Y || Y == 0  -->  X > Y   iff X != 0
   if (UnsignedPred == ICmpInst::ICMP_UGT && EqPred == ICmpInst::ICMP_EQ &&
-      isKnownNonZero(X, DL))
+      isKnownNonZero(X, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
     return IsAnd ? ZeroICmp : UnsignedICmp;
 
   // X >= Y || Y != 0  -->  true
   // X >= Y || Y == 0  -->  X >= Y
   if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd) {
     if (EqPred == ICmpInst::ICMP_NE)
       return getTrue(UnsignedICmp->getType());
     return UnsignedICmp;
if (Delta == 1)
       if (Pred0 == ICmpInst::ICMP_ULE && Pred1 == ICmpInst::ICMP_UGT)
         return getFalse(ITy);
   }
 
   return nullptr;
 }
 
 static Value *simplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1,
-                                 const InstrInfoQuery &IIQ,
-                                 const DataLayout &DL) {
-  if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true, DL))
+                                 const SimplifyQuery &Q) {
+  if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true, Q))
     return X;
-  if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/true, DL))
+  if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/true, Q))
     return X;
 
   if (Value *X = simplifyAndOfICmpsWithSameOperands(Op0, Op1))
     return X;
   if (Value *X = simplifyAndOfICmpsWithSameOperands(Op1, Op0))
     return X;
 
   if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, true))
     return X;
 
   if (Value *X = simplifyAndOrOfICmpsWithZero(Op0, Op1, true))
     return X;
 
-  if (Value *X = simplifyAndOfICmpsWithAdd(Op0, Op1, IIQ))
+  if (Value *X = simplifyAndOfICmpsWithAdd(Op0, Op1, Q.IIQ))
     return X;
-  if (Value *X = simplifyAndOfICmpsWithAdd(Op1, Op0, IIQ))
+  if (Value *X = simplifyAndOfICmpsWithAdd(Op1, Op0, Q.IIQ))
     return X;
 
   return nullptr;
 }
 
 static Value *simplifyOrOfICmpsWithAdd(ICmpInst *Op0, ICmpInst *Op1,
                                        const InstrInfoQuery &IIQ) {
   // (icmp (add V, C0), C1) | (icmp V, C0)
if (Delta == 1)
       if (Pred0 == ICmpInst::ICMP_UGT && Pred1 == ICmpInst::ICMP_ULE)
         return getTrue(ITy);
   }
 
   return nullptr;
 }
 
 static Value *simplifyOrOfICmps(ICmpInst *Op0, ICmpInst *Op1,
-                                const InstrInfoQuery &IIQ,
-                                const DataLayout &DL) {
-  if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false, DL))
+                                const SimplifyQuery &Q) {
+  if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/false, Q))
     return X;
-  if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/false, DL))
+  if (Value *X = simplifyUnsignedRangeCheck(Op1, Op0, /*IsAnd=*/false, Q))
     return X;
 
   if (Value *X = simplifyOrOfICmpsWithSameOperands(Op0, Op1))
     return X;
   if (Value *X = simplifyOrOfICmpsWithSameOperands(Op1, Op0))
     return X;
 
   if (Value *X = simplifyAndOrOfICmpsWithConstants(Op0, Op1, false))
     return X;
 
   if (Value *X = simplifyAndOrOfICmpsWithZero(Op0, Op1, false))
     return X;
 
-  if (Value *X = simplifyOrOfICmpsWithAdd(Op0, Op1, IIQ))
+  if (Value *X = simplifyOrOfICmpsWithAdd(Op0, Op1, Q.IIQ))
     return X;
-  if (Value *X = simplifyOrOfICmpsWithAdd(Op1, Op0, IIQ))
+  if (Value *X = simplifyOrOfICmpsWithAdd(Op1, Op0, Q.IIQ))
     return X;
 
   return nullptr;
 }
 
 static Value *simplifyAndOrOfFCmps(const TargetLibraryInfo *TLI,
                                    FCmpInst *LHS, FCmpInst *RHS, bool IsAnd) {
   Value *LHS0 = LHS->getOperand(0), *LHS1 = LHS->getOperand(1);
if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() &&
     Op0 = Cast0->getOperand(0);
     Op1 = Cast1->getOperand(0);
   }
 
   Value *V = nullptr;
   auto *ICmp0 = dyn_cast<ICmpInst>(Op0);
   auto *ICmp1 = dyn_cast<ICmpInst>(Op1);
   if (ICmp0 && ICmp1)
-    V = IsAnd ? simplifyAndOfICmps(ICmp0, ICmp1, Q.IIQ, Q.DL)
-              : simplifyOrOfICmps(ICmp0, ICmp1, Q.IIQ, Q.DL);
+    V = IsAnd ? simplifyAndOfICmps(ICmp0, ICmp1, Q)
+              : simplifyOrOfICmps(ICmp0, ICmp1, Q);
 
   auto *FCmp0 = dyn_cast<FCmpInst>(Op0);
   auto *FCmp1 = dyn_cast<FCmpInst>(Op1);
   if (FCmp0 && FCmp1)
     V = simplifyAndOrOfFCmps(Q.TLI, FCmp0, FCmp1, IsAnd);
 
   if (!V)
     return nullptr;

llvm/test/Transforms/InstSimplify/result-of-usub-by-nonzero-is-non-zero-and-no-overflow.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instsimplify -S | FileCheck %s
 
 ; Here we subtract two values, check that subtraction did not overflow AND
 ; that the result is non-zero. This can be simplified just to a comparison
 ; between the base and offset.
 
 define i1 @t0(i64 %base, i64* nonnull %offsetptr) {
 ; CHECK-LABEL: @t0(
 ; CHECK-NEXT:    [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i64 [[ADJUSTED]], [[BASE]]
-; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i64 [[ADJUSTED]], 0
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[NO_UNDERFLOW]]
 ;
   %offset = ptrtoint i64* %offsetptr to i64
 
   %adjusted = sub i64 %base, %offset
   %no_underflow = icmp uge i64 %adjusted, %base
   %not_null = icmp ne i64 %adjusted, 0
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 define i1 @t1(i64 %base, i64* nonnull %offsetptr) {
 ; CHECK-LABEL: @t1(
 ; CHECK-NEXT:    [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ult i64 [[ADJUSTED]], [[BASE]]
-; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp eq i64 [[ADJUSTED]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[NO_UNDERFLOW]]
 ;
   %offset = ptrtoint i64* %offsetptr to i64
 
   %adjusted = sub i64 %base, %offset
   %no_underflow = icmp ult i64 %adjusted, %base
   %not_null = icmp eq i64 %adjusted, 0
   %r = or i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 define i1 @t2_commutative(i64 %base, i64* nonnull %offsetptr) {
 ; CHECK-LABEL: @t2_commutative(
 ; CHECK-NEXT:    [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i64 [[BASE]], [[ADJUSTED]]
-; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i64 [[ADJUSTED]], 0
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[NO_UNDERFLOW]]
 ;
   %offset = ptrtoint i64* %offsetptr to i64
 
   %adjusted = sub i64 %base, %offset
   %no_underflow = icmp ule i64 %base, %adjusted
   %not_null = icmp ne i64 %adjusted, 0
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 define i1 @t3_commutative(i64 %base, i64* nonnull %offsetptr) {
 ; CHECK-LABEL: @t3_commutative(
 ; CHECK-NEXT:    [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ugt i64 [[BASE]], [[ADJUSTED]]
-; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp eq i64 [[ADJUSTED]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[NO_UNDERFLOW]]
 ;
   %offset = ptrtoint i64* %offsetptr to i64
 
   %adjusted = sub i64 %base, %offset
   %no_underflow = icmp ugt i64 %base, %adjusted
   %not_null = icmp eq i64 %adjusted, 0
   %r = or i1 %not_null, %no_underflow
   ret i1 %r