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

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 9dbe849b0c726b99ff53efcdd189b2f0b62b37ce..a710d8a452e44a70abd3e3639edb178a71b7ee05 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -640,7 +640,9 @@ MaybeObject* Object::GetProperty(Object* receiver,
     }
     case MAP_TRANSITION:
     case CONSTANT_TRANSITION:
-    case NULL_DESCRIPTOR:
+      break;
+    case NONEXISTENT:
+      UNREACHABLE();
       break;
   }
   UNREACHABLE();
@@ -2153,7 +2155,9 @@ MaybeObject* JSObject::SetPropertyViaPrototypes(
       }
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
-      case NULL_DESCRIPTOR:
+        break;
+      case NONEXISTENT:
+        UNREACHABLE();
         break;
     }
   }
@@ -2935,9 +2939,8 @@ MaybeObject* JSObject::SetPropertyForResult(LookupResult* result,
       // 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;
   }
@@ -3033,9 +3036,9 @@ MaybeObject* JSObject::SetLocalPropertyIgnoreAttributes(
     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
@@ -3328,11 +3331,11 @@ MaybeObject* JSObject::NormalizeProperties(PropertyNormalizationMode mode,
       }
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
-      case NULL_DESCRIPTOR:
       case INTERCEPTOR:
         break;
       case HANDLER:
       case NORMAL:
+      case NONEXISTENT:
         UNREACHABLE();
         break;
     }
@@ -3676,8 +3679,7 @@ MaybeObject* JSObject::GetHiddenPropertiesDictionary(bool create_if_absent) {
             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 {
@@ -3725,8 +3727,7 @@ MaybeObject* JSObject::SetHiddenPropertiesDictionary(
         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);
       }
     }
   }
@@ -4173,9 +4174,7 @@ int Map::NumberOfDescribedProperties(PropertyAttributes filter) {
 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;
 }
@@ -5082,11 +5081,13 @@ class IntrusiveMapTransitionIterator {
         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()) {
@@ -5876,7 +5877,6 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
   // 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();
@@ -5885,7 +5885,6 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
 
   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++;
   }
@@ -5943,8 +5942,7 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
       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;
@@ -6074,8 +6072,7 @@ int DescriptorArray::BinarySearch(String* name, int low, int high) {
   }
 
   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;
@@ -6087,9 +6084,7 @@ int DescriptorArray::LinearSearch(SearchMode mode, String* name, int len) {
   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;
 }
@@ -7348,75 +7343,152 @@ static bool ClearBackPointer(Heap* heap, Object* target) {
 }
 
 
-void Map::ClearNonLiveTransitions(Heap* heap) {
-  DescriptorArray* d = DescriptorArray::cast(
-      *RawField(this, Map::kInstanceDescriptorsOrBitField3Offset));
-  if (d->IsEmpty()) return;
-  Map* elements_transition = d->elements_transition_map();
-  if (elements_transition != NULL &&
-      ClearBackPointer(heap, elements_transition)) {
-    d->ClearElementsTransition();
+static void RightTrimFixedArray(Heap* heap, FixedArray* elms, int to_trim) {

[Michael Starzinger, 2012/06/25 11:21:57]

Add a comment that this function is only called from within the GC. Otherwise
the live-bytes counter will be inconsistent.

[Toon Verwaest, 2012/06/25 12:20:48]

Done.

+  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));
+
+  STATIC_ASSERT(FixedArray::kMapOffset == 0);
+  STATIC_ASSERT(FixedArray::kLengthOffset == kPointerSize);
+  STATIC_ASSERT(FixedArray::kHeaderSize == 2 * kPointerSize);

[Michael Starzinger, 2012/06/25 11:21:57]

These asserts are not needed for left-trimming!

[Toon Verwaest, 2012/06/25 12:20:48]

Done.

+
+  const int len = elms->length();

[Michael Starzinger, 2012/06/25 11:21:57]

Add an ASSERT(to_trim < len), other cases aren't handled correctly here.

[Toon Verwaest, 2012/06/25 12:20:48]

Done.

+
+  Address new_end = elms->address() + FixedArray::kHeaderSize +

[Michael Starzinger, 2012/06/25 11:21:57]

Better use "elms->address() + FixedArray::SizeFor(len - to_trim)" here.

[Toon Verwaest, 2012/06/25 12:20:48]

Done.

+      (len - to_trim) * kPointerSize;
+  if (to_trim > FixedArray::kHeaderSize / kPointerSize &&

[Michael Starzinger, 2012/06/25 11:21:57]

This condition doesn't make much sense to me. And as discussed offline, the
zapping is probably only needed for debug mode with the new GC.

[Toon Verwaest, 2012/06/25 12:20:48]

Done.

+      !heap->InNewSpace(elms)) {
+    // If we are doing a big trim in old space then we zap the space that was
+    // formerly part of the array so that the GC (aided by the card-based

[Michael Starzinger, 2012/06/25 11:21:57]

Comment no longer applies.

[Toon Verwaest, 2012/06/25 12:20:48]

Done.

+    // remembered set) won't find pointers to new-space there.
+    Object** zap = reinterpret_cast<Object**>(new_end);
+    zap++;  // Header of filler must be at least one word so skip that.
+    for (int i = 1; i < to_trim; i++) {
+      *zap++ = Smi::FromInt(0);
+    }
   }
-  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;
+
+  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 ClearDescriptor(Heap* heap,

[Michael Starzinger, 2012/06/25 11:21:57]

We should give this function the "ClearNonLive" prefix as well. How about
"ClearNonLiveTransitionsFromDescriptor"?

Also a comment describing the semantics of the return value would nice.

[Toon Verwaest, 2012/06/25 12:20:48]

Done.

+                            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;
           }
-          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 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 {
-          keep_entry = true;
+        } else if (!setter->IsTheHole()) {
+          cleared = false;
         }
-        break;
+        return cleared;
       }
-      case NORMAL:
-      case FIELD:
-      case CONSTANT_FUNCTION:
-      case HANDLER:
-      case INTERCEPTOR:
-      case NULL_DESCRIPTOR:
-        keep_entry = true;
-        break;
+      return false;
     }
-    // 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);
+    case NORMAL:
+    case FIELD:
+    case CONSTANT_FUNCTION:
+    case HANDLER:
+    case INTERCEPTOR:
+      return false;
+    case NONEXISTENT:
+      break;
+  }
+  UNREACHABLE();
+  return true;
+}
+
+
+void Map::ClearNonLiveTransitions(Heap* heap) {
+  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;
+  // Find the first descriptor that can be cleared.
+  while (descriptor_index < d->number_of_descriptors() &&

[Michael Starzinger, 2012/06/25 11:21:57]

Is there a strong reason why this loop is split into two parts and interleaved
with the clearing of elements transitions? Is seems overly complicated. Can we
merge these two loops into one?

[Toon Verwaest, 2012/06/25 12:20:48]

Done.

+         !ClearDescriptor(heap, d, descriptor_index)) {
+        ++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;
+  }
+
+  // Compact all live descriptors to the left.
+  for (int i = descriptor_index + 1; i < d->number_of_descriptors(); ++i) {
+    if (!ClearDescriptor(heap, d, i)) {
+      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++;
     }
   }
+
+  // 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) {
+    SetOwnBitField3(d->bit_field3_storage());
+    return;
+  }
+
+  int trim = d->number_of_descriptors() - descriptor_index;
+  if (trim > 0) {
+    RightTrimFixedArray(heap, d, trim * DescriptorArray::kDescriptorSize);
+  }
 }
 
 
@@ -8544,7 +8616,9 @@ const char* Code::PropertyType2String(PropertyType type) {
     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;
@@ -11243,8 +11317,10 @@ bool StringDictionary::ContainsTransition(int entry) {
     case CONSTANT_FUNCTION:
     case HANDLER:
     case INTERCEPTOR:
-    case NULL_DESCRIPTOR:
       return false;
+    case NONEXISTENT:
+      UNREACHABLE();
+      break;
   }
   UNREACHABLE();  // Keep the compiler happy.
   return false;