From dd3149d57977d0632cfaf24290dd93416fb2a0ef Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Wed, 26 Oct 2011 20:55:21 +0000 Subject: [PATCH] The maximum power of 2 dividing a power of 2 is itself. This occurs in 403.gcc and was spotted by my super-optimizer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143054 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ValueTracking.h | 6 ++-- lib/Analysis/InstructionSimplify.cpp | 9 ++++++ lib/Analysis/ValueTracking.cpp | 37 +++++++++++++++++------- test/Transforms/InstSimplify/AndOrXor.ll | 12 ++++++++ 4 files changed, 52 insertions(+), 12 deletions(-) create mode 100644 test/Transforms/InstSimplify/AndOrXor.ll diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 68263300c72..6f82b2cd98d 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -48,8 +48,10 @@ namespace llvm { /// isPowerOfTwo - Return true if the given value is known to have exactly one /// bit set when defined. For vectors return true if every element is known to /// be a power of two when defined. Supports values with integer or pointer - /// type and vectors of integers. - bool isPowerOfTwo(Value *V, const TargetData *TD = 0, unsigned Depth = 0); + /// type and vectors of integers. If 'OrZero' is set then returns true if the + /// given value is either a power of two or zero. + bool isPowerOfTwo(Value *V, const TargetData *TD = 0, bool OrZero = false, + unsigned Depth = 0); /// isKnownNonZero - Return true if the given value is known to be non-zero /// when defined. For vectors return true if every element is known to be diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 131cc97d237..d9e3400f895 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -1197,6 +1197,15 @@ static Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, (A == Op0 || B == Op0)) return Op0; + // A & (-A) = A if A is a power of two or zero. + if (match(Op0, m_Neg(m_Specific(Op1))) || + match(Op1, m_Neg(m_Specific(Op0)))) { + if (isPowerOfTwo(Op0, TD, /*OrZero*/true)) + return Op0; + if (isPowerOfTwo(Op1, TD, /*OrZero*/true)) + return Op1; + } + // Try some generic simplifications for associative operations. if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT, MaxRecurse)) diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index f2740a6ceb4..9ea27036c8f 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -745,10 +745,15 @@ void llvm::ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, /// bit set when defined. For vectors return true if every element is known to /// be a power of two when defined. Supports values with integer or pointer /// types and vectors of integers. -bool llvm::isPowerOfTwo(Value *V, const TargetData *TD, unsigned Depth) { - if (ConstantInt *CI = dyn_cast(V)) - return CI->getValue().isPowerOf2(); - // TODO: Handle vector constants. +bool llvm::isPowerOfTwo(Value *V, const TargetData *TD, bool OrZero, + unsigned Depth) { + if (Constant *C = dyn_cast(V)) { + if (C->isNullValue()) + return OrZero; + if (ConstantInt *CI = dyn_cast(C)) + return CI->getValue().isPowerOf2(); + // TODO: Handle vector constants. + } // 1 << X is clearly a power of two if the one is not shifted off the end. If // it is shifted off the end then the result is undefined. @@ -765,11 +770,23 @@ bool llvm::isPowerOfTwo(Value *V, const TargetData *TD, unsigned Depth) { return false; if (ZExtInst *ZI = dyn_cast(V)) - return isPowerOfTwo(ZI->getOperand(0), TD, Depth); + return isPowerOfTwo(ZI->getOperand(0), TD, OrZero, Depth); if (SelectInst *SI = dyn_cast(V)) - return isPowerOfTwo(SI->getTrueValue(), TD, Depth) && - isPowerOfTwo(SI->getFalseValue(), TD, Depth); + return isPowerOfTwo(SI->getTrueValue(), TD, OrZero, Depth) && + isPowerOfTwo(SI->getFalseValue(), TD, OrZero, Depth); + + Value *X = 0, *Y = 0; + if (OrZero && match(V, m_And(m_Value(X), m_Value(Y)))) { + // A power of two and'd with anything is a power of two or zero. + if (isPowerOfTwo(X, TD, /*OrZero*/true, Depth) || + isPowerOfTwo(Y, TD, /*OrZero*/true, Depth)) + return true; + // X & (-X) is always a power of two or zero. + if (match(X, m_Neg(m_Specific(Y))) || match(Y, m_Neg(m_Specific(X)))) + return true; + return false; + } // An exact divide or right shift can only shift off zero bits, so the result // is a power of two only if the first operand is a power of two and not @@ -778,7 +795,7 @@ bool llvm::isPowerOfTwo(Value *V, const TargetData *TD, unsigned Depth) { match(V, m_UDiv(m_Value(), m_Value()))) { PossiblyExactOperator *PEO = cast(V); if (PEO->isExact()) - return isPowerOfTwo(PEO->getOperand(0), TD, Depth); + return isPowerOfTwo(PEO->getOperand(0), TD, OrZero, Depth); } return false; @@ -879,9 +896,9 @@ bool llvm::isKnownNonZero(Value *V, const TargetData *TD, unsigned Depth) { } // The sum of a non-negative number and a power of two is not zero. - if (XKnownNonNegative && isPowerOfTwo(Y, TD, Depth)) + if (XKnownNonNegative && isPowerOfTwo(Y, TD, /*OrZero*/false, Depth)) return true; - if (YKnownNonNegative && isPowerOfTwo(X, TD, Depth)) + if (YKnownNonNegative && isPowerOfTwo(X, TD, /*OrZero*/false, Depth)) return true; } // X * Y. diff --git a/test/Transforms/InstSimplify/AndOrXor.ll b/test/Transforms/InstSimplify/AndOrXor.ll new file mode 100644 index 00000000000..3d04d584f48 --- /dev/null +++ b/test/Transforms/InstSimplify/AndOrXor.ll @@ -0,0 +1,12 @@ +; RUN: opt < %s -instsimplify -S | FileCheck %s + +define i64 @pow2(i32 %x) { +; CHECK: @pow2 + %negx = sub i32 0, %x + %x2 = and i32 %x, %negx + %e = zext i32 %x2 to i64 + %nege = sub i64 0, %e + %e2 = and i64 %e, %nege + ret i64 %e2 +; CHECK: ret i64 %e +} -- 2.34.1