Avoid initialization checks when loading from an immutable context variable.

Avoid initialization checks when loading from an immutable context variable.

This patch tries to address the issue by copying some code from the context specialization reduction. Sorry I am not yet familiar enough with the code to really write this, but it does avoid the initialization checks and a phi that frustrates further optimization, and it passes the checks, and looks plausible.

This can make a significant performance improvement to asm.js style code that frequently references immutable module variables, and should help JS code in general. The Odin asm.js implementation optimizes a 'const' module variable, but with this patch v8 appears to also optimize an immutable 'var' well. Further, Odin compiles before the module variables have been initialized, but with this patch V8 can compile knowing the initialized variable values which is a very interesting feature. See https://bugzilla.mozilla.org/show_bug.cgi?id=1138132 for a request to add the later support to Odin and asm.js and some discussion.

BUG=

[dougc, 2015-03-01 10:00:06]

dtc-v8@scieneer.com changed reviewers:
+ titzer@chromium.org

[dougc, 2015-03-01 10:17:30]

Improves performance of loads from immutable context variables. Assistance with
this would be appreciated, or perhaps someone would be able to work on it.

[titzer, 2015-03-05 19:44:45]

As far as I can tell, this just duplicates the logic of context specialization
in the graph builder. The only advantage here I see is that it avoids inserting
a branch that would be immediately optimized away after the first round of
context specialization + control reduction.

Have you observed a case where the existing context specialization + control
reduction doesn't work?

[Michael Starzinger, 2015-03-06 11:26:51]

mstarzinger@chromium.org changed reviewers:
+ mstarzinger@chromium.org

[Michael Starzinger, 2015-03-06 11:26:51]

I am highly opposed to doing such optimizations in the AstGraphBuilder. The
logic for this needs to be kept in one place. It uses feedback from the current
context slot content at compile time when we specialize for a context. I agree
with what Ben said, ideally all of the machinery to take care of this should
already be in place.

In general moving optimization like this into the graph builder is a slippery
slope. We'll end up with a gargantuan tangle similar to the HGraphBuilder.

If we ever want to do early optimizations in the AstGraphBuilder, we need to
find a clean interface that shares the logic with later optimization phases.
IMHO, duplicating the logic is not an option.

[dougc, 2015-03-06 14:20:35]

On 2015/03/05 19:44:45, titzer wrote:
> As far as I can tell, this just duplicates the logic of context specialization
> in the graph builder. The only advantage here I see is that it avoids
inserting
> a branch that would be immediately optimized away after the first round of
> context specialization + control reduction.
> 
> Have you observed a case where the existing context specialization + control
> reduction doesn't work?

Thank you all for the feedback. The issue is demonstrated by the following
example:

var buffer = new ArrayBuffer(16*1024*1024);
var asm = (function test (glob, env, b) {
    'use asm';
    const i32 = new glob.Int32Array(b);
    var MASK = env.MASK|0;
    function f(i, v) {
      i = i | 0; v = v | 0;
      var j = 0;
      for (j = 0; (j | 0) < 10000; j = (j + 4) | 0)
        i32[((i + j) & MASK) + 36 >> 2] = v;
      return;
    }
    return f;
})(this, {MASK: 0x680}, buffer);
for (var i = 0; i < 1000000; i++) asm(16, 10);

Without this patch the MASK input to the bitwise-and and is a Phi, with one
input being 'undefined'. The derived type of this Phi is thus not the constant
MASK, but includes zero. This in turn prevents the bounds check being derived as
unnecessary, and the array access is encoded as a call which is much slower.
With this patch the generated code becomes:

0x378032006630    80  81fb10270000   cmpl rbx,0x2710
0x378032006636    86  0f8d1f000000   jge 123  (0x37803200665b)
0x37803200663c    92  8d4b04         leal rcx,[rbx+0x4]
0x37803200663f    95  8d1c1a         leal rbx,[rdx+rbx*1]
0x378032006642    98  81e380060000   andl rbx,0x680
0x378032006648   104  48be10f0ffa20b7f0000 REX.W movq rsi,0x7f0ba2fff010  << can
this is hoisted too?
0x378032006652   114  89441e24       movl [rsi+rbx*1+0x24],rax
0x378032006656   118  488bd9         REX.W movq rbx,rcx
0x378032006659   121  ebd5           jmp 80  (0x378032006630)

Perhaps the real issue is elsewhere. Perhaps the branch you mention is not being
optimized away as cleanly as it could be. Shall explore further.

btw: it would be nice to have the loading of the array base hoisted out of such
loops too.

[titzer, 2015-03-06 21:20:40]

On 2015/03/06 14:20:35, dougc wrote:
> On 2015/03/05 19:44:45, titzer wrote:
> > As far as I can tell, this just duplicates the logic of context
specialization
> > in the graph builder. The only advantage here I see is that it avoids
> inserting
> > a branch that would be immediately optimized away after the first round of
> > context specialization + control reduction.
> > 
> > Have you observed a case where the existing context specialization + control
> > reduction doesn't work?
> 
> Thank you all for the feedback. The issue is demonstrated by the following
> example:
> 
> var buffer = new ArrayBuffer(16*1024*1024);
> var asm = (function test (glob, env, b) {
>     'use asm';
>     const i32 = new glob.Int32Array(b);
>     var MASK = env.MASK|0;
>     function f(i, v) {
>       i = i | 0; v = v | 0;
>       var j = 0;
>       for (j = 0; (j | 0) < 10000; j = (j + 4) | 0)
>         i32[((i + j) & MASK) + 36 >> 2] = v;
>       return;
>     }
>     return f;
> })(this, {MASK: 0x680}, buffer);
> for (var i = 0; i < 1000000; i++) asm(16, 10);
> 
> Without this patch the MASK input to the bitwise-and and is a Phi, with one
> input being 'undefined'. The derived type of this Phi is thus not the constant
> MASK, but includes zero. This in turn prevents the bounds check being derived
as
> unnecessary, and the array access is encoded as a call which is much slower.
> With this patch the generated code becomes:
> 
> 0x378032006630    80  81fb10270000   cmpl rbx,0x2710
> 0x378032006636    86  0f8d1f000000   jge 123  (0x37803200665b)
> 0x37803200663c    92  8d4b04         leal rcx,[rbx+0x4]
> 0x37803200663f    95  8d1c1a         leal rbx,[rdx+rbx*1]
> 0x378032006642    98  81e380060000   andl rbx,0x680
> 0x378032006648   104  48be10f0ffa20b7f0000 REX.W movq rsi,0x7f0ba2fff010  <<
can
> this is hoisted too?
> 0x378032006652   114  89441e24       movl [rsi+rbx*1+0x24],rax
> 0x378032006656   118  488bd9         REX.W movq rbx,rcx
> 0x378032006659   121  ebd5           jmp 80  (0x378032006630)
> 
> Perhaps the real issue is elsewhere. Perhaps the branch you mention is not
being
> optimized away as cleanly as it could be. Shall explore further.
> 
> btw: it would be nice to have the loading of the array base hoisted out of
such
> loops too.

Ok, we need to look into why context specialization doesn't catch this. Moz
shouldn't be using const for these bindings. The semantics differs between VMs
and on V8 there is a tricky live range hole.

[dougc, 2015-03-07 04:12:41]

On 2015/03/06 21:20:40, titzer wrote:
> On 2015/03/06 14:20:35, dougc wrote:
> > On 2015/03/05 19:44:45, titzer wrote:
...
> > var buffer = new ArrayBuffer(16*1024*1024);
> > var asm = (function test (glob, env, b) {
...
> Ok, we need to look into why context specialization doesn't catch this. Moz
> shouldn't be using const for these bindings. The semantics differs between VMs
> and on V8 there is a tricky live range hole.

Const seems useful as it allows the value to be baked in before parsing the
entire scope. Currently Odin will only bake in a const initialized to a literal
number, not a var. Const is defined in ES6 and V8 appears to have no problem
optimizing it's use well. Even a semantic difference between throwing versus
ignoring mutation is not of practical importance.

Could you give an example of how to tickle a 'live range hole' for the mode ==
CONST case? Is this hole check even necessary in this case?

There is some discussion in:
https://code.google.com/p/v8/issues/detail?id=3898
https://code.google.com/p/v8/issues/detail?id=327

Emscripten emits a 'var' for the arrays, so the above example was not so
representative. However the follow pattern is being discussed for Emscripten and
is also not well optimized by TurboFan.
    var i32 = new glob.Int32Array(b);
    const MASK = env.MASK|0;

The hole check is problematic because the result of the throw-reference-error
also feeds into a Phi. Context specialization replaces the JSLoadContext with
the constant value, but the Phi remains. I assume the throw can not return, so
should the Phi have been optimized away?

Could the hole checks be emitted after context specialization, and any needed
state be noted in a flag on JSLoadContext?

The common path is expected to be no-hole-check so it might be more efficient to
only emit the hole checks when needed, rather than emitting them for all loads
and then optimizing them away.

[Benedikt Meurer, 2015-04-10 08:58:44]

Hey Douglas,

I have uploaded a separate fix for this problem in
https://codereview.chromium.org/1072353002/ which addresses the problem by
turning the hole check diamond, that can only be removed during late control
reduction, into a select that can be removed during typed lowering. That should
address all problems described above.

Benedikt

[dougc, 2015-04-19 14:20:55]

On 2015/04/10 08:58:44, Benedikt Meurer wrote:
> Hey Douglas,
> 
> I have uploaded a separate fix for this problem in
> https://codereview.chromium.org/1072353002/ which addresses the problem by
> turning the hole check diamond, that can only be removed during late control
> reduction, into a select that can be removed during typed lowering. That
should
> address all problems described above.

This does not address the problem of the type of the constant as seen after the
select when the typer runs, and it still has a lower bound of zero. Perhaps the
typer could be extended to derive the type of the select in this case? Otherwise
there still seems to be an issue here to remove the hole check earlier in the
pipeline, and before types are derived.

[titzer, 2016-10-18 08:56:07]

titzer@chromium.org changed reviewers:
- titzer@chromium.org