From b15a082d56fb9fa8832109970f40312761566c0d Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Wed, 20 Aug 2014 12:10:41 +0000 Subject: [PATCH] Fix implementation of bit count functions. The bit counting functions provided by CompilerIntrinsics were undefined for zero, which was easily overlooked and unsafe in general. Also their implementation was kinda hacky and mostly untested. Fixed the implementation and moved the functions to base/bits.h. TEST=base-unittests,cctest,compiler-unittests,mjsunit R=hpayer@chromium.org Review URL: https://codereview.chromium.org/494633002 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@23229 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- include/v8config.h | 9 ++++ src/base/bits.h | 58 ++++++++++++++++++++++ src/compiler-intrinsics.h | 73 ---------------------------- src/compiler/arm/instruction-selector-arm.cc | 18 +++---- src/data-flow.cc | 17 +++++-- src/data-flow.h | 15 ++---- src/frames.cc | 3 +- src/heap/mark-compact.cc | 5 +- src/heap/mark-compact.h | 1 - src/hydrogen-instructions.cc | 4 +- src/mips/simulator-mips.cc | 9 ++-- src/mips64/simulator-mips64.cc | 9 ++-- test/base-unittests/bits-unittest.cc | 30 ++++++++++++ 13 files changed, 137 insertions(+), 114 deletions(-) delete mode 100644 src/compiler-intrinsics.h diff --git a/include/v8config.h b/include/v8config.h index 452ffc7..be02b6e 100644 --- a/include/v8config.h +++ b/include/v8config.h @@ -175,7 +175,10 @@ // V8_HAS_ATTRIBUTE_VISIBILITY - __attribute__((visibility)) supported // V8_HAS_ATTRIBUTE_WARN_UNUSED_RESULT - __attribute__((warn_unused_result)) // supported +// V8_HAS_BUILTIN_CLZ - __builtin_clz() supported +// V8_HAS_BUILTIN_CTZ - __builtin_ctz() supported // V8_HAS_BUILTIN_EXPECT - __builtin_expect() supported +// V8_HAS_BUILTIN_POPCOUNT - __builtin_popcount() supported // V8_HAS_DECLSPEC_ALIGN - __declspec(align(n)) supported // V8_HAS_DECLSPEC_DEPRECATED - __declspec(deprecated) supported // V8_HAS_DECLSPEC_NOINLINE - __declspec(noinline) supported @@ -206,7 +209,10 @@ # define V8_HAS_ATTRIBUTE_WARN_UNUSED_RESULT \ (__has_attribute(warn_unused_result)) +# define V8_HAS_BUILTIN_CLZ (__has_builtin(__builtin_clz)) +# define V8_HAS_BUILTIN_CTZ (__has_builtin(__builtin_ctz)) # define V8_HAS_BUILTIN_EXPECT (__has_builtin(__builtin_expect)) +# define V8_HAS_BUILTIN_POPCOUNT (__has_builtin(__builtin_popcount)) # define V8_HAS_CXX11_ALIGNAS (__has_feature(cxx_alignas)) # define V8_HAS_CXX11_STATIC_ASSERT (__has_feature(cxx_static_assert)) @@ -238,7 +244,10 @@ # define V8_HAS_ATTRIBUTE_WARN_UNUSED_RESULT \ (!V8_CC_INTEL && V8_GNUC_PREREQ(4, 1, 0)) +# define V8_HAS_BUILTIN_CLZ (V8_GNUC_PREREQ(3, 4, 0)) +# define V8_HAS_BUILTIN_CTZ (V8_GNUC_PREREQ(3, 4, 0)) # define V8_HAS_BUILTIN_EXPECT (V8_GNUC_PREREQ(2, 96, 0)) +# define V8_HAS_BUILTIN_POPCOUNT (V8_GNUC_PREREQ(3, 4, 0)) // g++ requires -std=c++0x or -std=gnu++0x to support C++11 functionality // without warnings (functionality used by the macros below). These modes diff --git a/src/base/bits.h b/src/base/bits.h index ec0f551..129bf62 100644 --- a/src/base/bits.h +++ b/src/base/bits.h @@ -6,6 +6,9 @@ #define V8_BASE_BITS_H_ #include "include/v8stdint.h" +#if V8_CC_MSVC +#include +#endif #if V8_OS_WIN32 #include "src/base/win32-headers.h" #endif @@ -14,6 +17,61 @@ namespace v8 { namespace base { namespace bits { +// CountSetBits32(value) returns the number of bits set in |value|. +inline uint32_t CountSetBits32(uint32_t value) { +#if V8_HAS_BUILTIN_POPCOUNT + return __builtin_popcount(value); +#else + value = ((value >> 1) & 0x55555555) + (value & 0x55555555); + value = ((value >> 2) & 0x33333333) + (value & 0x33333333); + value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f); + value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff); + value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff); + return value; +#endif +} + + +// CountLeadingZeros32(value) returns the number of zero bits following the most +// significant 1 bit in |value| if |value| is non-zero, otherwise it returns 32. +inline uint32_t CountLeadingZeros32(uint32_t value) { +#if V8_HAS_BUILTIN_CLZ + return value ? __builtin_clz(value) : 32; +#elif V8_CC_MSVC + unsigned long result; // NOLINT(runtime/int) + if (!_BitScanReverse(&result, value)) return 32; + return static_cast(31 - result); +#else + value = value | (value >> 1); + value = value | (value >> 2); + value = value | (value >> 4); + value = value | (value >> 8); + value = value | (value >> 16); + return CountSetBits32(~value); +#endif +} + + +// CountTrailingZeros32(value) returns the number of zero bits preceding the +// least significant 1 bit in |value| if |value| is non-zero, otherwise it +// returns 32. +inline uint32_t CountTrailingZeros32(uint32_t value) { +#if V8_HAS_BUILTIN_CTZ + return value ? __builtin_ctz(value) : 32; +#elif V8_CC_MSVC + unsigned long result; // NOLINT(runtime/int) + if (!_BitScanForward(&result, value)) return 32; + return static_cast(result); +#else + if (value == 0) return 32; + unsigned count = 0; + for (value ^= value - 1; value >>= 1; ++count) + ; + return count; +#endif +} + + inline uint32_t RotateRight32(uint32_t value, uint32_t shift) { if (shift == 0) return value; return (value >> shift) | (value << (32 - shift)); diff --git a/src/compiler-intrinsics.h b/src/compiler-intrinsics.h deleted file mode 100644 index 669dd28..0000000 --- a/src/compiler-intrinsics.h +++ /dev/null @@ -1,73 +0,0 @@ -// Copyright 2006-2008 the V8 project authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#ifndef V8_COMPILER_INTRINSICS_H_ -#define V8_COMPILER_INTRINSICS_H_ - -#include "src/base/macros.h" - -namespace v8 { -namespace internal { - -class CompilerIntrinsics { - public: - // Returns number of zero bits preceding least significant 1 bit. - // Undefined for zero value. - INLINE(static int CountTrailingZeros(uint32_t value)); - - // Returns number of zero bits following most significant 1 bit. - // Undefined for zero value. - INLINE(static int CountLeadingZeros(uint32_t value)); - - // Returns the number of bits set. - INLINE(static int CountSetBits(uint32_t value)); -}; - -#ifdef __GNUC__ -int CompilerIntrinsics::CountTrailingZeros(uint32_t value) { - return __builtin_ctz(value); -} - -int CompilerIntrinsics::CountLeadingZeros(uint32_t value) { - return __builtin_clz(value); -} - -int CompilerIntrinsics::CountSetBits(uint32_t value) { - return __builtin_popcount(value); -} - -#elif defined(_MSC_VER) - -#pragma intrinsic(_BitScanForward) -#pragma intrinsic(_BitScanReverse) - -int CompilerIntrinsics::CountTrailingZeros(uint32_t value) { - unsigned long result; //NOLINT - _BitScanForward(&result, static_cast(value)); //NOLINT - return static_cast(result); -} - -int CompilerIntrinsics::CountLeadingZeros(uint32_t value) { - unsigned long result; //NOLINT - _BitScanReverse(&result, static_cast(value)); //NOLINT - return 31 - static_cast(result); -} - -int CompilerIntrinsics::CountSetBits(uint32_t value) { - // Manually count set bits. - value = ((value >> 1) & 0x55555555) + (value & 0x55555555); - value = ((value >> 2) & 0x33333333) + (value & 0x33333333); - value = ((value >> 4) & 0x0f0f0f0f) + (value & 0x0f0f0f0f); - value = ((value >> 8) & 0x00ff00ff) + (value & 0x00ff00ff); - value = ((value >> 16) & 0x0000ffff) + (value & 0x0000ffff); - return value; -} - -#else -#error Unsupported compiler -#endif - -} } // namespace v8::internal - -#endif // V8_COMPILER_INTRINSICS_H_ diff --git a/src/compiler/arm/instruction-selector-arm.cc b/src/compiler/arm/instruction-selector-arm.cc index 5bd1352..5850568 100644 --- a/src/compiler/arm/instruction-selector-arm.cc +++ b/src/compiler/arm/instruction-selector-arm.cc @@ -2,9 +2,9 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. +#include "src/base/bits.h" #include "src/compiler/instruction-selector-impl.h" #include "src/compiler/node-matchers.h" -#include "src/compiler-intrinsics.h" namespace v8 { namespace internal { @@ -423,10 +423,10 @@ void InstructionSelector::VisitWord32And(Node* node) { } if (IsSupported(ARMv7) && m.right().HasValue()) { uint32_t value = m.right().Value(); - uint32_t width = CompilerIntrinsics::CountSetBits(value); - uint32_t msb = CompilerIntrinsics::CountLeadingZeros(value); + uint32_t width = base::bits::CountSetBits32(value); + uint32_t msb = base::bits::CountLeadingZeros32(value); if (width != 0 && msb + width == 32) { - DCHECK_EQ(0, CompilerIntrinsics::CountTrailingZeros(value)); + DCHECK_EQ(0, base::bits::CountTrailingZeros32(value)); if (m.left().IsWord32Shr()) { Int32BinopMatcher mleft(m.left().node()); if (mleft.right().IsInRange(0, 31)) { @@ -442,8 +442,8 @@ void InstructionSelector::VisitWord32And(Node* node) { } // Try to interpret this AND as BFC. width = 32 - width; - msb = CompilerIntrinsics::CountLeadingZeros(~value); - uint32_t lsb = CompilerIntrinsics::CountTrailingZeros(~value); + msb = base::bits::CountLeadingZeros32(~value); + uint32_t lsb = base::bits::CountTrailingZeros32(~value); if (msb + width + lsb == 32) { Emit(kArmBfc, g.DefineSameAsFirst(node), g.UseRegister(m.left().node()), g.TempImmediate(lsb), g.TempImmediate(width)); @@ -536,10 +536,10 @@ void InstructionSelector::VisitWord32Shr(Node* node) { Int32BinopMatcher mleft(m.left().node()); if (mleft.right().HasValue()) { uint32_t value = (mleft.right().Value() >> lsb) << lsb; - uint32_t width = CompilerIntrinsics::CountSetBits(value); - uint32_t msb = CompilerIntrinsics::CountLeadingZeros(value); + uint32_t width = base::bits::CountSetBits32(value); + uint32_t msb = base::bits::CountLeadingZeros32(value); if (msb + width + lsb == 32) { - DCHECK_EQ(lsb, CompilerIntrinsics::CountTrailingZeros(value)); + DCHECK_EQ(lsb, base::bits::CountTrailingZeros32(value)); Emit(kArmUbfx, g.DefineAsRegister(node), g.UseRegister(mleft.left().node()), g.TempImmediate(lsb), g.TempImmediate(width)); diff --git a/src/data-flow.cc b/src/data-flow.cc index e591778..9494525 100644 --- a/src/data-flow.cc +++ b/src/data-flow.cc @@ -2,9 +2,9 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -#include "src/v8.h" - #include "src/data-flow.h" + +#include "src/base/bits.h" #include "src/scopes.h" namespace v8 { @@ -40,4 +40,15 @@ void BitVector::Iterator::Advance() { current_value_ = val >> 1; } -} } // namespace v8::internal + +int BitVector::Count() const { + int count = 0; + for (int i = 0; i < data_length_; i++) { + int data = data_[i]; + if (data != 0) count += base::bits::CountSetBits32(data); + } + return count; +} + +} // namespace internal +} // namespace v8 diff --git a/src/data-flow.h b/src/data-flow.h index 042e29f..ad96c2c 100644 --- a/src/data-flow.h +++ b/src/data-flow.h @@ -164,14 +164,7 @@ class BitVector: public ZoneObject { return true; } - int Count() const { - int count = 0; - for (int i = 0; i < data_length_; i++) { - int data = data_[i]; - if (data != 0) count += CompilerIntrinsics::CountSetBits(data); - } - return count; - } + int Count() const; int length() const { return length_; } @@ -185,6 +178,7 @@ class BitVector: public ZoneObject { uint32_t* data_; }; + class GrowableBitVector BASE_EMBEDDED { public: class Iterator BASE_EMBEDDED { @@ -241,8 +235,7 @@ class GrowableBitVector BASE_EMBEDDED { BitVector* bits_; }; - -} } // namespace v8::internal - +} // namespace internal +} // namespace v8 #endif // V8_DATAFLOW_H_ diff --git a/src/frames.cc b/src/frames.cc index e892f80..b22fafd 100644 --- a/src/frames.cc +++ b/src/frames.cc @@ -5,6 +5,7 @@ #include "src/v8.h" #include "src/ast.h" +#include "src/base/bits.h" #include "src/deoptimizer.h" #include "src/frames-inl.h" #include "src/full-codegen.h" @@ -1579,7 +1580,7 @@ int StackHandler::Rewind(Isolate* isolate, // ------------------------------------------------------------------------- int NumRegs(RegList reglist) { - return CompilerIntrinsics::CountSetBits(reglist); + return base::bits::CountSetBits32(reglist); } diff --git a/src/heap/mark-compact.cc b/src/heap/mark-compact.cc index 8a44ce1..f114ba3 100644 --- a/src/heap/mark-compact.cc +++ b/src/heap/mark-compact.cc @@ -5,6 +5,7 @@ #include "src/v8.h" #include "src/base/atomicops.h" +#include "src/base/bits.h" #include "src/code-stubs.h" #include "src/compilation-cache.h" #include "src/cpu-profiler.h" @@ -1926,7 +1927,7 @@ static void DiscoverGreyObjectsOnPage(MarkingDeque* marking_deque, int offset = 0; while (grey_objects != 0) { - int trailing_zeros = CompilerIntrinsics::CountTrailingZeros(grey_objects); + int trailing_zeros = base::bits::CountTrailingZeros32(grey_objects); grey_objects >>= trailing_zeros; offset += trailing_zeros; MarkBit markbit(cell, 1 << offset, false); @@ -1965,7 +1966,7 @@ int MarkCompactCollector::DiscoverAndEvacuateBlackObjectsOnPage( int offset = 0; while (current_cell != 0) { - int trailing_zeros = CompilerIntrinsics::CountTrailingZeros(current_cell); + int trailing_zeros = base::bits::CountTrailingZeros32(current_cell); current_cell >>= trailing_zeros; offset += trailing_zeros; Address address = cell_base + offset * kPointerSize; diff --git a/src/heap/mark-compact.h b/src/heap/mark-compact.h index a32c16b..7a8b106 100644 --- a/src/heap/mark-compact.h +++ b/src/heap/mark-compact.h @@ -5,7 +5,6 @@ #ifndef V8_HEAP_MARK_COMPACT_H_ #define V8_HEAP_MARK_COMPACT_H_ -#include "src/compiler-intrinsics.h" #include "src/heap/spaces.h" namespace v8 { diff --git a/src/hydrogen-instructions.cc b/src/hydrogen-instructions.cc index 896efcf..6eb7306 100644 --- a/src/hydrogen-instructions.cc +++ b/src/hydrogen-instructions.cc @@ -4,6 +4,7 @@ #include "src/v8.h" +#include "src/base/bits.h" #include "src/double.h" #include "src/factory.h" #include "src/hydrogen-infer-representation.h" @@ -4179,8 +4180,7 @@ HInstruction* HUnaryMathOperation::New( return H_CONSTANT_DOUBLE(Floor(d)); case kMathClz32: { uint32_t i = DoubleToUint32(d); - return H_CONSTANT_INT( - (i == 0) ? 32 : CompilerIntrinsics::CountLeadingZeros(i)); + return H_CONSTANT_INT(base::bits::CountLeadingZeros32(i)); } default: UNREACHABLE(); diff --git a/src/mips/simulator-mips.cc b/src/mips/simulator-mips.cc index 2478539..b41e61d 100644 --- a/src/mips/simulator-mips.cc +++ b/src/mips/simulator-mips.cc @@ -12,6 +12,7 @@ #if V8_TARGET_ARCH_MIPS #include "src/assembler.h" +#include "src/base/bits.h" #include "src/disasm.h" #include "src/globals.h" // Need the BitCast. #include "src/mips/constants-mips.h" @@ -1966,10 +1967,8 @@ void Simulator::ConfigureTypeRegister(Instruction* instr, } else { // MIPS spec: If no bits were set in GPR rs, the result written to // GPR rd is 32. - // GCC __builtin_clz: If input is 0, the result is undefined. DCHECK(instr->SaValue() == 1); - *alu_out = - rs_u == 0 ? 32 : CompilerIntrinsics::CountLeadingZeros(rs_u); + *alu_out = base::bits::CountLeadingZeros32(rs_u); } break; case MFLO: @@ -2094,9 +2093,7 @@ void Simulator::ConfigureTypeRegister(Instruction* instr, case CLZ: // MIPS32 spec: If no bits were set in GPR rs, the result written to // GPR rd is 32. - // GCC __builtin_clz: If input is 0, the result is undefined. - *alu_out = - rs_u == 0 ? 32 : CompilerIntrinsics::CountLeadingZeros(rs_u); + *alu_out = base::bits::CountLeadingZeros32(rs_u); break; default: UNREACHABLE(); diff --git a/src/mips64/simulator-mips64.cc b/src/mips64/simulator-mips64.cc index c075584..cb6649a 100644 --- a/src/mips64/simulator-mips64.cc +++ b/src/mips64/simulator-mips64.cc @@ -12,6 +12,7 @@ #if V8_TARGET_ARCH_MIPS64 #include "src/assembler.h" +#include "src/base/bits.h" #include "src/disasm.h" #include "src/globals.h" // Need the BitCast. #include "src/mips64/constants-mips64.h" @@ -2074,10 +2075,8 @@ void Simulator::ConfigureTypeRegister(Instruction* instr, } else { // MIPS spec: If no bits were set in GPR rs, the result written to // GPR rd is 32. - // GCC __builtin_clz: If input is 0, the result is undefined. DCHECK(instr->SaValue() == 1); - *alu_out = - rs_u == 0 ? 32 : CompilerIntrinsics::CountLeadingZeros(rs_u); + *alu_out = base::bits::CountLeadingZeros32(rs_u); } break; case MFLO: @@ -2220,9 +2219,7 @@ void Simulator::ConfigureTypeRegister(Instruction* instr, case CLZ: // MIPS32 spec: If no bits were set in GPR rs, the result written to // GPR rd is 32. - // GCC __builtin_clz: If input is 0, the result is undefined. - *alu_out = - rs_u == 0 ? 32 : CompilerIntrinsics::CountLeadingZeros(rs_u); + *alu_out = base::bits::CountLeadingZeros32(rs_u); break; default: UNREACHABLE(); diff --git a/test/base-unittests/bits-unittest.cc b/test/base-unittests/bits-unittest.cc index 689fb41..56d3d92 100644 --- a/test/base-unittests/bits-unittest.cc +++ b/test/base-unittests/bits-unittest.cc @@ -10,6 +10,36 @@ namespace v8 { namespace base { namespace bits { +TEST(BitsTest, CountSetBits32) { + EXPECT_EQ(0u, CountSetBits32(0)); + EXPECT_EQ(1u, CountSetBits32(1)); + EXPECT_EQ(8u, CountSetBits32(0x11111111)); + EXPECT_EQ(16u, CountSetBits32(0xf0f0f0f0)); + EXPECT_EQ(24u, CountSetBits32(0xfff0f0ff)); + EXPECT_EQ(32u, CountSetBits32(0xffffffff)); +} + + +TEST(BitsTest, CountLeadingZeros32) { + EXPECT_EQ(32u, CountLeadingZeros32(0)); + EXPECT_EQ(31u, CountLeadingZeros32(1)); + TRACED_FORRANGE(uint32_t, shift, 0, 31) { + EXPECT_EQ(31u - shift, CountLeadingZeros32(1u << shift)); + } + EXPECT_EQ(4u, CountLeadingZeros32(0x0f0f0f0f)); +} + + +TEST(BitsTest, CountTrailingZeros32) { + EXPECT_EQ(32u, CountTrailingZeros32(0)); + EXPECT_EQ(31u, CountTrailingZeros32(0x80000000)); + TRACED_FORRANGE(uint32_t, shift, 0, 31) { + EXPECT_EQ(shift, CountTrailingZeros32(1u << shift)); + } + EXPECT_EQ(4u, CountTrailingZeros32(0xf0f0f0f0)); +} + + TEST(BitsTest, RotateRight32) { TRACED_FORRANGE(uint32_t, shift, 0, 31) { EXPECT_EQ(0u, RotateRight32(0u, shift)); -- 2.7.4