diff options
author | David Majnemer <david.majnemer@gmail.com> | 2013-06-29 08:40:07 +0000 |
---|---|---|
committer | David Majnemer <david.majnemer@gmail.com> | 2013-06-29 08:40:07 +0000 |
commit | f723e5d1c290a00378d3fc10c7ef502692e0710e (patch) | |
tree | d3a72dc5525fcdedce45406dafb31d0d8962cf91 /lib | |
parent | d4a9ebc7341a1ed066fcdff8e7e4e9cbf1bc4368 (diff) | |
download | external_llvm-f723e5d1c290a00378d3fc10c7ef502692e0710e.zip external_llvm-f723e5d1c290a00378d3fc10c7ef502692e0710e.tar.gz external_llvm-f723e5d1c290a00378d3fc10c7ef502692e0710e.tar.bz2 |
InstCombine: Be more agressive optimizing 'udiv' instrs with 'select' denoms
Real world code sometimes has the denominator of a 'udiv' be a
'select'. LLVM can handle such cases but only when the 'select'
operands are symmetric in structure (both select operands are a constant
power of two or a left shift, etc.). This falls apart if we are dealt a
'udiv' where the code is not symetric or if the select operands lead us
to more select instructions.
Instead, we should treat the LHS and each select operand as a distinct
divide operation and try to optimize them independently. If we can
to simplify each operation, then we can replace the 'udiv' with, say, a
'lshr' that has a new select with a bunch of new operands for the
select.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185257 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 121 |
1 files changed, 77 insertions, 44 deletions
diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index d0d4f41..bc5d699 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -705,26 +705,27 @@ static Value *dyn_castZExtVal(Value *V, Type *Ty) { return 0; } -Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { - Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - - if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) - return ReplaceInstUsesWith(I, V); - - // Handle the integer div common cases - if (Instruction *Common = commonIDivTransforms(I)) - return Common; +const unsigned MaxDepth = 6; +// \brief Recursively visits the possible right hand operands of a udiv +// instruction, seeing through select instructions, to determine if we can +// replace the udiv with something simpler. If we find that an operand is not +// able to simplify the udiv, we abort the entire transformation. +// +// Inserts any intermediate instructions used for the simplification into +// NewInstrs and returns a new instruction that depends upon them. +static Instruction *visitUDivOperand(Value *Op0, Value *Op1, + const BinaryOperator &I, + SmallVectorImpl<Instruction *> &NewInstrs, + unsigned Depth = 0) { { // X udiv 2^C -> X >> C // Check to see if this is an unsigned division with an exact power of 2, // if so, convert to a right shift. const APInt *C; if (match(Op1, m_Power2(C))) { - BinaryOperator *LShr = - BinaryOperator::CreateLShr(Op0, - ConstantInt::get(Op0->getType(), - C->logBase2())); + BinaryOperator *LShr = BinaryOperator::CreateLShr( + Op0, ConstantInt::get(Op0->getType(), C->logBase2())); if (I.isExact()) LShr->setIsExact(); return LShr; } @@ -733,51 +734,68 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) { // X udiv C, where C >= signbit if (C->getValue().isNegative()) { - Value *IC = Builder->CreateICmpULT(Op0, C); + ICmpInst *IC = new ICmpInst(ICmpInst::ICMP_ULT, Op0, C); + NewInstrs.push_back(IC); + return SelectInst::Create(IC, Constant::getNullValue(I.getType()), ConstantInt::get(I.getType(), 1)); } } - // (x lshr C1) udiv C2 --> x udiv (C2 << C1) - if (ConstantInt *C2 = dyn_cast<ConstantInt>(Op1)) { - Value *X; - ConstantInt *C1; - if (match(Op0, m_LShr(m_Value(X), m_ConstantInt(C1)))) { - APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); - return BinaryOperator::CreateUDiv(X, Builder->getInt(NC)); - } - } - // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) { const APInt *CI; Value *N; if (match(Op1, m_Shl(m_Power2(CI), m_Value(N))) || match(Op1, m_ZExt(m_Shl(m_Power2(CI), m_Value(N))))) { - if (*CI != 1) - N = Builder->CreateAdd(N, - ConstantInt::get(N->getType(), CI->logBase2())); - if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) - N = Builder->CreateZExt(N, Z->getDestTy()); - if (I.isExact()) - return BinaryOperator::CreateExactLShr(Op0, N); - return BinaryOperator::CreateLShr(Op0, N); + if (*CI != 1) { + N = BinaryOperator::CreateAdd( + N, ConstantInt::get(N->getType(), CI->logBase2())); + NewInstrs.push_back(cast<Instruction>(N)); + } + if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) { + N = new ZExtInst(N, Z->getDestTy()); + NewInstrs.push_back(cast<Instruction>(N)); + } + BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N); + if (I.isExact()) LShr->setIsExact(); + return LShr; } } - // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2) - // where C1&C2 are powers of two. - { Value *Cond; const APInt *C1, *C2; - if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { - // Construct the "on true" case of the select - Value *TSI = Builder->CreateLShr(Op0, C1->logBase2(), Op1->getName()+".t", - I.isExact()); + // The remaining tests are all recursive, so bail out if we hit the limit. + if (Depth++ == MaxDepth) + return 0; - // Construct the "on false" case of the select - Value *FSI = Builder->CreateLShr(Op0, C2->logBase2(), Op1->getName()+".f", - I.isExact()); + if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) + if (Instruction *LHS = + visitUDivOperand(Op0, SI->getOperand(1), I, NewInstrs)) { + NewInstrs.push_back(LHS); + if (Instruction *RHS = + visitUDivOperand(Op0, SI->getOperand(2), I, NewInstrs)) { + NewInstrs.push_back(RHS); + return SelectInst::Create(SI->getCondition(), LHS, RHS); + } + } - // construct the select instruction and return it. - return SelectInst::Create(Cond, TSI, FSI); + return 0; +} + +Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { + Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + + if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) + return ReplaceInstUsesWith(I, V); + + // Handle the integer div common cases + if (Instruction *Common = commonIDivTransforms(I)) + return Common; + + // (x lshr C1) udiv C2 --> x udiv (C2 << C1) + if (ConstantInt *C2 = dyn_cast<ConstantInt>(Op1)) { + Value *X; + ConstantInt *C1; + if (match(Op0, m_LShr(m_Value(X), m_ConstantInt(C1)))) { + APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); + return BinaryOperator::CreateUDiv(X, Builder->getInt(NC)); } } @@ -788,6 +806,21 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { I.isExact()), I.getType()); + // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...)))) + SmallVector<Instruction *, 4> NewInstrs; + Instruction *RetI = visitUDivOperand(Op0, Op1, I, NewInstrs); + for (unsigned i = 0, e = NewInstrs.size(); i != e; i++) + // If we managed to replace the UDiv completely, insert the new intermediate + // instructions before where the UDiv was. + // If we couldn't, we must clean up after ourselves by deleting the new + // instructions. + if (RetI) + NewInstrs[i]->insertBefore(&I); + else + delete NewInstrs[i]; + if (RetI) + return RetI; + return 0; } |