I'd like you to do code review. Changes since the previous reviews: Stopped using displacements, so ABSOLUTE_ADDRESS is completely gone. Jump-table is no longer in the assembler, but part of the fast-case switch.
To review this change, run gvn review --project https://v8.googlecode.com/svn/branches/bleeding_edge lrn/[EMAIL PROTECTED] Alternatively, to review the latest snapshot of this change branch, run gvn --project https://v8.googlecode.com/svn/branches/bleeding_edge review lrn/jumptable to review the following change: *lrn/[EMAIL PROTECTED] | lrn | 2008-09-18 10:02:08 +-100 (Thu, 18 Sep 2008) Description: 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. Fixed bug in previous version where relocating the code buffer munged displacements. Now don't use displacement at all. Affected Paths: M //branches/bleeding_edge/src/assembler-arm-inl.h M //branches/bleeding_edge/src/assembler-ia32-inl.h M //branches/bleeding_edge/src/assembler-ia32.cc M //branches/bleeding_edge/src/assembler-ia32.h M //branches/bleeding_edge/src/assembler.cc M //branches/bleeding_edge/src/assembler.h M //branches/bleeding_edge/src/codegen-ia32.cc M //branches/bleeding_edge/src/disassembler.cc A //branches/bleeding_edge/test/mjsunit/switch.js This is a semiautomated message from "gvn mail". See <http://code.google.com/p/gvn/> to learn more. Index: src/assembler-arm-inl.h =================================================================== --- src/assembler-arm-inl.h (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) +++ src/assembler-arm-inl.h (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) @@ -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<int32_t*>(pc_); + *p += delta; // relocate entry + } + // We do not use pc relative addressing on ARM, so there is + // nothing else to do. } Index: src/assembler-ia32-inl.h =================================================================== --- src/assembler-ia32-inl.h (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) +++ src/assembler-ia32-inl.h (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) @@ -56,6 +56,10 @@ void RelocInfo::apply(int delta) { // 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 } } Index: src/assembler-ia32.cc =================================================================== --- src/assembler-ia32.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) +++ src/assembler-ia32.cc (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) @@ -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); @@ -1936,6 +1938,11 @@ void Assembler::GrowBuffer() { 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; + } } } @@ -2002,7 +2009,12 @@ 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); // Don't record external references unless the heap will be serialized. @@ -2015,5 +2027,13 @@ void Assembler::RecordRelocInfo(RelocMode rmode, i 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 Index: src/assembler-ia32.h =================================================================== --- src/assembler-ia32.h (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) +++ src/assembler-ia32.h (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) @@ -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: @@ -674,6 +675,15 @@ class Assembler : public Malloced { void RecordPosition(int pos); void RecordStatementPosition(int pos); + // 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 = no_reloc); + + // 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_position() const { return last_position_; } bool last_position_is_statement() const { Index: src/assembler.cc =================================================================== --- src/assembler.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) +++ src/assembler.cc (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) @@ -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 rmo 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: Index: src/assembler.h =================================================================== --- src/assembler.h (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) +++ src/assembler.h (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) @@ -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. + internal_reference, // address inside same region (e.g. jump table entry) + // add more as needed + // Pseudo-types + reloc_mode_count, // must be no greater than 14! no_reloc, // never recorded - - // Pseudo-types - reloc_mode_count, 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 Index: src/codegen-ia32.cc =================================================================== --- src/codegen-ia32.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) +++ src/codegen-ia32.cc (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) @@ -314,6 +314,18 @@ class Ia32CodeGenerator: public CodeGenerator { NODE_LIST(DEF_VISIT) #undef DEF_VISIT + // Max ratio of labels-count/label-range for fast table-based Smi switch, + // i.e., the sparseness of the jump table, as percentage. + static const int kFastSwitchMaxOverheadPercent = 200; + // Minimal number of switch cases required before we use 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); + void RecordStatementPosition(Node* node); // Activation frames. @@ -2899,7 +2911,125 @@ void Ia32CodeGenerator::VisitWithExitStatement(Wit __ mov(Operand(ebp, StandardFrameConstants::kContextOffset), esi); } +bool Ia32CodeGenerator::TryFastCaseSwitchStatement(SwitchStatement *node) { + ZoneList<CaseClause*>* cases = node->cases(); + int length = cases->length(); + if (length < kFastSwitchMinCaseCount) { + return false; + } + + // test whether fast-case is possible + 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 > length * kFastSwitchMaxOverheadPercent / 100) { + return false; // range of labels is too sparse + } + + // Optimization accepted, generate code. + + SmartPointer<Label*> case_targets_alloc(NewArray<Label*>(range)); + SmartPointer<Label> case_labels_alloc(NewArray<Label>(length)); + + Label** case_targets = *case_targets_alloc; + Label* case_labels = *case_labels_alloc; + 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. + // Notice: Internal references, used by both the jmp instruction and the + // table entries, needs to be relocated if the buffer grows. This prevents + // the forward use of Labels, as their displacement doesn't survive reloaction, + // and it 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); + Label table_start; + __ bind(&table_start); + + for (int i = 0; i < range; i++) { + __ dd(0x0, internal_reference); // table entry, 0 is placeholder + } + + 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 replace placeholders and + // populate the table with the correct addresses. + __ WriteInternalReference(jump_table_ref, table_start); + for (int i = 0; i < range; i++) { + int table_entry_pos = table_start.pos() + i * sizeof(uint32_t); + __ WriteInternalReference(table_entry_pos, *case_targets[i]); + } + + return true; +} + + void Ia32CodeGenerator::VisitSwitchStatement(SwitchStatement* node) { Comment cmnt(masm_, "[ SwitchStatement"); if (FLAG_debug_info) RecordStatementPosition(node); @@ -2907,13 +3037,16 @@ void Ia32CodeGenerator::VisitSwitchStatement(Switc 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()) { Index: src/disassembler.cc =================================================================== --- src/disassembler.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) +++ src/disassembler.cc (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) @@ -139,6 +139,15 @@ static int DecodeIt(FILE* f, *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); Index: test/mjsunit/switch.js =================================================================== --- test/mjsunit/switch.js (added) +++ test/mjsunit/switch.js (^/changes/lrn/jumptable/bleeding_edge/test/mjsunit/[EMAIL PROTECTED]) @@ -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 -~----------~----~----~----~------~----~------~--~---
