escape-analysis.cc 31.2 KB
Newer Older
1
// Copyright 2017 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/escape-analysis.h"

7
#include "src/codegen/tick-counter.h"
8
#include "src/compiler/linkage.h"
9
#include "src/compiler/node-matchers.h"
10
#include "src/compiler/operator-properties.h"
11
#include "src/compiler/simplified-operator.h"
12
#include "src/handles/handles-inl.h"
13
#include "src/init/bootstrapper.h"
14
#include "src/objects/map-inl.h"
15

16 17 18 19 20 21 22 23 24
#ifdef DEBUG
#define TRACE(...)                                    \
  do {                                                \
    if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
  } while (false)
#else
#define TRACE(...)
#endif

25 26 27
namespace v8 {
namespace internal {
namespace compiler {
28

29 30
template <class T>
class Sidetable {
31
 public:
32 33 34 35 36
  explicit Sidetable(Zone* zone) : map_(zone) {}
  T& operator[](const Node* node) {
    NodeId id = node->id();
    if (id >= map_.size()) {
      map_.resize(id + 1);
37
    }
38
    return map_[id];
39
  }
40 41

 private:
42
  ZoneVector<T> map_;
43 44
};

45 46
template <class T>
class SparseSidetable {
47
 public:
48 49 50 51 52 53 54 55
  explicit SparseSidetable(Zone* zone, T def_value = T())
      : def_value_(std::move(def_value)), map_(zone) {}
  void Set(const Node* node, T value) {
    auto iter = map_.find(node->id());
    if (iter != map_.end()) {
      iter->second = std::move(value);
    } else if (value != def_value_) {
      map_.insert(iter, std::make_pair(node->id(), std::move(value)));
56 57
    }
  }
58 59 60
  const T& Get(const Node* node) const {
    auto iter = map_.find(node->id());
    return iter != map_.end() ? iter->second : def_value_;
61
  }
62 63

 private:
64 65
  T def_value_;
  ZoneUnorderedMap<NodeId, T> map_;
66 67
};

68 69 70 71 72 73
// Keeps track of the changes to the current node during reduction.
// Encapsulates the current state of the IR graph and the reducer state like
// side-tables. All access to the IR and the reducer state should happen through
// a ReduceScope to ensure that changes and dependencies are tracked and all
// necessary node revisitations happen.
class ReduceScope {
74
 public:
75
  using Reduction = EffectGraphReducer::Reduction;
76 77
  explicit ReduceScope(Node* node, Reduction* reduction)
      : current_node_(node), reduction_(reduction) {}
78

79 80 81
 protected:
  Node* current_node() const { return current_node_; }
  Reduction* reduction() { return reduction_; }
82

83 84 85
 private:
  Node* current_node_;
  Reduction* reduction_;
86 87
};

88 89 90 91 92 93 94 95 96 97 98 99 100
// A VariableTracker object keeps track of the values of variables at all points
// of the effect chain and introduces new phi nodes when necessary.
// Initially and by default, variables are mapped to nullptr, which means that
// the variable allocation point does not dominate the current point on the
// effect chain. We map variables that represent uninitialized memory to the
// Dead node to ensure it is not read.
// Unmapped values are impossible by construction, it is indistinguishable if a
// PersistentMap does not contain an element or maps it to the default element.
class VariableTracker {
 private:
  // The state of all variables at one point in the effect chain.
  class State {
   public:
101 102
    using Map = PersistentMap<Variable, Node*>;

103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
    explicit State(Zone* zone) : map_(zone) {}
    Node* Get(Variable var) const {
      CHECK(var != Variable::Invalid());
      return map_.Get(var);
    }
    void Set(Variable var, Node* node) {
      CHECK(var != Variable::Invalid());
      return map_.Set(var, node);
    }
    Map::iterator begin() const { return map_.begin(); }
    Map::iterator end() const { return map_.end(); }
    bool operator!=(const State& other) const { return map_ != other.map_; }

   private:
    Map map_;
  };
119

120 121
 public:
  VariableTracker(JSGraph* graph, EffectGraphReducer* reducer, Zone* zone);
122 123 124
  VariableTracker(const VariableTracker&) = delete;
  VariableTracker& operator=(const VariableTracker&) = delete;

125 126 127 128
  Variable NewVariable() { return Variable(next_variable_++); }
  Node* Get(Variable var, Node* effect) { return table_.Get(effect).Get(var); }
  Zone* zone() { return zone_; }

129
  class V8_NODISCARD Scope : public ReduceScope {
130 131 132
   public:
    Scope(VariableTracker* tracker, Node* node, Reduction* reduction);
    ~Scope();
133 134 135
    Maybe<Node*> Get(Variable var) {
      Node* node = current_state_.Get(var);
      if (node && node->opcode() == IrOpcode::kDead) {
136
        // TODO(turbofan): We use {Dead} as a sentinel for uninitialized memory.
137 138 139 140 141 142 143 144
        // Reading uninitialized memory can only happen in unreachable code. In
        // this case, we have to mark the object as escaping to avoid dead nodes
        // in the graph. This is a workaround that should be removed once we can
        // handle dead nodes everywhere.
        return Nothing<Node*>();
      }
      return Just(node);
    }
145 146 147 148 149 150
    void Set(Variable var, Node* node) { current_state_.Set(var, node); }

   private:
    VariableTracker* states_;
    State current_state_;
  };
151

152 153 154 155 156 157 158 159
 private:
  State MergeInputs(Node* effect_phi);
  Zone* zone_;
  JSGraph* graph_;
  SparseSidetable<State> table_;
  ZoneVector<Node*> buffer_;
  EffectGraphReducer* reducer_;
  int next_variable_ = 0;
160
  TickCounter* const tick_counter_;
161
};
162

163 164 165 166 167 168 169 170 171 172 173
// Encapsulates the current state of the escape analysis reducer to preserve
// invariants regarding changes and re-visitation.
class EscapeAnalysisTracker : public ZoneObject {
 public:
  EscapeAnalysisTracker(JSGraph* jsgraph, EffectGraphReducer* reducer,
                        Zone* zone)
      : virtual_objects_(zone),
        replacements_(zone),
        variable_states_(jsgraph, reducer, zone),
        jsgraph_(jsgraph),
        zone_(zone) {}
174 175
  EscapeAnalysisTracker(const EscapeAnalysisTracker&) = delete;
  EscapeAnalysisTracker& operator=(const EscapeAnalysisTracker&) = delete;
176

177
  class V8_NODISCARD Scope : public VariableTracker::Scope {
178 179 180 181 182 183 184 185 186 187 188 189 190
   public:
    Scope(EffectGraphReducer* reducer, EscapeAnalysisTracker* tracker,
          Node* node, Reduction* reduction)
        : VariableTracker::Scope(&tracker->variable_states_, node, reduction),
          tracker_(tracker),
          reducer_(reducer) {}
    const VirtualObject* GetVirtualObject(Node* node) {
      VirtualObject* vobject = tracker_->virtual_objects_.Get(node);
      if (vobject) vobject->AddDependency(current_node());
      return vobject;
    }
    // Create or retrieve a virtual object for the current node.
    const VirtualObject* InitVirtualObject(int size) {
191
      DCHECK_EQ(IrOpcode::kAllocate, current_node()->opcode());
192 193 194 195 196
      VirtualObject* vobject = tracker_->virtual_objects_.Get(current_node());
      if (vobject) {
        CHECK(vobject->size() == size);
      } else {
        vobject = tracker_->NewVirtualObject(size);
197
      }
198 199 200
      if (vobject) vobject->AddDependency(current_node());
      vobject_ = vobject;
      return vobject;
201
    }
202

203 204
    void SetVirtualObject(Node* object) {
      vobject_ = tracker_->virtual_objects_.Get(object);
205
    }
206

207 208 209 210 211 212 213 214
    void SetEscaped(Node* node) {
      if (VirtualObject* object = tracker_->virtual_objects_.Get(node)) {
        if (object->HasEscaped()) return;
        TRACE("Setting %s#%d to escaped because of use by %s#%d\n",
              node->op()->mnemonic(), node->id(),
              current_node()->op()->mnemonic(), current_node()->id());
        object->SetEscaped();
        object->RevisitDependants(reducer_);
215 216
      }
    }
217 218 219 220 221
    // The inputs of the current node have to be accessed through the scope to
    // ensure that they respect the node replacements.
    Node* ValueInput(int i) {
      return tracker_->ResolveReplacement(
          NodeProperties::GetValueInput(current_node(), i));
222
    }
223 224 225
    Node* ContextInput() {
      return tracker_->ResolveReplacement(
          NodeProperties::GetContextInput(current_node()));
226
    }
227

228 229 230 231
    void SetReplacement(Node* replacement) {
      replacement_ = replacement;
      vobject_ =
          replacement ? tracker_->virtual_objects_.Get(replacement) : nullptr;
232 233 234 235 236 237
      if (replacement) {
        TRACE("Set %s#%d as replacement.\n", replacement->op()->mnemonic(),
              replacement->id());
      } else {
        TRACE("Set nullptr as replacement.\n");
      }
238
    }
239

240
    void MarkForDeletion() { SetReplacement(tracker_->jsgraph_->Dead()); }
241 242 243 244 245

    ~Scope() {
      if (replacement_ != tracker_->replacements_[current_node()] ||
          vobject_ != tracker_->virtual_objects_.Get(current_node())) {
        reduction()->set_value_changed();
246
      }
247 248
      tracker_->replacements_[current_node()] = replacement_;
      tracker_->virtual_objects_.Set(current_node(), vobject_);
249
    }
250

251 252 253 254 255 256
   private:
    EscapeAnalysisTracker* tracker_;
    EffectGraphReducer* reducer_;
    VirtualObject* vobject_ = nullptr;
    Node* replacement_ = nullptr;
  };
257

258 259 260 261
  Node* GetReplacementOf(Node* node) { return replacements_[node]; }
  Node* ResolveReplacement(Node* node) {
    if (Node* replacement = GetReplacementOf(node)) {
      return replacement;
262
    }
263
    return node;
264 265
  }

266 267 268
 private:
  friend class EscapeAnalysisResult;
  static const size_t kMaxTrackedObjects = 100;
269

270 271
  VirtualObject* NewVirtualObject(int size) {
    if (next_object_id_ >= kMaxTrackedObjects) return nullptr;
272 273
    return zone_->New<VirtualObject>(&variable_states_, next_object_id_++,
                                     size);
274 275
  }

276 277 278 279 280 281 282
  SparseSidetable<VirtualObject*> virtual_objects_;
  Sidetable<Node*> replacements_;
  VariableTracker variable_states_;
  VirtualObject::Id next_object_id_ = 0;
  JSGraph* const jsgraph_;
  Zone* const zone_;
};
283

284
EffectGraphReducer::EffectGraphReducer(
285 286
    Graph* graph, std::function<void(Node*, Reduction*)> reduce,
    TickCounter* tick_counter, Zone* zone)
287 288 289 290
    : graph_(graph),
      state_(graph, kNumStates),
      revisit_(zone),
      stack_(zone),
291 292
      reduce_(std::move(reduce)),
      tick_counter_(tick_counter) {}
293 294 295 296 297 298 299

void EffectGraphReducer::ReduceFrom(Node* node) {
  // Perform DFS and eagerly trigger revisitation as soon as possible.
  // A stack element {node, i} indicates that input i of node should be visited
  // next.
  DCHECK(stack_.empty());
  stack_.push({node, 0});
300
  while (!stack_.empty()) {
301
    tick_counter_->TickAndMaybeEnterSafepoint();
302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319
    Node* current = stack_.top().node;
    int& input_index = stack_.top().input_index;
    if (input_index < current->InputCount()) {
      Node* input = current->InputAt(input_index);
      input_index++;
      switch (state_.Get(input)) {
        case State::kVisited:
          // The input is already reduced.
          break;
        case State::kOnStack:
          // The input is on the DFS stack right now, so it will be revisited
          // later anyway.
          break;
        case State::kUnvisited:
        case State::kRevisit: {
          state_.Set(input, State::kOnStack);
          stack_.push({input, 0});
          break;
320
        }
321 322 323 324 325 326 327 328 329 330 331 332
      }
    } else {
      stack_.pop();
      Reduction reduction;
      reduce_(current, &reduction);
      for (Edge edge : current->use_edges()) {
        // Mark uses for revisitation.
        Node* use = edge.from();
        if (NodeProperties::IsEffectEdge(edge)) {
          if (reduction.effect_changed()) Revisit(use);
        } else {
          if (reduction.value_changed()) Revisit(use);
333 334
        }
      }
335 336 337 338 339 340 341 342 343 344 345
      state_.Set(current, State::kVisited);
      // Process the revisitation buffer immediately. This improves performance
      // of escape analysis. Using a stack for {revisit_} reverses the order in
      // which the revisitation happens. This also seems to improve performance.
      while (!revisit_.empty()) {
        Node* revisit = revisit_.top();
        if (state_.Get(revisit) == State::kRevisit) {
          state_.Set(revisit, State::kOnStack);
          stack_.push({revisit, 0});
        }
        revisit_.pop();
346 347 348 349 350
      }
    }
  }
}

351 352 353 354 355 356
void EffectGraphReducer::Revisit(Node* node) {
  if (state_.Get(node) == State::kVisited) {
    TRACE("  Queueing for revisit: %s#%d\n", node->op()->mnemonic(),
          node->id());
    state_.Set(node, State::kRevisit);
    revisit_.push(node);
357 358 359
  }
}

360 361 362 363 364 365
VariableTracker::VariableTracker(JSGraph* graph, EffectGraphReducer* reducer,
                                 Zone* zone)
    : zone_(zone),
      graph_(graph),
      table_(zone, State(zone)),
      buffer_(zone),
366 367
      reducer_(reducer),
      tick_counter_(reducer->tick_counter()) {}
368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405

VariableTracker::Scope::Scope(VariableTracker* states, Node* node,
                              Reduction* reduction)
    : ReduceScope(node, reduction),
      states_(states),
      current_state_(states->zone_) {
  switch (node->opcode()) {
    case IrOpcode::kEffectPhi:
      current_state_ = states_->MergeInputs(node);
      break;
    default:
      int effect_inputs = node->op()->EffectInputCount();
      if (effect_inputs == 1) {
        current_state_ =
            states_->table_.Get(NodeProperties::GetEffectInput(node, 0));
      } else {
        DCHECK_EQ(0, effect_inputs);
      }
  }
}

VariableTracker::Scope::~Scope() {
  if (!reduction()->effect_changed() &&
      states_->table_.Get(current_node()) != current_state_) {
    reduction()->set_effect_changed();
  }
  states_->table_.Set(current_node(), current_state_);
}

VariableTracker::State VariableTracker::MergeInputs(Node* effect_phi) {
  // A variable that is mapped to [nullptr] was not assigned a value on every
  // execution path to the current effect phi. Relying on the invariant that
  // every variable is initialized (at least with a sentinel like the Dead
  // node), this means that the variable initialization does not dominate the
  // current point. So for loop effect phis, we can keep nullptr for a variable
  // as long as the first input of the loop has nullptr for this variable. For
  // non-loop effect phis, we can even keep it nullptr as long as any input has
  // nullptr.
406
  DCHECK_EQ(IrOpcode::kEffectPhi, effect_phi->opcode());
407 408 409 410 411 412 413 414 415
  int arity = effect_phi->op()->EffectInputCount();
  Node* control = NodeProperties::GetControlInput(effect_phi, 0);
  TRACE("control: %s#%d\n", control->op()->mnemonic(), control->id());
  bool is_loop = control->opcode() == IrOpcode::kLoop;
  buffer_.reserve(arity + 1);

  State first_input = table_.Get(NodeProperties::GetEffectInput(effect_phi, 0));
  State result = first_input;
  for (std::pair<Variable, Node*> var_value : first_input) {
416
    tick_counter_->TickAndMaybeEnterSafepoint();
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434
    if (Node* value = var_value.second) {
      Variable var = var_value.first;
      TRACE("var %i:\n", var.id_);
      buffer_.clear();
      buffer_.push_back(value);
      bool identical_inputs = true;
      int num_defined_inputs = 1;
      TRACE("  input 0: %s#%d\n", value->op()->mnemonic(), value->id());
      for (int i = 1; i < arity; ++i) {
        Node* next_value =
            table_.Get(NodeProperties::GetEffectInput(effect_phi, i)).Get(var);
        if (next_value != value) identical_inputs = false;
        if (next_value != nullptr) {
          num_defined_inputs++;
          TRACE("  input %i: %s#%d\n", i, next_value->op()->mnemonic(),
                next_value->id());
        } else {
          TRACE("  input %i: nullptr\n", i);
435
        }
436
        buffer_.push_back(next_value);
437 438
      }

439 440 441 442 443 444 445 446 447 448 449 450 451
      Node* old_value = table_.Get(effect_phi).Get(var);
      if (old_value) {
        TRACE("  old: %s#%d\n", old_value->op()->mnemonic(), old_value->id());
      } else {
        TRACE("  old: nullptr\n");
      }
      // Reuse a previously created phi node if possible.
      if (old_value && old_value->opcode() == IrOpcode::kPhi &&
          NodeProperties::GetControlInput(old_value, 0) == control) {
        // Since a phi node can never dominate its control node,
        // [old_value] cannot originate from the inputs. Thus [old_value]
        // must have been created by a previous reduction of this [effect_phi].
        for (int i = 0; i < arity; ++i) {
452 453 454 455 456 457
          Node* old_input = NodeProperties::GetValueInput(old_value, i);
          Node* new_input = buffer_[i] ? buffer_[i] : graph_->Dead();
          if (old_input != new_input) {
            NodeProperties::ReplaceValueInput(old_value, new_input, i);
            reducer_->Revisit(old_value);
          }
458
        }
459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
        result.Set(var, old_value);
      } else {
        if (num_defined_inputs == 1 && is_loop) {
          // For loop effect phis, the variable initialization dominates iff it
          // dominates the first input.
          DCHECK_EQ(2, arity);
          DCHECK_EQ(value, buffer_[0]);
          result.Set(var, value);
        } else if (num_defined_inputs < arity) {
          // If the variable is undefined on some input of this non-loop effect
          // phi, then its initialization does not dominate this point.
          result.Set(var, nullptr);
        } else {
          DCHECK_EQ(num_defined_inputs, arity);
          // We only create a phi if the values are different.
          if (identical_inputs) {
            result.Set(var, value);
476
          } else {
477 478 479 480 481
            TRACE("Creating new phi\n");
            buffer_.push_back(control);
            Node* phi = graph_->graph()->NewNode(
                graph_->common()->Phi(MachineRepresentation::kTagged, arity),
                arity + 1, &buffer_.front());
482 483
            // TODO(turbofan): Computing precise types here is tricky, because
            // of the necessary revisitations. If we really need this, we should
484 485 486 487
            // probably do it afterwards.
            NodeProperties::SetType(phi, Type::Any());
            reducer_->AddRoot(phi);
            result.Set(var, phi);
488 489 490
          }
        }
      }
491
#ifdef DEBUG
492 493 494 495 496
      if (Node* result_node = result.Get(var)) {
        TRACE("  result: %s#%d\n", result_node->op()->mnemonic(),
              result_node->id());
      } else {
        TRACE("  result: nullptr\n");
497
      }
498
#endif
499 500
    }
  }
501
  return result;
502 503
}

504 505
namespace {

506 507 508 509 510 511 512
int OffsetOfFieldAccess(const Operator* op) {
  DCHECK(op->opcode() == IrOpcode::kLoadField ||
         op->opcode() == IrOpcode::kStoreField);
  FieldAccess access = FieldAccessOf(op);
  return access.offset;
}

513 514 515
int OffsetOfElementAt(ElementAccess const& access, int index) {
  DCHECK_GE(index, 0);
  DCHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
516
            kTaggedSizeLog2);
517 518 519 520
  return access.header_size +
         (index << ElementSizeLog2Of(access.machine_type.representation()));
}

521 522 523
Maybe<int> OffsetOfElementsAccess(const Operator* op, Node* index_node) {
  DCHECK(op->opcode() == IrOpcode::kLoadElement ||
         op->opcode() == IrOpcode::kStoreElement);
524
  Type index_type = NodeProperties::GetType(index_node);
525 526 527
  if (!index_type.Is(Type::OrderedNumber())) return Nothing<int>();
  double max = index_type.Max();
  double min = index_type.Min();
528
  int index = static_cast<int>(min);
529
  if (index < 0 || index != min || index != max) return Nothing<int>();
530
  return Just(OffsetOfElementAt(ElementAccessOf(op), index));
531 532
}

533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557
Node* LowerCompareMapsWithoutLoad(Node* checked_map,
                                  ZoneHandleSet<Map> const& checked_against,
                                  JSGraph* jsgraph) {
  Node* true_node = jsgraph->TrueConstant();
  Node* false_node = jsgraph->FalseConstant();
  Node* replacement = false_node;
  for (Handle<Map> map : checked_against) {
    Node* map_node = jsgraph->HeapConstant(map);
    // We cannot create a HeapConstant type here as we are off-thread.
    NodeProperties::SetType(map_node, Type::Internal());
    Node* comparison = jsgraph->graph()->NewNode(
        jsgraph->simplified()->ReferenceEqual(), checked_map, map_node);
    NodeProperties::SetType(comparison, Type::Boolean());
    if (replacement == false_node) {
      replacement = comparison;
    } else {
      replacement = jsgraph->graph()->NewNode(
          jsgraph->common()->Select(MachineRepresentation::kTaggedPointer),
          comparison, true_node, replacement);
      NodeProperties::SetType(replacement, Type::Boolean());
    }
  }
  return replacement;
}

558 559 560 561 562
void ReduceNode(const Operator* op, EscapeAnalysisTracker::Scope* current,
                JSGraph* jsgraph) {
  switch (op->opcode()) {
    case IrOpcode::kAllocate: {
      NumberMatcher size(current->ValueInput(0));
563 564 565
      if (!size.HasResolvedValue()) break;
      int size_int = static_cast<int>(size.ResolvedValue());
      if (size_int != size.ResolvedValue()) break;
566 567 568
      if (const VirtualObject* vobject = current->InitVirtualObject(size_int)) {
        // Initialize with dead nodes as a sentinel for uninitialized memory.
        for (Variable field : *vobject) {
569
          current->Set(field, jsgraph->Dead());
570 571
        }
      }
572
      break;
573
    }
574
    case IrOpcode::kFinishRegion:
575
      current->SetVirtualObject(current->ValueInput(0));
576
      break;
577 578 579 580 581 582 583 584 585 586 587 588
    case IrOpcode::kStoreField: {
      Node* object = current->ValueInput(0);
      Node* value = current->ValueInput(1);
      const VirtualObject* vobject = current->GetVirtualObject(object);
      Variable var;
      if (vobject && !vobject->HasEscaped() &&
          vobject->FieldAt(OffsetOfFieldAccess(op)).To(&var)) {
        current->Set(var, value);
        current->MarkForDeletion();
      } else {
        current->SetEscaped(object);
        current->SetEscaped(value);
589 590
      }
      break;
591
    }
592 593 594 595 596 597 598 599 600 601 602 603 604 605 606
    case IrOpcode::kStoreElement: {
      Node* object = current->ValueInput(0);
      Node* index = current->ValueInput(1);
      Node* value = current->ValueInput(2);
      const VirtualObject* vobject = current->GetVirtualObject(object);
      int offset;
      Variable var;
      if (vobject && !vobject->HasEscaped() &&
          OffsetOfElementsAccess(op, index).To(&offset) &&
          vobject->FieldAt(offset).To(&var)) {
        current->Set(var, value);
        current->MarkForDeletion();
      } else {
        current->SetEscaped(value);
        current->SetEscaped(object);
607
      }
608
      break;
609
    }
610 611 612 613
    case IrOpcode::kLoadField: {
      Node* object = current->ValueInput(0);
      const VirtualObject* vobject = current->GetVirtualObject(object);
      Variable var;
614
      Node* value;
615
      if (vobject && !vobject->HasEscaped() &&
616 617 618
          vobject->FieldAt(OffsetOfFieldAccess(op)).To(&var) &&
          current->Get(var).To(&value)) {
        current->SetReplacement(value);
619 620
      } else {
        current->SetEscaped(object);
621
      }
622
      break;
623
    }
624 625 626 627 628 629
    case IrOpcode::kLoadElement: {
      Node* object = current->ValueInput(0);
      Node* index = current->ValueInput(1);
      const VirtualObject* vobject = current->GetVirtualObject(object);
      int offset;
      Variable var;
630
      Node* value;
631 632
      if (vobject && !vobject->HasEscaped() &&
          OffsetOfElementsAccess(op, index).To(&offset) &&
633 634
          vobject->FieldAt(offset).To(&var) && current->Get(var).To(&value)) {
        current->SetReplacement(value);
635
        break;
636 637 638 639 640 641 642 643 644 645 646 647
      } else if (vobject && !vobject->HasEscaped()) {
        // Compute the known length (aka the number of elements) of {object}
        // based on the virtual object information.
        ElementAccess const& access = ElementAccessOf(op);
        int const length =
            (vobject->size() - access.header_size) >>
            ElementSizeLog2Of(access.machine_type.representation());
        Variable var0, var1;
        Node* value0;
        Node* value1;
        if (length == 1 &&
            vobject->FieldAt(OffsetOfElementAt(access, 0)).To(&var) &&
648 649 650
            current->Get(var).To(&value) &&
            (value == nullptr ||
             NodeProperties::GetType(value).Is(access.type))) {
651 652 653 654 655 656 657 658
          // The {object} has no elements, and we know that the LoadElement
          // {index} must be within bounds, thus it must always yield this
          // one element of {object}.
          current->SetReplacement(value);
          break;
        } else if (length == 2 &&
                   vobject->FieldAt(OffsetOfElementAt(access, 0)).To(&var0) &&
                   current->Get(var0).To(&value0) &&
659 660
                   (value0 == nullptr ||
                    NodeProperties::GetType(value0).Is(access.type)) &&
661
                   vobject->FieldAt(OffsetOfElementAt(access, 1)).To(&var1) &&
662 663 664
                   current->Get(var1).To(&value1) &&
                   (value1 == nullptr ||
                    NodeProperties::GetType(value1).Is(access.type))) {
665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689
          if (value0 && value1) {
            // The {object} has exactly two elements, so the LoadElement
            // must return one of them (i.e. either the element at index
            // 0 or the one at index 1). So we can turn the LoadElement
            // into a Select operation instead (still allowing the {object}
            // to be scalar replaced). We must however mark the elements
            // of the {object} itself as escaping.
            Node* check =
                jsgraph->graph()->NewNode(jsgraph->simplified()->NumberEqual(),
                                          index, jsgraph->ZeroConstant());
            NodeProperties::SetType(check, Type::Boolean());
            Node* select = jsgraph->graph()->NewNode(
                jsgraph->common()->Select(access.machine_type.representation()),
                check, value0, value1);
            NodeProperties::SetType(select, access.type);
            current->SetReplacement(select);
            current->SetEscaped(value0);
            current->SetEscaped(value1);
            break;
          } else {
            // If the variables have no values, we have
            // not reached the fixed-point yet.
            break;
          }
        }
690
      }
691
      current->SetEscaped(object);
692
      break;
693
    }
694
    case IrOpcode::kTypeGuard: {
695
      current->SetVirtualObject(current->ValueInput(0));
696
      break;
697
    }
698 699 700 701 702 703 704 705 706 707 708 709
    case IrOpcode::kReferenceEqual: {
      Node* left = current->ValueInput(0);
      Node* right = current->ValueInput(1);
      const VirtualObject* left_object = current->GetVirtualObject(left);
      const VirtualObject* right_object = current->GetVirtualObject(right);
      Node* replacement = nullptr;
      if (left_object && !left_object->HasEscaped()) {
        if (right_object && !right_object->HasEscaped() &&
            left_object->id() == right_object->id()) {
          replacement = jsgraph->TrueConstant();
        } else {
          replacement = jsgraph->FalseConstant();
710
        }
711 712 713
      } else if (right_object && !right_object->HasEscaped()) {
        replacement = jsgraph->FalseConstant();
      }
714
      // TODO(turbofan) This is a workaround for uninhabited types. If we
715 716 717 718 719 720 721 722 723
      // replaced a value of uninhabited type with a constant, we would
      // widen the type of the node. This could produce inconsistent
      // types (which might confuse representation selection). We get
      // around this by refusing to constant-fold and escape-analyze
      // if the type is not inhabited.
      if (replacement && !NodeProperties::GetType(left).IsNone() &&
          !NodeProperties::GetType(right).IsNone()) {
        current->SetReplacement(replacement);
        break;
724
      }
725 726
      current->SetEscaped(left);
      current->SetEscaped(right);
727
      break;
728
    }
729 730 731 732 733
    case IrOpcode::kCheckMaps: {
      CheckMapsParameters params = CheckMapsParametersOf(op);
      Node* checked = current->ValueInput(0);
      const VirtualObject* vobject = current->GetVirtualObject(checked);
      Variable map_field;
734
      Node* map;
735
      if (vobject && !vobject->HasEscaped() &&
736 737 738
          vobject->FieldAt(HeapObject::kMapOffset).To(&map_field) &&
          current->Get(map_field).To(&map)) {
        if (map) {
739
          Type const map_type = NodeProperties::GetType(map);
740
          if (map_type.IsHeapConstant() &&
741
              params.maps().contains(
742
                  map_type.AsHeapConstant()->Ref().AsMap().object())) {
743 744 745
            current->MarkForDeletion();
            break;
          }
746 747 748 749
        } else {
          // If the variable has no value, we have not reached the fixed-point
          // yet.
          break;
750
        }
751
      }
752 753
      current->SetEscaped(checked);
      break;
754
    }
755 756 757 758
    case IrOpcode::kCompareMaps: {
      Node* object = current->ValueInput(0);
      const VirtualObject* vobject = current->GetVirtualObject(object);
      Variable map_field;
759
      Node* object_map;
760
      if (vobject && !vobject->HasEscaped() &&
761 762 763
          vobject->FieldAt(HeapObject::kMapOffset).To(&map_field) &&
          current->Get(map_field).To(&object_map)) {
        if (object_map) {
764
          current->SetReplacement(LowerCompareMapsWithoutLoad(
765
              object_map, CompareMapsParametersOf(op), jsgraph));
766 767 768 769 770 771 772 773 774 775
          break;
        } else {
          // If the variable has no value, we have not reached the fixed-point
          // yet.
          break;
        }
      }
      current->SetEscaped(object);
      break;
    }
776 777 778 779 780 781 782 783 784 785 786
    case IrOpcode::kCheckHeapObject: {
      Node* checked = current->ValueInput(0);
      switch (checked->opcode()) {
        case IrOpcode::kAllocate:
        case IrOpcode::kFinishRegion:
        case IrOpcode::kHeapConstant:
          current->SetReplacement(checked);
          break;
        default:
          current->SetEscaped(checked);
          break;
787
      }
788
      break;
789
    }
790 791 792 793 794
    case IrOpcode::kMapGuard: {
      Node* object = current->ValueInput(0);
      const VirtualObject* vobject = current->GetVirtualObject(object);
      if (vobject && !vobject->HasEscaped()) {
        current->MarkForDeletion();
795
      }
796
      break;
797
    }
798 799 800 801 802 803 804 805 806 807
    case IrOpcode::kStateValues:
    case IrOpcode::kFrameState:
      // These uses are always safe.
      break;
    default: {
      // For unknown nodes, treat all value inputs as escaping.
      int value_input_count = op->ValueInputCount();
      for (int i = 0; i < value_input_count; ++i) {
        Node* input = current->ValueInput(i);
        current->SetEscaped(input);
808
      }
809 810
      if (OperatorProperties::HasContextInput(op)) {
        current->SetEscaped(current->ContextInput());
811
      }
812
      break;
813 814 815 816
    }
  }
}

817 818 819 820 821 822 823 824
}  // namespace

void EscapeAnalysis::Reduce(Node* node, Reduction* reduction) {
  const Operator* op = node->op();
  TRACE("Reducing %s#%d\n", op->mnemonic(), node->id());

  EscapeAnalysisTracker::Scope current(this, tracker_, node, reduction);
  ReduceNode(op, &current, jsgraph());
825 826
}

827 828
EscapeAnalysis::EscapeAnalysis(JSGraph* jsgraph, TickCounter* tick_counter,
                               Zone* zone)
829 830 831
    : EffectGraphReducer(
          jsgraph->graph(),
          [this](Node* node, Reduction* reduction) { Reduce(node, reduction); },
832
          tick_counter, zone),
833
      tracker_(zone->New<EscapeAnalysisTracker>(jsgraph, this, zone)),
834 835 836
      jsgraph_(jsgraph) {}

Node* EscapeAnalysisResult::GetReplacementOf(Node* node) {
837 838 839 840 841 842
  Node* replacement = tracker_->GetReplacementOf(node);
  // Replacements cannot have replacements. This is important to ensure
  // re-visitation: If a replacement is replaced, then all nodes accessing
  // the replacement have to be updated.
  if (replacement) DCHECK_NULL(tracker_->GetReplacementOf(replacement));
  return replacement;
843 844
}

845 846 847 848
Node* EscapeAnalysisResult::GetVirtualObjectField(const VirtualObject* vobject,
                                                  int field, Node* effect) {
  return tracker_->variable_states_.Get(vobject->FieldAt(field).FromJust(),
                                        effect);
849 850
}

851 852
const VirtualObject* EscapeAnalysisResult::GetVirtualObject(Node* node) {
  return tracker_->virtual_objects_.Get(node);
853 854
}

855 856 857
VirtualObject::VirtualObject(VariableTracker* var_states, VirtualObject::Id id,
                             int size)
    : Dependable(var_states->zone()), id_(id), fields_(var_states->zone()) {
858
  DCHECK(IsAligned(size, kTaggedSize));
859
  TRACE("Creating VirtualObject id:%d size:%d\n", id, size);
860
  int num_fields = size / kTaggedSize;
861 862 863
  fields_.reserve(num_fields);
  for (int i = 0; i < num_fields; ++i) {
    fields_.push_back(var_states->NewVariable());
864 865 866
  }
}

867 868
#undef TRACE

869 870 871
}  // namespace compiler
}  // namespace internal
}  // namespace v8