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 : #include "src/compiler/load-elimination.h"
6 :
7 : #include "src/compiler/common-operator.h"
8 : #include "src/compiler/js-graph.h"
9 : #include "src/compiler/node-properties.h"
10 : #include "src/compiler/simplified-operator.h"
11 : #include "src/factory.h"
12 : #include "src/objects-inl.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 :
18 : namespace {
19 :
20 : enum Aliasing { kNoAlias, kMayAlias, kMustAlias };
21 :
22 7794442 : Aliasing QueryAlias(Node* a, Node* b) {
23 5725178 : if (a == b) return kMustAlias;
24 2713360 : if (!NodeProperties::GetType(a)->Maybe(NodeProperties::GetType(b))) {
25 : return kNoAlias;
26 : }
27 1008923 : switch (b->opcode()) {
28 : case IrOpcode::kAllocate: {
29 653549 : switch (a->opcode()) {
30 : case IrOpcode::kAllocate:
31 : case IrOpcode::kHeapConstant:
32 : case IrOpcode::kParameter:
33 : return kNoAlias;
34 : default:
35 : break;
36 : }
37 : break;
38 : }
39 : case IrOpcode::kFinishRegion:
40 : case IrOpcode::kTypeGuard:
41 38153 : return QueryAlias(a, b->InputAt(0));
42 : default:
43 : break;
44 : }
45 717142 : switch (a->opcode()) {
46 : case IrOpcode::kAllocate: {
47 40629 : switch (b->opcode()) {
48 : case IrOpcode::kHeapConstant:
49 : case IrOpcode::kParameter:
50 : return kNoAlias;
51 : default:
52 : break;
53 : }
54 : break;
55 : }
56 : case IrOpcode::kFinishRegion:
57 : case IrOpcode::kTypeGuard:
58 272197 : return QueryAlias(a->InputAt(0), b);
59 : default:
60 : break;
61 : }
62 425295 : return kMayAlias;
63 : }
64 :
65 2296273 : bool MayAlias(Node* a, Node* b) { return QueryAlias(a, b) != kNoAlias; }
66 :
67 3118555 : bool MustAlias(Node* a, Node* b) { return QueryAlias(a, b) == kMustAlias; }
68 :
69 : } // namespace
70 :
71 70936298 : Reduction LoadElimination::Reduce(Node* node) {
72 35468149 : if (FLAG_trace_turbo_load_elimination) {
73 0 : if (node->op()->EffectInputCount() > 0) {
74 0 : PrintF(" visit #%d:%s", node->id(), node->op()->mnemonic());
75 0 : if (node->op()->ValueInputCount() > 0) {
76 0 : PrintF("(");
77 0 : for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
78 0 : if (i > 0) PrintF(", ");
79 0 : Node* const value = NodeProperties::GetValueInput(node, i);
80 0 : PrintF("#%d:%s", value->id(), value->op()->mnemonic());
81 : }
82 0 : PrintF(")");
83 : }
84 0 : PrintF("\n");
85 0 : for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
86 0 : Node* const effect = NodeProperties::GetEffectInput(node, i);
87 0 : if (AbstractState const* const state = node_states_.Get(effect)) {
88 : PrintF(" state[%i]: #%d:%s\n", i, effect->id(),
89 0 : effect->op()->mnemonic());
90 0 : state->Print();
91 : } else {
92 : PrintF(" no state[%i]: #%d:%s\n", i, effect->id(),
93 0 : effect->op()->mnemonic());
94 : }
95 : }
96 : }
97 : }
98 35468149 : switch (node->opcode()) {
99 : case IrOpcode::kArrayBufferWasNeutered:
100 636 : return ReduceArrayBufferWasNeutered(node);
101 : case IrOpcode::kCheckMaps:
102 138591 : return ReduceCheckMaps(node);
103 : case IrOpcode::kEnsureWritableFastElements:
104 212 : return ReduceEnsureWritableFastElements(node);
105 : case IrOpcode::kMaybeGrowFastElements:
106 3217 : return ReduceMaybeGrowFastElements(node);
107 : case IrOpcode::kTransitionElementsKind:
108 667 : return ReduceTransitionElementsKind(node);
109 : case IrOpcode::kLoadField:
110 1427468 : return ReduceLoadField(node);
111 : case IrOpcode::kStoreField:
112 1344908 : return ReduceStoreField(node);
113 : case IrOpcode::kLoadElement:
114 56448 : return ReduceLoadElement(node);
115 : case IrOpcode::kStoreElement:
116 180680 : return ReduceStoreElement(node);
117 : case IrOpcode::kStoreTypedElement:
118 4921 : return ReduceStoreTypedElement(node);
119 : case IrOpcode::kEffectPhi:
120 956620 : return ReduceEffectPhi(node);
121 : case IrOpcode::kDead:
122 : break;
123 : case IrOpcode::kStart:
124 : return ReduceStart(node);
125 : default:
126 30955400 : return ReduceOtherNode(node);
127 : }
128 : return NoChange();
129 : }
130 :
131 : namespace {
132 :
133 41 : bool IsCompatibleCheck(Node const* a, Node const* b) {
134 41 : if (a->op() != b->op()) return false;
135 140 : for (int i = a->op()->ValueInputCount(); --i >= 0;) {
136 41 : if (!MustAlias(a->InputAt(i), b->InputAt(i))) return false;
137 : }
138 : return true;
139 : }
140 :
141 : } // namespace
142 :
143 149 : Node* LoadElimination::AbstractChecks::Lookup(Node* node) const {
144 1205 : for (Node* const check : nodes_) {
145 1073 : if (check && IsCompatibleCheck(check, node)) {
146 : return check;
147 : }
148 : }
149 : return nullptr;
150 : }
151 :
152 627 : bool LoadElimination::AbstractChecks::Equals(AbstractChecks const* that) const {
153 627 : if (this == that) return true;
154 1248 : for (size_t i = 0; i < arraysize(nodes_); ++i) {
155 1449 : if (Node* this_node = this->nodes_[i]) {
156 1615 : for (size_t j = 0;; ++j) {
157 1937 : if (j == arraysize(nodes_)) return false;
158 1736 : if (that->nodes_[j] == this_node) break;
159 1615 : }
160 : }
161 : }
162 1150 : for (size_t i = 0; i < arraysize(nodes_); ++i) {
163 1164 : if (Node* that_node = that->nodes_[i]) {
164 119 : for (size_t j = 0;; ++j) {
165 254 : if (j == arraysize(nodes_)) return false;
166 240 : if (this->nodes_[j] == that_node) break;
167 119 : }
168 : }
169 : }
170 : return true;
171 : }
172 :
173 263 : LoadElimination::AbstractChecks const* LoadElimination::AbstractChecks::Merge(
174 : AbstractChecks const* that, Zone* zone) const {
175 263 : if (this->Equals(that)) return this;
176 : AbstractChecks* copy = new (zone) AbstractChecks(zone);
177 1935 : for (Node* const this_node : this->nodes_) {
178 1720 : if (this_node == nullptr) continue;
179 1823 : for (Node* const that_node : that->nodes_) {
180 1622 : if (this_node == that_node) {
181 14 : copy->nodes_[copy->next_index_++] = this_node;
182 14 : break;
183 : }
184 : }
185 : }
186 215 : copy->next_index_ %= arraysize(nodes_);
187 215 : return copy;
188 : }
189 :
190 0 : void LoadElimination::AbstractChecks::Print() const {
191 0 : for (Node* const node : nodes_) {
192 0 : if (node != nullptr) {
193 0 : PrintF(" #%d:%s\n", node->id(), node->op()->mnemonic());
194 : }
195 : }
196 0 : }
197 :
198 165637 : Node* LoadElimination::AbstractElements::Lookup(Node* object,
199 : Node* index) const {
200 1478216 : for (Element const element : elements_) {
201 1314253 : if (element.object == nullptr) continue;
202 : DCHECK_NOT_NULL(element.index);
203 : DCHECK_NOT_NULL(element.value);
204 2317669 : if (MustAlias(object, element.object) && MustAlias(index, element.index)) {
205 : return element.value;
206 : }
207 : }
208 : return nullptr;
209 : }
210 :
211 : LoadElimination::AbstractElements const*
212 159590 : LoadElimination::AbstractElements::Kill(Node* object, Node* index,
213 : Zone* zone) const {
214 183427 : for (Element const element : this->elements_) {
215 180611 : if (element.object == nullptr) continue;
216 158939 : if (MayAlias(object, element.object)) {
217 : AbstractElements* that = new (zone) AbstractElements(zone);
218 2508384 : for (Element const element : this->elements_) {
219 1254192 : if (element.object == nullptr) continue;
220 : DCHECK_NOT_NULL(element.index);
221 : DCHECK_NOT_NULL(element.value);
222 2297841 : if (!MayAlias(object, element.object) ||
223 : !NodeProperties::GetType(index)->Maybe(
224 1147932 : NodeProperties::GetType(element.index))) {
225 1137898 : that->elements_[that->next_index_++] = element;
226 : }
227 : }
228 156774 : that->next_index_ %= arraysize(elements_);
229 : return that;
230 : }
231 : }
232 2816 : return this;
233 : }
234 :
235 23000 : bool LoadElimination::AbstractElements::Equals(
236 : AbstractElements const* that) const {
237 23000 : if (this == that) return true;
238 87014 : for (size_t i = 0; i < arraysize(elements_); ++i) {
239 92821 : Element this_element = this->elements_[i];
240 92821 : if (this_element.object == nullptr) continue;
241 53016 : for (size_t j = 0;; ++j) {
242 72412 : if (j == arraysize(elements_)) return false;
243 66605 : Element that_element = that->elements_[j];
244 66605 : if (this_element.object == that_element.object &&
245 13891 : this_element.index == that_element.index &&
246 : this_element.value == that_element.value) {
247 : break;
248 : }
249 53016 : }
250 : }
251 84344 : for (size_t i = 0; i < arraysize(elements_); ++i) {
252 84683 : Element that_element = that->elements_[i];
253 84683 : if (that_element.object == nullptr) continue;
254 9038 : for (size_t j = 0;; ++j) {
255 22414 : if (j == arraysize(elements_)) return false;
256 22075 : Element this_element = this->elements_[j];
257 22075 : if (that_element.object == this_element.object &&
258 13037 : that_element.index == this_element.index &&
259 : that_element.value == this_element.value) {
260 : break;
261 : }
262 9038 : }
263 : }
264 : return true;
265 : }
266 :
267 : LoadElimination::AbstractElements const*
268 10037 : LoadElimination::AbstractElements::Merge(AbstractElements const* that,
269 : Zone* zone) const {
270 10037 : if (this->Equals(that)) return this;
271 : AbstractElements* copy = new (zone) AbstractElements(zone);
272 53037 : for (Element const this_element : this->elements_) {
273 47144 : if (this_element.object == nullptr) continue;
274 57438 : for (Element const that_element : that->elements_) {
275 51230 : if (this_element.object == that_element.object &&
276 1220 : this_element.index == that_element.index &&
277 : this_element.value == that_element.value) {
278 918 : copy->elements_[copy->next_index_++] = this_element;
279 918 : break;
280 : }
281 : }
282 : }
283 5893 : copy->next_index_ %= arraysize(elements_);
284 5893 : return copy;
285 : }
286 :
287 0 : void LoadElimination::AbstractElements::Print() const {
288 0 : for (Element const& element : elements_) {
289 0 : if (element.object) {
290 : PrintF(" #%d:%s @ #%d:%s -> #%d:%s\n", element.object->id(),
291 : element.object->op()->mnemonic(), element.index->id(),
292 : element.index->op()->mnemonic(), element.value->id(),
293 0 : element.value->op()->mnemonic());
294 : }
295 : }
296 0 : }
297 :
298 616978 : Node* LoadElimination::AbstractField::Lookup(Node* object) const {
299 1703745 : for (auto pair : info_for_node_) {
300 713689 : if (MustAlias(object, pair.first)) return pair.second;
301 : }
302 : return nullptr;
303 : }
304 :
305 1081140 : LoadElimination::AbstractField const* LoadElimination::AbstractField::Kill(
306 : Node* object, Zone* zone) const {
307 2450425 : for (auto pair : this->info_for_node_) {
308 541688 : if (MayAlias(object, pair.first)) {
309 : AbstractField* that = new (zone) AbstractField(zone);
310 874339 : for (auto pair : this->info_for_node_) {
311 734506 : if (!MayAlias(object, pair.first)) that->info_for_node_.insert(pair);
312 : }
313 : return that;
314 : }
315 : }
316 : return this;
317 : }
318 :
319 0 : void LoadElimination::AbstractField::Print() const {
320 0 : for (auto pair : info_for_node_) {
321 : PrintF(" #%d:%s -> #%d:%s\n", pair.first->id(),
322 : pair.first->op()->mnemonic(), pair.second->id(),
323 0 : pair.second->op()->mnemonic());
324 : }
325 0 : }
326 :
327 58580 : bool LoadElimination::AbstractMaps::Lookup(
328 : Node* object, ZoneHandleSet<Map>* object_maps) const {
329 166504 : for (auto pair : info_for_node_) {
330 87156 : if (MustAlias(object, pair.first)) {
331 37812 : *object_maps = pair.second;
332 : return true;
333 : }
334 : }
335 : return false;
336 : }
337 :
338 54411 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Kill(
339 : Node* object, Zone* zone) const {
340 169122 : for (auto pair : this->info_for_node_) {
341 67475 : if (MayAlias(object, pair.first)) {
342 : AbstractMaps* that = new (zone) AbstractMaps(zone);
343 25359 : for (auto pair : this->info_for_node_) {
344 22018 : if (!MayAlias(object, pair.first)) that->info_for_node_.insert(pair);
345 : }
346 : return that;
347 : }
348 : }
349 : return this;
350 : }
351 :
352 0 : void LoadElimination::AbstractMaps::Print() const {
353 0 : for (auto pair : info_for_node_) {
354 0 : PrintF(" #%d:%s\n", pair.first->id(), pair.first->op()->mnemonic());
355 0 : OFStream os(stdout);
356 : ZoneHandleSet<Map> const& maps = pair.second;
357 0 : for (size_t i = 0; i < maps.size(); ++i) {
358 0 : os << " - " << Brief(*maps[i]) << "\n";
359 : }
360 0 : }
361 0 : }
362 :
363 205591 : bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
364 205591 : if (this->checks_) {
365 364 : if (!that->checks_ || !that->checks_->Equals(this->checks_)) {
366 : return false;
367 : }
368 205227 : } else if (that->checks_) {
369 : return false;
370 : }
371 205591 : if (this->elements_) {
372 12963 : if (!that->elements_ || !that->elements_->Equals(this->elements_)) {
373 : return false;
374 : }
375 192628 : } else if (that->elements_) {
376 : return false;
377 : }
378 6567599 : for (size_t i = 0u; i < arraysize(fields_); ++i) {
379 6567692 : AbstractField const* this_field = this->fields_[i];
380 6567692 : AbstractField const* that_field = that->fields_[i];
381 6567692 : if (this_field) {
382 757795 : if (!that_field || !that_field->Equals(this_field)) return false;
383 6188800 : } else if (that_field) {
384 : return false;
385 : }
386 : }
387 205235 : if (this->maps_) {
388 172816 : if (!that->maps_ || !that->maps_->Equals(this->maps_)) {
389 : return false;
390 : }
391 118827 : } else if (that->maps_) {
392 : return false;
393 : }
394 : return true;
395 : }
396 :
397 1285986 : void LoadElimination::AbstractState::Merge(AbstractState const* that,
398 : Zone* zone) {
399 : // Merge the information we have about the checks.
400 1285986 : if (this->checks_) {
401 : this->checks_ =
402 270 : that->checks_ ? that->checks_->Merge(this->checks_, zone) : nullptr;
403 : }
404 :
405 : // Merge the information we have about the elements.
406 1285986 : if (this->elements_) {
407 : this->elements_ = that->elements_
408 : ? that->elements_->Merge(this->elements_, zone)
409 20609 : : nullptr;
410 : }
411 :
412 : // Merge the information we have about the fields.
413 41151579 : for (size_t i = 0; i < arraysize(fields_); ++i) {
414 41151577 : if (this->fields_[i]) {
415 548285 : if (that->fields_[i]) {
416 197571 : this->fields_[i] = this->fields_[i]->Merge(that->fields_[i], zone);
417 : } else {
418 350714 : this->fields_[i] = nullptr;
419 : }
420 : }
421 : }
422 :
423 : // Merge the information we have about the maps.
424 1285988 : if (this->maps_) {
425 54857 : this->maps_ = that->maps_ ? that->maps_->Merge(this->maps_, zone) : nullptr;
426 : }
427 1285988 : }
428 :
429 0 : Node* LoadElimination::AbstractState::LookupCheck(Node* node) const {
430 444 : return this->checks_ ? this->checks_->Lookup(node) : nullptr;
431 : }
432 :
433 427 : LoadElimination::AbstractState const* LoadElimination::AbstractState::AddCheck(
434 : Node* node, Zone* zone) const {
435 427 : AbstractState* that = new (zone) AbstractState(*this);
436 427 : if (that->checks_) {
437 132 : that->checks_ = that->checks_->Extend(node, zone);
438 : } else {
439 295 : that->checks_ = new (zone) AbstractChecks(node, zone);
440 : }
441 427 : return that;
442 : }
443 :
444 0 : bool LoadElimination::AbstractState::LookupMaps(
445 : Node* object, ZoneHandleSet<Map>* object_map) const {
446 104162 : return this->maps_ && this->maps_->Lookup(object, object_map);
447 : }
448 :
449 196648 : LoadElimination::AbstractState const* LoadElimination::AbstractState::AddMaps(
450 : Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
451 196648 : AbstractState* that = new (zone) AbstractState(*this);
452 196648 : if (that->maps_) {
453 74989 : that->maps_ = that->maps_->Extend(object, maps, zone);
454 : } else {
455 243318 : that->maps_ = new (zone) AbstractMaps(object, maps, zone);
456 : }
457 196649 : return that;
458 : }
459 :
460 136487 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
461 : Node* object, Zone* zone) const {
462 136487 : if (this->maps_) {
463 54411 : AbstractMaps const* that_maps = this->maps_->Kill(object, zone);
464 54411 : if (this->maps_ != that_maps) {
465 7175 : AbstractState* that = new (zone) AbstractState(*this);
466 7175 : that->maps_ = that_maps;
467 7175 : return that;
468 : }
469 : }
470 129312 : return this;
471 : }
472 :
473 0 : Node* LoadElimination::AbstractState::LookupElement(Node* object,
474 : Node* index) const {
475 201346 : if (this->elements_) {
476 165637 : return this->elements_->Lookup(object, index);
477 : }
478 : return nullptr;
479 : }
480 :
481 : LoadElimination::AbstractState const*
482 200419 : LoadElimination::AbstractState::AddElement(Node* object, Node* index,
483 : Node* value, Zone* zone) const {
484 200419 : AbstractState* that = new (zone) AbstractState(*this);
485 200419 : if (that->elements_) {
486 164960 : that->elements_ = that->elements_->Extend(object, index, value, zone);
487 : } else {
488 35459 : that->elements_ = new (zone) AbstractElements(object, index, value, zone);
489 : }
490 200419 : return that;
491 : }
492 :
493 : LoadElimination::AbstractState const*
494 171495 : LoadElimination::AbstractState::KillElement(Node* object, Node* index,
495 : Zone* zone) const {
496 171495 : if (this->elements_) {
497 : AbstractElements const* that_elements =
498 159590 : this->elements_->Kill(object, index, zone);
499 159590 : if (this->elements_ != that_elements) {
500 156774 : AbstractState* that = new (zone) AbstractState(*this);
501 156774 : that->elements_ = that_elements;
502 156774 : return that;
503 : }
504 : }
505 14721 : return this;
506 : }
507 :
508 1829372 : LoadElimination::AbstractState const* LoadElimination::AbstractState::AddField(
509 : Node* object, size_t index, Node* value, Zone* zone) const {
510 1829373 : AbstractState* that = new (zone) AbstractState(*this);
511 1829373 : if (that->fields_[index]) {
512 488719 : that->fields_[index] = that->fields_[index]->Extend(object, value, zone);
513 : } else {
514 1340654 : that->fields_[index] = new (zone) AbstractField(object, value, zone);
515 : }
516 1829372 : return that;
517 : }
518 :
519 913348 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
520 : Node* object, size_t index, Zone* zone) const {
521 913348 : if (AbstractField const* this_field = this->fields_[index]) {
522 337385 : this_field = this_field->Kill(object, zone);
523 337385 : if (this->fields_[index] != this_field) {
524 194080 : AbstractState* that = new (zone) AbstractState(*this);
525 194080 : that->fields_[index] = this_field;
526 194080 : return that;
527 : }
528 : }
529 719268 : return this;
530 : }
531 :
532 : LoadElimination::AbstractState const*
533 92021 : LoadElimination::AbstractState::KillFields(Node* object, Zone* zone) const {
534 2025998 : for (size_t i = 0;; ++i) {
535 2118019 : if (i == arraysize(fields_)) return this;
536 2055163 : if (AbstractField const* this_field = this->fields_[i]) {
537 617705 : AbstractField const* that_field = this_field->Kill(object, zone);
538 617705 : if (that_field != this_field) {
539 29165 : AbstractState* that = new (zone) AbstractState(*this);
540 29165 : that->fields_[i] = that_field;
541 947807 : while (++i < arraysize(fields_)) {
542 889477 : if (this->fields_[i] != nullptr) {
543 126050 : that->fields_[i] = this->fields_[i]->Kill(object, zone);
544 : }
545 : }
546 : return that;
547 : }
548 : }
549 2025998 : }
550 : }
551 :
552 0 : Node* LoadElimination::AbstractState::LookupField(Node* object,
553 : size_t index) const {
554 1957632 : if (AbstractField const* this_field = this->fields_[index]) {
555 616978 : return this_field->Lookup(object);
556 : }
557 : return nullptr;
558 : }
559 :
560 0 : void LoadElimination::AbstractState::Print() const {
561 0 : if (checks_) {
562 0 : PrintF(" checks:\n");
563 0 : checks_->Print();
564 : }
565 0 : if (maps_) {
566 0 : PrintF(" maps:\n");
567 0 : maps_->Print();
568 : }
569 0 : if (elements_) {
570 0 : PrintF(" elements:\n");
571 0 : elements_->Print();
572 : }
573 0 : for (size_t i = 0; i < arraysize(fields_); ++i) {
574 0 : if (AbstractField const* const field = fields_[i]) {
575 0 : PrintF(" field %zu:\n", i);
576 0 : field->Print();
577 : }
578 : }
579 0 : }
580 :
581 : LoadElimination::AbstractState const*
582 26654038 : LoadElimination::AbstractStateForEffectNodes::Get(Node* node) const {
583 26654038 : size_t const id = node->id();
584 74680846 : if (id < info_for_node_.size()) return info_for_node_[id];
585 : return nullptr;
586 : }
587 :
588 9231190 : void LoadElimination::AbstractStateForEffectNodes::Set(
589 9231190 : Node* node, AbstractState const* state) {
590 9231190 : size_t const id = node->id();
591 18462380 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
592 9231186 : info_for_node_[id] = state;
593 9231186 : }
594 :
595 636 : Reduction LoadElimination::ReduceArrayBufferWasNeutered(Node* node) {
596 636 : Node* const effect = NodeProperties::GetEffectInput(node);
597 : AbstractState const* state = node_states_.Get(effect);
598 636 : if (state == nullptr) return NoChange();
599 444 : if (Node* const check = state->LookupCheck(node)) {
600 17 : ReplaceWithValue(node, check, effect);
601 : return Replace(check);
602 : }
603 427 : state = state->AddCheck(node, zone());
604 427 : return UpdateState(node, state);
605 : }
606 :
607 138591 : Reduction LoadElimination::ReduceCheckMaps(Node* node) {
608 138591 : ZoneHandleSet<Map> const maps = CheckMapsParametersOf(node->op()).maps();
609 138591 : Node* const object = NodeProperties::GetValueInput(node, 0);
610 138591 : Node* const effect = NodeProperties::GetEffectInput(node);
611 : AbstractState const* state = node_states_.Get(effect);
612 138591 : if (state == nullptr) return NoChange();
613 : ZoneHandleSet<Map> object_maps;
614 89089 : if (state->LookupMaps(object, &object_maps)) {
615 36782 : if (maps.contains(object_maps)) return Replace(effect);
616 679 : state = state->KillMaps(object, zone());
617 : // TODO(turbofan): Compute the intersection.
618 : }
619 52986 : state = state->AddMaps(object, maps, zone());
620 52986 : return UpdateState(node, state);
621 : }
622 :
623 212 : Reduction LoadElimination::ReduceEnsureWritableFastElements(Node* node) {
624 212 : Node* const object = NodeProperties::GetValueInput(node, 0);
625 212 : Node* const elements = NodeProperties::GetValueInput(node, 1);
626 212 : Node* const effect = NodeProperties::GetEffectInput(node);
627 : AbstractState const* state = node_states_.Get(effect);
628 212 : if (state == nullptr) return NoChange();
629 : // Check if the {elements} already have the fixed array map.
630 : ZoneHandleSet<Map> elements_maps;
631 : ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
632 196 : if (state->LookupMaps(elements, &elements_maps) &&
633 4 : fixed_array_maps.contains(elements_maps)) {
634 4 : ReplaceWithValue(node, elements, effect);
635 : return Replace(elements);
636 : }
637 : // We know that the resulting elements have the fixed array map.
638 188 : state = state->AddMaps(node, fixed_array_maps, zone());
639 : // Kill the previous elements on {object}.
640 : state =
641 188 : state->KillField(object, FieldIndexOf(JSObject::kElementsOffset), zone());
642 : // Add the new elements on {object}.
643 : state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
644 188 : zone());
645 188 : return UpdateState(node, state);
646 : }
647 :
648 3217 : Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
649 3217 : GrowFastElementsFlags flags = GrowFastElementsFlagsOf(node->op());
650 3217 : Node* const object = NodeProperties::GetValueInput(node, 0);
651 3217 : Node* const effect = NodeProperties::GetEffectInput(node);
652 : AbstractState const* state = node_states_.Get(effect);
653 3217 : if (state == nullptr) return NoChange();
654 2213 : if (flags & GrowFastElementsFlag::kDoubleElements) {
655 : // We know that the resulting elements have the fixed double array map.
656 : state = state->AddMaps(
657 193 : node, ZoneHandleSet<Map>(factory()->fixed_double_array_map()), zone());
658 : } else {
659 : // We know that the resulting elements have the fixed array map.
660 : state = state->AddMaps(
661 2020 : node, ZoneHandleSet<Map>(factory()->fixed_array_map()), zone());
662 : }
663 2213 : if (flags & GrowFastElementsFlag::kArrayObject) {
664 : // Kill the previous Array::length on {object}.
665 : state =
666 2200 : state->KillField(object, FieldIndexOf(JSArray::kLengthOffset), zone());
667 : }
668 : // Kill the previous elements on {object}.
669 : state =
670 2213 : state->KillField(object, FieldIndexOf(JSObject::kElementsOffset), zone());
671 : // Add the new elements on {object}.
672 : state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
673 2213 : zone());
674 2213 : return UpdateState(node, state);
675 : }
676 :
677 667 : Reduction LoadElimination::ReduceTransitionElementsKind(Node* node) {
678 667 : ElementsTransition transition = ElementsTransitionOf(node->op());
679 667 : Node* const object = NodeProperties::GetValueInput(node, 0);
680 : Handle<Map> source_map(transition.source());
681 : Handle<Map> target_map(transition.target());
682 667 : Node* const effect = NodeProperties::GetEffectInput(node);
683 : AbstractState const* state = node_states_.Get(effect);
684 667 : if (state == nullptr) return NoChange();
685 : ZoneHandleSet<Map> object_maps;
686 571 : if (state->LookupMaps(object, &object_maps)) {
687 125 : if (ZoneHandleSet<Map>(target_map).contains(object_maps)) {
688 : // The {object} already has the {target_map}, so this TransitionElements
689 : // {node} is fully redundant (independent of what {source_map} is).
690 : return Replace(effect);
691 : }
692 62 : if (object_maps.contains(ZoneHandleSet<Map>(source_map))) {
693 62 : object_maps.remove(source_map, zone());
694 62 : object_maps.insert(target_map, zone());
695 62 : state = state->KillMaps(object, zone());
696 62 : state = state->AddMaps(object, object_maps, zone());
697 : }
698 : } else {
699 446 : state = state->KillMaps(object, zone());
700 : }
701 508 : switch (transition.mode()) {
702 : case ElementsTransition::kFastTransition:
703 : break;
704 : case ElementsTransition::kSlowTransition:
705 : // Kill the elements as well.
706 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
707 281 : zone());
708 281 : break;
709 : }
710 508 : return UpdateState(node, state);
711 : }
712 :
713 1427802 : Reduction LoadElimination::ReduceLoadField(Node* node) {
714 1427468 : FieldAccess const& access = FieldAccessOf(node->op());
715 1427468 : Node* const object = NodeProperties::GetValueInput(node, 0);
716 1427468 : Node* const effect = NodeProperties::GetEffectInput(node);
717 1427467 : Node* const control = NodeProperties::GetControlInput(node);
718 : AbstractState const* state = node_states_.Get(effect);
719 1427469 : if (state == nullptr) return NoChange();
720 1144900 : if (access.offset == HeapObject::kMapOffset &&
721 : access.base_is_tagged == kTaggedBase) {
722 : DCHECK(IsAnyTagged(access.machine_type.representation()));
723 : ZoneHandleSet<Map> object_maps;
724 15009 : if (state->LookupMaps(object, &object_maps) && object_maps.size() == 1) {
725 334 : Node* value = jsgraph()->HeapConstant(object_maps[0]);
726 : NodeProperties::SetType(value, Type::OtherInternal());
727 130686 : ReplaceWithValue(node, value, effect);
728 334 : return Replace(value);
729 : }
730 : } else {
731 1130747 : int field_index = FieldIndexOf(access);
732 1130748 : if (field_index >= 0) {
733 2148984 : if (Node* replacement = state->LookupField(object, field_index)) {
734 : // Make sure we don't resurrect dead {replacement} nodes.
735 130352 : if (!replacement->IsDead()) {
736 : // We might need to guard the {replacement} if the type of the
737 : // {node} is more precise than the type of the {replacement}.
738 : Type* const node_type = NodeProperties::GetType(node);
739 130352 : if (!NodeProperties::GetType(replacement)->Is(node_type)) {
740 : replacement = graph()->NewNode(common()->TypeGuard(node_type),
741 910 : replacement, control);
742 : NodeProperties::SetType(replacement, node_type);
743 : }
744 : ReplaceWithValue(node, replacement, effect);
745 : return Replace(replacement);
746 : }
747 : }
748 944140 : state = state->AddField(object, field_index, node, zone());
749 : }
750 : }
751 : Handle<Map> field_map;
752 1014214 : if (access.map.ToHandle(&field_map)) {
753 11232 : state = state->AddMaps(node, ZoneHandleSet<Map>(field_map), zone());
754 : }
755 1014215 : return UpdateState(node, state);
756 : }
757 :
758 1344908 : Reduction LoadElimination::ReduceStoreField(Node* node) {
759 1344908 : FieldAccess const& access = FieldAccessOf(node->op());
760 1344908 : Node* const object = NodeProperties::GetValueInput(node, 0);
761 1344908 : Node* const new_value = NodeProperties::GetValueInput(node, 1);
762 1344908 : Node* const effect = NodeProperties::GetEffectInput(node);
763 : AbstractState const* state = node_states_.Get(effect);
764 1344908 : if (state == nullptr) return NoChange();
765 1105138 : if (access.offset == HeapObject::kMapOffset &&
766 : access.base_is_tagged == kTaggedBase) {
767 : DCHECK(IsAnyTagged(access.machine_type.representation()));
768 : // Kill all potential knowledge about the {object}s map.
769 129988 : state = state->KillMaps(object, zone());
770 : Type* const new_value_type = NodeProperties::GetType(new_value);
771 129988 : if (new_value_type->IsHeapConstant()) {
772 : // Record the new {object} map information.
773 : ZoneHandleSet<Map> object_maps(
774 : Handle<Map>::cast(new_value_type->AsHeapConstant()->Value()));
775 129967 : state = state->AddMaps(object, object_maps, zone());
776 : }
777 : } else {
778 975150 : int field_index = FieldIndexOf(access);
779 975150 : if (field_index >= 0) {
780 883140 : Node* const old_value = state->LookupField(object, field_index);
781 883140 : if (old_value == new_value) {
782 : // This store is fully redundant.
783 : return Replace(effect);
784 : }
785 : // Kill all potentially aliasing fields and record the new value.
786 882832 : state = state->KillField(object, field_index, zone());
787 882832 : state = state->AddField(object, field_index, new_value, zone());
788 : } else {
789 : // Unsupported StoreField operator.
790 92010 : state = state->KillFields(object, zone());
791 : }
792 : }
793 1104829 : return UpdateState(node, state);
794 : }
795 :
796 91657 : Reduction LoadElimination::ReduceLoadElement(Node* node) {
797 56448 : Node* const object = NodeProperties::GetValueInput(node, 0);
798 56448 : Node* const index = NodeProperties::GetValueInput(node, 1);
799 56448 : Node* const effect = NodeProperties::GetEffectInput(node);
800 56448 : Node* const control = NodeProperties::GetControlInput(node);
801 : AbstractState const* state = node_states_.Get(effect);
802 56448 : if (state == nullptr) return NoChange();
803 :
804 : // Only handle loads that do not require truncations.
805 35209 : ElementAccess const& access = ElementAccessOf(node->op());
806 35209 : switch (access.machine_type.representation()) {
807 : case MachineRepresentation::kNone:
808 : case MachineRepresentation::kSimd1x4:
809 : case MachineRepresentation::kSimd1x8:
810 : case MachineRepresentation::kSimd1x16:
811 : case MachineRepresentation::kBit:
812 0 : UNREACHABLE();
813 : break;
814 : case MachineRepresentation::kWord8:
815 : case MachineRepresentation::kWord16:
816 : case MachineRepresentation::kWord32:
817 : case MachineRepresentation::kWord64:
818 : case MachineRepresentation::kFloat32:
819 : // TODO(turbofan): Add support for doing the truncations.
820 : break;
821 : case MachineRepresentation::kFloat64:
822 : case MachineRepresentation::kSimd128:
823 : case MachineRepresentation::kTaggedSigned:
824 : case MachineRepresentation::kTaggedPointer:
825 : case MachineRepresentation::kTagged:
826 34902 : if (Node* replacement = state->LookupElement(object, index)) {
827 : // Make sure we don't resurrect dead {replacement} nodes.
828 655 : if (!replacement->IsDead()) {
829 : // We might need to guard the {replacement} if the type of the
830 : // {node} is more precise than the type of the {replacement}.
831 : Type* const node_type = NodeProperties::GetType(node);
832 655 : if (!NodeProperties::GetType(replacement)->Is(node_type)) {
833 : replacement = graph()->NewNode(common()->TypeGuard(node_type),
834 8 : replacement, control);
835 : NodeProperties::SetType(replacement, node_type);
836 : }
837 655 : ReplaceWithValue(node, replacement, effect);
838 : return Replace(replacement);
839 : }
840 : }
841 34247 : state = state->AddElement(object, index, node, zone());
842 34247 : return UpdateState(node, state);
843 : }
844 : return NoChange();
845 : }
846 :
847 180680 : Reduction LoadElimination::ReduceStoreElement(Node* node) {
848 180680 : ElementAccess const& access = ElementAccessOf(node->op());
849 180680 : Node* const object = NodeProperties::GetValueInput(node, 0);
850 180680 : Node* const index = NodeProperties::GetValueInput(node, 1);
851 180680 : Node* const new_value = NodeProperties::GetValueInput(node, 2);
852 180680 : Node* const effect = NodeProperties::GetEffectInput(node);
853 : AbstractState const* state = node_states_.Get(effect);
854 180680 : if (state == nullptr) return NoChange();
855 : Node* const old_value = state->LookupElement(object, index);
856 166444 : if (old_value == new_value) {
857 : // This store is fully redundant.
858 : return Replace(effect);
859 : }
860 : // Kill all potentially aliasing elements.
861 166422 : state = state->KillElement(object, index, zone());
862 : // Only record the new value if the store doesn't have an implicit truncation.
863 166422 : switch (access.machine_type.representation()) {
864 : case MachineRepresentation::kNone:
865 : case MachineRepresentation::kSimd1x4:
866 : case MachineRepresentation::kSimd1x8:
867 : case MachineRepresentation::kSimd1x16:
868 : case MachineRepresentation::kBit:
869 0 : UNREACHABLE();
870 : break;
871 : case MachineRepresentation::kWord8:
872 : case MachineRepresentation::kWord16:
873 : case MachineRepresentation::kWord32:
874 : case MachineRepresentation::kWord64:
875 : case MachineRepresentation::kFloat32:
876 : // TODO(turbofan): Add support for doing the truncations.
877 : break;
878 : case MachineRepresentation::kFloat64:
879 : case MachineRepresentation::kSimd128:
880 : case MachineRepresentation::kTaggedSigned:
881 : case MachineRepresentation::kTaggedPointer:
882 : case MachineRepresentation::kTagged:
883 166172 : state = state->AddElement(object, index, new_value, zone());
884 166172 : break;
885 : }
886 166422 : return UpdateState(node, state);
887 : }
888 :
889 4921 : Reduction LoadElimination::ReduceStoreTypedElement(Node* node) {
890 4921 : Node* const effect = NodeProperties::GetEffectInput(node);
891 : AbstractState const* state = node_states_.Get(effect);
892 4921 : if (state == nullptr) return NoChange();
893 3673 : return UpdateState(node, state);
894 : }
895 :
896 1614726 : Reduction LoadElimination::ReduceEffectPhi(Node* node) {
897 956620 : Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
898 1710676 : Node* const control = NodeProperties::GetControlInput(node);
899 : AbstractState const* state0 = node_states_.Get(effect0);
900 956619 : if (state0 == nullptr) return NoChange();
901 754056 : if (control->opcode() == IrOpcode::kLoop) {
902 : // Here we rely on having only reducible loops:
903 : // The loop entry edge always dominates the header, so we can just take
904 : // the state from the first input, and compute the loop state based on it.
905 95950 : AbstractState const* state = ComputeLoopState(node, state0);
906 95950 : return UpdateState(node, state);
907 : }
908 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
909 :
910 : // Shortcut for the case when we do not know anything about some input.
911 658106 : int const input_count = node->op()->EffectInputCount();
912 3673974 : for (int i = 1; i < input_count; ++i) {
913 3148171 : Node* const effect = NodeProperties::GetEffectInput(node, i);
914 3148171 : if (node_states_.Get(effect) == nullptr) return NoChange();
915 : }
916 :
917 : // Make a copy of the first input's state and merge with the state
918 : // from other inputs.
919 525805 : AbstractState* state = new (zone()) AbstractState(*state0);
920 1811793 : for (int i = 1; i < input_count; ++i) {
921 1285988 : Node* const input = NodeProperties::GetEffectInput(node, i);
922 1285988 : state->Merge(node_states_.Get(input), zone());
923 : }
924 525805 : return UpdateState(node, state);
925 : }
926 :
927 0 : Reduction LoadElimination::ReduceStart(Node* node) {
928 393189 : return UpdateState(node, empty_state());
929 : }
930 :
931 37515535 : Reduction LoadElimination::ReduceOtherNode(Node* node) {
932 30955956 : if (node->op()->EffectInputCount() == 1) {
933 8851681 : if (node->op()->EffectOutputCount() == 1) {
934 8151283 : Node* const effect = NodeProperties::GetEffectInput(node);
935 : AbstractState const* state = node_states_.Get(effect);
936 : // If we do not know anything about the predecessor, do not propagate
937 : // just yet because we will have to recompute anyway once we compute
938 : // the predecessor.
939 8151294 : if (state == nullptr) return NoChange();
940 : // Check if this {node} has some uncontrolled side effects.
941 6559579 : if (!node->op()->HasProperty(Operator::kNoWrite)) {
942 2312573 : state = empty_state();
943 : }
944 6559579 : return UpdateState(node, state);
945 : } else {
946 : // Effect terminators should be handled specially.
947 : return NoChange();
948 : }
949 : }
950 : DCHECK_EQ(0, node->op()->EffectInputCount());
951 : DCHECK_EQ(0, node->op()->EffectOutputCount());
952 : return NoChange();
953 : }
954 :
955 9954217 : Reduction LoadElimination::UpdateState(Node* node, AbstractState const* state) {
956 : AbstractState const* original = node_states_.Get(node);
957 : // Only signal that the {node} has Changed, if the information about {state}
958 : // has changed wrt. the {original}.
959 9954217 : if (state != original) {
960 9436065 : if (original == nullptr || !state->Equals(original)) {
961 9231189 : node_states_.Set(node, state);
962 : return Changed(node);
963 : }
964 : }
965 : return NoChange();
966 : }
967 :
968 95950 : LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
969 : Node* node, AbstractState const* state) const {
970 95950 : Node* const control = NodeProperties::GetControlInput(node);
971 95950 : ZoneQueue<Node*> queue(zone());
972 : ZoneSet<Node*> visited(zone());
973 : visited.insert(node);
974 383800 : for (int i = 1; i < control->InputCount(); ++i) {
975 287850 : queue.push(node->InputAt(i));
976 : }
977 804109 : while (!queue.empty()) {
978 783663 : Node* const current = queue.front();
979 : queue.pop();
980 783639 : if (visited.find(current) == visited.end()) {
981 : visited.insert(current);
982 2850268 : if (!current->op()->HasProperty(Operator::kNoWrite)) {
983 112055 : switch (current->opcode()) {
984 : case IrOpcode::kEnsureWritableFastElements: {
985 33 : Node* const object = NodeProperties::GetValueInput(current, 0);
986 : state = state->KillField(
987 33 : object, FieldIndexOf(JSObject::kElementsOffset), zone());
988 33 : break;
989 : }
990 : case IrOpcode::kMaybeGrowFastElements: {
991 : GrowFastElementsFlags flags =
992 1234 : GrowFastElementsFlagsOf(current->op());
993 1234 : Node* const object = NodeProperties::GetValueInput(current, 0);
994 : state = state->KillField(
995 1234 : object, FieldIndexOf(JSObject::kElementsOffset), zone());
996 1234 : if (flags & GrowFastElementsFlag::kArrayObject) {
997 : state = state->KillField(
998 1234 : object, FieldIndexOf(JSArray::kLengthOffset), zone());
999 : }
1000 : break;
1001 : }
1002 : case IrOpcode::kTransitionElementsKind: {
1003 157 : ElementsTransition transition = ElementsTransitionOf(current->op());
1004 157 : Node* const object = NodeProperties::GetValueInput(current, 0);
1005 : ZoneHandleSet<Map> object_maps;
1006 471 : if (!state->LookupMaps(object, &object_maps) ||
1007 : !ZoneHandleSet<Map>(transition.target())
1008 247 : .contains(object_maps)) {
1009 112 : state = state->KillMaps(object, zone());
1010 112 : switch (transition.mode()) {
1011 : case ElementsTransition::kFastTransition:
1012 : break;
1013 : case ElementsTransition::kSlowTransition:
1014 : // Kill the elements as well.
1015 : state = state->KillField(
1016 53 : object, FieldIndexOf(JSObject::kElementsOffset), zone());
1017 53 : break;
1018 : }
1019 : }
1020 : break;
1021 : }
1022 : case IrOpcode::kStoreField: {
1023 28291 : FieldAccess const& access = FieldAccessOf(current->op());
1024 28291 : Node* const object = NodeProperties::GetValueInput(current, 0);
1025 28291 : if (access.offset == HeapObject::kMapOffset) {
1026 : // Invalidate what we know about the {object}s map.
1027 5200 : state = state->KillMaps(object, zone());
1028 : } else {
1029 23091 : int field_index = FieldIndexOf(access);
1030 23091 : if (field_index < 0) {
1031 11 : state = state->KillFields(object, zone());
1032 : } else {
1033 23080 : state = state->KillField(object, field_index, zone());
1034 : }
1035 : }
1036 : break;
1037 : }
1038 : case IrOpcode::kStoreElement: {
1039 5073 : Node* const object = NodeProperties::GetValueInput(current, 0);
1040 5073 : Node* const index = NodeProperties::GetValueInput(current, 1);
1041 5073 : state = state->KillElement(object, index, zone());
1042 5073 : break;
1043 : }
1044 : case IrOpcode::kStoreBuffer:
1045 : case IrOpcode::kStoreTypedElement: {
1046 : // Doesn't affect anything we track with the state currently.
1047 : break;
1048 : }
1049 : default:
1050 75495 : return empty_state();
1051 : }
1052 : }
1053 4197450 : for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
1054 1498202 : queue.push(NodeProperties::GetEffectInput(current, i));
1055 : }
1056 : }
1057 : }
1058 : return state;
1059 : }
1060 :
1061 : // static
1062 0 : int LoadElimination::FieldIndexOf(int offset) {
1063 : DCHECK_EQ(0, offset % kPointerSize);
1064 2024927 : int field_index = offset / kPointerSize;
1065 2024927 : if (field_index >= static_cast<int>(kMaxTrackedFields)) return -1;
1066 : DCHECK_LT(0, field_index);
1067 1980711 : return field_index - 1;
1068 : }
1069 :
1070 : // static
1071 2128988 : int LoadElimination::FieldIndexOf(FieldAccess const& access) {
1072 2128988 : MachineRepresentation rep = access.machine_type.representation();
1073 : switch (rep) {
1074 : case MachineRepresentation::kNone:
1075 : case MachineRepresentation::kBit:
1076 : case MachineRepresentation::kSimd128:
1077 : case MachineRepresentation::kSimd1x4:
1078 : case MachineRepresentation::kSimd1x8:
1079 : case MachineRepresentation::kSimd1x16:
1080 0 : UNREACHABLE();
1081 : break;
1082 : case MachineRepresentation::kWord32:
1083 : case MachineRepresentation::kWord64:
1084 8600 : if (rep != MachineType::PointerRepresentation()) {
1085 : return -1; // We currently only track pointer size fields.
1086 : }
1087 : break;
1088 : case MachineRepresentation::kWord8:
1089 : case MachineRepresentation::kWord16:
1090 : case MachineRepresentation::kFloat32:
1091 : return -1; // Currently untracked.
1092 : case MachineRepresentation::kFloat64:
1093 : if (kDoubleSize != kPointerSize) {
1094 : return -1; // We currently only track pointer size fields.
1095 : }
1096 : // Fall through.
1097 : case MachineRepresentation::kTaggedSigned:
1098 : case MachineRepresentation::kTaggedPointer:
1099 : case MachineRepresentation::kTagged:
1100 : // TODO(bmeurer): Check that we never do overlapping load/stores of
1101 : // individual parts of Float64 values.
1102 : break;
1103 : }
1104 2121403 : if (access.base_is_tagged != kTaggedBase) {
1105 : return -1; // We currently only track tagged objects.
1106 : }
1107 4049854 : return FieldIndexOf(access.offset);
1108 : }
1109 :
1110 918 : CommonOperatorBuilder* LoadElimination::common() const {
1111 918 : return jsgraph()->common();
1112 : }
1113 :
1114 918 : Graph* LoadElimination::graph() const { return jsgraph()->graph(); }
1115 :
1116 2405 : Factory* LoadElimination::factory() const { return jsgraph()->factory(); }
1117 :
1118 : } // namespace compiler
1119 : } // namespace internal
1120 : } // namespace v8
|
