Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(425)

Unified Diff: src/ia32/code-stubs-ia32.cc

Issue 6932010: Unroll more StringDictionary lookup probes both for positive and negative dictionary lookups. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: revive inlined portions Created 9 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: src/ia32/code-stubs-ia32.cc
diff --git a/src/ia32/code-stubs-ia32.cc b/src/ia32/code-stubs-ia32.cc
index 7af000ade22d12dae3930fca061208a6b8580aaf..53e86e33cf7d3dc1c520189a1e272f1d13709a67 100644
--- a/src/ia32/code-stubs-ia32.cc
+++ b/src/ia32/code-stubs-ia32.cc
@@ -5859,6 +5859,109 @@ void ICCompareStub::GenerateMiss(MacroAssembler* masm) {
}
+void StringDictionaryLookupStub::Generate(MacroAssembler* masm) {
+ // Stack frame on entry:
+ // esp[0]: return address.
+ // esp[4]: key's hash.
+ // esp[8]: 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;
+
+ // 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 kFirstProbe = 4;
+ static const int kProbes = 20;
+ const int kElementsStartOffset =
+ StringDictionary::kHeaderSize +
+ StringDictionary::kElementsStartIndex * kPointerSize;
+
+ 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 = kFirstProbe; i < kProbes; 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, &not_in_dictionary);
+
+ if (i != kProbes - 1) {
+ // Stop if found the property.
+ __ cmp(scratch, Operand(esp, 3 * kPointerSize));
+ __ j(equal, &in_dictionary);
+
+ if (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(scratch, Immediate(0));
+ __ Drop(1);
+ __ ret(2 * kPointerSize);
+ }
+
+ __ bind(&in_dictionary);
+ __ mov(scratch, Immediate(1));
+ __ Drop(1);
+ __ ret(2 * kPointerSize);
+
+ __ bind(&not_in_dictionary);
+ __ mov(scratch, Immediate(0));
+ __ Drop(1);
+ __ ret(2 * kPointerSize);
+}
+
+
#undef __
} } // namespace v8::internal
« no previous file with comments | « src/ia32/code-stubs-ia32.h ('k') | src/ia32/ic-ia32.cc » ('j') | src/ia32/stub-cache-ia32.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698