Add infrastructure to keep track of references to prototypes.

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 15fdce65d98a63d8a89c1edbc474e818ec634ee3..b86a42e6fe3170049113e8173ebb7e32b59b5334 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -3064,9 +3064,8 @@ MaybeHandle<Object> Object::SetDataProperty(LookupIterator* it,
   // Old value for the observation change record.
   // Fetch before transforming the object since the encoding may become
   // incompatible with what's cached in |it|.
-  bool is_observed =
-      receiver->map()->is_observed() &&
-      !it->name().is_identical_to(it->factory()->hidden_string());
+  bool is_observed = receiver->map()->is_observed() &&
+                     !it->isolate()->IsInternallyUsedPropertyName(it->name());
   MaybeHandle<Object> maybe_old;
   if (is_observed) maybe_old = it->GetDataValue();
 
@@ -3136,7 +3135,7 @@ MaybeHandle<Object> Object::AddDataProperty(LookupIterator* it,
 
   // Send the change record if there are observers.
   if (receiver->map()->is_observed() &&
-      !it->name().is_identical_to(it->factory()->hidden_string())) {
+      !it->isolate()->IsInternallyUsedPropertyName(it->name())) {
     RETURN_ON_EXCEPTION(it->isolate(), JSObject::EnqueueChangeRecord(
                                            receiver, "add", it->name(),
                                            it->factory()->the_hole_value()),
@@ -3925,7 +3924,7 @@ void JSObject::AddProperty(Handle<JSObject> object, Handle<Name> name,
   DCHECK(maybe.has_value);
   DCHECK(!it.IsFound());
   DCHECK(object->map()->is_extensible() ||
-         name.is_identical_to(it.isolate()->factory()->hidden_string()));
+         it.isolate()->IsInternallyUsedPropertyName(name));
 #endif
   AddDataProperty(&it, value, attributes, STRICT,
                   CERTAINLY_NOT_STORE_FROM_KEYED).Check();
@@ -3943,7 +3942,7 @@ MaybeHandle<Object> JSObject::SetOwnPropertyIgnoreAttributes(
   DCHECK(!value->IsTheHole());
   LookupIterator it(object, name, LookupIterator::OWN_SKIP_INTERCEPTOR);
   bool is_observed = object->map()->is_observed() &&
-                     *name != it.isolate()->heap()->hidden_string();
+                     !it.isolate()->IsInternallyUsedPropertyName(name);
   for (; it.IsFound(); it.Next()) {
     switch (it.state()) {
       case LookupIterator::INTERCEPTOR:
@@ -5101,7 +5100,7 @@ MaybeHandle<Object> JSObject::DeleteProperty(Handle<JSObject> object,
   LookupIterator it(object, name, config);
 
   bool is_observed = object->map()->is_observed() &&
-                     *name != it.isolate()->heap()->hidden_string();
+                     !it.isolate()->IsInternallyUsedPropertyName(name);
   Handle<Object> old_value = it.isolate()->factory()->the_hole_value();
 
   for (; it.IsFound(); it.Next()) {
@@ -6327,7 +6326,7 @@ MaybeHandle<Object> JSObject::DefineAccessor(Handle<JSObject> object,
 
   Handle<Object> old_value = isolate->factory()->the_hole_value();
   bool is_observed = object->map()->is_observed() &&
-                     *name != isolate->heap()->hidden_string();
+                     !isolate->IsInternallyUsedPropertyName(name);
   bool preexists = false;
   if (is_observed) {
     if (is_element) {
@@ -6586,7 +6585,7 @@ Object* JSObject::SlowReverseLookup(Object* value) {
 Handle<Map> Map::RawCopy(Handle<Map> map, int instance_size) {
   Handle<Map> result = map->GetIsolate()->factory()->NewMap(
       map->instance_type(), instance_size);
-  result->set_prototype(map->prototype());
+  result->SetPrototype(handle(map->prototype(), map->GetIsolate()));
   result->set_constructor(map->constructor());
   result->set_bit_field(map->bit_field());
   result->set_bit_field2(map->bit_field2());
@@ -6783,6 +6782,12 @@ void Map::ConnectTransition(Handle<Map> parent, Handle<Map> child,
       parent->set_transitions(*transitions);
     }
     child->SetBackPointer(*parent);
+    if (child->prototype()->IsJSObject()) {
+      Handle<JSObject> proto(JSObject::cast(child->prototype()));
+      if (!child->ShouldRegisterAsPrototypeUser(proto)) {
+        JSObject::UnregisterPrototypeUser(proto, child);
+      }
+    }
 #if TRACE_MAPS
     Map::TraceTransition("Transition", *parent, *child, *name);
 #endif
@@ -8099,6 +8104,104 @@ bool FixedArray::IsEqualTo(FixedArray* other) {
 #endif
 
 
+// static
+void WeakFixedArray::Set(Handle<WeakFixedArray> array, int index,
+                         Handle<HeapObject> value) {
+  DCHECK(array->IsEmptySlot(index));  // Don't overwrite anything.
+  Handle<WeakCell> cell = array->GetIsolate()->factory()->NewWeakCell(value);
+  Handle<FixedArray>::cast(array)->set(index + kReservedFieldCount, *cell);

[Toon Verwaest, 2014/12/01 15:23:54]

So kReservedFieldCount is just an internal header? What about naming it
kFirstIndex like in the other arrays?

[Jakob Kummerow, 2014/12/02 12:32:15]

Done.

+  if (FLAG_trace_weak_arrays) {
+    PrintF("[WeakFixedArray: storing at index %d ]\n", index,
+           array->last_used_index());
+  }
+  array->set_last_used_index(index);
+}
+
+
+// static
+void WeakFixedArray::CopyFrom(Handle<WeakFixedArray> target,
+                              Handle<WeakFixedArray> source) {
+  DCHECK(source->length() <= target->length());
+  Handle<FixedArray> raw_target = Handle<FixedArray>::cast(target);
+  Handle<FixedArray> raw_source = Handle<FixedArray>::cast(source);
+  int target_index = kReservedFieldCount;
+  for (int source_index = kReservedFieldCount; source_index < source->length();
+       ++source_index) {
+    // Even though CopyFrom is intended for growing fully-populated source
+    // arrays, the act of allocating a bigger target array might have caused
+    // entries in source to be cleared. Copy only what's needed.
+    if (source->IsEmptySlot(source_index - kReservedFieldCount)) continue;
+    raw_target->set(target_index++, raw_source->get(source_index));
+  }
+  target->set_last_used_index(target_index - 1 - kReservedFieldCount);
+}
+
+
+// static
+bool WeakFixedArray::StoreAnywhere(Handle<WeakFixedArray> array,
+                                   Handle<HeapObject> value,
+                                   bool may_be_duplicate) {
+  if (may_be_duplicate) {
+    for (int i = 0; i < array->length(); ++i) {
+      if (array->get(i) == *value) return true;
+    }
+  } else {
+#ifdef DEBUG
+    for (int i = 0; i < array->length(); ++i) {
+      DCHECK_NE(*value, array->get(i));
+    }
+#endif
+  }
+
+  // Try to store the new entry if there's room. Optimize for consecutive
+  // accesses.
+  int first_index = array->last_used_index();

[Toon Verwaest, 2014/12/01 15:23:54]

Seems like you would want to start at last_used_index+1?

[Jakob Kummerow, 2014/12/02 12:32:15]

No; the last element may have been added and then removed again, so it's best to
start searching at its index.

+  for (int i = first_index;;) {
+    if (array->IsEmptySlot((i))) {
+      WeakFixedArray::Set(array, i, value);
+      return true;
+    }
+    if (FLAG_trace_weak_arrays) {
+      PrintF("[WeakFixedArray: searching for free slot]\n");
+    }
+    i++;
+    if (i == array->length()) i = 0;

[Toon Verwaest, 2014/12/01 15:23:54]

i = (i + 1) % array->length();

[Jakob Kummerow, 2014/12/02 12:32:15]

Done.

+    if (i == first_index) break;
+  }
+  return false;
+}
+
+
+// static
+Handle<WeakFixedArray> WeakFixedArray::GrowAndStore(
+    Handle<WeakFixedArray> original, Handle<HeapObject> value) {
+  int new_length = original->length() + (original->length() >> 1) + 4;
+  Handle<WeakFixedArray> new_array =
+      original->GetIsolate()->factory()->NewWeakFixedArray(new_length);
+  if (FLAG_trace_weak_arrays) {
+    PrintF("[WeakFixedArray: growing to size %d ]\n", new_length);
+  }
+  WeakFixedArray::CopyFrom(new_array, original);
+  WeakFixedArray::Set(new_array, original->length(), value);
+  return new_array;
+}
+
+
+void WeakFixedArray::Delete(Handle<HeapObject> value) {
+  // Optimize for the most recently added element to be removed again.
+  int first_index = last_used_index();
+  for (int i = first_index;;) {
+    if (get(i) == *value) {
+      clear(i);
+      return;  // StoreAnywhere() makes sure there are no duplicates.
+    }
+    i++;
+    if (i == length()) i = 0;
+    if (i == first_index) break;
+  }
+}
+
+
 Handle<DescriptorArray> DescriptorArray::Allocate(Isolate* isolate,
                                                   int number_of_descriptors,
                                                   int slack) {
@@ -9669,6 +9772,82 @@ void JSObject::ReoptimizeIfPrototype(Handle<JSObject> object) {
 }
 
 
+void JSObject::RegisterPrototypeUser(Handle<JSObject> prototype,
+                                     Handle<HeapObject> user) {
+  DCHECK(FLAG_track_prototype_users);
+  Isolate* isolate = prototype->GetIsolate();
+  Handle<Name> symbol = isolate->factory()->prototype_users_symbol();
+
+  // Get prototype users array, create it if it doesn't exist yet.
+  Handle<Object> maybe_array =
+      JSObject::GetProperty(prototype, symbol).ToHandleChecked();
+  bool must_store = false;
+  if (!maybe_array->IsWeakFixedArray()) {
+    maybe_array = isolate->factory()->NewWeakFixedArray(1);
+    must_store = true;
+  }
+  Handle<WeakFixedArray> array = Handle<WeakFixedArray>::cast(maybe_array);
+
+  if (!WeakFixedArray::StoreAnywhere(array, user)) {

[Toon Verwaest, 2014/12/01 15:23:54]

Handle<WFA> new_array = WFA::Add(array, user);
must_store = !new_array.is_identical_to(array);

[Jakob Kummerow, 2014/12/02 12:32:15]

Done.

+    array = WeakFixedArray::GrowAndStore(array, user);
+    must_store = true;
+  }
+  if (must_store) {
+    JSObject::SetOwnPropertyIgnoreAttributes(prototype, symbol, array,
+                                             DONT_ENUM).Assert();
+  }
+}
+
+
+void JSObject::UnregisterPrototypeUser(Handle<JSObject> prototype,
+                                       Handle<HeapObject> user) {
+  Isolate* isolate = prototype->GetIsolate();
+  Handle<Name> symbol = isolate->factory()->prototype_users_symbol();
+
+  LookupIterator it(prototype, symbol);
+  Handle<Object> maybe_array = JSObject::GetProperty(&it).ToHandleChecked();

[Toon Verwaest, 2014/12/01 15:23:54]

JSObject::GetProperty(prototype, symbol);

[Jakob Kummerow, 2014/12/02 12:32:15]

Done.

+  if (!maybe_array->IsWeakFixedArray()) return;
+  Handle<WeakFixedArray>::cast(maybe_array)->Delete(user);
+}
+
+
+void Map::SetPrototype(Handle<Object> prototype,
+                       PrototypeOptimizationMode proto_mode) {
+  if (this->prototype()->IsJSObject() && FLAG_track_prototype_users) {
+    Handle<JSObject> old_prototype(JSObject::cast(this->prototype()));
+    JSObject::UnregisterPrototypeUser(old_prototype, handle(this));
+  }
+  if (prototype->IsJSObject()) {
+    Handle<JSObject> prototype_jsobj = Handle<JSObject>::cast(prototype);
+    if (ShouldRegisterAsPrototypeUser(prototype_jsobj)) {
+      JSObject::RegisterPrototypeUser(prototype_jsobj, handle(this));
+    }
+    JSObject::OptimizeAsPrototype(prototype_jsobj, proto_mode);
+  }
+  WriteBarrierMode wb_mode =
+      prototype->IsNull() ? SKIP_WRITE_BARRIER : UPDATE_WRITE_BARRIER;
+  set_prototype(*prototype, wb_mode);
+}
+
+
+bool Map::ShouldRegisterAsPrototypeUser(Handle<JSObject> prototype) {
+  if (!FLAG_track_prototype_users) return false;
+  if (this->is_prototype_map()) return true;
+  Object* back = GetBackPointer();
+  if (!back->IsMap()) return true;

[Toon Verwaest, 2014/12/01 15:23:54]

That would include maps that aren't part of a transition tree right? Including
slow-mode maps.

[Jakob Kummerow, 2014/12/02 12:32:15]

Done -- blacklisted dictionary maps. On the other hand, these rules obviously
depend on what we need the information for, so we anyway might have to adapt
them over time as necessary.

+  if (Map::cast(back)->prototype() != *prototype) return true;
+  return false;
+}
+
+
+bool Map::CanUseOptimizationsBasedOnPrototypeRegistry() {
+  if (!FLAG_track_prototype_users) return false;
+  if (this->is_prototype_map()) return true;
+  if (GetBackPointer()->IsMap()) return true;
+  return false;
+}
+
+
 Handle<Object> CacheInitialJSArrayMaps(
     Handle<Context> native_context, Handle<Map> initial_map) {
   // Replace all of the cached initial array maps in the native context with
@@ -9807,11 +9986,9 @@ bool JSFunction::RemovePrototype() {
 
 void JSFunction::SetInitialMap(Handle<JSFunction> function, Handle<Map> map,
                                Handle<Object> prototype) {
-  if (prototype->IsJSObject()) {
-    Handle<JSObject> js_proto = Handle<JSObject>::cast(prototype);
-    JSObject::OptimizeAsPrototype(js_proto, FAST_PROTOTYPE);
+  if (map->prototype() != *prototype) {
+    map->SetPrototype(prototype, FAST_PROTOTYPE);
   }
-  map->set_prototype(*prototype);
   function->set_prototype_or_initial_map(*map);
   map->set_constructor(*function);
 #if TRACE_MAPS
@@ -11943,12 +12120,13 @@ const char* DependentCode::DependencyGroupName(DependencyGroup group) {
 
 
 Handle<Map> Map::TransitionToPrototype(Handle<Map> map,
-                                       Handle<Object> prototype) {
+                                       Handle<Object> prototype,
+                                       PrototypeOptimizationMode mode) {
   Handle<Map> new_map = GetPrototypeTransition(map, prototype);
   if (new_map.is_null()) {
     new_map = Copy(map, "TransitionToPrototype");
     PutPrototypeTransition(map, prototype, new_map);
-    new_map->set_prototype(*prototype);
+    new_map->SetPrototype(prototype, mode);
   }
   return new_map;
 }
@@ -12018,13 +12196,9 @@ MaybeHandle<Object> JSObject::SetPrototype(Handle<JSObject> object,
   // Nothing to do if prototype is already set.
   if (map->prototype() == *value) return value;
 
-  if (value->IsJSObject()) {
-    PrototypeOptimizationMode mode =
-        from_javascript ? REGULAR_PROTOTYPE : FAST_PROTOTYPE;
-    JSObject::OptimizeAsPrototype(Handle<JSObject>::cast(value), mode);
-  }
-
-  Handle<Map> new_map = Map::TransitionToPrototype(map, value);
+  PrototypeOptimizationMode mode =
+      from_javascript ? REGULAR_PROTOTYPE : FAST_PROTOTYPE;
+  Handle<Map> new_map = Map::TransitionToPrototype(map, value, mode);
   DCHECK(new_map->prototype() == *value);
   JSObject::MigrateToMap(real_receiver, new_map);