897606 - IonMonkey: Have precise memory dependencies (precise Alias Analysis)

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine: JIT, defect)

Description

[Nicolas B. Pierron [:nbp]]

Currently, our alias analysis is not precise enough to mark clear dependencies between load and write.  It still flag some poor & unique dependency which are used to hoist invariant out of loops.

Adding a better memory model to flag dependencies in the alias analysis should give us the ability to alias loads with stores.  This way, instead of doing a load from memory we can just alias the load with the MDefinition used as argument of the previous store.

The same way, with the addition of Recover instructions (Bug 878503), we should be able to remove non-observed writes to memory and handle them in a list of side effects stored on resume points.

At first we can do such a thing within loops, which gives 2% with the only load removal and 4% with the load & store removal, on the following minimal benchmark:

function fun(v) {
    var obj = {f: 2};
    obj.f += v;
    return obj;
}

Then we can extend the scope of this modification with the introduction of post-dominators, such as we can add memory Phis, and do this kind of optimizations across branches and for-loops.

Doing so, should prevent manipulation of the scope chain in any tight loop which has no call, and enable other optimizations such as range analysis to work on usually captured loop-variable.

Comment 1

[Nicolas B. Pierron [:nbp]]

Just for information, having clear dependencies instead of the latest visited instruction in the alias set already provides some interesting optimizations that we did not do until now.

One case from octane-crypto is:

  while(n > 2) {
    x[0] = 0; // need a new element vector & bound check for x.
    while(x[0] == 0) // need a new element vector & bound check for x.
      rng.nextBytes(x); // <-- might change x.
    ba[--n] = x[0]; // reuse the element vector & bound check of the condition.
  }

With the current status of our alias analysis, we do not reuse the element vector and the bound check of the condition of the while loop, because we visit the call-site before visiting the block following the back-edge.

And I think there is still room for improvement, as we should consider MElements as a load and thus introduces a Phi between the initial value and the potentially modified value as the result of the escaping call.

Comment 2

[Nicolas B. Pierron [:nbp]]

I finally managed to get scalar replacement working on top of a precise alias analysis.  All this work is done on top of the recover instruction (Bug 878503) patches, as it is mandatory to recover any store on bailouts.

You a working version of these optimizations on my github account:
  https://github.com/nbp/mozilla-central/compare/t/bug878503...t/bug897606

I still have to investigate some performance issues on octane (~1%), before implementing any additional recover instructions.  I guess this might be caused by some GVN / LICM which are no longer triggered as they used to be, or possibly some increase in compilation times.

Scalar replacement, is replacing writes by temporaries, and sink the stores in the following basic blocks.
For example:

function f(i) {
    var obj = { a: 0 };
    if (i % 2 == 0)
        obj.a = 1;
    else
        obj.a = 2;
    return obj;
}

becomes:

function f(i) {
    var obj = { };
    obj_a_ = 0;
    if (i % 2 == 0)
        obj_a_ = 1;
    else
        obj_a_ = 2;
    obj.a = obj_a_;
    return obj;
}

This instrument all bailout paths with recover instructions (Bug 878503), such as the last needed stores are done before the frame reconstruction needed for bailouts.

Comment 3

[Nicolas B. Pierron [:nbp]]

Wontfix for now.