From 2816e8a899a1f09e871c7a3e5bbd7c738a7475dc Mon Sep 17 00:00:00 2001 From: "lrn@chromium.org" Date: Thu, 18 Sep 2008 11:59:55 +0000 Subject: [PATCH] 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. git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@343 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/assembler-arm-inl.h | 8 +- src/assembler-ia32-inl.h | 4 + src/assembler-ia32.cc | 22 ++++- src/assembler-ia32.h | 12 ++- src/assembler.cc | 5 +- src/assembler.h | 11 ++- src/codegen-ia32.cc | 182 ++++++++++++++++++++++++++++++++++++++- src/disassembler.cc | 9 ++ test/mjsunit/switch.js | 220 +++++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 465 insertions(+), 8 deletions(-) create mode 100644 test/mjsunit/switch.js diff --git a/src/assembler-arm-inl.h b/src/assembler-arm-inl.h index d949811..57f6b09 100644 --- a/src/assembler-arm-inl.h +++ b/src/assembler-arm-inl.h @@ -50,7 +50,13 @@ Condition NegateCondition(Condition cc) { 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(pc_); + *p += delta; // relocate entry + } + // We do not use pc relative addressing on ARM, so there is + // nothing else to do. } diff --git a/src/assembler-ia32-inl.h b/src/assembler-ia32-inl.h index 66102e6..25b5f7d 100644 --- a/src/assembler-ia32-inl.h +++ b/src/assembler-ia32-inl.h @@ -56,6 +56,10 @@ void RelocInfo::apply(int delta) { // instruction has been inserted). int32_t* p = reinterpret_cast(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(pc_); + *p += delta; // relocate entry } } diff --git a/src/assembler-ia32.cc b/src/assembler-ia32.cc index d314a03..af9cc8a 100644 --- a/src/assembler-ia32.cc +++ b/src/assembler-ia32.cc @@ -151,7 +151,8 @@ void Displacement::init(Label* L, Type type) { 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 @@ void Assembler::bind_to(Label* L, int pos) { 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 @@ void Assembler::GrowBuffer() { if (rmode == runtime_entry) { int32_t* p = reinterpret_cast(it.rinfo()->pc()); *p -= pc_delta; // relocate entry + } else if (rmode == internal_reference) { + int32_t* p = reinterpret_cast(it.rinfo()->pc()); + if (*p != 0) { // 0 means uninitialized. + *p += pc_delta; + } } } @@ -2011,6 +2018,11 @@ void Assembler::emit_farith(int b1, int b2, int i) { 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 @@ void Assembler::RecordRelocInfo(RelocMode rmode, intptr_t data) { 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(addr_at(bound_label.pos())); + long_at_put(position, label_loc); +} } } // namespace v8::internal diff --git a/src/assembler-ia32.h b/src/assembler-ia32.h index 3f93505..abedd82 100644 --- a/src/assembler-ia32.h +++ b/src/assembler-ia32.h @@ -280,7 +280,7 @@ class Operand BASE_EMBEDDED { // // Displacement _data field layout // -// |31.....1|.......0| +// |31.....1| ......0| // [ next | type | class Displacement BASE_EMBEDDED { @@ -317,6 +317,7 @@ class Displacement BASE_EMBEDDED { }; + // CpuFeatures keeps track of which features are supported by the target CPU. // Supported features must be enabled by a Scope before use. // Example: @@ -675,6 +676,15 @@ class Assembler : public Malloced { 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_; } int last_position() const { return last_position_; } diff --git a/src/assembler.cc b/src/assembler.cc index 7b4ffc7..99877f7 100644 --- a/src/assembler.cc +++ b/src/assembler.cc @@ -78,7 +78,7 @@ int Label::pos() const { // 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 @@ const char* RelocInfo::RelocModeName(RelocMode rmode) { 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 @@ void RelocInfo::Verify() { case position: case statement_position: case external_reference: + case internal_reference: case no_reloc: break; case reloc_mode_count: diff --git a/src/assembler.h b/src/assembler.h index d50de61..e216123 100644 --- a/src/assembler.h +++ b/src/assembler.h @@ -158,11 +158,12 @@ enum RelocMode { 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 }; @@ -217,6 +218,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 // to which the relocation information applies, the relocation mode // (rmode), and an optional data field. The relocation mode may be diff --git a/src/codegen-ia32.cc b/src/codegen-ia32.cc index 3e36dbf..220a78c 100644 --- a/src/codegen-ia32.cc +++ b/src/codegen-ia32.cc @@ -314,6 +314,40 @@ class Ia32CodeGenerator: public CodeGenerator { 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 &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 @@ void Ia32CodeGenerator::VisitWithExitStatement(WithExitStatement* node) { } +// 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 &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* cases = node->cases(); + int length = cases->length(); + + SmartPointer case_targets(NewArray(range)); + SmartPointer