Bug 208664 – Allow deleteById to be cached in the DFG

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Justin Michaud]

Allow deleteById to be cached in the DFG

[Justin Michaud]

Created attachment 392619 [details]
Patch

[Justin Michaud]

Created attachment 392621 [details]
Patch

[Justin Michaud]

Created attachment 392768 [details]
Patch

[Justin Michaud]

Created attachment 393045 [details]
Patch

[Caio Lima]

Comment on attachment 393045 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=393045&action=review

Informal review. Overall LGTM. I left some comments below.

> Source/JavaScriptCore/bytecode/DeleteByIdVariant.h:45
> +        CacheableIdentifier, bool result,

I think it would be clearer for users of this class to receive `AccessCase::AccessType` instead of `bool result` directly. Then the constructor could properly sent `m_result` from this input. IIUC, it could be `m_result(accessType == AccessCase::Delete || accessType == AccessCase::DeleteMiss)`.

> Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:123
> +                DeleteByIdVariant variant(access.identifier(), access.type() == AccessCase::DeleteMiss ? true : false, structure, nullptr, invalidOffset);

Here we would only call `DeleteByIdVariant variant(access.identifier(), access.type(), structure, nullptr, invalidOffset);`.

> Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:135
> +                DeleteByIdVariant variant(access.identifier(), true, structure, newStructure, access.offset());

And here we would have `DeleteByIdVariant variant(access.identifier(), AccessCase::Delete, structure, newStructure, access.offset())`.

[Justin Michaud]

Created attachment 393428 [details]
Patch

[Saam Barati]

Comment on attachment 393428 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=393428&action=review

Mostly LGTM, but I think I found a couple legitimate bugs

> Source/JavaScriptCore/ChangeLog:10
> +        creating a new node, FilterDeleteByStatus, and then turning these DeleteById nodes into a FilterDeleteByStatus,
> +        CheckStructure, PutByOffset, then PutStructure. The logic for pessimising this optimization is the same as for 

or just CheckStructure in the case of a miss delete, right?

> Source/JavaScriptCore/ChangeLog:14
> +        This also adds a MultiDeleteByOffset node, for the case when there are multiple structures seen by the delete.

If they're all misses, do you still just emit a CheckStructure?

> Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:112
> +            if (access.viaProxy())
> +                return DeleteByStatus(JSC::slowVersion(summary), *stubInfo);

does this work currently in the IC? Like deleting via window proxy?

> Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:115
> +            if (access.usesPolyProto())
> +                return DeleteByStatus(JSC::slowVersion(summary), *stubInfo);

is this even possible? Delete doesn't do anything on the prototype chain. Seems like it should be an assert or just drop the line entirely

> Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:131
> +                ASSERT_UNUSED(offset, offset == access.offset());

how is this correct if we fail to find the transition?

> Source/JavaScriptCore/bytecode/DeleteByStatus.h:85
> +    bool finalize(VM&) { return true; }

this looks super wrong :-)

What if your variants structures aren't marked?

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:4651
> +        for (const DeleteByIdVariant& variant : deleteByStatus.variants()) {
> +            m_graph.registerStructure(variant.oldStructure());
> +            if (variant.newStructure())
> +                m_graph.registerStructure(variant.newStructure());
> +        }
> +
> +        MultiDeleteByOffsetData* data = m_graph.m_multiDeleteByOffsetData.add();
> +        data->variants = deleteByStatus.variants();
> +        data->identifierNumber = identifierNumber;
> +        set(destination,
> +            addToGraph(MultiDeleteByOffset, OpInfo(data), base));

if all of these are delete misses (and all either the non-configurable or the configurable kind), can we just turn this into a CheckStructure followed by "true" or "false" ? Seems like that's more efficient for other analyses

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:6030
> +            handleDeleteById(bytecode.m_dst, base, identifierNumber, deleteByStatus);

what about delete by val when the identifier is monotonic? If you don't do that in this patch, please file a bug to do it. (You can see what we do for get_by_val)

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1345
> +        addBaseCheck(indexInBlock, node, baseValue, m_graph.registerStructure(variant.oldStructure()));

this seems to indicate we must be exitOK to begin with

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1350
> +            node->origin.exitOK = false;

nit: we usually write this as:
node->origin = node->origin.withInvalidExit()

But, that said, why has our origin changed at all? Seems like we should just maintain if we're safe or not safe to exit, right?

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1373
> +        m_insertionSet.insertNode(
> +            indexInBlock, SpecNone, PutByOffset, origin.withInvalidExit(), OpInfo(&data), propertyStorage, node->child1(), Edge(clearValue));

This seems like it should maintain the same origin

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1376
> +        m_insertionSet.insertNode(
> +            indexInBlock, SpecNone, PutStructure, origin.withInvalidExit(), OpInfo(transition),
> +            node->child1());

and this seems like it should be exit invalid (as you have), since the store above invalidates exit state if we were safe to exit

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1378
> +        node->origin.exitOK = false;

nit: should be origin = origin.withInvalidExit()

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8132
> +        int missConfigurable = 0;
> +        int missNonconfigurable = 0;

size_t or unsigned

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8134
> +        for (unsigned i = data.variants.size(); i--;) {

size_t or unsigned

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8144
> +        int uniqueCaseCount = data.variants.size();

size_t or unsigned

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8150
> +        int trueBlock = missConfigurable ? uniqueCaseCount - 1 : -1;
> +        int falseBlock = missNonconfigurable ? uniqueCaseCount - 1 - !!missConfigurable : -1;

nit: Optional<size_t> or Optional<unsigned>

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8200
> +            results.append(m_out.anchor(variant.result() ? m_out.intPtrOne : m_out.intPtrZero));

This is wrong for booleans. We expect them to be i32. I wonder why nothing is actually crashing because of this in validation.

Anyways, you want m_out.booleanTrue and m_out.booleanFalse

If you do some math on your boolean result in js, I bet you trigger some validation errors

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8207
> +            results.append(m_out.anchor(m_out.intPtrZero));

ditto

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8213
> +            results.append(m_out.anchor(m_out.intPtrOne));

ditto

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8223
> +        setBoolean(m_out.phi(Int64, results));

and this should be Int32

[Justin Michaud]

(In reply to Saam Barati from comment #7)
> Comment on attachment 393428 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=393428&action=review
> 
> Mostly LGTM, but I think I found a couple legitimate bugs
> 
> > Source/JavaScriptCore/ChangeLog:10
> > +        creating a new node, FilterDeleteByStatus, and then turning these DeleteById nodes into a FilterDeleteByStatus,
> > +        CheckStructure, PutByOffset, then PutStructure. The logic for pessimising this optimization is the same as for 
> 
> or just CheckStructure in the case of a miss delete, right?

Yes, changed.

> 
> > Source/JavaScriptCore/ChangeLog:14
> > +        This also adds a MultiDeleteByOffset node, for the case when there are multiple structures seen by the delete.
> 
> If they're all misses, do you still just emit a CheckStructure?

Not yet, adding that now.

> 
> > Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:112
> > +            if (access.viaProxy())
> > +                return DeleteByStatus(JSC::slowVersion(summary), *stubInfo);
> 
> does this work currently in the IC? Like deleting via window proxy?

No. I replaced it with an assert.
> 
> > Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:115
> > +            if (access.usesPolyProto())
> > +                return DeleteByStatus(JSC::slowVersion(summary), *stubInfo);
> 
> is this even possible? Delete doesn't do anything on the prototype chain.
> Seems like it should be an assert or just drop the line entirely
> 
> > Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:131
> > +                ASSERT_UNUSED(offset, offset == access.offset());
> 
> how is this correct if we fail to find the transition?
If there is a valid access case for it, the transition should be valid, no? Or am I missing something?

> 
> > Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:4651
> > +        for (const DeleteByIdVariant& variant : deleteByStatus.variants()) {
> > +            m_graph.registerStructure(variant.oldStructure());
> > +            if (variant.newStructure())
> > +                m_graph.registerStructure(variant.newStructure());
> > +        }
> > +
> > +        MultiDeleteByOffsetData* data = m_graph.m_multiDeleteByOffsetData.add();
> > +        data->variants = deleteByStatus.variants();
> > +        data->identifierNumber = identifierNumber;
> > +        set(destination,
> > +            addToGraph(MultiDeleteByOffset, OpInfo(data), base));
> 
> if all of these are delete misses (and all either the non-configurable or
> the configurable kind), can we just turn this into a CheckStructure followed
> by "true" or "false" ? Seems like that's more efficient for other analyses

Ditto.

> 
> > Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:6030
> > +            handleDeleteById(bytecode.m_dst, base, identifierNumber, deleteByStatus);
> 
> what about delete by val when the identifier is monotonic? If you don't do
> that in this patch, please file a bug to do it. (You can see what we do for
> get_by_val)

Will do.

> 
> > Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1345
> > +        addBaseCheck(indexInBlock, node, baseValue, m_graph.registerStructure(variant.oldStructure()));
> 
> this seems to indicate we must be exitOK to begin with

There was already an assert, but I moved it up.

> 
> > Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:8200
> > +            results.append(m_out.anchor(variant.result() ? m_out.intPtrOne : m_out.intPtrZero));
> 
> This is wrong for booleans. We expect them to be i32. I wonder why nothing
> is actually crashing because of this in validation.
> 
> Anyways, you want m_out.booleanTrue and m_out.booleanFalse

Done, with test.

[Justin Michaud]

Created attachment 393539 [details]
Patch

[Justin Michaud]

Comment on attachment 393539 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=393539&action=review

> Source/JavaScriptCore/ChangeLog:125
> +

oops, will fix after review

[Justin Michaud]

Created attachment 393543 [details]
Patch

[Justin Michaud]

Created attachment 393551 [details]
Patch

[Justin Michaud]

Created attachment 393552 [details]
Patch

[Saam Barati]

Comment on attachment 393552 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=393552&action=review

r=me with a few comments

> Source/JavaScriptCore/bytecode/DeleteByStatus.cpp:127
> +                ASSERT_UNUSED(offset, offset == access.offset());

I think this should be moved after the branch on "newStructure"

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:6076
> +                    if (identifier.isCell()) {

this should be an assert. Also, it should be an assert in the get_by_val code. get_by_val is doing it wrong if it's not a cell, since we can't keep it alive.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1348
> +

nit: you could also do:
origin = origin.withInvalidExit()
here and then use that everywhere below instead of repeatedly calling it

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1370
> +        Node* clearValue = m_insertionSet.insertNode(indexInBlock, SpecNone, JSConstant, origin, OpInfo(m_graph.freezeStrong(JSValue())));

shouldn't this also be withInvalidExit?

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1372
> +            indexInBlock, SpecNone, PutByOffset, origin, OpInfo(&data), propertyStorage, node->child1(), Edge(clearValue));

can we assert node->child1() useKind is KnownCellUse? Or can wee just emit an edge with KnownCellUse directly to have the semantics be clearer?

Actually, looking at your code in mixup, it seems like we won't make this KnownCellUse. So I think that's required for proper exit semantics/bookkeeping

[Justin Michaud]

(In reply to Saam Barati from comment #14)
> Comment on attachment 393552 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=393552&action=review
> 
> r=me with a few comments
> 

> > Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1370
> > +        Node* clearValue = m_insertionSet.insertNode(indexInBlock, SpecNone, JSConstant, origin, OpInfo(m_graph.freezeStrong(JSValue())));
> 
> shouldn't this also be withInvalidExit?

If we exit before executing this node, we haven't changed any state yet, right? I am still not sure how the exit semantics work.

> 
> > Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:1372
> > +            indexInBlock, SpecNone, PutByOffset, origin, OpInfo(&data), propertyStorage, node->child1(), Edge(clearValue));
> 
> can we assert node->child1() useKind is KnownCellUse? Or can wee just emit
> an edge with KnownCellUse directly to have the semantics be clearer?
> 
> Actually, looking at your code in mixup, it seems like we won't make this
> KnownCellUse. So I think that's required for proper exit
> semantics/bookkeeping

We do, in addBaseCheck right? 

addBaseCheck(indexInBlock, node, baseValue, m_graph.registerStructure(variant.oldStructure()));
        node->child1().setUseKind(KnownCellUse);

[Justin Michaud]

Created attachment 394131 [details]
Patch

[Justin Michaud]

Created attachment 395408 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 395408 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=395408&action=review

Commented, since I found one GC bug.

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:6095
> +                auto identifier = CacheableIdentifier::createFromIdentifierOwnedByCodeBlock(m_inlineStackTop->m_profiledBlock, uid);

This is not correct. Please check https://bugs.webkit.org/show_bug.cgi?id=209698 & https://trac.webkit.org/changeset/259175/webkit.

[Yusuke Suzuki]

Comment on attachment 395408 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=395408&action=review

>> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:6095
>> +                auto identifier = CacheableIdentifier::createFromIdentifierOwnedByCodeBlock(m_inlineStackTop->m_profiledBlock, uid);
> 
> This is not correct. Please check https://bugs.webkit.org/show_bug.cgi?id=209698 & https://trac.webkit.org/changeset/259175/webkit.

Easiest fix is using CacheableIdentifier obtained from deleteByStatus.singleIdentifier() :)

[Justin Michaud]

Created attachment 395569 [details]
Patch

[Justin Michaud]

Created attachment 395571 [details]
Patch

[EWS]

Committed r259583: <https://trac.webkit.org/changeset/259583>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 395571 [details].

[Radar WebKit Bug Importer]

<rdar://problem/61352184>