From d913d9d2c387de1072858c91feba78284dfd3e79 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Thu, 12 Feb 2015 15:35:40 +0000 Subject: [PATCH] MathExtras: Bring Count(Trailing|Leading)Ones and CountPopulation in line with countTrailingZeros Update all callers. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@228930 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/APInt.h | 12 +- include/llvm/ADT/BitVector.h | 7 +- include/llvm/ADT/SmallBitVector.h | 6 +- include/llvm/ADT/SparseBitVector.h | 34 ++---- include/llvm/Support/MathExtras.h | 106 ++++++++++-------- lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 2 +- .../SelectionDAG/SelectionDAGBuilder.cpp | 6 +- lib/Support/APInt.cpp | 10 +- .../AArch64/AArch64ExpandPseudoInsts.cpp | 4 +- lib/Target/AArch64/AArch64ISelDAGToDAG.cpp | 8 +- .../MCTargetDesc/AArch64AddressingModes.h | 6 +- lib/Target/ARM/ARMISelDAGToDAG.cpp | 2 +- lib/Target/ARM/ARMISelLowering.cpp | 6 +- lib/Target/Hexagon/HexagonISelDAGToDAG.cpp | 4 +- lib/Target/Mips/MipsISelLowering.cpp | 2 +- lib/Target/NVPTX/NVPTXISelDAGToDAG.cpp | 6 +- lib/Target/PowerPC/PPCISelDAGToDAG.cpp | 2 +- lib/Target/R600/AMDGPUInstructions.td | 2 +- .../SystemZ/SystemZSelectionDAGInfo.cpp | 2 +- lib/Target/X86/X86FloatingPoint.cpp | 10 +- lib/Target/X86/X86ISelDAGToDAG.cpp | 2 +- lib/Target/X86/X86ISelLowering.cpp | 2 +- lib/Target/X86/X86InstrCompiler.td | 8 +- lib/Target/X86/X86InstrInfo.td | 4 +- unittests/Support/MathExtrasTest.cpp | 11 +- utils/TableGen/AsmMatcherEmitter.cpp | 4 +- 26 files changed, 125 insertions(+), 143 deletions(-) diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h index 025397d9ce4..c2fe09478a3 100644 --- a/include/llvm/ADT/APInt.h +++ b/include/llvm/ADT/APInt.h @@ -1356,7 +1356,7 @@ public: /// \brief Count the number of leading one bits. /// - /// This function is an APInt version of the countLeadingOnes_{32,64} + /// This function is an APInt version of the countLeadingOnes /// functions in MathExtras.h. It counts the number of ones from the most /// significant bit to the first zero bit. /// @@ -1372,7 +1372,7 @@ public: /// \brief Count the number of trailing zero bits. /// - /// This function is an APInt version of the countTrailingZeros_{32,64} + /// This function is an APInt version of the countTrailingZeros /// functions in MathExtras.h. It counts the number of zeros from the least /// significant bit to the first set bit. /// @@ -1382,7 +1382,7 @@ public: /// \brief Count the number of trailing one bits. /// - /// This function is an APInt version of the countTrailingOnes_{32,64} + /// This function is an APInt version of the countTrailingOnes /// functions in MathExtras.h. It counts the number of ones from the least /// significant bit to the first zero bit. /// @@ -1390,19 +1390,19 @@ public: /// of ones from the least significant bit to the first zero bit. unsigned countTrailingOnes() const { if (isSingleWord()) - return CountTrailingOnes_64(VAL); + return llvm::countTrailingOnes(VAL); return countTrailingOnesSlowCase(); } /// \brief Count the number of bits set. /// - /// This function is an APInt version of the countPopulation_{32,64} functions + /// This function is an APInt version of the countPopulation functions /// in MathExtras.h. It counts the number of 1 bits in the APInt value. /// /// \returns 0 if the value is zero, otherwise returns the number of set bits. unsigned countPopulation() const { if (isSingleWord()) - return CountPopulation_64(VAL); + return llvm::countPopulation(VAL); return countPopulationSlowCase(); } diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index 444f47471c3..0dbe810d904 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -121,12 +121,7 @@ public: size_type count() const { unsigned NumBits = 0; for (unsigned i = 0; i < NumBitWords(size()); ++i) - if (sizeof(BitWord) == 4) - NumBits += CountPopulation_32((uint32_t)Bits[i]); - else if (sizeof(BitWord) == 8) - NumBits += CountPopulation_64(Bits[i]); - else - llvm_unreachable("Unsupported!"); + NumBits += countPopulation(Bits[i]); return NumBits; } diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h index fe7345d0dfb..22e8ccd8ea0 100644 --- a/include/llvm/ADT/SmallBitVector.h +++ b/include/llvm/ADT/SmallBitVector.h @@ -180,11 +180,7 @@ public: size_type count() const { if (isSmall()) { uintptr_t Bits = getSmallBits(); - if (NumBaseBits == 32) - return CountPopulation_32(Bits); - if (NumBaseBits == 64) - return CountPopulation_64(Bits); - llvm_unreachable("Unsupported!"); + return countPopulation(Bits); } return getPointer()->count(); } diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index d5bde2963fb..20cbe2cddfc 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -124,25 +124,15 @@ public: size_type count() const { unsigned NumBits = 0; for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) - if (sizeof(BitWord) == 4) - NumBits += CountPopulation_32(Bits[i]); - else if (sizeof(BitWord) == 8) - NumBits += CountPopulation_64(Bits[i]); - else - llvm_unreachable("Unsupported!"); + NumBits += countPopulation(Bits[i]); return NumBits; } /// find_first - Returns the index of the first set bit. int find_first() const { for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) - if (Bits[i] != 0) { - if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - if (sizeof(BitWord) == 8) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - llvm_unreachable("Unsupported!"); - } + if (Bits[i] != 0) + return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); llvm_unreachable("Illegal empty element"); } @@ -161,23 +151,13 @@ public: // Mask off previous bits. Copy &= ~0UL << BitPos; - if (Copy != 0) { - if (sizeof(BitWord) == 4) - return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); - if (sizeof(BitWord) == 8) - return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); - llvm_unreachable("Unsupported!"); - } + if (Copy != 0) + return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); // Check subsequent words. for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i) - if (Bits[i] != 0) { - if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - if (sizeof(BitWord) == 8) - return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); - llvm_unreachable("Unsupported!"); - } + if (Bits[i] != 0) + return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); return -1; } diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h index cb3188c78f8..acffb46126e 100644 --- a/include/llvm/Support/MathExtras.h +++ b/include/llvm/Support/MathExtras.h @@ -375,62 +375,78 @@ inline uint64_t ByteSwap_64(uint64_t Value) { return sys::SwapByteOrder_64(Value); } -/// CountLeadingOnes_32 - this function performs the operation of -/// counting the number of ones from the most significant bit to the first zero -/// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8. -/// Returns 32 if the word is all ones. -inline unsigned CountLeadingOnes_32(uint32_t Value) { - return countLeadingZeros(~Value); -} - -/// CountLeadingOnes_64 - This function performs the operation -/// of counting the number of ones from the most significant bit to the first -/// zero bit (64 bit edition.) -/// Returns 64 if the word is all ones. -inline unsigned CountLeadingOnes_64(uint64_t Value) { - return countLeadingZeros(~Value); -} - -/// CountTrailingOnes_32 - this function performs the operation of -/// counting the number of ones from the least significant bit to the first zero -/// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8. -/// Returns 32 if the word is all ones. -inline unsigned CountTrailingOnes_32(uint32_t Value) { - return countTrailingZeros(~Value); +/// \brief Count the number of ones from the most significant bit to the first +/// zero bit. +/// +/// Ex. CountLeadingOnes(0xFF0FFF00) == 8. +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of all ones. Only ZB_Width and +/// ZB_Undefined are valid arguments. +template +std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits::is_integer && + !std::numeric_limits::is_signed, + "Only unsigned integral types are allowed."); + return countLeadingZeros(~Value, ZB); } -/// CountTrailingOnes_64 - This function performs the operation -/// of counting the number of ones from the least significant bit to the first -/// zero bit (64 bit edition.) -/// Returns 64 if the word is all ones. -inline unsigned CountTrailingOnes_64(uint64_t Value) { - return countTrailingZeros(~Value); +/// \brief Count the number of ones from the least significant bit to the first +/// zero bit. +/// +/// Ex. countTrailingOnes(0x00FF00FF) == 8. +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of all ones. Only ZB_Width and +/// ZB_Undefined are valid arguments. +template +std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits::is_integer && + !std::numeric_limits::is_signed, + "Only unsigned integral types are allowed."); + return countTrailingZeros(~Value, ZB); } -/// CountPopulation_32 - this function counts the number of set bits in a value. -/// Ex. CountPopulation(0xF000F000) = 8 -/// Returns 0 if the word is zero. -inline unsigned CountPopulation_32(uint32_t Value) { +namespace detail { +template struct PopulationCounter { + static unsigned count(T Value) { + // Generic version, forward to 32 bits. + static_assert(SizeOfT <= 4, "Not implemented!"); #if __GNUC__ >= 4 - return __builtin_popcount(Value); + return __builtin_popcount(Value); #else - uint32_t v = Value - ((Value >> 1) & 0x55555555); - v = (v & 0x33333333) + ((v >> 2) & 0x33333333); - return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; + uint32_t v = Value; + v = v - ((v >> 1) & 0x55555555); + v = (v & 0x33333333) + ((v >> 2) & 0x33333333); + return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; #endif -} + } +}; -/// CountPopulation_64 - this function counts the number of set bits in a value, -/// (64 bit edition.) -inline unsigned CountPopulation_64(uint64_t Value) { +template struct PopulationCounter { + static unsigned count(T Value) { #if __GNUC__ >= 4 - return __builtin_popcountll(Value); + return __builtin_popcountll(Value); #else - uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL); - v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); - v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; - return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); + uint64_t v = Value; + v = v - ((v >> 1) & 0x5555555555555555ULL); + v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); + v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; + return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); #endif + } +}; +} // namespace detail + +/// \brief Count the number of set bits in a value. +/// Ex. countPopulation(0xF000F000) = 8 +/// Returns 0 if the word is zero. +template +inline unsigned countPopulation(T Value) { + static_assert(std::numeric_limits::is_integer && + !std::numeric_limits::is_signed, + "Only unsigned integral types are allowed."); + return detail::PopulationCounter::count(Value); } /// Log2_32 - This function returns the floor log base 2 of the specified value, diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp index 06bd6ebc545..fd96519e455 100644 --- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -9489,7 +9489,7 @@ CheckForMaskedLoad(SDValue V, SDValue Ptr, SDValue Chain) { if (NotMaskLZ == 64) return Result; // All zero mask. // See if we have a continuous run of bits. If so, we have 0*1+0* - if (CountTrailingOnes_64(NotMask >> NotMaskTZ)+NotMaskTZ+NotMaskLZ != 64) + if (countTrailingOnes(NotMask >> NotMaskTZ) + NotMaskTZ + NotMaskLZ != 64) return Result; // Adjust NotMaskLZ down to be from the actual size of the int instead of i64. diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index d60c69556c9..014df6c5193 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1956,7 +1956,7 @@ void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB, SDValue ShiftOp = DAG.getCopyFromReg(getControlRoot(), getCurSDLoc(), Reg, VT); SDValue Cmp; - unsigned PopCount = CountPopulation_64(B.Mask); + unsigned PopCount = countPopulation(B.Mask); const TargetLowering &TLI = DAG.getTargetLoweringInfo(); if (PopCount == 1) { // Testing for a single bit; just compare the shift count with what it @@ -1968,7 +1968,7 @@ void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB, // There is only one zero bit in the range, test for it directly. Cmp = DAG.getSetCC( getCurSDLoc(), TLI.getSetCCResultType(*DAG.getContext(), VT), ShiftOp, - DAG.getConstant(CountTrailingOnes_64(B.Mask), VT), ISD::SETNE); + DAG.getConstant(countTrailingOnes(B.Mask), VT), ISD::SETNE); } else { // Make desired shift SDValue SwitchVal = DAG.getNode(ISD::SHL, getCurSDLoc(), VT, @@ -4595,7 +4595,7 @@ static SDValue ExpandPowI(SDLoc DL, SDValue LHS, SDValue RHS, Attribute::OptimizeForSize) || // If optimizing for size, don't insert too many multiplies. This // inserts up to 5 multiplies. - CountPopulation_32(Val)+Log2_32(Val) < 7) { + countPopulation(Val) + Log2_32(Val) < 7) { // We use the simple binary decomposition method to generate the multiply // sequence. There are more optimal ways to do this (for example, // powi(x,15) generates one more multiply than it should), but this has diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index 0ddc2ab8af3..50a639cc51e 100644 --- a/lib/Support/APInt.cpp +++ b/lib/Support/APInt.cpp @@ -713,7 +713,7 @@ unsigned APInt::countLeadingZerosSlowCase() const { unsigned APInt::countLeadingOnes() const { if (isSingleWord()) - return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth)); + return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth)); unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD; unsigned shift; @@ -724,13 +724,13 @@ unsigned APInt::countLeadingOnes() const { shift = APINT_BITS_PER_WORD - highWordBits; } int i = getNumWords() - 1; - unsigned Count = CountLeadingOnes_64(pVal[i] << shift); + unsigned Count = llvm::countLeadingOnes(pVal[i] << shift); if (Count == highWordBits) { for (i--; i >= 0; --i) { if (pVal[i] == -1ULL) Count += APINT_BITS_PER_WORD; else { - Count += CountLeadingOnes_64(pVal[i]); + Count += llvm::countLeadingOnes(pVal[i]); break; } } @@ -756,14 +756,14 @@ unsigned APInt::countTrailingOnesSlowCase() const { for (; i < getNumWords() && pVal[i] == -1ULL; ++i) Count += APINT_BITS_PER_WORD; if (i < getNumWords()) - Count += CountTrailingOnes_64(pVal[i]); + Count += llvm::countTrailingOnes(pVal[i]); return std::min(Count, BitWidth); } unsigned APInt::countPopulationSlowCase() const { unsigned Count = 0; for (unsigned i = 0; i < getNumWords(); ++i) - Count += CountPopulation_64(pVal[i]); + Count += llvm::countPopulation(pVal[i]); return Count; } diff --git a/lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp b/lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp index c850680d4c6..41b1132d3fd 100644 --- a/lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp +++ b/lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp @@ -229,7 +229,7 @@ static bool isStartChunk(uint64_t Chunk) { if (Chunk == 0 || Chunk == UINT64_MAX) return false; - return (CountLeadingOnes_64(Chunk) + countTrailingZeros(Chunk)) == 64; + return isMask_64(~Chunk); } /// \brief Check whether this chunk matches the pattern '0...1...' This pattern @@ -239,7 +239,7 @@ static bool isEndChunk(uint64_t Chunk) { if (Chunk == 0 || Chunk == UINT64_MAX) return false; - return (countLeadingZeros(Chunk) + CountTrailingOnes_64(Chunk)) == 64; + return isMask_64(Chunk); } /// \brief Clear or set all bits in the chunk at the given index. diff --git a/lib/Target/AArch64/AArch64ISelDAGToDAG.cpp b/lib/Target/AArch64/AArch64ISelDAGToDAG.cpp index 8735ca08e3e..5c1c66df907 100644 --- a/lib/Target/AArch64/AArch64ISelDAGToDAG.cpp +++ b/lib/Target/AArch64/AArch64ISelDAGToDAG.cpp @@ -1428,8 +1428,8 @@ static bool isBitfieldExtractOpFromAnd(SelectionDAG *CurDAG, SDNode *N, "bad amount in shift node!"); LSB = Srl_imm; - MSB = Srl_imm + (VT == MVT::i32 ? CountTrailingOnes_32(And_imm) - : CountTrailingOnes_64(And_imm)) - + MSB = Srl_imm + (VT == MVT::i32 ? countTrailingOnes(And_imm) + : countTrailingOnes(And_imm)) - 1; if (ClampMSB) // Since we're moving the extend before the right shift operation, we need @@ -1473,7 +1473,7 @@ static bool isSeveralBitsExtractOpFromShr(SDNode *N, unsigned &Opc, return false; // Check whether we really have several bits extract here. - unsigned BitWide = 64 - CountLeadingOnes_64(~(And_mask >> Srl_imm)); + unsigned BitWide = 64 - countLeadingOnes(~(And_mask >> Srl_imm)); if (BitWide && isMask_64(And_mask >> Srl_imm)) { if (N->getValueType(0) == MVT::i32) Opc = AArch64::UBFMWri; @@ -1872,7 +1872,7 @@ static bool isBitfieldPositioningOp(SelectionDAG *CurDAG, SDValue Op, return false; ShiftAmount = countTrailingZeros(NonZeroBits); - MaskWidth = CountTrailingOnes_64(NonZeroBits >> ShiftAmount); + MaskWidth = countTrailingOnes(NonZeroBits >> ShiftAmount); // BFI encompasses sufficiently many nodes that it's worth inserting an extra // LSL/LSR if the mask in NonZeroBits doesn't quite match up with the ISD::SHL diff --git a/lib/Target/AArch64/MCTargetDesc/AArch64AddressingModes.h b/lib/Target/AArch64/MCTargetDesc/AArch64AddressingModes.h index 4db9dea241a..ed24343a6f2 100644 --- a/lib/Target/AArch64/MCTargetDesc/AArch64AddressingModes.h +++ b/lib/Target/AArch64/MCTargetDesc/AArch64AddressingModes.h @@ -237,15 +237,15 @@ static inline bool processLogicalImmediate(uint64_t Imm, unsigned RegSize, if (isShiftedMask_64(Imm)) { I = countTrailingZeros(Imm); assert(I < 64 && "undefined behavior"); - CTO = CountTrailingOnes_64(Imm >> I); + CTO = countTrailingOnes(Imm >> I); } else { Imm |= ~Mask; if (!isShiftedMask_64(~Imm)) return false; - unsigned CLO = CountLeadingOnes_64(Imm); + unsigned CLO = countLeadingOnes(Imm); I = 64 - CLO; - CTO = CLO + CountTrailingOnes_64(Imm) - (64 - Size); + CTO = CLO + countTrailingOnes(Imm) - (64 - Size); } // Encode in Immr the number of RORs it would take to get *from* 0^m 1^n diff --git a/lib/Target/ARM/ARMISelDAGToDAG.cpp b/lib/Target/ARM/ARMISelDAGToDAG.cpp index 9621743fe30..0cbfe488ac4 100644 --- a/lib/Target/ARM/ARMISelDAGToDAG.cpp +++ b/lib/Target/ARM/ARMISelDAGToDAG.cpp @@ -2292,7 +2292,7 @@ SDNode *ARMDAGToDAGISel::SelectV6T2BitfieldExtractOp(SDNode *N, assert(Srl_imm > 0 && Srl_imm < 32 && "bad amount in shift node!"); // Note: The width operand is encoded as width-1. - unsigned Width = CountTrailingOnes_32(And_imm) - 1; + unsigned Width = countTrailingOnes(And_imm) - 1; unsigned LSB = Srl_imm; SDValue Reg0 = CurDAG->getRegister(0, MVT::i32); diff --git a/lib/Target/ARM/ARMISelLowering.cpp b/lib/Target/ARM/ARMISelLowering.cpp index 791e08f1411..3babd207167 100644 --- a/lib/Target/ARM/ARMISelLowering.cpp +++ b/lib/Target/ARM/ARMISelLowering.cpp @@ -10858,11 +10858,7 @@ bool ARM::isBitFieldInvertedMask(unsigned v) { // there can be 1's on either or both "outsides", all the "inside" // bits must be 0's - unsigned TO = CountTrailingOnes_32(v); - unsigned LO = CountLeadingOnes_32(v); - v = (v >> TO) << TO; - v = (v << LO) >> LO; - return v == 0; + return isShiftedMask_32(~v); } /// isFPImmLegal - Returns true if the target can instruction select the diff --git a/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp b/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp index 3d595a8aca2..fb056b50430 100644 --- a/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp +++ b/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp @@ -147,9 +147,7 @@ SDValue XformMskToBitPosU3Imm(uint8_t Imm) { // Return true if there is exactly one bit set in V, i.e., if V is one of the // following integers: 2^0, 2^1, ..., 2^31. bool ImmIsSingleBit(uint32_t v) const { - uint32_t c = CountPopulation_64(v); - // Only return true if we counted 1 bit. - return c == 1; + return isPowerOf2_32(v); } // XformM5ToU5Imm - Return a target constant with the specified value, of type diff --git a/lib/Target/Mips/MipsISelLowering.cpp b/lib/Target/Mips/MipsISelLowering.cpp index 8e00792eb9b..dcbd56bb927 100644 --- a/lib/Target/Mips/MipsISelLowering.cpp +++ b/lib/Target/Mips/MipsISelLowering.cpp @@ -70,7 +70,7 @@ static bool isShiftedMask(uint64_t I, uint64_t &Pos, uint64_t &Size) { if (!isShiftedMask_64(I)) return false; - Size = CountPopulation_64(I); + Size = countPopulation(I); Pos = countTrailingZeros(I); return true; } diff --git a/lib/Target/NVPTX/NVPTXISelDAGToDAG.cpp b/lib/Target/NVPTX/NVPTXISelDAGToDAG.cpp index 39750f446b2..2f55bd442e1 100644 --- a/lib/Target/NVPTX/NVPTXISelDAGToDAG.cpp +++ b/lib/Target/NVPTX/NVPTXISelDAGToDAG.cpp @@ -4775,7 +4775,7 @@ SDNode *NVPTXDAGToDAGISel::SelectBFE(SDNode *N) { } // How many bits are in our mask? - uint64_t NumBits = CountTrailingOnes_64(MaskVal); + uint64_t NumBits = countTrailingOnes(MaskVal); Len = CurDAG->getTargetConstant(NumBits, MVT::i32); if (LHS.getOpcode() == ISD::SRL || LHS.getOpcode() == ISD::SRA) { @@ -4839,10 +4839,10 @@ SDNode *NVPTXDAGToDAGISel::SelectBFE(SDNode *N) { NumZeros = 0; // The number of bits in the result bitfield will be the number of // trailing ones (the AND) minus the number of bits we shift off - NumBits = CountTrailingOnes_64(MaskVal) - ShiftAmt; + NumBits = countTrailingOnes(MaskVal) - ShiftAmt; } else if (isShiftedMask_64(MaskVal)) { NumZeros = countTrailingZeros(MaskVal); - unsigned NumOnes = CountTrailingOnes_64(MaskVal >> NumZeros); + unsigned NumOnes = countTrailingOnes(MaskVal >> NumZeros); // The number of bits in the result bitfield will be the number of // trailing zeros plus the number of set bits in the mask minus the // number of bits we shift off diff --git a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp index 7a8bc28f7a6..2418ca6b19a 100644 --- a/lib/Target/PowerPC/PPCISelDAGToDAG.cpp +++ b/lib/Target/PowerPC/PPCISelDAGToDAG.cpp @@ -2523,7 +2523,7 @@ SDNode *PPCDAGToDAGISel::Select(SDNode *N) { if (isInt64Immediate(N->getOperand(1).getNode(), Imm64) && isMask_64(Imm64)) { SDValue Val = N->getOperand(0); - MB = 64 - CountTrailingOnes_64(Imm64); + MB = 64 - countTrailingOnes(Imm64); SH = 0; // If the operand is a logical right shift, we can fold it into this diff --git a/lib/Target/R600/AMDGPUInstructions.td b/lib/Target/R600/AMDGPUInstructions.td index 6ab82a25913..12b494eef9c 100644 --- a/lib/Target/R600/AMDGPUInstructions.td +++ b/lib/Target/R600/AMDGPUInstructions.td @@ -590,7 +590,7 @@ applied. def legalshift32 : ImmLeaf =0 && Imm < 32;}]>; def bfemask : PatLeaf <(imm), [{return isMask_32(N->getZExtValue());}], - SDNodeXFormgetTargetConstant(CountTrailingOnes_32(N->getZExtValue()), MVT::i32);}]>>; + SDNodeXFormgetTargetConstant(countTrailingOnes(N->getZExtValue()), MVT::i32);}]>>; class BFEPattern : Pat < (and (srl i32:$x, legalshift32:$y), bfemask:$z), diff --git a/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp b/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp index a3cba64b9ed..b77a539ea04 100644 --- a/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp +++ b/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp @@ -103,7 +103,7 @@ EmitTargetCodeForMemset(SelectionDAG &DAG, SDLoc DL, SDValue Chain, // we can move at most 2 halfwords. uint64_t ByteVal = CByte->getZExtValue(); if (ByteVal == 0 || ByteVal == 255 ? - Bytes <= 16 && CountPopulation_64(Bytes) <= 2 : + Bytes <= 16 && countPopulation(Bytes) <= 2 : Bytes <= 4) { unsigned Size1 = Bytes == 16 ? 8 : 1 << findLastSet(Bytes); unsigned Size2 = Bytes - Size1; diff --git a/lib/Target/X86/X86FloatingPoint.cpp b/lib/Target/X86/X86FloatingPoint.cpp index 618910946bf..c8e5f64904e 100644 --- a/lib/Target/X86/X86FloatingPoint.cpp +++ b/lib/Target/X86/X86FloatingPoint.cpp @@ -898,7 +898,7 @@ void FPS::adjustLiveRegs(unsigned Mask, MachineBasicBlock::iterator I) { // Now we should have the correct registers live. DEBUG(dumpStack()); - assert(StackTop == CountPopulation_32(Mask) && "Live count mismatch"); + assert(StackTop == countPopulation(Mask) && "Live count mismatch"); } /// shuffleStackTop - emit fxch instructions before I to shuffle the top @@ -943,7 +943,7 @@ void FPS::handleCall(MachineBasicBlock::iterator &I) { } } - unsigned N = CountTrailingOnes_32(STReturns); + unsigned N = countTrailingOnes(STReturns); // FP registers used for function return must be consecutive starting at // FP0. @@ -1420,14 +1420,14 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &Inst) { if (STUses && !isMask_32(STUses)) MI->emitError("fixed input regs must be last on the x87 stack"); - unsigned NumSTUses = CountTrailingOnes_32(STUses); + unsigned NumSTUses = countTrailingOnes(STUses); // Defs must be contiguous from the stack top. ST0-STn. if (STDefs && !isMask_32(STDefs)) { MI->emitError("output regs must be last on the x87 stack"); STDefs = NextPowerOf2(STDefs) - 1; } - unsigned NumSTDefs = CountTrailingOnes_32(STDefs); + unsigned NumSTDefs = countTrailingOnes(STDefs); // So must the clobbered stack slots. ST0-STm, m >= n. if (STClobbers && !isMask_32(STDefs | STClobbers)) @@ -1437,7 +1437,7 @@ void FPS::handleSpecialFP(MachineBasicBlock::iterator &Inst) { unsigned STPopped = STUses & (STDefs | STClobbers); if (STPopped && !isMask_32(STPopped)) MI->emitError("implicitly popped regs must be last on the x87 stack"); - unsigned NumSTPopped = CountTrailingOnes_32(STPopped); + unsigned NumSTPopped = countTrailingOnes(STPopped); DEBUG(dbgs() << "Asm uses " << NumSTUses << " fixed regs, pops " << NumSTPopped << ", and defines " << NumSTDefs << " regs.\n"); diff --git a/lib/Target/X86/X86ISelDAGToDAG.cpp b/lib/Target/X86/X86ISelDAGToDAG.cpp index f143b200ec4..51ae5054b11 100644 --- a/lib/Target/X86/X86ISelDAGToDAG.cpp +++ b/lib/Target/X86/X86ISelDAGToDAG.cpp @@ -916,7 +916,7 @@ static bool FoldMaskAndShiftToScale(SelectionDAG &DAG, SDValue N, if (AMShiftAmt <= 0 || AMShiftAmt > 3) return true; // We also need to ensure that mask is a continuous run of bits. - if (CountTrailingOnes_64(Mask >> MaskTZ) + MaskTZ + MaskLZ != 64) return true; + if (countTrailingOnes(Mask >> MaskTZ) + MaskTZ + MaskLZ != 64) return true; // Scale the leading zero count down based on the actual size of the value. // Also scale it down based on the size of the shift. diff --git a/lib/Target/X86/X86ISelLowering.cpp b/lib/Target/X86/X86ISelLowering.cpp index 8cec2e39782..c11c8e3febd 100644 --- a/lib/Target/X86/X86ISelLowering.cpp +++ b/lib/Target/X86/X86ISelLowering.cpp @@ -24629,7 +24629,7 @@ static SDValue PerformAndCombine(SDNode *N, SelectionDAG &DAG, uint64_t Mask = MaskNode->getZExtValue(); uint64_t Shift = ShiftNode->getZExtValue(); if (isMask_64(Mask)) { - uint64_t MaskSize = CountPopulation_64(Mask); + uint64_t MaskSize = countPopulation(Mask); if (Shift + MaskSize <= VT.getSizeInBits()) return DAG.getNode(X86ISD::BEXTR, DL, VT, N0.getOperand(0), DAG.getConstant(Shift | (MaskSize << 8), VT)); diff --git a/lib/Target/X86/X86InstrCompiler.td b/lib/Target/X86/X86InstrCompiler.td index 3feae6d31fd..4dbba678e7c 100644 --- a/lib/Target/X86/X86InstrCompiler.td +++ b/lib/Target/X86/X86InstrCompiler.td @@ -1563,8 +1563,12 @@ def : Pat<(shl GR32:$src1, (i8 1)), (ADD32rr GR32:$src1, GR32:$src1)>; def : Pat<(shl GR64:$src1, (i8 1)), (ADD64rr GR64:$src1, GR64:$src1)>; // Helper imms that check if a mask doesn't change significant shift bits. -def immShift32 : ImmLeaf= 5; }]>; -def immShift64 : ImmLeaf= 6; }]>; +def immShift32 : ImmLeaf(Imm) >= 5; +}]>; +def immShift64 : ImmLeaf(Imm) >= 6; +}]>; // Shift amount is implicitly masked. multiclass MaskedShiftAmountPats { diff --git a/lib/Target/X86/X86InstrInfo.td b/lib/Target/X86/X86InstrInfo.td index c85c1099fd1..ba8e28ad876 100644 --- a/lib/Target/X86/X86InstrInfo.td +++ b/lib/Target/X86/X86InstrInfo.td @@ -2216,11 +2216,11 @@ let Predicates = [HasBMI2], Defs = [EFLAGS] in { def CountTrailingOnes : SDNodeXFormgetZExtValue())); + return getI8Imm(countTrailingOnes(N->getZExtValue())); }]>; def BZHIMask : ImmLeaf 32); + return isMask_64(Imm) && (countTrailingOnes(Imm) > 32); }]>; let Predicates = [HasBMI2] in { diff --git a/unittests/Support/MathExtrasTest.cpp b/unittests/Support/MathExtrasTest.cpp index 93a38cb03fd..9737393ee40 100644 --- a/unittests/Support/MathExtrasTest.cpp +++ b/unittests/Support/MathExtrasTest.cpp @@ -141,21 +141,18 @@ TEST(MathExtras, ByteSwap_64) { EXPECT_EQ(0x1100FFEEDDCCBBAAULL, ByteSwap_64(0xAABBCCDDEEFF0011LL)); } -TEST(MathExtras, CountLeadingOnes_32) { +TEST(MathExtras, countLeadingOnes) { for (int i = 30; i >= 0; --i) { // Start with all ones and unset some bit. - EXPECT_EQ(31u - i, CountLeadingOnes_32(0xFFFFFFFF ^ (1 << i))); + EXPECT_EQ(31u - i, countLeadingOnes(0xFFFFFFFF ^ (1 << i))); } -} - -TEST(MathExtras, CountLeadingOnes_64) { for (int i = 62; i >= 0; --i) { // Start with all ones and unset some bit. - EXPECT_EQ(63u - i, CountLeadingOnes_64(0xFFFFFFFFFFFFFFFFLL ^ (1LL << i))); + EXPECT_EQ(63u - i, countLeadingOnes(0xFFFFFFFFFFFFFFFFLL ^ (1LL << i))); } for (int i = 30; i >= 0; --i) { // Start with all ones and unset some bit. - EXPECT_EQ(31u - i, CountLeadingOnes_32(0xFFFFFFFF ^ (1 << i))); + EXPECT_EQ(31u - i, countLeadingOnes(0xFFFFFFFF ^ (1 << i))); } } diff --git a/utils/TableGen/AsmMatcherEmitter.cpp b/utils/TableGen/AsmMatcherEmitter.cpp index 3b2e48d1d01..65a34d3ae01 100644 --- a/utils/TableGen/AsmMatcherEmitter.cpp +++ b/utils/TableGen/AsmMatcherEmitter.cpp @@ -2956,8 +2956,8 @@ void AsmMatcherEmitter::run(raw_ostream &OS) { OS << " HadMatchOtherThanFeatures = true;\n"; OS << " uint64_t NewMissingFeatures = it->RequiredFeatures & " "~AvailableFeatures;\n"; - OS << " if (CountPopulation_64(NewMissingFeatures) <=\n" - " CountPopulation_64(MissingFeatures))\n"; + OS << " if (countPopulation(NewMissingFeatures) <=\n" + " countPopulation(MissingFeatures))\n"; OS << " MissingFeatures = NewMissingFeatures;\n"; OS << " continue;\n"; OS << " }\n"; -- 2.34.1