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/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
30 : : public NON_EXPORTED_BASE(AdvancedReducer) {
31 : public:
32 : LoadElimination(Editor* editor, JSGraph* jsgraph, Zone* zone)
33 928170 : : AdvancedReducer(editor), node_states_(zone), jsgraph_(jsgraph) {}
34 928168 : ~LoadElimination() final = default;
35 :
36 18 : const char* reducer_name() const override { return "LoadElimination"; }
37 :
38 : Reduction Reduce(Node* node) final;
39 :
40 : private:
41 : static const size_t kMaxTrackedElements = 8;
42 :
43 : // Abstract state to approximate the current state of an element along the
44 : // effect paths through the graph.
45 : class AbstractElements final : public ZoneObject {
46 : public:
47 56781 : explicit AbstractElements(Zone* zone) {
48 965277 : for (size_t i = 0; i < arraysize(elements_); ++i) {
49 454248 : elements_[i] = Element();
50 : }
51 : }
52 : AbstractElements(Node* object, Node* index, Node* value,
53 : MachineRepresentation representation, Zone* zone)
54 : : AbstractElements(zone) {
55 22614 : elements_[next_index_++] = Element(object, index, value, representation);
56 : }
57 :
58 38710 : AbstractElements const* Extend(Node* object, Node* index, Node* value,
59 : MachineRepresentation representation,
60 : Zone* zone) const {
61 38710 : AbstractElements* that = new (zone) AbstractElements(*this);
62 38710 : that->elements_[that->next_index_] =
63 38710 : Element(object, index, value, representation);
64 38710 : that->next_index_ = (that->next_index_ + 1) % arraysize(elements_);
65 38710 : return that;
66 : }
67 : Node* Lookup(Node* object, Node* index,
68 : MachineRepresentation representation) const;
69 : AbstractElements const* Kill(Node* object, Node* index, Zone* zone) const;
70 : bool Equals(AbstractElements const* that) const;
71 : AbstractElements const* Merge(AbstractElements const* that,
72 : Zone* zone) const;
73 :
74 : void Print() const;
75 :
76 : private:
77 : struct Element {
78 : Element() = default;
79 : Element(Node* object, Node* index, Node* value,
80 : MachineRepresentation representation)
81 : : object(object),
82 : index(index),
83 : value(value),
84 : representation(representation) {}
85 :
86 : Node* object = nullptr;
87 : Node* index = nullptr;
88 : Node* value = nullptr;
89 : MachineRepresentation representation = MachineRepresentation::kNone;
90 : };
91 :
92 : Element elements_[kMaxTrackedElements];
93 : size_t next_index_ = 0;
94 : };
95 :
96 : // Information we use to resolve object aliasing. Currently, we consider
97 : // object not aliased if they have different maps or if the nodes may
98 : // not alias.
99 : class AliasStateInfo;
100 :
101 : // Abstract state to approximate the current state of a certain field along
102 : // the effect paths through the graph.
103 : class AbstractField final : public ZoneObject {
104 : public:
105 : explicit AbstractField(Zone* zone) : info_for_node_(zone) {}
106 : AbstractField(Node* object, Node* value, MaybeHandle<Name> name, Zone* zone)
107 : : info_for_node_(zone) {
108 999310 : info_for_node_.insert(std::make_pair(object, Field(value, name)));
109 : }
110 :
111 643776 : AbstractField const* Extend(Node* object, Node* value,
112 : MaybeHandle<Name> name, Zone* zone) const {
113 : AbstractField* that = new (zone) AbstractField(zone);
114 : that->info_for_node_ = this->info_for_node_;
115 643776 : that->info_for_node_.insert(std::make_pair(object, Field(value, name)));
116 643776 : return that;
117 : }
118 : Node* Lookup(Node* object) const;
119 : AbstractField const* Kill(const AliasStateInfo& alias_info,
120 : MaybeHandle<Name> name, Zone* zone) const;
121 : bool Equals(AbstractField const* that) const {
122 499480 : return this == that || this->info_for_node_ == that->info_for_node_;
123 : }
124 262802 : AbstractField const* Merge(AbstractField const* that, Zone* zone) const {
125 262802 : if (this->Equals(that)) return this;
126 : AbstractField* copy = new (zone) AbstractField(zone);
127 73892 : for (auto this_it : this->info_for_node_) {
128 44755 : Node* this_object = this_it.first;
129 44755 : Field this_second = this_it.second;
130 44755 : if (this_object->IsDead()) continue;
131 : auto that_it = that->info_for_node_.find(this_object);
132 80035 : if (that_it != that->info_for_node_.end() &&
133 : that_it->second == this_second) {
134 : copy->info_for_node_.insert(this_it);
135 : }
136 : }
137 29137 : return copy;
138 : }
139 :
140 : void Print() const;
141 :
142 : private:
143 : struct Field {
144 : Field() = default;
145 : Field(Node* value, MaybeHandle<Name> name) : value(value), name(name) {}
146 :
147 : bool operator==(const Field& other) const {
148 357071 : return value == other.value && name.address() == other.name.address();
149 : }
150 :
151 : Node* value = nullptr;
152 : MaybeHandle<Name> name;
153 : };
154 :
155 : ZoneMap<Node*, Field> 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);
165 : AbstractMaps(Node* object, ZoneHandleSet<Map> maps, Zone* zone);
166 :
167 : AbstractMaps const* Extend(Node* object, ZoneHandleSet<Map> maps,
168 : Zone* zone) const;
169 : bool Lookup(Node* object, ZoneHandleSet<Map>* object_maps) const;
170 : AbstractMaps const* Kill(const AliasStateInfo& alias_info,
171 : Zone* zone) const;
172 : bool Equals(AbstractMaps const* that) const {
173 67126 : return this == that || this->info_for_node_ == that->info_for_node_;
174 : }
175 : AbstractMaps const* Merge(AbstractMaps const* that, Zone* zone) const;
176 :
177 : void Print() const;
178 :
179 : private:
180 : ZoneMap<Node*, ZoneHandleSet<Map>> info_for_node_;
181 : };
182 :
183 : class AbstractState final : public ZoneObject {
184 : public:
185 464085 : AbstractState() {
186 30165525 : for (size_t i = 0; i < arraysize(fields_); ++i) {
187 14850720 : fields_[i] = nullptr;
188 : }
189 : }
190 :
191 : bool Equals(AbstractState const* that) const;
192 : void Merge(AbstractState const* that, Zone* zone);
193 :
194 : AbstractState const* SetMaps(Node* object, ZoneHandleSet<Map> maps,
195 : Zone* zone) const;
196 : AbstractState const* KillMaps(Node* object, Zone* zone) const;
197 : AbstractState const* KillMaps(const AliasStateInfo& alias_info,
198 : Zone* zone) const;
199 : bool LookupMaps(Node* object, ZoneHandleSet<Map>* object_maps) const;
200 :
201 : AbstractState const* AddField(Node* object, size_t index, Node* value,
202 : MaybeHandle<Name> name, Zone* zone) const;
203 : AbstractState const* KillField(const AliasStateInfo& alias_info,
204 : size_t index, MaybeHandle<Name> name,
205 : Zone* zone) const;
206 : AbstractState const* KillField(Node* object, size_t index,
207 : MaybeHandle<Name> name, Zone* zone) const;
208 : AbstractState const* KillFields(Node* object, MaybeHandle<Name> name,
209 : Zone* zone) const;
210 : Node* LookupField(Node* object, size_t index) const;
211 :
212 : AbstractState const* AddElement(Node* object, Node* index, Node* value,
213 : MachineRepresentation representation,
214 : Zone* zone) const;
215 : AbstractState const* KillElement(Node* object, Node* index,
216 : Zone* zone) const;
217 : Node* LookupElement(Node* object, Node* index,
218 : MachineRepresentation representation) const;
219 :
220 : void Print() const;
221 :
222 : private:
223 : AbstractElements const* elements_ = nullptr;
224 : AbstractField const* fields_[kMaxTrackedFields];
225 : AbstractMaps const* maps_ = nullptr;
226 : };
227 :
228 464084 : class AbstractStateForEffectNodes final : public ZoneObject {
229 : public:
230 : explicit AbstractStateForEffectNodes(Zone* zone) : info_for_node_(zone) {}
231 : AbstractState const* Get(Node* node) const;
232 : void Set(Node* node, AbstractState const* state);
233 :
234 : Zone* zone() const { return info_for_node_.get_allocator().zone(); }
235 :
236 : private:
237 : ZoneVector<AbstractState const*> info_for_node_;
238 : };
239 :
240 : Reduction ReduceCheckMaps(Node* node);
241 : Reduction ReduceCompareMaps(Node* node);
242 : Reduction ReduceMapGuard(Node* node);
243 : Reduction ReduceEnsureWritableFastElements(Node* node);
244 : Reduction ReduceMaybeGrowFastElements(Node* node);
245 : Reduction ReduceTransitionElementsKind(Node* node);
246 : Reduction ReduceLoadField(Node* node, FieldAccess const& access);
247 : Reduction ReduceStoreField(Node* node, FieldAccess const& access);
248 : Reduction ReduceLoadElement(Node* node);
249 : Reduction ReduceStoreElement(Node* node);
250 : Reduction ReduceTransitionAndStoreElement(Node* node);
251 : Reduction ReduceStoreTypedElement(Node* node);
252 : Reduction ReduceEffectPhi(Node* node);
253 : Reduction ReduceStart(Node* node);
254 : Reduction ReduceStoreMessage(Node* node);
255 : Reduction ReduceLoadMessage(Node* node);
256 : Reduction ReduceOtherNode(Node* node);
257 :
258 : Reduction UpdateState(Node* node, AbstractState const* state);
259 :
260 : AbstractState const* ComputeLoopState(Node* node,
261 : AbstractState const* state) const;
262 : AbstractState const* ComputeLoopStateForStoreField(
263 : Node* current, LoadElimination::AbstractState const* state,
264 : FieldAccess const& access) const;
265 : AbstractState const* UpdateStateForPhi(AbstractState const* state,
266 : Node* effect_phi, Node* phi);
267 :
268 : static int FieldIndexOf(int offset);
269 : static int FieldIndexOf(FieldAccess const& access);
270 :
271 : CommonOperatorBuilder* common() const;
272 3098588 : AbstractState const* empty_state() const { return &empty_state_; }
273 : Isolate* isolate() const;
274 : Factory* factory() const;
275 : Graph* graph() const;
276 : JSGraph* jsgraph() const { return jsgraph_; }
277 : Zone* zone() const { return node_states_.zone(); }
278 :
279 : AbstractState const empty_state_;
280 : AbstractStateForEffectNodes node_states_;
281 : JSGraph* const jsgraph_;
282 :
283 : DISALLOW_COPY_AND_ASSIGN(LoadElimination);
284 : };
285 :
286 : } // namespace compiler
287 : } // namespace internal
288 : } // namespace v8
289 :
290 : #endif // V8_COMPILER_LOAD_ELIMINATION_H_
|
