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