Line data Source code
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
28 : : public NON_EXPORTED_BASE(AdvancedReducer) {
29 : public:
30 : LoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)
31 786350 : : AdvancedReducer(editor), node_states_(zone), jsgraph_(jsgraph) {}
32 393175 : ~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 510 : explicit AbstractChecks(Zone* zone) {
45 4080 : for (size_t i = 0; i < arraysize(nodes_); ++i) {
46 4080 : nodes_[i] = nullptr;
47 : }
48 : }
49 : AbstractChecks(Node* node, Zone* zone) : AbstractChecks(zone) {
50 295 : nodes_[next_index_++] = node;
51 : }
52 :
53 132 : AbstractChecks const* Extend(Node* node, Zone* zone) const {
54 132 : AbstractChecks* that = new (zone) AbstractChecks(*this);
55 132 : that->nodes_[that->next_index_] = node;
56 132 : that->next_index_ = (that->next_index_ + 1) % arraysize(nodes_);
57 132 : 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 1783134 : explicit AbstractElements(Zone* zone) {
77 1585008 : for (size_t i = 0; i < arraysize(elements_); ++i) {
78 1585008 : elements_[i] = Element();
79 : }
80 : }
81 35459 : AbstractElements(Node* object, Node* index, Node* value, Zone* zone)
82 : : AbstractElements(zone) {
83 35459 : elements_[next_index_++] = Element(object, index, value);
84 35459 : }
85 :
86 164960 : AbstractElements const* Extend(Node* object, Node* index, Node* value,
87 : Zone* zone) const {
88 164960 : AbstractElements* that = new (zone) AbstractElements(*this);
89 164960 : that->elements_[that->next_index_] = Element(object, index, value);
90 164960 : that->next_index_ = (that->next_index_ + 1) % arraysize(elements_);
91 164960 : 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 1585008 : 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 1340654 : AbstractField(Node* object, Node* value, Zone* zone)
122 : : info_for_node_(zone) {
123 2681307 : info_for_node_.insert(std::make_pair(object, value));
124 1340653 : }
125 :
126 488719 : 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 977438 : that->info_for_node_.insert(std::make_pair(object, value));
130 488719 : 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 755632 : return this == that || this->info_for_node_ == that->info_for_node_;
136 : }
137 197573 : AbstractField const* Merge(AbstractField const* that, Zone* zone) const {
138 197573 : if (this->Equals(that)) return this;
139 : AbstractField* copy = new (zone) AbstractField(zone);
140 228227 : for (auto this_it : this->info_for_node_) {
141 81335 : Node* this_object = this_it.first;
142 81335 : Node* this_value = this_it.second;
143 : auto that_it = that->info_for_node_.find(this_object);
144 134808 : if (that_it != that->info_for_node_.end() &&
145 53473 : that_it->second == this_value) {
146 : copy->info_for_node_.insert(this_it);
147 : }
148 : }
149 73446 : 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 121659 : AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone)
166 : : info_for_node_(zone) {
167 243319 : info_for_node_.insert(std::make_pair(object, maps));
168 121660 : }
169 :
170 74989 : 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 149978 : that->info_for_node_.insert(std::make_pair(object, maps));
175 74989 : 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 146648 : return this == that || this->info_for_node_ == that->info_for_node_;
181 : }
182 29471 : AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const {
183 29471 : if (this->Equals(that)) return this;
184 : AbstractMaps* copy = new (zone) AbstractMaps(zone);
185 38025 : for (auto this_it : this->info_for_node_) {
186 16395 : Node* this_object = this_it.first;
187 16395 : ZoneHandleSet<Map> this_maps = this_it.second;
188 : auto that_it = that->info_for_node_.find(this_object);
189 19104 : if (that_it != that->info_for_node_.end() &&
190 2709 : that_it->second == this_maps) {
191 : copy->info_for_node_.insert(this_it);
192 : }
193 : }
194 10815 : 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 393175 : AbstractState() {
206 12581600 : for (size_t i = 0; i < arraysize(fields_); ++i) {
207 12581600 : 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_
|
