diff options
author | Duncan Sands <baldrick@free.fr> | 2011-10-27 19:16:21 +0000 |
---|---|---|
committer | Duncan Sands <baldrick@free.fr> | 2011-10-27 19:16:21 +0000 |
commit | 32a43cc0fc3cd42702d7859eaa58dd42f561a54d (patch) | |
tree | 56449a56539910bed314212d85f556a4d59768c0 | |
parent | 6eb1ed8c9c6a6d3f9b57900c44fc076d08a358bd (diff) | |
download | llvm-32a43cc0fc3cd42702d7859eaa58dd42f561a54d.tar.gz llvm-32a43cc0fc3cd42702d7859eaa58dd42f561a54d.tar.bz2 llvm-32a43cc0fc3cd42702d7859eaa58dd42f561a54d.tar.xz |
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
-rw-r--r-- | lib/Analysis/InstructionSimplify.cpp | 5 | ||||
-rw-r--r-- | lib/Analysis/ValueTracking.cpp | 56 | ||||
-rw-r--r-- | test/Transforms/InstSimplify/2011-10-27-BinOpCrash.ll | 12 | ||||
-rw-r--r-- | test/Transforms/InstSimplify/compare.ll | 31 |
4 files changed, 95 insertions, 9 deletions
diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index d9e3400f89..31cbbba596 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -758,7 +758,8 @@ static Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 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 @@ static Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 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 9a234c068b..90757f9798 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -201,9 +201,36 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, 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 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask, 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 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { } // 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 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { // 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 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { // 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 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { } // 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 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { 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) && diff --git a/test/Transforms/InstSimplify/2011-10-27-BinOpCrash.ll b/test/Transforms/InstSimplify/2011-10-27-BinOpCrash.ll new file mode 100644 index 0000000000..a10081a42d --- /dev/null +++ b/test/Transforms/InstSimplify/2011-10-27-BinOpCrash.ll @@ -0,0 +1,12 @@ +; RUN: opt < %s -instcombine + +@_ZN11xercesc_2_5L11gDigitCharsE = external constant [32 x i16], align 2 +@_ZN11xercesc_2_5L10gBaseCharsE = external constant [354 x i16], align 2 +@_ZN11xercesc_2_5L17gIdeographicCharsE = external constant [7 x i16], align 2 +@_ZN11xercesc_2_5L15gCombiningCharsE = external constant [163 x i16], align 2 + +define i32 @_ZN11xercesc_2_515XMLRangeFactory11buildRangesEv(i32 %x) { + %a = add i32 %x, add (i32 add (i32 ashr (i32 add (i32 mul (i32 ptrtoint ([32 x i16]* @_ZN11xercesc_2_5L11gDigitCharsE to i32), i32 -1), i32 ptrtoint (i16* getelementptr inbounds ([32 x i16]* @_ZN11xercesc_2_5L11gDigitCharsE, i32 0, i32 30) to i32)), i32 1), i32 ashr (i32 add (i32 mul (i32 ptrtoint ([7 x i16]* @_ZN11xercesc_2_5L17gIdeographicCharsE to i32), i32 -1), i32 ptrtoint (i16* getelementptr inbounds ([7 x i16]* @_ZN11xercesc_2_5L17gIdeographicCharsE, i32 0, i32 4) to i32)), i32 1)), i32 8) + %b = add i32 %a, %x + ret i32 %b +} diff --git a/test/Transforms/InstSimplify/compare.ll b/test/Transforms/InstSimplify/compare.ll index 2cbd641a74..3ece118902 100644 --- a/test/Transforms/InstSimplify/compare.ll +++ b/test/Transforms/InstSimplify/compare.ll @@ -323,3 +323,34 @@ define i1 @and1(i32 %X) { ret i1 %B ; CHECK: ret i1 false } + +define i1 @mul1(i32 %X) { +; CHECK: @mul1 +; Square of a non-zero number is non-zero if there is no overflow. + %Y = or i32 %X, 1 + %M = mul nuw i32 %Y, %Y + %C = icmp eq i32 %M, 0 + ret i1 %C +; CHECK: ret i1 false +} + +define i1 @mul2(i32 %X) { +; CHECK: @mul2 +; Square of a non-zero number is positive if there is no signed overflow. + %Y = or i32 %X, 1 + %M = mul nsw i32 %Y, %Y + %C = icmp sgt i32 %M, 0 + ret i1 %C +; CHECK: ret i1 true +} + +define i1 @mul3(i32 %X, i32 %Y) { +; CHECK: @mul3 +; Product of non-negative numbers is non-negative if there is no signed overflow. + %XX = mul nsw i32 %X, %X + %YY = mul nsw i32 %Y, %Y + %M = mul nsw i32 %XX, %YY + %C = icmp sge i32 %M, 0 + ret i1 %C +; CHECK: ret i1 true +} |