[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 ↗

(On Diff #97237)

Space between 'if' and 'parenthese'

871 ↗

(On Diff #97237)

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 ↗

(On Diff #97237)

Space between 'if' and 'parenthese'

885 ↗

(On Diff #97237)

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 ↗

(On Diff #97237)

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

866 ↗

(On Diff #97237)

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

871 ↗

(On Diff #97237)

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?

llvm/trunk/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

llvm/trunk/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
+}

llvm/trunk/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