774006 - IonMonkey: Implement SETELEM IC

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicolas B. Pierron [:nbp]]

Attachment: Reduced 3d-raytrace.

This may affect performances on sunspider 3d-raytrace.js because createVector function output may have an optional field.  The attached test case is used to measure the performance issue between JM and Ion.

Comment 1

[Bobby Holley (:bholley)]

Is this really a js-ctypes bug?

Comment 2

[Nicolas B. Pierron [:nbp]]

(In reply to Bobby Holley (:bholley) from comment #1)
> Is this really a js-ctypes bug?

Sorry, my mistake.

Comment 3

[Nicolas B. Pierron [:nbp]]

Attachment: Implement SetElementCache for dense arrays.

> Review not urgent. <

This fix the performance issue of the benchmark attached to this bug.  Unfortunately this patch is lacking the property case and slow down other benchmarks more than the improvement it provides.

This patch still fails with « --no-jm jit-test/tests/jaeger/bug709067.js »

Comment 4

[Nicolas B. Pierron [:nbp]]

js::SetObjectElement is called by the Ion Code ~530k times and it seems to have a monotone behaviour, determined by looking at the identical number of calls of each functions under js::SetObjectElement.

One function do a js_NativeSet (512k times — 19%).
Another function use a dense array (24k times — 1.20%) and need to realloc (21k times) the element vector to make it grow.

It might be interesting to add supports for adding property on native with SetElemICs.

Comment 5

[Nicolas B. Pierron [:nbp]]

These stats are extracted from kraken audio-beat-detection run under callgrind with JM+Ion.

(In reply to Nicolas B. Pierron [:pierron] from comment #4)
> js::SetObjectElement is called by the Ion Code ~530k times and it seems to
> have a monotone behaviour, determined by looking at the identical number of
> calls of each functions under js::SetObjectElement.
> 
> One function do a js_NativeSet (512k times — 19%).
> Another function use a dense array (24k times — 1.20%) and need to realloc
> (21k times) the element vector to make it grow.
> 
> It might be interesting to add supports for adding property on native with
> SetElemICs.

Comment 6

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 643973 [details] [diff] [review]
Implement SetElementCache for dense arrays.

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

This approach seems fine. You can probably remove code designed to handle the setprop case since that doesn't seem in our crosshairs yet.

Comment 7

[Hannes Verschore [:h4writer]]

I think this is causing a 30% slowdown on the linpack GWT benchmarks. Adding this would bring the performance of IM on par with baseline. So this should get into the tree.
Nicolas: should I rebase and finish it or will you do that?

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #7)
> I think this is causing a 30% slowdown on the linpack GWT benchmarks. Adding
> this would bring the performance of IM on par with baseline. So this should
> get into the tree.
> Nicolas: should I rebase and finish it or will you do that?

I think I can rebase it between 2 builds of b2g.  Can you give me the link of linpack GWT Benchmark?

Comment 9

[Alon Zakai (:azakai)]

GWT benchmarks are linked to here: https://bugzilla.mozilla.org/show_bug.cgi?id=870627#c0

Comment 10

[Nicolas B. Pierron [:nbp]]

Attachment: Implement SetElementIC.

This is the rebased version of the patch.  the check that I made on gwt seems to appear as being a bad perf hit.  GWT seems to suffer from a constant bailout at line 428.

To make the IC useful, I added support for property cache extracted from SetPropertyIC, and guard against the Value of the property (which should better be implemented with the compare string function provided by the macro assembler).

Sadly, even if the cache seems to be working for the function at line 499 of linpack gwt benchmark, it is penalized by the fact that we cannot create an inline cache for adding the third property which implies the increase of the dynamic slots.

I don't think the original patch is still relevant since the refactoring of the slots & elements of arrays.

Comment 11

[Hannes Verschore [:h4writer]]

Comment on attachment 752519 [details] [diff] [review]
Implement SetElementIC.

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

The dense ic got added, but we failed every lookup and got back into SetElementIC::update. Manually testing showed "index == 1" and "capacity == 1024". So no reason to fail back to the update. The checks in the asm code were fault. Upon updating those I get the following:

Linpack
Before patch: 15s
After patch + small fixes: 2s

Nice!

Note: I haven't looked if the other "attach" functions are correct. Please look at them closely and verify they indeed work ...

::: js/src/ion/IonCaches.cpp
@@ +2493,5 @@
> +        masm.unboxInt32(indexVal, intIndex());
> +
> +        // Guard that we can increase the initialized length.
> +        Address capacity(elements, ObjectElements::offsetOfCapacity());
> +        masm.branch32(Assembler::AboveOrEqual, capacity, intIndex(), &failAndPop);

masm.branch32(Assembler::BelowOrEqual, capacity, intIndex(), &failAndPop);

@@ +2497,5 @@
> +        masm.branch32(Assembler::AboveOrEqual, capacity, intIndex(), &failAndPop);
> +
> +        // Guard on the initialized length.
> +        Address initLength(elements, ObjectElements::offsetOfInitializedLength());
> +        masm.branch32(Assembler::Above, initLength, intIndex(), &failAndPop);

masm.branch32(Assembler::Below, initLength, intIndex(), &failAndPop);

@@ +2658,5 @@
> +    RootedShape shape(cx);
> +    RootedObject holder(cx);
> +    uint32_t oldSlots = obj->numDynamicSlots();
> +    RootedShape oldShape(cx, obj->lastProperty());
> +

Here we need to add a check to see if the cache is disabled and just do "SetObjectElement()". This is needed, since all code after this point, can take precious time. At the end of this function we need to disable the cache when we encounter this update too much, but still haven't added a stub. (See GetElementIC, I fixed this for GetElementIC, we don't want to reintroduce such a problem).

FYI that's also the reason why this patch (without the fixes) increased the time from 15s to 22s. Since we are doing more than when we would have done a MCallSetElement.

Comment 12

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #11)
> Comment on attachment 752519 [details] [diff] [review]
> Implement SetElementIC.
> 
> Review of attachment 752519 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> The dense ic got added, but we failed every lookup and got back into
> SetElementIC::update. Manually testing showed "index == 1" and "capacity ==
> 1024". So no reason to fail back to the update. The checks in the asm code
> were fault. Upon updating those I get the following:
> 
> Linpack
> Before patch: 15s
> After patch + small fixes: 2s
> 
> Nice!
> 
> Note: I haven't looked if the other "attach" functions are correct. Please
> look at them closely and verify they indeed work ...

I know they are exercised on the linpack gwt shell benchmark.  Removing these SetElem[String] caches cause the benchmark time to go from 3.15s to 3.25s on my computer.

Comment 13

[Nicolas B. Pierron [:nbp]]

Attachment: Implement SetElementIC. for integer indexes.

Same thing, without the property accesses, I opened a separated bug for the property accesses. (Bug 875137)

Comment 14

[Hannes Verschore [:h4writer]]

Comment on attachment 753023 [details] [diff] [review]
Implement SetElementIC. for integer indexes.

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

::: js/src/ion/IonCaches.cpp
@@ +2634,5 @@
> +
> +        masm.bind(&below);
> +
> +        // :TODO: add an emitPreBarrier because we can potentially erase a GC
> +        // object.

There is still a TODO here ...

Comment 15

[Nicolas B. Pierron [:nbp]]

Attachment: Implement SetElementIC for integer indexes.

delta:
- Add a test case made for ion-eager
- Bump the length if the it is under the initialized length.
- Add pre-barrier when we are modifying an initialize element.

Comment 16

[Hannes Verschore [:h4writer]]

Comment on attachment 753386 [details] [diff] [review]
Implement SetElementIC for integer indexes.

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

Nice, thanks for doing this!

::: js/src/ion/IonBuilder.cpp
@@ +6541,5 @@
>          return abort("Type is not definitely lazy arguments.");
>  
> +    // Check if only objects are manipulated valid index, and generate a SetElementCache.
> +    do {
> +        if (object->type() != MIRType_Object)

We currently use the following in IonBuilder, before typePolicy is run. (Because it checks type() and resultTypeSet():
object->mightBeType(MIRType_Object);

=> same for the others

@@ +6555,5 @@
> +        current->add(ins);
> +        current->push(value);
> +
> +        return resumeAfter(ins);
> +    } while (false);

I'm not convinced we need a "do {} while()" here.
What about (based on getelemcache):

bool cachable = true;

if (!object->mightBeType(MIRType_Object))
    cachable = false;

if (!index->mightByType(MIRType_Value) ||
    !index->mightByType(MIRType_Int32) ||
    !index->mightByType(MIRType_String))
{
    cachable = false;
}

MInstruction *ins;
if (cachable)
     ins = MSetElementCache::New(object, index, value, script()->strict);
else
     ins = MCallSetElement::New(object, index, value);

current->add(ins);
current->push(value);

return resumeAfter(ins);

::: js/src/ion/IonCaches.cpp
@@ +1542,5 @@
>      RepatchIonCache::reset();
>      hasArrayLengthStub_ = false;
>      hasTypedArrayLengthStub_ = false;
> +    hasStrictArgumentsLengthStub_ = false;
> +    hasNormalArgumentsLengthStub_ = false;

I assume this is just leftovers from splitting the patch and should get in the other patch.

@@ +2561,5 @@
>  {
>      RepatchIonCache::reset();
>      hasDenseStub_ = false;
> +    hasStrictArgumentsStub_ = false;
> +    hasNormalArgumentsStub_ = false;

I assume this is just leftovers from splitting the patch and should get in the other patch.

@@ +2602,5 @@
> +    masm.branchTestInt32(Assembler::NotEqual, indexVal, &failures);
> +
> +    // Load elements vector.
> +    masm.push(object());
> +    Label outOfBounds; // index >= capacity || index > initialized length

OOOh, please put this label nexto "Label failures". This is the worst place, since accolades are just opening here. So it looks like that is the OutOfBound case...

@@ +2612,5 @@
> +        Register elements = object();
> +        masm.loadPtr(Address(object(), JSObject::offsetOfElements()), elements);
> +
> +        // Unbox the index.
> +        masm.unboxInt32(indexVal, intIndex());

There is a trick we can do here (in that case rename intIndex to scratch!!!!):

Register index = masm.extractInt32(indexVal, scratch);

=> This enables us to not having to push (on x86 and arm):

// Get a register to store the elements
Register elements = scratch;
if (scratch == index) {
    masm.push(object());
    elements = object();
}

masm.loadPtr(Address(object(), JSObject::offsetOfElements()), elements);

...

@@ +2622,5 @@
> +        // Guard on the initialized length.
> +        Address initLength(elements, ObjectElements::offsetOfInitializedLength());
> +        masm.branch32(Assembler::Below, initLength, intIndex(), &outOfBounds);
> +        masm.branch32(Assembler::NotEqual, initLength, intIndex(), &replaceElem);
> +        // push: index == initialized length

Not sure what this comment says.

But can you make it a bit more clear this codegen is split into three parts:

// Increase InitLength
masm.jump(storeNewElem);

// Mark old element
masm.jump(storeNewElem);

// Store new element
Label.bind(storeNewElem)


Currently the label replaceElem is misleading, since you expect it to remove and put the new value in. But it only does the marking.

::: js/src/ion/IonCaches.h
@@ +512,5 @@
>          allowGetters_(allowGetters),
>          hasArrayLengthStub_(false),
> +        hasTypedArrayLengthStub_(false),
> +        hasStrictArgumentsLengthStub_(false),
> +        hasNormalArgumentsLengthStub_(false)

I assume this is just leftovers from splitting the patch and should get in the other patch.

@@ +633,5 @@
>          output_(output),
>          monitoredResult_(monitoredResult),
>          hasDenseStub_(false),
> +        hasStrictArgumentsStub_(false),
> +        hasNormalArgumentsStub_(false),

I assume this is just leftovers from splitting the patch and should get in the other patch.

::: js/src/ion/LIR-Common.h
@@ +3989,5 @@
> +        return getOperand(0);
> +    }
> +    const LDefinition *intIndex() {
> +        return getTemp(0);
> +    }

s/intIndex/temp/
Using intIndex here is very confusing. In Codegen you still can do: Register intIndex = ToRegister(lir->temp()). Or just keep the 'temp' name...

@@ +4017,5 @@
> +        return getOperand(1);
> +    }
> +    const LDefinition *intIndex() {
> +        return getTemp(0);
> +    }

same: s/intIndex/temp/

::: js/src/ion/MIR.h
@@ +6326,5 @@
>      }
>  };
>  
> +class MSetElementInstruction
> +  : public MAryInstruction<3>

MTernaryInstruction

@@ +6328,5 @@
>  
> +class MSetElementInstruction
> +  : public MAryInstruction<3>
> +{
> +    bool strict_;

Move this to the MSetElementCache class, since MCallSetElement doesn't use that variable...

@@ +6442,5 @@
> +  public:
> +    INSTRUCTION_HEADER(SetElementCache);
> +
> +    static MSetElementCache *New(MDefinition *obj, MDefinition *index, MDefinition *value,
> +                                 bool strict) {

newline before {

Comment 17

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #16)
> ::: js/src/ion/IonCaches.h
> @@ +512,5 @@
> >          allowGetters_(allowGetters),
> >          hasArrayLengthStub_(false),
> > +        hasTypedArrayLengthStub_(false),
> > +        hasStrictArgumentsLengthStub_(false),
> > +        hasNormalArgumentsLengthStub_(false)
> 
> I assume this is just leftovers from splitting the patch and should get in
> the other patch.

No, this is some uninitialized bits which will just create some random deoptimizations.

> @@ +633,5 @@
> >          output_(output),
> >          monitoredResult_(monitoredResult),
> >          hasDenseStub_(false),
> > +        hasStrictArgumentsStub_(false),
> > +        hasNormalArgumentsStub_(false),
> 
> I assume this is just leftovers from splitting the patch and should get in
> the other patch.

Yes, it is.

Comment 18

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #16)
> @@ +6555,5 @@
> > +        current->add(ins);
> > +        current->push(value);
> > +
> > +        return resumeAfter(ins);
> > +    } while (false);
> 
> I'm not convinced we need a "do {} while()" here.
> What about (based on getelemcache):
> 
> bool cachable = true;
> 
> if (!object->mightBeType(MIRType_Object))
>     cachable = false;
> 
> if (!index->mightByType(MIRType_Value) ||
>     !index->mightByType(MIRType_Int32) ||
>     !index->mightByType(MIRType_String))
> {
>     cachable = false;
> }
> 
> MInstruction *ins;
> if (cachable)
>      ins = MSetElementCache::New(object, index, value, script()->strict);
> else
>      ins = MCallSetElement::New(object, index, value);
> 
> current->add(ins);
> current->push(value);
> 
> return resumeAfter(ins);

The do-while style is not needed but looks closer to the jsop_getprop style, which is desirable.  So If you don't mind I will keep it as it gives a scope to the cache-strategy.  As default to have a big clean-up, we should progressively migrate the MIR generation to the d-while strategy style, and then to the strategy functions.

Not having a scope makes things harder to understand as nothing is tied to the MIR generation, so you don't have a clear view of the hypothesis used before the MIR generation.

Comment 19

[Nicolas B. Pierron [:nbp]]

(In reply to Nicolas B. Pierron [:nbp] from comment #17)
> (In reply to Hannes Verschore [:h4writer] from comment #16)
> > @@ +633,5 @@
> > >          output_(output),
> > >          monitoredResult_(monitoredResult),
> > >          hasDenseStub_(false),
> > > +        hasStrictArgumentsStub_(false),
> > > +        hasNormalArgumentsStub_(false),
> > 
> > I assume this is just leftovers from splitting the patch and should get in
> > the other patch.
> 
> Yes, it is.

No, it is also a fix of GetElementIC.

Comment 20

[Nicolas B. Pierron [:nbp]]

Attachment: Implement SetElementIC for integer indexes.

Delta:
 - Apply non-commented nits.

Comment 21

[Hannes Verschore [:h4writer]]

Comment on attachment 753907 [details] [diff] [review]
Implement SetElementIC for integer indexes.

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

Looks good!

::: js/src/ion/IonCaches.cpp
@@ +2613,5 @@
> +        if (scratch == index) {
> +            masm.push(object());
> +            elements = object();
> +        }
> +        masm.loadPtr(Address(object(), JSObject::offsetOfElements()), elements);

Put the comment on masm.loadPtr and 
add comment "//If needed push a register to store elements" above

@@ +2656,5 @@
> +        }
> +        masm.bind(&storeElem);
> +
> +        // Store the value.
> +        masm.storeConstantOrRegister(value(), target);

Put the "storeElem" binding under the "// store the value" comment

::: js/src/ion/IonCaches.h
@@ +699,5 @@
> +    bool hasDenseStub_ : 1;
> +
> +    size_t failedUpdates_;
> +
> +    static const size_t MAX_FAILED_UPDATES;

failedUpdate_ and MAX_FAILED_UPDATES aren't used in this patch (possible needed in the other bug)

@@ +758,5 @@
> +    }
> +    bool shouldDisable() const {
> +        return !canAttachStub() ||
> +               (stubCount_ == 0 && failedUpdates_ > MAX_FAILED_UPDATES);
> +    }

incFailedUpdates, resetFailedUpdates and shouldDisable aren't used. (I assume you will have to add these in the other bug, but here not ...)

Comment 22

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #16)
> if (!index->mightByType(MIRType_Value) ||
>     !index->mightByType(MIRType_Int32) ||
>     !index->mightByType(MIRType_String))
> {
>     cachable = false;
> }

Just for the note, we guard that we don't pass MIRType_Value as argument of mightBeType().

Comment 23

[Nicolas B. Pierron [:nbp]]

http://hg.mozilla.org/integration/mozilla-inbound/rev/3835cbed5915

Comment 24

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/3835cbed5915