891070 - More range analysis enhancements

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Dan Gohman [:sunfish]]

Building on bug 889451, range analysis could be even more aggressive on several operators.

Comment 1

[Dan Gohman [:sunfish]]

Attachment: enhanced analysis for or, xor, and not

Comment 2

[Dan Gohman [:sunfish]]

Attachment: tidying

Comment 3

[Dan Gohman [:sunfish]]

Attachment: tidying

Comment 4

[Dan Gohman [:sunfish]]

Attachment: range analysis for boolean and int32 return types

Comment 5

[Dan Gohman [:sunfish]]

Attachment: tidying

Comment 6

[Nicolas B. Pierron [:nbp]]

Comment on attachment 772263 [details] [diff] [review]
enhanced analysis for or, xor, and not

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

Sounds good to me.

::: js/src/ion/RangeAnalysis.cpp
@@ +503,5 @@
> +                                  js_bitscan_clz32(~rhs->lower_));
> +    } else if (lhs->upper_ < 0 && rhs->lower_ >= 0) {
> +        // One operand is negative and the other is positive. The result will
> +        // have leading zeros where the negative operand has leading ones and
> +        // the non-negative operand has leading zeros.

nit: positive -> non-negative ?
nit: The result will have leading ones …

@@ +508,5 @@
> +        upper = -1;
> +        lower = (int32_t)~(UINT32_MAX >> Min(js_bitscan_clz32(~lhs->lower_),
> +                                             js_bitscan_clz32(rhs->upper_)));
> +    } else if (lhs->lower_ >= 0 && rhs->upper_ < 0) {
> +        // One operand is negative and the other is positive. As above.

nit: same here.

Comment 7

[Nicolas B. Pierron [:nbp]]

Comment on attachment 772265 [details] [diff] [review]
tidying

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

::: js/src/ion/RangeAnalysis.cpp
@@ +550,5 @@
>  
>      // If the shift doesn't loose bits or shift bits into the sign bit, we
>      // can simply compute the correct range by shifting.
> +    if ((int32_t)((uint32_t)lhs->lower_ << shift << 1 >> shift >> 1) == lhs->lower_ &&
> +        (int32_t)((uint32_t)lhs->upper_ << shift << 1 >> shift >> 1) == lhs->upper_)

nit: What I used to to do avoid the extra pair of parentheses is:
  int32_t(expr)

which act as a constructor instead of cast, which add an implicit cast as part of the argument coercion.

Comment 8

[Nicolas B. Pierron [:nbp]]

Comment on attachment 772268 [details] [diff] [review]
range analysis for boolean and int32 return types

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

::: js/src/ion/RangeAnalysis.cpp
@@ +691,5 @@
> +    // Default implementation: Just do what we can with the result type.
> +    if (resultType_ == MIRType_Boolean)
> +       setRange(new Range(0, 1));
> +    else if (resultType_ == MIRType_Int32)
> +       setRange(new Range(INT32_MIN, INT32_MAX));

This implies that we will allocate a Range on all int/bool definitions, even if it does not flow anywhere interesting for Range Analysis (such as copies).

I fail to see why we could not keep the result type comparisons in the Range constructor to prevent the allocation.

Comment 9

[Nicolas B. Pierron [:nbp]]

Comment on attachment 772269 [details] [diff] [review]
tidying

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

::: js/src/ion/RangeAnalysis.cpp
@@ +1098,5 @@
>      // Try to hoist any bounds checks from the loop using symbolic bounds.
>  
>      Vector<MBoundsCheck *, 0, IonAllocPolicy> hoistedChecks;
>  
> +    for (ReversePostorderIterator iter(graph_.rpoBegin(header)); iter != graph_.rpoEnd(); iter++) {

Nice catch :)

Comment 10

[Dan Gohman [:sunfish]]

Thanks for the reviews :). Your comment about allocating ranges when they aren't needed makes sense; I didn't know that that's what the code in the constructor was for. I'll work on a new patch which implements the Boolean range analysis in the constructor.

https://hg.mozilla.org/integration/mozilla-inbound/rev/ee3c65806ad5
https://hg.mozilla.org/integration/mozilla-inbound/rev/c9d870de3b12
https://hg.mozilla.org/integration/mozilla-inbound/rev/c42922a41374
https://hg.mozilla.org/integration/mozilla-inbound/rev/600df52eb174

Comment 11

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/ee3c65806ad5
https://hg.mozilla.org/mozilla-central/rev/c9d870de3b12
https://hg.mozilla.org/mozilla-central/rev/c42922a41374
https://hg.mozilla.org/mozilla-central/rev/600df52eb174

Comment 12

[Dan Gohman [:sunfish]]

Attachment: a proposed fix

This patch just teaches the range constructor about boolean types.

Comment 13

[Nicolas B. Pierron [:nbp]]

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

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

::: js/src/ion/RangeAnalysis.cpp
@@ +1495,5 @@
>  
> +void
> +Range::truncateToBoolean()
> +{
> +    if (isBoolean())

where is this function declared / defined?

@@ +1499,5 @@
> +    if (isBoolean())
> +        return;
> +    int32_t l = Max(Min(lower(), 1), 0);
> +    int32_t h = Max(Min(upper(), 1), 0);
> +    set(l, h, false, 1);

That's interesting, but I fail to see where any computeRange function will compute the Range of an MDefinition which has a Boolean results.  Is that a case which show-up in asm.js ?

Comment 14

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #13)
> Comment on attachment 772900 [details] [diff] [review]
> a proposed fix
> 
> Review of attachment 772900 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/ion/RangeAnalysis.cpp
> @@ +1495,5 @@
> >  
> > +void
> > +Range::truncateToBoolean()
> > +{
> > +    if (isBoolean())
> 
> where is this function declared / defined?

It's a member function defined inline in RangeAnalysis.h.

> @@ +1499,5 @@
> > +    if (isBoolean())
> > +        return;
> > +    int32_t l = Max(Min(lower(), 1), 0);
> > +    int32_t h = Max(Min(upper(), 1), 0);
> > +    set(l, h, false, 1);
> 
> That's interesting, but I fail to see where any computeRange function will
> compute the Range of an MDefinition which has a Boolean results.  Is that a
> case which show-up in asm.js ?

This actually comes up in non-asm.js code. It allows expressions like

  a[i] = a[i] + (b[i] == c[i])

where a[i] is something from a Uint8 typed array or so, to avoid an overflow check. I don't know if any benchmarks do this, but it happens in some code that I'm looking at :-).

Comment 15

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #14)
> (In reply to Nicolas B. Pierron [:nbp] from comment #13)
> > ::: js/src/ion/RangeAnalysis.cpp
> > @@ +1495,5 @@
> > >  
> > > +void
> > > +Range::truncateToBoolean()
> > > +{
> > > +    if (isBoolean())
> > 
> > where is this function declared / defined?
> 
> It's a member function defined inline in RangeAnalysis.h.

Hum … I do not have it in my work-directory and I cannot find it in mxr.mozilla.com.
Did it landed recently or I missed a patch?

> > @@ +1499,5 @@
> > > +    if (isBoolean())
> > > +        return;
> > > +    int32_t l = Max(Min(lower(), 1), 0);
> > > +    int32_t h = Max(Min(upper(), 1), 0);
> > > +    set(l, h, false, 1);
> > 
> > That's interesting, but I fail to see where any computeRange function will
> > compute the Range of an MDefinition which has a Boolean results.  Is that a
> > case which show-up in asm.js ?
> 
> This actually comes up in non-asm.js code. It allows expressions like
> 
>   a[i] = a[i] + (b[i] == c[i])
> 
> where a[i] is something from a Uint8 typed array or so, to avoid an overflow
> check. I don't know if any benchmarks do this, but it happens in some code
> that I'm looking at :-).

I meant I do not see where the Max(Min(…), …) logic can be useful, as this implied that we had a computeRange function on a MIR node which has a boolean returnType.

Comment 16

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #15)
> (In reply to Dan Gohman [:sunfish] from comment #14)
> > (In reply to Nicolas B. Pierron [:nbp] from comment #13)
> > > ::: js/src/ion/RangeAnalysis.cpp
> > > @@ +1495,5 @@
> > > >  
> > > > +void
> > > > +Range::truncateToBoolean()
> > > > +{
> > > > +    if (isBoolean())
> > > 
> > > where is this function declared / defined?
> > 
> > It's a member function defined inline in RangeAnalysis.h.
> 
> Hum … I do not have it in my work-directory and I cannot find it in
> mxr.mozilla.com.
> Did it landed recently or I missed a patch?

It's in this same patch :-).

> 
> > > @@ +1499,5 @@
> > > > +    if (isBoolean())
> > > > +        return;
> > > > +    int32_t l = Max(Min(lower(), 1), 0);
> > > > +    int32_t h = Max(Min(upper(), 1), 0);
> > > > +    set(l, h, false, 1);
> > > 
> > > That's interesting, but I fail to see where any computeRange function will
> > > compute the Range of an MDefinition which has a Boolean results.  Is that a
> > > case which show-up in asm.js ?
> > 
> > This actually comes up in non-asm.js code. It allows expressions like
> > 
> >   a[i] = a[i] + (b[i] == c[i])
> > 
> > where a[i] is something from a Uint8 typed array or so, to avoid an overflow
> > check. I don't know if any benchmarks do this, but it happens in some code
> > that I'm looking at :-).
> 
> I meant I do not see where the Max(Min(…), …) logic can be useful, as this
> implied that we had a computeRange function on a MIR node which has a
> boolean returnType.

Makes sense. I was thinking it looked more complete that way, but it's not important. I can replace this with just [0,1].

Comment 17

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #16)
> > > (In reply to Nicolas B. Pierron [:nbp] from comment #13)
> > > > ::: js/src/ion/RangeAnalysis.cpp
> > > > @@ +1495,5 @@
> > > > >  
> > > > > +void
> > > > > +Range::truncateToBoolean()
> > > > > +{
> > > > > +    if (isBoolean())
> > > > 
> > > > where is this function declared / defined?
> 
> It's in this same patch :-).

Whoa … I don't know how I missed it so many reviews of this patch.
Sorry about that.

Comment 18

[Nicolas B. Pierron [:nbp]]

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

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

Remove the Max(Min(…), …) and just do the set(0, 1, false, 1), as it will be useful until we add a computeRange on a MIR which has a Boolean returnType.
And r=me

Comment 19

[Dan Gohman [:sunfish]]

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

Comment 20

[Ed Morley [:emorley]]

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