[TurboFan] Calculate precise ranges for bitwise-or with positive input ranges.

[TurboFan] Calculate precise ranges for bitwise-or with positive input ranges.

The ranges computed for the bitwise-or operation, by the TurboFan typer, are currently very loose. Might as well compute the precise range, and this patch makes a start by doing so when the input ranges are positive. It also moves some simple and common special cases to the start.

BUG=

[dougc, 2015-03-08 16:22:30]

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

[Jarin, 2015-03-09 13:29:07]

On 2015/03/08 16:23:16, dougc wrote:

When writing the typer, we specifically wanted to keep it simple even if that
meant less precise typing. We'd prefer to add complexity only if there is some
real benefit.

Could you please motivate your change by showing some real world examples?

[dougc, 2015-03-10 06:52:24]

On 2015/03/09 13:29:07, jarin wrote:
> On 2015/03/08 16:23:16, dougc wrote:
> 
> When writing the typer, we specifically wanted to keep it simple even if that
> meant less precise typing. We'd prefer to add complexity only if there is some
> real benefit.
> 
> Could you please motivate your change by showing some real world examples?

The bitwise-or operation can be used in array index calculations, and used in
inputs to other operations, that can be usefully optimized if a narrower range
can be derived. For example: a[(i & 15) | 128]. 

Being able to derive that bounds checks are not needed does have a big benefit.
Here's a real world example showing the benefits of type derivation for bounds
check elimination using the zlib benchmark.

                   V8 x64   Odin x64
zlib standard:       39.2     29.1
zlib index masking:  30.2     29.7

                   V8 ia32  Odin x86
zlib standard:       40.8     43.0
zlib index masking   33.7     37.5

V8 is very competitive when using index masking, just a little slower than Odin
x64 and faster than Odin x86, but this demands a particular JS code style.
Extending the typer to handle operations typically used in index calculations
well would give app developers more flexibility and help optimize a wider
variety of code.

I believe there are other uses for type informations, other opportunities to
optimize operations if the input ranges have been derived to be narrower.

I am trying to bring Ion/Odin up to a similar level of type derivation
competence, for example https://bugzilla.mozilla.org/show_bug.cgi?id=1140932 so
that app developers can depend on a certain level of type derivation support.

The complexity of this patch, and planned work, is not that great and well
isolated. I am only proposing to derive the type for ranges defined by simple
sets such as the current linear range, and perhaps with an alignment value, not
to do symbolic range analysis etc.

Even if good deoptimization and bounds check hoisting support is added to
TurboFan, some applications can naturally use index masking such as a VM written
in JS that uses pointer tagging.

If you are not interested now then I'll probably create a public V8 branch to
ensure there is BSD licensed support available for future reference?

[Benedikt Meurer, 2015-03-10 07:43:14]

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

[Benedikt Meurer, 2015-03-10 07:43:14]

One thing I'd like to know: Do you plan to change Emscripten to generate this
"index masking" based code? Or is it just for developers who write asm.js code
by hand?

[titzer, 2015-03-10 07:47:12]

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

[titzer, 2015-03-10 07:47:13]

https://codereview.chromium.org/986073003/diff/1/src/compiler/typer.cc
File src/compiler/typer.cc (right):

https://codereview.chromium.org/986073003/diff/1/src/compiler/typer.cc#newcod...
src/compiler/typer.cc:877: 
Please add unit tests for the typer and mjsunit tests with JS code.

[dougc, 2015-03-12 13:14:24]

On 2015/03/10 07:43:14, Benedikt Meurer wrote:
> One thing I'd like to know: Do you plan to change Emscripten to generate this
> "index masking" based code? Or is it just for developers who write asm.js code
> by hand?

Emscripten has had an experimental 'POINTER_MASKING' feature for some time, and
an update is inbound, see: https://github.com/kripken/emscripten/pull/3240

It emits buffer accesses as a[(i&m)+c >> n] and V8 optimizes this well on the
ia32 and with a patch well on x64 see issue 860283004. The masks are defined
with a 'const' so the patch in issue 967093002 is also need for good performance
(Odin does not optimize a closure 'var' well).

[Benedikt Meurer, 2015-03-12 13:37:00]

On 2015/03/12 13:14:24, dougc wrote:
> On 2015/03/10 07:43:14, Benedikt Meurer wrote:
> > One thing I'd like to know: Do you plan to change Emscripten to generate
this
> > "index masking" based code? Or is it just for developers who write asm.js
code
> > by hand?
> 
> Emscripten has had an experimental 'POINTER_MASKING' feature for some time,
and
> an update is inbound, see: https://github.com/kripken/emscripten/pull/3240
> 
> It emits buffer accesses as a[(i&m)+c >> n] and V8 optimizes this well on the
> ia32 and with a patch well on x64 see issue 860283004. The masks are defined
> with a 'const' so the patch in issue 967093002 is also need for good
performance
> (Odin does not optimize a closure 'var' well).

That's great news! If this could be enabled by default for Emscripten, it'll
benefit both Firefox and Chrome immediately!
I'll look into the other patch again to see if we can make it work.

[titzer, 2016-03-10 10:14:08]

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