Closed Bug 1679750 Opened 5 months ago Closed 5 months ago

Warp: Transpile BigInt operations.

Categories

(Core :: JavaScript Engine: JIT, enhancement, P3)

enhancement

Tracking

()

RESOLVED FIXED
86 Branch
Tracking Status
firefox86 --- fixed

People

(Reporter: anba, Assigned: anba)

References

(Blocks 1 open bug)

Details

Attachments

(24 files)

47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
No description provided.

Add MacroAssembler::xor32(Address, Register) based on the already existing
MacroAssembler::and32(Address, Register) method.

The next part will call this method.

Inline BigInt comparison by looping over all digits, starting with the left-most one
until the first difference was found.

A later patch in this series will rename the existing
MacroAssembler::branchIfNegativeBigInt() method to match the newly added
branchIfBigIntIsNonNegative() method.

Depends on D98155

Reverse the comparison operator for "{Int32,Number,String} <comp> BigInt" when
emitting the CacheIR ops, so that we can remove Compare{Int32,Number,String}BigIntResult
in favour of using only CompareBigInt{Int32,Number,String}Result.

This change allows to remove near duplicated code and helps to avoid writing more
duplicated code in the next parts.

Depends on D98156

Also rename branchIfNegativeBigInt to branchIfBigIntIsNegative to match
the other branch methods from part 2 and part 8.

Depends on D98157

Uses an ABI call to perform the actual comparison, because
BigInt::compare(BigInt*,double) is too much code to easily implement with
inline assembly.

Depends on D98159

Uses a VM call similar to the CacheIR implementation.

Depends on D98160

Add branchIfBigIntIs{Non}Zero() in preparation for the next parts. Also
updates existing code to use the new methods.

Depends on D98161

Add MacroAssembler::branchAddPtr() in preparation for the next part.

Depends on D98162

The inline assembly code has an optimised path when both operands and the result
can be loaded in pointer-sized registers. Restricting the optimised path to
pointer-sized values instead of Int64 makes it easier to implement this code and
on x86 Int64 values can't be used anyway, because there aren't enough registers
available.

BigInt addition can throw when the resulting BigInt exceeds the maximum BigInt
digit length. Nonetheless MBigIntAdd isn't marked as a guard instruction,
because (1) this matches the behaviour of MConcat and (2) BigInt benchmarks
are available which rely on engines optimising out unused BigInt operations and
other engines already do just that.

Similar to number addition, MBigIntAdd also provides recover support for DCE.
When a BigInt addition is recovered, we throw an "out of memory" error instead
of a RangeError when the result is too large. The "recover-bigint.js" test file
covers this case.

The BigIntArithPolicy type policy matches the existing ArithPolicy. Both
type policies may no longer be necessary for Warp, but this can be cleaned up
later.

The "bigint-add.js" test file was generated. It covers additions near the usual
limits (0, 2^31, 2^32, 2^63, 2^64).

Depends on D98163

The next part will call this method.

Depends on D98164

Transpile BigInt subtraction similar to BigInt addition from part 10.

Depends on D98165

Increment and decrement operations are for now implemented through separate
MBigIntIncrement and MBigIntDecrement MIR nodes. If we ever add cached
BigInt constants, we could think about implementing these operations through
MBigInt{Add,Sub} similar to how their number counterparts are implemented.

Depends on D98168

The next part will call this method.

Depends on D98169

BigInt negation doesn't have any pointer-sized restrictions, but instead any
BigInt with inline digits can be handled in assembly code.

Depends on D98170

The next part will call this method.

Depends on D98172

The implementation follows the BigInt C++ code.

Depends on D98173

Add additional MacroAssembler shift methods in preparation for the next part.

Depends on D98174

The inlined shift operations are based on the BigInt C++ code.

Depends on D98175

BigInt division throws when the divisor is zero, so we can't optimise out
this operation, unless we can prove the divisor is non-zero.

Depends on D98177

Severity: -- → N/A
Priority: -- → P3
Pushed by abutkovits@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/7903c8a72850
Part 1: Add MacroAssembler::xor32(Address, Register). r=jandem
https://hg.mozilla.org/integration/autoland/rev/870397398a5f
Part 2: Transpile BigInt compared to BigInt. r=jandem
https://hg.mozilla.org/integration/autoland/rev/238e0776533c
Part 3: Reverse comparison operator for heterogenous BigInt comparisons in CacheIR. r=jandem
https://hg.mozilla.org/integration/autoland/rev/3c4555e5d59a
Part 4: Move BigInt with Int32 comparison to the MacroAssembler. r=jandem
https://hg.mozilla.org/integration/autoland/rev/67846b5fb533
Part 5: Transpile BigInt compared to Int32. r=jandem
https://hg.mozilla.org/integration/autoland/rev/822eea13c8c7
Part 6: Transpile BigInt compared to Number. r=jandem
https://hg.mozilla.org/integration/autoland/rev/e804e1f0b4a4
Part 7: Transpile BigInt compared to String. r=jandem
https://hg.mozilla.org/integration/autoland/rev/0cfd75ab21b8
Part 8: Add MacroAssembler::branchIfBigIntIs{Non}Zero. r=jandem
https://hg.mozilla.org/integration/autoland/rev/80f78c980c07
Part 9: Add MacroAssembler::branchAddPtr. r=jandem
https://hg.mozilla.org/integration/autoland/rev/8396e48cb09e
Part 10: Transpile Bigint addition. r=jandem
https://hg.mozilla.org/integration/autoland/rev/99f82d64de93
Part 11: Add MacroAssembler::branchSubPtr. r=jandem
https://hg.mozilla.org/integration/autoland/rev/234cc79df8d1
Part 12: Transpile BigInt subtraction. r=jandem
https://hg.mozilla.org/integration/autoland/rev/7f21f761a9d2
Part 13: Add MacroAssembler::branchMulPtr. r=jandem
https://hg.mozilla.org/integration/autoland/rev/723a000ec3ef
Part 14: Transpile BigInt multiplication. r=jandem
https://hg.mozilla.org/integration/autoland/rev/9b9acb6917bd
Part 15: Transpile BigInt increment and decrement. r=jandem
https://hg.mozilla.org/integration/autoland/rev/ff683dfe2357
Part 16: Add MacroAssembler::xor32(Imm32, Address). r=jandem
https://hg.mozilla.org/integration/autoland/rev/1e0b72830e95
Part 17: Transpile BigInt negation. r=jandem
https://hg.mozilla.org/integration/autoland/rev/542359a41cf9
Part 18: Transpile BigInt binary bitwise operations. r=jandem
https://hg.mozilla.org/integration/autoland/rev/c6840af4b13e
Part 19: Add MacroAssembler::notPtr(Register). r=jandem
https://hg.mozilla.org/integration/autoland/rev/b6c0885e4483
Part 20: Transpile BigInt bitwise not. r=jandem
https://hg.mozilla.org/integration/autoland/rev/95274172bd74
Part 21: Add MacroAssembler::{l,r}shiftPtr(Register, Register). r=jandem
https://hg.mozilla.org/integration/autoland/rev/5fe8bf1d376d
Part 22: Transpile BigInt shift operations. r=jandem
https://hg.mozilla.org/integration/autoland/rev/464d53cb1b5d
Part 23: Transpile BigInt division operations. r=jandem
https://hg.mozilla.org/integration/autoland/rev/a5c82fcf8385
Part 24: Transpile BigInt exponentiation. r=jandem
Flags: needinfo?(andrebargull)
Pushed by smolnar@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/a2193bebbaf3
Part 1: Add MacroAssembler::xor32(Address, Register). r=jandem
https://hg.mozilla.org/integration/autoland/rev/74f4e8e94b07
Part 2: Transpile BigInt compared to BigInt. r=jandem
https://hg.mozilla.org/integration/autoland/rev/a5fc93c132b9
Part 3: Reverse comparison operator for heterogenous BigInt comparisons in CacheIR. r=jandem
https://hg.mozilla.org/integration/autoland/rev/db4fc233784d
Part 4: Move BigInt with Int32 comparison to the MacroAssembler. r=jandem
https://hg.mozilla.org/integration/autoland/rev/751f898e3a42
Part 5: Transpile BigInt compared to Int32. r=jandem
https://hg.mozilla.org/integration/autoland/rev/956d262dbb5e
Part 6: Transpile BigInt compared to Number. r=jandem
https://hg.mozilla.org/integration/autoland/rev/0c0e75cffd17
Part 7: Transpile BigInt compared to String. r=jandem
https://hg.mozilla.org/integration/autoland/rev/2ecab5047f08
Part 8: Add MacroAssembler::branchIfBigIntIs{Non}Zero. r=jandem
https://hg.mozilla.org/integration/autoland/rev/7283ed22071c
Part 9: Add MacroAssembler::branchAddPtr. r=jandem
https://hg.mozilla.org/integration/autoland/rev/41aaa79b1af2
Part 10: Transpile Bigint addition. r=jandem
https://hg.mozilla.org/integration/autoland/rev/2efc0c5f4e83
Part 11: Add MacroAssembler::branchSubPtr. r=jandem
https://hg.mozilla.org/integration/autoland/rev/82ef5872f7db
Part 12: Transpile BigInt subtraction. r=jandem
https://hg.mozilla.org/integration/autoland/rev/84a4422d3959
Part 13: Add MacroAssembler::branchMulPtr. r=jandem
https://hg.mozilla.org/integration/autoland/rev/b9a80dc531fe
Part 14: Transpile BigInt multiplication. r=jandem
https://hg.mozilla.org/integration/autoland/rev/0516b5a77d4f
Part 15: Transpile BigInt increment and decrement. r=jandem
https://hg.mozilla.org/integration/autoland/rev/a3eb45b67a5c
Part 16: Add MacroAssembler::xor32(Imm32, Address). r=jandem
https://hg.mozilla.org/integration/autoland/rev/a089c0974d10
Part 17: Transpile BigInt negation. r=jandem
https://hg.mozilla.org/integration/autoland/rev/192a24886dd3
Part 18: Transpile BigInt binary bitwise operations. r=jandem
https://hg.mozilla.org/integration/autoland/rev/3e1ba8d59f6d
Part 19: Add MacroAssembler::notPtr(Register). r=jandem
https://hg.mozilla.org/integration/autoland/rev/792e8850bba8
Part 20: Transpile BigInt bitwise not. r=jandem
https://hg.mozilla.org/integration/autoland/rev/b8ecaacf7d5a
Part 21: Add MacroAssembler::{l,r}shiftPtr(Register, Register). r=jandem
https://hg.mozilla.org/integration/autoland/rev/ea4aa0fe4e76
Part 22: Transpile BigInt shift operations. r=jandem
https://hg.mozilla.org/integration/autoland/rev/c00bf1a5a25a
Part 23: Transpile BigInt division operations. r=jandem
https://hg.mozilla.org/integration/autoland/rev/916fe4f3e31a
Part 24: Transpile BigInt exponentiation. r=jandem
Status: ASSIGNED → RESOLVED
Closed: 5 months ago
Resolution: --- → FIXED
Target Milestone: --- → 86 Branch
Regressions: 1685662
Duplicate of this bug: 1523566
You need to log in before you can comment on or make changes to this bug.