1137688 - Eagerly remove boxed SIMD value-types across Phi nodes.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Nicolas B. Pierron [:nbp]]

The goal of this optimizations is to ensure that if we are using SIMD values, then we are the least likely to allocate a SIMD objects.  This is based on the assumption that SIMD code would most likely be monomorphic.

Not making this assumption, implies that we would have to keep MIRType_Object Phi nodes, even if the Phi node is unboxed, and even if all operands are boxed.  The problem can also happen if not all operands are SimdBox instructions such as:
 - With an OSR entry block
 - With a non-inlined infrequent function call.

Also note, that the best solution is to replace the Phi node in-place, as this prevents remembering the modified set of Phi instructions, but this implies adding additional MSimdBox to feed the entry resume point.

Duplicating the Phi node (as attempt previously) is the right approach in general, but it add more register pressure as we are not yet capable of recovering Phi instructions for the moment.  As SIMD are value-types, we can safely eagerly unbox and re-box for the ResumePoints, as we are not supposed to be able to distinguish the object identity.  The boxing instruction is then likely to be removed by the Sink phase, which will flag it as being a recover instruction if it is unused (or even move it inside branches once we re-enable this part of the Sink phase).

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Add eager simd unboxing phase.

I tested this patch on top of the folded patch for mandelbrot instructions
and increased the number of iterations.  I got a 33% speed-up with this patch.

Comment 2

[Nicolas B. Pierron [:nbp]]

Note, that with the folded patch, there is still one MSimdBox which remains in the loop because Int32x4.check is not implemented yet, as it use the boxed type of the Phi and that the Sink phase is disabled for the moment, we do not get all the performance that we should expect.

I can either go and fix the Sink phase, which would be better for the long term, or just do it in the eager simd unbox phase.

Comment 3

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8570661 [details] [diff] [review]
Add eager simd unboxing phase.

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

Missing files and stuff in this patch.

::: js/src/jit/CodeGenerator.cpp
@@ +4425,5 @@
> +CodeGenerator::captureSimdTemplate(JSContext *cx)
> +{
> +    BitSet types(simdRefreshTemplatesDuringLink_);
> +    JitCompartment *jitCompartment = cx->compartment()->jitCompartment();
> +    for (BitSet::Iterator i(types); i; ++i) {

This iterates over a bitset which hasn't been initialized...

@@ +4428,5 @@
> +    JitCompartment *jitCompartment = cx->compartment()->jitCompartment();
> +    for (BitSet::Iterator i(types); i; ++i) {
> +        SimdTypeDescr::Type type = SimdTypeDescr::Type(*i);
> +        JSObject *templateObject = jitCompartment->maybeGetSimdTemplateObjectFor(type);
> +        InlineTypedObject *inlineTypedObject = &templateObject->as<InlineTypedObject>();

Can't it be a null dereference? The "maybe" in the above method name suggests that it can return null.

@@ +4434,5 @@
> +        jitCompartment->getSimdTemplateObjectFor(cx, descr);
> +    }
> +}
> +
> +

nit: 2 blank lines, please remove one

::: js/src/jit/CodeGenerator.h
@@ +483,5 @@
> +    // CodeGenerator::link.
> +    //
> +    // Instead of saving the pointers, we just save the index of the Read
> +    // Barriered objects in a bit mask.
> +    uint32_t simdRefreshTemplatesDuringLink_;

Where is this initialized?

@@ +486,5 @@
> +    // Barriered objects in a bit mask.
> +    uint32_t simdRefreshTemplatesDuringLink_;
> +
> +    void registerSimdTemplate(InlineTypedObject *templateObject);
> +    void captureSimdTemplate(JSContext *cx);

this function is unused in this patch

::: js/src/jit/Ion.cpp
@@ +18,5 @@
>  #include "jit/BaselineFrame.h"
>  #include "jit/BaselineInspector.h"
>  #include "jit/BaselineJIT.h"
>  #include "jit/CodeGenerator.h"
> +#include "jit/EagerSimdUnbox.h"

Where is it?

::: js/src/jit/MIR.h
@@ +2996,5 @@
>      {
>          MOZ_ASSERT(IsSimdType(op->type()));
>          setMovable();
>          setResultType(MIRType_Object);
> +        if (constraints)

In which case don't we have constraints?

::: js/src/jit/ValueNumbering.cpp
@@ +729,5 @@
> +    // Skip optimizations on instructions which are recovered on bailout, to
> +    // avoid mixing instructions which are recovered on bailouts with
> +    // instructions which are not.
> +    if (def->isRecoveredOnBailout())
> +        return true;

I'm afraid I don't know enough about our GVN to be able to say whether this is fine or not. Please ask for review to somebody else for this particular change.

Comment 4

[Nicolas B. Pierron [:nbp]]

Attachment: Add eager simd unboxing phase.

Delta:
 - Add jit/EagerSimdUnbox.{cpp,h}

Comment 5

[Nicolas B. Pierron [:nbp]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #3)
> ::: js/src/jit/MIR.h
> @@ +2996,5 @@
> >      {
> >          MOZ_ASSERT(IsSimdType(op->type()));
> >          setMovable();
> >          setResultType(MIRType_Object);
> > +        if (constraints)
> 
> In which case don't we have constraints?

We cannot add any TypeSet constraints after IonBuilder.
And this is used as part of EagerSimdUnbox, for creating MSimdBox without a corresponding Baseline allocation.

> ::: js/src/jit/ValueNumbering.cpp
> @@ +729,5 @@
> > +    // Skip optimizations on instructions which are recovered on bailout, to
> > +    // avoid mixing instructions which are recovered on bailouts with
> > +    // instructions which are not.
> > +    if (def->isRecoveredOnBailout())
> > +        return true;
> 
> I'm afraid I don't know enough about our GVN to be able to say whether this
> is fine or not. Please ask for review to somebody else for this particular
> change.

Comment 6

[Nicolas B. Pierron [:nbp]]

Attachment: Add eager simd unboxing phase.

Delta:
 - Initialize simdRefreshTemplatesDuringLink_
 - Remove useless BitSet::iterator (why should we allocate anything)
 - Call captureSimdTemplate, and comment about maybeGet.
 - Fix registerSimdTemplate to make a simd-type bit mask.
 - Fix EagerSimdUnbox, to insert the recover instruction before other
 recover instructions (such as MObjectState in complex-4.js)

r? sunfish for GVN.  Not doing the GVN of recover instruction is not a big
deal for the moment, otherwise we should do it within recover instructions
and have the isRecoveredOnBailout bit be part of the value hash.

Comment 7

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8571346 [details] [diff] [review]
Add eager simd unboxing phase.

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

Sorry for being very nitpicky with comments, but I mostly use them to understand code, and that's why i give them a lot of attention...

The patch looks good.  However, I'm cancelling review, I would like to see the questions below answered, to be sure that I understand everything, especially with respect to phis having phis inputs.

::: js/src/jit/CodeGenerator.cpp
@@ +4430,5 @@
> +        uint32_t typeIndex = mozilla::CountTrailingZeroes32(simdRefreshTemplatesDuringLink_);
> +        simdRefreshTemplatesDuringLink_ ^= 1 << typeIndex;
> +
> +        SimdTypeDescr::Type type = SimdTypeDescr::Type(typeIndex);
> +        // Note: the returned pointer should be non-null as we either captured

nit: new line before multi-line comment

Also, can you use 'register' instead of 'capture' in this sentence, so that it refers to the previously defined function right above?

@@ +4432,5 @@
> +
> +        SimdTypeDescr::Type type = SimdTypeDescr::Type(typeIndex);
> +        // Note: the returned pointer should be non-null as we either captured
> +        // it during IonBuilder, otherwise we guard before using it in
> +        // EagerSimdUnbox phase.

nit: +the

@@ +4436,5 @@
> +        // EagerSimdUnbox phase.
> +        JSObject *templateObject = jitCompartment->maybeGetSimdTemplateObjectFor(type);
> +        InlineTypedObject *inlineTypedObject = &templateObject->as<InlineTypedObject>();
> +        Rooted<SimdTypeDescr *> descr(cx, &inlineTypedObject->typeDescr().as<SimdTypeDescr>());
> +        jitCompartment->getSimdTemplateObjectFor(cx, descr);

As stated on irc: the sole purpose of these few lines is to execute the read barrier in getSimdTemplateObjectFor.  Feel free to make a new variant of getSimdTemplateObjectFor that receives a SimdTypeDescr::Type argument and switches over it to choose the right typeDescr for creating the template object, that will spare a few lines of code here.

@@ +7412,5 @@
>      RootedScript script(cx, gen->info().script());
>      OptimizationLevel optimizationLevel = gen->optimizationInfo().level();
>  
> +    // Capture the SIMD template objects which are used during the
> +    // compilation. This iterate over the template objects, using read-barriers

nit: iterates

@@ +7413,5 @@
>      OptimizationLevel optimizationLevel = gen->optimizationInfo().level();
>  
> +    // Capture the SIMD template objects which are used during the
> +    // compilation. This iterate over the template objects, using read-barriers
> +    // to let the GC know that the generated code rely on these template

nit: relies

::: js/src/jit/EagerSimdUnbox.cpp
@@ +13,5 @@
> +namespace js {
> +namespace jit {
> +
> +static SimdTypeDescr::Type
> +SimdTypeDescrToMIRType(MIRType type)

The name says the opposite of what it does

@@ +25,5 @@
> +    MOZ_CRASH("unexpected MIRType");
> +}
> +
> +// Do not optimize any Phi instruction which has conflicting Unbox operations,
> +// as this might implies some intended polymorphism.

nit: imply

@@ +31,5 @@
> +CanUnboxSimdPhi(const JitCompartment *jitCompartment, MPhi *phi, MIRType unboxType)
> +{
> +    MOZ_ASSERT(phi->type() == MIRType_Object);
> +
> +    for (MUseDefIterator use(phi); use; use++) {

If my comment below about iterating over the resume point's operands isn't valid, is there any way you could merge the two loops of this function? (by using use->isDefinition())

@@ +32,5 @@
> +{
> +    MOZ_ASSERT(phi->type() == MIRType_Object);
> +
> +    for (MUseDefIterator use(phi); use; use++) {
> +        if (use.def()->isUnbox() && use.def()->toUnbox()->type() != MIRType_Object)

According to the comment in MUnbox's ctor, if use.def()->isUnbox(), *then* the unbox type has to be different from MIRType_Object.  Is that correct at this point? If so, can you morph the second part of the condition into an MOZ_ASSERT inside the if body?

@@ +39,5 @@
> +        if (use.def()->isSimdUnbox() && use.def()->toSimdUnbox()->type() != unboxType)
> +            return false;
> +    }
> +
> +    // If we are unboxing, we are more than likely to have box this SIMD type

nit: boxed

@@ +42,5 @@
> +
> +    // If we are unboxing, we are more than likely to have box this SIMD type
> +    // once in baseline, otherwise, we cannot create an MSimdBox as we have no
> +    // template object to use.
> +    if (!jitCompartment->maybeGetSimdTemplateObjectFor(SimdTypeDescrToMIRType(unboxType)))

Can we have this check at the top of this function, before the loop, for performance reasons?

@@ +46,5 @@
> +    if (!jitCompartment->maybeGetSimdTemplateObjectFor(SimdTypeDescrToMIRType(unboxType)))
> +        return false;
> +
> +    // If we cannot recover the Simd object at the entry of the basic block,
> +    // then we would have to produce box the content any way.

nit: s/produce//, and i think "any way" => "anyways"

@@ +48,5 @@
> +
> +    // If we cannot recover the Simd object at the entry of the basic block,
> +    // then we would have to produce box the content any way.
> +    MResumePoint *entry = phi->block()->entryResumePoint();
> +    for (MUseIterator i(phi->usesBegin()), e(phi->usesEnd()); i != e; i++) {

Any reason to prefer this rather than iterating over the resume point's operands? Not that I am asking for a change here, just trying to understand whether there was a preferred choice or not, and if there was one, why.

@@ +97,5 @@
> +                use->replaceProducer(recoverBox);
> +                continue;
> +            }
> +        } else {
> +            MOZ_ASSERT(ins->isResumePoint());

Well, isDefinition() == !isResumePoint() :) I appreciate it for documentation here, but the ins->toResumePoint() below seems sufficient, what do you think?

@@ +106,5 @@
> +        }
> +
> +        if (!box) {
> +            box = MSimdBox::New(alloc, nullptr, phi, inlineTypedObject, gc::DefaultHeap);
> +            phiBlock->insertBefore(at, box);

Please check my understanding: if a phi has another phi input from the same block, the loop iterating over the phi operands will insert a MSimdUnbox first, then we'll introduce a MSimdBox here? So we would still be boxing/unboxing in the loop?

For instance, there will still be one box in the loop body in this sequence (checked with iongraph and your patch)

function f() {
    var i4 = SIMD.int32x4(1,2,3,4);
    for (var i = 0; i++ < 1001;)
        i4 = SIMD.int32x4(i4.x, 2, 3, 4);
    return SIMD.int32x4.check(i4);
}

for (var i = 0; i++ < 1001;)
    f();

::: js/src/jit/EagerSimdUnbox.h
@@ +3,5 @@
> + * This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +// This file declares eager Simd unboxing.

minor nit: we use Simd in code, SIMD in comments, but that's not a big deal :)

::: js/src/jit/IonOptimizationLevels.h
@@ +60,5 @@
>  
>      // Toggles whether native scripts get inlined.
>      bool inlineNative_;
>  
>      // Toggles whether global value numbering is used.

nit: copy pasto here

::: js/src/vm/TraceLogging.cpp
@@ +675,5 @@
>          enabledTextIds[TraceLogger_SplitCriticalEdges] = true;
>          enabledTextIds[TraceLogger_RenumberBlocks] = true;
>          enabledTextIds[TraceLogger_DominatorTree] = true;
>          enabledTextIds[TraceLogger_PhiAnalysis] = true;
> +        enabledTextIds[TraceLogger_ScalarReplacement] = true;

good catch

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #7)
> @@ +48,5 @@
> > +
> > +    // If we cannot recover the Simd object at the entry of the basic block,
> > +    // then we would have to produce box the content any way.
> > +    MResumePoint *entry = phi->block()->entryResumePoint();
> > +    for (MUseIterator i(phi->usesBegin()), e(phi->usesEnd()); i != e; i++) {
> 
> Any reason to prefer this rather than iterating over the resume point's
> operands? Not that I am asking for a change here, just trying to understand
> whether there was a preferred choice or not, and if there was one, why.

Yes, we might have to add other uses than resume points here.

> @@ +31,5 @@
> > +CanUnboxSimdPhi(const JitCompartment *jitCompartment, MPhi *phi, MIRType unboxType)
> > +{
> > +    MOZ_ASSERT(phi->type() == MIRType_Object);
> > +
> > +    for (MUseDefIterator use(phi); use; use++) {
> 
> If my comment below about iterating over the resume point's operands isn't
> valid, is there any way you could merge the two loops of this function? (by
> using use->isDefinition())

Ok, I'll do that.

> @@ +32,5 @@
> > +{
> > +    MOZ_ASSERT(phi->type() == MIRType_Object);
> > +
> > +    for (MUseDefIterator use(phi); use; use++) {
> > +        if (use.def()->isUnbox() && use.def()->toUnbox()->type() != MIRType_Object)
> 
> According to the comment in MUnbox's ctor, if use.def()->isUnbox(), *then*
> the unbox type has to be different from MIRType_Object.  Is that correct at
> this point? If so, can you morph the second part of the condition into an
> MOZ_ASSERT inside the if body?

MUnbox is used to unbox a MIRType_Value to one of the enumerated one below
https://dxr.mozilla.org/mozilla-central/source/js/src/jit/MIR.h?from=MUnbox#4084-4089

Including MIRType_Object.  However, if the Unbox does not unbox to a MIRType_Object, then the likelyhood of having a SIMD value-object is 0.

> @@ +42,5 @@
> > +
> > +    // If we are unboxing, we are more than likely to have box this SIMD type
> > +    // once in baseline, otherwise, we cannot create an MSimdBox as we have no
> > +    // template object to use.
> > +    if (!jitCompartment->maybeGetSimdTemplateObjectFor(SimdTypeDescrToMIRType(unboxType)))
> 
> Can we have this check at the top of this function, before the loop, for
> performance reasons?

Yes, it used to be here because I first wrote this function without the MIRType unboxType argument first.

> @@ +97,5 @@
> > +                use->replaceProducer(recoverBox);
> > +                continue;
> > +            }
> > +        } else {
> > +            MOZ_ASSERT(ins->isResumePoint());
> 
> Well, isDefinition() == !isResumePoint() :) I appreciate it for
> documentation here, but the ins->toResumePoint() below seems sufficient,
> what do you think?

I totally agree.

> @@ +106,5 @@
> > +        }
> > +
> > +        if (!box) {
> > +            box = MSimdBox::New(alloc, nullptr, phi, inlineTypedObject, gc::DefaultHeap);
> > +            phiBlock->insertBefore(at, box);
> 
> Please check my understanding: if a phi has another phi input from the same
> block, the loop iterating over the phi operands will insert a MSimdUnbox
> first, then we'll introduce a MSimdBox here? So we would still be
> boxing/unboxing in the loop?

Yes, but this will be removed by GVN.  This is a naive implementation, but at the same time handling all these cases within this transformation phase would add extra complexity that I am just willing to have more allocation at compile time for the moment.

Comment 9

[Dan Gohman [:sunfish]]

Comment on attachment 8571346 [details] [diff] [review]
Add eager simd unboxing phase.

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

The GVN part looks fine to me. Ignoring recovered-on-bailout instructions in gvn seems perfectly reasonable.

Comment 10

[Nicolas B. Pierron [:nbp]]

Attachment: func01-pass21-Bounds Check Elimination-mir.gv.png

Not having .check, nor .x in my tree yet, I tested with:

function f() {
    var i4 = SIMD.int32x4(1,2,3,4);
    for (var i = 0; i++ < 1001;)
        i4 = SIMD.int32x4(i, 2, 3, 4);
    return SIMD.int32x4.add(i4, i4);
}

for (var i = 0; i++ < 1001;)
    f();

Indeed, there is a MSimdBox in the loop, but it is recovered on bailout, and used by 2 resume points.

So, maybe there is a problem with .check, or a problem with .x implementation.

Comment 11

[Nicolas B. Pierron [:nbp]]

Attachment: Add eager simd unboxing phase.

Carry on sunfish's review+.
Delta:
 - Apply comments and nits.

Comment 12

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8571495 [details] [diff] [review]
Add eager simd unboxing phase.

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

Thanks for the modifications, that makes the patch clearer and somehow simpler.

::: js/src/jit/EagerSimdUnbox.cpp
@@ +48,5 @@
> +        if (!(*i)->consumer()->isDefinition())
> +            continue;
> +
> +        MDefinition *def = (*i)->consumer()->toDefinition();
> +        if (def->isUnbox() && def->toUnbox()->type() != MIRType_Object)

Please double check my understanding here: def is an Unbox consuming the phi; the phi has the type MIRType_Object, as asserted above. There is this in the MUnbox ctor:

        // Only allow unboxing a non MIRType_Value when input and output types
        // don't match. This is often used to force a bailout. Boxing happens
        // during type analysis.
        MOZ_ASSERT_IF(ins->type() != MIRType_Value, type != ins->type());

so as ins->type() == MIRType_Object here (assertion above), we should be sure that type (namely def->toUnbox()->type()) is different from ins->type() (namely MIRType_Object). As a matter of fact, I think the second condition in the |if| is tautological. Any way to change it into a MOZ_ASSERT in the if body, please?

@@ +74,5 @@
> +
> +    // Change the MIRType of the Phi.
> +    phi->setResultType(unboxType);
> +
> +    // Add an MSimdBox, and replace all the Phi uses with it.

this comment applies a few lines below, above the definition of templateObject

@@ +99,5 @@
> +                use->replaceProducer(recoverBox);
> +                continue;
> +            }
> +        } else {
> +            if (ins->toResumePoint()->isRecoverableOperand(use)) {

you can merge the else and the if into an "else if"

@@ +144,5 @@
> +
> +} /* namespace jit */
> +} /* namespace js */
> +
> +

nit: too many blank lines here

Comment 13

[Nicolas B. Pierron [:nbp]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #12)
> ::: js/src/jit/EagerSimdUnbox.cpp
> @@ +48,5 @@
> > +        if (!(*i)->consumer()->isDefinition())
> > +            continue;
> > +
> > +        MDefinition *def = (*i)->consumer()->toDefinition();
> > +        if (def->isUnbox() && def->toUnbox()->type() != MIRType_Object)
> 
> Please double check my understanding here: def is an Unbox consuming the
> phi; the phi has the type MIRType_Object, as asserted above.

Oh, right.
I will remove this condition from this patch and make a follow-up patch to one extra corner case.

Comment 14

[Nicolas B. Pierron [:nbp]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/703cef22656c

Comment 15

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8571490 [details]
func01-pass21-Bounds Check Elimination-mir.gv.png

For the record, we've analyzed this on irc: SIMD check is inlined as a SimdUnbox that pushes back its input. As the checked value is returned, the input of the SimdUnbox is used, and as a matter of fact, a SimdBox is introduced in the loop.

The Sink phase would be able to put the SimdBox closer to its use (in the loop exit block), were it active.  Another solution would be to push a SimdBox instead of the input, when inlining check.

Comment 16

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/703cef22656c