[InstCombine] Merge duplicate functionality between InstCombine and ValueTracking
Summary:
Merge overflow computation for signed add,
appearing both in InstCombine and ValueTracking.
As part of the merge,
cleanup the interface for overflow checks in InstCombine.
Patch by Yoav Ben-Shalom.
Reviewers: craig.topper, majnemer
Reviewed By: craig.topper
Subscribers: takuto.ikuta, llvm-commits
Differential Revision: https://reviews.llvm.org/D32946
llvm-svn: 303029
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
index 3709360..74e3dbb 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -847,92 +847,6 @@
return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
}
-/// \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;
-
- // 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) {
- // There are different heuristics we can use for this. Here are some simple
- // ones.
-
- // If LHS and RHS each have at least two sign bits, the addition will look
- // like
- //
- // XX..... +
- // YY.....
- //
- // If the carry into the most significant position is 0, X and Y can't both
- // be 1 and therefore the carry out of the addition is also 0.
- //
- // If the carry into the most significant position is 1, X and Y can't both
- // be 0 and therefore the carry out of the addition is also 1.
- //
- // Since the carry into the most significant position is always equal to
- // the carry out of the addition, there is no signed overflow.
- if (ComputeNumSignBits(LHS, 0, &CxtI) > 1 &&
- ComputeNumSignBits(RHS, 0, &CxtI) > 1)
- return true;
-
- unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
- KnownBits LHSKnown(BitWidth);
- computeKnownBits(LHS, LHSKnown, 0, &CxtI);
-
- KnownBits RHSKnown(BitWidth);
- computeKnownBits(RHS, RHSKnown, 0, &CxtI);
-
- // Check if carry bit of addition will not cause overflow.
- 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
@@ -1306,8 +1220,7 @@
Constant *CI =
ConstantExpr::getTrunc(RHSC, LHSConv->getOperand(0)->getType());
if (ConstantExpr::getZExt(CI, I.getType()) == RHSC &&
- computeOverflowForUnsignedAdd(LHSConv->getOperand(0), CI, &I) ==
- OverflowResult::NeverOverflows) {
+ willNotOverflowUnsignedAdd(LHSConv->getOperand(0), CI, I)) {
// Insert the new, smaller add.
Value *NewAdd =
Builder->CreateNUWAdd(LHSConv->getOperand(0), CI, "addconv");
@@ -1324,9 +1237,8 @@
if (LHSConv->getOperand(0)->getType() ==
RHSConv->getOperand(0)->getType() &&
(LHSConv->hasOneUse() || RHSConv->hasOneUse()) &&
- computeOverflowForUnsignedAdd(LHSConv->getOperand(0),
- RHSConv->getOperand(0),
- &I) == OverflowResult::NeverOverflows) {
+ willNotOverflowUnsignedAdd(LHSConv->getOperand(0),
+ RHSConv->getOperand(0), I)) {
// Insert the new integer add.
Value *NewAdd = Builder->CreateNUWAdd(
LHSConv->getOperand(0), RHSConv->getOperand(0), "addconv");
@@ -1368,15 +1280,13 @@
}
// TODO(jingyue): Consider WillNotOverflowSignedAdd and
- // WillNotOverflowUnsignedAdd to reduce the number of invocations of
+ // willNotOverflowUnsignedAdd to reduce the number of invocations of
// computeKnownBits.
if (!I.hasNoSignedWrap() && WillNotOverflowSignedAdd(LHS, RHS, I)) {
Changed = true;
I.setHasNoSignedWrap(true);
}
- if (!I.hasNoUnsignedWrap() &&
- computeOverflowForUnsignedAdd(LHS, RHS, &I) ==
- OverflowResult::NeverOverflows) {
+ if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedAdd(LHS, RHS, I)) {
Changed = true;
I.setHasNoUnsignedWrap(true);
}