Polymorphism support for load IC.

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 917 matching lines @@
       return ReferenceError("not_defined", name);
     }
     return *result;
   }
 
   // Get the property.
   return object->GetProperty(*object, &lookup, *name, &attr);
 }
 
 
+static bool AddOneReceiverMapIfMissing(MapHandleList* receiver_maps,
+                                       Handle<Map> new_receiver_map) {
+  ASSERT(!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)) {
+      return false;
+    }
+  }
+  receiver_maps->Add(new_receiver_map);
+  return true;
+}
+
+
+bool IC::UpdatePolymorphicIC(State state,
+                             StrictModeFlag strict_mode,
+                             Handle<JSObject> receiver,
+                             Handle<String> name,
+                             Handle<Code> code) {
+  if (code->type() == Code::NORMAL) return false;
+  if (target()->ic_state() == MONOMORPHIC &&
+      target()->type() == Code::NORMAL) {
+    return false;
+  }
+  MapHandleList receiver_maps;
+  CodeHandleList handlers;
+  target()->FindAllMaps(&receiver_maps);
+  int number_of_maps = receiver_maps.length();
+  if (number_of_maps == 0 || number_of_maps >= 4) return false;
+
+  target()->FindAllCode(&handlers, receiver_maps.length());
+
+  if (!AddOneReceiverMapIfMissing(&receiver_maps,
+                                  Handle<Map>(receiver->map()))) {
+    return false;
+  }
+
+  handlers.Add(code);
+  Handle<Code> ic = isolate()->stub_cache()->ComputePolymorphicIC(
+      &receiver_maps, &handlers, 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(
+      receiver, handler, name);
+  set_target(*ic);
+}
+
+
+void KeyedLoadIC::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()->ComputeKeyedMonomorphicIC(
+      receiver, handler, name);
+  set_target(*ic);
+}
+
+
 void IC::PatchCache(State state,
                     StrictModeFlag strict_mode,
                     Handle<JSObject> receiver,
                     Handle<String> name,
                     Handle<Code> code) {
   switch (state) {
     case UNINITIALIZED:
     case PREMONOMORPHIC:
     case MONOMORPHIC_PROTOTYPE_FAILURE:
-      set_target(*code);
+      UpdateMonomorphicIC(receiver, code, name);
       break;
     case MONOMORPHIC:
       // Only move to megamorphic if the target changes.
       if (target() != *code) {
-        // We are transitioning from monomorphic to megamorphic case.
-        // Place the current monomorphic stub and stub compiled for
-        // the receiver into stub cache.
-        Map* map = target()->FindFirstMap();
-        if (map != NULL) {
-          UpdateMegamorphicCache(map, *name, target());
+        if (target()->is_load_stub()) {
+          if (UpdatePolymorphicIC(state, strict_mode, receiver, name, code)) {
+            break;
+          }
+        }
+        // We are transitioning from monomorphic to megamorphic case.  Place the
+        // stub compiled for the receiver into stub cache.
+        if (target()->is_store_stub()) {
+          Map* map = target()->FindFirstMap();
+          if (map != NULL) {
+            UpdateMegamorphicCache(map, *name, target());

[Jakob Kummerow, 2013/03/01 22:21:04]

Don't you want to do this for load stubs too when UpdatePolymorphicIC() has
returned false? (Similar to how you do it in line 1050.)

[Toon Verwaest, 2013/03/04 10:54:08]

Done.

+          }
         }
         UpdateMegamorphicCache(receiver->map(), *name, *code);
         set_target((strict_mode == kStrictMode)
                      ? *megamorphic_stub_strict()
                      : *megamorphic_stub());
       }
       break;
     case MEGAMORPHIC:
       // Update the stub cache.
       UpdateMegamorphicCache(receiver->map(), *name, *code);
       break;
     case POLYMORPHIC:
-      // When trying to patch a polymorphic stub with anything other than
-      // another polymorphic stub, go generic.
-      // TODO(verwaest): Currently we always go generic since no polymorphic
-      // stubs enter this code path. Replace with proper updating once named
-      // load/store can also be polymorphic.
-      set_target((strict_mode == kStrictMode)
-                 ? *generic_stub_strict()
-                 : *generic_stub());
+      if (target()->is_load_stub()) {
+        if (UpdatePolymorphicIC(state, strict_mode, receiver, name, code)) {
+          break;
+        }
+        MapHandleList receiver_maps;
+        CodeHandleList handlers;
+        target()->FindAllMaps(&receiver_maps);
+        target()->FindAllCode(&handlers, receiver_maps.length());
+        for (int i = 0; i < receiver_maps.length(); i++) {
+          UpdateMegamorphicCache(*receiver_maps.at(i), *name, *handlers.at(i));
+        }
+        UpdateMegamorphicCache(receiver->map(), *name, *code);
+        set_target(*megamorphic_stub());
+      } else {
+        // When trying to patch a polymorphic keyed load/store element stub

[Jakob Kummerow, 2013/03/01 22:21:04]

Comment seems inaccurate: We end up here when we try to patch anything other
than a polymorphic load stub.

[Toon Verwaest, 2013/03/04 10:54:08]

The polymorphic stubs that are not load stubs are element load/store stubs.

On 2013/03/01 22:21:04, Jakob wrote:

+        // with anything other than another polymorphic stub, go generic.
+        set_target((strict_mode == kStrictMode)
+                   ? *generic_stub_strict()
+                   : *generic_stub());
+      }
       break;
     case DEBUG_STUB:
       break;
     case GENERIC:
       UNREACHABLE();
       break;
   }
 }
 
 
+static void GetReceiverMapsForStub(Handle<Code> stub,
+                                   MapHandleList* result) {
+  ASSERT(stub->is_inline_cache_stub());
+  switch (stub->ic_state()) {
+    case MONOMORPHIC: {
+      Map* map = stub->FindFirstMap();
+      if (map != NULL) {
+        result->Add(Handle<Map>(map));
+      }
+      break;
+    }
+    case POLYMORPHIC: {
+      AssertNoAllocation no_allocation;
+      int mask = RelocInfo::ModeMask(RelocInfo::EMBEDDED_OBJECT);
+      for (RelocIterator it(*stub, mask); !it.done(); it.next()) {
+        RelocInfo* info = it.rinfo();
+        Handle<Object> object(info->target_object(), stub->GetIsolate());
+        if (object->IsString()) break;
+        ASSERT(object->IsMap());
+        AddOneReceiverMapIfMissing(result, Handle<Map>::cast(object));
+      }
+      break;
+    }
+    case MEGAMORPHIC:
+      break;
+    case UNINITIALIZED:
+    case PREMONOMORPHIC:
+    case MONOMORPHIC_PROTOTYPE_FAILURE:
+    case GENERIC:
+    case DEBUG_STUB:
+      UNREACHABLE();
+      break;
+  }
+}
+
+
 void LoadIC::UpdateCaches(LookupResult* lookup,
                           State state,
                           Handle<Object> object,
                           Handle<String> name) {
   // Bail out if the result is not cacheable.
   if (!lookup->IsCacheable()) return;
 
   // Loading properties from values is not common, so don't try to
   // deal with non-JS objects here.
   if (!object->IsJSObject()) return;
 
   Handle<JSObject> receiver = Handle<JSObject>::cast(object);
   Handle<Code> code;
   if (state == UNINITIALIZED) {
     // 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 = pre_monomorphic_stub();
   } else {
-    code = ComputeLoadMonomorphic(lookup, receiver, name);
+    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) {
   // Cache code holding map should be consistent with
   // GenerateMonomorphicCacheProbe.
   isolate()->stub_cache()->Set(name, map, code);
 }
 
 
-Handle<Code> LoadIC::ComputeLoadMonomorphic(LookupResult* lookup,
-                                            Handle<JSObject> receiver,
-                                            Handle<String> name) {
+Handle<Code> LoadIC::ComputeLoadHandler(LookupResult* lookup,
+                                        Handle<JSObject> receiver,
+                                        Handle<String> name) {
   if (!lookup->IsProperty()) {
     // Nonexistent property. The result is undefined.
     return isolate()->stub_cache()->ComputeLoadNonexistent(name, receiver);
   }
 
   // Compute monomorphic stub.
   Handle<JSObject> holder(lookup->holder());
   switch (lookup->type()) {
     case FIELD:
       return isolate()->stub_cache()->ComputeLoadField(
           name, receiver, holder, lookup->GetFieldIndex());
     case CONSTANT_FUNCTION: {
       Handle<JSFunction> constant(lookup->GetConstantFunction());
       return isolate()->stub_cache()->ComputeLoadConstant(
           name, receiver, holder, constant);
     }
     case NORMAL:
       if (holder->IsGlobalObject()) {
         Handle<GlobalObject> global = Handle<GlobalObject>::cast(holder);
         Handle<JSGlobalPropertyCell> cell(global->GetPropertyCell(lookup));
         return isolate()->stub_cache()->ComputeLoadGlobal(
             name, receiver, global, cell, lookup->IsDontDelete());
       }
       // There is only one shared stub for loading normalized
       // properties. It does not traverse the prototype chain, so the
       // property must be found in the receiver for the stub to be
       // applicable.
       if (!holder.is_identical_to(receiver)) break;
-      return isolate()->stub_cache()->ComputeLoadNormal();
+      return isolate()->stub_cache()->ComputeLoadNormal(name, receiver);
     case CALLBACKS: {
       Handle<Object> callback(lookup->GetCallbackObject(), isolate());
       if (callback->IsExecutableAccessorInfo()) {
         Handle<ExecutableAccessorInfo> info =
             Handle<ExecutableAccessorInfo>::cast(callback);
         if (v8::ToCData<Address>(info->getter()) == 0) break;
         if (!info->IsCompatibleReceiver(*receiver)) break;
         return isolate()->stub_cache()->ComputeLoadCallback(
             name, receiver, holder, info);
       } else if (callback->IsAccessorPair()) {
@@ skipping 35 matching lines @@
         key = Handle<Smi>(Smi::FromInt(int_value), isolate);
       }
     }
   } else if (key->IsUndefined()) {
     key = isolate->factory()->undefined_symbol();
   }
   return key;
 }
 
 
-static bool AddOneReceiverMapIfMissing(MapHandleList* receiver_maps,
-                                       Handle<Map> new_receiver_map) {
-  ASSERT(!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)) {
-      return false;
-    }
-  }
-  receiver_maps->Add(new_receiver_map);
-  return true;
-}
-
-
-static void GetReceiverMapsForStub(Handle<Code> stub,
-                                   MapHandleList* result) {
-  ASSERT(stub->is_inline_cache_stub());
-  ASSERT(stub->is_keyed_load_stub() || stub->is_keyed_store_stub());
-  switch (stub->ic_state()) {
-    case MONOMORPHIC: {
-      Map* map = stub->FindFirstMap();
-      if (map != NULL) {
-        result->Add(Handle<Map>(map));
-      }
-      break;
-    }
-    case POLYMORPHIC: {
-      AssertNoAllocation no_allocation;
-      int mask = RelocInfo::ModeMask(RelocInfo::EMBEDDED_OBJECT);
-      for (RelocIterator it(*stub, mask); !it.done(); it.next()) {
-        RelocInfo* info = it.rinfo();
-        Handle<Object> object(info->target_object(), stub->GetIsolate());
-        ASSERT(object->IsMap());
-        AddOneReceiverMapIfMissing(result, Handle<Map>::cast(object));
-      }
-      break;
-    }
-    case MEGAMORPHIC:
-      break;
-    case UNINITIALIZED:
-    case PREMONOMORPHIC:
-    case MONOMORPHIC_PROTOTYPE_FAILURE:
-    case GENERIC:
-    case DEBUG_STUB:
-      UNREACHABLE();
-      break;
-  }
-}
-
-
 Handle<Code> KeyedLoadIC::LoadElementStub(Handle<JSObject> receiver) {
   State ic_state = target()->ic_state();
 
   // Don't handle megamorphic property accesses for INTERCEPTORS or CALLBACKS
   // via megamorphic stubs, since they don't have a map in their relocation info
   // and so the stubs can't be harvested for the object needed for a map check.
   if (target()->type() != Code::NORMAL) {
     TRACE_GENERIC_IC(isolate(), "KeyedIC", "non-NORMAL target type");
     return generic_stub();
   }
@@ skipping 91 matching lines @@
     ASSERT(!stub.is_null());
     set_target(*stub);
     TRACE_IC("KeyedLoadIC", key, state, target());
   }
 
 
   return Runtime::GetObjectProperty(isolate(), object, key);
 }
 
 
-Handle<Code> KeyedLoadIC::ComputeLoadMonomorphic(LookupResult* lookup,
-                                                 Handle<JSObject> receiver,
-                                                 Handle<String> name) {
+Handle<Code> KeyedLoadIC::ComputeLoadHandler(LookupResult* lookup,
+                                             Handle<JSObject> receiver,
+                                             Handle<String> name) {
   // Bail out if we didn't find a result.
   if (!lookup->IsProperty()) return Handle<Code>::null();
 
   // Compute a monomorphic stub.
   Handle<JSObject> holder(lookup->holder());
   switch (lookup->type()) {
     case FIELD:
       return isolate()->stub_cache()->ComputeKeyedLoadField(
           name, receiver, holder, lookup->GetFieldIndex());
     case CONSTANT_FUNCTION: {
@@ skipping 1279 matching lines @@
 #undef ADDR
 };
 
 
 Address IC::AddressFromUtilityId(IC::UtilityId id) {
   return IC_utilities[id];
 }
 
 
 } }  // namespace v8::internal