[InstSimplify] Fold compare of no-wrap subtract

[hasyimibhar]

Summary

Simplify (icmp nsw|nuw (sub X, C2), C) to true|false.

[hasyimibhar]

Add missing CHECK

llvm/lib/Analysis/InstructionSimplify.cpp

if (LHSKnown.isNonNegative() &&
       return getTrue(ITy);
     break;
   }
   }
 
   return nullptr;
 }
 
+// Simplify (icmp (sub nuw/nsw C2, Y), C) to true/false.
+static Value *simplifyICmpWithNoWrapSub(CmpInst::Predicate Pred,
+                                        BinaryOperator *Sub, Value *RHS,
+                                        const InstrInfoQuery &IIQ) {
+  const APInt *C, *C2;
+
+  if (Sub->getOpcode() != Instruction::Sub)
+    return nullptr;
+  if (!match(RHS, m_APInt(C)))
+    return nullptr;
+  if (!match(Sub->getOperand(0), m_APInt(C2)))
+    return nullptr;
+
+  bool isNSW = IIQ.hasNoSignedWrap(Sub);
+  bool isNUW = IIQ.hasNoUnsignedWrap(Sub);
+
+  if (!(CmpInst::isUnsigned(Pred) && isNUW) &&
+      !(CmpInst::isSigned(Pred) && isNSW))
+    return nullptr;
+
+  Type *ITy = GetCompareTy(RHS); // The return type.
+
+  ConstantRange RHS_CR = ConstantRange::makeExactICmpRegion(Pred, *C);
+
+  if (RHS_CR.isEmptySet())
+    return ConstantInt::getFalse(ITy);
+  if (RHS_CR.isFullSet())
+    return ConstantInt::getTrue(ITy);
+
+  unsigned noWrapKind;
+  if (isNSW)
+    noWrapKind = OverflowingBinaryOperator::NoSignedWrap;
+  else
+    noWrapKind = OverflowingBinaryOperator::NoUnsignedWrap;
+
+  ConstantRange LHS_CR = ConstantRange(*C2).subWithNoWrap(
+      ConstantRange::getFull(C2->getBitWidth()), noWrapKind);
+
+  if (!LHS_CR.isFullSet()) {
+    if (RHS_CR.contains(LHS_CR))
+      return ConstantInt::getTrue(ITy);
+    if (RHS_CR.inverse().contains(LHS_CR))
+      return ConstantInt::getFalse(ITy);
+  }
+
+  return nullptr;
+}
+
 static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS,
                                        Value *RHS, const InstrInfoQuery &IIQ) {
   Type *ITy = GetCompareTy(RHS); // The return type.
 
   Value *X;
   // Sign-bit checks can be optimized to true/false after unsigned
   // floating-point casts:
   // icmp slt (bitcast (uitofp X)),  0 --> false
if ((match(LBO, m_UDiv(m_Mul(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) &&
       (match(LBO, m_UDiv(m_Shl(m_Specific(RHS), m_APInt(C1)), m_APInt(C2))) &&
        (APInt(C1->getBitWidth(), 1) << *C1).ule(*C2))) {
     if (Pred == ICmpInst::ICMP_UGT)
       return getFalse(ITy);
     if (Pred == ICmpInst::ICMP_ULE)
       return getTrue(ITy);
   }
 
+  if (Value *V = simplifyICmpWithNoWrapSub(Pred, LBO, RHS, Q.IIQ))
+    return V;
+
   return nullptr;
 }
 
 
 // If only one of the icmp's operands has NSW flags, try to prove that:
 //
 //   icmp slt (x + C1), (x +nsw C2)
 //

llvm/test/Transforms/InstSimplify/icmp.ll

loop:
   %p1 = phi i32 [ %x, %entry ], [ %sub1, %loop ]
   %p2 = phi i32 [ %x, %entry ], [ %sub2, %loop ]
   %cmp = icmp eq i32 %p1, %p2
   %user = zext i1 %cmp to i32
   %sub1 = sub i32 %p1, %p2
   %sub2 = sub i32 42, %p2
   br label %loop
 }
+
+define i1 @test_negative_combined_sub_signed_overflow(i8 %x) {
+; CHECK-LABEL: @test_negative_combined_sub_signed_overflow(
+; CHECK-NEXT:    ret i1 false
+;
+  %y = sub nsw i8 127, %x
+  %z = icmp slt i8 %y, -1
+  ret i1 %z
+}
+
+define i1 @test_negative_combined_sub_unsigned_overflow(i64 %x) {
+; CHECK-LABEL: @test_negative_combined_sub_unsigned_overflow(
+; CHECK-NEXT:    ret i1 true
+;
+  %y = sub nuw i64 10, %x
+  %z = icmp ult i64 %y, 11
+  ret i1 %z
+}