Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (243417 => 243418)
--- trunk/Source/_javascript_Core/ChangeLog 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Source/_javascript_Core/ChangeLog 2019-03-24 01:32:06 UTC (rev 243418)
@@ -1,3 +1,25 @@
+2019-03-23 Keith Miller <[email protected]>
+
+ 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 <[email protected]>
[JSC] Shrink sizeof(RegExp)
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h (243417 => 243418)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2019-03-24 01:32:06 UTC (rev 243418)
@@ -704,7 +704,7 @@
break;
}
uint32_t value = toUInt32(*number);
- setConstant(node, jsNumber(clz32(value)));
+ setConstant(node, jsNumber(clz(value)));
break;
}
switch (node->child1().useKind()) {
Modified: trunk/Source/_javascript_Core/dfg/DFGOperations.cpp (243417 => 243418)
--- trunk/Source/_javascript_Core/dfg/DFGOperations.cpp 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Source/_javascript_Core/dfg/DFGOperations.cpp 2019-03-24 01:32:06 UTC (rev 243418)
@@ -547,7 +547,7 @@
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)
Modified: trunk/Source/_javascript_Core/runtime/JSBigInt.cpp (243417 => 243418)
--- trunk/Source/_javascript_Core/runtime/JSBigInt.cpp 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Source/_javascript_Core/runtime/JSBigInt.cpp 2019-03-24 01:32:06 UTC (rev 243418)
@@ -647,11 +647,7 @@
#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 @@
// 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 @@
// 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 @@
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 @@
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;
Modified: trunk/Source/_javascript_Core/runtime/MathObject.cpp (243417 => 243418)
--- trunk/Source/_javascript_Core/runtime/MathObject.cpp 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Source/_javascript_Core/runtime/MathObject.cpp 2019-03-24 01:32:06 UTC (rev 243418)
@@ -169,7 +169,7 @@
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)
Modified: trunk/Source/WTF/ChangeLog (243417 => 243418)
--- trunk/Source/WTF/ChangeLog 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Source/WTF/ChangeLog 2019-03-24 01:32:06 UTC (rev 243418)
@@ -1,3 +1,26 @@
+2019-03-23 Keith Miller <[email protected]>
+
+ 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 <[email protected]>
Enable ThinLTO support in Production builds
Modified: trunk/Source/WTF/wtf/MathExtras.h (243417 => 243418)
--- trunk/Source/WTF/wtf/MathExtras.h 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Source/WTF/wtf/MathExtras.h 2019-03-24 01:32:06 UTC (rev 243418)
@@ -26,6 +26,7 @@
#pragma once
#include <algorithm>
+#include <climits>
#include <cmath>
#include <float.h>
#include <limits>
@@ -301,22 +302,6 @@
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,37 +615,19 @@
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;
-inline unsigned clz64(uint64_t number)
-{
+ using UT = typename std::make_unsigned<T>::type;
+ UT uValue = value;
+
#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.
@@ -667,12 +634,12 @@
// _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 @@
#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::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;
Modified: trunk/Tools/ChangeLog (243417 => 243418)
--- trunk/Tools/ChangeLog 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Tools/ChangeLog 2019-03-24 01:32:06 UTC (rev 243418)
@@ -1,3 +1,15 @@
+2019-03-23 Keith Miller <[email protected]>
+
+ 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 <[email protected]>
[GTK][WPE] check-webkit-style doesn't complain about identifiers with underscores in files under glib, gtk or wpe dirs
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/MathExtras.cpp (243417 => 243418)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/MathExtras.cpp 2019-03-24 00:47:08 UTC (rev 243417)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/MathExtras.cpp 2019-03-24 01:32:06 UTC (rev 243418)
@@ -433,4 +433,78 @@
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
