diff options
author | Dinesh Dwivedi <dinesh.d@samsung.com> | 2014-06-19 10:36:52 +0000 |
---|---|---|
committer | Dinesh Dwivedi <dinesh.d@samsung.com> | 2014-06-19 10:36:52 +0000 |
commit | 85386a3de9ebcbf688c0cb864fc26c62fa5220f3 (patch) | |
tree | de6c9b9c192f235da0fb9f92a28188e9c3cbab19 /lib/Transforms | |
parent | cfdf8052865b01e8b8d321640c3f51ff938cc3c4 (diff) | |
download | llvm-85386a3de9ebcbf688c0cb864fc26c62fa5220f3.tar.gz llvm-85386a3de9ebcbf688c0cb864fc26c62fa5220f3.tar.bz2 llvm-85386a3de9ebcbf688c0cb864fc26c62fa5220f3.tar.xz |
Added instruction combine to transform few more negative values addition to subtraction (Part 1)
This patch enables transforms for following patterns.
(x + (~(y & c) + 1) --> x - (y & c)
(x + (~((y >> z) & c) + 1) --> x - ((y>>z) & c)
Differential Revision: http://reviews.llvm.org/D3733
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@211266 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Transforms')
-rw-r--r-- | lib/Transforms/InstCombine/InstCombineAddSub.cpp | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/lib/Transforms/InstCombine/InstCombineAddSub.cpp index 77b2404b49..5b28d8ccb5 100644 --- a/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -954,6 +954,48 @@ bool InstCombiner::WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS) { return true; return false; + } + +// Checks if any operand is negative and we can convert add to sub. +// This function checks for following negative patterns +// ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C)) +// TODO: ADD(XOR(AND(Z, ~C), ~C), 1) == NEG(OR(Z, C)) if C is even +// TODO: XOR(AND(Z, ~C), (~C + 1)) == NEG(OR(Z, C)) if C is odd +Value *checkForNegativeOperand(BinaryOperator &I, + InstCombiner::BuilderTy *Builder) { + Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); + + // This function creates 2 instructions to replace ADD, we need at least one + // of LHS or RHS to have one use to ensure benefit in transform. + if (!LHS->hasOneUse() && !RHS->hasOneUse()) + return nullptr; + + bool IHasNSW = I.hasNoSignedWrap(); + bool IHasNUW = I.hasNoUnsignedWrap(); + + Value *X = nullptr, *Y = nullptr, *Z = nullptr; + const APInt *C1 = nullptr, *C2 = nullptr; + + // if ONE is on other side, swap + if (match(RHS, m_Add(m_Value(X), m_One()))) + std::swap(LHS, RHS); + + if (match(LHS, m_Add(m_Value(X), m_One()))) { + // if XOR on other side, swap + if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1)))) + std::swap(X, RHS); + + // X = XOR(Y, C1), Y = OR(Z, C2), C2 = NOT(C1) ==> X == NOT(AND(Z, C1)) + // ADD(ADD(X, 1), RHS) == ADD(X, ADD(RHS, 1)) == SUB(RHS, AND(Z, C1)) + if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) { + if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C2 == ~(*C1))) { + Value *NewAnd = Builder->CreateAnd(Z, *C1); + return Builder->CreateSub(RHS, NewAnd, "", IHasNUW, IHasNSW); + } + } + } + + return nullptr; } Instruction *InstCombiner::visitAdd(BinaryOperator &I) { @@ -1065,6 +1107,9 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { if (Value *V = dyn_castNegVal(RHS)) return BinaryOperator::CreateSub(LHS, V); + if (Value *V = checkForNegativeOperand(I, Builder)) + return ReplaceInstUsesWith(I, V); + // A+B --> A|B iff A and B have no bits set in common. if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { APInt LHSKnownOne(IT->getBitWidth(), 0); |