Reland of [stubs] KeyedStoreGeneric: inline dictionary property stores

src/code-stub-assembler.cc

 // Copyright 2016 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/code-stub-assembler.h"
 #include "src/code-factory.h"
 #include "src/frames-inl.h"
 #include "src/frames.h"
 
 namespace v8 {
 namespace internal {
@@ skipping 1318 matching lines @@
   if (Heap::RootIsImmortalImmovable(root_index)) {
     return StoreObjectFieldNoWriteBarrier(object, offset, LoadRoot(root_index));
   } else {
     return StoreObjectField(object, offset, LoadRoot(root_index));
   }
 }
 
 Node* CodeStubAssembler::StoreFixedArrayElement(Node* object, Node* index_node,
                                                 Node* value,
                                                 WriteBarrierMode barrier_mode,
+                                                int additional_offset,
                                                 ParameterMode parameter_mode) {
   DCHECK(barrier_mode == SKIP_WRITE_BARRIER ||
          barrier_mode == UPDATE_WRITE_BARRIER);
-  Node* offset =
-      ElementOffsetFromIndex(index_node, FAST_HOLEY_ELEMENTS, parameter_mode,
-                             FixedArray::kHeaderSize - kHeapObjectTag);
+  int header_size =
+      FixedArray::kHeaderSize + additional_offset - kHeapObjectTag;
+  Node* offset = ElementOffsetFromIndex(index_node, FAST_HOLEY_ELEMENTS,
+                                        parameter_mode, header_size);
   MachineRepresentation rep = MachineRepresentation::kTagged;
   if (barrier_mode == SKIP_WRITE_BARRIER) {
     return StoreNoWriteBarrier(rep, object, offset, value);
   } else {
     return Store(rep, object, offset, value);
   }
 }
 
 Node* CodeStubAssembler::StoreFixedDoubleArrayElement(
     Node* object, Node* index_node, Node* value, ParameterMode parameter_mode) {
@@ skipping 2674 matching lines @@
   Node* capacity = IntPtrRoundUpToPowerOfTwo32(
       WordShl(at_least_space_for, IntPtrConstant(1)));
   return IntPtrMax(capacity, IntPtrConstant(HashTableBase::kMinCapacity));
 }
 
 Node* CodeStubAssembler::IntPtrMax(Node* left, Node* right) {
   return Select(IntPtrGreaterThanOrEqual(left, right), left, right,
                 MachineType::PointerRepresentation());
 }
 
+template <class Dictionary>
+Node* CodeStubAssembler::GetNumberOfElements(Node* dictionary) {
+  return LoadFixedArrayElement(
+      dictionary, IntPtrConstant(Dictionary::kNumberOfElementsIndex), 0,
+      INTPTR_PARAMETERS);
+}
+
+template <class Dictionary>
+void CodeStubAssembler::SetNumberOfElements(Node* dictionary,
+                                            Node* num_elements_smi) {
+  StoreFixedArrayElement(dictionary, Dictionary::kNumberOfElementsIndex,
+                         num_elements_smi, SKIP_WRITE_BARRIER);
+}
+
+template <class Dictionary>
+Node* CodeStubAssembler::GetNumberOfDeletedElements(Node* dictionary) {
+  return LoadFixedArrayElement(
+      dictionary, IntPtrConstant(Dictionary::kNumberOfDeletedElementsIndex), 0,
+      INTPTR_PARAMETERS);
+}
+
+template <class Dictionary>
+Node* CodeStubAssembler::GetCapacity(Node* dictionary) {
+  return LoadFixedArrayElement(dictionary,
+                               IntPtrConstant(Dictionary::kCapacityIndex), 0,
+                               INTPTR_PARAMETERS);
+}
+
+template <class Dictionary>
+Node* CodeStubAssembler::GetNextEnumerationIndex(Node* dictionary) {
+  return LoadFixedArrayElement(
+      dictionary, IntPtrConstant(Dictionary::kNextEnumerationIndexIndex), 0,
+      INTPTR_PARAMETERS);
+}
+
+template <class Dictionary>
+void CodeStubAssembler::SetNextEnumerationIndex(Node* dictionary,
+                                                Node* next_enum_index_smi) {
+  StoreFixedArrayElement(dictionary, Dictionary::kNextEnumerationIndexIndex,
+                         next_enum_index_smi, SKIP_WRITE_BARRIER);
+}
+
 template <typename Dictionary>
 void CodeStubAssembler::NameDictionaryLookup(Node* dictionary,
                                              Node* unique_name, Label* if_found,
                                              Variable* var_name_index,
                                              Label* if_not_found,
-                                             int inlined_probes) {
+                                             int inlined_probes,
+                                             LookupMode mode) {
   CSA_ASSERT(this, IsDictionary(dictionary));
   DCHECK_EQ(MachineType::PointerRepresentation(), var_name_index->rep());
+  DCHECK_IMPLIES(mode == kFindInsertionIndex,
+                 inlined_probes == 0 && if_found == nullptr);
   Comment("NameDictionaryLookup");
 
-  Node* capacity = SmiUntag(LoadFixedArrayElement(
-      dictionary, IntPtrConstant(Dictionary::kCapacityIndex), 0,
-      INTPTR_PARAMETERS));
+  Node* capacity = SmiUntag(GetCapacity<Dictionary>(dictionary));
   Node* mask = IntPtrSub(capacity, IntPtrConstant(1));
   Node* hash = ChangeUint32ToWord(LoadNameHash(unique_name));
 
   // See Dictionary::FirstProbe().
   Node* count = IntPtrConstant(0);
   Node* entry = WordAnd(hash, mask);
 
   for (int i = 0; i < inlined_probes; i++) {
     Node* index = EntryToIndex<Dictionary>(entry);
     var_name_index->Bind(index);
 
     Node* current =
         LoadFixedArrayElement(dictionary, index, 0, INTPTR_PARAMETERS);
     GotoIf(WordEqual(current, unique_name), if_found);
 
     // See Dictionary::NextProbe().
     count = IntPtrConstant(i + 1);
     entry = WordAnd(IntPtrAdd(entry, count), mask);
   }
+  if (mode == kFindInsertionIndex) {
+    // Appease the variable merging algorithm for "Goto(&loop)" below.
+    var_name_index->Bind(IntPtrConstant(0));
+  }
 
   Node* undefined = UndefinedConstant();
+  Node* the_hole = mode == kFindExisting ? nullptr : TheHoleConstant();
 
   Variable var_count(this, MachineType::PointerRepresentation());
   Variable var_entry(this, MachineType::PointerRepresentation());
   Variable* loop_vars[] = {&var_count, &var_entry, var_name_index};
   Label loop(this, 3, loop_vars);
   var_count.Bind(count);
   var_entry.Bind(entry);
   Goto(&loop);
   Bind(&loop);
   {
     Node* count = var_count.value();
     Node* entry = var_entry.value();
 
     Node* index = EntryToIndex<Dictionary>(entry);
     var_name_index->Bind(index);
 
     Node* current =
         LoadFixedArrayElement(dictionary, index, 0, INTPTR_PARAMETERS);
     GotoIf(WordEqual(current, undefined), if_not_found);
-    GotoIf(WordEqual(current, unique_name), if_found);
+    if (mode == kFindExisting) {
+      GotoIf(WordEqual(current, unique_name), if_found);
+    } else {
+      DCHECK_EQ(kFindInsertionIndex, mode);
+      GotoIf(WordEqual(current, the_hole), if_not_found);
+    }
 
     // See Dictionary::NextProbe().
     count = IntPtrAdd(count, IntPtrConstant(1));
     entry = WordAnd(IntPtrAdd(entry, count), mask);
 
     var_count.Bind(count);
     var_entry.Bind(entry);
     Goto(&loop);
   }
 }
 
 // Instantiate template methods to workaround GCC compilation issue.
 template void CodeStubAssembler::NameDictionaryLookup<NameDictionary>(
-    Node*, Node*, Label*, Variable*, Label*, int);
+    Node*, Node*, Label*, Variable*, Label*, int, LookupMode);
 template void CodeStubAssembler::NameDictionaryLookup<GlobalDictionary>(
-    Node*, Node*, Label*, Variable*, Label*, int);
+    Node*, Node*, Label*, Variable*, Label*, int, LookupMode);
 
 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)));
   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* intptr_index,
                                                Label* if_found,
                                                Variable* var_entry,
                                                Label* if_not_found) {
   CSA_ASSERT(this, IsDictionary(dictionary));
   DCHECK_EQ(MachineType::PointerRepresentation(), var_entry->rep());
   Comment("NumberDictionaryLookup");
 
-  Node* capacity = SmiUntag(LoadFixedArrayElement(
-      dictionary, IntPtrConstant(Dictionary::kCapacityIndex), 0,
-      INTPTR_PARAMETERS));
+  Node* capacity = SmiUntag(GetCapacity<Dictionary>(dictionary));
   Node* mask = IntPtrSub(capacity, IntPtrConstant(1));
 
   Node* int32_seed;
   if (Dictionary::ShapeT::UsesSeed) {
     int32_seed = HashSeed();
   } else {
     int32_seed = Int32Constant(kZeroHashSeed);
   }
   Node* hash = ChangeUint32ToWord(ComputeIntegerHash(intptr_index, int32_seed));
   Node* key_as_float64 = RoundIntPtrToFloat64(intptr_index);
@@ skipping 43 matching lines @@
     // See Dictionary::NextProbe().
     count = IntPtrAdd(count, IntPtrConstant(1));
     entry = WordAnd(IntPtrAdd(entry, count), mask);
 
     var_count.Bind(count);
     var_entry->Bind(entry);
     Goto(&loop);
   }
 }
 
+template <class Dictionary>
+void CodeStubAssembler::FindInsertionEntry(Node* dictionary, Node* key,
+                                           Variable* var_key_index) {
+  UNREACHABLE();
+}
+
+template <>
+void CodeStubAssembler::FindInsertionEntry<NameDictionary>(
+    Node* dictionary, Node* key, Variable* var_key_index) {
+  Label done(this);
+  NameDictionaryLookup<NameDictionary>(dictionary, key, nullptr, var_key_index,
+                                       &done, 0, kFindInsertionIndex);
+  Bind(&done);
+}
+
+template <class Dictionary>
+void CodeStubAssembler::InsertEntry(Node* dictionary, Node* key, Node* value,
+                                    Node* index, Node* enum_index) {
+  UNREACHABLE();  // Use specializations instead.
+}
+
+template <>
+void CodeStubAssembler::InsertEntry<NameDictionary>(Node* dictionary,
+                                                    Node* name, Node* value,
+                                                    Node* index,
+                                                    Node* enum_index) {
+  // Store name and value.
+  StoreFixedArrayElement(dictionary, index, name, UPDATE_WRITE_BARRIER, 0,
+                         INTPTR_PARAMETERS);
+  const int kNameToValueOffset =
+      (NameDictionary::kEntryValueIndex - NameDictionary::kEntryKeyIndex) *
+      kPointerSize;
+  StoreFixedArrayElement(dictionary, index, value, UPDATE_WRITE_BARRIER,
+                         kNameToValueOffset, INTPTR_PARAMETERS);
+
+  // Prepare details of the new property.
+  Variable var_details(this, MachineRepresentation::kTaggedSigned);
+  const int kInitialIndex = 0;
+  PropertyDetails d(NONE, DATA, kInitialIndex, PropertyCellType::kNoCell);
+  enum_index =
+      WordShl(enum_index, PropertyDetails::DictionaryStorageField::kShift);
+  STATIC_ASSERT(kInitialIndex == 0);
+  var_details.Bind(WordOr(SmiConstant(d.AsSmi()), enum_index));
+
+  // Private names must be marked non-enumerable.
+  Label not_private(this, &var_details);
+  GotoUnless(IsSymbolMap(LoadMap(name)), &not_private);
+  Node* flags = SmiToWord32(LoadObjectField(name, Symbol::kFlagsOffset));
+  const int kPrivateMask = 1 << Symbol::kPrivateBit;
+  GotoUnless(IsSetWord32(flags, kPrivateMask), &not_private);
+  Node* dont_enum =
+      WordShl(SmiConstant(DONT_ENUM), PropertyDetails::AttributesField::kShift);
+  var_details.Bind(WordOr(var_details.value(), dont_enum));
+  Goto(&not_private);
+  Bind(&not_private);
+
+  // Finally, store the details.
+  const int kNameToDetailsOffset =
+      (NameDictionary::kEntryDetailsIndex - NameDictionary::kEntryKeyIndex) *
+      kPointerSize;
+  StoreFixedArrayElement(dictionary, index, var_details.value(),
+                         SKIP_WRITE_BARRIER, kNameToDetailsOffset,
+                         INTPTR_PARAMETERS);
+}
+
+template <>
+void CodeStubAssembler::InsertEntry<GlobalDictionary>(Node* dictionary,
+                                                      Node* key, Node* value,
+                                                      Node* index,
+                                                      Node* enum_index) {
+  UNIMPLEMENTED();
+}
+
+template <class Dictionary>
+void CodeStubAssembler::Add(Node* dictionary, Node* key, Node* value,
+                            Label* bailout) {
+  Node* capacity = GetCapacity<Dictionary>(dictionary);
+  Node* nof = GetNumberOfElements<Dictionary>(dictionary);
+  Node* new_nof = SmiAdd(nof, SmiConstant(1));
+  // Require 33% to still be free after adding additional_elements.
+  // Computing "x + (x >> 1)" on a Smi x does not return a valid Smi!
+  // But that's OK here because it's only used for a comparison.
+  Node* required_capacity_pseudo_smi = SmiAdd(new_nof, WordShr(new_nof, 1));
+  GotoIf(UintPtrLessThan(capacity, required_capacity_pseudo_smi), bailout);
+  // Require rehashing if more than 50% of free elements are deleted elements.
+  Node* deleted = GetNumberOfDeletedElements<Dictionary>(dictionary);
+  CSA_ASSERT(this, UintPtrGreaterThan(capacity, new_nof));
+  Node* half_of_free_elements = WordShr(SmiSub(capacity, new_nof), 1);
+  GotoIf(UintPtrGreaterThan(deleted, half_of_free_elements), bailout);
+  Node* enum_index = nullptr;
+  if (Dictionary::kIsEnumerable) {
+    enum_index = GetNextEnumerationIndex<Dictionary>(dictionary);
+    Node* new_enum_index = SmiAdd(enum_index, SmiConstant(1));
+    Node* max_enum_index =
+        SmiConstant(PropertyDetails::DictionaryStorageField::kMax);
+    GotoIf(UintPtrGreaterThan(new_enum_index, max_enum_index), bailout);
+
+    // No more bailouts after this point.
+    // Operations from here on can have side effects.
+
+    SetNextEnumerationIndex<Dictionary>(dictionary, new_enum_index);
+  } else {
+    USE(enum_index);
+  }
+  SetNumberOfElements<Dictionary>(dictionary, new_nof);
+
+  Variable var_key_index(this, MachineType::PointerRepresentation());
+  FindInsertionEntry<Dictionary>(dictionary, key, &var_key_index);
+  InsertEntry<Dictionary>(dictionary, key, value, var_key_index.value(),
+                          enum_index);
+}
+
+template void CodeStubAssembler::Add<NameDictionary>(Node*, Node*, Node*,
+                                                     Label*);
+
 void CodeStubAssembler::DescriptorLookupLinear(Node* unique_name,
                                                Node* descriptors, Node* nof,
                                                Label* if_found,
                                                Variable* var_name_index,
                                                Label* if_not_found) {
   Node* first_inclusive = IntPtrConstant(DescriptorArray::ToKeyIndex(0));
   Node* factor = IntPtrConstant(DescriptorArray::kDescriptorSize);
   Node* last_exclusive = IntPtrAdd(first_inclusive, IntPtrMul(nof, factor));
 
   BuildFastLoop(
@@ skipping 977 matching lines @@
     STATIC_ASSERT(Context::kHeaderSize == FixedArray::kHeaderSize);
     DCHECK_EQ(Context::SlotOffset(0) + kHeapObjectTag,
               FixedArray::OffsetOfElementAt(0));
     if (is_load) {
       Node* result = LoadFixedArrayElement(the_context, mapped_index, 0,
                                            INTPTR_PARAMETERS);
       CSA_ASSERT(this, WordNotEqual(result, TheHoleConstant()));
       var_result.Bind(result);
     } else {
       StoreFixedArrayElement(the_context, mapped_index, value,
-                             UPDATE_WRITE_BARRIER, INTPTR_PARAMETERS);
+                             UPDATE_WRITE_BARRIER, 0, INTPTR_PARAMETERS);
     }
     Goto(&end);
   }
 
   Bind(&if_unmapped);
   {
     Node* backing_store = LoadFixedArrayElement(elements, IntPtrConstant(1), 0,
                                                 INTPTR_PARAMETERS);
     GotoIf(WordNotEqual(LoadMap(backing_store), FixedArrayMapConstant()),
            bailout);
 
     Node* backing_store_length =
         LoadAndUntagFixedArrayBaseLength(backing_store);
     GotoIf(UintPtrGreaterThanOrEqual(key, backing_store_length), bailout);
 
     // The key falls into unmapped range.
     if (is_load) {
       Node* result =
           LoadFixedArrayElement(backing_store, key, 0, INTPTR_PARAMETERS);
       GotoIf(WordEqual(result, TheHoleConstant()), bailout);
       var_result.Bind(result);
     } else {
-      StoreFixedArrayElement(backing_store, key, value, UPDATE_WRITE_BARRIER,
+      StoreFixedArrayElement(backing_store, key, value, UPDATE_WRITE_BARRIER, 0,
                              INTPTR_PARAMETERS);
     }
     Goto(&end);
   }
 
   Bind(&end);
   return var_result.value();
 }
 
 Node* CodeStubAssembler::LoadScriptContext(Node* context, int context_index) {
@@ skipping 62 matching lines @@
     return;
   }
 
   WriteBarrierMode barrier_mode =
       IsFastSmiElementsKind(kind) ? SKIP_WRITE_BARRIER : UPDATE_WRITE_BARRIER;
   if (IsFastDoubleElementsKind(kind)) {
     // Make sure we do not store signalling NaNs into double arrays.
     value = Float64SilenceNaN(value);
     StoreFixedDoubleArrayElement(elements, index, value, mode);
   } else {
-    StoreFixedArrayElement(elements, index, value, barrier_mode, mode);
+    StoreFixedArrayElement(elements, index, value, barrier_mode, 0, mode);
   }
 }
 
 void CodeStubAssembler::EmitElementStore(Node* object, Node* key, Node* value,
                                          bool is_jsarray,
                                          ElementsKind elements_kind,
                                          KeyedAccessStoreMode store_mode,
                                          Label* bailout) {
   Node* elements = LoadElements(object);
   if (IsFastSmiOrObjectElementsKind(elements_kind) &&
@@ skipping 371 matching lines @@
   Node* next_site = LoadBufferObject(site_list, 0);
 
   // TODO(mvstanton): This is a store to a weak pointer, which we may want to
   // mark as such in order to skip the write barrier, once we have a unified
   // system for weakness. For now we decided to keep it like this because having
   // an initial write barrier backed store makes this pointer strong until the
   // next GC, and allocation sites are designed to survive several GCs anyway.
   StoreObjectField(site, AllocationSite::kWeakNextOffset, next_site);
   StoreNoWriteBarrier(MachineRepresentation::kTagged, site_list, site);
 
-  StoreFixedArrayElement(feedback_vector, slot, site, UPDATE_WRITE_BARRIER,
+  StoreFixedArrayElement(feedback_vector, slot, site, UPDATE_WRITE_BARRIER, 0,
                          CodeStubAssembler::SMI_PARAMETERS);
   return site;
 }
 
 Node* CodeStubAssembler::CreateWeakCellInFeedbackVector(Node* feedback_vector,
                                                         Node* slot,
                                                         Node* value) {
   Node* size = IntPtrConstant(WeakCell::kSize);
   Node* cell = Allocate(size, CodeStubAssembler::kPretenured);
 
   // Initialize the WeakCell.
   StoreObjectFieldRoot(cell, WeakCell::kMapOffset, Heap::kWeakCellMapRootIndex);
   StoreObjectField(cell, WeakCell::kValueOffset, value);
   StoreObjectFieldRoot(cell, WeakCell::kNextOffset,
                        Heap::kTheHoleValueRootIndex);
 
   // Store the WeakCell in the feedback vector.
-  StoreFixedArrayElement(feedback_vector, slot, cell, UPDATE_WRITE_BARRIER,
+  StoreFixedArrayElement(feedback_vector, slot, cell, UPDATE_WRITE_BARRIER, 0,
                          CodeStubAssembler::SMI_PARAMETERS);
   return cell;
 }
 
 void CodeStubAssembler::BuildFastLoop(
     const CodeStubAssembler::VariableList& vars,
     MachineRepresentation index_rep, Node* start_index, Node* end_index,
     std::function<void(CodeStubAssembler* assembler, Node* index)> body,
     int increment, IndexAdvanceMode mode) {
   Variable var(this, index_rep);
@@ skipping 1987 matching lines @@
 
 compiler::Node* CodeStubAssembler::IsDebugActive() {
   Node* is_debug_active = Load(
       MachineType::Uint8(),
       ExternalConstant(ExternalReference::debug_is_active_address(isolate())));
   return WordNotEqual(is_debug_active, Int32Constant(0));
 }
 
 }  // namespace internal
 }  // namespace v8