[InstCombine] fold icmp sgt/slt (add nsw X, C2), C --> icmp sgt/slt X, (C - C2)

I found one special case of this transform for 'slt 0', so I removed that and added the general transform.

Alive code to check correctness:

Name: slt_no_overflow
Pre: WillNotOverflowSignedSub(C1, C2)
%a = add nsw i8 %x, C2
%b = icmp slt %a, C1
  =>
%b = icmp slt %x, C1 - C2

Name: sgt_no_overflow
Pre: WillNotOverflowSignedSub(C1, C2)
%a = add nsw i8 %x, C2
%b = icmp sgt %a, C1
  =>
%b = icmp sgt %x, C1 - C2

http://rise4fun.com/Alive/MH

Differential Revision: https://reviews.llvm.org/D29774

llvm-svn: 294898

2 files changed, 25 insertions, 21 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
index e209ae148c6..ce11e470d05 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -2373,6 +2373,22 @@ Instruction *InstCombiner::foldICmpAddConstant(ICmpInst &Cmp,
   Value *X = Add->getOperand(0);
   Type *Ty = Add->getType();
   CmpInst::Predicate Pred = Cmp.getPredicate();
+
+  // If the add does not wrap, we can always adjust the compare by subtracting
+  // the constants. Equality comparisons are handled elsewhere. SGE/SLE are
+  // canonicalized to SGT/SLT.
+  if (Add->hasNoSignedWrap() &&
+      (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT)) {
+    bool Overflow;
+    APInt NewC = C->ssub_ov(*C2, Overflow);
+    // If there is overflow, the result must be true or false.
+    // TODO: Can we assert there is no overflow because InstSimplify always
+    // handles those cases?
+    if (!Overflow)
+      // icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2)
+      return new ICmpInst(Pred, X, ConstantInt::get(Ty, NewC));
+  }
+
   auto CR = ConstantRange::makeExactICmpRegion(Pred, *C).subtract(*C2);
   const APInt &Upper = CR.getUpper();
   const APInt &Lower = CR.getLower();
@@ -2795,12 +2811,6 @@ Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) {
     D = BO1->getOperand(1);
   }
 
-  // icmp (X+cst) < 0 --> X < -cst
-  if (NoOp0WrapProblem && ICmpInst::isSigned(Pred) && match(Op1, m_Zero()))
-    if (ConstantInt *RHSC = dyn_cast_or_null<ConstantInt>(B))
-      if (!RHSC->isMinValue(/*isSigned=*/true))
-        return new ICmpInst(Pred, A, ConstantExpr::getNeg(RHSC));
-
   // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow.
   if ((A == Op1 || B == Op1) && NoOp0WrapProblem)
     return new ICmpInst(Pred, A == Op1 ? B : A,
diff --git a/llvm/test/Transforms/InstCombine/icmp-add.ll b/llvm/test/Transforms/InstCombine/icmp-add.ll
index 971bc33326b..7345621045d 100644
--- a/llvm/test/Transforms/InstCombine/icmp-add.ll
+++ b/llvm/test/Transforms/InstCombine/icmp-add.ll
@@ -88,8 +88,7 @@ define <2 x i1> @test4vec(<2 x i32> %a) {
 
 define i1 @nsw_slt1(i8 %a) {
 ; CHECK-LABEL: @nsw_slt1(
-; CHECK-NEXT:    [[B:%.*]] = add nsw i8 %a, 100
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 [[B]], -27
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 %a, -128
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = add nsw i8 %a, 100
@@ -102,8 +101,7 @@ define i1 @nsw_slt1(i8 %a) {
 
 define i1 @nsw_slt2(i8 %a) {
 ; CHECK-LABEL: @nsw_slt2(
-; CHECK-NEXT:    [[B:%.*]] = add nsw i8 %a, -100
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 [[B]], 27
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i8 %a, 127
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = add nsw i8 %a, -100
@@ -116,8 +114,7 @@ define i1 @nsw_slt2(i8 %a) {
 
 define i1 @nsw_slt3(i8 %a) {
 ; CHECK-LABEL: @nsw_slt3(
-; CHECK-NEXT:    [[B:%.*]] = add nsw i8 %a, 100
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 [[B]], -26
+; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 %a, -126
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = add nsw i8 %a, 100
@@ -130,8 +127,7 @@ define i1 @nsw_slt3(i8 %a) {
 
 define i1 @nsw_slt4(i8 %a) {
 ; CHECK-LABEL: @nsw_slt4(
-; CHECK-NEXT:    [[B:%.*]] = add nsw i8 %a, -100
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 [[B]], 26
+; CHECK-NEXT:    [[C:%.*]] = icmp slt i8 %a, 126
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = add nsw i8 %a, -100
@@ -144,8 +140,7 @@ define i1 @nsw_slt4(i8 %a) {
 
 define i1 @nsw_sgt1(i8 %a) {
 ; CHECK-LABEL: @nsw_sgt1(
-; CHECK-NEXT:    [[B:%.*]] = add nsw i8 %a, -100
-; CHECK-NEXT:    [[C:%.*]] = icmp sgt i8 [[B]], 26
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 %a, 127
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %b = add nsw i8 %a, -100
@@ -155,11 +150,11 @@ define i1 @nsw_sgt1(i8 %a) {
 
 ; icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2), when C - C2 does not overflow.
 ; Try a vector type to make sure that works too.
+; FIXME: This should be 'eq 127' as above.
 
 define <2 x i1> @nsw_sgt2_splat_vec(<2 x i8> %a) {
 ; CHECK-LABEL: @nsw_sgt2_splat_vec(
-; CHECK-NEXT:    [[B:%.*]] = add nsw <2 x i8> %a, <i8 100, i8 100>
-; CHECK-NEXT:    [[C:%.*]] = icmp sgt <2 x i8> [[B]], <i8 -26, i8 -26>
+; CHECK-NEXT:    [[C:%.*]] = icmp sgt <2 x i8> %a, <i8 -126, i8 -126>
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %b = add nsw <2 x i8> %a, <i8 100, i8 100>
@@ -180,12 +175,11 @@ define i1 @slt_zero_add_nsw(i32 %a) {
   ret i1 %cmp
 }
 
-; FIXME: The same fold should work with vectors.
+; The same fold should work with vectors.
 
 define <2 x i1> @slt_zero_add_nsw_splat_vec(<2 x i8> %a) {
 ; CHECK-LABEL: @slt_zero_add_nsw_splat_vec(
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw <2 x i8> %a, <i8 1, i8 1>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[ADD]], zeroinitializer
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> %a, <i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %add = add nsw <2 x i8> %a, <i8 1, i8 1>