Experimental: allow the virtual frame to explicitly indicate sharing...

Experimental: allow the virtual frame to explicitly indicate sharing
of memory (as well as register) elements.

A new type of frame element is introduced, which is a copy of a memory
or register element.  As a simple first implementation, sets of copies
are backed by their lowest frame element.  This requires adjusting the
backing store when moving elements up and down in the frame.

Copied elements have copy-on-write semantics---modifying the backing
frame element requires finding the appropriate new backing element and
updating all copies in the set.


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

[Kevin Millikin (Chromium), 2009-02-02 16:26:41]

Kasper & Bill, can you take a look at this?

Two caveats: 

(1) Much of the complication is involved in correctly implementing
VirtualFrame::MakeMergable, which is all going away shortly.  It will be
replaced with a function to calculate a target frame based on a set of incoming
frames, and that makes the frame mergable in one-pass if needed.

(2) There is a potential issue that I don't think arises in practice. Spilling
or syncing a virtual frame element (which is used by merging, make mergable, and
calling functions) can require (no more than) one free register to perform
memory-to-memory moves.  Obviously, we need to either ensure that this is always
the case or detect when it isn't and fall back on something (spilling an
arbitrary register to use, for instance).

[William Hesse, 2009-02-09 12:24:36]

OK, LGTM, with comments.  Will a flag or a linked list be added so that a base
element knows it has copies?

http://codereview.chromium.org/19755/diff/405/1405
File src/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/19755/diff/405/1405#newcode255
Line 255: ASSERT(temp.is_valid());
Why do we know that the base of the copy is synced?
Can't it be a register element?

http://codereview.chromium.org/19755/diff/405/1405#newcode335
Line 335: // Spill the arguments.
Is there a reason the elements need to be spilled in reverse order?  If so, note
it, and also that they will actually be synced in forwards order in the range
above the stack pointer first, if relevant.

http://codereview.chromium.org/19755/diff/405/1405#newcode871
Line 871: for (int i = 0; i < elements_.length(); i++) {
What if frame_index is less than the index of the existing use of the register? 
Then new_element should be the register, and the existing one should be made
into a copy, right?  Don't we have the canonicalization that all the copies have
higher indices than the element they are a copy of?

http://codereview.chromium.org/19755/diff/405/1405#newcode1076
Line 1076: if (original.is_register() || original.is_memory()) {
Shouldn't the early bailout if the Store is overwriting a value with the same
value (a copy with a copy, a register with a register, a copy with an original,
etc.) happen before the
AdjustCopies()?

http://codereview.chromium.org/19755/diff/405/1405#newcode1223
Line 1223: PrepareForCall(frame_arg_count, frame_arg_count);
Good catch.

[Kevin Millikin (Chromium), 2009-02-09 13:43:53]

http://codereview.chromium.org/19755/diff/405/1405
File src/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/19755/diff/405/1405#newcode255
Line 255: ASSERT(temp.is_valid());
On 2009/02/09 12:24:36, William Hesse wrote:
> Why do we know that the base of the copy is synced?
> Can't it be a register element?

That's a bug.

http://codereview.chromium.org/19755/diff/405/1405#newcode335
Line 335: // Spill the arguments.
On 2009/02/09 12:24:36, William Hesse wrote:
> Is there a reason the elements need to be spilled in reverse order?  If so,
note
> it, and also that they will actually be synced in forwards order in the range
> above the stack pointer first, if relevant.

Comment added.

They are spilled that way so that copies are spilled before their backing store.
 For register copies it is better to spill via a register-to-memory move than to
(allocate a temp register and) spill via a memory-to-memory move.

http://codereview.chromium.org/19755/diff/405/1405#newcode871
Line 871: for (int i = 0; i < elements_.length(); i++) {
On 2009/02/09 12:24:36, William Hesse wrote:
> What if frame_index is less than the index of the existing use of the
register? 
> Then new_element should be the register, and the existing one should be made
> into a copy, right?  Don't we have the canonicalization that all the copies
have
> higher indices than the element they are a copy of?

That's a bug.

http://codereview.chromium.org/19755/diff/405/1405#newcode1076
Line 1076: if (original.is_register() || original.is_memory()) {
On 2009/02/09 12:24:36, William Hesse wrote:
> Shouldn't the early bailout if the Store is overwriting a value with the same
> value (a copy with a copy, a register with a register, a copy with an
original,
> etc.) happen before the
> AdjustCopies()?
> 

We don't actually have that early bailout here.

Overwriting a copy with a copy of the same thing doesn't trigger the adjustment,
so it's not an issue.

We can't overwrite a register with itself (registers are singly referenced, so
the top element would be a copy).

I think the existing code does the right thing when overwriting a copy's backing
store with the copy.  We adjust so that the backing store is no longer backing
the copy, and then write the copy to an element below its (new) backing store.

There's some wasted work to adjust and adjust back again, but I'm not sure it's
worth optimizing.  First, I'm not sure that it occurs much.  Second and mainly,
I think everything will be simplified by choosing a better (more explicitly
linked) data structure for copies and possibly relaxing the requirement that the
"backing store" be lowest in the frame.

[William Hesse, 2009-02-09 15:18:20]

http://codereview.chromium.org/19755/diff/405/1405
File src/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/19755/diff/405/1405#newcode1133
Line 1133: }
What about all the other copies of the backing element?  Their indices need to
be redirected to the new base too.

http://codereview.chromium.org/19755/diff/405/1405#newcode1135
Line 1135: } else if (original.is_register()) {
If this happens, then top was a copy of original, but now the copies based at
original are rebased at something else.  elements_[index] has to get overwritten
if it is a register, because otherwise we have two instances of the same
register in the frame (left that way by AdjustCopies() ).  The whole effect of
the earlier AdjustCopies has to be undone.  I think it is better to catch this
case before AdjustCopies().

[Kevin Millikin (Chromium), 2009-02-09 15:52:55]

New change list uploaded.

http://codereview.chromium.org/19755/diff/405/1405
File src/virtual-frame-ia32.cc (right):

http://codereview.chromium.org/19755/diff/405/1405#newcode1133
Line 1133: }
On 2009/02/09 15:18:20, William Hesse wrote:
> What about all the other copies of the backing element?  Their indices need to
> be redirected to the new base too.

Yes.  Done.

http://codereview.chromium.org/19755/diff/405/1405#newcode1135
Line 1135: } else if (original.is_register()) {
On 2009/02/09 15:18:20, William Hesse wrote:
> If this happens, then top was a copy of original, but now the copies based at
> original are rebased at something else.  elements_[index] has to get
overwritten
> if it is a register, because otherwise we have two instances of the same
> register in the frame (left that way by AdjustCopies() ).  The whole effect of
> the earlier AdjustCopies has to be undone.  I think it is better to catch this
> case before AdjustCopies().

I'm pretty sure this case can't occur.  I've gotten rid of it entirely in favor
of asserting that it doesn't occur.