[stubs] Extend HasProperty stub with dictionary-mode and double-elements objects support.

src/code-stub-assembler.cc

Index: src/code-stub-assembler.cc
diff --git a/src/code-stub-assembler.cc b/src/code-stub-assembler.cc
index e0963145ff0198c2698e63a55e6f59097eba8623..6b32a15ac78a61efddcbab10061bfecc4e3b9c9d 100644
--- a/src/code-stub-assembler.cc
+++ b/src/code-stub-assembler.cc
@@ -46,6 +46,14 @@ Node* CodeStubAssembler::UndefinedConstant() {
   return LoadRoot(Heap::kUndefinedValueRootIndex);
 }
 
+Node* CodeStubAssembler::TheHoleConstant() {
+  return LoadRoot(Heap::kTheHoleValueRootIndex);
+}
+
+Node* CodeStubAssembler::HashSeed() {
+  return SmiToWord32(LoadRoot(Heap::kHashSeedRootIndex));
+}
+
 Node* CodeStubAssembler::StaleRegisterConstant() {
   return LoadRoot(Heap::kStaleRegisterRootIndex);
 }
@@ -469,6 +477,10 @@ Node* CodeStubAssembler::LoadInstanceType(Node* object) {
   return LoadMapInstanceType(LoadMap(object));
 }
 
+Node* CodeStubAssembler::LoadProperties(Node* object) {
+  return LoadObjectField(object, JSObject::kPropertiesOffset);
+}
+
 Node* CodeStubAssembler::LoadElements(Node* object) {
   return LoadObjectField(object, JSObject::kElementsOffset);
 }
@@ -505,11 +517,27 @@ Node* CodeStubAssembler::LoadMapPrototype(Node* map) {
   return LoadObjectField(map, Map::kPrototypeOffset);
 }
 
-Node* CodeStubAssembler::LoadNameHash(Node* name) {
+Node* CodeStubAssembler::LoadNameHashField(Node* name) {
   return Load(MachineType::Uint32(), name,
               IntPtrConstant(Name::kHashFieldOffset - kHeapObjectTag));
 }
 
+Node* CodeStubAssembler::LoadNameHash(Node* name, Label* if_hash_not_computed) {
+  Node* hash_field = LoadNameHashField(name);
+  if (if_hash_not_computed != nullptr) {
+    GotoIf(WordEqual(
+               Word32And(hash_field, Int32Constant(Name::kHashNotComputedMask)),
+               Int32Constant(0)),
+           if_hash_not_computed);
+  }
+  return Word32Shr(hash_field, Int32Constant(Name::kHashShift));
+}
+
+Node* CodeStubAssembler::LoadMapInstanceSize(Node* map) {
+  return Load(MachineType::Uint8(), map,
+              IntPtrConstant(Map::kInstanceSizeOffset - kHeapObjectTag));
+}
+
 Node* CodeStubAssembler::AllocateUninitializedFixedArray(Node* length) {
   Node* header_size = IntPtrConstant(FixedArray::kHeaderSize);
   Node* data_size = WordShl(length, IntPtrConstant(kPointerSizeLog2));
@@ -533,11 +561,6 @@ Node* CodeStubAssembler::LoadFixedArrayElementInt32Index(
   return Load(MachineType::AnyTagged(), object, offset);
 }
 
-Node* CodeStubAssembler::LoadMapInstanceSize(Node* map) {
-  return Load(MachineType::Uint8(), map,
-              IntPtrConstant(Map::kInstanceSizeOffset - kHeapObjectTag));
-}
-
 Node* CodeStubAssembler::LoadFixedArrayElementSmiIndex(Node* object,
                                                        Node* smi_index,
                                                        int additional_offset) {
@@ -560,6 +583,23 @@ Node* CodeStubAssembler::LoadFixedArrayElementConstantIndex(Node* object,
   return Load(MachineType::AnyTagged(), object, offset);
 }
 
+Node* CodeStubAssembler::OffsetOfFixedDoubleArrayElementInt32Index(
+    Node* index, int additional_offset) {
+  Node* header_size = IntPtrConstant(
+      additional_offset + FixedDoubleArray::kHeaderSize - kHeapObjectTag);
+  index = ChangeInt32ToIntPtr(index);
+  Node* scaled_index = WordShl(index, IntPtrConstant(kDoubleSizeLog2));
+  return IntPtrAdd(scaled_index, header_size);
+}
+
+Node* CodeStubAssembler::LoadFixedDoubleArrayElementInt32Index(
+    Node* object, Node* index, MachineType machine_type,
+    int additional_offset) {
+  Node* offset =
+      OffsetOfFixedDoubleArrayElementInt32Index(index, additional_offset);
+  return Load(machine_type, object, offset);
+}
+
 Node* CodeStubAssembler::LoadNativeContext(Node* context) {
   return LoadFixedArrayElementConstantIndex(context,
                                             Context::NATIVE_CONTEXT_INDEX);
@@ -1286,9 +1326,7 @@ void CodeStubAssembler::TryToName(Node* key, Label* if_keyisindex,
   Bind(&if_keyissmi);
   {
     // Negative smi keys are named properties. Handle in the runtime.
-    Label if_keyispositive(this);
-    Branch(WordIsPositiveSmi(key), &if_keyispositive, call_runtime);
-    Bind(&if_keyispositive);
+    GotoUnless(WordIsPositiveSmi(key), call_runtime);
 
     var_index->Bind(SmiToWord32(key));
     Goto(if_keyisindex);
@@ -1297,123 +1335,321 @@ void CodeStubAssembler::TryToName(Node* key, Label* if_keyisindex,
   Bind(&if_keyisnotsmi);
 
   Node* key_instance_type = LoadInstanceType(key);
-  Label if_keyisnotsymbol(this);
-  Branch(Word32Equal(key_instance_type, Int32Constant(SYMBOL_TYPE)),
-         if_keyisunique, &if_keyisnotsymbol);
-  Bind(&if_keyisnotsymbol);
+  // Symbols are unique.
+  GotoIf(Word32Equal(key_instance_type, Int32Constant(SYMBOL_TYPE)),
+         if_keyisunique);
+
+  Label if_keyisinternalized(this);
+  Node* bits =
+      WordAnd(key_instance_type,
+              Int32Constant(kIsNotStringMask | kIsNotInternalizedMask));
+  Branch(Word32Equal(bits, Int32Constant(kStringTag | kInternalizedTag)),
+         &if_keyisinternalized, call_runtime);
+  Bind(&if_keyisinternalized);
+
+  // Check whether the key is an array index passed in as string. Handle
+  // uniform with smi keys if so.
+  // TODO(verwaest): Also support non-internalized strings.
+  Node* hash = LoadNameHashField(key);
+  Node* bit = Word32And(hash, Int32Constant(Name::kIsNotArrayIndexMask));
+  GotoIf(Word32NotEqual(bit, Int32Constant(0)), if_keyisunique);
+  // Key is an index. Check if it is small enough to be encoded in the
+  // hash_field. Handle too big array index in runtime.
+  bit = Word32And(hash, Int32Constant(Name::kContainsCachedArrayIndexMask));
+  GotoIf(Word32NotEqual(bit, Int32Constant(0)), call_runtime);
+  var_index->Bind(BitFieldDecode<Name::ArrayIndexValueBits>(hash));
+  Goto(if_keyisindex);
+}
+
+template <typename Dictionary>
+void CodeStubAssembler::NameDictionaryLookup(Node* dictionary,
+                                             Node* unique_name, Label* if_found,
+                                             Label* if_not_found,
+                                             Label* call_runtime,
+                                             int inlined_probes) {
+  const int kElementsStartOffset =
+      Dictionary::kElementsStartIndex * kPointerSize;
+
+  Node* capacity = SmiToWord32(LoadFixedArrayElementConstantIndex(
+      dictionary, Dictionary::kCapacityIndex));
+  Node* mask = Int32Sub(capacity, Int32Constant(1));
+  Node* hash = LoadNameHash(unique_name);
+
+  // See Dictionary::FirstProbe().
+  Node* count = Int32Constant(0);
+  Node* entry = Word32And(hash, mask);
+
+  for (int i = 0; i < inlined_probes; i++) {
+    // See Dictionary::EntryToIndex()
+    Node* index = Int32Mul(entry, Int32Constant(Dictionary::kEntrySize));
+    Node* current = LoadFixedArrayElementInt32Index(dictionary, index,
+                                                    kElementsStartOffset);
+    GotoIf(WordEqual(current, unique_name), if_found);
+
+    // See Dictionary::NextProbe().
+    count = Int32Constant(i + 1);
+    entry = Word32And(Int32Add(entry, count), mask);
+  }
+
+  Node* undefined = UndefinedConstant();
+
+  Variable var_count(this, MachineRepresentation::kWord32);
+  Variable var_entry(this, MachineType::PointerRepresentation());

[Toon Verwaest, 2016/05/19 14:50:22]

Shouldn't this be kWord32 as well?

[Igor Sheludko, 2016/05/30 12:11:34]

Done.

+  Variable* loop_vars[] = {&var_count, &var_entry};
+  Label loop(this, 2, loop_vars);
+  var_count.Bind(count);
+  var_entry.Bind(entry);
+  Goto(&loop);
+  Bind(&loop);
   {
-    Label if_keyisinternalized(this);
-    Node* bits =
-        WordAnd(key_instance_type,
-                Int32Constant(kIsNotStringMask | kIsNotInternalizedMask));
-    Branch(Word32Equal(bits, Int32Constant(kStringTag | kInternalizedTag)),
-           &if_keyisinternalized, call_runtime);
-    Bind(&if_keyisinternalized);
-
-    // Check whether the key is an array index passed in as string. Handle
-    // uniform with smi keys if so.
-    // TODO(verwaest): Also support non-internalized strings.
-    Node* hash = LoadNameHash(key);
-    Node* bit =
-        Word32And(hash, Int32Constant(internal::Name::kIsNotArrayIndexMask));
-    Label if_isarrayindex(this);
-    Branch(Word32Equal(bit, Int32Constant(0)), &if_isarrayindex,
-           if_keyisunique);
-    Bind(&if_isarrayindex);
-    var_index->Bind(BitFieldDecode<internal::Name::ArrayIndexValueBits>(hash));
-    Goto(if_keyisindex);
+    Node* count = var_count.value();
+    Node* entry = var_entry.value();
+
+    // See Dictionary::EntryToIndex()
+    Node* index = Int32Mul(entry, Int32Constant(Dictionary::kEntrySize));
+    Node* current = LoadFixedArrayElementInt32Index(dictionary, index,
+                                                    kElementsStartOffset);
+    GotoIf(WordEqual(current, undefined), if_not_found);
+    GotoIf(WordEqual(current, unique_name), if_found);
+
+    // See Dictionary::NextProbe().
+    count = Int32Add(count, Int32Constant(1));
+    entry = Word32And(Int32Add(entry, count), mask);
+
+    var_count.Bind(count);
+    var_entry.Bind(entry);
+    Goto(&loop);
   }
 }
 
-void CodeStubAssembler::TryLookupProperty(Node* object, Node* map,
-                                          Node* instance_type, Node* name,
-                                          Label* if_found, Label* if_not_found,
-                                          Label* call_runtime) {
+Node* CodeStubAssembler::ComputeIntegerHash(Node* key, Node* seed) {
+  // See v8::internal::ComputeIntegerHash()
+  Node* hash = key;
+  hash = Word32Xor(hash, seed);
+  hash = Int32Add(Word32Xor(hash, Int32Constant(0xffffffff)),
+                  Word32Shl(hash, Int32Constant(15)));

[Toon Verwaest, 2016/05/19 14:50:22]

What about explicitly sharing these constants with runtime code?

[Igor Sheludko, 2016/05/30 12:11:34]

I think we can just rely on a respective unit test results instead.

+  hash = Word32Xor(hash, Word32Shr(hash, Int32Constant(12)));
+  hash = Int32Add(hash, Word32Shl(hash, Int32Constant(2)));
+  hash = Word32Xor(hash, Word32Shr(hash, Int32Constant(4)));
+  hash = Int32Mul(hash, Int32Constant(2057));
+  hash = Word32Xor(hash, Word32Shr(hash, Int32Constant(16)));
+  return Word32And(hash, Int32Constant(0x3fffffff));
+}
+
+template <typename Dictionary>
+void CodeStubAssembler::NumberDictionaryLookup(Node* dictionary, Node* key,
+                                               Label* if_found,
+                                               Label* if_not_found,
+                                               Label* call_runtime) {
+  const int kElementsStartOffset =
+      Dictionary::kElementsStartIndex * kPointerSize;
+
+  Node* capacity = SmiToWord32(LoadFixedArrayElementConstantIndex(
+      dictionary, Dictionary::kCapacityIndex));
+  Node* mask = Int32Sub(capacity, Int32Constant(1));
+
+  Node* seed;
+  if (Dictionary::ShapeT::UsesSeed) {
+    seed = HashSeed();
+  } else {
+    seed = Int32Constant(kZeroHashSeed);
+  }
+  Node* hash = ComputeIntegerHash(key, seed);
+  Node* key_as_float64 = ChangeUint32ToFloat64(key);
+
+  // See Dictionary::FirstProbe().
+  Node* count = Int32Constant(0);
+  Node* entry = Word32And(hash, mask);
+
+  Node* undefined = UndefinedConstant();
+  Node* the_hole = TheHoleConstant();
+
+  Variable var_count(this, MachineRepresentation::kWord32);
+  Variable var_entry(this, MachineType::PointerRepresentation());
+  Variable* loop_vars[] = {&var_count, &var_entry};
+  Label loop(this, 2, loop_vars);
+  var_count.Bind(count);
+  var_entry.Bind(entry);
+  Goto(&loop);
+  Bind(&loop);
   {
-    Label if_objectissimple(this);
-    Branch(Int32LessThanOrEqual(instance_type,
-                                Int32Constant(LAST_SPECIAL_RECEIVER_TYPE)),
-           call_runtime, &if_objectissimple);
-    Bind(&if_objectissimple);
+    Node* count = var_count.value();
+    Node* entry = var_entry.value();
+
+    // See Dictionary::EntryToIndex()
+    Node* index = Int32Mul(entry, Int32Constant(Dictionary::kEntrySize));
+    Node* current = LoadFixedArrayElementInt32Index(dictionary, index,
+                                                    kElementsStartOffset);
+    GotoIf(WordEqual(current, undefined), if_not_found);
+    Label next_probe(this);
+    {
+      Label if_currentissmi(this), if_currentisnotsmi(this);
+      Branch(WordIsSmi(current), &if_currentissmi, &if_currentisnotsmi);
+      Bind(&if_currentissmi);
+      {
+        Node* current_value = SmiToWord32(current);
+        Branch(Word32Equal(current_value, key), if_found, &next_probe);
+      }
+      Bind(&if_currentisnotsmi);
+      {
+        GotoIf(WordEqual(current, the_hole), &next_probe);
+        // Current must be the Number.
+        Node* current_value = LoadHeapNumberValue(current);
+        Branch(Float64Equal(current_value, key_as_float64), if_found,
+               &next_probe);
+      }
+    }
+
+    Bind(&next_probe);
+    // See Dictionary::NextProbe().
+    count = Int32Add(count, Int32Constant(1));
+    entry = Word32And(Int32Add(entry, count), mask);
+
+    var_count.Bind(count);
+    var_entry.Bind(entry);
+    Goto(&loop);
   }
+}
+
+void CodeStubAssembler::TryLookupProperty(Node* object, Node* map,
+                                          Node* instance_type,
+                                          Node* unique_name, Label* if_found,
+                                          Label* if_not_found,
+                                          Label* call_runtime) {
+  // Handle non-simple objects in runtime.
+  GotoIf(Int32LessThanOrEqual(instance_type,
+                              Int32Constant(LAST_SPECIAL_RECEIVER_TYPE)),
+         call_runtime);
 
-  // TODO(verwaest): Perform a dictonary lookup on slow-mode receivers.
   Node* bit_field3 = LoadMapBitField3(map);
   Node* bit = BitFieldDecode<Map::DictionaryMap>(bit_field3);
-  Label if_isfastmap(this);
-  Branch(Word32Equal(bit, Int32Constant(0)), &if_isfastmap, call_runtime);
+  Label if_isfastmap(this), if_isslowmap(this);
+  Branch(Word32Equal(bit, Int32Constant(0)), &if_isfastmap, &if_isslowmap);
   Bind(&if_isfastmap);
-  Node* nof = BitFieldDecode<Map::NumberOfOwnDescriptorsBits>(bit_field3);
-  // Bail out to the runtime for large numbers of own descriptors. The stub only
-  // does linear search, which becomes too expensive in that case.
   {
-    static const int32_t kMaxLinear = 210;
-    Label above_max(this), below_max(this);
-    Branch(Int32LessThanOrEqual(nof, Int32Constant(kMaxLinear)), &below_max,
-           call_runtime);
-    Bind(&below_max);
-  }
-  Node* descriptors = LoadMapDescriptors(map);
+    Node* nof = BitFieldDecode<Map::NumberOfOwnDescriptorsBits>(bit_field3);
+    // Bail out to the runtime for large numbers of own descriptors. The stub
+    // only does linear search, which becomes too expensive in that case.
+    {
+      static const int32_t kMaxLinear = 210;
+      GotoIf(Int32GreaterThan(nof, Int32Constant(kMaxLinear)), call_runtime);
+    }
+    Node* descriptors = LoadMapDescriptors(map);
 
-  Variable var_descriptor(this, MachineRepresentation::kWord32);
-  Label loop(this, &var_descriptor);
-  var_descriptor.Bind(Int32Constant(0));
-  Goto(&loop);
-  Bind(&loop);
-  {
-    Node* index = var_descriptor.value();
-    Node* offset = Int32Constant(DescriptorArray::ToKeyIndex(0));
-    Node* factor = Int32Constant(DescriptorArray::kDescriptorSize);
-    Label if_notdone(this);
-    Branch(Word32Equal(index, nof), if_not_found, &if_notdone);
-    Bind(&if_notdone);
+    Variable var_descriptor(this, MachineRepresentation::kWord32);
+    Label loop(this, &var_descriptor);
+    var_descriptor.Bind(Int32Constant(0));
+    Goto(&loop);
+    Bind(&loop);
     {
+      Node* index = var_descriptor.value();
+      Node* offset = Int32Constant(DescriptorArray::ToKeyIndex(0));
+      Node* factor = Int32Constant(DescriptorArray::kDescriptorSize);
+      GotoIf(Word32Equal(index, nof), if_not_found);
+
       Node* array_index = Int32Add(offset, Int32Mul(index, factor));
       Node* current = LoadFixedArrayElementInt32Index(descriptors, array_index);
-      Label if_unequal(this);
-      Branch(WordEqual(current, name), if_found, &if_unequal);
-      Bind(&if_unequal);
+      GotoIf(WordEqual(current, unique_name), if_found);
 
       var_descriptor.Bind(Int32Add(index, Int32Constant(1)));
       Goto(&loop);
     }
   }
+  Bind(&if_isslowmap);
+  {
+    Node* dictionary = LoadProperties(object);
+
+    Label if_isglobal(this), if_isnotglobal(this);
+    Branch(Word32Equal(instance_type, Int32Constant(JS_GLOBAL_OBJECT_TYPE)),
+           &if_isglobal, &if_isnotglobal);
+
+    Bind(&if_isnotglobal);
+    NameDictionaryLookup<NameDictionary>(dictionary, unique_name, if_found,
+                                         if_not_found, call_runtime);
+
+    Bind(&if_isglobal);
+    NameDictionaryLookup<GlobalDictionary>(dictionary, unique_name, if_found,

[Toon Verwaest, 2016/05/19 14:50:22]

JS_GLOBAL_OBJECT_TYPE <= LAST_SPECIAL_RECEIVER_TYPE, so I presume this isn't
tested. Perhaps we shouldn't add until that point?

[Igor Sheludko, 2016/05/30 12:11:34]

Fixed and added unit tests.

+                                           if_not_found, call_runtime);
+  }
 }
 
 void CodeStubAssembler::TryLookupElement(Node* object, Node* map,
                                          Node* instance_type, Node* index,
                                          Label* if_found, Label* if_not_found,
                                          Label* call_runtime) {
-  {
-    Label if_objectissimple(this);
-    Branch(Int32LessThanOrEqual(instance_type,
-                                Int32Constant(LAST_CUSTOM_ELEMENTS_RECEIVER)),
-           call_runtime, &if_objectissimple);
-    Bind(&if_objectissimple);
-  }
+  // Handle objects with non-simple elements in runtime.
+  GotoIf(Int32LessThanOrEqual(instance_type,
+                              Int32Constant(LAST_CUSTOM_ELEMENTS_RECEIVER)),
+         call_runtime);
 
   Node* bit_field2 = LoadMapBitField2(map);
   Node* elements_kind = BitFieldDecode<Map::ElementsKindBits>(bit_field2);
 
   // TODO(verwaest): Support other elements kinds as well.
-  Label if_isobjectorsmi(this);
-  Branch(
-      Int32LessThanOrEqual(elements_kind, Int32Constant(FAST_HOLEY_ELEMENTS)),
-      &if_isobjectorsmi, call_runtime);
+  Label if_isobjectorsmi(this), if_isdouble(this), if_isdictionary(this);
+  // clang-format off
+  int32_t values[] = {
+      // Handled by {if_isobjectorsmi}.
+      FAST_SMI_ELEMENTS, FAST_HOLEY_SMI_ELEMENTS, FAST_ELEMENTS,
+          FAST_HOLEY_ELEMENTS, FAST_STRING_WRAPPER_ELEMENTS,
+      // Handled by {if_isdouble}.
+      FAST_DOUBLE_ELEMENTS, FAST_HOLEY_DOUBLE_ELEMENTS,
+      // Handled by {if_is_dictionary}.
+      DICTIONARY_ELEMENTS, SLOW_STRING_WRAPPER_ELEMENTS,
+  };
+  Label* labels[] = {
+      &if_isobjectorsmi, &if_isobjectorsmi, &if_isobjectorsmi,
+          &if_isobjectorsmi, &if_isobjectorsmi,
+      &if_isdouble, &if_isdouble,
+      &if_isdictionary, &if_isdictionary,
+  };
+  // clang-format on
+  STATIC_ASSERT(arraysize(values) == arraysize(labels));
+  Switch(elements_kind, call_runtime, values, labels, arraysize(values));
+
   Bind(&if_isobjectorsmi);
   {
     Node* elements = LoadElements(object);
     Node* length = LoadFixedArrayBaseLength(elements);
 
-    Label if_iskeyinrange(this);
-    Branch(Int32LessThan(index, SmiToWord32(length)), &if_iskeyinrange,
-           if_not_found);
+    GotoIf(Int32GreaterThanOrEqual(index, SmiToWord32(length)), if_not_found);
 
-    Bind(&if_iskeyinrange);
     Node* element = LoadFixedArrayElementInt32Index(elements, index);
-    Node* the_hole = LoadRoot(Heap::kTheHoleValueRootIndex);
+    Node* the_hole = TheHoleConstant();
     Branch(WordEqual(element, the_hole), if_not_found, if_found);
   }
+  Bind(&if_isdouble);
+  {
+    Node* elements = LoadElements(object);
+    Node* length = LoadFixedArrayBaseLength(elements);
+
+    GotoIf(Int32GreaterThanOrEqual(index, SmiToWord32(length)), if_not_found);
+
+    if (kPointerSize == kDoubleSize) {
+      Node* element = LoadFixedDoubleArrayElementInt32Index(
+          elements, index, MachineType::Uint64());
+      Node* the_hole = Int64Constant(kHoleNanInt64);
+      Branch(Word64Equal(element, the_hole), if_not_found, if_found);
+    } else {
+      DCHECK_EQ(4, kPointerSize);
+      Node* offset = OffsetOfFixedDoubleArrayElementInt32Index(index);
+      // Since upper and lower parts are the same, don't care about endianness.
+      STATIC_ASSERT(kHoleNanUpper32 == kHoleNanLower32);
+      Node* element_lo = Load(MachineType::Int32(), elements, offset);
+      GotoUnless(Word32Equal(element_lo, Int32Constant(kHoleNanLower32)),
+                 if_found);
+      Node* element_hi = Load(MachineType::Int32(), elements,
+                              Int32Add(offset, Int32Constant(kPointerSize)));
+      Branch(Word32Equal(element_hi, Int32Constant(kHoleNanUpper32)),
+             if_not_found, if_found);
+    }
+  }
+  Bind(&if_isdictionary);
+  {
+    Node* elements = LoadElements(object);
+    NumberDictionaryLookup<SeededNumberDictionary>(elements, index, if_found,
+                                                   if_not_found, call_runtime);
+  }
 }
 
 Node* CodeStubAssembler::OrdinaryHasInstance(Node* context, Node* callable,