Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: deb0d2fa4be6ecd15bf67bf44613db50820999d7
https://github.com/WebKit/WebKit/commit/deb0d2fa4be6ecd15bf67bf44613db50820999d7
Author: Yusuke Suzuki <[email protected]>
Date: 2026-08-02 (Sun, 02 Aug 2026)
Changed paths:
A JSTests/stress/bigint-add-sub-fixed-size.js
A JSTests/stress/bigint-square-comba.js
M Source/JavaScriptCore/runtime/JSBigInt.cpp
M Source/JavaScriptCore/runtime/JSBigInt.h
Log Message:
-----------
[JSC] Deply add / sub / mul tightening to JSBigInt
https://bugs.webkit.org/show_bug.cgi?id=320806
rdar://183823079
Reviewed by Yijia Huang.
This patch tightening JSBigInt add / sub / mul.
1. We add size-fixed streamlined implementations to add and sub as the
same to mul.
2. Removed unnecessary absoluteCompare for sub. Before doing sub, we
already did absoluteCompare.
3. Multiply streamlined implementations should have square optimization.
4. DigitColumnAccumulator now picks where a column's carry lives per
consumer. Keeping it in the condition flags is the shortest sequence, but
there is only one flag register, so in the fully unrolled Comba kernels,
where two mac chains end up interleaved, the compiler spilled it with
mrs / msr NZCV: 6 times in multiplyCombaFixed<4> and 14 times in <8>.
CombaAccumulator now materializes the carry as a value with
__builtin_addcll, which removes those spills and 6 instructions per
4-digit multiply. The Barrett / folding helpers keep the flag form on
purpose: switching them over too pushes 8 flag spills into cachedMod,
which is three times hotter, and cancels the win.
In squire multiplication, Comba multiplication can leverage the fact
that the same value multiplication is happening. a[i] * b[j] and
a[j] * b[i] will be the same since a[i] == b[i] in squire case.
a0 a1 a2 a3
a0 [0,0] (0,1) (0,2) (0,3)
a1 (1,0) [1,1] (1,2) (1,3) [i,i] diagonal - counted once
a2 (2,0) (2,1) [2,2] (2,3) (i,j) off-diagonal - equal in pairs
a3 (3,0) (3,1) (3,2) [3,3]
So, half of multilication is not necessary. So then in the Comba multiplication,
a6 a5 a4 a3 a2 a1 a0
x a6 a5 a4 a3 a2 a1 a0
--------------------------------------
a6a0 a5a0 a4a0 a3a0 a2a0 a1a0 a0a0
a6a1 a5a1 a4a1 a3a1 a2a1 a1a1 a0a1
a6a2 a5a2 a4a2 a3a2 a2a2 a1a2 a0a2
a6a3 a5a3 a4a3 a3a3 a2a3 a1a3 a0a3
a6a4 a5a4 a4a4 a3a4 a2a4 a1a4 a0a4
a6a5 a5a5 a4a5 a3a5 a2a5 a1a5 a0a5
a6a6 a5a6 a4a6 a3a6 a2a6 a1a6 a0a6
-----------------------------------------------------------------
Now we can find that, in each column (that's how Comba multiplication computes),
basically you only need to compute the half way. And you can double the
result and that's what you need. Like, a6a0 == a0a6, so only diagonal
case, a3a3, needs to be additionally done. But other ones should just
use a6a0 * 2, and then, you do not need to compute a0a6.
Tests: JSTests/stress/bigint-add-sub-fixed-size.js
JSTests/stress/bigint-square-comba.js
* JSTests/stress/bigint-add-sub-fixed-size.js: Added.
(shouldBe):
(nextDigit):
(fromDigits):
(randomOfLength):
(check):
* JSTests/stress/bigint-square-comba.js: Added.
(shouldBe):
(checkSquare):
(nextDigit):
(fromDigits):
(a.a.2n.a.copy):
* Source/JavaScriptCore/runtime/JSBigInt.cpp:
(JSC::DigitColumnAccumulator::mac):
(JSC::DigitColumnAccumulator::macDoubled):
(JSC::DigitColumnAccumulator::addCarrying):
(JSC::CombaAccumulator::computeSquareColumn):
(JSC::CombaAccumulator::squarePass):
(JSC::JSBigInt::squareCombaFixed):
(JSC::JSBigInt::multiplySpecialLow):
(JSC::JSBigInt::multiplySpecialHigh):
(JSC::JSBigInt::multiplyComba):
(JSC::multiplySpecialColumn):
(JSC::JSBigInt::multiplySpecialHighFixed):
(JSC::JSBigInt::multiplySpecialLowFixed):
(JSC::JSBigInt::multiplyDigitsInto):
(JSC::JSBigInt::multiplyImpl):
(JSC::JSBigInt::addDigits):
(JSC::JSBigInt::multiplyDigits):
(JSC::JSBigInt::addImpl):
(JSC::JSBigInt::subImpl):
(JSC::JSBigInt::addSchoolbookFixed):
(JSC::JSBigInt::addDigitsInto):
(JSC::JSBigInt::absoluteAdd):
(JSC::JSBigInt::subSchoolbookFixed):
(JSC::JSBigInt::subDigitsInto):
(JSC::JSBigInt::absoluteSub):
* Source/JavaScriptCore/runtime/JSBigInt.h:
Canonical link: https://commits.webkit.org/318413@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
