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/access-builder.h"
8 : #include "src/compiler/common-operator.h"
9 : #include "src/compiler/js-graph.h"
10 : #include "src/compiler/node-properties.h"
11 : #include "src/compiler/simplified-operator.h"
12 : #include "src/heap/factory.h"
13 : #include "src/objects-inl.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 : namespace compiler {
18 :
19 : namespace {
20 :
21 341147368 : bool IsRename(Node* node) {
22 341147368 : switch (node->opcode()) {
23 : case IrOpcode::kCheckHeapObject:
24 : case IrOpcode::kFinishRegion:
25 : case IrOpcode::kTypeGuard:
26 831884 : return !node->IsDead();
27 : default:
28 : return false;
29 : }
30 : }
31 :
32 338989865 : Node* ResolveRenames(Node* node) {
33 339895521 : while (IsRename(node)) {
34 : node = node->InputAt(0);
35 : }
36 338989864 : return node;
37 : }
38 :
39 1850936 : bool MayAlias(Node* a, Node* b) {
40 1850936 : if (a != b) {
41 1173841 : if (!NodeProperties::GetType(a).Maybe(NodeProperties::GetType(b))) {
42 : return false;
43 863923 : } else if (IsRename(b)) {
44 23165 : return MayAlias(a, b->InputAt(0));
45 840758 : } else if (IsRename(a)) {
46 355892 : return MayAlias(a->InputAt(0), b);
47 484866 : } else if (b->opcode() == IrOpcode::kAllocate) {
48 81110 : switch (a->opcode()) {
49 : case IrOpcode::kAllocate:
50 : case IrOpcode::kHeapConstant:
51 : case IrOpcode::kParameter:
52 : return false;
53 : default:
54 : break;
55 : }
56 403756 : } else if (a->opcode() == IrOpcode::kAllocate) {
57 133543 : switch (b->opcode()) {
58 : case IrOpcode::kHeapConstant:
59 : case IrOpcode::kParameter:
60 : return false;
61 : default:
62 : break;
63 : }
64 : }
65 : }
66 : return true;
67 : }
68 :
69 : bool MustAlias(Node* a, Node* b) {
70 169329684 : return ResolveRenames(a) == ResolveRenames(b);
71 : }
72 :
73 : } // namespace
74 :
75 36715005 : Reduction LoadElimination::Reduce(Node* node) {
76 36715005 : if (FLAG_trace_turbo_load_elimination) {
77 0 : if (node->op()->EffectInputCount() > 0) {
78 0 : PrintF(" visit #%d:%s", node->id(), node->op()->mnemonic());
79 0 : if (node->op()->ValueInputCount() > 0) {
80 0 : PrintF("(");
81 0 : for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
82 0 : if (i > 0) PrintF(", ");
83 0 : Node* const value = NodeProperties::GetValueInput(node, i);
84 0 : PrintF("#%d:%s", value->id(), value->op()->mnemonic());
85 : }
86 0 : PrintF(")");
87 : }
88 0 : PrintF("\n");
89 817 : for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
90 0 : Node* const effect = NodeProperties::GetEffectInput(node, i);
91 0 : if (AbstractState const* const state = node_states_.Get(effect)) {
92 : PrintF(" state[%i]: #%d:%s\n", i, effect->id(),
93 0 : effect->op()->mnemonic());
94 0 : state->Print();
95 : } else {
96 : PrintF(" no state[%i]: #%d:%s\n", i, effect->id(),
97 0 : effect->op()->mnemonic());
98 : }
99 : }
100 : }
101 : }
102 36715822 : switch (node->opcode()) {
103 : case IrOpcode::kMapGuard:
104 8870 : return ReduceMapGuard(node);
105 : case IrOpcode::kCheckMaps:
106 148802 : return ReduceCheckMaps(node);
107 : case IrOpcode::kCompareMaps:
108 9383 : return ReduceCompareMaps(node);
109 : case IrOpcode::kEnsureWritableFastElements:
110 6779 : return ReduceEnsureWritableFastElements(node);
111 : case IrOpcode::kMaybeGrowFastElements:
112 9965 : return ReduceMaybeGrowFastElements(node);
113 : case IrOpcode::kTransitionElementsKind:
114 954 : return ReduceTransitionElementsKind(node);
115 : case IrOpcode::kLoadField:
116 1543112 : return ReduceLoadField(node, FieldAccessOf(node->op()));
117 : case IrOpcode::kStoreField:
118 2411311 : return ReduceStoreField(node, FieldAccessOf(node->op()));
119 : case IrOpcode::kStoreMessage:
120 55978 : return ReduceStoreField(node, AccessBuilder::ForExternalIntPtr());
121 : case IrOpcode::kLoadMessage:
122 50513 : return ReduceLoadField(node, AccessBuilder::ForExternalIntPtr());
123 : case IrOpcode::kLoadElement:
124 31788 : return ReduceLoadElement(node);
125 : case IrOpcode::kStoreElement:
126 58164 : return ReduceStoreElement(node);
127 : case IrOpcode::kTransitionAndStoreElement:
128 546 : return ReduceTransitionAndStoreElement(node);
129 : case IrOpcode::kStoreTypedElement:
130 6620 : return ReduceStoreTypedElement(node);
131 : case IrOpcode::kEffectPhi:
132 607919 : return ReduceEffectPhi(node);
133 : case IrOpcode::kDead:
134 : break;
135 : case IrOpcode::kStart:
136 : return ReduceStart(node);
137 : default:
138 31289081 : return ReduceOtherNode(node);
139 : }
140 : return NoChange();
141 : }
142 :
143 : namespace {
144 :
145 : bool IsCompatible(MachineRepresentation r1, MachineRepresentation r2) {
146 1676 : if (r1 == r2) return true;
147 232 : return IsAnyTagged(r1) && IsAnyTagged(r2);
148 : }
149 :
150 : } // namespace
151 :
152 40004 : Node* LoadElimination::AbstractElements::Lookup(
153 : Node* object, Node* index, MachineRepresentation representation) const {
154 349251 : for (Element const element : elements_) {
155 310916 : if (element.object == nullptr) continue;
156 : DCHECK_NOT_NULL(element.index);
157 : DCHECK_NOT_NULL(element.value);
158 260661 : if (MustAlias(object, element.object) && MustAlias(index, element.index) &&
159 : IsCompatible(representation, element.representation)) {
160 : return element.value;
161 : }
162 : }
163 : return nullptr;
164 : }
165 :
166 : LoadElimination::AbstractElements const*
167 37370 : LoadElimination::AbstractElements::Kill(Node* object, Node* index,
168 : Zone* zone) const {
169 79908 : for (Element const element : this->elements_) {
170 75200 : if (element.object == nullptr) continue;
171 52865 : if (MayAlias(object, element.object)) {
172 : AbstractElements* that = new (zone) AbstractElements(zone);
173 555254 : for (Element const element : this->elements_) {
174 261296 : if (element.object == nullptr) continue;
175 : DCHECK_NOT_NULL(element.index);
176 : DCHECK_NOT_NULL(element.value);
177 375798 : if (!MayAlias(object, element.object) ||
178 351704 : !NodeProperties::GetType(index).Maybe(
179 : NodeProperties::GetType(element.index))) {
180 116654 : that->elements_[that->next_index_++] = element;
181 : }
182 : }
183 32662 : that->next_index_ %= arraysize(elements_);
184 : return that;
185 : }
186 : }
187 4708 : return this;
188 : }
189 :
190 14538 : bool LoadElimination::AbstractElements::Equals(
191 : AbstractElements const* that) const {
192 14538 : if (this == that) return true;
193 74476 : for (size_t i = 0; i < arraysize(elements_); ++i) {
194 35693 : Element this_element = this->elements_[i];
195 35693 : if (this_element.object == nullptr) continue;
196 13965 : for (size_t j = 0;; ++j) {
197 20461 : if (j == arraysize(elements_)) return false;
198 19280 : Element that_element = that->elements_[j];
199 19280 : if (this_element.object == that_element.object &&
200 5322 : this_element.index == that_element.index &&
201 : this_element.value == that_element.value) {
202 : break;
203 : }
204 : }
205 : }
206 61615 : for (size_t i = 0; i < arraysize(elements_); ++i) {
207 29433 : Element that_element = that->elements_[i];
208 29433 : if (that_element.object == nullptr) continue;
209 9155 : for (size_t j = 0;; ++j) {
210 14493 : if (j == arraysize(elements_)) return false;
211 13732 : Element this_element = this->elements_[j];
212 13732 : if (that_element.object == this_element.object &&
213 4577 : that_element.index == this_element.index &&
214 : that_element.value == this_element.value) {
215 : break;
216 : }
217 : }
218 : }
219 : return true;
220 : }
221 :
222 : LoadElimination::AbstractElements const*
223 7197 : LoadElimination::AbstractElements::Merge(AbstractElements const* that,
224 : Zone* zone) const {
225 7197 : if (this->Equals(that)) return this;
226 : AbstractElements* copy = new (zone) AbstractElements(zone);
227 13617 : for (Element const this_element : this->elements_) {
228 12104 : if (this_element.object == nullptr) continue;
229 14590 : for (Element const that_element : that->elements_) {
230 13219 : if (this_element.object == that_element.object &&
231 986 : this_element.index == that_element.index &&
232 : this_element.value == that_element.value) {
233 979 : copy->elements_[copy->next_index_++] = this_element;
234 979 : break;
235 : }
236 : }
237 : }
238 1513 : copy->next_index_ %= arraysize(elements_);
239 1513 : return copy;
240 : }
241 :
242 0 : void LoadElimination::AbstractElements::Print() const {
243 0 : for (Element const& element : elements_) {
244 0 : if (element.object) {
245 : PrintF(" #%d:%s @ #%d:%s -> #%d:%s\n", element.object->id(),
246 : element.object->op()->mnemonic(), element.index->id(),
247 0 : element.index->op()->mnemonic(), element.value->id(),
248 0 : element.value->op()->mnemonic());
249 : }
250 : }
251 0 : }
252 :
253 761840 : Node* LoadElimination::AbstractField::Lookup(Node* object) const {
254 169590528 : for (auto pair : info_for_node_) {
255 169070699 : if (pair.first->IsDead()) continue;
256 169070699 : if (MustAlias(object, pair.first)) return pair.second.value;
257 : }
258 : return nullptr;
259 : }
260 :
261 : namespace {
262 :
263 : bool MayAlias(MaybeHandle<Name> x, MaybeHandle<Name> y) {
264 508831 : if (!x.address()) return true;
265 298200 : if (!y.address()) return true;
266 228066 : if (x.address() != y.address()) return false;
267 : return true;
268 : }
269 :
270 : } // namespace
271 :
272 : class LoadElimination::AliasStateInfo {
273 : public:
274 : AliasStateInfo(const AbstractState* state, Node* object, Handle<Map> map)
275 1313 : : state_(state), object_(object), map_(map) {}
276 : AliasStateInfo(const AbstractState* state, Node* object)
277 2362209 : : state_(state), object_(object) {}
278 :
279 : bool MayAlias(Node* other) const;
280 :
281 : private:
282 : const AbstractState* state_;
283 : Node* object_;
284 : MaybeHandle<Map> map_;
285 : };
286 :
287 26624750 : LoadElimination::AbstractField const* LoadElimination::AbstractField::Kill(
288 : const AliasStateInfo& alias_info, MaybeHandle<Name> name,
289 : Zone* zone) const {
290 239176613 : for (auto pair : this->info_for_node_) {
291 213055602 : if (pair.first->IsDead()) continue;
292 213055602 : if (alias_info.MayAlias(pair.first)) {
293 : AbstractField* that = new (zone) AbstractField(zone);
294 1268187 : for (auto pair : this->info_for_node_) {
295 1273279 : if (!alias_info.MayAlias(pair.first) ||
296 : !MayAlias(name, pair.second.name)) {
297 : that->info_for_node_.insert(pair);
298 : }
299 : }
300 : return that;
301 : }
302 : }
303 : return this;
304 : }
305 :
306 0 : void LoadElimination::AbstractField::Print() const {
307 0 : for (auto pair : info_for_node_) {
308 : PrintF(" #%d:%s -> #%d:%s\n", pair.first->id(),
309 : pair.first->op()->mnemonic(), pair.second.value->id(),
310 0 : pair.second.value->op()->mnemonic());
311 : }
312 0 : }
313 :
314 0 : LoadElimination::AbstractMaps::AbstractMaps(Zone* zone)
315 0 : : info_for_node_(zone) {}
316 :
317 115685 : LoadElimination::AbstractMaps::AbstractMaps(Node* object,
318 : ZoneHandleSet<Map> maps, Zone* zone)
319 : : info_for_node_(zone) {
320 115685 : object = ResolveRenames(object);
321 231370 : info_for_node_.insert(std::make_pair(object, maps));
322 115685 : }
323 :
324 92403 : bool LoadElimination::AbstractMaps::Lookup(
325 : Node* object, ZoneHandleSet<Map>* object_maps) const {
326 92403 : auto it = info_for_node_.find(ResolveRenames(object));
327 92403 : if (it == info_for_node_.end()) return false;
328 47708 : *object_maps = it->second;
329 47708 : return true;
330 : }
331 :
332 95829 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Kill(
333 : const AliasStateInfo& alias_info, Zone* zone) const {
334 28237434 : for (auto pair : this->info_for_node_) {
335 28164476 : if (alias_info.MayAlias(pair.first)) {
336 : AbstractMaps* that = new (zone) AbstractMaps(zone);
337 55556 : for (auto pair : this->info_for_node_) {
338 32685 : if (!alias_info.MayAlias(pair.first)) that->info_for_node_.insert(pair);
339 : }
340 : return that;
341 : }
342 : }
343 : return this;
344 : }
345 :
346 32503 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Merge(
347 : AbstractMaps const* that, Zone* zone) const {
348 32503 : if (this->Equals(that)) return this;
349 : AbstractMaps* copy = new (zone) AbstractMaps(zone);
350 25749 : for (auto this_it : this->info_for_node_) {
351 15770 : Node* this_object = this_it.first;
352 15770 : ZoneHandleSet<Map> this_maps = this_it.second;
353 : auto that_it = that->info_for_node_.find(this_object);
354 15770 : if (that_it != that->info_for_node_.end() && that_it->second == this_maps) {
355 : copy->info_for_node_.insert(this_it);
356 : }
357 : }
358 9979 : return copy;
359 : }
360 :
361 122409 : LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Extend(
362 : Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
363 : AbstractMaps* that = new (zone) AbstractMaps(zone);
364 : that->info_for_node_ = this->info_for_node_;
365 122409 : object = ResolveRenames(object);
366 122409 : that->info_for_node_[object] = maps;
367 122409 : return that;
368 : }
369 :
370 0 : void LoadElimination::AbstractMaps::Print() const {
371 : AllowHandleDereference allow_handle_dereference;
372 0 : StdoutStream os;
373 0 : for (auto pair : info_for_node_) {
374 0 : os << " #" << pair.first->id() << ":" << pair.first->op()->mnemonic()
375 : << std::endl;
376 : ZoneHandleSet<Map> const& maps = pair.second;
377 0 : for (size_t i = 0; i < maps.size(); ++i) {
378 0 : os << " - " << Brief(*maps[i]) << std::endl;
379 : }
380 : }
381 0 : }
382 :
383 61276 : bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
384 61276 : if (this->elements_) {
385 7355 : if (!that->elements_ || !that->elements_->Equals(this->elements_)) {
386 : return false;
387 : }
388 53921 : } else if (that->elements_) {
389 : return false;
390 : }
391 3885279 : for (size_t i = 0u; i < arraysize(fields_); ++i) {
392 1913360 : AbstractField const* this_field = this->fields_[i];
393 1913360 : AbstractField const* that_field = that->fields_[i];
394 1913360 : if (this_field) {
395 147826 : if (!that_field || !that_field->Equals(this_field)) return false;
396 1839446 : } else if (that_field) {
397 : return false;
398 : }
399 : }
400 59700 : if (this->maps_) {
401 40556 : if (!that->maps_ || !that->maps_->Equals(this->maps_)) {
402 : return false;
403 : }
404 39422 : } else if (that->maps_) {
405 : return false;
406 : }
407 : return true;
408 : }
409 :
410 713775 : void LoadElimination::AbstractState::Merge(AbstractState const* that,
411 : Zone* zone) {
412 : // Merge the information we have about the elements.
413 713775 : if (this->elements_) {
414 11800 : this->elements_ = that->elements_
415 : ? that->elements_->Merge(this->elements_, zone)
416 11800 : : nullptr;
417 : }
418 :
419 : // Merge the information we have about the fields.
420 46394873 : for (size_t i = 0; i < arraysize(fields_); ++i) {
421 22840549 : if (this->fields_[i]) {
422 332282 : if (that->fields_[i]) {
423 263129 : this->fields_[i] = this->fields_[i]->Merge(that->fields_[i], zone);
424 : } else {
425 69153 : this->fields_[i] = nullptr;
426 : }
427 : }
428 : }
429 :
430 : // Merge the information we have about the maps.
431 713775 : if (this->maps_) {
432 40884 : this->maps_ = that->maps_ ? that->maps_->Merge(this->maps_, zone) : nullptr;
433 : }
434 713775 : }
435 :
436 0 : bool LoadElimination::AbstractState::LookupMaps(
437 : Node* object, ZoneHandleSet<Map>* object_map) const {
438 358305 : return this->maps_ && this->maps_->Lookup(object, object_map);
439 : }
440 :
441 238094 : LoadElimination::AbstractState const* LoadElimination::AbstractState::SetMaps(
442 : Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
443 238094 : AbstractState* that = new (zone) AbstractState(*this);
444 238094 : if (that->maps_) {
445 122409 : that->maps_ = that->maps_->Extend(object, maps, zone);
446 : } else {
447 231370 : that->maps_ = new (zone) AbstractMaps(object, maps, zone);
448 : }
449 238094 : return that;
450 : }
451 :
452 172217 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
453 : const AliasStateInfo& alias_info, Zone* zone) const {
454 172217 : if (this->maps_) {
455 95829 : AbstractMaps const* that_maps = this->maps_->Kill(alias_info, zone);
456 95829 : if (this->maps_ != that_maps) {
457 22871 : AbstractState* that = new (zone) AbstractState(*this);
458 22871 : that->maps_ = that_maps;
459 22871 : return that;
460 : }
461 : }
462 : return this;
463 : }
464 :
465 0 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
466 : Node* object, Zone* zone) const {
467 : AliasStateInfo alias_info(this, object);
468 171447 : return KillMaps(alias_info, zone);
469 : }
470 :
471 0 : Node* LoadElimination::AbstractState::LookupElement(
472 : Node* object, Node* index, MachineRepresentation representation) const {
473 62625 : if (this->elements_) {
474 40004 : return this->elements_->Lookup(object, index, representation);
475 : }
476 : return nullptr;
477 : }
478 :
479 : LoadElimination::AbstractState const*
480 61309 : LoadElimination::AbstractState::AddElement(Node* object, Node* index,
481 : Node* value,
482 : MachineRepresentation representation,
483 : Zone* zone) const {
484 61309 : AbstractState* that = new (zone) AbstractState(*this);
485 61309 : if (that->elements_) {
486 : that->elements_ =
487 38688 : that->elements_->Extend(object, index, value, representation, zone);
488 : } else {
489 : that->elements_ =
490 22621 : new (zone) AbstractElements(object, index, value, representation, zone);
491 : }
492 61309 : return that;
493 : }
494 :
495 : LoadElimination::AbstractState const*
496 49026 : LoadElimination::AbstractState::KillElement(Node* object, Node* index,
497 : Zone* zone) const {
498 49026 : if (this->elements_) {
499 : AbstractElements const* that_elements =
500 37370 : this->elements_->Kill(object, index, zone);
501 37370 : if (this->elements_ != that_elements) {
502 32662 : AbstractState* that = new (zone) AbstractState(*this);
503 32662 : that->elements_ = that_elements;
504 32662 : return that;
505 : }
506 : }
507 : return this;
508 : }
509 :
510 1652848 : LoadElimination::AbstractState const* LoadElimination::AbstractState::AddField(
511 : Node* object, size_t index, Node* value, MaybeHandle<Name> name,
512 : Zone* zone) const {
513 1652848 : AbstractState* that = new (zone) AbstractState(*this);
514 1652848 : if (that->fields_[index]) {
515 : that->fields_[index] =
516 649094 : that->fields_[index]->Extend(object, value, name, zone);
517 : } else {
518 2007508 : that->fields_[index] = new (zone) AbstractField(object, value, name, zone);
519 : }
520 1652848 : return that;
521 : }
522 :
523 0 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
524 : Node* object, size_t index, MaybeHandle<Name> name, Zone* zone) const {
525 : AliasStateInfo alias_info(this, object);
526 1195091 : return KillField(alias_info, index, name, zone);
527 : }
528 :
529 1195634 : LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
530 : const AliasStateInfo& alias_info, size_t index, MaybeHandle<Name> name,
531 : Zone* zone) const {
532 1195634 : if (AbstractField const* this_field = this->fields_[index]) {
533 538718 : this_field = this_field->Kill(alias_info, name, zone);
534 538718 : if (this->fields_[index] != this_field) {
535 154246 : AbstractState* that = new (zone) AbstractState(*this);
536 154246 : that->fields_[index] = this_field;
537 154246 : return that;
538 : }
539 : }
540 : return this;
541 : }
542 :
543 : LoadElimination::AbstractState const*
544 995671 : LoadElimination::AbstractState::KillFields(Node* object, MaybeHandle<Name> name,
545 : Zone* zone) const {
546 : AliasStateInfo alias_info(this, object);
547 31476366 : for (size_t i = 0;; ++i) {
548 32472037 : if (i == arraysize(fields_)) return this;
549 31488898 : if (AbstractField const* this_field = this->fields_[i]) {
550 : AbstractField const* that_field =
551 25740978 : this_field->Kill(alias_info, name, zone);
552 25740978 : if (that_field != this_field) {
553 12532 : AbstractState* that = new (zone) AbstractState(*this);
554 12532 : that->fields_[i] = that_field;
555 385106 : while (++i < arraysize(fields_)) {
556 372574 : if (this->fields_[i] != nullptr) {
557 345054 : that->fields_[i] = this->fields_[i]->Kill(alias_info, name, zone);
558 : }
559 : }
560 : return that;
561 : }
562 : }
563 : }
564 : }
565 :
566 0 : Node* LoadElimination::AbstractState::LookupField(Node* object,
567 : size_t index) const {
568 1765594 : if (AbstractField const* this_field = this->fields_[index]) {
569 761840 : return this_field->Lookup(object);
570 : }
571 : return nullptr;
572 : }
573 :
574 242017211 : bool LoadElimination::AliasStateInfo::MayAlias(Node* other) const {
575 : // If {object} is being initialized right here (indicated by {object} being
576 : // an Allocate node instead of a FinishRegion node), we know that {other}
577 : // can only alias with {object} if they refer to exactly the same node.
578 484034422 : if (object_->opcode() == IrOpcode::kAllocate) {
579 240723463 : return object_ == other;
580 : }
581 : // Decide aliasing based on the node kinds.
582 1293748 : if (!compiler::MayAlias(object_, other)) {
583 : return false;
584 : }
585 : // Decide aliasing based on maps (if available).
586 : Handle<Map> map;
587 935814 : if (map_.ToHandle(&map)) {
588 : ZoneHandleSet<Map> other_maps;
589 2710 : if (state_->LookupMaps(other, &other_maps) && other_maps.size() == 1) {
590 843 : if (map.address() != other_maps.at(0).address()) {
591 528 : return false;
592 : }
593 : }
594 : }
595 : return true;
596 : }
597 :
598 0 : void LoadElimination::AbstractState::Print() const {
599 0 : if (maps_) {
600 0 : PrintF(" maps:\n");
601 0 : maps_->Print();
602 : }
603 0 : if (elements_) {
604 0 : PrintF(" elements:\n");
605 0 : elements_->Print();
606 : }
607 0 : for (size_t i = 0; i < arraysize(fields_); ++i) {
608 0 : if (AbstractField const* const field = fields_[i]) {
609 0 : PrintF(" field %zu:\n", i);
610 0 : field->Print();
611 : }
612 : }
613 0 : }
614 :
615 : LoadElimination::AbstractState const*
616 0 : LoadElimination::AbstractStateForEffectNodes::Get(Node* node) const {
617 29654009 : size_t const id = node->id();
618 52647907 : if (id < info_for_node_.size()) return info_for_node_[id];
619 : return nullptr;
620 : }
621 :
622 12125427 : void LoadElimination::AbstractStateForEffectNodes::Set(
623 : Node* node, AbstractState const* state) {
624 12125427 : size_t const id = node->id();
625 12125427 : if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
626 12125424 : info_for_node_[id] = state;
627 12125424 : }
628 :
629 8870 : Reduction LoadElimination::ReduceMapGuard(Node* node) {
630 8870 : ZoneHandleSet<Map> const& maps = MapGuardMapsOf(node->op());
631 8870 : Node* const object = NodeProperties::GetValueInput(node, 0);
632 8870 : Node* const effect = NodeProperties::GetEffectInput(node);
633 : AbstractState const* state = node_states_.Get(effect);
634 8870 : if (state == nullptr) return NoChange();
635 : ZoneHandleSet<Map> object_maps;
636 7634 : if (state->LookupMaps(object, &object_maps)) {
637 290 : if (maps.contains(object_maps)) return Replace(effect);
638 : // TODO(turbofan): Compute the intersection.
639 : }
640 7532 : state = state->SetMaps(object, maps, zone());
641 7532 : return UpdateState(node, state);
642 : }
643 :
644 148802 : Reduction LoadElimination::ReduceCheckMaps(Node* node) {
645 148802 : ZoneHandleSet<Map> const& maps = CheckMapsParametersOf(node->op()).maps();
646 148802 : Node* const object = NodeProperties::GetValueInput(node, 0);
647 148802 : Node* const effect = NodeProperties::GetEffectInput(node);
648 : AbstractState const* state = node_states_.Get(effect);
649 148803 : if (state == nullptr) return NoChange();
650 : ZoneHandleSet<Map> object_maps;
651 100585 : if (state->LookupMaps(object, &object_maps)) {
652 44302 : if (maps.contains(object_maps)) return Replace(effect);
653 : // TODO(turbofan): Compute the intersection.
654 : }
655 56512 : state = state->SetMaps(object, maps, zone());
656 56512 : return UpdateState(node, state);
657 : }
658 :
659 9383 : Reduction LoadElimination::ReduceCompareMaps(Node* node) {
660 9383 : ZoneHandleSet<Map> const& maps = CompareMapsParametersOf(node->op());
661 9383 : Node* const object = NodeProperties::GetValueInput(node, 0);
662 9383 : Node* const effect = NodeProperties::GetEffectInput(node);
663 : AbstractState const* state = node_states_.Get(effect);
664 9383 : if (state == nullptr) return NoChange();
665 : ZoneHandleSet<Map> object_maps;
666 7956 : if (state->LookupMaps(object, &object_maps)) {
667 236 : if (maps.contains(object_maps)) {
668 54 : Node* value = jsgraph()->TrueConstant();
669 : ReplaceWithValue(node, value, effect);
670 : return Replace(value);
671 : }
672 : // TODO(turbofan): Compute the intersection.
673 : }
674 7902 : return UpdateState(node, state);
675 : }
676 :
677 6779 : Reduction LoadElimination::ReduceEnsureWritableFastElements(Node* node) {
678 6779 : Node* const object = NodeProperties::GetValueInput(node, 0);
679 6779 : Node* const elements = NodeProperties::GetValueInput(node, 1);
680 6779 : Node* const effect = NodeProperties::GetEffectInput(node);
681 : AbstractState const* state = node_states_.Get(effect);
682 6779 : if (state == nullptr) return NoChange();
683 : // Check if the {elements} already have the fixed array map.
684 : ZoneHandleSet<Map> elements_maps;
685 : ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
686 3107 : if (state->LookupMaps(elements, &elements_maps) &&
687 1287 : fixed_array_maps.contains(elements_maps)) {
688 : ReplaceWithValue(node, elements, effect);
689 : return Replace(elements);
690 : }
691 : // We know that the resulting elements have the fixed array map.
692 1793 : state = state->SetMaps(node, fixed_array_maps, zone());
693 : // Kill the previous elements on {object}.
694 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
695 : MaybeHandle<Name>(), zone());
696 : // Add the new elements on {object}.
697 3586 : state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
698 1793 : MaybeHandle<Name>(), zone());
699 1793 : return UpdateState(node, state);
700 : }
701 :
702 9965 : Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
703 9965 : GrowFastElementsParameters params = GrowFastElementsParametersOf(node->op());
704 9965 : Node* const object = NodeProperties::GetValueInput(node, 0);
705 9965 : Node* const effect = NodeProperties::GetEffectInput(node);
706 : AbstractState const* state = node_states_.Get(effect);
707 9965 : if (state == nullptr) return NoChange();
708 3819 : if (params.mode() == GrowFastElementsMode::kDoubleElements) {
709 : // We know that the resulting elements have the fixed double array map.
710 460 : state = state->SetMaps(
711 460 : node, ZoneHandleSet<Map>(factory()->fixed_double_array_map()), zone());
712 : } else {
713 : // We know that the resulting elements have the fixed array map or the COW
714 : // version thereof (if we didn't grow and it was already COW before).
715 : ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
716 3359 : fixed_array_maps.insert(factory()->fixed_cow_array_map(), zone());
717 3359 : state = state->SetMaps(node, fixed_array_maps, zone());
718 : }
719 : // Kill the previous elements on {object}.
720 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
721 : MaybeHandle<Name>(), zone());
722 : // Add the new elements on {object}.
723 7638 : state = state->AddField(object, FieldIndexOf(JSObject::kElementsOffset), node,
724 3819 : MaybeHandle<Name>(), zone());
725 3819 : return UpdateState(node, state);
726 : }
727 :
728 954 : Reduction LoadElimination::ReduceTransitionElementsKind(Node* node) {
729 954 : ElementsTransition transition = ElementsTransitionOf(node->op());
730 954 : Node* const object = NodeProperties::GetValueInput(node, 0);
731 : Handle<Map> source_map(transition.source());
732 : Handle<Map> target_map(transition.target());
733 954 : Node* const effect = NodeProperties::GetEffectInput(node);
734 : AbstractState const* state = node_states_.Get(effect);
735 954 : if (state == nullptr) return NoChange();
736 727 : switch (transition.mode()) {
737 : case ElementsTransition::kFastTransition:
738 : break;
739 : case ElementsTransition::kSlowTransition:
740 : // Kill the elements as well.
741 : AliasStateInfo alias_info(state, object, source_map);
742 : state =
743 884 : state->KillField(alias_info, FieldIndexOf(JSObject::kElementsOffset),
744 442 : MaybeHandle<Name>(), zone());
745 442 : break;
746 : }
747 : ZoneHandleSet<Map> object_maps;
748 727 : if (state->LookupMaps(object, &object_maps)) {
749 196 : if (ZoneHandleSet<Map>(target_map).contains(object_maps)) {
750 : // The {object} already has the {target_map}, so this TransitionElements
751 : // {node} is fully redundant (independent of what {source_map} is).
752 : return Replace(effect);
753 : }
754 106 : if (object_maps.contains(ZoneHandleSet<Map>(source_map))) {
755 106 : object_maps.remove(source_map, zone());
756 106 : object_maps.insert(target_map, zone());
757 : AliasStateInfo alias_info(state, object, source_map);
758 106 : state = state->KillMaps(alias_info, zone());
759 106 : state = state->SetMaps(object, object_maps, zone());
760 : }
761 : } else {
762 : AliasStateInfo alias_info(state, object, source_map);
763 531 : state = state->KillMaps(alias_info, zone());
764 : }
765 637 : return UpdateState(node, state);
766 : }
767 :
768 546 : Reduction LoadElimination::ReduceTransitionAndStoreElement(Node* node) {
769 546 : Node* const object = NodeProperties::GetValueInput(node, 0);
770 546 : Handle<Map> double_map(DoubleMapParameterOf(node->op()));
771 546 : Handle<Map> fast_map(FastMapParameterOf(node->op()));
772 546 : Node* const effect = NodeProperties::GetEffectInput(node);
773 : AbstractState const* state = node_states_.Get(effect);
774 546 : if (state == nullptr) return NoChange();
775 :
776 : // We need to add the double and fast maps to the set of possible maps for
777 : // this object, because we don't know which of those we'll transition to.
778 : // Additionally, we should kill all alias information.
779 : ZoneHandleSet<Map> object_maps;
780 260 : if (state->LookupMaps(object, &object_maps)) {
781 0 : object_maps.insert(double_map, zone());
782 0 : object_maps.insert(fast_map, zone());
783 : state = state->KillMaps(object, zone());
784 0 : state = state->SetMaps(object, object_maps, zone());
785 : }
786 : // Kill the elements as well.
787 : state = state->KillField(object, FieldIndexOf(JSObject::kElementsOffset),
788 : MaybeHandle<Name>(), zone());
789 260 : return UpdateState(node, state);
790 : }
791 :
792 1593625 : Reduction LoadElimination::ReduceLoadField(Node* node,
793 : FieldAccess const& access) {
794 1593625 : Node* object = NodeProperties::GetValueInput(node, 0);
795 1593624 : Node* effect = NodeProperties::GetEffectInput(node);
796 1593624 : Node* control = NodeProperties::GetControlInput(node);
797 : AbstractState const* state = node_states_.Get(effect);
798 1593624 : if (state == nullptr) return NoChange();
799 1412198 : if (access.offset == HeapObject::kMapOffset &&
800 : access.base_is_tagged == kTaggedBase) {
801 : DCHECK(IsAnyTagged(access.machine_type.representation()));
802 : ZoneHandleSet<Map> object_maps;
803 4074 : if (state->LookupMaps(object, &object_maps) && object_maps.size() == 1) {
804 14 : Node* value = jsgraph()->HeapConstant(object_maps[0]);
805 : NodeProperties::SetType(value, Type::OtherInternal());
806 : ReplaceWithValue(node, value, effect);
807 14 : return Replace(value);
808 : }
809 : } else {
810 1408138 : int field_index = FieldIndexOf(access);
811 1408138 : if (field_index >= 0) {
812 1209628 : if (Node* replacement = state->LookupField(object, field_index)) {
813 : // Make sure we don't resurrect dead {replacement} nodes.
814 116340 : if (!replacement->IsDead()) {
815 : // Introduce a TypeGuard if the type of the {replacement} node is not
816 : // a subtype of the original {node}'s type.
817 232666 : if (!NodeProperties::GetType(replacement)
818 : .Is(NodeProperties::GetType(node))) {
819 : Type replacement_type = Type::Intersect(
820 : NodeProperties::GetType(node),
821 983 : NodeProperties::GetType(replacement), graph()->zone());
822 : replacement = effect =
823 983 : graph()->NewNode(common()->TypeGuard(replacement_type),
824 : replacement, effect, control);
825 : NodeProperties::SetType(replacement, replacement_type);
826 : }
827 : ReplaceWithValue(node, replacement, effect);
828 : return Replace(replacement);
829 : }
830 : }
831 488481 : state = state->AddField(object, field_index, node, access.name, zone());
832 : }
833 : }
834 : Handle<Map> field_map;
835 1295850 : if (access.map.ToHandle(&field_map)) {
836 3181 : state = state->SetMaps(node, ZoneHandleSet<Map>(field_map), zone());
837 : }
838 1295850 : return UpdateState(node, state);
839 : }
840 :
841 2467290 : Reduction LoadElimination::ReduceStoreField(Node* node,
842 : FieldAccess const& access) {
843 2467290 : Node* const object = NodeProperties::GetValueInput(node, 0);
844 2467290 : Node* const new_value = NodeProperties::GetValueInput(node, 1);
845 2467290 : Node* const effect = NodeProperties::GetEffectInput(node);
846 : AbstractState const* state = node_states_.Get(effect);
847 2467290 : if (state == nullptr) return NoChange();
848 2321561 : if (access.offset == HeapObject::kMapOffset &&
849 : access.base_is_tagged == kTaggedBase) {
850 : DCHECK(IsAnyTagged(access.machine_type.representation()));
851 : // Kill all potential knowledge about the {object}s map.
852 : state = state->KillMaps(object, zone());
853 165116 : Type const new_value_type = NodeProperties::GetType(new_value);
854 165116 : if (new_value_type.IsHeapConstant()) {
855 : // Record the new {object} map information.
856 : AllowHandleDereference handle_dereference;
857 : ZoneHandleSet<Map> object_maps(
858 165115 : Handle<Map>::cast(new_value_type.AsHeapConstant()->Value()));
859 165115 : state = state->SetMaps(object, object_maps, zone());
860 : }
861 : } else {
862 2156445 : int field_index = FieldIndexOf(access);
863 2156445 : if (field_index >= 0) {
864 1160780 : Node* const old_value = state->LookupField(object, field_index);
865 1160779 : if (old_value == new_value) {
866 : // This store is fully redundant.
867 : return Replace(effect);
868 : }
869 : // Kill all potentially aliasing fields and record the new value.
870 : state = state->KillField(object, field_index, access.name, zone());
871 : state =
872 1158755 : state->AddField(object, field_index, new_value, access.name, zone());
873 : } else {
874 : // Unsupported StoreField operator.
875 995665 : state = state->KillFields(object, access.name, zone());
876 : }
877 : }
878 2319535 : return UpdateState(node, state);
879 : }
880 :
881 31788 : Reduction LoadElimination::ReduceLoadElement(Node* node) {
882 31788 : Node* const object = NodeProperties::GetValueInput(node, 0);
883 31788 : Node* const index = NodeProperties::GetValueInput(node, 1);
884 31788 : Node* const effect = NodeProperties::GetEffectInput(node);
885 : AbstractState const* state = node_states_.Get(effect);
886 31788 : if (state == nullptr) return NoChange();
887 :
888 : // Only handle loads that do not require truncations.
889 20012 : ElementAccess const& access = ElementAccessOf(node->op());
890 : switch (access.machine_type.representation()) {
891 : case MachineRepresentation::kNone:
892 : case MachineRepresentation::kBit:
893 : // TODO(solanes): Create the code for the compressed values
894 : case MachineRepresentation::kCompressedSigned:
895 : case MachineRepresentation::kCompressedPointer:
896 : case MachineRepresentation::kCompressed:
897 0 : UNREACHABLE();
898 : break;
899 : case MachineRepresentation::kWord8:
900 : case MachineRepresentation::kWord16:
901 : case MachineRepresentation::kWord32:
902 : case MachineRepresentation::kWord64:
903 : case MachineRepresentation::kFloat32:
904 : // TODO(turbofan): Add support for doing the truncations.
905 : break;
906 : case MachineRepresentation::kFloat64:
907 : case MachineRepresentation::kSimd128:
908 : case MachineRepresentation::kTaggedSigned:
909 : case MachineRepresentation::kTaggedPointer:
910 : case MachineRepresentation::kTagged:
911 20012 : if (Node* replacement = state->LookupElement(
912 : object, index, access.machine_type.representation())) {
913 : // Make sure we don't resurrect dead {replacement} nodes.
914 : // Skip lowering if the type of the {replacement} node is not a subtype
915 : // of the original {node}'s type.
916 : // TODO(tebbi): We should insert a {TypeGuard} for the intersection of
917 : // these two types here once we properly handle {Type::None} everywhere.
918 2620 : if (!replacement->IsDead() && NodeProperties::GetType(replacement)
919 : .Is(NodeProperties::GetType(node))) {
920 : ReplaceWithValue(node, replacement, effect);
921 : return Replace(replacement);
922 : }
923 : }
924 : state = state->AddElement(object, index, node,
925 18717 : access.machine_type.representation(), zone());
926 18717 : return UpdateState(node, state);
927 : }
928 : return NoChange();
929 : }
930 :
931 58164 : Reduction LoadElimination::ReduceStoreElement(Node* node) {
932 58164 : ElementAccess const& access = ElementAccessOf(node->op());
933 58164 : Node* const object = NodeProperties::GetValueInput(node, 0);
934 58164 : Node* const index = NodeProperties::GetValueInput(node, 1);
935 58164 : Node* const new_value = NodeProperties::GetValueInput(node, 2);
936 58163 : Node* const effect = NodeProperties::GetEffectInput(node);
937 : AbstractState const* state = node_states_.Get(effect);
938 58164 : if (state == nullptr) return NoChange();
939 : Node* const old_value =
940 : state->LookupElement(object, index, access.machine_type.representation());
941 42613 : if (old_value == new_value) {
942 : // This store is fully redundant.
943 : return Replace(effect);
944 : }
945 : // Kill all potentially aliasing elements.
946 42592 : state = state->KillElement(object, index, zone());
947 : // Only record the new value if the store doesn't have an implicit truncation.
948 : switch (access.machine_type.representation()) {
949 : case MachineRepresentation::kNone:
950 : case MachineRepresentation::kBit:
951 : // TODO(solanes): Create the code for the compressed values
952 : case MachineRepresentation::kCompressedSigned:
953 : case MachineRepresentation::kCompressedPointer:
954 : case MachineRepresentation::kCompressed:
955 0 : UNREACHABLE();
956 : break;
957 : case MachineRepresentation::kWord8:
958 : case MachineRepresentation::kWord16:
959 : case MachineRepresentation::kWord32:
960 : case MachineRepresentation::kWord64:
961 : case MachineRepresentation::kFloat32:
962 : // TODO(turbofan): Add support for doing the truncations.
963 : break;
964 : case MachineRepresentation::kFloat64:
965 : case MachineRepresentation::kSimd128:
966 : case MachineRepresentation::kTaggedSigned:
967 : case MachineRepresentation::kTaggedPointer:
968 : case MachineRepresentation::kTagged:
969 : state = state->AddElement(object, index, new_value,
970 42592 : access.machine_type.representation(), zone());
971 42592 : break;
972 : }
973 42592 : return UpdateState(node, state);
974 : }
975 :
976 6620 : Reduction LoadElimination::ReduceStoreTypedElement(Node* node) {
977 6620 : Node* const effect = NodeProperties::GetEffectInput(node);
978 : AbstractState const* state = node_states_.Get(effect);
979 6620 : if (state == nullptr) return NoChange();
980 4897 : return UpdateState(node, state);
981 : }
982 :
983 233772 : LoadElimination::AbstractState const* LoadElimination::UpdateStateForPhi(
984 : AbstractState const* state, Node* effect_phi, Node* phi) {
985 233772 : int predecessor_count = phi->InputCount() - 1;
986 : // TODO(jarin) Consider doing a union here. At the moment, we just keep this
987 : // consistent with AbstractState::Merge.
988 :
989 : // Check if all the inputs have the same maps.
990 : AbstractState const* input_state =
991 233772 : node_states_.Get(NodeProperties::GetEffectInput(effect_phi, 0));
992 : ZoneHandleSet<Map> object_maps;
993 233769 : if (!input_state->LookupMaps(phi->InputAt(0), &object_maps)) return state;
994 434 : for (int i = 1; i < predecessor_count; i++) {
995 : input_state =
996 360 : node_states_.Get(NodeProperties::GetEffectInput(effect_phi, i));
997 : ZoneHandleSet<Map> input_maps;
998 682 : if (!input_state->LookupMaps(phi->InputAt(i), &input_maps)) return state;
999 38 : if (input_maps != object_maps) return state;
1000 : }
1001 36 : return state->SetMaps(phi, object_maps, zone());
1002 : }
1003 :
1004 607917 : Reduction LoadElimination::ReduceEffectPhi(Node* node) {
1005 607917 : Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
1006 607922 : Node* const control = NodeProperties::GetControlInput(node);
1007 : AbstractState const* state0 = node_states_.Get(effect0);
1008 607919 : if (state0 == nullptr) return NoChange();
1009 476551 : if (control->opcode() == IrOpcode::kLoop) {
1010 : // Here we rely on having only reducible loops:
1011 : // The loop entry edge always dominates the header, so we can just take
1012 : // the state from the first input, and compute the loop state based on it.
1013 85791 : AbstractState const* state = ComputeLoopState(node, state0);
1014 85791 : return UpdateState(node, state);
1015 : }
1016 : DCHECK_EQ(IrOpcode::kMerge, control->opcode());
1017 :
1018 : // Shortcut for the case when we do not know anything about some input.
1019 : int const input_count = node->op()->EffectInputCount();
1020 4037000 : for (int i = 1; i < input_count; ++i) {
1021 1911703 : Node* const effect = NodeProperties::GetEffectInput(node, i);
1022 1911706 : if (node_states_.Get(effect) == nullptr) return NoChange();
1023 : }
1024 :
1025 : // Make a copy of the first input's state and merge with the state
1026 : // from other inputs.
1027 302180 : AbstractState* state = new (zone()) AbstractState(*state0);
1028 1729730 : for (int i = 1; i < input_count; ++i) {
1029 713768 : Node* const input = NodeProperties::GetEffectInput(node, i);
1030 713767 : state->Merge(node_states_.Get(input), zone());
1031 : }
1032 :
1033 : // For each phi, try to compute the new state for the phi from
1034 : // the inputs.
1035 : AbstractState const* state_with_phis = state;
1036 1652391 : for (Node* use : control->uses()) {
1037 1350207 : if (use->opcode() == IrOpcode::kPhi) {
1038 233774 : state_with_phis = UpdateStateForPhi(state_with_phis, node, use);
1039 : }
1040 : }
1041 :
1042 302184 : return UpdateState(node, state_with_phis);
1043 : }
1044 :
1045 0 : Reduction LoadElimination::ReduceStart(Node* node) {
1046 464167 : return UpdateState(node, empty_state());
1047 : }
1048 :
1049 31291781 : Reduction LoadElimination::ReduceOtherNode(Node* node) {
1050 31291781 : if (node->op()->EffectInputCount() == 1) {
1051 10280190 : if (node->op()->EffectOutputCount() == 1) {
1052 9413247 : Node* const effect = NodeProperties::GetEffectInput(node);
1053 : AbstractState const* state = node_states_.Get(effect);
1054 : // If we do not know anything about the predecessor, do not propagate
1055 : // just yet because we will have to recompute anyway once we compute
1056 : // the predecessor.
1057 9413580 : if (state == nullptr) return NoChange();
1058 : // Check if this {node} has some uncontrolled side effects.
1059 7817966 : if (!node->op()->HasProperty(Operator::kNoWrite)) {
1060 : state = empty_state();
1061 : }
1062 7817966 : return UpdateState(node, state);
1063 : } else {
1064 : // Effect terminators should be handled specially.
1065 : return NoChange();
1066 : }
1067 : }
1068 : DCHECK_EQ(0, node->op()->EffectInputCount());
1069 : DCHECK_EQ(0, node->op()->EffectOutputCount());
1070 : return NoChange();
1071 : }
1072 :
1073 12430122 : Reduction LoadElimination::UpdateState(Node* node, AbstractState const* state) {
1074 : AbstractState const* original = node_states_.Get(node);
1075 : // Only signal that the {node} has Changed, if the information about {state}
1076 : // has changed wrt. the {original}.
1077 12430122 : if (state != original) {
1078 12185125 : if (original == nullptr || !state->Equals(original)) {
1079 12125428 : node_states_.Set(node, state);
1080 : return Changed(node);
1081 : }
1082 : }
1083 : return NoChange();
1084 : }
1085 :
1086 : LoadElimination::AbstractState const*
1087 33351 : LoadElimination::ComputeLoopStateForStoreField(
1088 : Node* current, LoadElimination::AbstractState const* state,
1089 : FieldAccess const& access) const {
1090 33351 : Node* const object = NodeProperties::GetValueInput(current, 0);
1091 33351 : if (access.offset == HeapObject::kMapOffset) {
1092 : // Invalidate what we know about the {object}s map.
1093 : state = state->KillMaps(object, zone());
1094 : } else {
1095 27458 : int field_index = FieldIndexOf(access);
1096 27458 : if (field_index < 0) {
1097 6 : state = state->KillFields(object, access.name, zone());
1098 : } else {
1099 27452 : state = state->KillField(object, field_index, access.name, zone());
1100 : }
1101 : }
1102 33351 : return state;
1103 : }
1104 :
1105 85791 : LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
1106 : Node* node, AbstractState const* state) const {
1107 85791 : Node* const control = NodeProperties::GetControlInput(node);
1108 : struct TransitionElementsKindInfo {
1109 : ElementsTransition transition;
1110 : Node* object;
1111 : };
1112 : ZoneVector<TransitionElementsKindInfo> element_transitions_(zone());
1113 85791 : ZoneQueue<Node*> queue(zone());
1114 : ZoneSet<Node*> visited(zone());
1115 : visited.insert(node);
1116 257371 : for (int i = 1; i < control->InputCount(); ++i) {
1117 257372 : queue.push(node->InputAt(i));
1118 : }
1119 1686014 : while (!queue.empty()) {
1120 862460 : Node* const current = queue.front();
1121 : queue.pop();
1122 862430 : if (visited.find(current) == visited.end()) {
1123 : visited.insert(current);
1124 1596928 : if (!current->op()->HasProperty(Operator::kNoWrite)) {
1125 107716 : switch (current->opcode()) {
1126 : case IrOpcode::kEnsureWritableFastElements: {
1127 754 : Node* const object = NodeProperties::GetValueInput(current, 0);
1128 : state = state->KillField(object,
1129 : FieldIndexOf(JSObject::kElementsOffset),
1130 : MaybeHandle<Name>(), zone());
1131 754 : break;
1132 : }
1133 : case IrOpcode::kMaybeGrowFastElements: {
1134 1821 : Node* const object = NodeProperties::GetValueInput(current, 0);
1135 : state = state->KillField(object,
1136 : FieldIndexOf(JSObject::kElementsOffset),
1137 : MaybeHandle<Name>(), zone());
1138 1821 : break;
1139 : }
1140 : case IrOpcode::kTransitionElementsKind: {
1141 226 : ElementsTransition transition = ElementsTransitionOf(current->op());
1142 226 : Node* const object = NodeProperties::GetValueInput(current, 0);
1143 : ZoneHandleSet<Map> object_maps;
1144 678 : if (!state->LookupMaps(object, &object_maps) ||
1145 : !ZoneHandleSet<Map>(transition.target())
1146 412 : .contains(object_maps)) {
1147 266 : element_transitions_.push_back({transition, object});
1148 : }
1149 : break;
1150 : }
1151 : case IrOpcode::kTransitionAndStoreElement: {
1152 438 : Node* const object = NodeProperties::GetValueInput(current, 0);
1153 : // Invalidate what we know about the {object}s map.
1154 : state = state->KillMaps(object, zone());
1155 : // Kill the elements as well.
1156 : state = state->KillField(object,
1157 : FieldIndexOf(JSObject::kElementsOffset),
1158 : MaybeHandle<Name>(), zone());
1159 438 : break;
1160 : }
1161 : case IrOpcode::kStoreField:
1162 30539 : state = ComputeLoopStateForStoreField(current, state,
1163 61078 : FieldAccessOf(current->op()));
1164 30539 : break;
1165 : case IrOpcode::kStoreMessage:
1166 2812 : state = ComputeLoopStateForStoreField(
1167 5624 : current, state, AccessBuilder::ForExternalIntPtr());
1168 2812 : break;
1169 : case IrOpcode::kStoreElement: {
1170 6434 : Node* const object = NodeProperties::GetValueInput(current, 0);
1171 6434 : Node* const index = NodeProperties::GetValueInput(current, 1);
1172 6434 : state = state->KillElement(object, index, zone());
1173 6434 : break;
1174 : }
1175 : case IrOpcode::kStoreTypedElement: {
1176 : // Doesn't affect anything we track with the state currently.
1177 : break;
1178 : }
1179 : default:
1180 62353 : return empty_state();
1181 : }
1182 : }
1183 3893276 : for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
1184 1614083 : queue.push(NodeProperties::GetEffectInput(current, i));
1185 : }
1186 : }
1187 : }
1188 :
1189 : // Finally, we apply the element transitions. For each transition, we will try
1190 : // to only invalidate information about nodes that can have the transition's
1191 : // source map. The trouble is that an object can be transitioned by some other
1192 : // transition to the source map. In that case, the other transition will
1193 : // invalidate the information, so we are mostly fine.
1194 : //
1195 : // The only bad case is
1196 : //
1197 : // mapA ---fast---> mapB ---slow---> mapC
1198 : //
1199 : // If we process the slow transition first on an object that has mapA, we will
1200 : // ignore the transition because the object does not have its source map
1201 : // (mapB). When we later process the fast transition, we invalidate the
1202 : // object's map, but we keep the information about the object's elements. This
1203 : // is wrong because the elements will be overwritten by the slow transition.
1204 : //
1205 : // Note that the slow-slow case is fine because either of the slow transition
1206 : // will invalidate the elements field, so the processing order does not
1207 : // matter.
1208 : //
1209 : // To handle the bad case properly, we first kill the maps using all
1210 : // transitions. We kill the the fields later when all the transitions are
1211 : // already reflected in the map information.
1212 :
1213 23575 : for (const TransitionElementsKindInfo& t : element_transitions_) {
1214 133 : AliasStateInfo alias_info(state, t.object, t.transition.source());
1215 133 : state = state->KillMaps(alias_info, zone());
1216 : }
1217 23575 : for (const TransitionElementsKindInfo& t : element_transitions_) {
1218 133 : switch (t.transition.mode()) {
1219 : case ElementsTransition::kFastTransition:
1220 : break;
1221 : case ElementsTransition::kSlowTransition: {
1222 101 : AliasStateInfo alias_info(state, t.object, t.transition.source());
1223 202 : state = state->KillField(alias_info,
1224 : FieldIndexOf(JSObject::kElementsOffset),
1225 101 : MaybeHandle<Name>(), zone());
1226 : break;
1227 : }
1228 : }
1229 : }
1230 : return state;
1231 : }
1232 :
1233 : // static
1234 0 : int LoadElimination::FieldIndexOf(int offset) {
1235 : DCHECK(IsAligned(offset, kTaggedSize));
1236 3521744 : int field_index = offset / kTaggedSize;
1237 3521744 : if (field_index >= static_cast<int>(kMaxTrackedFields)) return -1;
1238 : DCHECK_LT(0, field_index);
1239 1793046 : return field_index - 1;
1240 : }
1241 :
1242 : // static
1243 3592039 : int LoadElimination::FieldIndexOf(FieldAccess const& access) {
1244 : MachineRepresentation rep = access.machine_type.representation();
1245 : switch (rep) {
1246 : case MachineRepresentation::kNone:
1247 : case MachineRepresentation::kBit:
1248 : case MachineRepresentation::kSimd128:
1249 0 : UNREACHABLE();
1250 : break;
1251 : case MachineRepresentation::kWord32:
1252 : if (kInt32Size != kTaggedSize) {
1253 : return -1; // We currently only track tagged pointer size fields.
1254 : }
1255 : break;
1256 : case MachineRepresentation::kWord64:
1257 : if (kInt64Size != kTaggedSize) {
1258 : return -1; // We currently only track tagged pointer size fields.
1259 : }
1260 : break;
1261 : case MachineRepresentation::kWord8:
1262 : case MachineRepresentation::kWord16:
1263 : case MachineRepresentation::kFloat32:
1264 : return -1; // Currently untracked.
1265 : case MachineRepresentation::kFloat64:
1266 : if (kDoubleSize != kTaggedSize) {
1267 : return -1; // We currently only track tagged pointer size fields.
1268 : }
1269 : break;
1270 : case MachineRepresentation::kTaggedSigned:
1271 : case MachineRepresentation::kTaggedPointer:
1272 : case MachineRepresentation::kTagged:
1273 : case MachineRepresentation::kCompressedSigned:
1274 : case MachineRepresentation::kCompressedPointer:
1275 : case MachineRepresentation::kCompressed:
1276 : // TODO(bmeurer): Check that we never do overlapping load/stores of
1277 : // individual parts of Float64 values.
1278 : break;
1279 : }
1280 3588993 : if (access.base_is_tagged != kTaggedBase) {
1281 : return -1; // We currently only track tagged objects.
1282 : }
1283 7043488 : return FieldIndexOf(access.offset);
1284 : }
1285 :
1286 0 : CommonOperatorBuilder* LoadElimination::common() const {
1287 0 : return jsgraph()->common();
1288 : }
1289 :
1290 0 : Graph* LoadElimination::graph() const { return jsgraph()->graph(); }
1291 :
1292 0 : Isolate* LoadElimination::isolate() const { return jsgraph()->isolate(); }
1293 :
1294 0 : Factory* LoadElimination::factory() const { return jsgraph()->factory(); }
1295 :
1296 : } // namespace compiler
1297 : } // namespace internal
1298 122004 : } // namespace v8
|
