Initial real implementation of simple merge for frames. Does not yet...

Initial real implementation of simple merge for frames.  Does not yet
support register->register moves (which never occur right now).

This is preliminary, so comments on what sort of abstractions it needs
are very welcome.

Committed: http://code.google.com/p/v8/source/detail?r=925

[Kevin Millikin (Chromium), 2008-12-04 13:00:33]

There are some pending issues to fix after this is submitted: we're getting
dangerously close to having to manage esi and edi registers properly across
calls; also the make mergable code for branches should be moved off the edge
leading to a branch and onto the taken edge.

[Kevin Millikin (Chromium), 2008-12-05 08:51:58]

I've uploaded a new patch set with a fix for the loop index bug.

[William Hesse, 2008-12-05 11:03:52]

I have only commented virtual-frame-ia32.cc so far, but here they are.

http://codereview.chromium.org/13127/diff/1/5
File src/virtual-frame-ia32.cc (left):

http://codereview.chromium.org/13127/diff/1/5#oldcode178
Line 178: while (min_count > 0) {
There is no increment of i in this loop.

http://codereview.chromium.org/13127/diff/1/5#oldcode196
Line 196: 
Assert that frame's count of result is 0.

http://codereview.chromium.org/13127/diff/209/13
File src/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/13127/diff/209/13#newcode184
Line 184: SyncRange(stack_pointer_ + 1, i);
I find it tricky to call this a lot with empty or negative ranges that do
nothing.  Comment?  Should SpillElementAt(i)
include this SyncRange call, since it is always a precondition?

http://codereview.chromium.org/13127/diff/209/13#newcode298
Line 298: // This code path is currently not triggered.  UNIMPLEMENTED is
Why is it not triggered?  What will make it be triggered?  Is it because we sync
or spill all before merges?  Or because we have no registers and constants?

http://codereview.chromium.org/13127/diff/209/13#newcode302
Line 302: Register reg = cgen_->allocator()->AllocateWithoutSpilling();
Does AllocateWithoutSpilling increment the allocator's register count for the
result?  If so, we are double counting when we call Use() later.  If not, how
does it record that it is used, so it doesn't return it twice?

http://codereview.chromium.org/13127/diff/209/13#newcode317
Line 317: } else {
// element is a memory element.

http://codereview.chromium.org/13127/diff/209/13#newcode328
Line 328: if (target.is_register()) {
Comment or assert that target will never be a source register later in the
frame. (or is it obvious that we got it from AllocateWithoutSpilling?)

http://codereview.chromium.org/13127/diff/209/13#newcode394
Line 394: SyncRange(stack_pointer_ + 1, i);
Won't this hit register-to-register moves and things we keep in registers with a
write to the stack?  Or is this OK, because something needs to be written to
that stack slot anyway?  In which case, the earlier source elements, which have
already been overwritten by the target, now have their sync bit set.  Is this a
problem with register-register moves that have not been done yet?  We are
syncing the previous value!

http://codereview.chromium.org/13127/diff/209/13#newcode411
Line 411: // Then register-to-register moves, not yet implemented.
Does a register moving to itself need any implementation?  Could we say that
these are currently handled, and allow them?

[William Hesse, 2008-12-05 11:55:45]

OK, not much to say about all the other files.

http://codereview.chromium.org/13127/diff/209/17
File src/codegen-ia32.cc (right):

http://codereview.chromium.org/13127/diff/209/17#newcode250
Line 250: CheckStack();
Were the only changes necessary to make CheckStack work without a SpillAll the
implementation of real merge on the jump targets?  There was already a SpillAll
on the slow case of CheckStack?  And will a return from the debugger put all the
values that should be in registers, in registers?  That is pretty amazing.

[Kevin Millikin (Chromium), 2008-12-05 13:00:52]

http://codereview.chromium.org/13127/diff/209/17
File src/codegen-ia32.cc (right):

http://codereview.chromium.org/13127/diff/209/17#newcode250
Line 250: CheckStack();
On 2008/12/05 11:55:46, William Hesse wrote:
> Were the only changes necessary to make CheckStack work without a SpillAll the
> implementation of real merge on the jump targets?  There was already a
SpillAll
> on the slow case of CheckStack?  And will a return from the debugger put all
the
> values that should be in registers, in registers?  That is pretty amazing.

It should work (at least, the debugger tests pass).  The call to the runtime is
followed by memory->register moves to restore the expected frame.  We just
needed the target frame to be mergable and code to implement the merge for the
elements it contained.

http://codereview.chromium.org/13127/diff/209/13
File src/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/13127/diff/209/13#newcode184
Line 184: SyncRange(stack_pointer_ + 1, i);
On 2008/12/05 11:03:53, William Hesse wrote:
> I find it tricky to call this a lot with empty or negative ranges that do
> nothing.  Comment?  Should SpillElementAt(i)
> include this SyncRange call, since it is always a precondition?
> 
> 

Zero sized ranges are OK, they allow us to have only two cases (below or above)
instead of three (below, immediately above, and way above) in code that already
has a lot of different cases.  This is the only call site with a true
negative-sized range.

I have moved the call to SyncRange inside SpillElementAt, which addresses both
of your concerns.

http://codereview.chromium.org/13127/diff/209/13#newcode298
Line 298: // This code path is currently not triggered.  UNIMPLEMENTED is
On 2008/12/05 11:03:53, William Hesse wrote:
> Why is it not triggered?  What will make it be triggered?  Is it because we
sync
> or spill all before merges?  Or because we have no registers and constants?

I wouldn't claim it's actually impossible to trigger it, but rather that it
doesn't get triggered by our entire test suite (including the Mozilla tests).

We can only have non-synced constants or duplicated registers due to the
interaction of literals and assignments (the only real non-spill code right
now).

http://codereview.chromium.org/13127/diff/209/13#newcode302
Line 302: Register reg = cgen_->allocator()->AllocateWithoutSpilling();
On 2008/12/05 11:03:53, William Hesse wrote:
> Does AllocateWithoutSpilling increment the allocator's register count for the
> result?  If so, we are double counting when we call Use() later.  If not, how
> does it record that it is used, so it doesn't return it twice?

Yes, we are double counting here and it's a bug.  Good catch.  I have fixed it.

http://codereview.chromium.org/13127/diff/209/13#newcode328
Line 328: if (target.is_register()) {
On 2008/12/05 11:03:53, William Hesse wrote:
> Comment or assert that target will never be a source register later in the
> frame. (or is it obvious that we got it from AllocateWithoutSpilling?)

I think it should be clear that the targets have all been allocated to us, ie,
are available to move values into immediately.

http://codereview.chromium.org/13127/diff/209/13#newcode394
Line 394: SyncRange(stack_pointer_ + 1, i);
On 2008/12/05 11:03:53, William Hesse wrote:
> Won't this hit register-to-register moves and things we keep in registers with
a
> write to the stack?  Or is this OK, because something needs to be written to
> that stack slot anyway?  In which case, the earlier source elements, which
have
> already been overwritten by the target, now have their sync bit set.  Is this
a
> problem with register-register moves that have not been done yet?  We are
> syncing the previous value!

It will hit register-to-register moves, but those elements don't hold their
final (synced or unsynced) value yet because we haven't done those moves.

We do need to be careful that sync bits match the expected frame, possibly with
a separate pass to clear ones that have been unexpectedly set.

I will make that a separate change.

http://codereview.chromium.org/13127/diff/209/13#newcode411
Line 411: // Then register-to-register moves, not yet implemented.
On 2008/12/05 11:03:53, William Hesse wrote:
> Does a register moving to itself need any implementation?  Could we say that
> these are currently handled, and allow them?
> 

Sure, but the ASSERT is really there to catch the case when they become
(possibly unexpectedly) enabled so we can consider what to do then.  So I'll
just leave the assert in.

[William Hesse, 2008-12-05 13:27:13]

Two possible changes are suggested, otherwise LGTM.
My stuff will use this, so I hope it checks in.

http://codereview.chromium.org/13127/diff/28/605
File src/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/13127/diff/28/605#newcode358
Line 358: __ push(source.reg());
Is this now SpillElement(i)?

http://codereview.chromium.org/13127/diff/28/605#newcode405
Line 405: __ push(source.reg());
Isn't this entire else block now just SpillElement(i)?

[Kevin Millikin (Chromium), 2008-12-05 13:47:42]

http://codereview.chromium.org/13127/diff/28/605
File src/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/13127/diff/28/605#newcode358
Line 358: __ push(source.reg());
On 2008/12/05 13:27:13, William Hesse wrote:
> Is this now SpillElement(i)?

Almost, ditto below.  New patch set coming.