[turbofan] Initial support for transitioning stores.

src/compiler/js-native-context-specialization.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/js-native-context-specialization.h"
 
 #include "src/accessors.h"
 #include "src/compilation-dependencies.h"
 #include "src/compiler/access-builder.h"
 #include "src/compiler/js-graph.h"
@@ skipping 230 matching lines @@
       simplified()->StoreField(AccessBuilder::ForPropertyCellValue()),
       jsgraph()->Constant(property_cell), value, effect, control);
   return Replace(node, value, effect, control);
 }
 
 
 // This class encapsulates all information required to access a certain
 // object property, either on the object itself or on the prototype chain.
 class JSNativeContextSpecialization::PropertyAccessInfo final {
  public:
-  enum Kind { kInvalid, kDataConstant, kDataField };
+  enum Kind { kInvalid, kDataConstant, kDataField, kTransitionToField };
 
   static PropertyAccessInfo DataConstant(Type* receiver_type,
                                          Handle<Object> constant,
                                          MaybeHandle<JSObject> holder) {
     return PropertyAccessInfo(holder, constant, receiver_type);
   }
-  static PropertyAccessInfo DataField(Type* receiver_type,
-                                      FieldIndex field_index, Type* field_type,
-                                      MaybeHandle<JSObject> holder) {
+  static PropertyAccessInfo DataField(
+      Type* receiver_type, FieldIndex field_index, Type* field_type,
+      MaybeHandle<JSObject> holder = MaybeHandle<JSObject>()) {
     return PropertyAccessInfo(holder, field_index, field_type, receiver_type);
   }
+  static PropertyAccessInfo TransitionToField(Type* receiver_type,
+                                              FieldIndex field_index,
+                                              Type* field_type,
+                                              Handle<Map> transition_map,
+                                              MaybeHandle<JSObject> holder) {
+    return PropertyAccessInfo(holder, transition_map, field_index, field_type,
+                              receiver_type);
+  }
 
   PropertyAccessInfo() : kind_(kInvalid) {}
   PropertyAccessInfo(MaybeHandle<JSObject> holder, Handle<Object> constant,
                      Type* receiver_type)
       : kind_(kDataConstant),
         receiver_type_(receiver_type),
         constant_(constant),
         holder_(holder) {}
   PropertyAccessInfo(MaybeHandle<JSObject> holder, FieldIndex field_index,
                      Type* field_type, Type* receiver_type)
       : kind_(kDataField),
         receiver_type_(receiver_type),
         holder_(holder),
         field_index_(field_index),
         field_type_(field_type) {}
+  PropertyAccessInfo(MaybeHandle<JSObject> holder, Handle<Map> transition_map,
+                     FieldIndex field_index, Type* field_type,
+                     Type* receiver_type)
+      : kind_(kTransitionToField),
+        receiver_type_(receiver_type),
+        transition_map_(transition_map),
+        holder_(holder),
+        field_index_(field_index),
+        field_type_(field_type) {}
 
   bool IsDataConstant() const { return kind() == kDataConstant; }
   bool IsDataField() const { return kind() == kDataField; }
+  bool IsTransitionToField() const { return kind() == kTransitionToField; }
 
   Kind kind() const { return kind_; }
   MaybeHandle<JSObject> holder() const { return holder_; }
   Handle<Object> constant() const { return constant_; }
+  Handle<Object> transition_map() const { return transition_map_; }
   FieldIndex field_index() const { return field_index_; }
   Type* field_type() const { return field_type_; }
   Type* receiver_type() const { return receiver_type_; }
 
  private:
   Kind kind_;
   Type* receiver_type_;
   Handle<Object> constant_;
+  Handle<Map> transition_map_;
   MaybeHandle<JSObject> holder_;
   FieldIndex field_index_;
   Type* field_type_ = Type::Any();
 };
 
 
 namespace {
 
 bool CanInlinePropertyAccess(Handle<Map> map) {
   // TODO(bmeurer): Do something about the number stuff.
   if (map->instance_type() == HEAP_NUMBER_TYPE) return false;
   if (map->instance_type() < FIRST_NONSTRING_TYPE) return true;
   return map->IsJSObjectMap() && !map->is_dictionary_map() &&
          !map->has_named_interceptor() &&
          // TODO(verwaest): Whitelist contexts to which we have access.
          !map->is_access_check_needed();
 }
 
 }  // namespace
 
 
 bool JSNativeContextSpecialization::ComputePropertyAccessInfo(
     Handle<Map> map, Handle<Name> name, PropertyAccessMode access_mode,
     PropertyAccessInfo* access_info) {
-  MaybeHandle<JSObject> holder;
+  // Check if it is safe to inline property access for the {map}.
+  if (!CanInlinePropertyAccess(map)) return false;
+
+  // Compute the receiver type.
   Handle<Map> receiver_map = map;
   Type* receiver_type = Type::Class(receiver_map, graph()->zone());
-  while (CanInlinePropertyAccess(map)) {
+
+  // We support fast inline cases for certain JSObject getters.
+  if (access_mode == kLoad) {
     // Check for special JSObject field accessors.
     int offset;
     if (Accessors::IsJSObjectFieldAccessor(map, name, &offset)) {
-      // Don't bother optimizing stores to special JSObject field accessors.
-      if (access_mode == kStore) {
-        break;
-      }
       FieldIndex field_index = FieldIndex::ForInObjectOffset(offset);
       Type* field_type = Type::Tagged();
       if (map->IsStringMap()) {
         DCHECK(Name::Equals(factory()->length_string(), name));
         // The String::length property is always a smi in the range
         // [0, String::kMaxLength].
         field_type = type_cache_.kStringLengthType;
       } else if (map->IsJSArrayMap()) {
         DCHECK(Name::Equals(factory()->length_string(), name));
         // The JSArray::length property is a smi in the range
         // [0, FixedDoubleArray::kMaxLength] in case of fast double
         // elements, a smi in the range [0, FixedArray::kMaxLength]
         // in case of other fast elements, and [0, kMaxUInt32] in
         // case of other arrays.
         if (IsFastDoubleElementsKind(map->elements_kind())) {
           field_type = type_cache_.kFixedDoubleArrayLengthType;
         } else if (IsFastElementsKind(map->elements_kind())) {
           field_type = type_cache_.kFixedArrayLengthType;
         } else {
           field_type = type_cache_.kJSArrayLengthType;
         }
       }
-      *access_info = PropertyAccessInfo::DataField(receiver_type, field_index,
-                                                   field_type, holder);
+      *access_info =
+          PropertyAccessInfo::DataField(receiver_type, field_index, field_type);
       return true;
     }
+  }
 
+  MaybeHandle<JSObject> holder;
+  while (true) {
     // Lookup the named property on the {map}.
     Handle<DescriptorArray> descriptors(map->instance_descriptors(), isolate());
     int const number = descriptors->SearchWithCache(*name, *map);
     if (number != DescriptorArray::kNotFound) {
-      if (access_mode == kStore && !map.is_identical_to(receiver_map)) {
-        return false;
+      PropertyDetails const details = descriptors->GetDetails(number);
+      if (access_mode == kStore) {
+        // Don't bother optimizing stores to read-only properties.
+        if (details.IsReadOnly()) {
+          return false;
+        }
+        // Check for store to data property on a prototype.
+        if (details.kind() == kData && !holder.is_null()) {
+          // We need to add the data field to the receiver. Leave the loop
+          // and check whether we already have a transition for this field.
+          // Implemented according to ES6 section 9.1.9 [[Set]] (P, V, Receiver)
+          break;
+        }
       }
-      PropertyDetails const details = descriptors->GetDetails(number);
       if (details.type() == DATA_CONSTANT) {
         *access_info = PropertyAccessInfo::DataConstant(
             receiver_type, handle(descriptors->GetValue(number), isolate()),
             holder);
         return true;
       } else if (details.type() == DATA) {
-        // Don't bother optimizing stores to read-only properties.
-        if (access_mode == kStore && details.IsReadOnly()) {
-          break;
-        }
         int index = descriptors->GetFieldIndex(number);
         Representation field_representation = details.representation();
         FieldIndex field_index = FieldIndex::ForPropertyIndex(
             *map, index, field_representation.IsDouble());
         Type* field_type = Type::Tagged();
         if (field_representation.IsSmi()) {
           field_type = type_cache_.kSmi;
         } else if (field_representation.IsDouble()) {
           if (access_mode == kStore) {
             // TODO(bmeurer): Add support for storing to double fields.
-            break;
+            return false;
           }
           field_type = type_cache_.kFloat64;
         } else if (field_representation.IsHeapObject()) {
           // Extract the field type from the property details (make sure its
           // representation is TaggedPointer to reflect the heap object case).
           field_type = Type::Intersect(
               Type::Convert<HeapType>(
                   handle(descriptors->GetFieldType(number), isolate()),
                   graph()->zone()),
               Type::TaggedPointer(), graph()->zone());
           if (field_type->Is(Type::None())) {
-            if (access_mode == kStore) {
-              // Store is not safe if the field type was cleared.
-              break;
-            }
+            // Store is not safe if the field type was cleared.
+            if (access_mode == kStore) return false;
 
             // The field type was cleared by the GC, so we don't know anything
             // about the contents now.
             // TODO(bmeurer): It would be awesome to make this saner in the
             // runtime/GC interaction.
             field_type = Type::TaggedPointer();
           } else if (!Type::Any()->Is(field_type)) {
             // Add proper code dependencies in case of stable field map(s).
             Handle<Map> field_owner_map(map->FindFieldOwner(number), isolate());
             dependencies()->AssumeFieldType(field_owner_map);
           }
           DCHECK(field_type->Is(Type::TaggedPointer()));
         }
         *access_info = PropertyAccessInfo::DataField(receiver_type, field_index,
                                                      field_type, holder);
         return true;
       } else {
         // TODO(bmeurer): Add support for accessors.
-        break;
+        return false;
       }
     }
 
     // Don't search on the prototype chain for special indices in case of
     // integer indexed exotic objects (see ES6 section 9.4.5).
     if (map->IsJSTypedArrayMap() && name->IsString() &&
         IsSpecialIndex(isolate()->unicode_cache(), String::cast(*name))) {
-      break;
+      return false;
     }
 
     // Walk up the prototype chain.
     if (!map->prototype()->IsJSObject()) {
       // Perform the implicit ToObject for primitives here.
       // Implemented according to ES6 section 7.3.2 GetV (V, P).
       Handle<JSFunction> constructor;
       if (Map::GetConstructorFunction(map, native_context())
               .ToHandle(&constructor)) {
         map = handle(constructor->initial_map(), isolate());
         DCHECK(map->prototype()->IsJSObject());
+      } else if (map->prototype()->IsNull()) {
+        // Store to property not found on the receiver or any prototype, we need
+        // to transition to a new data property.
+        // Implemented according to ES6 section 9.1.9 [[Set]] (P, V, Receiver)
+        if (access_mode == kStore) {
+          break;
+        }
+        // TODO(bmeurer): Handle the not found case if the prototype is null.
+        return false;
       } else {
-        // TODO(bmeurer): Handle the not found case if the prototype is null.
-        break;
+        return false;
       }
     }
     Handle<JSObject> map_prototype(JSObject::cast(map->prototype()), isolate());
     if (map_prototype->map()->is_deprecated()) {
       // Try to migrate the prototype object so we don't embed the deprecated
       // map into the optimized code.
       JSObject::TryMigrateInstance(map_prototype);
     }
     map = handle(map_prototype->map(), isolate());
     holder = map_prototype;
+
+    // Check if it is safe to inline property access for the {map}.
+    if (!CanInlinePropertyAccess(map)) return false;
+  }
+  DCHECK_EQ(kStore, access_mode);
+
+  // Check if the {receiver_map} has a data transition with the given {name}.

[Jarin, 2015/10/29 09:02:33]

The structure of this code is strange. This whole chunk would seem to belong to
the place where you "break" out of the loop (well, ideally factored out into a
separate method).

[Benedikt Meurer, 2015/10/29 09:03:47]

Yes, but currently we have two "break" points. I want to rewrite the method when
I add the NotFound case, which also depends on the "break".

+  if (receiver_map->unused_property_fields() == 0) return false;
+  if (Map* transition = TransitionArray::SearchTransition(*receiver_map, kData,
+                                                          *name, NONE)) {
+    Handle<Map> transition_map(transition, isolate());
+    int const number = transition_map->LastAdded();
+    PropertyDetails const details =
+        transition_map->instance_descriptors()->GetDetails(number);
+    // Don't bother optimizing stores to read-only properties.
+    if (details.IsReadOnly()) return false;
+    // TODO(bmeurer): Handle transition to data constant?
+    if (details.type() != DATA) return false;
+    int const index = details.field_index();
+    Representation field_representation = details.representation();
+    FieldIndex field_index = FieldIndex::ForPropertyIndex(
+        *transition_map, index, field_representation.IsDouble());
+    Type* field_type = Type::Tagged();
+    if (field_representation.IsSmi()) {
+      field_type = type_cache_.kSmi;
+    } else if (field_representation.IsDouble()) {
+      // TODO(bmeurer): Add support for storing to double fields.
+      return false;
+    } else if (field_representation.IsHeapObject()) {
+      // Extract the field type from the property details (make sure its
+      // representation is TaggedPointer to reflect the heap object case).
+      field_type = Type::Intersect(
+          Type::Convert<HeapType>(
+              handle(
+                  transition_map->instance_descriptors()->GetFieldType(number),
+                  isolate()),
+              graph()->zone()),
+          Type::TaggedPointer(), graph()->zone());
+      if (field_type->Is(Type::None())) {
+        // Store is not safe if the field type was cleared.
+        return false;
+      } else if (!Type::Any()->Is(field_type)) {
+        // Add proper code dependencies in case of stable field map(s).
+        Handle<Map> field_owner_map(transition_map->FindFieldOwner(number),
+                                    isolate());
+        dependencies()->AssumeFieldType(field_owner_map);
+      }
+      DCHECK(field_type->Is(Type::TaggedPointer()));
+    }
+    dependencies()->AssumeMapNotDeprecated(transition_map);
+    *access_info = PropertyAccessInfo::TransitionToField(
+        receiver_type, field_index, field_type, transition_map, holder);
+    return true;
   }
   return false;
 }
 
 
 bool JSNativeContextSpecialization::ComputePropertyAccessInfos(
     MapHandleList const& maps, Handle<Name> name,
     PropertyAccessMode access_mode,
     ZoneVector<PropertyAccessInfo>* access_infos) {
   for (Handle<Map> map : maps) {
@@ skipping 97 matching lines @@
           (this_control_count == 1)
               ? this_controls.front()
               : graph()->NewNode(common()->Merge(this_control_count),
                                  this_control_count, &this_controls.front());
     }
 
     // Determine actual holder and perform prototype chain checks.
     Handle<JSObject> holder;
     if (access_info.holder().ToHandle(&holder)) {
       AssumePrototypesStable(receiver_type, holder);
-      if (access_mode == kLoad) {
-        this_receiver = jsgraph()->Constant(holder);
-      }
     }
 
     // Generate the actual property access.
     if (access_info.IsDataConstant()) {
       this_value = jsgraph()->Constant(access_info.constant());
       if (access_mode == kStore) {
         Node* check = graph()->NewNode(
             simplified()->ReferenceEqual(Type::Tagged()), value, this_value);
         Node* branch = graph()->NewNode(common()->Branch(BranchHint::kTrue),
                                         check, this_control);
         exit_controls.push_back(graph()->NewNode(common()->IfFalse(), branch));
         this_control = graph()->NewNode(common()->IfTrue(), branch);
       }
     } else {
-      DCHECK(access_info.IsDataField());
+      DCHECK(access_info.IsDataField() || access_info.IsTransitionToField());
       FieldIndex const field_index = access_info.field_index();
       Type* const field_type = access_info.field_type();
+      if (access_mode == kLoad && access_info.holder().ToHandle(&holder)) {
+        this_receiver = jsgraph()->Constant(holder);
+      }
+      Node* this_storage = this_receiver;
       if (!field_index.is_inobject()) {
-        this_receiver = this_effect = graph()->NewNode(
+        this_storage = this_effect = graph()->NewNode(
             simplified()->LoadField(AccessBuilder::ForJSObjectProperties()),
-            this_receiver, this_effect, this_control);
+            this_storage, this_effect, this_control);
       }
       FieldAccess field_access = {kTaggedBase, field_index.offset(), name,
                                   field_type, kMachAnyTagged};
       if (access_mode == kLoad) {
         if (field_type->Is(Type::UntaggedFloat64())) {
           if (!field_index.is_inobject() || field_index.is_hidden_field() ||
               !FLAG_unbox_double_fields) {
-            this_receiver = this_effect =
+            this_storage = this_effect =
                 graph()->NewNode(simplified()->LoadField(field_access),
-                                 this_receiver, this_effect, this_control);
+                                 this_storage, this_effect, this_control);
             field_access.offset = HeapNumber::kValueOffset;
             field_access.name = MaybeHandle<Name>();
           }
           field_access.machine_type = kMachFloat64;
         }
         this_value = this_effect =
             graph()->NewNode(simplified()->LoadField(field_access),
-                             this_receiver, this_effect, this_control);
+                             this_storage, this_effect, this_control);
       } else {
         DCHECK_EQ(kStore, access_mode);
         if (field_type->Is(Type::TaggedSigned())) {
           Node* check = graph()->NewNode(simplified()->ObjectIsSmi(), value);
           Node* branch = graph()->NewNode(common()->Branch(BranchHint::kTrue),
                                           check, this_control);
           exit_controls.push_back(
               graph()->NewNode(common()->IfFalse(), branch));
           this_control = graph()->NewNode(common()->IfTrue(), branch);
         } else if (field_type->Is(Type::TaggedPointer())) {
@@ skipping 25 matching lines @@
             this_control =
                 (this_control_count == 1)
                     ? this_controls.front()
                     : graph()->NewNode(common()->Merge(this_control_count),
                                        this_control_count,
                                        &this_controls.front());
           }
         } else {
           DCHECK(field_type->Is(Type::Tagged()));
         }
+        if (access_info.IsTransitionToField()) {
+          this_effect = graph()->NewNode(common()->BeginRegion(), this_effect);
+          this_effect = graph()->NewNode(
+              simplified()->StoreField(AccessBuilder::ForMap()), this_receiver,
+              jsgraph()->Constant(access_info.transition_map()), this_effect,
+              this_control);
+        }
         this_effect = graph()->NewNode(simplified()->StoreField(field_access),
-                                       this_receiver, this_value, this_effect,
+                                       this_storage, this_value, this_effect,
                                        this_control);
+        if (access_info.IsTransitionToField()) {
+          this_effect =
+              graph()->NewNode(common()->FinishRegion(),
+                               jsgraph()->UndefinedConstant(), this_effect);
+        }
       }
     }
 
     // Remember the final state for this property access.
     values.push_back(this_value);
     effects.push_back(this_effect);
     controls.push_back(this_control);
   }
 
   // Collect the fallthru control as final "exit" control.
@@ skipping 161 matching lines @@
 }
 
 
 SimplifiedOperatorBuilder* JSNativeContextSpecialization::simplified() const {
   return jsgraph()->simplified();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8