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 MapUpdater(Isolate* isolate, Handle<Map> old_map); 48 49 // Prepares for reconfiguring of a property at |descriptor| to data field 50 // with given |attributes| and |representation|/|field_type| and 51 // performs the steps 1-5. 52 Handle<Map> ReconfigureToDataField(int descriptor, 53 PropertyAttributes attributes, 54 PropertyConstness constness, 55 Representation representation, 56 Handle<FieldType> field_type); 57 58 // Prepares for reconfiguring elements kind and performs the steps 1-5. 59 Handle<Map> ReconfigureElementsKind(ElementsKind elements_kind); 60 61 // Prepares for updating deprecated map to most up-to-date non-deprecated 62 // version and performs the steps 1-5. 63 Handle<Map> Update(); 64 65 private: 66 enum State { kInitialized, kAtRootMap, kAtTargetMap, kEnd }; 67 68 // Try to reconfigure property in-place without rebuilding transition tree 69 // and creating new maps. See implementation for details. 70 State TryRecofigureToDataFieldInplace(); 71 72 // Step 1. 73 // - Search the root of the transition tree using FindRootMap. 74 // - Find/create a |root_map_| with requested |new_elements_kind_|. 75 State FindRootMap(); 76 77 // Step 2. 78 // - Find |target_map_|, the newest matching version of this map using the 79 // "updated" |old_map|'s descriptor array (i.e. whose entry at 80 // |modified_descriptor_| is considered to be of |new_kind| and having 81 // |new_attributes|) to walk the transition tree. 82 State FindTargetMap(); 83 84 // Step 3. 85 // - Merge/generalize the "updated" descriptor array of the |old_map_| and 86 // descriptor array of the |target_map_|. 87 // - Generalize the |modified_descriptor_| using |new_representation| and 88 // |new_field_type_|. 89 Handle<DescriptorArray> BuildDescriptorArray(); 90 91 // Step 4. 92 // - Walk the tree again starting from the root towards |target_map|. Stop at 93 // |split_map|, the first map who's descriptor array does not match the 94 // merged descriptor array. 95 Handle<Map> FindSplitMap(Handle<DescriptorArray> descriptors); 96 97 // Step 5. 98 // - If |target_map| == |split_map|, |target_map| is in the expected state. 99 // Return it. 100 // - Otherwise, invalidate the outdated transition target from |target_map|, 101 // and replace its transition tree with a new branch for the updated 102 // descriptors. 103 State ConstructNewMap(); 104 105 // When a requested reconfiguration can not be done the result is a copy 106 // of |old_map_| where every field has |Tagged| representation and |Any| 107 // field type. This map is disconnected from the transition tree. 108 State CopyGeneralizeAllFields(const char* reason); 109 110 // Returns name of a |descriptor| property. 111 inline Name* GetKey(int descriptor) const; 112 113 // Returns property details of a |descriptor| in "updated" |old_descrtiptors_| 114 // array. 115 inline PropertyDetails GetDetails(int descriptor) const; 116 117 // Returns value of a |descriptor| with kDescriptor location in "updated" 118 // |old_descrtiptors_| array. 119 inline Object* GetValue(int descriptor) const; 120 121 // Returns field type for a |descriptor| with kField location in "updated" 122 // |old_descrtiptors_| array. 123 inline FieldType* GetFieldType(int descriptor) const; 124 125 // If a |descriptor| property in "updated" |old_descriptors_| has kField 126 // location then returns it's field type otherwise computes optimal field 127 // type for the descriptor's value and |representation|. The |location| 128 // value must be a pre-fetched location for |descriptor|. 129 inline Handle<FieldType> GetOrComputeFieldType( 130 int descriptor, PropertyLocation location, 131 Representation representation) const; 132 133 // If a |descriptor| property in given |descriptors| array has kField 134 // location then returns it's field type otherwise computes optimal field 135 // type for the descriptor's value and |representation|. 136 // The |location| value must be a pre-fetched location for |descriptor|. 137 inline Handle<FieldType> GetOrComputeFieldType( 138 Handle<DescriptorArray> descriptors, int descriptor, 139 PropertyLocation location, Representation representation); 140 141 void GeneralizeField(Handle<Map> map, int modify_index, 142 PropertyConstness new_constness, 143 Representation new_representation, 144 Handle<FieldType> new_field_type); 145 146 Isolate* isolate_; 147 Handle<Map> old_map_; 148 Handle<DescriptorArray> old_descriptors_; 149 Handle<Map> root_map_; 150 Handle<Map> target_map_; 151 Handle<Map> result_map_; 152 int old_nof_; 153 154 State state_ = kInitialized; 155 ElementsKind new_elements_kind_; 156 bool is_transitionable_fast_elements_kind_; 157 158 // If |modified_descriptor_| is not equal to -1 then the fields below form 159 // an "update" of the |old_map_|'s descriptors. 160 int modified_descriptor_ = -1; 161 PropertyKind new_kind_ = kData; 162 PropertyAttributes new_attributes_ = NONE; 163 PropertyConstness new_constness_ = PropertyConstness::kMutable; 164 PropertyLocation new_location_ = kField; 165 Representation new_representation_ = Representation::None(); 166 167 // Data specific to kField location. 168 Handle<FieldType> new_field_type_; 169 170 // Data specific to kDescriptor location. 171 Handle<Object> new_value_; 172 }; 173 174 } // namespace internal 175 } // namespace v8 176 177 #endif // V8_MAP_UPDATER_H_ 178