Improve the x64 Load and Store access instruction selection to include immediate offsets.

Improve the x64 Load and Store access instruction selection to include immediate offsets.

Currently GetEffectiveAddressMemoryOperand() uses
BaseWithIndexAndDisplacement64Match. However this does not recognize
the ChangeUint32ToUint64 operation which is applied to the index. It
looks like a lot of work to rework BaseWithIndexAndDisplacement64Match,
and BaseWithIndexAndDisplacement32Match seems ok as-is, so it seems more
appropriate to add x64 backend specific code to match the patterns
which is done inline in GetEffectiveAddressMemoryOperand().

Some of the code in VisitChangeUint32ToUint64() has been refactored
into OpZeroExtends() and is needed in the pattern matching.

The BaseWithIndexAndDisplacementMatch code has some OwnedBy()
tests. It's not immediately clear if these are to maintain some
invariant or if they are just a heuristic? It seems generally better
to dehoist the index offsets aggressively so the OwnedBy() test is
omitted in this patch. This could use some reviewer scrutiny?

A TODO note is included to explore the scaled-index patterns matched
by BaseWithIndexAndDisplacement64Match. Such patterns are less likely
to be proven within bounds and thus not taken by these paths anyway,
so they are left for future work.

This patch gives a useful x0.92 improvement in run time for an asm.js
zlib benchmark when using index masking to avoid bounds checks.

BUG=

[dougc, 2015-01-28 05:39:19]

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

[Benedikt Meurer, 2015-01-28 05:55:34]

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

[Benedikt Meurer, 2015-01-28 05:55:34]

I think this problem is not limited to x64, but affects all 64bit platforms, so
we may need to think about a way to push/hoist the ChangeUint32ToUint64
operations up.

https://codereview.chromium.org/860283004/diff/1/src/compiler/x64/instruction...
File src/compiler/x64/instruction-selector-x64.cc (right):

https://codereview.chromium.org/860283004/diff/1/src/compiler/x64/instruction...
src/compiler/x64/instruction-selector-x64.cc:14: static bool OpZeroExtends(Node
*value) {
Use anonymous namespace instead of static.

https://codereview.chromium.org/860283004/diff/1/src/compiler/x64/instruction...
src/compiler/x64/instruction-selector-x64.cc:132: if (index32->opcode() ==
IrOpcode::kInt32Add) {
I don't think this optimization is sound. You basically assume that
ChangeUint32ToUint64(Int32Add(x,y)) is equivalent to
Int64Add(ChangeUint32ToUint64(x), ChangeUint32ToUint64(y)), which doesn't hold
in general.

https://codereview.chromium.org/860283004/diff/1/src/compiler/x64/instruction...
src/compiler/x64/instruction-selector-x64.cc:134: if (madd.right().HasValue() &&
OpZeroExtends(madd.left().node()) &&
CanBeImmediate(mdd.right().node()) implies madd.right().HasValue(), so you don't
need to check madd.right().HasValue().

[dougc, 2015-01-29 08:14:08]

Thank you for the feedback.

There was a problem with the difference between the int32 addition the int64
address calculation - the 32 bit argument to the addition operation is not sign
extended when used in an 64 bit address calculation operation so the calculation
failed when it was negative. The constant offset is sign extended. It appears
that a simple type check can avoid this by only applying the optimization when
the argument to the 32 bit addition operation is not negative. Some source
comments have been added to explain this.

Can you see any other issues?

It may well be cleaner to transform the int32 addition to an int64 addition
earlier and I'll give this a try too.

[Benedikt Meurer, 2015-01-29 08:17:28]

On 2015/01/29 at 08:14:08, dtc-v8 wrote:
> Thank you for the feedback.
> 
> There was a problem with the difference between the int32 addition the int64
address calculation - the 32 bit argument to the addition operation is not sign
extended when used in an 64 bit address calculation operation so the calculation
failed when it was negative. The constant offset is sign extended. It appears
that a simple type check can avoid this by only applying the optimization when
the argument to the 32 bit addition operation is not negative. Some source
comments have been added to explain this.
> 
> Can you see any other issues?
> 
> It may well be cleaner to transform the int32 addition to an int64 addition
earlier and I'll give this a try too.

Well, the problem is still the same: 

ChangeUint32ToUint64(Int32Add(x,y)) is not equivalent to
Int64Add(ChangeUint32ToUint64(x), ChangeUint32ToUint64(y)), but to
Word64And(Int64Add(ChangeUint32ToUint64(x), ChangeUint32ToUint64(y)),
0xffffffff), so the optimization itself is unsound. It might be safe for asm.js
heap access patterns, where we end with Load/Store operations, but in general
that's not true.

[dougc, 2015-01-29 09:23:43]

On 2015/01/29 08:17:28, Benedikt Meurer wrote:
> On 2015/01/29 at 08:14:08, dtc-v8 wrote:
...
> > 
> > Can you see any other issues?
> > 
> > It may well be cleaner to transform the int32 addition to an int64 addition
> earlier and I'll give this a try too.
> 
> Well, the problem is still the same: 
> 
> ChangeUint32ToUint64(Int32Add(x,y)) is not equivalent to
> Int64Add(ChangeUint32ToUint64(x), ChangeUint32ToUint64(y)), but to
> Word64And(Int64Add(ChangeUint32ToUint64(x), ChangeUint32ToUint64(y)),
> 0xffffffff), so the optimization itself is unsound. It might be safe for
asm.js
> heap access patterns, where we end with Load/Store operations, but in general
> that's not true.

Even if this logic is hoisted earlier it will be similar, so the required
constraints need to be understood.

A 32 bit addition is not equivalent to a 64 bit addition in general but this is
a very useful optimization and the question is if it is valid under the
constraints?

The index (the result of the addition) is constrained to be a 31 bit unsigned
integer whether calculated using 32 bit or 64 bit addition.

The offset (an argument to the addition) is a signed 32 bit integer that is sign
extended to 64 bits in the 64 bit addition.

The other argument to the addition operation has been constrained to be a 31 bit
unsigned integer that is zero extended to 64 bits in the address calculation.

The original addition is an Int32Add, which I presume means it truncates or was
proven to not overflow so truncation was not an issue. This could be produced by
a truncating u[i>>n] asm.js style access or a u[i] un-truncated access that is
proven to not overflow. This is not asm.js specific.

If there are cases that are not valid then an example would be very helpful?

[Benedikt Meurer, 2015-01-30 04:50:09]

I think this is something that can only be solved properly by adding support for
64bit integers to representation selection (i.e. simplified lowering).

Otherwise it is unsound because the index is not guaranteed to be constrained to
31-bit unsigned integer.

[Benedikt Meurer, 2015-01-30 06:04:40]

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

[dougc, 2015-01-30 12:13:20]

On 2015/01/30 04:50:09, Benedikt Meurer wrote:
> I think this is something that can only be solved properly by adding support
for
> 64bit integers to representation selection (i.e. simplified lowering).
> 
> Otherwise it is unsound because the index is not guaranteed to be constrained
to
> 31-bit unsigned integer.

The index is constrained to be a 31-bit unsigned integer because: it is an array
buffer index, and the maximum array buffer size is 2GB, and at this point in the
code the index is known to be within bounds?

Hydrogen has logic for dehoisting these offsets too, see hydrogen-dehoist.cc,
and I have some wip patches to generalize this to work better on asm.js style
accesses. The turbofan code looks much cleaner.

[Benedikt Meurer, 2015-01-30 12:15:03]

> The index is constrained to be a 31-bit unsigned integer because: it is an
array buffer index, and the maximum array buffer size is 2GB, and at this point
in the code the index is known to be within bounds?

That's only true for asm.js heap access, not for Load/Store in general.

[dougc, 2015-01-30 12:36:57]

On 2015/01/30 12:15:03, Benedikt Meurer wrote:
> > The index is constrained to be a 31-bit unsigned integer because: it is an
> array buffer index, and the maximum array buffer size is 2GB, and at this
point
> in the code the index is known to be within bounds?
> 
> That's only true for asm.js heap access, not for Load/Store in general.

Could you help me understand what aspect of asm.js this is limited to?

This code path is only taken for typed arrays, when
IsExternalArrayElementsKind() is true? E.g. See the logic in
JSTypedLowering::ReduceJSLoadProperty().

[Benedikt Meurer, 2015-02-04 18:39:34]

On 2015/01/30 12:36:57, dougc wrote:
> On 2015/01/30 12:15:03, Benedikt Meurer wrote:
> > > The index is constrained to be a 31-bit unsigned integer because: it is an
> > array buffer index, and the maximum array buffer size is 2GB, and at this
> point
> > in the code the index is known to be within bounds?
> > 
> > That's only true for asm.js heap access, not for Load/Store in general.
> 
> Could you help me understand what aspect of asm.js this is limited to?
> 
> This code path is only taken for typed arrays, when
> IsExternalArrayElementsKind() is true? E.g. See the logic in
> JSTypedLowering::ReduceJSLoadProperty().

As said, that is the current implementation, which only considers asm.js. But we
will be targeting regular JavaScript soon(ish), and that means you can have
abitrary Loads/Stores, i.e. even Loads/Stores for Blink DOM objects or other
arrays/objects/whatever. You cannot make any assumptions about the index in that
case.

[dougc, 2015-02-05 13:36:07]

On 2015/02/04 18:39:34, Benedikt Meurer wrote:
> On 2015/01/30 12:36:57, dougc wrote:
> > On 2015/01/30 12:15:03, Benedikt Meurer wrote:
> > > > The index is constrained to be a 31-bit unsigned integer because: it is
an
> > > array buffer index, and the maximum array buffer size is 2GB, and at this
> > point
> > > in the code the index is known to be within bounds?
> > > 
> > > That's only true for asm.js heap access, not for Load/Store in general.
> > 
> > Could you help me understand what aspect of asm.js this is limited to?
> > 
> > This code path is only taken for typed arrays, when
> > IsExternalArrayElementsKind() is true? E.g. See the logic in
> > JSTypedLowering::ReduceJSLoadProperty().
> 
> As said, that is the current implementation, which only considers asm.js. But
we
> will be targeting regular JavaScript soon(ish), and that means you can have
> abitrary Loads/Stores, i.e. even Loads/Stores for Blink DOM objects or other
> arrays/objects/whatever. You cannot make any assumptions about the index in
that
> case.

It's true that asm.js heap access patterns are a subset of the code this path
supports, but this path is not limited to asm.js, rather it deals with typed
array element access. For example u32[i+K] is supported by this path but is not
asm.js.

It would appear that LoadElement() and StoreElement() are only used when the
index is within bounds, as they do no bounds checking, so even if these were
used for other objects they would only be used when the index is known to be
within bounds of the object?  Further ReduceJSLoadProperty() would be checking
that the index is within the 2G limit. Thus even in future the index will be an
unsigned 31-bit integer if the LoadElement() or StoreElement() paths are taken?

Transforming the addition to a 64 bit operation earlier might also frustrate
later optimizations. For example the right and left shift are optimized away via
some patterns etc, and the addition moved over a low bit masking operation. A 64
bit op might require more general pattern matching and might not even capture
the constrains needed to satisfy the transforms. It might be sound to lower to
32 bit ops when possible.

If the code is in flux then I can wait and rework the patch in future.

[Benedikt Meurer, 2015-02-05 13:53:33]

On 2015/02/05 at 13:36:07, dtc-v8 wrote:
> On 2015/02/04 18:39:34, Benedikt Meurer wrote:
> > On 2015/01/30 12:36:57, dougc wrote:
> > > On 2015/01/30 12:15:03, Benedikt Meurer wrote:
> > > > > The index is constrained to be a 31-bit unsigned integer because: it
is an
> > > > array buffer index, and the maximum array buffer size is 2GB, and at
this
> > > point
> > > > in the code the index is known to be within bounds?
> > > > 
> > > > That's only true for asm.js heap access, not for Load/Store in general.
> > > 
> > > Could you help me understand what aspect of asm.js this is limited to?
> > > 
> > > This code path is only taken for typed arrays, when
> > > IsExternalArrayElementsKind() is true? E.g. See the logic in
> > > JSTypedLowering::ReduceJSLoadProperty().
> > 
> > As said, that is the current implementation, which only considers asm.js.
But we
> > will be targeting regular JavaScript soon(ish), and that means you can have
> > abitrary Loads/Stores, i.e. even Loads/Stores for Blink DOM objects or other
> > arrays/objects/whatever. You cannot make any assumptions about the index in
that
> > case.
> 
> It's true that asm.js heap access patterns are a subset of the code this path
supports, but this path is not limited to asm.js, rather it deals with typed
array element access. For example u32[i+K] is supported by this path but is not
asm.js.
> 
> It would appear that LoadElement() and StoreElement() are only used when the
index is within bounds, as they do no bounds checking, so even if these were
used for other objects they would only be used when the index is known to be
within bounds of the object?  Further ReduceJSLoadProperty() would be checking
that the index is within the 2G limit. Thus even in future the index will be an
unsigned 31-bit integer if the LoadElement() or StoreElement() paths are taken?
> 
> Transforming the addition to a 64 bit operation earlier might also frustrate
later optimizations. For example the right and left shift are optimized away via
some patterns etc, and the addition moved over a low bit masking operation. A 64
bit op might require more general pattern matching and might not even capture
the constrains needed to satisfy the transforms. It might be sound to lower to
32 bit ops when possible.
> 
> If the code is in flux then I can wait and rework the patch in future.

Yes, let's first get the missing bits for JavaScript in.

[Benedikt Meurer, 2016-04-19 04:22:38]

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