Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(10)

Unified Diff: src/transitions.h

Issue 980573002: Simplify and compact transitions storage (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: fix -Werror=pedantic ( rebase Created 5 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/objects-printer.cc ('k') | src/transitions.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/transitions.h
diff --git a/src/transitions.h b/src/transitions.h
index 999ad86c558c176f8bb112df840b626f81c36cbb..648559ba4cd2652fd836b691e81c9fbb226a48d9 100644
--- a/src/transitions.h
+++ b/src/transitions.h
@@ -16,47 +16,98 @@ namespace internal {
// TransitionArrays are fixed arrays used to hold map transitions for property,
-// constant, and element changes. They can either be simple transition arrays
-// that store a single property transition, or a full transition array that has
+// constant, and element changes. "Simple" transitions storing only a single
+// property transition are stored inline (i.e. the target map is stored
+// directly); otherwise a full transition array is used that has
// prototype transitions and multiple property transitons. The details related
// to property transitions are accessed in the descriptor array of the target
// map. In the case of a simple transition, the key is also read from the
// descriptor array of the target map.
//
-// The simple format of the these objects is:
-// [0] Undefined or back pointer map
-// [1] Single transition
+// This class provides a static interface that operates directly on maps
+// and handles the distinction between simple and full transitions storage.
//
// The full format is:
-// [0] Undefined or back pointer map
-// [1] Smi(0) or fixed array of prototype transitions
-// [2] Number of transitions
-// [3] First transition
-// [3 + number of transitions * kTransitionSize]: start of slack
+// [0] Smi(0) or fixed array of prototype transitions
+// [1] Number of transitions
+// [2] First transition
+// [2 + number of transitions * kTransitionSize]: start of slack
class TransitionArray: public FixedArray {
public:
- // Accessors for fetching instance transition at transition number.
- inline Name* GetKey(int transition_number);
- inline void SetKey(int transition_number, Name* value);
- inline Object** GetKeySlot(int transition_number);
- int GetSortedKeyIndex(int transition_number) { return transition_number; }
+ // Insert a new transition into |map|'s transition array, extending it
+ // as necessary.
+ static void Insert(Handle<Map> map, Handle<Name> name, Handle<Map> target,
+ SimpleTransitionFlag flag);
- Name* GetSortedKey(int transition_number) {
- return GetKey(transition_number);
- }
+ static Map* SearchTransition(Map* map, PropertyKind kind, Name* name,
+ PropertyAttributes attributes);
- inline Map* GetTarget(int transition_number);
- inline void SetTarget(int transition_number, Map* target);
+ static Map* SearchSpecial(Map* map, Symbol* name);
- inline PropertyDetails GetTargetDetails(int transition_number);
- inline Object* GetTargetValue(int transition_number);
+ static Handle<Map> FindTransitionToField(Handle<Map> map, Handle<Name> name);
- inline bool HasElementsTransition();
+ static Handle<String> ExpectedTransitionKey(Handle<Map> map);
- inline Object* back_pointer_storage();
- inline void set_back_pointer_storage(
- Object* back_pointer,
- WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
+ static Handle<Map> ExpectedTransitionTarget(Handle<Map> map) {
+ DCHECK(!ExpectedTransitionKey(map).is_null());
+ return Handle<Map>(GetSimpleTransition(map->raw_transitions()));
+ }
+ // Returns true if |raw_transition| can be overwritten with a simple
+ // transition (because it's either uninitialized, or has been cleared).
+ static inline bool CanStoreSimpleTransition(Object* raw_transition) {
+ return raw_transition->IsSmi() ||
+ (raw_transition->IsWeakCell() &&
+ WeakCell::cast(raw_transition)->cleared());
+ }
+ static inline bool IsSimpleTransition(Object* raw_transition) {
+ DCHECK(!raw_transition->IsWeakCell() ||
+ WeakCell::cast(raw_transition)->cleared() ||
+ WeakCell::cast(raw_transition)->value()->IsMap());
+ return raw_transition->IsWeakCell() &&
+ !WeakCell::cast(raw_transition)->cleared();
+ }
+ static inline Map* GetSimpleTransition(Object* raw_transition) {
+ DCHECK(IsSimpleTransition(raw_transition));
+ return Map::cast(WeakCell::cast(raw_transition)->value());
+ }
+ static inline bool IsFullTransitionArray(Object* raw_transitions) {
+ return raw_transitions->IsTransitionArray();
+ }
+
+ // The size of transition arrays are limited so they do not end up in large
+ // object space. Otherwise ClearNonLiveReferences would leak memory while
+ // applying in-place right trimming.
+ static bool CanHaveMoreTransitions(Handle<Map> map);
+
+ // ===== PROTOTYPE TRANSITIONS =====
+ // When you set the prototype of an object using the __proto__ accessor you
+ // need a new map for the object (the prototype is stored in the map). In
+ // order not to multiply maps unnecessarily we store these as transitions in
+ // the original map. That way we can transition to the same map if the same
+ // prototype is set, rather than creating a new map every time. The
+ // transitions are in the form of a map where the keys are prototype objects
+ // and the values are the maps they transition to.
+ // Cache format:
+ // 0: finger - index of the first free cell in the cache
+ // 1 + i: target map
+ static const int kMaxCachedPrototypeTransitions = 256;
+ static Handle<Map> PutPrototypeTransition(Handle<Map> map,
+ Handle<Object> prototype,
+ Handle<Map> target_map);
+
+ static Handle<Map> GetPrototypeTransition(Handle<Map> map,
+ Handle<Object> prototype);
+
+ static FixedArray* GetPrototypeTransitions(Map* map);
+
+ static int NumberOfPrototypeTransitions(FixedArray* proto_transitions) {
+ if (proto_transitions->length() == 0) return 0;
+ Object* raw = proto_transitions->get(kProtoTransitionNumberOfEntriesOffset);
+ return Smi::cast(raw)->value();
+ }
+
+ static void SetNumberOfPrototypeTransitions(FixedArray* proto_transitions,
+ int value);
inline FixedArray* GetPrototypeTransitions();
inline void SetPrototypeTransitions(
@@ -65,133 +116,92 @@ class TransitionArray: public FixedArray {
inline Object** GetPrototypeTransitionsSlot();
inline bool HasPrototypeTransitions();
- // Returns the number of transitions in the array.
- int number_of_transitions() {
- if (IsSimpleTransition()) return 1;
- if (length() <= kFirstIndex) return 0;
- return Smi::cast(get(kTransitionLengthIndex))->value();
- }
+ // ===== ITERATION =====
- int number_of_transitions_storage() {
- if (IsSimpleTransition()) return 1;
- if (length() <= kFirstIndex) return 0;
- return (length() - kFirstIndex) / kTransitionSize;
- }
+ typedef void (*TraverseCallback)(Map* map, void* data);
- int NumberOfSlackTransitions() {
- return number_of_transitions_storage() - number_of_transitions();
+ // Traverse the transition tree in postorder.
+ static void TraverseTransitionTree(Map* map, TraverseCallback callback,
+ void* data) {
+ // Make sure that we do not allocate in the callback.
+ DisallowHeapAllocation no_allocation;
+ TraverseTransitionTreeInternal(map, callback, data);
}
- inline void SetNumberOfTransitions(int number_of_transitions);
- inline int number_of_entries() { return number_of_transitions(); }
+ // ===== LOW-LEVEL ACCESSORS =====
- // Creates a FullTransitionArray from a SimpleTransitionArray in
- // containing_map.
- static Handle<TransitionArray> ExtendToFullTransitionArray(
- Handle<Map> containing_map);
-
- // Return a transition array, using the array from the owning map if it
- // already has one (copying into a larger array if necessary), otherwise
- // creating a new one according to flag.
- // TODO(verwaest): This should not cause an existing transition to be
- // overwritten.
- static Handle<TransitionArray> Insert(Handle<Map> map, Handle<Name> name,
- Handle<Map> target,
- SimpleTransitionFlag flag);
- // Search a transition for a given kind, property name and attributes.
- int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
- int* out_insertion_index = NULL);
+ // Accessors for fetching instance transition at transition number.
+ static inline Name* GetKey(Object* raw_transitions, int transition_number);
+ inline Name* GetKey(int transition_number);
+ inline void SetKey(int transition_number, Name* value);
+ inline Object** GetKeySlot(int transition_number);
+ int GetSortedKeyIndex(int transition_number) { return transition_number; }
- // Search a non-property transition (like elements kind, observe or frozen
- // transitions).
- inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = NULL) {
- return SearchName(symbol, out_insertion_index);
+ Name* GetSortedKey(int transition_number) {
+ return GetKey(transition_number);
}
+ static inline Map* GetTarget(Object* raw_transitions, int transition_number);
+ inline Map* GetTarget(int transition_number);
+ inline void SetTarget(int transition_number, Map* target);
+
static inline PropertyDetails GetTargetDetails(Name* name, Map* target);
- // Allocates a TransitionArray.
- static Handle<TransitionArray> Allocate(Isolate* isolate,
- int number_of_transitions,
- int slack = 0);
+ // Returns the number of transitions in the array.
+ static int NumberOfTransitions(Object* raw_transitions);
+ // Required for templatized Search interface.
+ inline int number_of_entries() { return number_of_transitions(); }
- bool IsSimpleTransition() {
- return length() == kSimpleTransitionSize &&
- get(kSimpleTransitionTarget)->IsHeapObject() &&
- // The IntrusivePrototypeTransitionIterator may have set the map of the
- // prototype transitions array to a smi. In that case, there are
- // prototype transitions, hence this transition array is a full
- // transition array.
- HeapObject::cast(get(kSimpleTransitionTarget))->map()->IsMap() &&
- get(kSimpleTransitionTarget)->IsMap();
- }
+ inline void SetNumberOfTransitions(int number_of_transitions);
- bool IsFullTransitionArray() {
- return length() > kFirstIndex ||
- (length() == kFirstIndex && !IsSimpleTransition());
- }
+ static int Capacity(Object* raw_transitions);
// Casting.
static inline TransitionArray* cast(Object* obj);
- // Constant for denoting key was not found.
- static const int kNotFound = -1;
-
- static const int kBackPointerStorageIndex = 0;
-
- // Layout for full transition arrays.
- static const int kPrototypeTransitionsIndex = 1;
- static const int kTransitionLengthIndex = 2;
- static const int kFirstIndex = 3;
-
- // Layout for simple transition arrays.
- static const int kSimpleTransitionTarget = 1;
- static const int kSimpleTransitionSize = 2;
- static const int kSimpleTransitionIndex = 0;
- STATIC_ASSERT(kSimpleTransitionIndex != kNotFound);
-
- static const int kBackPointerStorageOffset = FixedArray::kHeaderSize;
-
- // Layout for the full transition array header.
- static const int kPrototypeTransitionsOffset = kBackPointerStorageOffset +
- kPointerSize;
- static const int kTransitionLengthOffset =
- kPrototypeTransitionsOffset + kPointerSize;
-
- // Layout of map transition entries in full transition arrays.
- static const int kTransitionKey = 0;
- static const int kTransitionTarget = 1;
static const int kTransitionSize = 2;
+ static const int kProtoTransitionHeaderSize = 1;
#if defined(DEBUG) || defined(OBJECT_PRINT)
// For our gdb macros, we should perhaps change these in the future.
void Print();
// Print all the transitions.
- void PrintTransitions(std::ostream& os, bool print_header = true); // NOLINT
+ static void PrintTransitions(std::ostream& os, Object* transitions,
+ bool print_header = true); // NOLINT
#endif
#ifdef DEBUG
bool IsSortedNoDuplicates(int valid_entries = -1);
- bool IsConsistentWithBackPointers(Map* current_map);
- bool IsEqualTo(TransitionArray* other);
+ static bool IsSortedNoDuplicates(Map* map);
+ static bool IsConsistentWithBackPointers(Map* map);
// Returns true for a non-property transitions like elements kind, observed
// or frozen transitions.
static inline bool IsSpecialTransition(Name* name);
#endif
+ // Constant for denoting key was not found.
+ static const int kNotFound = -1;
+
// The maximum number of transitions we want in a transition array (should
// fit in a page).
static const int kMaxNumberOfTransitions = 1024 + 512;
- // Returns the fixed array length required to hold number_of_transitions
- // transitions.
- static int LengthFor(int number_of_transitions) {
- return ToKeyIndex(number_of_transitions);
- }
-
private:
+ // Layout for full transition arrays.
+ static const int kPrototypeTransitionsIndex = 0;
+ static const int kTransitionLengthIndex = 1;
+ static const int kFirstIndex = 2;
+
+ // Layout of map transition entries in full transition arrays.
+ static const int kTransitionKey = 0;
+ static const int kTransitionTarget = 1;
+ STATIC_ASSERT(kTransitionSize == 2);
+
+ static const int kProtoTransitionNumberOfEntriesOffset = 0;
+ STATIC_ASSERT(kProtoTransitionHeaderSize == 1);
+
// Conversion from transition number to array indices.
static int ToKeyIndex(int transition_number) {
return kFirstIndex +
@@ -205,20 +215,55 @@ class TransitionArray: public FixedArray {
kTransitionTarget;
}
- static Handle<TransitionArray> AllocateSimple(
- Isolate* isolate, Handle<Map> target);
+ // Returns the fixed array length required to hold number_of_transitions
+ // transitions.
+ static int LengthFor(int number_of_transitions) {
+ return ToKeyIndex(number_of_transitions);
+ }
+
+ // Allocates a TransitionArray.
+ static Handle<TransitionArray> Allocate(Isolate* isolate,
+ int number_of_transitions,
+ int slack = 0);
+
+ static void EnsureHasFullTransitionArray(Handle<Map> map);
+ static void ReplaceTransitions(Handle<Map> map, Object* new_transitions);
- // Allocate a new transition array with a single entry.
- static Handle<TransitionArray> NewWith(Handle<Map> map,
- Handle<Name> name,
- Handle<Map> target,
- SimpleTransitionFlag flag);
+ // Search a transition for a given kind, property name and attributes.
+ int Search(PropertyKind kind, Name* name, PropertyAttributes attributes,
+ int* out_insertion_index = NULL);
+ // Search a non-property transition (like elements kind, observe or frozen
+ // transitions).
+ inline int SearchSpecial(Symbol* symbol, int* out_insertion_index = NULL) {
+ return SearchName(symbol, out_insertion_index);
+ }
// Search a first transition for a given property name.
inline int SearchName(Name* name, int* out_insertion_index = NULL);
int SearchDetails(int transition, PropertyKind kind,
PropertyAttributes attributes, int* out_insertion_index);
+ int number_of_transitions() {
+ if (length() < kFirstIndex) return 0;
+ return Smi::cast(get(kTransitionLengthIndex))->value();
+ }
+
+ static inline PropertyDetails GetSimpleTargetDetails(Map* transition) {
+ return transition->GetLastDescriptorDetails();
+ }
+
+ static inline Name* GetSimpleTransitionKey(Map* transition) {
+ int descriptor = transition->LastAdded();
+ return transition->instance_descriptors()->GetKey(descriptor);
+ }
+
+ static void TraverseTransitionTreeInternal(Map* map,
+ TraverseCallback callback,
+ void* data);
+
+ static void SetPrototypeTransitions(Handle<Map> map,
+ Handle<FixedArray> proto_transitions);
+
// Compares two tuples <key, kind, attributes>, returns -1 if
// tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise.
static inline int CompareKeys(Name* key1, uint32_t hash1, PropertyKind kind1,
@@ -247,6 +292,12 @@ class TransitionArray: public FixedArray {
int origin_transition,
int target_transition);
+#ifdef DEBUG
+ static void CheckNewTransitionsAreConsistent(Handle<Map> map,
+ TransitionArray* old_transitions,
+ Object* transitions);
+#endif
+
DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionArray);
};
« no previous file with comments | « src/objects-printer.cc ('k') | src/transitions.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698