Bug 186459 – [DFG] Fold GetByVal if Array is CoW

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

[Yusuke Suzuki]

If we know the array is a constant one and it has a CoW structure (by CheckStructure etc.), InBounds GetByVal can be turned into a constant.

[Yusuke Suzuki]

(In reply to Yusuke Suzuki from comment #0)
> If we know the array is a constant one and it has a CoW structure (by
> CheckStructure etc.), InBounds GetByVal can be turned into a constant.

Does this happen? => I think it can happen. For example, we have a global variable, which is an array in a literal form.
And some functions access it. At that time,

1. GlobalVar access can be folded into a constant if it is not changed.
2. GetByVal can emit CheckStructure
3. Then, we have a GetByVal with a constant JSArray with JSImmutableButterfly!

[Yusuke Suzuki]

Created attachment 342367 [details]
Patch

[Keith Miller]

Comment on attachment 342367 [details]
Patch

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

This has some intense indentation maybe we should flip the logic and have it bail out instead?

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1829
> +                    // Check the structure set is finite. This means that this constant's structure is watched and guaranteed the one of this set.
> +                    // When the structure is changed, this code should be invalidated. This is important since the following code relies on the
> +                    // constant object's is not changed.
> +                    if (arrayValue.m_structure.isFinite()
> +                        && (arrayEdge.useKind() == CellUse || arrayEdge.useKind() == KnownCellUse || !(arrayValue.m_type & ~SpecCell))) {

Doesn't AI finding a constant value guarantee this?

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1848
> +                                        if (static_cast<unsigned>(index) < immutableButterfly->length()) {
> +                                            JSValue value = immutableButterfly->get(index);
> +                                            if (value.isCell())
> +                                                setConstant(node, *m_graph.freeze(value.asCell()));
> +                                            else
> +                                                setConstant(node, value);
> +                                            break;

Nit: I think you could handle the out of bounds case too if we are watching for a sane chain.

[Yusuke Suzuki]

Comment on attachment 342367 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1829
>> +                        && (arrayEdge.useKind() == CellUse || arrayEdge.useKind() == KnownCellUse || !(arrayValue.m_type & ~SpecCell))) {
> 
> Doesn't AI finding a constant value guarantee this?

Right. Removed.

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1848
>> +                                            break;
> 
> Nit: I think you could handle the out of bounds case too if we are watching for a sane chain.

OK, we can handle Array::SaneChain case :)

[Yusuke Suzuki]

Comment on attachment 342367 [details]
Patch

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

>>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1848
>>> +                                            break;
>> 
>> Nit: I think you could handle the out of bounds case too if we are watching for a sane chain.
> 
> OK, we can handle Array::SaneChain case :)

Ah, no. Array::SaneChain case does not happen since it is only considering array holes. JSImmutableButterfly does not have any holes.

[Yusuke Suzuki]

Created attachment 342386 [details]
Patch

[Saam Barati]

Comment on attachment 342386 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1849
> +                WTF::loadLoadFence();

Does the main thread order stores in such a way that this is safe? Like:
storeButterfly
storeStoreFence
storeIndexingType

[Saam Barati]

(In reply to Saam Barati from comment #7)
> Comment on attachment 342386 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=342386&action=review
> 
> > Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1849
> > +                WTF::loadLoadFence();
> 
> Does the main thread order stores in such a way that this is safe? Like:
> storeButterfly
> storeStoreFence
> storeIndexingType
Actually this ordering I wrote is wrong. I think you’d need the reverse:

storeIndexingType
storeStoreFence
storeButterfly

[Keith Miller]

Comment on attachment 342386 [details]
Patch

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

>>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1849
>>> +                WTF::loadLoadFence();
>> 
>> Does the main thread order stores in such a way that this is safe? Like:
>> storeButterfly
>> storeStoreFence
>> storeIndexingType
> 
> Actually this ordering I wrote is wrong. I think you’d need the reverse:
> 
> storeIndexingType
> storeStoreFence
> storeButterfly

Yeah, I think you want to check the array's structure is CoW.

[Yusuke Suzuki]

Comment on attachment 342386 [details]
Patch

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

>>>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1849
>>>> +                WTF::loadLoadFence();
>>> 
>>> Does the main thread order stores in such a way that this is safe? Like:
>>> storeButterfly
>>> storeStoreFence
>>> storeIndexingType
>> 
>> Actually this ordering I wrote is wrong. I think you’d need the reverse:
>> 
>> storeIndexingType
>> storeStoreFence
>> storeButterfly
> 
> Yeah, I think you want to check the array's structure is CoW.

OK, I've added structure check here.

[Yusuke Suzuki]

Created attachment 342516 [details]
Patch

[Yusuke Suzuki]

Created attachment 342524 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 342524 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1826
> +                // FIXME: We can expand this for non x86 environments.
> +                // https://bugs.webkit.org/show_bug.cgi?id=134641
> +                if (!isX86())
> +                    return false;
> +

Unfortunately, currently we do not have any guarantee between stores of Structure & Butterfly (except for x86), is it correct?
So, we cannot ensure the availability of this optimization except for x86.

[Yusuke Suzuki]

Comment on attachment 342524 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1826
>> +
> 
> Unfortunately, currently we do not have any guarantee between stores of Structure & Butterfly (except for x86), is it correct?
> So, we cannot ensure the availability of this optimization except for x86.

In x86, it is TSO. So we can do this. And since x86 is TSO, we always emit storeStoreFence() in JSObject, because it is just a compiler fence.
It is unfortunate that we cannot rely on these things in ARM...

[EWS Watchlist]

Comment on attachment 342524 [details]
Patch

Attachment 342524 [details] did not pass win-ews (win):
Output: http://webkit-queues.webkit.org/results/8147668

New failing tests:
http/tests/security/canvas-remote-read-remote-video-redirect.html
storage/indexeddb/modern/leak-1.html

[EWS Watchlist]

Created attachment 342547 [details]
Archive of layout-test-results from ews206 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews206  Port: win-future  Platform: CYGWIN_NT-6.1-2.9.0-0.318-5-3-x86_64-64bit

[Yusuke Suzuki]

Created attachment 342560 [details]
Patch

[Yusuke Suzuki]

Created attachment 342561 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 342561 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1825
> +                // FIXME: We can expand this for non x86 environments.
> +                // https://bugs.webkit.org/show_bug.cgi?id=134641
> +                if (!isX86())
> +                    return false;

If we always use `nuke` & `storeStoreFence` when converting CoW to non-CoW, we can expand this for the other architectures which are not Total Store Ordering.

[Yusuke Suzuki]

Comment on attachment 342561 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1871
> +                // To keep immutableButterfly alive, we first cast it to JSImmutableButterfly even if a butterfly is not
> +                // JSImmutableButterfly.
> +                WTF::loadLoadFence();
> +                JSImmutableButterfly* immutableButterfly = JSImmutableButterfly::fromButterfly(array->butterfly());
> +
> +                WTF::loadLoadFence();
> +                StructureID structureIDLate = array->structureID();
> +
> +                if (structureIDEarly != structureIDLate)
> +                    return false;
> +
> +                Structure* structure = array->structure(m_vm);
> +                if (!isCopyOnWrite(structure->indexingMode()))
> +                    return false;
> +

Finally, it becomes really fancy! We rely on that non-CoW -> CoW transition cannot happen too.

[Saam Barati]

Comment on attachment 342561 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1858
> +                // To keep immutableButterfly alive, we first cast it to JSImmutableButterfly even if a butterfly is not
> +                // JSImmutableButterfly.

What do you even mean by this? Why is this needed? Why can't you just load it as Butterfly*?

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1868
> +                Structure* structure = array->structure(m_vm);

Why not use one of the StructureIDs here? This seems like it's probably fine, given we don't transition in the nonCoW->CoW, but it just looks scary.

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1888
> +                    Structure* arrayPrototypeStructure = globalObject->arrayPrototype()->structure(m_vm);
> +                    Structure* objectPrototypeStructure = globalObject->objectPrototype()->structure(m_vm);
> +                    if (arrayPrototypeStructure->transitionWatchpointSetIsStillValid()
> +                        && objectPrototypeStructure->transitionWatchpointSetIsStillValid()
> +                        && globalObject->arrayPrototypeChainIsSane()) {

How is this correct? What if these prototypes have indexed properties?

[Yusuke Suzuki]

Comment on attachment 342561 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1858
>> +                // JSImmutableButterfly.
> 
> What do you even mean by this? Why is this needed? Why can't you just load it as Butterfly*?

We should have a reference to JSImmutableButterfly here, otherwise, it would be collected since that Butterfly pointer is pointing the middle of JSImmutableButterfly JSCell.

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1868
>> +                Structure* structure = array->structure(m_vm);
> 
> Why not use one of the StructureIDs here? This seems like it's probably fine, given we don't transition in the nonCoW->CoW, but it just looks scary.

Having StructureID in conservative roots does not mark Structure*. We should get a structure once again from JSObject. Since non CoW -> CoW transition does not happen, if we find th structure says CoW, our butterfly is definitely immutavble one.

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1888
>> +                        && globalObject->arrayPrototypeChainIsSane()) {
> 
> How is this correct? What if these prototypes have indexed properties?

It is the same to Fixup’s SaneChain condition. But we calculate this for OutOfBounds case. If indexed element is set, structure transition happens and invalidates the code.
This patch includes the test for that.

[Saam Barati]

Comment on attachment 342561 [details]
Patch

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

>>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1858
>>> +                // JSImmutableButterfly.
>> 
>> What do you even mean by this? Why is this needed? Why can't you just load it as Butterfly*?
> 
> We should have a reference to JSImmutableButterfly here, otherwise, it would be collected since that Butterfly pointer is pointing the middle of JSImmutableButterfly JSCell.

No. The GC isn't running at this point in the compiler. It needs to safe point compiler threads before finishing GC

[Yusuke Suzuki]

Comment on attachment 342561 [details]
Patch

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

>>>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1858
>>>> +                // JSImmutableButterfly.
>>> 
>>> What do you even mean by this? Why is this needed? Why can't you just load it as Butterfly*?
>> 
>> We should have a reference to JSImmutableButterfly here, otherwise, it would be collected since that Butterfly pointer is pointing the middle of JSImmutableButterfly JSCell.
> 
> No. The GC isn't running at this point in the compiler. It needs to safe point compiler threads before finishing GC

That’s good. We can just hold Butterfly here.

>>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1868
>>> +                Structure* structure = array->structure(m_vm);
>> 
>> Why not use one of the StructureIDs here? This seems like it's probably fine, given we don't transition in the nonCoW->CoW, but it just looks scary.
> 
> Having StructureID in conservative roots does not mark Structure*. We should get a structure once again from JSObject. Since non CoW -> CoW transition does not happen, if we find th structure says CoW, our butterfly is definitely immutavble one.

Then, we can get Structre by vm. getStructure.

[Yusuke Suzuki]

Created attachment 342578 [details]
Patch

[EWS Watchlist]

Comment on attachment 342578 [details]
Patch

Attachment 342578 [details] did not pass win-ews (win):
Output: http://webkit-queues.webkit.org/results/8155251

New failing tests:
http/tests/security/canvas-remote-read-remote-video-localhost.html

[EWS Watchlist]

Created attachment 342623 [details]
Archive of layout-test-results from ews206 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews206  Port: win-future  Platform: CYGWIN_NT-6.1-2.9.0-0.318-5-3-x86_64-64bit

[Yusuke Suzuki]

Ping?

[Saam Barati]

Comment on attachment 342578 [details]
Patch

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

r=me

> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1848
> +                int32_t index = indexConstant.asInt32();

Nit: I’d use uint32_t here and asUint32

[Yusuke Suzuki]

Comment on attachment 342578 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h:1848
>> +                int32_t index = indexConstant.asInt32();
> 
> Nit: I’d use uint32_t here and asUint32

Fixed :)

[Yusuke Suzuki]

Committed r234066: <https://trac.webkit.org/changeset/234066>

[Radar WebKit Bug Importer]

<rdar://problem/42444870>