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/heap/factory.h"
12#include "src/objects/objects-inl.h"
13
14namespace v8 {
15namespace internal {
16namespace compiler {
17
18namespace {
19
20bool IsRename(Node* node) {
21  switch (node->opcode()) {
22    case IrOpcode::kCheckHeapObject:
23    case IrOpcode::kFinishRegion:
24    case IrOpcode::kTypeGuard:
25      return !node->IsDead();
26    default:
27      return false;
28  }
29}
30
31Node* ResolveRenames(Node* node) {
32  while (IsRename(node)) {
33    node = node->InputAt(0);
34  }
35  return node;
36}
37
38bool MayAlias(Node* a, Node* b) {
39  if (a != b) {
40    if (!NodeProperties::GetType(a).Maybe(NodeProperties::GetType(b))) {
41      return false;
42    } else if (IsRename(b)) {
43      return MayAlias(a, b->InputAt(0));
44    } else if (IsRename(a)) {
45      return MayAlias(a->InputAt(0), b);
46    } else if (b->opcode() == IrOpcode::kAllocate) {
47      switch (a->opcode()) {
48        case IrOpcode::kAllocate:
49        case IrOpcode::kHeapConstant:
50        case IrOpcode::kParameter:
51          return false;
52        default:
53          break;
54      }
55    } else if (a->opcode() == IrOpcode::kAllocate) {
56      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
68bool MustAlias(Node* a, Node* b) {
69  return ResolveRenames(a) == ResolveRenames(b);
70}
71
72}  // namespace
73
74Reduction LoadElimination::Reduce(Node* node) {
75  if (FLAG_trace_turbo_load_elimination) {
76    if (node->op()->EffectInputCount() > 0) {
77      PrintF(" visit #%d:%s", node->id(), node->op()->mnemonic());
78      if (node->op()->ValueInputCount() > 0) {
79        PrintF("(");
80        for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
81          if (i > 0) PrintF(", ");
82          Node* const value = NodeProperties::GetValueInput(node, i);
83          PrintF("#%d:%s", value->id(), value->op()->mnemonic());
84        }
85        PrintF(")");
86      }
87      PrintF("\n");
88      for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
89        Node* const effect = NodeProperties::GetEffectInput(node, i);
90        if (AbstractState const* const state = node_states_.Get(effect)) {
91          PrintF("  state[%i]: #%d:%s\n", i, effect->id(),
92                 effect->op()->mnemonic());
93          state->Print();
94        } else {
95          PrintF("  no state[%i]: #%d:%s\n", i, effect->id(),
96                 effect->op()->mnemonic());
97        }
98      }
99    }
100  }
101  switch (node->opcode()) {
102    case IrOpcode::kMapGuard:
103      return ReduceMapGuard(node);
104    case IrOpcode::kCheckMaps:
105      return ReduceCheckMaps(node);
106    case IrOpcode::kCompareMaps:
107      return ReduceCompareMaps(node);
108    case IrOpcode::kEnsureWritableFastElements:
109      return ReduceEnsureWritableFastElements(node);
110    case IrOpcode::kMaybeGrowFastElements:
111      return ReduceMaybeGrowFastElements(node);
112    case IrOpcode::kTransitionElementsKind:
113      return ReduceTransitionElementsKind(node);
114    case IrOpcode::kLoadField:
115      return ReduceLoadField(node, FieldAccessOf(node->op()));
116    case IrOpcode::kStoreField:
117      return ReduceStoreField(node, FieldAccessOf(node->op()));
118    case IrOpcode::kLoadElement:
119      return ReduceLoadElement(node);
120    case IrOpcode::kStoreElement:
121      return ReduceStoreElement(node);
122    case IrOpcode::kTransitionAndStoreElement:
123      return ReduceTransitionAndStoreElement(node);
124    case IrOpcode::kStoreTypedElement:
125      return ReduceStoreTypedElement(node);
126    case IrOpcode::kEffectPhi:
127      return ReduceEffectPhi(node);
128    case IrOpcode::kDead:
129      break;
130    case IrOpcode::kStart:
131      return ReduceStart(node);
132    default:
133      return ReduceOtherNode(node);
134  }
135  return NoChange();
136}
137
138namespace {
139
140bool IsCompatible(MachineRepresentation r1, MachineRepresentation r2) {
141  if (r1 == r2) return true;
142  return IsAnyTagged(r1) && IsAnyTagged(r2);
143}
144
145}  // namespace
146
147LoadElimination::AbstractState const
148    LoadElimination::AbstractState::empty_state_;
149
150Node* LoadElimination::AbstractElements::Lookup(
151    Node* object, Node* index, MachineRepresentation representation) const {
152  for (Element const element : elements_) {
153    if (element.object == nullptr) continue;
154    DCHECK_NOT_NULL(element.index);
155    DCHECK_NOT_NULL(element.value);
156    if (MustAlias(object, element.object) && MustAlias(index, element.index) &&
157        IsCompatible(representation, element.representation)) {
158      return element.value;
159    }
160  }
161  return nullptr;
162}
163
164LoadElimination::AbstractElements const*
165LoadElimination::AbstractElements::Kill(Node* object, Node* index,
166                                        Zone* zone) const {
167  for (Element const element : this->elements_) {
168    if (element.object == nullptr) continue;
169    if (MayAlias(object, element.object)) {
170      AbstractElements* that = zone->New<AbstractElements>(zone);
171      for (Element const element2 : this->elements_) {
172        if (element2.object == nullptr) continue;
173        DCHECK_NOT_NULL(element2.index);
174        DCHECK_NOT_NULL(element2.value);
175        if (!MayAlias(object, element2.object) ||
176            !NodeProperties::GetType(index).Maybe(
177                NodeProperties::GetType(element2.index))) {
178          that->elements_[that->next_index_++] = element2;
179        }
180      }
181      that->next_index_ %= arraysize(elements_);
182      return that;
183    }
184  }
185  return this;
186}
187
188bool LoadElimination::AbstractElements::Equals(
189    AbstractElements const* that) const {
190  if (this == that) return true;
191  for (size_t i = 0; i < arraysize(elements_); ++i) {
192    Element this_element = this->elements_[i];
193    if (this_element.object == nullptr) continue;
194    for (size_t j = 0;; ++j) {
195      if (j == arraysize(elements_)) return false;
196      Element that_element = that->elements_[j];
197      if (this_element.object == that_element.object &&
198          this_element.index == that_element.index &&
199          this_element.value == that_element.value) {
200        break;
201      }
202    }
203  }
204  for (size_t i = 0; i < arraysize(elements_); ++i) {
205    Element that_element = that->elements_[i];
206    if (that_element.object == nullptr) continue;
207    for (size_t j = 0;; ++j) {
208      if (j == arraysize(elements_)) return false;
209      Element this_element = this->elements_[j];
210      if (that_element.object == this_element.object &&
211          that_element.index == this_element.index &&
212          that_element.value == this_element.value) {
213        break;
214      }
215    }
216  }
217  return true;
218}
219
220LoadElimination::AbstractElements const*
221LoadElimination::AbstractElements::Merge(AbstractElements const* that,
222                                         Zone* zone) const {
223  if (this->Equals(that)) return this;
224  AbstractElements* copy = zone->New<AbstractElements>(zone);
225  for (Element const this_element : this->elements_) {
226    if (this_element.object == nullptr) continue;
227    for (Element const that_element : that->elements_) {
228      if (this_element.object == that_element.object &&
229          this_element.index == that_element.index &&
230          this_element.value == that_element.value) {
231        copy->elements_[copy->next_index_++] = this_element;
232        break;
233      }
234    }
235  }
236  copy->next_index_ %= arraysize(elements_);
237  return copy;
238}
239
240void LoadElimination::AbstractElements::Print() const {
241  for (Element const& element : elements_) {
242    if (element.object) {
243      PrintF("    #%d:%s @ #%d:%s -> #%d:%s\n", element.object->id(),
244             element.object->op()->mnemonic(), element.index->id(),
245             element.index->op()->mnemonic(), element.value->id(),
246             element.value->op()->mnemonic());
247    }
248  }
249}
250
251LoadElimination::FieldInfo const* LoadElimination::AbstractField::Lookup(
252    Node* object) const {
253  for (auto& pair : info_for_node_) {
254    if (pair.first->IsDead()) continue;
255    if (MustAlias(object, pair.first)) return &pair.second;
256  }
257  return nullptr;
258}
259
260namespace {
261
262bool MayAlias(MaybeHandle<Name> x, MaybeHandle<Name> y) {
263  if (!x.address()) return true;
264  if (!y.address()) return true;
265  if (x.address() != y.address()) return false;
266  return true;
267}
268
269}  // namespace
270
271class LoadElimination::AliasStateInfo {
272 public:
273  AliasStateInfo(const AbstractState* state, Node* object, Handle<Map> map)
274      : state_(state), object_(object), map_(map) {}
275  AliasStateInfo(const AbstractState* state, Node* object)
276      : state_(state), object_(object) {}
277
278  bool MayAlias(Node* other) const;
279
280 private:
281  const AbstractState* state_;
282  Node* object_;
283  MaybeHandle<Map> map_;
284};
285
286LoadElimination::AbstractField const* LoadElimination::AbstractField::KillConst(
287    Node* object, Zone* zone) const {
288  for (auto info1 : this->info_for_node_) {
289    if (info1.first->IsDead()) continue;
290    // If we previously recorded information about a const store on the given
291    // 'object', we might not have done it on the same node; e.g. we might now
292    // identify the object by a FinishRegion node, whereas the initial const
293    // store was performed on the Allocate node. We therefore remove information
294    // on all nodes that must alias with 'object'.
295    if (MustAlias(object, info1.first)) {
296      AbstractField* that = zone->New<AbstractField>(zone);
297      for (auto info2 : this->info_for_node_) {
298        if (!MustAlias(object, info2.first)) {
299          that->info_for_node_.insert(info2);
300        }
301      }
302      return that;
303    }
304  }
305  return this;
306}
307
308LoadElimination::AbstractField const* LoadElimination::AbstractField::Kill(
309    const AliasStateInfo& alias_info, MaybeHandle<Name> name,
310    Zone* zone) const {
311  for (auto info1 : this->info_for_node_) {
312    if (info1.first->IsDead()) continue;
313    if (alias_info.MayAlias(info1.first)) {
314      AbstractField* that = zone->New<AbstractField>(zone);
315      for (auto info2 : this->info_for_node_) {
316        if (!alias_info.MayAlias(info2.first) ||
317            !MayAlias(name, info2.second.name)) {
318          that->info_for_node_.insert(info2);
319        }
320      }
321      return that;
322    }
323  }
324  return this;
325}
326
327void LoadElimination::AbstractField::Print() const {
328  for (auto pair : info_for_node_) {
329    PrintF("    #%d:%s -> #%d:%s [repr=%s]\n", pair.first->id(),
330           pair.first->op()->mnemonic(), pair.second.value->id(),
331           pair.second.value->op()->mnemonic(),
332           MachineReprToString(pair.second.representation));
333  }
334}
335
336LoadElimination::AbstractMaps::AbstractMaps(Zone* zone)
337    : info_for_node_(zone) {}
338
339LoadElimination::AbstractMaps::AbstractMaps(Node* object,
340                                            ZoneHandleSet<Map> maps, Zone* zone)
341    : info_for_node_(zone) {
342  object = ResolveRenames(object);
343  info_for_node_.insert(std::make_pair(object, maps));
344}
345
346bool LoadElimination::AbstractMaps::Lookup(
347    Node* object, ZoneHandleSet<Map>* object_maps) const {
348  auto it = info_for_node_.find(ResolveRenames(object));
349  if (it == info_for_node_.end()) return false;
350  *object_maps = it->second;
351  return true;
352}
353
354LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Kill(
355    const AliasStateInfo& alias_info, Zone* zone) const {
356  for (auto info1 : this->info_for_node_) {
357    if (alias_info.MayAlias(info1.first)) {
358      AbstractMaps* that = zone->New<AbstractMaps>(zone);
359      for (auto info2 : this->info_for_node_) {
360        if (!alias_info.MayAlias(info2.first))
361          that->info_for_node_.insert(info2);
362      }
363      return that;
364    }
365  }
366  return this;
367}
368
369LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Merge(
370    AbstractMaps const* that, Zone* zone) const {
371  if (this->Equals(that)) return this;
372  AbstractMaps* copy = zone->New<AbstractMaps>(zone);
373  for (auto this_it : this->info_for_node_) {
374    Node* this_object = this_it.first;
375    ZoneHandleSet<Map> this_maps = this_it.second;
376    auto that_it = that->info_for_node_.find(this_object);
377    if (that_it != that->info_for_node_.end() && that_it->second == this_maps) {
378      copy->info_for_node_.insert(this_it);
379    }
380  }
381  return copy;
382}
383
384LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Extend(
385    Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
386  AbstractMaps* that = zone->New<AbstractMaps>(zone);
387  that->info_for_node_ = this->info_for_node_;
388  object = ResolveRenames(object);
389  that->info_for_node_[object] = maps;
390  return that;
391}
392
393void LoadElimination::AbstractMaps::Print() const {
394  AllowHandleDereference allow_handle_dereference;
395  StdoutStream os;
396  for (auto pair : info_for_node_) {
397    os << "    #" << pair.first->id() << ":" << pair.first->op()->mnemonic()
398       << std::endl;
399    ZoneHandleSet<Map> const& maps = pair.second;
400    for (size_t i = 0; i < maps.size(); ++i) {
401      os << "     - " << Brief(*maps[i]) << std::endl;
402    }
403  }
404}
405
406bool LoadElimination::AbstractState::FieldsEquals(
407    AbstractFields const& this_fields,
408    AbstractFields const& that_fields) const {
409  for (size_t i = 0u; i < this_fields.size(); ++i) {
410    AbstractField const* this_field = this_fields[i];
411    AbstractField const* that_field = that_fields[i];
412    if (this_field) {
413      if (!that_field || !that_field->Equals(this_field)) return false;
414    } else if (that_field) {
415      return false;
416    }
417  }
418  return true;
419}
420
421bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
422  if (this->elements_) {
423    if (!that->elements_ || !that->elements_->Equals(this->elements_)) {
424      return false;
425    }
426  } else if (that->elements_) {
427    return false;
428  }
429  if (!FieldsEquals(this->fields_, that->fields_) ||
430      !FieldsEquals(this->const_fields_, that->const_fields_)) {
431    return false;
432  }
433  if (this->maps_) {
434    if (!that->maps_ || !that->maps_->Equals(this->maps_)) {
435      return false;
436    }
437  } else if (that->maps_) {
438    return false;
439  }
440  return true;
441}
442
443void LoadElimination::AbstractState::FieldsMerge(
444    AbstractFields* this_fields, AbstractFields const& that_fields,
445    Zone* zone) {
446  for (size_t i = 0; i < this_fields->size(); ++i) {
447    AbstractField const*& this_field = (*this_fields)[i];
448    if (this_field) {
449      if (that_fields[i]) {
450        this_field = this_field->Merge(that_fields[i], zone);
451      } else {
452        this_field = nullptr;
453      }
454    }
455  }
456}
457
458void LoadElimination::AbstractState::Merge(AbstractState const* that,
459                                           Zone* zone) {
460  // Merge the information we have about the elements.
461  if (this->elements_) {
462    this->elements_ = that->elements_
463                          ? that->elements_->Merge(this->elements_, zone)
464                          : nullptr;
465  }
466
467  // Merge the information we have about the fields.
468  FieldsMerge(&this->fields_, that->fields_, zone);
469  FieldsMerge(&this->const_fields_, that->const_fields_, zone);
470
471  // Merge the information we have about the maps.
472  if (this->maps_) {
473    this->maps_ = that->maps_ ? that->maps_->Merge(this->maps_, zone) : nullptr;
474  }
475}
476
477bool LoadElimination::AbstractState::LookupMaps(
478    Node* object, ZoneHandleSet<Map>* object_map) const {
479  return this->maps_ && this->maps_->Lookup(object, object_map);
480}
481
482LoadElimination::AbstractState const* LoadElimination::AbstractState::SetMaps(
483    Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
484  AbstractState* that = zone->New<AbstractState>(*this);
485  if (that->maps_) {
486    that->maps_ = that->maps_->Extend(object, maps, zone);
487  } else {
488    that->maps_ = zone->New<AbstractMaps>(object, maps, zone);
489  }
490  return that;
491}
492
493LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
494    const AliasStateInfo& alias_info, Zone* zone) const {
495  if (this->maps_) {
496    AbstractMaps const* that_maps = this->maps_->Kill(alias_info, zone);
497    if (this->maps_ != that_maps) {
498      AbstractState* that = zone->New<AbstractState>(*this);
499      that->maps_ = that_maps;
500      return that;
501    }
502  }
503  return this;
504}
505
506LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
507    Node* object, Zone* zone) const {
508  AliasStateInfo alias_info(this, object);
509  return KillMaps(alias_info, zone);
510}
511
512Node* LoadElimination::AbstractState::LookupElement(
513    Node* object, Node* index, MachineRepresentation representation) const {
514  if (this->elements_) {
515    return this->elements_->Lookup(object, index, representation);
516  }
517  return nullptr;
518}
519
520LoadElimination::AbstractState const*
521LoadElimination::AbstractState::AddElement(Node* object, Node* index,
522                                           Node* value,
523                                           MachineRepresentation representation,
524                                           Zone* zone) const {
525  AbstractState* that = zone->New<AbstractState>(*this);
526  if (that->elements_) {
527    that->elements_ =
528        that->elements_->Extend(object, index, value, representation, zone);
529  } else {
530    that->elements_ =
531        zone->New<AbstractElements>(object, index, value, representation, zone);
532  }
533  return that;
534}
535
536LoadElimination::AbstractState const*
537LoadElimination::AbstractState::KillElement(Node* object, Node* index,
538                                            Zone* zone) const {
539  if (this->elements_) {
540    AbstractElements const* that_elements =
541        this->elements_->Kill(object, index, zone);
542    if (this->elements_ != that_elements) {
543      AbstractState* that = zone->New<AbstractState>(*this);
544      that->elements_ = that_elements;
545      return that;
546    }
547  }
548  return this;
549}
550
551LoadElimination::AbstractState const* LoadElimination::AbstractState::AddField(
552    Node* object, IndexRange index_range, LoadElimination::FieldInfo info,
553    Zone* zone) const {
554  AbstractState* that = zone->New<AbstractState>(*this);
555  AbstractFields& fields =
556      info.const_field_info.IsConst() ? that->const_fields_ : that->fields_;
557  for (int index : index_range) {
558    if (fields[index]) {
559      fields[index] = fields[index]->Extend(object, info, zone);
560    } else {
561      fields[index] = zone->New<AbstractField>(object, info, zone);
562    }
563  }
564  return that;
565}
566
567LoadElimination::AbstractState const*
568LoadElimination::AbstractState::KillConstField(Node* object,
569                                               IndexRange index_range,
570                                               Zone* zone) const {
571  AliasStateInfo alias_info(this, object);
572  AbstractState* that = nullptr;
573  for (int index : index_range) {
574    if (AbstractField const* this_field = this->const_fields_[index]) {
575      this_field = this_field->KillConst(object, zone);
576      if (this->const_fields_[index] != this_field) {
577        if (!that) that = zone->New<AbstractState>(*this);
578        that->const_fields_[index] = this_field;
579      }
580    }
581  }
582  return that ? that : this;
583}
584
585LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
586    Node* object, IndexRange index_range, MaybeHandle<Name> name,
587    Zone* zone) const {
588  AliasStateInfo alias_info(this, object);
589  return KillField(alias_info, index_range, name, zone);
590}
591
592LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
593    const AliasStateInfo& alias_info, IndexRange index_range,
594    MaybeHandle<Name> name, Zone* zone) const {
595  AbstractState* that = nullptr;
596  for (int index : index_range) {
597    if (AbstractField const* this_field = this->fields_[index]) {
598      this_field = this_field->Kill(alias_info, name, zone);
599      if (this->fields_[index] != this_field) {
600        if (!that) that = zone->New<AbstractState>(*this);
601        that->fields_[index] = this_field;
602      }
603    }
604  }
605  return that ? that : this;
606}
607
608LoadElimination::AbstractState const*
609LoadElimination::AbstractState::KillFields(Node* object, MaybeHandle<Name> name,
610                                           Zone* zone) const {
611  AliasStateInfo alias_info(this, object);
612  for (size_t i = 0;; ++i) {
613    if (i == fields_.size()) return this;
614    if (AbstractField const* this_field = this->fields_[i]) {
615      AbstractField const* that_field =
616          this_field->Kill(alias_info, name, zone);
617      if (that_field != this_field) {
618        AbstractState* that = zone->New<AbstractState>(*this);
619        that->fields_[i] = that_field;
620        while (++i < fields_.size()) {
621          if (this->fields_[i] != nullptr) {
622            that->fields_[i] = this->fields_[i]->Kill(alias_info, name, zone);
623          }
624        }
625        return that;
626      }
627    }
628  }
629}
630
631LoadElimination::AbstractState const* LoadElimination::AbstractState::KillAll(
632    Zone* zone) const {
633  // Kill everything except for const fields
634  for (size_t i = 0; i < const_fields_.size(); ++i) {
635    if (const_fields_[i]) {
636      AbstractState* that = zone->New<AbstractState>();
637      that->const_fields_ = const_fields_;
638      return that;
639    }
640  }
641  return LoadElimination::empty_state();
642}
643
644LoadElimination::FieldInfo const* LoadElimination::AbstractState::LookupField(
645    Node* object, IndexRange index_range,
646    ConstFieldInfo const_field_info) const {
647  // Check if all the indices in {index_range} contain identical information.
648  // If not, a partially overlapping access has invalidated part of the value.
649  base::Optional<LoadElimination::FieldInfo const*> result;
650  for (int index : index_range) {
651    LoadElimination::FieldInfo const* info = nullptr;
652    if (const_field_info.IsConst()) {
653      if (AbstractField const* this_field = const_fields_[index]) {
654        info = this_field->Lookup(object);
655      }
656      if (!(info && info->const_field_info == const_field_info)) return nullptr;
657    } else {
658      if (AbstractField const* this_field = fields_[index]) {
659        info = this_field->Lookup(object);
660      }
661      if (!info) return nullptr;
662    }
663    if (!result.has_value()) {
664      result = info;
665    } else if (**result != *info) {
666      // We detected inconsistent information for a field here.
667      // This can happen when incomplete alias information makes an unrelated
668      // write invalidate part of a field and then we re-combine this partial
669      // information.
670      // This is probably OK, but since it's rare, we better bail out here.
671      return nullptr;
672    }
673  }
674  return *result;
675}
676
677bool LoadElimination::AliasStateInfo::MayAlias(Node* other) const {
678  // If {object} is being initialized right here (indicated by {object} being
679  // an Allocate node instead of a FinishRegion node), we know that {other}
680  // can only alias with {object} if they refer to exactly the same node.
681  if (object_->opcode() == IrOpcode::kAllocate) {
682    return object_ == other;
683  }
684  // Decide aliasing based on the node kinds.
685  if (!compiler::MayAlias(object_, other)) {
686    return false;
687  }
688  // Decide aliasing based on maps (if available).
689  Handle<Map> map;
690  if (map_.ToHandle(&map)) {
691    ZoneHandleSet<Map> other_maps;
692    if (state_->LookupMaps(other, &other_maps) && other_maps.size() == 1) {
693      if (map.address() != other_maps.at(0).address()) {
694        return false;
695      }
696    }
697  }
698  return true;
699}
700
701void LoadElimination::AbstractState::Print() const {
702  if (maps_) {
703    PrintF("   maps:\n");
704    maps_->Print();
705  }
706  if (elements_) {
707    PrintF("   elements:\n");
708    elements_->Print();
709  }
710  for (size_t i = 0; i < fields_.size(); ++i) {
711    if (AbstractField const* const field = fields_[i]) {
712      PrintF("   field %zu:\n", i);
713      field->Print();
714    }
715  }
716  for (size_t i = 0; i < const_fields_.size(); ++i) {
717    if (AbstractField const* const const_field = const_fields_[i]) {
718      PrintF("   const field %zu:\n", i);
719      const_field->Print();
720    }
721  }
722}
723
724LoadElimination::AbstractState const*
725LoadElimination::AbstractStateForEffectNodes::Get(Node* node) const {
726  size_t const id = node->id();
727  if (id < info_for_node_.size()) return info_for_node_[id];
728  return nullptr;
729}
730
731void LoadElimination::AbstractStateForEffectNodes::Set(
732    Node* node, AbstractState const* state) {
733  size_t const id = node->id();
734  if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
735  info_for_node_[id] = state;
736}
737
738Reduction LoadElimination::ReduceMapGuard(Node* node) {
739  ZoneHandleSet<Map> const& maps = MapGuardMapsOf(node->op());
740  Node* const object = NodeProperties::GetValueInput(node, 0);
741  Node* const effect = NodeProperties::GetEffectInput(node);
742  AbstractState const* state = node_states_.Get(effect);
743  if (state == nullptr) return NoChange();
744  ZoneHandleSet<Map> object_maps;
745  if (state->LookupMaps(object, &object_maps)) {
746    if (maps.contains(object_maps)) return Replace(effect);
747    // TODO(turbofan): Compute the intersection.
748  }
749  state = state->SetMaps(object, maps, zone());
750  return UpdateState(node, state);
751}
752
753Reduction LoadElimination::ReduceCheckMaps(Node* node) {
754  ZoneHandleSet<Map> const& maps = CheckMapsParametersOf(node->op()).maps();
755  Node* const object = NodeProperties::GetValueInput(node, 0);
756  Node* const effect = NodeProperties::GetEffectInput(node);
757  AbstractState const* state = node_states_.Get(effect);
758  if (state == nullptr) return NoChange();
759  ZoneHandleSet<Map> object_maps;
760  if (state->LookupMaps(object, &object_maps)) {
761    if (maps.contains(object_maps)) return Replace(effect);
762    // TODO(turbofan): Compute the intersection.
763  }
764  state = state->SetMaps(object, maps, zone());
765  return UpdateState(node, state);
766}
767
768Reduction LoadElimination::ReduceCompareMaps(Node* node) {
769  ZoneHandleSet<Map> const& maps = CompareMapsParametersOf(node->op());
770  Node* const object = NodeProperties::GetValueInput(node, 0);
771  Node* const effect = NodeProperties::GetEffectInput(node);
772  AbstractState const* state = node_states_.Get(effect);
773  if (state == nullptr) return NoChange();
774  ZoneHandleSet<Map> object_maps;
775  if (state->LookupMaps(object, &object_maps)) {
776    if (maps.contains(object_maps)) {
777      Node* value = jsgraph()->TrueConstant();
778      ReplaceWithValue(node, value, effect);
779      return Replace(value);
780    }
781    // TODO(turbofan): Compute the intersection.
782  }
783  return UpdateState(node, state);
784}
785
786Reduction LoadElimination::ReduceEnsureWritableFastElements(Node* node) {
787  Node* const object = NodeProperties::GetValueInput(node, 0);
788  Node* const elements = NodeProperties::GetValueInput(node, 1);
789  Node* const effect = NodeProperties::GetEffectInput(node);
790  AbstractState const* state = node_states_.Get(effect);
791  if (state == nullptr) return NoChange();
792  // Check if the {elements} already have the fixed array map.
793  ZoneHandleSet<Map> elements_maps;
794  ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
795  if (state->LookupMaps(elements, &elements_maps) &&
796      fixed_array_maps.contains(elements_maps)) {
797    ReplaceWithValue(node, elements, effect);
798    return Replace(elements);
799  }
800  // We know that the resulting elements have the fixed array map.
801  state = state->SetMaps(node, fixed_array_maps, zone());
802  // Kill the previous elements on {object}.
803  state = state->KillField(object,
804                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
805                           MaybeHandle<Name>(), zone());
806  // Add the new elements on {object}.
807  state = state->AddField(
808      object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
809      {node, MachineRepresentation::kTaggedPointer}, zone());
810  return UpdateState(node, state);
811}
812
813Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
814  GrowFastElementsParameters params = GrowFastElementsParametersOf(node->op());
815  Node* const object = NodeProperties::GetValueInput(node, 0);
816  Node* const effect = NodeProperties::GetEffectInput(node);
817  AbstractState const* state = node_states_.Get(effect);
818  if (state == nullptr) return NoChange();
819  if (params.mode() == GrowFastElementsMode::kDoubleElements) {
820    // We know that the resulting elements have the fixed double array map.
821    state = state->SetMaps(
822        node, ZoneHandleSet<Map>(factory()->fixed_double_array_map()), zone());
823  } else {
824    // We know that the resulting elements have the fixed array map or the COW
825    // version thereof (if we didn't grow and it was already COW before).
826    ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
827    fixed_array_maps.insert(factory()->fixed_cow_array_map(), zone());
828    state = state->SetMaps(node, fixed_array_maps, zone());
829  }
830  // Kill the previous elements on {object}.
831  state = state->KillField(object,
832                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
833                           MaybeHandle<Name>(), zone());
834  // Add the new elements on {object}.
835  state = state->AddField(
836      object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
837      {node, MachineRepresentation::kTaggedPointer}, zone());
838  return UpdateState(node, state);
839}
840
841Reduction LoadElimination::ReduceTransitionElementsKind(Node* node) {
842  ElementsTransition transition = ElementsTransitionOf(node->op());
843  Node* const object = NodeProperties::GetValueInput(node, 0);
844  Handle<Map> source_map(transition.source());
845  Handle<Map> target_map(transition.target());
846  Node* const effect = NodeProperties::GetEffectInput(node);
847  AbstractState const* state = node_states_.Get(effect);
848  if (state == nullptr) return NoChange();
849  switch (transition.mode()) {
850    case ElementsTransition::kFastTransition:
851      break;
852    case ElementsTransition::kSlowTransition:
853      // Kill the elements as well.
854      AliasStateInfo alias_info(state, object, source_map);
855      state = state->KillField(
856          alias_info, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
857          MaybeHandle<Name>(), zone());
858      break;
859  }
860  ZoneHandleSet<Map> object_maps;
861  if (state->LookupMaps(object, &object_maps)) {
862    if (ZoneHandleSet<Map>(target_map).contains(object_maps)) {
863      // The {object} already has the {target_map}, so this TransitionElements
864      // {node} is fully redundant (independent of what {source_map} is).
865      return Replace(effect);
866    }
867    if (object_maps.contains(ZoneHandleSet<Map>(source_map))) {
868      object_maps.remove(source_map, zone());
869      object_maps.insert(target_map, zone());
870      AliasStateInfo alias_info(state, object, source_map);
871      state = state->KillMaps(alias_info, zone());
872      state = state->SetMaps(object, object_maps, zone());
873    }
874  } else {
875    AliasStateInfo alias_info(state, object, source_map);
876    state = state->KillMaps(alias_info, zone());
877  }
878  return UpdateState(node, state);
879}
880
881Reduction LoadElimination::ReduceTransitionAndStoreElement(Node* node) {
882  Node* const object = NodeProperties::GetValueInput(node, 0);
883  Handle<Map> double_map(DoubleMapParameterOf(node->op()));
884  Handle<Map> fast_map(FastMapParameterOf(node->op()));
885  Node* const effect = NodeProperties::GetEffectInput(node);
886  AbstractState const* state = node_states_.Get(effect);
887  if (state == nullptr) return NoChange();
888
889  // We need to add the double and fast maps to the set of possible maps for
890  // this object, because we don't know which of those we'll transition to.
891  // Additionally, we should kill all alias information.
892  ZoneHandleSet<Map> object_maps;
893  if (state->LookupMaps(object, &object_maps)) {
894    object_maps.insert(double_map, zone());
895    object_maps.insert(fast_map, zone());
896    state = state->KillMaps(object, zone());
897    state = state->SetMaps(object, object_maps, zone());
898  }
899  // Kill the elements as well.
900  state = state->KillField(object,
901                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
902                           MaybeHandle<Name>(), zone());
903  return UpdateState(node, state);
904}
905
906Reduction LoadElimination::ReduceLoadField(Node* node,
907                                           FieldAccess const& access) {
908  Node* object = NodeProperties::GetValueInput(node, 0);
909  Node* effect = NodeProperties::GetEffectInput(node);
910  Node* control = NodeProperties::GetControlInput(node);
911  AbstractState const* state = node_states_.Get(effect);
912  if (state == nullptr) return NoChange();
913  if (access.offset == HeapObject::kMapOffset &&
914      access.base_is_tagged == kTaggedBase) {
915    DCHECK(IsAnyTagged(access.machine_type.representation()));
916    ZoneHandleSet<Map> object_maps;
917    if (state->LookupMaps(object, &object_maps) && object_maps.size() == 1) {
918      Node* value = jsgraph()->HeapConstant(object_maps[0]);
919      NodeProperties::SetType(value, Type::OtherInternal());
920      ReplaceWithValue(node, value, effect);
921      return Replace(value);
922    }
923  } else {
924    IndexRange field_index = FieldIndexOf(access);
925    if (field_index != IndexRange::Invalid()) {
926      MachineRepresentation representation =
927          access.machine_type.representation();
928      FieldInfo const* lookup_result =
929          state->LookupField(object, field_index, access.const_field_info);
930      if (!lookup_result && access.const_field_info.IsConst()) {
931        // If the access is const and we didn't find anything, also try to look
932        // up information from mutable stores
933        lookup_result =
934            state->LookupField(object, field_index, ConstFieldInfo::None());
935      }
936      if (lookup_result) {
937        // Make sure we don't reuse values that were recorded with a different
938        // representation or resurrect dead {replacement} nodes.
939        Node* replacement = lookup_result->value;
940        if (IsCompatible(representation, lookup_result->representation) &&
941            !replacement->IsDead()) {
942          // Introduce a TypeGuard if the type of the {replacement} node is not
943          // a subtype of the original {node}'s type.
944          if (!NodeProperties::GetType(replacement)
945                   .Is(NodeProperties::GetType(node))) {
946            Type replacement_type = Type::Intersect(
947                NodeProperties::GetType(node),
948                NodeProperties::GetType(replacement), graph()->zone());
949            replacement = effect =
950                graph()->NewNode(common()->TypeGuard(replacement_type),
951                                 replacement, effect, control);
952            NodeProperties::SetType(replacement, replacement_type);
953          }
954          ReplaceWithValue(node, replacement, effect);
955          return Replace(replacement);
956        }
957      }
958      FieldInfo info(node, representation, access.name,
959                     access.const_field_info);
960      state = state->AddField(object, field_index, info, zone());
961    }
962  }
963  Handle<Map> field_map;
964  if (access.map.ToHandle(&field_map)) {
965    state = state->SetMaps(node, ZoneHandleSet<Map>(field_map), zone());
966  }
967  return UpdateState(node, state);
968}
969
970Reduction LoadElimination::ReduceStoreField(Node* node,
971                                            FieldAccess const& access) {
972  Node* const object = NodeProperties::GetValueInput(node, 0);
973  Node* const new_value = NodeProperties::GetValueInput(node, 1);
974  Node* const effect = NodeProperties::GetEffectInput(node);
975  AbstractState const* state = node_states_.Get(effect);
976  if (state == nullptr) return NoChange();
977  if (access.offset == HeapObject::kMapOffset &&
978      access.base_is_tagged == kTaggedBase) {
979    DCHECK(IsAnyTagged(access.machine_type.representation()));
980    // Kill all potential knowledge about the {object}s map.
981    state = state->KillMaps(object, zone());
982    Type const new_value_type = NodeProperties::GetType(new_value);
983    if (new_value_type.IsHeapConstant()) {
984      // Record the new {object} map information.
985      ZoneHandleSet<Map> object_maps(
986          new_value_type.AsHeapConstant()->Ref().AsMap().object());
987      state = state->SetMaps(object, object_maps, zone());
988    }
989  } else {
990    IndexRange field_index = FieldIndexOf(access);
991    if (field_index != IndexRange::Invalid()) {
992      bool is_const_store = access.const_field_info.IsConst();
993      MachineRepresentation representation =
994          access.machine_type.representation();
995      FieldInfo const* lookup_result =
996          state->LookupField(object, field_index, access.const_field_info);
997
998      if (lookup_result &&
999          (!is_const_store || V8_ENABLE_DOUBLE_CONST_STORE_CHECK_BOOL)) {
1000        // At runtime, we should never encounter
1001        // - any store replacing existing info with a different, incompatible
1002        //   representation, nor
1003        // - two consecutive const stores, unless the latter is a store into
1004        //   a literal.
1005        // However, we may see such code statically, so we guard against
1006        // executing it by emitting Unreachable.
1007        // TODO(gsps): Re-enable the double const store check even for
1008        //   non-debug builds once we have identified other FieldAccesses
1009        //   that should be marked mutable instead of const
1010        //   (cf. JSCreateLowering::AllocateFastLiteral).
1011        bool incompatible_representation =
1012            !lookup_result->name.is_null() &&
1013            !IsCompatible(representation, lookup_result->representation);
1014        bool illegal_double_const_store =
1015            is_const_store && !access.is_store_in_literal;
1016        if (incompatible_representation || illegal_double_const_store) {
1017          Node* control = NodeProperties::GetControlInput(node);
1018          Node* unreachable =
1019              graph()->NewNode(common()->Unreachable(), effect, control);
1020          return Replace(unreachable);
1021        }
1022        if (lookup_result->value == new_value) {
1023          // This store is fully redundant.
1024          return Replace(effect);
1025        }
1026      }
1027
1028      // Kill all potentially aliasing fields and record the new value.
1029      FieldInfo new_info(new_value, representation, access.name,
1030                         access.const_field_info);
1031      if (is_const_store && access.is_store_in_literal) {
1032        // We only kill const information when there is a chance that we
1033        // previously stored information about the given const field (namely,
1034        // when we observe const stores to literals).
1035        state = state->KillConstField(object, field_index, zone());
1036      }
1037      state = state->KillField(object, field_index, access.name, zone());
1038      state = state->AddField(object, field_index, new_info, zone());
1039      if (is_const_store) {
1040        // For const stores, we track information in both the const and the
1041        // mutable world to guard against field accesses that should have
1042        // been marked const, but were not.
1043        new_info.const_field_info = ConstFieldInfo::None();
1044        state = state->AddField(object, field_index, new_info, zone());
1045      }
1046    } else {
1047      // Unsupported StoreField operator.
1048      state = state->KillFields(object, access.name, zone());
1049    }
1050  }
1051  return UpdateState(node, state);
1052}
1053
1054Reduction LoadElimination::ReduceLoadElement(Node* node) {
1055  Node* const object = NodeProperties::GetValueInput(node, 0);
1056  Node* const index = NodeProperties::GetValueInput(node, 1);
1057  Node* const effect = NodeProperties::GetEffectInput(node);
1058  AbstractState const* state = node_states_.Get(effect);
1059  if (state == nullptr) return NoChange();
1060
1061  // Only handle loads that do not require truncations.
1062  ElementAccess const& access = ElementAccessOf(node->op());
1063  switch (access.machine_type.representation()) {
1064    case MachineRepresentation::kNone:
1065    case MachineRepresentation::kBit:
1066    case MachineRepresentation::kWord8:
1067    case MachineRepresentation::kWord16:
1068    case MachineRepresentation::kWord32:
1069    case MachineRepresentation::kWord64:
1070    case MachineRepresentation::kFloat32:
1071    case MachineRepresentation::kCompressedPointer:
1072    case MachineRepresentation::kCompressed:
1073    case MachineRepresentation::kSandboxedPointer:
1074      // TODO(turbofan): Add support for doing the truncations.
1075      break;
1076    case MachineRepresentation::kFloat64:
1077    case MachineRepresentation::kSimd128:
1078    case MachineRepresentation::kTaggedSigned:
1079    case MachineRepresentation::kTaggedPointer:
1080    case MachineRepresentation::kTagged:
1081    case MachineRepresentation::kMapWord:
1082      if (Node* replacement = state->LookupElement(
1083              object, index, access.machine_type.representation())) {
1084        // Make sure we don't resurrect dead {replacement} nodes.
1085        // Skip lowering if the type of the {replacement} node is not a subtype
1086        // of the original {node}'s type.
1087        // TODO(turbofan): We should insert a {TypeGuard} for the intersection
1088        // of these two types here once we properly handle {Type::None}
1089        // everywhere.
1090        if (!replacement->IsDead() && NodeProperties::GetType(replacement)
1091                                          .Is(NodeProperties::GetType(node))) {
1092          ReplaceWithValue(node, replacement, effect);
1093          return Replace(replacement);
1094        }
1095      }
1096      state = state->AddElement(object, index, node,
1097                                access.machine_type.representation(), zone());
1098      return UpdateState(node, state);
1099  }
1100  return NoChange();
1101}
1102
1103Reduction LoadElimination::ReduceStoreElement(Node* node) {
1104  ElementAccess const& access = ElementAccessOf(node->op());
1105  Node* const object = NodeProperties::GetValueInput(node, 0);
1106  Node* const index = NodeProperties::GetValueInput(node, 1);
1107  Node* const new_value = NodeProperties::GetValueInput(node, 2);
1108  Node* const effect = NodeProperties::GetEffectInput(node);
1109  AbstractState const* state = node_states_.Get(effect);
1110  if (state == nullptr) return NoChange();
1111  Node* const old_value =
1112      state->LookupElement(object, index, access.machine_type.representation());
1113  if (old_value == new_value) {
1114    // This store is fully redundant.
1115    return Replace(effect);
1116  }
1117  // Kill all potentially aliasing elements.
1118  state = state->KillElement(object, index, zone());
1119  // Only record the new value if the store doesn't have an implicit truncation.
1120  switch (access.machine_type.representation()) {
1121    case MachineRepresentation::kNone:
1122    case MachineRepresentation::kBit:
1123    case MachineRepresentation::kWord8:
1124    case MachineRepresentation::kWord16:
1125    case MachineRepresentation::kWord32:
1126    case MachineRepresentation::kWord64:
1127    case MachineRepresentation::kFloat32:
1128    case MachineRepresentation::kCompressedPointer:
1129    case MachineRepresentation::kCompressed:
1130    case MachineRepresentation::kSandboxedPointer:
1131      // TODO(turbofan): Add support for doing the truncations.
1132      break;
1133    case MachineRepresentation::kFloat64:
1134    case MachineRepresentation::kSimd128:
1135    case MachineRepresentation::kTaggedSigned:
1136    case MachineRepresentation::kTaggedPointer:
1137    case MachineRepresentation::kTagged:
1138    case MachineRepresentation::kMapWord:
1139      state = state->AddElement(object, index, new_value,
1140                                access.machine_type.representation(), zone());
1141      break;
1142  }
1143  return UpdateState(node, state);
1144}
1145
1146Reduction LoadElimination::ReduceStoreTypedElement(Node* node) {
1147  Node* const effect = NodeProperties::GetEffectInput(node);
1148  AbstractState const* state = node_states_.Get(effect);
1149  if (state == nullptr) return NoChange();
1150  return UpdateState(node, state);
1151}
1152
1153LoadElimination::AbstractState const* LoadElimination::UpdateStateForPhi(
1154    AbstractState const* state, Node* effect_phi, Node* phi) {
1155  int predecessor_count = phi->InputCount() - 1;
1156  // TODO(jarin) Consider doing a union here. At the moment, we just keep this
1157  // consistent with AbstractState::Merge.
1158
1159  // Check if all the inputs have the same maps.
1160  AbstractState const* input_state =
1161      node_states_.Get(NodeProperties::GetEffectInput(effect_phi, 0));
1162  ZoneHandleSet<Map> object_maps;
1163  if (!input_state->LookupMaps(phi->InputAt(0), &object_maps)) return state;
1164  for (int i = 1; i < predecessor_count; i++) {
1165    input_state =
1166        node_states_.Get(NodeProperties::GetEffectInput(effect_phi, i));
1167    ZoneHandleSet<Map> input_maps;
1168    if (!input_state->LookupMaps(phi->InputAt(i), &input_maps)) return state;
1169    if (input_maps != object_maps) return state;
1170  }
1171  return state->SetMaps(phi, object_maps, zone());
1172}
1173
1174Reduction LoadElimination::ReduceEffectPhi(Node* node) {
1175  Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
1176  Node* const control = NodeProperties::GetControlInput(node);
1177  AbstractState const* state0 = node_states_.Get(effect0);
1178  if (state0 == nullptr) return NoChange();
1179  if (control->opcode() == IrOpcode::kLoop) {
1180    // Here we rely on having only reducible loops:
1181    // The loop entry edge always dominates the header, so we can just take
1182    // the state from the first input, and compute the loop state based on it.
1183    AbstractState const* state = ComputeLoopState(node, state0);
1184    return UpdateState(node, state);
1185  }
1186  DCHECK_EQ(IrOpcode::kMerge, control->opcode());
1187
1188  // Shortcut for the case when we do not know anything about some input.
1189  int const input_count = node->op()->EffectInputCount();
1190  for (int i = 1; i < input_count; ++i) {
1191    Node* const effect = NodeProperties::GetEffectInput(node, i);
1192    if (node_states_.Get(effect) == nullptr) return NoChange();
1193  }
1194
1195  // Make a copy of the first input's state and merge with the state
1196  // from other inputs.
1197  AbstractState* state = zone()->New<AbstractState>(*state0);
1198  for (int i = 1; i < input_count; ++i) {
1199    Node* const input = NodeProperties::GetEffectInput(node, i);
1200    state->Merge(node_states_.Get(input), zone());
1201  }
1202
1203  // For each phi, try to compute the new state for the phi from
1204  // the inputs.
1205  AbstractState const* state_with_phis = state;
1206  for (Node* use : control->uses()) {
1207    if (use->opcode() == IrOpcode::kPhi) {
1208      state_with_phis = UpdateStateForPhi(state_with_phis, node, use);
1209    }
1210  }
1211
1212  return UpdateState(node, state_with_phis);
1213}
1214
1215Reduction LoadElimination::ReduceStart(Node* node) {
1216  return UpdateState(node, empty_state());
1217}
1218
1219Reduction LoadElimination::ReduceOtherNode(Node* node) {
1220  if (node->op()->EffectInputCount() == 1) {
1221    if (node->op()->EffectOutputCount() == 1) {
1222      Node* const effect = NodeProperties::GetEffectInput(node);
1223      AbstractState const* state = node_states_.Get(effect);
1224      // If we do not know anything about the predecessor, do not propagate
1225      // just yet because we will have to recompute anyway once we compute
1226      // the predecessor.
1227      if (state == nullptr) return NoChange();
1228      // Check if this {node} has some uncontrolled side effects.
1229      if (!node->op()->HasProperty(Operator::kNoWrite)) {
1230        state = state->KillAll(zone());
1231      }
1232      return UpdateState(node, state);
1233    } else {
1234      // Effect terminators should be handled specially.
1235      return NoChange();
1236    }
1237  }
1238  DCHECK_EQ(0, node->op()->EffectInputCount());
1239  DCHECK_EQ(0, node->op()->EffectOutputCount());
1240  return NoChange();
1241}
1242
1243Reduction LoadElimination::UpdateState(Node* node, AbstractState const* state) {
1244  AbstractState const* original = node_states_.Get(node);
1245  // Only signal that the {node} has Changed, if the information about {state}
1246  // has changed wrt. the {original}.
1247  if (state != original) {
1248    if (original == nullptr || !state->Equals(original)) {
1249      node_states_.Set(node, state);
1250      return Changed(node);
1251    }
1252  }
1253  return NoChange();
1254}
1255
1256LoadElimination::AbstractState const*
1257LoadElimination::ComputeLoopStateForStoreField(
1258    Node* current, LoadElimination::AbstractState const* state,
1259    FieldAccess const& access) const {
1260  Node* const object = NodeProperties::GetValueInput(current, 0);
1261  if (access.offset == HeapObject::kMapOffset) {
1262    // Invalidate what we know about the {object}s map.
1263    state = state->KillMaps(object, zone());
1264  } else {
1265    IndexRange field_index = FieldIndexOf(access);
1266    if (field_index == IndexRange::Invalid()) {
1267      state = state->KillFields(object, access.name, zone());
1268    } else {
1269      state = state->KillField(object, field_index, access.name, zone());
1270    }
1271  }
1272  return state;
1273}
1274
1275LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
1276    Node* node, AbstractState const* state) const {
1277  Node* const control = NodeProperties::GetControlInput(node);
1278  struct TransitionElementsKindInfo {
1279    ElementsTransition transition;
1280    Node* object;
1281  };
1282  // Allocate zone data structures in a temporary zone with a lifetime limited
1283  // to this function to avoid blowing up the size of the stage-global zone.
1284  Zone temp_zone(zone()->allocator(), "Temporary scoped zone");
1285  ZoneVector<TransitionElementsKindInfo> element_transitions_(&temp_zone);
1286  ZoneQueue<Node*> queue(&temp_zone);
1287  ZoneSet<Node*> visited(&temp_zone);
1288  visited.insert(node);
1289  for (int i = 1; i < control->InputCount(); ++i) {
1290    queue.push(node->InputAt(i));
1291  }
1292  while (!queue.empty()) {
1293    Node* const current = queue.front();
1294    queue.pop();
1295    if (visited.find(current) == visited.end()) {
1296      visited.insert(current);
1297      if (!current->op()->HasProperty(Operator::kNoWrite)) {
1298        switch (current->opcode()) {
1299          case IrOpcode::kEnsureWritableFastElements: {
1300            Node* const object = NodeProperties::GetValueInput(current, 0);
1301            state = state->KillField(
1302                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
1303                MaybeHandle<Name>(), zone());
1304            break;
1305          }
1306          case IrOpcode::kMaybeGrowFastElements: {
1307            Node* const object = NodeProperties::GetValueInput(current, 0);
1308            state = state->KillField(
1309                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
1310                MaybeHandle<Name>(), zone());
1311            break;
1312          }
1313          case IrOpcode::kTransitionElementsKind: {
1314            ElementsTransition transition = ElementsTransitionOf(current->op());
1315            Node* const object = NodeProperties::GetValueInput(current, 0);
1316            ZoneHandleSet<Map> object_maps;
1317            if (!state->LookupMaps(object, &object_maps) ||
1318                !ZoneHandleSet<Map>(transition.target())
1319                     .contains(object_maps)) {
1320              element_transitions_.push_back({transition, object});
1321            }
1322            break;
1323          }
1324          case IrOpcode::kTransitionAndStoreElement: {
1325            Node* const object = NodeProperties::GetValueInput(current, 0);
1326            // Invalidate what we know about the {object}s map.
1327            state = state->KillMaps(object, zone());
1328            // Kill the elements as well.
1329            state = state->KillField(
1330                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
1331                MaybeHandle<Name>(), zone());
1332            break;
1333          }
1334          case IrOpcode::kStoreField: {
1335            FieldAccess access = FieldAccessOf(current->op());
1336            state = ComputeLoopStateForStoreField(current, state, access);
1337            break;
1338          }
1339          case IrOpcode::kStoreElement: {
1340            Node* const object = NodeProperties::GetValueInput(current, 0);
1341            Node* const index = NodeProperties::GetValueInput(current, 1);
1342            state = state->KillElement(object, index, zone());
1343            break;
1344          }
1345          case IrOpcode::kStoreTypedElement: {
1346            // Doesn't affect anything we track with the state currently.
1347            break;
1348          }
1349          default:
1350            return state->KillAll(zone());
1351        }
1352      }
1353      for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
1354        queue.push(NodeProperties::GetEffectInput(current, i));
1355      }
1356    }
1357  }
1358
1359  // Finally, we apply the element transitions. For each transition, we will try
1360  // to only invalidate information about nodes that can have the transition's
1361  // source map. The trouble is that an object can be transitioned by some other
1362  // transition to the source map. In that case, the other transition will
1363  // invalidate the information, so we are mostly fine.
1364  //
1365  // The only bad case is
1366  //
1367  //    mapA   ---fast--->   mapB   ---slow--->   mapC
1368  //
1369  // If we process the slow transition first on an object that has mapA, we will
1370  // ignore the transition because the object does not have its source map
1371  // (mapB). When we later process the fast transition, we invalidate the
1372  // object's map, but we keep the information about the object's elements. This
1373  // is wrong because the elements will be overwritten by the slow transition.
1374  //
1375  // Note that the slow-slow case is fine because either of the slow transition
1376  // will invalidate the elements field, so the processing order does not
1377  // matter.
1378  //
1379  // To handle the bad case properly, we first kill the maps using all
1380  // transitions. We kill the the fields later when all the transitions are
1381  // already reflected in the map information.
1382
1383  for (const TransitionElementsKindInfo& t : element_transitions_) {
1384    AliasStateInfo alias_info(state, t.object, t.transition.source());
1385    state = state->KillMaps(alias_info, zone());
1386  }
1387  for (const TransitionElementsKindInfo& t : element_transitions_) {
1388    switch (t.transition.mode()) {
1389      case ElementsTransition::kFastTransition:
1390        break;
1391      case ElementsTransition::kSlowTransition: {
1392        AliasStateInfo alias_info(state, t.object, t.transition.source());
1393        state = state->KillField(
1394            alias_info, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
1395            MaybeHandle<Name>(), zone());
1396        break;
1397      }
1398    }
1399  }
1400  return state;
1401}
1402
1403// static
1404LoadElimination::IndexRange LoadElimination::FieldIndexOf(
1405    int offset, int representation_size) {
1406  DCHECK(IsAligned(offset, kTaggedSize));
1407  int field_index = offset / kTaggedSize - 1;
1408  DCHECK_EQ(0, representation_size % kTaggedSize);
1409  return IndexRange(field_index, representation_size / kTaggedSize);
1410}
1411
1412// static
1413LoadElimination::IndexRange LoadElimination::FieldIndexOf(
1414    FieldAccess const& access) {
1415  MachineRepresentation rep = access.machine_type.representation();
1416  switch (rep) {
1417    case MachineRepresentation::kNone:
1418    case MachineRepresentation::kBit:
1419    case MachineRepresentation::kSimd128:
1420      UNREACHABLE();
1421    case MachineRepresentation::kWord8:
1422    case MachineRepresentation::kWord16:
1423    case MachineRepresentation::kFloat32:
1424      // Currently untracked.
1425      return IndexRange::Invalid();
1426    case MachineRepresentation::kFloat64:
1427    case MachineRepresentation::kWord32:
1428    case MachineRepresentation::kWord64:
1429    case MachineRepresentation::kTaggedSigned:
1430    case MachineRepresentation::kTaggedPointer:
1431    case MachineRepresentation::kTagged:
1432    case MachineRepresentation::kMapWord:
1433    case MachineRepresentation::kCompressedPointer:
1434    case MachineRepresentation::kCompressed:
1435    case MachineRepresentation::kSandboxedPointer:
1436      break;
1437  }
1438  int representation_size = ElementSizeInBytes(rep);
1439  // We currently only track fields that are at least tagged pointer sized.
1440  if (representation_size < kTaggedSize) return IndexRange::Invalid();
1441  DCHECK_EQ(0, representation_size % kTaggedSize);
1442
1443  if (access.base_is_tagged != kTaggedBase) {
1444    // We currently only track tagged objects.
1445    return IndexRange::Invalid();
1446  }
1447  return FieldIndexOf(access.offset, representation_size);
1448}
1449
1450CommonOperatorBuilder* LoadElimination::common() const {
1451  return jsgraph()->common();
1452}
1453
1454Graph* LoadElimination::graph() const { return jsgraph()->graph(); }
1455
1456Isolate* LoadElimination::isolate() const { return jsgraph()->isolate(); }
1457
1458Factory* LoadElimination::factory() const { return jsgraph()->factory(); }
1459
1460}  // namespace compiler
1461}  // namespace internal
1462}  // namespace v8
1463