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

[spatel]

Summary

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

Here are Alive programs that try to verify the correctness of the logic:
http://rise4fun.com/Alive/GH

(is there a better way to write the no-overflow constraints?)

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

=>

%b = icmp slt %x, C2 - C1

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

=>

%b = icmp sgt %x, C2 - C1

And here are the cases where the subtraction does overflow:
http://rise4fun.com/Alive/ao

Name: slt_overflow_false
Pre: C2 < 0 && C1 >= 0 && (C2 - C1) >= 0
%a = add nsw i8 %x, C1
%b = icmp slt %a, C2

=>

%b = false

Name: slt_overflow_true
Pre: C2 >= 0 && C1 < 0 && (C2 - C1) < 0
%a = add nsw i8 %x, C1
%b = icmp slt %a, C2

=>

%b = true

Name: sgt_overflow_true
Pre: C2 < 0 && C1 >= 0 && (C2 - C1) >= 0
%a = add nsw i8 %x, C1
%b = icmp sgt %a, C2

=>

%b = true

Name: sgt_overflow_false
Pre: C2 >= 0 && C1 < 0 && (C2 - C1) < 0
%a = add nsw i8 %x, C1
%b = icmp sgt %a, C2

=>

%b = false

[nlopes]

LGTM.
The easy way to check for overflow in Alive: http://rise4fun.com/Alive/MH

Regarding the instsimplify ones you mention, I didn't check what's implemented, but they need a precondition stronger than just that C1-C2 overflows: http://rise4fun.com/Alive/TRL

[spatel]

In D29774#674493, @nlopes wrote:

LGTM.
The easy way to check for overflow in Alive: http://rise4fun.com/Alive/MH

Thanks! I should read some docs now. :)
It looks like I should start with the papers and presentations from previous LLVM dev confs...is there also a reference doc for the online tool?

Regarding the instsimplify ones you mention, I didn't check what's implemented, but they need a precondition stronger than just that C1-C2 overflows: http://rise4fun.com/Alive/TRL

We know that those will simplify to true/false in all cases, but we don't know if the result is true or false unless we check the sign of C2:
http://rise4fun.com/Alive/2S

[nlopes]

In D29774#674564, @spatel wrote:

In D29774#674493, @nlopes wrote:

LGTM.
The easy way to check for overflow in Alive: http://rise4fun.com/Alive/MH

Thanks! I should read some docs now. :)
It looks like I should start with the papers and presentations from previous LLVM dev confs...is there also a reference doc for the online tool?

There isn't much available, sorry. I need to write down some documentation.
You can see the list of predicates/functions here (the syntax highlighting code): https://github.com/nunoplopes/alive/blob/newsema/rise4fun/language

Anyway, if there's some feature you are missing let me know ;)

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::foldICmpAddConstant(ICmpInst &Cmp,
   const APInt *C2;
   if (Cmp.isEquality() || !match(Y, m_APInt(C2)))
     return nullptr;
 
   // Fold icmp pred (add X, C2), C.
   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();
   if (Cmp.isSigned()) {
     if (Lower.isSignBit())
       return new ICmpInst(ICmpInst::ICMP_SLT, X, ConstantInt::get(Ty, Upper));
     if (Upper.isSignBit())
       return new ICmpInst(ICmpInst::ICMP_SGE, X, ConstantInt::get(Ty, Lower));
if (BO0 && BO0->getOpcode() == Instruction::Add) {
     A = BO0->getOperand(0);
     B = BO0->getOperand(1);
   }
   if (BO1 && BO1->getOpcode() == Instruction::Add) {
     C = BO1->getOperand(0);
     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,
                         Constant::getNullValue(Op1->getType()));
 
   // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow.
   if ((C == Op0 || D == Op0) && NoOp1WrapProblem)
     return new ICmpInst(Pred, Constant::getNullValue(Op0->getType()),

llvm/trunk/test/Transforms/InstCombine/icmp-add.ll

;
   ret <2 x i1> %c
 }
 
 ; icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2), when C - C2 does not overflow.
 ; This becomes equality because it's at the limit.
 
 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
   %c = icmp slt i8 %b, -27
   ret i1 %c
 }
 
 ; icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2), when C - C2 does not overflow.
 ; This becomes equality because it's at the limit.
 
 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
   %c = icmp slt i8 %b, 27
   ret i1 %c
 }
 
 ; icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2), when C - C2 does not overflow.
 ; Less than the limit, so the predicate doesn't change.
 
 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
   %c = icmp slt i8 %b, -26
   ret i1 %c
 }
 
 ; icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2), when C - C2 does not overflow.
 ; Less than the limit, so the predicate doesn't change.
 
 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
   %c = icmp slt i8 %b, 26
   ret i1 %c
 }
 
 ; icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2), when C - C2 does not overflow.
 ; Try sgt to make sure that works too.
 
 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
   %c = icmp sgt i8 %b, 26
   ret i1 %c
 }
 
 ; 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>
   %c = icmp sgt <2 x i8> %b, <i8 -26, i8 -26>
   ret <2 x i1> %c
 }
 
 ; icmp Pred (add nsw X, C2), C --> icmp Pred X, (C - C2), when C - C2 does not overflow.
 ; Comparison with 0 doesn't need special-casing.
 
 define i1 @slt_zero_add_nsw(i32 %a) {
 ; CHECK-LABEL: @slt_zero_add_nsw(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 %a, -1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i32 %a, 1
   %cmp = icmp slt i32 %add, 0
   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>
   %cmp = icmp slt <2 x i8> %add, zeroinitializer
   ret <2 x i1> %cmp
 }
 
 ; Test the edges - instcombine should not interfere with simplification to constants.