678355 - GVN: arrays are people too!

Status: NEW

(Core :: JavaScript Engine: JIT, enhancement, P3)

Description

[Marty Rosenberg [:mjrosenb]]

currently, vn's are a single integer that, and when assigning a variable,
we do something like
new_vn <- hash(op, left_vn, right_vn).
Even if hash is an associative + commutative operation when op is an associative, commutative operation, we still lose information, particularly when doing things that look like indexing into arrays.

Depending on the use patterns that we see, it may be helpful to increase vn's to two integers, a "real" vn, and an offset, then do something like this
if (op == add)
    (new_rvn, new_offset) = (hash(left_vn,right_vn), left_offset+right_offset)
else
    (new_rvn, new_offset) = (hash(left_vn, right_vn, left_offset, right_offset),0)
so in the cases that we know that two values are related by a constant offset, we record that, and as soon as that value gets used in some other context, it gets collapsed into a normal vn.

Comment 1

[Dan Gohman [:sunfish]]

This is an interesting idea, though it's unclear to me how it would work in practice. Can you describe an example in which this optimization might apply?

Comment 2

[Marty Rosenberg [:mjrosenb]]

The most immediate thing that comes to mind is indexing into an asm.js heap.  If there is a structure like:
struct foo {
    int x;
    struct bar {
        int i, j

    };
    bar y[20];
}
then a loop over foo.y[idx].j may look sort of like
heap[(&foo + 4) + (8*idx + 4)]
where we can collapse the two immediates into one.

*more far flung case*
If we happen to get to the same value through two different struct lookup paths
e.g. heap[(&foo+8) + (8*idx +4)] and heap[(&foo + 4) + (8*idx + 8)]
are currently not recognized as accessing the same location in memory, but would be with this patch.  I suspect more relevant examples can be found in multi-dimensional arrays.

Comment 3

[Nicolas B. Pierron [:nbp]]

Doesn't this kind of optimization would make sense to alias some array accesses in cases where we have already unrolled a few iteration of a loop?

Also, when you say multidimensional arrays, I think you mean encoding multidimensional array in a sequential one, as on the other case we still have some aliasing where array accesses might alias each others.

Comment 4

[Marty Rosenberg [:mjrosenb]]

(In reply to Nicolas B. Pierron [:nbp] from comment #3)
> Doesn't this kind of optimization would make sense to alias some array
> accesses in cases where we have already unrolled a few iteration of a loop?
Yes, it will!
> Also, when you say multidimensional arrays, I think you mean encoding
> multidimensional array in a sequential one, as on the other case we still
> have some aliasing where array accesses might alias each others.
I guess it was unclear, but I was talking about asm.js arrays the whole time, which only has sequential arrays.