Bug 186459 - [DFG] Fold GetByVal if Array is CoW
Summary: [DFG] Fold GetByVal if Array is CoW
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Yusuke Suzuki
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2018-06-09 02:58 PDT by Yusuke Suzuki
Modified: 2018-07-20 14:28 PDT (History)
7 users (show)

See Also:


Attachments
Patch (10.12 KB, patch)
2018-06-09 11:18 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (12.93 KB, patch)
2018-06-10 11:50 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (13.21 KB, patch)
2018-06-11 22:43 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (13.41 KB, patch)
2018-06-12 04:06 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from ews206 for win-future (12.83 MB, application/zip)
2018-06-12 09:11 PDT, EWS Watchlist
no flags Details
Patch (13.75 KB, patch)
2018-06-12 10:35 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (13.75 KB, patch)
2018-06-12 10:39 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (13.54 KB, patch)
2018-06-12 12:24 PDT, Yusuke Suzuki
sbarati: review+
ews-watchlist: commit-queue-
Details | Formatted Diff | Diff
Archive of layout-test-results from ews206 for win-future (12.79 MB, application/zip)
2018-06-12 20:46 PDT, EWS Watchlist
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description Yusuke Suzuki 2018-06-09 02:58:21 PDT
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.
Comment 1 Yusuke Suzuki 2018-06-09 03:02:54 PDT
(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!
Comment 2 Yusuke Suzuki 2018-06-09 11:18:30 PDT
Created attachment 342367 [details]
Patch
Comment 3 Keith Miller 2018-06-10 09:31:10 PDT
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.
Comment 4 Yusuke Suzuki 2018-06-10 11:24:17 PDT
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 :)
Comment 5 Yusuke Suzuki 2018-06-10 11:47:32 PDT
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.
Comment 6 Yusuke Suzuki 2018-06-10 11:50:42 PDT
Created attachment 342386 [details]
Patch
Comment 7 Saam Barati 2018-06-10 16:04:09 PDT
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
Comment 8 Saam Barati 2018-06-10 16:05:45 PDT
(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
Comment 9 Keith Miller 2018-06-11 09:49:41 PDT
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.
Comment 10 Yusuke Suzuki 2018-06-11 22:43:24 PDT
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.
Comment 11 Yusuke Suzuki 2018-06-11 22:43:56 PDT
Created attachment 342516 [details]
Patch
Comment 12 Yusuke Suzuki 2018-06-12 04:06:12 PDT
Created attachment 342524 [details]
Patch
Comment 13 Yusuke Suzuki 2018-06-12 04:09:47 PDT
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.
Comment 14 Yusuke Suzuki 2018-06-12 04:51:13 PDT
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...
Comment 15 EWS Watchlist 2018-06-12 09:10:52 PDT
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
Comment 16 EWS Watchlist 2018-06-12 09:11:04 PDT
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
Comment 17 Yusuke Suzuki 2018-06-12 10:35:12 PDT
Created attachment 342560 [details]
Patch
Comment 18 Yusuke Suzuki 2018-06-12 10:39:17 PDT
Created attachment 342561 [details]
Patch
Comment 19 Yusuke Suzuki 2018-06-12 10:42:58 PDT
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.
Comment 20 Yusuke Suzuki 2018-06-12 10:53:35 PDT
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.
Comment 21 Saam Barati 2018-06-12 11:44:33 PDT
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?
Comment 22 Yusuke Suzuki 2018-06-12 12:01:00 PDT
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.
Comment 23 Saam Barati 2018-06-12 12:11:50 PDT
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
Comment 24 Yusuke Suzuki 2018-06-12 12:13:50 PDT
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.
Comment 25 Yusuke Suzuki 2018-06-12 12:24:53 PDT
Created attachment 342578 [details]
Patch
Comment 26 EWS Watchlist 2018-06-12 20:46:25 PDT
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
Comment 27 EWS Watchlist 2018-06-12 20:46:36 PDT
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
Comment 28 Yusuke Suzuki 2018-06-13 20:24:38 PDT
Ping?
Comment 29 Saam Barati 2018-06-14 10:52:25 PDT
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
Comment 30 Yusuke Suzuki 2018-07-20 14:19:21 PDT
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 :)
Comment 31 Yusuke Suzuki 2018-07-20 14:25:24 PDT
Committed r234066: <https://trac.webkit.org/changeset/234066>
Comment 32 Radar WebKit Bug Importer 2018-07-20 14:28:04 PDT
<rdar://problem/42444870>