load-elimination.cc 54.3 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 element2 : this->elements_) {
        if (element2.object == nullptr) continue;
        DCHECK_NOT_NULL(element2.index);
        DCHECK_NOT_NULL(element2.value);
        if (!MayAlias(object, element2.object) ||
176
            !NodeProperties::GetType(index).Maybe(
177 178
                NodeProperties::GetType(element2.index))) {
          that->elements_[that->next_index_++] = element2;
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
LoadElimination::AbstractField const* LoadElimination::AbstractField::KillConst(
    Node* object, Zone* zone) const {
288 289
  for (auto info1 : this->info_for_node_) {
    if (info1.first->IsDead()) continue;
290 291 292 293 294
    // 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'.
295
    if (MustAlias(object, info1.first)) {
296
      AbstractField* that = zone->New<AbstractField>(zone);
297 298 299
      for (auto info2 : this->info_for_node_) {
        if (!MustAlias(object, info2.first)) {
          that->info_for_node_.insert(info2);
300 301 302 303 304 305 306 307
        }
      }
      return that;
    }
  }
  return this;
}

308
LoadElimination::AbstractField const* LoadElimination::AbstractField::Kill(
309 310
    const AliasStateInfo& alias_info, MaybeHandle<Name> name,
    Zone* zone) const {
311 312 313
  for (auto info1 : this->info_for_node_) {
    if (info1.first->IsDead()) continue;
    if (alias_info.MayAlias(info1.first)) {
314
      AbstractField* that = zone->New<AbstractField>(zone);
315 316 317 318
      for (auto info2 : this->info_for_node_) {
        if (!alias_info.MayAlias(info2.first) ||
            !MayAlias(name, info2.second.name)) {
          that->info_for_node_.insert(info2);
319
        }
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 357
  for (auto info1 : this->info_for_node_) {
    if (alias_info.MayAlias(info1.first)) {
358
      AbstractMaps* that = zone->New<AbstractMaps>(zone);
359 360 361
      for (auto info2 : this->info_for_node_) {
        if (!alias_info.MayAlias(info2.first))
          that->info_for_node_.insert(info2);
362 363 364 365 366 367 368
      }
      return that;
    }
  }
  return this;
}

369 370 371
LoadElimination::AbstractMaps const* LoadElimination::AbstractMaps::Merge(
    AbstractMaps const* that, Zone* zone) const {
  if (this->Equals(that)) return this;
372
  AbstractMaps* copy = zone->New<AbstractMaps>(zone);
373 374
  for (auto this_it : this->info_for_node_) {
    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 378
    if (that_it != that->info_for_node_.end() && that_it->second == this_maps) {
      copy->info_for_node_.insert(this_it);
379 380 381 382 383 384
    }
  }
  return copy;
}

LoadElimination::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 391 392
  return that;
}

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

406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
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;
}

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

443
void LoadElimination::AbstractState::FieldsMerge(
444
    AbstractFields* this_fields, AbstractFields const& that_fields,
445
    Zone* zone) {
446 447 448
  for (size_t i = 0; i < this_fields->size(); ++i) {
    AbstractField const*& this_field = (*this_fields)[i];
    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
      }
    }
  }
}

458 459 460 461 462 463
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)
464
                          : nullptr;
465 466 467
  }

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

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

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

482
LoadElimination::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 491 492 493
  }
  return that;
}

LoadElimination::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 500 501 502 503 504 505
      that->maps_ = that_maps;
      return that;
    }
  }
  return this;
}

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

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

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

536 537 538 539 540 541 542
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) {
543
      AbstractState* that = zone->New<AbstractState>(*this);
544 545
      that->elements_ = that_elements;
      return that;
546 547
    }
  }
548 549
  return this;
}
550

551
LoadElimination::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 556
  AbstractFields& fields =
      info.const_field_info.IsConst() ? that->const_fields_ : that->fields_;
557 558 559 560
  for (int index : index_range) {
    if (fields[index]) {
      fields[index] = fields[index]->Extend(object, info, zone);
    } else {
561
      fields[index] = zone->New<AbstractField>(object, info, zone);
562
    }
563
  }
564 565 566
  return that;
}

567 568 569 570 571 572 573 574 575 576
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) {
577
        if (!that) that = zone->New<AbstractState>(*this);
578 579 580 581 582 583 584
        that->const_fields_[index] = this_field;
      }
    }
  }
  return that ? that : this;
}

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

LoadElimination::AbstractState const* LoadElimination::AbstractState::KillField(
593 594 595 596 597 598 599
    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) {
600
        if (!that) that = zone->New<AbstractState>(*this);
601 602
        that->fields_[index] = this_field;
      }
603
    }
604
  }
605
  return that ? that : this;
606
}
607

608
LoadElimination::AbstractState const*
609 610
LoadElimination::AbstractState::KillFields(Node* object, MaybeHandle<Name> name,
                                           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 616
      AbstractField const* that_field =
          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 626 627 628 629 630
          }
        }
        return that;
      }
    }
  }
}

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

644
LoadElimination::FieldInfo const* LoadElimination::AbstractState::LookupField(
645 646
    Node* object, IndexRange index_range,
    ConstFieldInfo const_field_info) const {
647 648 649 650 651
  // 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;
652 653 654 655 656 657 658 659 660 661
    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;
662 663 664
    }
    if (!result.has_value()) {
      result = info;
665 666 667 668 669 670 671
    } 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;
672
    }
673
  }
674
  return *result;
675 676
}

677
bool LoadElimination::AliasStateInfo::MayAlias(Node* other) const {
678 679 680 681 682 683
  // 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;
  }
684 685
  // Decide aliasing based on the node kinds.
  if (!compiler::MayAlias(object_, other)) {
686 687
    return false;
  }
688
  // Decide aliasing based on maps (if available).
689 690 691 692 693 694 695 696 697 698 699 700
  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;
}

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

724 725 726 727 728 729 730 731 732 733 734 735 736
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;
}
737

738
Reduction 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 743
  AbstractState const* state = node_states_.Get(effect);
  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 748
    // TODO(turbofan): Compute the intersection.
  }
749
  state = state->SetMaps(object, maps, zone());
750 751 752
  return UpdateState(node, state);
}

753
Reduction 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 758
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
759 760
  ZoneHandleSet<Map> object_maps;
  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 766 767
  return UpdateState(node, state);
}

768
Reduction LoadElimination::ReduceCompareMaps(Node* node) {
769
  ZoneHandleSet<Map> const& maps = CompareMapsParametersOf(node->op());
770 771 772 773
  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();
774 775
  ZoneHandleSet<Map> object_maps;
  if (state->LookupMaps(object, &object_maps)) {
776 777 778 779
    if (maps.contains(object_maps)) {
      Node* value = jsgraph()->TrueConstant();
      ReplaceWithValue(node, value, effect);
      return Replace(value);
780
    }
781
    // TODO(turbofan): Compute the intersection.
782 783 784 785
  }
  return UpdateState(node, state);
}

786 787 788 789 790 791
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();
792
  // Check if the {elements} already have the fixed array map.
793 794 795 796 797 798
  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);
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 804
  state = state->KillField(object,
                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
805
                           MaybeHandle<Name>(), zone());
806
  // Add the new elements on {object}.
807 808
  state = state->AddField(
      object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
809
      {node, MachineRepresentation::kTaggedPointer}, zone());
810 811 812
  return UpdateState(node, state);
}

813
Reduction LoadElimination::ReduceMaybeGrowFastElements(Node* node) {
814
  GrowFastElementsParameters params = GrowFastElementsParametersOf(node->op());
815 816 817 818
  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();
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 825 826 827 828
    // 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());
829 830
  }
  // Kill the previous elements on {object}.
831 832
  state = state->KillField(object,
                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
833
                           MaybeHandle<Name>(), zone());
834
  // Add the new elements on {object}.
835 836
  state = state->AddField(
      object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
837
      {node, MachineRepresentation::kTaggedPointer}, zone());
838 839 840
  return UpdateState(node, state);
}

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

881 882 883 884 885 886 887 888 889 890 891 892 893 894 895
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());
896
    state = state->KillMaps(object, zone());
897
    state = state->SetMaps(object, object_maps, zone());
898 899
  }
  // Kill the elements as well.
900 901
  state = state->KillField(object,
                           FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
902
                           MaybeHandle<Name>(), zone());
903 904 905
  return UpdateState(node, state);
}

906 907
Reduction LoadElimination::ReduceLoadField(Node* node,
                                           FieldAccess const& access) {
908 909 910
  Node* object = NodeProperties::GetValueInput(node, 0);
  Node* effect = NodeProperties::GetEffectInput(node);
  Node* control = NodeProperties::GetControlInput(node);
911 912
  AbstractState const* state = node_states_.Get(effect);
  if (state == nullptr) return NoChange();
913 914
  if (access.offset == HeapObject::kMapOffset &&
      access.base_is_tagged == kTaggedBase) {
915
    DCHECK(IsAnyTagged(access.machine_type.representation()));
916 917 918
    ZoneHandleSet<Map> object_maps;
    if (state->LookupMaps(object, &object_maps) && object_maps.size() == 1) {
      Node* value = jsgraph()->HeapConstant(object_maps[0]);
919
      NodeProperties::SetType(value, Type::OtherInternal());
920 921 922 923
      ReplaceWithValue(node, value, effect);
      return Replace(value);
    }
  } else {
924 925
    IndexRange field_index = FieldIndexOf(access);
    if (field_index != IndexRange::Invalid()) {
926 927 928
      MachineRepresentation representation =
          access.machine_type.representation();
      FieldInfo const* lookup_result =
929 930 931 932 933 934
          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());
935
      }
936 937 938 939 940 941
      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()) {
942 943 944 945 946 947 948 949 950 951 952 953
          // 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);
          }
954 955
          ReplaceWithValue(node, replacement, effect);
          return Replace(replacement);
956
        }
957
      }
958 959 960
      FieldInfo info(node, representation, access.name,
                     access.const_field_info);
      state = state->AddField(object, field_index, info, zone());
961 962
    }
  }
963 964
  Handle<Map> field_map;
  if (access.map.ToHandle(&field_map)) {
965
    state = state->SetMaps(node, ZoneHandleSet<Map>(field_map), zone());
966
  }
967 968
  return UpdateState(node, state);
}
969

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

998 999
      if (lookup_result &&
          (!is_const_store || V8_ENABLE_DOUBLE_CONST_STORE_CHECK_BOOL)) {
1000 1001 1002
        // At runtime, we should never encounter
        // - any store replacing existing info with a different, incompatible
        //   representation, nor
1003 1004
        // - two consecutive const stores, unless the latter is a store into
        //   a literal.
1005 1006
        // However, we may see such code statically, so we guard against
        // executing it by emitting Unreachable.
1007 1008 1009 1010
        // 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).
1011 1012 1013
        bool incompatible_representation =
            !lookup_result->name.is_null() &&
            !IsCompatible(representation, lookup_result->representation);
1014 1015 1016
        bool illegal_double_const_store =
            is_const_store && !access.is_store_in_literal;
        if (incompatible_representation || illegal_double_const_store) {
1017 1018 1019 1020 1021 1022 1023 1024 1025
          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);
        }
1026
      }
1027

1028
      // Kill all potentially aliasing fields and record the new value.
1029 1030
      FieldInfo new_info(new_value, representation, access.name,
                         access.const_field_info);
1031 1032 1033 1034 1035 1036
      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());
      }
1037
      state = state->KillField(object, field_index, access.name, zone());
1038 1039
      state = state->AddField(object, field_index, new_info, zone());
      if (is_const_store) {
1040 1041 1042
        // 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.
1043 1044
        new_info.const_field_info = ConstFieldInfo::None();
        state = state->AddField(object, field_index, new_info, zone());
1045
      }
1046 1047
    } else {
      // Unsupported StoreField operator.
1048
      state = state->KillFields(object, access.name, zone());
1049
    }
1050 1051 1052
  }
  return UpdateState(node, state);
}
1053

1054 1055 1056 1057 1058 1059
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();
1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070

  // 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:
1071 1072
    case MachineRepresentation::kCompressedPointer:
    case MachineRepresentation::kCompressed:
Samuel Groß's avatar
Samuel Groß committed
1073
    case MachineRepresentation::kSandboxedPointer:
1074 1075 1076 1077 1078 1079 1080
      // TODO(turbofan): Add support for doing the truncations.
      break;
    case MachineRepresentation::kFloat64:
    case MachineRepresentation::kSimd128:
    case MachineRepresentation::kTaggedSigned:
    case MachineRepresentation::kTaggedPointer:
    case MachineRepresentation::kTagged:
1081
    case MachineRepresentation::kMapWord:
1082 1083
      if (Node* replacement = state->LookupElement(
              object, index, access.machine_type.representation())) {
1084
        // Make sure we don't resurrect dead {replacement} nodes.
1085 1086
        // Skip lowering if the type of the {replacement} node is not a subtype
        // of the original {node}'s type.
1087 1088 1089
        // TODO(turbofan): We should insert a {TypeGuard} for the intersection
        // of these two types here once we properly handle {Type::None}
        // everywhere.
1090
        if (!replacement->IsDead() && NodeProperties::GetType(replacement)
1091
                                          .Is(NodeProperties::GetType(node))) {
1092 1093 1094
          ReplaceWithValue(node, replacement, effect);
          return Replace(replacement);
        }
1095
      }
1096 1097
      state = state->AddElement(object, index, node,
                                access.machine_type.representation(), zone());
1098
      return UpdateState(node, state);
1099
  }
1100
  return NoChange();
1101
}
1102

1103 1104 1105 1106 1107 1108 1109 1110
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();
1111 1112
  Node* const old_value =
      state->LookupElement(object, index, access.machine_type.representation());
1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127
  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:
1128 1129
    case MachineRepresentation::kCompressedPointer:
    case MachineRepresentation::kCompressed:
Samuel Groß's avatar
Samuel Groß committed
1130
    case MachineRepresentation::kSandboxedPointer:
1131 1132 1133 1134
      // TODO(turbofan): Add support for doing the truncations.
      break;
    case MachineRepresentation::kFloat64:
    case MachineRepresentation::kSimd128:
1135 1136
    case MachineRepresentation::kTaggedSigned:
    case MachineRepresentation::kTaggedPointer:
1137
    case MachineRepresentation::kTagged:
1138
    case MachineRepresentation::kMapWord:
1139 1140
      state = state->AddElement(object, index, new_value,
                                access.machine_type.representation(), zone());
1141 1142 1143 1144
      break;
  }
  return UpdateState(node, state);
}
1145

1146 1147 1148 1149 1150 1151 1152
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);
}

1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170
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;
  }
1171
  return state->SetMaps(phi, object_maps, zone());
1172 1173
}

1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189
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();
1190 1191 1192
  for (int i = 1; i < input_count; ++i) {
    Node* const effect = NodeProperties::GetEffectInput(node, i);
    if (node_states_.Get(effect) == nullptr) return NoChange();
1193 1194 1195 1196
  }

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

  // 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);
1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229
}

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)) {
1230
        state = state->KillAll(zone());
1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241
      }
      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();
}
1242

1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255
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();
}

1256 1257 1258 1259 1260 1261 1262 1263 1264
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 {
1265 1266
    IndexRange field_index = FieldIndexOf(access);
    if (field_index == IndexRange::Invalid()) {
1267 1268 1269 1270 1271 1272 1273 1274
      state = state->KillFields(object, access.name, zone());
    } else {
      state = state->KillField(object, field_index, access.name, zone());
    }
  }
  return state;
}

1275 1276 1277
LoadElimination::AbstractState const* LoadElimination::ComputeLoopState(
    Node* node, AbstractState const* state) const {
  Node* const control = NodeProperties::GetControlInput(node);
1278 1279 1280 1281
  struct TransitionElementsKindInfo {
    ElementsTransition transition;
    Node* object;
  };
1282 1283 1284 1285 1286 1287
  // 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);
1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298
  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()) {
1299 1300
          case IrOpcode::kEnsureWritableFastElements: {
            Node* const object = NodeProperties::GetValueInput(current, 0);
1301 1302 1303
            state = state->KillField(
                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
                MaybeHandle<Name>(), zone());
1304 1305
            break;
          }
1306 1307
          case IrOpcode::kMaybeGrowFastElements: {
            Node* const object = NodeProperties::GetValueInput(current, 0);
1308 1309 1310
            state = state->KillField(
                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
                MaybeHandle<Name>(), zone());
1311 1312
            break;
          }
1313
          case IrOpcode::kTransitionElementsKind: {
1314
            ElementsTransition transition = ElementsTransitionOf(current->op());
1315
            Node* const object = NodeProperties::GetValueInput(current, 0);
1316 1317 1318 1319
            ZoneHandleSet<Map> object_maps;
            if (!state->LookupMaps(object, &object_maps) ||
                !ZoneHandleSet<Map>(transition.target())
                     .contains(object_maps)) {
1320
              element_transitions_.push_back({transition, object});
1321
            }
1322 1323
            break;
          }
1324 1325 1326 1327 1328
          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.
1329 1330 1331
            state = state->KillField(
                object, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
                MaybeHandle<Name>(), zone());
1332 1333
            break;
          }
1334 1335
          case IrOpcode::kStoreField: {
            FieldAccess access = FieldAccessOf(current->op());
1336
            state = ComputeLoopStateForStoreField(current, state, access);
1337
            break;
1338
          }
1339 1340 1341 1342 1343 1344
          case IrOpcode::kStoreElement: {
            Node* const object = NodeProperties::GetValueInput(current, 0);
            Node* const index = NodeProperties::GetValueInput(current, 1);
            state = state->KillElement(object, index, zone());
            break;
          }
1345 1346 1347 1348
          case IrOpcode::kStoreTypedElement: {
            // Doesn't affect anything we track with the state currently.
            break;
          }
1349
          default:
1350
            return state->KillAll(zone());
1351 1352 1353 1354 1355 1356 1357
        }
      }
      for (int i = 0; i < current->op()->EffectInputCount(); ++i) {
        queue.push(NodeProperties::GetEffectInput(current, i));
      }
    }
  }
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 1387 1388 1389 1390 1391 1392

  // 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());
1393 1394 1395
        state = state->KillField(
            alias_info, FieldIndexOf(JSObject::kElementsOffset, kTaggedSize),
            MaybeHandle<Name>(), zone());
1396 1397 1398 1399
        break;
      }
    }
  }
1400 1401 1402
  return state;
}

1403
// static
1404 1405
LoadElimination::IndexRange LoadElimination::FieldIndexOf(
    int offset, int representation_size) {
1406
  DCHECK(IsAligned(offset, kTaggedSize));
1407 1408 1409
  int field_index = offset / kTaggedSize - 1;
  DCHECK_EQ(0, representation_size % kTaggedSize);
  return IndexRange(field_index, representation_size / kTaggedSize);
1410 1411
}

1412
// static
1413 1414
LoadElimination::IndexRange LoadElimination::FieldIndexOf(
    FieldAccess const& access) {
1415 1416
  MachineRepresentation rep = access.machine_type.representation();
  switch (rep) {
1417 1418
    case MachineRepresentation::kNone:
    case MachineRepresentation::kBit:
1419
    case MachineRepresentation::kSimd128:
1420
      UNREACHABLE();
1421 1422
    case MachineRepresentation::kWord8:
    case MachineRepresentation::kWord16:
1423
    case MachineRepresentation::kFloat32:
1424 1425
      // Currently untracked.
      return IndexRange::Invalid();
1426
    case MachineRepresentation::kFloat64:
1427 1428
    case MachineRepresentation::kWord32:
    case MachineRepresentation::kWord64:
1429 1430
    case MachineRepresentation::kTaggedSigned:
    case MachineRepresentation::kTaggedPointer:
1431
    case MachineRepresentation::kTagged:
1432
    case MachineRepresentation::kMapWord:
1433 1434
    case MachineRepresentation::kCompressedPointer:
    case MachineRepresentation::kCompressed:
Samuel Groß's avatar
Samuel Groß committed
1435
    case MachineRepresentation::kSandboxedPointer:
1436 1437
      break;
  }
1438 1439 1440 1441 1442
  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);

1443
  if (access.base_is_tagged != kTaggedBase) {
1444 1445
    // We currently only track tagged objects.
    return IndexRange::Invalid();
1446
  }
1447
  return FieldIndexOf(access.offset, representation_size);
1448 1449
}

1450 1451 1452 1453 1454 1455
CommonOperatorBuilder* LoadElimination::common() const {
  return jsgraph()->common();
}

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

1456 1457
Isolate* LoadElimination::isolate() const { return jsgraph()->isolate(); }

1458 1459
Factory* LoadElimination::factory() const { return jsgraph()->factory(); }

1460 1461 1462
}  // namespace compiler
}  // namespace internal
}  // namespace v8