[InstCombine][KnownBits] Use KnownBits better to detect nsw adds

[yabash]

Summary

Change checkRippleForAdd from a heuristic to a full check -
if it is provable that the add does not overflow return true, otherwise false.

[craig.topper]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

866

Space between 'if' and 'parenthese'

871

Wrap both MaxLHS and MaxRHS in std::move so we can reuse one of their allocations to hold the addition result when dealing with larger than 64-bit numbers.

880

Space between 'if' and 'parenthese'

885

Wrap both MinLHS and MinRHS in std::move so we can reuse one of their allocations to hold the addition result when dealing with larger than 64-bit numbers.

[craig.topper]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

853

The these parameter names are swapped relative to the caller. Prefer LHS followed by RHS.

866

Also do LHS check first then RHS. Basically as much as possible do everything for LHS before RHS.

871

Or better yet, maybe just use MaxLHS += MaxRHS.

[yabash]

Thanks for the comments, fixed.

I opted for std::move and not += because both don't allocate,
and std::move looks more readable (dedicated name 'Result').
Let me know what you think.

[craig.topper]

LGTM

[yabash]

Thanks!
Can you help with committing?

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (Coeff.isTwo() || Coeff.isMinusTwo()) {
     NeedNeg = Coeff.isMinusTwo();
     return createFAdd(OpndVal, OpndVal);
   }
 
   NeedNeg = false;
   return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
 }
 
-// If one of the operands only has one non-zero bit, and if the other
-// operand has a known-zero bit in a more significant place than it (not
-// including the sign bit) the ripple may go up to and fill the zero, but
-// won't change the sign. For example, (X & ~4) + 1.
-static bool checkRippleForAdd(const APInt &Op0KnownZero,
-                              const APInt &Op1KnownZero) {
-  APInt Op1MaybeOne = ~Op1KnownZero;
-  // Make sure that one of the operand has at most one bit set to 1.
-  if (Op1MaybeOne.countPopulation() != 1)
-    return false;
+/// \brief Return true if we can prove that adding the two values of the
+/// knownbits will not overflow.
+/// Otherwise return false.
+static bool checkRippleForAdd(const KnownBits &LHSKnown,
+                              const KnownBits &RHSKnown) {
+  // Addition of two 2's complement numbers having opposite signs will never
+  // overflow.
+  if ((LHSKnown.isNegative() && RHSKnown.isNonNegative()) ||
+      (LHSKnown.isNonNegative() && RHSKnown.isNegative()))
+    return true;
 
-  // Find the most significant known 0 other than the sign bit.
-  int BitWidth = Op0KnownZero.getBitWidth();
-  APInt Op0KnownZeroTemp(Op0KnownZero);
-  Op0KnownZeroTemp.clearSignBit();
-  int Op0ZeroPosition = BitWidth - Op0KnownZeroTemp.countLeadingZeros() - 1;
-
-  int Op1OnePosition = BitWidth - Op1MaybeOne.countLeadingZeros() - 1;
-  assert(Op1OnePosition >= 0);
-
-  // This also covers the case of no known zero, since in that case
-  // Op0ZeroPosition is -1.
-  return Op0ZeroPosition >= Op1OnePosition;
+  // If either of the values is known to be non-negative, adding them can only
+  // overflow if the second is also non-negative, so we can assume that.
+  // Two non-negative numbers will only overflow if there is a carry to the 
+  // sign bit, so we can check if even when the values are as big as possible
+  // there is no overflow to the sign bit.
+  if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative()) {
+    APInt MaxLHS = ~LHSKnown.Zero;
+    MaxLHS.clearSignBit();
+    APInt MaxRHS = ~RHSKnown.Zero;
+    MaxRHS.clearSignBit();
+    APInt Result = std::move(MaxLHS) + std::move(MaxRHS);
+    return Result.isSignBitClear();
+  }
+
+  // If either of the values is known to be negative, adding them can only
+  // overflow if the second is also negative, so we can assume that.
+  // Two negative number will only overflow if there is no carry to the sign
+  // bit, so we can check if even when the values are as small as possible
+  // there is overflow to the sign bit.
+  if (LHSKnown.isNegative() || RHSKnown.isNegative()) {
+    APInt MinLHS = LHSKnown.One;
+    MinLHS.clearSignBit();
+    APInt MinRHS = RHSKnown.One;
+    MinRHS.clearSignBit();
+    APInt Result = std::move(MinLHS) + std::move(MinRHS);
+    return Result.isSignBitSet();
+  }
+
+  // If we reached here it means that we know nothing about the sign bits.
+  // In this case we can't know if there will be an overflow, since by 
+  // changing the sign bits any two values can be made to overflow.
+  return false;
 }
 
 /// Return true if we can prove that:
 ///    (sext (add LHS, RHS))  === (add (sext LHS), (sext RHS))
 /// This basically requires proving that the add in the original type would not
 /// overflow to change the sign bit or have a carry out.
 bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS,
                                             Instruction &CxtI) {
bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS,
 
   unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
   KnownBits LHSKnown(BitWidth);
   computeKnownBits(LHS, LHSKnown, 0, &CxtI);
 
   KnownBits RHSKnown(BitWidth);
   computeKnownBits(RHS, RHSKnown, 0, &CxtI);
 
-  // Addition of two 2's complement numbers having opposite signs will never
-  // overflow.
-  if ((LHSKnown.One[BitWidth - 1] && RHSKnown.Zero[BitWidth - 1]) ||
-      (LHSKnown.Zero[BitWidth - 1] && RHSKnown.One[BitWidth - 1]))
-    return true;
-
   // Check if carry bit of addition will not cause overflow.
-  if (checkRippleForAdd(LHSKnown.Zero, RHSKnown.Zero))
-    return true;
-  if (checkRippleForAdd(RHSKnown.Zero, LHSKnown.Zero))
+  if (checkRippleForAdd(LHSKnown, RHSKnown))
     return true;
 
   return false;
 }
 
 /// \brief Return true if we can prove that:
 ///    (sub LHS, RHS)  === (sub nsw LHS, RHS)
 /// This basically requires proving that the add in the original type would not

test/Transforms/InstCombine/AddOverFlow.ll

 ; CHECK: add nsw i16 %b, %a
 define i16 @ripple_nsw2(i16 %x, i16 %y) {
   %a = and i16 %y, 1
   %b = and i16 %x, 49151
   %c = add i16 %b, %a
   ret i16 %c
 }
 
+; CHECK-LABEL: @ripple_nsw3
+; CHECK: add nsw i16 %a, %b
+define i16 @ripple_nsw3(i16 %x, i16 %y) {
+  %a = and i16 %y, 43691
+  %b = and i16 %x, 21843
+  %c = add i16 %a, %b
+  ret i16 %c
+}
+
+; Like the previous test, but flip %a and %b
+; CHECK-LABEL: @ripple_nsw4
+; CHECK: add nsw i16 %b, %a
+define i16 @ripple_nsw4(i16 %x, i16 %y) {
+  %a = and i16 %y, 43691
+  %b = and i16 %x, 21843
+  %c = add i16 %b, %a
+  ret i16 %c
+}
+
+; CHECK-LABEL: @ripple_nsw5
+; CHECK: add nsw i16 %a, %b
+define i16 @ripple_nsw5(i16 %x, i16 %y) {
+  %a = or i16 %y, 43691
+  %b = or i16 %x, 54613
+  %c = add i16 %a, %b
+  ret i16 %c
+}
+
+; Like the previous test, but flip %a and %b
+; CHECK-LABEL: @ripple_nsw6
+; CHECK: add nsw i16 %b, %a
+define i16 @ripple_nsw6(i16 %x, i16 %y) {
+  %a = or i16 %y, 43691
+  %b = or i16 %x, 54613
+  %c = add i16 %b, %a
+  ret i16 %c
+}
+
 ; CHECK-LABEL: @ripple_no_nsw1
 ; CHECK: add i32 %a, %x
 define i32 @ripple_no_nsw1(i32 %x, i32 %y) {
 ; We know nothing about %x
   %a = and i32 %y, 1
   %b = add i32 %a, %x
   ret i32 %b
 }
 
 ; CHECK-LABEL: @ripple_no_nsw2
 ; CHECK: add nuw i16 %a, %b
 define i16 @ripple_no_nsw2(i16 %x, i16 %y) {
 ; %a has at most one bit set
   %a = and i16 %y, 1
 
 ; %b has a 0 bit, but it is the sign bit
   %b = and i16 %x, 32767
 
   %c = add i16 %a, %b
   ret i16 %c
 }
+
+; CHECK-LABEL: @ripple_no_nsw3
+; CHECK: add i16 %a, %b
+define i16 @ripple_no_nsw3(i16 %x, i16 %y) {
+  %a = and i16 %y, 43691
+  %b = and i16 %x, 21845
+  %c = add i16 %a, %b
+  ret i16 %c
+}
+
+; Like the previous test, but flip %a and %b
+; CHECK-LABEL: @ripple_no_nsw4
+; CHECK: add i16 %b, %a
+define i16 @ripple_no_nsw4(i16 %x, i16 %y) {
+  %a = and i16 %y, 43691
+  %b = and i16 %x, 21845
+  %c = add i16 %b, %a
+  ret i16 %c
+}
+
+; CHECK-LABEL: @ripple_no_nsw5
+; CHECK: add i16 %a, %b
+define i16 @ripple_no_nsw5(i16 %x, i16 %y) {
+  %a = or i16 %y, 43689
+  %b = or i16 %x, 54613
+  %c = add i16 %a, %b
+  ret i16 %c
+}
+
+; Like the previous test, but flip %a and %b
+; CHECK-LABEL: @ripple_no_nsw6
+; CHECK: add i16 %b, %a
+define i16 @ripple_no_nsw6(i16 %x, i16 %y) {
+  %a = or i16 %y, 43689
+  %b = or i16 %x, 54613
+  %c = add i16 %b, %a
+  ret i16 %c
+}

test/Transforms/InstCombine/demand_shrink_nsw.ll

 ; RUN: opt -instcombine -o - -S %s | FileCheck %s
 
 ; The constant at %v35 should be shrunk, but this must lead to the nsw flag of
 ; %v43 getting removed so that %v44 is not illegally optimized away.
 ; CHECK-LABEL: @foo
-; CHECK: %v35 = add nuw i32 %v34, 1362915575
+; CHECK: %v35 = add nuw nsw i32 %v34, 1362915575
 ; ...
 ; CHECK: add nuw i32 %v42, 1533579450
 ; CHECK-NEXT: %v44 = or i32 %v43, -2147483648
 ; CHECK-NEXT: %v45 = xor i32 %v44, 749011377
 ; CHECK-NEXT: ret i32 %v45
 define i32 @foo(i32 %arg) {
   %v33 = and i32 %arg, 223
   %v34 = xor i32 %v33, 29