[InstCombine] foldUnsignedUnderflowCheck(): handle last few 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)

With this, i see no other missing folds for
https://bugs.llvm.org/show_bug.cgi?id=43251

[lebedev.ri]

Rebased, NFC.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static Value *foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd,
   }
   return nullptr;
 }
 
 /// Commuted variants are assumed to be handled by calling this function again
 /// with the parameters swapped.
 static Value *foldUnsignedUnderflowCheck(ICmpInst *ZeroICmp,
                                          ICmpInst *UnsignedICmp, bool IsAnd,
+                                         const SimplifyQuery &Q,
                                          InstCombiner::BuilderTy &Builder) {
   Value *Subtracted;
   ICmpInst::Predicate EqPred;
   if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Subtracted), m_Zero())) ||
       !ICmpInst::isEquality(EqPred))
     return nullptr;
 
   Value *Base, *Offset;
   if (!match(Subtracted, m_Sub(m_Value(Base), m_Value(Offset))))
     return nullptr;
 
   ICmpInst::Predicate UnsignedPred;
+
+  // Subtracted <  Base && Subtracted != 0  --> Base >  Offset  iff Offset != 0
+  // Subtracted >= Base || Subtracted == 0  --> Base <= Base    iff Offset != 0
+  if (match(UnsignedICmp,
+            m_c_ICmp(UnsignedPred, m_Specific(Subtracted), m_Specific(Base)))) {
+    if (UnsignedICmp->getOperand(0) != Subtracted)
+      UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
+
+    if (UnsignedPred == ICmpInst::ICMP_ULT && IsAnd &&
+        EqPred == ICmpInst::ICMP_NE &&
+        isKnownNonZero(Offset, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
+      return Builder.CreateICmpUGT(Base, Offset);
+    if (UnsignedPred == ICmpInst::ICMP_UGE && !IsAnd &&
+        EqPred == ICmpInst::ICMP_EQ &&
+        isKnownNonZero(Offset, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
+      return Builder.CreateICmpULE(Base, Offset);
+  }
+
   if (!match(UnsignedICmp,
              m_c_ICmp(UnsignedPred, m_Specific(Base), m_Specific(Offset))) ||
       !ICmpInst::isUnsigned(UnsignedPred))
     return nullptr;
   if (UnsignedICmp->getOperand(0) != Base)
     UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
 
   // Base >=/> Offset && (Base - Offset) != 0  <-->  Base > Offset
if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, true, Builder))
     return V;
 
   if (Value *V = foldSignedTruncationCheck(LHS, RHS, CxtI, Builder))
     return V;
 
   if (Value *V = foldIsPowerOf2(LHS, RHS, true /* JoinedByAnd */, Builder))
     return V;
 
-  if (Value *X = foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/true, Builder))
+  if (Value *X =
+          foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/true, SQ, Builder))
     return X;
-  if (Value *X = foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/true, Builder))
+  if (Value *X =
+          foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/true, SQ, Builder))
     return X;
 
   // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
   Value *LHS0 = LHS->getOperand(0), *RHS0 = RHS->getOperand(0);
   ConstantInt *LHSC = dyn_cast<ConstantInt>(LHS->getOperand(1));
   ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS->getOperand(1));
   if (!LHSC || !RHSC)
     return nullptr;
if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
     return V;
 
   if (Value *V = foldAndOrOfEqualityCmpsWithConstants(LHS, RHS, false, Builder))
     return V;
 
   if (Value *V = foldIsPowerOf2(LHS, RHS, false /* JoinedByAnd */, Builder))
     return V;
 
-  if (Value *X = foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/false, Builder))
+  if (Value *X =
+          foldUnsignedUnderflowCheck(LHS, RHS, /*IsAnd=*/false, SQ, Builder))
     return X;
-  if (Value *X = foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/false, Builder))
+  if (Value *X =
+          foldUnsignedUnderflowCheck(RHS, LHS, /*IsAnd=*/false, SQ, Builder))
     return X;
 
   // This only handles icmp of constants: (icmp1 A, C1) | (icmp2 B, C2).
   if (!LHSC || !RHSC)
     return nullptr;
 
   if (LHSC == RHSC && PredL == PredR) {
     // (icmp ne A, 0) | (icmp ne B, 0) --> (icmp ne (A|B), 0)

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

 ; CHECK-LABEL: @t10(
 ; CHECK-NEXT:    [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use64(i64 [[ADJUSTED]])
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ult i64 [[ADJUSTED]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i64 [[ADJUSTED]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[OFFSET]], [[BASE]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %offset = ptrtoint i64* %offsetptr to i64
 
   %adjusted = sub i64 %base, %offset
   call void @use64(i64 %adjusted)
   %no_underflow = icmp ult i64 %adjusted, %base
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i64 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }
 define i1 @t11_commutative(i64 %base, i64* nonnull %offsetptr) {
 ; CHECK-LABEL: @t11_commutative(
 ; CHECK-NEXT:    [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use64(i64 [[ADJUSTED]])
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ult i64 [[ADJUSTED]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i64 [[ADJUSTED]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[OFFSET]], [[BASE]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %offset = ptrtoint i64* %offsetptr to i64
 
   %adjusted = sub i64 %base, %offset
   call void @use64(i64 %adjusted)
   %no_underflow = icmp ugt i64 %base, %adjusted ; swapped
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i64 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 define i1 @t12(i64 %base, i64* nonnull %offsetptr) {
 ; CHECK-LABEL: @t12(
 ; CHECK-NEXT:    [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use64(i64 [[ADJUSTED]])
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i64 [[ADJUSTED]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp eq i64 [[ADJUSTED]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i64 [[OFFSET]], [[BASE]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %offset = ptrtoint i64* %offsetptr to i64
 
   %adjusted = sub i64 %base, %offset
   call void @use64(i64 %adjusted)
   %no_underflow = icmp uge i64 %adjusted, %base
   call void @use1(i1 %no_underflow)
   %not_null = icmp eq i64 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = or i1 %not_null, %no_underflow
   ret i1 %r
 }
 define i1 @t13(i64 %base, i64* nonnull %offsetptr) {
 ; CHECK-LABEL: @t13(
 ; CHECK-NEXT:    [[OFFSET:%.*]] = ptrtoint i64* [[OFFSETPTR:%.*]] to i64
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i64 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use64(i64 [[ADJUSTED]])
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i64 [[ADJUSTED]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp eq i64 [[ADJUSTED]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i64 [[OFFSET]], [[BASE]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %offset = ptrtoint i64* %offsetptr to i64
 
   %adjusted = sub i64 %base, %offset
   call void @use64(i64 %adjusted)
   %no_underflow = icmp ule i64 %base, %adjusted ; swapped
   call void @use1(i1 %no_underflow)
   %not_null = icmp eq i64 %adjusted, 0