Bug 147265 – SparseValueMap check is skipped when the butterfly's vectorLength is larger than the access-requested index

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Yusuke Suzuki]

SparseValueMap check is skipped when the butterfly's vectorLength is larger than the access-requested index

[Filip Pizlo]

(In reply to comment #0)
> SparseValueMap check is skipped when the butterfly's vectorLength is larger
> than the access-requested index

That may be intentional.  We don't want to always check for the sparse value map.

[Yusuke Suzuki]

(In reply to comment #1)
> (In reply to comment #0)
> > SparseValueMap check is skipped when the butterfly's vectorLength is larger
> > than the access-requested index
> 
> That may be intentional.  We don't want to always check for the sparse value
> map.

Ah, sorry for misleading my description.
Yes, but, when the accessed value is the array hole and there's a sparse map, we need to check it.

Following is the test to reproduce this issue.

function testing(object) {
    var value = object[1];
    if (value !== 1)
        throw new Error("OUT");
}
noInline(testing);

for (var i = 0; i < 10000; ++i)
    testing({
        0: 0,
        1: 1,
        2: "String"
    });

// Now, object[1] (inside testing) will be return `undefined` for the following object.
testing({
    0: 0,
    get 1() {
        return 1;
    },
    set 1(value) {
        throw new Error(2);
    },
});

[Filip Pizlo]

(In reply to comment #2)
> (In reply to comment #1)
> > (In reply to comment #0)
> > > SparseValueMap check is skipped when the butterfly's vectorLength is larger
> > > than the access-requested index
> > 
> > That may be intentional.  We don't want to always check for the sparse value
> > map.
> 
> Ah, sorry for misleading my description.
> Yes, but, when the accessed value is the array hole and there's a sparse
> map, we need to check it.
> 
> Following is the test to reproduce this issue.
> 
> function testing(object) {
>     var value = object[1];
>     if (value !== 1)
>         throw new Error("OUT");
> }
> noInline(testing);
> 
> for (var i = 0; i < 10000; ++i)
>     testing({
>         0: 0,
>         1: 1,
>         2: "String"
>     });
> 
> // Now, object[1] (inside testing) will be return `undefined` for the
> following object.
> testing({
>     0: 0,
>     get 1() {
>         return 1;
>     },
>     set 1(value) {
>         throw new Error(2);
>     },
> });

I think that the bug here is that vectorLength is not zero.  That's the intent anyway.  It would probably be rather gross to change the array load/store algorithm to always check for sparse map even on indices in-bounds of vectorLength, since that means changing *a lot* of code.

[Yusuke Suzuki]

(In reply to comment #3)
> I think that the bug here is that vectorLength is not zero.  That's the
> intent anyway.  It would probably be rather gross to change the array
> load/store algorithm to always check for sparse map even on indices
> in-bounds of vectorLength, since that means changing *a lot* of code.

In the current DFG, since it speculate the value is not the array hole when accessing the vector, when the speculation is not met, it causes exit.
After that, since runtime JSObject skips the sparse map check, this issue occurs.
So I think DFG/FTL changes are not necessary.

I think there's 2 solutions at least.

1. Just check the sparse map if the vector returns the array hole.
2. When indexed accessor is stored, throw away the vector and make the array DictionaryIndexingMode.

I think what solution is the better depends on how frequently we use indexed accessors.
I guess indexed accessors are not so much used, (2) seems nice.

[Geoffrey Garen]

I agree that indexed accessors on arrays are rare, and should be treated specially.

[Yusuke Suzuki]

Created attachment 257492 [details]
Patch

[Geoffrey Garen]

Comment on attachment 257492 [details]
Patch

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

r=me

> Source/JavaScriptCore/ChangeLog:17
> +        As a result, if the length of the vector overlaps the indice of the accessors stored in the SparseValueMap,

indice => indices

> Source/JavaScriptCore/ChangeLog:18
> +        we accidentally skip the phase looking up from the SparseValueMap. Instead, just looks the vector and if

just looks the vector => we just load from the vector

[Filip Pizlo]

(In reply to comment #4)
> (In reply to comment #3)
> > I think that the bug here is that vectorLength is not zero.  That's the
> > intent anyway.  It would probably be rather gross to change the array
> > load/store algorithm to always check for sparse map even on indices
> > in-bounds of vectorLength, since that means changing *a lot* of code.
> 
> In the current DFG, since it speculate the value is not the array hole when
> accessing the vector

This is not true.  The DFG has a path for storing to holes.  It also has optimizations for loading from holes.

> , when the speculation is not met, it causes exit.
> After that, since runtime JSObject skips the sparse map check, this issue
> occurs.
> So I think DFG/FTL changes are not necessary.
> 
> I think there's 2 solutions at least.
> 
> 1. Just check the sparse map if the vector returns the array hole.
> 2. When indexed accessor is stored, throw away the vector and make the array
> DictionaryIndexingMode.
> 
> I think what solution is the better depends on how frequently we use indexed
> accessors.
> I guess indexed accessors are not so much used, (2) seems nice.

Does your solution depend on your assumption that the DFG doesn't support hole accesses?

[Yusuke Suzuki]

(In reply to comment #8)
> (In reply to comment #4)
> > (In reply to comment #3)
> > > I think that the bug here is that vectorLength is not zero.  That's the
> > > intent anyway.  It would probably be rather gross to change the array
> > > load/store algorithm to always check for sparse map even on indices
> > > in-bounds of vectorLength, since that means changing *a lot* of code.
> > 
> > In the current DFG, since it speculate the value is not the array hole when
> > accessing the vector
> 
> This is not true.  The DFG has a path for storing to holes.  It also has
> optimizations for loading from holes.

Ah, I missed StoreToHole.
I just checked ArrayStorage loading path because when there's a sparse value map, the array becomes storage indexing types.

> 
> > , when the speculation is not met, it causes exit.
> > After that, since runtime JSObject skips the sparse map check, this issue
> > occurs.
> > So I think DFG/FTL changes are not necessary.
> > 
> > I think there's 2 solutions at least.
> > 
> > 1. Just check the sparse map if the vector returns the array hole.
> > 2. When indexed accessor is stored, throw away the vector and make the array
> > DictionaryIndexingMode.
> > 
> > I think what solution is the better depends on how frequently we use indexed
> > accessors.
> > I guess indexed accessors are not so much used, (2) seems nice.
> 
> Does your solution depend on your assumption that the DFG doesn't support
> hole accesses?

No. In this patch, we maintain the invariant that the stored indices in the sparse value map is always larger than the vector length. Previously this invariant is broken when setting the indexed accessors.

[Yusuke Suzuki]

Committed r187464: <http://trac.webkit.org/changeset/187464>

[Yusuke Suzuki]

Comment on attachment 257492 [details]
Patch

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

Thanks for your review!

>> Source/JavaScriptCore/ChangeLog:17
>> +        As a result, if the length of the vector overlaps the indice of the accessors stored in the SparseValueMap,
> 
> indice => indices

Fixed.

>> Source/JavaScriptCore/ChangeLog:18
>> +        we accidentally skip the phase looking up from the SparseValueMap. Instead, just looks the vector and if
> 
> just looks the vector => we just load from the vector

Fixed.