[InstSimplify] simplifyUnsignedRangeCheck(): '(a+b) </>= c &&/|| (a+b) ==/!= 0' if we known 'c' is 'a' or 'b' and is non-zero (PR43259)

[lebedev.ri]

Summary

I realize that these get increasingly boring with each patch,
but i'm running out of commit messages here :/

Alive proofs:
https://rise4fun.com/Alive/8Bq

https://bugs.llvm.org/show_bug.cgi?id=43259

[lebedev.ri]

Fix fold: we need to know that the value we compared with in UnsignedICmp is non-zero, not either of the values in add.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

1413–1415

Comments don't match code.

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

1413–1415

That's D67498

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

1413–1415

Actually, i don't see it?
Comments being added by this patch, or D67498?

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

1413–1415

Disregard - my comment applied to the earlier rev of the patch. Your update happened while I was looking at this.

llvm/test/Transforms/InstSimplify/result-of-add-of-negative-is-non-zero-and-no-underflow.ll

91–92

I thought you proved this test already?
https://rise4fun.com/Alive/WslQ

[lebedev.ri]

llvm/test/Transforms/InstSimplify/result-of-add-of-negative-is-non-zero-and-no-underflow.ll

91–92

Uhm.
Looks like i'm losing the plot because all these patterns in these patches are so similar.
I should wait until three existing patches lang, and then deal with PR43259

[xbolva00]

Status of this patch?

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
 
   ICmpInst::Predicate EqPred;
   if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
       !ICmpInst::isEquality(EqPred))
     return nullptr;
 
   ICmpInst::Predicate UnsignedPred;
 
+  Value *ComparedWith;
+  if (match(UnsignedICmp,
+            m_c_ICmp(UnsignedPred, m_Specific(Y), m_Value(ComparedWith))) &&
+      match(Y, m_c_Add(m_Specific(ComparedWith), m_Value()))) {
+    if (UnsignedICmp->getOperand(0) != Y)
+      UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
+
+    // Given  Y = (A + B)
+    //   Y >= ComparedWith && Y == 0  --> false
+    //   Y <  ComparedWith || Y != 0  --> true
+    // iff ComparedWith is A or B and is non-zero.
+    if (UnsignedPred == ICmpInst::ICMP_UGE && EqPred == ICmpInst::ICMP_EQ &&
+        IsAnd &&
+        isKnownNonZero(ComparedWith, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
+      return ConstantInt::getFalse(UnsignedICmp->getType());
+    if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE &&
+        !IsAnd &&
+        isKnownNonZero(ComparedWith, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
+      return ConstantInt::getTrue(UnsignedICmp->getType());
+  }
+
   Value *A, *B;
   // Y = (A - B);
   if (match(Y, m_Sub(m_Value(A), m_Value(B)))) {
     // A >= B || (A - B) != 0  <-->  true
     // A <  B && (A - B) == 0  <-->  false
     if (match(UnsignedICmp,
               m_c_ICmp(UnsignedPred, m_Specific(A), m_Specific(B))) &&
         ICmpInst::isUnsigned(UnsignedPred)) {
       if (UnsignedICmp->getOperand(0) != A)
         UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
 
       if (UnsignedPred == ICmpInst::ICMP_UGE && EqPred == ICmpInst::ICMP_NE &&
           !IsAnd)
         return ConstantInt::getTrue(UnsignedICmp->getType());
       if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
           IsAnd)
         return ConstantInt::getFalse(UnsignedICmp->getType());
     }

llvm/test/Transforms/InstSimplify/result-of-add-of-negative-is-non-zero-and-no-underflow.ll

 ; If we are checking that the result is not null or no underflow happened,
 ; it is tautological (always-true).
 define i1 @t1(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t1(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[BASE:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = add i8 [[BASE]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[ADJUSTED]], 0
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ult i8 [[ADJUSTED]], [[BASE]]
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i8 %base, 0
   call void @llvm.assume(i1 %cmp)
 
   %adjusted = add i8 %base, %offset
   call void @use8(i8 %adjusted)
   %not_null = icmp ne i8 %adjusted, 0
   %no_underflow = icmp ult i8 %adjusted, %base
   %r = or i1 %not_null, %no_underflow
   ret i1 %r
 }
 define i1 @t2_commutative(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t2_commutative(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[BASE:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = add i8 [[BASE]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[ADJUSTED]], 0
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ugt i8 [[BASE]], [[ADJUSTED]]
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %cmp = icmp slt i8 %base, 0
   call void @llvm.assume(i1 %cmp)
 
   %adjusted = add i8 %base, %offset
   call void @use8(i8 %adjusted)
   %not_null = icmp ne i8 %adjusted, 0
   %no_underflow = icmp ugt i8 %base, %adjusted
   %r = or i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 ; If we are checking that the result is null and underflow happened,
 ; it is tautological (always-false).
 define i1 @t3(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t3(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[BASE:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = add i8 [[BASE]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp eq i8 [[ADJUSTED]], 0
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i8 [[ADJUSTED]], [[BASE]]
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cmp = icmp slt i8 %base, 0
   call void @llvm.assume(i1 %cmp)
 
   %adjusted = add i8 %base, %offset
   call void @use8(i8 %adjusted)
   %not_null = icmp eq i8 %adjusted, 0
   %no_underflow = icmp uge i8 %adjusted, %base
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }
 define i1 @t4_commutative(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t4_commutative(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[BASE:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = add i8 [[BASE]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp eq i8 [[ADJUSTED]], 0
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[BASE]], [[ADJUSTED]]
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cmp = icmp slt i8 %base, 0
   call void @llvm.assume(i1 %cmp)
 
   %adjusted = add i8 %base, %offset
   call void @use8(i8 %adjusted)
   %not_null = icmp eq i8 %adjusted, 0
   %no_underflow = icmp ule i8 %base, %adjusted
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }
+
+; We need to know that the value we compare with here (%base) is non-zero,
+; so knowledge about %offset won't do.
+define i1 @t5_bad(i8 %base, i8 %offset) {
+; CHECK-LABEL: @t5_bad(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[OFFSET:%.*]], 0
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
+; CHECK-NEXT:    [[ADJUSTED:%.*]] = add i8 [[BASE:%.*]], [[OFFSET]]
+; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
+; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[ADJUSTED]], 0
+; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ult i8 [[ADJUSTED]], [[BASE]]
+; CHECK-NEXT:    [[R:%.*]] = or i1 [[NOT_NULL]], [[NO_UNDERFLOW]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %cmp = icmp slt i8 %offset, 0
+  call void @llvm.assume(i1 %cmp)
+
+  %adjusted = add i8 %base, %offset
+  call void @use8(i8 %adjusted)
+  %not_null = icmp ne i8 %adjusted, 0
+  %no_underflow = icmp ult i8 %adjusted, %base
+  %r = or i1 %not_null, %no_underflow
+  ret i1 %r
+}