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() ||

[danno, 2013/05/02 11:36:06]

// Determine whether the failure is due to a name failure or a prototype chain
failure.

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

+      target->is_keyed_call_stub() ||
+      target->is_keyed_store_stub()) {
+    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);
+    if (target->is_load_stub() || target->is_keyed_load_stub()) {

[danno, 2013/05/02 11:36:06]

// For loads, handlers are stored in addition to the ICs on the map. Remove
those, too.

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

+      Code* handler = target->FindFirstCode();
+      index = map->IndexInCodeCache(name, handler);
+      if (index >= 0) {
+        map->RemoveFromCodeCache(String::cast(name), handler, index);
+      }
+    }
     return true;
   }
 
-  return false;
+  if (cache_holder != OWN_MAP) return false;

[danno, 2013/05/02 11:36:06]

// If the IC is shared between multiple receivers (slow dictionary mode), then
the map cannot be deprecated and the stub invalidated.

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

+
+  // Also flag monomorphic prototype failure if the old map was deprecated.
+  Map* old_map = target->FindFirstMap();
+  if (old_map == NULL) return false;
+  return old_map == map || old_map->is_deprecated();

[danno, 2013/05/02 11:36:06]

// 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. Tread deprecated maps in the same way as prototype failures
(stay monomorphic if possible).

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

 }
 
 
 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 230 matching lines @@
     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;
+  bool overwrote = false;

[danno, 2013/05/02 11:36:06]

// If the name doesn't match, go generic. Otherwise, if one of the maps already
in the polymorphic ic is the receiver map, just overwrite the handler. This
handles both the prototype chain changes and deprecated maps without prematurely
going generic. 

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

+  Handle<Map> new_receiver_map(receiver->map());
+  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)) {
+      overwrote = true;
+      handlers.InsertAt(current, code);
+      break;
+    }
   }

[danno, 2013/05/02 11:36:06]

Move this loop about the code above to get the map count right. Better yet, fold
the two loops together.

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

 
-  handlers.Add(code);
+  if (!overwrote) {
+    receiver_maps.Add(new_receiver_map);
+    handlers.Add(code);
+    number_of_valid_maps++;
+  }
+
   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 14 matching lines @@
 
 void IC::CopyICToMegamorphicCache(Handle<String> name) {
   MapHandleList receiver_maps;
   CodeHandleList handlers;
   {
     AssertNoAllocation no_gc;
     target()->FindAllMaps(&receiver_maps);
     target()->FindAllCode(&handlers, receiver_maps.length());
   }
   for (int i = 0; i < receiver_maps.length(); i++) {
+    if (receiver_maps.at(i)->is_deprecated()) continue;

[danno, 2013/05/02 11:36:06]

Maybe defer this to Crankshaft? Don't throw away the deprecated maps, just
replace them with their promoted version. Whatever you decide, please comment
about the reasoning.

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

     UpdateMegamorphicCache(*receiver_maps.at(i), *name, *handlers.at(i));
   }
 }
 
 
 bool IC::IsTransitionedMapOfMonomorphicTarget(Map* receiver_map) {
   AssertNoAllocation no_allocation;
 
   Map* current_map = target()->FindFirstMap();
   ElementsKind receiver_elements_kind = receiver_map->elements_kind();
@@ skipping 32 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 (!value->FitsRepresentation(target_details.representation())) {

[danno, 2013/05/02 11:36:06]

Comment this.

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

+    Handle<Map> target(lookup->GetTransitionMapFromMap(receiver->map()));
+    Map::GeneralizeRepresentation(
+        target, target->LastAdded(), value->OptimalRepresentation());
+    *state = MONOMORPHIC_PROTOTYPE_FAILURE;

[danno, 2013/05/02 11:36:06]

Check for already deprecated maps? Deprecated maps shouldn't change the target
at all?

[Toon Verwaest, 2013/05/02 12:27:20]

Done.

+  }
+  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