1040027 - Escape Analysis: Replace Load and Stores of NewArray.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Nicolas B. Pierron [:nbp]]

The goal of this bug is to do the same thing as we did with Bug 992845 but for MNewArray.  Note, that this patch would be divided in 2 independent parts, one which does the escaping, and one which recover the Array allocation.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Part 1 - Detect when we can replace an Array by an ArrayState.

This patch replicate what was done for scalar replacemenet of objects with
new arrays.

Comment 2

[Nicolas B. Pierron [:nbp]]

Attachment: Part 2 - Recover MNewArray.

This patch is orthogonal, and add the ability to recover unused MNewArray.

On Pdf.JS, I noticed an improvement of .6% over 100 runs of the benchmark.

Comment 3

[Jan de Mooij [:jandem]]

Comment on attachment 8458112 [details] [diff] [review]
Part 1 - Detect when we can replace an Array by an ArrayState.

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

Looks good, but I wonder if there's a problem with getters on the prototype (see last comment below), clearing review until that's addressed.

::: js/src/jit/MIR.h
@@ +1907,5 @@
>          return true;
>      }
>  };
>  
> +// Represent the content of all indexes of an array.  This instruction is not

Nit: s/content/contents, s/indexes/elements

@@ +1912,5 @@
> +// lowered and is not used to generate code.
> +class MArrayState : public MVariadicInstruction
> +{
> +  private:
> +    uint32_t numIndexes_;

Use numElements_ here too; it's nice to have "slots" (MNewObject, MSlots, M{Load,Store}Slot) and "elements" (MNewArray, MElements, M{Load,Store}Element).

::: js/src/jit/Recover.h
@@ +494,5 @@
>  
> +class RArrayState MOZ_FINAL : public RInstruction
> +{
> +  private:
> +    uint32_t numIndexes_;

Nit: numElements_ here too.

::: js/src/jit/ScalarReplacement.cpp
@@ +351,5 @@
> +IsArrayEscaped(MInstruction *ins)
> +{
> +    MOZ_ASSERT(ins->type() == MIRType_Object);
> +    if (!ins->isNewArray())
> +        return true;

IsObjectEscaped doesn't check this... Can we MOZ_ASSERT(ins->isNewArray()) here and MOZ_ASSERT(ins->isNewObject()) in IsObjectEscaped for consistency?

@@ +356,5 @@
> +    uint32_t count = ins->toNewArray()->count();
> +
> +    // Check if the object is escaped. If the object is not the first argument
> +    // of either a known Store / Load, then we consider it as escaped. This is a
> +    // cheap an conservative escape analysis.

Nit: s/an/and, also in IsObjectEscaped.

@@ +371,5 @@
> +        switch (def->op()) {
> +          case MDefinition::Op_Elements: {
> +            MOZ_ASSERT(def->toElements()->object() == ins);
> +            for (MUseIterator i(def->usesBegin()); i != def->usesEnd(); i++) {
> +                // The MIRType_Element cannot be caputred in a resume point as

Nit: s/Element/Elements and captured (typo)

@@ +460,5 @@
> +    if (!states.reserve(graph.numBlocks()))
> +        return false;
> +
> +    for (size_t bid = 0; bid < graph.numBlocks(); bid++)
> +        states.infallibleAppend(nullptr);

Nit: states.appendN(nullptr, graph.numBlocks()) like ScalarReplacementOfObject.

@@ +462,5 @@
> +
> +    for (size_t bid = 0; bid < graph.numBlocks(); bid++)
> +        states.infallibleAppend(nullptr);
> +
> +    // Uninitialized slots have an "undefined" value.

Nit: s/slots/elements

Also how does this work for something like this:

Object.defineProperty(Array.prototype, 3, {get: function() { print("get"); return 8; }});

var arr = [1,,,,,,2];
print(arr[3]); // Prints "8"

Comment 4

[Jan de Mooij [:jandem]]

Comment on attachment 8458116 [details] [diff] [review]
Part 2 - Recover MNewArray.

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

::: js/src/jit/Recover.cpp
@@ +919,5 @@
> +
> +    // See CodeGenerator::visitNewArrayCallVM
> +    if (!templateObject->hasSingletonType())
> +        type = templateObject->type();
> +    resultObject = NewInitArray(cx, count_, type);

Nit: JSObject *resultObject = ...;

MNewArray is also used for |new Array(1000000);| and in that case we don't want to allocate all elements immediately (see MNewArray::AllocatingBehaviour). Should we store this enum value too, or, maybe simpler, only recover MNewArray if NewArray_Allocating?

Comment 5

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #4)
> MNewArray is also used for |new Array(1000000);| and in that case we don't
> want to allocate all elements immediately (see
> MNewArray::AllocatingBehaviour). Should we store this enum value too, or,
> maybe simpler, only recover MNewArray if NewArray_Allocating?

I think there is 2 issues here.  The first one is the size of the Array.  We do not want to allocate an object state which has 10^n elements in it.

The second one is avoiding the eager allocation of this array.

The solution I took, was to avoid the escape analysis if we are not allocating in Ion, and if the NewArray allocation is unused, then I still keep it as a Recover instruction and allocate it as we do with js_Array.

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #3)
> ::: js/src/jit/ScalarReplacement.cpp
> @@ +351,5 @@
> > +IsArrayEscaped(MInstruction *ins)
> > +{
> > +    MOZ_ASSERT(ins->type() == MIRType_Object);
> > +    if (!ins->isNewArray())
> > +        return true;
> 
> IsObjectEscaped doesn't check this... Can we MOZ_ASSERT(ins->isNewArray())
> here and MOZ_ASSERT(ins->isNewObject()) in IsObjectEscaped for consistency?

I will add the MOZ_ASSERT in IsObjectEscaped as part of Bug 1039607.

Comment 7

[Nicolas B. Pierron [:nbp]]

Attachment: Part 1 - Detect when we can replace an Array by an ArrayState.

Delta:
 - Prevent non int32 constant to flow as element indexes.
 - Check for isAllocating and needsHoleCheck flags before escaping.
 - Refuse any StoreElement which stores a Hole inside the array, as we do not yet support encoding it in snapshots.
 - Fix typos and follow suggestions.

Comment 8

[Nicolas B. Pierron [:nbp]]

Attachment: Part 2 - IonMonkey: Recover MNewArray.

Delta:
 - Recover allocation is based on the same condition as js_Array.
 - Move variable declaration below in the recover function.

Comment 9

[Jan de Mooij [:jandem]]

(In reply to Nicolas B. Pierron [:nbp] from comment #8)
>  - Recover allocation is based on the same condition as js_Array.

Also for NEWARRAY? For array initializers we need to allocate all elements because IonBuilder::jsop_initelem_array() does not add any bounds checks and we don't want to resize...

Comment 10

[Jan de Mooij [:jandem]]

Comment on attachment 8461468 [details] [diff] [review]
Part 1 - Detect when we can replace an Array by an ArrayState.

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

Looks good, r=me with comments addressed.

::: js/src/jit/Recover.cpp
@@ +1012,5 @@
> +        Value val = iter.read();
> +
> +        if (index >= initLength) {
> +            MOZ_ASSERT(val.isUndefined());
> +            continue;

When does this happen? We don't optimize MStoreElement if the index >= |count| right? I'll r+ this patch assuming we can remove it but if we need the check we should discuss.

::: js/src/jit/ScalarReplacement.cpp
@@ +353,5 @@
> +IsArrayEscaped(MInstruction *ins)
> +{
> +    MOZ_ASSERT(ins->type() == MIRType_Object);
> +    if (!ins->isNewArray())
> +        return true;

Nit: can we change the argument type from MInstruction* to MNewArray*, or MOZ_ASSERT(ins->isNewArray())?

@@ +358,5 @@
> +    uint32_t count = ins->toNewArray()->count();
> +
> +    // The array is probably too large to be represented efficiently with
> +    // MArrayState, and we do not want to make huge allocations during bailouts.
> +    if (!ins->toNewArray()->isAllocating())

As we discussed last week, isAllocating is also true for huge array initializers. Should we also limit the length?

@@ +405,5 @@
> +                    if (!index->isConstant())
> +                        return true;
> +                    Value v = index->toConstant()->value();
> +                    if (v.toNumber() >= count || !v.isInt32())
> +                        return true;

Nit: this "MDefinition-to-index" code appears 4 times in this file. Can we add a helper function for it?

Comment 11

[Jan de Mooij [:jandem]]

Comment on attachment 8461469 [details] [diff] [review]
Part 2 - IonMonkey: Recover MNewArray.

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

As discussed last week, this is fine for |new Array(len)| but for array literals (JSOP_NEWARRAY) we need the eager allocation behavior even if the length is huge (because we don't want to resize and JSOP_INITELEM_ARRAY assumes all elements have been allocated).

Can RNewArray store the MNewArray::AllocationBehavior enum value, and then when we bailout we call NewInitArray if we're allocating and NewDenseUnallocatedArray if we're not?

Comment 12

[Nicolas B. Pierron [:nbp]]

(In reply to Jan de Mooij [:jandem] from comment #10)
> Comment on attachment 8461468 [details] [diff] [review]
> Part 1 - Detect when we can replace an Array by an ArrayState.
> 
> Review of attachment 8461468 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Looks good, r=me with comments addressed.
> 
> ::: js/src/jit/Recover.cpp
> @@ +1012,5 @@
> > +        Value val = iter.read();
> > +
> > +        if (index >= initLength) {
> > +            MOZ_ASSERT(val.isUndefined());
> > +            continue;
> 
> When does this happen? We don't optimize MStoreElement if the index >=
> |count| right? I'll r+ this patch assuming we can remove it but if we need
> the check we should discuss.

This is needed and tested by arrayInitBail0 and arrayInitBail1.  We need it for cases where the array is not completely initialized yet, especially in case of a GC.  We used to have similar bugs in array initializations and this is also the reason behind the implementation of MSetInitializedLength.  One of the problem we encountered was that a partially initialized array would let the GC traverses the full content of the array beyond what is currently initialized, which means that the GC was reading uninitialized memory.

Comment 13

[Nicolas B. Pierron [:nbp]]

Attachment: Part 1 - Detect when we can replace an Array by an ArrayState.

Delta:
 - Add upper bound for MArrayState.
 - Add IndexOf function to find the index of Load/Store element.

(Asking again for review, with nits applied, as the RArrayState::recover condition is mandatory)

Comment 14

[Nicolas B. Pierron [:nbp]]

Attachment: Part 2 - IonMonkey: Recover MNewArray.

Delta:
 - Carry the isAllocating flag over to the RNewArray.

Comment 15

[Nicolas B. Pierron [:nbp]]

https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=a1c841c6b3b0
https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=8a746c3e25be

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

Comment 16

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/eb591b79d451
https://hg.mozilla.org/mozilla-central/rev/9bdc7649cc78

Comment 17

[Benjamin Bouvier [:bbouvier] (inactive)]

This introduced a build warning:

/home/ben/code/moz/inbound/js/src/jit/ScalarReplacement.cpp: In function ‘bool js::jit::IsArrayEscaped(js::jit::MInstruction*)’:
/home/ben/code/moz/inbound/js/src/jit/ScalarReplacement.cpp:529:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (index < 0 || count <= index)
                                               ^
/home/ben/code/moz/inbound/js/src/jit/ScalarReplacement.cpp:550:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if (index < 0 || count <= index)

Comment 18

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Erase the warning

r+ from efaust on irc

Comment 19

[Benjamin Bouvier [:bbouvier] (inactive)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/7ed02a668784

Comment 20

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/7ed02a668784