Bug 176217 – [DFG] GetArrayLength array checking is too restrictive

• Component: JavaScriptCore
• Status: NEW

[Yusuke Suzuki]

Before converting GetById to GetArrayLength, we emit array checks.
However, this array check is designed for GetByVal / PutByVal.
While it restricts the array type to specific one type (like, DoubleArray) or converting it to some generic ones (like ContiguousArray),
GetArrayLength operation itself is very generic to several array types. For example, DoubleArray and ContiguousArray should have the same way to retrieve array length.

However, the problem exists. Consider the case that we see Int32Arrays. And we eventually see DoubleArrays in the same sites (for example, we find uint32_t values!).
In that case, array check fails, and OSR exit occurs. After that, we will compile it again in DFG. But at that time, we give up converting GetById(length) => GetArrayLength
because we have m_graph.hasExitSite(..., BadCache) guard. So, it will be compiled to GetById(length), it is really bad.

I think these guards are very strange ones. GetByVal / PutByVal do not have such guards. array mode should have appropriate array profiles. Thus, checkArray should emit appropriate array type check / conversions. I think this guard is too conservative.
One concern is that checkArray sometimes attempts to convert arrays to one type, like, DoubleArray to ContiguousArray.
It is essentially unnecessary. GetArrayLength operation is very generic. It can accidentally convert arrays to very generic ones even though we just look up "length".
But I think arrays will be used soon when getting "length" property, so, anyway, this conversion happens. So, I do not think this becomes a problem in practice.

[Yusuke Suzuki]

Fil, Saam, what do you think of?

[Yusuke Suzuki]

Created attachment 319591 [details]
Patch

[Yusuke Suzuki]

                                                 baseline                  patched                                      
Octane:
   encrypt                                   0.21051+-0.00493    ?     0.21841+-0.00571       ? might be 1.0375x slower
   decrypt                                   3.13930+-0.02251    ?     3.14503+-0.02825       ?
   deltablue                        x2       0.19008+-0.00532          0.18701+-0.01080         might be 1.0164x faster
   earley                                    0.37951+-0.00704    ?     0.38019+-0.01609       ?
   boyer                                     6.83988+-0.07740    ?     6.92880+-0.13538       ? might be 1.0130x slower
   navier-stokes                    x2       5.12818+-0.01423    ?     5.20143+-0.13349       ? might be 1.0143x slower
   raytrace                         x2       1.10658+-0.02242          1.07772+-0.03495         might be 1.0268x faster
   richards                         x2       0.10029+-0.00300          0.09836+-0.00175         might be 1.0196x faster
   splay                            x2       0.41247+-0.00484    ?     0.41323+-0.00390       ?
   regexp                           x2      25.11709+-1.65443         24.02918+-1.09488         might be 1.0453x faster
   pdfjs                            x2      52.38952+-3.33446    ?    54.46457+-2.45946       ? might be 1.0396x slower
   mandreel                         x2      58.90158+-3.29544         58.31994+-1.33219       
   gbemu                            x2      46.22318+-5.13633    ?    47.94010+-2.71271       ? might be 1.0371x slower
   closure                                   0.77792+-0.05047          0.74478+-0.06120         might be 1.0445x faster
   jquery                                    9.94905+-0.89518    ?    10.06185+-1.05702       ? might be 1.0113x slower
   box2d                            x2      13.13463+-0.83851         13.00404+-0.92778         might be 1.0100x faster
   zlib                             x2     483.27601+-16.13273       472.78395+-21.69978        might be 1.0222x faster
   typescript                       x2     840.25972+-86.80347   ?   859.47900+-63.90594      ? might be 1.0229x slower

   <geometric>                               6.79766+-0.13819          6.78804+-0.05220         might be 1.0014x faster

                                                 baseline                  patched                                      
Kraken:
   ai-astar                                  162.816+-11.413           151.680+-8.954           might be 1.0734x faster
   audio-beat-detection                       51.240+-7.588      ?      59.653+-11.218        ? might be 1.1642x slower
   audio-dft                                 102.862+-9.032            101.754+-4.882           might be 1.0109x faster
   audio-fft                                  40.371+-4.881             39.468+-3.200           might be 1.0229x faster
   audio-oscillator                           74.562+-24.268            67.619+-4.408           might be 1.1027x faster
   imaging-darkroom                          117.375+-7.022      ?     123.776+-7.671         ? might be 1.0545x slower
   imaging-desaturate                         70.970+-3.241      ?      73.692+-3.828         ? might be 1.0383x slower
   imaging-gaussian-blur                     108.991+-7.294            105.578+-7.984           might be 1.0323x faster
   json-parse-financial                       62.531+-4.510      ?      63.012+-4.097         ?
   json-stringify-tinderbox                   39.587+-2.309             37.797+-5.784           might be 1.0474x faster
   stanford-crypto-aes                        55.642+-5.342             55.556+-4.205         
   stanford-crypto-ccm                        48.734+-4.757      ?      54.429+-8.420         ? might be 1.1169x slower
   stanford-crypto-pbkdf2                     89.641+-9.154      ?      98.097+-6.939         ? might be 1.0943x slower
   stanford-crypto-sha256-iterative           32.858+-3.015      ?      34.105+-2.050         ? might be 1.0379x slower

   <arithmetic>                               75.584+-2.270      ?      76.158+-1.470         ? might be 1.0076x slower

                                                 baseline                  patched                                      
Geomean of preferred means:
   <scaled-result>                           22.6621+-0.2043     ?     22.7354+-0.1574        ? might be 1.0032x slower

[Saam Barati]

Comment on attachment 319591 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:16
> +        However, the problem exists. Consider the case that we see Int32Arrays.

"However, the problem exits" doesn't make sense in this context.

> Source/JavaScriptCore/ChangeLog:25
> +        have such guards. array mode should have appropriate array profiles.

array mode => Array mode
Also, instead of "should have", you should assert they do. Perhaps "The array profile already has the information we need based on profiling."

> Source/JavaScriptCore/ChangeLog:31
> +        I think this guard is too conservative. One concern is that checkArray
> +        sometimes attempts to convert arrays to one type, like, DoubleArray to
> +        ContiguousArray. It is essentially unnecessary. GetArrayLength operation
> +        is very generic. It can accidentally convert arrays to very generic ones
> +        even though we just look up "length". But I think arrays will be used soon

Maybe your patch should address this issue? It does seem weird that we would ever convert something for GetArrayLength.

> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:-1319
> -            if (node->child1()->shouldSpeculateCellOrOther()
> -                && !m_graph.hasExitSite(node->origin.semantic, BadType)
> -                && !m_graph.hasExitSite(node->origin.semantic, BadCache)
> -                && !m_graph.hasExitSite(node->origin.semantic, BadIndexingType)
> -                && !m_graph.hasExitSite(node->origin.semantic, ExoticObjectMode)) {
> -                

I agree in principle that the ArrayProfile should contain the necessary information, but I think completely removing these may leave us with the chance of having an OSR exit loop. Maybe we could use this information to drive us emitting a generic version of GetArrayLength that works over polymorphic indexing type?

[Filip Pizlo]

Comment on attachment 319591 [details]
Patch

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

>> Source/JavaScriptCore/ChangeLog:31
>> +        even though we just look up "length". But I think arrays will be used soon
> 
> Maybe your patch should address this issue? It does seem weird that we would ever convert something for GetArrayLength.

We should carefully benchmark this change and take it or not based on what we see. 

The reason why the current behavior exists is an explicit policy decision that I made. Often the length access dominated everything else, so it’s a convenient place to attempt an array conversion. It’s better than the array conversion being inside the loop. Just imagine something like:

for (i = 0; i < array.length; ++i)
   sum += array[i];

The length access ends up in the loop preheader so it’s the perfect place to do the conversion.

[Yusuke Suzuki]

Comment on attachment 319591 [details]
Patch

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

>> Source/JavaScriptCore/ChangeLog:16
>> +        However, the problem exists. Consider the case that we see Int32Arrays.
> 
> "However, the problem exits" doesn't make sense in this context.

OK, dropped.

>> Source/JavaScriptCore/ChangeLog:25
>> +        have such guards. array mode should have appropriate array profiles.
> 
> array mode => Array mode
> Also, instead of "should have", you should assert they do. Perhaps "The array profile already has the information we need based on profiling."

Fixed.

>>> Source/JavaScriptCore/ChangeLog:31
>>> +        even though we just look up "length". But I think arrays will be used soon
>> 
>> Maybe your patch should address this issue? It does seem weird that we would ever convert something for GetArrayLength.
> 
> We should carefully benchmark this change and take it or not based on what we see. 
> 
> The reason why the current behavior exists is an explicit policy decision that I made. Often the length access dominated everything else, so it’s a convenient place to attempt an array conversion. It’s better than the array conversion being inside the loop. Just imagine something like:
> 
> for (i = 0; i < array.length; ++i)
>    sum += array[i];
> 
> The length access ends up in the loop preheader so it’s the perfect place to do the conversion.

OK, it makes sense. It is natural that the code accessing "length" soon accesses array[xxx]. I'll perform extensive benchmarking.

>> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:-1319
>> -                
> 
> I agree in principle that the ArrayProfile should contain the necessary information, but I think completely removing these may leave us with the chance of having an OSR exit loop. Maybe we could use this information to drive us emitting a generic version of GetArrayLength that works over polymorphic indexing type?

If array mode becomes Array::Generic, we do not convert GetById to GetArrayLength. And I think IC should work for this case, correct?
And array profile should be refined if OSR exit occurs.

[Yusuke Suzuki]

Comment on attachment 319591 [details]
Patch

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

>>> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:-1319
>>> -                
>> 
>> I agree in principle that the ArrayProfile should contain the necessary information, but I think completely removing these may leave us with the chance of having an OSR exit loop. Maybe we could use this information to drive us emitting a generic version of GetArrayLength that works over polymorphic indexing type?
> 
> If array mode becomes Array::Generic, we do not convert GetById to GetArrayLength. And I think IC should work for this case, correct?
> And array profile should be refined if OSR exit occurs.

Yeah, array profile will be updated when OSR exit occurs. Thus, this is OK.

[Yusuke Suzuki]

Created attachment 327356 [details]
Patch