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/heap/factory.h"
12 : #include "src/objects-inl.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 :
18 : namespace {
19 :
20 340309981 : bool IsRename(Node* node) {
21 340309981 : switch (node->opcode()) {
22 : case IrOpcode::kCheckHeapObject:
23 : case IrOpcode::kFinishRegion:
24 : case IrOpcode::kTypeGuard:
25 783218 : return !node->IsDead();
26 : default:
27 : return false;
28 : }
29 : }
30 :
31 338805855 : Node* ResolveRenames(Node* node) {
32 678095575 : while (IsRename(node)) {
33 : node = node->InputAt(0);
34 : }
35 338805856 : return node;
36 : }
37 :
38 1876300 : bool MayAlias(Node* a, Node* b) {
39 1430584 : if (a != b) {
40 752362 : if (!NodeProperties::GetType(a).Maybe(NodeProperties::GetType(b))) {
41 : return false;
42 522211 : } else if (IsRename(b)) {
43 24150 : return MayAlias(a, b->InputAt(0));
44 498060 : } else if (IsRename(a)) {
45 275202 : return MayAlias(a->InputAt(0), b);
46 222858 : } else if (b->opcode() == IrOpcode::kAllocate) {
47 66721 : switch (a->opcode()) {
48 : case IrOpcode::kAllocate:
49 : case IrOpcode::kHeapConstant:
50 : case IrOpcode::kParameter:
51 : return false;
52 : default:
53 : break;
54 : }
55 156137 : } else if (a->opcode() == IrOpcode::kAllocate) {
56 44409 : switch (b->opcode()) {
57 : case IrOpcode::kHeapConstant:
58 : case IrOpcode::kParameter:
59 : return false;
60 : default:
61 : break;
62 : }
63 : }
64 : }
65 : return true;
66 : }
67 :
68 : bool MustAlias(Node* a, Node* b) {
69 169233864 : return ResolveRenames(a) == ResolveRenames(b);
70 : }
71 :
72 : } // namespace
73 :
74 67791362 : Reduction LoadElimination::Reduce(Node* node) {
75 33895681 : if (FLAG_trace_turbo_load_elimination) {
76 0 : if (node->op()->EffectInputCount() > 0) {
77 0 : PrintF(" visit #%d:%s", node->id(), node->op()->mnemonic());
78 0 : if (node->op()->ValueInputCount() > 0) {
79 0 : PrintF("(");
80 0 : for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
81 0 : if (i > 0) PrintF(", ");
82 0 : Node* const value = NodeProperties::GetValueInput(node, i);
83 0 : PrintF("#%d:%s", value->id(), value->op()->mnemonic());
84 : }
85 0 : PrintF(")");
86 : }
87 0 : PrintF("\n");
88 0 : for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
89 0 : Node* const effect = NodeProperties::GetEffectInput(node, i);
90 0 : if (AbstractState const* const state = node_states_.Get(effect)) {
91 : PrintF(" state[%i]: #%d:%s\n", i, effect->id(),
92 0 : effect->op()->mnemonic());
93 0 : state->Print();
94 : } else {
95 : PrintF(" no state[%i]: #%d:%s\n", i, effect->id(),
96 0 : effect->op()->mnemonic());
97 : }
98 : }
99 : }
100 : }
101 33895681 : switch (node->opcode()) {
102 : case IrOpcode::kMapGuard:
103 6835 : return ReduceMapGuard(node);
104 : case IrOpcode::kCheckMaps:
105 186718 : return ReduceCheckMaps(node);
106 : case IrOpcode::kCompareMaps:
107 7398 : return ReduceCompareMaps(node);
108 : case IrOpcode::kEnsureWritableFastElements:
109 9390 : return ReduceEnsureWritableFastElements(node);
110 : case IrOpcode::kMaybeGrowFastElements:
111 13040 : return ReduceMaybeGrowFastElements(node);
112 : case IrOpcode::kTransitionElementsKind:
113 938 : return ReduceTransitionElementsKind(node);
114 : case IrOpcode::kLoadField:
115 1135557 : return ReduceLoadField(node);
116 : case IrOpcode::kStoreField:
117 1751601 : return ReduceStoreField(node);
118 : case IrOpcode::kLoadElement:
119 36004 : return ReduceLoadElement(node);
120 : case IrOpcode::kStoreElement:
121 62913 : return ReduceStoreElement(node);
122 : case IrOpcode::kTransitionAndStoreElement:
123 579 : return ReduceTransitionAndStoreElement(node);
124 : case IrOpcode::kStoreTypedElement:
125 5840 : return ReduceStoreTypedElement(node);
126 : case IrOpcode::kEffectPhi:
127 608191 : return ReduceEffectPhi(node);
128 : case IrOpcode::kDead:
129 : break;
130 : case IrOpcode::kStart:
131 : return ReduceStart(node);
132 : default:
133 29601642 : return ReduceOtherNode(node);
134 : }
135 : return NoChange();
136 : }
137 :
138 : namespace {
139 :
140 1712 : bool IsCompatible(MachineRepresentation r1, MachineRepresentation r2) {
141 1712 : if (r1 == r2) return true;
142 258 : return IsAnyTagged(r1) && IsAnyTagged(r2);
143 : }
144 :
145 : } // namespace
146 :
147 40490 : Node* LoadElimination::AbstractElements::Lookup(
148 : Node* object, Node* index, MachineRepresentation representation) const {
149 353220 : for (Element const element : elements_) {
150 314435 : if (element.object == nullptr) continue;
151 : DCHECK_NOT_NULL(element.index);
152 : DCHECK_NOT_NULL(element.value);
153 252103 : if (MustAlias(object, element.object) && MustAlias(index, element.index) &&
154 1712 : IsCompatible(representation, element.representation)) {
155 : return element.value;
156 : }
157 : }
158 : return nullptr;
159 : }
160 :
161 : LoadElimination::AbstractElements const*
162 36875 : LoadElimination::AbstractElements::Kill(Node* object, Node* index,
163 : Zone* zone) const {
164 69572 : for (Element const element : this->elements_) {
165 66110 : if (element.object == nullptr) continue;
166 42871 : if (MayAlias(object, element.object)) {
167 33413 : AbstractElements* that = new (zone) AbstractElements(zone);
168 300717 : for (Element const element : this->elements_) {
169 267304 : if (element.object == nullptr) continue;
170 : DCHECK_NOT_NULL(element.index);
171 : DCHECK_NOT_NULL(element.value);
172 363087 : if (!MayAlias(object, element.object) ||
173 : !NodeProperties::GetType(index).Maybe(
174 346649 : NodeProperties::GetType(element.index))) {
175 111829 : that->elements_[that->next_index_++] = element;
176 : }
177 : }
178 33413 : that->next_index_ %= arraysize(elements_);
179 : return that;
180 : }
181 : }
182 3462 : return this;
183 : }
184 :
185 14486 : bool LoadElimination::AbstractElements::Equals(
186 : AbstractElements const* that) const {
187 14486 : if (this == that) return true;
188 38185 : for (size_t i = 0; i < arraysize(elements_); ++i) {
189 39437 : Element this_element = this->elements_[i];
190 39437 : if (this_element.object == nullptr) continue;
191 20043 : for (size_t j = 0;; ++j) {
192 27570 : if (j == arraysize(elements_)) return false;
193 26318 : Element that_element = that->elements_[j];
194 26318 : if (this_element.object == that_element.object &&
195 6330 : this_element.index == that_element.index &&
196 : this_element.value == that_element.value) {
197 : break;
198 : }
199 20043 : }
200 : }
201 29923 : for (size_t i = 0; i < arraysize(elements_); ++i) {
202 30982 : Element that_element = that->elements_[i];
203 30982 : if (that_element.object == nullptr) continue;
204 11498 : for (size_t j = 0;; ++j) {
205 17115 : if (j == arraysize(elements_)) return false;
206 16056 : Element this_element = this->elements_[j];
207 16056 : if (that_element.object == this_element.object &&
208 4558 : that_element.index == this_element.index &&
209 : that_element.value == this_element.value) {
210 : break;
211 : }
212 11498 : }
213 : }
214 : return true;
215 : }
216 :
217 : LoadElimination::AbstractElements const*
218 7218 : LoadElimination::AbstractElements::Merge(AbstractElements const* that,
219 : Zone* zone) const {
220 7218 : if (this->Equals(that)) return this;
221 1505 : AbstractElements* copy = new (zone) AbstractElements(zone);
222 13545 : for (Element const this_element : this->elements_) {
223 12040 : if (this_element.object == nullptr) continue;
224 13940 : for (Element const that_element : that->elements_) {
225 12550 : if (this_element.object == that_element.object &&
226 763 : this_element.index == that_element.index &&
227 : this_element.value == that_element.value) {
228 756 : copy->elements_[copy->next_index_++] = this_element;
229 756 : break;
230 : }
231 : }
232 : }
233 1505 : copy->next_index_ %= arraysize(elements_);
234 1505 : return copy;
235 : }
236 :
237 0 : void LoadElimination::AbstractElements::Print() const {
238 0 : for (Element const& element : elements_) {
239 0 : if (element.object) {
240 : PrintF(" #%d:%s @ #%d:%s -> #%d:%s\n", element.object->id(),
241 : element.object->op()->mnemonic(), element.index->id(),
242 : element.index->op()->mnemonic(), element.value->id(),
243 0 : element.value->op()->mnemonic());
244 : }
245 : }
246 0 : }
247 :
248 702719 : Node* LoadElimination::AbstractField::Lookup(Node* object) const {
249 170135552 : for (auto pair : info_for_node_) {
250 168983473 : if (pair.first->IsDead()) continue;
251 168983474 : if (MustAlias(object, pair.first)) return pair.second.value;
252 : }
253 : return nullptr;
254 : }
255 :
256 : namespace {
257 :
258 : bool MayAlias(MaybeHandle<Name> x, MaybeHandle<Name> y) {
259 349128 : if (!x.address()) return true;
260 178812 : if (!y.address()) return true;
261 154124 : if (x.address() != y.address()) return false;
262 : return true;
263 : }
264 :
265 : } // namespace
266 :
267 : class LoadElimination::AliasStateInfo {
268 : public:
269 : AliasStateInfo(const AbstractState* state, Node* object, Handle<Map> map)
270 1274 : : state_(state), object_(object), map_(map) {}
271 : AliasStateInfo(const AbstractState* state, Node* object)
272 1608846 : : state_(state), object_(object) {}
273 :
274 : bool MayAlias(Node* other) const;
275 :
276 : private:
277 : const AbstractState* state_;
278 : Node* object_;
279 : MaybeHandle<Map> map_;
280 : };
281 :
282 5522542 : LoadElimination::AbstractField const* LoadElimination::AbstractField::Kill(
283 : const AliasStateInfo& alias_info, MaybeHandle<Name> name,
284 : Zone* zone) const {
285 183838459 : for (auto pair : this->info_for_node_) {
286 173137405 : if (pair.first->IsDead()) continue;
287 173137406 : if (alias_info.MayAlias(pair.first)) {
288 : AbstractField* that = new (zone) AbstractField(zone);
289 1168589 : for (auto pair : this->info_for_node_) {
290 829633 : if (!alias_info.MayAlias(pair.first) ||
291 : !MayAlias(name, pair.second.name)) {
292 : that->info_for_node_.insert(pair);
293 : }
294 : }
295 : return that;
296 : }
297 : }
298 : return this;
299 : }
300 :
301 0 : void LoadElimination::AbstractField::Print() const {
302 0 : for (auto pair : info_for_node_) {
303 : PrintF(" #%d:%s -> #%d:%s\n", pair.first->id(),
304 : pair.first->op()->mnemonic(), pair.second.value->id(),
305 0 : pair.second.value->op()->mnemonic());
306 : }
307 0 : }
308 :
309 0 : LoadElimination::AbstractMaps::AbstractMaps(Zone* zone)
310 0 : : info_for_node_(zone) {}
311 :
312 120349 : LoadElimination::AbstractMaps::AbstractMaps(Node* object,
313 : ZoneHandleSet<Map> maps, Zone* zone)
314 : : info_for_node_(zone) {
315 120349 : object = ResolveRenames(object);
316 240703 : info_for_node_.insert(std::make_pair(object, maps));
317 120352 : }
318 :
319 102723 : bool LoadElimination::AbstractMaps::Lookup(
320 : Node* object, ZoneHandleSet<Map>* object_maps) const {
321 205446 : auto it = info_for_node_.find(ResolveRenames(object));
322 102723 : if (it == info_for_node_.end()) return false;
323 49239 : *object_maps = it->second;
324 49239 : return true;
325 : }
326 :
327 92034 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Kill(
328 : const AliasStateInfo& alias_info, Zone* zone) const {
329 28328629 : for (auto pair : this->info_for_node_) {
330 28163395 : if (alias_info.MayAlias(pair.first)) {
331 : AbstractMaps* that = new (zone) AbstractMaps(zone);
332 65477 : for (auto pair : this->info_for_node_) {
333 27809 : if (!alias_info.MayAlias(pair.first)) that->info_for_node_.insert(pair);
334 : }
335 : return that;
336 : }
337 : }
338 : return this;
339 : }
340 :
341 34185 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Merge(
342 : AbstractMaps const* that, Zone* zone) const {
343 34185 : if (this->Equals(that)) return this;
344 : AbstractMaps* copy = new (zone) AbstractMaps(zone);
345 32194 : for (auto this_it : this->info_for_node_) {
346 14854 : Node* this_object = this_it.first;
347 14854 : ZoneHandleSet<Map> this_maps = this_it.second;
348 : auto that_it = that->info_for_node_.find(this_object);
349 14855 : if (that_it != that->info_for_node_.end() && that_it->second == this_maps) {
350 : copy->info_for_node_.insert(this_it);
351 : }
352 : }
353 8670 : return copy;
354 : }
355 :
356 115053 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Extend(
357 : Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
358 : AbstractMaps* that = new (zone) AbstractMaps(zone);
359 : that->info_for_node_ = this->info_for_node_;
360 115053 : object = ResolveRenames(object);
361 115054 : that->info_for_node_[object] = maps;
362 115054 : return that;
363 : }
364 :
365 0 : void LoadElimination::AbstractMaps::Print() const {
366 : AllowHandleDereference allow_handle_dereference;
367 0 : StdoutStream os;
368 0 : for (auto pair : info_for_node_) {
369 0 : os << " #" << pair.first->id() << ":" << pair.first->op()->mnemonic()
370 : << std::endl;
371 : ZoneHandleSet<Map> const& maps = pair.second;
372 0 : for (size_t i = 0; i < maps.size(); ++i) {
373 0 : os << " - " << Brief(*maps[i]) << std::endl;
374 : }
375 0 : }
376 0 : }
377 :
378 58287 : bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
379 58287 : if (this->elements_) {
380 7282 : if (!that->elements_ || !that->elements_->Equals(this->elements_)) {
381 : return false;
382 : }
383 51005 : } else if (that->elements_) {
384 : return false;
385 : }
386 1796852 : for (size_t i = 0u; i < arraysize(fields_); ++i) {
387 1798221 : AbstractField const* this_field = this->fields_[i];
388 1798221 : AbstractField const* that_field = that->fields_[i];
389 1798221 : if (this_field) {
390 148706 : if (!that_field || !that_field->Equals(this_field)) return false;
391 1723867 : } else if (that_field) {
392 : return false;
393 : }
394 : }
395 56098 : if (this->maps_) {
396 37684 : if (!that->maps_ || !that->maps_->Equals(this->maps_)) {
397 : return false;
398 : }
399 37256 : } else if (that->maps_) {
400 : return false;
401 : }
402 : return true;
403 : }
404 :
405 570184 : void LoadElimination::AbstractState::Merge(AbstractState const* that,
406 : Zone* zone) {
407 : // Merge the information we have about the elements.
408 570184 : if (this->elements_) {
409 : this->elements_ = that->elements_
410 : ? that->elements_->Merge(this->elements_, zone)
411 14679 : : nullptr;
412 : }
413 :
414 : // Merge the information we have about the fields.
415 18245688 : for (size_t i = 0; i < arraysize(fields_); ++i) {
416 18245685 : if (this->fields_[i]) {
417 437166 : if (that->fields_[i]) {
418 225916 : this->fields_[i] = this->fields_[i]->Merge(that->fields_[i], zone);
419 : } else {
420 211250 : this->fields_[i] = nullptr;
421 : }
422 : }
423 : }
424 :
425 : // Merge the information we have about the maps.
426 570187 : if (this->maps_) {
427 53530 : this->maps_ = that->maps_ ? that->maps_->Merge(this->maps_, zone) : nullptr;
428 : }
429 570187 : }
430 :
431 0 : bool LoadElimination::AbstractState::LookupMaps(
432 : Node* object, ZoneHandleSet<Map>* object_map) const {
433 354370 : return this->maps_ && this->maps_->Lookup(object, object_map);
434 : }
435 :
436 235404 : LoadElimination::AbstractState const* LoadElimination::AbstractState::SetMaps(
437 : Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
438 235403 : AbstractState* that = new (zone) AbstractState(*this);
439 235403 : if (that->maps_) {
440 115053 : that->maps_ = that->maps_->Extend(object, maps, zone);
441 : } else {
442 240700 : that->maps_ = new (zone) AbstractMaps(object, maps, zone);
443 : }
444 235406 : return that;
445 : }
446 :
447 165716 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
448 : const AliasStateInfo& alias_info, Zone* zone) const {
449 165716 : if (this->maps_) {
450 92033 : AbstractMaps const* that_maps = this->maps_->Kill(alias_info, zone);
451 92034 : if (this->maps_ != that_maps) {
452 18834 : AbstractState* that = new (zone) AbstractState(*this);
453 18834 : that->maps_ = that_maps;
454 18834 : return that;
455 : }
456 : }
457 146883 : return this;
458 : }
459 :
460 0 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
461 : Node* object, Zone* zone) const {
462 : AliasStateInfo alias_info(this, object);
463 164980 : return KillMaps(alias_info, zone);
464 : }
465 :
466 0 : Node* LoadElimination::AbstractState::LookupElement(
467 : Node* object, Node* index, MachineRepresentation representation) const {
468 64156 : if (this->elements_) {
469 40490 : return this->elements_->Lookup(object, index, representation);
470 : }
471 : return nullptr;
472 : }
473 :
474 : LoadElimination::AbstractState const*
475 62853 : LoadElimination::AbstractState::AddElement(Node* object, Node* index,
476 : Node* value,
477 : MachineRepresentation representation,
478 : Zone* zone) const {
479 62853 : AbstractState* that = new (zone) AbstractState(*this);
480 62853 : if (that->elements_) {
481 : that->elements_ =
482 39188 : that->elements_->Extend(object, index, value, representation, zone);
483 : } else {
484 : that->elements_ =
485 23665 : new (zone) AbstractElements(object, index, value, representation, zone);
486 : }
487 62853 : return that;
488 : }
489 :
490 : LoadElimination::AbstractState const*
491 48540 : LoadElimination::AbstractState::KillElement(Node* object, Node* index,
492 : Zone* zone) const {
493 48540 : if (this->elements_) {
494 : AbstractElements const* that_elements =
495 36875 : this->elements_->Kill(object, index, zone);
496 36875 : if (this->elements_ != that_elements) {
497 33413 : AbstractState* that = new (zone) AbstractState(*this);
498 33413 : that->elements_ = that_elements;
499 33413 : return that;
500 : }
501 : }
502 15127 : return this;
503 : }
504 :
505 1754407 : LoadElimination::AbstractState const* LoadElimination::AbstractState::AddField(
506 : Node* object, size_t index, Node* value, MaybeHandle<Name> name,
507 : Zone* zone) const {
508 1754405 : AbstractState* that = new (zone) AbstractState(*this);
509 1754405 : if (that->fields_[index]) {
510 : that->fields_[index] =
511 582884 : that->fields_[index]->Extend(object, value, name, zone);
512 : } else {
513 2343042 : that->fields_[index] = new (zone) AbstractField(object, value, name, zone);
514 : }
515 1754405 : return that;
516 : }
517 :
518 0 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
519 : Node* object, size_t index, MaybeHandle<Name> name, Zone* zone) const {
520 : AliasStateInfo alias_info(this, object);
521 1153048 : return KillField(alias_info, index, name, zone);
522 : }
523 :
524 1153585 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
525 : const AliasStateInfo& alias_info, size_t index, MaybeHandle<Name> name,
526 : Zone* zone) const {
527 1153585 : if (AbstractField const* this_field = this->fields_[index]) {
528 510104 : this_field = this_field->Kill(alias_info, name, zone);
529 510104 : if (this->fields_[index] != this_field) {
530 160533 : AbstractState* that = new (zone) AbstractState(*this);
531 160533 : that->fields_[index] = this_field;
532 160533 : return that;
533 : }
534 : }
535 993051 : return this;
536 : }
537 :
538 : LoadElimination::AbstractState const*
539 290818 : LoadElimination::AbstractState::KillFields(Node* object, MaybeHandle<Name> name,
540 : Zone* zone) const {
541 : AliasStateInfo alias_info(this, object);
542 9103723 : for (size_t i = 0;; ++i) {
543 9394541 : if (i == arraysize(fields_)) return this;
544 9110515 : if (AbstractField const* this_field = this->fields_[i]) {
545 : AbstractField const* that_field =
546 4832820 : this_field->Kill(alias_info, name, zone);
547 4832739 : if (that_field != this_field) {
548 6711 : AbstractState* that = new (zone) AbstractState(*this);
549 6711 : that->fields_[i] = that_field;
550 208315 : while (++i < arraysize(fields_)) {
551 194893 : if (this->fields_[i] != nullptr) {
552 179624 : that->fields_[i] = this->fields_[i]->Kill(alias_info, name, zone);
553 : }
554 : }
555 : return that;
556 : }
557 : }
558 9103723 : }
559 : }
560 :
561 0 : Node* LoadElimination::AbstractState::LookupField(Node* object,
562 : size_t index) const {
563 1874243 : if (AbstractField const* this_field = this->fields_[index]) {
564 702720 : return this_field->Lookup(object);
565 : }
566 : return nullptr;
567 : }
568 :
569 201809116 : bool LoadElimination::AliasStateInfo::MayAlias(Node* other) const {
570 : // If {object} is being initialized right here (indicated by {object} being
571 : // an Allocate node instead of a FinishRegion node), we know that {other}
572 : // can only alias with {object} if they refer to exactly the same node.
573 403618232 : if (object_->opcode() == IrOpcode::kAllocate) {
574 200841784 : return object_ == other;
575 : }
576 : // Decide aliasing based on the node kinds.
577 967332 : if (!compiler::MayAlias(object_, other)) {
578 : return false;
579 : }
580 : // Decide aliasing based on maps (if available).
581 : Handle<Map> map;
582 693347 : if (map_.ToHandle(&map)) {
583 : ZoneHandleSet<Map> other_maps;
584 2722 : if (state_->LookupMaps(other, &other_maps) && other_maps.size() == 1) {
585 1780 : if (map.address() != other_maps.at(0).address()) {
586 555 : return false;
587 : }
588 : }
589 : }
590 : return true;
591 : }
592 :
593 0 : void LoadElimination::AbstractState::Print() const {
594 0 : if (maps_) {
595 0 : PrintF(" maps:\n");
596 0 : maps_->Print();
597 : }
598 0 : if (elements_) {
599 0 : PrintF(" elements:\n");
600 0 : elements_->Print();
601 : }
602 0 : for (size_t i = 0; i < arraysize(fields_); ++i) {
603 0 : if (AbstractField const* const field = fields_[i]) {
604 0 : PrintF(" field %zu:\n", i);
605 0 : field->Print();
606 : }
607 : }
608 0 : }
609 :
610 : LoadElimination::AbstractState const*
611 25039659 : LoadElimination::AbstractStateForEffectNodes::Get(Node* node) const {
612 25039659 : size_t const id = node->id();
613 69087111 : if (id < info_for_node_.size()) return info_for_node_[id];
614 : return nullptr;
615 : }
616 :
617 10156251 : void LoadElimination::AbstractStateForEffectNodes::Set(
618 10156251 : Node* node, AbstractState const* state) {
619 10156251 : size_t const id = node->id();
620 20312502 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
621 10156237 : info_for_node_[id] = state;
622 10156237 : }
623 :
624 6835 : Reduction LoadElimination::ReduceMapGuard(Node* node) {
625 6835 : ZoneHandleSet<Map> const maps = MapGuardMapsOf(node->op()).maps();
626 6835 : Node* const object = NodeProperties::GetValueInput(node, 0);
627 6835 : Node* const effect = NodeProperties::GetEffectInput(node);
628 : AbstractState const* state = node_states_.Get(effect);
629 6835 : if (state == nullptr) return NoChange();
630 : ZoneHandleSet<Map> object_maps;
631 5750 : if (state->LookupMaps(object, &object_maps)) {
632 273 : if (maps.contains(object_maps)) return Replace(effect);
633 : // TODO(turbofan): Compute the intersection.
634 : }
635 5637 : state = state->SetMaps(object, maps, zone());
636 5637 : return UpdateState(node, state);
637 : }
638 :
639 186718 : Reduction LoadElimination::ReduceCheckMaps(Node* node) {
640 186718 : ZoneHandleSet<Map> const maps = CheckMapsParametersOf(node->op()).maps();
641 186718 : Node* const object = NodeProperties::GetValueInput(node, 0);
642 186719 : Node* const effect = NodeProperties::GetEffectInput(node);
643 : AbstractState const* state = node_states_.Get(effect);
644 186719 : if (state == nullptr) return NoChange();
645 : ZoneHandleSet<Map> object_maps;
646 104922 : if (state->LookupMaps(object, &object_maps)) {
647 45628 : if (maps.contains(object_maps)) return Replace(effect);
648 : // TODO(turbofan): Compute the intersection.
649 : }
650 59525 : state = state->SetMaps(object, maps, zone());
651 59525 : return UpdateState(node, state);
652 : }
653 :
654 7468 : Reduction LoadElimination::ReduceCompareMaps(Node* node) {
655 7398 : ZoneHandleSet<Map> const maps = CompareMapsParametersOf(node->op()).maps();
656 7398 : Node* const object = NodeProperties::GetValueInput(node, 0);
657 7398 : Node* const effect = NodeProperties::GetEffectInput(node);
658 : AbstractState const* state = node_states_.Get(effect);
659 7398 : if (state == nullptr) return NoChange();
660 : ZoneHandleSet<Map> object_maps;
661 6111 : if (state->LookupMaps(object, &object_maps)) {
662 230 : if (maps.contains(object_maps)) {
663 70 : Node* value = jsgraph()->TrueConstant();
664 70 : ReplaceWithValue(node, value, effect);
665 : return Replace(value);
666 : }
667 : // TODO(turbofan): Compute the intersection.
668 : }
669 6041 : return UpdateState(node, state);
670 : }
671 :
672 9390 : Reduction LoadElimination::ReduceEnsureWritableFastElements(Node* node) {
673 9390 : Node* const object = NodeProperties::GetValueInput(node, 0);
674 9390 : Node* const elements = NodeProperties::GetValueInput(node, 1);
675 9390 : Node* const effect = NodeProperties::GetEffectInput(node);
676 : AbstractState const* state = node_states_.Get(effect);
677 9390 : if (state == nullptr) return NoChange();
678 : // Check if the {elements} already have the fixed array map.
679 : ZoneHandleSet<Map> elements_maps;
680 : ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
681 2982 : if (state->LookupMaps(elements, &elements_maps) &&
682 1186 : fixed_array_maps.contains(elements_maps)) {
683 11 : ReplaceWithValue(node, elements, effect);
684 : return Replace(elements);
685 : }
686 : // We know that the resulting elements have the fixed array map.
687 1785 : state = state->SetMaps(node, fixed_array_maps, zone());
688 : // Kill the previous elements on {object}.
689 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
690 : MaybeHandle<Name>(), zone());
691 : // Add the new elements on {object}.
692 : state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
693 1785 : MaybeHandle<Name>(), zone());
694 1785 : return UpdateState(node, state);
695 : }
696 :
697 13040 : Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
698 13040 : GrowFastElementsParameters params = GrowFastElementsParametersOf(node->op());
699 13040 : Node* const object = NodeProperties::GetValueInput(node, 0);
700 13040 : Node* const effect = NodeProperties::GetEffectInput(node);
701 : AbstractState const* state = node_states_.Get(effect);
702 13040 : if (state == nullptr) return NoChange();
703 3933 : if (params.mode() == GrowFastElementsMode::kDoubleElements) {
704 : // We know that the resulting elements have the fixed double array map.
705 : state = state->SetMaps(
706 501 : node, ZoneHandleSet<Map>(factory()->fixed_double_array_map()), zone());
707 : } else {
708 : // We know that the resulting elements have the fixed array map or the COW
709 : // version thereof (if we didn't grow and it was already COW before).
710 : ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
711 3432 : fixed_array_maps.insert(factory()->fixed_cow_array_map(), zone());
712 3432 : state = state->SetMaps(node, fixed_array_maps, zone());
713 : }
714 : // Kill the previous elements on {object}.
715 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
716 : MaybeHandle<Name>(), zone());
717 : // Add the new elements on {object}.
718 : state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
719 3933 : MaybeHandle<Name>(), zone());
720 3933 : return UpdateState(node, state);
721 : }
722 :
723 938 : Reduction LoadElimination::ReduceTransitionElementsKind(Node* node) {
724 938 : ElementsTransition transition = ElementsTransitionOf(node->op());
725 938 : Node* const object = NodeProperties::GetValueInput(node, 0);
726 : Handle<Map> source_map(transition.source());
727 : Handle<Map> target_map(transition.target());
728 938 : Node* const effect = NodeProperties::GetEffectInput(node);
729 : AbstractState const* state = node_states_.Get(effect);
730 938 : if (state == nullptr) return NoChange();
731 699 : switch (transition.mode()) {
732 : case ElementsTransition::kFastTransition:
733 : break;
734 : case ElementsTransition::kSlowTransition:
735 : // Kill the elements as well.
736 : AliasStateInfo alias_info(state, object, source_map);
737 : state =
738 : state->KillField(alias_info, FieldIndexOf(JSObject::kElementsOffset),
739 435 : MaybeHandle<Name>(), zone());
740 435 : break;
741 : }
742 : ZoneHandleSet<Map> object_maps;
743 699 : if (state->LookupMaps(object, &object_maps)) {
744 191 : if (ZoneHandleSet<Map>(target_map).contains(object_maps)) {
745 : // The {object} already has the {target_map}, so this TransitionElements
746 : // {node} is fully redundant (independent of what {source_map} is).
747 : return Replace(effect);
748 : }
749 95 : if (object_maps.contains(ZoneHandleSet<Map>(source_map))) {
750 95 : object_maps.remove(source_map, zone());
751 95 : object_maps.insert(target_map, zone());
752 : AliasStateInfo alias_info(state, object, source_map);
753 95 : state = state->KillMaps(alias_info, zone());
754 95 : state = state->SetMaps(object, object_maps, zone());
755 : }
756 : } else {
757 : AliasStateInfo alias_info(state, object, source_map);
758 508 : state = state->KillMaps(alias_info, zone());
759 : }
760 603 : return UpdateState(node, state);
761 : }
762 :
763 1737 : Reduction LoadElimination::ReduceTransitionAndStoreElement(Node* node) {
764 579 : Node* const object = NodeProperties::GetValueInput(node, 0);
765 579 : Handle<Map> double_map(DoubleMapParameterOf(node->op()));
766 579 : Handle<Map> fast_map(FastMapParameterOf(node->op()));
767 579 : Node* const effect = NodeProperties::GetEffectInput(node);
768 : AbstractState const* state = node_states_.Get(effect);
769 579 : if (state == nullptr) return NoChange();
770 :
771 : // We need to add the double and fast maps to the set of possible maps for
772 : // this object, because we don't know which of those we'll transition to.
773 : // Additionally, we should kill all alias information.
774 : ZoneHandleSet<Map> object_maps;
775 272 : if (state->LookupMaps(object, &object_maps)) {
776 0 : object_maps.insert(double_map, zone());
777 0 : object_maps.insert(fast_map, zone());
778 : state = state->KillMaps(object, zone());
779 0 : state = state->SetMaps(object, object_maps, zone());
780 : }
781 : // Kill the elements as well.
782 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
783 : MaybeHandle<Name>(), zone());
784 272 : return UpdateState(node, state);
785 : }
786 :
787 1135571 : Reduction LoadElimination::ReduceLoadField(Node* node) {
788 1135557 : FieldAccess const& access = FieldAccessOf(node->op());
789 1135558 : Node* object = NodeProperties::GetValueInput(node, 0);
790 1135558 : Node* effect = NodeProperties::GetEffectInput(node);
791 1135557 : Node* control = NodeProperties::GetControlInput(node);
792 : AbstractState const* state = node_states_.Get(effect);
793 1135558 : if (state == nullptr) return NoChange();
794 905913 : if (access.offset == HeapObject::kMapOffset &&
795 : access.base_is_tagged == kTaggedBase) {
796 : DCHECK(IsAnyTagged(access.machine_type.representation()));
797 : ZoneHandleSet<Map> object_maps;
798 5090 : if (state->LookupMaps(object, &object_maps) && object_maps.size() == 1) {
799 14 : Node* value = jsgraph()->HeapConstant(object_maps[0]);
800 : NodeProperties::SetType(value, Type::OtherInternal());
801 123062 : ReplaceWithValue(node, value, effect);
802 14 : return Replace(value);
803 : }
804 : } else {
805 900837 : int field_index = FieldIndexOf(access);
806 900836 : if (field_index >= 0) {
807 1518562 : if (Node* replacement = state->LookupField(object, field_index)) {
808 : // Make sure we don't resurrect dead {replacement} nodes.
809 123048 : if (!replacement->IsDead()) {
810 : // Introduce a TypeGuard if the type of the {replacement} node is not
811 : // a subtype of the original {node}'s type.
812 123048 : if (!NodeProperties::GetType(replacement)
813 246096 : .Is(NodeProperties::GetType(node))) {
814 : Type replacement_type = Type::Intersect(
815 : NodeProperties::GetType(node),
816 1289 : NodeProperties::GetType(replacement), graph()->zone());
817 : replacement = effect =
818 : graph()->NewNode(common()->TypeGuard(replacement_type),
819 1289 : replacement, effect, control);
820 : NodeProperties::SetType(replacement, replacement_type);
821 : }
822 : ReplaceWithValue(node, replacement, effect);
823 : return Replace(replacement);
824 : }
825 : }
826 636233 : state = state->AddField(object, field_index, node, access.name, zone());
827 : }
828 : }
829 : Handle<Map> field_map;
830 782850 : if (access.map.ToHandle(&field_map)) {
831 6134 : state = state->SetMaps(node, ZoneHandleSet<Map>(field_map), zone());
832 : }
833 782850 : return UpdateState(node, state);
834 : }
835 :
836 1751593 : Reduction LoadElimination::ReduceStoreField(Node* node) {
837 1751593 : FieldAccess const& access = FieldAccessOf(node->op());
838 1751598 : Node* const object = NodeProperties::GetValueInput(node, 0);
839 1751602 : Node* const new_value = NodeProperties::GetValueInput(node, 1);
840 1751607 : Node* const effect = NodeProperties::GetEffectInput(node);
841 : AbstractState const* state = node_states_.Get(effect);
842 1751627 : if (state == nullptr) return NoChange();
843 1564015 : if (access.offset == HeapObject::kMapOffset &&
844 : access.base_is_tagged == kTaggedBase) {
845 : DCHECK(IsAnyTagged(access.machine_type.representation()));
846 : // Kill all potential knowledge about the {object}s map.
847 : state = state->KillMaps(object, zone());
848 158261 : Type const new_value_type = NodeProperties::GetType(new_value);
849 158261 : if (new_value_type.IsHeapConstant()) {
850 : // Record the new {object} map information.
851 : AllowHandleDereference handle_dereference;
852 : ZoneHandleSet<Map> object_maps(
853 158260 : Handle<Map>::cast(new_value_type.AsHeapConstant()->Value()));
854 158261 : state = state->SetMaps(object, object_maps, zone());
855 : }
856 : } else {
857 1405754 : int field_index = FieldIndexOf(access);
858 1405787 : if (field_index >= 0) {
859 1114962 : Node* const old_value = state->LookupField(object, field_index);
860 1114962 : if (old_value == new_value) {
861 : // This store is fully redundant.
862 : return Replace(effect);
863 : }
864 : // Kill all potentially aliasing fields and record the new value.
865 : state = state->KillField(object, field_index, access.name, zone());
866 : state =
867 1112456 : state->AddField(object, field_index, new_value, access.name, zone());
868 : } else {
869 : // Unsupported StoreField operator.
870 290825 : state = state->KillFields(object, access.name, zone());
871 : }
872 : }
873 1561597 : return UpdateState(node, state);
874 : }
875 :
876 57100 : Reduction LoadElimination::ReduceLoadElement(Node* node) {
877 36004 : Node* const object = NodeProperties::GetValueInput(node, 0);
878 36004 : Node* const index = NodeProperties::GetValueInput(node, 1);
879 36004 : Node* const effect = NodeProperties::GetEffectInput(node);
880 : AbstractState const* state = node_states_.Get(effect);
881 36004 : if (state == nullptr) return NoChange();
882 :
883 : // Only handle loads that do not require truncations.
884 21096 : ElementAccess const& access = ElementAccessOf(node->op());
885 40911 : switch (access.machine_type.representation()) {
886 : case MachineRepresentation::kNone:
887 : case MachineRepresentation::kBit:
888 0 : UNREACHABLE();
889 : break;
890 : case MachineRepresentation::kWord8:
891 : case MachineRepresentation::kWord16:
892 : case MachineRepresentation::kWord32:
893 : case MachineRepresentation::kWord64:
894 : case MachineRepresentation::kFloat32:
895 : // TODO(turbofan): Add support for doing the truncations.
896 : break;
897 : case MachineRepresentation::kFloat64:
898 : case MachineRepresentation::kSimd128:
899 : case MachineRepresentation::kTaggedSigned:
900 : case MachineRepresentation::kTaggedPointer:
901 : case MachineRepresentation::kTagged:
902 21096 : if (Node* replacement = state->LookupElement(
903 : object, index, access.machine_type.representation())) {
904 : // Make sure we don't resurrect dead {replacement} nodes.
905 : // Skip lowering if the type of the {replacement} node is not a subtype
906 : // of the original {node}'s type.
907 : // TODO(tebbi): We should insert a {TypeGuard} for the intersection of
908 : // these two types here once we properly handle {Type::None} everywhere.
909 3888 : if (!replacement->IsDead() && NodeProperties::GetType(replacement)
910 3888 : .Is(NodeProperties::GetType(node))) {
911 1281 : ReplaceWithValue(node, replacement, effect);
912 : return Replace(replacement);
913 : }
914 : }
915 : state = state->AddElement(object, index, node,
916 19815 : access.machine_type.representation(), zone());
917 19814 : return UpdateState(node, state);
918 : }
919 : return NoChange();
920 : }
921 :
922 62913 : Reduction LoadElimination::ReduceStoreElement(Node* node) {
923 62913 : ElementAccess const& access = ElementAccessOf(node->op());
924 62913 : Node* const object = NodeProperties::GetValueInput(node, 0);
925 62913 : Node* const index = NodeProperties::GetValueInput(node, 1);
926 62913 : Node* const new_value = NodeProperties::GetValueInput(node, 2);
927 62913 : Node* const effect = NodeProperties::GetEffectInput(node);
928 : AbstractState const* state = node_states_.Get(effect);
929 62913 : if (state == nullptr) return NoChange();
930 : Node* const old_value =
931 86099 : state->LookupElement(object, index, access.machine_type.representation());
932 43060 : if (old_value == new_value) {
933 : // This store is fully redundant.
934 : return Replace(effect);
935 : }
936 : // Kill all potentially aliasing elements.
937 43039 : state = state->KillElement(object, index, zone());
938 : // Only record the new value if the store doesn't have an implicit truncation.
939 : switch (access.machine_type.representation()) {
940 : case MachineRepresentation::kNone:
941 : case MachineRepresentation::kBit:
942 0 : UNREACHABLE();
943 : break;
944 : case MachineRepresentation::kWord8:
945 : case MachineRepresentation::kWord16:
946 : case MachineRepresentation::kWord32:
947 : case MachineRepresentation::kWord64:
948 : case MachineRepresentation::kFloat32:
949 : // TODO(turbofan): Add support for doing the truncations.
950 : break;
951 : case MachineRepresentation::kFloat64:
952 : case MachineRepresentation::kSimd128:
953 : case MachineRepresentation::kTaggedSigned:
954 : case MachineRepresentation::kTaggedPointer:
955 : case MachineRepresentation::kTagged:
956 : state = state->AddElement(object, index, new_value,
957 43039 : access.machine_type.representation(), zone());
958 43039 : break;
959 : }
960 43039 : return UpdateState(node, state);
961 : }
962 :
963 5840 : Reduction LoadElimination::ReduceStoreTypedElement(Node* node) {
964 5840 : Node* const effect = NodeProperties::GetEffectInput(node);
965 : AbstractState const* state = node_states_.Get(effect);
966 5840 : if (state == nullptr) return NoChange();
967 4495 : return UpdateState(node, state);
968 : }
969 :
970 227916 : LoadElimination::AbstractState const* LoadElimination::UpdateStateForPhi(
971 : AbstractState const* state, Node* effect_phi, Node* phi) {
972 227916 : int predecessor_count = phi->InputCount() - 1;
973 : // TODO(jarin) Consider doing a union here. At the moment, we just keep this
974 : // consistent with AbstractState::Merge.
975 :
976 : // Check if all the inputs have the same maps.
977 : AbstractState const* input_state =
978 227916 : node_states_.Get(NodeProperties::GetEffectInput(effect_phi, 0));
979 : ZoneHandleSet<Map> object_maps;
980 227915 : if (!input_state->LookupMaps(phi->InputAt(0), &object_maps)) return state;
981 751 : for (int i = 1; i < predecessor_count; i++) {
982 : input_state =
983 677 : node_states_.Get(NodeProperties::GetEffectInput(effect_phi, i));
984 : ZoneHandleSet<Map> input_maps;
985 1316 : if (!input_state->LookupMaps(phi->InputAt(i), &input_maps)) return state;
986 38 : if (input_maps != object_maps) return state;
987 : }
988 36 : return state->SetMaps(phi, object_maps, zone());
989 : }
990 :
991 977423 : Reduction LoadElimination::ReduceEffectPhi(Node* node) {
992 608192 : Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
993 1065234 : Node* const control = NodeProperties::GetControlInput(node);
994 : AbstractState const* state0 = node_states_.Get(effect0);
995 608194 : if (state0 == nullptr) return NoChange();
996 457041 : if (control->opcode() == IrOpcode::kLoop) {
997 : // Here we rely on having only reducible loops:
998 : // The loop entry edge always dominates the header, so we can just take
999 : // the state from the first input, and compute the loop state based on it.
1000 87810 : AbstractState const* state = ComputeLoopState(node, state0);
1001 87810 : return UpdateState(node, state);
1002 : }
1003 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
1004 :
1005 : // Shortcut for the case when we do not know anything about some input.
1006 369231 : int const input_count = node->op()->EffectInputCount();
1007 1675482 : for (int i = 1; i < input_count; ++i) {
1008 1383182 : Node* const effect = NodeProperties::GetEffectInput(node, i);
1009 1383182 : if (node_states_.Get(effect) == nullptr) return NoChange();
1010 : }
1011 :
1012 : // Make a copy of the first input's state and merge with the state
1013 : // from other inputs.
1014 292300 : AbstractState* state = new (zone()) AbstractState(*state0);
1015 862485 : for (int i = 1; i < input_count; ++i) {
1016 570179 : Node* const input = NodeProperties::GetEffectInput(node, i);
1017 570181 : state->Merge(node_states_.Get(input), zone());
1018 : }
1019 :
1020 : // For each phi, try to compute the new state for the phi from
1021 : // the inputs.
1022 : AbstractState const* state_with_phis = state;
1023 3114797 : for (Node* use : control->uses()) {
1024 1265093 : if (use->opcode() == IrOpcode::kPhi) {
1025 227917 : state_with_phis = UpdateStateForPhi(state_with_phis, node, use);
1026 : }
1027 : }
1028 :
1029 292305 : return UpdateState(node, state_with_phis);
1030 : }
1031 :
1032 0 : Reduction LoadElimination::ReduceStart(Node* node) {
1033 456088 : return UpdateState(node, empty_state());
1034 : }
1035 :
1036 36711073 : Reduction LoadElimination::ReduceOtherNode(Node* node) {
1037 29602703 : if (node->op()->EffectInputCount() == 1) {
1038 9436903 : if (node->op()->EffectOutputCount() == 1) {
1039 8598428 : Node* const effect = NodeProperties::GetEffectInput(node);
1040 : AbstractState const* state = node_states_.Get(effect);
1041 : // If we do not know anything about the predecessor, do not propagate
1042 : // just yet because we will have to recompute anyway once we compute
1043 : // the predecessor.
1044 8598583 : if (state == nullptr) return NoChange();
1045 : // Check if this {node} has some uncontrolled side effects.
1046 7108370 : if (!node->op()->HasProperty(Operator::kNoWrite)) {
1047 2220168 : state = empty_state();
1048 : }
1049 7108370 : return UpdateState(node, state);
1050 : } else {
1051 : // Effect terminators should be handled specially.
1052 : return NoChange();
1053 : }
1054 : }
1055 : DCHECK_EQ(0, node->op()->EffectInputCount());
1056 : DCHECK_EQ(0, node->op()->EffectOutputCount());
1057 : return NoChange();
1058 : }
1059 :
1060 10434086 : Reduction LoadElimination::UpdateState(Node* node, AbstractState const* state) {
1061 : AbstractState const* original = node_states_.Get(node);
1062 : // Only signal that the {node} has Changed, if the information about {state}
1063 : // has changed wrt. the {original}.
1064 10434086 : if (state != original) {
1065 10212333 : if (original == nullptr || !state->Equals(original)) {
1066 10156270 : node_states_.Set(node, state);
1067 : return Changed(node);
1068 : }
1069 : }
1070 : return NoChange();
1071 : }
1072 :
1073 87809 : LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
1074 : Node* node, AbstractState const* state) const {
1075 87809 : Node* const control = NodeProperties::GetControlInput(node);
1076 : struct TransitionElementsKindInfo {
1077 : ElementsTransition transition;
1078 : Node* object;
1079 : };
1080 : ZoneVector<TransitionElementsKindInfo> element_transitions_(zone());
1081 87810 : ZoneQueue<Node*> queue(zone());
1082 : ZoneSet<Node*> visited(zone());
1083 : visited.insert(node);
1084 351248 : for (int i = 1; i < control->InputCount(); ++i) {
1085 263428 : queue.push(node->InputAt(i));
1086 : }
1087 884057 : while (!queue.empty()) {
1088 857407 : Node* const current = queue.front();
1089 : queue.pop();
1090 857383 : if (visited.find(current) == visited.end()) {
1091 : visited.insert(current);
1092 3104799 : if (!current->op()->HasProperty(Operator::kNoWrite)) {
1093 110053 : switch (current->opcode()) {
1094 : case IrOpcode::kEnsureWritableFastElements: {
1095 744 : Node* const object = NodeProperties::GetValueInput(current, 0);
1096 : state = state->KillField(object,
1097 : FieldIndexOf(JSObject::kElementsOffset),
1098 : MaybeHandle<Name>(), zone());
1099 744 : break;
1100 : }
1101 : case IrOpcode::kMaybeGrowFastElements: {
1102 1899 : Node* const object = NodeProperties::GetValueInput(current, 0);
1103 : state = state->KillField(object,
1104 : FieldIndexOf(JSObject::kElementsOffset),
1105 : MaybeHandle<Name>(), zone());
1106 1899 : break;
1107 : }
1108 : case IrOpcode::kTransitionElementsKind: {
1109 240 : ElementsTransition transition = ElementsTransitionOf(current->op());
1110 240 : Node* const object = NodeProperties::GetValueInput(current, 0);
1111 : ZoneHandleSet<Map> object_maps;
1112 720 : if (!state->LookupMaps(object, &object_maps) ||
1113 : !ZoneHandleSet<Map>(transition.target())
1114 452 : .contains(object_maps)) {
1115 268 : element_transitions_.push_back({transition, object});
1116 : }
1117 : break;
1118 : }
1119 : case IrOpcode::kTransitionAndStoreElement: {
1120 438 : Node* const object = NodeProperties::GetValueInput(current, 0);
1121 : // Invalidate what we know about the {object}s map.
1122 : state = state->KillMaps(object, zone());
1123 : // Kill the elements as well.
1124 : state = state->KillField(object,
1125 : FieldIndexOf(JSObject::kElementsOffset),
1126 : MaybeHandle<Name>(), zone());
1127 438 : break;
1128 : }
1129 : case IrOpcode::kStoreField: {
1130 37807 : FieldAccess const& access = FieldAccessOf(current->op());
1131 37807 : Node* const object = NodeProperties::GetValueInput(current, 0);
1132 37807 : if (access.offset == HeapObject::kMapOffset) {
1133 : // Invalidate what we know about the {object}s map.
1134 : state = state->KillMaps(object, zone());
1135 : } else {
1136 31526 : int field_index = FieldIndexOf(access);
1137 31526 : if (field_index < 0) {
1138 6 : state = state->KillFields(object, access.name, zone());
1139 : } else {
1140 : state =
1141 31520 : state->KillField(object, field_index, access.name, zone());
1142 : }
1143 : }
1144 : break;
1145 : }
1146 : case IrOpcode::kStoreElement: {
1147 5501 : Node* const object = NodeProperties::GetValueInput(current, 0);
1148 5501 : Node* const index = NodeProperties::GetValueInput(current, 1);
1149 5501 : state = state->KillElement(object, index, zone());
1150 5501 : break;
1151 : }
1152 : case IrOpcode::kStoreTypedElement: {
1153 : // Doesn't affect anything we track with the state currently.
1154 : break;
1155 : }
1156 : default:
1157 61159 : return empty_state();
1158 : }
1159 : }
1160 4580649 : for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
1161 1598194 : queue.push(NodeProperties::GetEffectInput(current, i));
1162 : }
1163 : }
1164 : }
1165 :
1166 : // Finally, we apply the element transitions. For each transition, we will try
1167 : // to only invalidate information about nodes that can have the transition's
1168 : // source map. The trouble is that an object can be transitioned by some other
1169 : // transition to the source map. In that case, the other transition will
1170 : // invalidate the information, so we are mostly fine.
1171 : //
1172 : // The only bad case is
1173 : //
1174 : // mapA ---fast---> mapB ---slow---> mapC
1175 : //
1176 : // If we process the slow transition first on an object that has mapA, we will
1177 : // ignore the transition because the object does not have its source map
1178 : // (mapB). When we later process the fast transition, we invalidate the
1179 : // object's map, but we keep the information about the object's elements. This
1180 : // is wrong because the elements will be overwritten by the slow transition.
1181 : //
1182 : // Note that the slow-slow case is fine because either of the slow transition
1183 : // will invalidate the elements field, so the processing order does not
1184 : // matter.
1185 : //
1186 : // To handle the bad case properly, we first kill the maps using all
1187 : // transitions. We kill the the fields later when all the transitions are
1188 : // already reflected in the map information.
1189 :
1190 53434 : for (const TransitionElementsKindInfo& t : element_transitions_) {
1191 134 : AliasStateInfo alias_info(state, t.object, t.transition.source());
1192 134 : state = state->KillMaps(alias_info, zone());
1193 : }
1194 53434 : for (const TransitionElementsKindInfo& t : element_transitions_) {
1195 134 : switch (t.transition.mode()) {
1196 : case ElementsTransition::kFastTransition:
1197 : break;
1198 : case ElementsTransition::kSlowTransition: {
1199 102 : AliasStateInfo alias_info(state, t.object, t.transition.source());
1200 : state = state->KillField(alias_info,
1201 : FieldIndexOf(JSObject::kElementsOffset),
1202 102 : MaybeHandle<Name>(), zone());
1203 : break;
1204 : }
1205 : }
1206 : }
1207 : return state;
1208 : }
1209 :
1210 : // static
1211 0 : int LoadElimination::FieldIndexOf(int offset) {
1212 : DCHECK(IsAligned(offset, kTaggedSize));
1213 2269843 : int field_index = offset / kTaggedSize;
1214 2269843 : if (field_index >= static_cast<int>(kMaxTrackedFields)) return -1;
1215 : DCHECK_LT(0, field_index);
1216 1905764 : return field_index - 1;
1217 : }
1218 :
1219 : // static
1220 2338095 : int LoadElimination::FieldIndexOf(FieldAccess const& access) {
1221 2338095 : MachineRepresentation rep = access.machine_type.representation();
1222 : switch (rep) {
1223 : case MachineRepresentation::kNone:
1224 : case MachineRepresentation::kBit:
1225 : case MachineRepresentation::kSimd128:
1226 0 : UNREACHABLE();
1227 : break;
1228 : case MachineRepresentation::kWord32:
1229 : if (kInt32Size != kTaggedSize) {
1230 : return -1; // We currently only track tagged pointer size fields.
1231 : }
1232 : break;
1233 : case MachineRepresentation::kWord64:
1234 : if (kInt64Size != kTaggedSize) {
1235 : return -1; // We currently only track tagged pointer size fields.
1236 : }
1237 : break;
1238 : case MachineRepresentation::kWord8:
1239 : case MachineRepresentation::kWord16:
1240 : case MachineRepresentation::kFloat32:
1241 : return -1; // Currently untracked.
1242 : case MachineRepresentation::kFloat64:
1243 : if (kDoubleSize != kTaggedSize) {
1244 : return -1; // We currently only track tagged pointer size fields.
1245 : }
1246 : break;
1247 : case MachineRepresentation::kTaggedSigned:
1248 : case MachineRepresentation::kTaggedPointer:
1249 : case MachineRepresentation::kTagged:
1250 : // TODO(bmeurer): Check that we never do overlapping load/stores of
1251 : // individual parts of Float64 values.
1252 : break;
1253 : }
1254 2334054 : if (access.base_is_tagged != kTaggedBase) {
1255 : return -1; // We currently only track tagged objects.
1256 : }
1257 4539686 : return FieldIndexOf(access.offset);
1258 : }
1259 :
1260 1289 : CommonOperatorBuilder* LoadElimination::common() const {
1261 1289 : return jsgraph()->common();
1262 : }
1263 :
1264 2578 : Graph* LoadElimination::graph() const { return jsgraph()->graph(); }
1265 :
1266 0 : Isolate* LoadElimination::isolate() const { return jsgraph()->isolate(); }
1267 :
1268 5729 : Factory* LoadElimination::factory() const { return jsgraph()->factory(); }
1269 :
1270 : } // namespace compiler
1271 : } // namespace internal
1272 183867 : } // namespace v8
|
