Bug 906368 - IonMonkey: Define a proper CountPopulation32 function, and use it in place of manual code in RegisterSets.h. r=nbp
authorDan Gohman <sunfish@google.com>
Mon, 19 Aug 2013 12:32:22 -0700
changeset 156083 8d3b2cb5d698934a49dfa315f8ba7bcb55a20dc2
parent 156082 f6d8cd174ec927fce5f1e1f716e78ca1303127bc
child 156084 12b9f93e32adf1be6eaa213738715d569492ef02
push id2961
push userlsblakk@mozilla.com
push dateMon, 28 Oct 2013 21:59:28 +0000
treeherdermozilla-beta@73ef4f13486f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnbp
bugs906368
milestone26.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 906368 - IonMonkey: Define a proper CountPopulation32 function, and use it in place of manual code in RegisterSets.h. r=nbp
js/src/jit/RegisterSets.h
mfbt/MathAlgorithms.h
mfbt/tests/TestCountPopulation.cpp
--- a/js/src/jit/RegisterSets.h
+++ b/js/src/jit/RegisterSets.h
@@ -444,21 +444,17 @@ class TypedRegisterSet
     }
     void clear() {
         bits_ = 0;
     }
     uint32_t bits() const {
         return bits_;
     }
     uint32_t size() const {
-        uint32_t sum2  = (bits_ & 0x55555555) + ((bits_ & 0xaaaaaaaa) >> 1);
-        uint32_t sum4  = (sum2  & 0x33333333) + ((sum2  & 0xcccccccc) >> 2);
-        uint32_t sum8  = (sum4  & 0x0f0f0f0f) + ((sum4  & 0xf0f0f0f0) >> 4);
-        uint32_t sum16 = (sum8  & 0x00ff00ff) + ((sum8  & 0xff00ff00) >> 8);
-        return sum16;
+        return mozilla::CountPopulation32(bits_);
     }
     bool operator ==(const TypedRegisterSet<T> &other) const {
         return other.bits_ == bits_;
     }
 };
 
 typedef TypedRegisterSet<Register> GeneralRegisterSet;
 typedef TypedRegisterSet<FloatRegister> FloatRegisterSet;
--- a/mfbt/MathAlgorithms.h
+++ b/mfbt/MathAlgorithms.h
@@ -182,16 +182,26 @@ namespace detail {
   CountTrailingZeroes32(uint32_t u)
   {
     unsigned long index;
     _BitScanForward(&index, static_cast<unsigned long>(u));
     return uint_fast8_t(index);
   }
 
   inline uint_fast8_t
+  CountPopulation32(uint32_t u)
+  {
+     uint32_t sum2  = (u     & 0x55555555) + ((u     & 0xaaaaaaaa) >> 1);
+     uint32_t sum4  = (sum2  & 0x33333333) + ((sum2  & 0xcccccccc) >> 2);
+     uint32_t sum8  = (sum4  & 0x0f0f0f0f) + ((sum4  & 0xf0f0f0f0) >> 4);
+     uint32_t sum16 = (sum8  & 0x00ff00ff) + ((sum8  & 0xff00ff00) >> 8);
+     return sum16;
+  }
+
+  inline uint_fast8_t
   CountLeadingZeroes64(uint64_t u)
   {
 #  if defined(MOZ_BITSCAN_WINDOWS64)
     unsigned long index;
     _BitScanReverse64(&index, static_cast<unsigned __int64>(u));
     return uint_fast8_t(63 - index);
 #  else
     uint32_t hi = uint32_t(u >> 32);
@@ -238,31 +248,38 @@ namespace detail {
 
   inline uint_fast8_t
   CountTrailingZeroes32(uint32_t u)
   {
     return __builtin_ctz(u);
   }
 
   inline uint_fast8_t
+  CountPopulation32(uint32_t u)
+  {
+    return __builtin_popcount(u);
+  }
+
+  inline uint_fast8_t
   CountLeadingZeroes64(uint64_t u)
   {
     return __builtin_clzll(u);
   }
 
   inline uint_fast8_t
   CountTrailingZeroes64(uint64_t u)
   {
     return __builtin_ctzll(u);
   }
 
 #else
 #  error "Implement these!"
   inline uint_fast8_t CountLeadingZeroes32(uint32_t u) MOZ_DELETE;
   inline uint_fast8_t CountTrailingZeroes32(uint32_t u) MOZ_DELETE;
+  inline uint_fast8_t CountPopulation32(uint32_t u) MOZ_DELETE;
   inline uint_fast8_t CountLeadingZeroes64(uint64_t u) MOZ_DELETE;
   inline uint_fast8_t CountTrailingZeroes64(uint64_t u) MOZ_DELETE;
 #endif
 
 } // namespace detail
 
 /**
  * Compute the number of high-order zero bits in the NON-ZERO number |u|.  That
@@ -295,16 +312,25 @@ CountLeadingZeroes32(uint32_t u)
  */
 inline uint_fast8_t
 CountTrailingZeroes32(uint32_t u)
 {
   MOZ_ASSERT(u != 0);
   return detail::CountTrailingZeroes32(u);
 }
 
+/**
+ * Compute the number of one bits in the number |u|,
+ */
+inline uint_fast8_t
+CountPopulation32(uint32_t u)
+{
+  return detail::CountPopulation32(u);
+}
+
 /** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
 inline uint_fast8_t
 CountLeadingZeroes64(uint64_t u)
 {
   MOZ_ASSERT(u != 0);
   return detail::CountLeadingZeroes64(u);
 }
 
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestCountPopulation.cpp
@@ -0,0 +1,32 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/MathAlgorithms.h"
+
+using mozilla::CountPopulation32;
+
+static void
+TestCountPopulation32()
+{
+  MOZ_ASSERT(CountPopulation32(0xFFFFFFFF) == 32);
+  MOZ_ASSERT(CountPopulation32(0xF0FF1000) == 13);
+  MOZ_ASSERT(CountPopulation32(0x7F8F0001) == 13);
+  MOZ_ASSERT(CountPopulation32(0x3FFF0100) == 15);
+  MOZ_ASSERT(CountPopulation32(0x1FF50010) == 12);
+  MOZ_ASSERT(CountPopulation32(0x00800000) == 1);
+  MOZ_ASSERT(CountPopulation32(0x00400000) == 1);
+  MOZ_ASSERT(CountPopulation32(0x00008000) == 1);
+  MOZ_ASSERT(CountPopulation32(0x00004000) == 1);
+  MOZ_ASSERT(CountPopulation32(0x00000080) == 1);
+  MOZ_ASSERT(CountPopulation32(0x00000040) == 1);
+  MOZ_ASSERT(CountPopulation32(0x00000001) == 1);
+  MOZ_ASSERT(CountPopulation32(0x00000000) == 0);
+}
+
+int main()
+{
+  TestCountPopulation32();
+  return 0;
+}