836102 - IonMonkey: Avoid double math in base.js's Math.random() replacement

Status: RESOLVED FIXED

Description

[Sean Stangl [:sstangl]]

The following Math.random() replacement from v8's base.js uses double arithmetic:

> Math.random = (function() {
>   var seed = 49734321;
>   return function() {
>     // Robert Jenkins' 32 bit integer hash function.
>     seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
>     seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
>     seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
>     seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
>     seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
>     seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
>     return (seed & 0xfffffff) / 0x10000000;
>   };
> })();

Since the effective bits beyond 32 are discarded, the 0xffffffff (or |0) should propagate.

This is worth about 3% on v8-regexp.

Comment 1

[Hannes Verschore [:h4writer]]

Looking quickly into this, we do use integer arithmetic.

The problem is
1) We don't specialize the loadFixedslot of "seed" to integer loadFixedSlotT
2) The code does StoreFixedSlot after LoadFixedSlot. This can get removed. See bug 801872.

Comment 2

[Hannes Verschore [:h4writer]]

Okay, scratch that previous comment. I'll look tomorrow when I'm more awake ;).

Comment 3

[Marty Rosenberg [:mjrosenb]]

There is a simple fix for this.  I recently added a pass that identifies computations that overflow and are truncated, and forces them back to integer computations.  It requires identifying int32->double conversions and removing them.  The problem here is that operations like |seed + 0xfd7046c5| involve seed getting coerced to double because the other operand is a double.  Since the constant 0xfd7046c5 is a double, and not converted from an integer, we don't convert the operation to an integer.  Adding a simple (in pseudo-code)
virtual bool MConstant::isBigIntOutput() { return typeIsNumber() && frac(number) == 0 && log_2(number) - 32; }
basically, if the constant is a double, and all of the fractional bits are zero, then we want to return the number of bits past the 32nd bit that would need to be set in order for the number to be represented exactly.  There may also be some magic required to truncate the double constant into an integer constant at compile time.

Comment 4

[Hannes Verschore [:h4writer]]

Attachment: Truncate constants

Running this benchmark 1000000 times gives:

Without patch:
real	0m1.882s

With patch:
real	0m0.031s

Comment 5

[Hannes Verschore [:h4writer]]

Comment on attachment 708086 [details] [diff] [review]
Truncate constants

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

I'll add testcases for the issues I found here.

::: js/src/ion/MIR.cpp
@@ +340,5 @@
> +    if (js::ion::EdgeCaseAnalysis::AllUsesTruncate(this) &&
> +        value_.isDouble() && isBigIntOutput())
> +    {
> +        // Truncate the double to int, since all uses truncates it.
> +        value_.setInt32(int32_t(value_.toDouble()));

Off course this should be: ToInt32() instead of int32_t cast

::: js/src/ion/MIR.h
@@ +710,5 @@
> +            double value = value_.toDouble();
> +            int64_t valint = value;
> +            int64_t max = 1LL<<53;
> +            if (double(valint) != value)
> +                return false;

if (valint < 0)
  valint = -valint;

// This should get added to handle the negative case.

Comment 6

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 708086 [details] [diff] [review]
Truncate constants

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

The patch mostly looks good.  You may want to lower the limit from 1<<53 to 1 << 33 for now... It will handle all of the cases present in the Math.random() replacement, and won't involve handling incredibly annoying cases such as:
var x = 0x123456789abcd;
x = x + x; // x = 640511947003802
x = x + x; // x = 1281023894007604
x = x + x; // x = 2562047788015208
x = x + x; // x = 5124095576030416
x = x + x; // x = 10248191152060832
print(x+1) // prints 10248191152060832
print(x+1 | 0) // prints -248153696, with optimization and without the previous print, will print -248153695
Since we cut off after 20 operations, limiting the size of the constant to 33 bits should prevent us from ever reaching the magical 2**53 plateau.  Or you can figure out how to limit the number of additions to a lower number when one of the immediates present is well over 2**32.

Comment 7

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/efc9d9f5f30e

Follow-up bug to do this better:
https://bugzilla.mozilla.org/show_bug.cgi?id=836826

Comment 8

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/efc9d9f5f30e