Unify implementations of Map handles vectors and lists

src/ic/ic.cc

 // Copyright 2012 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/ic/ic.h"
 
 #include "src/accessors.h"
 #include "src/api-arguments-inl.h"
 #include "src/api.h"
 #include "src/arguments.h"
@@ skipping 531 matching lines @@
   } else {
     // Non-keyed ICs don't track the name explicitly.
     if (!is_keyed()) name = Handle<Name>::null();
     nexus()->ConfigureMonomorphic(name, map, handler);
   }
 
   vector_set_ = true;
   OnFeedbackChanged(isolate(), GetHostFunction());
 }
 
-void IC::ConfigureVectorState(Handle<Name> name, MapHandleList* maps,
+void IC::ConfigureVectorState(Handle<Name> name, MapHandles const& maps,
                               List<Handle<Object>>* handlers) {
   DCHECK(!IsLoadGlobalIC());
   // Non-keyed ICs don't track the name explicitly.
   if (!is_keyed()) name = Handle<Name>::null();
   nexus()->ConfigurePolymorphic(name, maps, handlers);
 
   vector_set_ = true;
   OnFeedbackChanged(isolate(), GetHostFunction());
 }
 
@@ skipping 66 matching lines @@
         LoadScriptContextFieldStub stub(isolate(), &lookup_result);
         PatchCache(name, stub.GetCode());
         TRACE_IC("LoadGlobalIC", name);
       }
       return result;
     }
   }
   return LoadIC::Load(global, name);
 }
 
-static bool AddOneReceiverMapIfMissing(MapHandleList* receiver_maps,
+static bool AddOneReceiverMapIfMissing(MapHandles* receiver_maps,
                                        Handle<Map> new_receiver_map) {
   DCHECK(!new_receiver_map.is_null());
-  for (int current = 0; current < receiver_maps->length(); ++current) {
-    if (!receiver_maps->at(current).is_null() &&
-        receiver_maps->at(current).is_identical_to(new_receiver_map)) {
+  for (auto map : *receiver_maps) {
+    if (!map.is_null() && map.is_identical_to(new_receiver_map)) {
       return false;
     }
   }
-  receiver_maps->Add(new_receiver_map);
+  receiver_maps->push_back(new_receiver_map);
   return true;
 }
 
 bool IC::UpdatePolymorphicIC(Handle<Name> name, Handle<Object> handler) {
   DCHECK(IsHandler(*handler));
   if (is_keyed() && state() != RECOMPUTE_HANDLER) return false;
   Handle<Map> map = receiver_map();
-  MapHandleList maps;
+  MapHandles maps;
   List<Handle<Object>> handlers;
 
   TargetMaps(&maps);
-  int number_of_maps = maps.length();
+  int number_of_maps = static_cast<int>(maps.size());
   int deprecated_maps = 0;
   int handler_to_overwrite = -1;
 
   for (int i = 0; i < number_of_maps; i++) {
     Handle<Map> current_map = maps.at(i);
     if (current_map->is_deprecated()) {
       // Filter out deprecated maps to ensure their instances get migrated.
       ++deprecated_maps;
     } else if (map.is_identical_to(current_map)) {
       // If the receiver type is already in the polymorphic IC, this indicates
       // there was a prototoype chain failure. In that case, just overwrite the
       // handler.
       handler_to_overwrite = i;
     } else if (handler_to_overwrite == -1 &&
                IsTransitionOfMonomorphicTarget(*current_map, *map)) {
       handler_to_overwrite = i;
     }
   }
 
   int number_of_valid_maps =
       number_of_maps - deprecated_maps - (handler_to_overwrite != -1);
 
   if (number_of_valid_maps >= kMaxPolymorphicMapCount) return false;
   if (number_of_maps == 0 && state() != MONOMORPHIC && state() != POLYMORPHIC) {
     return false;
   }
-  if (!nexus()->FindHandlers(&handlers, maps.length())) return false;
+  if (!nexus()->FindHandlers(&handlers, static_cast<int>(maps.size())))
+    return false;
 
   number_of_valid_maps++;
   if (number_of_valid_maps > 1 && is_keyed()) return false;
   if (number_of_valid_maps == 1) {
     ConfigureVectorState(name, receiver_map(), handler);
   } else {
     if (handler_to_overwrite >= 0) {
       handlers.Set(handler_to_overwrite, handler);
       if (!map.is_identical_to(maps.at(handler_to_overwrite))) {
-        maps.Set(handler_to_overwrite, map);
+        maps[handler_to_overwrite] = map;
       }
     } else {
-      maps.Add(map);
+      maps.push_back(map);
       handlers.Add(handler);
     }
 
-    ConfigureVectorState(name, &maps, &handlers);
+    ConfigureVectorState(name, maps, &handlers);
   }
 
   return true;
 }
 
 void IC::UpdateMonomorphicIC(Handle<Object> handler, Handle<Name> name) {
   DCHECK(IsHandler(*handler));
   ConfigureVectorState(name, receiver_map(), handler);
 }
 
 
 void IC::CopyICToMegamorphicCache(Handle<Name> name) {
-  MapHandleList maps;
+  MapHandles maps;
   List<Handle<Object>> handlers;
   TargetMaps(&maps);
-  if (!nexus()->FindHandlers(&handlers, maps.length())) return;
-  for (int i = 0; i < maps.length(); i++) {
+  if (!nexus()->FindHandlers(&handlers, static_cast<int>(maps.size()))) return;
+  for (int i = 0; i < static_cast<int>(maps.size()); i++) {
     UpdateMegamorphicCache(*maps.at(i), *name, *handlers.at(i));
   }
 }
 
 
 bool IC::IsTransitionOfMonomorphicTarget(Map* source_map, Map* target_map) {
   if (source_map == NULL) return true;
   if (target_map == NULL) return false;
   ElementsKind target_elements_kind = target_map->elements_kind();
   bool more_general_transition = IsMoreGeneralElementsKindTransition(
       source_map->elements_kind(), target_elements_kind);
   Map* transitioned_map = nullptr;
   if (more_general_transition) {
-    MapHandleList map_list;
-    map_list.Add(handle(target_map));
-    transitioned_map = source_map->FindElementsKindTransitionedMap(&map_list);
+    MapHandles map_list;
+    map_list.push_back(handle(target_map));
+    transitioned_map = source_map->FindElementsKindTransitionedMap(map_list);
   }
   return transitioned_map == target_map;
 }
 
 void IC::PatchCache(Handle<Name> name, Handle<Object> handler) {
   DCHECK(IsHandler(*handler));
   // Currently only load and store ICs support non-code handlers.
   DCHECK(IsAnyLoad() || IsAnyStore());
   switch (state()) {
     case UNINITIALIZED:
@@ skipping 561 matching lines @@
   } else if (key->IsString()) {
     key = isolate->factory()->InternalizeString(Handle<String>::cast(key));
   }
   return key;
 }
 
 void KeyedLoadIC::UpdateLoadElement(Handle<HeapObject> receiver) {
   Handle<Map> receiver_map(receiver->map(), isolate());
   DCHECK(receiver_map->instance_type() != JS_VALUE_TYPE &&
          receiver_map->instance_type() != JS_PROXY_TYPE);  // Checked by caller.
-  MapHandleList target_receiver_maps;
+  MapHandles target_receiver_maps;
   TargetMaps(&target_receiver_maps);
 
-  if (target_receiver_maps.length() == 0) {
+  if (target_receiver_maps.empty()) {
     Handle<Object> handler = LoadElementHandler(receiver_map);
     return ConfigureVectorState(Handle<Name>(), receiver_map, handler);
   }
 
-  for (int i = 0; i < target_receiver_maps.length(); i++) {
-    Handle<Map> map = target_receiver_maps.at(i);
+  for (auto map : target_receiver_maps) {
     if (map.is_null()) continue;
     if (map->instance_type() == JS_VALUE_TYPE) {
       TRACE_GENERIC_IC("JSValue");
       return;
     }
     if (map->instance_type() == JS_PROXY_TYPE) {
       TRACE_GENERIC_IC("JSProxy");
       return;
     }
   }
@@ skipping 19 matching lines @@
   // adding the map that was just encountered.
   if (!AddOneReceiverMapIfMissing(&target_receiver_maps, receiver_map)) {
     // If the miss wasn't due to an unseen map, a polymorphic stub
     // won't help, use the generic stub.
     TRACE_GENERIC_IC("same map added twice");
     return;
   }
 
   // If the maximum number of receiver maps has been exceeded, use the generic
   // version of the IC.
-  if (target_receiver_maps.length() > kMaxKeyedPolymorphism) {
+  if (target_receiver_maps.size() > kMaxKeyedPolymorphism) {
     TRACE_GENERIC_IC("max polymorph exceeded");
     return;
   }
 
-  List<Handle<Object>> handlers(target_receiver_maps.length());
+  List<Handle<Object>> handlers(static_cast<int>(target_receiver_maps.size()));
   LoadElementPolymorphicHandlers(&target_receiver_maps, &handlers);
-  DCHECK_LE(1, target_receiver_maps.length());
-  if (target_receiver_maps.length() == 1) {
-    ConfigureVectorState(Handle<Name>(), target_receiver_maps.at(0),
+  DCHECK_LE(1, target_receiver_maps.size());
+  if (target_receiver_maps.size() == 1) {
+    ConfigureVectorState(Handle<Name>(), target_receiver_maps[0],
                          handlers.at(0));
   } else {
-    ConfigureVectorState(Handle<Name>(), &target_receiver_maps, &handlers);
+    ConfigureVectorState(Handle<Name>(), target_receiver_maps, &handlers);
   }
 }
 
 Handle<Object> KeyedLoadIC::LoadElementHandler(Handle<Map> receiver_map) {
   if (receiver_map->has_indexed_interceptor() &&
       !receiver_map->GetIndexedInterceptor()->getter()->IsUndefined(
           isolate()) &&
       !receiver_map->GetIndexedInterceptor()->non_masking()) {
     TRACE_HANDLER_STATS(isolate(), KeyedLoadIC_LoadIndexedInterceptorStub);
     return LoadIndexedInterceptorStub(isolate()).GetCode();
@@ skipping 24 matching lines @@
   // TODO(jkummerow): Use IsHoleyElementsKind(elements_kind).
   bool convert_hole_to_undefined =
       is_js_array && elements_kind == FAST_HOLEY_ELEMENTS &&
       *receiver_map == isolate()->get_initial_js_array_map(elements_kind);
   TRACE_HANDLER_STATS(isolate(), KeyedLoadIC_LoadElementDH);
   return LoadHandler::LoadElement(isolate(), elements_kind,
                                   convert_hole_to_undefined, is_js_array);
 }
 
 void KeyedLoadIC::LoadElementPolymorphicHandlers(
-    MapHandleList* receiver_maps, List<Handle<Object>>* handlers) {
-  for (int i = 0; i < receiver_maps->length(); ++i) {
-    Handle<Map> receiver_map(receiver_maps->at(i));
+    MapHandles* receiver_maps, List<Handle<Object>>* handlers) {
+  MapHandles::iterator current_map = receiver_maps->begin();
+  MapHandles::iterator last_valid_map = receiver_maps->end();
+  while (current_map < last_valid_map) {
+    Handle<Map> receiver_map = *current_map;
     if (receiver_map->is_deprecated()) {
       // Filter out deprecated maps to ensure their instances get migrated.
-      receiver_maps->Remove(i--);
+      --last_valid_map;
+      std::swap(*current_map, *last_valid_map);
+      receiver_maps->erase(last_valid_map, receiver_maps->end());
       continue;
     }
 
     // Mark all stable receiver maps that have elements kind transition map
     // among receiver_maps as unstable because the optimizing compilers may
     // generate an elements kind transition for this kind of receivers.
     if (receiver_map->is_stable()) {
-      Map* tmap = receiver_map->FindElementsKindTransitionedMap(receiver_maps);
+      Map* tmap = receiver_map->FindElementsKindTransitionedMap(*receiver_maps);
       if (tmap != nullptr) {
         receiver_map->NotifyLeafMapLayoutChange();
       }
     }
     handlers->Add(LoadElementHandler(receiver_map));
+    ++current_map;
   }
 }
 
 MaybeHandle<Object> KeyedLoadIC::Load(Handle<Object> object,
                                       Handle<Object> key) {
   if (MigrateDeprecated(object)) {
     Handle<Object> result;
     ASSIGN_RETURN_ON_EXCEPTION(
         isolate(), result, Runtime::GetObjectProperty(isolate(), object, key),
         Object);
@@ skipping 457 matching lines @@
   }
   TRACE_HANDLER_STATS(isolate(), StoreIC_StoreViaSetter);
   int expected_arguments =
       JSFunction::cast(*setter)->shared()->internal_formal_parameter_count();
   return compiler.CompileStoreViaSetter(
       receiver, lookup->name(), lookup->GetAccessorIndex(), expected_arguments);
 }
 
 void KeyedStoreIC::UpdateStoreElement(Handle<Map> receiver_map,
                                       KeyedAccessStoreMode store_mode) {
-  MapHandleList target_receiver_maps;
+  MapHandles target_receiver_maps;
   TargetMaps(&target_receiver_maps);
-  if (target_receiver_maps.length() == 0) {
+  if (target_receiver_maps.empty()) {
     Handle<Map> monomorphic_map =
         ComputeTransitionedMap(receiver_map, store_mode);
     store_mode = GetNonTransitioningStoreMode(store_mode);
     Handle<Object> handler = StoreElementHandler(monomorphic_map, store_mode);
     return ConfigureVectorState(Handle<Name>(), monomorphic_map, handler);
   }
 
-  for (int i = 0; i < target_receiver_maps.length(); i++) {
-    if (!target_receiver_maps.at(i).is_null() &&
-        target_receiver_maps.at(i)->instance_type() == JS_VALUE_TYPE) {
+  for (auto map : target_receiver_maps) {
+    if (!map.is_null() && map->instance_type() == JS_VALUE_TYPE) {
       TRACE_GENERIC_IC("JSValue");
       return;
     }
   }
 
   // There are several special cases where an IC that is MONOMORPHIC can still
   // transition to a different GetNonTransitioningStoreMode IC that handles a
   // superset of the original IC. Handle those here if the receiver map hasn't
   // changed or it has transitioned to a more general kind.
   KeyedAccessStoreMode old_store_mode = GetKeyedAccessStoreMode();
@@ skipping 44 matching lines @@
 
   if (!map_added) {
     // If the miss wasn't due to an unseen map, a polymorphic stub
     // won't help, use the megamorphic stub which can handle everything.
     TRACE_GENERIC_IC("same map added twice");
     return;
   }
 
   // If the maximum number of receiver maps has been exceeded, use the
   // megamorphic version of the IC.
-  if (target_receiver_maps.length() > kMaxKeyedPolymorphism) return;
+  if (target_receiver_maps.size() > kMaxKeyedPolymorphism) return;
 
   // Make sure all polymorphic handlers have the same store mode, otherwise the
   // megamorphic stub must be used.
   store_mode = GetNonTransitioningStoreMode(store_mode);
   if (old_store_mode != STANDARD_STORE) {
     if (store_mode == STANDARD_STORE) {
       store_mode = old_store_mode;
     } else if (store_mode != old_store_mode) {
       TRACE_GENERIC_IC("store mode mismatch");
       return;
     }
   }
 
   // If the store mode isn't the standard mode, make sure that all polymorphic
   // receivers are either external arrays, or all "normal" arrays. Otherwise,
   // use the megamorphic stub.
   if (store_mode != STANDARD_STORE) {
-    int external_arrays = 0;
-    for (int i = 0; i < target_receiver_maps.length(); ++i) {
-      if (target_receiver_maps[i]->has_fixed_typed_array_elements()) {
+    size_t external_arrays = 0;
+    for (auto map : target_receiver_maps) {
+      if (map->has_fixed_typed_array_elements()) {
         external_arrays++;
       }
     }
     if (external_arrays != 0 &&
-        external_arrays != target_receiver_maps.length()) {
+        external_arrays != target_receiver_maps.size()) {
       TRACE_GENERIC_IC("unsupported combination of external and normal arrays");
       return;
     }
   }
 
-  List<Handle<Object>> handlers(target_receiver_maps.length());
+  List<Handle<Object>> handlers(static_cast<int>(target_receiver_maps.size()));
   StoreElementPolymorphicHandlers(&target_receiver_maps, &handlers, store_mode);
-  DCHECK_LE(1, target_receiver_maps.length());
-  if (target_receiver_maps.length() == 1) {
-    ConfigureVectorState(Handle<Name>(), target_receiver_maps.at(0),
+  DCHECK_LE(1, target_receiver_maps.size());
+  if (target_receiver_maps.size() == 1) {
+    ConfigureVectorState(Handle<Name>(), target_receiver_maps[0],
                          handlers.at(0));
   } else {
-    ConfigureVectorState(Handle<Name>(), &target_receiver_maps, &handlers);
+    ConfigureVectorState(Handle<Name>(), target_receiver_maps, &handlers);
   }
 }
 
 
 Handle<Map> KeyedStoreIC::ComputeTransitionedMap(
     Handle<Map> map, KeyedAccessStoreMode store_mode) {
   switch (store_mode) {
     case STORE_TRANSITION_TO_OBJECT:
     case STORE_AND_GROW_TRANSITION_TO_OBJECT: {
       ElementsKind kind = IsFastHoleyElementsKind(map->elements_kind())
@@ skipping 45 matching lines @@
     DCHECK_EQ(DICTIONARY_ELEMENTS, elements_kind);
     stub = StoreSlowElementStub(isolate(), store_mode).GetCode();
   }
   Handle<Object> validity_cell =
       Map::GetOrCreatePrototypeChainValidityCell(receiver_map, isolate());
   if (validity_cell.is_null()) return stub;
   return isolate()->factory()->NewTuple2(validity_cell, stub);
 }
 
 void KeyedStoreIC::StoreElementPolymorphicHandlers(
-    MapHandleList* receiver_maps, List<Handle<Object>>* handlers,
+    MapHandles* receiver_maps, List<Handle<Object>>* handlers,
     KeyedAccessStoreMode store_mode) {
   DCHECK(store_mode == STANDARD_STORE ||
          store_mode == STORE_AND_GROW_NO_TRANSITION ||
          store_mode == STORE_NO_TRANSITION_IGNORE_OUT_OF_BOUNDS ||
          store_mode == STORE_NO_TRANSITION_HANDLE_COW);
 
-  for (int i = 0; i < receiver_maps->length(); ++i) {
-    Handle<Map> receiver_map(receiver_maps->at(i));
+  MapHandles::iterator current_map = receiver_maps->begin();
+  MapHandles::iterator last_valid_map = receiver_maps->end();
+  while (current_map < last_valid_map) {

[Franzi, 2017/05/02 16:29:32]

Are there strong performance reasons for this pattern? If not, I'd prefer a
remove_if() followed by an erase(). 

[danno, 2017/05/03 15:10:30]

Done.

+    Handle<Map> receiver_map = *current_map;
     if (receiver_map->is_deprecated()) {
       // Filter out deprecated maps to ensure their instances get migrated.
-      receiver_maps->Remove(i--);
+      --last_valid_map;
+      std::swap(*current_map, *last_valid_map);
+      receiver_maps->erase(last_valid_map, receiver_maps->end());
       continue;
     }
 
     Handle<Object> handler;
     Handle<Map> transitioned_map;
 
     if (receiver_map->instance_type() < FIRST_JS_RECEIVER_TYPE ||
         receiver_map->DictionaryElementsInPrototypeChainOnly()) {
       // TODO(mvstanton): Consider embedding store_mode in the state of the slow
       // keyed store ic for uniformity.
       TRACE_HANDLER_STATS(isolate(), KeyedStoreIC_SlowStub);
       handler = isolate()->builtins()->KeyedStoreIC_Slow();
 
     } else {
       {
         Map* tmap =
-            receiver_map->FindElementsKindTransitionedMap(receiver_maps);
+            receiver_map->FindElementsKindTransitionedMap(*receiver_maps);
         if (tmap != nullptr) {
           if (receiver_map->is_stable()) {
             receiver_map->NotifyLeafMapLayoutChange();
           }
           transitioned_map = handle(tmap);
         }
       }
 
       // TODO(mvstanton): The code below is doing pessimistic elements
       // transitions. I would like to stop doing that and rely on Allocation
@@ skipping 17 matching lines @@
         }
         Handle<WeakCell> transition = Map::WeakCellForMap(transitioned_map);
         handler =
             isolate()->factory()->NewTuple3(transition, stub, validity_cell);
       } else {
         handler = StoreElementHandler(receiver_map, store_mode);
       }
     }
     DCHECK(!handler.is_null());
     handlers->Add(handler);
+    ++current_map;
   }
 }
 
 bool IsOutOfBoundsAccess(Handle<JSObject> receiver, uint32_t index) {
   uint32_t length = 0;
   if (receiver->IsJSArray()) {
     JSArray::cast(*receiver)->length()->ToArrayLength(&length);
   } else {
     length = static_cast<uint32_t>(receiver->elements()->length());
   }
@@ skipping 809 matching lines @@
     DCHECK_EQ(LookupIterator::INTERCEPTOR, it.state());
     it.Next();
     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, result,
                                        Object::GetProperty(&it));
   }
 
   return *result;
 }
 }  // namespace internal
 }  // namespace v8