Author: [EMAIL PROTECTED]
Date: Thu Sep 18 04:59:55 2008
New Revision: 343
Added:
branches/bleeding_edge/test/mjsunit/switch.js
Removed:
changes/lrn/jumptable/
Modified:
branches/bleeding_edge/src/assembler-arm-inl.h
branches/bleeding_edge/src/assembler-ia32-inl.h
branches/bleeding_edge/src/assembler-ia32.cc
branches/bleeding_edge/src/assembler-ia32.h
branches/bleeding_edge/src/assembler.cc
branches/bleeding_edge/src/assembler.h
branches/bleeding_edge/src/codegen-ia32.cc
branches/bleeding_edge/src/disassembler.cc
Log:
Added fast-case for switch statement where all lables are constant Smi's in
a limited range (IA32 only so far).
Implemented using a jump-table, for constant time lookup.
Modified: branches/bleeding_edge/src/assembler-arm-inl.h
==============================================================================
--- branches/bleeding_edge/src/assembler-arm-inl.h (original)
+++ branches/bleeding_edge/src/assembler-arm-inl.h Thu Sep 18 04:59:55 2008
@@ -50,7 +50,13 @@
void RelocInfo::apply(int delta) {
- // We do not use pc relative addressing on ARM, so there is nothing to
do.
+ if (is_internal_reference(rmode_)) {
+ // absolute code pointer inside code object moves with the code object.
+ int32_t* p = reinterpret_cast<int32_t*>(pc_);
+ *p += delta; // relocate entry
+ }
+ // We do not use pc relative addressing on ARM, so there is
+ // nothing else to do.
}
Modified: branches/bleeding_edge/src/assembler-ia32-inl.h
==============================================================================
--- branches/bleeding_edge/src/assembler-ia32-inl.h (original)
+++ branches/bleeding_edge/src/assembler-ia32-inl.h Thu Sep 18 04:59:55 2008
@@ -56,6 +56,10 @@
// instruction has been inserted).
int32_t* p = reinterpret_cast<int32_t*>(pc_ + 1);
*p -= delta; // relocate entry
+ } else if (is_internal_reference(rmode_)) {
+ // absolute code pointer inside code object moves with the code object.
+ int32_t* p = reinterpret_cast<int32_t*>(pc_);
+ *p += delta; // relocate entry
}
}
Modified: branches/bleeding_edge/src/assembler-ia32.cc
==============================================================================
--- branches/bleeding_edge/src/assembler-ia32.cc (original)
+++ branches/bleeding_edge/src/assembler-ia32.cc Thu Sep 18 04:59:55 2008
@@ -151,7 +151,8 @@
const int RelocInfo::kApplyMask =
- RelocInfo::kCodeTargetMask | 1 << runtime_entry | 1 << js_return;
+ RelocInfo::kCodeTargetMask | 1 << runtime_entry |
+ 1 << js_return | 1 << internal_reference;
void RelocInfo::patch_code(byte* instructions, int instruction_count) {
@@ -1181,6 +1182,7 @@
if (disp.type() == Displacement::UNCONDITIONAL_JUMP) {
ASSERT(byte_at(fixup_pos - 1) == 0xE9); // jmp expected
}
+ // relative address, relative to point after address
int imm32 = pos - (fixup_pos + sizeof(int32_t));
long_at_put(fixup_pos, imm32);
disp.next(L);
@@ -1945,6 +1947,11 @@
if (rmode == runtime_entry) {
int32_t* p = reinterpret_cast<int32_t*>(it.rinfo()->pc());
*p -= pc_delta; // relocate entry
+ } else if (rmode == internal_reference) {
+ int32_t* p = reinterpret_cast<int32_t*>(it.rinfo()->pc());
+ if (*p != 0) { // 0 means uninitialized.
+ *p += pc_delta;
+ }
}
}
@@ -2011,6 +2018,11 @@
EMIT(b2 + i);
}
+void Assembler::dd(uint32_t data, RelocMode reloc_info) {
+ EnsureSpace ensure_space(this);
+ emit(data, reloc_info);
+}
+
void Assembler::RecordRelocInfo(RelocMode rmode, intptr_t data) {
ASSERT(rmode != no_reloc);
@@ -2024,5 +2036,13 @@
reloc_info_writer.Write(&rinfo);
}
+void Assembler::WriteInternalReference(int position, Label &bound_label) {
+ ASSERT(bound_label.is_bound());
+ ASSERT(0 <= position && position + (int)sizeof(uint32_t) <= pc_offset());
+ ASSERT(long_at(position) == 0); // only initialize once!
+
+ uint32_t label_loc =
reinterpret_cast<uint32_t>(addr_at(bound_label.pos()));
+ long_at_put(position, label_loc);
+}
} } // namespace v8::internal
Modified: branches/bleeding_edge/src/assembler-ia32.h
==============================================================================
--- branches/bleeding_edge/src/assembler-ia32.h (original)
+++ branches/bleeding_edge/src/assembler-ia32.h Thu Sep 18 04:59:55 2008
@@ -280,7 +280,7 @@
//
// Displacement _data field layout
//
-// |31.....1|.......0|
+// |31.....1| ......0|
// [ next | type |
class Displacement BASE_EMBEDDED {
@@ -317,6 +317,7 @@
};
+
// CpuFeatures keeps track of which features are supported by the target
CPU.
// Supported features must be enabled by a Scope before use.
// Example:
@@ -674,6 +675,15 @@
void RecordPosition(int pos);
void RecordStatementPosition(int pos);
void WriteRecordedPositions();
+
+ // Writes a single word of data in the code stream.
+ // Used for inline tables, e.g., jump-tables.
+ void dd(uint32_t data, RelocMode reloc_info);
+
+ // Writes the absolute address of a bound label at the given position in
+ // the generated code. That positions should have the relocation mode
+ // internal_reference!
+ void WriteInternalReference(int position, Label &bound_label);
int pc_offset() const { return pc_ - buffer_; }
int last_statement_position() const { return last_statement_position_; }
Modified: branches/bleeding_edge/src/assembler.cc
==============================================================================
--- branches/bleeding_edge/src/assembler.cc (original)
+++ branches/bleeding_edge/src/assembler.cc Thu Sep 18 04:59:55 2008
@@ -78,7 +78,7 @@
// statement_position: [6 bits pc delta] 10,
// [7 bits signed data delta] 1
//
-// any nondata mode: 00 [4 bits rmode] 11,
+// any nondata mode: 00 [4 bits rmode] 11, // rmode: 0..13 only
// 00 [6 bits pc delta]
//
// pc-jump: 00 1111 11,
@@ -429,6 +429,8 @@
return "statement position";
case external_reference:
return "external reference";
+ case internal_reference:
+ return "internal reference";
case reloc_mode_count:
UNREACHABLE();
return "reloc_mode_count";
@@ -489,6 +491,7 @@
case position:
case statement_position:
case external_reference:
+ case internal_reference:
case no_reloc:
break;
case reloc_mode_count:
Modified: branches/bleeding_edge/src/assembler.h
==============================================================================
--- branches/bleeding_edge/src/assembler.h (original)
+++ branches/bleeding_edge/src/assembler.h Thu Sep 18 04:59:55 2008
@@ -158,11 +158,12 @@
position, // See comment for kNoPosition above.
statement_position, // See comment for kNoPosition above.
external_reference, // The address of an external C++ function.
- // add more as needed
- no_reloc, // never recorded
+ internal_reference, // An address inside the same function.
+ // add more as needed
// Pseudo-types
- reloc_mode_count,
+ reloc_mode_count, // Must be no greater than 14. See RelocInfoWriter.
+ no_reloc, // never recorded
last_code_enum = code_target,
last_gced_enum = embedded_string
};
@@ -215,6 +216,10 @@
inline bool is_external_reference(RelocMode mode) {
return mode == external_reference;
+}
+
+inline bool is_internal_reference(RelocMode mode) {
+ return mode == internal_reference;
}
// Relocation information consists of the address (pc) of the datum
Modified: branches/bleeding_edge/src/codegen-ia32.cc
==============================================================================
--- branches/bleeding_edge/src/codegen-ia32.cc (original)
+++ branches/bleeding_edge/src/codegen-ia32.cc Thu Sep 18 04:59:55 2008
@@ -314,6 +314,40 @@
NODE_LIST(DEF_VISIT)
#undef DEF_VISIT
+ // Only allow fast-case switch if the range of labels is at most
+ // this factor times the number of case labels.
+ // Value is derived from comparing the size of code generated by the
normal
+ // switch code for Smi-labels to the size of a single pointer. If code
+ // quality increases this number should be decreased to match.
+ static const int kFastSwitchMaxOverheadFactor = 5;
+
+ // Minimal number of switch cases required before we allow jump-table
+ // optimization.
+ static const int kFastSwitchMinCaseCount = 5;
+
+ // Create fast switch implementation if all labels are small integers
+ // in a limited range. Returns false if this is not the case, and no
+ // code has been generated (i.e., the default implementation should be
used).
+ bool TryFastCaseSwitchStatement(SwitchStatement *switchStmt);
+
+ // Generate a computed jump with an empty jump table.
+ // Binds a label to the start of the jump table. This table must
+ // be populated later when the adresses of the targets are known.
+ // Used by GenerateFastCaseSwitchStatement.
+ void GenerateFastCaseSwitchJumpTable(
+ int min_index, int range, Label *fail_label, Label &table_start);
+
+ // Populate an empty jump table with the adresses of bound labels.
+ // Used by GenerateFastCaseSwitchStatement.
+ void PopulateFastCaseSwitchJumpTable(
+ Label &table_start, SmartPointer<Label*> &case_targets, int
table_size);
+
+ // Generates a fast-case switch statement for a switch with all-Smi
labels
+ // in a limited range.
+ // Used by TryFastCaseSwitchStatement.
+ void GenerateFastCaseSwitchStatement(
+ SwitchStatement *node, int min_index, int range, int default_index);
+
void RecordStatementPosition(Node* node);
// Activation frames.
@@ -2900,6 +2934,149 @@
}
+// Generate a computed jump with an empty jump table.
+// Returns a label pointing to the start of the jump table. This must
+// be populated later when the adresses of the targets are known
+void Ia32CodeGenerator::GenerateFastCaseSwitchJumpTable(
+ int min_index, int range, Label *fail_label, Label &table_start) {
+ // 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 survive
relocation,
+ // and it also cannot safely be distinguished from a real address.
+ // Instead we put in zero-values as placeholders, and fill in the
adresses after
+ // the labels have been bound.
+
+ __ pop(eax); // supposed Smi
+ // check range of value, if outside [0..length-1] jump to default/end
label.
+ ASSERT(kSmiTagSize == 1 && kSmiTag == 0);
+ if (min_index != 0) {
+ __ sub(Operand(eax), Immediate(min_index * 2)); // Smi subtraction
+ }
+ __ test(eax, Immediate(0x80000000 | kSmiTagMask)); // negative or not
Smi
+ __ j(not_equal, fail_label, not_taken);
+ __ cmp(eax, range * 2);
+ __ j(greater_equal, fail_label, not_taken);
+
+ __ jmp(Operand(eax, times_2, 0x0, internal_reference)); // 0 is
placeholder
+ // calculate address to overwrite later with actual address of table.
+ int32_t jump_table_ref = __ pc_offset() - sizeof(int32_t);
+
+ __ Align(4);
+ __ bind(&table_start);
+ __ WriteInternalReference(jump_table_ref, table_start);
+
+ for (int i = 0; i < range; i++) {
+ __ dd(0x0, internal_reference); // table entry, 0 is placeholder
+ }
+}
+
+
+// Populate an empty jump table with the adresses of bound labels.
+void Ia32CodeGenerator::PopulateFastCaseSwitchJumpTable(
+ Label &table_start, SmartPointer<Label*> &case_targets, int
table_size) {
+ for (int i = 0; i < table_size; i++) {
+ int table_entry_pos = table_start.pos() + i * sizeof(uint32_t);
+ __ WriteInternalReference(table_entry_pos, *case_targets[i]);
+ }
+}
+
+
+// Generates a fast-case switch statement for a switch with all-Smi labels
+// in a limited range.
+void Ia32CodeGenerator::GenerateFastCaseSwitchStatement(
+ SwitchStatement *node, int min_index, int range, int default_index) {
+ ZoneList<CaseClause*>* cases = node->cases();
+ int length = cases->length();
+
+ SmartPointer<Label*> case_targets(NewArray<Label*>(range));
+ SmartPointer<Label> case_labels(NewArray<Label>(length));
+
+ Label* fail_label = (default_index >= 0 ? &(case_labels[default_index])
+ : node->break_target());
+
+ // create array of labels to jump to by index.
+ // set default jump targets everywhere
+ for (int i = 0; i < range; i++) {
+ // length => end label
+ case_targets[i] = fail_label;
+ }
+ // overwrite for values of cases:
+ // (reverse order, so that if same label twice, the first one wins)
+ for (int i = length-1; i >= 0 ; i--) {
+ CaseClause* clause = cases->at(i);
+ if (!clause->is_default()) {
+ Object* label_value = *(clause->label()->AsLiteral()->handle());
+ int case_value = Smi::cast(label_value)->value();
+ case_targets[case_value - min_index] = &(case_labels[i]);
+ }
+ }
+
+ // Generate the jump table and code for all cases.
+ Label table_start;
+
+ GenerateFastCaseSwitchJumpTable(min_index, range, fail_label,
table_start);
+
+ for (int i = 0; i < length; i++) {
+ Comment cmnt(masm_, "[ case clause");
+ __ bind(&(case_labels[i]));
+ VisitStatements(cases->at(i)->statements());
+ }
+
+ __ bind(node->break_target());
+
+ // all labels bound now, so we can populate the table with the
+ // correct addresses.
+ PopulateFastCaseSwitchJumpTable(table_start, case_targets, range);
+}
+
+
+bool Ia32CodeGenerator::TryFastCaseSwitchStatement(SwitchStatement *node) {
+ ZoneList<CaseClause*>* cases = node->cases();
+ int length = cases->length();
+
+ if (length < kFastSwitchMinCaseCount) {
+ return false;
+ }
+
+ // Test whether fast-case should be used.
+ int default_index = -1;
+ int min_index = Smi::kMaxValue;
+ int max_index = Smi::kMinValue;
+ for (int i = 0; i < length; i++) {
+ CaseClause* clause = cases->at(i);
+ if (clause->is_default()) {
+ if (default_index >= 0) {
+ return false; // More than one default label:
+ // Defer to normal case for error.
+ }
+ default_index = i;
+ } else {
+ Expression* label = clause->label();
+ Literal* literal = label->AsLiteral();
+ if (literal == NULL) {
+ return false; // fail fast case
+ }
+ Object* value = *(literal->handle());
+ if (!value->IsSmi()) {
+ return false;
+ }
+ int smi = Smi::cast(value)->value();
+ if (smi < min_index) { min_index = smi; }
+ if (smi > max_index) { max_index = smi; }
+ }
+ }
+ // all labels are Smi.
+ int range = max_index - min_index + 1; // |min..max| inclusive
+ if (range / kFastSwitchMaxOverheadFactor > length) {
+ return false; // range of labels is too sparse
+ }
+
+ // Optimization accepted, generate code.
+ GenerateFastCaseSwitchStatement(node, min_index, range, default_index);
+ return true;
+}
+
+
void Ia32CodeGenerator::VisitSwitchStatement(SwitchStatement* node) {
Comment cmnt(masm_, "[ SwitchStatement");
RecordStatementPosition(node);
@@ -2907,13 +3084,16 @@
Load(node->tag());
+ if (TryFastCaseSwitchStatement(node)) {
+ return;
+ }
+
Label next, fall_through, default_case;
ZoneList<CaseClause*>* cases = node->cases();
int length = cases->length();
for (int i = 0; i < length; i++) {
CaseClause* clause = cases->at(i);
-
Comment cmnt(masm_, "[ case clause");
if (clause->is_default()) {
Modified: branches/bleeding_edge/src/disassembler.cc
==============================================================================
--- branches/bleeding_edge/src/disassembler.cc (original)
+++ branches/bleeding_edge/src/disassembler.cc Thu Sep 18 04:59:55 2008
@@ -139,6 +139,15 @@
*reinterpret_cast<int32_t*>(pc));
constants = num_const;
pc += 4;
+ } else if (it != NULL && !it->done() && it->rinfo()->pc() == pc &&
+ it->rinfo()->rmode() == internal_reference) {
+ // raw pointer embedded in code stream, e.g., jump table
+ byte* ptr = *reinterpret_cast<byte**>(pc);
+ OS::SNPrintF(decode_buffer,
+ "%08x jump table entry %4d",
+ reinterpret_cast<int32_t>(ptr),
+ ptr - begin);
+ pc += 4;
} else {
decode_buffer[0] = '\0';
pc += d.InstructionDecode(decode_buffer, pc);
Added: branches/bleeding_edge/test/mjsunit/switch.js
==============================================================================
--- (empty file)
+++ branches/bleeding_edge/test/mjsunit/switch.js Thu Sep 18 04:59:55 2008
@@ -0,0 +1,220 @@
+// Copyright 2008 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+function f0() {
+ switch (0) {
+ // switch deliberatly left empty
+ }
+}
+
+f0(); // no errors
+
+function f1(x) {
+ switch (x) {
+ default: return "f1";
+ }
+ return "foo";
+}
+
+assertEquals("f1", f1(0), "default-switch.0");
+assertEquals("f1", f1(1), "default-switch.1");
+
+function f2(x) {
+ var r;
+ switch (x) {
+ case 0:
+ r = "zero";
+ break;
+ case 1:
+ r = "one";
+ break;
+ case 2:
+ r = "two";
+ break
+ case 3:
+ r = "three";
+ break;
+ default:
+ r = "default";
+ }
+ return r;
+}
+
+assertEquals("zero", f2(0), "0-1-switch.0");
+assertEquals("one", f2(1), "0-1-switch.1");
+assertEquals("default", f2(7), "0-1-switch.2");
+assertEquals("default", f2(-1), "0-1-switch.-1");
+assertEquals("default", f2(NaN), "0-1-switch.NaN");
+
+
+function f3(x, c) {
+ var r = 0;
+ switch (x) {
+ default:
+ r = "default";
+ break;
+ case c:
+ r = "value is c = " + c;
+ break;
+ case 2:
+ r = "two";
+ break;
+ case -5:
+ r = "minus 5";
+ break;
+ case 9:
+ r = "nine";
+ break;
+ }
+ return r;
+}
+
+assertEquals("two", f3(2,0), "value-switch.2-0");
+assertEquals("minus 5", f3(-5,0), "value-switch.-5-0");
+assertEquals("nine", f3(9,0), "value-switch.9-0");
+assertEquals("value is c = 0", f3(0,0), "value-switch.0-0");
+assertEquals("value is c = 2", f3(2,2), "value-switch.2-2");
+assertEquals("default", f3(7,0), "value-switch.7-0");
+
+
+function f4(x) {
+ switch(x) {
+ case 0:
+ x++;
+ default:
+ x++;
+ case 2:
+ x++;
+ }
+ return x;
+}
+
+
+assertEquals(3, f4(0), "fallthrough-switch.0")
+assertEquals(3, f4(1), "fallthrough-switch.1")
+assertEquals(3, f4(2), "fallthrough-switch.2")
+assertEquals(5, f4(3), "fallthrough-switch.3")
+
+
+function f5(x) {
+ switch(x) {
+ case -2: return true;
+ case -1: return false;
+ case 0: return true;
+ case 2: return false;
+ default: return 42;
+ }
+}
+
+assertTrue(f5(-2), "negcase.-2")
+assertFalse(f5(-1), "negcase.-1")
+assertTrue(f5(0), "negcase.-0")
+assertEquals(42, f5(1), "negcase.1")
+assertFalse(f5(2), "negcase.2")
+
+function f6(N) {
+ // long enough case that code buffer grows while it is code-generated.
+ var res = 0;
+ for(var i = 0; i < N; i++) {
+ switch(i & 0x3f) {
+ case 0: res += 0; break;
+ case 1: res += 1; break;
+ case 2: res += 2; break;
+ case 3: res += 3; break;
+ case 4: res += 4; break;
+ case 5: res += 5; break;
+ case 6: res += 6; break;
+ case 7: res += 7; break;
+ case 8: res += 8; break;
+ case 9: res += 9; break;
+ case 10: res += 10; break;
+ case 11: res += 11; break;
+ case 12: res += 12; break;
+ case 13: res += 13; break;
+ case 14: res += 14; break;
+ case 15: res += 15; break;
+ case 16: res += 16; break;
+ case 17: res += 17; break;
+ case 18: res += 18; break;
+ case 19: res += 19; break;
+ case 20: res += 20; break;
+ case 21: res += 21; break;
+ case 22: res += 22; break;
+ case 23: res += 23; break;
+ case 24: res += 24; break;
+ case 25: res += 25; break;
+ case 26: res += 26; break;
+ case 27: res += 27; break;
+ case 28: res += 28; break;
+ case 29: res += 29; break;
+ case 30: res += 30; break;
+ case 31: res += 31; break;
+ case 32: res += 32; break;
+ case 33: res += 33; break;
+ case 34: res += 34; break;
+ case 35: res += 35; break;
+ case 36: res += 36; break;
+ case 37: res += 37; break;
+ case 38: res += 38; break;
+ case 39: res += 39; break;
+ case 40: res += 40; break;
+ case 41: res += 41; break;
+ case 42: res += 42; break;
+ case 43: res += 43; break;
+ case 44: res += 44; break;
+ case 45: res += 45; break;
+ case 46: res += 46; break;
+ case 47: res += 47; break;
+ case 48: res += 48; break;
+ case 49: res += 49; break;
+ case 50: res += 50; break;
+ case 51: res += 51; break;
+ case 52: res += 52; break;
+ case 53: res += 53; break;
+ case 54: res += 54; break;
+ case 55: res += 55; break;
+ case 56: res += 56; break;
+ case 57: res += 57; break;
+ case 58: res += 58; break;
+ case 59: res += 59; break;
+ case 60: res += 60; break;
+ case 61: res += 61; break;
+ case 62: res += 62; break;
+ case 63: res += 63; break;
+ case 64: break;
+ default: break;
+ }
+ }
+ return res;
+}
+
+assertEquals(190, f6(20), "largeSwitch.20");
+assertEquals(2016, f6(64), "largeSwitch.64");
+assertEquals(4032, f6(128), "largeSwitch.128");
+assertEquals(4222, f6(148), "largeSwitch.148");
+
+
\ No newline at end of file
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
