Author: [email protected]
Date: Tue Feb 10 00:54:44 2009
New Revision: 1245
Modified:
branches/experimental/toiger/src/virtual-frame-ia32.cc
branches/experimental/toiger/src/virtual-frame-ia32.h
Log:
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.
Review URL: http://codereview.chromium.org/19755
Modified: branches/experimental/toiger/src/virtual-frame-ia32.cc
==============================================================================
--- branches/experimental/toiger/src/virtual-frame-ia32.cc (original)
+++ branches/experimental/toiger/src/virtual-frame-ia32.cc Tue Feb 10
00:54:44 2009
@@ -85,6 +85,46 @@
}
+FrameElement VirtualFrame::CopyElementAt(int index) {
+ ASSERT(index >= 0);
+ ASSERT(index < elements_.length());
+
+ FrameElement target = elements_[index];
+ FrameElement result;
+
+ switch (target.type()) {
+ case FrameElement::CONSTANT:
+ // We do not copy constants and instead return a fresh unsynced
+ // constant.
+ result = FrameElement::ConstantElement(target.handle(),
+ FrameElement::NOT_SYNCED);
+ break;
+
+ case FrameElement::COPY:
+ // We do not allow copies of copies, so we follow one link to
+ // the actual backing store of a copy before making a copy.
+ index = target.index();
+ ASSERT(elements_[index].is_memory() ||
elements_[index].is_register());
+ // Fall through.
+
+ case FrameElement::MEMORY: // Fall through.
+ case FrameElement::REGISTER:
+ // All copies are backed by memory or register locations.
+ result.type_ =
+ FrameElement::TypeField::encode(FrameElement::COPY) |
+ FrameElement::SyncField::encode(FrameElement::NOT_SYNCED);
+ result.data_.index_ = index;
+ break;
+
+ case FrameElement::INVALID:
+ // We should not try to copy invalid elements.
+ UNREACHABLE();
+ break;
+ }
+ return result;
+}
+
+
// Modify the state of the virtual frame to match the actual frame by
adding
// extra in-memory elements to the top of the virtual frame. The extra
// elements will be externally materialized on the actual frame (eg, by
@@ -167,57 +207,100 @@
}
-// Spill an element, making its type be MEMORY.
-// Does not decrement usage counts, if element is a register.
-void VirtualFrame::RawSpillElementAt(int index) {
- if (elements_[index].is_valid()) {
- SyncElementAt(index);
- // The element is now in memory.
- elements_[index] = FrameElement::MemoryElement();
- }
-}
-
-
// Make the type of the element at a given index be MEMORY.
void VirtualFrame::SpillElementAt(int index) {
+ if (!elements_[index].is_valid()) return;
+
if (elements_[index].is_register()) {
Unuse(elements_[index].reg());
}
- RawSpillElementAt(index);
+ SyncElementAt(index);
+ // The element is now in memory.
+ elements_[index] = FrameElement::MemoryElement();
}
-// Clear the dirty bit for the element at a given index.
-// The element must be on the physical stack, or the first
-// element below the stack pointer (created by a single push).
+// Clear the dirty bit for the element at a given index if it is a
+// valid element. The stack address corresponding to the element must
+// be allocated on the physical stack, or the first element above the
+// stack pointer so it can be allocated by a single push instruction.
void VirtualFrame::RawSyncElementAt(int index) {
FrameElement element = elements_[index];
- if (element.is_valid() && !element.is_synced()) {
- if (index <= stack_pointer_) {
- // Write elements below the stack pointer to their (already
allocated)
- // actual frame location.
- if (element.is_constant()) {
- __ Set(Operand(ebp, fp_relative(index)),
Immediate(element.handle()));
- } else {
- ASSERT(element.is_register());
+
+ if (!element.is_valid() || element.is_synced()) return;
+
+ if (index <= stack_pointer_) {
+ // Emit code to write elements below the stack pointer to their
+ // (already allocated) stack address.
+ switch (element.type()) {
+ case FrameElement::INVALID: // Fall through.
+ case FrameElement::MEMORY:
+ // There was an early bailout for invalid and synced elements
+ // (memory elements are always synced).
+ UNREACHABLE();
+ break;
+
+ case FrameElement::REGISTER:
__ mov(Operand(ebp, fp_relative(index)), element.reg());
+ break;
+
+ case FrameElement::CONSTANT:
+ __ Set(Operand(ebp, fp_relative(index)),
Immediate(element.handle()));
+ break;
+
+ case FrameElement::COPY: {
+ int backing_index = element.index();
+ FrameElement backing_element = elements_[backing_index];
+ if (backing_element.is_memory()) {
+ Result temp = cgen_->allocator()->Allocate();
+ ASSERT(temp.is_valid());
+ __ mov(temp.reg(), Operand(ebp, fp_relative(backing_index)));
+ __ mov(Operand(ebp, fp_relative(index)), temp.reg());
+ } else {
+ ASSERT(backing_element.is_register());
+ __ mov(Operand(ebp, fp_relative(index)), backing_element.reg());
+ }
+ break;
}
- } else {
- // Push elements above the stack pointer to allocate space and sync
- // them. Space should have already been allocated in the actual
frame
- // for all the elements below this one.
- ASSERT(index == stack_pointer_ + 1);
- stack_pointer_++;
- if (element.is_constant()) {
- __ push(Immediate(element.handle()));
- } else {
- ASSERT(element.is_register());
+ }
+
+ } else {
+ // Push elements above the stack pointer to allocate space and
+ // sync them. Space should have already been allocated in the
+ // actual frame for all the elements below this one.
+ ASSERT(index == stack_pointer_ + 1);
+ stack_pointer_++;
+ switch (element.type()) {
+ case FrameElement::INVALID: // Fall through.
+ case FrameElement::MEMORY:
+ // There was an early bailout for invalid and synced elements
+ // (memory elements are always synced).
+ UNREACHABLE();
+ break;
+
+ case FrameElement::REGISTER:
__ push(element.reg());
+ break;
+
+ case FrameElement::CONSTANT:
+ __ push(Immediate(element.handle()));
+ break;
+
+ case FrameElement::COPY: {
+ int backing_index = element.index();
+ FrameElement backing = elements_[backing_index];
+ ASSERT(backing.is_memory() || backing.is_register());
+ if (backing.is_memory()) {
+ __ push(Operand(ebp, fp_relative(backing_index)));
+ } else {
+ __ push(backing.reg());
+ }
+ break;
}
}
-
- elements_[index].set_sync();
}
+
+ elements_[index].set_sync();
}
@@ -253,12 +336,19 @@
ASSERT(height() >= spilled_args);
ASSERT(dropped_args <= spilled_args);
- // Below the arguments to the function being called, spill all registers
and
- // make sure that locals have the right values by synching them. The
synching
- // is necessary to give the debugger a consistent view of the values of
- // locals in the frame. Spill the arguments to the function being
called.
int arg_base_index = elements_.length() - spilled_args;
- for (int i = 0; i < arg_base_index; i++) {
+ // Spill the arguments. We spill from the top down so that the
+ // backing stores of register copies will be spilled only after all
+ // the copies are spilled---it is better to spill via a
+ // register-to-memory move than a memory-to-memory move.
+ for (int i = elements_.length() - 1; i >= arg_base_index; i--) {
+ SpillElementAt(i);
+ }
+
+ // Below the arguments, spill registers and sync everything else.
+ // Syncing is necessary for the locals and parameters to give the
+ // debugger a consistent view of the frame.
+ for (int i = arg_base_index - 1; i >= 0; i--) {
FrameElement element = elements_[i];
if (element.is_register()) {
SpillElementAt(i);
@@ -266,10 +356,6 @@
SyncElementAt(i);
}
}
- // The arguments are spilled.
- for (int i = arg_base_index; i < elements_.length(); i++) {
- SpillElementAt(i);
- }
// Forget the frame elements that will be popped by the call.
Forget(dropped_args);
@@ -283,53 +369,142 @@
ASSERT(cgen_->frame() == this);
ASSERT(cgen_->HasValidEntryRegisters());
- // Remove constants from the frame and ensure that no registers are
- // multiply referenced within the frame. Allocate elements to their new
- // locations from the top down so that the topmost elements have a chance
- // to be in registers, then fill them into memory from the bottom up.
- // (NB: Currently when spilling registers that are multiply referenced,
it
- // is the lowermost occurrence that gets to stay in the register.)
-
- // The elements of new_elements are initially invalid.
+ // Remove constants from the frame and ensure that there are no
+ // copies. Allocate elements to their new locations from the top
+ // down so that the topmost elements have a chance to be in
+ // registers, then fill them into memory from the bottom up.
+ //
+ // Compute the new frame elements first. The elements of
+ // new_elements are initially invalid.
FrameElement* new_elements = new FrameElement[elements_.length()];
+ // Array of flags, true if we have found a the topmost copy of a
+ // register. Every element after the first is initialized to 0 (ie,
+ // false).
+ bool topmost_found[RegisterFile::kNumRegisters] = { false };
+ // "Singleton" memory element. They have no internal state.
FrameElement memory_element = FrameElement::MemoryElement();
+
for (int i = elements_.length() - 1; i >= 0; i--) {
FrameElement element = elements_[i];
- if (element.is_constant() ||
- (element.is_register() &&
- frame_registers_.count(element.reg()) > 1)) {
- // A simple strategy is to locate these elements in memory if they
are
- // synced (avoiding a spill right now) and otherwise to prefer a
- // register for them.
- if (element.is_synced()) {
- new_elements[i] = memory_element;
- } else {
- Result fresh = cgen_->allocator()->AllocateWithoutSpilling();
- if (fresh.is_valid()) {
- // We immediately record the frame's use of the register so that
- // it will not be allocated again.
- Use(fresh.reg());
- new_elements[i] =
- FrameElement::RegisterElement(fresh.reg(),
- FrameElement::NOT_SYNCED);
+
+ switch (element.type()) {
+ case FrameElement::INVALID: // Fall through.
+ case FrameElement::MEMORY:
+ new_elements[i] = element;
+ break;
+
+ case FrameElement::REGISTER:
+ // If this is not the first (and only) register reference we
+ // try to find a good home for it, otherwise it can stay in
+ // the register.
+ if (topmost_found[element.reg().code()]) {
+ // A simple strategy is to spill to memory if it is already
+ // synced (avoiding a spill now), and otherwise to prefer a
+ // register if one is available.
+ if (element.is_synced()) {
+ // We do not unuse this register reference because we want
+ // the register allocator to count the other one (higher
+ // up in the new frame).
+ new_elements[i] = memory_element;
+ } else {
+ Result fresh = cgen_->allocator()->AllocateWithoutSpilling();
+ if (fresh.is_valid()) {
+ // We immediately record the frame's use of the register
+ // so that the register allocator will not try to use it
+ // again.
+ Use(fresh.reg());
+ new_elements[i] =
+ FrameElement::RegisterElement(fresh.reg(),
+ FrameElement::NOT_SYNCED);
+ } else {
+ new_elements[i] = memory_element;
+ }
+ }
} else {
+ // The only occurrence can stay in the register.
+ new_elements[i] = element;
+ }
+ break;
+
+ case FrameElement::CONSTANT:
+ // Prefer spilling synced constants and registers for the rest.
+ if (element.is_synced()) {
new_elements[i] = memory_element;
+ } else {
+ Result fresh = cgen_->allocator()->AllocateWithoutSpilling();
+ if (fresh.is_valid()) {
+ // We immediately record the frame's use of the register
+ // so that the register allocator will not try to use it
+ // again.
+ Use(fresh.reg());
+ new_elements[i] =
+ FrameElement::RegisterElement(fresh.reg(),
+ FrameElement::NOT_SYNCED);
+ } else {
+ new_elements[i] = memory_element;
+ }
}
- }
+ break;
+
+ case FrameElement::COPY: {
+ FrameElement backing = elements_[element.index()];
+ if (backing.is_memory()) {
+ new_elements[i] = memory_element;
+ } else {
+ ASSERT(backing.is_register());
+ if (topmost_found[backing.reg().code()]) {
+ if (element.is_synced()) {
+ new_elements[i] = memory_element;
+ } else {
+ Result fresh = cgen_->allocator()->AllocateWithoutSpilling();
+ if (fresh.is_valid()) {
+ // We immediately record the frame's use of the
+ // register so that the register allocator will not
+ // try to use it again.
+ Use(fresh.reg());
+ new_elements[i] =
+ FrameElement::RegisterElement(fresh.reg(),
+
FrameElement::NOT_SYNCED);
+ } else {
+ new_elements[i] = memory_element;
+ }
+ }
+ // When performing the moves (from bottom to top) later,
+ // we will need to know what register this one is a copy
+ // of and the original backing element will already be
+ // overwritten. We store that information in this
+ // elements frame slot so that it looks like this is a
+ // move from a register rather than a copy.
+ if (element.is_synced()) {
+ backing.set_sync();
+ } else {
+ backing.clear_sync();
+ }
+ Use(backing.reg());
+ elements_[i] = backing;
- // We have not moved register references, but record that we will so
- // that we do not unnecessarily spill the last reference within the
- // frame.
- if (element.is_register()) {
- Unuse(element.reg());
+ } else {
+ // This is the top occurrence of the register.
+ topmost_found[backing.reg().code()] = true;
+ if (element.is_synced()) {
+ backing.set_sync();
+ } else {
+ backing.clear_sync();
+ }
+ // Record the register reference immediately so that
+ // register allocator does not try to use this register as
+ // a temp register when performing the moves.
+ Use(backing.reg());
+ new_elements[i] = backing;
+ }
+ }
+ break;
}
- } else {
- // The element is in memory or a singly-frame-referenced register.
- new_elements[i] = element;
}
}
- // Perform the moves.
+ // Perform the moves. Reference counts for register targets have
+ // already been incremented.
for (int i = 0; i < elements_.length(); i++) {
FrameElement source = elements_[i];
FrameElement target = new_elements[i];
@@ -338,15 +513,18 @@
if (source.is_constant()) {
__ Set(target.reg(), Immediate(source.handle()));
} else if (source.is_register() && !source.reg().is(target.reg())) {
+ Unuse(source.reg());
__ mov(target.reg(), source.reg());
}
+ // Otherwise the source and target are the same register or the
+ // source is a copy. If the source is a copy that implies that
+ // it is the same register as the target (copies that are moved
+ // to other registers appear as register-to-register moves).
elements_[i] = target;
+ ASSERT(target.is_synced() == source.is_synced());
} else if (target.is_memory()) {
if (!source.is_memory()) {
- // Spilling a source register would decrement its reference count,
- // but we have already done that when computing new target
elements,
- // so we use a raw spill.
- RawSpillElementAt(i);
+ SpillElementAt(i);
}
}
// Invalid elements do not need to be moved.
@@ -425,11 +603,14 @@
void VirtualFrame::MergeMoveRegistersToMemory(VirtualFrame *expected) {
+ // Move registers, constants, and copies to memory.
for (int i = 0; i < elements_.length(); i++) {
FrameElement source = elements_[i];
FrameElement target = expected->elements_[i];
if (target.is_memory() && !source.is_memory()) {
- ASSERT(source.is_register() || source.is_constant());
+ ASSERT(source.is_register() ||
+ source.is_constant() ||
+ source.is_copy());
SpillElementAt(i);
}
}
@@ -437,6 +618,7 @@
void VirtualFrame::MergeMoveRegistersToRegisters(VirtualFrame *expected) {
+ // Perform register-to-register moves.
int start = 0;
int end = elements_.length() - 1;
bool any_moves_blocked; // Did we fail to make some moves this
iteration?
@@ -498,46 +680,45 @@
void VirtualFrame::MergeMoveMemoryToRegisters(VirtualFrame *expected) {
- // Finally, constant-to-register and memory-to-register. We do these
from
- // the top down so we can use pop for memory-to-register moves above the
- // expected stack pointer.
- for (int i = elements_.length() - 1; i >= 0; i--) {
+ // Move memory, constants, and copies to registers. This is the
+ // final step and is done from the bottom up so that the backing
+ // elements of copies are in their correct locations when we
+ // encounter the copies.
+ for (int i = 0; i < elements_.length(); i++) {
FrameElement source = elements_[i];
FrameElement target = expected->elements_[i];
if (target.is_register() && !source.is_register()) {
- ASSERT(source.is_constant() || source.is_memory());
- if (source.is_memory()) {
- ASSERT(i <= stack_pointer_);
- if (i <= expected->stack_pointer_) {
- // Elements below both stack pointers can just be moved.
+ switch (source.type()) {
+ case FrameElement::INVALID: // Fall through.
+ case FrameElement::REGISTER:
+ UNREACHABLE();
+ break;
+
+ case FrameElement::MEMORY:
+ ASSERT(i <= stack_pointer_);
__ mov(target.reg(), Operand(ebp, fp_relative(i)));
- } else {
- // Elements below the current stack pointer but above the
expected
- // one can be popped, but first we may have to adjust the stack
- // pointer downward.
- if (stack_pointer_ > i) {
- // Sync elements between i and stack pointer, and bring
- // stack pointer down to i.
-#ifdef DEBUG
- // In debug builds check to ensure this is safe.
- for (int j = stack_pointer_; j > i; j--) {
- ASSERT(!elements_[j].is_memory());
- }
-#endif
- int difference = stack_pointer_ - i;
- __ add(Operand(esp), Immediate(difference * kPointerSize));
- stack_pointer_ = i;
+ break;
+
+ case FrameElement::CONSTANT:
+ __ Set(target.reg(), Immediate(source.handle()));
+ break;
+
+ case FrameElement::COPY: {
+ FrameElement backing = elements_[source.index()];
+ ASSERT(backing.is_memory() || backing.is_register());
+ if (backing.is_memory()) {
+ ASSERT(source.index() <= stack_pointer_);
+ __ mov(target.reg(), Operand(ebp,
fp_relative(source.index())));
+ } else {
+ __ mov(target.reg(), backing.reg());
}
- stack_pointer_--;
- __ pop(target.reg());
- }
- } else {
- // Source is constant.
- __ Set(target.reg(), Immediate(source.handle()));
- if (target.is_synced()) {
- SyncElementAt(i);
}
}
+ // Ensure the proper sync state. If the source was memory no
+ // code needs to be emitted.
+ if (target.is_synced() && !source.is_memory()) {
+ SyncElementAt(i);
+ }
Use(target.reg());
elements_[i] = target;
}
@@ -661,32 +842,66 @@
ASSERT(frame_index >= 0);
ASSERT(frame_index < elements_.length());
ASSERT(value->is_valid());
- FrameElement target = elements_[frame_index];
+ FrameElement original = elements_[frame_index];
+
+ // Early exit if the element is the same as the one being set.
+ bool same_register = original.is_register()
+ && value->is_register()
+ && original.reg().is(value->reg());
+ bool same_constant = original.is_constant()
+ && value->is_constant()
+ && original.handle().is_identical_to(value->handle());
+ if (same_register || same_constant) {
+ value->Unuse();
+ return;
+ }
+
+ // If the original may be a copy, adjust to preserve the copy-on-write
+ // semantics of copied elements.
+ if (original.is_register() || original.is_memory()) {
+ FrameElement ignored = AdjustCopies(frame_index);
+ }
- if (target.is_register()) {
- Unuse(target.reg());
+ // If the original is a register reference, deallocate it.
+ if (original.is_register()) {
+ Unuse(original.reg());
}
+ FrameElement new_element;
if (value->is_register()) {
- Use(value->reg());
- // Write the new value to the frame, if it is changed.
- // Otherwise, if target equals value, keep its current sync state.
- if (!target.is_register() ||
- !value->reg().is(target.reg())) {
+ // There are two cases depending no whether the register already
+ // occurs in the frame or not.
+ if (register_count(value->reg()) == 0) {
+ Use(value->reg());
elements_[frame_index] =
FrameElement::RegisterElement(value->reg(),
FrameElement::NOT_SYNCED);
+ } else {
+ for (int i = 0; i < elements_.length(); i++) {
+ FrameElement element = elements_[i];
+ if (element.is_register() && element.reg().is(value->reg())) {
+ // The register backing store is lower in the frame than its
+ // copy.
+ if (i < frame_index) {
+ elements_[frame_index] = CopyElementAt(i);
+ } else {
+ // There was an early bailout for the case of setting a
+ // register element to itself.
+ ASSERT(i != frame_index);
+ element.clear_sync();
+ elements_[frame_index] = element;
+ elements_[i] = CopyElementAt(frame_index);
+ }
+ // Exit the loop once the appropriate copy is inserted.
+ break;
+ }
+ }
}
} else {
ASSERT(value->is_constant());
- // Write the new value to the frame element, if it is a change.
- // Otherwise, do nothing, and keep the current sync state.
- if (!target.is_constant() ||
- !value->handle().is_identical_to(target.handle())) {
- elements_[frame_index] =
- FrameElement::ConstantElement(value->handle(),
- FrameElement::NOT_SYNCED);
- }
+ elements_[frame_index] =
+ FrameElement::ConstantElement(value->handle(),
+ FrameElement::NOT_SYNCED);
}
value->Unuse();
}
@@ -733,81 +948,257 @@
void VirtualFrame::LoadFrameSlotAt(int index) {
- ASSERT(index >= 0);
- ASSERT(index < elements_.length());
+ FrameElement new_element = CopyElementAt(index);
+ elements_.Add(new_element);
+}
- FrameElement element = elements_[index];
- if (element.is_memory()) {
- ASSERT(index <= stack_pointer_);
- // Eagerly load memory elements into a register. The element at
- // the index and the new top of the frame are backed by the same
- // register location.
- Result temp = cgen_->allocator()->Allocate();
- ASSERT(temp.is_valid());
- FrameElement new_element
- = FrameElement::RegisterElement(temp.reg(),
- FrameElement::SYNCED);
- Use(temp.reg());
- elements_[index] = new_element;
- __ mov(temp.reg(), Operand(ebp, fp_relative(index)));
-
- Use(temp.reg());
- new_element.clear_sync();
- elements_.Add(new_element);
- } else {
- // For constants and registers, add an (unsynced) copy of the element
to
- // the top of the frame.
- ASSERT(element.is_register() || element.is_constant());
- if (element.is_register()) {
- Use(element.reg());
+// Before changing an element which is copied, adjust so that the
+// first copy becomes the new backing store and all the other copies
+// are updated. If the original was in memory, the new backing store
+// is allocated to a register. Return a copy of the new backing store
+// or an invalid element if the original was not a copy.
+FrameElement VirtualFrame::AdjustCopies(int index) {
+ FrameElement original = elements_[index];
+ ASSERT(original.is_memory() || original.is_register());
+
+ // Go looking for a first copy above index.
+ int i = index + 1;
+ while (i < elements_.length()) {
+ FrameElement elt = elements_[i];
+ if (elt.is_copy() && elt.index() == index) break;
+ i++;
+ }
+
+ if (i < elements_.length()) {
+ // There was a first copy. Make it the new backing element.
+ Register backing_reg;
+ if (original.is_memory()) {
+ Result fresh = cgen_->allocator()->Allocate();
+ ASSERT(fresh.is_valid());
+ backing_reg = fresh.reg();
+ __ mov(backing_reg, Operand(ebp, fp_relative(index)));
+ } else {
+ // The original was in a register.
+ backing_reg = original.reg();
+ }
+ FrameElement new_backing_element =
+ FrameElement::RegisterElement(backing_reg,
FrameElement::NOT_SYNCED);
+ if (elements_[i].is_synced()) {
+ new_backing_element.set_sync();
+ }
+ Use(backing_reg);
+ elements_[i] = new_backing_element;
+
+ // Update the other copies.
+ FrameElement copy = CopyElementAt(i);
+ for (int j = i; j < elements_.length(); j++) {
+ FrameElement elt = elements_[j];
+ if (elt.is_copy() && elt.index() == index) {
+ if (elt.is_synced()) {
+ copy.set_sync();
+ } else {
+ copy.clear_sync();
+ }
+ elements_[j] = copy;
+ }
}
- element.clear_sync();
- elements_.Add(element);
+
+ copy.clear_sync();
+ return copy;
}
+
+ return FrameElement::InvalidElement();
}
void VirtualFrame::TakeFrameSlotAt(int index) {
- LoadFrameSlotAt(index);
+ ASSERT(index >= 0);
+ ASSERT(index <= elements_.length());
+ FrameElement original = elements_[index];
- if (elements_[index].is_register()) {
- Unuse(elements_[index].reg());
+ switch (original.type()) {
+ case FrameElement::INVALID:
+ UNREACHABLE();
+ break;
+
+ case FrameElement::MEMORY: {
+ // Allocate the element to a register. If it is not copied,
+ // push that register on top of the frame. If it is copied,
+ // make the first copy the backing store and push a fresh copy
+ // on top of the frame.
+ FrameElement copy = AdjustCopies(index);
+ if (copy.is_valid()) {
+ // The original element was a copy. Push the copy of the new
+ // backing store.
+ elements_.Add(copy);
+ } else {
+ // The element was not a copy. Move it to a register and push
+ // that.
+ Result fresh = cgen_->allocator()->Allocate();
+ ASSERT(fresh.is_valid());
+ FrameElement new_element =
+ FrameElement::RegisterElement(fresh.reg(),
+ FrameElement::NOT_SYNCED);
+ Use(fresh.reg());
+ elements_.Add(new_element);
+ __ mov(fresh.reg(), Operand(ebp, fp_relative(index)));
+ }
+ break;
+ }
+
+ case FrameElement::REGISTER: {
+ // If the element is not copied, push it on top of the frame.
+ // If it is copied, make the first copy be the new backing store
+ // and push a fresh copy on top of the frame.
+ FrameElement copy = AdjustCopies(index);
+ if (copy.is_valid()) {
+ // The original element was a copy. Push the copy of the new
+ // backing store.
+ elements_.Add(copy);
+ // This is the only case where we have to unuse the original
+ // register. The original is still counted and so is the new
+ // backing store of the copies.
+ Unuse(original.reg());
+ } else {
+ // The element was not a copy. Push it.
+ original.clear_sync();
+ elements_.Add(original);
+ }
+ break;
+ }
+
+ case FrameElement::CONSTANT:
+ elements_.Add(original);
+ break;
+
+ case FrameElement::COPY:
+ elements_.Add(original);
+ break;
}
elements_[index] = FrameElement::InvalidElement();
}
void VirtualFrame::StoreToFrameSlotAt(int index) {
- // Store the value on top of the frame to the virtual frame slot at a
- // given index. The value on top of the frame is left in place.
+ // Store the value on top of the frame to the virtual frame slot at
+ // a given index. The value on top of the frame is left in place.
+ // This is a duplicating operation, so it can create copies.
ASSERT(index >= 0);
ASSERT(index < elements_.length());
- FrameElement top = elements_[elements_.length() - 1];
- if (elements_[index].is_register()) {
- Unuse(elements_[index].reg());
+ FrameElement original = elements_[index];
+ // If the stored-to slot may be copied, adjust to preserve the
+ // copy-on-write semantics of copied elements.
+ if (original.is_register() || original.is_memory()) {
+ FrameElement ignored = AdjustCopies(index);
+ }
+
+ // If the stored-to slot is a register reference, deallocate it.
+ if (original.is_register()) {
+ Unuse(original.reg());
+ }
+
+ int top_index = elements_.length() - 1;
+ FrameElement top = elements_[top_index];
+ ASSERT(top.is_valid());
+
+ if (top.is_copy()) {
+ // There are two cases based on the relative positions of the
+ // stored-to slot and the backing slot of the top element.
+ int backing_index = top.index();
+ ASSERT(backing_index != index);
+ if (backing_index < index) {
+ // 1. The top element is a copy of a slot below the stored-to
+ // slot. The stored-to slot becomes an unsynced copy of that
+ // same backing slot.
+ elements_[index] = CopyElementAt(backing_index);
+ } else {
+ // 2. The top element is a copy of a slot above the stored-to
+ // slot. The stored-to slot becomes the new (unsynced) backing
+ // slot and both the top element and the element at the former
+ // backing slot become copies of it. The sync state of the top
+ // and former backing elements is preserved.
+ FrameElement backing_element = elements_[backing_index];
+ ASSERT(backing_element.is_memory() || backing_element.is_register());
+ if (backing_element.is_memory()) {
+ // Because sets of copies are canonicalized to be backed by
+ // their lowest frame element, and because memory frame
+ // elements are backed by the corresponding stack address, we
+ // have to move the actual value down in the stack.
+ //
+ // TODO(209): considering allocating the stored-to slot to the
+ // temp register. Alternatively, allow copies to appear in
+ // any order in the frame and lazily move the value down to
+ // the slot.
+ Result temp = cgen_->allocator()->Allocate();
+ ASSERT(temp.is_valid());
+ __ mov(temp.reg(), Operand(ebp, fp_relative(backing_index)));
+ __ mov(Operand(ebp, fp_relative(index)), temp.reg());
+ } else if (backing_element.is_synced()) {
+ // If the element is a register, we will not actually move
+ // anything on the stack but only update the virtual frame
+ // element.
+ backing_element.clear_sync();
+ }
+ elements_[index] = backing_element;
+
+ // The old backing element becomes a copy of the new backing
+ // element.
+ FrameElement new_element = CopyElementAt(index);
+ elements_[backing_index] = new_element;
+ if (backing_element.is_synced()) {
+ elements_[backing_index].set_sync();
+ }
+
+ // All the copies of the old backing element (including the top
+ // element) become copies of the new backing element.
+ for (int i = backing_index + 1; i < elements_.length(); i++) {
+ FrameElement current = elements_[i];
+ if (current.is_copy() && current.index() == backing_index) {
+ elements_[i] = new_element;
+ if (current.is_synced()) {
+ elements_[i].set_sync();
+ }
+ }
+ }
+ }
+
+ return;
}
- // The virtual frame slot will be of the same type and have the same
value
- // as the frame top.
- elements_[index] = top;
+ // Move the top element to the stored-to slot and replace it (the
+ // top element) with a copy.
+ elements_[index] = top;
if (top.is_memory()) {
- // TODO(209): consider allocating the slot to a register.
- //
- // Emit code to store memory values into the required frame slot.
+ // TODO(209): consider allocating the stored-to slot to the temp
+ // register. Alternatively, allow copies to appear in any order
+ // in the frame and lazily move the value down to the slot.
+ FrameElement new_top = CopyElementAt(index);
+ new_top.set_sync();
+ elements_[top_index] = new_top;
+
+ // The sync state of the former top element is correct (synced).
+ // Emit code to move the value down in the frame.
Result temp = cgen_->allocator()->Allocate();
ASSERT(temp.is_valid());
__ mov(temp.reg(), Top());
__ mov(Operand(ebp, fp_relative(index)), temp.reg());
+ } else if (top.is_register()) {
+ // The stored-to slot has the (unsynced) register reference and
+ // the top element becomes a copy. The sync state of the top is
+ // preserved.
+ FrameElement new_top = CopyElementAt(index);
+ if (top.is_synced()) {
+ new_top.set_sync();
+ elements_[index].clear_sync();
+ }
+ elements_[top_index] = new_top;
} else {
- // We have not actually written the value to memory.
+ // The stored-to slot holds the same value as the top but
+ // unsynced. (We do not have copies of constants yet.)
+ ASSERT(top.is_constant());
elements_[index].clear_sync();
-
- if (top.is_register()) {
- // Establish another frame-internal reference to the register.
- Use(top.reg());
- }
}
}
@@ -825,9 +1216,8 @@
}
-Result VirtualFrame::CallStub(CodeStub* stub, int frame_arg_count) {
+Result VirtualFrame::RawCallStub(CodeStub* stub, int frame_arg_count) {
ASSERT(cgen_->HasValidEntryRegisters());
- PrepareForCall(frame_arg_count, frame_arg_count);
__ CallStub(stub);
Result result = cgen_->allocator()->Allocate(eax);
ASSERT(result.is_valid());
@@ -835,11 +1225,18 @@
}
+Result VirtualFrame::CallStub(CodeStub* stub, int frame_arg_count) {
+ PrepareForCall(frame_arg_count, frame_arg_count);
+ return RawCallStub(stub, frame_arg_count);
+}
+
+
Result VirtualFrame::CallStub(CodeStub* stub,
Result* arg,
int frame_arg_count) {
+ PrepareForCall(frame_arg_count, frame_arg_count);
arg->Unuse();
- return CallStub(stub, frame_arg_count);
+ return RawCallStub(stub, frame_arg_count);
}
@@ -847,16 +1244,17 @@
Result* arg0,
Result* arg1,
int frame_arg_count) {
+ PrepareForCall(frame_arg_count, frame_arg_count);
arg0->Unuse();
arg1->Unuse();
- return CallStub(stub, frame_arg_count);
+ return RawCallStub(stub, frame_arg_count);
}
Result VirtualFrame::CallRuntime(Runtime::Function* f,
int frame_arg_count) {
- ASSERT(cgen_->HasValidEntryRegisters());
PrepareForCall(frame_arg_count, frame_arg_count);
+ ASSERT(cgen_->HasValidEntryRegisters());
__ CallRuntime(f, frame_arg_count);
Result result = cgen_->allocator()->Allocate(eax);
ASSERT(result.is_valid());
@@ -866,8 +1264,8 @@
Result VirtualFrame::CallRuntime(Runtime::FunctionId id,
int frame_arg_count) {
- ASSERT(cgen_->HasValidEntryRegisters());
PrepareForCall(frame_arg_count, frame_arg_count);
+ ASSERT(cgen_->HasValidEntryRegisters());
__ CallRuntime(id, frame_arg_count);
Result result = cgen_->allocator()->Allocate(eax);
ASSERT(result.is_valid());
@@ -878,8 +1276,8 @@
Result VirtualFrame::InvokeBuiltin(Builtins::JavaScript id,
InvokeFlag flag,
int frame_arg_count) {
- ASSERT(cgen_->HasValidEntryRegisters());
PrepareForCall(frame_arg_count, frame_arg_count);
+ ASSERT(cgen_->HasValidEntryRegisters());
__ InvokeBuiltin(id, flag);
Result result = cgen_->allocator()->Allocate(eax);
ASSERT(result.is_valid());
@@ -888,11 +1286,8 @@
Result VirtualFrame::RawCallCodeObject(Handle<Code> code,
- RelocInfo::Mode rmode,
- int spilled_args,
- int dropped_args) {
+ RelocInfo::Mode rmode) {
ASSERT(cgen_->HasValidEntryRegisters());
- PrepareForCall(spilled_args, dropped_args);
__ call(code, rmode);
Result result = cgen_->allocator()->Allocate(eax);
ASSERT(result.is_valid());
@@ -922,7 +1317,8 @@
UNREACHABLE();
break;
}
- return RawCallCodeObject(code, rmode, spilled_args, dropped_args);
+ PrepareForCall(spilled_args, dropped_args);
+ return RawCallCodeObject(code, rmode);
}
@@ -952,8 +1348,9 @@
UNREACHABLE();
break;
}
+ PrepareForCall(spilled_args, dropped_args);
arg->Unuse();
- return RawCallCodeObject(code, rmode, spilled_args, dropped_args);
+ return RawCallCodeObject(code, rmode);
}
@@ -982,9 +1379,10 @@
UNREACHABLE();
break;
}
+ PrepareForCall(spilled_args, dropped_args);
arg0->Unuse();
arg1->Unuse();
- return RawCallCodeObject(code, rmode, spilled_args, dropped_args);
+ return RawCallCodeObject(code, rmode);
}
@@ -1010,30 +1408,53 @@
Result VirtualFrame::Pop() {
- FrameElement popped = elements_.RemoveLast();
- bool pop_needed = (stack_pointer_ == elements_.length());
+ FrameElement element = elements_.RemoveLast();
+ int index = elements_.length();
+ ASSERT(element.is_valid());
- if (popped.is_constant()) {
- if (pop_needed) {
- stack_pointer_--;
- __ add(Operand(esp), Immediate(kPointerSize));
- }
- return Result(popped.handle(), cgen_);
- } else if (popped.is_register()) {
- Unuse(popped.reg());
- if (pop_needed) {
- stack_pointer_--;
- __ add(Operand(esp), Immediate(kPointerSize));
+ bool pop_needed = (stack_pointer_ == index);
+ if (pop_needed) {
+ stack_pointer_--;
+ if (element.is_memory()) {
+ Result temp = cgen_->allocator()->Allocate();
+ ASSERT(temp.is_valid());
+ __ pop(temp.reg());
+ return temp;
}
- return Result(popped.reg(), cgen_);
- } else {
- ASSERT(popped.is_memory());
+
+ __ add(Operand(esp), Immediate(kPointerSize));
+ }
+ ASSERT(!element.is_memory());
+
+ // The top element is a register, constant, or a copy. Unuse
+ // registers and follow copies to their backing store.
+ if (element.is_register()) {
+ Unuse(element.reg());
+ } else if (element.is_copy()) {
+ ASSERT(element.index() < index);
+ index = element.index();
+ element = elements_[index];
+ }
+ ASSERT(!element.is_copy());
+
+ // The element is memory, a register, or a constant.
+ if (element.is_memory()) {
+ // Memory elements could only be the backing store of a copy.
+ // Allocate the original to a register.
+ ASSERT(index <= stack_pointer_);
Result temp = cgen_->allocator()->Allocate();
ASSERT(temp.is_valid());
- ASSERT(pop_needed);
- stack_pointer_--;
- __ pop(temp.reg());
- return temp;
+ Use(temp.reg());
+ FrameElement new_element =
+ FrameElement::RegisterElement(temp.reg(), FrameElement::SYNCED);
+ elements_[index] = new_element;
+ __ mov(temp.reg(), Operand(ebp, fp_relative(index)));
+ return Result(temp.reg(), cgen_);
+ } else if (element.is_register()) {
+ return Result(element.reg(), cgen_);
+ } else {
+ ASSERT(element.is_constant());
+ return Result(element.handle(), cgen_);
}
}
@@ -1079,9 +1500,21 @@
void VirtualFrame::Push(Register reg) {
- Use(reg);
- elements_.Add(FrameElement::RegisterElement(reg,
- FrameElement::NOT_SYNCED));
+ FrameElement new_element;
+ if (register_count(reg) == 0) {
+ Use(reg);
+ new_element =
+ FrameElement::RegisterElement(reg, FrameElement::NOT_SYNCED);
+ } else {
+ for (int i = 0; i < elements_.length(); i++) {
+ FrameElement element = elements_[i];
+ if (element.is_register() && element.reg().is(reg)) {
+ new_element = CopyElementAt(i);
+ break;
+ }
+ }
+ }
+ elements_.Add(new_element);
}
Modified: branches/experimental/toiger/src/virtual-frame-ia32.h
==============================================================================
--- branches/experimental/toiger/src/virtual-frame-ia32.h (original)
+++ branches/experimental/toiger/src/virtual-frame-ia32.h Tue Feb 10
00:54:44 2009
@@ -107,23 +107,30 @@
bool is_memory() const { return type() == MEMORY; }
bool is_register() const { return type() == REGISTER; }
bool is_constant() const { return type() == CONSTANT; }
+ bool is_copy() const { return type() == COPY; }
Register reg() const {
- ASSERT(type() == REGISTER);
+ ASSERT(is_register());
return data_.reg_;
}
Handle<Object> handle() const {
- ASSERT(type() == CONSTANT);
+ ASSERT(is_constant());
return Handle<Object>(data_.handle_);
}
+ int index() const {
+ ASSERT(is_copy());
+ return data_.index_;
+ }
+
private:
enum Type {
INVALID,
MEMORY,
REGISTER,
- CONSTANT
+ CONSTANT,
+ COPY
};
// BitField is <type, shift, size>.
@@ -140,7 +147,10 @@
union {
Register reg_;
Object** handle_;
+ int index_;
} data_;
+
+ friend class VirtualFrame;
};
@@ -177,6 +187,9 @@
// Construct a virtual frame as a clone of an existing one.
explicit VirtualFrame(VirtualFrame* original);
+ // Create a duplicate of an existing valid frame element.
+ FrameElement CopyElementAt(int index);
+
// The height of the virtual expression stack.
int height() const {
return elements_.length() - expression_base_index();
@@ -498,10 +511,6 @@
// constant.
void SpillElementAt(int index);
- // Spill the element at an index without modifying its reference count
(if
- // it was in a register).
- void RawSpillElementAt(int index);
-
// Sync the element at a particular index. If it is a register or
// constant that disagrees with the value on the stack, write it to
memory.
// Keep the element type as register or constant, and clear the dirty
bit.
@@ -552,12 +561,21 @@
// should be equal.
void MergeMoveMemoryToRegisters(VirtualFrame* expected);
- // Calls a code object which takes spilled_args frame arguments
- // and which drops dropped_args of them.
- Result RawCallCodeObject(Handle<Code> code,
- RelocInfo::Mode rmode,
- int spilled_args,
- int dropped_args);
+ // Helper function to implement the copy-on-write semantics of an
+ // element's copies just before writing to the element. The copies
+ // are updated, but the element is not changed. A copy of the new
+ // backing store of all the copies is returned if there were any
+ // copies and in invalid frame element is returned if there were no
+ // copies.
+ FrameElement AdjustCopies(int index);
+
+ // Call a code stub that has already been prepared for calling (via
+ // PrepareForCall).
+ Result RawCallStub(CodeStub* stub, int frame_arg_count);
+
+ // Calls a code object which has already been prepared for calling
+ // (via PrepareForCall).
+ Result RawCallCodeObject(Handle<Code> code, RelocInfo::Mode rmode);
};
} } // namespace v8::internal
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
