889451 - Range analysis enhancements

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Dan Gohman [:sunfish]]

Range analysis could be more aggressive on several operators, especially the bitwise operators, which all always return int32 results.

Comment 1

[Dan Gohman [:sunfish]]

Attachment: a proposed fix

This patch implements basic range analysis for several operators. More could be done for several of the operators, of course.

Comment 2

[Nicolas B. Pierron [:nbp]]

Comment on attachment 770290 [details] [diff] [review]
a proposed fix

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

::: js/src/ion/RangeAnalysis.cpp
@@ +589,5 @@
> +    // Get the lower and upper values of the operand, and adjust them
> +    // for infinities. Range's constructor treats any value beyond the
> +    // int32_t range as infinity.
> +    int64_t l = (int64_t)op->lower() - op->isLowerInfinite();
> +    int64_t u = (int64_t)op->upper() + op->isUpperInfinite();

nice trick :)
Better than what I suggested to fix it in Bug 888568, can you include the test case with this patch?

Comment 3

[Dan Gohman [:sunfish]]

Attachment: same patch, plus the testcase from bug 888568

Comment 4

[Dan Gohman [:sunfish]]

Comment on attachment 770357 [details] [diff] [review]
same patch, plus the testcase from bug 888568

nbp volunteered on irc to review this :)

Comment 5

[Nicolas B. Pierron [:nbp]]

Comment on attachment 770357 [details] [diff] [review]
same patch, plus the testcase from bug 888568

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

Good job, still some issue on Ursh, as explained in IRC.

Ursh always returns an unsigned, even if it does not fit in the range of an int32.  This is not an unsigned operation which cast its result into a signed number, as an example:

js> -1 >>> 0
4294967295
js> -1 | 0
-1

::: js/src/ion/RangeAnalysis.cpp
@@ +479,5 @@
> +    int64_t upper = INT32_MAX;
> +
> +    if (lhs->lower_ >= 0 && rhs->lower_ >= 0) {
> +        lower = 0;
> +    } else if (lhs->upper_ < 0 && rhs->upper_ < 0) {

Add a comment to mention that if the sign bits are identical then the result would be positive.

@@ +553,5 @@
> +    int32_t shift = c & 0x1f;
> +
> +    // If the value is always non-negative or always negative, we can simply
> +    // compute the correct range by shifting.
> +    if (lhs->lower_ >= 0 || lhs->upper_ < 0) {

nit: non-negative => positive ?

@@ +556,5 @@
> +    // compute the correct range by shifting.
> +    if (lhs->lower_ >= 0 || lhs->upper_ < 0) {
> +        return new Range(
> +            (int32_t)((uint32_t)lhs->lower_ >> shift),
> +            (int32_t)((uint32_t)lhs->upper_ >> shift));

Convert it back to an int64_t instead of int32_t, such as we note the overflow outside of the int32 range if shift is 0.

@@ +560,5 @@
> +            (int32_t)((uint32_t)lhs->upper_ >> shift));
> +    }
> +
> +    // Otherwise an unsigned right shift may have a discontiguous signed range.
> +    return new Range(INT32_MIN, INT32_MAX);

Otherwise it is included in:
  new Range(0, (int64_t)((uint32_t)-1 >> shift))

@@ +579,5 @@
> +Range *
> +Range::ursh(const Range *lhs, const Range *rhs)
> +{
> +    return new Range(Min(0, lhs->lower()),
> +                     lhs->lower() >= 0 ? lhs->upper() : INT32_MAX);

This is not INT32_MAX, but uint32_t(-1), which is larger than INT32_MAX.

@@ +833,1 @@
>  MRsh::computeRange()

There is a trailing whitespace above the definition of this function.

@@ -718,5 @@
>  
>  void
>  MMul::computeRange()
>  {
> -    if ((specialization() != MIRType_Int32 && specialization() != MIRType_Double) || isTruncated())

Good catch.

Comment 6

[Dan Gohman [:sunfish]]

Attachment: patch updated for review comments

> ::: js/src/ion/RangeAnalysis.cpp
> @@ +479,5 @@
> > +    int64_t upper = INT32_MAX;
> > +
> > +    if (lhs->lower_ >= 0 && rhs->lower_ >= 0) {
> > +        lower = 0;
> > +    } else if (lhs->upper_ < 0 && rhs->upper_ < 0) {
> 
> Add a comment to mention that if the sign bits are identical then the result
> would be positive.

Done.

> @@ +553,5 @@
> > +    int32_t shift = c & 0x1f;
> > +
> > +    // If the value is always non-negative or always negative, we can simply
> > +    // compute the correct range by shifting.
> > +    if (lhs->lower_ >= 0 || lhs->upper_ < 0) {
> 
> nit: non-negative => positive ?

Non-negative includes zero :-).

> @@ +556,5 @@
> > +    // compute the correct range by shifting.
> > +    if (lhs->lower_ >= 0 || lhs->upper_ < 0) {
> > +        return new Range(
> > +            (int32_t)((uint32_t)lhs->lower_ >> shift),
> > +            (int32_t)((uint32_t)lhs->upper_ >> shift));
> 
> Convert it back to an int64_t instead of int32_t, such as we note the
> overflow outside of the int32 range if shift is 0.

Done.

> @@ +560,5 @@
> > +            (int32_t)((uint32_t)lhs->upper_ >> shift));
> > +    }
> > +
> > +    // Otherwise an unsigned right shift may have a discontiguous signed range.
> > +    return new Range(INT32_MIN, INT32_MAX);
> 
> Otherwise it is included in:
>   new Range(0, (int64_t)((uint32_t)-1 >> shift))

Done.

> @@ +579,5 @@
> > +Range *
> > +Range::ursh(const Range *lhs, const Range *rhs)
> > +{
> > +    return new Range(Min(0, lhs->lower()),
> > +                     lhs->lower() >= 0 ? lhs->upper() : INT32_MAX);
> 
> This is not INT32_MAX, but uint32_t(-1), which is larger than INT32_MAX.

Done.

> @@ +833,1 @@
> >  MRsh::computeRange()
> 
> There is a trailing whitespace above the definition of this function.

Done.

Comment 7

[Nicolas B. Pierron [:nbp]]

Comment on attachment 770523 [details] [diff] [review]
patch updated for review comments

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

Sorry for the new round-trip, I just want to make sure we do not have subtle bugs.
I think we need to be careful with Double inputs of MUrsh.

::: js/src/ion/RangeAnalysis.cpp
@@ +558,5 @@
> +    // compute the correct range by shifting.
> +    if (lhs->lower_ >= 0 || lhs->upper_ < 0) {
> +        return new Range(
> +            (int64_t)((uint32_t)lhs->lower_ >> shift),
> +            (int64_t)((uint32_t)lhs->upper_ >> shift));

I think we need to check for infinity in the case of Ursh, because it is a double which is shifted by c, we need to account that the max is not INT32_MAX (maximal value of lhs->upper_), but UINT32_MAX.  If we do not account for that then we might get the exponent of by 1 for the exponent over approximation, which will cause the following test case to fail:

  function f(x) {
    if (x >= 0) {
      // if it does not fail, try with lower power of 2.
      return (((x >>> 1) + 1) + 4194304 /* 2 ** (52 - 30) */ + 1) & 1;
    }
    return 2;
  }
  
  assertEq(f(-1 >> 0), 1);
  assertEq(f(-1 >>> 0), 0);
  assertEq(f(-1 >>> 0), 0);

@@ +581,5 @@
> +Range *
> +Range::ursh(const Range *lhs, const Range *rhs)
> +{
> +    return new Range(Min(0, lhs->lower()),
> +                     lhs->lower() >= 0 ? lhs->upper() : UINT32_MAX);

Same thing here,
  lhs->lower() >= 0 && !lhs->isUpperInfinite() ? … : …

Comment 8

[Dan Gohman [:sunfish]]

Comment on attachment 770523 [details] [diff] [review]
patch updated for review comments

Thanks for your help with ursh :-).

Comment 9

[Dan Gohman [:sunfish]]

Attachment: a further revised patch

Comment 10

[Jan de Mooij [:jandem]]

Comment on attachment 770566 [details] [diff] [review]
a further revised patch

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

::: js/src/ion/RangeAnalysis.cpp
@@ +463,5 @@
> +    int64_t lower = INT32_MIN;
> +    int64_t upper = INT32_MAX;
> +
> +    // If the sign bits are the same, the result has the same sign.
> +    if (lhs->lower_ >= 0 && rhs->lower_ >= 0) {

Drive-by style nit: condition and then/else bodies fit on a single line so no braces, same for the xor_ and not_ methods.

Comment 11

[Nicolas B. Pierron [:nbp]]

Comment on attachment 770566 [details] [diff] [review]
a further revised patch

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

Good Work!
Add the test case I provided during the previous review.
And r=me with jandem nits applied.

Comment 12

[Dan Gohman [:sunfish]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/199bda69b2d9

Comment 13

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/199bda69b2d9