Bug 175823 - [DFG] Support ArrayPush with multiple args
Summary: [DFG] Support ArrayPush with multiple args
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: 177051 177675
Blocks: 179821
  Show dependency treegraph
 
Reported: 2017-08-22 05:18 PDT by Yusuke Suzuki
Modified: 2018-04-04 23:07 PDT (History)
12 users (show)

See Also:


Attachments
Patch (46.56 KB, patch)
2017-09-16 13:12 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (68.55 KB, patch)
2017-09-23 13:07 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (79.03 KB, patch)
2017-09-23 14:10 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (78.92 KB, patch)
2017-09-23 14:17 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from ews121 for ios-simulator-wk2 (946.73 KB, application/zip)
2017-09-23 16:01 PDT, Build Bot
no flags Details
Patch (79.16 KB, patch)
2017-09-23 17:04 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (81.23 KB, patch)
2017-09-25 16:26 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (80.48 KB, patch)
2017-09-25 16:29 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (80.48 KB, patch)
2017-09-25 17:15 PDT, Yusuke Suzuki
saam: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Yusuke Suzuki 2017-08-22 05:18:29 PDT
It turns out that Speedometer Ember uses this form in addToListeners, pushUniqueListener, and pushUniqueWithGrid.
And Array#push is not inlined in this case.
Comment 1 Yusuke Suzuki 2017-09-09 10:18:40 PDT
Good news: https://arewefastyet.com/#machine=29&view=single&suite=six-speed&subtest=spread-literal-es5 is also affected by this optimization.
Comment 2 Yusuke Suzuki 2017-09-16 13:12:16 PDT
Created attachment 321008 [details]
Patch

WIP: Int32/Contiguous support
Comment 3 Keith Miller 2017-09-21 12:19:39 PDT
Oh, cool! I started working on this at one point but got distracted by the build systems stuff I was doing.
Comment 4 Yusuke Suzuki 2017-09-22 01:30:11 PDT
OK, bug 177051 is landed. Starting it...
Comment 5 Yusuke Suzuki 2017-09-23 13:07:12 PDT
Created attachment 321635 [details]
Patch
Comment 6 Yusuke Suzuki 2017-09-23 14:10:26 PDT
Created attachment 321638 [details]
Patch
Comment 7 Yusuke Suzuki 2017-09-23 14:17:10 PDT
Created attachment 321639 [details]
Patch
Comment 8 Sam Weinig 2017-09-23 15:47:43 PDT
Comment on attachment 321639 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:30
> +                spread-literal.es5       90.3482+-6.6514     ^     24.8123+-2.3304        ^ definitely 3.6413x faster

Wow!
Comment 9 Build Bot 2017-09-23 16:01:22 PDT
Comment on attachment 321639 [details]
Patch

Attachment 321639 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: http://webkit-queues.webkit.org/results/4638732

New failing tests:
http/tests/cache-storage/cache-representation.https.html
Comment 10 Build Bot 2017-09-23 16:01:23 PDT
Created attachment 321640 [details]
Archive of layout-test-results from ews121 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews121  Port: ios-simulator-wk2  Platform: Mac OS X 10.12.6
Comment 11 Yusuke Suzuki 2017-09-23 16:44:59 PDT
Comment on attachment 321639 [details]
Patch

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

>> Source/JavaScriptCore/ChangeLog:30
>> +                spread-literal.es5       90.3482+-6.6514     ^     24.8123+-2.3304        ^ definitely 3.6413x faster
> 
> Wow!

Yay! Now, our ArrayPush(multiple args) can perform bulk push operation!
Comment 12 Yusuke Suzuki 2017-09-23 17:04:45 PDT
Created attachment 321643 [details]
Patch
Comment 13 Darin Adler 2017-09-23 17:08:22 PDT
Comment on attachment 321643 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:28
> +                array-push-1            133.8845+-7.0349     ?    136.1775+-5.8327        ? might be 1.0171x slower

What other benchmarks are heavy on single element pushes and might suffer from this possible slight additional cost?
Comment 14 Yusuke Suzuki 2017-09-23 17:19:06 PDT
Comment on attachment 321643 [details]
Patch

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

>> Source/JavaScriptCore/ChangeLog:28
>> +                array-push-1            133.8845+-7.0349     ?    136.1775+-5.8327        ? might be 1.0171x slower
> 
> What other benchmarks are heavy on single element pushes and might suffer from this possible slight additional cost?

I think this is pure noise because this test emits the same machine codes.
Our patch has `elementCount == 1` branch to keep our `array.push(oneElement)` case as fast as the current one.
https://gist.github.com/Constellation/6e53f19a2ff972fd15a53fb2138eb071
https://gist.github.com/Constellation/0897251c7c871de8f18f2f5652721859
Comment 15 Yusuke Suzuki 2017-09-23 17:23:00 PDT
Comment on attachment 321643 [details]
Patch

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

>>> Source/JavaScriptCore/ChangeLog:28
>>> +                array-push-1            133.8845+-7.0349     ?    136.1775+-5.8327        ? might be 1.0171x slower
>> 
>> What other benchmarks are heavy on single element pushes and might suffer from this possible slight additional cost?
> 
> I think this is pure noise because this test emits the same machine codes.
> Our patch has `elementCount == 1` branch to keep our `array.push(oneElement)` case as fast as the current one.
> https://gist.github.com/Constellation/6e53f19a2ff972fd15a53fb2138eb071
> https://gist.github.com/Constellation/0897251c7c871de8f18f2f5652721859

One difference between this one and the current one is that we emit Check nodes separated from ArrayPush.
But basically, the emitted machine code for `array.push(oneElement)` is almost the same.
Comment 16 Saam Barati 2017-09-23 17:56:07 PDT
Comment on attachment 321643 [details]
Patch

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

Will look more later when I’m by a computer, just one question/comment

> Source/JavaScriptCore/dfg/DFGOperations.cpp:893
> +        array->pushInline(exec, JSValue::decode(values[i]));

I think this might be wrong:
Can’t push perform arbitrary side effects? If so, it can be re-entrant into JIT code and potentially overwrite the buffer?

> Source/JavaScriptCore/runtime/JSArrayInlines.h:83
> +ALWAYS_INLINE void JSArray::pushInline(ExecState* exec, JSValue value)

Is there actually value in inlining this function?
Comment 17 Yusuke Suzuki 2017-09-23 18:55:14 PDT
Comment on attachment 321643 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGOperations.cpp:893
>> +        array->pushInline(exec, JSValue::decode(values[i]));
> 
> I think this might be wrong:
> Can’t push perform arbitrary side effects? If so, it can be re-entrant into JIT code and potentially overwrite the buffer?

Oops, right. I think Int32/Contiguous/Double are ok b/c

1. They do not have ArrayStorage. That means we do not have sparse map which can have accessors of this array.
2. Since they are not ArrayStorageSlowPut, we can say that it does not have accessors in this array’s prototype chain (for indexed elements).

The above conditions mean that Array::push is not observable for them.
We should have a safe path for ArrayStorage case.

>> Source/JavaScriptCore/runtime/JSArrayInlines.h:83
>> +ALWAYS_INLINE void JSArray::pushInline(ExecState* exec, JSValue value)
> 
> Is there actually value in inlining this function?

I think it’s good since there are DFG operations that just call this function.
Comment 18 Yusuke Suzuki 2017-09-23 18:59:41 PDT
Comment on attachment 321643 [details]
Patch

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

>>> Source/JavaScriptCore/dfg/DFGOperations.cpp:893
>>> +        array->pushInline(exec, JSValue::decode(values[i]));
>> 
>> I think this might be wrong:
>> Can’t push perform arbitrary side effects? If so, it can be re-entrant into JIT code and potentially overwrite the buffer?
> 
> Oops, right. I think Int32/Contiguous/Double are ok b/c
> 
> 1. They do not have ArrayStorage. That means we do not have sparse map which can have accessors of this array.
> 2. Since they are not ArrayStorageSlowPut, we can say that it does not have accessors in this array’s prototype chain (for indexed elements).
> 
> The above conditions mean that Array::push is not observable for them.
> We should have a safe path for ArrayStorage case.

For the non-array-index length (> 0xffffffff), it throws an error anyway, so no problem.
Comment 19 Yusuke Suzuki 2017-09-25 16:25:10 PDT
Comment on attachment 321643 [details]
Patch

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

>>>> Source/JavaScriptCore/dfg/DFGOperations.cpp:893
>>>> +        array->pushInline(exec, JSValue::decode(values[i]));
>>> 
>>> I think this might be wrong:
>>> Can’t push perform arbitrary side effects? If so, it can be re-entrant into JIT code and potentially overwrite the buffer?
>> 
>> Oops, right. I think Int32/Contiguous/Double are ok b/c
>> 
>> 1. They do not have ArrayStorage. That means we do not have sparse map which can have accessors of this array.
>> 2. Since they are not ArrayStorageSlowPut, we can say that it does not have accessors in this array’s prototype chain (for indexed elements).
>> 
>> The above conditions mean that Array::push is not observable for them.
>> We should have a safe path for ArrayStorage case.
> 
> For the non-array-index length (> 0xffffffff), it throws an error anyway, so no problem.

Oh, I find an interesting thing. Actually, we do not need to handle the above special cases.
If you have an indexed accessor, your array length is always larger than that accessor. As a result, Array#push is never trapped with this.
If an indexed accessor exists on the prototype chain, IndexingType should become ArrayWithSlowPutArrayStorage. So, DFG ArrayPush is not used.
Comment 20 Yusuke Suzuki 2017-09-25 16:26:28 PDT
Created attachment 321763 [details]
Patch
Comment 21 Yusuke Suzuki 2017-09-25 16:29:14 PDT
Created attachment 321764 [details]
Patch
Comment 22 Yusuke Suzuki 2017-09-25 17:15:53 PDT
Created attachment 321778 [details]
Patch
Comment 23 Saam Barati 2017-09-26 15:23:09 PDT
Comment on attachment 321778 [details]
Patch

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

r=me

> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:1039
> +            // and ArrayPush uses the edge as known typed edge. In this way, ArrayPush do not need to perform type checks.

In this way => Therefore

> Source/JavaScriptCore/dfg/DFGOperations.cpp:899
> +    ASSERT(array->indexingType() == ArrayWithInt32 || array->indexingType() == ArrayWithContiguous || array->indexingType() == ArrayWithArrayStorage);

I'd vote for:
RELEASE_ASSERT(!shouldUseSlowPut(array->indexingType())

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:8088
> +        // Refuse to handle bizarre lengths.
> +        speculationCheck(Uncountable, JSValueRegs(), 0, m_jit.branch32(MacroAssembler::Above, storageLengthGPR, TrustedImm32(bizarreLength)));

Let's name this something better, like largestPositiveInt32Length or something more descriptive. "bizarre" is not a descriptive name. I'd also make the comment state the reasoning: that DFG AI says this node results in Int32

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:4162
> +            ValueFromBlock fastResult = m_out.anchor(m_out.baseIndex(storage, m_out.zeroExtPtr(prevLength), ScaleEight));

let's call these fastBufferResult and slowBufferResult

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:4209
> +            setJSValue(m_out.phi(Int64, fastCallResult, slowCallResult));

and then you can just name these fastResult and slowResult since "fastCallResult" isn't from a call
Comment 24 Yusuke Suzuki 2017-09-27 11:37:20 PDT
Comment on attachment 321778 [details]
Patch

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

Thanks!

>> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:1039
>> +            // and ArrayPush uses the edge as known typed edge. In this way, ArrayPush do not need to perform type checks.
> 
> In this way => Therefore

Fixed.

>> Source/JavaScriptCore/dfg/DFGOperations.cpp:899
>> +    ASSERT(array->indexingType() == ArrayWithInt32 || array->indexingType() == ArrayWithContiguous || array->indexingType() == ArrayWithArrayStorage);
> 
> I'd vote for:
> RELEASE_ASSERT(!shouldUseSlowPut(array->indexingType())

Sounds nice, changed.

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:8088
>> +        speculationCheck(Uncountable, JSValueRegs(), 0, m_jit.branch32(MacroAssembler::Above, storageLengthGPR, TrustedImm32(bizarreLength)));
> 
> Let's name this something better, like largestPositiveInt32Length or something more descriptive. "bizarre" is not a descriptive name. I'd also make the comment state the reasoning: that DFG AI says this node results in Int32

Fixed.

>> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:4162
>> +            ValueFromBlock fastResult = m_out.anchor(m_out.baseIndex(storage, m_out.zeroExtPtr(prevLength), ScaleEight));
> 
> let's call these fastBufferResult and slowBufferResult

Fixed.

>> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:4209
>> +            setJSValue(m_out.phi(Int64, fastCallResult, slowCallResult));
> 
> and then you can just name these fastResult and slowResult since "fastCallResult" isn't from a call

OK, fixed.
Comment 25 Yusuke Suzuki 2017-09-27 11:37:44 PDT
Committed r222563: <http://trac.webkit.org/changeset/222563>
Comment 26 Yusuke Suzuki 2017-09-27 11:54:43 PDT
Committed r222565: <http://trac.webkit.org/changeset/222565>
Comment 27 Radar WebKit Bug Importer 2017-09-27 12:48:31 PDT
<rdar://problem/34694064>
Comment 28 Ryan Haddad 2017-09-27 14:14:15 PDT
(In reply to Yusuke Suzuki from comment #25)
> Committed r222563: <http://trac.webkit.org/changeset/222563>
The tests added with this change are hitting an assertion failure on 32-bit JSC bots:

ASSERTION FAILED: currentLowest != NUM_REGS && currentSpillOrder != SpillHintInvalid

https://build.webkit.org/builders/Apple%20High%20Sierra%2032-bit%20JSC%20%28BuildAndTest%29/builds/8
Comment 29 Yusuke Suzuki 2017-09-27 15:05:23 PDT
(In reply to Ryan Haddad from comment #28)
> (In reply to Yusuke Suzuki from comment #25)
> > Committed r222563: <http://trac.webkit.org/changeset/222563>
> The tests added with this change are hitting an assertion failure on 32-bit
> JSC bots:
> 
> ASSERTION FAILED: currentLowest != NUM_REGS && currentSpillOrder !=
> SpillHintInvalid
> 
> https://build.webkit.org/builders/Apple%20High%20Sierra%2032-
> bit%20JSC%20%28BuildAndTest%29/builds/8

I'm checking it now. It looks like regs are exhausted...
Comment 30 Yusuke Suzuki 2017-09-27 15:49:45 PDT
(In reply to Yusuke Suzuki from comment #29)
> (In reply to Ryan Haddad from comment #28)
> > (In reply to Yusuke Suzuki from comment #25)
> > > Committed r222563: <http://trac.webkit.org/changeset/222563>
> > The tests added with this change are hitting an assertion failure on 32-bit
> > JSC bots:
> > 
> > ASSERTION FAILED: currentLowest != NUM_REGS && currentSpillOrder !=
> > SpillHintInvalid
> > 
> > https://build.webkit.org/builders/Apple%20High%20Sierra%2032-
> > bit%20JSC%20%28BuildAndTest%29/builds/8
> 
> I'm checking it now. It looks like regs are exhausted...

In the meantime, let's disable for x86 32bit environment for now.
Comment 31 Yusuke Suzuki 2017-09-27 16:00:09 PDT
Committed r222581: <http://trac.webkit.org/changeset/222581>
Comment 32 WebKit Commit Bot 2017-09-29 11:46:32 PDT
Re-opened since this is blocked by bug 177675
Comment 33 Saam Barati 2017-09-29 12:32:21 PDT
This patch crashed Youtube.com inside FixupPhase
Comment 34 Saam Barati 2017-09-29 12:32:57 PDT
>  1 com.apple.JavaScriptCore       0x000ca6e4 JSC::DFG::FixupPhase::fixupNode(JSC::DFG::Node*) + 57252
   2 com.apple.JavaScriptCore       0x000bc559 JSC::DFG::FixupPhase::run() + 121
   3 com.apple.JavaScriptCore       0x0069e62f bool JSC::DFG::runAndLog<JSC::DFG::FixupPhase>(JSC::DFG::FixupPhase&) + 47
   4 com.apple.JavaScriptCore       0x000bc468 bool JSC::DFG::runPhase<JSC::DFG::FixupPhase>(JSC::DFG::Graph&) + 104
   5 com.apple.JavaScriptCore       0x0074a018 JSC::DFG::Plan::compileInThreadImpl() + 1864
   6 com.apple.JavaScriptCore       0x007492bb JSC::DFG::Plan::compileInThread(JSC::DFG::ThreadData*) + 683
   7 com.apple.JavaScriptCore       0x0080ccb5 JSC::DFG::Worklist::ThreadBody::work() + 277
   8 com.apple.JavaScriptCore       0x00b48148 WTF::Function<void ()>::CallableWrapper<WTF::AutomaticThread::start(WTF::AbstractLocker const&)::$_0>::call() + 296
   9 com.apple.JavaScriptCore       0x00b6b4e4 WTF::Thread::entryPoint(WTF::Thread::NewThreadContext*) + 228
  10 com.apple.JavaScriptCore       0x000032b9 WTF::wtfThreadEntryPoint(void*) + 9
  11 libsystem_pthread.dylib        0x000036c1 _pthread_body + 340 (/BuildRoot/Library/Caches/com.apple.xbs/Sources/libpthread/libpthread-301.20.1/src/pthread.c:740)
  12 libsystem_pthread.dylib        0x0000356d _pthread_start + 377 (/BuildRoot/Library/Caches/com.apple.xbs/Sources/libpthread/libpthread-301.20.1/src/pthread.c:799)
  13 libsystem_pthread.dylib        0x00002c5d thread_start + 13
Comment 35 Yusuke Suzuki 2017-09-29 18:16:59 PDT
Committed r222675: <http://trac.webkit.org/changeset/222675>
Comment 36 Filip Pizlo 2018-04-04 15:10:10 PDT
Comment on attachment 321778 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:7917
> +                RELEASE_ASSERT(!needsTypeCheck(element, SpecInt32Only));

Should be DFG_ASSERT

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:7962
> +                RELEASE_ASSERT(!needsTypeCheck(element, SpecInt32Only));

DFG_ASSERT

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:7989
> +            RELEASE_ASSERT(!needsTypeCheck(element, SpecDoubleReal));

DFG_ASSERT

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:8033
> +            RELEASE_ASSERT(!needsTypeCheck(element, SpecDoubleReal));

DFG_ASSERT

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:8136
> +        RELEASE_ASSERT_NOT_REACHED();

DFG_CRASH
Comment 37 Filip Pizlo 2018-04-04 15:13:13 PDT
Comment on attachment 321778 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:7989
>> +            RELEASE_ASSERT(!needsTypeCheck(element, SpecDoubleReal));
> 
> DFG_ASSERT

Also, why are you asserting this?  What makes this true?
Comment 38 Filip Pizlo 2018-04-04 15:17:30 PDT
Comment on attachment 321778 [details]
Patch

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

Filip Pizlo

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp:-3442
> -            DFG_TYPE_CHECK(
> -                JSValueRegs(), node->child2(), SpecDoubleReal,
> -                m_jit.branchDouble(MacroAssembler::DoubleNotEqualOrUnordered, valueFPR, valueFPR));

This type check should not have been removed.
Comment 39 Filip Pizlo 2018-04-04 15:39:27 PDT
(In reply to Filip Pizlo from comment #38)
> Comment on attachment 321778 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=321778&action=review
> 
> Filip Pizlo
> 
> > Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp:-3442
> > -            DFG_TYPE_CHECK(
> > -                JSValueRegs(), node->child2(), SpecDoubleReal,
> > -                m_jit.branchDouble(MacroAssembler::DoubleNotEqualOrUnordered, valueFPR, valueFPR));
> 
> This type check should not have been removed.

Never mind.  The bug is in CSE.  It was OK to remove this check because of the fixup.
Comment 40 Yusuke Suzuki 2018-04-04 23:07:31 PDT
(In reply to Filip Pizlo from comment #39)
> (In reply to Filip Pizlo from comment #38)
> > Comment on attachment 321778 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=321778&action=review
> > 
> > Filip Pizlo
> > 
> > > Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp:-3442
> > > -            DFG_TYPE_CHECK(
> > > -                JSValueRegs(), node->child2(), SpecDoubleReal,
> > > -                m_jit.branchDouble(MacroAssembler::DoubleNotEqualOrUnordered, valueFPR, valueFPR));
> > 
> > This type check should not have been removed.
> 
> Never mind.  The bug is in CSE.  It was OK to remove this check because of
> the fixup.

I've seen that RELEASE_ASSERT to DFG_ASSERT is handled in 
https://trac.webkit.org/changeset/230287/webkit, thank you!