Reapply commit 143028 with a fix: the problem was casting a ConstantExpr Mul
using BinaryOperator (which only works for instructions) when it should have
been a cast to OverflowingBinaryOperator (which also works for constants).
While there, correct a few other dubious looking uses of BinaryOperator.
Thanks to Chad Rosier for the testcase. Original commit message:
My super-optimizer noticed that we weren't folding this expression to
true: (x *nsw x) sgt 0, where x = (y | 1). This occurs in 464.h264ref.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143125 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp
index d9e3400..31cbbba 100644
--- a/lib/Analysis/InstructionSimplify.cpp
+++ b/lib/Analysis/InstructionSimplify.cpp
@@ -758,7 +758,8 @@
Value *X = 0, *Y = 0;
if ((match(Op0, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op1) || // (X / Y) * Y
(match(Op1, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op0)) { // Y * (X / Y)
- BinaryOperator *Div = cast<BinaryOperator>(Y == Op1 ? Op0 : Op1);
+ PossiblyExactOperator *Div =
+ cast<PossiblyExactOperator>(Y == Op1 ? Op0 : Op1);
if (Div->isExact())
return X;
}
@@ -842,7 +843,7 @@
Value *X = 0, *Y = 0;
if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) {
if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1
- BinaryOperator *Mul = cast<BinaryOperator>(Op0);
+ OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0);
// If the Mul knows it does not overflow, then we are good to go.
if ((isSigned && Mul->hasNoSignedWrap()) ||
(!isSigned && Mul->hasNoUnsignedWrap()))
diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index 9a234c0..90757f9 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -201,9 +201,36 @@
ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero, KnownOne, TD,Depth+1);
ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD,
Depth+1);
- assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
- assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
-
+ assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
+ assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
+
+ bool isKnownNegative = false;
+ bool isKnownNonNegative = false;
+ // If the multiplication is known not to overflow, compute the sign bit.
+ if (Mask.isNegative() &&
+ cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap()) {
+ Value *Op1 = I->getOperand(1), *Op2 = I->getOperand(0);
+ if (Op1 == Op2) {
+ // The product of a number with itself is non-negative.
+ isKnownNonNegative = true;
+ } else {
+ bool isKnownNonNegative1 = KnownZero.isNegative();
+ bool isKnownNonNegative2 = KnownZero2.isNegative();
+ bool isKnownNegative1 = KnownOne.isNegative();
+ bool isKnownNegative2 = KnownOne2.isNegative();
+ // The product of two numbers with the same sign is non-negative.
+ isKnownNonNegative = (isKnownNegative1 && isKnownNegative2) ||
+ (isKnownNonNegative1 && isKnownNonNegative2);
+ // The product of a negative number and a non-negative number is either
+ // negative or zero.
+ if (!isKnownNonNegative)
+ isKnownNegative = (isKnownNegative1 && isKnownNonNegative2 &&
+ isKnownNonZero(Op2, TD, Depth)) ||
+ (isKnownNegative2 && isKnownNonNegative1 &&
+ isKnownNonZero(Op1, TD, Depth));
+ }
+ }
+
// If low bits are zero in either operand, output low known-0 bits.
// Also compute a conserative estimate for high known-0 bits.
// More trickiness is possible, but this is sufficient for the
@@ -220,6 +247,12 @@
KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
APInt::getHighBitsSet(BitWidth, LeadZ);
KnownZero &= Mask;
+
+ if (isKnownNonNegative)
+ KnownZero.setBit(BitWidth - 1);
+ else if (isKnownNegative)
+ KnownOne.setBit(BitWidth - 1);
+
return;
}
case Instruction::UDiv: {
@@ -784,7 +817,7 @@
}
// The remaining tests are all recursive, so bail out if we hit the limit.
- if (Depth++ == MaxDepth)
+ if (Depth++ >= MaxDepth)
return false;
unsigned BitWidth = getBitWidth(V->getType(), TD);
@@ -802,7 +835,7 @@
// if the lowest bit is shifted off the end.
if (BitWidth && match(V, m_Shl(m_Value(X), m_Value(Y)))) {
// shl nuw can't remove any non-zero bits.
- BinaryOperator *BO = cast<BinaryOperator>(V);
+ OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
if (BO->hasNoUnsignedWrap())
return isKnownNonZero(X, TD, Depth);
@@ -816,7 +849,7 @@
// defined if the sign bit is shifted off the end.
else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) {
// shr exact can only shift out zero bits.
- BinaryOperator *BO = cast<BinaryOperator>(V);
+ PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V);
if (BO->isExact())
return isKnownNonZero(X, TD, Depth);
@@ -827,7 +860,7 @@
}
// div exact can only produce a zero if the dividend is zero.
else if (match(V, m_IDiv(m_Value(X), m_Value()))) {
- BinaryOperator *BO = cast<BinaryOperator>(V);
+ PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V);
if (BO->isExact())
return isKnownNonZero(X, TD, Depth);
}
@@ -868,6 +901,15 @@
if (YKnownNonNegative && isPowerOfTwo(X, TD, /*OrZero*/false, Depth))
return true;
}
+ // X * Y.
+ else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) {
+ OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
+ // If X and Y are non-zero then so is X * Y as long as the multiplication
+ // does not overflow.
+ if ((BO->hasNoSignedWrap() || BO->hasNoUnsignedWrap()) &&
+ isKnownNonZero(X, TD, Depth) && isKnownNonZero(Y, TD, Depth))
+ return true;
+ }
// (C ? X : Y) != 0 if X != 0 and Y != 0.
else if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
if (isKnownNonZero(SI->getTrueValue(), TD, Depth) &&