[turbofan] fine grained in-block move optimization

[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves.

For example, there are improvements on x64 in Emscripten (Bullet, in
particular) , JetStream geomean, Embenchen (zlib).

In the process of making this change, I noticed we can separate the
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=

Committed: https://crrev.com/1ecf58f409668ccd805fca2eef5f2350071ee49b
Cr-Commit-Position: refs/heads/master@{#33715}

[Mircea Trofin, 2016-01-28 03:15:40]

Description was changed from

==========
[turbofan] piecemeal move pushdown
BUG=
==========

to

==========
So far, we've been moving down gaps wholesale. This change moves
individual move operations instead.

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

[Mircea Trofin, 2016-01-28 03:15:40]

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

[Mircea Trofin, 2016-01-28 03:24:44]

Let me know if you'd prefer me making this smaller first.

[Jarin, 2016-02-03 05:25:18]

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
File src/compiler/move-optimizer.cc (right):

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:124: // ret makes any assignment before it
unnecessary, except for the one
Nit: Start comments with capital letters, please. (Here and below.)

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:145: // where it appears on the LHS
Nit: Dot at the end of sentences. (Here and below.)

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:152: // Same for temp operands.
I do not understand why it is still ok to move assignments where the output
appears on LHS. Would not we then end up with different value in the
destination?

I suppose it should not happen that output overwrites previous move, but still
sounds dangerous.

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:159: for (MoveOperands* move :
*from->parallel_moves()[0]) {
from->parallel_moves[0] ==> from_moves

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:163: src_cant_be.insert(move->destination());
Again, would not it be also bad to swap "dest = y" with "dest = z"?

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
File src/compiler/move-optimizer.h (right):

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.h:32: // Attempt to push down to the last
instruction those moves that can.
Could not parse the comment. Please, rewrite.

(Does it mean "Push the moves in {block} as late as possible."?

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.h:40: // that remain behind.
Again, could not really parse that comment.

[Jarin, 2016-02-03 05:28:29]

One more thing: could you write down the motivation for this change? Does it
improve any benchmark? Or does it visibly improve register allocation for some
important examples? We should have a good justification for adding so much
complexity to the allocator.

[Mircea Trofin, 2016-02-04 05:22:39]

Description was changed from

==========
So far, we've been moving down gaps wholesale. This change moves
individual move operations instead.

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

to

==========
So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves.

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

[Mircea Trofin, 2016-02-04 05:23:32]

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
File src/compiler/move-optimizer.cc (right):

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:124: // ret makes any assignment before it
unnecessary, except for the one
On 2016/02/03 05:25:17, Jarin wrote:
> Nit: Start comments with capital letters, please. (Here and below.)

Done.

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:145: // where it appears on the LHS
On 2016/02/03 05:25:17, Jarin wrote:
> Nit: Dot at the end of sentences. (Here and below.)

Done.

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:152: // Same for temp operands.
On 2016/02/03 05:25:17, Jarin wrote:
> I do not understand why it is still ok to move assignments where the output
> appears on LHS. Would not we then end up with different value in the
> destination?
> 
> I suppose it should not happen that output overwrites previous move, but still
> sounds dangerous.

It's because we first perform RemoveClobberedDestinations first. Added a
comment. 

I could also factor a bit the code in RemoveClobberedDestinations and add a
DCHECK in MigrateMoves, but may be overkill?

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:159: for (MoveOperands* move :
*from->parallel_moves()[0]) {
On 2016/02/03 05:25:17, Jarin wrote:
> from->parallel_moves[0] ==> from_moves

Done.

https://codereview.chromium.org/1634093002/diff/240001/src/compiler/move-opti...
src/compiler/move-optimizer.cc:163: src_cant_be.insert(move->destination());
On 2016/02/03 05:25:18, Jarin wrote:
> Again, would not it be also bad to swap "dest = y" with "dest = z"?

By this stage, we did CompressMoves which takes care of that. Added comment.

[Jarin, 2016-02-04 05:32:10]

Description was changed from

==========
So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves.

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

to

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves.

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

[Jarin, 2016-02-04 05:33:39]

lgtm. Thanks for clarifying the comments. 

Could you add a line to the description that says which benchmarks have been
improved by this?

[Mircea Trofin, 2016-02-04 05:42:59]

Description was changed from

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves.

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

to

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves. For example, there are improvements on x64 in
Emscripten (Bullet, in particular) , JetStream geomean, Embenchen (zlib).

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

[Mircea Trofin, 2016-02-04 05:43:22]

The CQ bit was checked by mtrofin@chromium.org

[commit-bot: I haz the power, 2016-02-04 05:43:28]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1634093002/280001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1634093002/280001

[Mircea Trofin, 2016-02-04 05:47:02]

Description was changed from

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves. For example, there are improvements on x64 in
Emscripten (Bullet, in particular) , JetStream geomean, Embenchen (zlib).

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

to

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves. 

For example, there are improvements on x64 in Emscripten (Bullet, in 
particular) , JetStream geomean, Embenchen (zlib).

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

[commit-bot: I haz the power, 2016-02-04 06:30:01]

Description was changed from

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves. 

For example, there are improvements on x64 in Emscripten (Bullet, in 
particular) , JetStream geomean, Embenchen (zlib).

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

to

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves. 

For example, there are improvements on x64 in Emscripten (Bullet, in 
particular) , JetStream geomean, Embenchen (zlib).

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

[commit-bot: I haz the power, 2016-02-04 06:30:01]

Committed patchset #15 (id:280001)

[commit-bot: I haz the power, 2016-02-04 06:30:44]

Description was changed from

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves. 

For example, there are improvements on x64 in Emscripten (Bullet, in 
particular) , JetStream geomean, Embenchen (zlib).

In the process of making this change, I noticed we can separate the 
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we 
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=
==========

to

==========
[turbofan] fine grained in-block move optimization

So far, we've been moving down gaps wholesale. This change moves
individual move operations instead. This improves some benchmarks,
and should overall reduce code size, because it improves the chance of
reducing the number of moves.

For example, there are improvements on x64 in Emscripten (Bullet, in
particular) , JetStream geomean, Embenchen (zlib).

In the process of making this change, I noticed we can separate the
tasks performed by the move optimizer, as follows:

- group gaps into 1
- push gaps down, jumping instructions (these 2 were together before)
- merge blocks (and then push gaps down)
- finalize

We can do without a finalization list. This avoids duplicating storage -
we already have the list of instructions; it also simplifies the logic, since,
with this change, we may process an instruction's gap twice.

Compile time doesn't regress much (see pathological cases), but we
may want to avoid the allocations of the few sets used in the new code.
I'll do that in a subsequent change.

BUG=

Committed: https://crrev.com/1ecf58f409668ccd805fca2eef5f2350071ee49b
Cr-Commit-Position: refs/heads/master@{#33715}
==========

[commit-bot: I haz the power, 2016-02-04 06:30:45]

Patchset 15 (id:??) landed as
https://crrev.com/1ecf58f409668ccd805fca2eef5f2350071ee49b
Cr-Commit-Position: refs/heads/master@{#33715}