Line data Source code
1 : // Copyright 2017 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_MAP_UPDATER_H_
6 : #define V8_MAP_UPDATER_H_
7 :
8 : #include "src/elements-kind.h"
9 : #include "src/field-type.h"
10 : #include "src/globals.h"
11 : #include "src/handles.h"
12 : #include "src/objects/map.h"
13 : #include "src/property-details.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 :
18 : // The |MapUpdater| class implements all sorts of map reconfigurations
19 : // including changes of elements kind, property attributes, property kind,
20 : // property location and field representations/type changes. It ensures that
21 : // the reconfigured map and all the intermediate maps are properly integrated
22 : // into the exising transition tree.
23 : //
24 : // To avoid high degrees over polymorphism, and to stabilize quickly, on every
25 : // rewrite the new type is deduced by merging the current type with any
26 : // potential new (partial) version of the type in the transition tree.
27 : // To do this, on each rewrite:
28 : // - Search the root of the transition tree using FindRootMap.
29 : // - Find/create a |root_map| with requested |new_elements_kind|.
30 : // - Find |target_map|, the newest matching version of this map using the
31 : // "updated" |old_map|'s descriptor array (i.e. whose entry at |modify_index|
32 : // is considered to be of |new_kind| and having |new_attributes|) to walk
33 : // the transition tree.
34 : // - Merge/generalize the "updated" descriptor array of the |old_map| and
35 : // descriptor array of the |target_map|.
36 : // - Generalize the |modify_index| descriptor using |new_representation| and
37 : // |new_field_type|.
38 : // - Walk the tree again starting from the root towards |target_map|. Stop at
39 : // |split_map|, the first map who's descriptor array does not match the merged
40 : // descriptor array.
41 : // - If |target_map| == |split_map|, |target_map| is in the expected state.
42 : // Return it.
43 : // - Otherwise, invalidate the outdated transition target from |target_map|, and
44 : // replace its transition tree with a new branch for the updated descriptors.
45 : class MapUpdater {
46 : public:
47 792258 : MapUpdater(Isolate* isolate, Handle<Map> old_map)
48 : : isolate_(isolate),
49 : old_map_(old_map),
50 : old_descriptors_(old_map->instance_descriptors(), isolate_),
51 : old_nof_(old_map_->NumberOfOwnDescriptors()),
52 : new_elements_kind_(old_map_->elements_kind()),
53 : is_transitionable_fast_elements_kind_(
54 3169032 : IsTransitionableFastElementsKind(new_elements_kind_)) {
55 : // We shouldn't try to update remote objects.
56 : DCHECK(!old_map->FindRootMap()->GetConstructor()->IsFunctionTemplateInfo());
57 792258 : }
58 :
59 : // Prepares for reconfiguring of a property at |descriptor| to data field
60 : // with given |attributes| and |representation|/|field_type| and
61 : // performs the steps 1-5.
62 : Handle<Map> ReconfigureToDataField(int descriptor,
63 : PropertyAttributes attributes,
64 : PropertyConstness constness,
65 : Representation representation,
66 : Handle<FieldType> field_type);
67 :
68 : // Prepares for reconfiguring elements kind and performs the steps 1-5.
69 : Handle<Map> ReconfigureElementsKind(ElementsKind elements_kind);
70 :
71 : // Prepares for updating deprecated map to most up-to-date non-deprecated
72 : // version and performs the steps 1-5.
73 : Handle<Map> Update();
74 :
75 : private:
76 : enum State { kInitialized, kAtRootMap, kAtTargetMap, kEnd };
77 :
78 : // Try to reconfigure property in-place without rebuilding transition tree
79 : // and creating new maps. See implementation for details.
80 : State TryRecofigureToDataFieldInplace();
81 :
82 : // Step 1.
83 : // - Search the root of the transition tree using FindRootMap.
84 : // - Find/create a |root_map_| with requested |new_elements_kind_|.
85 : State FindRootMap();
86 :
87 : // Step 2.
88 : // - Find |target_map_|, the newest matching version of this map using the
89 : // "updated" |old_map|'s descriptor array (i.e. whose entry at
90 : // |modified_descriptor_| is considered to be of |new_kind| and having
91 : // |new_attributes|) to walk the transition tree.
92 : State FindTargetMap();
93 :
94 : // Step 3.
95 : // - Merge/generalize the "updated" descriptor array of the |old_map_| and
96 : // descriptor array of the |target_map_|.
97 : // - Generalize the |modified_descriptor_| using |new_representation| and
98 : // |new_field_type_|.
99 : Handle<DescriptorArray> BuildDescriptorArray();
100 :
101 : // Step 4.
102 : // - Walk the tree again starting from the root towards |target_map|. Stop at
103 : // |split_map|, the first map who's descriptor array does not match the
104 : // merged descriptor array.
105 : Handle<Map> FindSplitMap(Handle<DescriptorArray> descriptors);
106 :
107 : // Step 5.
108 : // - If |target_map| == |split_map|, |target_map| is in the expected state.
109 : // Return it.
110 : // - Otherwise, invalidate the outdated transition target from |target_map|,
111 : // and replace its transition tree with a new branch for the updated
112 : // descriptors.
113 : State ConstructNewMap();
114 :
115 : // When a requested reconfiguration can not be done the result is a copy
116 : // of |old_map_| where every field has |Tagged| representation and |Any|
117 : // field type. This map is disconnected from the transition tree.
118 : State CopyGeneralizeAllFields(const char* reason);
119 :
120 : // Returns name of a |descriptor| property.
121 : inline Name* GetKey(int descriptor) const;
122 :
123 : // Returns property details of a |descriptor| in "updated" |old_descrtiptors_|
124 : // array.
125 : inline PropertyDetails GetDetails(int descriptor) const;
126 :
127 : // Returns value of a |descriptor| with kDescriptor location in "updated"
128 : // |old_descrtiptors_| array.
129 : inline Object* GetValue(int descriptor) const;
130 :
131 : // Returns field type for a |descriptor| with kField location in "updated"
132 : // |old_descrtiptors_| array.
133 : inline FieldType* GetFieldType(int descriptor) const;
134 :
135 : // If a |descriptor| property in "updated" |old_descriptors_| has kField
136 : // location then returns it's field type otherwise computes optimal field
137 : // type for the descriptor's value and |representation|. The |location|
138 : // value must be a pre-fetched location for |descriptor|.
139 : inline Handle<FieldType> GetOrComputeFieldType(
140 : int descriptor, PropertyLocation location,
141 : Representation representation) const;
142 :
143 : // If a |descriptor| property in given |descriptors| array has kField
144 : // location then returns it's field type otherwise computes optimal field
145 : // type for the descriptor's value and |representation|.
146 : // The |location| value must be a pre-fetched location for |descriptor|.
147 : inline Handle<FieldType> GetOrComputeFieldType(
148 : Handle<DescriptorArray> descriptors, int descriptor,
149 : PropertyLocation location, Representation representation);
150 :
151 : inline void GeneralizeIfTransitionableFastElementsKind(
152 : PropertyConstness* constness, Representation* representation,
153 : Handle<FieldType>* field_type);
154 :
155 : void GeneralizeField(Handle<Map> map, int modify_index,
156 : PropertyConstness new_constness,
157 : Representation new_representation,
158 : Handle<FieldType> new_field_type);
159 :
160 : Isolate* isolate_;
161 : Handle<Map> old_map_;
162 : Handle<DescriptorArray> old_descriptors_;
163 : Handle<Map> root_map_;
164 : Handle<Map> target_map_;
165 : Handle<Map> result_map_;
166 : int old_nof_;
167 :
168 : State state_ = kInitialized;
169 : ElementsKind new_elements_kind_;
170 : bool is_transitionable_fast_elements_kind_;
171 :
172 : // If |modified_descriptor_| is not equal to -1 then the fields below form
173 : // an "update" of the |old_map_|'s descriptors.
174 : int modified_descriptor_ = -1;
175 : PropertyKind new_kind_ = kData;
176 : PropertyAttributes new_attributes_ = NONE;
177 : PropertyConstness new_constness_ = kMutable;
178 : PropertyLocation new_location_ = kField;
179 : Representation new_representation_ = Representation::None();
180 :
181 : // Data specific to kField location.
182 : Handle<FieldType> new_field_type_;
183 :
184 : // Data specific to kDescriptor location.
185 : Handle<Object> new_value_;
186 : };
187 :
188 : } // namespace internal
189 : } // namespace v8
190 :
191 : #endif // V8_MAP_UPDATER_H_
|
