801872 - Ionmonkey: remove Load{Elem|FixedSlot} after Store{Elem|FixedSlot}

Status: RESOLVED DUPLICATE of bug 1049691

(Core :: JavaScript Engine, defect)

Description

[Hannes Verschore [:h4writer]]

Load depending on a Load already gets removed, but the same can be done for a Load depending on a Store. The load doesn't need to happen, because the value stored is still available.

Comment 1

[Hannes Verschore [:h4writer]]

Attachment: Patch

Passes all jit-tests with --ion.

Having a known computer problem (stuck on 0.8GHZ), therefor no final benchmarks. But with only folding MLoadElem I got an improvement in kraken from 2471.6ms to 2467.6ms. So the final patch should be worth a little bit more. Didn't test V8 or SS. If required I can run them tomorrow.

Also feel free to hand the review to somebody more suited when needed. I really didn't know who to give it too.

Comment 2

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 671612 [details] [diff] [review]
Patch

Cool! Jan is more familiar with Ion's AA, so throwing review to him.

Comment 3

[Jan de Mooij [:jandem]]

Comment on attachment 671612 [details] [diff] [review]
Patch

Review of attachment 671612 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ion/MIR.cpp
@@ +1526,5 @@
> +    if (dependency() && dependency()->isStoreElement()) {
> +        MStoreElement *store = dependency()->toStoreElement();
> +        if (EqualValues(useValueNumbers, store->index(), index()) &&
> +            EqualValues(useValueNumbers, store->elements(), elements()) &&
> +            store->type() == type()) {

store->type() is always MIRType_None so the condition is always false, you want store->value()->type() instead.

A more serious problem is that AA ignores conditional control flow, so here the LoadElement is marked as depending on the StoreElement:

function f() {
    if (x)
        a[3] = 10;
    else
        y = a[3];
}

The easiest fix would be to check if the load and store are in the same basic block or, a bit more complicated, if the store's block dominates the other block.

Before we add this optimization we should check where it will help, either try benchmarks like SS/V8/Kraken, or instrument the browser and visit some popular websites.

Comment 4

[Marty Rosenberg [:mjrosenb]]

Do we actually need domination as a condition?
as a simple case, we can have something like
function f(x,y) {
    if (x)
        a[3] = x;
    else
        a[3] = y;
    return a[3];
}
where neither assignment dominates the return statement, but we still don't need to do the array load (at the cost of inserting a phi).
If we've decided we're in the business of inserting phis, then the set of loads dominating (Is there a term for this already? I don't know of one) is not a requirement, since we can turn
function f(a,x) {
    if (x)
        a[3] = x;
    return a[3];
}
into
function f(a,x) {
    if (!x) goto elsecase;
        setelem a, 3 <- x
        goto join
    elsecase:
        tmp <- getelem a, 3
    join:
        retval <- phi(x, tmp);
        return retval;
}
which still has a getelem in it, but now it is conditional, so we'll have at most one array operation in an invocation of this function, rather than one or two depending on its inputs.

Comment 5

[Hannes Verschore [:h4writer]]

(In reply to Jan de Mooij [:jandem] from comment #3)
> A more serious problem is that AA ignores conditional control flow, so here
> the LoadElement is marked as depending on the StoreElement:

Ah really, I had no idea. Hmm this really limits the usefulness of this patch.
The patch reduced to only same block does removes loads, but not enough (2 on full SS benchmark, V8 a lot more).
No performance difference visible on SS and kraken using the same block.

So I think the more elaborate version will be needed, having functions just like marty suggests.
Would even enable us to remove store after store.
Not sure how much the speed improvements will be, therefore atm low priority.
(I'll look into it when I start working.)