1679750 - Warp: Transpile BigInt operations.

Status: RESOLVED FIXED

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

Comment 1

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 1: Add MacroAssembler::xor32(Address, Register). r=jandem!

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

The next part will call this method.

Comment 2

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 2: Transpile BigInt compared to BigInt. r=jandem!

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

Comment 3

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 3: Reverse comparison operator for heterogenous BigInt comparisons in CacheIR. r=jandem!

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

Comment 4

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 4: Move BigInt with Int32 comparison to the MacroAssembler. r=jandem!

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

Depends on D98157

Comment 5

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 5: Transpile BigInt compared to Int32. r=jandem!

Depends on D98158

Comment 6

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 6: Transpile BigInt compared to Number. r=jandem!

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

Comment 7

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 7: Transpile BigInt compared to String. r=jandem!

Uses a VM call similar to the CacheIR implementation.

Depends on D98160

Comment 8

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 8: Add MacroAssembler::branchIfBigIntIs{Non}Zero. r=jandem!

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

Depends on D98161

Comment 9

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 9: Add MacroAssembler::branchAddPtr. r=jandem!

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

Depends on D98162

Comment 10

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 10: Transpile Bigint addition. r=jandem!

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

Comment 11

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 11: Add MacroAssembler::branchSubPtr. r=jandem!

The next part will call this method.

Depends on D98164

Comment 12

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 12: Transpile BigInt subtraction. r=jandem!

Transpile BigInt subtraction similar to BigInt addition from part 10.

Depends on D98165

Comment 13

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 13: Add MacroAssembler::branchMulPtr. r=jandem!

Depends on D98166

Comment 14

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 14: Transpile BigInt multiplication. r=jandem!

Depends on D98167

Comment 15

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 15: Transpile BigInt increment and decrement. r=jandem!

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

Comment 16

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 16: Add MacroAssembler::xor32(Imm32, Address). r=jandem!

The next part will call this method.

Depends on D98169

Comment 17

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 17: Transpile BigInt negation. r=jandem!

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

Comment 18

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 18: Transpile BigInt binary bitwise operations. r=jandem!

Depends on D98171

Comment 19

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 19: Add MacroAssembler::notPtr(Register). r=jandem!

The next part will call this method.

Depends on D98172

Comment 20

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 20: Transpile BigInt bitwise not. r=jandem!

The implementation follows the BigInt C++ code.

Depends on D98173

Comment 21

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 21: Add MacroAssembler::{l,r}shiftPtr(Register, Register). r=jandem!

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

Depends on D98174

Comment 22

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 22: Transpile BigInt shift operations. r=jandem!

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

Depends on D98175

Comment 23

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 23: Transpile BigInt division operations. r=jandem!

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

Comment 24

[André Bargull [:anba]]

Attachment: Bug 1679750 - Part 24: Transpile BigInt exponentiation. r=jandem!

Depends on D98178

Comment 25

[Pulsebot]

Pushed by [e-mail]:
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

Comment 26

[Noemi Erli[:noemi_erli]]

Backed out 24 changesets (Bug 1679750) for causing build bustages in CodeGenerator.cpp CLOSED TREE

Push with failures: https://treeherder.mozilla.org/jobs?repo=autoland&group_state=expanded&selectedTaskRun=F_RmKQoNRmKP5Oxh7rffXw.0&resultStatus=testfailed%2Cbusted%2Cexception&revision=a5c82fcf8385aa1dfe648f139c9f01591d4c3768

Failure log: https://treeherder.mozilla.org/logviewer?job_id=325160508&repo=autoland&lineNumber=3655

Backout: https://hg.mozilla.org/integration/autoland/rev/e10b35152bae741154eed0e098a8a50783001580

Comment 27

[Pulsebot]

Pushed by [e-mail]:
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

Comment 28

[Cosmin Sabou [:CosminS]]

https://hg.mozilla.org/mozilla-central/rev/a2193bebbaf3
https://hg.mozilla.org/mozilla-central/rev/74f4e8e94b07
https://hg.mozilla.org/mozilla-central/rev/a5fc93c132b9
https://hg.mozilla.org/mozilla-central/rev/db4fc233784d
https://hg.mozilla.org/mozilla-central/rev/751f898e3a42
https://hg.mozilla.org/mozilla-central/rev/956d262dbb5e
https://hg.mozilla.org/mozilla-central/rev/0c0e75cffd17
https://hg.mozilla.org/mozilla-central/rev/2ecab5047f08
https://hg.mozilla.org/mozilla-central/rev/7283ed22071c
https://hg.mozilla.org/mozilla-central/rev/41aaa79b1af2
https://hg.mozilla.org/mozilla-central/rev/2efc0c5f4e83
https://hg.mozilla.org/mozilla-central/rev/82ef5872f7db
https://hg.mozilla.org/mozilla-central/rev/84a4422d3959
https://hg.mozilla.org/mozilla-central/rev/b9a80dc531fe
https://hg.mozilla.org/mozilla-central/rev/0516b5a77d4f
https://hg.mozilla.org/mozilla-central/rev/a3eb45b67a5c
https://hg.mozilla.org/mozilla-central/rev/a089c0974d10
https://hg.mozilla.org/mozilla-central/rev/192a24886dd3
https://hg.mozilla.org/mozilla-central/rev/3e1ba8d59f6d
https://hg.mozilla.org/mozilla-central/rev/792e8850bba8
https://hg.mozilla.org/mozilla-central/rev/b8ecaacf7d5a
https://hg.mozilla.org/mozilla-central/rev/ea4aa0fe4e76
https://hg.mozilla.org/mozilla-central/rev/c00bf1a5a25a
https://hg.mozilla.org/mozilla-central/rev/916fe4f3e31a