923659 - Sunspider regression of 3% on x86-32

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Kannan Vijayan [:djvj]]

AWFY shows a clear 3% sunspider regression on x86-32 bit.  Relevant changeset:

http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=c7bb40f2578a&tochange=a587ed24ade0

Comment 1

[Kannan Vijayan [:djvj]]

Pushlog suggests one of Dan's or Brian's patches might be at issue.  Needinfoing.

Comment 2

[Brian Hackett [Laid off!]]

It looks like all the regression on awfy is in fannkuch and nsieve-bits.  I compared 32 bit threadsafe builds on my mac with parallel compilation on, looking at before either of our changes, after Dan's change, and after my change.  I don't see any difference in SS score, either overall or on these two tests.  Historically ss-fannkuch has been a pretty annoying test as it pounds on a few small arrays and seems to see large effects due to perturbations in where those arrays end up in memory (cache effects I guess).  ss-nsieve-bits also pounds on a few arrays.

Comment 3

[Dan Gohman [:sunfish]]

I don't see any performance difference in ss-fannkuch or ss-nieve-bits on 32-bit Linux either. I do plan to look into the RangeAnalysis output on those tests to see if there's a significant change.

Comment 4

[Dan Gohman [:sunfish]]

There is a regression due to the range analysis changes. I'll take this.

Comment 5

[Dan Gohman [:sunfish]]

Beta node insertion was previously assuming that if the input value has type() == MIRType_Int32, then the beta node can have [INT32_MIN,INT32_MAX] as a worst-case range. The new code does not do this, because it's not safe to trust the type() for range analysis purposes in general. I'll need to determine if there's a reason why trusting type() is ok for beta node analysis, or if there's some other way to achieve the same result.

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #5)
> Beta node insertion was previously assuming that if the input value has
> type() == MIRType_Int32, then the beta node can have [INT32_MIN,INT32_MAX]
> as a worst-case range. The new code does not do this, because it's not safe
> to trust the type() for range analysis purposes in general. I'll need to
> determine if there's a reason why trusting type() is ok for beta node
> analysis, or if there's some other way to achieve the same result.

I guess this is related to the input type of "n", right?  I guess that we can infer the parameter range fits, such as guarding the input types as we do.

Comment 7

[Dan Gohman [:sunfish]]

Attachment: trust-the-type.patch

To be specific, here's a patch which effectively restores the old behavior and eliminates an overflow check in one of the adds in fannkuch.

It's not currently clear to me how this might be safe when it isn't safe for the Range(const MDefinition *def) constructor to do the same thing.

Comment 8

[Dan Gohman [:sunfish]]

One thing that's going on is that MArrayLength does setResultType(MIRType_Int32) in its constructor, however array lengths are in [0,UINT32_MAX], so it doesn't actually return an int32.

Comment 9

[Brian Hackett [Laid off!]]

We use TI to distinguish arrays that might have non-int32 lengths, and should only be generating MArrayLength when it is guaranteed to be int32.  See OBJECT_FLAG_LENGTH_OVERFLOW.

Comment 10

[Nicolas B. Pierron [:nbp]]

(In reply to Brian Hackett (:bhackett) from comment #9)
> We use TI to distinguish arrays that might have non-int32 lengths, and
> should only be generating MArrayLength when it is guaranteed to be int32. 
> See OBJECT_FLAG_LENGTH_OVERFLOW.

Oh, nice I did not know about that.

(In reply to Dan Gohman [:sunfish] from comment #7)
> It's not currently clear to me how this might be safe when it isn't safe for
> the Range(const MDefinition *def) constructor to do the same thing.

In general, if there is no Range we should assume that the MIRType is correct, knowing that all instructions which might have UInt32 are guarded (fallible unbox int32) or have a known range.

Comment 11

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #10)
> (In reply to Brian Hackett (:bhackett) from comment #9)
> > We use TI to distinguish arrays that might have non-int32 lengths, and
> > should only be generating MArrayLength when it is guaranteed to be int32. 
> > See OBJECT_FLAG_LENGTH_OVERFLOW.
> 
> Oh, nice I did not know about that.

Oh, MArrayLength::computeRange didn't know about that either :). I'll add a patch to update it.

> (In reply to Dan Gohman [:sunfish] from comment #7)
> > It's not currently clear to me how this might be safe when it isn't safe for
> > the Range(const MDefinition *def) constructor to do the same thing.
> 
> In general, if there is no Range we should assume that the MIRType is
> correct, knowing that all instructions which might have UInt32 are guarded
> (fallible unbox int32) or have a known range.

Here's my new theory: MDefinition::range() describes the return value *before* any bailout checks. MDefinition::type() describes the return value *after* all bailout checks pass. Except for MUrsh's type(), which is allowed to be MIRType_Int32 even when it doesn't return an int32 and even when its bailout checks have been disabled, because asm.js needs it to work that way (though bug 750947 may eventually provide an alternative approach). So far, this seems to explain everything.

Comment 12

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #11)
> > (In reply to Dan Gohman [:sunfish] from comment #7)
> > > It's not currently clear to me how this might be safe when it isn't safe for
> > > the Range(const MDefinition *def) constructor to do the same thing.
> > 
> > In general, if there is no Range we should assume that the MIRType is
> > correct, knowing that all instructions which might have UInt32 are guarded
> > (fallible unbox int32) or have a known range.
> 
> Here's my new theory: MDefinition::range() describes the return value
> *before* any bailout checks. MDefinition::type() describes the return value
> *after* all bailout checks pass. Except for MUrsh's type(), which is allowed
> to be MIRType_Int32 even when it doesn't return an int32 and even when its
> bailout checks have been disabled, because asm.js needs it to work that way
> (though bug 750947 may eventually provide an alternative approach). So far,
> this seems to explain everything.

This is correct.  At the same time, a load of an Int32 out of a value will always respect the Int32 Range because we cannot encode an unsigned int32 on a Value.

Comment 13

[Dan Gohman [:sunfish]]

Comment on attachment 814003 [details] [diff] [review]
trust-the-type.patch

I believe I know what's going on here now.

Comment 14

[Dan Gohman [:sunfish]]

Attachment: range-beta-eq.patch

Fix a minor error from an earlier patch merge.

Comment 15

[Dan Gohman [:sunfish]]

Attachment: range-null-for-unknown.patch

A minor cleanup.

Comment 16

[Dan Gohman [:sunfish]]

Looking at the code, it appears MInitializedLength is another instruction which is permitted to violate its type() in this way. At least, it's a load from a C++ uint32_t variable, it doesn't have bailouts, and there's no obvious flag like OBJECT_FLAG_LENGTH_OVERFLOW guarding its use. Is this right, or is there something I'm missing?

Comment 17

[Jan de Mooij [:jandem]]

(In reply to Dan Gohman [:sunfish] from comment #16)
> Looking at the code, it appears MInitializedLength is another instruction
> which is permitted to violate its type() in this way. At least, it's a load
> from a C++ uint32_t variable, it doesn't have bailouts, and there's no
> obvious flag like OBJECT_FLAG_LENGTH_OVERFLOW guarding its use. Is this
> right, or is there something I'm missing?

The initialized length is always < NELEMENTS_LIMIT (1 << 28 I think).

Comment 18

[Dan Gohman [:sunfish]]

Attachment: range-array-length.patch

This patch teaches range analysis about the real ranges of MArrayLength and MInitializedLength, as described in comment 9 and comment 17.

Comment 19

[Dan Gohman [:sunfish]]

Attachment: range-typed-array-load.patch

The uint32 version of MLoadTypedArrayElement has bailout checks for the non-int32 case, so it doesn't need extendUInt32ToInt32Min.

Comment 20

[Dan Gohman [:sunfish]]

Attachment: range-get-operand-range.patch

This pass documents and implements some of the subtleties discussed above concerning range() returning a value before bailout checks.

Comment 21

[Dan Gohman [:sunfish]]

Attachment: range-cleanup.patch

This is just some simple cleanups; it's nice for debugging purposes if the range code makes all the adjustments it needs before calling setRange, rather than after, so that the MDefinition only sees the range it's supposed to have.

Comment 22

[Dan Gohman [:sunfish]]

Attachment: range-check-all.patch

This patch changes range checking to use the MDefinition Range constructor instead of using range() directly, since range checking checks the value after bailout checks.

Comment 23

[Dan Gohman [:sunfish]]

Attachment: range-use-types.patch

The MDefinition Range constructor was a little confused about whether it's supposed to use types to adjust the range or to JS_ASSERT. This patch takes a stance, reflecting the discussion above that:
 - type() describes the value after bailout checks, and is trustworthy (except Ursh)
 - range() describes the value before bailout checks, so it can't be assumed to conform to type()

Comment 24

[Dan Gohman [:sunfish]]

Attachment: range-ursh-special-case.patch

As discussed above, Ursh is a special case which is allowed to return non-int32 values despite having an int32 type. This patch clarifies and documents this special case.

Also, it moves the special-case handling out of MUrsh::computeRange() and into Range::Range(MDefinition *), since MUrsh's range() before bailout checks really is [0,UINT32_MAX], and after bailout checks it may be implicitly converted to int32 so its post-bailout range must reflect that.

Comment 25

[Dan Gohman [:sunfish]]

The above patch sequence eliminates the overflow check regression in fannkuch. I haven't yet reproduced the actual slowdown; I just confirmed it by examining the code.

Comment 26

[Nicolas B. Pierron [:nbp]]

Comment on attachment 815022 [details] [diff] [review]
range-typed-array-load.patch

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

::: js/src/jit/RangeAnalysis.cpp
@@ -1267,5 @@
>  MLoadTypedArrayElement::computeRange()
>  {
> -    if (Range *range = GetTypedArrayRange(arrayType())) {
> -        if (type() == MIRType_Int32 && !range->hasInt32UpperBound())
> -            range->extendUInt32ToInt32Min();

Sorry, we need that for the Uint32 case.

@@ -1276,5 @@
>  void
>  MLoadTypedArrayElementStatic::computeRange()
>  {
> -    if (Range *range = GetTypedArrayRange(typedArray_->type()))
> -        setRange(range);

And here too, unless you want to move that as part of the NewUint32Range?

Comment 27

[Dan Gohman [:sunfish]]

Attachment: range-typed-array-load.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #26)
> Comment on attachment 815022 [details] [diff] [review]
> range-typed-array-load.patch
> 
> Review of attachment 815022 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ -1267,5 @@
> >  MLoadTypedArrayElement::computeRange()
> >  {
> > -    if (Range *range = GetTypedArrayRange(arrayType())) {
> > -        if (type() == MIRType_Int32 && !range->hasInt32UpperBound())
> > -            range->extendUInt32ToInt32Min();
> 
> Sorry, we need that for the Uint32 case.

MLoadTypedArrayElement uses a bailout to protect the Uint32 case, so it doesn't need this.

One of the goals of this patch series is to make a distinction between ranges before and after bailouts. extendUInt32ToInt32Min() is used to fix pre-bailout ranges, however type() is a post-bailout property, so the only place where range analysis cares about UInt32 values not fitting their type is after bailouts. From the discussion above and my own investigation, the only operator with this problem currently is Ursh.

At the end of the series, extendUInt32ToInt32Min() is gone, only Ursh is special-cased, and it's special-cased in a post-bailout way :).

I added comments about MLoadTypedArrayElement to the patch.

> @@ -1276,5 @@
> >  void
> >  MLoadTypedArrayElementStatic::computeRange()
> >  {
> > -    if (Range *range = GetTypedArrayRange(typedArray_->type()))
> > -        setRange(range);
> 
> And here too, unless you want to move that as part of the NewUint32Range?

MLoadTypedArrayElementStatic isn't currently used with UInt32 types, so it doesn't need this. I added an assert and a comment.

Comment 28

[Nicolas B. Pierron [:nbp]]

Comment on attachment 815025 [details] [diff] [review]
range-get-operand-range.patch

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

::: js/src/jit/RangeAnalysis.cpp
@@ -841,5 @@
> -        Range *input = getOperand(i)->range();
> -
> -        if (!input) {
> -            range = nullptr;
> -            break;

if there is no input range, then there is no need to continue, because the result of unionWith would give the same as the result as Range(ofThisPhi).  Doing so might prevent allocating a Range for nothing (if this is the first operand).

@@ +854,5 @@
>  {
>      bool emptyRange = false;
>  
> +    Range opRange(getOperand(0));
> +    Range *range = Range::intersect(&opRange, comparison_, &emptyRange);

Nice catch!

Comment 29

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #27)
> Created attachment 815539 [details] [diff] [review]
> range-typed-array-load.patch
> 
> (In reply to Nicolas B. Pierron [:nbp] from comment #26)
> > Comment on attachment 815022 [details] [diff] [review]
> > range-typed-array-load.patch
> > 
> > Review of attachment 815022 [details] [diff] [review]:
> > -----------------------------------------------------------------
> > 
> > ::: js/src/jit/RangeAnalysis.cpp
> > @@ -1267,5 @@
> > >  MLoadTypedArrayElement::computeRange()
> > >  {
> > > -    if (Range *range = GetTypedArrayRange(arrayType())) {
> > > -        if (type() == MIRType_Int32 && !range->hasInt32UpperBound())
> > > -            range->extendUInt32ToInt32Min();
> > 
> > Sorry, we need that for the Uint32 case.
> 
> MLoadTypedArrayElement uses a bailout to protect the Uint32 case, so it
> doesn't need this.
> 
> One of the goals of this patch series is to make a distinction between
> ranges before and after bailouts. extendUInt32ToInt32Min() is used to fix
> pre-bailout ranges, however type() is a post-bailout property, so the only
> place where range analysis cares about UInt32 values not fitting their type
> is after bailouts. From the discussion above and my own investigation, the
> only operator with this problem currently is Ursh.
> 
> At the end of the series, extendUInt32ToInt32Min() is gone, only Ursh is
> special-cased, and it's special-cased in a post-bailout way :).

I think the last un-reviewed patch belong to another bug, as they seems unrelated to the sunspider regression.
Or I don't see how they directly relate to this performance regression.

Comment 30

[Dan Gohman [:sunfish]]

Comment on attachment 815037 [details] [diff] [review]
range-ursh-special-case.patch

(In reply to Nicolas B. Pierron [:nbp] from comment #29)
> (In reply to Dan Gohman [:sunfish] from comment #27)
> > At the end of the series, extendUInt32ToInt32Min() is gone, only Ursh is
> > special-cased, and it's special-cased in a post-bailout way :).
> 
> I think the last un-reviewed patch belong to another bug, as they seems
> unrelated to the sunspider regression.
> Or I don't see how they directly relate to this performance regression.

Ok. I created bug 925586 and moved the last patch there.

Comment 31

[Dan Gohman [:sunfish]]

Comment on attachment 815030 [details] [diff] [review]
range-check-all.patch

Moved to bug 925586.

Comment 32

[Dan Gohman [:sunfish]]

Comment on attachment 815034 [details] [diff] [review]
range-use-types.patch

Moved to bug 925586.

Comment 33

[Dan Gohman [:sunfish]]

Reading your comment again I think you wanted me to move the other unreviewed patches to a different bug too. This is now done, except for range-typed-array-load.patch, which you've already started reviewing here.

Comment 34

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #33)
> Reading your comment again I think you wanted me to move the other
> unreviewed patches to a different bug too. This is now done, except for
> range-typed-array-load.patch, which you've already started reviewing here.

It has nothing to do with this regression, right?
There is no TypedArray in sunspider.

I am sorry for the book-keeping, but this is just to keep things clear between what is a fix and what is an improvement.

Comment 35

[Nicolas B. Pierron [:nbp]]

Comment on attachment 815539 [details] [diff] [review]
range-typed-array-load.patch

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

Cancel the review as this patch should be part of Bug 925586.

Comment 36

[Dan Gohman [:sunfish]]

Comment on attachment 815539 [details] [diff] [review]
range-typed-array-load.patch

Moved to bug 925586.

Comment 37

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #28)
> @@ -841,5 @@
> > -        Range *input = getOperand(i)->range();
> > -
> > -        if (!input) {
> > -            range = nullptr;
> > -            break;
> 
> if there is no input range, then there is no need to continue, because the
> result of unionWith would give the same as the result as Range(ofThisPhi). 
> Doing so might prevent allocating a Range for nothing (if this is the first
> operand).

Ok, I reintroduced code doing this.

https://hg.mozilla.org/integration/mozilla-inbound/rev/4a67b5951c23
https://hg.mozilla.org/integration/mozilla-inbound/rev/22e6f21251c9
https://hg.mozilla.org/integration/mozilla-inbound/rev/21f1754f307b
https://hg.mozilla.org/integration/mozilla-inbound/rev/465f94eb4952

Comment 38

[Dan Gohman [:sunfish]]

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

Comment 39

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/4a67b5951c23
https://hg.mozilla.org/mozilla-central/rev/22e6f21251c9
https://hg.mozilla.org/mozilla-central/rev/21f1754f307b
https://hg.mozilla.org/mozilla-central/rev/465f94eb4952
https://hg.mozilla.org/mozilla-central/rev/ea7391a59323