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