Author: [EMAIL PROTECTED]
Date: Fri Dec 5 05:58:46 2008
New Revision: 925
Modified:
branches/experimental/toiger/src/codegen-ia32.cc
branches/experimental/toiger/src/codegen.cc
branches/experimental/toiger/src/flag-definitions.h
branches/experimental/toiger/src/jump-target-ia32.cc
branches/experimental/toiger/src/register-allocator-ia32.cc
branches/experimental/toiger/src/register-allocator-ia32.h
branches/experimental/toiger/src/virtual-frame-ia32.cc
branches/experimental/toiger/src/virtual-frame-ia32.h
Log:
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.
Review URL: http://codereview.chromium.org/13127
Modified: branches/experimental/toiger/src/codegen-ia32.cc
==============================================================================
--- branches/experimental/toiger/src/codegen-ia32.cc (original)
+++ branches/experimental/toiger/src/codegen-ia32.cc Fri Dec 5 05:58:46
2008
@@ -247,7 +247,6 @@
frame_->CallRuntime(Runtime::kTraceEnter, 0);
// Ignore the return value.
}
- frame_->SpillAll();
CheckStack();
// Compile the body of the function in a vanilla state. Don't
Modified: branches/experimental/toiger/src/codegen.cc
==============================================================================
--- branches/experimental/toiger/src/codegen.cc (original)
+++ branches/experimental/toiger/src/codegen.cc Fri Dec 5 05:58:46 2008
@@ -78,7 +78,9 @@
Handle<Script> script,
bool is_eval) {
#ifdef ENABLE_DISASSEMBLER
- bool print_code = FLAG_print_code && !Bootstrapper::IsActive();
+ bool print_code = Bootstrapper::IsActive()
+ ? FLAG_print_builtin_code
+ : FLAG_print_code;
#endif
#ifdef DEBUG
@@ -89,7 +91,6 @@
if (Bootstrapper::IsActive()) {
print_source = FLAG_print_builtin_source;
print_ast = FLAG_print_builtin_ast;
- print_code = FLAG_print_builtin_code;
ftype = "builtin";
} else {
print_source = FLAG_print_source;
Modified: branches/experimental/toiger/src/flag-definitions.h
==============================================================================
--- branches/experimental/toiger/src/flag-definitions.h (original)
+++ branches/experimental/toiger/src/flag-definitions.h Fri Dec 5 05:58:46
2008
@@ -249,7 +249,6 @@
// codegen-ia32.cc / codegen-arm.cc
DEFINE_bool(trace_codegen, false,
"print name of functions for which code is generated")
-DEFINE_bool(print_builtin_code, false, "print generated code for builtins")
DEFINE_bool(print_source, false, "pretty print source code")
DEFINE_bool(print_builtin_source, false,
"pretty print source code for builtins")
@@ -342,6 +341,7 @@
// codegen-ia32.cc / codegen-arm.cc
DEFINE_bool(print_code, false, "print generated code")
+DEFINE_bool(print_builtin_code, false, "print generated code for builtins")
// Cleanup...
#undef FLAG_FULL
Modified: branches/experimental/toiger/src/jump-target-ia32.cc
==============================================================================
--- branches/experimental/toiger/src/jump-target-ia32.cc (original)
+++ branches/experimental/toiger/src/jump-target-ia32.cc Fri Dec 5
05:58:46 2008
@@ -69,11 +69,13 @@
if (expected_frame_ == NULL) {
expected_frame_ = current_frame;
- expected_frame_->EnsureMergable();
// The frame at the actual function return will always have height
zero.
if (code_generator_->IsActualFunctionReturn(this)) {
expected_frame_->Forget(expected_frame_->height());
}
+ if (!expected_frame_->IsMergable()) {
+ expected_frame_->MakeMergable();
+ }
code_generator_->set_frame(NULL);
} else {
// No code needs to be emitted to merge to the expected frame at the
@@ -101,11 +103,13 @@
if (expected_frame_ == NULL) {
expected_frame_ = new VirtualFrame(current_frame);
- expected_frame_->EnsureMergable();
// The frame at the actual function return will always have height
zero.
if (code_generator_->IsActualFunctionReturn(this)) {
expected_frame_->Forget(expected_frame_->height());
}
+ if (!expected_frame_->IsMergable()) {
+ expected_frame_->MakeMergable();
+ }
} else {
// No code needs to be emitted to merge to the expected frame at the
// actual function return.
@@ -132,7 +136,9 @@
ASSERT(expected_frame_ == NULL);
expected_frame_ = new VirtualFrame(current_frame);
- expected_frame_->EnsureMergable();
+ if (!expected_frame_->IsMergable()) {
+ expected_frame_->MakeMergable();
+ }
// Adjust the expected frame's height to account for the return address
// pushed by the call instruction.
expected_frame_->Adjust(1);
@@ -156,10 +162,12 @@
if (expected_frame_ == NULL) {
expected_frame_ = new VirtualFrame(current_frame);
- expected_frame_->EnsureMergable();
// The frame at the actual function return will always have height
zero.
if (code_generator_->IsActualFunctionReturn(this)) {
expected_frame_->Forget(expected_frame_->height());
+ }
+ if (!expected_frame_->IsMergable()) {
+ expected_frame_->MakeMergable();
}
} else if (current_frame == NULL) {
code_generator_->set_frame(new VirtualFrame(expected_frame_));
Modified: branches/experimental/toiger/src/register-allocator-ia32.cc
==============================================================================
--- branches/experimental/toiger/src/register-allocator-ia32.cc (original)
+++ branches/experimental/toiger/src/register-allocator-ia32.cc Fri Dec 5
05:58:46 2008
@@ -41,7 +41,7 @@
}
-Register RegisterAllocator::Allocate() {
+Register RegisterAllocator::AllocateWithoutSpilling() {
// Return the first free register, if any.
for (int i = 0; i < num_registers(); i++) {
if (!registers_.is_used(i)) {
@@ -50,15 +50,21 @@
return result;
}
}
+ return no_reg;
+}
- // Ask the current frame to spill a register.
- ASSERT(code_generator_->frame() != NULL);
- Register result = code_generator_->frame()->SpillAnyRegister();
- if (!result.is(no_reg)) {
- ASSERT(!registers_.is_used(result.code()));
- registers_.Use(result);
- }
+Register RegisterAllocator::Allocate() {
+ Register result = AllocateWithoutSpilling();
+ if (result.is(no_reg)) {
+ // Ask the current frame to spill a register.
+ ASSERT(code_generator_->frame() != NULL);
+ result = code_generator_->frame()->SpillAnyRegister();
+ if (!result.is(no_reg)) {
+ ASSERT(!registers_.is_used(result.code()));
+ registers_.Use(result);
+ }
+ }
return result;
}
Modified: branches/experimental/toiger/src/register-allocator-ia32.h
==============================================================================
--- branches/experimental/toiger/src/register-allocator-ia32.h (original)
+++ branches/experimental/toiger/src/register-allocator-ia32.h Fri Dec 5
05:58:46 2008
@@ -101,6 +101,10 @@
// Allocate a free register if possible or fail by returning no_reg.
Register Allocate();
+ // Allocate a free register without spilling any or fail and return
+ // no_reg.
+ Register AllocateWithoutSpilling();
+
private:
CodeGenerator* code_generator_;
RegisterFile registers_;
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 Fri Dec 5
05:58:46 2008
@@ -172,7 +172,7 @@
if (best_register_code != no_reg.code_) {
// Spill all occurrences of the register. There are min_count
- // occurrences, stop when we've spilled them all to avoid syncing
+ // occurrences, stop when we have spilled them all to avoid syncing
// elements unnecessarily.
int i = 0;
while (min_count > 0) {
@@ -183,17 +183,12 @@
// Spill it.
SpillElementAt(i);
min_count--;
- } else {
- if (i > stack_pointer_) {
- // Make sure to materialize elements on the virtual frame in
- // memory. We rely on this to spill occurrences of the register
- // lying above the current virtual stack pointer.
- SyncElementAt(i);
- }
}
+ i++;
}
}
+ ASSERT(cgen_->allocator()->count(best_register_code) == 0);
Register result = { best_register_code };
return result;
}
@@ -203,6 +198,9 @@
// allocate space in the actual frame for the virtual element immediately
// above the stack pointer.
void VirtualFrame::SpillElementAt(int index) {
+ if (index > stack_pointer_ + 1) {
+ SyncRange(stack_pointer_ + 1, index);
+ }
SyncElementAt(index);
// The element is now in memory.
if (elements_[index].is_register()) {
@@ -212,14 +210,15 @@
}
-// Clear the dirty bits for all elements.
-void VirtualFrame::SyncAll() {
- for (int i = 0; i < elements_.length(); i++) {
+// Clear the dirty bits for the range of elements in [begin, end).
+void VirtualFrame::SyncRange(int begin, int end) {
+ ASSERT(begin >= 0);
+ ASSERT(end <= elements_.length());
+ for (int i = begin; i < end; i++) {
SyncElementAt(i);
}
}
-
// Make the type of all elements be MEMORY.
void VirtualFrame::SpillAll() {
for (int i = 0; i < elements_.length(); i++) {
@@ -253,17 +252,106 @@
}
-void VirtualFrame::EnsureMergable() {
+bool VirtualFrame::IsMergable() {
// We cannot merge to a frame that has constants as elements, because an
- // arbitrary frame might not have constants in those locations.
- //
- // We cannot merge to a frame that has registers as elements because we
- // haven't implemented merging for such frames yet.
- SpillAll();
+ // arbitrary frame may not have the same constants at those locations.
We
+ // cannot merge to a frame that has registers that are mulitply
referenced
+ // in the frame, because an arbitrary frame might not exhibit the same
+ // sharing. Thus, a frame is mergable if all elements are in memory or a
+ // register and no register is multiply referenced.
+ for (int i = 0; i < RegisterFile::kNumRegisters; i++) {
+ if (frame_registers_.count(i) > 1) {
+ return false;
+ }
+ }
+
+ for (int i = 0; i < elements_.length(); i++) {
+ if (!elements_[i].is_memory() && !elements_[i].is_register()) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+
+void VirtualFrame::MakeMergable() {
+ Comment cmnt(masm_, "[ Make frame mergable");
+ // 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.)
+ FrameElement* new_elements = new FrameElement[elements_.length()];
+ FrameElement memory_element;
+ 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().code()) > 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 {
+ // This code path is currently not triggered. UNIMPLEMENTED is
+ // temporarily used to trap when it becomes active so we can test
+ // it.
+ UNIMPLEMENTED();
+ Register reg = cgen_->allocator()->AllocateWithoutSpilling();
+ if (reg.is(no_reg)) {
+ new_elements[i] = memory_element;
+ } else {
+ FrameElement register_element(reg, FrameElement::NOT_SYNCED);
+ new_elements[i] = register_element;
+ }
+ }
+
+ // 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 {
+ // The element is in memory or a singly-frame-referenced register.
+ new_elements[i] = element;
+ }
+ }
+
+ // Perform the moves.
+ for (int i = 0; i < elements_.length(); i++) {
+ FrameElement source = elements_[i];
+ FrameElement target = new_elements[i];
+ ASSERT(target.is_register() || target.is_memory());
+ if (target.is_register()) {
+ if (source.is_constant()) {
+ // The allocator's register reference count was incremented by
+ // register allocation, so we only record the new reference in the
+ // frame. The frame now owns the reference.
+ frame_registers_.Use(target.reg());
+ __ Set(target.reg(), Immediate(source.handle()));
+ } else if (source.is_register() && !source.reg().is(target.reg())) {
+ // The frame now owns the reference.
+ frame_registers_.Use(target.reg());
+ __ mov(target.reg(), source.reg());
+ }
+ elements_[i] = target;
+ } else {
+ // The target is memory.
+ SpillElementAt(i);
+ }
+ }
+
+ delete[] new_elements;
}
void VirtualFrame::MergeTo(VirtualFrame* expected) {
+ Comment cmnt(masm_, "[ Merge frame");
ASSERT(cgen_ == expected->cgen_);
ASSERT(masm_ == expected->masm_);
ASSERT(elements_.length() == expected->elements_.length());
@@ -271,12 +359,67 @@
ASSERT(local_count_ == expected->local_count_);
ASSERT(frame_pointer_ == expected->frame_pointer_);
- // Mergable frames do not have constants and they do not (currently) have
- // registers. They are always fully spilled, so the only thing needed to
- // make this frame match the expected one is to spill everything.
- //
- // TODO(): Implement a non-stupid way of merging frames.
- SpillAll();
+ // Mergable frames have all elements in locations, either memory or
+ // register. We thus have a series of to-memory and to-register moves.
+ // First perform all to-memory moves, register-to-memory moves because
+ // they can free registers and constant-to-memory moves because they do
+ // not use registers.
+ 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());
+ SpillElementAt(i);
+ }
+ }
+
+ // Then register-to-register moves, not yet implemented.
+ for (int i = 0; i < elements_.length(); i++) {
+ FrameElement source = elements_[i];
+ FrameElement target = expected->elements_[i];
+ ASSERT(!source.is_register() || !target.is_register());
+ }
+
+ // 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--) {
+ 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.
+ __ mov(target.reg(), Operand(ebp, fp_relative(i)));
+ } else {
+ // Elements below the current stack pointer but above the
expected
+ // one can be popped, bet first we may have to adjust the stack
+ // pointer downward.
+ if (stack_pointer_ > i + 1) {
+#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
+ stack_pointer_ = i + 1;
+ __ add(Operand(esp),
+ Immediate((stack_pointer_ - i) * kPointerSize));
+ }
+ stack_pointer_--;
+ __ pop(target.reg());
+ }
+ Use(target.reg());
+ } else if (source.is_constant()) {
+ // Not yet implemented. When done, code in common with the
+ // memory-to-register just above case can be factored out.
+ UNIMPLEMENTED();
+ }
+ elements_[i] = target;
+ }
+ }
ASSERT(stack_pointer_ == expected->stack_pointer_);
}
@@ -330,9 +473,11 @@
if (count > 0) {
Comment cmnt(masm_, "[ Allocate space for locals");
- // The locals are constants (the undefined value), but we sync them
with
- // the actual frame to allocate space for spilling them.
- SyncAll();
+ // The locals are initialized to a constant (the undefined value), but
+ // we sync them with the actual frame to allocate space for spilling
+ // them later. First sync everything above the stack pointer so we can
+ // use pushes to allocate and initialize the locals.
+ SyncRange(stack_pointer_ + 1, elements_.length());
Handle<Object> undefined = Factory::undefined_value();
FrameElement initial_value(undefined, FrameElement::SYNCED);
Register tmp = cgen_->allocator()->Allocate();
@@ -368,7 +513,7 @@
__ mov(Operand(ebp, fp_relative(index)), temp);
cgen_->allocator()->Unuse(temp);
} else {
- // We haven't actually written the value to memory.
+ // We have not actually written the value to memory.
elements_[index].clear_sync();
if (top.is_register()) {
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 Fri Dec 5
05:58:46 2008
@@ -151,9 +151,14 @@
// it was not possible to spill one.
Register SpillAnyRegister();
+ // True if an arbitrary frame of the same size could be merged to this
+ // one. Requires all values to be in a unique register or memory
+ // location.
+ bool IsMergable();
+
// Ensure that this frame is in a state where an arbitrary frame of the
// right size could be merged to it. May emit code.
- void EnsureMergable();
+ void MakeMergable();
// Make this virtual frame have a state identical to an expected virtual
// frame. As a side effect, code may be emitted to make this frame match
@@ -350,8 +355,8 @@
// for all the elements below this one (at least).
void SpillElementAt(int index);
- // Sync all elements in the frame.
- void SyncAll();
+ // Sync the range of elements in [begin, end).
+ void SyncRange(int begin, int end);
// Store the value on top of the frame to a frame slot (typically a local
// or parameter).
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
