Author: [email protected]
Date: Wed Feb 4 02:59:12 2009
New Revision: 1221
Modified:
branches/experimental/toiger/src/codegen-ia32.cc
branches/experimental/toiger/src/codegen-ia32.h
branches/experimental/toiger/src/codegen.cc
branches/experimental/toiger/src/jump-target-ia32.cc
branches/experimental/toiger/src/jump-target.h
Log:
Experimental: handle single-entry basic blocks as a special case.
Also, clean up fast switch jump tables.
If basic block entry labels are forward-only and they are bound with
exactly one incoming CFG edge (either a live frame and no jumps or
branches, or no live frame and a single jump or branch) then they can
be treated specially.
The body of the block is compiled with the single reaching frame, with
no extra code emitted.
The fast-case switch statements are cleaned up to use raw labels
rather than jump targets, because they do not fit the jump target
abstraction very well.
Review URL: http://codereview.chromium.org/21040
Modified: branches/experimental/toiger/src/codegen-ia32.cc
==============================================================================
--- branches/experimental/toiger/src/codegen-ia32.cc (original)
+++ branches/experimental/toiger/src/codegen-ia32.cc Wed Feb 4 02:59:12
2009
@@ -1443,9 +1443,7 @@
node->set_break_stack_height(break_stack_height_);
node->break_target()->Initialize(this);
VisitStatements(node->statements());
- if (node->break_target()->is_linked()) {
- node->break_target()->Bind();
- }
+ node->break_target()->Bind();
}
@@ -1602,9 +1600,7 @@
}
}
- if (exit.is_linked()) {
- exit.Bind();
- }
+ exit.Bind();
}
@@ -1755,9 +1751,9 @@
SwitchStatement* node,
int min_index,
int range,
- JumpTarget* fail_label,
- Vector<JumpTarget*> case_targets,
- Vector<JumpTarget> case_labels) {
+ Label* default_label,
+ Vector<Label*> case_targets,
+ Vector<Label> case_labels) {
// Notice: Internal references, used by both the jmp instruction and
// the table entries, need to be relocated if the buffer grows. This
// prevents the forward use of Labels, since a displacement cannot
@@ -1766,38 +1762,48 @@
// placeholders, and fill in the addresses after the labels have been
// bound.
- Result switch_value = frame_->Pop(); // supposed Smi
- // If value is not in range [0..length-1] then jump to the default/end
label.
- ASSERT(kSmiTagSize == 1 && kSmiTag == 0);
-
- // Test whether input is a HeapNumber that is really a Smi
+ JumpTarget setup_default(this);
JumpTarget is_smi(this);
+
+ // A non-null default label pointer indicates a default case among
+ // the case labels. Otherwise we use the break target as a
+ // "default".
+ JumpTarget* default_target =
+ (default_label == NULL) ? node->break_target() : &setup_default;
+
+ // Test whether input is a smi.
+ ASSERT(kSmiTagSize == 1 && kSmiTag == 0);
+ Result switch_value = frame_->Pop();
switch_value.ToRegister();
__ test(switch_value.reg(), Immediate(kSmiTagMask));
is_smi.Branch(equal, &switch_value, taken);
- // It's a heap object, not a Smi or a Failure
+
+ // It's a heap object, not a smi or a failure. Check if it is a
+ // heap number.
Result temp = allocator()->Allocate();
ASSERT(temp.is_valid());
__ mov(temp.reg(), FieldOperand(switch_value.reg(),
HeapObject::kMapOffset));
__ movzx_b(temp.reg(), FieldOperand(temp.reg(),
Map::kInstanceTypeOffset));
__ cmp(temp.reg(), HEAP_NUMBER_TYPE);
temp.Unuse();
- fail_label->Branch(not_equal);
- // Result switch_value is a heap number.
+ default_target->Branch(not_equal);
+
+ // The switch value is a heap number. Convert it to a smi.
frame_->Push(&switch_value);
Result smi_value = frame_->CallRuntime(Runtime::kNumberToSmi, 1);
+
is_smi.Bind(&smi_value);
smi_value.ToRegister();
-
+ // Convert the switch value to a 0-based table index.
if (min_index != 0) {
frame_->Spill(smi_value.reg());
__ sub(Operand(smi_value.reg()), Immediate(min_index << kSmiTagSize));
}
+ // Go to the default case if the table index is negative or not a smi.
__ test(smi_value.reg(), Immediate(0x80000000 | kSmiTagMask));
- // Go to slow case if adjusted index is negative or not a Smi.
- fail_label->Branch(not_equal, not_taken);
+ default_target->Branch(not_equal, not_taken);
__ cmp(smi_value.reg(), range << kSmiTagSize);
- fail_label->Branch(greater_equal, not_taken);
+ default_target->Branch(greater_equal, not_taken);
// 0 is placeholder.
// Jump to the address at table_address + 2 * smi_value.reg().
@@ -1805,27 +1811,50 @@
// The Smi encoding of smi_value.reg() is 2 * switch_value.
__ jmp(Operand(smi_value.reg(), smi_value.reg(),
times_1, 0x0, RelocInfo::INTERNAL_REFERENCE));
+ smi_value.Unuse();
+
+ // The expected frame at all the case labels is the (mergable
+ // version of the) current one. Keep a copy to restore at the start
+ // of every label.
+ frame_->MakeMergable();
+ VirtualFrame* start_frame = new VirtualFrame(frame_);
+
// Calculate address to overwrite later with actual address of table.
int32_t jump_table_ref = __ pc_offset() - sizeof(int32_t);
-
__ Align(4);
- JumpTarget table_start(this);
- smi_value.Unuse();
- table_start.Bind();
- __ WriteInternalReference(jump_table_ref, *table_start.entry_label());
+ Label table_start;
+ __ bind(&table_start);
+ __ WriteInternalReference(jump_table_ref, table_start);
for (int i = 0; i < range; i++) {
// These are the table entries. 0x0 is the placeholder for case
address.
__ dd(0x0, RelocInfo::INTERNAL_REFERENCE);
}
- GenerateFastCaseSwitchCases(node, case_labels, &table_start);
+ GenerateFastCaseSwitchCases(node, case_labels, start_frame);
- for (int i = 0, entry_pos = table_start.entry_label()->pos();
+ // If there was a default case, we need to emit the code to match it.
+ if (default_label != NULL) {
+ node->break_target()->Jump();
+ setup_default.Bind();
+ frame_->MergeTo(start_frame);
+ __ jmp(default_label);
+ DeleteFrame();
+ }
+ node->break_target()->Bind();
+
+ for (int i = 0, entry_pos = table_start.pos();
i < range;
i++, entry_pos += sizeof(uint32_t)) {
- __ WriteInternalReference(entry_pos, *case_targets[i]->entry_label());
+ if (case_targets[i] == NULL) {
+ __ WriteInternalReference(entry_pos,
+ *node->break_target()->entry_label());
+ } else {
+ __ WriteInternalReference(entry_pos, *case_targets[i]);
+ }
}
+
+ delete start_frame;
}
@@ -1837,7 +1866,6 @@
node->break_target()->Initialize(this);
Load(node->tag());
-
if (TryGenerateFastCaseSwitchStatement(node)) {
return;
}
@@ -1918,13 +1946,8 @@
}
}
- if (fall_through.is_linked()) {
- fall_through.Bind();
- }
-
- if (node->break_target()->is_linked()) {
- node->break_target()->Bind();
- }
+ fall_through.Bind();
+ node->break_target()->Bind();
}
@@ -1984,16 +2007,12 @@
}
} else if (info == ALWAYS_FALSE) {
// If we had a continue in the body we have to bind its jump
target.
- if (node->continue_target()->is_linked()) {
- node->continue_target()->Bind();
- }
+ node->continue_target()->Bind();
} else {
ASSERT(info == DONT_KNOW);
// We have to compile the test expression if it can be reached by
// control flow falling out of the body or via continue.
- if (node->continue_target()->is_linked()) {
- node->continue_target()->Bind();
- }
+ node->continue_target()->Bind();
if (has_valid_frame()) {
LoadCondition(node->cond(), NOT_INSIDE_TYPEOF,
&body, node->break_target(), true);
@@ -2021,9 +2040,7 @@
JumpTarget body(this);
LoadCondition(node->cond(), NOT_INSIDE_TYPEOF,
&body, node->break_target(), true);
- if (body.is_linked()) {
- body.Bind();
- }
+ body.Bind();
}
if (has_valid_frame()) {
@@ -2066,9 +2083,7 @@
JumpTarget body(this);
LoadCondition(node->cond(), NOT_INSIDE_TYPEOF,
&body, node->break_target(), true);
- if (body.is_linked()) {
- body.Bind();
- }
+ body.Bind();
}
if (has_valid_frame()) {
@@ -2085,9 +2100,7 @@
// If there is an update statement and control flow can reach it
// via falling out of the body of the loop or continuing, we
// compile the update statement.
- if (node->continue_target()->is_linked()) {
- node->continue_target()->Bind();
- }
+ node->continue_target()->Bind();
if (has_valid_frame()) {
// Record source position of the statement as this code which
is
// after the code for the body actually belongs to the loop
@@ -2104,9 +2117,7 @@
}
DecrementLoopNesting();
- if (node->break_target()->is_linked()) {
- node->break_target()->Bind();
- }
+ node->break_target()->Bind();
}
@@ -2130,7 +2141,6 @@
JumpTarget fixed_array(this);
JumpTarget entry(this, JumpTarget::BIDIRECTIONAL);
JumpTarget end_del_check(this);
- JumpTarget cleanup(this);
JumpTarget exit(this);
// Get the object to enumerate over (converted to JSObject).
@@ -2216,7 +2226,7 @@
entry.Bind();
__ mov(eax, frame_->ElementAt(0)); // load the current count
__ cmp(eax, frame_->ElementAt(1)); // compare to the array length
- cleanup.Branch(above_equal);
+ node->break_target()->Branch(above_equal);
// Get the i'th entry of the array.
__ mov(edx, frame_->ElementAt(2));
@@ -2291,7 +2301,6 @@
entry.Jump();
// Cleanup.
- cleanup.Bind();
node->break_target()->Bind();
frame_->Drop(5);
@@ -2661,9 +2670,7 @@
Load(node->else_expression(), typeof_state());
}
- if (exit.is_linked()) {
- exit.Bind();
- }
+ exit.Bind();
}
@@ -2801,12 +2808,7 @@
// scope.
}
- // If we definitely did not jump over the assignment, we do not need
- // to bind the exit label. Doing so can defeat peephole
- // optimization.
- if (exit.is_linked()) {
- exit.Bind();
- }
+ exit.Bind();
}
}
Modified: branches/experimental/toiger/src/codegen-ia32.h
==============================================================================
--- branches/experimental/toiger/src/codegen-ia32.h (original)
+++ branches/experimental/toiger/src/codegen-ia32.h Wed Feb 4 02:59:12 2009
@@ -438,15 +438,15 @@
void GenerateFastCaseSwitchJumpTable(SwitchStatement* node,
int min_index,
int range,
- JumpTarget* fail_label,
- Vector<JumpTarget*> case_targets,
- Vector<JumpTarget> case_labels);
+ Label* fail_label,
+ Vector<Label*> case_targets,
+ Vector<Label> case_labels);
// Generate the code for cases for the fast case switch.
// Called by GenerateFastCaseSwitchJumpTable.
void GenerateFastCaseSwitchCases(SwitchStatement* node,
- Vector<JumpTarget> case_labels,
- JumpTarget* table_start);
+ Vector<Label> case_labels,
+ VirtualFrame* start_frame);
// Fast support for constant-Smi switches.
void GenerateFastCaseSwitchStatement(SwitchStatement* node,
Modified: branches/experimental/toiger/src/codegen.cc
==============================================================================
--- branches/experimental/toiger/src/codegen.cc (original)
+++ branches/experimental/toiger/src/codegen.cc Wed Feb 4 02:59:12 2009
@@ -379,17 +379,14 @@
ZoneList<CaseClause*>* cases = node->cases();
int length = cases->length();
- // JumpTarget pointer per number in range.
- SmartPointer<JumpTarget*> case_targets(NewArray<JumpTarget*>(range));
+ // Label pointer per number in range.
+ SmartPointer<Label*> case_targets(NewArray<Label*>(range));
- // JumpTarget per switch case.
- SmartPointer<JumpTarget> case_labels(NewArray<JumpTarget>(length));
- for (int i = 0; i < length; i++) {
- case_labels[i].Initialize(this);
- }
+ // Label per switch case.
+ SmartPointer<Label> case_labels(NewArray<Label>(length));
- JumpTarget* fail_label = default_index >= 0 ?
&(case_labels[default_index])
- : node->break_target();
+ Label* fail_label =
+ default_index >= 0 ? &(case_labels[default_index]) : NULL;
// Populate array of label pointers for each number in the range.
// Initally put the failure label everywhere.
@@ -400,7 +397,7 @@
// Overwrite with label of a case for the number value of that case.
// (In reverse order, so that if the same label occurs twice, the
// first one wins).
- for (int i = length-1; i >= 0 ; i--) {
+ for (int i = length - 1; i >= 0 ; i--) {
CaseClause* clause = cases->at(i);
if (!clause->is_default()) {
Object* label_value = *(clause->label()->AsLiteral()->handle());
@@ -413,35 +410,33 @@
min_index,
range,
fail_label,
- Vector<JumpTarget*>(*case_targets,
range),
- Vector<JumpTarget>(*case_labels,
length));
+ Vector<Label*>(*case_targets, range),
+ Vector<Label>(*case_labels, length));
}
void CodeGenerator::GenerateFastCaseSwitchCases(
SwitchStatement* node,
- Vector<JumpTarget> case_labels,
- JumpTarget* table_start) {
+ Vector<Label> case_labels,
+ VirtualFrame* start_frame) {
ZoneList<CaseClause*>* cases = node->cases();
int length = cases->length();
for (int i = 0; i < length; i++) {
Comment cmnt(masm(), "[ Case clause");
- case_labels[i].Bind();
+ masm()->bind(&case_labels[i]);
VisitStatements(cases->at(i)->statements());
- // All of the labels match the same expected frame as the table start.
- // If control flow cannot fall off the end of the case statement, we
- // pick up the expected frame from the table start. Otherwise we have
- // to generate merge code to match the next label.
+ // If control flow did not fall off the end of the case statement,
+ // we restore the expected frame for the next iteration (or exit
+ // of the loop). Otherwise we have to generate merge code to
+ // expectation at the next case.
if (frame_ == NULL) {
- frame_ = new VirtualFrame(table_start->expected_frame());
+ frame_ = new VirtualFrame(start_frame);
} else {
- frame_->MergeTo(table_start->expected_frame());
+ frame_->MergeTo(start_frame);
}
}
-
- node->break_target()->Bind();
}
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 Wed Feb 4
02:59:12 2009
@@ -42,7 +42,9 @@
direction_(direction),
reaching_frames_(0),
merge_labels_(0),
- expected_frame_(NULL) {
+ expected_frame_(NULL),
+ is_bound_(false),
+ is_linked_(false) {
ASSERT(cgen_ != NULL);
masm_ = cgen_->masm();
}
@@ -54,7 +56,9 @@
direction_(FORWARD_ONLY),
reaching_frames_(0),
merge_labels_(0),
- expected_frame_(NULL) {
+ expected_frame_(NULL),
+ is_bound_(false),
+ is_linked_(false) {
}
@@ -67,6 +71,26 @@
}
+void JumpTarget::Unuse() {
+ ASSERT(!is_linked());
+ entry_label_.Unuse();
+ delete expected_frame_;
+ expected_frame_ = NULL;
+ is_bound_ = false;
+ is_linked_ = false;
+}
+
+
+void JumpTarget::Reset() {
+ reaching_frames_.Clear();
+ merge_labels_.Clear();
+ expected_frame_ = NULL;
+ entry_label_.Unuse();
+ is_bound_ = false;
+ is_linked_ = false;
+}
+
+
void JumpTarget::Jump() {
ASSERT(cgen_ != NULL);
ASSERT(cgen_->has_valid_frame());
@@ -90,6 +114,8 @@
cgen_->SetFrame(NULL, &empty);
__ jmp(&merge_labels_.last());
}
+
+ is_linked_ = !is_bound_;
}
@@ -160,6 +186,8 @@
AddReachingFrame(new VirtualFrame(cgen_->frame()));
__ j(cc, &merge_labels_.last(), hint);
}
+
+ is_linked_ = !is_bound_;
}
@@ -298,12 +326,13 @@
target_frame->Adjust(1);
AddReachingFrame(target_frame);
__ call(&merge_labels_.last());
+
+ is_linked_ = !is_bound_;
}
void JumpTarget::Bind() {
ASSERT(cgen_ != NULL);
- ASSERT(is_linked() || cgen_->has_valid_frame());
ASSERT(!is_bound());
if (is_linked()) {
@@ -311,46 +340,71 @@
// the frames reaching the block via forward jumps are merged to it.
ASSERT(reaching_frames_.length() == merge_labels_.length());
- // Choose a frame as the basis of the expected frame, and make it
- // mergable. If there is a current frame use it, otherwise use the
- // first in the list (there will be at least one).
- int start_index = 0;
- if (cgen_->has_valid_frame()) {
- // Live non-frame registers are not allowed at the start of a labeled
- // basic block.
- ASSERT(cgen_->HasValidEntryRegisters());
- } else {
+ // A special case is that there was only one jump to the block so
+ // far, no fall-through, and there cannot be another entry because
+ // the block is forward only. In that case, simply use the single
+ // frame.
+ bool single_entry = (direction_ == FORWARD_ONLY) &&
+ !cgen_->has_valid_frame() &&
+ (reaching_frames_.length() == 1);
+ if (single_entry) {
+ // Pick up the only forward reaching frame and bind its merge
+ // label. No merge code is emitted.
RegisterFile reserved_registers = RegisterAllocator::Reserved();
- cgen_->SetFrame(reaching_frames_[start_index], &reserved_registers);
- __ bind(&merge_labels_[start_index++]);
- }
- cgen_->frame()->MakeMergable();
- expected_frame_ = new VirtualFrame(cgen_->frame());
-
- for (int i = start_index; i < reaching_frames_.length(); i++) {
- cgen_->DeleteFrame();
- __ jmp(&entry_label_);
+ cgen_->SetFrame(reaching_frames_[0], &reserved_registers);
+ __ bind(&merge_labels_[0]);
+ } else {
+ // Otherwise, choose a frame as the basis of the expected frame,
+ // and make it mergable. If there is a current frame use it,
+ // otherwise use the first in the list (there will be at least
+ // one).
+ int start_index = 0;
+ if (cgen_->has_valid_frame()) {
+ // Live non-frame registers are not allowed at the start of a
+ // labeled basic block.
+ ASSERT(cgen_->HasValidEntryRegisters());
+ } else {
+ RegisterFile reserved_registers = RegisterAllocator::Reserved();
+ cgen_->SetFrame(reaching_frames_[start_index],
&reserved_registers);
+ __ bind(&merge_labels_[start_index++]);
+ }
+ cgen_->frame()->MakeMergable();
+ expected_frame_ = new VirtualFrame(cgen_->frame());
+
+ for (int i = start_index; i < reaching_frames_.length(); i++) {
+ cgen_->DeleteFrame();
+ __ jmp(&entry_label_);
+
+ RegisterFile reserved_registers = RegisterAllocator::Reserved();
+ cgen_->SetFrame(reaching_frames_[i], &reserved_registers);
+ __ bind(&merge_labels_[i]);
- RegisterFile reserved_registers = RegisterAllocator::Reserved();
- cgen_->SetFrame(reaching_frames_[i], &reserved_registers);
- __ bind(&merge_labels_[i]);
+ cgen_->frame()->MergeTo(expected_frame_);
+ }
- cgen_->frame()->MergeTo(expected_frame_);
+ __ bind(&entry_label_);
}
- __ bind(&entry_label_);
// All but the last reaching virtual frame have been deleted, and
// the last one is the current frame.
reaching_frames_.Clear();
merge_labels_.Clear();
+
} else {
- // There were no forward jumps. There must be a current frame,
- // which is made mergable and used as the expected frame.
- ASSERT(cgen_->HasValidEntryRegisters());
- cgen_->frame()->MakeMergable();
- expected_frame_ = new VirtualFrame(cgen_->frame());
- __ bind(&entry_label_);
+ // There were no forward jumps. If this jump target is not
+ // bidirectional, there is no need to do anything. For
+ // bidirectional jump targets, the current frame is made mergable
+ // and used for the expected frame.
+ if (direction_ == BIDIRECTIONAL) {
+ ASSERT(cgen_->HasValidEntryRegisters());
+ cgen_->frame()->MakeMergable();
+ expected_frame_ = new VirtualFrame(cgen_->frame());
+ __ bind(&entry_label_);
+ }
}
+
+ is_linked_ = false;
+ is_bound_ = true;
}
@@ -424,6 +478,8 @@
}
destination->expected_frame_ = expected_frame_;
destination->entry_label_ = entry_label_;
+ destination->is_bound_ = is_bound_;
+ destination->is_linked_ = is_linked_;
}
Modified: branches/experimental/toiger/src/jump-target.h
==============================================================================
--- branches/experimental/toiger/src/jump-target.h (original)
+++ branches/experimental/toiger/src/jump-target.h Wed Feb 4 02:59:12 2009
@@ -83,29 +83,19 @@
}
// Predicates testing the state of the encapsulated label.
- bool is_bound() const { return expected_frame_ != NULL; }
- bool is_linked() const { return reaching_frames_.length() > 0; }
+ bool is_bound() const { return is_bound_; }
+ bool is_linked() const { return is_linked_; }
bool is_unused() const { return !is_bound() && !is_linked(); }
// Treat the jump target as a fresh one. The expected frame if any
// will be deallocated and there should be no dangling jumps to the
// target (thus no reaching frames).
- void Unuse() {
- ASSERT(!is_linked());
- entry_label_.Unuse();
- delete expected_frame_;
- expected_frame_ = NULL;
- }
+ void Unuse();
// Reset the internal state of this jump target. Pointed-to virtual
// frames are not deallocated and dangling jumps to the target are
// left dangling.
- void Reset() {
- reaching_frames_.Clear();
- merge_labels_.Clear();
- expected_frame_ = NULL;
- entry_label_.Unuse();
- }
+ void Reset();
// Copy the state of this jump target to the destination. The lists
// of forward-reaching frames and merge-point labels are copied.
@@ -177,6 +167,12 @@
// The actual entry label of the block.
Label entry_label_;
+
+ // A target is bound if its Bind member function has been called.
+ // It is linked if it is not bound but its Jump, Branch, or Call
+ // member functions have been called.
+ bool is_bound_;
+ bool is_linked_;
// Add a virtual frame reaching this labeled block via a forward
// jump, and a fresh label for its merge code.
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
