Changeset 243418 in webkit


Ignore:
Timestamp:
Mar 23, 2019 6:32:06 PM (5 years ago)
Author:
keith_miller@apple.com
Message:

Refactor clz/ctz and fix getLSBSet.
​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):

Location:
trunk
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r243408 r243418  
     12019-03-23  Keith Miller  <keith_miller@apple.com>
     2
     3        Refactor clz/ctz and fix getLSBSet.
     4        https://bugs.webkit.org/show_bug.cgi?id=196162
     5
     6        Reviewed by Saam Barati.
     7
     8        Refactor references of clz32/64 and ctz32 to use clz and ctz,
     9        respectively.
     10
     11        * dfg/DFGAbstractInterpreterInlines.h:
     12        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
     13        * dfg/DFGOperations.cpp:
     14        * runtime/JSBigInt.cpp:
     15        (JSC::JSBigInt::digitDiv):
     16        (JSC::JSBigInt::absoluteDivWithBigIntDivisor):
     17        (JSC::JSBigInt::calculateMaximumCharactersRequired):
     18        (JSC::JSBigInt::toStringBasePowerOfTwo):
     19        (JSC::JSBigInt::compareToDouble):
     20        * runtime/MathObject.cpp:
     21        (JSC::mathProtoFuncClz32):
     22
    1232019-03-23  Yusuke Suzuki  <ysuzuki@apple.com>
    224

  • trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h

    r243268 r243418  
    705705            }
    706706            uint32_t value = toUInt32(*number);
    707             setConstant(node, jsNumber(clz32(value)));
     707            setConstant(node, jsNumber(clz(value)));
    708708            break;
    709709        }

  • trunk/Source/JavaScriptCore/dfg/DFGOperations.cpp

    r243294 r243418  
    548548    uint32_t value = op1.toUInt32(exec);
    549549    RETURN_IF_EXCEPTION(scope, 0);
    550     return clz32(value);
     550    return clz(value);
    551551}
    552552

  • trunk/Source/JavaScriptCore/runtime/JSBigInt.cpp

    r242715 r243418  
    648648    static constexpr Digit halfDigitBase = 1ull << halfDigitBits;
    649649    // Adapted from Warren, Hacker's Delight, p. 152.
    650 #if USE(JSVALUE64)
    651     unsigned s = clz64(divisor);
    652 #else
    653     unsigned s = clz32(divisor);
    654 #endif
     650    unsigned s = clz(divisor);
    655651    // If {s} is digitBits here, it causes an undefined behavior.
    656652    // But {s} is never digitBits since {divisor} is never zero here.
    … …  
    985981    // result).
    986982    Digit lastDigit = divisor->digit(n - 1);
    987     unsigned shift = sizeof(lastDigit) == 8 ? clz64(lastDigit) : clz32(lastDigit);
     983    unsigned shift = clz(lastDigit);
    988984
    989985    if (shift > 0) {
    … …  
    14461442uint64_t JSBigInt::calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign)
    14471443{
    1448     unsigned leadingZeros;
    1449     if (sizeof(lastDigit) == 8)
    1450         leadingZeros = clz64(lastDigit);
    1451     else
    1452         leadingZeros = clz32(lastDigit);
     1444    unsigned leadingZeros = clz(lastDigit);
    14531445
    14541446    size_t bitLength = length * digitBits - leadingZeros;
    … …  
    14831475    const unsigned length = x->length();
    14841476    const bool sign = x->sign();
    1485     const unsigned bitsPerChar = ctz32(radix);
     1477    const unsigned bitsPerChar = ctz(radix);
    14861478    const unsigned charMask = radix - 1;
    14871479    // Compute the length of the resulting string: divide the bit length of the
    … …  
    14891481    const Digit msd = x->digit(length - 1);
    14901482
    1491 #if USE(JSVALUE64)
    1492     const unsigned msdLeadingZeros = clz64(msd);
    1493 #else
    1494     const unsigned msdLeadingZeros = clz32(msd);
    1495 #endif
    1496    
     1483    const unsigned msdLeadingZeros = clz(msd);
     1484
    14971485    const size_t bitLength = length * digitBits - msdLeadingZeros;
    14981486    const size_t charsRequired = (bitLength + bitsPerChar - 1) / bitsPerChar + sign;
    … …  
    18771865    int xLength = x->length();
    18781866    Digit xMSD = x->digit(xLength - 1);
    1879     int msdLeadingZeros = sizeof(xMSD) == 8  ? clz64(xMSD) : clz32(xMSD);
     1867    int msdLeadingZeros = clz(xMSD);
    18801868
    18811869    int xBitLength = xLength * digitBits - msdLeadingZeros;

  • trunk/Source/JavaScriptCore/runtime/MathObject.cpp

    r225519 r243418  
    170170    uint32_t value = exec->argument(0).toUInt32(exec);
    171171    RETURN_IF_EXCEPTION(scope, encodedJSValue());
    172     return JSValue::encode(JSValue(clz32(value)));
     172    return JSValue::encode(JSValue(clz(value)));
    173173}
    174174

  • trunk/Source/WTF/ChangeLog

    r243396 r243418  
     12019-03-23  Keith Miller  <keith_miller@apple.com>
     2
     3        Refactor clz/ctz and fix getLSBSet.
     4        https://bugs.webkit.org/show_bug.cgi?id=196162
     5
     6        Reviewed by Saam Barati.
     7
     8        This patch makes clz32/64 and ctz32 generic so they work on any
     9        numeric type. Since these methods work on any type we don't need
     10        to have a separate implementation of getLSBSet, which also
     11        happened to be getMSBSet. This patch also adds getMSBSet as there
     12        may be users who want that in the future.
     13
     14        * wtf/MathExtras.h:
     15        (WTF::clz):
     16        (WTF::ctz):
     17        (WTF::getLSBSet):
     18        (WTF::getMSBSet):
     19        (getLSBSet): Deleted.
     20        (WTF::clz32): Deleted.
     21        (WTF::clz64): Deleted.
     22        (WTF::ctz32): Deleted.
     23
    1242019-03-22  Keith Rollin  <krollin@apple.com>
    225

  • trunk/Source/WTF/wtf/MathExtras.h

    r241192 r243418  
    2727
    2828#include <algorithm>
     29#include <climits>
    2930#include <cmath>
    3031#include <float.h>
    … …  
    301302    return !hasZeroOrOneBitsSet(value);
    302303}
    303 
    304 // FIXME: Some Darwin projects shamelessly include WTF headers and don't build with C++14... See: rdar://problem/45395767
    305 // Since C++11 and before don't support constexpr statements we can't mark this function constexpr.
    306 #if !defined(WTF_CPP_STD_VER) || WTF_CPP_STD_VER >= 14
    307 template <typename T> constexpr unsigned getLSBSet(T value)
    308 {
    309     typedef typename std::make_unsigned<T>::type UnsignedT;
    310     unsigned result = 0;
    311 
    312     UnsignedT unsignedValue = static_cast<UnsignedT>(value);
    313     while (unsignedValue >>= 1)
    314         ++result;
    315 
    316     return result;
    317 }
    318 #endif
    319304
    320305template<typename T> inline T divideRoundedUp(T a, T b)
    … …  
    631616}
    632617
    633 inline unsigned clz32(uint32_t number)
    634 {
     618template<typename T>
     619inline unsigned clz(T value)
     620{
     621    constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     622    constexpr unsigned bitSize64 = sizeof(uint64_t) * CHAR_BIT;
     623
     624    using UT = typename std::make_unsigned<T>::type;
     625    UT uValue = value;
     626
    635627#if COMPILER(GCC_COMPATIBLE)
    636     if (number)
    637         return __builtin_clz(number);
    638     return 32;
    639 #elif COMPILER(MSVC)
    640     // Visual Studio 2008 or upper have __lzcnt, but we can't detect Intel AVX at compile time.
    641     // So we use bit-scan-reverse operation to calculate clz.
    642     unsigned long ret = 0;
    643     if (_BitScanReverse(&ret, number))
    644         return 31 - ret;
    645     return 32;
    646 #else
    647     unsigned zeroCount = 0;
    648     for (int i = 31; i >= 0; i--) {
    649         if (!(number >> i))
    650             zeroCount++;
    651         else
    652             break;
    653     }
    654     return zeroCount;
    655 #endif
    656 }
    657 
    658 inline unsigned clz64(uint64_t number)
    659 {
    660 #if COMPILER(GCC_COMPATIBLE)
    661     if (number)
    662         return __builtin_clzll(number);
    663     return 64;
     628    if (uValue)
     629        return __builtin_clzll(uValue) - (bitSize64 - bitSize);
     630    return bitSize;
    664631#elif COMPILER(MSVC) && !CPU(X86)
    665632    // Visual Studio 2008 or upper have __lzcnt, but we can't detect Intel AVX at compile time.
    … …  
    668635    unsigned long ret = 0;
    669636    if (_BitScanReverse64(&ret, number))
    670         return 63 - ret;
    671     return 64;
     637        return bitSize - ret;
     638    return bitSize;
    672639#else
    673640    unsigned zeroCount = 0;
    674     for (int i = 63; i >= 0; i--) {
    675         if (!(number >> i))
     641    for (int i = bitSize64 - 1; i >= 0; i--) {
     642        if (!(static_cast<uint64_t>(uValue) >> i))
    676643            zeroCount++;
    677644        else
    … …  
    682649}
    683650
    684 inline unsigned ctz32(uint32_t number)
    685 {
     651template<typename T>
     652inline unsigned ctz(T value)
     653{
     654    constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     655
     656    using UT = typename std::make_unsigned<T>::type;
     657    UT uValue = value;
     658
    686659#if COMPILER(GCC_COMPATIBLE)
    687     if (number)
    688         return __builtin_ctz(number);
    689     return 32;
     660    if (uValue)
     661        return __builtin_ctzll(uValue);
     662    return bitSize;
    690663#elif COMPILER(MSVC) && !CPU(X86)
    691664    unsigned long ret = 0;
    692     if (_BitScanForward(&ret, number))
     665    if (_BitScanForward64(&ret, number))
    693666        return ret;
    694     return 32;
     667    return bitSize;
    695668#else
    696669    unsigned zeroCount = 0;
    697     for (unsigned i = 0; i < 32; i++) {
    698         if (number & 1)
     670    for (unsigned i = 0; i < bitSize; i++) {
     671        if (uValue & 1)
    699672            break;
    700673
    701674        zeroCount++;
    702         number >>= 1;
     675        uValue >>= 1;
    703676    }
    704677    return zeroCount;
    705678#endif
     679}
     680
     681template<typename T>
     682inline unsigned getLSBSet(T t)
     683{
     684    ASSERT(t);
     685    return ctz(t);
     686}
     687
     688template<typename T>
     689inline unsigned getMSBSet(T t)
     690{
     691    constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
     692    ASSERT(t);
     693    return bitSize - 1 - clz(t);
    706694}
    707695
    … …  
    713701using WTF::preciseIndexMaskShiftForSize;
    714702using WTF::shuffleVector;
    715 using WTF::clz32;
    716 using WTF::clz64;
    717 using WTF::ctz32;
     703using WTF::clz;
     704using WTF::ctz;
     705using WTF::getLSBSet;
     706using WTF::getMSBSet;

  • trunk/Tools/ChangeLog

    r243411 r243418  
     12019-03-23  Keith Miller  <keith_miller@apple.com>
     2
     3        Refactor clz/ctz and fix getLSBSet.
     4        https://bugs.webkit.org/show_bug.cgi?id=196162
     5
     6        Reviewed by Saam Barati.
     7
     8        Add tests for clz, ctz, getLSBSet, and getMSBSet.
     9
     10        * TestWebKitAPI/Tests/WTF/MathExtras.cpp:
     11        (TestWebKitAPI::TEST):
     12
    1132019-03-23  Carlos Garcia Campos  <cgarcia@igalia.com>
    214

  • trunk/Tools/TestWebKitAPI/Tests/WTF/MathExtras.cpp

    r241247 r243418  
    434434}
    435435
     436TEST(WTF, clz)
     437{
     438    EXPECT_EQ(WTF::clz<int32_t>(1), 31U);
     439    EXPECT_EQ(WTF::clz<int32_t>(42), 26U);
     440    EXPECT_EQ(WTF::clz<uint32_t>(static_cast<uint32_t>(-1)), 0U);
     441    EXPECT_EQ(WTF::clz<uint32_t>(static_cast<uint32_t>(std::numeric_limits<int32_t>::min()) >> 1), 1U);
     442    EXPECT_EQ(WTF::clz<uint32_t>(0), 32U);
     443
     444    EXPECT_EQ(WTF::clz<int8_t>(42), 2U);
     445    EXPECT_EQ(WTF::clz<int8_t>(3), 6U);
     446    EXPECT_EQ(WTF::clz<uint8_t>(static_cast<uint8_t>(-1)), 0U);
     447    EXPECT_EQ(WTF::clz<uint8_t>(0), 8U);
     448
     449    EXPECT_EQ(WTF::clz<int64_t>(-1), 0U);
     450    EXPECT_EQ(WTF::clz<int64_t>(1), 63U);
     451    EXPECT_EQ(WTF::clz<int64_t>(3), 62U);
     452    EXPECT_EQ(WTF::clz<uint64_t>(42), 58U);
     453    EXPECT_EQ(WTF::clz<uint64_t>(0), 64U);
     454}
     455
     456TEST(WTF, ctz)
     457{
     458    EXPECT_EQ(WTF::ctz<int32_t>(1), 0U);
     459    EXPECT_EQ(WTF::ctz<int32_t>(42), 1U);
     460    EXPECT_EQ(WTF::ctz<uint32_t>(static_cast<uint32_t>(-1)), 0U);
     461    EXPECT_EQ(WTF::ctz<uint32_t>(static_cast<uint32_t>(std::numeric_limits<int32_t>::min()) >> 1), 30U);
     462    EXPECT_EQ(WTF::ctz<uint32_t>(0), 32U);
     463
     464    EXPECT_EQ(WTF::ctz<int8_t>(42), 1U);
     465    EXPECT_EQ(WTF::ctz<int8_t>(3), 0U);
     466    EXPECT_EQ(WTF::ctz<uint8_t>(static_cast<uint8_t>(-1)), 0U);
     467    EXPECT_EQ(WTF::ctz<uint8_t>(0), 8U);
     468
     469    EXPECT_EQ(WTF::ctz<int64_t>(static_cast<uint32_t>(-1)), 0U);
     470    EXPECT_EQ(WTF::ctz<int64_t>(1), 0U);
     471    EXPECT_EQ(WTF::ctz<int64_t>(3), 0U);
     472    EXPECT_EQ(WTF::ctz<uint64_t>(42), 1U);
     473    EXPECT_EQ(WTF::ctz<uint64_t>(0), 64U);
     474}
     475
     476TEST(WTF, getLSBSet)
     477{
     478    EXPECT_EQ(WTF::getLSBSet<int32_t>(1), 0U);
     479    EXPECT_EQ(WTF::getLSBSet<int32_t>(42), 1U);
     480    EXPECT_EQ(WTF::getLSBSet<uint32_t>(static_cast<uint32_t>(-1)), 0U);
     481    EXPECT_EQ(WTF::getLSBSet<uint32_t>(static_cast<uint32_t>(std::numeric_limits<int32_t>::min()) >> 1), 30U);
     482
     483    EXPECT_EQ(WTF::getLSBSet<int8_t>(42), 1U);
     484    EXPECT_EQ(WTF::getLSBSet<int8_t>(3), 0U);
     485    EXPECT_EQ(WTF::getLSBSet<uint8_t>(static_cast<uint8_t>(-1)), 0U);
     486
     487    EXPECT_EQ(WTF::getLSBSet<int64_t>(-1), 0U);
     488    EXPECT_EQ(WTF::getLSBSet<int64_t>(1), 0U);
     489    EXPECT_EQ(WTF::getLSBSet<int64_t>(3), 0U);
     490    EXPECT_EQ(WTF::getLSBSet<uint64_t>(42), 1U);
     491}
     492
     493TEST(WTF, getMSBSet)
     494{
     495    EXPECT_EQ(WTF::getMSBSet<int32_t>(1), 0U);
     496    EXPECT_EQ(WTF::getMSBSet<int32_t>(42), 5U);
     497    EXPECT_EQ(WTF::getMSBSet<uint32_t>(static_cast<uint32_t>(-1)), 31U);
     498    EXPECT_EQ(WTF::getMSBSet<uint32_t>(static_cast<uint32_t>(std::numeric_limits<int32_t>::min()) >> 1), 30U);
     499
     500    EXPECT_EQ(WTF::getMSBSet<int8_t>(42), 5U);
     501    EXPECT_EQ(WTF::getMSBSet<int8_t>(3), 1U);
     502    EXPECT_EQ(WTF::getMSBSet<uint8_t>(static_cast<uint8_t>(-1)), 7U);
     503
     504    EXPECT_EQ(WTF::getMSBSet<int64_t>(-1), 63U);
     505    EXPECT_EQ(WTF::getMSBSet<int64_t>(1), 0U);
     506    EXPECT_EQ(WTF::getMSBSet<int64_t>(3), 1U);
     507    EXPECT_EQ(WTF::getMSBSet<uint64_t>(42), 5U);
     508}
     509
    436510} // namespace TestWebKitAPI
Note: See TracChangeset for help on using the changeset viewer.