load-elimination.cc 53.9 KB
Newer Older
1
// Copyright 2016 the V8 project authors. All rights reserved.
2 3 4 5 6
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/load-elimination.h"

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 14 15 16 17

namespace v8 {
namespace internal {
namespace compiler {

18 19
namespace {

20 21
bool IsRename(Node* node) {
  switch (node->opcode()) {
22
    case IrOpcode::kCheckHeapObject:
23 24
    case IrOpcode::kFinishRegion:
    case IrOpcode::kTypeGuard:
25
      return !node->IsDead();
26 27 28 29 30 31 32 33 34 35 36
    default:
      return false;
  }
}

Node* ResolveRenames(Node* node) {
  while (IsRename(node)) {
    node = node->InputAt(0);
  }
  return node;
}
37

38
bool MayAlias(Node* a, Node* b) {
39 40 41 42 43 44 45 46
  if (a != b) {
    if (!NodeProperties::GetType(a).Maybe(NodeProperties::GetType(b))) {
      return false;
    } else if (IsRename(b)) {
      return MayAlias(a, b->InputAt(0));
    } else if (IsRename(a)) {
      return MayAlias(a->InputAt(0), b);
    } else if (b->opcode() == IrOpcode::kAllocate) {
47 48 49 50
      switch (a->opcode()) {
        case IrOpcode::kAllocate:
        case IrOpcode::kHeapConstant:
        case IrOpcode::kParameter:
51
          return false;
52 53 54
        default:
          break;
      }
55
    } else if (a->opcode() == IrOpcode::kAllocate) {
56 57 58
      switch (b->opcode()) {
        case IrOpcode::kHeapConstant:
        case IrOpcode::kParameter:
59
          return false;
60 61 62
        default:
          break;
      }
63 64
    }
  }
65
  return true;
66 67
}

68 69 70
bool MustAlias(Node* a, Node* b) {
  return ResolveRenames(a) == ResolveRenames(b);
}
71

72
}  // namespace
73

74
Reduction LoadElimination::Reduce(Node* node) {
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
  if (FLAG_trace_turbo_load_elimination) {
    if (node->op()->EffectInputCount() > 0) {
      PrintF(" visit #%d:%s", node->id(), node->op()->mnemonic());
      if (node->op()->ValueInputCount() > 0) {
        PrintF("(");
        for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
          if (i > 0) PrintF(", ");
          Node* const value = NodeProperties::GetValueInput(node, i);
          PrintF("#%d:%s", value->id(), value->op()->mnemonic());
        }
        PrintF(")");
      }
      PrintF("\n");
      for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
        Node* const effect = NodeProperties::GetEffectInput(node, i);
        if (AbstractState const* const state = node_states_.Get(effect)) {
          PrintF("  state[%i]: #%d:%s\n", i, effect->id(),
                 effect->op()->mnemonic());
          state->Print();
        } else {
          PrintF("  no state[%i]: #%d:%s\n", i, effect->id(),
                 effect->op()->mnemonic());
        }
      }
    }
  }
101
  switch (node->opcode()) {
102 103
    case IrOpcode::kMapGuard:
      return ReduceMapGuard(node);
104 105
    case IrOpcode::kCheckMaps:
      return ReduceCheckMaps(node);
106 107
    case IrOpcode::kCompareMaps:
      return ReduceCompareMaps(node);
108 109
    case IrOpcode::kEnsureWritableFastElements:
      return ReduceEnsureWritableFastElements(node);
110 111
    case IrOpcode::kMaybeGrowFastElements:
      return ReduceMaybeGrowFastElements(node);
112 113
    case IrOpcode::kTransitionElementsKind:
      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 119 120 121
    case IrOpcode::kLoadElement:
      return ReduceLoadElement(node);
    case IrOpcode::kStoreElement:
      return ReduceStoreElement(node);
122 123
    case IrOpcode::kTransitionAndStoreElement:
      return ReduceTransitionAndStoreElement(node);
124 125
    case IrOpcode::kStoreTypedElement:
      return ReduceStoreTypedElement(node);
126 127 128 129 130 131 132 133
    case IrOpcode::kEffectPhi:
      return ReduceEffectPhi(node);
    case IrOpcode::kDead:
      break;
    case IrOpcode::kStart:
      return ReduceStart(node);
    default:
      return ReduceOtherNode(node);
134
  }
135 136 137
  return NoChange();
}

138 139
namespace {

140 141
bool IsCompatible(MachineRepresentation r1, MachineRepresentation r2) {
  if (r1 == r2) return true;
142
  return IsAnyTagged(r1) && IsAnyTagged(r2);
143 144 145 146
}

}  // namespace

147 148 149
LoadElimination::AbstractState const
    LoadElimination::AbstractState::empty_state_;

150 151
Node* LoadElimination::AbstractElements::Lookup(
    Node* object, Node* index, MachineRepresentation representation) const {
152 153 154 155
  for (Element const element : elements_) {
    if (element.object == nullptr) continue;
    DCHECK_NOT_NULL(element.index);
    DCHECK_NOT_NULL(element.value);
156 157
    if (MustAlias(object, element.object) && MustAlias(index, element.index) &&
        IsCompatible(representation, element.representation)) {
158
      return element.value;
159
    }
160 161 162 163 164 165 166 167 168 169
  }
  return nullptr;
}

LoadElimination::AbstractElements const*
LoadElimination::AbstractElements::Kill(Node* object, Node* index,
                                        Zone* zone) const {
  for (Element const element : this->elements_) {
    if (element.object == nullptr) continue;
    if (MayAlias(object, element.object)) {
170
      AbstractElements* that = zone->New<AbstractElements>(zone);
171 172 173 174 175
      for (Element const element : this->elements_) {
        if (element.object == nullptr) continue;
        DCHECK_NOT_NULL(element.index);
        DCHECK_NOT_NULL(element.value);
        if (!MayAlias(object, element.object) ||
176
            !NodeProperties::GetType(index).Maybe(
177
                NodeProperties::GetType(element.index))) {
178
          that->elements_[that->next_index_++] = element;
179
        }
180
      }
181
      that->next_index_ %= arraysize(elements_);
182
      return that;
183 184
    }
  }
185 186
  return this;
}
187

188 189 190 191 192 193 194 195 196 197 198 199 200
bool LoadElimination::AbstractElements::Equals(
    AbstractElements const* that) const {
  if (this == that) return true;
  for (size_t i = 0; i < arraysize(elements_); ++i) {
    Element this_element = this->elements_[i];
    if (this_element.object == nullptr) continue;
    for (size_t j = 0;; ++j) {
      if (j == arraysize(elements_)) return false;
      Element that_element = that->elements_[j];
      if (this_element.object == that_element.object &&
          this_element.index == that_element.index &&
          this_element.value == that_element.value) {
        break;
201 202
      }
    }
203 204 205 206 207 208 209 210 211 212 213
  }
  for (size_t i = 0; i < arraysize(elements_); ++i) {
    Element that_element = that->elements_[i];
    if (that_element.object == nullptr) continue;
    for (size_t j = 0;; ++j) {
      if (j == arraysize(elements_)) return false;
      Element this_element = this->elements_[j];
      if (that_element.object == this_element.object &&
          that_element.index == this_element.index &&
          that_element.value == this_element.value) {
        break;
214 215
      }
    }
216 217 218 219 220 221 222 223
  }
  return true;
}

LoadElimination::AbstractElements const*
LoadElimination::AbstractElements::Merge(AbstractElements const* that,
                                         Zone* zone) const {
  if (this->Equals(that)) return this;
224
  AbstractElements* copy = zone->New<AbstractElements>(zone);
225 226 227 228 229 230 231
  for (Element const this_element : this->elements_) {
    if (this_element.object == nullptr) continue;
    for (Element const that_element : that->elements_) {
      if (this_element.object == that_element.object &&
          this_element.index == that_element.index &&
          this_element.value == that_element.value) {
        copy->elements_[copy->next_index_++] = this_element;
232
        break;
233
      }
234 235
    }
  }
236
  copy->next_index_ %= arraysize(elements_);
237 238
  return copy;
}
239

240 241 242 243 244 245 246 247 248 249 250
void LoadElimination::AbstractElements::Print() const {
  for (Element const& element : elements_) {
    if (element.object) {
      PrintF("    #%d:%s @ #%d:%s -> #%d:%s\n", element.object->id(),
             element.object->op()->mnemonic(), element.index->id(),
             element.index->op()->mnemonic(), element.value->id(),
             element.value->op()->mnemonic());
    }
  }
}

251 252 253
LoadElimination::FieldInfo const* LoadElimination::AbstractField::Lookup(
    Node* object) const {
  for (auto& pair : info_for_node_) {
254
    if (pair.first->IsDead()) continue;
255
    if (MustAlias(object, pair.first)) return &pair.second;
256
  }
257 258
  return nullptr;
}
259

260 261 262 263 264 265 266 267 268 269 270
namespace {

bool MayAlias(MaybeHandle<Name> x, MaybeHandle<Name> y) {
  if (!x.address()) return true;
  if (!y.address()) return true;
  if (x.address() != y.address()) return false;
  return true;
}

}  // namespace

271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
class LoadElimination::AliasStateInfo {
 public:
  AliasStateInfo(const AbstractState* state, Node* object, Handle<Map> map)
      : state_(state), object_(object), map_(map) {}
  AliasStateInfo(const AbstractState* state, Node* object)
      : state_(state), object_(object) {}

  bool MayAlias(Node* other) const;

 private:
  const AbstractState* state_;
  Node* object_;
  MaybeHandle<Map> map_;
};

286 287 288 289 290 291 292 293 294 295
LoadElimination::AbstractField const* LoadElimination::AbstractField::KillConst(
    Node* object, Zone* zone) const {
  for (auto pair : this->info_for_node_) {
    if (pair.first->IsDead()) continue;
    // If we previously recorded information about a const store on the given
    // 'object', we might not have done it on the same node; e.g. we might now
    // identify the object by a FinishRegion node, whereas the initial const
    // store was performed on the Allocate node. We therefore remove information
    // on all nodes that must alias with 'object'.
    if (MustAlias(object, pair.first)) {
296
      AbstractField* that = zone->New<AbstractField>(zone);
297 298 299 300 301 302 303 304 305 306 307
      for (auto pair : this->info_for_node_) {
        if (!MustAlias(object, pair.first)) {
          that->info_for_node_.insert(pair);
        }
      }
      return that;
    }
  }
  return this;
}

308
LoadElimination::AbstractField const* LoadElimination::AbstractField::Kill(
309 310
    const AliasStateInfo& alias_info, MaybeHandle<Name> name,
    Zone* zone) const {
311
  for (auto pair : this->info_for_node_) {
312
    if (pair.first->IsDead()) continue;
313
    if (alias_info.MayAlias(pair.first)) {
314
      AbstractField* that = zone->New<AbstractField>(zone);
315
      for (auto pair : this->info_for_node_) {
316
        if (!alias_info.MayAlias(pair.first) ||
317 318 319
            !MayAlias(name, pair.second.name)) {
          that->info_for_node_.insert(pair);
        }
320
      }
321
      return that;
322
    }
323 324 325 326
  }
  return this;
}

327 328
void LoadElimination::AbstractField::Print() const {
  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 332
           pair.second.value->op()->mnemonic(),
           MachineReprToString(pair.second.representation));
333 334 335
  }
}

336 337 338 339
LoadElimination::AbstractMaps::AbstractMaps(Zone* zone)
    : info_for_node_(zone) {}

LoadElimination::AbstractMaps::AbstractMaps(Node* object,
340
                                            ZoneHandleSet<Map> maps, Zone* zone)
341 342
    : info_for_node_(zone) {
  object = ResolveRenames(object);
343
  info_for_node_.insert(std::make_pair(object, maps));
344 345
}

346 347
bool LoadElimination::AbstractMaps::Lookup(
    Node* object, ZoneHandleSet<Map>* object_maps) const {
348 349
  auto it = info_for_node_.find(ResolveRenames(object));
  if (it == info_for_node_.end()) return false;
350
  *object_maps = it->second;
351
  return true;
352 353 354
}

LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Kill(
355
    const AliasStateInfo& alias_info, Zone* zone) const {
356
  for (auto pair : this->info_for_node_) {
357
    if (alias_info.MayAlias(pair.first)) {
358
      AbstractMaps* that = zone->New<AbstractMaps>(zone);
359
      for (auto pair : this->info_for_node_) {
360
        if (!alias_info.MayAlias(pair.first)) that->info_for_node_.insert(pair);
361 362 363 364 365 366 367
      }
      return that;
    }
  }
  return this;
}

368 369 370
LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Merge(
    AbstractMaps const* that, Zone* zone) const {
  if (this->Equals(that)) return this;
371
  AbstractMaps* copy = zone->New<AbstractMaps>(zone);
372 373
  for (auto this_it : this->info_for_node_) {
    Node* this_object = this_it.first;
374
    ZoneHandleSet<Map> this_maps = this_it.second;
375
    auto that_it = that->info_for_node_.find(this_object);
376 377
    if (that_it != that->info_for_node_.end() && that_it->second == this_maps) {
      copy->info_for_node_.insert(this_it);
378 379 380 381 382 383
    }
  }
  return copy;
}

LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Extend(
384
    Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
385
  AbstractMaps* that = zone->New<AbstractMaps>(zone);
386
  that->info_for_node_ = this->info_for_node_;
387
  object = ResolveRenames(object);
388
  that->info_for_node_[object] = maps;
389 390 391
  return that;
}

392
void LoadElimination::AbstractMaps::Print() const {
393
  AllowHandleDereference allow_handle_dereference;
394
  StdoutStream os;
395
  for (auto pair : info_for_node_) {
396 397
    os << "    #" << pair.first->id() << ":" << pair.first->op()->mnemonic()
       << std::endl;
398 399
    ZoneHandleSet<Map> const& maps = pair.second;
    for (size_t i = 0; i < maps.size(); ++i) {
400
      os << "     - " << Brief(*maps[i]) << std::endl;
401 402 403 404
    }
  }
}

405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
bool LoadElimination::AbstractState::FieldsEquals(
    AbstractFields const& this_fields,
    AbstractFields const& that_fields) const {
  for (size_t i = 0u; i < this_fields.size(); ++i) {
    AbstractField const* this_field = this_fields[i];
    AbstractField const* that_field = that_fields[i];
    if (this_field) {
      if (!that_field || !that_field->Equals(this_field)) return false;
    } else if (that_field) {
      return false;
    }
  }
  return true;
}

420 421 422 423
bool LoadElimination::AbstractState::Equals(AbstractState const* that) const {
  if (this->elements_) {
    if (!that->elements_ || !that->elements_->Equals(this->elements_)) {
      return false;
424
    }
425 426 427
  } else if (that->elements_) {
    return false;
  }
428 429 430
  if (!FieldsEquals(this->fields_, that->fields_) ||
      !FieldsEquals(this->const_fields_, that->const_fields_)) {
    return false;
431
  }
432 433 434 435 436 437 438
  if (this->maps_) {
    if (!that->maps_ || !that->maps_->Equals(this->maps_)) {
      return false;
    }
  } else if (that->maps_) {
    return false;
  }
439 440 441
  return true;
}

442
void LoadElimination::AbstractState::FieldsMerge(
443
    AbstractFields* this_fields, AbstractFields const& that_fields,
444
    Zone* zone) {
445 446 447
  for (size_t i = 0; i < this_fields->size(); ++i) {
    AbstractField const*& this_field = (*this_fields)[i];
    if (this_field) {
448
      if (that_fields[i]) {
449
        this_field = this_field->Merge(that_fields[i], zone);
450
      } else {
451
        this_field = nullptr;
452 453 454 455 456
      }
    }
  }
}

457 458 459 460 461 462
void LoadElimination::AbstractState::Merge(AbstractState const* that,
                                           Zone* zone) {
  // Merge the information we have about the elements.
  if (this->elements_) {
    this->elements_ = that->elements_
                          ? that->elements_->Merge(this->elements_, zone)
463
                          : nullptr;
464 465 466
  }

  // Merge the information we have about the fields.
467 468
  FieldsMerge(&this->fields_, that->fields_, zone);
  FieldsMerge(&this->const_fields_, that->const_fields_, zone);
469 470 471 472 473

  // Merge the information we have about the maps.
  if (this->maps_) {
    this->maps_ = that->maps_ ? that->maps_->Merge(this->maps_, zone) : nullptr;
  }
474
}
475

476 477 478 479 480
bool LoadElimination::AbstractState::LookupMaps(
    Node* object, ZoneHandleSet<Map>* object_map) const {
  return this->maps_ && this->maps_->Lookup(object, object_map);
}

481
LoadElimination::AbstractState const* LoadElimination::AbstractState::SetMaps(
482
    Node* object, ZoneHandleSet<Map> maps, Zone* zone) const {
483
  AbstractState* that = zone->New<AbstractState>(*this);
484
  if (that->maps_) {
485
    that->maps_ = that->maps_->Extend(object, maps, zone);
486
  } else {
487
    that->maps_ = zone->New<AbstractMaps>(object, maps, zone);
488 489 490 491 492
  }
  return that;
}

LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
493
    const AliasStateInfo& alias_info, Zone* zone) const {
494
  if (this->maps_) {
495
    AbstractMaps const* that_maps = this->maps_->Kill(alias_info, zone);
496
    if (this->maps_ != that_maps) {
497
      AbstractState* that = zone->New<AbstractState>(*this);
498 499 500 501 502 503 504
      that->maps_ = that_maps;
      return that;
    }
  }
  return this;
}

505 506 507 508 509 510
LoadElimination::AbstractState const* LoadElimination::AbstractState::KillMaps(
    Node* object, Zone* zone) const {
  AliasStateInfo alias_info(this, object);
  return KillMaps(alias_info, zone);
}

511 512
Node* LoadElimination::AbstractState::LookupElement(
    Node* object, Node* index, MachineRepresentation representation) const {
513
  if (this->elements_) {
514
    return this->elements_->Lookup(object, index, representation);
515
  }
516 517
  return nullptr;
}
518

519 520
LoadElimination::AbstractState const*
LoadElimination::AbstractState::AddElement(Node* object, Node* index,
521 522 523
                                           Node* value,
                                           MachineRepresentation representation,
                                           Zone* zone) const {
524
  AbstractState* that = zone->New<AbstractState>(*this);
525
  if (that->elements_) {
526 527
    that->elements_ =
        that->elements_->Extend(object, index, value, representation, zone);
528
  } else {
529
    that->elements_ =
530
        zone->New<AbstractElements>(object, index, value, representation, zone);
531
  }
532 533
  return that;
}
534

535 536 537 538 539 540 541
LoadElimination::AbstractState const*
LoadElimination::AbstractState::KillElement(Node* object, Node* index,
                                            Zone* zone) const {
  if (this->elements_) {
    AbstractElements const* that_elements =
        this->elements_->Kill(object, index, zone);
    if (this->elements_ != that_elements) {
542
      AbstractState* that = zone->New<AbstractState>(*this);
543 544
      that->elements_ = that_elements;
      return that;
545 546
    }
  }
547 548
  return this;
}
549

550
LoadElimination::AbstractState const* LoadElimination::AbstractState::AddField(
551
    Node* object, IndexRange index_range, LoadElimination::FieldInfo info,
552
    Zone* zone) const {
553
  AbstractState* that = zone->New<AbstractState>(*this);
554 555
  AbstractFields& fields =
      info.const_field_info.IsConst() ? that->const_fields_ : that->fields_;
556 557 558 559
  for (int index : index_range) {
    if (fields[index]) {
      fields[index] = fields[index]->Extend(object, info, zone);
    } else {
560
      fields[index] = zone->New<AbstractField>(object, info, zone);
561
    }
562
  }
563 564 565
  return that;
}

566 567 568 569 570 571 572 573 574 575
LoadElimination::AbstractState const*
LoadElimination::AbstractState::KillConstField(Node* object,
                                               IndexRange index_range,
                                               Zone* zone) const {
  AliasStateInfo alias_info(this, object);
  AbstractState* that = nullptr;
  for (int index : index_range) {
    if (AbstractField const* this_field = this->const_fields_[index]) {
      this_field = this_field->KillConst(object, zone);
      if (this->const_fields_[index] != this_field) {
576
        if (!that) that = zone->New<AbstractState>(*this);
577 578 579 580 581 582 583
        that->const_fields_[index] = this_field;
      }
    }
  }
  return that ? that : this;
}

584
LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
585 586
    Node* object, IndexRange index_range, MaybeHandle<Name> name,
    Zone* zone) const {
587
  AliasStateInfo alias_info(this, object);
588
  return KillField(alias_info, index_range, name, zone);
589 590 591
}

LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
592 593 594 595 596 597 598
    const AliasStateInfo& alias_info, IndexRange index_range,
    MaybeHandle<Name> name, Zone* zone) const {
  AbstractState* that = nullptr;
  for (int index : index_range) {
    if (AbstractField const* this_field = this->fields_[index]) {
      this_field = this_field->Kill(alias_info, name, zone);
      if (this->fields_[index] != this_field) {
599
        if (!that) that = zone->New<AbstractState>(*this);
600 601
        that->fields_[index] = this_field;
      }
602
    }
603
  }
604
  return that ? that : this;
605
}
606

607
LoadElimination::AbstractState const*
608 609
LoadElimination::AbstractState::KillFields(Node* object, MaybeHandle<Name> name,
                                           Zone* zone) const {
610
  AliasStateInfo alias_info(this, object);
611
  for (size_t i = 0;; ++i) {
612
    if (i == fields_.size()) return this;
613
    if (AbstractField const* this_field = this->fields_[i]) {
614 615
      AbstractField const* that_field =
          this_field->Kill(alias_info, name, zone);
616
      if (that_field != this_field) {
617
        AbstractState* that = zone->New<AbstractState>(*this);
618
        that->fields_[i] = that_field;
619
        while (++i < fields_.size()) {
620
          if (this->fields_[i] != nullptr) {
621
            that->fields_[i] = this->fields_[i]->Kill(alias_info, name, zone);
622 623 624 625 626 627 628 629
          }
        }
        return that;
      }
    }
  }
}

630 631
LoadElimination::AbstractState const* LoadElimination::AbstractState::KillAll(
    Zone* zone) const {
632 633 634
  // Kill everything except for const fields
  for (size_t i = 0; i < const_fields_.size(); ++i) {
    if (const_fields_[i]) {
635
      AbstractState* that = zone->New<AbstractState>();
636 637
      that->const_fields_ = const_fields_;
      return that;
638 639 640 641 642
    }
  }
  return LoadElimination::empty_state();
}

643
LoadElimination::FieldInfo const* LoadElimination::AbstractState::LookupField(
644 645
    Node* object, IndexRange index_range,
    ConstFieldInfo const_field_info) const {
646 647 648 649 650
  // Check if all the indices in {index_range} contain identical information.
  // If not, a partially overlapping access has invalidated part of the value.
  base::Optional<LoadElimination::FieldInfo const*> result;
  for (int index : index_range) {
    LoadElimination::FieldInfo const* info = nullptr;
651 652 653 654 655 656 657 658 659 660
    if (const_field_info.IsConst()) {
      if (AbstractField const* this_field = const_fields_[index]) {
        info = this_field->Lookup(object);
      }
      if (!(info && info->const_field_info == const_field_info)) return nullptr;
    } else {
      if (AbstractField const* this_field = fields_[index]) {
        info = this_field->Lookup(object);
      }
      if (!info) return nullptr;
661 662 663
    }
    if (!result.has_value()) {
      result = info;
664 665 666 667 668 669 670
    } else if (**result != *info) {
      // We detected inconsistent information for a field here.
      // This can happen when incomplete alias information makes an unrelated
      // write invalidate part of a field and then we re-combine this partial
      // information.
      // This is probably OK, but since it's rare, we better bail out here.
      return nullptr;
671
    }
672
  }
673
  return *result;
674 675
}

676
bool LoadElimination::AliasStateInfo::MayAlias(Node* other) const {
677 678 679 680 681 682
  // If {object} is being initialized right here (indicated by {object} being
  // an Allocate node instead of a FinishRegion node), we know that {other}
  // can only alias with {object} if they refer to exactly the same node.
  if (object_->opcode() == IrOpcode::kAllocate) {
    return object_ == other;
  }
683 684
  // Decide aliasing based on the node kinds.
  if (!compiler::MayAlias(object_, other)) {
685 686
    return false;
  }
687
  // Decide aliasing based on maps (if available).
688 689 690 691 692 693 694 695 696 697 698 699
  Handle<Map> map;
  if (map_.ToHandle(&map)) {
    ZoneHandleSet<Map> other_maps;
    if (state_->LookupMaps(other, &other_maps) && other_maps.size() == 1) {
      if (map.address() != other_maps.at(0).address()) {
        return false;
      }
    }
  }
  return true;
}

700
void LoadElimination::AbstractState::Print() const {
701 702 703 704
  if (maps_) {
    PrintF("   maps:\n");
    maps_->Print();
  }
705 706 707 708
  if (elements_) {
    PrintF("   elements:\n");
    elements_->Print();
  }
709
  for (size_t i = 0; i < fields_.size(); ++i) {
710 711 712 713 714
    if (AbstractField const* const field = fields_[i]) {
      PrintF("   field %zu:\n", i);
      field->Print();
    }
  }
715 716 717 718 719 720
  for (size_t i = 0; i < const_fields_.size(); ++i) {
    if (AbstractField const* const const_field = const_fields_[i]) {
      PrintF("   const field %zu:\n", i);
      const_field->Print();
    }
  }
721 722
}

723 724 725 726 727 728 729 730 731 732 733 734 735
LoadElimination::AbstractState const*
LoadElimination::AbstractStateForEffectNodes::Get(Node* node) const {
  size_t const id = node->id();
  if (id < info_for_node_.size()) return info_for_node_[id];
  return nullptr;
}

void LoadElimination::AbstractStateForEffectNodes::Set(
    Node* node, AbstractState const* state) {
  size_t const id = node->id();
  if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
  info_for_node_[id] = state;
}
736

737
Reduction LoadElimination::ReduceMapGuard(Node* node) {
738
  ZoneHandleSet<Map> const& maps = MapGuardMapsOf(node->op());
739
  Node* const object = NodeProperties::GetValueInput(node, 0);
740
  Node* const effect = NodeProperties::GetEffectInput(node);
741 742
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
743
  ZoneHandleSet<Map> object_maps;
744
  if (state->LookupMaps(object, &object_maps)) {
745
    if (maps.contains(object_maps)) return Replace(effect);
746 747
    // TODO(turbofan): Compute the intersection.
  }
748
  state = state->SetMaps(object, maps, zone());
749 750 751
  return UpdateState(node, state);
}

752
Reduction LoadElimination::ReduceCheckMaps(Node* node) {
753
  ZoneHandleSet<Map> const& maps = CheckMapsParametersOf(node->op()).maps();
754
  Node* const object = NodeProperties::GetValueInput(node, 0);
755
  Node* const effect = NodeProperties::GetEffectInput(node);
756 757
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
758 759
  ZoneHandleSet<Map> object_maps;
  if (state->LookupMaps(object, &object_maps)) {
760
    if (maps.contains(object_maps)) return Replace(effect);
761
    // TODO(turbofan): Compute the intersection.
762
  }
763
  state = state->SetMaps(object, maps, zone());
764 765 766
  return UpdateState(node, state);
}

767
Reduction LoadElimination::ReduceCompareMaps(Node* node) {
768
  ZoneHandleSet<Map> const& maps = CompareMapsParametersOf(node->op());
769 770 771 772
  Node* const object = NodeProperties::GetValueInput(node, 0);
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
773 774
  ZoneHandleSet<Map> object_maps;
  if (state->LookupMaps(object, &object_maps)) {
775 776 777 778
    if (maps.contains(object_maps)) {
      Node* value = jsgraph()->TrueConstant();
      ReplaceWithValue(node, value, effect);
      return Replace(value);
779
    }
780
    // TODO(turbofan): Compute the intersection.
781 782 783 784
  }
  return UpdateState(node, state);
}

785 786 787 788 789 790
Reduction LoadElimination::ReduceEnsureWritableFastElements(Node* node) {
  Node* const object = NodeProperties::GetValueInput(node, 0);
  Node* const elements = NodeProperties::GetValueInput(node, 1);
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
791
  // Check if the {elements} already have the fixed array map.
792 793 794 795 796 797
  ZoneHandleSet<Map> elements_maps;
  ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
  if (state->LookupMaps(elements, &elements_maps) &&
      fixed_array_maps.contains(elements_maps)) {
    ReplaceWithValue(node, elements, effect);
    return Replace(elements);
798 799
  }
  // We know that the resulting elements have the fixed array map.
800
  state = state->SetMaps(node, fixed_array_maps, zone());
801
  // Kill the previous elements on {object}.
802 803
  state = state->KillField(object,
                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
804
                           MaybeHandle<Name>(), zone());
805
  // Add the new elements on {object}.
806 807
  state = state->AddField(
      object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
808
      {node, MachineRepresentation::kTaggedPointer}, zone());
809 810 811
  return UpdateState(node, state);
}

812
Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
813
  GrowFastElementsParameters params = GrowFastElementsParametersOf(node->op());
814 815 816 817
  Node* const object = NodeProperties::GetValueInput(node, 0);
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
818
  if (params.mode() == GrowFastElementsMode::kDoubleElements) {
819
    // We know that the resulting elements have the fixed double array map.
820
    state = state->SetMaps(
821
        node, ZoneHandleSet<Map>(factory()->fixed_double_array_map()), zone());
822
  } else {
823 824 825 826 827
    // We know that the resulting elements have the fixed array map or the COW
    // version thereof (if we didn't grow and it was already COW before).
    ZoneHandleSet<Map> fixed_array_maps(factory()->fixed_array_map());
    fixed_array_maps.insert(factory()->fixed_cow_array_map(), zone());
    state = state->SetMaps(node, fixed_array_maps, zone());
828 829
  }
  // Kill the previous elements on {object}.
830 831
  state = state->KillField(object,
                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
832
                           MaybeHandle<Name>(), zone());
833
  // Add the new elements on {object}.
834 835
  state = state->AddField(
      object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
836
      {node, MachineRepresentation::kTaggedPointer}, zone());
837 838 839
  return UpdateState(node, state);
}

840
Reduction LoadElimination::ReduceTransitionElementsKind(Node* node) {
841
  ElementsTransition transition = ElementsTransitionOf(node->op());
842
  Node* const object = NodeProperties::GetValueInput(node, 0);
843 844
  Handle<Map> source_map(transition.source());
  Handle<Map> target_map(transition.target());
845 846 847
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
848 849 850 851 852 853
  switch (transition.mode()) {
    case ElementsTransition::kFastTransition:
      break;
    case ElementsTransition::kSlowTransition:
      // Kill the elements as well.
      AliasStateInfo alias_info(state, object, source_map);
854 855 856
      state = state->KillField(
          alias_info, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
          MaybeHandle<Name>(), zone());
857 858
      break;
  }
859 860 861
  ZoneHandleSet<Map> object_maps;
  if (state->LookupMaps(object, &object_maps)) {
    if (ZoneHandleSet<Map>(target_map).contains(object_maps)) {
862 863 864 865
      // The {object} already has the {target_map}, so this TransitionElements
      // {node} is fully redundant (independent of what {source_map} is).
      return Replace(effect);
    }
866
    if (object_maps.contains(ZoneHandleSet<Map>(source_map))) {
867 868
      object_maps.remove(source_map, zone());
      object_maps.insert(target_map, zone());
869 870
      AliasStateInfo alias_info(state, object, source_map);
      state = state->KillMaps(alias_info, zone());
871
      state = state->SetMaps(object, object_maps, zone());
872 873
    }
  } else {
874 875
    AliasStateInfo alias_info(state, object, source_map);
    state = state->KillMaps(alias_info, zone());
876 877 878 879
  }
  return UpdateState(node, state);
}

880 881 882 883 884 885 886 887 888 889 890 891 892 893 894
Reduction LoadElimination::ReduceTransitionAndStoreElement(Node* node) {
  Node* const object = NodeProperties::GetValueInput(node, 0);
  Handle<Map> double_map(DoubleMapParameterOf(node->op()));
  Handle<Map> fast_map(FastMapParameterOf(node->op()));
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();

  // We need to add the double and fast maps to the set of possible maps for
  // this object, because we don't know which of those we'll transition to.
  // Additionally, we should kill all alias information.
  ZoneHandleSet<Map> object_maps;
  if (state->LookupMaps(object, &object_maps)) {
    object_maps.insert(double_map, zone());
    object_maps.insert(fast_map, zone());
895
    state = state->KillMaps(object, zone());
896
    state = state->SetMaps(object, object_maps, zone());
897 898
  }
  // Kill the elements as well.
899 900
  state = state->KillField(object,
                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
901
                           MaybeHandle<Name>(), zone());
902 903 904
  return UpdateState(node, state);
}

905 906
Reduction LoadElimination::ReduceLoadField(Node* node,
                                           FieldAccess const& access) {
907 908 909
  Node* object = NodeProperties::GetValueInput(node, 0);
  Node* effect = NodeProperties::GetEffectInput(node);
  Node* control = NodeProperties::GetControlInput(node);
910 911
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
912 913
  if (access.offset == HeapObject::kMapOffset &&
      access.base_is_tagged == kTaggedBase) {
914
    DCHECK(IsAnyTagged(access.machine_type.representation()));
915 916 917
    ZoneHandleSet<Map> object_maps;
    if (state->LookupMaps(object, &object_maps) && object_maps.size() == 1) {
      Node* value = jsgraph()->HeapConstant(object_maps[0]);
918
      NodeProperties::SetType(value, Type::OtherInternal());
919 920 921 922
      ReplaceWithValue(node, value, effect);
      return Replace(value);
    }
  } else {
923 924
    IndexRange field_index = FieldIndexOf(access);
    if (field_index != IndexRange::Invalid()) {
925 926 927
      MachineRepresentation representation =
          access.machine_type.representation();
      FieldInfo const* lookup_result =
928 929 930 931 932 933
          state->LookupField(object, field_index, access.const_field_info);
      if (!lookup_result && access.const_field_info.IsConst()) {
        // If the access is const and we didn't find anything, also try to look
        // up information from mutable stores
        lookup_result =
            state->LookupField(object, field_index, ConstFieldInfo::None());
934
      }
935 936 937 938 939 940
      if (lookup_result) {
        // Make sure we don't reuse values that were recorded with a different
        // representation or resurrect dead {replacement} nodes.
        Node* replacement = lookup_result->value;
        if (IsCompatible(representation, lookup_result->representation) &&
            !replacement->IsDead()) {
941 942 943 944 945 946 947 948 949 950 951 952
          // Introduce a TypeGuard if the type of the {replacement} node is not
          // a subtype of the original {node}'s type.
          if (!NodeProperties::GetType(replacement)
                   .Is(NodeProperties::GetType(node))) {
            Type replacement_type = Type::Intersect(
                NodeProperties::GetType(node),
                NodeProperties::GetType(replacement), graph()->zone());
            replacement = effect =
                graph()->NewNode(common()->TypeGuard(replacement_type),
                                 replacement, effect, control);
            NodeProperties::SetType(replacement, replacement_type);
          }
953 954
          ReplaceWithValue(node, replacement, effect);
          return Replace(replacement);
955
        }
956
      }
957 958 959
      FieldInfo info(node, representation, access.name,
                     access.const_field_info);
      state = state->AddField(object, field_index, info, zone());
960 961
    }
  }
962 963
  Handle<Map> field_map;
  if (access.map.ToHandle(&field_map)) {
964
    state = state->SetMaps(node, ZoneHandleSet<Map>(field_map), zone());
965
  }
966 967
  return UpdateState(node, state);
}
968

969 970
Reduction LoadElimination::ReduceStoreField(Node* node,
                                            FieldAccess const& access) {
971 972 973 974 975
  Node* const object = NodeProperties::GetValueInput(node, 0);
  Node* const new_value = NodeProperties::GetValueInput(node, 1);
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
976 977
  if (access.offset == HeapObject::kMapOffset &&
      access.base_is_tagged == kTaggedBase) {
978
    DCHECK(IsAnyTagged(access.machine_type.representation()));
979 980
    // Kill all potential knowledge about the {object}s map.
    state = state->KillMaps(object, zone());
981
    Type const new_value_type = NodeProperties::GetType(new_value);
982
    if (new_value_type.IsHeapConstant()) {
983 984
      // Record the new {object} map information.
      ZoneHandleSet<Map> object_maps(
985
          new_value_type.AsHeapConstant()->Ref().AsMap().object());
986
      state = state->SetMaps(object, object_maps, zone());
987 988
    }
  } else {
989 990
    IndexRange field_index = FieldIndexOf(access);
    if (field_index != IndexRange::Invalid()) {
991
      bool is_const_store = access.const_field_info.IsConst();
992 993 994
      MachineRepresentation representation =
          access.machine_type.representation();
      FieldInfo const* lookup_result =
995
          state->LookupField(object, field_index, access.const_field_info);
996

997 998
      if (lookup_result &&
          (!is_const_store || V8_ENABLE_DOUBLE_CONST_STORE_CHECK_BOOL)) {
999 1000 1001
        // At runtime, we should never encounter
        // - any store replacing existing info with a different, incompatible
        //   representation, nor
1002 1003
        // - two consecutive const stores, unless the latter is a store into
        //   a literal.
1004 1005
        // However, we may see such code statically, so we guard against
        // executing it by emitting Unreachable.
1006 1007 1008 1009
        // TODO(gsps): Re-enable the double const store check even for
        //   non-debug builds once we have identified other FieldAccesses
        //   that should be marked mutable instead of const
        //   (cf. JSCreateLowering::AllocateFastLiteral).
1010 1011 1012
        bool incompatible_representation =
            !lookup_result->name.is_null() &&
            !IsCompatible(representation, lookup_result->representation);
1013 1014 1015
        bool illegal_double_const_store =
            is_const_store && !access.is_store_in_literal;
        if (incompatible_representation || illegal_double_const_store) {
1016 1017 1018 1019 1020 1021 1022 1023 1024
          Node* control = NodeProperties::GetControlInput(node);
          Node* unreachable =
              graph()->NewNode(common()->Unreachable(), effect, control);
          return Replace(unreachable);
        }
        if (lookup_result->value == new_value) {
          // This store is fully redundant.
          return Replace(effect);
        }
1025
      }
1026

1027
      // Kill all potentially aliasing fields and record the new value.
1028 1029
      FieldInfo new_info(new_value, representation, access.name,
                         access.const_field_info);
1030 1031 1032 1033 1034 1035
      if (is_const_store && access.is_store_in_literal) {
        // We only kill const information when there is a chance that we
        // previously stored information about the given const field (namely,
        // when we observe const stores to literals).
        state = state->KillConstField(object, field_index, zone());
      }
1036
      state = state->KillField(object, field_index, access.name, zone());
1037 1038
      state = state->AddField(object, field_index, new_info, zone());
      if (is_const_store) {
1039 1040 1041
        // For const stores, we track information in both the const and the
        // mutable world to guard against field accesses that should have
        // been marked const, but were not.
1042 1043
        new_info.const_field_info = ConstFieldInfo::None();
        state = state->AddField(object, field_index, new_info, zone());
1044
      }
1045 1046
    } else {
      // Unsupported StoreField operator.
1047
      state = state->KillFields(object, access.name, zone());
1048
    }
1049 1050 1051
  }
  return UpdateState(node, state);
}
1052

1053 1054 1055 1056 1057 1058
Reduction LoadElimination::ReduceLoadElement(Node* node) {
  Node* const object = NodeProperties::GetValueInput(node, 0);
  Node* const index = NodeProperties::GetValueInput(node, 1);
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069

  // Only handle loads that do not require truncations.
  ElementAccess const& access = ElementAccessOf(node->op());
  switch (access.machine_type.representation()) {
    case MachineRepresentation::kNone:
    case MachineRepresentation::kBit:
    case MachineRepresentation::kWord8:
    case MachineRepresentation::kWord16:
    case MachineRepresentation::kWord32:
    case MachineRepresentation::kWord64:
    case MachineRepresentation::kFloat32:
1070 1071
    case MachineRepresentation::kCompressedPointer:
    case MachineRepresentation::kCompressed:
1072 1073 1074 1075 1076 1077 1078
      // TODO(turbofan): Add support for doing the truncations.
      break;
    case MachineRepresentation::kFloat64:
    case MachineRepresentation::kSimd128:
    case MachineRepresentation::kTaggedSigned:
    case MachineRepresentation::kTaggedPointer:
    case MachineRepresentation::kTagged:
1079 1080
      if (Node* replacement = state->LookupElement(
              object, index, access.machine_type.representation())) {
1081
        // Make sure we don't resurrect dead {replacement} nodes.
1082 1083 1084 1085 1086
        // Skip lowering if the type of the {replacement} node is not a subtype
        // of the original {node}'s type.
        // TODO(tebbi): We should insert a {TypeGuard} for the intersection of
        // these two types here once we properly handle {Type::None} everywhere.
        if (!replacement->IsDead() && NodeProperties::GetType(replacement)
1087
                                          .Is(NodeProperties::GetType(node))) {
1088 1089 1090
          ReplaceWithValue(node, replacement, effect);
          return Replace(replacement);
        }
1091
      }
1092 1093
      state = state->AddElement(object, index, node,
                                access.machine_type.representation(), zone());
1094
      return UpdateState(node, state);
1095
  }
1096
  return NoChange();
1097
}
1098

1099 1100 1101 1102 1103 1104 1105 1106
Reduction LoadElimination::ReduceStoreElement(Node* node) {
  ElementAccess const& access = ElementAccessOf(node->op());
  Node* const object = NodeProperties::GetValueInput(node, 0);
  Node* const index = NodeProperties::GetValueInput(node, 1);
  Node* const new_value = NodeProperties::GetValueInput(node, 2);
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
1107 1108
  Node* const old_value =
      state->LookupElement(object, index, access.machine_type.representation());
1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123
  if (old_value == new_value) {
    // This store is fully redundant.
    return Replace(effect);
  }
  // Kill all potentially aliasing elements.
  state = state->KillElement(object, index, zone());
  // Only record the new value if the store doesn't have an implicit truncation.
  switch (access.machine_type.representation()) {
    case MachineRepresentation::kNone:
    case MachineRepresentation::kBit:
    case MachineRepresentation::kWord8:
    case MachineRepresentation::kWord16:
    case MachineRepresentation::kWord32:
    case MachineRepresentation::kWord64:
    case MachineRepresentation::kFloat32:
1124 1125
    case MachineRepresentation::kCompressedPointer:
    case MachineRepresentation::kCompressed:
1126 1127 1128 1129
      // TODO(turbofan): Add support for doing the truncations.
      break;
    case MachineRepresentation::kFloat64:
    case MachineRepresentation::kSimd128:
1130 1131
    case MachineRepresentation::kTaggedSigned:
    case MachineRepresentation::kTaggedPointer:
1132
    case MachineRepresentation::kTagged:
1133 1134
      state = state->AddElement(object, index, new_value,
                                access.machine_type.representation(), zone());
1135 1136 1137 1138
      break;
  }
  return UpdateState(node, state);
}
1139

1140 1141 1142 1143 1144 1145 1146
Reduction LoadElimination::ReduceStoreTypedElement(Node* node) {
  Node* const effect = NodeProperties::GetEffectInput(node);
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
  return UpdateState(node, state);
}

1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164
LoadElimination::AbstractState const* LoadElimination::UpdateStateForPhi(
    AbstractState const* state, Node* effect_phi, Node* phi) {
  int predecessor_count = phi->InputCount() - 1;
  // TODO(jarin) Consider doing a union here. At the moment, we just keep this
  // consistent with AbstractState::Merge.

  // Check if all the inputs have the same maps.
  AbstractState const* input_state =
      node_states_.Get(NodeProperties::GetEffectInput(effect_phi, 0));
  ZoneHandleSet<Map> object_maps;
  if (!input_state->LookupMaps(phi->InputAt(0), &object_maps)) return state;
  for (int i = 1; i < predecessor_count; i++) {
    input_state =
        node_states_.Get(NodeProperties::GetEffectInput(effect_phi, i));
    ZoneHandleSet<Map> input_maps;
    if (!input_state->LookupMaps(phi->InputAt(i), &input_maps)) return state;
    if (input_maps != object_maps) return state;
  }
1165
  return state->SetMaps(phi, object_maps, zone());
1166 1167
}

1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183
Reduction LoadElimination::ReduceEffectPhi(Node* node) {
  Node* const effect0 = NodeProperties::GetEffectInput(node, 0);
  Node* const control = NodeProperties::GetControlInput(node);
  AbstractState const* state0 = node_states_.Get(effect0);
  if (state0 == nullptr) return NoChange();
  if (control->opcode() == IrOpcode::kLoop) {
    // Here we rely on having only reducible loops:
    // The loop entry edge always dominates the header, so we can just take
    // the state from the first input, and compute the loop state based on it.
    AbstractState const* state = ComputeLoopState(node, state0);
    return UpdateState(node, state);
  }
  DCHECK_EQ(IrOpcode::kMerge, control->opcode());

  // Shortcut for the case when we do not know anything about some input.
  int const input_count = node->op()->EffectInputCount();
1184 1185 1186
  for (int i = 1; i < input_count; ++i) {
    Node* const effect = NodeProperties::GetEffectInput(node, i);
    if (node_states_.Get(effect) == nullptr) return NoChange();
1187 1188 1189 1190
  }

  // Make a copy of the first input's state and merge with the state
  // from other inputs.
1191
  AbstractState* state = zone()->New<AbstractState>(*state0);
1192 1193 1194 1195
  for (int i = 1; i < input_count; ++i) {
    Node* const input = NodeProperties::GetEffectInput(node, i);
    state->Merge(node_states_.Get(input), zone());
  }
1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206

  // For each phi, try to compute the new state for the phi from
  // the inputs.
  AbstractState const* state_with_phis = state;
  for (Node* use : control->uses()) {
    if (use->opcode() == IrOpcode::kPhi) {
      state_with_phis = UpdateStateForPhi(state_with_phis, node, use);
    }
  }

  return UpdateState(node, state_with_phis);
1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223
}

Reduction LoadElimination::ReduceStart(Node* node) {
  return UpdateState(node, empty_state());
}

Reduction LoadElimination::ReduceOtherNode(Node* node) {
  if (node->op()->EffectInputCount() == 1) {
    if (node->op()->EffectOutputCount() == 1) {
      Node* const effect = NodeProperties::GetEffectInput(node);
      AbstractState const* state = node_states_.Get(effect);
      // If we do not know anything about the predecessor, do not propagate
      // just yet because we will have to recompute anyway once we compute
      // the predecessor.
      if (state == nullptr) return NoChange();
      // Check if this {node} has some uncontrolled side effects.
      if (!node->op()->HasProperty(Operator::kNoWrite)) {
1224
        state = state->KillAll(zone());
1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235
      }
      return UpdateState(node, state);
    } else {
      // Effect terminators should be handled specially.
      return NoChange();
    }
  }
  DCHECK_EQ(0, node->op()->EffectInputCount());
  DCHECK_EQ(0, node->op()->EffectOutputCount());
  return NoChange();
}
1236

1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249
Reduction LoadElimination::UpdateState(Node* node, AbstractState const* state) {
  AbstractState const* original = node_states_.Get(node);
  // Only signal that the {node} has Changed, if the information about {state}
  // has changed wrt. the {original}.
  if (state != original) {
    if (original == nullptr || !state->Equals(original)) {
      node_states_.Set(node, state);
      return Changed(node);
    }
  }
  return NoChange();
}

1250 1251 1252 1253 1254 1255 1256 1257 1258
LoadElimination::AbstractState const*
LoadElimination::ComputeLoopStateForStoreField(
    Node* current, LoadElimination::AbstractState const* state,
    FieldAccess const& access) const {
  Node* const object = NodeProperties::GetValueInput(current, 0);
  if (access.offset == HeapObject::kMapOffset) {
    // Invalidate what we know about the {object}s map.
    state = state->KillMaps(object, zone());
  } else {
1259 1260
    IndexRange field_index = FieldIndexOf(access);
    if (field_index == IndexRange::Invalid()) {
1261 1262 1263 1264 1265 1266 1267 1268
      state = state->KillFields(object, access.name, zone());
    } else {
      state = state->KillField(object, field_index, access.name, zone());
    }
  }
  return state;
}

1269 1270 1271
LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
    Node* node, AbstractState const* state) const {
  Node* const control = NodeProperties::GetControlInput(node);
1272 1273 1274 1275
  struct TransitionElementsKindInfo {
    ElementsTransition transition;
    Node* object;
  };
1276 1277 1278 1279 1280 1281
  // Allocate zone data structures in a temporary zone with a lifetime limited
  // to this function to avoid blowing up the size of the stage-global zone.
  Zone temp_zone(zone()->allocator(), "Temporary scoped zone");
  ZoneVector<TransitionElementsKindInfo> element_transitions_(&temp_zone);
  ZoneQueue<Node*> queue(&temp_zone);
  ZoneSet<Node*> visited(&temp_zone);
1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292
  visited.insert(node);
  for (int i = 1; i < control->InputCount(); ++i) {
    queue.push(node->InputAt(i));
  }
  while (!queue.empty()) {
    Node* const current = queue.front();
    queue.pop();
    if (visited.find(current) == visited.end()) {
      visited.insert(current);
      if (!current->op()->HasProperty(Operator::kNoWrite)) {
        switch (current->opcode()) {
1293 1294
          case IrOpcode::kEnsureWritableFastElements: {
            Node* const object = NodeProperties::GetValueInput(current, 0);
1295 1296 1297
            state = state->KillField(
                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
                MaybeHandle<Name>(), zone());
1298 1299
            break;
          }
1300 1301
          case IrOpcode::kMaybeGrowFastElements: {
            Node* const object = NodeProperties::GetValueInput(current, 0);
1302 1303 1304
            state = state->KillField(
                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
                MaybeHandle<Name>(), zone());
1305 1306
            break;
          }
1307
          case IrOpcode::kTransitionElementsKind: {
1308
            ElementsTransition transition = ElementsTransitionOf(current->op());
1309
            Node* const object = NodeProperties::GetValueInput(current, 0);
1310 1311 1312 1313
            ZoneHandleSet<Map> object_maps;
            if (!state->LookupMaps(object, &object_maps) ||
                !ZoneHandleSet<Map>(transition.target())
                     .contains(object_maps)) {
1314
              element_transitions_.push_back({transition, object});
1315
            }
1316 1317
            break;
          }
1318 1319 1320 1321 1322
          case IrOpcode::kTransitionAndStoreElement: {
            Node* const object = NodeProperties::GetValueInput(current, 0);
            // Invalidate what we know about the {object}s map.
            state = state->KillMaps(object, zone());
            // Kill the elements as well.
1323 1324 1325
            state = state->KillField(
                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
                MaybeHandle<Name>(), zone());
1326 1327
            break;
          }
1328 1329
          case IrOpcode::kStoreField: {
            FieldAccess access = FieldAccessOf(current->op());
1330
            state = ComputeLoopStateForStoreField(current, state, access);
1331
            break;
1332
          }
1333 1334 1335 1336 1337 1338
          case IrOpcode::kStoreElement: {
            Node* const object = NodeProperties::GetValueInput(current, 0);
            Node* const index = NodeProperties::GetValueInput(current, 1);
            state = state->KillElement(object, index, zone());
            break;
          }
1339 1340 1341 1342
          case IrOpcode::kStoreTypedElement: {
            // Doesn't affect anything we track with the state currently.
            break;
          }
1343
          default:
1344
            return state->KillAll(zone());
1345 1346 1347 1348 1349 1350 1351
        }
      }
      for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
        queue.push(NodeProperties::GetEffectInput(current, i));
      }
    }
  }
1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386

  // Finally, we apply the element transitions. For each transition, we will try
  // to only invalidate information about nodes that can have the transition's
  // source map. The trouble is that an object can be transitioned by some other
  // transition to the source map. In that case, the other transition will
  // invalidate the information, so we are mostly fine.
  //
  // The only bad case is
  //
  //    mapA   ---fast--->   mapB   ---slow--->   mapC
  //
  // If we process the slow transition first on an object that has mapA, we will
  // ignore the transition because the object does not have its source map
  // (mapB). When we later process the fast transition, we invalidate the
  // object's map, but we keep the information about the object's elements. This
  // is wrong because the elements will be overwritten by the slow transition.
  //
  // Note that the slow-slow case is fine because either of the slow transition
  // will invalidate the elements field, so the processing order does not
  // matter.
  //
  // To handle the bad case properly, we first kill the maps using all
  // transitions. We kill the the fields later when all the transitions are
  // already reflected in the map information.

  for (const TransitionElementsKindInfo& t : element_transitions_) {
    AliasStateInfo alias_info(state, t.object, t.transition.source());
    state = state->KillMaps(alias_info, zone());
  }
  for (const TransitionElementsKindInfo& t : element_transitions_) {
    switch (t.transition.mode()) {
      case ElementsTransition::kFastTransition:
        break;
      case ElementsTransition::kSlowTransition: {
        AliasStateInfo alias_info(state, t.object, t.transition.source());
1387 1388 1389
        state = state->KillField(
            alias_info, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
            MaybeHandle<Name>(), zone());
1390 1391 1392 1393
        break;
      }
    }
  }
1394 1395 1396
  return state;
}

1397
// static
1398 1399
LoadElimination::IndexRange LoadElimination::FieldIndexOf(
    int offset, int representation_size) {
1400
  DCHECK(IsAligned(offset, kTaggedSize));
1401 1402 1403
  int field_index = offset / kTaggedSize - 1;
  DCHECK_EQ(0, representation_size % kTaggedSize);
  return IndexRange(field_index, representation_size / kTaggedSize);
1404 1405
}

1406
// static
1407 1408
LoadElimination::IndexRange LoadElimination::FieldIndexOf(
    FieldAccess const& access) {
1409 1410
  MachineRepresentation rep = access.machine_type.representation();
  switch (rep) {
1411 1412
    case MachineRepresentation::kNone:
    case MachineRepresentation::kBit:
1413
    case MachineRepresentation::kSimd128:
1414
      UNREACHABLE();
1415 1416
    case MachineRepresentation::kWord8:
    case MachineRepresentation::kWord16:
1417
    case MachineRepresentation::kFloat32:
1418 1419
      // Currently untracked.
      return IndexRange::Invalid();
1420
    case MachineRepresentation::kFloat64:
1421 1422
    case MachineRepresentation::kWord32:
    case MachineRepresentation::kWord64:
1423 1424
    case MachineRepresentation::kTaggedSigned:
    case MachineRepresentation::kTaggedPointer:
1425
    case MachineRepresentation::kTagged:
1426 1427
    case MachineRepresentation::kCompressedPointer:
    case MachineRepresentation::kCompressed:
1428 1429
      break;
  }
1430 1431 1432 1433 1434
  int representation_size = ElementSizeInBytes(rep);
  // We currently only track fields that are at least tagged pointer sized.
  if (representation_size < kTaggedSize) return IndexRange::Invalid();
  DCHECK_EQ(0, representation_size % kTaggedSize);

1435
  if (access.base_is_tagged != kTaggedBase) {
1436 1437
    // We currently only track tagged objects.
    return IndexRange::Invalid();
1438
  }
1439
  return FieldIndexOf(access.offset, representation_size);
1440 1441
}

1442 1443 1444 1445 1446 1447
CommonOperatorBuilder* LoadElimination::common() const {
  return jsgraph()->common();
}

Graph* LoadElimination::graph() const { return jsgraph()->graph(); }

1448 1449
Isolate* LoadElimination::isolate() const { return jsgraph()->isolate(); }

1450 1451
Factory* LoadElimination::factory() const { return jsgraph()->factory(); }

1452 1453 1454
}  // namespace compiler
}  // namespace internal
}  // namespace v8