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