From 9a9211e22d1f74b508995b3dc8c722e0fb4a08e2 Mon Sep 17 00:00:00 2001 From: "vegorov@chromium.org" Date: Thu, 5 May 2011 12:30:57 +0000 Subject: [PATCH] Unroll more StringDictionary lookup probes both for positive and negative dictionary lookups. Review URL: http://codereview.chromium.org/6932010 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@7795 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/code-stubs-arm.cc | 230 ++++++++++++++++++++++++++++++++++++++++++++ src/arm/code-stubs-arm.h | 55 +++++++++++ src/arm/ic-arm.cc | 87 +++-------------- src/arm/stub-cache-arm.cc | 72 ++------------ src/code-stubs.h | 3 +- src/ia32/code-stubs-ia32.cc | 209 ++++++++++++++++++++++++++++++++++++++++ src/ia32/code-stubs-ia32.h | 68 +++++++++++++ src/ia32/ic-ia32.cc | 82 +++------------- src/ia32/stub-cache-ia32.cc | 64 ++---------- src/x64/code-stubs-x64.cc | 199 +++++++++++++++++++++++++++++++++++++- src/x64/code-stubs-x64.h | 67 +++++++++++++ src/x64/ic-x64.cc | 80 +++------------ src/x64/stub-cache-x64.cc | 64 ++---------- 13 files changed, 894 insertions(+), 386 deletions(-) diff --git a/src/arm/code-stubs-arm.cc b/src/arm/code-stubs-arm.cc index 4d1b1b7..caeb6c1 100644 --- a/src/arm/code-stubs-arm.cc +++ b/src/arm/code-stubs-arm.cc @@ -6104,6 +6104,236 @@ void DirectCEntryStub::GenerateCall(MacroAssembler* masm, } +void StringDictionaryLookupStub::GenerateNegativeLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register receiver, + Register properties, + String* name, + Register scratch0) { + // If names of slots in range from 1 to kProbes - 1 for the hash value are + // not equal to the name and kProbes-th slot is not used (its name is the + // undefined value), it guarantees the hash table doesn't contain the + // property. It's true even if some slots represent deleted properties + // (their names are the null value). + for (int i = 0; i < kInlinedProbes; i++) { + // scratch0 points to properties hash. + // Compute the masked index: (hash + i + i * i) & mask. + Register index = scratch0; + // Capacity is smi 2^n. + __ ldr(index, FieldMemOperand(properties, kCapacityOffset)); + __ sub(index, index, Operand(1)); + __ and_(index, index, Operand( + Smi::FromInt(name->Hash() + StringDictionary::GetProbeOffset(i)))); + + // Scale the index by multiplying by the entry size. + ASSERT(StringDictionary::kEntrySize == 3); + __ add(index, index, Operand(index, LSL, 1)); // index *= 3. + + Register entity_name = scratch0; + // Having undefined at this place means the name is not contained. + ASSERT_EQ(kSmiTagSize, 1); + Register tmp = properties; + __ add(tmp, properties, Operand(index, LSL, 1)); + __ ldr(entity_name, FieldMemOperand(tmp, kElementsStartOffset)); + + ASSERT(!tmp.is(entity_name)); + __ LoadRoot(tmp, Heap::kUndefinedValueRootIndex); + __ cmp(entity_name, tmp); + __ b(eq, done); + + if (i != kInlinedProbes - 1) { + // Stop if found the property. + __ cmp(entity_name, Operand(Handle(name))); + __ b(eq, miss); + + // Check if the entry name is not a symbol. + __ ldr(entity_name, FieldMemOperand(entity_name, HeapObject::kMapOffset)); + __ ldrb(entity_name, + FieldMemOperand(entity_name, Map::kInstanceTypeOffset)); + __ tst(entity_name, Operand(kIsSymbolMask)); + __ b(eq, miss); + + // Restore the properties. + __ ldr(properties, + FieldMemOperand(receiver, JSObject::kPropertiesOffset)); + } + } + + const int spill_mask = + (lr.bit() | r6.bit() | r5.bit() | r4.bit() | r3.bit() | + r2.bit() | r1.bit() | r0.bit()); + + __ stm(db_w, sp, spill_mask); + __ ldr(r0, FieldMemOperand(receiver, JSObject::kPropertiesOffset)); + __ mov(r1, Operand(Handle(name))); + StringDictionaryLookupStub stub(NEGATIVE_LOOKUP); + __ CallStub(&stub); + __ tst(r0, Operand(r0)); + __ ldm(ia_w, sp, spill_mask); + + __ b(eq, done); + __ b(ne, miss); +} + + +// Probe the string dictionary in the |elements| register. Jump to the +// |done| label if a property with the given name is found. Jump to +// the |miss| label otherwise. +// If lookup was successful |scratch2| will be equal to elements + 4 * index. +void StringDictionaryLookupStub::GeneratePositiveLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register elements, + Register name, + Register scratch1, + Register scratch2) { + // Assert that name contains a string. + if (FLAG_debug_code) __ AbortIfNotString(name); + + // Compute the capacity mask. + __ ldr(scratch1, FieldMemOperand(elements, kCapacityOffset)); + __ mov(scratch1, Operand(scratch1, ASR, kSmiTagSize)); // convert smi to int + __ sub(scratch1, scratch1, Operand(1)); + + // Generate an unrolled loop that performs a few probes before + // giving up. Measurements done on Gmail indicate that 2 probes + // cover ~93% of loads from dictionaries. + for (int i = 0; i < kInlinedProbes; i++) { + // Compute the masked index: (hash + i + i * i) & mask. + __ ldr(scratch2, FieldMemOperand(name, String::kHashFieldOffset)); + if (i > 0) { + // Add the probe offset (i + i * i) left shifted to avoid right shifting + // the hash in a separate instruction. The value hash + i + i * i is right + // shifted in the following and instruction. + ASSERT(StringDictionary::GetProbeOffset(i) < + 1 << (32 - String::kHashFieldOffset)); + __ add(scratch2, scratch2, Operand( + StringDictionary::GetProbeOffset(i) << String::kHashShift)); + } + __ and_(scratch2, scratch1, Operand(scratch2, LSR, String::kHashShift)); + + // Scale the index by multiplying by the element size. + ASSERT(StringDictionary::kEntrySize == 3); + // scratch2 = scratch2 * 3. + __ add(scratch2, scratch2, Operand(scratch2, LSL, 1)); + + // Check if the key is identical to the name. + __ add(scratch2, elements, Operand(scratch2, LSL, 2)); + __ ldr(ip, FieldMemOperand(scratch2, kElementsStartOffset)); + __ cmp(name, Operand(ip)); + __ b(eq, done); + } + + const int spill_mask = + (lr.bit() | r6.bit() | r5.bit() | r4.bit() | + r3.bit() | r2.bit() | r1.bit() | r0.bit()) & + ~(scratch1.bit() | scratch2.bit()); + + __ stm(db_w, sp, spill_mask); + __ Move(r0, elements); + __ Move(r1, name); + StringDictionaryLookupStub stub(POSITIVE_LOOKUP); + __ CallStub(&stub); + __ tst(r0, Operand(r0)); + __ mov(scratch2, Operand(r2)); + __ ldm(ia_w, sp, spill_mask); + + __ b(ne, done); + __ b(eq, miss); +} + + +void StringDictionaryLookupStub::Generate(MacroAssembler* masm) { + // Registers: + // result: StringDictionary to probe + // r1: key + // : StringDictionary to probe. + // index_: will hold an index of entry if lookup is successful. + // might alias with result_. + // Returns: + // result_ is zero if lookup failed, non zero otherwise. + + Register result = r0; + Register dictionary = r0; + Register key = r1; + Register index = r2; + Register mask = r3; + Register hash = r4; + Register undefined = r5; + Register entry_key = r6; + + Label in_dictionary, maybe_in_dictionary, not_in_dictionary; + + __ ldr(mask, FieldMemOperand(dictionary, kCapacityOffset)); + __ mov(mask, Operand(mask, ASR, kSmiTagSize)); + __ sub(mask, mask, Operand(1)); + + __ ldr(hash, FieldMemOperand(key, String::kHashFieldOffset)); + + __ LoadRoot(undefined, Heap::kUndefinedValueRootIndex); + + for (int i = kInlinedProbes; i < kTotalProbes; i++) { + // Compute the masked index: (hash + i + i * i) & mask. + // Capacity is smi 2^n. + if (i > 0) { + // Add the probe offset (i + i * i) left shifted to avoid right shifting + // the hash in a separate instruction. The value hash + i + i * i is right + // shifted in the following and instruction. + ASSERT(StringDictionary::GetProbeOffset(i) < + 1 << (32 - String::kHashFieldOffset)); + __ add(index, hash, Operand( + StringDictionary::GetProbeOffset(i) << String::kHashShift)); + } else { + __ mov(index, Operand(hash)); + } + __ and_(index, mask, Operand(index, LSR, String::kHashShift)); + + // Scale the index by multiplying by the entry size. + ASSERT(StringDictionary::kEntrySize == 3); + __ add(index, index, Operand(index, LSL, 1)); // index *= 3. + + ASSERT_EQ(kSmiTagSize, 1); + __ add(index, dictionary, Operand(index, LSL, 2)); + __ ldr(entry_key, FieldMemOperand(index, kElementsStartOffset)); + + // Having undefined at this place means the name is not contained. + __ cmp(entry_key, Operand(undefined)); + __ b(eq, ¬_in_dictionary); + + // Stop if found the property. + __ cmp(entry_key, Operand(key)); + __ b(eq, &in_dictionary); + + if (i != kTotalProbes - 1 && mode_ == NEGATIVE_LOOKUP) { + // Check if the entry name is not a symbol. + __ ldr(entry_key, FieldMemOperand(entry_key, HeapObject::kMapOffset)); + __ ldrb(entry_key, + FieldMemOperand(entry_key, Map::kInstanceTypeOffset)); + __ tst(entry_key, Operand(kIsSymbolMask)); + __ b(eq, &maybe_in_dictionary); + } + } + + __ bind(&maybe_in_dictionary); + // If we are doing negative lookup then probing failure should be + // treated as a lookup success. For positive lookup probing failure + // should be treated as lookup failure. + if (mode_ == POSITIVE_LOOKUP) { + __ mov(result, Operand(0)); + __ Ret(); + } + + __ bind(&in_dictionary); + __ mov(result, Operand(1)); + __ Ret(); + + __ bind(¬_in_dictionary); + __ mov(result, Operand(0)); + __ Ret(); +} + + #undef __ } } // namespace v8::internal diff --git a/src/arm/code-stubs-arm.h b/src/arm/code-stubs-arm.h index 4d4d30d..a167c03 100644 --- a/src/arm/code-stubs-arm.h +++ b/src/arm/code-stubs-arm.h @@ -605,6 +605,61 @@ class FloatingPointHelper : public AllStatic { }; +class StringDictionaryLookupStub: public CodeStub { + public: + enum LookupMode { POSITIVE_LOOKUP, NEGATIVE_LOOKUP }; + + explicit StringDictionaryLookupStub(LookupMode mode) : mode_(mode) { } + + void Generate(MacroAssembler* masm); + + static void GenerateNegativeLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register receiver, + Register properties, + String* name, + Register scratch0) ; + + static void GeneratePositiveLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register elements, + Register name, + Register r0, + Register r1); + + private: + static const int kInlinedProbes = 4; + static const int kTotalProbes = 20; + + static const int kCapacityOffset = + StringDictionary::kHeaderSize + + StringDictionary::kCapacityIndex * kPointerSize; + + static const int kElementsStartOffset = + StringDictionary::kHeaderSize + + StringDictionary::kElementsStartIndex * kPointerSize; + + +#ifdef DEBUG + void Print() { + PrintF("StringDictionaryLookupStub\n"); + } +#endif + + Major MajorKey() { return StringDictionaryNegativeLookup; } + + int MinorKey() { + return LookupModeBits::encode(mode_); + } + + class LookupModeBits: public BitField {}; + + LookupMode mode_; +}; + + } } // namespace v8::internal #endif // V8_ARM_CODE_STUBS_ARM_H_ diff --git a/src/arm/ic-arm.cc b/src/arm/ic-arm.cc index db04f33..731c471 100644 --- a/src/arm/ic-arm.cc +++ b/src/arm/ic-arm.cc @@ -105,65 +105,6 @@ static void GenerateStringDictionaryReceiverCheck(MacroAssembler* masm, } -// Probe the string dictionary in the |elements| register. Jump to the -// |done| label if a property with the given name is found. Jump to -// the |miss| label otherwise. -static void GenerateStringDictionaryProbes(MacroAssembler* masm, - Label* miss, - Label* done, - Register elements, - Register name, - Register scratch1, - Register scratch2) { - // Assert that name contains a string. - if (FLAG_debug_code) __ AbortIfNotString(name); - - // Compute the capacity mask. - const int kCapacityOffset = StringDictionary::kHeaderSize + - StringDictionary::kCapacityIndex * kPointerSize; - __ ldr(scratch1, FieldMemOperand(elements, kCapacityOffset)); - __ mov(scratch1, Operand(scratch1, ASR, kSmiTagSize)); // convert smi to int - __ sub(scratch1, scratch1, Operand(1)); - - const int kElementsStartOffset = StringDictionary::kHeaderSize + - StringDictionary::kElementsStartIndex * kPointerSize; - - // Generate an unrolled loop that performs a few probes before - // giving up. Measurements done on Gmail indicate that 2 probes - // cover ~93% of loads from dictionaries. - static const int kProbes = 4; - for (int i = 0; i < kProbes; i++) { - // Compute the masked index: (hash + i + i * i) & mask. - __ ldr(scratch2, FieldMemOperand(name, String::kHashFieldOffset)); - if (i > 0) { - // Add the probe offset (i + i * i) left shifted to avoid right shifting - // the hash in a separate instruction. The value hash + i + i * i is right - // shifted in the following and instruction. - ASSERT(StringDictionary::GetProbeOffset(i) < - 1 << (32 - String::kHashFieldOffset)); - __ add(scratch2, scratch2, Operand( - StringDictionary::GetProbeOffset(i) << String::kHashShift)); - } - __ and_(scratch2, scratch1, Operand(scratch2, LSR, String::kHashShift)); - - // Scale the index by multiplying by the element size. - ASSERT(StringDictionary::kEntrySize == 3); - // scratch2 = scratch2 * 3. - __ add(scratch2, scratch2, Operand(scratch2, LSL, 1)); - - // Check if the key is identical to the name. - __ add(scratch2, elements, Operand(scratch2, LSL, 2)); - __ ldr(ip, FieldMemOperand(scratch2, kElementsStartOffset)); - __ cmp(name, Operand(ip)); - if (i != kProbes - 1) { - __ b(eq, done); - } else { - __ b(ne, miss); - } - } -} - - // Helper function used from LoadIC/CallIC GenerateNormal. // // elements: Property dictionary. It is not clobbered if a jump to the miss @@ -191,13 +132,13 @@ static void GenerateDictionaryLoad(MacroAssembler* masm, Label done; // Probe the dictionary. - GenerateStringDictionaryProbes(masm, - miss, - &done, - elements, - name, - scratch1, - scratch2); + StringDictionaryLookupStub::GeneratePositiveLookup(masm, + miss, + &done, + elements, + name, + scratch1, + scratch2); // If probing finds an entry check that the value is a normal // property. @@ -240,13 +181,13 @@ static void GenerateDictionaryStore(MacroAssembler* masm, Label done; // Probe the dictionary. - GenerateStringDictionaryProbes(masm, - miss, - &done, - elements, - name, - scratch1, - scratch2); + StringDictionaryLookupStub::GeneratePositiveLookup(masm, + miss, + &done, + elements, + name, + scratch1, + scratch2); // If probing finds an entry in the dictionary check that the value // is a normal property that is not read only. diff --git a/src/arm/stub-cache-arm.cc b/src/arm/stub-cache-arm.cc index 97097c8..6fd5063 100644 --- a/src/arm/stub-cache-arm.cc +++ b/src/arm/stub-cache-arm.cc @@ -136,69 +136,15 @@ static void GenerateDictionaryNegativeLookup(MacroAssembler* masm, // Restore the temporarily used register. __ ldr(properties, FieldMemOperand(receiver, JSObject::kPropertiesOffset)); - // Compute the capacity mask. - const int kCapacityOffset = - StringDictionary::kHeaderSize + - StringDictionary::kCapacityIndex * kPointerSize; - - // Generate an unrolled loop that performs a few probes before - // giving up. - static const int kProbes = 4; - const int kElementsStartOffset = - StringDictionary::kHeaderSize + - StringDictionary::kElementsStartIndex * kPointerSize; - - // If names of slots in range from 1 to kProbes - 1 for the hash value are - // not equal to the name and kProbes-th slot is not used (its name is the - // undefined value), it guarantees the hash table doesn't contain the - // property. It's true even if some slots represent deleted properties - // (their names are the null value). - for (int i = 0; i < kProbes; i++) { - // scratch0 points to properties hash. - // Compute the masked index: (hash + i + i * i) & mask. - Register index = scratch1; - // Capacity is smi 2^n. - __ ldr(index, FieldMemOperand(properties, kCapacityOffset)); - __ sub(index, index, Operand(1)); - __ and_(index, index, Operand( - Smi::FromInt(name->Hash() + StringDictionary::GetProbeOffset(i)))); - - // Scale the index by multiplying by the entry size. - ASSERT(StringDictionary::kEntrySize == 3); - __ add(index, index, Operand(index, LSL, 1)); // index *= 3. - - Register entity_name = scratch1; - // Having undefined at this place means the name is not contained. - ASSERT_EQ(kSmiTagSize, 1); - Register tmp = properties; - __ add(tmp, properties, Operand(index, LSL, 1)); - __ ldr(entity_name, FieldMemOperand(tmp, kElementsStartOffset)); - - ASSERT(!tmp.is(entity_name)); - __ LoadRoot(tmp, Heap::kUndefinedValueRootIndex); - __ cmp(entity_name, tmp); - if (i != kProbes - 1) { - __ b(eq, &done); - - // Stop if found the property. - __ cmp(entity_name, Operand(Handle(name))); - __ b(eq, miss_label); - - // Check if the entry name is not a symbol. - __ ldr(entity_name, FieldMemOperand(entity_name, HeapObject::kMapOffset)); - __ ldrb(entity_name, - FieldMemOperand(entity_name, Map::kInstanceTypeOffset)); - __ tst(entity_name, Operand(kIsSymbolMask)); - __ b(eq, miss_label); - - // Restore the properties. - __ ldr(properties, - FieldMemOperand(receiver, JSObject::kPropertiesOffset)); - } else { - // Give up probing if still not found the undefined value. - __ b(ne, miss_label); - } - } + + StringDictionaryLookupStub::GenerateNegativeLookup(masm, + miss_label, + &done, + receiver, + properties, + name, + scratch1); + __ bind(&done); __ DecrementCounter(counters->negative_lookups_miss(), 1, scratch0, scratch1); } diff --git a/src/code-stubs.h b/src/code-stubs.h index 42a8d2e..a3de29a 100644 --- a/src/code-stubs.h +++ b/src/code-stubs.h @@ -65,7 +65,8 @@ namespace internal { V(NumberToString) \ V(CEntry) \ V(JSEntry) \ - V(DebuggerStatement) + V(DebuggerStatement) \ + V(StringDictionaryNegativeLookup) // List of code stubs only used on ARM platforms. #ifdef V8_TARGET_ARCH_ARM diff --git a/src/ia32/code-stubs-ia32.cc b/src/ia32/code-stubs-ia32.cc index f422e8f..0392e1d 100644 --- a/src/ia32/code-stubs-ia32.cc +++ b/src/ia32/code-stubs-ia32.cc @@ -5998,6 +5998,215 @@ void ICCompareStub::GenerateMiss(MacroAssembler* masm) { } +// Helper function used to check that the dictionary doesn't contain +// the property. This function may return false negatives, so miss_label +// must always call a backup property check that is complete. +// This function is safe to call if the receiver has fast properties. +// Name must be a symbol and receiver must be a heap object. +void StringDictionaryLookupStub::GenerateNegativeLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register properties, + String* name, + Register r0) { + ASSERT(name->IsSymbol()); + + // If names of slots in range from 1 to kProbes - 1 for the hash value are + // not equal to the name and kProbes-th slot is not used (its name is the + // undefined value), it guarantees the hash table doesn't contain the + // property. It's true even if some slots represent deleted properties + // (their names are the null value). + for (int i = 0; i < kInlinedProbes; i++) { + // Compute the masked index: (hash + i + i * i) & mask. + Register index = r0; + // Capacity is smi 2^n. + __ mov(index, FieldOperand(properties, kCapacityOffset)); + __ dec(index); + __ and_(Operand(index), + Immediate(Smi::FromInt(name->Hash() + + StringDictionary::GetProbeOffset(i)))); + + // Scale the index by multiplying by the entry size. + ASSERT(StringDictionary::kEntrySize == 3); + __ lea(index, Operand(index, index, times_2, 0)); // index *= 3. + Register entity_name = r0; + // Having undefined at this place means the name is not contained. + ASSERT_EQ(kSmiTagSize, 1); + __ mov(entity_name, Operand(properties, index, times_half_pointer_size, + kElementsStartOffset - kHeapObjectTag)); + __ cmp(entity_name, masm->isolate()->factory()->undefined_value()); + __ j(equal, done, taken); + + // Stop if found the property. + __ cmp(entity_name, Handle(name)); + __ j(equal, miss, not_taken); + + // Check if the entry name is not a symbol. + __ mov(entity_name, FieldOperand(entity_name, HeapObject::kMapOffset)); + __ test_b(FieldOperand(entity_name, Map::kInstanceTypeOffset), + kIsSymbolMask); + __ j(zero, miss, not_taken); + } + + StringDictionaryLookupStub stub(properties, + r0, + r0, + StringDictionaryLookupStub::NEGATIVE_LOOKUP); + __ push(Immediate(Handle(name))); + __ push(Immediate(name->Hash())); + __ CallStub(&stub); + __ test(r0, Operand(r0)); + __ j(not_zero, miss); + __ jmp(done); +} + + +// Probe the string dictionary in the |elements| register. Jump to the +// |done| label if a property with the given name is found leaving the +// index into the dictionary in |r0|. Jump to the |miss| label +// otherwise. +void StringDictionaryLookupStub::GeneratePositiveLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register elements, + Register name, + Register r0, + Register r1) { + // Assert that name contains a string. + if (FLAG_debug_code) __ AbortIfNotString(name); + + __ mov(r1, FieldOperand(elements, kCapacityOffset)); + __ shr(r1, kSmiTagSize); // convert smi to int + __ dec(r1); + + // Generate an unrolled loop that performs a few probes before + // giving up. Measurements done on Gmail indicate that 2 probes + // cover ~93% of loads from dictionaries. + for (int i = 0; i < kInlinedProbes; i++) { + // Compute the masked index: (hash + i + i * i) & mask. + __ mov(r0, FieldOperand(name, String::kHashFieldOffset)); + __ shr(r0, String::kHashShift); + if (i > 0) { + __ add(Operand(r0), Immediate(StringDictionary::GetProbeOffset(i))); + } + __ and_(r0, Operand(r1)); + + // Scale the index by multiplying by the entry size. + ASSERT(StringDictionary::kEntrySize == 3); + __ lea(r0, Operand(r0, r0, times_2, 0)); // r0 = r0 * 3 + + // Check if the key is identical to the name. + __ cmp(name, Operand(elements, + r0, + times_4, + kElementsStartOffset - kHeapObjectTag)); + __ j(equal, done, taken); + } + + StringDictionaryLookupStub stub(elements, + r1, + r0, + POSITIVE_LOOKUP); + __ push(name); + __ mov(r0, FieldOperand(name, String::kHashFieldOffset)); + __ shr(r0, String::kHashShift); + __ push(r0); + __ CallStub(&stub); + + __ test(r1, Operand(r1)); + __ j(zero, miss); + __ jmp(done); +} + + +void StringDictionaryLookupStub::Generate(MacroAssembler* masm) { + // Stack frame on entry: + // esp[0 * kPointerSize]: return address. + // esp[1 * kPointerSize]: key's hash. + // esp[2 * kPointerSize]: key. + // Registers: + // dictionary_: StringDictionary to probe. + // result_: used as scratch. + // index_: will hold an index of entry if lookup is successful. + // might alias with result_. + // Returns: + // result_ is zero if lookup failed, non zero otherwise. + + Label in_dictionary, maybe_in_dictionary, not_in_dictionary; + + Register scratch = result_; + + __ mov(scratch, FieldOperand(dictionary_, kCapacityOffset)); + __ dec(scratch); + __ SmiUntag(scratch); + __ push(scratch); + + // If names of slots in range from 1 to kProbes - 1 for the hash value are + // not equal to the name and kProbes-th slot is not used (its name is the + // undefined value), it guarantees the hash table doesn't contain the + // property. It's true even if some slots represent deleted properties + // (their names are the null value). + for (int i = kInlinedProbes; i < kTotalProbes; i++) { + // Compute the masked index: (hash + i + i * i) & mask. + __ mov(scratch, Operand(esp, 2 * kPointerSize)); + if (i > 0) { + __ add(Operand(scratch), + Immediate(StringDictionary::GetProbeOffset(i))); + } + __ and_(scratch, Operand(esp, 0)); + + // Scale the index by multiplying by the entry size. + ASSERT(StringDictionary::kEntrySize == 3); + __ lea(index_, Operand(scratch, scratch, times_2, 0)); // index *= 3. + + // Having undefined at this place means the name is not contained. + ASSERT_EQ(kSmiTagSize, 1); + __ mov(scratch, Operand(dictionary_, + index_, + times_pointer_size, + kElementsStartOffset - kHeapObjectTag)); + __ cmp(scratch, masm->isolate()->factory()->undefined_value()); + __ j(equal, ¬_in_dictionary); + + // Stop if found the property. + __ cmp(scratch, Operand(esp, 3 * kPointerSize)); + __ j(equal, &in_dictionary); + + if (i != kTotalProbes - 1 && mode_ == NEGATIVE_LOOKUP) { + // If we hit a non symbol key during negative lookup + // we have to bailout as this key might be equal to the + // key we are looking for. + + // Check if the entry name is not a symbol. + __ mov(scratch, FieldOperand(scratch, HeapObject::kMapOffset)); + __ test_b(FieldOperand(scratch, Map::kInstanceTypeOffset), + kIsSymbolMask); + __ j(zero, &maybe_in_dictionary); + } + } + + __ bind(&maybe_in_dictionary); + // If we are doing negative lookup then probing failure should be + // treated as a lookup success. For positive lookup probing failure + // should be treated as lookup failure. + if (mode_ == POSITIVE_LOOKUP) { + __ mov(result_, Immediate(0)); + __ Drop(1); + __ ret(2 * kPointerSize); + } + + __ bind(&in_dictionary); + __ mov(result_, Immediate(1)); + __ Drop(1); + __ ret(2 * kPointerSize); + + __ bind(¬_in_dictionary); + __ mov(result_, Immediate(0)); + __ Drop(1); + __ ret(2 * kPointerSize); +} + + #undef __ } } // namespace v8::internal diff --git a/src/ia32/code-stubs-ia32.h b/src/ia32/code-stubs-ia32.h index a17ebda..1132cb4 100644 --- a/src/ia32/code-stubs-ia32.h +++ b/src/ia32/code-stubs-ia32.h @@ -430,6 +430,74 @@ class NumberToStringStub: public CodeStub { #endif }; + +class StringDictionaryLookupStub: public CodeStub { + public: + enum LookupMode { POSITIVE_LOOKUP, NEGATIVE_LOOKUP }; + + StringDictionaryLookupStub(Register dictionary, + Register result, + Register index, + LookupMode mode) + : dictionary_(dictionary), result_(result), index_(index), mode_(mode) { } + + void Generate(MacroAssembler* masm); + + static void GenerateNegativeLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register properties, + String* name, + Register r0); + + static void GeneratePositiveLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register elements, + Register name, + Register r0, + Register r1); + + private: + static const int kInlinedProbes = 4; + static const int kTotalProbes = 20; + + static const int kCapacityOffset = + StringDictionary::kHeaderSize + + StringDictionary::kCapacityIndex * kPointerSize; + + static const int kElementsStartOffset = + StringDictionary::kHeaderSize + + StringDictionary::kElementsStartIndex * kPointerSize; + + +#ifdef DEBUG + void Print() { + PrintF("StringDictionaryLookupStub\n"); + } +#endif + + Major MajorKey() { return StringDictionaryNegativeLookup; } + + int MinorKey() { + return DictionaryBits::encode(dictionary_.code()) | + ResultBits::encode(result_.code()) | + IndexBits::encode(index_.code()) | + LookupModeBits::encode(mode_); + } + + class DictionaryBits: public BitField {}; + class ResultBits: public BitField {}; + class IndexBits: public BitField {}; + class LookupModeBits: public BitField {}; + + Register dictionary_; + Register result_; + Register index_; + LookupMode mode_; +}; + + } } // namespace v8::internal #endif // V8_IA32_CODE_STUBS_IA32_H_ diff --git a/src/ia32/ic-ia32.cc b/src/ia32/ic-ia32.cc index 4106f01..1e77a78 100644 --- a/src/ia32/ic-ia32.cc +++ b/src/ia32/ic-ia32.cc @@ -97,60 +97,6 @@ static void GenerateStringDictionaryReceiverCheck(MacroAssembler* masm, } -// Probe the string dictionary in the |elements| register. Jump to the -// |done| label if a property with the given name is found leaving the -// index into the dictionary in |r0|. Jump to the |miss| label -// otherwise. -static void GenerateStringDictionaryProbes(MacroAssembler* masm, - Label* miss, - Label* done, - Register elements, - Register name, - Register r0, - Register r1) { - // Assert that name contains a string. - if (FLAG_debug_code) __ AbortIfNotString(name); - - // Compute the capacity mask. - const int kCapacityOffset = - StringDictionary::kHeaderSize + - StringDictionary::kCapacityIndex * kPointerSize; - __ mov(r1, FieldOperand(elements, kCapacityOffset)); - __ shr(r1, kSmiTagSize); // convert smi to int - __ dec(r1); - - // Generate an unrolled loop that performs a few probes before - // giving up. Measurements done on Gmail indicate that 2 probes - // cover ~93% of loads from dictionaries. - static const int kProbes = 4; - const int kElementsStartOffset = - StringDictionary::kHeaderSize + - StringDictionary::kElementsStartIndex * kPointerSize; - for (int i = 0; i < kProbes; i++) { - // Compute the masked index: (hash + i + i * i) & mask. - __ mov(r0, FieldOperand(name, String::kHashFieldOffset)); - __ shr(r0, String::kHashShift); - if (i > 0) { - __ add(Operand(r0), Immediate(StringDictionary::GetProbeOffset(i))); - } - __ and_(r0, Operand(r1)); - - // Scale the index by multiplying by the entry size. - ASSERT(StringDictionary::kEntrySize == 3); - __ lea(r0, Operand(r0, r0, times_2, 0)); // r0 = r0 * 3 - - // Check if the key is identical to the name. - __ cmp(name, Operand(elements, r0, times_4, - kElementsStartOffset - kHeapObjectTag)); - if (i != kProbes - 1) { - __ j(equal, done, taken); - } else { - __ j(not_equal, miss, not_taken); - } - } -} - - // Helper function used to load a property from a dictionary backing // storage. This function may fail to load a property even though it is @@ -183,13 +129,13 @@ static void GenerateDictionaryLoad(MacroAssembler* masm, Label done; // Probe the dictionary. - GenerateStringDictionaryProbes(masm, - miss_label, - &done, - elements, - name, - r0, - r1); + StringDictionaryLookupStub::GeneratePositiveLookup(masm, + miss_label, + &done, + elements, + name, + r0, + r1); // If probing finds an entry in the dictionary, r0 contains the // index into the dictionary. Check that the value is a normal @@ -238,13 +184,13 @@ static void GenerateDictionaryStore(MacroAssembler* masm, // Probe the dictionary. - GenerateStringDictionaryProbes(masm, - miss_label, - &done, - elements, - name, - r0, - r1); + StringDictionaryLookupStub::GeneratePositiveLookup(masm, + miss_label, + &done, + elements, + name, + r0, + r1); // If probing finds an entry in the dictionary, r0 contains the // index into the dictionary. Check that the value is a normal diff --git a/src/ia32/stub-cache-ia32.cc b/src/ia32/stub-cache-ia32.cc index c625115..30e9dee 100644 --- a/src/ia32/stub-cache-ia32.cc +++ b/src/ia32/stub-cache-ia32.cc @@ -118,7 +118,6 @@ static void GenerateDictionaryNegativeLookup(MacroAssembler* masm, __ IncrementCounter(counters->negative_lookups(), 1); __ IncrementCounter(counters->negative_lookups_miss(), 1); - Label done; __ mov(r0, FieldOperand(receiver, HeapObject::kMapOffset)); const int kInterceptorOrAccessCheckNeededMask = @@ -142,62 +141,13 @@ static void GenerateDictionaryNegativeLookup(MacroAssembler* masm, Immediate(masm->isolate()->factory()->hash_table_map())); __ j(not_equal, miss_label); - // Compute the capacity mask. - const int kCapacityOffset = - StringDictionary::kHeaderSize + - StringDictionary::kCapacityIndex * kPointerSize; - - // Generate an unrolled loop that performs a few probes before - // giving up. - static const int kProbes = 4; - const int kElementsStartOffset = - StringDictionary::kHeaderSize + - StringDictionary::kElementsStartIndex * kPointerSize; - - // If names of slots in range from 1 to kProbes - 1 for the hash value are - // not equal to the name and kProbes-th slot is not used (its name is the - // undefined value), it guarantees the hash table doesn't contain the - // property. It's true even if some slots represent deleted properties - // (their names are the null value). - for (int i = 0; i < kProbes; i++) { - // r0 points to properties hash. - // Compute the masked index: (hash + i + i * i) & mask. - Register index = r1; - // Capacity is smi 2^n. - __ mov(index, FieldOperand(properties, kCapacityOffset)); - __ dec(index); - __ and_(Operand(index), - Immediate(Smi::FromInt(name->Hash() + - StringDictionary::GetProbeOffset(i)))); - - // Scale the index by multiplying by the entry size. - ASSERT(StringDictionary::kEntrySize == 3); - __ lea(index, Operand(index, index, times_2, 0)); // index *= 3. - - Register entity_name = r1; - // Having undefined at this place means the name is not contained. - ASSERT_EQ(kSmiTagSize, 1); - __ mov(entity_name, Operand(properties, index, times_half_pointer_size, - kElementsStartOffset - kHeapObjectTag)); - __ cmp(entity_name, masm->isolate()->factory()->undefined_value()); - if (i != kProbes - 1) { - __ j(equal, &done, taken); - - // Stop if found the property. - __ cmp(entity_name, Handle(name)); - __ j(equal, miss_label, not_taken); - - // Check if the entry name is not a symbol. - __ mov(entity_name, FieldOperand(entity_name, HeapObject::kMapOffset)); - __ test_b(FieldOperand(entity_name, Map::kInstanceTypeOffset), - kIsSymbolMask); - __ j(zero, miss_label, not_taken); - } else { - // Give up probing if still not found the undefined value. - __ j(not_equal, miss_label, not_taken); - } - } - + Label done; + StringDictionaryLookupStub::GenerateNegativeLookup(masm, + miss_label, + &done, + properties, + name, + r1); __ bind(&done); __ DecrementCounter(counters->negative_lookups_miss(), 1); } diff --git a/src/x64/code-stubs-x64.cc b/src/x64/code-stubs-x64.cc index 319b105..cfe62e7 100644 --- a/src/x64/code-stubs-x64.cc +++ b/src/x64/code-stubs-x64.cc @@ -996,7 +996,7 @@ void TypeRecordingBinaryOpStub::GenerateFloatingPointCode( // We need tagged values in rdx and rax for the following code, // not int32 in rax and rcx. __ Integer32ToSmi(rax, rcx); - __ Integer32ToSmi(rdx, rbx); + __ Integer32ToSmi(rdx, rax); __ jmp(allocation_failure); } break; @@ -4876,6 +4876,203 @@ void ICCompareStub::GenerateMiss(MacroAssembler* masm) { } +void StringDictionaryLookupStub::GenerateNegativeLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register properties, + String* name, + Register r0) { + // If names of slots in range from 1 to kProbes - 1 for the hash value are + // not equal to the name and kProbes-th slot is not used (its name is the + // undefined value), it guarantees the hash table doesn't contain the + // property. It's true even if some slots represent deleted properties + // (their names are the null value). + for (int i = 0; i < kInlinedProbes; i++) { + // r0 points to properties hash. + // Compute the masked index: (hash + i + i * i) & mask. + Register index = r0; + // Capacity is smi 2^n. + __ SmiToInteger32(index, FieldOperand(properties, kCapacityOffset)); + __ decl(index); + __ and_(index, + Immediate(name->Hash() + StringDictionary::GetProbeOffset(i))); + + // Scale the index by multiplying by the entry size. + ASSERT(StringDictionary::kEntrySize == 3); + __ lea(index, Operand(index, index, times_2, 0)); // index *= 3. + + Register entity_name = r0; + // Having undefined at this place means the name is not contained. + ASSERT_EQ(kSmiTagSize, 1); + __ movq(entity_name, Operand(properties, + index, + times_pointer_size, + kElementsStartOffset - kHeapObjectTag)); + __ Cmp(entity_name, masm->isolate()->factory()->undefined_value()); + __ j(equal, done); + + // Stop if found the property. + __ Cmp(entity_name, Handle(name)); + __ j(equal, miss); + + // Check if the entry name is not a symbol. + __ movq(entity_name, FieldOperand(entity_name, HeapObject::kMapOffset)); + __ testb(FieldOperand(entity_name, Map::kInstanceTypeOffset), + Immediate(kIsSymbolMask)); + __ j(zero, miss); + } + + StringDictionaryLookupStub stub(properties, + r0, + r0, + StringDictionaryLookupStub::NEGATIVE_LOOKUP); + __ Push(Handle(name)); + __ push(Immediate(name->Hash())); + __ CallStub(&stub); + __ testq(r0, r0); + __ j(not_zero, miss); + __ jmp(done); +} + + +// Probe the string dictionary in the |elements| register. Jump to the +// |done| label if a property with the given name is found leaving the +// index into the dictionary in |r1|. Jump to the |miss| label +// otherwise. +void StringDictionaryLookupStub::GeneratePositiveLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register elements, + Register name, + Register r0, + Register r1) { + // Assert that name contains a string. + if (FLAG_debug_code) __ AbortIfNotString(name); + + __ SmiToInteger32(r0, FieldOperand(elements, kCapacityOffset)); + __ decl(r0); + + for (int i = 0; i < kInlinedProbes; i++) { + // Compute the masked index: (hash + i + i * i) & mask. + __ movl(r1, FieldOperand(name, String::kHashFieldOffset)); + __ shrl(r1, Immediate(String::kHashShift)); + if (i > 0) { + __ addl(r1, Immediate(StringDictionary::GetProbeOffset(i))); + } + __ and_(r1, r0); + + // Scale the index by multiplying by the entry size. + ASSERT(StringDictionary::kEntrySize == 3); + __ lea(r1, Operand(r1, r1, times_2, 0)); // r1 = r1 * 3 + + // Check if the key is identical to the name. + __ cmpq(name, Operand(elements, r1, times_pointer_size, + kElementsStartOffset - kHeapObjectTag)); + __ j(equal, done); + } + + StringDictionaryLookupStub stub(elements, + r0, + r1, + POSITIVE_LOOKUP); + __ push(name); + __ movl(r0, FieldOperand(name, String::kHashFieldOffset)); + __ shrl(r0, Immediate(String::kHashShift)); + __ push(r0); + __ CallStub(&stub); + + __ testq(r0, r0); + __ j(zero, miss); + __ jmp(done); +} + + +void StringDictionaryLookupStub::Generate(MacroAssembler* masm) { + // Stack frame on entry: + // esp[0 * kPointerSize]: return address. + // esp[1 * kPointerSize]: key's hash. + // esp[2 * kPointerSize]: key. + // Registers: + // dictionary_: StringDictionary to probe. + // result_: used as scratch. + // index_: will hold an index of entry if lookup is successful. + // might alias with result_. + // Returns: + // result_ is zero if lookup failed, non zero otherwise. + + Label in_dictionary, maybe_in_dictionary, not_in_dictionary; + + Register scratch = result_; + + __ SmiToInteger32(scratch, FieldOperand(dictionary_, kCapacityOffset)); + __ decl(scratch); + __ push(scratch); + + // If names of slots in range from 1 to kProbes - 1 for the hash value are + // not equal to the name and kProbes-th slot is not used (its name is the + // undefined value), it guarantees the hash table doesn't contain the + // property. It's true even if some slots represent deleted properties + // (their names are the null value). + for (int i = kInlinedProbes; i < kTotalProbes; i++) { + // Compute the masked index: (hash + i + i * i) & mask. + __ movq(scratch, Operand(rsp, 2 * kPointerSize)); + if (i > 0) { + __ addl(scratch, Immediate(StringDictionary::GetProbeOffset(i))); + } + __ and_(scratch, Operand(rsp, 0)); + + // Scale the index by multiplying by the entry size. + ASSERT(StringDictionary::kEntrySize == 3); + __ lea(index_, Operand(scratch, scratch, times_2, 0)); // index *= 3. + + // Having undefined at this place means the name is not contained. + __ movq(scratch, Operand(dictionary_, + index_, + times_pointer_size, + kElementsStartOffset - kHeapObjectTag)); + + __ Cmp(scratch, masm->isolate()->factory()->undefined_value()); + __ j(equal, ¬_in_dictionary); + + // Stop if found the property. + __ cmpq(scratch, Operand(rsp, 3 * kPointerSize)); + __ j(equal, &in_dictionary); + + if (i != kTotalProbes - 1 && mode_ == NEGATIVE_LOOKUP) { + // If we hit a non symbol key during negative lookup + // we have to bailout as this key might be equal to the + // key we are looking for. + + // Check if the entry name is not a symbol. + __ movq(scratch, FieldOperand(scratch, HeapObject::kMapOffset)); + __ testb(FieldOperand(scratch, Map::kInstanceTypeOffset), + Immediate(kIsSymbolMask)); + __ j(zero, &maybe_in_dictionary); + } + } + + __ bind(&maybe_in_dictionary); + // If we are doing negative lookup then probing failure should be + // treated as a lookup success. For positive lookup probing failure + // should be treated as lookup failure. + if (mode_ == POSITIVE_LOOKUP) { + __ movq(scratch, Immediate(0)); + __ Drop(1); + __ ret(2 * kPointerSize); + } + + __ bind(&in_dictionary); + __ movq(scratch, Immediate(1)); + __ Drop(1); + __ ret(2 * kPointerSize); + + __ bind(¬_in_dictionary); + __ movq(scratch, Immediate(0)); + __ Drop(1); + __ ret(2 * kPointerSize); +} + + #undef __ } } // namespace v8::internal diff --git a/src/x64/code-stubs-x64.h b/src/x64/code-stubs-x64.h index 0ee10b5..f1e1e5b 100644 --- a/src/x64/code-stubs-x64.h +++ b/src/x64/code-stubs-x64.h @@ -428,6 +428,73 @@ class NumberToStringStub: public CodeStub { }; +class StringDictionaryLookupStub: public CodeStub { + public: + enum LookupMode { POSITIVE_LOOKUP, NEGATIVE_LOOKUP }; + + StringDictionaryLookupStub(Register dictionary, + Register result, + Register index, + LookupMode mode) + : dictionary_(dictionary), result_(result), index_(index), mode_(mode) { } + + void Generate(MacroAssembler* masm); + + static void GenerateNegativeLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register properties, + String* name, + Register r0); + + static void GeneratePositiveLookup(MacroAssembler* masm, + Label* miss, + Label* done, + Register elements, + Register name, + Register r0, + Register r1); + + private: + static const int kInlinedProbes = 4; + static const int kTotalProbes = 20; + + static const int kCapacityOffset = + StringDictionary::kHeaderSize + + StringDictionary::kCapacityIndex * kPointerSize; + + static const int kElementsStartOffset = + StringDictionary::kHeaderSize + + StringDictionary::kElementsStartIndex * kPointerSize; + + +#ifdef DEBUG + void Print() { + PrintF("StringDictionaryLookupStub\n"); + } +#endif + + Major MajorKey() { return StringDictionaryNegativeLookup; } + + int MinorKey() { + return DictionaryBits::encode(dictionary_.code()) | + ResultBits::encode(result_.code()) | + IndexBits::encode(index_.code()) | + LookupModeBits::encode(mode_); + } + + class DictionaryBits: public BitField {}; + class ResultBits: public BitField {}; + class IndexBits: public BitField {}; + class LookupModeBits: public BitField {}; + + Register dictionary_; + Register result_; + Register index_; + LookupMode mode_; +}; + + } } // namespace v8::internal #endif // V8_X64_CODE_STUBS_X64_H_ diff --git a/src/x64/ic-x64.cc b/src/x64/ic-x64.cc index 5ed89b5..05d8719 100644 --- a/src/x64/ic-x64.cc +++ b/src/x64/ic-x64.cc @@ -97,58 +97,6 @@ static void GenerateStringDictionaryReceiverCheck(MacroAssembler* masm, } -// Probe the string dictionary in the |elements| register. Jump to the -// |done| label if a property with the given name is found leaving the -// index into the dictionary in |r1|. Jump to the |miss| label -// otherwise. -static void GenerateStringDictionaryProbes(MacroAssembler* masm, - Label* miss, - Label* done, - Register elements, - Register name, - Register r0, - Register r1) { - // Assert that name contains a string. - if (FLAG_debug_code) __ AbortIfNotString(name); - - // Compute the capacity mask. - const int kCapacityOffset = - StringDictionary::kHeaderSize + - StringDictionary::kCapacityIndex * kPointerSize; - __ SmiToInteger32(r0, FieldOperand(elements, kCapacityOffset)); - __ decl(r0); - - // Generate an unrolled loop that performs a few probes before - // giving up. Measurements done on Gmail indicate that 2 probes - // cover ~93% of loads from dictionaries. - static const int kProbes = 4; - const int kElementsStartOffset = - StringDictionary::kHeaderSize + - StringDictionary::kElementsStartIndex * kPointerSize; - for (int i = 0; i < kProbes; i++) { - // Compute the masked index: (hash + i + i * i) & mask. - __ movl(r1, FieldOperand(name, String::kHashFieldOffset)); - __ shrl(r1, Immediate(String::kHashShift)); - if (i > 0) { - __ addl(r1, Immediate(StringDictionary::GetProbeOffset(i))); - } - __ and_(r1, r0); - - // Scale the index by multiplying by the entry size. - ASSERT(StringDictionary::kEntrySize == 3); - __ lea(r1, Operand(r1, r1, times_2, 0)); // r1 = r1 * 3 - - // Check if the key is identical to the name. - __ cmpq(name, Operand(elements, r1, times_pointer_size, - kElementsStartOffset - kHeapObjectTag)); - if (i != kProbes - 1) { - __ j(equal, done); - } else { - __ j(not_equal, miss); - } - } -} - // Helper function used to load a property from a dictionary backing storage. // This function may return false negatives, so miss_label @@ -179,13 +127,13 @@ static void GenerateDictionaryLoad(MacroAssembler* masm, Label done; // Probe the dictionary. - GenerateStringDictionaryProbes(masm, - miss_label, - &done, - elements, - name, - r0, - r1); + StringDictionaryLookupStub::GeneratePositiveLookup(masm, + miss_label, + &done, + elements, + name, + r0, + r1); // If probing finds an entry in the dictionary, r0 contains the // index into the dictionary. Check that the value is a normal @@ -237,13 +185,13 @@ static void GenerateDictionaryStore(MacroAssembler* masm, Label done; // Probe the dictionary. - GenerateStringDictionaryProbes(masm, - miss_label, - &done, - elements, - name, - scratch0, - scratch1); + StringDictionaryLookupStub::GeneratePositiveLookup(masm, + miss_label, + &done, + elements, + name, + scratch0, + scratch1); // If probing finds an entry in the dictionary, scratch0 contains the // index into the dictionary. Check that the value is a normal diff --git a/src/x64/stub-cache-x64.cc b/src/x64/stub-cache-x64.cc index ef6f758..6c83606 100644 --- a/src/x64/stub-cache-x64.cc +++ b/src/x64/stub-cache-x64.cc @@ -93,7 +93,6 @@ static void GenerateDictionaryNegativeLookup(MacroAssembler* masm, __ IncrementCounter(counters->negative_lookups(), 1); __ IncrementCounter(counters->negative_lookups_miss(), 1); - Label done; __ movq(r0, FieldOperand(receiver, HeapObject::kMapOffset)); const int kInterceptorOrAccessCheckNeededMask = @@ -117,62 +116,13 @@ static void GenerateDictionaryNegativeLookup(MacroAssembler* masm, Heap::kHashTableMapRootIndex); __ j(not_equal, miss_label); - // Compute the capacity mask. - const int kCapacityOffset = - StringDictionary::kHeaderSize + - StringDictionary::kCapacityIndex * kPointerSize; - - // Generate an unrolled loop that performs a few probes before - // giving up. - static const int kProbes = 4; - const int kElementsStartOffset = - StringDictionary::kHeaderSize + - StringDictionary::kElementsStartIndex * kPointerSize; - - // If names of slots in range from 1 to kProbes - 1 for the hash value are - // not equal to the name and kProbes-th slot is not used (its name is the - // undefined value), it guarantees the hash table doesn't contain the - // property. It's true even if some slots represent deleted properties - // (their names are the null value). - for (int i = 0; i < kProbes; i++) { - // r0 points to properties hash. - // Compute the masked index: (hash + i + i * i) & mask. - Register index = r1; - // Capacity is smi 2^n. - __ SmiToInteger32(index, FieldOperand(properties, kCapacityOffset)); - __ decl(index); - __ and_(index, - Immediate(name->Hash() + StringDictionary::GetProbeOffset(i))); - - // Scale the index by multiplying by the entry size. - ASSERT(StringDictionary::kEntrySize == 3); - __ lea(index, Operand(index, index, times_2, 0)); // index *= 3. - - Register entity_name = r1; - // Having undefined at this place means the name is not contained. - ASSERT_EQ(kSmiTagSize, 1); - __ movq(entity_name, Operand(properties, index, times_pointer_size, - kElementsStartOffset - kHeapObjectTag)); - __ Cmp(entity_name, masm->isolate()->factory()->undefined_value()); - // __ jmp(miss_label); - if (i != kProbes - 1) { - __ j(equal, &done); - - // Stop if found the property. - __ Cmp(entity_name, Handle(name)); - __ j(equal, miss_label); - - // Check if the entry name is not a symbol. - __ movq(entity_name, FieldOperand(entity_name, HeapObject::kMapOffset)); - __ testb(FieldOperand(entity_name, Map::kInstanceTypeOffset), - Immediate(kIsSymbolMask)); - __ j(zero, miss_label); - } else { - // Give up probing if still not found the undefined value. - __ j(not_equal, miss_label); - } - } - + Label done; + StringDictionaryLookupStub::GenerateNegativeLookup(masm, + miss_label, + &done, + properties, + name, + r1); __ bind(&done); __ DecrementCounter(counters->negative_lookups_miss(), 1); } -- 2.7.4