Revision: 23229
Author: [email protected]
Date: Wed Aug 20 12:10:41 2014 UTC
Log: 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
[email protected]
Review URL: https://codereview.chromium.org/494633002
http://code.google.com/p/v8/source/detail?r=23229
Deleted:
/branches/bleeding_edge/src/compiler-intrinsics.h
Modified:
/branches/bleeding_edge/include/v8config.h
/branches/bleeding_edge/src/base/bits.h
/branches/bleeding_edge/src/compiler/arm/instruction-selector-arm.cc
/branches/bleeding_edge/src/data-flow.cc
/branches/bleeding_edge/src/data-flow.h
/branches/bleeding_edge/src/frames.cc
/branches/bleeding_edge/src/heap/mark-compact.cc
/branches/bleeding_edge/src/heap/mark-compact.h
/branches/bleeding_edge/src/hydrogen-instructions.cc
/branches/bleeding_edge/src/mips/simulator-mips.cc
/branches/bleeding_edge/src/mips64/simulator-mips64.cc
/branches/bleeding_edge/test/base-unittests/bits-unittest.cc
=======================================
--- /branches/bleeding_edge/src/compiler-intrinsics.h Wed Jul 30 13:54:45
2014 UTC
+++ /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<long>(value)); //NOLINT
- return static_cast<int>(result);
-}
-
-int CompilerIntrinsics::CountLeadingZeros(uint32_t value) {
- unsigned long result; //NOLINT
- _BitScanReverse(&result, static_cast<long>(value)); //NOLINT
- return 31 - static_cast<int>(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_
=======================================
--- /branches/bleeding_edge/include/v8config.h Tue Apr 29 06:42:26 2014 UTC
+++ /branches/bleeding_edge/include/v8config.h Wed Aug 20 12:10:41 2014 UTC
@@ -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
=======================================
--- /branches/bleeding_edge/src/base/bits.h Thu Aug 14 09:31:52 2014 UTC
+++ /branches/bleeding_edge/src/base/bits.h Wed Aug 20 12:10:41 2014 UTC
@@ -6,6 +6,9 @@
#define V8_BASE_BITS_H_
#include "include/v8stdint.h"
+#if V8_CC_MSVC
+#include <intrin.h>
+#endif
#if V8_OS_WIN32
#include "src/base/win32-headers.h"
#endif
@@ -14,6 +17,61 @@
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<uint32_t>(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<uint32_t>(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));
=======================================
--- /branches/bleeding_edge/src/compiler/arm/instruction-selector-arm.cc
Wed Aug 20 04:01:00 2014 UTC
+++ /branches/bleeding_edge/src/compiler/arm/instruction-selector-arm.cc
Wed Aug 20 12:10:41 2014 UTC
@@ -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 @@
}
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 @@
}
// 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 @@
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));
=======================================
--- /branches/bleeding_edge/src/data-flow.cc Tue Jun 3 08:12:43 2014 UTC
+++ /branches/bleeding_edge/src/data-flow.cc Wed Aug 20 12:10:41 2014 UTC
@@ -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/data-flow.h"
+#include "src/base/bits.h"
#include "src/scopes.h"
namespace v8 {
@@ -40,4 +40,15 @@
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
=======================================
--- /branches/bleeding_edge/src/data-flow.h Mon Aug 4 11:34:54 2014 UTC
+++ /branches/bleeding_edge/src/data-flow.h Wed Aug 20 12:10:41 2014 UTC
@@ -164,14 +164,7 @@
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 @@
uint32_t* data_;
};
+
class GrowableBitVector BASE_EMBEDDED {
public:
class Iterator BASE_EMBEDDED {
@@ -241,8 +235,7 @@
BitVector* bits_;
};
-
-} } // namespace v8::internal
-
+} // namespace internal
+} // namespace v8
#endif // V8_DATAFLOW_H_
=======================================
--- /branches/bleeding_edge/src/frames.cc Tue Aug 5 08:18:22 2014 UTC
+++ /branches/bleeding_edge/src/frames.cc Wed Aug 20 12:10:41 2014 UTC
@@ -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 NumRegs(RegList reglist) {
- return CompilerIntrinsics::CountSetBits(reglist);
+ return base::bits::CountSetBits32(reglist);
}
=======================================
--- /branches/bleeding_edge/src/heap/mark-compact.cc Tue Aug 19 10:56:49
2014 UTC
+++ /branches/bleeding_edge/src/heap/mark-compact.cc Wed Aug 20 12:10:41
2014 UTC
@@ -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 @@
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 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;
=======================================
--- /branches/bleeding_edge/src/heap/mark-compact.h Tue Aug 5 11:58:24
2014 UTC
+++ /branches/bleeding_edge/src/heap/mark-compact.h Wed Aug 20 12:10:41
2014 UTC
@@ -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 {
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc Mon Aug 18
07:54:19 2014 UTC
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Wed Aug 20
12:10:41 2014 UTC
@@ -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 @@
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();
=======================================
--- /branches/bleeding_edge/src/mips/simulator-mips.cc Wed Aug 13 14:43:22
2014 UTC
+++ /branches/bleeding_edge/src/mips/simulator-mips.cc Wed Aug 20 12:10:41
2014 UTC
@@ -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 @@
} 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 @@
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();
=======================================
--- /branches/bleeding_edge/src/mips64/simulator-mips64.cc Mon Aug 4
11:34:54 2014 UTC
+++ /branches/bleeding_edge/src/mips64/simulator-mips64.cc Wed Aug 20
12:10:41 2014 UTC
@@ -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 @@
} 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 @@
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();
=======================================
--- /branches/bleeding_edge/test/base-unittests/bits-unittest.cc Thu Aug 14
09:07:58 2014 UTC
+++ /branches/bleeding_edge/test/base-unittests/bits-unittest.cc Wed Aug 20
12:10:41 2014 UTC
@@ -10,6 +10,36 @@
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));
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
