From 6b47d262171a8212e00e9e602ed14310692fe87a Mon Sep 17 00:00:00 2001 From: "vegorov@chromium.org" Date: Mon, 8 Mar 2010 11:58:33 +0000 Subject: [PATCH] Port of changes from r3842 (symbol table probing for two character strings) to x64 and arm Review URL: http://codereview.chromium.org/661469 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@4050 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/codegen-arm.cc | 246 ++++++++++++++++++++++++++++++- src/arm/codegen-arm.h | 30 ++++ src/arm/macro-assembler-arm.cc | 45 ++++-- src/arm/macro-assembler-arm.h | 16 ++ src/ia32/codegen-ia32.cc | 16 +- src/objects.h | 2 + src/x64/codegen-x64.cc | 257 +++++++++++++++++++++++++++++++-- src/x64/codegen-x64.h | 27 ++++ src/x64/macro-assembler-x64.cc | 44 ++++++ src/x64/macro-assembler-x64.h | 14 ++ 10 files changed, 659 insertions(+), 38 deletions(-) diff --git a/src/arm/codegen-arm.cc b/src/arm/codegen-arm.cc index 966d5b938..91ea2ec11 100644 --- a/src/arm/codegen-arm.cc +++ b/src/arm/codegen-arm.cc @@ -7249,6 +7249,170 @@ void StringStubBase::GenerateCopyCharactersLong(MacroAssembler* masm, } +void StringStubBase::GenerateTwoCharacterSymbolTableProbe(MacroAssembler* masm, + Register c1, + Register c2, + Register scratch1, + Register scratch2, + Register scratch3, + Register scratch4, + Register scratch5, + Label* not_found) { + // Register scratch3 is the general scratch register in this function. + Register scratch = scratch3; + + // Make sure that both characters are not digits as such strings has a + // different hash algorithm. Don't try to look for these in the symbol table. + Label not_array_index; + __ sub(scratch, c1, Operand(static_cast('0'))); + __ cmp(scratch, Operand(static_cast('9' - '0'))); + __ b(hi, ¬_array_index); + __ sub(scratch, c2, Operand(static_cast('0'))); + __ cmp(scratch, Operand(static_cast('9' - '0'))); + + // If check failed combine both characters into single halfword. + // This is required by the contract of the method: code at the + // not_found branch expects this combination in c1 register + __ orr(c1, c1, Operand(c2, LSL, kBitsPerByte), LeaveCC, ls); + __ b(ls, not_found); + + __ bind(¬_array_index); + // Calculate the two character string hash. + Register hash = scratch1; + GenerateHashInit(masm, hash, c1); + GenerateHashAddCharacter(masm, hash, c2); + GenerateHashGetHash(masm, hash); + + // Collect the two characters in a register. + Register chars = c1; + __ orr(chars, chars, Operand(c2, LSL, kBitsPerByte)); + + // chars: two character string, char 1 in byte 0 and char 2 in byte 1. + // hash: hash of two character string. + + // Load symbol table + // Load address of first element of the symbol table. + Register symbol_table = c2; + __ LoadRoot(symbol_table, Heap::kSymbolTableRootIndex); + + // Load undefined value + Register undefined = scratch4; + __ LoadRoot(undefined, Heap::kUndefinedValueRootIndex); + + // Calculate capacity mask from the symbol table capacity. + Register mask = scratch2; + __ ldr(mask, FieldMemOperand(symbol_table, SymbolTable::kCapacityOffset)); + __ mov(mask, Operand(mask, ASR, 1)); + __ sub(mask, mask, Operand(1)); + + // Calculate untagged address of the first element of the symbol table. + Register first_symbol_table_element = symbol_table; + __ add(first_symbol_table_element, symbol_table, + Operand(SymbolTable::kElementsStartOffset - kHeapObjectTag)); + + // Registers + // chars: two character string, char 1 in byte 0 and char 2 in byte 1. + // hash: hash of two character string + // mask: capacity mask + // first_symbol_table_element: address of the first element of + // the symbol table + // scratch: - + + // Perform a number of probes in the symbol table. + static const int kProbes = 4; + Label found_in_symbol_table; + Label next_probe[kProbes]; + for (int i = 0; i < kProbes; i++) { + Register candidate = scratch5; // Scratch register contains candidate. + + // Calculate entry in symbol table. + if (i > 0) { + __ add(candidate, hash, Operand(SymbolTable::GetProbeOffset(i))); + } else { + __ mov(candidate, hash); + } + + __ and_(candidate, candidate, Operand(mask)); + + // Load the entry from the symble table. + ASSERT_EQ(1, SymbolTable::kEntrySize); + __ ldr(candidate, + MemOperand(first_symbol_table_element, + candidate, + LSL, + kPointerSizeLog2)); + + // If entry is undefined no string with this hash can be found. + __ cmp(candidate, undefined); + __ b(eq, not_found); + + // If length is not 2 the string is not a candidate. + __ ldr(scratch, FieldMemOperand(candidate, String::kLengthOffset)); + __ cmp(scratch, Operand(2)); + __ b(ne, &next_probe[i]); + + // Check that the candidate is a non-external ascii string. + __ ldr(scratch, FieldMemOperand(candidate, HeapObject::kMapOffset)); + __ ldrb(scratch, FieldMemOperand(scratch, Map::kInstanceTypeOffset)); + __ JumpIfInstanceTypeIsNotSequentialAscii(scratch, scratch, + &next_probe[i]); + + // Check if the two characters match. + // Assumes that word load is little endian. + __ ldrh(scratch, FieldMemOperand(candidate, SeqAsciiString::kHeaderSize)); + __ cmp(chars, scratch); + __ b(eq, &found_in_symbol_table); + __ bind(&next_probe[i]); + } + + // No matching 2 character string found by probing. + __ jmp(not_found); + + // Scratch register contains result when we fall through to here. + Register result = scratch; + __ bind(&found_in_symbol_table); + if (!result.is(r0)) { + __ mov(r0, result); + } +} + + +void StringStubBase::GenerateHashInit(MacroAssembler* masm, + Register hash, + Register character) { + // hash = character + (character << 10); + __ add(hash, character, Operand(character, LSL, 10)); + // hash ^= hash >> 6; + __ eor(hash, hash, Operand(hash, ASR, 6)); +} + + +void StringStubBase::GenerateHashAddCharacter(MacroAssembler* masm, + Register hash, + Register character) { + // hash += character; + __ add(hash, hash, Operand(character)); + // hash += hash << 10; + __ add(hash, hash, Operand(hash, LSL, 10)); + // hash ^= hash >> 6; + __ eor(hash, hash, Operand(hash, ASR, 6)); +} + + +void StringStubBase::GenerateHashGetHash(MacroAssembler* masm, + Register hash) { + // hash += hash << 3; + __ add(hash, hash, Operand(hash, LSL, 3)); + // hash ^= hash >> 11; + __ eor(hash, hash, Operand(hash, ASR, 11)); + // hash += hash << 15; + __ add(hash, hash, Operand(hash, LSL, 15), SetCC); + + // if (hash == 0) hash = 27; + __ mov(hash, Operand(27), LeaveCC, nz); +} + + void SubStringStub::Generate(MacroAssembler* masm) { Label runtime; @@ -7284,11 +7448,14 @@ void SubStringStub::Generate(MacroAssembler* masm) { __ sub(r2, r2, Operand(r3), SetCC); __ b(mi, &runtime); // Fail if from > to. - // Handle sub-strings of length 2 and less in the runtime system. + // Special handling of sub-strings of length 1 and 2. One character strings + // are handled in the runtime system (looked up in the single character + // cache). Two character strings are looked for in the symbol cache. __ cmp(r2, Operand(2)); - __ b(le, &runtime); + __ b(lt, &runtime); // r2: length + // r3: from index (untaged smi) // r6: from (smi) // r7: to (smi) @@ -7302,6 +7469,7 @@ void SubStringStub::Generate(MacroAssembler* masm) { // r1: instance type // r2: length + // r3: from index (untaged smi) // r5: string // r6: from (smi) // r7: to (smi) @@ -7328,6 +7496,7 @@ void SubStringStub::Generate(MacroAssembler* masm) { // r1: instance type. // r2: length + // r3: from index (untaged smi) // r5: string // r6: from (smi) // r7: to (smi) @@ -7337,6 +7506,7 @@ void SubStringStub::Generate(MacroAssembler* masm) { // r1: instance type. // r2: result string length. + // r3: from index (untaged smi) // r5: string. // r6: from offset (smi) // Check for flat ascii string. @@ -7345,6 +7515,35 @@ void SubStringStub::Generate(MacroAssembler* masm) { ASSERT_EQ(0, kTwoByteStringTag); __ b(eq, &non_ascii_flat); + Label result_longer_than_two; + __ cmp(r2, Operand(2)); + __ b(gt, &result_longer_than_two); + + // Sub string of length 2 requested. + // Get the two characters forming the sub string. + __ add(r5, r5, Operand(r3)); + __ ldrb(r3, FieldMemOperand(r5, SeqAsciiString::kHeaderSize)); + __ ldrb(r4, FieldMemOperand(r5, SeqAsciiString::kHeaderSize + 1)); + + // Try to lookup two character string in symbol table. + Label make_two_character_string; + GenerateTwoCharacterSymbolTableProbe(masm, r3, r4, r1, r5, r6, r7, r9, + &make_two_character_string); + __ IncrementCounter(&Counters::sub_string_native, 1, r3, r4); + __ add(sp, sp, Operand(3 * kPointerSize)); + __ Ret(); + + // r2: result string length. + // r3: two characters combined into halfword in little endian byte order. + __ bind(&make_two_character_string); + __ AllocateAsciiString(r0, r2, r4, r5, r9, &runtime); + __ strh(r3, FieldMemOperand(r0, SeqAsciiString::kHeaderSize)); + __ IncrementCounter(&Counters::sub_string_native, 1, r3, r4); + __ add(sp, sp, Operand(3 * kPointerSize)); + __ Ret(); + + __ bind(&result_longer_than_two); + // Allocate the result. __ AllocateAsciiString(r0, r2, r3, r4, r1, &runtime); @@ -7553,14 +7752,52 @@ void StringAddStub::Generate(MacroAssembler* masm) { // r4: first string instance type (if string_check_) // r5: second string instance type (if string_check_) // Look at the length of the result of adding the two strings. - Label string_add_flat_result; + Label string_add_flat_result, longer_than_two; // Adding two lengths can't overflow. ASSERT(String::kMaxLength * 2 > String::kMaxLength); __ add(r6, r2, Operand(r3)); // Use the runtime system when adding two one character strings, as it // contains optimizations for this specific case using the symbol table. __ cmp(r6, Operand(2)); - __ b(eq, &string_add_runtime); + __ b(ne, &longer_than_two); + + // Check that both strings are non-external ascii strings. + if (!string_check_) { + __ ldr(r4, FieldMemOperand(r0, HeapObject::kMapOffset)); + __ ldr(r5, FieldMemOperand(r1, HeapObject::kMapOffset)); + __ ldrb(r4, FieldMemOperand(r4, Map::kInstanceTypeOffset)); + __ ldrb(r5, FieldMemOperand(r5, Map::kInstanceTypeOffset)); + } + __ JumpIfBothInstanceTypesAreNotSequentialAscii(r4, r5, r6, r7, + &string_add_runtime); + + // Get the two characters forming the sub string. + __ ldrb(r2, FieldMemOperand(r0, SeqAsciiString::kHeaderSize)); + __ ldrb(r3, FieldMemOperand(r1, SeqAsciiString::kHeaderSize)); + + // Try to lookup two character string in symbol table. If it is not found + // just allocate a new one. + Label make_two_character_string; + GenerateTwoCharacterSymbolTableProbe(masm, r2, r3, r6, r7, r4, r5, r9, + &make_two_character_string); + __ IncrementCounter(&Counters::string_add_native, 1, r2, r3); + __ add(sp, sp, Operand(2 * kPointerSize)); + __ Ret(); + + __ bind(&make_two_character_string); + // Resulting string has length 2 and first chars of two strings + // are combined into single halfword in r2 register. + // So we can fill resulting string without two loops by a single + // halfword store instruction (which assumes that processor is + // in a little endian mode) + __ mov(r6, Operand(2)); + __ AllocateAsciiString(r0, r6, r4, r5, r9, &string_add_runtime); + __ strh(r2, FieldMemOperand(r0, SeqAsciiString::kHeaderSize)); + __ IncrementCounter(&Counters::string_add_native, 1, r2, r3); + __ add(sp, sp, Operand(2 * kPointerSize)); + __ Ret(); + + __ bind(&longer_than_two); // Check if resulting string will be flat. __ cmp(r6, Operand(String::kMinNonFlatLength)); __ b(lt, &string_add_flat_result); @@ -7639,6 +7876,7 @@ void StringAddStub::Generate(MacroAssembler* masm) { // Both strings are sequential ASCII strings. We also know that they are // short (since the sum of the lengths is less than kMinNonFlatLength). + // r6: length of resulting flat string __ AllocateAsciiString(r7, r6, r4, r5, r9, &string_add_runtime); // Locate first character of result. __ add(r6, r7, Operand(SeqAsciiString::kHeaderSize - kHeapObjectTag)); diff --git a/src/arm/codegen-arm.h b/src/arm/codegen-arm.h index 39f61b4c6..4ea7941c1 100644 --- a/src/arm/codegen-arm.h +++ b/src/arm/codegen-arm.h @@ -564,6 +564,36 @@ class StringStubBase: public CodeStub { Register scratch4, Register scratch5, int flags); + + + // Probe the symbol table for a two character string. If the string is + // not found by probing a jump to the label not_found is performed. This jump + // does not guarantee that the string is not in the symbol table. If the + // string is found the code falls through with the string in register r0. + // Contents of both c1 and c2 registers are modified. At the exit c1 is + // guaranteed to contain halfword with low and high bytes equal to + // initial contents of c1 and c2 respectively. + void GenerateTwoCharacterSymbolTableProbe(MacroAssembler* masm, + Register c1, + Register c2, + Register scratch1, + Register scratch2, + Register scratch3, + Register scratch4, + Register scratch5, + Label* not_found); + + // Generate string hash. + void GenerateHashInit(MacroAssembler* masm, + Register hash, + Register character); + + void GenerateHashAddCharacter(MacroAssembler* masm, + Register hash, + Register character); + + void GenerateHashGetHash(MacroAssembler* masm, + Register hash); }; diff --git a/src/arm/macro-assembler-arm.cc b/src/arm/macro-assembler-arm.cc index 045bf5021..36bebdfeb 100644 --- a/src/arm/macro-assembler-arm.cc +++ b/src/arm/macro-assembler-arm.cc @@ -1417,15 +1417,12 @@ void MacroAssembler::JumpIfNonSmisNotBothSequentialAsciiStrings( ldr(scratch2, FieldMemOperand(second, HeapObject::kMapOffset)); ldrb(scratch1, FieldMemOperand(scratch1, Map::kInstanceTypeOffset)); ldrb(scratch2, FieldMemOperand(scratch2, Map::kInstanceTypeOffset)); - int kFlatAsciiStringMask = - kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask; - int kFlatAsciiStringTag = ASCII_STRING_TYPE; - and_(scratch1, scratch1, Operand(kFlatAsciiStringMask)); - and_(scratch2, scratch2, Operand(kFlatAsciiStringMask)); - cmp(scratch1, Operand(kFlatAsciiStringTag)); - // Ignore second test if first test failed. - cmp(scratch2, Operand(kFlatAsciiStringTag), eq); - b(ne, failure); + + JumpIfBothInstanceTypesAreNotSequentialAscii(scratch1, + scratch2, + scratch1, + scratch2, + failure); } void MacroAssembler::JumpIfNotBothSequentialAsciiStrings(Register first, @@ -1446,6 +1443,36 @@ void MacroAssembler::JumpIfNotBothSequentialAsciiStrings(Register first, } +void MacroAssembler::JumpIfBothInstanceTypesAreNotSequentialAscii( + Register first, + Register second, + Register scratch1, + Register scratch2, + Label* failure) { + int kFlatAsciiStringMask = + kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask; + int kFlatAsciiStringTag = ASCII_STRING_TYPE; + and_(scratch1, first, Operand(kFlatAsciiStringMask)); + and_(scratch2, second, Operand(kFlatAsciiStringMask)); + cmp(scratch1, Operand(kFlatAsciiStringTag)); + // Ignore second test if first test failed. + cmp(scratch2, Operand(kFlatAsciiStringTag), eq); + b(ne, failure); +} + + +void MacroAssembler::JumpIfInstanceTypeIsNotSequentialAscii(Register type, + Register scratch, + Label* failure) { + int kFlatAsciiStringMask = + kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask; + int kFlatAsciiStringTag = ASCII_STRING_TYPE; + and_(scratch, type, Operand(kFlatAsciiStringMask)); + cmp(scratch, Operand(kFlatAsciiStringTag)); + b(ne, failure); +} + + #ifdef ENABLE_DEBUGGER_SUPPORT CodePatcher::CodePatcher(byte* address, int instructions) : address_(address), diff --git a/src/arm/macro-assembler-arm.h b/src/arm/macro-assembler-arm.h index 8e57929dd..5d9e51304 100644 --- a/src/arm/macro-assembler-arm.h +++ b/src/arm/macro-assembler-arm.h @@ -425,6 +425,22 @@ class MacroAssembler: public Assembler { Register scratch2, Label* not_flat_ascii_strings); + // Checks if both instance types are sequential ASCII strings and jumps to + // label if either is not. + void JumpIfBothInstanceTypesAreNotSequentialAscii( + Register first_object_instance_type, + Register second_object_instance_type, + Register scratch1, + Register scratch2, + Label* failure); + + // Check if instance type is sequential ASCII string and jump to label if + // it is not. + void JumpIfInstanceTypeIsNotSequentialAscii(Register type, + Register scratch, + Label* failure); + + private: void Jump(intptr_t target, RelocInfo::Mode rmode, Condition cond = al); void Call(intptr_t target, RelocInfo::Mode rmode, Condition cond = al); diff --git a/src/ia32/codegen-ia32.cc b/src/ia32/codegen-ia32.cc index dfb5cd779..dfa48bd07 100644 --- a/src/ia32/codegen-ia32.cc +++ b/src/ia32/codegen-ia32.cc @@ -11019,6 +11019,7 @@ void StringAddStub::Generate(MacroAssembler* masm) { Label make_two_character_string, make_flat_ascii_string; GenerateTwoCharacterSymbolTableProbe(masm, ebx, ecx, eax, edx, edi, &make_two_character_string); + __ IncrementCounter(&Counters::string_add_native, 1); __ ret(2 * kPointerSize); __ bind(&make_two_character_string); @@ -11299,10 +11300,7 @@ void StringStubBase::GenerateTwoCharacterSymbolTableProbe(MacroAssembler* masm, // Calculate capacity mask from the symbol table capacity. Register mask = scratch2; - static const int kCapacityOffset = - FixedArray::kHeaderSize + - SymbolTable::kCapacityIndex * kPointerSize; - __ mov(mask, FieldOperand(symbol_table, kCapacityOffset)); + __ mov(mask, FieldOperand(symbol_table, SymbolTable::kCapacityOffset)); __ SmiUntag(mask); __ sub(Operand(mask), Immediate(1)); @@ -11327,16 +11325,12 @@ void StringStubBase::GenerateTwoCharacterSymbolTableProbe(MacroAssembler* masm, // Load the entry from the symble table. Register candidate = scratch; // Scratch register contains candidate. - ASSERT_EQ(1, SymbolTableShape::kEntrySize); - static const int kFirstElementOffset = - FixedArray::kHeaderSize + - SymbolTable::kPrefixStartIndex * kPointerSize + - SymbolTableShape::kPrefixSize * kPointerSize; + ASSERT_EQ(1, SymbolTable::kEntrySize); __ mov(candidate, FieldOperand(symbol_table, scratch, times_pointer_size, - kFirstElementOffset)); + SymbolTable::kElementsStartOffset)); // If entry is undefined no string with this hash can be found. __ cmp(candidate, Factory::undefined_value()); @@ -11490,7 +11484,7 @@ void SubStringStub::Generate(MacroAssembler* masm) { Label make_two_character_string; GenerateTwoCharacterSymbolTableProbe(masm, ebx, ecx, eax, edx, edi, &make_two_character_string); - __ ret(2 * kPointerSize); + __ ret(3 * kPointerSize); __ bind(&make_two_character_string); // Setup registers for allocating the two character string. diff --git a/src/objects.h b/src/objects.h index e35fc11a4..e34182115 100644 --- a/src/objects.h +++ b/src/objects.h @@ -1969,6 +1969,8 @@ class HashTable: public FixedArray { static const int kEntrySize = Shape::kEntrySize; static const int kElementsStartOffset = kHeaderSize + kElementsStartIndex * kPointerSize; + static const int kCapacityOffset = + kHeaderSize + kCapacityIndex * kPointerSize; // Constant used for denoting a absent entry. static const int kNotFound = -1; diff --git a/src/x64/codegen-x64.cc b/src/x64/codegen-x64.cc index e9dfe2901..d2ddbd126 100644 --- a/src/x64/codegen-x64.cc +++ b/src/x64/codegen-x64.cc @@ -9000,16 +9000,11 @@ void StringAddStub::Generate(MacroAssembler* masm) { // rbx: length of first string // rcx: length of second string // rdx: second string - // r8: instance type of first string if string check was performed above - // r9: instance type of first string if string check was performed above - Label string_add_flat_result; + // r8: map of first string if string check was performed above + // r9: map of second string if string check was performed above + Label string_add_flat_result, longer_than_two; __ bind(&both_not_zero_length); - // Look at the length of the result of adding the two strings. - __ addl(rbx, rcx); - // Use the runtime system when adding two one character strings, as it - // contains optimizations for this specific case using the symbol table. - __ cmpl(rbx, Immediate(2)); - __ j(equal, &string_add_runtime); + // If arguments where known to be strings, maps are not loaded to r8 and r9 // by the code above. if (!string_check_) { @@ -9019,6 +9014,35 @@ void StringAddStub::Generate(MacroAssembler* masm) { // Get the instance types of the two strings as they will be needed soon. __ movzxbl(r8, FieldOperand(r8, Map::kInstanceTypeOffset)); __ movzxbl(r9, FieldOperand(r9, Map::kInstanceTypeOffset)); + + // Look at the length of the result of adding the two strings. + __ addl(rbx, rcx); + // Use the runtime system when adding two one character strings, as it + // contains optimizations for this specific case using the symbol table. + __ cmpl(rbx, Immediate(2)); + __ j(not_equal, &longer_than_two); + + // Check that both strings are non-external ascii strings. + __ JumpIfBothInstanceTypesAreNotSequentialAscii(r8, r9, rbx, rcx, + &string_add_runtime); + + // Get the two characters forming the sub string. + __ movzxbq(rbx, FieldOperand(rax, SeqAsciiString::kHeaderSize)); + __ movzxbq(rcx, FieldOperand(rdx, SeqAsciiString::kHeaderSize)); + + // Try to lookup two character string in symbol table. If it is not found + // just allocate a new one. + Label make_two_character_string, make_flat_ascii_string; + GenerateTwoCharacterSymbolTableProbe(masm, rbx, rcx, r14, r12, rdi, r15, + &make_two_character_string); + __ IncrementCounter(&Counters::string_add_native, 1); + __ ret(2 * kPointerSize); + + __ bind(&make_two_character_string); + __ Set(rbx, 2); + __ jmp(&make_flat_ascii_string); + + __ bind(&longer_than_two); // Check if resulting string will be flat. __ cmpl(rbx, Immediate(String::kMinNonFlatLength)); __ j(below, &string_add_flat_result); @@ -9085,6 +9109,8 @@ void StringAddStub::Generate(MacroAssembler* masm) { __ j(zero, &non_ascii_string_add_flat_result); __ testl(r9, Immediate(kAsciiStringTag)); __ j(zero, &string_add_runtime); + + __ bind(&make_flat_ascii_string); // Both strings are ascii strings. As they are short they are both flat. __ AllocateAsciiString(rcx, rbx, rdi, r14, r15, &string_add_runtime); // rcx: result string @@ -9235,6 +9261,179 @@ void StringStubBase::GenerateCopyCharactersREP(MacroAssembler* masm, __ bind(&done); } +void StringStubBase::GenerateTwoCharacterSymbolTableProbe(MacroAssembler* masm, + Register c1, + Register c2, + Register scratch1, + Register scratch2, + Register scratch3, + Register scratch4, + Label* not_found) { + // Register scratch3 is the general scratch register in this function. + Register scratch = scratch3; + + // Make sure that both characters are not digits as such strings has a + // different hash algorithm. Don't try to look for these in the symbol table. + Label not_array_index; + __ movq(scratch, c1); + __ subq(scratch, Immediate(static_cast('0'))); + __ cmpq(scratch, Immediate(static_cast('9' - '0'))); + __ j(above, ¬_array_index); + __ movq(scratch, c2); + __ subq(scratch, Immediate(static_cast('0'))); + __ cmpq(scratch, Immediate(static_cast('9' - '0'))); + __ j(below_equal, not_found); + + __ bind(¬_array_index); + // Calculate the two character string hash. + Register hash = scratch1; + GenerateHashInit(masm, hash, c1, scratch); + GenerateHashAddCharacter(masm, hash, c2, scratch); + GenerateHashGetHash(masm, hash, scratch); + + // Collect the two characters in a register. + Register chars = c1; + __ shl(c2, Immediate(kBitsPerByte)); + __ orl(chars, c2); + + // chars: two character string, char 1 in byte 0 and char 2 in byte 1. + // hash: hash of two character string. + + // Load the symbol table. + Register symbol_table = c2; + __ LoadRoot(symbol_table, Heap::kSymbolTableRootIndex); + + // Calculate capacity mask from the symbol table capacity. + Register mask = scratch2; + __ movq(mask, FieldOperand(symbol_table, SymbolTable::kCapacityOffset)); + __ SmiToInteger32(mask, mask); + __ decl(mask); + + Register undefined = scratch4; + __ LoadRoot(undefined, Heap::kUndefinedValueRootIndex); + + // Registers + // chars: two character string, char 1 in byte 0 and char 2 in byte 1. + // hash: hash of two character string (32-bit int) + // symbol_table: symbol table + // mask: capacity mask (32-bit int) + // undefined: undefined value + // scratch: - + + // Perform a number of probes in the symbol table. + static const int kProbes = 4; + Label found_in_symbol_table; + Label next_probe[kProbes]; + for (int i = 0; i < kProbes; i++) { + // Calculate entry in symbol table. + __ movl(scratch, hash); + if (i > 0) { + __ addl(scratch, Immediate(SymbolTable::GetProbeOffset(i))); + } + __ andl(scratch, mask); + + // Load the entry from the symble table. + Register candidate = scratch; // Scratch register contains candidate. + ASSERT_EQ(1, SymbolTable::kEntrySize); + __ movq(candidate, + FieldOperand(symbol_table, + scratch, + times_pointer_size, + SymbolTable::kElementsStartOffset)); + + // If entry is undefined no string with this hash can be found. + __ cmpq(candidate, undefined); + __ j(equal, not_found); + + // If length is not 2 the string is not a candidate. + __ cmpl(FieldOperand(candidate, String::kLengthOffset), Immediate(2)); + __ j(not_equal, &next_probe[i]); + + // We use kScratchRegister as a temporary register in assumption that + // JumpIfInstanceTypeIsNotSequentialAscii does not use it implicitly + Register temp = kScratchRegister; + + // Check that the candidate is a non-external ascii string. + __ movq(temp, FieldOperand(candidate, HeapObject::kMapOffset)); + __ movzxbl(temp, FieldOperand(temp, Map::kInstanceTypeOffset)); + __ JumpIfInstanceTypeIsNotSequentialAscii( + temp, temp, &next_probe[i]); + + // Check if the two characters match. + __ movl(temp, FieldOperand(candidate, SeqAsciiString::kHeaderSize)); + __ andl(temp, Immediate(0x0000ffff)); + __ cmpl(chars, temp); + __ j(equal, &found_in_symbol_table); + __ bind(&next_probe[i]); + } + + // No matching 2 character string found by probing. + __ jmp(not_found); + + // Scratch register contains result when we fall through to here. + Register result = scratch; + __ bind(&found_in_symbol_table); + if (!result.is(rax)) { + __ movq(rax, result); + } +} + + +void StringStubBase::GenerateHashInit(MacroAssembler* masm, + Register hash, + Register character, + Register scratch) { + // hash = character + (character << 10); + __ movl(hash, character); + __ shll(hash, Immediate(10)); + __ addl(hash, character); + // hash ^= hash >> 6; + __ movl(scratch, hash); + __ sarl(scratch, Immediate(6)); + __ xorl(hash, scratch); +} + + +void StringStubBase::GenerateHashAddCharacter(MacroAssembler* masm, + Register hash, + Register character, + Register scratch) { + // hash += character; + __ addl(hash, character); + // hash += hash << 10; + __ movl(scratch, hash); + __ shll(scratch, Immediate(10)); + __ addl(hash, scratch); + // hash ^= hash >> 6; + __ movl(scratch, hash); + __ sarl(scratch, Immediate(6)); + __ xorl(hash, scratch); +} + + +void StringStubBase::GenerateHashGetHash(MacroAssembler* masm, + Register hash, + Register scratch) { + // hash += hash << 3; + __ movl(scratch, hash); + __ shll(scratch, Immediate(3)); + __ addl(hash, scratch); + // hash ^= hash >> 11; + __ movl(scratch, hash); + __ sarl(scratch, Immediate(11)); + __ xorl(hash, scratch); + // hash += hash << 15; + __ movl(scratch, hash); + __ shll(scratch, Immediate(15)); + __ addl(hash, scratch); + + // if (hash == 0) hash = 27; + Label hash_not_zero; + __ testl(hash, hash); + __ j(not_zero, &hash_not_zero); + __ movl(hash, Immediate(27)); + __ bind(&hash_not_zero); +} void SubStringStub::Generate(MacroAssembler* masm) { Label runtime; @@ -9261,25 +9460,55 @@ void SubStringStub::Generate(MacroAssembler* masm) { // rax: string // rbx: instance type // Calculate length of sub string using the smi values. + Label result_longer_than_two; __ movq(rcx, Operand(rsp, kToOffset)); __ movq(rdx, Operand(rsp, kFromOffset)); __ JumpIfNotBothPositiveSmi(rcx, rdx, &runtime); __ SmiSub(rcx, rcx, rdx, NULL); // Overflow doesn't happen. __ j(negative, &runtime); - // Handle sub-strings of length 2 and less in the runtime system. + // Special handling of sub-strings of length 1 and 2. One character strings + // are handled in the runtime system (looked up in the single character + // cache). Two character strings are looked for in the symbol cache. __ SmiToInteger32(rcx, rcx); __ cmpl(rcx, Immediate(2)); - __ j(below_equal, &runtime); + __ j(greater, &result_longer_than_two); + __ j(less, &runtime); + + // Sub string of length 2 requested. + // rax: string + // rbx: instance type + // rcx: sub string length (value is 2) + // rdx: from index (smi) + __ JumpIfInstanceTypeIsNotSequentialAscii(rbx, rbx, &runtime); + + // Get the two characters forming the sub string. + __ SmiToInteger32(rdx, rdx); // From index is no longer smi. + __ movzxbq(rbx, FieldOperand(rax, rdx, times_1, SeqAsciiString::kHeaderSize)); + __ movzxbq(rcx, + FieldOperand(rax, rdx, times_1, SeqAsciiString::kHeaderSize + 1)); + + // Try to lookup two character string in symbol table. + Label make_two_character_string; + GenerateTwoCharacterSymbolTableProbe(masm, rbx, rcx, rax, rdx, rdi, r14, + &make_two_character_string); + __ ret(3 * kPointerSize); + + __ bind(&make_two_character_string); + // Setup registers for allocating the two character string. + __ movq(rax, Operand(rsp, kStringOffset)); + __ movq(rbx, FieldOperand(rax, HeapObject::kMapOffset)); + __ movzxbl(rbx, FieldOperand(rbx, Map::kInstanceTypeOffset)); + __ Set(rcx, 2); + + __ bind(&result_longer_than_two); // rax: string // rbx: instance type // rcx: result string length // Check for flat ascii string Label non_ascii_flat; - __ and_(rbx, Immediate(kStringRepresentationMask | kStringEncodingMask)); - __ cmpb(rbx, Immediate(kSeqStringTag | kAsciiStringTag)); - __ j(not_equal, &non_ascii_flat); + __ JumpIfInstanceTypeIsNotSequentialAscii(rbx, rbx, &non_ascii_flat); // Allocate the result. __ AllocateAsciiString(rax, rcx, rbx, rdx, rdi, &runtime); diff --git a/src/x64/codegen-x64.h b/src/x64/codegen-x64.h index 7c0883039..b634ee414 100644 --- a/src/x64/codegen-x64.h +++ b/src/x64/codegen-x64.h @@ -773,6 +773,33 @@ class StringStubBase: public CodeStub { Register src, // Must be rsi. Register count, // Must be rcx. bool ascii); + + + // Probe the symbol table for a two character string. If the string is + // not found by probing a jump to the label not_found is performed. This jump + // does not guarantee that the string is not in the symbol table. If the + // string is found the code falls through with the string in register rax. + void GenerateTwoCharacterSymbolTableProbe(MacroAssembler* masm, + Register c1, + Register c2, + Register scratch1, + Register scratch2, + Register scratch3, + Register scratch4, + Label* not_found); + + // Generate string hash. + void GenerateHashInit(MacroAssembler* masm, + Register hash, + Register character, + Register scratch); + void GenerateHashAddCharacter(MacroAssembler* masm, + Register hash, + Register character, + Register scratch); + void GenerateHashGetHash(MacroAssembler* masm, + Register hash, + Register scratch); }; diff --git a/src/x64/macro-assembler-x64.cc b/src/x64/macro-assembler-x64.cc index ac81517ed..dca27806e 100644 --- a/src/x64/macro-assembler-x64.cc +++ b/src/x64/macro-assembler-x64.cc @@ -1400,6 +1400,50 @@ void MacroAssembler::JumpIfNotBothSequentialAsciiStrings(Register first_object, } +void MacroAssembler::JumpIfInstanceTypeIsNotSequentialAscii( + Register instance_type, + Register scratch, + Label *failure) { + if (!scratch.is(instance_type)) { + movl(scratch, instance_type); + } + + const int kFlatAsciiStringMask = + kIsNotStringMask | kStringRepresentationMask | kStringEncodingMask; + + andl(scratch, Immediate(kFlatAsciiStringMask)); + cmpl(scratch, Immediate(kStringTag | kSeqStringTag | kAsciiStringTag)); + j(not_equal, failure); +} + + +void MacroAssembler::JumpIfBothInstanceTypesAreNotSequentialAscii( + Register first_object_instance_type, + Register second_object_instance_type, + Register scratch1, + Register scratch2, + Label* on_fail) { + // Load instance type for both strings. + movq(scratch1, first_object_instance_type); + movq(scratch2, second_object_instance_type); + + // Check that both are flat ascii strings. + ASSERT(kNotStringTag != 0); + const int kFlatAsciiStringMask = + kIsNotStringMask | kStringRepresentationMask | kStringEncodingMask; + const int kFlatAsciiStringTag = ASCII_STRING_TYPE; + + andl(scratch1, Immediate(kFlatAsciiStringMask)); + andl(scratch2, Immediate(kFlatAsciiStringMask)); + // Interleave the bits to check both scratch1 and scratch2 in one test. + ASSERT_EQ(0, kFlatAsciiStringMask & (kFlatAsciiStringMask << 3)); + lea(scratch1, Operand(scratch1, scratch2, times_8, 0)); + cmpl(scratch1, + Immediate(kFlatAsciiStringTag + (kFlatAsciiStringTag << 3))); + j(not_equal, on_fail); +} + + void MacroAssembler::Move(Register dst, Handle source) { ASSERT(!source->IsFailure()); if (source->IsSmi()) { diff --git a/src/x64/macro-assembler-x64.h b/src/x64/macro-assembler-x64.h index 912daf90b..bbb6e2183 100644 --- a/src/x64/macro-assembler-x64.h +++ b/src/x64/macro-assembler-x64.h @@ -426,6 +426,20 @@ class MacroAssembler: public Assembler { Register scratch2, Label* on_not_both_flat_ascii); + // Check whether the instance type represents a flat ascii string. Jump to the + // label if not. If the instance type can be scratched specify same register + // for both instance type and scratch. + void JumpIfInstanceTypeIsNotSequentialAscii(Register instance_type, + Register scratch, + Label *on_not_flat_ascii_string); + + void JumpIfBothInstanceTypesAreNotSequentialAscii( + Register first_object_instance_type, + Register second_object_instance_type, + Register scratch1, + Register scratch2, + Label* on_fail); + // --------------------------------------------------------------------------- // Macro instructions. -- 2.34.1