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