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 2981097 : bool IsRename(Node* node) {
21 2981097 : switch (node->opcode()) {
22 : case IrOpcode::kFinishRegion:
23 : case IrOpcode::kTypeGuard:
24 : return true;
25 : default:
26 : return false;
27 : }
28 : }
29 :
30 2645624 : Node* ResolveRenames(Node* node) {
31 5626721 : while (IsRename(node)) {
32 : node = node->InputAt(0);
33 : }
34 2645624 : return node;
35 : }
36 :
37 3230111 : bool MayAlias(Node* a, Node* b) {
38 1870806 : if (a == b) return true;
39 1119513 : if (!NodeProperties::GetType(a)->Maybe(NodeProperties::GetType(b))) {
40 : return false;
41 : }
42 698724 : switch (b->opcode()) {
43 : case IrOpcode::kAllocate: {
44 563475 : switch (a->opcode()) {
45 : case IrOpcode::kAllocate:
46 : case IrOpcode::kHeapConstant:
47 : case IrOpcode::kParameter:
48 : return false;
49 : default:
50 : break;
51 : }
52 : break;
53 : }
54 : case IrOpcode::kFinishRegion:
55 : case IrOpcode::kTypeGuard:
56 54606 : return MayAlias(a, b->InputAt(0));
57 : default:
58 : break;
59 : }
60 402074 : switch (a->opcode()) {
61 : case IrOpcode::kAllocate: {
62 19305 : switch (b->opcode()) {
63 : case IrOpcode::kHeapConstant:
64 : case IrOpcode::kParameter:
65 : return false;
66 : default:
67 : break;
68 : }
69 : break;
70 : }
71 : case IrOpcode::kFinishRegion:
72 : case IrOpcode::kTypeGuard:
73 250362 : return MayAlias(a->InputAt(0), b);
74 : default:
75 : break;
76 : }
77 147855 : return true;
78 : }
79 :
80 : bool MustAlias(Node* a, Node* b) {
81 1158553 : return ResolveRenames(a) == ResolveRenames(b);
82 : }
83 :
84 : } // namespace
85 :
86 67845804 : Reduction LoadElimination::Reduce(Node* node) {
87 33922902 : if (FLAG_trace_turbo_load_elimination) {
88 0 : if (node->op()->EffectInputCount() > 0) {
89 0 : PrintF(" visit #%d:%s", node->id(), node->op()->mnemonic());
90 0 : if (node->op()->ValueInputCount() > 0) {
91 0 : PrintF("(");
92 0 : for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
93 0 : if (i > 0) PrintF(", ");
94 0 : Node* const value = NodeProperties::GetValueInput(node, i);
95 0 : PrintF("#%d:%s", value->id(), value->op()->mnemonic());
96 : }
97 0 : PrintF(")");
98 : }
99 0 : PrintF("\n");
100 0 : for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
101 0 : Node* const effect = NodeProperties::GetEffectInput(node, i);
102 0 : if (AbstractState const* const state = node_states_.Get(effect)) {
103 : PrintF(" state[%i]: #%d:%s\n", i, effect->id(),
104 0 : effect->op()->mnemonic());
105 0 : state->Print();
106 : } else {
107 : PrintF(" no state[%i]: #%d:%s\n", i, effect->id(),
108 0 : effect->op()->mnemonic());
109 : }
110 : }
111 : }
112 : }
113 33922902 : switch (node->opcode()) {
114 : case IrOpcode::kArrayBufferWasNeutered:
115 764 : return ReduceArrayBufferWasNeutered(node);
116 : case IrOpcode::kMapGuard:
117 11602 : return ReduceMapGuard(node);
118 : case IrOpcode::kCheckMaps:
119 134322 : return ReduceCheckMaps(node);
120 : case IrOpcode::kCompareMaps:
121 12023 : return ReduceCompareMaps(node);
122 : case IrOpcode::kEnsureWritableFastElements:
123 400 : return ReduceEnsureWritableFastElements(node);
124 : case IrOpcode::kMaybeGrowFastElements:
125 4577 : return ReduceMaybeGrowFastElements(node);
126 : case IrOpcode::kTransitionElementsKind:
127 1040 : return ReduceTransitionElementsKind(node);
128 : case IrOpcode::kLoadField:
129 1497648 : return ReduceLoadField(node);
130 : case IrOpcode::kStoreField:
131 1603479 : return ReduceStoreField(node);
132 : case IrOpcode::kLoadElement:
133 35627 : return ReduceLoadElement(node);
134 : case IrOpcode::kStoreElement:
135 54204 : return ReduceStoreElement(node);
136 : case IrOpcode::kTransitionAndStoreElement:
137 474 : return ReduceTransitionAndStoreElement(node);
138 : case IrOpcode::kStoreTypedElement:
139 9792 : return ReduceStoreTypedElement(node);
140 : case IrOpcode::kEffectPhi:
141 658631 : return ReduceEffectPhi(node);
142 : case IrOpcode::kDead:
143 : break;
144 : case IrOpcode::kStart:
145 : return ReduceStart(node);
146 : default:
147 29448453 : return ReduceOtherNode(node);
148 : }
149 : return NoChange();
150 : }
151 :
152 : namespace {
153 :
154 123 : bool LoadEliminationIsCompatibleCheck(Node const* a, Node const* b) {
155 123 : if (a->op() != b->op()) return false;
156 421 : for (int i = a->op()->ValueInputCount(); --i >= 0;) {
157 123 : if (!MustAlias(a->InputAt(i), b->InputAt(i))) return false;
158 : }
159 : return true;
160 : }
161 :
162 : } // namespace
163 :
164 248 : Node* LoadElimination::AbstractChecks::Lookup(Node* node) const {
165 1816 : for (Node* const check : nodes_) {
166 1866 : if (check && !check->IsDead() &&
167 123 : LoadEliminationIsCompatibleCheck(check, node)) {
168 : return check;
169 : }
170 : }
171 : return nullptr;
172 : }
173 :
174 549 : bool LoadElimination::AbstractChecks::Equals(AbstractChecks const* that) const {
175 549 : if (this == that) return true;
176 1352 : for (size_t i = 0; i < arraysize(nodes_); ++i) {
177 1534 : if (Node* this_node = this->nodes_[i]) {
178 1456 : for (size_t j = 0;; ++j) {
179 1791 : if (j == arraysize(nodes_)) return false;
180 1609 : if (that->nodes_[j] == this_node) break;
181 1456 : }
182 : }
183 : }
184 855 : for (size_t i = 0; i < arraysize(nodes_); ++i) {
185 926 : if (Node* that_node = that->nodes_[i]) {
186 568 : for (size_t j = 0;; ++j) {
187 792 : if (j == arraysize(nodes_)) return false;
188 721 : if (this->nodes_[j] == that_node) break;
189 568 : }
190 : }
191 : }
192 : return true;
193 : }
194 :
195 431 : LoadElimination::AbstractChecks const* LoadElimination::AbstractChecks::Merge(
196 : AbstractChecks const* that, Zone* zone) const {
197 431 : if (this->Equals(that)) return this;
198 : AbstractChecks* copy = new (zone) AbstractChecks(zone);
199 2277 : for (Node* const this_node : this->nodes_) {
200 2024 : if (this_node == nullptr) continue;
201 1709 : for (Node* const that_node : that->nodes_) {
202 1527 : if (this_node == that_node) {
203 71 : copy->nodes_[copy->next_index_++] = this_node;
204 71 : break;
205 : }
206 : }
207 : }
208 253 : copy->next_index_ %= arraysize(nodes_);
209 253 : return copy;
210 : }
211 :
212 0 : void LoadElimination::AbstractChecks::Print() const {
213 0 : for (Node* const node : nodes_) {
214 0 : if (node != nullptr) {
215 0 : PrintF(" #%d:%s\n", node->id(), node->op()->mnemonic());
216 : }
217 : }
218 0 : }
219 :
220 : namespace {
221 :
222 1861 : bool IsCompatible(MachineRepresentation r1, MachineRepresentation r2) {
223 1861 : if (r1 == r2) return true;
224 286 : return IsAnyTagged(r1) && IsAnyTagged(r2);
225 : }
226 :
227 : } // namespace
228 :
229 42413 : Node* LoadElimination::AbstractElements::Lookup(
230 : Node* object, Node* index, MachineRepresentation representation) const {
231 369186 : for (Element const element : elements_) {
232 328634 : if (element.object == nullptr) continue;
233 : DCHECK_NOT_NULL(element.index);
234 : DCHECK_NOT_NULL(element.value);
235 350106 : if (MustAlias(object, element.object) && MustAlias(index, element.index) &&
236 1861 : IsCompatible(representation, element.representation)) {
237 : return element.value;
238 : }
239 : }
240 : return nullptr;
241 : }
242 :
243 : LoadElimination::AbstractElements const*
244 39371 : LoadElimination::AbstractElements::Kill(Node* object, Node* index,
245 : Zone* zone) const {
246 69997 : for (Element const element : this->elements_) {
247 66333 : if (element.object == nullptr) continue;
248 38200 : if (MayAlias(object, element.object)) {
249 35707 : AbstractElements* that = new (zone) AbstractElements(zone);
250 321363 : for (Element const element : this->elements_) {
251 285656 : if (element.object == nullptr) continue;
252 : DCHECK_NOT_NULL(element.index);
253 : DCHECK_NOT_NULL(element.value);
254 331934 : if (!MayAlias(object, element.object) ||
255 : !NodeProperties::GetType(index)->Maybe(
256 164981 : NodeProperties::GetType(element.index))) {
257 158098 : that->elements_[that->next_index_++] = element;
258 : }
259 : }
260 35707 : that->next_index_ %= arraysize(elements_);
261 : return that;
262 : }
263 : }
264 3664 : return this;
265 : }
266 :
267 7005 : bool LoadElimination::AbstractElements::Equals(
268 : AbstractElements const* that) const {
269 7005 : if (this == that) return true;
270 14180 : for (size_t i = 0; i < arraysize(elements_); ++i) {
271 16064 : Element this_element = this->elements_[i];
272 16064 : if (this_element.object == nullptr) continue;
273 16015 : for (size_t j = 0;; ++j) {
274 19196 : if (j == arraysize(elements_)) return false;
275 17312 : Element that_element = that->elements_[j];
276 17312 : if (this_element.object == that_element.object &&
277 1674 : this_element.index == that_element.index &&
278 : this_element.value == that_element.value) {
279 : break;
280 : }
281 16015 : }
282 : }
283 9788 : for (size_t i = 0; i < arraysize(elements_); ++i) {
284 10321 : Element that_element = that->elements_[i];
285 10321 : if (that_element.object == nullptr) continue;
286 4580 : for (size_t j = 0;; ++j) {
287 5790 : if (j == arraysize(elements_)) return false;
288 5257 : Element this_element = this->elements_[j];
289 5257 : if (that_element.object == this_element.object &&
290 677 : that_element.index == this_element.index &&
291 : that_element.value == this_element.value) {
292 : break;
293 : }
294 4580 : }
295 : }
296 : return true;
297 : }
298 :
299 : LoadElimination::AbstractElements const*
300 4438 : LoadElimination::AbstractElements::Merge(AbstractElements const* that,
301 : Zone* zone) const {
302 4438 : if (this->Equals(that)) return this;
303 1940 : AbstractElements* copy = new (zone) AbstractElements(zone);
304 17460 : for (Element const this_element : this->elements_) {
305 15520 : if (this_element.object == nullptr) continue;
306 19766 : for (Element const that_element : that->elements_) {
307 17683 : if (this_element.object == that_element.object &&
308 860 : this_element.index == that_element.index &&
309 : this_element.value == that_element.value) {
310 483 : copy->elements_[copy->next_index_++] = this_element;
311 483 : break;
312 : }
313 : }
314 : }
315 1940 : copy->next_index_ %= arraysize(elements_);
316 1940 : return copy;
317 : }
318 :
319 0 : void LoadElimination::AbstractElements::Print() const {
320 0 : for (Element const& element : elements_) {
321 0 : if (element.object) {
322 : PrintF(" #%d:%s @ #%d:%s -> #%d:%s\n", element.object->id(),
323 : element.object->op()->mnemonic(), element.index->id(),
324 : element.index->op()->mnemonic(), element.value->id(),
325 0 : element.value->op()->mnemonic());
326 : }
327 : }
328 0 : }
329 :
330 605019 : Node* LoadElimination::AbstractField::Lookup(Node* object) const {
331 1697232 : for (auto pair : info_for_node_) {
332 810185 : if (MustAlias(object, pair.first)) return pair.second.value;
333 : }
334 : return nullptr;
335 : }
336 :
337 : namespace {
338 :
339 : bool MayAlias(MaybeHandle<Name> x, MaybeHandle<Name> y) {
340 327807 : if (!x.address()) return true;
341 98170 : if (!y.address()) return true;
342 90484 : if (x.address() != y.address()) return false;
343 : return true;
344 : }
345 :
346 : } // namespace
347 :
348 : class LoadElimination::AliasStateInfo {
349 : public:
350 : AliasStateInfo(const AbstractState* state, Node* object, Handle<Map> map)
351 1161 : : state_(state), object_(object), map_(map) {}
352 : AliasStateInfo(const AbstractState* state, Node* object)
353 1363577 : : state_(state), object_(object) {}
354 :
355 : bool MayAlias(Node* other) const;
356 :
357 : private:
358 : const AbstractState* state_;
359 : Node* object_;
360 : MaybeHandle<Map> map_;
361 : };
362 :
363 1888837 : LoadElimination::AbstractField const* LoadElimination::AbstractField::Kill(
364 : const AliasStateInfo& alias_info, MaybeHandle<Name> name,
365 : Zone* zone) const {
366 4171666 : for (auto pair : this->info_for_node_) {
367 712842 : if (alias_info.MayAlias(pair.first)) {
368 : AbstractField* that = new (zone) AbstractField(zone);
369 1130821 : for (auto pair : this->info_for_node_) {
370 820928 : if (!alias_info.MayAlias(pair.first) ||
371 : !MayAlias(name, pair.second.name)) {
372 : that->info_for_node_.insert(pair);
373 : }
374 : }
375 : return that;
376 : }
377 : }
378 : return this;
379 : }
380 :
381 0 : void LoadElimination::AbstractField::Print() const {
382 0 : for (auto pair : info_for_node_) {
383 : PrintF(" #%d:%s -> #%d:%s\n", pair.first->id(),
384 : pair.first->op()->mnemonic(), pair.second.value->id(),
385 0 : pair.second.value->op()->mnemonic());
386 : }
387 0 : }
388 :
389 0 : LoadElimination::AbstractMaps::AbstractMaps(Zone* zone)
390 0 : : info_for_node_(zone) {}
391 :
392 121241 : LoadElimination::AbstractMaps::AbstractMaps(Node* object,
393 : ZoneHandleSet<Map> maps, Zone* zone)
394 : : info_for_node_(zone) {
395 121241 : object = ResolveRenames(object);
396 242482 : info_for_node_.insert(std::make_pair(object, maps));
397 121241 : }
398 :
399 102186 : bool LoadElimination::AbstractMaps::Lookup(
400 : Node* object, ZoneHandleSet<Map>* object_maps) const {
401 204372 : auto it = info_for_node_.find(ResolveRenames(object));
402 102186 : if (it == info_for_node_.end()) return false;
403 44591 : *object_maps = it->second;
404 44591 : return true;
405 : }
406 :
407 77986 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Kill(
408 : const AliasStateInfo& alias_info, Zone* zone) const {
409 244349 : for (auto pair : this->info_for_node_) {
410 113048 : if (alias_info.MayAlias(pair.first)) {
411 : AbstractMaps* that = new (zone) AbstractMaps(zone);
412 91016 : for (auto pair : this->info_for_node_) {
413 41674 : if (!alias_info.MayAlias(pair.first)) that->info_for_node_.insert(pair);
414 : }
415 : return that;
416 : }
417 : }
418 : return this;
419 : }
420 :
421 34401 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Merge(
422 : AbstractMaps const* that, Zone* zone) const {
423 34401 : if (this->Equals(that)) return this;
424 : AbstractMaps* copy = new (zone) AbstractMaps(zone);
425 43578 : for (auto this_it : this->info_for_node_) {
426 19908 : Node* this_object = this_it.first;
427 19908 : ZoneHandleSet<Map> this_maps = this_it.second;
428 : auto that_it = that->info_for_node_.find(this_object);
429 19908 : if (that_it != that->info_for_node_.end() && that_it->second == this_maps) {
430 : copy->info_for_node_.insert(this_it);
431 : }
432 : }
433 11835 : return copy;
434 : }
435 :
436 105094 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Extend(
437 : Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
438 : AbstractMaps* that = new (zone) AbstractMaps(zone);
439 : that->info_for_node_ = this->info_for_node_;
440 105094 : object = ResolveRenames(object);
441 105094 : that->info_for_node_[object] = maps;
442 105094 : return that;
443 : }
444 :
445 0 : void LoadElimination::AbstractMaps::Print() const {
446 0 : for (auto pair : info_for_node_) {
447 0 : PrintF(" #%d:%s\n", pair.first->id(), pair.first->op()->mnemonic());
448 0 : OFStream os(stdout);
449 : ZoneHandleSet<Map> const& maps = pair.second;
450 0 : for (size_t i = 0; i < maps.size(); ++i) {
451 0 : os << " - " << Brief(*maps[i]) << "\n";
452 : }
453 0 : }
454 0 : }
455 :
456 78410 : bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
457 78410 : if (this->checks_) {
458 118 : if (!that->checks_ || !that->checks_->Equals(this->checks_)) {
459 : return false;
460 : }
461 78292 : } else if (that->checks_) {
462 : return false;
463 : }
464 78410 : if (this->elements_) {
465 2567 : if (!that->elements_ || !that->elements_->Equals(this->elements_)) {
466 : return false;
467 : }
468 75843 : } else if (that->elements_) {
469 : return false;
470 : }
471 2419315 : for (size_t i = 0u; i < arraysize(fields_); ++i) {
472 2422062 : AbstractField const* this_field = this->fields_[i];
473 2422062 : AbstractField const* that_field = that->fields_[i];
474 2422062 : if (this_field) {
475 408762 : if (!that_field || !that_field->Equals(this_field)) return false;
476 2217681 : } else if (that_field) {
477 : return false;
478 : }
479 : }
480 75186 : if (this->maps_) {
481 85286 : if (!that->maps_ || !that->maps_->Equals(this->maps_)) {
482 : return false;
483 : }
484 32543 : } else if (that->maps_) {
485 : return false;
486 : }
487 : return true;
488 : }
489 :
490 497535 : void LoadElimination::AbstractState::Merge(AbstractState const* that,
491 : Zone* zone) {
492 : // Merge the information we have about the checks.
493 497535 : if (this->checks_) {
494 : this->checks_ =
495 463 : that->checks_ ? that->checks_->Merge(this->checks_, zone) : nullptr;
496 : }
497 :
498 : // Merge the information we have about the elements.
499 497535 : if (this->elements_) {
500 : this->elements_ = that->elements_
501 : ? that->elements_->Merge(this->elements_, zone)
502 8519 : : nullptr;
503 : }
504 :
505 : // Merge the information we have about the fields.
506 15921411 : for (size_t i = 0; i < arraysize(fields_); ++i) {
507 15921400 : if (this->fields_[i]) {
508 374967 : if (that->fields_[i]) {
509 169397 : this->fields_[i] = this->fields_[i]->Merge(that->fields_[i], zone);
510 : } else {
511 205570 : this->fields_[i] = nullptr;
512 : }
513 : }
514 : }
515 :
516 : // Merge the information we have about the maps.
517 497546 : if (this->maps_) {
518 53064 : this->maps_ = that->maps_ ? that->maps_->Merge(this->maps_, zone) : nullptr;
519 : }
520 497546 : }
521 :
522 0 : Node* LoadElimination::AbstractState::LookupCheck(Node* node) const {
523 621 : return this->checks_ ? this->checks_->Lookup(node) : nullptr;
524 : }
525 :
526 569 : LoadElimination::AbstractState const* LoadElimination::AbstractState::AddCheck(
527 : Node* node, Zone* zone) const {
528 569 : AbstractState* that = new (zone) AbstractState(*this);
529 569 : if (that->checks_) {
530 196 : that->checks_ = that->checks_->Extend(node, zone);
531 : } else {
532 373 : that->checks_ = new (zone) AbstractChecks(node, zone);
533 : }
534 569 : return that;
535 : }
536 :
537 0 : bool LoadElimination::AbstractState::LookupMaps(
538 : Node* object, ZoneHandleSet<Map>* object_map) const {
539 392364 : return this->maps_ && this->maps_->Lookup(object, object_map);
540 : }
541 :
542 226335 : LoadElimination::AbstractState const* LoadElimination::AbstractState::SetMaps(
543 : Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
544 226335 : AbstractState* that = new (zone) AbstractState(*this);
545 226335 : if (that->maps_) {
546 105094 : that->maps_ = that->maps_->Extend(object, maps, zone);
547 : } else {
548 242482 : that->maps_ = new (zone) AbstractMaps(object, maps, zone);
549 : }
550 226335 : return that;
551 : }
552 :
553 156379 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
554 : const AliasStateInfo& alias_info, Zone* zone) const {
555 156379 : if (this->maps_) {
556 77986 : AbstractMaps const* that_maps = this->maps_->Kill(alias_info, zone);
557 77986 : if (this->maps_ != that_maps) {
558 24671 : AbstractState* that = new (zone) AbstractState(*this);
559 24671 : that->maps_ = that_maps;
560 24671 : return that;
561 : }
562 : }
563 131708 : return this;
564 : }
565 :
566 0 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
567 : Node* object, Zone* zone) const {
568 : AliasStateInfo alias_info(this, object);
569 155762 : return KillMaps(alias_info, zone);
570 : }
571 :
572 0 : Node* LoadElimination::AbstractState::LookupElement(
573 : Node* object, Node* index, MachineRepresentation representation) const {
574 63011 : if (this->elements_) {
575 42413 : return this->elements_->Lookup(object, index, representation);
576 : }
577 : return nullptr;
578 : }
579 :
580 : LoadElimination::AbstractState const*
581 61617 : LoadElimination::AbstractState::AddElement(Node* object, Node* index,
582 : Node* value,
583 : MachineRepresentation representation,
584 : Zone* zone) const {
585 61617 : AbstractState* that = new (zone) AbstractState(*this);
586 61617 : if (that->elements_) {
587 : that->elements_ =
588 41019 : that->elements_->Extend(object, index, value, representation, zone);
589 : } else {
590 : that->elements_ =
591 20598 : new (zone) AbstractElements(object, index, value, representation, zone);
592 : }
593 61617 : return that;
594 : }
595 :
596 : LoadElimination::AbstractState const*
597 48280 : LoadElimination::AbstractState::KillElement(Node* object, Node* index,
598 : Zone* zone) const {
599 48280 : if (this->elements_) {
600 : AbstractElements const* that_elements =
601 39371 : this->elements_->Kill(object, index, zone);
602 39371 : if (this->elements_ != that_elements) {
603 35707 : AbstractState* that = new (zone) AbstractState(*this);
604 35707 : that->elements_ = that_elements;
605 35707 : return that;
606 : }
607 : }
608 12573 : return this;
609 : }
610 :
611 2010055 : LoadElimination::AbstractState const* LoadElimination::AbstractState::AddField(
612 : Node* object, size_t index, Node* value, MaybeHandle<Name> name,
613 : Zone* zone) const {
614 2010054 : AbstractState* that = new (zone) AbstractState(*this);
615 2010054 : if (that->fields_[index]) {
616 : that->fields_[index] =
617 453273 : that->fields_[index]->Extend(object, value, name, zone);
618 : } else {
619 3113562 : that->fields_[index] = new (zone) AbstractField(object, value, name, zone);
620 : }
621 2010055 : return that;
622 : }
623 :
624 0 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
625 : Node* object, size_t index, MaybeHandle<Name> name, Zone* zone) const {
626 : AliasStateInfo alias_info(this, object);
627 1077131 : return KillField(alias_info, index, name, zone);
628 : }
629 :
630 1077675 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
631 : const AliasStateInfo& alias_info, size_t index, MaybeHandle<Name> name,
632 : Zone* zone) const {
633 1077675 : if (AbstractField const* this_field = this->fields_[index]) {
634 389590 : this_field = this_field->Kill(alias_info, name, zone);
635 389590 : if (this->fields_[index] != this_field) {
636 206740 : AbstractState* that = new (zone) AbstractState(*this);
637 206740 : that->fields_[index] = this_field;
638 206740 : return that;
639 : }
640 : }
641 870935 : return this;
642 : }
643 :
644 : LoadElimination::AbstractState const*
645 130684 : LoadElimination::AbstractState::KillFields(Node* object, MaybeHandle<Name> name,
646 : Zone* zone) const {
647 : AliasStateInfo alias_info(this, object);
648 3522467 : for (size_t i = 0;; ++i) {
649 3653151 : if (i == arraysize(fields_)) return this;
650 3543724 : if (AbstractField const* this_field = this->fields_[i]) {
651 : AbstractField const* that_field =
652 1344621 : this_field->Kill(alias_info, name, zone);
653 1344621 : if (that_field != this_field) {
654 21257 : AbstractState* that = new (zone) AbstractState(*this);
655 21257 : that->fields_[i] = that_field;
656 680678 : while (++i < arraysize(fields_)) {
657 638164 : if (this->fields_[i] != nullptr) {
658 154626 : that->fields_[i] = this->fields_[i]->Kill(alias_info, name, zone);
659 : }
660 : }
661 : return that;
662 : }
663 : }
664 3522467 : }
665 : }
666 :
667 0 : Node* LoadElimination::AbstractState::LookupField(Node* object,
668 : size_t index) const {
669 2161801 : if (AbstractField const* this_field = this->fields_[index]) {
670 605019 : return this_field->Lookup(object);
671 : }
672 : return nullptr;
673 : }
674 :
675 1360685 : bool LoadElimination::AliasStateInfo::MayAlias(Node* other) const {
676 : // Decide aliasing based on the node kinds.
677 1360685 : if (!compiler::MayAlias(object_, other)) {
678 : return false;
679 : }
680 : // Decide aliasing based on maps (if available).
681 : Handle<Map> map;
682 698460 : if (map_.ToHandle(&map)) {
683 : ZoneHandleSet<Map> other_maps;
684 2579 : if (state_->LookupMaps(other, &other_maps) && other_maps.size() == 1) {
685 853 : if (map.address() != other_maps.at(0).address()) {
686 717 : return false;
687 : }
688 : }
689 : }
690 : return true;
691 : }
692 :
693 0 : void LoadElimination::AbstractState::Print() const {
694 0 : if (checks_) {
695 0 : PrintF(" checks:\n");
696 0 : checks_->Print();
697 : }
698 0 : if (maps_) {
699 0 : PrintF(" maps:\n");
700 0 : maps_->Print();
701 : }
702 0 : if (elements_) {
703 0 : PrintF(" elements:\n");
704 0 : elements_->Print();
705 : }
706 0 : for (size_t i = 0; i < arraysize(fields_); ++i) {
707 0 : if (AbstractField const* const field = fields_[i]) {
708 0 : PrintF(" field %zu:\n", i);
709 0 : field->Print();
710 : }
711 : }
712 0 : }
713 :
714 : LoadElimination::AbstractState const*
715 25289077 : LoadElimination::AbstractStateForEffectNodes::Get(Node* node) const {
716 25289077 : size_t const id = node->id();
717 70729127 : if (id < info_for_node_.size()) return info_for_node_[id];
718 : return nullptr;
719 : }
720 :
721 10454426 : void LoadElimination::AbstractStateForEffectNodes::Set(
722 10454426 : Node* node, AbstractState const* state) {
723 10454426 : size_t const id = node->id();
724 20908852 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
725 10454420 : info_for_node_[id] = state;
726 10454420 : }
727 :
728 764 : Reduction LoadElimination::ReduceArrayBufferWasNeutered(Node* node) {
729 764 : Node* const effect = NodeProperties::GetEffectInput(node);
730 : AbstractState const* state = node_states_.Get(effect);
731 764 : if (state == nullptr) return NoChange();
732 621 : if (Node* const check = state->LookupCheck(node)) {
733 52 : ReplaceWithValue(node, check, effect);
734 : return Replace(check);
735 : }
736 569 : state = state->AddCheck(node, zone());
737 569 : return UpdateState(node, state);
738 : }
739 :
740 11602 : Reduction LoadElimination::ReduceMapGuard(Node* node) {
741 11602 : ZoneHandleSet<Map> const maps = MapGuardMapsOf(node->op()).maps();
742 11602 : Node* const object = NodeProperties::GetValueInput(node, 0);
743 11602 : Node* const effect = NodeProperties::GetEffectInput(node);
744 : AbstractState const* state = node_states_.Get(effect);
745 11602 : if (state == nullptr) return NoChange();
746 : ZoneHandleSet<Map> object_maps;
747 9978 : if (state->LookupMaps(object, &object_maps)) {
748 1614 : if (maps.contains(object_maps)) return Replace(effect);
749 : // TODO(turbofan): Compute the intersection.
750 : }
751 9961 : state = state->SetMaps(object, maps, zone());
752 9961 : return UpdateState(node, state);
753 : }
754 :
755 134322 : Reduction LoadElimination::ReduceCheckMaps(Node* node) {
756 134322 : ZoneHandleSet<Map> const maps = CheckMapsParametersOf(node->op()).maps();
757 134322 : Node* const object = NodeProperties::GetValueInput(node, 0);
758 134322 : Node* const effect = NodeProperties::GetEffectInput(node);
759 : AbstractState const* state = node_states_.Get(effect);
760 134322 : if (state == nullptr) return NoChange();
761 : ZoneHandleSet<Map> object_maps;
762 95241 : if (state->LookupMaps(object, &object_maps)) {
763 39490 : if (maps.contains(object_maps)) return Replace(effect);
764 : // TODO(turbofan): Compute the intersection.
765 : }
766 56276 : state = state->SetMaps(object, maps, zone());
767 56276 : return UpdateState(node, state);
768 : }
769 :
770 12040 : Reduction LoadElimination::ReduceCompareMaps(Node* node) {
771 12023 : ZoneHandleSet<Map> const maps = CompareMapsParametersOf(node->op()).maps();
772 12023 : Node* const object = NodeProperties::GetValueInput(node, 0);
773 12023 : Node* const effect = NodeProperties::GetEffectInput(node);
774 : AbstractState const* state = node_states_.Get(effect);
775 12023 : if (state == nullptr) return NoChange();
776 : ZoneHandleSet<Map> object_maps;
777 10297 : if (state->LookupMaps(object, &object_maps)) {
778 1606 : if (maps.contains(object_maps)) {
779 17 : Node* value = jsgraph()->TrueConstant();
780 17 : ReplaceWithValue(node, value, effect);
781 : return Replace(value);
782 : }
783 : // TODO(turbofan): Compute the intersection.
784 : }
785 10280 : return UpdateState(node, state);
786 : }
787 :
788 400 : Reduction LoadElimination::ReduceEnsureWritableFastElements(Node* node) {
789 400 : Node* const object = NodeProperties::GetValueInput(node, 0);
790 400 : Node* const elements = NodeProperties::GetValueInput(node, 1);
791 400 : Node* const effect = NodeProperties::GetEffectInput(node);
792 : AbstractState const* state = node_states_.Get(effect);
793 400 : if (state == nullptr) return NoChange();
794 : // Check if the {elements} already have the fixed array map.
795 : ZoneHandleSet<Map> elements_maps;
796 : ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
797 377 : if (state->LookupMaps(elements, &elements_maps) &&
798 13 : fixed_array_maps.contains(elements_maps)) {
799 13 : ReplaceWithValue(node, elements, effect);
800 : return Replace(elements);
801 : }
802 : // We know that the resulting elements have the fixed array map.
803 351 : state = state->SetMaps(node, fixed_array_maps, zone());
804 : // Kill the previous elements on {object}.
805 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
806 : MaybeHandle<Name>(), zone());
807 : // Add the new elements on {object}.
808 : state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
809 351 : MaybeHandle<Name>(), zone());
810 351 : return UpdateState(node, state);
811 : }
812 :
813 4577 : Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
814 4577 : GrowFastElementsMode mode = GrowFastElementsModeOf(node->op());
815 4577 : Node* const object = NodeProperties::GetValueInput(node, 0);
816 4577 : Node* const effect = NodeProperties::GetEffectInput(node);
817 : AbstractState const* state = node_states_.Get(effect);
818 4577 : if (state == nullptr) return NoChange();
819 2956 : if (mode == GrowFastElementsMode::kDoubleElements) {
820 : // We know that the resulting elements have the fixed double array map.
821 : state = state->SetMaps(
822 321 : node, ZoneHandleSet<Map>(factory()->fixed_double_array_map()), zone());
823 : } else {
824 : // We know that the resulting elements have the fixed array map.
825 : state = state->SetMaps(
826 2635 : node, ZoneHandleSet<Map>(factory()->fixed_array_map()), zone());
827 : }
828 : // Kill the previous elements on {object}.
829 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
830 : MaybeHandle<Name>(), zone());
831 : // Add the new elements on {object}.
832 : state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
833 2956 : MaybeHandle<Name>(), zone());
834 2956 : return UpdateState(node, state);
835 : }
836 :
837 1040 : Reduction LoadElimination::ReduceTransitionElementsKind(Node* node) {
838 1040 : ElementsTransition transition = ElementsTransitionOf(node->op());
839 1040 : Node* const object = NodeProperties::GetValueInput(node, 0);
840 : Handle<Map> source_map(transition.source());
841 : Handle<Map> target_map(transition.target());
842 1040 : Node* const effect = NodeProperties::GetEffectInput(node);
843 : AbstractState const* state = node_states_.Get(effect);
844 1040 : if (state == nullptr) return NoChange();
845 721 : switch (transition.mode()) {
846 : case ElementsTransition::kFastTransition:
847 : break;
848 : case ElementsTransition::kSlowTransition:
849 : // Kill the elements as well.
850 : AliasStateInfo alias_info(state, object, source_map);
851 : state =
852 : state->KillField(alias_info, FieldIndexOf(JSObject::kElementsOffset),
853 472 : MaybeHandle<Name>(), zone());
854 472 : break;
855 : }
856 : ZoneHandleSet<Map> object_maps;
857 721 : if (state->LookupMaps(object, &object_maps)) {
858 235 : if (ZoneHandleSet<Map>(target_map).contains(object_maps)) {
859 : // The {object} already has the {target_map}, so this TransitionElements
860 : // {node} is fully redundant (independent of what {source_map} is).
861 : return Replace(effect);
862 : }
863 83 : if (object_maps.contains(ZoneHandleSet<Map>(source_map))) {
864 83 : object_maps.remove(source_map, zone());
865 83 : object_maps.insert(target_map, zone());
866 83 : state = state->SetMaps(object, object_maps, zone());
867 : }
868 : } else {
869 : AliasStateInfo alias_info(state, object, source_map);
870 486 : state = state->KillMaps(alias_info, zone());
871 : }
872 569 : return UpdateState(node, state);
873 : }
874 :
875 1422 : Reduction LoadElimination::ReduceTransitionAndStoreElement(Node* node) {
876 474 : Node* const object = NodeProperties::GetValueInput(node, 0);
877 474 : Handle<Map> double_map(DoubleMapParameterOf(node->op()));
878 474 : Handle<Map> fast_map(FastMapParameterOf(node->op()));
879 474 : Node* const effect = NodeProperties::GetEffectInput(node);
880 : AbstractState const* state = node_states_.Get(effect);
881 474 : if (state == nullptr) return NoChange();
882 :
883 : // We need to add the double and fast maps to the set of possible maps for
884 : // this object, because we don't know which of those we'll transition to.
885 : // Additionally, we should kill all alias information.
886 : ZoneHandleSet<Map> object_maps;
887 157 : if (state->LookupMaps(object, &object_maps)) {
888 0 : object_maps.insert(double_map, zone());
889 0 : object_maps.insert(fast_map, zone());
890 0 : state = state->SetMaps(object, object_maps, zone());
891 : }
892 : // Kill the elements as well.
893 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
894 : MaybeHandle<Name>(), zone());
895 157 : return UpdateState(node, state);
896 : }
897 :
898 1497726 : Reduction LoadElimination::ReduceLoadField(Node* node) {
899 1497648 : FieldAccess const& access = FieldAccessOf(node->op());
900 1497648 : Node* const object = NodeProperties::GetValueInput(node, 0);
901 1497648 : Node* const effect = NodeProperties::GetEffectInput(node);
902 : AbstractState const* state = node_states_.Get(effect);
903 1497648 : if (state == nullptr) return NoChange();
904 1257070 : if (access.offset == HeapObject::kMapOffset &&
905 : access.base_is_tagged == kTaggedBase) {
906 : DCHECK(IsAnyTagged(access.machine_type.representation()));
907 : ZoneHandleSet<Map> object_maps;
908 9160 : if (state->LookupMaps(object, &object_maps) && object_maps.size() == 1) {
909 78 : Node* value = jsgraph()->HeapConstant(object_maps[0]);
910 : NodeProperties::SetType(value, Type::OtherInternal());
911 153398 : ReplaceWithValue(node, value, effect);
912 78 : return Replace(value);
913 : }
914 : } else {
915 1247988 : int field_index = FieldIndexOf(access);
916 1247988 : if (field_index >= 0) {
917 2236204 : if (Node* replacement = state->LookupField(object, field_index)) {
918 : // Make sure we don't resurrect dead {replacement} nodes.
919 : // Skip lowering if the type of the {replacement} node is not a subtype
920 : // of the original {node}'s type.
921 : // TODO(tebbi): We should insert a {TypeGuard} for the intersection of
922 : // these two types here once we properly handle {Type::None} everywhere.
923 309030 : if (!replacement->IsDead() && NodeProperties::GetType(replacement)
924 : ->Is(NodeProperties::GetType(node))) {
925 : ReplaceWithValue(node, replacement, effect);
926 : return Replace(replacement);
927 : }
928 : }
929 964782 : state = state->AddField(object, field_index, node, access.name, zone());
930 : }
931 : }
932 : Handle<Map> field_map;
933 1103672 : if (access.map.ToHandle(&field_map)) {
934 5050 : state = state->SetMaps(node, ZoneHandleSet<Map>(field_map), zone());
935 : }
936 1103672 : return UpdateState(node, state);
937 : }
938 :
939 1603479 : Reduction LoadElimination::ReduceStoreField(Node* node) {
940 1603479 : FieldAccess const& access = FieldAccessOf(node->op());
941 1603479 : Node* const object = NodeProperties::GetValueInput(node, 0);
942 1603479 : Node* const new_value = NodeProperties::GetValueInput(node, 1);
943 1603479 : Node* const effect = NodeProperties::GetEffectInput(node);
944 : AbstractState const* state = node_states_.Get(effect);
945 1603479 : if (state == nullptr) return NoChange();
946 1326001 : if (access.offset == HeapObject::kMapOffset &&
947 : access.base_is_tagged == kTaggedBase) {
948 : DCHECK(IsAnyTagged(access.machine_type.representation()));
949 : // Kill all potential knowledge about the {object}s map.
950 : state = state->KillMaps(object, zone());
951 : Type* const new_value_type = NodeProperties::GetType(new_value);
952 151638 : if (new_value_type->IsHeapConstant()) {
953 : // Record the new {object} map information.
954 : ZoneHandleSet<Map> object_maps(
955 : bit_cast<Handle<Map>>(new_value_type->AsHeapConstant()->Value()));
956 151637 : state = state->SetMaps(object, object_maps, zone());
957 : }
958 : } else {
959 1174363 : int field_index = FieldIndexOf(access);
960 1174363 : if (field_index >= 0) {
961 1043699 : Node* const old_value = state->LookupField(object, field_index);
962 1043699 : if (old_value == new_value) {
963 : // This store is fully redundant.
964 : return Replace(effect);
965 : }
966 : // Kill all potentially aliasing fields and record the new value.
967 : state = state->KillField(object, field_index, access.name, zone());
968 : state =
969 1041966 : state->AddField(object, field_index, new_value, access.name, zone());
970 : } else {
971 : // Unsupported StoreField operator.
972 130664 : state = state->KillFields(object, access.name, zone());
973 : }
974 : }
975 1324268 : return UpdateState(node, state);
976 : }
977 :
978 56005 : Reduction LoadElimination::ReduceLoadElement(Node* node) {
979 35627 : Node* const object = NodeProperties::GetValueInput(node, 0);
980 35627 : Node* const index = NodeProperties::GetValueInput(node, 1);
981 35627 : Node* const effect = NodeProperties::GetEffectInput(node);
982 : AbstractState const* state = node_states_.Get(effect);
983 35627 : if (state == nullptr) return NoChange();
984 :
985 : // Only handle loads that do not require truncations.
986 20378 : ElementAccess const& access = ElementAccessOf(node->op());
987 39386 : switch (access.machine_type.representation()) {
988 : case MachineRepresentation::kNone:
989 : case MachineRepresentation::kBit:
990 0 : UNREACHABLE();
991 : break;
992 : case MachineRepresentation::kWord8:
993 : case MachineRepresentation::kWord16:
994 : case MachineRepresentation::kWord32:
995 : case MachineRepresentation::kWord64:
996 : case MachineRepresentation::kFloat32:
997 : // TODO(turbofan): Add support for doing the truncations.
998 : break;
999 : case MachineRepresentation::kFloat64:
1000 : case MachineRepresentation::kSimd128:
1001 : case MachineRepresentation::kTaggedSigned:
1002 : case MachineRepresentation::kTaggedPointer:
1003 : case MachineRepresentation::kTagged:
1004 20378 : if (Node* replacement = state->LookupElement(
1005 : object, index, access.machine_type.representation())) {
1006 : // Make sure we don't resurrect dead {replacement} nodes.
1007 : // Skip lowering if the type of the {replacement} node is not a subtype
1008 : // of the original {node}'s type.
1009 : // TODO(tebbi): We should insert a {TypeGuard} for the intersection of
1010 : // these two types here once we properly handle {Type::None} everywhere.
1011 2784 : if (!replacement->IsDead() && NodeProperties::GetType(replacement)
1012 : ->Is(NodeProperties::GetType(node))) {
1013 1370 : ReplaceWithValue(node, replacement, effect);
1014 : return Replace(replacement);
1015 : }
1016 : }
1017 : state = state->AddElement(object, index, node,
1018 19008 : access.machine_type.representation(), zone());
1019 19008 : return UpdateState(node, state);
1020 : }
1021 : return NoChange();
1022 : }
1023 :
1024 54204 : Reduction LoadElimination::ReduceStoreElement(Node* node) {
1025 54204 : ElementAccess const& access = ElementAccessOf(node->op());
1026 54204 : Node* const object = NodeProperties::GetValueInput(node, 0);
1027 54204 : Node* const index = NodeProperties::GetValueInput(node, 1);
1028 54204 : Node* const new_value = NodeProperties::GetValueInput(node, 2);
1029 54204 : Node* const effect = NodeProperties::GetEffectInput(node);
1030 : AbstractState const* state = node_states_.Get(effect);
1031 54204 : if (state == nullptr) return NoChange();
1032 : Node* const old_value =
1033 85242 : state->LookupElement(object, index, access.machine_type.representation());
1034 42633 : if (old_value == new_value) {
1035 : // This store is fully redundant.
1036 : return Replace(effect);
1037 : }
1038 : // Kill all potentially aliasing elements.
1039 42609 : state = state->KillElement(object, index, zone());
1040 : // Only record the new value if the store doesn't have an implicit truncation.
1041 : switch (access.machine_type.representation()) {
1042 : case MachineRepresentation::kNone:
1043 : case MachineRepresentation::kBit:
1044 0 : UNREACHABLE();
1045 : break;
1046 : case MachineRepresentation::kWord8:
1047 : case MachineRepresentation::kWord16:
1048 : case MachineRepresentation::kWord32:
1049 : case MachineRepresentation::kWord64:
1050 : case MachineRepresentation::kFloat32:
1051 : // TODO(turbofan): Add support for doing the truncations.
1052 : break;
1053 : case MachineRepresentation::kFloat64:
1054 : case MachineRepresentation::kSimd128:
1055 : case MachineRepresentation::kTaggedSigned:
1056 : case MachineRepresentation::kTaggedPointer:
1057 : case MachineRepresentation::kTagged:
1058 : state = state->AddElement(object, index, new_value,
1059 42609 : access.machine_type.representation(), zone());
1060 42609 : break;
1061 : }
1062 42609 : return UpdateState(node, state);
1063 : }
1064 :
1065 9792 : Reduction LoadElimination::ReduceStoreTypedElement(Node* node) {
1066 9792 : Node* const effect = NodeProperties::GetEffectInput(node);
1067 : AbstractState const* state = node_states_.Get(effect);
1068 9792 : if (state == nullptr) return NoChange();
1069 6385 : return UpdateState(node, state);
1070 : }
1071 :
1072 264437 : LoadElimination::AbstractState const* LoadElimination::UpdateStateForPhi(
1073 : AbstractState const* state, Node* effect_phi, Node* phi) {
1074 264437 : int predecessor_count = phi->InputCount() - 1;
1075 : // TODO(jarin) Consider doing a union here. At the moment, we just keep this
1076 : // consistent with AbstractState::Merge.
1077 :
1078 : // Check if all the inputs have the same maps.
1079 : AbstractState const* input_state =
1080 264437 : node_states_.Get(NodeProperties::GetEffectInput(effect_phi, 0));
1081 : ZoneHandleSet<Map> object_maps;
1082 264436 : if (!input_state->LookupMaps(phi->InputAt(0), &object_maps)) return state;
1083 687 : for (int i = 1; i < predecessor_count; i++) {
1084 : input_state =
1085 645 : node_states_.Get(NodeProperties::GetEffectInput(effect_phi, i));
1086 : ZoneHandleSet<Map> input_maps;
1087 1269 : if (!input_state->LookupMaps(phi->InputAt(i), &input_maps)) return state;
1088 22 : if (input_maps != object_maps) return state;
1089 : }
1090 21 : return state->SetMaps(phi, object_maps, zone());
1091 : }
1092 :
1093 1052690 : Reduction LoadElimination::ReduceEffectPhi(Node* node) {
1094 658630 : Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
1095 1141973 : Node* const control = NodeProperties::GetControlInput(node);
1096 : AbstractState const* state0 = node_states_.Get(effect0);
1097 658630 : if (state0 == nullptr) return NoChange();
1098 483344 : if (control->opcode() == IrOpcode::kLoop) {
1099 : // Here we rely on having only reducible loops:
1100 : // The loop entry edge always dominates the header, so we can just take
1101 : // the state from the first input, and compute the loop state based on it.
1102 89284 : AbstractState const* state = ComputeLoopState(node, state0);
1103 89283 : return UpdateState(node, state);
1104 : }
1105 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
1106 :
1107 : // Shortcut for the case when we do not know anything about some input.
1108 394060 : int const input_count = node->op()->EffectInputCount();
1109 1440107 : for (int i = 1; i < input_count; ++i) {
1110 1115256 : Node* const effect = NodeProperties::GetEffectInput(node, i);
1111 1115257 : if (node_states_.Get(effect) == nullptr) return NoChange();
1112 : }
1113 :
1114 : // Make a copy of the first input's state and merge with the state
1115 : // from other inputs.
1116 324847 : AbstractState* state = new (zone()) AbstractState(*state0);
1117 822393 : for (int i = 1; i < input_count; ++i) {
1118 497539 : Node* const input = NodeProperties::GetEffectInput(node, i);
1119 497544 : state->Merge(node_states_.Get(input), zone());
1120 : }
1121 :
1122 : // For each phi, try to compute the new state for the phi from
1123 : // the inputs.
1124 : AbstractState const* state_with_phis = state;
1125 3262238 : for (Node* use : control->uses()) {
1126 1468694 : if (use->opcode() == IrOpcode::kPhi) {
1127 264438 : state_with_phis = UpdateStateForPhi(state_with_phis, node, use);
1128 : }
1129 : }
1130 :
1131 324850 : return UpdateState(node, state_with_phis);
1132 : }
1133 :
1134 0 : Reduction LoadElimination::ReduceStart(Node* node) {
1135 443362 : return UpdateState(node, empty_state());
1136 : }
1137 :
1138 36728309 : Reduction LoadElimination::ReduceOtherNode(Node* node) {
1139 29449001 : if (node->op()->EffectInputCount() == 1) {
1140 9472283 : if (node->op()->EffectOutputCount() == 1) {
1141 8672716 : Node* const effect = NodeProperties::GetEffectInput(node);
1142 : AbstractState const* state = node_states_.Get(effect);
1143 : // If we do not know anything about the predecessor, do not propagate
1144 : // just yet because we will have to recompute anyway once we compute
1145 : // the predecessor.
1146 8672756 : if (state == nullptr) return NoChange();
1147 : // Check if this {node} has some uncontrolled side effects.
1148 7279308 : if (!node->op()->HasProperty(Operator::kNoWrite)) {
1149 2281104 : state = empty_state();
1150 : }
1151 7279308 : return UpdateState(node, state);
1152 : } else {
1153 : // Effect terminators should be handled specially.
1154 : return NoChange();
1155 : }
1156 : }
1157 : DCHECK_EQ(0, node->op()->EffectInputCount());
1158 : DCHECK_EQ(0, node->op()->EffectOutputCount());
1159 : return NoChange();
1160 : }
1161 :
1162 10713857 : Reduction LoadElimination::UpdateState(Node* node, AbstractState const* state) {
1163 : AbstractState const* original = node_states_.Get(node);
1164 : // Only signal that the {node} has Changed, if the information about {state}
1165 : // has changed wrt. the {original}.
1166 10713857 : if (state != original) {
1167 10529611 : if (original == nullptr || !state->Equals(original)) {
1168 10454424 : node_states_.Set(node, state);
1169 : return Changed(node);
1170 : }
1171 : }
1172 : return NoChange();
1173 : }
1174 :
1175 89284 : LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
1176 : Node* node, AbstractState const* state) const {
1177 89284 : Node* const control = NodeProperties::GetControlInput(node);
1178 : struct TransitionElementsKindInfo {
1179 : ElementsTransition transition;
1180 : Node* object;
1181 : };
1182 : ZoneVector<TransitionElementsKindInfo> element_transitions_(zone());
1183 89284 : ZoneQueue<Node*> queue(zone());
1184 : ZoneSet<Node*> visited(zone());
1185 : visited.insert(node);
1186 357148 : for (int i = 1; i < control->InputCount(); ++i) {
1187 267852 : queue.push(node->InputAt(i));
1188 : }
1189 948443 : while (!queue.empty()) {
1190 921255 : Node* const current = queue.front();
1191 : queue.pop();
1192 921246 : if (visited.find(current) == visited.end()) {
1193 : visited.insert(current);
1194 3350157 : if (!current->op()->HasProperty(Operator::kNoWrite)) {
1195 109261 : switch (current->opcode()) {
1196 : case IrOpcode::kEnsureWritableFastElements: {
1197 32 : Node* const object = NodeProperties::GetValueInput(current, 0);
1198 : state = state->KillField(object,
1199 : FieldIndexOf(JSObject::kElementsOffset),
1200 : MaybeHandle<Name>(), zone());
1201 32 : break;
1202 : }
1203 : case IrOpcode::kMaybeGrowFastElements: {
1204 1934 : Node* const object = NodeProperties::GetValueInput(current, 0);
1205 : state = state->KillField(object,
1206 : FieldIndexOf(JSObject::kElementsOffset),
1207 : MaybeHandle<Name>(), zone());
1208 1934 : break;
1209 : }
1210 : case IrOpcode::kTransitionElementsKind: {
1211 580 : ElementsTransition transition = ElementsTransitionOf(current->op());
1212 580 : Node* const object = NodeProperties::GetValueInput(current, 0);
1213 : ZoneHandleSet<Map> object_maps;
1214 1740 : if (!state->LookupMaps(object, &object_maps) ||
1215 : !ZoneHandleSet<Map>(transition.target())
1216 650 : .contains(object_maps)) {
1217 1154 : element_transitions_.push_back({transition, object});
1218 : }
1219 : break;
1220 : }
1221 : case IrOpcode::kTransitionAndStoreElement: {
1222 330 : Node* const object = NodeProperties::GetValueInput(current, 0);
1223 : // Invalidate what we know about the {object}s map.
1224 : state = state->KillMaps(object, zone());
1225 : // Kill the elements as well.
1226 : state = state->KillField(object,
1227 : FieldIndexOf(JSObject::kElementsOffset),
1228 : MaybeHandle<Name>(), zone());
1229 330 : break;
1230 : }
1231 : case IrOpcode::kStoreField: {
1232 33219 : FieldAccess const& access = FieldAccessOf(current->op());
1233 33219 : Node* const object = NodeProperties::GetValueInput(current, 0);
1234 33219 : if (access.offset == HeapObject::kMapOffset) {
1235 : // Invalidate what we know about the {object}s map.
1236 : state = state->KillMaps(object, zone());
1237 : } else {
1238 29425 : int field_index = FieldIndexOf(access);
1239 29425 : if (field_index < 0) {
1240 20 : state = state->KillFields(object, access.name, zone());
1241 : } else {
1242 : state =
1243 29405 : state->KillField(object, field_index, access.name, zone());
1244 : }
1245 : }
1246 : break;
1247 : }
1248 : case IrOpcode::kStoreElement: {
1249 5671 : Node* const object = NodeProperties::GetValueInput(current, 0);
1250 5671 : Node* const index = NodeProperties::GetValueInput(current, 1);
1251 5671 : state = state->KillElement(object, index, zone());
1252 5671 : break;
1253 : }
1254 : case IrOpcode::kStoreTypedElement: {
1255 : // Doesn't affect anything we track with the state currently.
1256 : break;
1257 : }
1258 : default:
1259 62096 : return empty_state();
1260 : }
1261 : }
1262 4956327 : for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
1263 1730385 : queue.push(NodeProperties::GetEffectInput(current, i));
1264 : }
1265 : }
1266 : }
1267 :
1268 : // Finally, we apply the element transitions. For each transition, we will try
1269 : // to only invalidate information about nodes that can have the transition's
1270 : // source map. The trouble is that an object can be transitioned by some other
1271 : // transition to the source map. In that case, the other transition will
1272 : // invalidate the information, so we are mostly fine.
1273 : //
1274 : // The only bad case is
1275 : //
1276 : // mapA ---fast---> mapB ---slow---> mapC
1277 : //
1278 : // If we process the slow transition first on an object that has mapA, we will
1279 : // ignore the transition because the object does not have its source map
1280 : // (mapB). When we later process the fast transition, we invalidate the
1281 : // object's map, but we keep the information about the object's elements. This
1282 : // is wrong because the elements will be overwritten by the slow transition.
1283 : //
1284 : // Note that the slow-slow case is fine because either of the slow transition
1285 : // will invalidate the elements field, so the processing order does not
1286 : // matter.
1287 : //
1288 : // To handle the bad case properly, we first kill the maps using all
1289 : // transitions. We kill the the fields later when all the transitions are
1290 : // already reflected in the map information.
1291 :
1292 54507 : for (const TransitionElementsKindInfo& t : element_transitions_) {
1293 131 : AliasStateInfo alias_info(state, t.object, t.transition.source());
1294 131 : state = state->KillMaps(alias_info, zone());
1295 : }
1296 54507 : for (const TransitionElementsKindInfo& t : element_transitions_) {
1297 131 : switch (t.transition.mode()) {
1298 : case ElementsTransition::kFastTransition:
1299 : break;
1300 : case ElementsTransition::kSlowTransition: {
1301 72 : AliasStateInfo alias_info(state, t.object, t.transition.source());
1302 : state = state->KillField(alias_info,
1303 : FieldIndexOf(JSObject::kElementsOffset),
1304 72 : MaybeHandle<Name>(), zone());
1305 : break;
1306 : }
1307 : }
1308 : }
1309 : return state;
1310 : }
1311 :
1312 : // static
1313 0 : int LoadElimination::FieldIndexOf(int offset) {
1314 : DCHECK_EQ(0, offset % kPointerSize);
1315 2388145 : int field_index = offset / kPointerSize;
1316 2388145 : if (field_index >= static_cast<int>(kMaxTrackedFields)) return -1;
1317 : DCHECK_LT(0, field_index);
1318 2191206 : return field_index - 1;
1319 : }
1320 :
1321 : // static
1322 2451776 : int LoadElimination::FieldIndexOf(FieldAccess const& access) {
1323 2451776 : MachineRepresentation rep = access.machine_type.representation();
1324 : switch (rep) {
1325 : case MachineRepresentation::kNone:
1326 : case MachineRepresentation::kBit:
1327 : case MachineRepresentation::kSimd128:
1328 0 : UNREACHABLE();
1329 : break;
1330 : case MachineRepresentation::kWord32:
1331 : case MachineRepresentation::kWord64:
1332 10986 : if (rep != MachineType::PointerRepresentation()) {
1333 : return -1; // We currently only track pointer size fields.
1334 : }
1335 : break;
1336 : case MachineRepresentation::kWord8:
1337 : case MachineRepresentation::kWord16:
1338 : case MachineRepresentation::kFloat32:
1339 : return -1; // Currently untracked.
1340 : case MachineRepresentation::kFloat64:
1341 : if (kDoubleSize != kPointerSize) {
1342 : return -1; // We currently only track pointer size fields.
1343 : }
1344 : // Fall through.
1345 : case MachineRepresentation::kTaggedSigned:
1346 : case MachineRepresentation::kTaggedPointer:
1347 : case MachineRepresentation::kTagged:
1348 : // TODO(bmeurer): Check that we never do overlapping load/stores of
1349 : // individual parts of Float64 values.
1350 : break;
1351 : }
1352 2443855 : if (access.base_is_tagged != kTaggedBase) {
1353 : return -1; // We currently only track tagged objects.
1354 : }
1355 4776290 : return FieldIndexOf(access.offset);
1356 : }
1357 :
1358 0 : CommonOperatorBuilder* LoadElimination::common() const {
1359 0 : return jsgraph()->common();
1360 : }
1361 :
1362 0 : Graph* LoadElimination::graph() const { return jsgraph()->graph(); }
1363 :
1364 3320 : Factory* LoadElimination::factory() const { return jsgraph()->factory(); }
1365 :
1366 : } // namespace compiler
1367 : } // namespace internal
1368 : } // namespace v8
|
