Refactor clz/ctz and fix getLSBSet.
authorkeith_miller@apple.com <keith_miller@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 24 Mar 2019 01:32:06 +0000 (01:32 +0000)
committerkeith_miller@apple.com <keith_miller@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 24 Mar 2019 01:32:06 +0000 (01:32 +0000)
https://bugs.webkit.org/show_bug.cgi?id=196162

Reviewed by Saam Barati.

Source/JavaScriptCore:

Refactor references of clz32/64 and ctz32 to use clz and ctz,
respectively.

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGOperations.cpp:
* runtime/JSBigInt.cpp:
(JSC::JSBigInt::digitDiv):
(JSC::JSBigInt::absoluteDivWithBigIntDivisor):
(JSC::JSBigInt::calculateMaximumCharactersRequired):
(JSC::JSBigInt::toStringBasePowerOfTwo):
(JSC::JSBigInt::compareToDouble):
* runtime/MathObject.cpp:
(JSC::mathProtoFuncClz32):

Source/WTF:

This patch makes clz32/64 and ctz32 generic so they work on any
numeric type. Since these methods work on any type we don't need
to have a separate implementation of getLSBSet, which also
happened to be getMSBSet. This patch also adds getMSBSet as there
may be users who want that in the future.

* wtf/MathExtras.h:
(WTF::clz):
(WTF::ctz):
(WTF::getLSBSet):
(WTF::getMSBSet):
(getLSBSet): Deleted.
(WTF::clz32): Deleted.
(WTF::clz64): Deleted.
(WTF::ctz32): Deleted.

Tools:

Add tests for clz, ctz, getLSBSet, and getMSBSet.

* TestWebKitAPI/Tests/WTF/MathExtras.cpp:
(TestWebKitAPI::TEST):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@243418 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/runtime/JSBigInt.cpp
Source/JavaScriptCore/runtime/MathObject.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/MathExtras.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/MathExtras.cpp

index aa4d210..f375a88 100644 (file)
@@ -1,3 +1,25 @@
+2019-03-23  Keith Miller  <keith_miller@apple.com>
+
+        Refactor clz/ctz and fix getLSBSet.
+        https://bugs.webkit.org/show_bug.cgi?id=196162
+
+        Reviewed by Saam Barati.
+
+        Refactor references of clz32/64 and ctz32 to use clz and ctz,
+        respectively.
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGOperations.cpp:
+        * runtime/JSBigInt.cpp:
+        (JSC::JSBigInt::digitDiv):
+        (JSC::JSBigInt::absoluteDivWithBigIntDivisor):
+        (JSC::JSBigInt::calculateMaximumCharactersRequired):
+        (JSC::JSBigInt::toStringBasePowerOfTwo):
+        (JSC::JSBigInt::compareToDouble):
+        * runtime/MathObject.cpp:
+        (JSC::mathProtoFuncClz32):
+
 2019-03-23  Yusuke Suzuki  <ysuzuki@apple.com>
 
         [JSC] Shrink sizeof(RegExp)
index a8c0dcd..e5b91bd 100644 (file)
@@ -704,7 +704,7 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
                 break;
             }
             uint32_t value = toUInt32(*number);
-            setConstant(node, jsNumber(clz32(value)));
+            setConstant(node, jsNumber(clz(value)));
             break;
         }
         switch (node->child1().useKind()) {
index 0f4cb30..34aea7c 100644 (file)
@@ -547,7 +547,7 @@ uint32_t JIT_OPERATION operationArithClz32(ExecState* exec, EncodedJSValue encod
     JSValue op1 = JSValue::decode(encodedOp1);
     uint32_t value = op1.toUInt32(exec);
     RETURN_IF_EXCEPTION(scope, 0);
-    return clz32(value);
+    return clz(value);
 }
 
 double JIT_OPERATION operationArithFRound(ExecState* exec, EncodedJSValue encodedOp1)
index c588e3f..7e3ccb4 100644 (file)
@@ -647,11 +647,7 @@ inline JSBigInt::Digit JSBigInt::digitDiv(Digit high, Digit low, Digit divisor,
 #else
     static constexpr Digit halfDigitBase = 1ull << halfDigitBits;
     // Adapted from Warren, Hacker's Delight, p. 152.
-#if USE(JSVALUE64)
-    unsigned s = clz64(divisor);
-#else
-    unsigned s = clz32(divisor);
-#endif
+    unsigned s = clz(divisor);
     // If {s} is digitBits here, it causes an undefined behavior.
     // But {s} is never digitBits since {divisor} is never zero here.
     ASSERT(s != digitBits);
@@ -984,7 +980,7 @@ void JSBigInt::absoluteDivWithBigIntDivisor(ExecState* exec, JSBigInt* dividend,
     // overflowing (they take a two digits wide input, and return a one digit
     // result).
     Digit lastDigit = divisor->digit(n - 1);
-    unsigned shift = sizeof(lastDigit) == 8 ? clz64(lastDigit) : clz32(lastDigit);
+    unsigned shift = clz(lastDigit);
 
     if (shift > 0) {
         divisor = absoluteLeftShiftAlwaysCopy(exec, divisor, shift, LeftShiftMode::SameSizeResult);
@@ -1445,11 +1441,7 @@ static constexpr size_t bitsPerCharTableMultiplier = 1u << bitsPerCharTableShift
 // Divide bit length of the BigInt by bits representable per character.
 uint64_t JSBigInt::calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign)
 {
-    unsigned leadingZeros;
-    if (sizeof(lastDigit) == 8)
-        leadingZeros = clz64(lastDigit);
-    else
-        leadingZeros = clz32(lastDigit);
+    unsigned leadingZeros = clz(lastDigit);
 
     size_t bitLength = length * digitBits - leadingZeros;
 
@@ -1482,18 +1474,14 @@ String JSBigInt::toStringBasePowerOfTwo(ExecState* exec, JSBigInt* x, unsigned r
 
     const unsigned length = x->length();
     const bool sign = x->sign();
-    const unsigned bitsPerChar = ctz32(radix);
+    const unsigned bitsPerChar = ctz(radix);
     const unsigned charMask = radix - 1;
     // Compute the length of the resulting string: divide the bit length of the
     // BigInt by the number of bits representable per character (rounding up).
     const Digit msd = x->digit(length - 1);
 
-#if USE(JSVALUE64)
-    const unsigned msdLeadingZeros = clz64(msd);
-#else
-    const unsigned msdLeadingZeros = clz32(msd);
-#endif
-    
+    const unsigned msdLeadingZeros = clz(msd);
+
     const size_t bitLength = length * digitBits - msdLeadingZeros;
     const size_t charsRequired = (bitLength + bitsPerChar - 1) / bitsPerChar + sign;
 
@@ -1876,7 +1864,7 @@ JSBigInt::ComparisonResult JSBigInt::compareToDouble(JSBigInt* x, double y)
 
     int xLength = x->length();
     Digit xMSD = x->digit(xLength - 1);
-    int msdLeadingZeros = sizeof(xMSD) == 8  ? clz64(xMSD) : clz32(xMSD);
+    int msdLeadingZeros = clz(xMSD);
 
     int xBitLength = xLength * digitBits - msdLeadingZeros;
     int yBitLength = exponent + 1;
index b4f93c9..71ce38b 100644 (file)
@@ -169,7 +169,7 @@ EncodedJSValue JSC_HOST_CALL mathProtoFuncClz32(ExecState* exec)
     auto scope = DECLARE_THROW_SCOPE(vm);
     uint32_t value = exec->argument(0).toUInt32(exec);
     RETURN_IF_EXCEPTION(scope, encodedJSValue());
-    return JSValue::encode(JSValue(clz32(value)));
+    return JSValue::encode(JSValue(clz(value)));
 }
 
 EncodedJSValue JSC_HOST_CALL mathProtoFuncCos(ExecState* exec)
index 884d884..4196136 100644 (file)
@@ -1,3 +1,26 @@
+2019-03-23  Keith Miller  <keith_miller@apple.com>
+
+        Refactor clz/ctz and fix getLSBSet.
+        https://bugs.webkit.org/show_bug.cgi?id=196162
+
+        Reviewed by Saam Barati.
+
+        This patch makes clz32/64 and ctz32 generic so they work on any
+        numeric type. Since these methods work on any type we don't need
+        to have a separate implementation of getLSBSet, which also
+        happened to be getMSBSet. This patch also adds getMSBSet as there
+        may be users who want that in the future.
+
+        * wtf/MathExtras.h:
+        (WTF::clz):
+        (WTF::ctz):
+        (WTF::getLSBSet):
+        (WTF::getMSBSet):
+        (getLSBSet): Deleted.
+        (WTF::clz32): Deleted.
+        (WTF::clz64): Deleted.
+        (WTF::ctz32): Deleted.
+
 2019-03-22  Keith Rollin  <krollin@apple.com>
 
         Enable ThinLTO support in Production builds
index 6e17700..a3edd2a 100644 (file)
@@ -26,6 +26,7 @@
 #pragma once
 
 #include <algorithm>
+#include <climits>
 #include <cmath>
 #include <float.h>
 #include <limits>
@@ -301,22 +302,6 @@ template<typename T> constexpr bool hasTwoOrMoreBitsSet(T value)
     return !hasZeroOrOneBitsSet(value);
 }
 
-// FIXME: Some Darwin projects shamelessly include WTF headers and don't build with C++14... See: rdar://problem/45395767
-// Since C++11 and before don't support constexpr statements we can't mark this function constexpr.
-#if !defined(WTF_CPP_STD_VER) || WTF_CPP_STD_VER >= 14
-template <typename T> constexpr unsigned getLSBSet(T value)
-{
-    typedef typename std::make_unsigned<T>::type UnsignedT;
-    unsigned result = 0;
-
-    UnsignedT unsignedValue = static_cast<UnsignedT>(value);
-    while (unsignedValue >>= 1)
-        ++result;
-
-    return result;
-}
-#endif
-
 template<typename T> inline T divideRoundedUp(T a, T b)
 {
     return (a + b - 1) / b;
@@ -630,49 +615,31 @@ void shuffleVector(VectorType& vector, const RandomFunc& randomFunc)
     shuffleVector(vector, vector.size(), randomFunc);
 }
 
-inline unsigned clz32(uint32_t number)
+template<typename T>
+inline unsigned clz(T value)
 {
-#if COMPILER(GCC_COMPATIBLE)
-    if (number)
-        return __builtin_clz(number);
-    return 32;
-#elif COMPILER(MSVC)
-    // Visual Studio 2008 or upper have __lzcnt, but we can't detect Intel AVX at compile time.
-    // So we use bit-scan-reverse operation to calculate clz.
-    unsigned long ret = 0;
-    if (_BitScanReverse(&ret, number))
-        return 31 - ret;
-    return 32;
-#else
-    unsigned zeroCount = 0;
-    for (int i = 31; i >= 0; i--) {
-        if (!(number >> i))
-            zeroCount++;
-        else
-            break;
-    }
-    return zeroCount;
-#endif
-}
+    constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
+    constexpr unsigned bitSize64 = sizeof(uint64_t) * CHAR_BIT;
+
+    using UT = typename std::make_unsigned<T>::type;
+    UT uValue = value;
 
-inline unsigned clz64(uint64_t number)
-{
 #if COMPILER(GCC_COMPATIBLE)
-    if (number)
-        return __builtin_clzll(number);
-    return 64;
+    if (uValue)
+        return __builtin_clzll(uValue) - (bitSize64 - bitSize);
+    return bitSize;
 #elif COMPILER(MSVC) && !CPU(X86)
     // Visual Studio 2008 or upper have __lzcnt, but we can't detect Intel AVX at compile time.
     // So we use bit-scan-reverse operation to calculate clz.
     // _BitScanReverse64 is defined in X86_64 and ARM in MSVC supported environments.
     unsigned long ret = 0;
     if (_BitScanReverse64(&ret, number))
-        return 63 - ret;
-    return 64;
+        return bitSize - ret;
+    return bitSize;
 #else
     unsigned zeroCount = 0;
-    for (int i = 63; i >= 0; i--) {
-        if (!(number >> i))
+    for (int i = bitSize64 - 1; i >= 0; i--) {
+        if (!(static_cast<uint64_t>(uValue) >> i))
             zeroCount++;
         else
             break;
@@ -681,30 +648,51 @@ inline unsigned clz64(uint64_t number)
 #endif
 }
 
-inline unsigned ctz32(uint32_t number)
+template<typename T>
+inline unsigned ctz(T value)
 {
+    constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
+
+    using UT = typename std::make_unsigned<T>::type;
+    UT uValue = value;
+
 #if COMPILER(GCC_COMPATIBLE)
-    if (number)
-        return __builtin_ctz(number);
-    return 32;
+    if (uValue)
+        return __builtin_ctzll(uValue);
+    return bitSize;
 #elif COMPILER(MSVC) && !CPU(X86)
     unsigned long ret = 0;
-    if (_BitScanForward(&ret, number))
+    if (_BitScanForward64(&ret, number))
         return ret;
-    return 32;
+    return bitSize;
 #else
     unsigned zeroCount = 0;
-    for (unsigned i = 0; i < 32; i++) {
-        if (number & 1)
+    for (unsigned i = 0; i < bitSize; i++) {
+        if (uValue & 1)
             break;
 
         zeroCount++;
-        number >>= 1;
+        uValue >>= 1;
     }
     return zeroCount;
 #endif
 }
 
+template<typename T>
+inline unsigned getLSBSet(T t)
+{
+    ASSERT(t);
+    return ctz(t);
+}
+
+template<typename T>
+inline unsigned getMSBSet(T t)
+{
+    constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
+    ASSERT(t);
+    return bitSize - 1 - clz(t);
+}
+
 } // namespace WTF
 
 using WTF::opaque;
@@ -712,6 +700,7 @@ using WTF::preciseIndexMaskPtr;
 using WTF::preciseIndexMaskShift;
 using WTF::preciseIndexMaskShiftForSize;
 using WTF::shuffleVector;
-using WTF::clz32;
-using WTF::clz64;
-using WTF::ctz32;
+using WTF::clz;
+using WTF::ctz;
+using WTF::getLSBSet;
+using WTF::getMSBSet;
index b782420..3057897 100644 (file)
@@ -1,3 +1,15 @@
+2019-03-23  Keith Miller  <keith_miller@apple.com>
+
+        Refactor clz/ctz and fix getLSBSet.
+        https://bugs.webkit.org/show_bug.cgi?id=196162
+
+        Reviewed by Saam Barati.
+
+        Add tests for clz, ctz, getLSBSet, and getMSBSet.
+
+        * TestWebKitAPI/Tests/WTF/MathExtras.cpp:
+        (TestWebKitAPI::TEST):
+
 2019-03-23  Carlos Garcia Campos  <cgarcia@igalia.com>
 
         [GTK][WPE] check-webkit-style doesn't complain about identifiers with underscores in files under glib, gtk or wpe dirs
index 1280d8e..7e66266 100644 (file)
@@ -433,4 +433,78 @@ TEST(WTF, roundUpToPowerOfTwo)
     EXPECT_EQ(WTF::roundUpToPowerOfTwo((1U << 31) + 1), 0U);
 }
 
+TEST(WTF, clz)
+{
+    EXPECT_EQ(WTF::clz<int32_t>(1), 31U);
+    EXPECT_EQ(WTF::clz<int32_t>(42), 26U);
+    EXPECT_EQ(WTF::clz<uint32_t>(static_cast<uint32_t>(-1)), 0U);
+    EXPECT_EQ(WTF::clz<uint32_t>(static_cast<uint32_t>(std::numeric_limits<int32_t>::min()) >> 1), 1U);
+    EXPECT_EQ(WTF::clz<uint32_t>(0), 32U);
+
+    EXPECT_EQ(WTF::clz<int8_t>(42), 2U);
+    EXPECT_EQ(WTF::clz<int8_t>(3), 6U);
+    EXPECT_EQ(WTF::clz<uint8_t>(static_cast<uint8_t>(-1)), 0U);
+    EXPECT_EQ(WTF::clz<uint8_t>(0), 8U);
+
+    EXPECT_EQ(WTF::clz<int64_t>(-1), 0U);
+    EXPECT_EQ(WTF::clz<int64_t>(1), 63U);
+    EXPECT_EQ(WTF::clz<int64_t>(3), 62U);
+    EXPECT_EQ(WTF::clz<uint64_t>(42), 58U);
+    EXPECT_EQ(WTF::clz<uint64_t>(0), 64U);
+}
+
+TEST(WTF, ctz)
+{
+    EXPECT_EQ(WTF::ctz<int32_t>(1), 0U);
+    EXPECT_EQ(WTF::ctz<int32_t>(42), 1U);
+    EXPECT_EQ(WTF::ctz<uint32_t>(static_cast<uint32_t>(-1)), 0U);
+    EXPECT_EQ(WTF::ctz<uint32_t>(static_cast<uint32_t>(std::numeric_limits<int32_t>::min()) >> 1), 30U);
+    EXPECT_EQ(WTF::ctz<uint32_t>(0), 32U);
+
+    EXPECT_EQ(WTF::ctz<int8_t>(42), 1U);
+    EXPECT_EQ(WTF::ctz<int8_t>(3), 0U);
+    EXPECT_EQ(WTF::ctz<uint8_t>(static_cast<uint8_t>(-1)), 0U);
+    EXPECT_EQ(WTF::ctz<uint8_t>(0), 8U);
+
+    EXPECT_EQ(WTF::ctz<int64_t>(static_cast<uint32_t>(-1)), 0U);
+    EXPECT_EQ(WTF::ctz<int64_t>(1), 0U);
+    EXPECT_EQ(WTF::ctz<int64_t>(3), 0U);
+    EXPECT_EQ(WTF::ctz<uint64_t>(42), 1U);
+    EXPECT_EQ(WTF::ctz<uint64_t>(0), 64U);
+}
+
+TEST(WTF, getLSBSet)
+{
+    EXPECT_EQ(WTF::getLSBSet<int32_t>(1), 0U);
+    EXPECT_EQ(WTF::getLSBSet<int32_t>(42), 1U);
+    EXPECT_EQ(WTF::getLSBSet<uint32_t>(static_cast<uint32_t>(-1)), 0U);
+    EXPECT_EQ(WTF::getLSBSet<uint32_t>(static_cast<uint32_t>(std::numeric_limits<int32_t>::min()) >> 1), 30U);
+
+    EXPECT_EQ(WTF::getLSBSet<int8_t>(42), 1U);
+    EXPECT_EQ(WTF::getLSBSet<int8_t>(3), 0U);
+    EXPECT_EQ(WTF::getLSBSet<uint8_t>(static_cast<uint8_t>(-1)), 0U);
+
+    EXPECT_EQ(WTF::getLSBSet<int64_t>(-1), 0U);
+    EXPECT_EQ(WTF::getLSBSet<int64_t>(1), 0U);
+    EXPECT_EQ(WTF::getLSBSet<int64_t>(3), 0U);
+    EXPECT_EQ(WTF::getLSBSet<uint64_t>(42), 1U);
+}
+
+TEST(WTF, getMSBSet)
+{
+    EXPECT_EQ(WTF::getMSBSet<int32_t>(1), 0U);
+    EXPECT_EQ(WTF::getMSBSet<int32_t>(42), 5U);
+    EXPECT_EQ(WTF::getMSBSet<uint32_t>(static_cast<uint32_t>(-1)), 31U);
+    EXPECT_EQ(WTF::getMSBSet<uint32_t>(static_cast<uint32_t>(std::numeric_limits<int32_t>::min()) >> 1), 30U);
+
+    EXPECT_EQ(WTF::getMSBSet<int8_t>(42), 5U);
+    EXPECT_EQ(WTF::getMSBSet<int8_t>(3), 1U);
+    EXPECT_EQ(WTF::getMSBSet<uint8_t>(static_cast<uint8_t>(-1)), 7U);
+
+    EXPECT_EQ(WTF::getMSBSet<int64_t>(-1), 63U);
+    EXPECT_EQ(WTF::getMSBSet<int64_t>(1), 0U);
+    EXPECT_EQ(WTF::getMSBSet<int64_t>(3), 1U);
+    EXPECT_EQ(WTF::getMSBSet<uint64_t>(42), 5U);
+}
+
 } // namespace TestWebKitAPI