From d49344495d55bf46b15fc7feab2c0e3ef4a47e38 Mon Sep 17 00:00:00 2001 From: Craig Topper Date: Fri, 12 May 2017 17:20:30 +0000 Subject: [PATCH] [KnownBits] Add bit counting methods to KnownBits struct and use them where possible This patch adds min/max population count, leading/trailing zero/one bit counting methods. The min methods return answers based on bits that are known without considering unknown bits. The max methods give answers taking into account the largest count that unknown bits could give. Differential Revision: https://reviews.llvm.org/D32931 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@302925 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/KnownBits.h | 60 ++++++++++++++++ lib/Analysis/DemandedBits.cpp | 4 +- lib/Analysis/InstructionSimplify.cpp | 2 +- lib/Analysis/ScalarEvolution.cpp | 2 +- lib/Analysis/ValueTracking.cpp | 70 ++++++++----------- lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 55 +++++++-------- .../SelectionDAG/SelectionDAGBuilder.cpp | 2 +- lib/Target/AMDGPU/AMDGPUISelLowering.cpp | 2 +- .../Hexagon/HexagonLoopIdiomRecognition.cpp | 2 +- lib/Target/X86/X86ISelLowering.cpp | 2 +- lib/Target/XCore/XCoreISelLowering.cpp | 2 +- .../InstCombine/InstCombineCalls.cpp | 8 +-- .../InstCombineSimplifyDemanded.cpp | 2 +- .../InstCombine/InstructionCombining.cpp | 4 +- lib/Transforms/Utils/BypassSlowDivision.cpp | 4 +- lib/Transforms/Utils/Local.cpp | 2 +- .../Vectorize/LoadStoreVectorizer.cpp | 2 +- 17 files changed, 136 insertions(+), 89 deletions(-) diff --git a/include/llvm/Support/KnownBits.h b/include/llvm/Support/KnownBits.h index 3d38cf87853..2c77d40559b 100644 --- a/include/llvm/Support/KnownBits.h +++ b/include/llvm/Support/KnownBits.h @@ -133,6 +133,66 @@ public: KnownBits zextOrTrunc(unsigned BitWidth) { return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth)); } + + /// Returns the minimum number of trailing zero bits. + unsigned countMinTrailingZeros() const { + return Zero.countTrailingOnes(); + } + + /// Returns the minimum number of trailing one bits. + unsigned countMinTrailingOnes() const { + return One.countTrailingOnes(); + } + + /// Returns the minimum number of leading zero bits. + unsigned countMinLeadingZeros() const { + return Zero.countLeadingOnes(); + } + + /// Returns the minimum number of leading one bits. + unsigned countMinLeadingOnes() const { + return One.countLeadingOnes(); + } + + /// Returns the number of times the sign bit is replicated into the other + /// bits. + unsigned countMinSignBits() const { + if (isNonNegative()) + return countMinLeadingZeros(); + if (isNegative()) + return countMinLeadingOnes(); + return 0; + } + + /// Returns the maximum number of trailing zero bits possible. + unsigned countMaxTrailingZeros() const { + return One.countTrailingZeros(); + } + + /// Returns the maximum number of trailing one bits possible. + unsigned countMaxTrailingOnes() const { + return Zero.countTrailingZeros(); + } + + /// Returns the maximum number of leading zero bits possible. + unsigned countMaxLeadingZeros() const { + return One.countLeadingZeros(); + } + + /// Returns the maximum number of leading one bits possible. + unsigned countMaxLeadingOnes() const { + return Zero.countLeadingZeros(); + } + + /// Returns the number of bits known to be one. + unsigned countMinPopulation() const { + return One.countPopulation(); + } + + /// Returns the maximum number of bits that could be one. + unsigned countMaxPopulation() const { + return getBitWidth() - Zero.countPopulation(); + } }; } // end namespace llvm diff --git a/lib/Analysis/DemandedBits.cpp b/lib/Analysis/DemandedBits.cpp index 9f5dc531823..c2b35b99d7c 100644 --- a/lib/Analysis/DemandedBits.cpp +++ b/lib/Analysis/DemandedBits.cpp @@ -118,7 +118,7 @@ void DemandedBits::determineLiveOperandBits( // known to be one. ComputeKnownBits(BitWidth, I, nullptr); AB = APInt::getHighBitsSet(BitWidth, - std::min(BitWidth, Known.One.countLeadingZeros()+1)); + std::min(BitWidth, Known.countMaxLeadingZeros()+1)); } break; case Intrinsic::cttz: @@ -128,7 +128,7 @@ void DemandedBits::determineLiveOperandBits( // known to be one. ComputeKnownBits(BitWidth, I, nullptr); AB = APInt::getLowBitsSet(BitWidth, - std::min(BitWidth, Known.One.countTrailingZeros()+1)); + std::min(BitWidth, Known.countMaxTrailingZeros()+1)); } break; } diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index de16e42f766..1457422b255 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -1317,7 +1317,7 @@ static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0, // If all valid bits in the shift amount are known zero, the first operand is // unchanged. unsigned NumValidShiftBits = Log2_32_Ceil(BitWidth); - if (Known.Zero.countTrailingOnes() >= NumValidShiftBits) + if (Known.countMinTrailingZeros() >= NumValidShiftBits) return Op0; return nullptr; diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 17fb979f50f..d71206335a5 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -4636,7 +4636,7 @@ uint32_t ScalarEvolution::GetMinTrailingZerosImpl(const SCEV *S) { KnownBits Known(BitWidth); computeKnownBits(U->getValue(), Known, getDataLayout(), 0, &AC, nullptr, &DT); - return Known.Zero.countTrailingOnes(); + return Known.countMinTrailingZeros(); } // SCEVUDivExpr diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index 39a92066a48..38bcb0f6c71 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -348,10 +348,10 @@ static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW, // Also compute a conservative estimate for high known-0 bits. // More trickiness is possible, but this is sufficient for the // interesting case of alignment computation. - unsigned TrailZ = Known.Zero.countTrailingOnes() + - Known2.Zero.countTrailingOnes(); - unsigned LeadZ = std::max(Known.Zero.countLeadingOnes() + - Known2.Zero.countLeadingOnes(), + unsigned TrailZ = Known.countMinTrailingZeros() + + Known2.countMinTrailingZeros(); + unsigned LeadZ = std::max(Known.countMinLeadingZeros() + + Known2.countMinLeadingZeros(), BitWidth) - BitWidth; TrailZ = std::min(TrailZ, BitWidth); @@ -756,8 +756,8 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I)); // Whatever high bits in c are zero are known to be zero. - Known.Zero.setHighBits(RHSKnown.Zero.countLeadingOnes()); - // assume(v <_u c) + Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros()); + // assume(v <_u c) } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) && Pred == ICmpInst::ICMP_ULT && isValidAssumeForContext(I, Q.CxtI, Q.DT)) { @@ -767,9 +767,9 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, // Whatever high bits in c are zero are known to be zero (if c is a power // of 2, then one more). if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, I))) - Known.Zero.setHighBits(RHSKnown.Zero.countLeadingOnes()+1); + Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros() + 1); else - Known.Zero.setHighBits(RHSKnown.Zero.countLeadingOnes()); + Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros()); } } @@ -922,7 +922,7 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, m_Value(Y))))) { Known2.resetAll(); computeKnownBits(Y, Known2, Depth + 1, Q); - if (Known2.One.countTrailingOnes() > 0) + if (Known2.countMinTrailingOnes() > 0) Known.Zero.setBit(0); } break; @@ -959,14 +959,13 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, // treat a udiv as a logical right shift by the power of 2 known to // be less than the denominator. computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q); - unsigned LeadZ = Known2.Zero.countLeadingOnes(); + unsigned LeadZ = Known2.countMinLeadingZeros(); Known2.resetAll(); computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q); - unsigned RHSUnknownLeadingOnes = Known2.One.countLeadingZeros(); - if (RHSUnknownLeadingOnes != BitWidth) - LeadZ = std::min(BitWidth, - LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); + unsigned RHSMaxLeadingZeros = Known2.countMaxLeadingZeros(); + if (RHSMaxLeadingZeros != BitWidth) + LeadZ = std::min(BitWidth, LeadZ + BitWidth - RHSMaxLeadingZeros - 1); Known.Zero.setHighBits(LeadZ); break; @@ -989,8 +988,8 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, if (Known.isNegative() && Known2.isNegative()) // We can derive a lower bound on the result by taking the max of the // leading one bits. - MaxHighOnes = std::max(Known.One.countLeadingOnes(), - Known2.One.countLeadingOnes()); + MaxHighOnes = + std::max(Known.countMinLeadingOnes(), Known2.countMinLeadingOnes()); // If either side is non-negative, the result is non-negative. else if (Known.isNonNegative() || Known2.isNonNegative()) MaxHighZeros = 1; @@ -999,8 +998,8 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, if (Known.isNonNegative() && Known2.isNonNegative()) // We can derive an upper bound on the result by taking the max of the // leading zero bits. - MaxHighZeros = std::max(Known.Zero.countLeadingOnes(), - Known2.Zero.countLeadingOnes()); + MaxHighZeros = std::max(Known.countMinLeadingZeros(), + Known2.countMinLeadingZeros()); // If either side is negative, the result is negative. else if (Known.isNegative() || Known2.isNegative()) MaxHighOnes = 1; @@ -1008,12 +1007,12 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, // We can derive a lower bound on the result by taking the max of the // leading one bits. MaxHighOnes = - std::max(Known.One.countLeadingOnes(), Known2.One.countLeadingOnes()); + std::max(Known.countMinLeadingOnes(), Known2.countMinLeadingOnes()); } else if (SPF == SPF_UMIN) { // We can derive an upper bound on the result by taking the max of the // leading zero bits. MaxHighZeros = - std::max(Known.Zero.countLeadingOnes(), Known2.Zero.countLeadingOnes()); + std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros()); } // Only known if known in both the LHS and RHS. @@ -1191,8 +1190,8 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, computeKnownBits(I->getOperand(0), Known, Depth + 1, Q); computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q); - unsigned Leaders = std::max(Known.Zero.countLeadingOnes(), - Known2.Zero.countLeadingOnes()); + unsigned Leaders = + std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros()); Known.resetAll(); Known.Zero.setHighBits(Leaders); break; @@ -1213,7 +1212,7 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, // to determine if we can prove known low zero bits. KnownBits LocalKnown(BitWidth); computeKnownBits(I->getOperand(0), LocalKnown, Depth + 1, Q); - unsigned TrailZ = LocalKnown.Zero.countTrailingOnes(); + unsigned TrailZ = LocalKnown.countMinTrailingZeros(); gep_type_iterator GTI = gep_type_begin(I); for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { @@ -1247,7 +1246,7 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, computeKnownBits(Index, LocalKnown, Depth + 1, Q); TrailZ = std::min(TrailZ, unsigned(countTrailingZeros(TypeSize) + - LocalKnown.Zero.countTrailingOnes())); + LocalKnown.countMinTrailingZeros())); } } @@ -1292,8 +1291,8 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, KnownBits Known3(Known); computeKnownBits(L, Known3, Depth + 1, Q); - Known.Zero.setLowBits(std::min(Known2.Zero.countTrailingOnes(), - Known3.Zero.countTrailingOnes())); + Known.Zero.setLowBits(std::min(Known2.countMinTrailingZeros(), + Known3.countMinTrailingZeros())); if (DontImproveNonNegativePhiBits) break; @@ -1418,7 +1417,7 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits &Known, computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q); // We can bound the space the count needs. Also, bits known to be zero // can't contribute to the population. - unsigned BitsPossiblySet = BitWidth - Known2.Zero.countPopulation(); + unsigned BitsPossiblySet = Known2.countMaxPopulation(); unsigned LowBits = Log2_32(BitsPossiblySet)+1; Known.Zero.setBitsFrom(LowBits); // TODO: we could bound KnownOne using the lower bound on the number @@ -1869,10 +1868,10 @@ bool isKnownNonZero(const Value *V, unsigned Depth, const Query &Q) { if (ConstantInt *Shift = dyn_cast(Y)) { auto ShiftVal = Shift->getLimitedValue(BitWidth - 1); // Is there a known one in the portion not shifted out? - if (Known.One.countLeadingZeros() < BitWidth - ShiftVal) + if (Known.countMaxLeadingZeros() < BitWidth - ShiftVal) return true; // Are all the bits to be shifted out known zero? - if (Known.Zero.countTrailingOnes() >= ShiftVal) + if (Known.countMinTrailingZeros() >= ShiftVal) return isKnownNonZero(X, Depth, Q); } } @@ -2284,14 +2283,7 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth, // If we know that the sign bit is either zero or one, determine the number of // identical bits in the top of the input value. - if (Known.isNonNegative()) - return std::max(FirstAnswer, Known.Zero.countLeadingOnes()); - - if (Known.isNegative()) - return std::max(FirstAnswer, Known.One.countLeadingOnes()); - - // computeKnownBits gave us no extra information about the top bits. - return FirstAnswer; + return std::max(FirstAnswer, Known.countMinSignBits()); } /// This function computes the integer multiple of Base that equals V. @@ -3449,8 +3441,8 @@ OverflowResult llvm::computeOverflowForUnsignedMul(const Value *LHS, computeKnownBits(RHS, RHSKnown, DL, /*Depth=*/0, AC, CxtI, DT); // Note that underestimating the number of zero bits gives a more // conservative answer. - unsigned ZeroBits = LHSKnown.Zero.countLeadingOnes() + - RHSKnown.Zero.countLeadingOnes(); + unsigned ZeroBits = LHSKnown.countMinLeadingZeros() + + RHSKnown.countMinLeadingZeros(); // First handle the easy case: if we have enough zero bits there's // definitely no overflow. if (ZeroBits >= BitWidth) diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index cd8e6cd3f6d..28de92c6c88 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -2217,10 +2217,10 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, // Also compute a conservative estimate for high known-0 bits. // More trickiness is possible, but this is sufficient for the // interesting case of alignment computation. - unsigned TrailZ = Known.Zero.countTrailingOnes() + - Known2.Zero.countTrailingOnes(); - unsigned LeadZ = std::max(Known.Zero.countLeadingOnes() + - Known2.Zero.countLeadingOnes(), + unsigned TrailZ = Known.countMinTrailingZeros() + + Known2.countMinTrailingZeros(); + unsigned LeadZ = std::max(Known.countMinLeadingZeros() + + Known2.countMinLeadingZeros(), BitWidth) - BitWidth; Known.resetAll(); @@ -2233,13 +2233,12 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, // treat a udiv as a logical right shift by the power of 2 known to // be less than the denominator. computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1); - unsigned LeadZ = Known2.Zero.countLeadingOnes(); + unsigned LeadZ = Known2.countMinLeadingZeros(); computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1); - unsigned RHSUnknownLeadingOnes = Known2.One.countLeadingZeros(); - if (RHSUnknownLeadingOnes != BitWidth) - LeadZ = std::min(BitWidth, - LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); + unsigned RHSMaxLeadingZeros = Known2.countMaxLeadingZeros(); + if (RHSMaxLeadingZeros != BitWidth) + LeadZ = std::min(BitWidth, LeadZ + BitWidth - RHSMaxLeadingZeros - 1); Known.Zero.setHighBits(LeadZ); break; @@ -2359,7 +2358,7 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, case ISD::CTTZ_ZERO_UNDEF: { computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1); // If we have a known 1, its position is our upper bound. - unsigned PossibleTZ = Known2.One.countTrailingZeros(); + unsigned PossibleTZ = Known2.countMaxTrailingZeros(); unsigned LowBits = Log2_32(PossibleTZ) + 1; Known.Zero.setBitsFrom(LowBits); break; @@ -2368,7 +2367,7 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, case ISD::CTLZ_ZERO_UNDEF: { computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1); // If we have a known 1, its position is our upper bound. - unsigned PossibleLZ = Known2.One.countLeadingZeros(); + unsigned PossibleLZ = Known2.countMaxLeadingZeros(); unsigned LowBits = Log2_32(PossibleLZ) + 1; Known.Zero.setBitsFrom(LowBits); break; @@ -2376,7 +2375,7 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, case ISD::CTPOP: { computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1); // If we know some of the bits are zero, they can't be one. - unsigned PossibleOnes = BitWidth - Known2.Zero.countPopulation(); + unsigned PossibleOnes = Known2.countMaxPopulation(); Known.Zero.setBitsFrom(Log2_32(PossibleOnes) + 1); break; } @@ -2493,13 +2492,12 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, // going to be 0 in the result. Both addition and complement operations // preserve the low zero bits. computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1); - unsigned KnownZeroLow = Known2.Zero.countTrailingOnes(); + unsigned KnownZeroLow = Known2.countMinTrailingZeros(); if (KnownZeroLow == 0) break; computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1); - KnownZeroLow = std::min(KnownZeroLow, - Known2.Zero.countTrailingOnes()); + KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros()); Known.Zero.setLowBits(KnownZeroLow); break; } @@ -2526,15 +2524,13 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, // and the other has the top 8 bits clear, we know the top 7 bits of the // output must be clear. computeKnownBits(Op.getOperand(0), Known2, DemandedElts, Depth + 1); - unsigned KnownZeroHigh = Known2.Zero.countLeadingOnes(); - unsigned KnownZeroLow = Known2.Zero.countTrailingOnes(); + unsigned KnownZeroHigh = Known2.countMinLeadingZeros(); + unsigned KnownZeroLow = Known2.countMinTrailingZeros(); computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1); - KnownZeroHigh = std::min(KnownZeroHigh, - Known2.Zero.countLeadingOnes()); - KnownZeroLow = std::min(KnownZeroLow, - Known2.Zero.countTrailingOnes()); + KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros()); + KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros()); if (Opcode == ISD::ADDE || Opcode == ISD::ADDCARRY) { // With ADDE and ADDCARRY, a carry bit may be added in, so we can only @@ -2594,8 +2590,8 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, computeKnownBits(Op.getOperand(0), Known, DemandedElts, Depth + 1); computeKnownBits(Op.getOperand(1), Known2, DemandedElts, Depth + 1); - uint32_t Leaders = std::max(Known.Zero.countLeadingOnes(), - Known2.Zero.countLeadingOnes()); + uint32_t Leaders = + std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros()); Known.resetAll(); Known.Zero.setHighBits(Leaders); break; @@ -2711,8 +2707,8 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, // UMIN - we know that the result will have the maximum of the // known zero leading bits of the inputs. - unsigned LeadZero = Known.Zero.countLeadingOnes(); - LeadZero = std::max(LeadZero, Known2.Zero.countLeadingOnes()); + unsigned LeadZero = Known.countMinLeadingZeros(); + LeadZero = std::max(LeadZero, Known2.countMinLeadingZeros()); Known.Zero &= Known2.Zero; Known.One &= Known2.One; @@ -2726,8 +2722,8 @@ void SelectionDAG::computeKnownBits(SDValue Op, KnownBits &Known, // UMAX - we know that the result will have the maximum of the // known one leading bits of the inputs. - unsigned LeadOne = Known.One.countLeadingOnes(); - LeadOne = std::max(LeadOne, Known2.One.countLeadingOnes()); + unsigned LeadOne = Known.countMinLeadingOnes(); + LeadOne = std::max(LeadOne, Known2.countMinLeadingOnes()); Known.Zero &= Known2.Zero; Known.One &= Known2.One; @@ -2843,8 +2839,7 @@ bool SelectionDAG::isKnownToBeAPowerOfTwo(SDValue Val) const { // Fall back to computeKnownBits to catch other known cases. KnownBits Known; computeKnownBits(Val, Known); - return (Known.Zero.countPopulation() == BitWidth - 1) && - (Known.One.countPopulation() == 1); + return (Known.countMaxPopulation() == 1) && (Known.countMinPopulation() == 1); } unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const { @@ -7520,7 +7515,7 @@ unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const { KnownBits Known(PtrWidth); llvm::computeKnownBits(const_cast(GV), Known, getDataLayout()); - unsigned AlignBits = Known.Zero.countTrailingOnes(); + unsigned AlignBits = Known.countMinTrailingZeros(); unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0; if (Align) return MinAlign(Align, GVOffset); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 6b4ebaac19f..1c32f7a0ce5 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -661,7 +661,7 @@ SDValue RegsForValue::getCopyFromRegs(SelectionDAG &DAG, unsigned RegSize = RegisterVT.getSizeInBits(); unsigned NumSignBits = LOI->NumSignBits; - unsigned NumZeroBits = LOI->Known.Zero.countLeadingOnes(); + unsigned NumZeroBits = LOI->Known.countMinLeadingZeros(); if (NumZeroBits == RegSize) { // The current value is a zero. diff --git a/lib/Target/AMDGPU/AMDGPUISelLowering.cpp b/lib/Target/AMDGPU/AMDGPUISelLowering.cpp index f3bcfbb25bb..f80652b8737 100644 --- a/lib/Target/AMDGPU/AMDGPUISelLowering.cpp +++ b/lib/Target/AMDGPU/AMDGPUISelLowering.cpp @@ -2305,7 +2305,7 @@ static bool isU24(SDValue Op, SelectionDAG &DAG) { EVT VT = Op.getValueType(); DAG.computeKnownBits(Op, Known); - return (VT.getSizeInBits() - Known.Zero.countLeadingOnes()) <= 24; + return (VT.getSizeInBits() - Known.countMinLeadingZeros()) <= 24; } static bool isI24(SDValue Op, SelectionDAG &DAG) { diff --git a/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp b/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp index 5a5799dbe00..e4df7ff5c20 100644 --- a/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp +++ b/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp @@ -1209,7 +1209,7 @@ bool PolynomialMultiplyRecognize::highBitsAreZero(Value *V, KnownBits Known(T->getBitWidth()); computeKnownBits(V, Known, DL); - return Known.Zero.countLeadingOnes() >= IterCount; + return Known.countMinLeadingZeros() >= IterCount; } diff --git a/lib/Target/X86/X86ISelLowering.cpp b/lib/Target/X86/X86ISelLowering.cpp index 6cc356dfa1d..1f5b94ff8fa 100644 --- a/lib/Target/X86/X86ISelLowering.cpp +++ b/lib/Target/X86/X86ISelLowering.cpp @@ -16752,7 +16752,7 @@ static SDValue LowerAndToBT(SDValue And, ISD::CondCode CC, if (BitWidth > AndBitWidth) { KnownBits Known; DAG.computeKnownBits(Op0, Known); - if (Known.Zero.countLeadingOnes() < BitWidth - AndBitWidth) + if (Known.countMinLeadingZeros() < BitWidth - AndBitWidth) return SDValue(); } LHS = Op1; diff --git a/lib/Target/XCore/XCoreISelLowering.cpp b/lib/Target/XCore/XCoreISelLowering.cpp index 7c0d27e9167..1da189c5cd3 100644 --- a/lib/Target/XCore/XCoreISelLowering.cpp +++ b/lib/Target/XCore/XCoreISelLowering.cpp @@ -409,7 +409,7 @@ static bool isWordAligned(SDValue Value, SelectionDAG &DAG) { KnownBits Known; DAG.computeKnownBits(Value, Known); - return Known.Zero.countTrailingOnes() >= 2; + return Known.countMinTrailingZeros() >= 2; } SDValue XCoreTargetLowering:: diff --git a/lib/Transforms/InstCombine/InstCombineCalls.cpp b/lib/Transforms/InstCombine/InstCombineCalls.cpp index 6989d67f006..face7abcc95 100644 --- a/lib/Transforms/InstCombine/InstCombineCalls.cpp +++ b/lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -1384,10 +1384,10 @@ static Instruction *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) { // Create a mask for bits above (ctlz) or below (cttz) the first known one. bool IsTZ = II.getIntrinsicID() == Intrinsic::cttz; - unsigned PossibleZeros = IsTZ ? Known.One.countTrailingZeros() - : Known.One.countLeadingZeros(); - unsigned DefiniteZeros = IsTZ ? Known.Zero.countTrailingOnes() - : Known.Zero.countLeadingOnes(); + unsigned PossibleZeros = IsTZ ? Known.countMaxTrailingZeros() + : Known.countMaxLeadingZeros(); + unsigned DefiniteZeros = IsTZ ? Known.countMinTrailingZeros() + : Known.countMinLeadingZeros(); // If all bits above (ctlz) or below (cttz) the first known one are known // zero, this value is constant. diff --git a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp index 05b01774cd5..4028a92771a 100644 --- a/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp +++ b/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp @@ -611,7 +611,7 @@ Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, SimplifyDemandedBits(I, 1, AllOnes, Known2, Depth + 1)) return I; - unsigned Leaders = Known2.Zero.countLeadingOnes(); + unsigned Leaders = Known2.countMinLeadingZeros(); Known.Zero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask; break; } diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp index 1792cb585f8..04e81f4bd15 100644 --- a/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -2264,8 +2264,8 @@ Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) { unsigned BitWidth = cast(Cond->getType())->getBitWidth(); KnownBits Known(BitWidth); computeKnownBits(Cond, Known, 0, &SI); - unsigned LeadingKnownZeros = Known.Zero.countLeadingOnes(); - unsigned LeadingKnownOnes = Known.One.countLeadingOnes(); + unsigned LeadingKnownZeros = Known.countMinLeadingZeros(); + unsigned LeadingKnownOnes = Known.countMinLeadingOnes(); // Compute the number of leading bits we can ignore. // TODO: A better way to determine this would use ComputeNumSignBits(). diff --git a/lib/Transforms/Utils/BypassSlowDivision.cpp b/lib/Transforms/Utils/BypassSlowDivision.cpp index 7ffdad597a9..83ec7f55d1a 100644 --- a/lib/Transforms/Utils/BypassSlowDivision.cpp +++ b/lib/Transforms/Utils/BypassSlowDivision.cpp @@ -261,10 +261,10 @@ ValueRange FastDivInsertionTask::getValueRange(Value *V, computeKnownBits(V, Known, DL); - if (Known.Zero.countLeadingOnes() >= HiBits) + if (Known.countMinLeadingZeros() >= HiBits) return VALRNG_KNOWN_SHORT; - if (Known.One.countLeadingZeros() < HiBits) + if (Known.countMaxLeadingZeros() < HiBits) return VALRNG_LIKELY_LONG; // Long integer divisions are often used in hashtable implementations. It's diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 6473d718f35..608834b06de 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -1041,7 +1041,7 @@ unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, KnownBits Known(BitWidth); computeKnownBits(V, Known, DL, 0, AC, CxtI, DT); - unsigned TrailZ = Known.Zero.countTrailingOnes(); + unsigned TrailZ = Known.countMinTrailingZeros(); // Avoid trouble with ridiculously large TrailZ values, such as // those computed from a null pointer. diff --git a/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp b/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp index 97dcb40a1d7..9cf66382b58 100644 --- a/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp +++ b/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp @@ -346,7 +346,7 @@ bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) { if (!Safe) { KnownBits Known(BitWidth); computeKnownBits(OpA, Known, DL, 0, nullptr, OpA, &DT); - if (Known.Zero.countTrailingZeros() < (BitWidth - 1)) + if (Known.countMaxTrailingOnes() < (BitWidth - 1)) Safe = true; } -- 2.50.1