diff options
Diffstat (limited to 'lib/Transforms/InstCombine')
6 files changed, 59 insertions, 107 deletions
diff --git a/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/lib/Transforms/InstCombine/InstCombineAddSub.cpp index 4f1f19499768..153a186d5ed4 100644 --- a/lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ b/lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -847,29 +847,49 @@ Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) { return createFMul(OpndVal, Coeff.getValue(Instr->getType())); } -// If one of the operands only has one non-zero bit, and if the other -// operand has a known-zero bit in a more significant place than it (not -// including the sign bit) the ripple may go up to and fill the zero, but -// won't change the sign. For example, (X & ~4) + 1. -static bool checkRippleForAdd(const APInt &Op0KnownZero, - const APInt &Op1KnownZero) { - APInt Op1MaybeOne = ~Op1KnownZero; - // Make sure that one of the operand has at most one bit set to 1. - if (Op1MaybeOne.countPopulation() != 1) - return false; - - // Find the most significant known 0 other than the sign bit. - int BitWidth = Op0KnownZero.getBitWidth(); - APInt Op0KnownZeroTemp(Op0KnownZero); - Op0KnownZeroTemp.clearSignBit(); - int Op0ZeroPosition = BitWidth - Op0KnownZeroTemp.countLeadingZeros() - 1; - - int Op1OnePosition = BitWidth - Op1MaybeOne.countLeadingZeros() - 1; - assert(Op1OnePosition >= 0); - - // This also covers the case of no known zero, since in that case - // Op0ZeroPosition is -1. - return Op0ZeroPosition >= Op1OnePosition; +/// \brief Return true if we can prove that adding the two values of the +/// knownbits will not overflow. +/// Otherwise return false. +static bool checkRippleForAdd(const KnownBits &LHSKnown, + const KnownBits &RHSKnown) { + // Addition of two 2's complement numbers having opposite signs will never + // overflow. + if ((LHSKnown.isNegative() && RHSKnown.isNonNegative()) || + (LHSKnown.isNonNegative() && RHSKnown.isNegative())) + return true; + + // If either of the values is known to be non-negative, adding them can only + // overflow if the second is also non-negative, so we can assume that. + // Two non-negative numbers will only overflow if there is a carry to the + // sign bit, so we can check if even when the values are as big as possible + // there is no overflow to the sign bit. + if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative()) { + APInt MaxLHS = ~LHSKnown.Zero; + MaxLHS.clearSignBit(); + APInt MaxRHS = ~RHSKnown.Zero; + MaxRHS.clearSignBit(); + APInt Result = std::move(MaxLHS) + std::move(MaxRHS); + return Result.isSignBitClear(); + } + + // If either of the values is known to be negative, adding them can only + // overflow if the second is also negative, so we can assume that. + // Two negative number will only overflow if there is no carry to the sign + // bit, so we can check if even when the values are as small as possible + // there is overflow to the sign bit. + if (LHSKnown.isNegative() || RHSKnown.isNegative()) { + APInt MinLHS = LHSKnown.One; + MinLHS.clearSignBit(); + APInt MinRHS = RHSKnown.One; + MinRHS.clearSignBit(); + APInt Result = std::move(MinLHS) + std::move(MinRHS); + return Result.isSignBitSet(); + } + + // If we reached here it means that we know nothing about the sign bits. + // In this case we can't know if there will be an overflow, since by + // changing the sign bits any two values can be made to overflow. + return false; } /// Return true if we can prove that: @@ -906,16 +926,8 @@ bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS, KnownBits RHSKnown(BitWidth); computeKnownBits(RHS, RHSKnown, 0, &CxtI); - // Addition of two 2's complement numbers having opposite signs will never - // overflow. - if ((LHSKnown.One[BitWidth - 1] && RHSKnown.Zero[BitWidth - 1]) || - (LHSKnown.Zero[BitWidth - 1] && RHSKnown.One[BitWidth - 1])) - return true; - // Check if carry bit of addition will not cause overflow. - if (checkRippleForAdd(LHSKnown.Zero, RHSKnown.Zero)) - return true; - if (checkRippleForAdd(RHSKnown.Zero, LHSKnown.Zero)) + if (checkRippleForAdd(LHSKnown, RHSKnown)) return true; return false; diff --git a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index c7092bf3a398..b114801cc1c0 100644 --- a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -1834,25 +1834,8 @@ Value *InstCombiner::FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, case ICmpInst::ICMP_UGT: // (X == 13 | X u> 14) -> no change case ICmpInst::ICMP_SGT: // (X == 13 | X s> 14) -> no change break; - case ICmpInst::ICMP_NE: // (X == 13 | X != 15) -> X != 15 - case ICmpInst::ICMP_ULT: // (X == 13 | X u< 15) -> X u< 15 - case ICmpInst::ICMP_SLT: // (X == 13 | X s< 15) -> X s< 15 - return RHS; } break; - case ICmpInst::ICMP_NE: - switch (PredR) { - default: - llvm_unreachable("Unknown integer condition code!"); - case ICmpInst::ICMP_EQ: // (X != 13 | X == 15) -> X != 13 - case ICmpInst::ICMP_UGT: // (X != 13 | X u> 15) -> X != 13 - case ICmpInst::ICMP_SGT: // (X != 13 | X s> 15) -> X != 13 - return LHS; - case ICmpInst::ICMP_NE: // (X != 13 | X != 15) -> true - case ICmpInst::ICMP_ULT: // (X != 13 | X u< 15) -> true - case ICmpInst::ICMP_SLT: // (X != 13 | X s< 15) -> true - return Builder->getTrue(); - } case ICmpInst::ICMP_ULT: switch (PredR) { default: @@ -1860,15 +1843,9 @@ Value *InstCombiner::FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, case ICmpInst::ICMP_EQ: // (X u< 13 | X == 14) -> no change break; case ICmpInst::ICMP_UGT: // (X u< 13 | X u> 15) -> (X-13) u> 2 - // If RHSC is [us]MAXINT, it is always false. Not handling - // this can cause overflow. - if (RHSC->isMaxValue(false)) - return LHS; + assert(!RHSC->isMaxValue(false) && "Missed icmp simplification"); return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, false, false); - case ICmpInst::ICMP_NE: // (X u< 13 | X != 15) -> X != 15 - case ICmpInst::ICMP_ULT: // (X u< 13 | X u< 15) -> X u< 15 - return RHS; } break; case ICmpInst::ICMP_SLT: @@ -1878,39 +1855,9 @@ Value *InstCombiner::FoldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, case ICmpInst::ICMP_EQ: // (X s< 13 | X == 14) -> no change break; case ICmpInst::ICMP_SGT: // (X s< 13 | X s> 15) -> (X-13) s> 2 - // If RHSC is [us]MAXINT, it is always false. Not handling - // this can cause overflow. - if (RHSC->isMaxValue(true)) - return LHS; + assert(!RHSC->isMaxValue(true) && "Missed icmp simplification"); return insertRangeTest(LHS0, LHSC->getValue(), RHSC->getValue() + 1, true, false); - case ICmpInst::ICMP_NE: // (X s< 13 | X != 15) -> X != 15 - case ICmpInst::ICMP_SLT: // (X s< 13 | X s< 15) -> X s< 15 - return RHS; - } - break; - case ICmpInst::ICMP_UGT: - switch (PredR) { - default: - llvm_unreachable("Unknown integer condition code!"); - case ICmpInst::ICMP_EQ: // (X u> 13 | X == 15) -> X u> 13 - case ICmpInst::ICMP_UGT: // (X u> 13 | X u> 15) -> X u> 13 - return LHS; - case ICmpInst::ICMP_NE: // (X u> 13 | X != 15) -> true - case ICmpInst::ICMP_ULT: // (X u> 13 | X u< 15) -> true - return Builder->getTrue(); - } - break; - case ICmpInst::ICMP_SGT: - switch (PredR) { - default: - llvm_unreachable("Unknown integer condition code!"); - case ICmpInst::ICMP_EQ: // (X s> 13 | X == 15) -> X > 13 - case ICmpInst::ICMP_SGT: // (X s> 13 | X s> 15) -> X > 13 - return LHS; - case ICmpInst::ICMP_NE: // (X s> 13 | X != 15) -> true - case ICmpInst::ICMP_SLT: // (X s> 13 | X s< 15) -> true - return Builder->getTrue(); } break; } diff --git a/lib/Transforms/InstCombine/InstCombineCalls.cpp b/lib/Transforms/InstCombine/InstCombineCalls.cpp index 4fd90d78a63b..6989d67f0060 100644 --- a/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -3619,7 +3619,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) { // then this one is redundant, and should be removed. KnownBits Known(1); computeKnownBits(IIOperand, Known, 0, II); - if (Known.One.isAllOnesValue()) + if (Known.isAllOnes()) return eraseInstFromFunction(*II); // Update the cache of affected values for this assumption (we might be diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index 60970775de63..34ce235b3fe2 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -4050,7 +4050,7 @@ Instruction *InstCombiner::foldICmpUsingKnownBits(ICmpInst &I) { // is set. If the comparison is against zero, then this is a check to see if // *that* bit is set. APInt Op0KnownZeroInverted = ~Op0Known.Zero; - if (~Op1Known.Zero == 0) { + if (Op1Known.isZero()) { // If the LHS is an AND with the same constant, look through it. Value *LHS = nullptr; const APInt *LHSC; diff --git a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp index 0195c5e727c9..05b01774cd5e 100644 --- a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp +++ b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp @@ -120,8 +120,7 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, return nullptr; } - Known.Zero.clearAllBits(); - Known.One.clearAllBits(); + Known.resetAll(); if (DemandedMask == 0) // Not demanding any bits from V. return UndefValue::get(VTy); @@ -329,13 +328,11 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, case Instruction::Trunc: { unsigned truncBf = I->getOperand(0)->getType()->getScalarSizeInBits(); DemandedMask = DemandedMask.zext(truncBf); - Known.Zero = Known.Zero.zext(truncBf); - Known.One = Known.One.zext(truncBf); + Known = Known.zext(truncBf); if (SimplifyDemandedBits(I, 0, DemandedMask, Known, Depth + 1)) return I; DemandedMask = DemandedMask.trunc(BitWidth); - Known.Zero = Known.Zero.trunc(BitWidth); - Known.One = Known.One.trunc(BitWidth); + Known = Known.trunc(BitWidth); assert(!(Known.Zero & Known.One) && "Bits known to be one AND zero?"); break; } @@ -365,13 +362,11 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); DemandedMask = DemandedMask.trunc(SrcBitWidth); - Known.Zero = Known.Zero.trunc(SrcBitWidth); - Known.One = Known.One.trunc(SrcBitWidth); + Known = Known.trunc(SrcBitWidth); if (SimplifyDemandedBits(I, 0, DemandedMask, Known, Depth + 1)) return I; DemandedMask = DemandedMask.zext(BitWidth); - Known.Zero = Known.Zero.zext(BitWidth); - Known.One = Known.One.zext(BitWidth); + Known = Known.zext(BitWidth); assert(!(Known.Zero & Known.One) && "Bits known to be one AND zero?"); // The top bits are known to be zero. Known.Zero.setBitsFrom(SrcBitWidth); @@ -391,13 +386,11 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, InputDemandedBits.setBit(SrcBitWidth-1); InputDemandedBits = InputDemandedBits.trunc(SrcBitWidth); - Known.Zero = Known.Zero.trunc(SrcBitWidth); - Known.One = Known.One.trunc(SrcBitWidth); + Known = Known.trunc(SrcBitWidth); if (SimplifyDemandedBits(I, 0, InputDemandedBits, Known, Depth + 1)) return I; InputDemandedBits = InputDemandedBits.zext(BitWidth); - Known.Zero = Known.Zero.zext(BitWidth); - Known.One = Known.One.zext(BitWidth); + Known = Known.zext(BitWidth); assert(!(Known.Zero & Known.One) && "Bits known to be one AND zero?"); // If the sign bit of the input is known set or clear, then we know the diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index 1eb98b18bfb5..1792cb585f87 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -2182,8 +2182,8 @@ Instruction *InstCombiner::visitReturnInst(ReturnInst &RI) { // determine the value. If so, constant fold it. KnownBits Known(VTy->getPrimitiveSizeInBits()); computeKnownBits(ResultOp, Known, 0, &RI); - if ((Known.Zero|Known.One).isAllOnesValue()) - RI.setOperand(0, Constant::getIntegerValue(VTy, Known.One)); + if (Known.isConstant()) + RI.setOperand(0, Constant::getIntegerValue(VTy, Known.getConstant())); return nullptr; } @@ -2863,8 +2863,8 @@ bool InstCombiner::run() { unsigned BitWidth = Ty->getScalarSizeInBits(); KnownBits Known(BitWidth); computeKnownBits(I, Known, /*Depth*/0, I); - if ((Known.Zero | Known.One).isAllOnesValue()) { - Constant *C = ConstantInt::get(Ty, Known.One); + if (Known.isConstant()) { + Constant *C = ConstantInt::get(Ty, Known.getConstant()); DEBUG(dbgs() << "IC: ConstFold (all bits known) to: " << *C << " from: " << *I << '\n'); |