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