Implement optional turbofan UnalignedLoad and UnalignedStore operators

Implement optional turbofan UnalignedLoad and UnalignedStore operators

Implement optional turbofan UnalignedLoad and
UnalignedStore operators used to support unaligned
memory accesses in WASM. These operators must be used
on architectures that do not support missalinged memory access.

Architectures that do support unaligned access don't 
need to implement these operators. In that case regular
Load and Store turbofan operators are used.

BUG=mjsunit/wasm/module-memory

[ivica.bogosavljevic, 2016-03-11 16:44:53]

Description was changed from

==========
Implement turbofan UnalignedLoad and UnalignedStore operators

Implement turbofan UnalignedLoad and UnalignedStore operators
used to support unaligned memory accesses in WASM. These operators
must be used on architectures that do not support mimsalinged
memory access.
This is a draft and implementation is given for MIPS32 only.

BUG=mjsunit/wasm/module-memory
==========

to

==========
Implement turbofan UnalignedLoad and UnalignedStore operators

Implement turbofan UnalignedLoad and UnalignedStore operators
used to support unaligned memory accesses in WASM. These operators
must be used on architectures that do not support mimsalinged
memory access.
This is a draft and implementation is given for MIPS32 only.

BUG=mjsunit/wasm/module-memory
==========

[ivica.bogosavljevic, 2016-03-11 16:44:53]

ivica.bogosavljevic@imgtec.com changed reviewers:
+ akos.palfi@imgtec.com, balazs.kilvady@imgtec.com, gergely.kis@imgtec.com,
ilija.pavlovic@imgtec.com, marija.antic@imgtec.com, miran.karic@imgtec.com

[ivica.bogosavljevic, 2016-03-11 16:45:04]

PTAL

[ivica.bogosavljevic, 2016-03-11 16:45:06]

PTAL

[Paul Lind, 2016-03-12 05:07:45]

plind44@gmail.com changed reviewers:
+ plind44@gmail.com, titzer@chromium.org

[Paul Lind, 2016-03-12 05:07:46]

This looks like it's going the right direction to me. 

However, I wonder if it is possible to modify existing
LoadRepresentation/StoreRepresentation in some clever way, or the calls to
VisitLoad()/VisitStore(), to minimize changes to the other arch's which don't
care about alignment.

With your approach it looks like you'll have new visitors in all arch's (though
maybe they just call existing VisitLoad()/VisitStore()?). If you have a nice way
to do this, maybe you can add a non-mips arch to your CL now to show us how that
could work.

Ben, do you have any suggestions for how this can work cleanly?

nits: spell err 'misaligned' in commit msg. Your 'draft/mips32' comment needs to
go away at some point. Also, some of your comments in our slack channel might be
good to add to commit message for further explanation of the alignment
attributes.

https://codereview.chromium.org/1779713009/diff/1/src/compiler/mips/code-gene...
File src/compiler/mips/code-generator-mips.cc (right):

https://codereview.chromium.org/1779713009/diff/1/src/compiler/mips/code-gene...
src/compiler/mips/code-generator-mips.cc:1167: UNREACHABLE();
I'm guessing you just don't have implementation yet, and this will be removed?
Seems like the instruction-selector can generate this instruction....

[ivica.bogosavljevic, 2016-03-16 11:59:36]

Description was changed from

==========
Implement turbofan UnalignedLoad and UnalignedStore operators

Implement turbofan UnalignedLoad and UnalignedStore operators
used to support unaligned memory accesses in WASM. These operators
must be used on architectures that do not support mimsalinged
memory access.
This is a draft and implementation is given for MIPS32 only.

BUG=mjsunit/wasm/module-memory
==========

to

==========
Implement optional turbofan UnalignedLoad and UnalignedStore operators

Implement optional turbofan UnalignedLoad and  UnalignedStore operators used to
support unaligned memory accesses in WASM. These operators must be used on
architectures that do not support missalinged memory access.
Architectures that do support unaligned access don't need to implement these
operators. In that case regular Load and Store turbofan operators are used.


BUG=mjsunit/wasm/module-memory
==========

[ivica.bogosavljevic, 2016-03-16 12:00:09]

Description was changed from

==========
Implement optional turbofan UnalignedLoad and UnalignedStore operators

Implement optional turbofan UnalignedLoad and  UnalignedStore operators used to
support unaligned memory accesses in WASM. These operators must be used on
architectures that do not support missalinged memory access.
Architectures that do support unaligned access don't need to implement these
operators. In that case regular Load and Store turbofan operators are used.


BUG=mjsunit/wasm/module-memory
==========

to

==========
Implement optional turbofan UnalignedLoad and UnalignedStore operators

Implement optional turbofan UnalignedLoad and
UnalignedStore operators used to support unaligned
memory accesses in WASM. These operators must be used
on architectures that do not support missalinged memory access.
Architectures that do support unaligned access don't 
need to implement these operators. In that case regular
Load and Store turbofan operators are used.

BUG=mjsunit/wasm/module-memory
==========

[ivica.bogosavljevic, 2016-03-16 12:00:18]

Description was changed from

==========
Implement optional turbofan UnalignedLoad and UnalignedStore operators

Implement optional turbofan UnalignedLoad and
UnalignedStore operators used to support unaligned
memory accesses in WASM. These operators must be used
on architectures that do not support missalinged memory access.
Architectures that do support unaligned access don't 
need to implement these operators. In that case regular
Load and Store turbofan operators are used.

BUG=mjsunit/wasm/module-memory
==========

to

==========
Implement optional turbofan UnalignedLoad and UnalignedStore operators

Implement optional turbofan UnalignedLoad and
UnalignedStore operators used to support unaligned
memory accesses in WASM. These operators must be used
on architectures that do not support missalinged memory access.

Architectures that do support unaligned access don't 
need to implement these operators. In that case regular
Load and Store turbofan operators are used.

BUG=mjsunit/wasm/module-memory
==========

[ivica.bogosavljevic, 2016-03-16 12:00:57]

PTAL

[ivica.bogosavljevic, 2016-03-22 14:48:29]

Tested on arm simulator and x64 simulator and no regressions.

Tested on MIPS32EL board and MIPS64EB board, MIPS32 and MIPS64 simulator and no
regressions.

This patch is ready to land.

[titzer, 2016-03-22 15:00:20]

I agree this is generally the right approach. Thanks for doing this.

Some ARM variants also have unaligned loads/stores, CC'ing.

https://codereview.chromium.org/1779713009/diff/100001/src/compiler/ia32/inst...
File src/compiler/ia32/instruction-selector-ia32.cc (right):

https://codereview.chromium.org/1779713009/diff/100001/src/compiler/ia32/inst...
src/compiler/ia32/instruction-selector-ia32.cc:306: // Architecture supports
unaliged access, therefore VisitLoad is used instead
s/unaliged/unaligned/

here and in other files

https://codereview.chromium.org/1779713009/diff/100001/src/compiler/machine-o...
File src/compiler/machine-operator-reducer.cc (right):

https://codereview.chromium.org/1779713009/diff/100001/src/compiler/machine-o...
src/compiler/machine-operator-reducer.cc:717: Reduction
MachineOperatorReducer::ReduceUnalignedStore(Node* node) {
This looks like an exact duplicate of the above method. Can you factor this out
to be a common routine?

https://codereview.chromium.org/1779713009/diff/100001/src/compiler/wasm-comp...
File src/compiler/wasm-compiler.h (right):

https://codereview.chromium.org/1779713009/diff/100001/src/compiler/wasm-comp...
src/compiler/wasm-compiler.h:122: uint32_t offset, bool aligned);
This alignment parameter will be more than a boolean. It's actually a power two,
under the theory that we can generate better code for a word32 load aligned on a
2-byte boundary.

[martyn.capewell, 2016-03-24 11:01:25]

On 2016/03/22 15:00:20, titzer wrote:

> Some ARM variants also have unaligned loads/stores, CC'ing.

For 32-bit ARM, single integer loads and stores can be unaligned since ARMv6
(ARM11xx), but we still require aligned FP loads and stores. I think the type
information is available to handle this in instruction selection/code
generation.

64-bit ARM supports unaligned for integer and FP.

[ivica.bogosavljevic, 2016-03-28 09:04:40]

Implemented remarks from code review, please have a look!

[titzer, 2016-03-29 08:42:49]

https://codereview.chromium.org/1779713009/diff/100001/src/compiler/machine-o...
File src/compiler/machine-operator-reducer.cc (right):

https://codereview.chromium.org/1779713009/diff/100001/src/compiler/machine-o...
src/compiler/machine-operator-reducer.cc:717: Reduction
MachineOperatorReducer::ReduceUnalignedStore(Node* node) {
On 2016/03/22 15:00:20, titzer wrote:
> This looks like an exact duplicate of the above method. Can you factor this
out
> to be a common routine?

New patchset got lost here?

https://codereview.chromium.org/1779713009/diff/120001/src/compiler/int64-low...
File src/compiler/int64-lowering.cc (right):

https://codereview.chromium.org/1779713009/diff/120001/src/compiler/int64-low...
src/compiler/int64-lowering.cc:129: case IrOpcode::kUnalignedLoad: {
Can you factor out the common code between load/unaligned_load and
store/unaligned_store?

[ivica.bogosavljevic, 2016-03-30 14:18:46]

Removed duplicate code in int64-lowering and machine-code-reducer.
PTAL

[ivica.bogosavljevic, 2016-04-04 14:38:53]

Reminder :)

[titzer, 2016-04-04 14:57:30]

Now with a bit more perspective on this CL, I think we can do this in a pretty
general way that is also platform-independent in wasm-compiler.cc.

If we pass in the alignment parameter from the ast-decoder.cc, we can have
wasm-compiler.cc generate multiple loads/stores as graph nodes, and then no
platform-specific code is necessary. We can then independently improve the
instruction-selector on MIPS to match the lwl/lwr pairs. We already have a bit
of infrastructure to do this for x64 memory operand combining.

[ivica.bogosavljevic, 2016-04-07 07:45:36]

On 2016/04/04 14:57:30, titzer wrote:
> Now with a bit more perspective on this CL, I think we can do this in a pretty
> general way that is also platform-independent in wasm-compiler.cc.
> 
> If we pass in the alignment parameter from the ast-decoder.cc, we can have
> wasm-compiler.cc generate multiple loads/stores as graph nodes, and then no
> platform-specific code is necessary. We can then independently improve the
> instruction-selector on MIPS to match the lwl/lwr pairs. We already have a bit
> of infrastructure to do this for x64 memory operand combining.

The suggested approach is somewhat different than presented here. Instead
of having UnalingedLoad and UnalignedStore operations, we implement
unaligned load or store by using combination of single byte load and store
and bitshifting. In instruction-selector-mips, when this array of operations
is detected, it is replaced by lwl/lwr combination.

[titzer, 2016-04-08 13:21:11]

On 2016/04/07 07:45:36, ivica.bogosavljevic wrote:
> On 2016/04/04 14:57:30, titzer wrote:
> > Now with a bit more perspective on this CL, I think we can do this in a
pretty
> > general way that is also platform-independent in wasm-compiler.cc.
> > 
> > If we pass in the alignment parameter from the ast-decoder.cc, we can have
> > wasm-compiler.cc generate multiple loads/stores as graph nodes, and then no
> > platform-specific code is necessary. We can then independently improve the
> > instruction-selector on MIPS to match the lwl/lwr pairs. We already have a
bit
> > of infrastructure to do this for x64 memory operand combining.
> 
> The suggested approach is somewhat different than presented here. Instead
> of having UnalingedLoad and UnalignedStore operations, we implement
> unaligned load or store by using combination of single byte load and store
> and bitshifting. In instruction-selector-mips, when this array of operations
> is detected, it is replaced by lwl/lwr combination.

That is correct. I think that will be much cleaner in the end and have the added
bonus of working on the other architectures where unaligned loads/stores can be
a problem.

[ivica.bogosavljevic, 2016-04-20 10:04:02]

PTAL

The latest patch implements unaligned access differently. Instead of having a
special UnalignedLoad and UnalignedStore operators, in wasm-compiler we simulate
unaliged load and unaligned store using a sequence of Load/Shift/Or and
Store/Shift/And operations. Later, in instruction-selector-mips.cc we try to
match these combinations of turbofan operators and reduce them to MIPS
instructions for unaligned load.
This is a draft only. it misses implementation of Unaligned store reducing.
Also, if it were to land, we would need to remove UnalignedLoad and
UnalignedStore operators and everything related to them.

Personally, I like the approach with UnalignedLoad and UnalignedStore operators
much better than this one, for these reasons:
1) Simulation of unaligned load and unaligned store is complicated compared to
emitting one UnalignedLoad or UnalignedStore operator
2) Simulation is different on big endian and little endian systems because low
and high end bytes are stored differently
3) It is possible that we "miss" some unaligned access simulation because it is
written differently, for example, some nodes get reduced elsewhere, or operands
in the And/Or operator gets switched. Technically, this is still an unaligned
access, but we failed to catch it and reduce it
4) Code for matching is complicated and wastes cycles if no matching occurs (we
need around 20 operators to simulate Load Double). If the matching code is bad,
we won't see any errors, just performance degradation we are unaware of

[titzer, 2016-04-20 12:59:26]

https://codereview.chromium.org/1779713009/diff/160001/src/compiler/wasm-comp...
File src/compiler/wasm-compiler.cc (right):

https://codereview.chromium.org/1779713009/diff/160001/src/compiler/wasm-comp...
src/compiler/wasm-compiler.cc:2419: for (int i = 0; i < numberOfLoads; i++) {
This is good enough for a first cut, since it does byte-by-byte loads, but in
the future we can also use the alignment to generate halfword-by-halfword
loads/stores.

https://codereview.chromium.org/1779713009/diff/160001/src/compiler/wasm-comp...
src/compiler/wasm-compiler.cc:2475: bool aligned = alignment >=
ElementSizeLog2Of(memtype.representation());
It's probably best to have a
machine()->UnalignedLoadSupported(MachineRepresentation, int alignment)

which is backed by appropriate flags.

[titzer, 2016-04-20 13:05:41]

On 2016/04/20 10:04:02, ivica.bogosavljevic wrote:
> PTAL
> 
> The latest patch implements unaligned access differently. Instead of having a
> special UnalignedLoad and UnalignedStore operators, in wasm-compiler we
simulate
> unaliged load and unaligned store using a sequence of Load/Shift/Or and
> Store/Shift/And operations. Later, in instruction-selector-mips.cc we try to
> match these combinations of turbofan operators and reduce them to MIPS
> instructions for unaligned load.
> This is a draft only. it misses implementation of Unaligned store reducing.
> Also, if it were to land, we would need to remove UnalignedLoad and
> UnalignedStore operators and everything related to them.
> 

Thanks for doing this! Comments below. I think the main benefits of this
approach will be more clear if the new approach is separated from the old
approach.

> Personally, I like the approach with UnalignedLoad and UnalignedStore
operators
> much better than this one, for these reasons:
> 1) Simulation of unaligned load and unaligned store is complicated compared to
> emitting one UnalignedLoad or UnalignedStore operator

Yes, that's true. But that extra complexity only impacts the
platform-independent code and the platforms that require unaligned loads/stores
to be emulated, rather than touching all platforms.


> 2) Simulation is different on big endian and little endian systems because low
> and high end bytes are stored differently



> 3) It is possible that we "miss" some unaligned access simulation because it
is
> written differently, for example, some nodes get reduced elsewhere, or
operands
> in the And/Or operator gets switched. Technically, this is still an unaligned
> access, but we failed to catch it and reduce it

> 4) Code for matching is complicated and wastes cycles if no matching occurs
(we
> need around 20 operators to simulate Load Double). If the matching code is
bad,
> we won't see any errors, just performance degradation we are unaware of

That can happen, so we should write many tests to make sure that the pattern
matching is working well. That is the approach we generally take with other
instruction selection matches.

In general we expect unaligned accesses to be rare; they should only occur when
the producer _knows_ the access is unaligned and doesn't want to pay a 1000x
perform penalty due to emulation by the OS/trap handler.

One other benefit of doing the pattern matching in the instruction selector is
that it might catch cases where the user code itself does the individual loads
and stores. Then the pattern matcher will find it and emit better code. That
might even make sense to do on other platforms that do support unaligned loads
and stores. E.g. even on Intel we might want to pattern match user code that
does 4-1 byte loads and then does the equivalent of a "bswap".

[ivica.bogosavljevic, 2016-05-04 11:16:20]

This Code Review is split into separate reviews and moved.

The architecture independent part of emulating unaligned access in WASM is
available here:

https://codereview.chromium.org/1928513002/