Promoting elements transitions to their own field.

src/objects.h

 // 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 151 matching lines @@
 };
 
 
 // Indicates whether a get method should implicitly create the object looked up.
 enum CreationFlag {
   ALLOW_CREATION,
   OMIT_CREATION
 };
 
 
+// Indicates whether the search function should expect a sorted or an unsorted
+// descriptor array as input.
+enum SearchMode {

[danno, 2012/06/04 13:52:13]

Since this is specific to Descriptor Arrays, consider making it an enum inside
the class, or call it something like DescriptorArraySearchMode.

[Toon Verwaest, 2012/06/04 15:03:20]

Done.

+  EXPECT_SORTED,
+  EXPECT_UNSORTED
+};
+
+
+// Indicates whether the search function should expect a sorted or an unsorted
+// descriptor array as input.
+enum SharedMode {
+  MAYBE_SHARED,

[danno, 2012/06/04 13:52:13]

MAY_BE_SHARED

[Toon Verwaest, 2012/06/04 15:03:20]

Done.

+  FORCE_NEW

[danno, 2012/06/04 13:52:13]

Either make this CANNOT_BE_SHARED, or, since this is behavior specific to
DescriptorArrays, make it an enum that's local to the class.

[Toon Verwaest, 2012/06/04 15:03:20]

Done.

+};
+
+
 // Instance size sentinel for objects of variable size.
 const int kVariableSizeSentinel = 0;
 
 
 // All Maps have a field instance_type containing a InstanceType.
 // It describes the type of the instances.
 //
 // As an example, a JavaScript object is a heap object and its map
 // instance_type is JS_OBJECT_TYPE.
 //
@@ skipping 2209 matching lines @@
 //          [1]: pointer to fixed array with enum cache
 //   [3]: first key
 //   [length() - 1]: last key
 //
 class DescriptorArray: public FixedArray {
  public:
   // Returns true for both shared empty_descriptor_array and for smis, which the
   // map uses to encode additional bit fields when the descriptor array is not
   // yet used.
   inline bool IsEmpty();
+  inline bool MayContainTransitions();
+
+  DECL_ACCESSORS(elements_transition_map, Map)
 
   // Returns the number of descriptors in the array.
   int number_of_descriptors() {
-    ASSERT(length() > kFirstIndex || IsEmpty());
+    ASSERT(length() > kFirstIndex ||
+           length() == kTransitionsIndex ||
+           IsEmpty());
     int len = length();
     return len <= kFirstIndex ? 0 : (len - kFirstIndex) / kDescriptorSize;
   }
 
   int NextEnumerationIndex() {
     if (IsEmpty()) return PropertyDetails::kInitialIndex;
     Object* obj = get(kEnumerationIndexIndex);
     if (obj->IsSmi()) {
       return Smi::cast(obj)->value();
     } else {
@@ skipping 17 matching lines @@
     FixedArray* bridge = FixedArray::cast(get(kEnumerationIndexIndex));
     return bridge->get(kEnumCacheBridgeCacheIndex);
   }
 
   Object** GetEnumCacheSlot() {
     ASSERT(HasEnumCache());
     return HeapObject::RawField(reinterpret_cast<HeapObject*>(this),
                                 kEnumerationIndexOffset);
   }
 
+  Object** GetTransitionsSlot() {
+    ASSERT(elements_transition_map() != NULL);
+    return HeapObject::RawField(reinterpret_cast<HeapObject*>(this),
+                                kTransitionsOffset);
+  }
+
   // TODO(1399): It should be possible to make room for bit_field3 in the map
   //             without overloading the instance descriptors field in the map
   //             (and storing it in the DescriptorArray when the map has one).
   inline int bit_field3_storage();
   inline void set_bit_field3_storage(int value);
 
   // Initialize or change the enum cache,
   // using the supplied storage for the small "bridge".
   void SetEnumCache(FixedArray* bridge_storage,
                     FixedArray* new_cache,
@@ skipping 58 matching lines @@
   // remove map transitions.  If the descriptor is already present, it is
   // replaced.  If a replaced descriptor is a real property (not a transition
   // or null), its enumeration index is kept as is.
   // If adding a real property, map transitions must be removed.  If adding
   // a transition, they must not be removed.  All null descriptors are removed.
   MUST_USE_RESULT MaybeObject* CopyInsert(Descriptor* descriptor,
                                           TransitionFlag transition_flag);
 
   // Return a copy of the array with all transitions and null descriptors
   // removed. Return a Failure object in case of an allocation failure.
-  MUST_USE_RESULT MaybeObject* RemoveTransitions();
+  MUST_USE_RESULT MaybeObject* RemoveTransitions(SharedMode shared_mode);
 
   // Sort the instance descriptors by the hash codes of their keys.
   // Does not check for duplicates.
   void SortUnchecked(const WhitenessWitness&);
 
   // Sort the instance descriptors by the hash codes of their keys.
   // Checks the result for duplicates.
   void Sort(const WhitenessWitness&);
 
   // Search the instance descriptors for given name.
   inline int Search(String* name);
 
   // As the above, but uses DescriptorLookupCache and updates it when
   // necessary.
   inline int SearchWithCache(String* name);
 
   // Tells whether the name is present int the array.
   bool Contains(String* name) { return kNotFound != Search(name); }
 
   // Perform a binary search in the instance descriptors represented
   // by this fixed array.  low and high are descriptor indices.  If there
   // are three instance descriptors in this array it should be called
   // with low=0 and high=2.
   int BinarySearch(String* name, int low, int high);
 
   // Perform a linear search in the instance descriptors represented
   // by this fixed array.  len is the number of descriptor indices that are
-  // valid.  Does not require the descriptors to be sorted.
-  int LinearSearch(String* name, int len);
+  // valid.
+  int LinearSearch(SearchMode mode, String* name, int len);
 
   // Allocates a DescriptorArray, but returns the singleton
   // empty descriptor array object if number_of_descriptors is 0.
-  MUST_USE_RESULT static MaybeObject* Allocate(int number_of_descriptors);
+  MUST_USE_RESULT static MaybeObject* Allocate(int number_of_descriptors,
+                                               SharedMode shared_mode);
 
   // Casting.
   static inline DescriptorArray* cast(Object* obj);
 
   // Constant for denoting key was not found.
   static const int kNotFound = -1;
 
   static const int kBitField3StorageIndex = 0;
-  static const int kEnumerationIndexIndex = 1;
-  static const int kFirstIndex = 2;
+  static const int kTransitionsIndex = 1;
+  static const int kEnumerationIndexIndex = 2;
+  static const int kFirstIndex = 3;
 
   // The length of the "bridge" to the enum cache.
   static const int kEnumCacheBridgeLength = 3;
   static const int kEnumCacheBridgeEnumIndex = 0;
   static const int kEnumCacheBridgeCacheIndex = 1;
   static const int kEnumCacheBridgeIndicesCacheIndex = 2;
 
   // Layout description.
   static const int kBitField3StorageOffset = FixedArray::kHeaderSize;
-  static const int kEnumerationIndexOffset = kBitField3StorageOffset +
-                                             kPointerSize;
+  static const int kTransitionsOffset = kBitField3StorageOffset + kPointerSize;
+  static const int kEnumerationIndexOffset = kTransitionsOffset + kPointerSize;
   static const int kFirstOffset = kEnumerationIndexOffset + kPointerSize;
 
   // Layout description for the bridge array.
   static const int kEnumCacheBridgeEnumOffset = FixedArray::kHeaderSize;
   static const int kEnumCacheBridgeCacheOffset =
     kEnumCacheBridgeEnumOffset + kPointerSize;
 
   // Layout of descriptor.
   static const int kDescriptorKey = 0;
   static const int kDescriptorDetails = 1;
@@ skipping 2085 matching lines @@
   }
 
   inline bool has_slow_elements_kind() {
     return elements_kind() == DICTIONARY_ELEMENTS
         || elements_kind() == NON_STRICT_ARGUMENTS_ELEMENTS;
   }
 
   static bool IsValidElementsTransition(ElementsKind from_kind,
                                         ElementsKind to_kind);
 
+  inline Map* elements_transition_map();
+  inline void set_elements_transition_map(Map* transitioned_map);
+
   // Tells whether the map is attached to SharedFunctionInfo
   // (for inobject slack tracking).
   inline void set_attached_to_shared_function_info(bool value);
 
   inline bool attached_to_shared_function_info();
 
   // Tells whether the map is shared between objects that may have different
   // behavior. If true, the map should never be modified, instead a clone
   // should be created and modified.
   inline void set_is_shared(bool value);
@@ skipping 76 matching lines @@
                            String* name,
                            LookupResult* result);
 
   MUST_USE_RESULT MaybeObject* CopyDropDescriptors();
 
   MUST_USE_RESULT MaybeObject* CopyNormalized(PropertyNormalizationMode mode,
                                               NormalizedMapSharingMode sharing);
 
   // Returns a copy of the map, with all transitions dropped from the
   // instance descriptors.
-  MUST_USE_RESULT MaybeObject* CopyDropTransitions();
+  MUST_USE_RESULT MaybeObject* CopyDropTransitions(SharedMode shared_mode);
 
   // Returns the property index for name (only valid for FAST MODE).
   int PropertyIndexFor(String* name);
 
   // Returns the next free property index (only valid for FAST MODE).
   int NextFreePropertyIndex();
 
   // Returns the number of properties described in instance_descriptors
   // filtering out properties with the specified attributes.
   int NumberOfDescribedProperties(PropertyAttributes filter = NONE);
@@ skipping 32 matching lines @@
 
   // Computes a hash value for this map, to be used in HashTables and such.
   int Hash();
 
   // Compares this map to another to see if they describe equivalent objects.
   // If |mode| is set to CLEAR_INOBJECT_PROPERTIES, |other| is treated as if
   // it had exactly zero inobject properties.
   // The "shared" flags of both this map and |other| are ignored.
   bool EquivalentToForNormalization(Map* other, PropertyNormalizationMode mode);
 
-  // Returns the contents of this map's descriptor array for the given string.
-  // May return NULL. |safe_to_add_transition| is set to false and NULL
-  // is returned if adding transitions is not allowed.
-  Object* GetDescriptorContents(String* sentinel_name,
-                                bool* safe_to_add_transitions);
-
   // Returns the map that this map transitions to if its elements_kind
   // is changed to |elements_kind|, or NULL if no such map is cached yet.
   // |safe_to_add_transitions| is set to false if adding transitions is not
   // allowed.
-  Map* LookupElementsTransitionMap(ElementsKind elements_kind,
-                                   bool* safe_to_add_transition);
+  Map* LookupElementsTransitionMap(ElementsKind elements_kind);
 
-  // Adds an entry to this map's descriptor array for a transition to
-  // |transitioned_map| when its elements_kind is changed to |elements_kind|.
-  MUST_USE_RESULT MaybeObject* AddElementsTransition(
-      ElementsKind elements_kind, Map* transitioned_map);
+  // Adds a new transitions for changing the elements kind to |elements_kind|.
+  MUST_USE_RESULT MaybeObject* CreateNextElementsTransition(
+      ElementsKind elements_kind);
 
   // Returns the transitioned map for this map with the most generic
   // elements_kind that's found in |candidates|, or null handle if no match is
   // found at all.
   Handle<Map> FindTransitionedMap(MapHandleList* candidates);
   Map* FindTransitionedMap(MapList* candidates);
 
   // Zaps the contents of backing data structures in debug mode. Note that the
   // heap verifier (i.e. VerifyMarkingVisitor) relies on zapping of objects
   // holding weak references when incremental marking is used, because it also
@@ skipping 121 matching lines @@
   // Layout of the default cache. It holds alternating name and code objects.
   static const int kCodeCacheEntrySize = 2;
   static const int kCodeCacheEntryNameOffset = 0;
   static const int kCodeCacheEntryCodeOffset = 1;
 
   typedef FixedBodyDescriptor<kPointerFieldsBeginOffset,
                               kPointerFieldsEndOffset,
                               kSize> BodyDescriptor;
 
  private:
-  String* elements_transition_sentinel_name();
   DISALLOW_IMPLICIT_CONSTRUCTORS(Map);
 };
 
 
 // An abstract superclass, a marker class really, for simple structure classes.
 // It doesn't carry much functionality but allows struct classes to be
 // identified in the type system.
 class Struct: public HeapObject {
  public:
   inline void InitializeBody(int object_size);
@@ skipping 3680 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_