diff options
author | Kay Tiong Khoo <kkhoo@perfwizard.com> | 2013-12-19 18:07:17 +0000 |
---|---|---|
committer | Kay Tiong Khoo <kkhoo@perfwizard.com> | 2013-12-19 18:07:17 +0000 |
commit | 79b37835f931be609e6c5530934135e7726ee40a (patch) | |
tree | caf2f925dec30a9520a845413845b581d68ab45e /lib | |
parent | 23b78795840aadc327fa9b74ef83c2a28dbaa0ab (diff) | |
download | llvm-79b37835f931be609e6c5530934135e7726ee40a.tar.gz llvm-79b37835f931be609e6c5530934135e7726ee40a.tar.bz2 llvm-79b37835f931be609e6c5530934135e7726ee40a.tar.xz |
Improved fix for PR17827 (instcombine of shift/and/compare).
This change fixes the case of arithmetic shift right - do not attempt to fold that case.
This change also relaxes the conditions when attempting to fold the logical shift right and shift left cases.
No additional IR-level test cases included at this time. See http://llvm.org/bugs/show_bug.cgi?id=17827 for proofs that these are correct transformations.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197705 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Transforms/InstCombine/InstCombineCompares.cpp | 54 |
1 files changed, 32 insertions, 22 deletions
diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index 150450a870..eb2cc918ce 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -1195,33 +1195,43 @@ Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI, ConstantInt *ShAmt; ShAmt = Shift ? dyn_cast<ConstantInt>(Shift->getOperand(1)) : 0; - // We can fold this as long as we can't shift unknown bits - // into the mask. This can happen with signed shift - // rights, as they sign-extend. With logical shifts, - // we must still make sure the comparison is not signed - // because we are effectively changing the - // position of the sign bit (PR17827). - // TODO: We can relax these constraints a bit more. + // This seemingly simple opportunity to fold away a shift turns out to + // be rather complicated. See PR17827 + // ( http://llvm.org/bugs/show_bug.cgi?id=17827 ) for details. if (ShAmt) { bool CanFold = false; unsigned ShiftOpcode = Shift->getOpcode(); if (ShiftOpcode == Instruction::AShr) { - // To test for the bad case of the signed shr, see if any - // of the bits shifted in could be tested after the mask. - Type *ShiftType = Shift->getType(); - Type *AndType = AndCst->getType(); - - unsigned ShiftBitWidth = ShiftType->getPrimitiveSizeInBits(); - unsigned AndBitWidth = AndType->getPrimitiveSizeInBits(); - - int ShAmtVal = ShiftBitWidth - ShAmt->getLimitedValue(ShiftBitWidth); - - if ((APInt::getHighBitsSet(AndBitWidth, AndBitWidth - ShAmtVal) & - AndCst->getValue()) == 0) + // There may be some constraints that make this possible, + // but nothing simple has been discovered yet. + CanFold = false; + } else if (ShiftOpcode == Instruction::Shl) { + // For a left shift, we can fold if the comparison is not signed. + // We can also fold a signed comparison if the mask value and + // comparison value are not negative. These constraints may not be + // obvious, but we can prove that they are correct using an SMT + // solver such as "Z3" : + // http://rise4fun.com/Z3/DyMp + if (!ICI.isSigned() || (!AndCst->isNegative() && !RHS->isNegative())) CanFold = true; - } else if (ShiftOpcode == Instruction::Shl || - ShiftOpcode == Instruction::LShr) { - CanFold = !ICI.isSigned(); + } else if (ShiftOpcode == Instruction::LShr) { + // For a logical right shift, we can fold if the comparison is not + // signed. We can also fold a signed comparison if the shifted mask + // value and the shifted comparison value are not negative. + // These constraints may not be obvious, but we can prove that they + // are correct using an SMT solver such as "Z3" : + // http://rise4fun.com/Z3/Tslfh + if (!ICI.isSigned()) + CanFold = true; + else { + ConstantInt *ShiftedAndCst = + cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt)); + ConstantInt *ShiftedRHSCst = + cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt)); + + if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative()) + CanFold = true; + } } if (CanFold) { |