CSA fast path for Map.prototype.(Get|Has) for string keys.

src/builtins/builtins-collections-gen.cc

 // Copyright 2017 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/builtins/builtins-constructor-gen.h"
 #include "src/builtins/builtins-iterator-gen.h"
 #include "src/builtins/builtins-utils-gen.h"
 #include "src/code-stub-assembler.h"
 #include "src/objects/hash-table.h"
 
@@ skipping 11 matching lines @@
   Node* AllocateJSMap(Node* js_map_function);
 
   template <typename CollectionType>
   Node* AllocateOrderedHashTable();
   Node* AllocateJSCollection(Node* js_map_function);
 
   Node* CallGetRaw(Node* const table, Node* const key);
   template <typename CollectionType, int entrysize>
   Node* CallHasRaw(Node* const table, Node* const key);
 
-  // Tries to find OrderedHashMap entry for given Smi key, jumps
-  // to {entry_found} if the key is found, or to {not_found} if the
-  // key was not found. Returns the node with the entry index (relative to
-  // OrderedHashMap::kHashTableStartIndex). The node can only be used in the
-  // {entry_found} branch.
-  Node* FindOrderedHashMapEntryForSmiKey(Node* table, Node* key_tagged,
-                                         Label* entry_found, Label* not_found);
+  // Builds code that finds OrderedHashMap entry for given key with hash code
+  // {hash} with using the comparison code generated by {key_compare}. The code
+  // jumps to {entry_found} if the key is found, or to {not_found} if the key
+  // was not found. In the {entry_found} branch, the variable
+  // entry_start_position will be bound to the index of the entry (relative to
+  // OrderedHashMap::kHashTableStartIndex).
+  void FindOrderedHashMapEntry(
+      Node* table, Node* key_tagged, Node* hash,
+      std::function<void(Node* other, Label* if_same, Label* if_not_same)>
+          key_compare,
+      Label* entry_found, Variable* entry_start_position, Label* not_found);

[Camillo Bruni, 2017/07/03 14:51:29]

nit: I think it would be nice to have the entry_found and not_found next to each
other.

[Jarin, 2017/07/04 04:24:47]

Well, the idea behind this order was that entry_start_position is only valid in
the entry_found, so those two go together. Since it was not clear to you, it
will likely not be clear to anyone; so I am moving it as you suggested.

+
+  // Specialization for Smi.
+  void FindOrderedHashMapEntryForSmiKey(Node* table, Node* key_tagged,
+                                        Label* entry_found,
+                                        Variable* entry_start_position,
+                                        Label* not_found);
+  void SameValueZeroSmi(Node* key_smi, Node* candidate_key, Label* if_same,
+                        Label* if_not_same);
+
+  // Specialization for String.
+  void FindOrderedHashMapEntryForStringKey(Node* context, Node* table,
+                                           Node* key_tagged, Label* entry_found,
+                                           Variable* entry_start_position,
+                                           Label* not_found);
+  Node* ComputeIntegerHashForString(Node* context, Node* string_key);
+  void SameValueZeroString(Node* context, Node* key_string, Node* candidate_key,
+                           Label* if_same, Label* if_not_same);
 };
 
 template <typename CollectionType>
 Node* CollectionsBuiltinsAssembler::AllocateOrderedHashTable() {
   static const int kCapacity = CollectionType::kMinCapacity;
   static const int kBucketCount = kCapacity / CollectionType::kLoadFactor;
   static const int kDataTableLength = kCapacity * CollectionType::kEntrySize;
   static const int kFixedArrayLength =
       CollectionType::kHashTableStartIndex + kBucketCount + kDataTableLength;
   static const int kDataTableStartIndex =
@@ skipping 324 matching lines @@
   MachineType type_tagged = MachineType::AnyTagged();
 
   Node* const result =
       CallCFunction3(type_uint8, type_ptr, type_tagged, type_tagged,
                      function_addr, isolate_ptr, table, key);
 
   return SelectBooleanConstant(
       Word32NotEqual(Word32And(result, Int32Constant(0xFF)), Int32Constant(0)));
 }
 
-Node* CollectionsBuiltinsAssembler::FindOrderedHashMapEntryForSmiKey(
-    Node* table, Node* key_tagged, Label* entry_found, Label* not_found) {
-  // Compute the hash.
-  Node* const key = SmiUntag(key_tagged);
+void CollectionsBuiltinsAssembler::SameValueZeroSmi(Node* key_smi,
+                                                    Node* candidate_key,
+                                                    Label* if_same,
+                                                    Label* if_not_same) {
+  // If the key is the same, we are done.
+  GotoIf(WordEqual(candidate_key, key_smi), if_same);
+
+  // If the candidate key is smi, then it must be different (because
+  // we already checked for equality above).
+  GotoIf(TaggedIsSmi(candidate_key), if_not_same);
+
+  // If the candidate key is not smi, we still have to check if it is a
+  // heap number with the same value.
+  GotoIfNot(IsHeapNumber(candidate_key), if_not_same);
+
+  Node* const candidate_key_number = LoadHeapNumberValue(candidate_key);
+  Node* const key_number = SmiToFloat64(key_smi);
+
+  GotoIf(Float64Equal(candidate_key_number, key_number), if_same);
+
+  Goto(if_not_same);
+}
+
+void CollectionsBuiltinsAssembler::FindOrderedHashMapEntryForSmiKey(
+    Node* table, Node* smi_key, Label* entry_found,
+    Variable* entry_start_position, Label* not_found) {
+  Node* const key = SmiUntag(smi_key);
   Node* const hash =
       ChangeInt32ToIntPtr(ComputeIntegerHash(key, Int32Constant(0)));
+  FindOrderedHashMapEntry(
+      table, smi_key, hash,
+      [&](Node* other_key, Label* if_same, Label* if_not_same) {
+        SameValueZeroSmi(smi_key, other_key, if_same, if_not_same);
+      },
+      entry_found, entry_start_position, not_found);
+}
 
+void CollectionsBuiltinsAssembler::FindOrderedHashMapEntryForStringKey(
+    Node* context, Node* table, Node* key_tagged, Label* entry_found,
+    Variable* entry_start_position, Label* not_found) {
+  Node* const hash = ComputeIntegerHashForString(context, key_tagged);
+  FindOrderedHashMapEntry(
+      table, key_tagged, hash,
+      [&](Node* other_key, Label* if_same, Label* if_not_same) {
+        SameValueZeroString(context, key_tagged, other_key, if_same,
+                            if_not_same);
+      },
+      entry_found, entry_start_position, not_found);
+}
+
+Node* CollectionsBuiltinsAssembler::ComputeIntegerHashForString(
+    Node* context, Node* string_key) {
+  VARIABLE(var_result, MachineType::PointerRepresentation());
+
+  Label hash_not_computed(this), done(this, &var_result);
+  Node* hash =
+      ChangeInt32ToIntPtr(LoadNameHash(string_key, &hash_not_computed));
+  var_result.Bind(hash);
+  Goto(&done);
+
+  BIND(&hash_not_computed);
+  Node* tagged_hash = CallRuntime(Runtime::kGenericHash, context, string_key);

[Camillo Bruni, 2017/07/03 14:51:29]

For me this RT-call is OK.

I remembered jkummerow complaining about that the hash-computation is rather
expensive. I don't remember whether he concluded that you can basically
internalize the key at slightly higher cost. (again that would mostly make sense
for Set)

[Jarin, 2017/07/04 04:24:47]

Acknowledged.

+  CSA_ASSERT(this, TaggedIsSmi(tagged_hash));
+  var_result.Bind(SmiUntag(tagged_hash));
+  Goto(&done);
+
+  BIND(&done);
+  return var_result.value();
+}
+
+void CollectionsBuiltinsAssembler::SameValueZeroString(Node* context,
+                                                       Node* key_string,
+                                                       Node* candidate_key,
+                                                       Label* if_same,
+                                                       Label* if_not_same) {
+  // If the candidate is not a string, the keys are not equal.
+  GotoIf(TaggedIsSmi(candidate_key), if_not_same);
+  GotoIfNot(IsString(candidate_key), if_not_same);
+
+  Branch(WordEqual(CallBuiltin(Builtins::kStringEqual, context, key_string,
+                               candidate_key),
+                   TrueConstant()),
+         if_same, if_not_same);
+}
+
+void CollectionsBuiltinsAssembler::FindOrderedHashMapEntry(
+    Node* table, Node* key_tagged, Node* hash,
+    std::function<void(Node*, Label*, Label*)> key_compare, Label* entry_found,
+    Variable* entry_start_position, Label* not_found) {
   // Get the index of the bucket.
   Node* const number_of_buckets = SmiUntag(
       LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex));
   Node* const bucket =
       WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1)));
   Node* const first_entry = SmiUntag(LoadFixedArrayElement(
       table, bucket, OrderedHashMap::kHashTableStartIndex * kPointerSize));
 
-  Node* entry_start_position;
   // Walk the bucket chain.
   {
     VARIABLE(var_entry, MachineType::PointerRepresentation(), first_entry);
-    Label loop(this, &var_entry), continue_next_entry(this);
+    Label loop(this, {&var_entry, entry_start_position}),
+        continue_next_entry(this);
     Goto(&loop);
     BIND(&loop);
 
     // If the entry index is the not-found sentinel, we are done.
     GotoIf(
         WordEqual(var_entry.value(), IntPtrConstant(OrderedHashMap::kNotFound)),
         not_found);
 
     // Make sure the entry index is within range.
     CSA_ASSERT(
         this,
         UintPtrLessThan(
             var_entry.value(),
             SmiUntag(SmiAdd(
                 LoadFixedArrayElement(table,
                                       OrderedHashMap::kNumberOfElementsIndex),
                 LoadFixedArrayElement(
                     table, OrderedHashMap::kNumberOfDeletedElementsIndex)))));
 
     // Compute the index of the entry relative to kHashTableStartIndex.
-    entry_start_position =
+    Node* entry_start =
         IntPtrAdd(IntPtrMul(var_entry.value(),
                             IntPtrConstant(OrderedHashMap::kEntrySize)),
                   number_of_buckets);
+    entry_start_position->Bind(entry_start);
 
     // Load the key from the entry.
     Node* const candidate_key = LoadFixedArrayElement(
-        table, entry_start_position,
+        table, entry_start,
         OrderedHashMap::kHashTableStartIndex * kPointerSize);
 
-    // If the key is the same, we are done.
-    GotoIf(WordEqual(candidate_key, key_tagged), entry_found);
-
-    // If the candidate key is smi, then it must be different (because
-    // we already checked for equality above).
-    GotoIf(TaggedIsSmi(candidate_key), &continue_next_entry);
-
-    // If the candidate key is not smi, we still have to check if it is a heap
-    // number with the same value.
-    GotoIfNot(IsHeapNumber(candidate_key), &continue_next_entry);
-
-    Node* const candidate_key_number = LoadHeapNumberValue(candidate_key);
-    Node* const key_number = SmiToFloat64(key_tagged);
-
-    GotoIf(Float64Equal(candidate_key_number, key_number), entry_found);
-
-    Goto(&continue_next_entry);
+    key_compare(candidate_key, entry_found, &continue_next_entry);
 
     BIND(&continue_next_entry);
     // Load the index of the next entry in the bucket chain.
     var_entry.Bind(SmiUntag(LoadFixedArrayElement(
-        table, entry_start_position,
+        table, entry_start,
         (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kChainOffset) *
             kPointerSize)));
 
     Goto(&loop);
   }
-  return entry_start_position;
 }
 
 TF_BUILTIN(MapGet, CollectionsBuiltinsAssembler) {
   Node* const receiver = Parameter(Descriptor::kReceiver);
   Node* const key_tagged = Parameter(Descriptor::kKey);
   Node* const context = Parameter(Descriptor::kContext);
 
   ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.get");
 
   Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
 
-  Label if_key_smi(this);
+  VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
+           IntPtrConstant(0));
+  Label if_key_smi(this), if_key_string(this);
   GotoIf(TaggedIsSmi(key_tagged), &if_key_smi);
+  GotoIf(IsString(key_tagged), &if_key_string);
 
   Return(CallGetRaw(table, key_tagged));
 
   BIND(&if_key_smi);
-  Label entry_found(this), not_found(this);
-  Node* entry_start_position = FindOrderedHashMapEntryForSmiKey(
-      table, key_tagged, &entry_found, &not_found);
+  Label entry_found(this, &entry_start_position), not_found(this);
+  FindOrderedHashMapEntryForSmiKey(table, key_tagged, &entry_found,
+                                   &entry_start_position, &not_found);
+
+  BIND(&if_key_string);
+  FindOrderedHashMapEntryForStringKey(context, table, key_tagged, &entry_found,
+                                      &entry_start_position, &not_found);
 
   BIND(&entry_found);
   Return(LoadFixedArrayElement(
-      table, entry_start_position,
+      table, entry_start_position.value(),
       (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset) *
           kPointerSize));
 
   BIND(&not_found);
   Return(UndefinedConstant());
 }
 
 TF_BUILTIN(MapHas, CollectionsBuiltinsAssembler) {
   Node* const receiver = Parameter(Descriptor::kReceiver);
   Node* const key_tagged = Parameter(Descriptor::kKey);
   Node* const context = Parameter(Descriptor::kContext);
 
   ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.has");
 
   Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
 
-  Label if_key_smi(this);
+  VARIABLE(entry_start_position, MachineType::PointerRepresentation(),
+           IntPtrConstant(0));
+  Label if_key_smi(this), if_key_string(this);
   GotoIf(TaggedIsSmi(key_tagged), &if_key_smi);
+  GotoIf(IsString(key_tagged), &if_key_string);
 
   Return(CallHasRaw<OrderedHashMap, 2>(table, key_tagged));
 
   BIND(&if_key_smi);
   Label entry_found(this), not_found(this);
-  FindOrderedHashMapEntryForSmiKey(table, key_tagged, &entry_found, &not_found);
+  FindOrderedHashMapEntryForSmiKey(table, key_tagged, &entry_found,
+                                   &entry_start_position, &not_found);
+
+  BIND(&if_key_string);
+  FindOrderedHashMapEntryForStringKey(context, table, key_tagged, &entry_found,
+                                      &entry_start_position, &not_found);
 
   BIND(&entry_found);
   Return(TrueConstant());
 
   BIND(&not_found);
   Return(FalseConstant());
 }
 
 TF_BUILTIN(SetHas, CollectionsBuiltinsAssembler) {
   Node* const receiver = Parameter(Descriptor::kReceiver);
   Node* const key = Parameter(Descriptor::kKey);
   Node* const context = Parameter(Descriptor::kContext);
 
   ThrowIfNotInstanceType(context, receiver, JS_SET_TYPE, "Set.prototype.has");
 
   Node* const table = LoadObjectField(receiver, JSMap::kTableOffset);
   Return(CallHasRaw<OrderedHashSet, 1>(table, key));
 }
 
 }  // namespace internal
 }  // namespace v8