Better support for 'polymorphic' JS and external arrays

src/ic.cc

Index: src/ic.cc
diff --git a/src/ic.cc b/src/ic.cc
index 229992278d4b359697eb9e2395555d52b5bc2cc8..a5ac08cf9a6a1bbf1eeab1026f05ae93a2c6cdfe 100644
--- a/src/ic.cc
+++ b/src/ic.cc
@@ -1,4 +1,4 @@
-// Copyright 2006-2009 the V8 project authors. All rights reserved.
+// Copyright 2011 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:
@@ -67,7 +67,33 @@ void IC::TraceIC(const char* type,
     State new_state = StateFrom(new_target,
                                 HEAP->undefined_value(),
                                 HEAP->undefined_value());
-    PrintF("[%s (%c->%c)%s", type,
+    PrintF("[%s in ", type);
+    StackFrameIterator it;
+    while (it.frame()->fp() != this->fp()) it.Advance();
+    StackFrame* raw_frame = it.frame();
+    if (raw_frame->is_internal()) {
+      Isolate* isolate = new_target->GetIsolate();
+      Code* apply_builtin = isolate->builtins()->builtin(
+          Builtins::kFunctionApply);
+      if (raw_frame->unchecked_code() == apply_builtin) {
+        PrintF("apply from ");
+        it.Advance();
+        raw_frame = it.frame();
+      }
+    }
+    if (raw_frame->is_java_script()) {
+      JavaScriptFrame* frame = JavaScriptFrame::cast(raw_frame);
+      Code* js_code = frame->unchecked_code();
+      // Find the function on the stack and both the active code for the
+      // function and the original code.
+      JSFunction* function = JSFunction::cast(frame->function());
+      function->PrintName();
+      int code_offset = address() - js_code->instruction_start();
+      PrintF("+%d", code_offset);
+    } else {
+      PrintF("<unknown>");
+    }
+    PrintF(" (%c->%c)%s",
            TransitionMarkFromState(old_state),
            TransitionMarkFromState(new_state),
            extra_info);
@@ -274,11 +300,9 @@ void IC::Clear(Address address) {
   switch (target->kind()) {
     case Code::LOAD_IC: return LoadIC::Clear(address, target);
     case Code::KEYED_LOAD_IC:
-    case Code::KEYED_EXTERNAL_ARRAY_LOAD_IC:
       return KeyedLoadIC::Clear(address, target);
     case Code::STORE_IC: return StoreIC::Clear(address, target);
     case Code::KEYED_STORE_IC:
-    case Code::KEYED_EXTERNAL_ARRAY_STORE_IC:
       return KeyedStoreIC::Clear(address, target);
     case Code::CALL_IC: return CallIC::Clear(address, target);
     case Code::KEYED_CALL_IC:  return KeyedCallIC::Clear(address, target);
@@ -1030,9 +1054,50 @@ void LoadIC::UpdateCaches(LookupResult* lookup,
 }
 
 
+String* KeyedLoadIC::GetStubNameForCache(IC::State ic_state) {
+  if (ic_state == MONOMORPHIC) {
+    return isolate()->heap()->KeyedLoadSpecializedMonomorphic_symbol();
+  } else {
+    ASSERT(ic_state == MEGAMORPHIC);
+    return isolate()->heap()->KeyedLoadSpecializedPolymorphic_symbol();
+  }
+}
+
+
+MaybeObject* KeyedLoadIC::ConstructSpecializedKeyedIC(
+    Handle<Map> receiver_map,
+    StrictModeFlag strict_mode) {
+  Object* object;
+  KeyedLoadStubCompiler compiler;
+  MaybeObject* maybe_code = compiler.CompileLoadSpecialized(receiver_map);
+  if (!maybe_code->ToObject(&object)) return maybe_code;
+  PROFILE(isolate(), CodeCreateEvent(Logger::KEYED_LOAD_IC_TAG,
+                                     Code::cast(object), 0));
+  return object;
+}
+
+
+MaybeObject* KeyedLoadIC::ConstructMegamorphicKeyedIC(
+    ZoneMapList* receiver_maps,

[Mads Ager (chromium), 2011/04/28 13:02:01]

Do you have a zone at this point? Maybe just use normal C++ allocated lists for
these?

+    ZoneCodeList* targets,
+    StrictModeFlag strict_mode) {
+  Object* object;
+  KeyedLoadStubCompiler compiler;
+  MaybeObject* maybe_code = compiler.CompileLoadMegamorphic(receiver_maps,
+                                                            targets);
+  if (!maybe_code->ToObject(&object)) return maybe_code;
+  isolate()->counters()->keyed_load_polymorphic_stubs()->Increment();
+  PROFILE(isolate(), CodeCreateEvent(
+      Logger::KEYED_LOAD_MEGAMORPHIC_IC_TAG,
+      Code::cast(object), 0));
+  return object;
+}
+
+
 MaybeObject* KeyedLoadIC::Load(State state,
                                Handle<Object> object,
-                               Handle<Object> key) {
+                               Handle<Object> key,
+                               bool force_generic_stub) {
   // Check for values that can be converted into a symbol.
   // TODO(1295): Remove this code.
   HandleScope scope(isolate());
@@ -1156,39 +1221,49 @@ MaybeObject* KeyedLoadIC::Load(State state,
   // the global object).
   bool use_ic = FLAG_use_ic && !object->IsAccessCheckNeeded();
 
+#ifdef DEBUG
+  TraceIC("KeyedLoadIC", key, state, target());
+#endif  // DEBUG
+
+  Code* stub = generic_stub();
   if (use_ic) {
-    Code* stub = generic_stub();
-    if (state == UNINITIALIZED) {
+    if (!force_generic_stub) {
       if (object->IsString() && key->IsNumber()) {
-        stub = string_stub();
+        if (state == UNINITIALIZED) {
+          stub = string_stub();
+        }
       } else if (object->IsJSObject()) {
-        Handle<JSObject> receiver = Handle<JSObject>::cast(object);
-        if (receiver->HasExternalArrayElements()) {
-          MaybeObject* probe =
-              isolate()->stub_cache()->ComputeKeyedLoadOrStoreExternalArray(
-                  *receiver, false, kNonStrictMode);
-          stub = probe->IsFailure() ?
-              NULL : Code::cast(probe->ToObjectUnchecked());
-        } else if (receiver->HasIndexedInterceptor()) {
+        JSObject* receiver = JSObject::cast(*object);
+        if (receiver->HasIndexedInterceptor()) {
           stub = indexed_interceptor_stub();
-        } else if (key->IsSmi() &&
-                   receiver->map()->has_fast_elements()) {
-          MaybeObject* probe =
-              isolate()->stub_cache()->ComputeKeyedLoadSpecialized(*receiver);
-          stub = probe->IsFailure() ?
-              NULL : Code::cast(probe->ToObjectUnchecked());
+        } else if (key->IsSmi()) {
+          MaybeObject* maybe_stub = ComputeKeyedIC(receiver,
+                                                   false,
+                                                   kNonStrictMode,
+                                                   stub);
+          if (!maybe_stub->To(&stub)) return maybe_stub;
         }
       }
     }
-    if (stub != NULL) set_target(stub);
+  }
 
 #ifdef DEBUG
-    TraceIC("KeyedLoadIC", key, state, target());
+  TraceIC("KeyedLoadIC", key, state, stub);
 #endif  // DEBUG
-  }
+
+  HandleScope handle_scope(isolate());

[Mads Ager (chromium), 2011/04/28 13:02:01]

This is a nasty mix of handlified and non-handlified code. I don't understand
why this is needed. We really should just set the stub and then return the
result of a runtime lookup.

+  Handle<Code> stub_handle(stub); // Survives possible GC below.
 
   // Get the property.
-  return Runtime::GetObjectProperty(isolate(), object, key);
+  MaybeObject* result = Runtime::GetObjectProperty(isolate(), object, key);
+
+  ASSERT(!result->IsFailure());
+  if (use_ic) {
+    ASSERT(*stub_handle != NULL);
+    set_target(*stub_handle);
+  }
+
+  return result;
 }
 
 
@@ -1482,11 +1557,198 @@ void StoreIC::UpdateCaches(LookupResult* lookup,
 }
 
 
+static bool AddOneReceiverMapIfMissing(ZoneMapList* receiver_maps,
+                                       Map* new_receiver_map) {
+  for (int current = 0; current < receiver_maps->length(); ++current) {
+    if (*(receiver_maps->at(current)) == new_receiver_map) {
+      return false;
+    }
+  }
+  receiver_maps->Add(Handle<Map>(new_receiver_map));
+  return true;
+}
+
+
+static ZoneMapList* GetReceiverMapsForStub(Code* stub) {
+  ASSERT(stub->is_inline_cache_stub());
+  if (!stub->is_keyed_load_stub() && !stub->is_keyed_store_stub()) {
+    return new ZoneMapList(KeyedIC::kMaxKeyedPolymorphism);
+  }
+  ZoneMapList* result = new ZoneMapList(KeyedIC::kMaxKeyedPolymorphism);
+  AssertNoAllocation no_allocation;
+  if (stub->ic_state() == MONOMORPHIC) {
+    result->Add(Handle<Map>(Map::cast(stub->FindFirstMap())));
+  } else {
+    ASSERT(stub->ic_state() == MEGAMORPHIC);
+    ZoneMapList* result = new ZoneMapList(KeyedIC::kMaxKeyedPolymorphism);

[Mads Ager (chromium), 2011/04/28 13:02:01]

This looks wrong. You have a local |result| here that you modify and then you
return the empty one in the outer scope?

+    AssertNoAllocation no_allocation;
+    int mask = RelocInfo::ModeMask(RelocInfo::EMBEDDED_OBJECT);
+    for (RelocIterator it(stub, mask); !it.done(); it.next()) {
+      RelocInfo* info = it.rinfo();
+      Object* object = info->target_object();
+      ASSERT(object->IsMap());
+      result->Add(Handle<Map>(Map::cast(object)));
+    }
+  }
+  return result;
+}
+
+
+MaybeObject* KeyedIC::ComputeKeyedIC(JSObject* receiver,
+                                     bool is_store,
+                                     StrictModeFlag strict_mode,
+                                     Code* generic_stub) {
+  State ic_state = target()->ic_state();
+  Code* monomorphic_stub = generic_stub;
+
+  if (receiver->HasExternalArrayElements()) {
+    MaybeObject* maybe_stub =
+        isolate()->stub_cache()->ComputeKeyedLoadOrStoreExternalArray(
+            receiver, is_store, strict_mode);
+    if (maybe_stub->IsFailure()) return maybe_stub;
+    monomorphic_stub = Code::cast(maybe_stub->ToObjectUnchecked());
+  } else if (receiver->map()->has_fast_elements()) {
+    HandleScope handle_scope;

[Mads Ager (chromium), 2011/04/28 13:02:01]

This looks really dangerous. Is this handle scope only there because you are
doing lists of handles to maps? In that case, please use lists of raw maps.
Allocations are not safe here so I would prefer not to use handlified code. That
way it is completely clear that you have to check for failures and deal with it
appropriately and not call handlified methods that will garbage collect.

+    Code::Kind kind = this->kind();
+    Code::Flags flags = Code::ComputeMonomorphicFlags(kind, NORMAL, strict_mode);
+    String* name = GetStubNameForCache(MONOMORPHIC);
+    Object* maybe_cached_stub = receiver->map()->FindInCodeCache(name, flags);
+    if (maybe_cached_stub->IsUndefined()) {
+      MaybeObject* maybe_stub = ConstructSpecializedKeyedIC(
+          Handle<Map>(receiver->map()),
+          strict_mode);
+      if (!maybe_stub->To(&monomorphic_stub)) return maybe_stub;
+
+      MaybeObject* maybe_update = receiver->UpdateMapCodeCache(name, monomorphic_stub);
+      if (maybe_update->IsFailure()) return maybe_update;
+    } else {
+      monomorphic_stub = Code::cast(maybe_cached_stub);
+    }
+  }
+
+  if (ic_state == UNINITIALIZED) {
+    return monomorphic_stub;
+  }
+
+  ZoneScope zone_scope(DELETE_ON_EXIT);

[Mads Ager (chromium), 2011/04/28 13:02:01]

The lists here do not seem big enough to require zone allocation. I would just
use C++ allocation for them (see list.h).

+  HandleScope handle_scope;

[Mads Ager (chromium), 2011/04/28 13:02:01]

Let's not add HandleScopes here. That makes it very tempting to call handlified
methods which can garbage collect which is unsafe at this point. We need to
stick to raw pointers here to force ourselves to deal with allocation failures
directly.

+  // Determine the list of receiver maps that this call site has seen,
+  // adding the map that was just encountered.
+  ZoneMapList* target_receiver_maps = GetReceiverMapsForStub(target());
+  if (!AddOneReceiverMapIfMissing(target_receiver_maps, receiver->map())) {
+    // If the miss wasn't due to an unseen map, a MEGAMORPHIC stub
+    // won't help, use the generic stub.
+    return generic_stub;
+  }
+
+  Code::Kind kind = this->kind();
+  Code::Flags flags = Code::ComputeFlags(kind, NOT_IN_LOOP, MEGAMORPHIC, strict_mode);
+  String* megamorphic_name = GetStubNameForCache(MEGAMORPHIC);
+  Object* maybe_cached_stub = receiver->map()->FindInCodeCache(megamorphic_name, flags);
+
+  // Create a set of all receiver maps that have been seen at the IC call site
+  // and those seen by the MEGAMORPHIC cached stub, if that's the stub that's
+  // been selected.
+  ZoneMapList* receiver_maps = maybe_cached_stub->IsUndefined()
+      ? new ZoneMapList(KeyedIC::kMaxKeyedPolymorphism)
+      : GetReceiverMapsForStub(Code::cast(maybe_cached_stub));
+  bool added_map = false;
+  for (int i = 0; i < target_receiver_maps->length(); ++i) {
+    if (AddOneReceiverMapIfMissing(receiver_maps,
+                                   *(target_receiver_maps->at(i)))) {
+      added_map = true;
+    }
+  }
+
+  // If the maximum number of receiver maps has been exceeded, use the Generic
+  // version of the IC.
+  if (receiver_maps->length() > KeyedIC::kMaxKeyedPolymorphism) {
+    return generic_stub;
+  }
+
+  // If no maps have been seen at the call site that aren't in the cached
+  // stub, then use it.
+  if (!added_map) {
+    ASSERT(!maybe_cached_stub->IsUndefined());
+    ASSERT(maybe_cached_stub->IsCode());
+    return Code::cast(maybe_cached_stub);
+  }
+
+  // Lookup all of the receiver maps in the cache, they should all already

[Mads Ager (chromium), 2011/04/28 13:02:01]

This introduces a dependency that I don't think we have had before. Namely that
map caches cannot be cleared unless you also clear IC stubs in all code. This is
true by default. We have flags that could break this. We should probably remove
those flags. (Something like cleanup-caches-in-maps-at-gc and cleanup-ics-at-gc.
Those can no longer be set independently. Clearing map caches at GC will have to
always imply clearing ICs at GC.)

+  // have MONOMORPHIC stubs.
+  ZoneCodeList* handler_ics = new ZoneCodeList(KeyedIC::kMaxKeyedPolymorphism);
+  flags = Code::ComputeMonomorphicFlags(kind, NORMAL, strict_mode);
+  String* monomorphic_name = GetStubNameForCache(MONOMORPHIC);
+  for (int current = 0; current < receiver_maps->length(); ++current) {
+    Handle<Map> receiver_map(receiver_maps->at(current));
+    Object* maybe_cached_stub = receiver_map->FindInCodeCache(monomorphic_name, flags);
+    if (maybe_cached_stub->IsUndefined()) {
+      UNREACHABLE();
+      return generic_stub;
+    }
+    handler_ics->Add(Handle<Code>(Code::cast(maybe_cached_stub)));
+  }
+
+  Code* stub;
+  // Build the MEGAMORPHIC stub.
+  MaybeObject* maybe_stub = ConstructMegamorphicKeyedIC(receiver_maps,
+                                                        handler_ics,
+                                                        strict_mode);
+  if (!maybe_stub->To(&stub)) return maybe_stub;
+
+  MaybeObject* maybe_update = receiver->UpdateMapCodeCache(
+      megamorphic_name,
+      stub);
+  if (maybe_update->IsFailure()) return maybe_update;
+  return stub;
+}
+
+
+String* KeyedStoreIC::GetStubNameForCache(IC::State ic_state) {
+  if (ic_state == MONOMORPHIC) {
+    return isolate()->heap()->KeyedStoreSpecializedMonomorphic_symbol();
+  } else {
+    ASSERT(ic_state == MEGAMORPHIC);
+    return isolate()->heap()->KeyedStoreSpecializedPolymorphic_symbol();
+  }
+}
+
+
+MaybeObject* KeyedStoreIC::ConstructSpecializedKeyedIC(
+    Handle<Map> receiver_map,
+    StrictModeFlag strict_mode) {
+  Object* object;
+  KeyedStoreStubCompiler compiler(strict_mode);
+  MaybeObject* maybe_code = compiler.CompileStoreSpecialized(receiver_map);
+  if (!maybe_code->ToObject(&object)) return maybe_code;
+  PROFILE(isolate(), CodeCreateEvent(Logger::KEYED_STORE_IC_TAG,
+                                     Code::cast(object), 0));
+  return object;
+}
+
+
+MaybeObject* KeyedStoreIC::ConstructMegamorphicKeyedIC(
+    ZoneMapList* receiver_maps,
+    ZoneCodeList* targets,
+    StrictModeFlag strict_mode) {
+  Object* object;
+  KeyedStoreStubCompiler compiler(strict_mode);
+  MaybeObject* maybe_code = compiler.CompileStoreMegamorphic(receiver_maps, targets);
+  if (!maybe_code->ToObject(&object)) return maybe_code;
+  isolate()->counters()->keyed_store_polymorphic_stubs()->Increment();
+  PROFILE(isolate(), CodeCreateEvent(
+      Logger::KEYED_STORE_MEGAMORPHIC_IC_TAG,
+      Code::cast(object), 0));
+  return object;
+}
+
+
 MaybeObject* KeyedStoreIC::Store(State state,
                                  StrictModeFlag strict_mode,
                                  Handle<Object> object,
                                  Handle<Object> key,
-                                 Handle<Object> value) {
+                                 Handle<Object> value,
+                                 bool force_generic) {
   if (key->IsSymbol()) {
     Handle<String> name = Handle<String>::cast(key);
 
@@ -1527,33 +1789,40 @@ MaybeObject* KeyedStoreIC::Store(State state,
   bool use_ic = FLAG_use_ic && !object->IsAccessCheckNeeded();
   ASSERT(!(use_ic && object->IsJSGlobalProxy()));
 
+  Code* stub = (strict_mode == kStrictMode)
+      ? generic_stub_strict()
+      : generic_stub();
   if (use_ic) {
-    Code* stub =
-        (strict_mode == kStrictMode) ? generic_stub_strict() : generic_stub();
-    if (state == UNINITIALIZED) {
-      if (object->IsJSObject()) {
-        Handle<JSObject> receiver = Handle<JSObject>::cast(object);
-        if (receiver->HasExternalArrayElements()) {
-          MaybeObject* probe =
-              isolate()->stub_cache()->ComputeKeyedLoadOrStoreExternalArray(
-                  *receiver, true, strict_mode);
-          stub = probe->IsFailure() ?
-              NULL : Code::cast(probe->ToObjectUnchecked());
-        } else if (key->IsSmi() && receiver->map()->has_fast_elements()) {
-          MaybeObject* probe =
-              isolate()->stub_cache()->ComputeKeyedStoreSpecialized(
-                  *receiver, strict_mode);
-          stub = probe->IsFailure() ?
-              NULL : Code::cast(probe->ToObjectUnchecked());
-        }
+    if (!force_generic) {
+      if (object->IsJSObject() && key->IsSmi()) {
+        JSObject* receiver = JSObject::cast(*object);
+        MaybeObject* maybe_stub = ComputeKeyedIC(receiver,
+                                                 true,
+                                                 strict_mode,
+                                                 stub);
+        if (!maybe_stub->To(&stub)) return maybe_stub;
       }
     }
-    if (stub != NULL) set_target(stub);
   }
 
+#ifdef DEBUG
+  TraceIC("KeyedStoreIC", key, state, stub);
+#endif
+
+  HandleScope handle_scope(isolate());
+  Handle<Code> stub_handle(stub); // Survives possible GC below.
+
   // Set the property.
-  return Runtime::SetObjectProperty(
+  MaybeObject* result = Runtime::SetObjectProperty(
       isolate(), object , key, value, NONE, strict_mode);
+
+  ASSERT(!result->IsFailure());
+  if (use_ic) {
+    ASSERT(*stub_handle != NULL);
+    set_target(*stub_handle);
+  }
+
+  return result;
 }
 
 
@@ -1719,7 +1988,16 @@ RUNTIME_FUNCTION(MaybeObject*, KeyedLoadIC_Miss) {
   ASSERT(args.length() == 2);
   KeyedLoadIC ic(isolate);
   IC::State state = IC::StateFrom(ic.target(), args[0], args[1]);
-  return ic.Load(state, args.at<Object>(0), args.at<Object>(1));
+  return ic.Load(state, args.at<Object>(0), args.at<Object>(1), false);
+}
+
+
+RUNTIME_FUNCTION(MaybeObject*, KeyedLoadIC_MissForceGeneric) {
+  NoHandleAllocation na;
+  ASSERT(args.length() == 2);
+  KeyedLoadIC ic(isolate);
+  IC::State state = IC::StateFrom(ic.target(), args[0], args[1]);
+  return ic.Load(state, args.at<Object>(0), args.at<Object>(1), true);
 }
 
 
@@ -1803,7 +2081,23 @@ RUNTIME_FUNCTION(MaybeObject*, KeyedStoreIC_Miss) {
                   static_cast<StrictModeFlag>(extra_ic_state & kStrictMode),
                   args.at<Object>(0),
                   args.at<Object>(1),
-                  args.at<Object>(2));
+                  args.at<Object>(2),
+                  false);
+}
+
+
+RUNTIME_FUNCTION(MaybeObject*, KeyedStoreIC_MissForceGeneric) {
+  NoHandleAllocation na;
+  ASSERT(args.length() == 3);
+  KeyedStoreIC ic(isolate);
+  IC::State state = IC::StateFrom(ic.target(), args[0], args[1]);
+  Code::ExtraICState extra_ic_state = ic.target()->extra_ic_state();
+  return ic.Store(state,
+                  static_cast<StrictModeFlag>(extra_ic_state & kStrictMode),
+                  args.at<Object>(0),
+                  args.at<Object>(1),
+                  args.at<Object>(2),
+                  true);
 }