1 // Copyright 2016 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_COMPILER_LOAD_ELIMINATION_H_ 6 #define V8_COMPILER_LOAD_ELIMINATION_H_ 7 8 #include "src/base/compiler-specific.h" 9 #include "src/codegen/machine-type.h" 10 #include "src/common/globals.h" 11 #include "src/compiler/graph-reducer.h" 12 #include "src/compiler/simplified-operator.h" 13 #include "src/handles/maybe-handles.h" 14 #include "src/zone/zone-handle-set.h" 15 16 namespace v8 { 17 namespace internal { 18 19 // Forward declarations. 20 class Factory; 21 22 namespace compiler { 23 24 // Forward declarations. 25 class CommonOperatorBuilder; 26 struct FieldAccess; 27 class Graph; 28 class JSGraph; 29 30 class V8_EXPORT_PRIVATE LoadElimination final NON_EXPORTED_BASE(AdvancedReducer)31 : public NON_EXPORTED_BASE(AdvancedReducer) { 32 public: 33 LoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone) 34 : AdvancedReducer(editor), node_states_(zone), jsgraph_(jsgraph) {} 35 ~LoadElimination() final = default; 36 LoadElimination(const LoadElimination&) = delete; 37 LoadElimination& operator=(const LoadElimination&) = delete; 38 39 const char* reducer_name() const override { return "LoadElimination"; } 40 41 Reduction Reduce(Node* node) final; 42 43 private: 44 static const size_t kMaxTrackedElements = 8; 45 46 // Abstract state to approximate the current state of an element along the 47 // effect paths through the graph. 48 class AbstractElements final : public ZoneObject { 49 public: 50 explicit AbstractElements(Zone* zone) { 51 for (size_t i = 0; i < arraysize(elements_); ++i) { 52 elements_[i] = Element(); 53 } 54 } 55 AbstractElements(Node* object, Node* index, Node* value, 56 MachineRepresentation representation, Zone* zone) 57 : AbstractElements(zone) { 58 elements_[next_index_++] = Element(object, index, value, representation); 59 } 60 61 AbstractElements const* Extend(Node* object, Node* index, Node* value, 62 MachineRepresentation representation, 63 Zone* zone) const { 64 AbstractElements* that = zone->New<AbstractElements>(*this); 65 that->elements_[that->next_index_] = 66 Element(object, index, value, representation); 67 that->next_index_ = (that->next_index_ + 1) % arraysize(elements_); 68 return that; 69 } 70 Node* Lookup(Node* object, Node* index, 71 MachineRepresentation representation) const; 72 AbstractElements const* Kill(Node* object, Node* index, Zone* zone) const; 73 bool Equals(AbstractElements const* that) const; 74 AbstractElements const* Merge(AbstractElements const* that, 75 Zone* zone) const; 76 77 void Print() const; 78 79 private: 80 struct Element { 81 Element() = default; 82 Element(Node* object, Node* index, Node* value, 83 MachineRepresentation representation) 84 : object(object), 85 index(index), 86 value(value), 87 representation(representation) {} 88 89 Node* object = nullptr; 90 Node* index = nullptr; 91 Node* value = nullptr; 92 MachineRepresentation representation = MachineRepresentation::kNone; 93 }; 94 95 Element elements_[kMaxTrackedElements]; 96 size_t next_index_ = 0; 97 }; 98 99 // Information we use to resolve object aliasing. Currently, we consider 100 // object not aliased if they have different maps or if the nodes may 101 // not alias. 102 class AliasStateInfo; 103 104 struct FieldInfo { 105 FieldInfo() = default; 106 FieldInfo(Node* value, MachineRepresentation representation, 107 MaybeHandle<Name> name = {}, 108 ConstFieldInfo const_field_info = ConstFieldInfo::None()) 109 : value(value), 110 representation(representation), 111 name(name), 112 const_field_info(const_field_info) {} 113 114 bool operator==(const FieldInfo& other) const { 115 return value == other.value && representation == other.representation && 116 name.address() == other.name.address() && 117 const_field_info == other.const_field_info; 118 } 119 bool operator!=(const FieldInfo& other) const { return !(*this == other); } 120 121 Node* value = nullptr; 122 MachineRepresentation representation = MachineRepresentation::kNone; 123 MaybeHandle<Name> name; 124 ConstFieldInfo const_field_info; 125 }; 126 127 // Abstract state to approximate the current state of a certain field along 128 // the effect paths through the graph. 129 class AbstractField final : public ZoneObject { 130 public: 131 explicit AbstractField(Zone* zone) : info_for_node_(zone) {} 132 AbstractField(Node* object, FieldInfo info, Zone* zone) 133 : info_for_node_(zone) { 134 info_for_node_.insert(std::make_pair(object, info)); 135 } 136 137 AbstractField const* Extend(Node* object, FieldInfo info, 138 Zone* zone) const { 139 AbstractField* that = zone->New<AbstractField>(zone); 140 that->info_for_node_ = this->info_for_node_; 141 that->info_for_node_[object] = info; 142 return that; 143 } 144 FieldInfo const* Lookup(Node* object) const; 145 AbstractField const* KillConst(Node* object, Zone* zone) const; 146 AbstractField const* Kill(const AliasStateInfo& alias_info, 147 MaybeHandle<Name> name, Zone* zone) const; 148 bool Equals(AbstractField const* that) const { 149 return this == that || this->info_for_node_ == that->info_for_node_; 150 } 151 AbstractField const* Merge(AbstractField const* that, Zone* zone) const { 152 if (this->Equals(that)) return this; 153 AbstractField* copy = zone->New<AbstractField>(zone); 154 for (auto this_it : this->info_for_node_) { 155 Node* this_object = this_it.first; 156 FieldInfo this_second = this_it.second; 157 if (this_object->IsDead()) continue; 158 auto that_it = that->info_for_node_.find(this_object); 159 if (that_it != that->info_for_node_.end() && 160 that_it->second == this_second) { 161 copy->info_for_node_.insert(this_it); 162 } 163 } 164 return copy; 165 } 166 167 void Print() const; 168 169 private: 170 ZoneMap<Node*, FieldInfo> info_for_node_; 171 }; 172 173 static size_t const kMaxTrackedFields = 32; 174 175 // Abstract state to approximate the current map of an object along the 176 // effect paths through the graph. 177 class AbstractMaps final : public ZoneObject { 178 public: 179 explicit AbstractMaps(Zone* zone); 180 AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone); 181 182 AbstractMaps const* Extend(Node* object, ZoneHandleSet<Map> maps, 183 Zone* zone) const; 184 bool Lookup(Node* object, ZoneHandleSet<Map>* object_maps) const; 185 AbstractMaps const* Kill(const AliasStateInfo& alias_info, 186 Zone* zone) const; 187 bool Equals(AbstractMaps const* that) const { 188 return this == that || this->info_for_node_ == that->info_for_node_; 189 } 190 AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const; 191 192 void Print() const; 193 194 private: 195 ZoneMap<Node*, ZoneHandleSet<Map>> info_for_node_; 196 }; 197 198 class IndexRange { 199 public: 200 IndexRange(int begin, int size) : begin_(begin), end_(begin + size) { 201 DCHECK_LE(0, begin); 202 DCHECK_LE(1, size); 203 if (end_ > static_cast<int>(kMaxTrackedFields)) { 204 *this = IndexRange::Invalid(); 205 } 206 } 207 static IndexRange Invalid() { return IndexRange(); } 208 209 bool operator==(const IndexRange& other) { 210 return begin_ == other.begin_ && end_ == other.end_; 211 } 212 bool operator!=(const IndexRange& other) { return !(*this == other); } 213 214 struct Iterator { 215 int i; 216 int operator*() { return i; } 217 void operator++() { ++i; } 218 bool operator!=(Iterator other) { return i != other.i; } 219 }; 220 221 Iterator begin() { return {begin_}; } 222 Iterator end() { return {end_}; } 223 224 private: 225 int begin_; 226 int end_; 227 228 IndexRange() : begin_(-1), end_(-1) {} 229 }; 230 231 class AbstractState final : public ZoneObject { 232 public: 233 bool Equals(AbstractState const* that) const; 234 void Merge(AbstractState const* that, Zone* zone); 235 236 AbstractState const* SetMaps(Node* object, ZoneHandleSet<Map> maps, 237 Zone* zone) const; 238 AbstractState const* KillMaps(Node* object, Zone* zone) const; 239 AbstractState const* KillMaps(const AliasStateInfo& alias_info, 240 Zone* zone) const; 241 bool LookupMaps(Node* object, ZoneHandleSet<Map>* object_maps) const; 242 243 AbstractState const* AddField(Node* object, IndexRange index, 244 FieldInfo info, Zone* zone) const; 245 AbstractState const* KillConstField(Node* object, IndexRange index_range, 246 Zone* zone) const; 247 AbstractState const* KillField(const AliasStateInfo& alias_info, 248 IndexRange index, MaybeHandle<Name> name, 249 Zone* zone) const; 250 AbstractState const* KillField(Node* object, IndexRange index, 251 MaybeHandle<Name> name, Zone* zone) const; 252 AbstractState const* KillFields(Node* object, MaybeHandle<Name> name, 253 Zone* zone) const; 254 AbstractState const* KillAll(Zone* zone) const; 255 FieldInfo const* LookupField(Node* object, IndexRange index, 256 ConstFieldInfo const_field_info) const; 257 258 AbstractState const* AddElement(Node* object, Node* index, Node* value, 259 MachineRepresentation representation, 260 Zone* zone) const; 261 AbstractState const* KillElement(Node* object, Node* index, 262 Zone* zone) const; 263 Node* LookupElement(Node* object, Node* index, 264 MachineRepresentation representation) const; 265 266 void Print() const; 267 268 static AbstractState const* empty_state() { return &empty_state_; } 269 270 private: 271 static AbstractState const empty_state_; 272 273 using AbstractFields = std::array<AbstractField const*, kMaxTrackedFields>; 274 275 bool FieldsEquals(AbstractFields const& this_fields, 276 AbstractFields const& that_fields) const; 277 void FieldsMerge(AbstractFields* this_fields, 278 AbstractFields const& that_fields, Zone* zone); 279 280 AbstractElements const* elements_ = nullptr; 281 AbstractFields fields_{}; 282 AbstractFields const_fields_{}; 283 AbstractMaps const* maps_ = nullptr; 284 }; 285 286 class AbstractStateForEffectNodes final : public ZoneObject { 287 public: 288 explicit AbstractStateForEffectNodes(Zone* zone) : info_for_node_(zone) {} 289 AbstractState const* Get(Node* node) const; 290 void Set(Node* node, AbstractState const* state); 291 292 Zone* zone() const { return info_for_node_.get_allocator().zone(); } 293 294 private: 295 ZoneVector<AbstractState const*> info_for_node_; 296 }; 297 298 Reduction ReduceCheckMaps(Node* node); 299 Reduction ReduceCompareMaps(Node* node); 300 Reduction ReduceMapGuard(Node* node); 301 Reduction ReduceEnsureWritableFastElements(Node* node); 302 Reduction ReduceMaybeGrowFastElements(Node* node); 303 Reduction ReduceTransitionElementsKind(Node* node); 304 Reduction ReduceLoadField(Node* node, FieldAccess const& access); 305 Reduction ReduceStoreField(Node* node, FieldAccess const& access); 306 Reduction ReduceLoadElement(Node* node); 307 Reduction ReduceStoreElement(Node* node); 308 Reduction ReduceTransitionAndStoreElement(Node* node); 309 Reduction ReduceStoreTypedElement(Node* node); 310 Reduction ReduceEffectPhi(Node* node); 311 Reduction ReduceStart(Node* node); 312 Reduction ReduceOtherNode(Node* node); 313 314 Reduction UpdateState(Node* node, AbstractState const* state); 315 316 AbstractState const* ComputeLoopState(Node* node, 317 AbstractState const* state) const; 318 AbstractState const* ComputeLoopStateForStoreField( 319 Node* current, LoadElimination::AbstractState const* state, 320 FieldAccess const& access) const; 321 AbstractState const* UpdateStateForPhi(AbstractState const* state, 322 Node* effect_phi, Node* phi); 323 324 static IndexRange FieldIndexOf(int offset, int representation_size); 325 static IndexRange FieldIndexOf(FieldAccess const& access); 326 327 static AbstractState const* empty_state() { 328 return AbstractState::empty_state(); 329 } 330 331 CommonOperatorBuilder* common() const; 332 Isolate* isolate() const; 333 Factory* factory() const; 334 Graph* graph() const; 335 JSGraph* jsgraph() const { return jsgraph_; } 336 Zone* zone() const { return node_states_.zone(); } 337 338 AbstractStateForEffectNodes node_states_; 339 JSGraph* const jsgraph_; 340 }; 341 342 } // namespace compiler 343 } // namespace internal 344 } // namespace v8 345 346 #endif // V8_COMPILER_LOAD_ELIMINATION_H_ 347