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