commit 34de8212a70815d504d03d80ef1b411e0bb9f881
parent 1e220e42dc45ebb2161bba9fd8fda308e64ee3e4
Author: André Bargull <andre.bargull@gmail.com>
Date: Mon, 10 Nov 2025 15:13:42 +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).
Alternatively the `[U]Int128` classes from "js/src/builtin/temporal/Int128.h" can
be used.
Differential Revision: https://phabricator.services.mozilla.com/D271436
Diffstat:
3 files changed, 86 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,37 @@
#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;
+};
+
+#if defined(__SIZEOF_INT128__)
+template <>
+struct TwiceLarger<uint64_t> {
+ using Type = __uint128_t;
+};
+#endif
+
+template <typename DivConstants, typename UintT>
+static auto ComputeDivisionConstants(UintT d, int maxLog) {
+ using UintT_Twice = typename TwiceLarger<UintT>::Type;
+
+ 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(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 +99,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 % d) + 1 < 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 = (UINT_TWICE_MAX >> (UINT_TWICE_BITS - p)) / d + 1;
+ rmc.shiftAmount = p - UINT_BITS;
return rmc;
}
+
+ReciprocalMulConstants::Div32Constants
+ReciprocalMulConstants::computeDivisionConstants(uint32_t d, int maxLog) {
+ return ComputeDivisionConstants<Div32Constants>(d, maxLog);
+}
+
+#if defined(__SIZEOF_INT128__)
+ReciprocalMulConstants::Div64Constants
+ReciprocalMulConstants::computeDivisionConstants(uint64_t d, int maxLog) {
+ return ComputeDivisionConstants<Div64Constants>(d, maxLog);
+}
+#endif
diff --git a/js/src/jit/ReciprocalMulConstants.h b/js/src/jit/ReciprocalMulConstants.h
@@ -14,20 +14,40 @@
namespace js::jit {
struct ReciprocalMulConstants {
- int64_t multiplier;
- int32_t shiftAmount;
+ template <typename Multiplier, typename ShiftAmount>
+ struct DivConstants {
+ Multiplier multiplier;
+ ShiftAmount shiftAmount;
+ };
- static ReciprocalMulConstants computeSignedDivisionConstants(int32_t d) {
+ using Div32Constants = DivConstants<int64_t, int32_t>;
+
+ 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);
}
+#if defined(__SIZEOF_INT128__)
+ using Div64Constants = DivConstants<__int128_t, int32_t>;
+
+ static auto computeSignedDivisionConstants(int64_t d) {
+ return computeDivisionConstants(mozilla::Abs(d), 63);
+ }
+
+ static auto computeUnsignedDivisionConstants(uint64_t d) {
+ return computeDivisionConstants(d, 64);
+ }
+#endif
+
private:
- static ReciprocalMulConstants computeDivisionConstants(uint32_t d,
- int maxLog);
+ static Div32Constants computeDivisionConstants(uint32_t d, int maxLog);
+
+#if defined(__SIZEOF_INT128__)
+ static Div64Constants computeDivisionConstants(uint64_t d, int maxLog);
+#endif
};
} // namespace js::jit
