commit d92b922fa3bcc892a679d885207e0aee915413d5
parent 65eef9a90d2d0543762d819042619bd72dfee9f0
Author: André Bargull <andre.bargull@gmail.com>
Date: Sat, 15 Nov 2025 10:15:23 +0000
Bug 1998457 - Part 1: Extend ReciprocalMulConstants for Int64 division. r=spidermonkey-reviewers,iain
Clang and GCC support the non-standard types `__int128_t` and `__uint128_t` on
x64 and arm64 (and other 64-bit architectures, but not for 32-bit architectures).
Unfortunately there are some problems with using `__[u]int128_t` when using
clang-cl, see bug 1998457, comment #10. Therefore the `[U]Int128` classes added
for `Temporal` are used.
Differential Revision: https://phabricator.services.mozilla.com/D271436
Diffstat:
3 files changed, 85 insertions(+), 18 deletions(-)
diff --git a/js/src/jit/MacroAssembler.cpp b/js/src/jit/MacroAssembler.cpp
@@ -2062,7 +2062,8 @@ void MacroAssembler::loadInt32ToStringWithBase(
// "Unsigned Division by 7" for the case when |rmc.multiplier| exceeds
// UINT32_MAX and we need to adjust the shift amount.
- auto rmc = ReciprocalMulConstants::computeUnsignedDivisionConstants(base);
+ auto rmc = ReciprocalMulConstants::computeUnsignedDivisionConstants(
+ uint32_t(base));
// We first compute |q = (M * n) >> 32), where M = rmc.multiplier.
mulHighUnsigned32(Imm32(rmc.multiplier), input, scratch1);
diff --git a/js/src/jit/ReciprocalMulConstants.cpp b/js/src/jit/ReciprocalMulConstants.cpp
@@ -8,14 +8,39 @@
#include "mozilla/Assertions.h"
+#include <limits>
+
using namespace js::jit;
-ReciprocalMulConstants ReciprocalMulConstants::computeDivisionConstants(
- uint32_t d, int maxLog) {
- MOZ_ASSERT(maxLog >= 2 && maxLog <= 32);
+template <typename UintT>
+struct TwiceLarger;
+
+template <>
+struct TwiceLarger<uint32_t> {
+ using Type = uint64_t;
+ using SignedType = int64_t;
+};
+
+template <>
+struct TwiceLarger<uint64_t> {
+ using Type = js::Uint128;
+ using SignedType = js::Int128;
+};
+
+template <typename DivConstants, typename UintT>
+static auto ComputeDivisionConstants(UintT d, int maxLog) {
+ using UintT_Twice = typename TwiceLarger<UintT>::Type;
+ using IntT_Twice = typename TwiceLarger<UintT>::SignedType;
+
+ MOZ_ASSERT(maxLog >= 2 && maxLog <= std::numeric_limits<UintT>::digits);
+
// In what follows, 0 < d < 2^maxLog and d is not a power of 2.
- MOZ_ASSERT(d < (uint64_t(1) << maxLog) && (d & (d - 1)) != 0);
+ MOZ_ASSERT(UintT_Twice(d) < (UintT_Twice(1) << maxLog) &&
+ !mozilla::IsPowerOfTwo(d));
+ // NOTE: The following explanation assumes T = uint32_t, but
+ // T = uint64_t works similar.
+ //
// Speeding up division by non power-of-2 constants is possible by
// calculating, during compilation, a value M such that high-order
// bits of M*n correspond to the result of the division of n by d.
@@ -76,19 +101,43 @@ ReciprocalMulConstants ReciprocalMulConstants::computeDivisionConstants(
// compute it as (2^p-1) % d + 1, where 2^p-1 can then be computed
// without overflow as UINT64_MAX >> (64-p).
- // We now compute the least p >= 32 with the property above...
- int32_t p = 32;
- while ((uint64_t(1) << (p - maxLog)) + (UINT64_MAX >> (64 - p)) % d + 1 < d) {
- p++;
+ static constexpr auto UINT_BITS = std::numeric_limits<UintT>::digits;
+ static constexpr auto UINT_TWICE_BITS =
+ std::numeric_limits<UintT_Twice>::digits;
+ static constexpr auto UINT_TWICE_MAX =
+ std::numeric_limits<UintT_Twice>::max();
+
+ // We now compute the least p >= UINT_BITS with the property above...
+ int32_t p = UINT_BITS;
+ while (true) {
+ auto u = (UintT_Twice(1) << (p - maxLog));
+ auto v = (UINT_TWICE_MAX >> (UINT_TWICE_BITS - p));
+ if (u + (v % UintT_Twice(d)) + UintT_Twice(1) < UintT_Twice(d)) {
+ p++;
+ } else {
+ break;
+ }
}
// ...and the corresponding M. For either the signed (L=31) or the
// unsigned (L=32) case, this value can be too large (cf. item a).
// Codegen can still multiply by M by multiplying by (M - 2^L) and
// adjusting the value afterwards, if this is the case.
- ReciprocalMulConstants rmc;
- rmc.multiplier = (UINT64_MAX >> (64 - p)) / d + 1;
- rmc.shiftAmount = p - 32;
+ DivConstants rmc;
+ rmc.multiplier = static_cast<IntT_Twice>(
+ (UINT_TWICE_MAX >> (UINT_TWICE_BITS - p)) / UintT_Twice(d) +
+ UintT_Twice(1));
+ rmc.shiftAmount = p - UINT_BITS;
return rmc;
}
+
+ReciprocalMulConstants::Div32Constants
+ReciprocalMulConstants::computeDivisionConstants(uint32_t d, int maxLog) {
+ return ComputeDivisionConstants<Div32Constants>(d, maxLog);
+}
+
+ReciprocalMulConstants::Div64Constants
+ReciprocalMulConstants::computeDivisionConstants(uint64_t d, int maxLog) {
+ return ComputeDivisionConstants<Div64Constants>(d, maxLog);
+}
diff --git a/js/src/jit/ReciprocalMulConstants.h b/js/src/jit/ReciprocalMulConstants.h
@@ -11,23 +11,40 @@
#include <stdint.h>
+#include "vm/Int128.h"
+
namespace js::jit {
struct ReciprocalMulConstants {
- int64_t multiplier;
- int32_t shiftAmount;
+ template <typename Multiplier, typename ShiftAmount>
+ struct DivConstants {
+ Multiplier multiplier;
+ ShiftAmount shiftAmount;
+ };
+
+ using Div32Constants = DivConstants<int64_t, int32_t>;
- static ReciprocalMulConstants computeSignedDivisionConstants(int32_t d) {
+ static auto computeSignedDivisionConstants(int32_t d) {
return computeDivisionConstants(mozilla::Abs(d), 31);
}
- static ReciprocalMulConstants computeUnsignedDivisionConstants(uint32_t d) {
+ static auto computeUnsignedDivisionConstants(uint32_t d) {
return computeDivisionConstants(d, 32);
}
+ using Div64Constants = DivConstants<Int128, int32_t>;
+
+ static auto computeSignedDivisionConstants(int64_t d) {
+ return computeDivisionConstants(mozilla::Abs(d), 63);
+ }
+
+ static auto computeUnsignedDivisionConstants(uint64_t d) {
+ return computeDivisionConstants(d, 64);
+ }
+
private:
- static ReciprocalMulConstants computeDivisionConstants(uint32_t d,
- int maxLog);
+ static Div32Constants computeDivisionConstants(uint32_t d, int maxLog);
+ static Div64Constants computeDivisionConstants(uint64_t d, int maxLog);
};
} // namespace js::jit
