809472 - IonMonkey: Do truncate analysis for MMul

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Hannes Verschore [:h4writer]]

MMul could also benefit from truncate analysis by not needing a snapshot/bailout.

Comment 1

[Hannes Verschore [:h4writer]]

Attachment: Add truncate analysis

Comment 2

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 679171 [details] [diff] [review]
Add truncate analysis

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

Sadly, I considered this when I initially wrote the code.  The standard trick of "just ignore everything but the lower 32 bits" doesn't work with multiply.  Consider:
js> var int_max = 0x7fffffff;
js> print ((int_max*int_max) | 0);
0
where the product is a number so large (4611686014132420609) that a double cannot hold it exactly, and gets rounded.  Actually looking at that computation gives:
js> print(int_max*int_max)
4611686014132420600

Now that range analysis has landed, we can see if the range of the multiply is outside of what a double can hold exactly, and only then apply the transformation.  This will likely require a bit of processing after the range analysis phase to continue to propagate truncation information after the multiply's truncation is known to be safe.

Comment 3

[Hannes Verschore [:h4writer]]

(In reply to Marty Rosenberg [:mjrosenb] from comment #2)
> Sadly, I considered this when I initially wrote the code.  The standard
> trick of "just ignore everything but the lower 32 bits" doesn't work with
> multiply.  Consider:
> js> var int_max = 0x7fffffff;
> js> print ((int_max*int_max) | 0);
> 0
> where the product is a number so large (4611686014132420609) that a double
> cannot hold it exactly, and gets rounded.  Actually looking at that
> computation gives:
> js> print(int_max*int_max)
> 4611686014132420600

Wow, that's annoying. I thought it would be an easy (small) win for crypto am3.
Until I find more benchmark where this matters, I will leave it for now.

Comment 4

[Hannes Verschore [:h4writer]]

Attachment: Truncate analysis for Mul

Was actually easier than expected. During truncate analysis we annotate the MMul to be only used truncated. During range analysis we decide to truncate when the output range is lower than 2^53 (Numbers only get imprecise if value is bigger than 2^53).

Comment 5

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 679613 [details] [diff] [review]
Truncate analysis for Mul

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

Wow, I'm surprised it was this easy as well!

::: js/src/ion/RangeAnalysis.cpp
@@ +419,5 @@
>  
>  bool
> +Range::precisionLossMul(const Range *lhs, const Range *rhs)
> +{
> +    int64_t loss  = 9007199254740992; // result must be lower than 2^53

Can we not hardcode that number?

::: js/src/jit-test/tests/ion/bug809472.js
@@ +10,5 @@
> +//MAX_INT
> +var x = 0x7ffffffe;
> +assertEq(test1(x), 2113929216);
> +assertEq(test2(x), 2130706434);
> +assertEq(test3(x), 2139095042);

Another corner case that it'll be easy to mess up (doesn't look like your code has this issue) is something like:
var a = 0x7fff ffff; // INT_MIN
var b = a + a + 3 // UINT_MAX+1, cannot be represented in 32 bits, b | 0 == 1
return b * b | 0

Where the danger is propagating the truncation past the multiplication, to the operands of the addition, and if we assume that truncation happens, then the truncate on the multiply is valid.

Comment 6

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9f3a01124d8c

Comment 7

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/9f3a01124d8c