Closed Bug 1471134 Opened Last year Closed Last year

BigInt support for basic arithmetic operations

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla63
Tracking Status
firefox63 --- fixed

People

(Reporter: terpri, Assigned: terpri)

References

Details

Attachments

(5 files, 10 obsolete files)

5.81 KB, patch
terpri
: review+
Details | Diff | Splinter Review
5.82 KB, patch
terpri
: review+
Details | Diff | Splinter Review
6.87 KB, patch
terpri
: review+
Details | Diff | Splinter Review
8.41 KB, patch
terpri
: review+
Details | Diff | Splinter Review
5.64 KB, patch
terpri
: review+
Details | Diff | Splinter Review
Now that BigInt is available as a data type, the interpreter should allow BigInt operands to be used in arithmetic expressions.
Attachment #8987750 - Flags: review?(jwalden+bmo)
Follow the example of AddOperation, which uses MutableHandleValue for
arguments that will be passed to ToPrimitive. This allows arguments to
be converted using ToNumeric instead of ToNumber.
Attachment #8987752 - Flags: review?(jdemooij)
They replace calls to math_pow_handle that should allow generic
arithmetic instead of only handling Numbers.
Attachment #8987753 - Flags: review?(jdemooij)
Operands are converted to primitive values using ToNumeric, which can
result in either BigInt or Number values. If any operand is a BigInt,
TryBigIntBinaryOperation or TryBigIntUnaryOperation is used to check
operand types and call the corresponding BigInt method. Otherwise, the
existing behavior for Number operands is used.
Attachment #8987754 - Flags: review?(jdemooij)
Comment on attachment 8987751 [details] [diff] [review]
Part 2: Add numeric type dispatch functions for use in the interpreter.

Not sure how I feel about the use of function pointers here instead of templates or something. OTOH we only call this if one of the operands is a BigInt so it probably shouldn't affect non-BigInt-perf.

Requesting feedback from our resident C++ expert.
Attachment #8987751 - Flags: feedback?(jwalden+bmo)
Comment on attachment 8987752 [details] [diff] [review]
Part 3: Make arithmetic operand arguments mutable.

Review of attachment 8987752 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/BaselineIC.cpp
@@ +4557,5 @@
>          break;
>        }
> +      case JSOP_NEG: {
> +        RootedValue valCopy(cx, val);
> +        if (!NegOperation(cx, &valCopy, res))

This is not valid because the code after this tries to attach an IC stub based on |val|'s type... There might be similar issues with the other operators.

(One potential but non-trivial fix is to attach the IC stub before we get here..)
Attachment #8987752 - Flags: review?(jdemooij)
Oh embarrassing, I was reading the patch wrong. I'll take another look.
Comment on attachment 8987752 [details] [diff] [review]
Part 3: Make arithmetic operand arguments mutable.

Review of attachment 8987752 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/BaselineIC.cpp
@@ +4556,5 @@
>          res.setInt32(result);
>          break;
>        }
> +      case JSOP_NEG: {
> +        RootedValue valCopy(cx, val);

Please add a comment here explaining we copy val because we need the original value below.

::: js/src/jit/IonIC.cpp
@@ +520,5 @@
>          res.setInt32(result);
>          break;
>        }
> +      case JSOP_NEG: {
> +        RootedValue valCopy(cx, val);

Same here.
Attachment #8987752 - Flags: review+
Comment on attachment 8987753 [details] [diff] [review]
Part 4: Add PowValues/PowOperation for exponentiation.

Review of attachment 8987753 [details] [diff] [review]:
-----------------------------------------------------------------

There are more calls to math_pow_handle, for instance from JIT code (jit/CodeGenerator.cpp). Should we convert these to PowValues too?
Attachment #8987753 - Flags: review?(jdemooij) → review+
Comment on attachment 8987754 [details] [diff] [review]
Part 5: Support BigInt operands for basic arithmetic operators.

Review of attachment 8987754 [details] [diff] [review]:
-----------------------------------------------------------------

Makes sense, but I'm curious about the Math.pow() question below.

::: js/src/vm/Interpreter.cpp
@@ +1580,5 @@
>          return false;
> +
> +#ifdef ENABLE_BIGINT
> +    if (lhs.isBigInt() || rhs.isBigInt())
> +        return TryBigIntBinaryOperation(cx, BigInt::sub, lhs, rhs, res);

s/sub/mul/, same for div/mod/pow below

@@ +1633,5 @@
> +        return false;
> +
> +#ifdef ENABLE_BIGINT
> +    if (lhs.isBigInt() || rhs.isBigInt())
> +        return TryBigIntBinaryOperation(cx, BigInt::sub, lhs, rhs, res);

What will happen to math_pow_handle/Math.pow? Wondering if this should live in math_pow_handle instead.
Attachment #8987754 - Flags: review?(jdemooij)
Comment on attachment 8987751 [details] [diff] [review]
Part 2: Add numeric type dispatch functions for use in the interpreter.

Review of attachment 8987751 [details] [diff] [review]:
-----------------------------------------------------------------

I'm very sorry for the delay. Some suggestions below, what do you think? If you can post updated patches I'll review quickly.

::: js/src/vm/Interpreter-inl.h
@@ +33,5 @@
> +TryBigIntBinaryOperation(JSContext* cx, BigIntBinaryOperation op,
> +                         HandleValue lhs, HandleValue rhs,
> +                         MutableHandleValue res)
> +{
> +    if (lhs.isBigInt() && rhs.isBigInt()) {

How do you feel about adding these as static methods to BigInt:

  static bool BigInt::add(JSContext* cx, HandleValue lhs, HandleValue rhs, MutableHandleValue rhs);

Where you can then do:

static bool
BigInt::add(JSContext* cx, HandleValue lhs, HandleValue rhs, MutableHandleValue rhs)
{
    ... This helper method will also assert lhs.isBigInt() || rhs.isBigInt() ...
    if (!somethingThatThrowsIfLhsAndRhsAreNotBothBigInt(cx, lhs, rhs))
        return false;
    
    RootedBigInt lhsBigInt(cx, lhs.toBigInt());
    RootedBigInt rhsBigInt(cx, rhs.toBigInt());
    BigInt* resBigInt = add(cx, lhsBigInt, rhsBigInt);
        return false;
    res.setBigInt(resBigInt);
    return true;
}

That way the semantics are defined in the BigInt code and we also don't need the function pointer or template indirection so it might be faster too (there's a little duplication of a few lines of boilerplate but that's fine).

@@ +52,5 @@
> +static inline bool
> +TryBigIntUnaryOperation(JSContext* cx, BigIntUnaryOperation op, HandleValue operand,
> +                        MutableHandleValue res)
> +{
> +    if (operand.isBigInt()) {

This could be MOZ_ASSERT(operand.isBigInt()) I think? Could probably be inlined into the callers then (or do what I described above).
Attachment #8987751 - Flags: review?(jdemooij)
Attachment #8987751 - Flags: feedback?(jwalden+bmo)
Comment on attachment 8987750 [details] [diff] [review]
Part 1: Define methods for basic BigInt arithmetic.

Review of attachment 8987750 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/vm/BigIntType.cpp
@@ +256,5 @@
> +    // Steps 2-3.
> +    BigInt* z = create(cx);
> +    if (!z)
> +        return nullptr;
> +    mpz_pow_ui(z->num_, x->num_, mpz_get_ui(y->num_));

This doesn't look like it's doing x**y at all, but rather something like x**(y mod 2**32).  Which *practically* is the desirable thing because if it were that large, you'd OOM for sure.

Except, wait, it's not.  Wouldn't this mean 2n**(2n**32n) would evaluate to 1, not report OOM or some other failure condition?
Attachment #8987750 - Flags: review?(jwalden+bmo) → feedback+
And, yeah, I think I kind of favor a bunch of static functions on BigInt for doing the various arithmetic things.
(In reply to Jan de Mooij [:jandem] from comment #12)
> @@ +1633,5 @@
> > +        return false;
> > +
> > +#ifdef ENABLE_BIGINT
> > +    if (lhs.isBigInt() || rhs.isBigInt())
> > +        return TryBigIntBinaryOperation(cx, BigInt::sub, lhs, rhs, res);
> 
> What will happen to math_pow_handle/Math.pow? Wondering if this should live
> in math_pow_handle instead.

Math.pow doesn't allow BigInt arguments in the current proposal, so pow functions using ToNumber and ToNumeric are both needed for the time being. Other than math_pow which needs math_pow_handle's error reporting, there are only a few uses of math_pow_handle to consider:

 - The LPowV LIR instruction: it should eventually handle BigInt operands, so it probably makes sense to use the ToNumeric variant
 - Recovery instructions for MPow/MPowHalf: I didn't change these because they're only generated for Number operands, although using ToNumeric would work too
 - PowOperation: could call ecmaPow directly for Number operands
(In reply to Jeff Walden [:Waldo] from comment #14)
> Comment on attachment 8987750 [details] [diff] [review]
> Part 1: Define methods for basic BigInt arithmetic.
> 
> Review of attachment 8987750 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/vm/BigIntType.cpp
> @@ +256,5 @@
> > +    // Steps 2-3.
> > +    BigInt* z = create(cx);
> > +    if (!z)
> > +        return nullptr;
> > +    mpz_pow_ui(z->num_, x->num_, mpz_get_ui(y->num_));
> 
> This doesn't look like it's doing x**y at all, but rather something like
> x**(y mod 2**32).  Which *practically* is the desirable thing because if it
> were that large, you'd OOM for sure.
> 
> Except, wait, it's not.  Wouldn't this mean 2n**(2n**32n) would evaluate to
> 1, not report OOM or some other failure condition?

Yes, this is wrong for large exponents. The revised version checks that the exponent fits in an unsigned long, as required by gmp, and throws a RangeError if it doesn't. I don't think that overflow behavior is spelled out in the spec, but it seems reasonable and matches V8's behavior. It can still OOM when the exponentiation is performed, but won't return mathematically incorrect results.
Changes: add a BIGINT_TOO_LARGE RangeError. Throw it from BigInt::pow if
the exponent can't fit in an unsigned long, instead of silently wrapping
around on overflow. (It's worth noting that the GMP operations used here
can still MOZ_CRASH on allocation failures; this only prevents incorrect
results from being returned.)
Attachment #8989629 - Flags: review?(jdemooij)
Attachment #8987750 - Attachment is obsolete: true
Attachment #8987751 - Attachment is obsolete: true
Attachment #8987752 - Attachment is obsolete: true
Attachment #8987753 - Attachment is obsolete: true
Attachment #8987754 - Attachment is obsolete: true
These replace TryBigIntBinaryFunction/TryBigIntUnaryFunction from the
old patch, following the suggested template. Unlike the old functions,
these methods require at least one BigInt operand.
Attachment #8989641 - Flags: review?(jdemooij)
Carry forward r+ with comments on value-copying.
Attachment #8989642 - Flags: review+
One minor change: call PowValues instead of math_pow_handle from LPowV
(for unspecialized MPow), since it will probably allow BigInt values in
the future.
Attachment #8989643 - Flags: review?(jdemooij)
Operands are converted to primitive values using ToNumeric, which can
result in either BigInt or Number values. If any operand is a BigInt,
the corresponding BigInt method is called; otherwise, the existing
behavior for Numbers is used.
Attachment #8989644 - Flags: review?(jdemooij)
Comment on attachment 8989629 [details] [diff] [review]
Part 1: Define methods for basic BigInt arithmetic.

Review of attachment 8989629 [details] [diff] [review]:
-----------------------------------------------------------------

Forwarding this one to Waldo as he commented on the previous version.
Attachment #8989629 - Flags: review?(jdemooij) → review?(jwalden+bmo)
Comment on attachment 8989641 [details] [diff] [review]
Part 2: Add BigInt arithmetic methods that accept Value arguments.

Review of attachment 8989641 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks!
Attachment #8989641 - Flags: review?(jdemooij) → review+
Comment on attachment 8989643 [details] [diff] [review]
Part 4: Add PowValues/PowOperation for exponentiation.

Review of attachment 8989643 [details] [diff] [review]:
-----------------------------------------------------------------

Given the different semantics for Math.pow and JSOP_POW, I think we should:

* Call PowValues in Recover.cpp too, for consistency.
* Then inline math_pow_handle into js::math_pow (and remove it).
* In PowOperation, call ecmaPow directly.

r=me with this addressed in either this patch or a follow-up patch :)

(Note that IonBuilder::powTrySpecialized (MPow/LPowV) is called for both Math.pow and JSOP_POW. Fortunately, it checks IsNumberType for both operands so it should be compatible with both.)

::: js/src/vm/Interpreter.h
@@ +468,5 @@
>  bool
>  ModValues(JSContext* cx, MutableHandleValue lhs, MutableHandleValue rhs, MutableHandleValue res);
>  
> +bool
> +PowValues(JSContext* cx, MutableHandleValue lhs, MutableHandleValue rhs, MutableHandleValue res);

Nice!
Attachment #8989643 - Flags: review?(jdemooij) → review+
Comment on attachment 8989644 [details] [diff] [review]
Part 5: Support BigInt operands for basic arithmetic operators.

Review of attachment 8989644 [details] [diff] [review]:
-----------------------------------------------------------------

Beautiful.
Attachment #8989644 - Flags: review?(jdemooij) → review+
Comment on attachment 8989629 [details] [diff] [review]
Part 1: Define methods for basic BigInt arithmetic.

Review of attachment 8989629 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/vm/BigIntType.cpp
@@ +208,5 @@
> +BigInt*
> +BigInt::div(JSContext* cx, HandleBigInt x, HandleBigInt y)
> +{
> +    // Step 1.
> +    if (!mpz_size(y->num_)) {

I'd prefer |== 0| for a comparison to zero, because the alternative implies the function being called actually returns a boolean, and then you get into confusion over what the function call actually *means*.

@@ +227,5 @@
> +BigInt*
> +BigInt::mod(JSContext* cx, HandleBigInt x, HandleBigInt y)
> +{
> +    // Step 1.
> +    if (!mpz_size(y->num_)) {

Ditto.

@@ +248,5 @@
> +{
> +    // Step 1.
> +    if (mpz_sgn(y->num_) < 0) {
> +        JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
> +                                  JSMSG_BIGINT_NEGATIVE_EXPONENT);

Technically this isn't consistent with the spec in the case of 1n**(-1n).  I can imagine plausible arguments why a blanket no-negative-exponents rule is the most sensible approach, but it is not what exists now.  Bring this up with spec proposal peoples and get this change added.
Attachment #8989629 - Flags: review?(jwalden+bmo) → review+
(In reply to Jeff Walden [:Waldo] from comment #27)
> Comment on attachment 8989629 [details] [diff] [review]
> @@ +248,5 @@
> > +{
> > +    // Step 1.
> > +    if (mpz_sgn(y->num_) < 0) {
> > +        JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
> > +                                  JSMSG_BIGINT_NEGATIVE_EXPONENT);
> 
> Technically this isn't consistent with the spec in the case of 1n**(-1n).  I
> can imagine plausible arguments why a blanket no-negative-exponents rule is
> the most sensible approach, but it is not what exists now.  Bring this up
> with spec proposal peoples and get this change added.

I think this is spec-compliant, due to the check for negative exponents being in the first step of BigInt::exponentiate. It might be changed in the future, and there is a github issue suggesting that 1n**(-1n) should be 1n, but currently it is expected to throw an error.
Use |== 0| instead of |!| to compare size_t values to zero. (Still
throws RangeError on all negative exponents including -1n, see previous
comment)
Attachment #8989629 - Attachment is obsolete: true
Attachment #8989641 - Attachment is obsolete: true
Attachment #8989642 - Attachment is obsolete: true
Attachment #8989643 - Attachment is obsolete: true
Attachment #8989644 - Attachment is obsolete: true
Follow the example of AddOperation, which uses MutableHandleValue for
arguments that will be passed to ToPrimitive. This allows parameters to
be converted using ToNumeric instead of ToNumber.
Attachment #8990642 - Flags: review+
Inline math_pow_handle into math_pow and PowValues, and replace other
uses with calls to PowValues.
Attachment #8990643 - Flags: review+
Operands are converted to primitive values using ToNumeric, which can
result in either BigInt or Number values. If any operand is a BigInt,
the corresponding BigInt method is called; otherwise, the existing
behavior for Numbers is used.
Attachment #8990644 - Flags: review+
Attachment #8990640 - Flags: review+
(In reply to Robin Templeton [:terpri] from comment #28)
> I think this is spec-compliant, due to the check for negative exponents
> being in the first step of BigInt::exponentiate.

Hrm.  Either I skimmed too fast reading the spec, or it didn't say this when I checked.  Probably the former.  Carry on!
Keywords: checkin-needed
Pushed by apavel@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b1ebc15b5eec
Part 1: Define methods for basic BigInt arithmetic. r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/1b449d788c94
Part 2: Add BigInt arithmetic methods that accept Value arguments. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/f0328b9f1a4d
Part 3: Make arithmetic operand arguments mutable. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/22883fe0cf16
Part 4: Add PowValues/PowOperation for exponentiation. r=jandem
https://hg.mozilla.org/integration/mozilla-inbound/rev/214a13e783ac
Part 5: Support BigInt operands for basic arithmetic operators. r=jandem
Keywords: checkin-needed
Assignee: nobody → robin
You need to log in before you can comment on or make changes to this bug.