In-place shrinking of descriptor arrays with non-live transitions.

src/objects.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 622 matching lines @@
           receiver, result->GetCallbackObject(), name);
     case HANDLER:
       return result->proxy()->GetPropertyWithHandler(receiver, name);
     case INTERCEPTOR: {
       JSObject* recvr = JSObject::cast(receiver);
       return result->holder()->GetPropertyWithInterceptor(
           recvr, name, attributes);
     }
     case MAP_TRANSITION:
     case CONSTANT_TRANSITION:
-    case NULL_DESCRIPTOR:
+      break;
+    case NONEXISTENT:
+      UNREACHABLE();
       break;
   }
   UNREACHABLE();
   return NULL;
 }
 
 
 MaybeObject* Object::GetElementWithReceiver(Object* receiver, uint32_t index) {
   Heap* heap = IsSmi()
       ? Isolate::Current()->heap()
@@ skipping 1492 matching lines @@
         *done = true;
         return SetPropertyWithCallback(result.GetCallbackObject(),
             name, value, result.holder(), strict_mode);
       }
       case HANDLER: {
         return result.proxy()->SetPropertyViaPrototypesWithHandler(
             this, name, value, attributes, strict_mode, done);
       }
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
-      case NULL_DESCRIPTOR:
+        break;
+      case NONEXISTENT:
+        UNREACHABLE();
         break;
     }
   }
 
   // If we get here with *done true, we have encountered a read-only property.
   if (!FLAG_es5_readonly) *done = false;
   if (*done) {
     if (strict_mode == kNonStrictMode) return value;
     Handle<Object> args[] = { Handle<Object>(name), Handle<Object>(this)};
     return isolate->Throw(*isolate->factory()->NewTypeError(
@@ skipping 761 matching lines @@
       JSFunction* function =
           JSFunction::cast(target_descriptors->GetValue(number));
       if (value == function) {
         set_map(target_map);
         return value;
       }
       // Otherwise, replace with a MAP_TRANSITION to a new map with a
       // FIELD, even if the value is a constant function.
       return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     }
-    case NULL_DESCRIPTOR:
-      return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     case HANDLER:
+    case NONEXISTENT:
       UNREACHABLE();
       return value;
   }
   UNREACHABLE();  // keep the compiler happy
   return value;
 }
 
 
 // Set a real local property, even if it is READ_ONLY.  If the property is not
 // present, add it with attributes NONE.  This code is an exact clone of
@@ skipping 75 matching lines @@
       // Preserve the attributes of this existing property.
       attributes = result.GetAttributes();
       return ConvertDescriptorToField(name, value, attributes);
     case CALLBACKS:
     case INTERCEPTOR:
       // Override callback in clone
       return ConvertDescriptorToField(name, value, attributes);
     case CONSTANT_TRANSITION:
       // Replace with a MAP_TRANSITION to a new map with a FIELD, even
       // if the value is a function.
-    case NULL_DESCRIPTOR:
       return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     case HANDLER:
+    case NONEXISTENT:
       UNREACHABLE();
   }
   UNREACHABLE();  // keep the compiler happy
   return value;
 }
 
 
 PropertyAttributes JSObject::GetPropertyAttributePostInterceptor(
       JSObject* receiver,
       String* name,
@@ skipping 272 matching lines @@
               AccessorPair::cast(value)->CopyWithoutTransitions();
           if (!maybe_copy->To(&value)) return maybe_copy;
         }
         MaybeObject* maybe_dictionary =
             dictionary->Add(descs->GetKey(i), value, details);
         if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
         break;
       }
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
-      case NULL_DESCRIPTOR:
       case INTERCEPTOR:
         break;
       case HANDLER:
       case NORMAL:
+      case NONEXISTENT:
         UNREACHABLE();
         break;
     }
   }
 
   Heap* current_heap = GetHeap();
 
   // Copy the next enumeration index from instance descriptor.
   int index = map_of_this->instance_descriptors()->NextEnumerationIndex();
   dictionary->SetNextEnumerationIndex(index);
@@ skipping 323 matching lines @@
     // hidden symbols hash code is zero (and no other string has hash
     // code zero) it will always occupy the first entry if present.
     DescriptorArray* descriptors = this->map()->instance_descriptors();
     if ((descriptors->number_of_descriptors() > 0) &&
         (descriptors->GetKey(0) == GetHeap()->hidden_symbol())) {
       if (descriptors->GetType(0) == FIELD) {
         Object* hidden_store =
             this->FastPropertyAt(descriptors->GetFieldIndex(0));
         return StringDictionary::cast(hidden_store);
       } else {
-        ASSERT(descriptors->GetType(0) == NULL_DESCRIPTOR ||
-               descriptors->GetType(0) == MAP_TRANSITION);
+        ASSERT(descriptors->GetType(0) == MAP_TRANSITION);
       }
     }
   } else {
     PropertyAttributes attributes;
     // You can't install a getter on a property indexed by the hidden symbol,
     // so we can be sure that GetLocalPropertyPostInterceptor returns a real
     // object.
     Object* lookup =
         GetLocalPropertyPostInterceptor(this,
                                         GetHeap()->hidden_symbol(),
@@ skipping 27 matching lines @@
     // in the descriptor array matches the hidden symbol. Since the
     // hidden symbols hash code is zero (and no other string has hash
     // code zero) it will always occupy the first entry if present.
     DescriptorArray* descriptors = this->map()->instance_descriptors();
     if ((descriptors->number_of_descriptors() > 0) &&
         (descriptors->GetKey(0) == GetHeap()->hidden_symbol())) {
       if (descriptors->GetType(0) == FIELD) {
         this->FastPropertyAtPut(descriptors->GetFieldIndex(0), dictionary);
         return this;
       } else {
-        ASSERT(descriptors->GetType(0) == NULL_DESCRIPTOR ||
-               descriptors->GetType(0) == MAP_TRANSITION);
+        ASSERT(descriptors->GetType(0) == MAP_TRANSITION);
       }
     }
   }
   MaybeObject* store_result =
       SetPropertyPostInterceptor(GetHeap()->hidden_symbol(),
                                  dictionary,
                                  DONT_ENUM,
                                  kNonStrictMode,
                                  OMIT_EXTENSIBILITY_CHECK);
   if (store_result->IsFailure()) return store_result;
@@ skipping 426 matching lines @@
       result++;
     }
   }
   return result;
 }
 
 
 int Map::PropertyIndexFor(String* name) {
   DescriptorArray* descs = instance_descriptors();
   for (int i = 0; i < descs->number_of_descriptors(); i++) {
-    if (name->Equals(descs->GetKey(i)) && !descs->IsNullDescriptor(i)) {
-      return descs->GetFieldIndex(i);
-    }
+    if (name->Equals(descs->GetKey(i))) return descs->GetFieldIndex(i);
   }
   return -1;
 }
 
 
 int Map::NextFreePropertyIndex() {
   int max_index = -1;
   DescriptorArray* descs = instance_descriptors();
   for (int i = 0; i < descs->number_of_descriptors(); i++) {
     if (descs->GetType(i) == FIELD) {
@@ skipping 886 matching lines @@
             *DescriptorArrayHeader() = Smi::FromInt(raw_index);
             return static_cast<Map*>(accessor);
           }
           break;
         }
         case NORMAL:
         case FIELD:
         case CONSTANT_FUNCTION:
         case HANDLER:
         case INTERCEPTOR:
-        case NULL_DESCRIPTOR:
           // We definitely have no map transition.
           raw_index += 2;
           ++index;
           break;
+        case NONEXISTENT:
+          UNREACHABLE();
+          break;
       }
     }
     if (index == descriptor_array_->number_of_descriptors()) {
       Map* elements_transition = descriptor_array_->elements_transition_map();
       if (elements_transition != NULL) {
         *DescriptorArrayHeader() = Smi::FromInt(raw_index + 2);
         return elements_transition;
       }
     }
     *DescriptorArrayHeader() = descriptor_array_->GetHeap()->fixed_array_map();
@@ skipping 769 matching lines @@
 
 MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
                                          TransitionFlag transition_flag) {
   // Transitions are only kept when inserting another transition.
   // This precondition is not required by this function's implementation, but
   // is currently required by the semantics of maps, so we check it.
   // Conversely, we filter after replacing, so replacing a transition and
   // removing all other transitions is not supported.
   bool remove_transitions = transition_flag == REMOVE_TRANSITIONS;
   ASSERT(remove_transitions == !descriptor->ContainsTransition());
-  ASSERT(descriptor->GetDetails().type() != NULL_DESCRIPTOR);
 
   // Ensure the key is a symbol.
   { MaybeObject* maybe_result = descriptor->KeyToSymbol();
     if (maybe_result->IsFailure()) return maybe_result;
   }
 
   int new_size = 0;
   for (int i = 0; i < number_of_descriptors(); i++) {
-    if (IsNullDescriptor(i)) continue;
     if (remove_transitions && IsTransitionOnly(i)) continue;
     new_size++;
   }
 
   // If key is in descriptor, we replace it in-place when filtering.
   // Count a null descriptor for key as inserted, not replaced.
   int index = Search(descriptor->GetKey());
   const bool replacing = (index != kNotFound);
   bool keep_enumeration_index = false;
   if (!replacing) {
@@ skipping 37 matching lines @@
   // and inserting or replacing a descriptor.
   int to_index = 0;
   int insertion_index = -1;
   int from_index = 0;
   while (from_index < number_of_descriptors()) {
     if (insertion_index < 0 &&
         InsertionPointFound(GetKey(from_index), descriptor->GetKey())) {
       insertion_index = to_index++;
       if (replacing) from_index++;
     } else {
-      if (!(IsNullDescriptor(from_index) ||
-            (remove_transitions && IsTransitionOnly(from_index)))) {
+      if (!(remove_transitions && IsTransitionOnly(from_index))) {
         MaybeObject* copy_result =
             new_descriptors->CopyFrom(to_index++, this, from_index, witness);
         if (copy_result->IsFailure()) return copy_result;
       }
       from_index++;
     }
   }
   if (insertion_index < 0) insertion_index = to_index++;
 
   ASSERT(insertion_index < new_descriptors->number_of_descriptors());
@@ skipping 109 matching lines @@
     uint32_t mid_hash = mid_name->Hash();
 
     if (mid_hash >= hash) {
       high = mid;
     } else {
       low = mid + 1;
     }
   }
 
   for (; low <= limit && GetKey(low)->Hash() == hash; ++low) {
-    if (GetKey(low)->Equals(name) && !IsNullDescriptor(low))
-      return low;
+    if (GetKey(low)->Equals(name)) return low;
   }
 
   return kNotFound;
 }
 
 
 int DescriptorArray::LinearSearch(SearchMode mode, String* name, int len) {
   uint32_t hash = name->Hash();
   for (int number = 0; number < len; number++) {
     String* entry = GetKey(number);
     if (mode == EXPECT_SORTED && entry->Hash() > hash) break;
-    if (name->Equals(entry) && !IsNullDescriptor(number)) {
-      return number;
-    }
+    if (name->Equals(entry)) return number;
   }
   return kNotFound;
 }
 
 
 MaybeObject* AccessorPair::CopyWithoutTransitions() {
   Heap* heap = GetHeap();
   AccessorPair* copy;
   { MaybeObject* maybe_copy = heap->AllocateAccessorPair();
     if (!maybe_copy->To(&copy)) return maybe_copy;
@@ skipping 1238 matching lines @@
 // Return true in case a back pointer has been cleared and false otherwise.
 static bool ClearBackPointer(Heap* heap, Object* target) {
   ASSERT(target->IsMap());
   Map* map = Map::cast(target);
   if (Marking::MarkBitFrom(map).Get()) return false;
   map->SetBackPointer(heap->undefined_value(), SKIP_WRITE_BARRIER);
   return true;
 }
 
 
+// This function should only be called from within the GC, since it uses
+// IncrementLiveBytesFromGC. If called from anywhere else, this results in an
+// inconsistent live-bytes count.
+static void RightTrimFixedArray(Heap* heap, FixedArray* elms, int to_trim) {
+  ASSERT(elms->map() != HEAP->fixed_cow_array_map());
+  // For now this trick is only applied to fixed arrays in new and paged space.
+  // In large object space the object's start must coincide with chunk
+  // and thus the trick is just not applicable.
+  ASSERT(!HEAP->lo_space()->Contains(elms));
+
+  const int len = elms->length();
+
+  ASSERT(to_trim < len);
+
+  Address new_end = elms->address() + FixedArray::SizeFor(len - to_trim);
+
+#ifdef DEBUG
+  if (to_trim > FixedArray::kHeaderSize / kPointerSize &&
+      !heap->InNewSpace(elms)) {

[Michael Starzinger, 2012/06/25 12:48:38]

Since it's debug code now, I think we should just unconditionally zap, no matter
how much we trim or in which space we trim.

+    // If we are doing a big trim in old space then we zap the space.
+    Object** zap = reinterpret_cast<Object**>(new_end);
+    zap++;  // Header of filler must be at least one word so skip that.

[Michael Starzinger, 2012/06/25 12:48:38]

Using the same reasoning, I think we should also just zap the first word.

+    for (int i = 1; i < to_trim; i++) {
+      *zap++ = Smi::FromInt(0);
+    }
+  }
+#endif
+
+  int size_delta = to_trim * kPointerSize;
+
+  // Technically in new space this write might be omitted (except for
+  // debug mode which iterates through the heap), but to play safer
+  // we still do it.
+  heap->CreateFillerObjectAt(new_end, size_delta);
+
+  elms->set_length(len - to_trim);
+
+  // Maintain marking consistency for IncrementalMarking.
+  if (Marking::IsBlack(Marking::MarkBitFrom(elms))) {
+    MemoryChunk::IncrementLiveBytesFromGC(elms->address(), -size_delta);
+  }
+}
+
+
+static bool ClearNonLiveTransitionsFromDescriptor(Heap* heap,

[Michael Starzinger, 2012/06/25 12:48:38]

Add a comment describing the semantics of the return value.

+                                                  DescriptorArray* d,
+                                                  int descriptor_index) {
+  // If the pair (value, details) is a map transition, check if the target is
+  // live. If not, null the descriptor. Also drop the back pointer for that
+  // map transition, so that this map is not reached again by following a back
+  // pointer from that non-live map.
+  PropertyDetails details(d->GetDetails(descriptor_index));
+  switch (details.type()) {
+    case MAP_TRANSITION:
+    case CONSTANT_TRANSITION:
+      return ClearBackPointer(heap, d->GetValue(descriptor_index));
+    case CALLBACKS: {
+      Object* object = d->GetValue(descriptor_index);
+      if (object->IsAccessorPair()) {
+        bool cleared = true;
+        AccessorPair* accessors = AccessorPair::cast(object);
+        Object* getter = accessors->getter();
+        if (getter->IsMap()) {
+          if (ClearBackPointer(heap, getter)) {
+            accessors->set_getter(heap->the_hole_value());
+          } else {
+            cleared = false;
+          }
+        } else if (!getter->IsTheHole()) {
+          cleared = false;
+        }
+        Object* setter = accessors->setter();
+        if (setter->IsMap()) {
+          if (ClearBackPointer(heap, setter)) {
+            accessors->set_setter(heap->the_hole_value());
+          } else {
+            cleared = false;
+          }
+        } else if (!setter->IsTheHole()) {
+          cleared = false;
+        }
+        return cleared;
+      }
+      return false;
+    }
+    case NORMAL:
+    case FIELD:
+    case CONSTANT_FUNCTION:
+    case HANDLER:
+    case INTERCEPTOR:
+      return false;
+    case NONEXISTENT:
+      break;
+  }
+  UNREACHABLE();
+  return true;
+}
+
+
 void Map::ClearNonLiveTransitions(Heap* heap) {
-  DescriptorArray* d = DescriptorArray::cast(
-      *RawField(this, Map::kInstanceDescriptorsOrBitField3Offset));
-  if (d->IsEmpty()) return;
+  Object* array = *RawField(this, Map::kInstanceDescriptorsOrBitField3Offset);
+  // If there are no descriptors to be cleared, return.
+  // TODO(verwaest) Should be an assert, otherwise back pointers are not
+  // properly cleared.
+  if (array->IsSmi()) return;
+  DescriptorArray* d = DescriptorArray::cast(array);
+
+  int descriptor_index = 0;
+  // Compact all live descriptors to the left.
+  for (int i = 0; i < d->number_of_descriptors(); ++i) {
+    if (!ClearNonLiveTransitionsFromDescriptor(heap, d, i)) {
+      if (i != descriptor_index) {
+        d->SetKeyUnchecked(heap, descriptor_index, d->GetKey(i));
+        d->SetDetailsUnchecked(descriptor_index, d->GetDetails(i).AsSmi());
+        d->SetValueUnchecked(heap, descriptor_index, d->GetValue(i));
+      }
+      descriptor_index++;
+    }
+  }
+
   Map* elements_transition = d->elements_transition_map();
   if (elements_transition != NULL &&
       ClearBackPointer(heap, elements_transition)) {
+    elements_transition = NULL;
     d->ClearElementsTransition();
+  } else {
+    // If there are no descriptors to be cleared, return.
+    // TODO(verwaest) Should be an assert, otherwise back pointers are not
+    // properly cleared.
+    if (descriptor_index == d->number_of_descriptors()) return;
   }
-  Smi* NullDescriptorDetails =
-    PropertyDetails(NONE, NULL_DESCRIPTOR).AsSmi();
-  for (int i = 0; i < d->number_of_descriptors(); ++i) {
-    // If the pair (value, details) is a map transition, check if the target is
-    // live. If not, null the descriptor. Also drop the back pointer for that
-    // map transition, so that this map is not reached again by following a back
-    // pointer from that non-live map.
-    bool keep_entry = false;
-    PropertyDetails details(d->GetDetails(i));
-    switch (details.type()) {
-      case MAP_TRANSITION:
-      case CONSTANT_TRANSITION:
-        keep_entry = !ClearBackPointer(heap, d->GetValue(i));
-        break;
-      case CALLBACKS: {
-        Object* object = d->GetValue(i);
-        if (object->IsAccessorPair()) {
-          AccessorPair* accessors = AccessorPair::cast(object);
-          Object* getter = accessors->getter();
-          if (getter->IsMap()) {
-            if (ClearBackPointer(heap, getter)) {
-              accessors->set_getter(heap->the_hole_value());
-            } else {
-              keep_entry = true;
-            }
-          } else if (!getter->IsTheHole()) {
-            keep_entry = true;
-          }
-          Object* setter = accessors->setter();
-          if (setter->IsMap()) {
-            if (ClearBackPointer(heap, setter)) {
-              accessors->set_setter(heap->the_hole_value());
-            } else {
-              keep_entry = true;
-            }
-          } else if (!setter->IsTheHole()) {
-            keep_entry = true;
-          }
-        } else {
-          keep_entry = true;
-        }
-        break;
-      }
-      case NORMAL:
-      case FIELD:
-      case CONSTANT_FUNCTION:
-      case HANDLER:
-      case INTERCEPTOR:
-      case NULL_DESCRIPTOR:
-        keep_entry = true;
-        break;
-    }
-    // Make sure that an entry containing only dead transitions gets collected.
-    // What we *really* want to do here is removing this entry completely, but
-    // for technical reasons we can't do this, so we zero it out instead.
-    if (!keep_entry) {
-      d->SetDetailsUnchecked(i, NullDescriptorDetails);
-      d->SetNullValueUnchecked(i, heap);
-    }
+
+  // If the final descriptor array does not contain any live descriptors, remove
+  // the descriptor array from the map.
+  if (descriptor_index == 0 && elements_transition == NULL) {
+    ClearDescriptorArray();
+    return;
+  }
+
+  int trim = d->number_of_descriptors() - descriptor_index;
+  if (trim > 0) {
+    RightTrimFixedArray(heap, d, trim * DescriptorArray::kDescriptorSize);
   }
 }
 
 
 int Map::Hash() {
   // For performance reasons we only hash the 3 most variable fields of a map:
   // constructor, prototype and bit_field2.
 
   // Shift away the tag.
   int hash = (static_cast<uint32_t>(
@@ skipping 1108 matching lines @@
 const char* Code::PropertyType2String(PropertyType type) {
   switch (type) {
     case NORMAL: return "NORMAL";
     case FIELD: return "FIELD";
     case CONSTANT_FUNCTION: return "CONSTANT_FUNCTION";
     case CALLBACKS: return "CALLBACKS";
     case HANDLER: return "HANDLER";
     case INTERCEPTOR: return "INTERCEPTOR";
     case MAP_TRANSITION: return "MAP_TRANSITION";
     case CONSTANT_TRANSITION: return "CONSTANT_TRANSITION";
-    case NULL_DESCRIPTOR: return "NULL_DESCRIPTOR";
+    case NONEXISTENT:
+      UNREACHABLE();
+      break;
   }
   UNREACHABLE();  // keep the compiler happy
   return NULL;
 }
 
 
 void Code::PrintExtraICState(FILE* out, Kind kind, ExtraICState extra) {
   const char* name = NULL;
   switch (kind) {
     case CALL_IC:
@@ skipping 2678 matching lines @@
       Object* value = ValueAt(entry);
       if (!value->IsAccessorPair()) return false;
       AccessorPair* accessors = AccessorPair::cast(value);
       return accessors->getter()->IsMap() || accessors->setter()->IsMap();
     }
     case NORMAL:
     case FIELD:
     case CONSTANT_FUNCTION:
     case HANDLER:
     case INTERCEPTOR:
-    case NULL_DESCRIPTOR:
       return false;
+    case NONEXISTENT:
+      UNREACHABLE();
+      break;
   }
   UNREACHABLE();  // Keep the compiler happy.
   return false;
 }
 
 
 template<typename Shape, typename Key>
 MaybeObject* HashTable<Shape, Key>::Rehash(HashTable* new_table, Key key) {
   ASSERT(NumberOfElements() < new_table->Capacity());
 
@@ skipping 2020 matching lines @@
   set_year(Smi::FromInt(year), SKIP_WRITE_BARRIER);
   set_month(Smi::FromInt(month), SKIP_WRITE_BARRIER);
   set_day(Smi::FromInt(day), SKIP_WRITE_BARRIER);
   set_weekday(Smi::FromInt(weekday), SKIP_WRITE_BARRIER);
   set_hour(Smi::FromInt(hour), SKIP_WRITE_BARRIER);
   set_min(Smi::FromInt(min), SKIP_WRITE_BARRIER);
   set_sec(Smi::FromInt(sec), SKIP_WRITE_BARRIER);
 }
 
 } }  // namespace v8::internal