Change the algorithm and generated code for parallel moves on IA32.

Change the algorithm and generated code for parallel moves on IA32.

Instead of spilling and then immediately restoring eax to resolve
memory to memory moves, the gap move resolver now tracks registers
that are known to be free and uses one if available.  If not it spills
but restores lazily when the spilled value is needed or at the end of
the algorithm.

Instead of using esi for resolving cycles and assuming it is free to
overwrite because it can be rematerialized, the gap move resolver now
resolves cycles using swaps, possibly using a free register as above.

The algorithm is also changed to be simpler: a recursive depth-first
traversal of the move dependence graph.  It uses a list of moves to be
performed (because it mutates the moves themselves), but does not use
any auxiliary structure other than the control stack.  It does not
build up a separate list of scheduled moves to be interpreted by the
code generate, but emits code on the fly.

[Kevin Millikin (Chromium), 2011-01-14 15:18:09]

Bill and Florian, could you take a look at this?

The gyp changes are out dated so I will fix them.  There is also a renaming-only
change to make in the other platform files (I found "to" and "from" to be
confusing in the code because they're directions, not locations places.  I've
changed them to "source" and "destination").

[Kevin Millikin (Chromium), 2011-01-17 08:20:20]

I just updated a more polished version.  Compilation is fixed on all platforms,
XMM register use counts are removed (they're not used), and double stack slot
swap is implemented.

Ready for review.

[fschneider, 2011-01-17 09:44:16]

LGTM.

This is much better than the old code. Please also check if we hit all the cases
in EmitMove and EmitSwap in our tests.

http://codereview.chromium.org/6263005/diff/2001/src/ia32/lithium-gap-resolve...
File src/ia32/lithium-gap-resolver-ia32.cc (right):

http://codereview.chromium.org/6263005/diff/2001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:64: if (!moves_[i].IsEliminated()) {
Not sure: can a move with a constant source operand be eliminated by PerformMove
at all?

http://codereview.chromium.org/6263005/diff/2001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:87: }
How about a slot assert that verifies the move-graph property that no operand is
used as a destination more than once?

http://codereview.chromium.org/6263005/diff/2001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:367: // spilling src at this point. 
Memory-to-memory swaps are a rare case.
The comment mentions mem-to-mem swaps which are not handled here, but further
below.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:84: for (int i = moves->length() - 1; i >=
0; --i) {
Would it make the code more concise by passing a LMoveOperands* to
PerformMove/RemoveMove/...?

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:92: // Each call to this function performs
a move and deletes it from the move
Can we ASSSERT(!moves_[index].IsPending()) here? 

I think this is already covered by the !IsRedundant(), but
the predicates are a little confusing.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:104: LOperand* destination =
moves_[index].destination();
Reason for iterating in reverse order? Maybe add a comment about it.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:148: }
Maybe pass a LMoveOperands* here.

http://codereview.chromium.org/6263005/diff/6001/src/lithium-allocator.h
File src/lithium-allocator.h (right):

http://codereview.chromium.org/6263005/diff/6001/src/lithium-allocator.h#newc...
src/lithium-allocator.h:359: bool IsEliminated() const { return source_ == NULL;
}
maybe ASSERT(destination_ == NULL) here, or 

return source_ == NULL && destination_ == NULL;

http://codereview.chromium.org/6263005/diff/6001/src/lithium.cc
File src/lithium.cc (right):

http://codereview.chromium.org/6263005/diff/6001/src/lithium.cc#newcode43
src/lithium.cc:43: for (int i = move_operands_.length() - 1; i >= 0; --i) {
I'd also change the printint order to i=0..length-1.

[Kevin Millikin (Chromium), 2011-01-17 10:13:08]

http://codereview.chromium.org/6263005/diff/2001/src/ia32/lithium-gap-resolve...
File src/ia32/lithium-gap-resolver-ia32.cc (right):

http://codereview.chromium.org/6263005/diff/2001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:64: if (!moves_[i].IsEliminated()) {
On 2011/01/17 09:44:16, fschneider wrote:
> Not sure: can a move with a constant source operand be eliminated by
PerformMove
> at all?

Only if it's the move passed to PerformMove.

http://codereview.chromium.org/6263005/diff/2001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:87: }
On 2011/01/17 09:44:16, fschneider wrote:
> How about a slot assert that verifies the move-graph property that no operand
is
> used as a destination more than once?

Good idea.  I will add it.

http://codereview.chromium.org/6263005/diff/2001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:367: // spilling src at this point. 
Memory-to-memory swaps are a rare case.
On 2011/01/17 09:44:16, fschneider wrote:
> The comment mentions mem-to-mem swaps which are not handled here, but further
> below.

I will fix it.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:84: for (int i = moves->length() - 1; i >=
0; --i) {
On 2011/01/17 09:44:16, fschneider wrote:
> Would it make the code more concise by passing a LMoveOperands* to
> PerformMove/RemoveMove/...?

A little, but I'm nervous about passing addresses of elements in a List.  Adding
to the list can reallocate the backing store.

Of course, here the algorithm doesn't necessarily work if we add to the list
after we start performing moves, but I'd still like to be careful.

If nothing else, the index makes it clear that the list is holding the pair and
passing a pointer obscures that a bit.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:92: // Each call to this function performs
a move and deletes it from the move
On 2011/01/17 09:44:16, fschneider wrote:
> Can we ASSSERT(!moves_[index].IsPending()) here? 
> 
> I think this is already covered by the !IsRedundant(), but
> the predicates are a little confusing.
> 

I agree the predicates are confusing (one has to read their implementation). 
That's probably unavoidable while keeping their names relatively short.

I will assert !IsPending() && !IsRedundant() (the assert will hit a null
dereference otherwise, which still catches the case but is a little less direct.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:104: LOperand* destination =
moves_[index].destination();
On 2011/01/17 09:44:16, fschneider wrote:
> Reason for iterating in reverse order? Maybe add a comment about it.

No reason, order is abitrary.  I'll just stick with forward so nobody has to
wonder about it.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:148: }
On 2011/01/17 09:44:16, fschneider wrote:
> Maybe pass a LMoveOperands* here.

I'd rather not.  We don't need to mutate it and it's another pointer into a
List.

http://codereview.chromium.org/6263005/diff/6001/src/lithium-allocator.h
File src/lithium-allocator.h (right):

http://codereview.chromium.org/6263005/diff/6001/src/lithium-allocator.h#newc...
src/lithium-allocator.h:359: bool IsEliminated() const { return source_ == NULL;
}
On 2011/01/17 09:44:16, fschneider wrote:
> maybe ASSERT(destination_ == NULL) here, or 
> 
> return source_ == NULL && destination_ == NULL;
> 

I'll assert (source_ != NULL || destination_ == NULL).

http://codereview.chromium.org/6263005/diff/6001/src/lithium.cc
File src/lithium.cc (right):

http://codereview.chromium.org/6263005/diff/6001/src/lithium.cc#newcode43
src/lithium.cc:43: for (int i = move_operands_.length() - 1; i >= 0; --i) {
On 2011/01/17 09:44:16, fschneider wrote:
> I'd also change the printint order to i=0..length-1.

I have no idea why it's backwards.  I'll change it.

[William Hesse, 2011-01-17 10:43:43]

LGTM.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
File src/ia32/lithium-gap-resolver-ia32.cc (right):

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:35: : cgen_(owner), moves_(32),
spilled_register_(-1) {
Can we use no_reg, or no_reg.code(), for no spilled register?

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:104: for (int i = moves_.length() - 1; i
>= 0; --i) {
Do we have the source use counts at this point?  I guess only for registers. 
Can we skip this loop if the destination is a register, and its use count is 0?

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:217: moves_.Rewind(0);
Shouldn't we have a List::Clear for Rewind(0), and also shouldn't Rewind()
assert that the new index < length_?

Obviously, this could go in a different change.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:265: // combinations are possible.
Are only combinations prohibited by the double vs word size difference, and
constants as destinations, prohibited, or are there other, hidden, non-supported
cases?

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:340: // spilling src at this point. 
Memory-to-memory swaps are a rare case.
Why is the memory-to-memory comment here?

http://codereview.chromium.org/6263005/diff/6001/src/lithium.cc
File src/lithium.cc (right):

http://codereview.chromium.org/6263005/diff/6001/src/lithium.cc#newcode53
src/lithium.cc:53: stream->Add(" = ");
Why not use a "move arrow" "<-" rather than "=" when printing it out?

[Kevin Millikin (Chromium), 2011-01-17 11:18:17]

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
File src/ia32/lithium-gap-resolver-ia32.cc (right):

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:35: : cgen_(owner), moves_(32),
spilled_register_(-1) {
On 2011/01/17 10:43:43, William Hesse wrote:
> Can we use no_reg, or no_reg.code(), for no spilled register?

That seems like a subtle type error.  This is an allocation index, not a
register code.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:104: for (int i = moves_.length() - 1; i
>= 0; --i) {
On 2011/01/17 10:43:43, William Hesse wrote:
> Do we have the source use counts at this point?  I guess only for registers. 
> Can we skip this loop if the destination is a register, and its use count is
0?

We have source use counts for the general purpose registers.  I wanted to keep
things simple: most gaps have 0, 1, or two moves.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:217: moves_.Rewind(0);
On 2011/01/17 10:43:43, William Hesse wrote:
> Shouldn't we have a List::Clear for Rewind(0), and also shouldn't Rewind()
> assert that the new index < length_?
> 
> Obviously, this could go in a different change.

We have List::Clear but it does something different (deallocates the backing
store).  At this point List::Rewind(0) is a V8 idiom.

http://codereview.chromium.org/6263005/diff/6001/src/ia32/lithium-gap-resolve...
src/ia32/lithium-gap-resolver-ia32.cc:265: // combinations are possible.
On 2011/01/17 10:43:43, William Hesse wrote:
> Are only combinations prohibited by the double vs word size difference, and
> constants as destinations, prohibited, or are there other, hidden,
non-supported
> cases?

The first.