Closed Bug 1679750 Opened 4 years ago Closed 4 years 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)

(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
(deleted), text/x-phabricator-request
Details
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

Depends on D98158

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

Depends on D98166

Depends on D98167

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

Depends on D98178

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: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → 86 Branch
Regressions: 1685662
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: