[InstSimplify] simplifyUnsignedRangeCheck(): handle few tautological cases (PR43251)

[lebedev.ri]

Summary

This is split off from D67356, since these cases produce a constant,
no real need to keep them in instcombine.

Alive proofs:
https://rise4fun.com/Alive/u7Fk
https://rise4fun.com/Alive/4lV

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

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

1388–1389 ↗

(On Diff #219909)

This doesn't seem general enough - we can handle more predicates at least:
https://rise4fun.com/Alive/4lV

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

1388–1389 ↗

(On Diff #219909)

Thanks, will update.

[lebedev.ri]

Support two more patterns as noted in https://reviews.llvm.org/D67498#inline-606717

[spatel]

LGTM

llvm/trunk/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;
 
-  // 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,
+  // Y = (A - B);
+  if (match(Y, m_Sub(m_Value(A), m_Value(B)))) {
+    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);
+
+      // A >=/<= B || (A - B) != 0  <-->  true
+      if ((UnsignedPred == ICmpInst::ICMP_UGE ||
+           UnsignedPred == ICmpInst::ICMP_ULE) &&
+          EqPred == ICmpInst::ICMP_NE && !IsAnd)
+        return ConstantInt::getTrue(UnsignedICmp->getType());
+      // A </> B && (A - B) == 0  <-->  false
+      if ((UnsignedPred == ICmpInst::ICMP_ULT ||
+           UnsignedPred == ICmpInst::ICMP_UGT) &&
+          EqPred == ICmpInst::ICMP_EQ && IsAnd)
+        return ConstantInt::getFalse(UnsignedICmp->getType());
+    }
+
+    // Given  Y = (A - B)
+    //   Y >= A && Y != 0  --> Y >= A  iff B != 0
+    //   Y <  A || Y == 0  --> Y <  A  iff B != 0
+    if (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);

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

 define i1 @t1(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t1(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[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:    ret i1 true
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp uge i8 %base, %offset
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i8 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = or i1 %not_null, %no_underflow

 define i1 @t1_commutativity(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t1_commutativity(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[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:    ret i1 true
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp ule i8 %offset, %base
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i8 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = or i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 ; Likewise, if we are checking that we both got null and overflow happened,
 ; it makes no sense and is always false.
 
 define i1 @t2(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t2(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
 ; CHECK-NEXT:    [[UNDERFLOW:%.*]] = icmp ult i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[UNDERFLOW]])
 ; CHECK-NEXT:    [[NULL:%.*]] = icmp eq i8 [[ADJUSTED]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[NULL]])
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NULL]], [[UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %underflow = icmp ult i8 %base, %offset
   call void @use1(i1 %underflow)
   %null = icmp eq i8 %adjusted, 0
   call void @use1(i1 %null)
   %r = and i1 %null, %underflow

 define i1 @t2_commutativity(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t2_commutativity(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
 ; CHECK-NEXT:    [[UNDERFLOW:%.*]] = icmp ugt i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[UNDERFLOW]])
 ; CHECK-NEXT:    [[NULL:%.*]] = icmp eq i8 [[ADJUSTED]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[NULL]])
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[NULL]], [[UNDERFLOW]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %underflow = icmp ugt i8 %offset, %base
   call void @use1(i1 %underflow)
   %null = icmp eq i8 %adjusted, 0
   call void @use1(i1 %null)
   %r = and i1 %null, %underflow
   ret i1 %r
 }
 
 ; Overflow OR not zero => always true
 define i1 @t3(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t3(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[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:    ret i1 true
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp ule i8 %base, %offset
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i8 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = or i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 ; No overflow and zero => always false
 define i1 @t4(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t4(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
 ; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ugt i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp eq i8 [[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:    ret i1 false
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp ugt i8 %base, %offset
   call void @use1(i1 %no_underflow)
   %not_null = icmp eq i8 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }