[InstSimplify] try to eliminate icmp Pred (add nsw X, C1), C2

[spatel]

Summary

I was surprised to see that we're missing icmp folds based on 'add nsw' in InstCombine, but I think we should handle the 'InstSimplify' cases first because that could make the InstCombine code simpler.

Here's an attempt to prove the logic with Alive:
http://rise4fun.com/Alive/g5Q

gcc has had these kinds of folds since at least v4.4 based on:
https://godbolt.org/g/J1nh5Q

[nlopes]

Alive is still not great for thins kind of patch; I guess it needs some macro support.
But you can use a little more general preconditions like this: http://rise4fun.com/Alive/Tz0

Regardless, the patch LGTM.

[spatel]

In D29053#654651, @nlopes wrote:

Alive is still not great for thins kind of patch; I guess it needs some macro support.
But you can use a little more general preconditions like this: http://rise4fun.com/Alive/Tz0

Thanks! It's a good sign when people can mostly use the product without reading any docs or code. :)

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

 /// Many binary operators with a constant operand have an easy-to-compute
 /// range of outputs. This can be used to fold a comparison to always true or
 /// always false.
 static void setLimitsForBinOp(BinaryOperator &BO, APInt &Lower, APInt &Upper) {
   unsigned Width = Lower.getBitWidth();
   const APInt *C;
   switch (BO.getOpcode()) {
   case Instruction::Add:
-    if (BO.hasNoUnsignedWrap() && match(BO.getOperand(1), m_APInt(C)))
+    if (match(BO.getOperand(1), m_APInt(C)) && *C != 0) {
+      // FIXME: If we have both nuw and nsw, we should reduce the range further.
+      if (BO.hasNoUnsignedWrap()) {
         // 'add nuw x, C' produces [C, UINT_MAX].
         Lower = *C;
+      } else if (BO.hasNoSignedWrap()) {
+        if (C->isNegative()) {
+          // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C].
+          Lower = APInt::getSignedMinValue(Width);
+          Upper = APInt::getSignedMaxValue(Width) + *C + 1;
+        } else {
+          // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX].
+          Lower = APInt::getSignedMinValue(Width) + *C;
+          Upper = APInt::getSignedMaxValue(Width) + 1;
+        }
+      }
+    }
     break;
 
   case Instruction::And:
     if (match(BO.getOperand(1), m_APInt(C)))
       // 'and x, C' produces [0, C].
       Upper = *C + 1;
     break;
 

llvm/trunk/test/Transforms/InstSimplify/icmp-constant.ll

;
   %cmp = icmp ne <2 x i32> %add, <i32 12, i32 12>
   ret <2 x i1> %cmp
 }
 
 ; The upper bound of the 'add' is 0.
 
 define i1 @add_nsw_neg_const1(i32 %x) {
 ; CHECK-LABEL: @add_nsw_neg_const1(
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, -2147483647
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[ADD]], 0
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %add = add nsw i32 %x, -2147483647
   %cmp = icmp sgt i32 %add, 0
   ret i1 %cmp
 }
 
 ; InstCombine can fold this, but not InstSimplify.
 
 define i1 @add_nsw_neg_const2(i32 %x) {
 ; CHECK-LABEL: @add_nsw_neg_const2(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, -2147483647
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[ADD]], -1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i32 %x, -2147483647
   %cmp = icmp sgt i32 %add, -1
   ret i1 %cmp
 }
 
 ; The upper bound of the 'add' is 1 (move the constants to prove we're doing range-based analysis).
 
 define i1 @add_nsw_neg_const3(i32 %x) {
 ; CHECK-LABEL: @add_nsw_neg_const3(
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, -2147483646
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[ADD]], 1
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %add = add nsw i32 %x, -2147483646
   %cmp = icmp sgt i32 %add, 1
   ret i1 %cmp
 }
 
 ; InstCombine can fold this, but not InstSimplify.
 
 define i1 @add_nsw_neg_const4(i32 %x) {
 ; CHECK-LABEL: @add_nsw_neg_const4(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, -2147483646
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[ADD]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i32 %x, -2147483646
   %cmp = icmp sgt i32 %add, 0
   ret i1 %cmp
 }
 
 ; The upper bound of the 'add' is 2147483647 - 42 = 2147483605 (move the constants again and try a different cmp predicate).
 
 define i1 @add_nsw_neg_const5(i32 %x) {
 ; CHECK-LABEL: @add_nsw_neg_const5(
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, -42
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[ADD]], 2147483606
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %add = add nsw i32 %x, -42
   %cmp = icmp ne i32 %add, 2147483606
   ret i1 %cmp
 }
 
 ; InstCombine can fold this, but not InstSimplify.
 
 define i1 @add_nsw_neg_const6(i32 %x) {
 ; CHECK-LABEL: @add_nsw_neg_const6(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, -42
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[ADD]], 2147483605
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i32 %x, -42
   %cmp = icmp ne i32 %add, 2147483605
   ret i1 %cmp
 }
 
 ; The lower bound of the 'add' is -1.
 
 define i1 @add_nsw_pos_const1(i32 %x) {
 ; CHECK-LABEL: @add_nsw_pos_const1(
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, 2147483647
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD]], -1
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %add = add nsw i32 %x, 2147483647
   %cmp = icmp slt i32 %add, -1
   ret i1 %cmp
 }
 
 ; InstCombine can fold this, but not InstSimplify.
 
 define i1 @add_nsw_pos_const2(i32 %x) {
 ; CHECK-LABEL: @add_nsw_pos_const2(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, 2147483647
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i32 %x, 2147483647
   %cmp = icmp slt i32 %add, 0
   ret i1 %cmp
 }
 
 ; The lower bound of the 'add' is -2 (move the constants to prove we're doing range-based analysis).
 
 define i1 @add_nsw_pos_const3(i32 %x) {
 ; CHECK-LABEL: @add_nsw_pos_const3(
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, 2147483646
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD]], -2
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %add = add nsw i32 %x, 2147483646
   %cmp = icmp slt i32 %add, -2
   ret i1 %cmp
 }
 
 ; InstCombine can fold this, but not InstSimplify.
 
 define i1 @add_nsw_pos_const4(i32 %x) {
 ; CHECK-LABEL: @add_nsw_pos_const4(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, 2147483646
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD]], -1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i32 %x, 2147483646
   %cmp = icmp slt i32 %add, -1
   ret i1 %cmp
 }
 
 ; The lower bound of the 'add' is -2147483648 + 42 = -2147483606 (move the constants again and change the cmp predicate).
 
 define i1 @add_nsw_pos_const5(i32 %x) {
 ; CHECK-LABEL: @add_nsw_pos_const5(
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, 42
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[ADD]], -2147483607
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %add = add nsw i32 %x, 42
   %cmp = icmp eq i32 %add, -2147483607
   ret i1 %cmp
 }
 
 ; InstCombine can fold this, but not InstSimplify.
 
 define i1 @add_nsw_pos_const6(i32 %x) {
 ; CHECK-LABEL: @add_nsw_pos_const6(
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 %x, 42
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[ADD]], -2147483606
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = add nsw i32 %x, 42
   %cmp = icmp eq i32 %add, -2147483606
   ret i1 %cmp
 }
 
 ; Verify that vectors work too.
 
 define <2 x i1> @add_nsw_pos_const5_splat_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @add_nsw_pos_const5_splat_vec(
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw <2 x i32> %x, <i32 42, i32 42>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[ADD]], <i32 -2147483607, i32 -2147483607>
-; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+; CHECK-NEXT:    ret <2 x i1> <i1 true, i1 true>
 ;
   %add = add nsw <2 x i32> %x, <i32 42, i32 42>
   %cmp = icmp ne <2 x i32> %add, <i32 -2147483607, i32 -2147483607>
   ret <2 x i1> %cmp
 }