Bug 175823 – [DFG] Support ArrayPush with multiple args

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

[Yusuke Suzuki]

It turns out that Speedometer Ember uses this form in addToListeners, pushUniqueListener, and pushUniqueWithGrid.
And Array#push is not inlined in this case.

[Yusuke Suzuki]

Good news: https://arewefastyet.com/#machine=29&view=single&suite=six-speed&subtest=spread-literal-es5 is also affected by this optimization.

[Yusuke Suzuki]

Created attachment 321008 [details]
Patch

WIP: Int32/Contiguous support

[Keith Miller]

Oh, cool! I started working on this at one point but got distracted by the build systems stuff I was doing.

[Yusuke Suzuki]

OK, bug 177051 is landed. Starting it...

[Yusuke Suzuki]

Created attachment 321635 [details]
Patch

[Yusuke Suzuki]

Created attachment 321638 [details]
Patch

[Yusuke Suzuki]

Created attachment 321639 [details]
Patch

[Sam Weinig]

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!

[Build Bot]

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

[Build Bot]

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

[Yusuke Suzuki]

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!

[Yusuke Suzuki]

Created attachment 321643 [details]
Patch

[Darin Adler]

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?

[Yusuke Suzuki]

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

[Yusuke Suzuki]

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.

[Saam Barati]

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?

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

Created attachment 321763 [details]
Patch

[Yusuke Suzuki]

Created attachment 321764 [details]
Patch

[Yusuke Suzuki]

Created attachment 321778 [details]
Patch

[Saam Barati]

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

[Yusuke Suzuki]

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.

[Yusuke Suzuki]

Committed r222563: <http://trac.webkit.org/changeset/222563>

[Yusuke Suzuki]

Committed r222565: <http://trac.webkit.org/changeset/222565>

[Radar WebKit Bug Importer]

<rdar://problem/34694064>

[Ryan Haddad]

(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

[Yusuke Suzuki]

(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...

[Yusuke Suzuki]

(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.

[Yusuke Suzuki]

Committed r222581: <http://trac.webkit.org/changeset/222581>

[WebKit Commit Bot]

Re-opened since this is blocked by bug 177675

[Saam Barati]

This patch crashed Youtube.com inside FixupPhase

[Saam Barati]

>  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

[Yusuke Suzuki]

Committed r222675: <http://trac.webkit.org/changeset/222675>

[Filip Pizlo]

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

[Filip Pizlo]

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?

[Filip Pizlo]

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.

[Filip Pizlo]

(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.

[Yusuke Suzuki]

(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!