Cleanup IC heuristics.

src/ic.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 164 matching lines @@
   intptr_t delta =
       original_code->instruction_start() - code->instruction_start();
   return addr + delta;
 }
 #endif
 
 
 static bool TryRemoveInvalidPrototypeDependentStub(Code* target,
                                                    Object* receiver,
                                                    Object* name) {
-  // If the code is NORMAL, it handles dictionary mode objects. Such stubs do
-  // not check maps, but do positive/negative lookups.
-  if (target->type() != Code::NORMAL) {
-    Map* map = target->FindFirstMap();
-    if (map != NULL && map->is_deprecated()) {
-      return true;
-    }
+  if (target->is_keyed_load_stub() ||
+      target->is_keyed_call_stub() ||
+      target->is_keyed_store_stub()) {
+    // Determine whether the failure is due to a name failure.
+    if (!name->IsName()) return false;
+    Name* stub_name = target->FindFirstName();
+    if (Name::cast(name) != stub_name) return false;
   }
 
   InlineCacheHolderFlag cache_holder =
       Code::ExtractCacheHolderFromFlags(target->flags());
 
   Isolate* isolate = target->GetIsolate();
   if (cache_holder == OWN_MAP && !receiver->IsJSObject()) {
     // The stub was generated for JSObject but called for non-JSObject.
     // IC::GetCodeCacheHolder is not applicable.
     return false;
   } else if (cache_holder == PROTOTYPE_MAP &&
              receiver->GetPrototype(isolate)->IsNull()) {
     // IC::GetCodeCacheHolder is not applicable.
     return false;
   }
   Map* map = IC::GetCodeCacheHolder(isolate, receiver, cache_holder)->map();
 
   // Decide whether the inline cache failed because of changes to the
   // receiver itself or changes to one of its prototypes.
   //
   // If there are changes to the receiver itself, the map of the
   // receiver will have changed and the current target will not be in
   // the receiver map's code cache.  Therefore, if the current target
   // is in the receiver map's code cache, the inline cache failed due
   // to prototype check failure.
   int index = map->IndexInCodeCache(name, target);
   if (index >= 0) {
     map->RemoveFromCodeCache(String::cast(name), target, index);
+    // For loads, handlers are stored in addition to the ICs on the map. Remove
+    // those, too.
+    if (target->is_load_stub() || target->is_keyed_load_stub()) {
+      Code* handler = target->FindFirstCode();
+      index = map->IndexInCodeCache(name, handler);
+      if (index >= 0) {
+        map->RemoveFromCodeCache(String::cast(name), handler, index);
+      }
+    }
     return true;
   }
 
-  return false;
+  // If the IC is shared between multiple receivers (slow dictionary mode), then
+  // the map cannot be deprecated and the stub invalidated.
+  if (cache_holder != OWN_MAP) return false;
+
+  // The stub is not in the cache. We've ruled out all other kinds of failure
+  // except for proptotype chain changes, a deprecated map, or a map that's
+  // different from the one that the stub expects. If the map hasn't changed,
+  // assume it's a prototype failure. Treat deprecated maps in the same way as
+  // prototype failures (stay monomorphic if possible).
+  Map* old_map = target->FindFirstMap();
+  if (old_map == NULL) return false;
+  return old_map == map || old_map->is_deprecated();
 }
 
 
 IC::State IC::StateFrom(Code* target, Object* receiver, Object* name) {
   IC::State state = target->ic_state();
 
   if (state != MONOMORPHIC || !name->IsString()) return state;
   if (receiver->IsUndefined() || receiver->IsNull()) return state;
 
-  // For keyed load/store/call, the most likely cause of cache failure is
-  // that the key has changed.  We do not distinguish between
-  // prototype and non-prototype failures for keyed access.
   Code::Kind kind = target->kind();
-  if (kind == Code::KEYED_LOAD_IC ||
-      kind == Code::KEYED_STORE_IC ||
-      kind == Code::KEYED_CALL_IC) {
-    return MONOMORPHIC;
-  }
-
   // Remove the target from the code cache if it became invalid
   // because of changes in the prototype chain to avoid hitting it
   // again.
   // Call stubs handle this later to allow extra IC state
   // transitions.
-  if (kind != Code::CALL_IC &&
+  if (kind != Code::CALL_IC && kind != Code::KEYED_CALL_IC &&
       TryRemoveInvalidPrototypeDependentStub(target, receiver, name)) {
     return MONOMORPHIC_PROTOTYPE_FAILURE;
   }
 
   // The builtins object is special.  It only changes when JavaScript
   // builtins are loaded lazily.  It is important to keep inline
   // caches for the builtins object monomorphic.  Therefore, if we get
   // an inline cache miss for the builtins object after lazily loading
   // JavaScript builtins, we return uninitialized as the state to
   // force the inline cache back to monomorphic state.
@@ skipping 458 matching lines @@
     // This is the first time we execute this inline cache.
     // Set the target to the pre monomorphic stub to delay
     // setting the monomorphic state.
     code = isolate()->stub_cache()->ComputeCallPreMonomorphic(
         argc, kind_, extra_ic_state);
   } else if (state == MONOMORPHIC) {
     if (kind_ == Code::CALL_IC &&
         TryUpdateExtraICState(lookup, object, &extra_ic_state)) {
       code = ComputeMonomorphicStub(lookup, state, extra_ic_state,
                                     object, name);
-    } else if (kind_ == Code::CALL_IC &&
-               TryRemoveInvalidPrototypeDependentStub(target(),
+    } else if (TryRemoveInvalidPrototypeDependentStub(target(),
                                                       *object,
                                                       *name)) {
       state = MONOMORPHIC_PROTOTYPE_FAILURE;
       code = ComputeMonomorphicStub(lookup, state, extra_ic_state,
                                     object, name);
     } else {
       code = isolate()->stub_cache()->ComputeCallMegamorphic(
           argc, kind_, extra_ic_state);
     }
   } else {
     code = ComputeMonomorphicStub(lookup, state, extra_ic_state,
                                   object, name);
   }
 
   // If there's no appropriate stub we simply avoid updating the caches.
   if (code.is_null()) return;
 
   // Patch the call site depending on the state of the cache.
   switch (state) {
     case UNINITIALIZED:
     case MONOMORPHIC_PROTOTYPE_FAILURE:
     case PREMONOMORPHIC:
-      set_target(*code);
-      break;
     case MONOMORPHIC:
-      if (code->ic_state() != MONOMORPHIC) {
-        Map* map = target()->FindFirstMap();
-        if (map != NULL) {
-          UpdateMegamorphicCache(map, *name, target());
-        }
-      }
       set_target(*code);
       break;
     case MEGAMORPHIC: {
       // Cache code holding map should be consistent with
       // GenerateMonomorphicCacheProbe. It is not the map which holds the stub.
       Handle<JSObject> cache_object = object->IsJSObject()
           ? Handle<JSObject>::cast(object)
           : Handle<JSObject>(JSObject::cast(object->GetPrototype(isolate())),
                              isolate());
       // Update the stub cache.
@@ skipping 209 matching lines @@
   if (code->type() == Code::NORMAL) return false;
   if (target()->ic_state() == MONOMORPHIC &&
       target()->type() == Code::NORMAL) {
     return false;
   }
 
   MapHandleList receiver_maps;
   CodeHandleList handlers;
 
   int number_of_valid_maps;
+  int handler_to_overwrite = -1;
+  Handle<Map> new_receiver_map(receiver->map());
   {
     AssertNoAllocation no_gc;
     target()->FindAllMaps(&receiver_maps);
     int number_of_maps = receiver_maps.length();
     number_of_valid_maps = number_of_maps;
+
     for (int i = 0; i < number_of_maps; i++) {
-      if (receiver_maps.at(i)->is_deprecated()) {
+      Handle<Map> map = receiver_maps.at(i);
+      // Filter out deprecated maps to ensure its instances get migrated.
+      if (map->is_deprecated()) {
         number_of_valid_maps--;
+      // If the receiver map is already in the polymorphic IC, this indicates
+      // there was a prototoype chain failure. In that case, just overwrite the
+      // handler.
+      } else if (map.is_identical_to(new_receiver_map)) {
+        number_of_valid_maps--;
+        handler_to_overwrite = i;
       }
     }
 
     if (number_of_valid_maps >= 4) return false;
 
     // Only allow 0 maps in case target() was reset to UNINITIALIZED by the GC.
     // In that case, allow the IC to go back monomorphic.
     if (number_of_maps == 0 && target()->ic_state() != UNINITIALIZED) {
       return false;
     }
     target()->FindAllCode(&handlers, receiver_maps.length());
   }
 
-  if (!AddOneReceiverMapIfMissing(&receiver_maps,
-                                  Handle<Map>(receiver->map()))) {
-    return false;
+  number_of_valid_maps++;
+  if (handler_to_overwrite >= 0) {
+    handlers.InsertAt(handler_to_overwrite, code);
+  } else {
+    receiver_maps.Add(new_receiver_map);
+    handlers.Add(code);
   }
 
-  handlers.Add(code);
   Handle<Code> ic = isolate()->stub_cache()->ComputePolymorphicIC(
-      &receiver_maps, &handlers, number_of_valid_maps + 1, name);
+      &receiver_maps, &handlers, number_of_valid_maps, name);
   set_target(*ic);
   return true;
 }
 
 
 void LoadIC::UpdateMonomorphicIC(Handle<JSObject> receiver,
                                  Handle<Code> handler,
                                  Handle<String> name) {
   if (handler->type() == Code::NORMAL) return set_target(*handler);
   Handle<Code> ic = isolate()->stub_cache()->ComputeMonomorphicIC(
@@ skipping 66 matching lines @@
             is_same_handler = old_handler == *code;
           }
           if (is_same_handler
               && IsTransitionedMapOfMonomorphicTarget(receiver->map())) {
             UpdateMonomorphicIC(receiver, code, name);
             break;
           }
           if (UpdatePolymorphicIC(state, strict_mode, receiver, name, code)) {
             break;
           }
-        }
-        if (target()->type() != Code::NORMAL) {
-          if (target()->is_load_stub()) {
+
+          if (target()->type() != Code::NORMAL) {
             CopyICToMegamorphicCache(name);
-          } else if (target()->is_store_stub()) {
-            // Ensure that the IC stays monomorphic when replacing a monomorphic
-            // IC for a deprecated map.
-            // TODO(verwaest): Remove this code once polymorphic store ICs are
-            // implemented. Updating the polymorphic IC will keep it monomorphic
-            // by filtering deprecated maps.
-            MapHandleList maps;
-            Code* handler = target();
-            handler->FindAllMaps(&maps);
-            for (int i = 0; i < Min(1, maps.length()); i++) {
-              if (maps.at(i)->is_deprecated()) {
-                UpdateMonomorphicIC(receiver, code, name);
-                return;
-              }
-            }
-            if (maps.length() > 0) {
-              if (receiver->map() == *maps.at(0)) {
-                UpdateMonomorphicIC(receiver, code, name);
-                return;
-              }
-              UpdateMegamorphicCache(*maps.at(0), *name, handler);
-            }
-          } else {
-            Code* handler = target();
-            Map* map = handler->FindFirstMap();
-            if (map != NULL) {
-              UpdateMegamorphicCache(map, *name, handler);
-            }
           }
         }
 
         UpdateMegamorphicCache(receiver->map(), *name, *code);
         set_target((strict_mode == kStrictMode)
                      ? *megamorphic_stub_strict()
                      : *megamorphic_stub());
       }
       break;
     case MEGAMORPHIC:
@@ skipping 82 matching lines @@
   } else {
     code = ComputeLoadHandler(lookup, receiver, name);
     if (code.is_null()) return;
   }
 
   PatchCache(state, kNonStrictMode, receiver, name, code);
   TRACE_IC("LoadIC", name, state, target());
 }
 
 
-void IC::UpdateMegamorphicCache(Map* map, String* name, Code* code) {
+void IC::UpdateMegamorphicCache(Map* map, Name* name, Code* code) {
   // Cache code holding map should be consistent with
   // GenerateMonomorphicCacheProbe.
   isolate()->stub_cache()->Set(name, map, code);
 }
 
 
 Handle<Code> LoadIC::ComputeLoadHandler(LookupResult* lookup,
                                         Handle<JSObject> receiver,
                                         Handle<String> name) {
   if (!lookup->IsProperty()) {
@@ skipping 241 matching lines @@
       // repeatedly try to rewrite.
       return generic_stub();
   }
   return Handle<Code>::null();
 }
 
 
 static bool LookupForWrite(Handle<JSObject> receiver,
                            Handle<String> name,
                            Handle<Object> value,
-                           LookupResult* lookup) {
+                           LookupResult* lookup,
+                           IC::State* state) {
   Handle<JSObject> holder = receiver;
   receiver->Lookup(*name, lookup);
   if (lookup->IsFound()) {
     if (lookup->IsReadOnly() || !lookup->IsCacheable()) return false;
 
     if (lookup->holder() == *receiver) {
       if (lookup->IsInterceptor() &&
           receiver->GetNamedInterceptor()->setter()->IsUndefined()) {
         receiver->LocalLookupRealNamedProperty(*name, lookup);
         return lookup->IsFound() &&
@@ skipping 16 matching lines @@
   // While normally LookupTransition gets passed the receiver, in this case we
   // pass the holder of the property that we overwrite. This keeps the holder in
   // the LookupResult intact so we can later use it to generate a prototype
   // chain check. This avoids a double lookup, but requires us to pass in the
   // receiver when trying to fetch extra information from the transition.
   receiver->map()->LookupTransition(*holder, *name, lookup);
   if (!lookup->IsTransition()) return false;
   PropertyDetails target_details =
       lookup->GetTransitionDetails(receiver->map());
   if (target_details.IsReadOnly()) return false;
-  return value->FitsRepresentation(target_details.representation());
+
+  // If the value that's being stored does not fit in the field that the
+  // instance would transition to, create a new transition that fits the value.
+  // This has to be done before generating the IC, since that IC will embed the
+  // transition target.
+  // Ensure the instance and its map were migrated before trying to update the
+  // transition target.
+  ASSERT(!receiver->map()->is_deprecated());
+  if (!value->FitsRepresentation(target_details.representation())) {
+    Handle<Map> target(lookup->GetTransitionMapFromMap(receiver->map()));
+    Map::GeneralizeRepresentation(
+        target, target->LastAdded(), value->OptimalRepresentation());
+    *state = MONOMORPHIC_PROTOTYPE_FAILURE;
+  }
+  return true;
 }
 
 
 MaybeObject* StoreIC::Store(State state,
                             StrictModeFlag strict_mode,
                             Handle<Object> object,
                             Handle<String> name,
                             Handle<Object> value,
                             JSReceiver::StoreFromKeyed store_mode) {
   // Handle proxies.
@@ skipping 63 matching lines @@
           ? global_proxy_stub_strict()
           : global_proxy_stub();
       set_target(*stub);
       TRACE_IC("StoreIC", name, state, *stub);
     }
     return JSReceiver::SetPropertyOrFail(
         receiver, name, value, NONE, strict_mode, store_mode);
   }
 
   LookupResult lookup(isolate());
-  if (LookupForWrite(receiver, name, value, &lookup)) {
+  if (LookupForWrite(receiver, name, value, &lookup, &state)) {
     if (FLAG_use_ic) {
       UpdateCaches(&lookup, state, strict_mode, receiver, name, value);
     }
   } else if (strict_mode == kStrictMode &&
              !(lookup.IsProperty() && lookup.IsReadOnly()) &&
              IsUndeclaredGlobal(object)) {
     // Strict mode doesn't allow setting non-existent global property.
     return ReferenceError("not_defined", name);
   }
 
@@ skipping 1341 matching lines @@
 #undef ADDR
 };
 
 
 Address IC::AddressFromUtilityId(IC::UtilityId id) {
   return IC_utilities[id];
 }
 
 
 } }  // namespace v8::internal