Unify grow mode and stub kind

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 41 matching lines @@
 
     // We never see the debugger states here, because the state is
     // computed from the original code - not the patched code. Let
     // these cases fall through to the unreachable code below.
     case DEBUG_STUB: break;
   }
   UNREACHABLE();
   return 0;
 }
 
+
+const char* GetTransitionMarkModifier(KeyedAccessStoreMode mode) {
+  if (mode == STORE_NO_TRANSITION_HANDLE_COW) return ".COW";
+  if (mode == STORE_NO_TRANSITION_IGNORE_OUT_OF_BOUNDS) {
+    return ".IGNORE_OOB";
+  }
+  if (IsGrowStoreMode(mode)) return ".GROW";
+  return "";
+}
+
+
 void IC::TraceIC(const char* type,
                  Handle<Object> name,
                  State old_state,
                  Code* new_target) {
   if (FLAG_trace_ic) {
     Object* undef = new_target->GetHeap()->undefined_value();
     State new_state = StateFrom(new_target, undef, undef);
     PrintF("[%s in ", type);
     Isolate* isolate = new_target->GetIsolate();
     StackFrameIterator it(isolate);
     while (it.frame()->fp() != this->fp()) it.Advance();
     StackFrame* raw_frame = it.frame();
     if (raw_frame->is_internal()) {
       Code* apply_builtin = isolate->builtins()->builtin(
           Builtins::kFunctionApply);
       if (raw_frame->unchecked_code() == apply_builtin) {
         PrintF("apply from ");
         it.Advance();
         raw_frame = it.frame();
       }
     }
     JavaScriptFrame::PrintTop(isolate, stdout, false, true);
-    bool new_can_grow =
-        Code::GetKeyedAccessGrowMode(new_target->extra_ic_state()) ==
-        ALLOW_JSARRAY_GROWTH;
+    Code::ExtraICState state = new_target->extra_ic_state();
+    const char* modifier =
+        GetTransitionMarkModifier(Code::GetKeyedAccessStoreMode(state));
     PrintF(" (%c->%c%s)",
            TransitionMarkFromState(old_state),
            TransitionMarkFromState(new_state),
-           new_can_grow ? ".GROW" : "");
+           modifier);
     name->Print();
     PrintF("]\n");
   }
 }
 
 #define TRACE_GENERIC_IC(isolate, type, reason)                 \
   do {                                                          \
     if (FLAG_trace_ic) {                                        \
       PrintF("[%s patching generic stub in ", type);            \
       JavaScriptFrame::PrintTop(isolate, stdout, false, true);  \
@@ skipping 1494 matching lines @@
     case NONEXISTENT:
     case HANDLER:
       UNREACHABLE();
       break;
   }
   return Handle<Code>::null();
 }
 
 
 Handle<Code> KeyedStoreIC::StoreElementStub(Handle<JSObject> receiver,
-                                            StubKind stub_kind,
+                                            KeyedAccessStoreMode store_mode,
                                             StrictModeFlag strict_mode) {
-  State ic_state = target()->ic_state();
-  KeyedAccessGrowMode grow_mode = IsGrowStubKind(stub_kind)
-      ? ALLOW_JSARRAY_GROWTH
-      : DO_NOT_ALLOW_JSARRAY_GROWTH;
-
   // 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 strict_mode == kStrictMode ? generic_stub_strict() : generic_stub();
   }
 
+  if ((store_mode == STORE_NO_TRANSITION_HANDLE_COW ||
+       store_mode == STORE_NO_TRANSITION_IGNORE_OUT_OF_BOUNDS)) {
+    // TODO(danno): We'll soon handle MONOMORPHIC ICs that also support
+    // copying COW arrays and silently ignoring some OOB stores into external
+    // arrays, but for now use the generic.
+    TRACE_GENERIC_IC(isolate(), "KeyedIC", "COW/OOB external array");
+    return strict_mode == kStrictMode
+        ? generic_stub_strict()
+        : generic_stub();
+  }
+
+  State ic_state = target()->ic_state();
   Handle<Map> receiver_map(receiver->map());
   MapHandleList target_receiver_maps;
   if (ic_state == UNINITIALIZED || ic_state == PREMONOMORPHIC) {
     // Optimistically assume that ICs that haven't reached the MONOMORPHIC state
     // yet will do so and stay there.
-    Handle<Map> monomorphic_map = ComputeTransitionedMap(receiver, stub_kind);
-    stub_kind = GetNoTransitionStubKind(stub_kind);
+    Handle<Map> monomorphic_map = ComputeTransitionedMap(receiver, store_mode);
+    store_mode = GetUntransitionedStoreMode(store_mode);

[Toon Verwaest, 2013/03/06 14:47:28]

GetNonTransitioningStoreMode? The store mode itself is not untransitioned right?

[danno, 2013/03/06 16:56:06]

Done.

     return isolate()->stub_cache()->ComputeKeyedStoreElement(
-        monomorphic_map, stub_kind, strict_mode, grow_mode);
+        monomorphic_map, strict_mode, store_mode);
   }
 
   GetReceiverMapsForStub(Handle<Code>(target()), &target_receiver_maps);

[Toon Verwaest, 2013/03/06 14:47:28]

Not directly related to this CL, but I think we can get rid of
GetReceiverMapsForStub, and just use
target()->FindAllMaps(&target_receiver_maps) instead.

[danno, 2013/03/06 16:56:06]

Done.

   if (target_receiver_maps.length() == 0) {
     // Optimistically assume that ICs that haven't reached the MONOMORPHIC state
     // yet will do so and stay there.
-    stub_kind = GetNoTransitionStubKind(stub_kind);
+    store_mode = GetUntransitionedStoreMode(store_mode);
     return isolate()->stub_cache()->ComputeKeyedStoreElement(
-        receiver_map, stub_kind, strict_mode, grow_mode);
+        receiver_map, strict_mode, store_mode);
   }
-  // The first time a receiver is seen that is a transitioned version of the
-  // previous monomorphic receiver type, assume the new ElementsKind is the
-  // monomorphic type. This benefits global arrays that only transition
-  // once, and all call sites accessing them are faster if they remain
-  // monomorphic. If this optimistic assumption is not true, the IC will
-  // miss again and it will become polymorphic and support both the
-  // untransitioned and transitioned maps.
-  if (ic_state == MONOMORPHIC &&
-      IsTransitionStubKind(stub_kind) &&
-      IsMoreGeneralElementsKindTransition(
-          target_receiver_maps.at(0)->elements_kind(),
-          receiver->GetElementsKind())) {
-    Handle<Map> monomorphic_map = ComputeTransitionedMap(receiver, stub_kind);
-    ASSERT(*monomorphic_map != *receiver_map);
-    stub_kind = GetNoTransitionStubKind(stub_kind);
-    return isolate()->stub_cache()->ComputeKeyedStoreElement(
-        monomorphic_map, stub_kind, strict_mode, grow_mode);
+
+  // There are several special cases where a IC that is MONOMORPHIC can still

[Toon Verwaest, 2013/03/06 14:47:28]

an IC

[danno, 2013/03/06 16:56:06]

Done.

+  // transition to a different GetUntransitionedStoreMode 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 =
+      Code::GetKeyedAccessStoreMode(target()->extra_ic_state());

[Toon Verwaest, 2013/03/06 14:47:28]

As far as I can tell, we are not certain that the target() is actually a
store-element stub. The map we retrieved may be a random map of a prototype that
we checked, in case of a prototype chain check required for a, for example,
global property load. We can make odd decisions based on such maps. Probably
this will not result in wrong semantics, but may have weird performance
implications.

Can we use the extra_ic_state somehow to distinguish different types of Keyed
Store ICs? Non-element-stores should only use the extra_ic_state for encoding
the strict-mode afaik.

[danno, 2013/03/06 16:56:06]

Done.

+  Handle<Map> previous_receiver_map = target_receiver_maps.at(0);
+  if (ic_state == MONOMORPHIC && old_store_mode == STORE_NO_TRANSITION) {
+    Handle<Map> transitioned_receiver_map = receiver_map;
+    if (IsTransitionStoreMode(store_mode)) {
+      transitioned_receiver_map =
+          ComputeTransitionedMap(receiver, store_mode);
+    }
+    ElementsKind transitioned_kind =
+        transitioned_receiver_map->elements_kind();
+    bool more_general_transition =
+        IsMoreGeneralElementsKindTransition(
+            previous_receiver_map->elements_kind(),
+            transitioned_kind);
+    Map* transitioned_previous_map = more_general_transition
+        ? previous_receiver_map->LookupElementsTransitionMap(transitioned_kind)
+        : NULL;
+    if (transitioned_previous_map == *transitioned_receiver_map) {
+      store_mode = GetUntransitionedStoreMode(store_mode);
+      return isolate()->stub_cache()->ComputeKeyedStoreElement(
+          transitioned_receiver_map, strict_mode, store_mode);
+    } else if (*previous_receiver_map == receiver->map()) {
+      if (store_mode == IsGrowStoreMode(store_mode)) {

[Toon Verwaest, 2013/03/06 14:47:28]

It seems like store_mode == IsGrowStoreMode(store_mode) is always false?

If you meant to write something like
IsNonTransitioningGrowStoreMode(store_mode), Isn't that a tautology within its
surrounding branch? If the original receiver maps were equal, and we didn't
transition (which is what the previous branch implies), we can't have a
transitioning store right?

In any case, this whole block of code is pretty hard to wade through. I'd prefer
if it were restructured to make it more obvious which cases it's handling.

[danno, 2013/03/06 16:56:06]

Done.

+        // A "normal" IC that handles stores can switch to a version that can
+        // grow at the end of the array and still stay MONOMORPHIC.
+        return isolate()->stub_cache()->ComputeKeyedStoreElement(
+            receiver_map, strict_mode, store_mode);
+      }
+    }
   }
 
   ASSERT(ic_state != GENERIC);
 
   bool map_added =
       AddOneReceiverMapIfMissing(&target_receiver_maps, receiver_map);
 
-  if (IsTransitionStubKind(stub_kind)) {
-    Handle<Map> new_map = ComputeTransitionedMap(receiver, stub_kind);
+  if (IsTransitionStoreMode(store_mode)) {
+    Handle<Map> new_map = ComputeTransitionedMap(receiver, store_mode);

[Toon Verwaest, 2013/03/06 14:47:28]

Can we also call this transitioned_receiver_map, to be consistent with code
above?

[danno, 2013/03/06 16:56:06]

Done.

     map_added |= AddOneReceiverMapIfMissing(&target_receiver_maps, new_map);
   }
 
   if (!map_added) {
     // If the miss wasn't due to an unseen map, a polymorphic stub
     // won't help, use the generic stub.
     TRACE_GENERIC_IC(isolate(), "KeyedIC", "same map added twice");
     return strict_mode == kStrictMode ? generic_stub_strict() : generic_stub();
   }
 
   // If the maximum number of receiver maps has been exceeded, use the generic
   // version of the IC.
   if (target_receiver_maps.length() > kMaxKeyedPolymorphism) {
     TRACE_GENERIC_IC(isolate(), "KeyedIC", "max polymorph exceeded");
     return strict_mode == kStrictMode ? generic_stub_strict() : generic_stub();
   }
 
-  if ((Code::GetKeyedAccessGrowMode(target()->extra_ic_state()) ==
-       ALLOW_JSARRAY_GROWTH)) {
-    grow_mode = ALLOW_JSARRAY_GROWTH;
+  // Make sure all polymorphic handlers have the same store mode, otherwise the
+  // generic stub must be used.
+  store_mode = GetUntransitionedStoreMode(store_mode);
+  if (old_store_mode != STORE_NO_TRANSITION) {

[Toon Verwaest, 2013/03/06 14:47:28]

Meaning STORE_AND_GROW_NO_TRANSITION?

[danno, 2013/03/06 16:56:06]

Well, this is currently correct, but for the next CL OOB and COW will also !=
STORE_NO_TRANSITION

+    if (store_mode == STORE_NO_TRANSITION) {
+      store_mode = old_store_mode;
+    } else if (store_mode != old_store_mode) {

[Toon Verwaest, 2013/03/06 14:47:28]

Can this happen? I presumed though would only be possible if

store_mode == STORE_NO_TRANSITION_IGNORE_OUT_OF_BOUNDS ||
store_mode == STORE_NO_TRANSITION_HANDLE_COW
(or old_store_mode == one of those).

But both cases are already excluded at the top of the function.

[danno, 2013/03/06 16:56:06]

As discussed offline, no change needed.

On 2013/03/06 14:47:28, Toon Verwaest wrote:

+      TRACE_GENERIC_IC(isolate(), "KeyedIC", "store mode mismatch");
+      return strict_mode == kStrictMode
+          ? generic_stub_strict()
+          : generic_stub();
+    }
   }
 
   return isolate()->stub_cache()->ComputeStoreElementPolymorphic(
-      &target_receiver_maps, grow_mode, strict_mode);
+      &target_receiver_maps, store_mode, strict_mode);
 }
 
 
-Handle<Map> KeyedStoreIC::ComputeTransitionedMap(Handle<JSObject> receiver,
-                                                 StubKind stub_kind) {
-  switch (stub_kind) {
+Handle<Map> KeyedStoreIC::ComputeTransitionedMap(
+    Handle<JSObject> receiver,
+    KeyedAccessStoreMode store_mode) {
+  switch (store_mode) {
     case STORE_TRANSITION_SMI_TO_OBJECT:
     case STORE_TRANSITION_DOUBLE_TO_OBJECT:
     case STORE_AND_GROW_TRANSITION_SMI_TO_OBJECT:
     case STORE_AND_GROW_TRANSITION_DOUBLE_TO_OBJECT:
       return JSObject::GetElementsTransitionMap(receiver, FAST_ELEMENTS);
     case STORE_TRANSITION_SMI_TO_DOUBLE:
     case STORE_AND_GROW_TRANSITION_SMI_TO_DOUBLE:
       return JSObject::GetElementsTransitionMap(receiver, FAST_DOUBLE_ELEMENTS);
     case STORE_TRANSITION_HOLEY_SMI_TO_OBJECT:
     case STORE_TRANSITION_HOLEY_DOUBLE_TO_OBJECT:
     case STORE_AND_GROW_TRANSITION_HOLEY_SMI_TO_OBJECT:
     case STORE_AND_GROW_TRANSITION_HOLEY_DOUBLE_TO_OBJECT:
       return JSObject::GetElementsTransitionMap(receiver,
                                                 FAST_HOLEY_ELEMENTS);
     case STORE_TRANSITION_HOLEY_SMI_TO_DOUBLE:
     case STORE_AND_GROW_TRANSITION_HOLEY_SMI_TO_DOUBLE:
       return JSObject::GetElementsTransitionMap(receiver,
                                                 FAST_HOLEY_DOUBLE_ELEMENTS);
+    case STORE_NO_TRANSITION_IGNORE_OUT_OF_BOUNDS:
+      ASSERT(receiver->map()->has_external_array_elements());
+      // Fall through
+    case STORE_NO_TRANSITION_HANDLE_COW:
     case STORE_NO_TRANSITION:
     case STORE_AND_GROW_NO_TRANSITION:
       return Handle<Map>(receiver->map());
   }
   return Handle<Map>::null();
 }
 
 
-KeyedStoreIC::StubKind KeyedStoreIC::GetStubKind(Handle<JSObject> receiver,
-                                                 Handle<Object> key,
-                                                 Handle<Object> value) {
+bool IsOutOfBoundsAccess(Handle<JSObject> receiver,
+                         int index) {
+  if (receiver->IsJSArray()) {

[Toon Verwaest, 2013/03/06 14:47:28]

Maybe add a comment stating that for JSArrays (including external arrays),
negative indices are handled as properties, and thus don't fall under OOB.

[danno, 2013/03/06 16:56:06]

Done.

+    return JSArray::cast(*receiver)->length()->IsSmi() &&
+        index >= Smi::cast(JSArray::cast(*receiver)->length())->value();
+  }
+  return index >= receiver->elements()->length() || index < 0;
+}
+
+
+KeyedAccessStoreMode KeyedStoreIC::GetStoreMode(Handle<JSObject> receiver,
+                                                Handle<Object> key,
+                                                Handle<Object> value) {
   ASSERT(key->IsSmi());
   int index = Smi::cast(*key)->value();
-  bool allow_growth = receiver->IsJSArray() &&
-      JSArray::cast(*receiver)->length()->IsSmi() &&
-      index >= Smi::cast(JSArray::cast(*receiver)->length())->value();
-
+  bool oob_access = IsOutOfBoundsAccess(receiver, index);
+  bool allow_growth = receiver->IsJSArray() && oob_access;
   if (allow_growth) {
     // Handle growing array in stub if necessary.
     if (receiver->HasFastSmiElements()) {
       if (value->IsHeapNumber()) {
         if (receiver->HasFastHoleyElements()) {
           return STORE_AND_GROW_TRANSITION_HOLEY_SMI_TO_DOUBLE;
         } else {
           return STORE_AND_GROW_TRANSITION_SMI_TO_DOUBLE;
         }
       }
@@ skipping 32 matching lines @@
       }
     } else if (receiver->HasFastDoubleElements()) {
       if (!value->IsSmi() && !value->IsHeapNumber()) {
         if (receiver->HasFastHoleyElements()) {
           return STORE_TRANSITION_HOLEY_DOUBLE_TO_OBJECT;
         } else {
           return STORE_TRANSITION_DOUBLE_TO_OBJECT;
         }
       }
     }
-    return STORE_NO_TRANSITION;
+    if (!FLAG_trace_external_array_abuse &&
+        receiver->map()->has_external_array_elements() && oob_access) {
+      return STORE_NO_TRANSITION_IGNORE_OUT_OF_BOUNDS;
+    } else {
+      return STORE_NO_TRANSITION;
+    }
   }
 }
 
 
 MaybeObject* KeyedStoreIC::Store(State state,
                                  StrictModeFlag strict_mode,
                                  Handle<Object> object,
                                  Handle<Object> key,
                                  Handle<Object> value,
                                  ICMissMode miss_mode) {
@@ skipping 19 matching lines @@
     Handle<Code> stub = (strict_mode == kStrictMode)
         ? generic_stub_strict()
         : generic_stub();
     if (miss_mode != MISS_FORCE_GENERIC) {
       if (object->IsJSObject()) {
         Handle<JSObject> receiver = Handle<JSObject>::cast(object);
         if (receiver->elements()->map() ==
             isolate()->heap()->non_strict_arguments_elements_map()) {
           stub = non_strict_arguments_stub();
         } else if (key->IsSmi() && (target() != *non_strict_arguments_stub())) {
-          StubKind stub_kind = GetStubKind(receiver, key, value);
-          stub = StoreElementStub(receiver, stub_kind, strict_mode);
+          KeyedAccessStoreMode store_mode = GetStoreMode(receiver, key, value);
+          stub = StoreElementStub(receiver, store_mode, strict_mode);
         }
       }
     } else {
       TRACE_GENERIC_IC(isolate(), "KeyedStoreIC", "force generic");
     }
     ASSERT(!stub.is_null());
     set_target(*stub);
     TRACE_IC("KeyedStoreIC", key, state, target());
   }
 
@@ skipping 808 matching lines @@
 #undef ADDR
 };
 
 
 Address IC::AddressFromUtilityId(IC::UtilityId id) {
   return IC_utilities[id];
 }
 
 
 } }  // namespace v8::internal