1 // Copyright 2015 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "src/compiler/escape-analysis.h"
6 
7 #include <limits>
8 
9 #include "src/base/flags.h"
10 #include "src/bootstrapper.h"
11 #include "src/compilation-dependencies.h"
12 #include "src/compiler/common-operator.h"
13 #include "src/compiler/graph-reducer.h"
14 #include "src/compiler/js-operator.h"
15 #include "src/compiler/node.h"
16 #include "src/compiler/node-matchers.h"
17 #include "src/compiler/node-properties.h"
18 #include "src/compiler/operator-properties.h"
19 #include "src/compiler/simplified-operator.h"
20 #include "src/objects-inl.h"
21 #include "src/type-cache.h"
22 
23 namespace v8 {
24 namespace internal {
25 namespace compiler {
26 
27 const EscapeAnalysis::Alias EscapeAnalysis::kNotReachable =
28     std::numeric_limits<Alias>::max();
29 const EscapeAnalysis::Alias EscapeAnalysis::kUntrackable =
30     std::numeric_limits<Alias>::max() - 1;
31 
32 
33 class VirtualObject : public ZoneObject {
34  public:
35   enum Status { kUntracked = 0, kTracked = 1 };
VirtualObject(NodeId id,Zone * zone)36   VirtualObject(NodeId id, Zone* zone)
37       : id_(id),
38         status_(kUntracked),
39         fields_(zone),
40         phi_(zone),
41         object_state_(nullptr) {}
42 
VirtualObject(const VirtualObject & other)43   VirtualObject(const VirtualObject& other)
44       : id_(other.id_),
45         status_(other.status_),
46         fields_(other.fields_),
47         phi_(other.phi_),
48         object_state_(other.object_state_) {}
49 
VirtualObject(NodeId id,Zone * zone,size_t field_number)50   VirtualObject(NodeId id, Zone* zone, size_t field_number)
51       : id_(id),
52         status_(kTracked),
53         fields_(zone),
54         phi_(zone),
55         object_state_(nullptr) {
56     fields_.resize(field_number);
57     phi_.resize(field_number, false);
58   }
59 
GetField(size_t offset)60   Node* GetField(size_t offset) {
61     if (offset < fields_.size()) {
62       return fields_[offset];
63     }
64     return nullptr;
65   }
66 
IsCreatedPhi(size_t offset)67   bool IsCreatedPhi(size_t offset) {
68     if (offset < phi_.size()) {
69       return phi_[offset];
70     }
71     return false;
72   }
73 
SetField(size_t offset,Node * node,bool created_phi=false)74   bool SetField(size_t offset, Node* node, bool created_phi = false) {
75     bool changed = fields_[offset] != node || phi_[offset] != created_phi;
76     fields_[offset] = node;
77     phi_[offset] = created_phi;
78     if (changed && FLAG_trace_turbo_escape && node) {
79       PrintF("Setting field %zu of #%d to #%d (%s)\n", offset, id(), node->id(),
80              node->op()->mnemonic());
81     }
82     return changed;
83   }
IsVirtual() const84   bool IsVirtual() const { return status_ == kTracked; }
IsTracked() const85   bool IsTracked() const { return status_ != kUntracked; }
86 
fields_array()87   Node** fields_array() { return &fields_.front(); }
field_count()88   size_t field_count() { return fields_.size(); }
ResizeFields(size_t field_count)89   bool ResizeFields(size_t field_count) {
90     if (field_count != fields_.size()) {
91       fields_.resize(field_count);
92       phi_.resize(field_count);
93       return true;
94     }
95     return false;
96   }
ClearAllFields()97   bool ClearAllFields() {
98     bool changed = false;
99     for (size_t i = 0; i < fields_.size(); ++i) {
100       if (fields_[i] != nullptr) {
101         fields_[i] = nullptr;
102         changed = true;
103       }
104       phi_[i] = false;
105     }
106     return changed;
107   }
108   bool UpdateFrom(const VirtualObject& other);
SetObjectState(Node * node)109   void SetObjectState(Node* node) { object_state_ = node; }
GetObjectState() const110   Node* GetObjectState() const { return object_state_; }
111 
id() const112   NodeId id() const { return id_; }
id(NodeId id)113   void id(NodeId id) { id_ = id; }
114 
115  private:
116   NodeId id_;
117   Status status_;
118   ZoneVector<Node*> fields_;
119   ZoneVector<bool> phi_;
120   Node* object_state_;
121 };
122 
123 
UpdateFrom(const VirtualObject & other)124 bool VirtualObject::UpdateFrom(const VirtualObject& other) {
125   bool changed = status_ != other.status_;
126   status_ = other.status_;
127   if (fields_.size() != other.fields_.size()) {
128     fields_ = other.fields_;
129     return true;
130   }
131   for (size_t i = 0; i < fields_.size(); ++i) {
132     if (fields_[i] != other.fields_[i]) {
133       changed = true;
134       fields_[i] = other.fields_[i];
135     }
136   }
137   return changed;
138 }
139 
140 
141 class VirtualState : public ZoneObject {
142  public:
143   VirtualState(Zone* zone, size_t size);
144   VirtualState(const VirtualState& states);
145 
146   VirtualObject* VirtualObjectFromAlias(size_t alias);
147   VirtualObject* GetOrCreateTrackedVirtualObject(EscapeAnalysis::Alias alias,
148                                                  NodeId id, Zone* zone);
149   void SetVirtualObject(EscapeAnalysis::Alias alias, VirtualObject* state);
LastChangedAt(Node * node)150   void LastChangedAt(Node* node) { last_changed_ = node; }
GetLastChanged()151   Node* GetLastChanged() { return last_changed_; }
152   bool UpdateFrom(VirtualState* state, Zone* zone);
153   bool MergeFrom(MergeCache* cache, Zone* zone, Graph* graph,
154                  CommonOperatorBuilder* common, Node* control);
size() const155   size_t size() const { return info_.size(); }
156 
157  private:
158   ZoneVector<VirtualObject*> info_;
159   Node* last_changed_;
160 };
161 
162 
163 class MergeCache : public ZoneObject {
164  public:
MergeCache(Zone * zone)165   explicit MergeCache(Zone* zone)
166       : states_(zone), objects_(zone), fields_(zone) {
167     states_.reserve(4);
168     objects_.reserve(4);
169     fields_.reserve(4);
170   }
states()171   ZoneVector<VirtualState*>& states() { return states_; }
objects()172   ZoneVector<VirtualObject*>& objects() { return objects_; }
fields()173   ZoneVector<Node*>& fields() { return fields_; }
Clear()174   void Clear() {
175     states_.clear();
176     objects_.clear();
177     fields_.clear();
178   }
179   size_t LoadVirtualObjectsFromStatesFor(EscapeAnalysis::Alias alias);
180   void LoadVirtualObjectsForFieldsFrom(
181       VirtualState* state, const ZoneVector<EscapeAnalysis::Alias>& aliases);
182   Node* GetFields(size_t pos);
183 
184  private:
185   ZoneVector<VirtualState*> states_;
186   ZoneVector<VirtualObject*> objects_;
187   ZoneVector<Node*> fields_;
188 };
189 
190 
LoadVirtualObjectsFromStatesFor(EscapeAnalysis::Alias alias)191 size_t MergeCache::LoadVirtualObjectsFromStatesFor(
192     EscapeAnalysis::Alias alias) {
193   objects_.clear();
194   DCHECK_GT(states_.size(), 0u);
195   size_t min = std::numeric_limits<size_t>::max();
196   for (VirtualState* state : states_) {
197     if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) {
198       objects_.push_back(obj);
199       min = std::min(obj->field_count(), min);
200     }
201   }
202   return min;
203 }
204 
205 
LoadVirtualObjectsForFieldsFrom(VirtualState * state,const ZoneVector<EscapeAnalysis::Alias> & aliases)206 void MergeCache::LoadVirtualObjectsForFieldsFrom(
207     VirtualState* state, const ZoneVector<EscapeAnalysis::Alias>& aliases) {
208   objects_.clear();
209   size_t max_alias = state->size();
210   for (Node* field : fields_) {
211     EscapeAnalysis::Alias alias = aliases[field->id()];
212     if (alias >= max_alias) continue;
213     if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) {
214       objects_.push_back(obj);
215     }
216   }
217 }
218 
219 
GetFields(size_t pos)220 Node* MergeCache::GetFields(size_t pos) {
221   fields_.clear();
222   Node* rep = objects_.front()->GetField(pos);
223   for (VirtualObject* obj : objects_) {
224     Node* field = obj->GetField(pos);
225     if (field) {
226       fields_.push_back(field);
227     }
228     if (field != rep) {
229       rep = nullptr;
230     }
231   }
232   return rep;
233 }
234 
235 
VirtualState(Zone * zone,size_t size)236 VirtualState::VirtualState(Zone* zone, size_t size)
237     : info_(size, nullptr, zone), last_changed_(nullptr) {}
238 
239 
VirtualState(const VirtualState & state)240 VirtualState::VirtualState(const VirtualState& state)
241     : info_(state.info_.size(), nullptr, state.info_.get_allocator().zone()),
242       last_changed_(state.last_changed_) {
243   for (size_t i = 0; i < state.info_.size(); ++i) {
244     if (state.info_[i]) {
245       info_[i] =
246           new (info_.get_allocator().zone()) VirtualObject(*state.info_[i]);
247     }
248   }
249 }
250 
251 
VirtualObjectFromAlias(size_t alias)252 VirtualObject* VirtualState::VirtualObjectFromAlias(size_t alias) {
253   return info_[alias];
254 }
255 
256 
GetOrCreateTrackedVirtualObject(EscapeAnalysis::Alias alias,NodeId id,Zone * zone)257 VirtualObject* VirtualState::GetOrCreateTrackedVirtualObject(
258     EscapeAnalysis::Alias alias, NodeId id, Zone* zone) {
259   if (VirtualObject* obj = VirtualObjectFromAlias(alias)) {
260     return obj;
261   }
262   VirtualObject* obj = new (zone) VirtualObject(id, zone, 0);
263   SetVirtualObject(alias, obj);
264   return obj;
265 }
266 
267 
SetVirtualObject(EscapeAnalysis::Alias alias,VirtualObject * obj)268 void VirtualState::SetVirtualObject(EscapeAnalysis::Alias alias,
269                                     VirtualObject* obj) {
270   info_[alias] = obj;
271 }
272 
273 
UpdateFrom(VirtualState * from,Zone * zone)274 bool VirtualState::UpdateFrom(VirtualState* from, Zone* zone) {
275   bool changed = false;
276   for (EscapeAnalysis::Alias alias = 0; alias < size(); ++alias) {
277     VirtualObject* ls = VirtualObjectFromAlias(alias);
278     VirtualObject* rs = from->VirtualObjectFromAlias(alias);
279 
280     if (rs == nullptr) {
281       continue;
282     }
283 
284     if (ls == nullptr) {
285       ls = new (zone) VirtualObject(*rs);
286       SetVirtualObject(alias, ls);
287       changed = true;
288       continue;
289     }
290 
291     if (FLAG_trace_turbo_escape) {
292       PrintF("  Updating fields of @%d\n", alias);
293     }
294 
295     changed = ls->UpdateFrom(*rs) || changed;
296   }
297   return false;
298 }
299 
300 
301 namespace {
302 
IsEquivalentPhi(Node * node1,Node * node2)303 bool IsEquivalentPhi(Node* node1, Node* node2) {
304   if (node1 == node2) return true;
305   if (node1->opcode() != IrOpcode::kPhi || node2->opcode() != IrOpcode::kPhi ||
306       node1->op()->ValueInputCount() != node2->op()->ValueInputCount()) {
307     return false;
308   }
309   for (int i = 0; i < node1->op()->ValueInputCount(); ++i) {
310     Node* input1 = NodeProperties::GetValueInput(node1, i);
311     Node* input2 = NodeProperties::GetValueInput(node2, i);
312     if (!IsEquivalentPhi(input1, input2)) {
313       return false;
314     }
315   }
316   return true;
317 }
318 
319 
IsEquivalentPhi(Node * phi,ZoneVector<Node * > & inputs)320 bool IsEquivalentPhi(Node* phi, ZoneVector<Node*>& inputs) {
321   if (phi->opcode() != IrOpcode::kPhi) return false;
322   if (phi->op()->ValueInputCount() != inputs.size()) {
323     return false;
324   }
325   for (size_t i = 0; i < inputs.size(); ++i) {
326     Node* input = NodeProperties::GetValueInput(phi, static_cast<int>(i));
327     if (!IsEquivalentPhi(input, inputs[i])) {
328       return false;
329     }
330   }
331   return true;
332 }
333 
334 }  // namespace
335 
336 
GetReplacementIfSame(ZoneVector<VirtualObject * > & objs)337 Node* EscapeAnalysis::GetReplacementIfSame(ZoneVector<VirtualObject*>& objs) {
338   Node* rep = GetReplacement(objs.front()->id());
339   for (VirtualObject* obj : objs) {
340     if (GetReplacement(obj->id()) != rep) {
341       return nullptr;
342     }
343   }
344   return rep;
345 }
346 
347 
MergeFrom(MergeCache * cache,Zone * zone,Graph * graph,CommonOperatorBuilder * common,Node * control)348 bool VirtualState::MergeFrom(MergeCache* cache, Zone* zone, Graph* graph,
349                              CommonOperatorBuilder* common, Node* control) {
350   DCHECK_GT(cache->states().size(), 0u);
351   bool changed = false;
352   for (EscapeAnalysis::Alias alias = 0; alias < size(); ++alias) {
353     size_t fields = cache->LoadVirtualObjectsFromStatesFor(alias);
354     if (cache->objects().size() == cache->states().size()) {
355       if (FLAG_trace_turbo_escape) {
356         PrintF("  Merging virtual objects of @%d\n", alias);
357       }
358       VirtualObject* mergeObject = GetOrCreateTrackedVirtualObject(
359           alias, cache->objects().front()->id(), zone);
360       changed = mergeObject->ResizeFields(fields) || changed;
361       for (size_t i = 0; i < fields; ++i) {
362         if (Node* field = cache->GetFields(i)) {
363           changed = mergeObject->SetField(i, field) || changed;
364           if (FLAG_trace_turbo_escape) {
365             PrintF("    Field %zu agree on rep #%d\n", i, field->id());
366           }
367         } else {
368           int value_input_count = static_cast<int>(cache->fields().size());
369           if (cache->fields().size() == cache->objects().size()) {
370             Node* rep = mergeObject->GetField(i);
371             if (!rep || !mergeObject->IsCreatedPhi(i)) {
372               cache->fields().push_back(control);
373               Node* phi = graph->NewNode(
374                   common->Phi(MachineRepresentation::kTagged,
375                               value_input_count),
376                   value_input_count + 1, &cache->fields().front());
377               mergeObject->SetField(i, phi, true);
378               if (FLAG_trace_turbo_escape) {
379                 PrintF("    Creating Phi #%d as merge of", phi->id());
380                 for (int i = 0; i < value_input_count; i++) {
381                   PrintF(" #%d (%s)", cache->fields()[i]->id(),
382                          cache->fields()[i]->op()->mnemonic());
383                 }
384                 PrintF("\n");
385               }
386               changed = true;
387             } else {
388               DCHECK(rep->opcode() == IrOpcode::kPhi);
389               for (int n = 0; n < value_input_count; ++n) {
390                 if (n < rep->op()->ValueInputCount()) {
391                   Node* old = NodeProperties::GetValueInput(rep, n);
392                   if (old != cache->fields()[n]) {
393                     changed = true;
394                     NodeProperties::ReplaceValueInput(rep, cache->fields()[n],
395                                                       n);
396                   }
397                 } else {
398                   changed = true;
399                   rep->InsertInput(graph->zone(), n, cache->fields()[n]);
400                 }
401               }
402               if (rep->op()->ValueInputCount() != value_input_count) {
403                 if (FLAG_trace_turbo_escape) {
404                   PrintF("    Widening Phi #%d of arity %d to %d", rep->id(),
405                          rep->op()->ValueInputCount(), value_input_count);
406                 }
407                 NodeProperties::ChangeOp(
408                     rep, common->Phi(MachineRepresentation::kTagged,
409                                      value_input_count));
410               }
411             }
412           } else {
413             changed = mergeObject->SetField(i, nullptr) || changed;
414           }
415         }
416       }
417     } else {
418       SetVirtualObject(alias, nullptr);
419     }
420   }
421   return changed;
422 }
423 
424 
EscapeStatusAnalysis(EscapeAnalysis * object_analysis,Graph * graph,Zone * zone)425 EscapeStatusAnalysis::EscapeStatusAnalysis(EscapeAnalysis* object_analysis,
426                                            Graph* graph, Zone* zone)
427     : object_analysis_(object_analysis),
428       graph_(graph),
429       zone_(zone),
430       status_(graph->NodeCount(), kUnknown, zone),
431       queue_(zone) {}
432 
433 
~EscapeStatusAnalysis()434 EscapeStatusAnalysis::~EscapeStatusAnalysis() {}
435 
436 
HasEntry(Node * node)437 bool EscapeStatusAnalysis::HasEntry(Node* node) {
438   return status_[node->id()] & (kTracked | kEscaped);
439 }
440 
441 
IsVirtual(Node * node)442 bool EscapeStatusAnalysis::IsVirtual(Node* node) {
443   return (status_[node->id()] & kTracked) && !(status_[node->id()] & kEscaped);
444 }
445 
446 
IsEscaped(Node * node)447 bool EscapeStatusAnalysis::IsEscaped(Node* node) {
448   return status_[node->id()] & kEscaped;
449 }
450 
451 
IsAllocation(Node * node)452 bool EscapeStatusAnalysis::IsAllocation(Node* node) {
453   return node->opcode() == IrOpcode::kAllocate ||
454          node->opcode() == IrOpcode::kFinishRegion;
455 }
456 
457 
SetEscaped(Node * node)458 bool EscapeStatusAnalysis::SetEscaped(Node* node) {
459   bool changed = !(status_[node->id()] & kEscaped);
460   status_[node->id()] |= kEscaped | kTracked;
461   return changed;
462 }
463 
464 
Resize()465 void EscapeStatusAnalysis::Resize() {
466   status_.resize(graph()->NodeCount(), kUnknown);
467 }
468 
469 
size()470 size_t EscapeStatusAnalysis::size() { return status_.size(); }
471 
472 
Run()473 void EscapeStatusAnalysis::Run() {
474   Resize();
475   queue_.push_back(graph()->end());
476   status_[graph()->end()->id()] |= kOnStack;
477   while (!queue_.empty()) {
478     Node* node = queue_.front();
479     queue_.pop_front();
480     status_[node->id()] &= ~kOnStack;
481     Process(node);
482     status_[node->id()] |= kVisited;
483     for (Edge edge : node->input_edges()) {
484       Node* input = edge.to();
485       if (!(status_[input->id()] & (kVisited | kOnStack))) {
486         queue_.push_back(input);
487         status_[input->id()] |= kOnStack;
488       }
489     }
490   }
491 }
492 
493 
RevisitInputs(Node * node)494 void EscapeStatusAnalysis::RevisitInputs(Node* node) {
495   for (Edge edge : node->input_edges()) {
496     Node* input = edge.to();
497     if (!(status_[input->id()] & kOnStack)) {
498       queue_.push_back(input);
499       status_[input->id()] |= kOnStack;
500     }
501   }
502 }
503 
504 
RevisitUses(Node * node)505 void EscapeStatusAnalysis::RevisitUses(Node* node) {
506   for (Edge edge : node->use_edges()) {
507     Node* use = edge.from();
508     if (!(status_[use->id()] & kOnStack)) {
509       queue_.push_back(use);
510       status_[use->id()] |= kOnStack;
511     }
512   }
513 }
514 
515 
Process(Node * node)516 void EscapeStatusAnalysis::Process(Node* node) {
517   switch (node->opcode()) {
518     case IrOpcode::kAllocate:
519       ProcessAllocate(node);
520       break;
521     case IrOpcode::kFinishRegion:
522       ProcessFinishRegion(node);
523       break;
524     case IrOpcode::kStoreField:
525       ProcessStoreField(node);
526       break;
527     case IrOpcode::kStoreElement:
528       ProcessStoreElement(node);
529       break;
530     case IrOpcode::kLoadField:
531     case IrOpcode::kLoadElement: {
532       if (Node* rep = object_analysis_->GetReplacement(node)) {
533         if (IsAllocation(rep) && CheckUsesForEscape(node, rep)) {
534           RevisitInputs(rep);
535           RevisitUses(rep);
536         }
537       }
538       break;
539     }
540     case IrOpcode::kPhi:
541       if (!HasEntry(node)) {
542         status_[node->id()] |= kTracked;
543         if (!IsAllocationPhi(node)) {
544           SetEscaped(node);
545           RevisitUses(node);
546         }
547       }
548       CheckUsesForEscape(node);
549     default:
550       break;
551   }
552 }
553 
554 
IsAllocationPhi(Node * node)555 bool EscapeStatusAnalysis::IsAllocationPhi(Node* node) {
556   for (Edge edge : node->input_edges()) {
557     Node* input = edge.to();
558     if (input->opcode() == IrOpcode::kPhi && !IsEscaped(input)) continue;
559     if (IsAllocation(input)) continue;
560     return false;
561   }
562   return true;
563 }
564 
565 
ProcessStoreField(Node * node)566 void EscapeStatusAnalysis::ProcessStoreField(Node* node) {
567   DCHECK_EQ(node->opcode(), IrOpcode::kStoreField);
568   Node* to = NodeProperties::GetValueInput(node, 0);
569   Node* val = NodeProperties::GetValueInput(node, 1);
570   if ((IsEscaped(to) || !IsAllocation(to)) && SetEscaped(val)) {
571     RevisitUses(val);
572     RevisitInputs(val);
573     if (FLAG_trace_turbo_escape) {
574       PrintF("Setting #%d (%s) to escaped because of store to field of #%d\n",
575              val->id(), val->op()->mnemonic(), to->id());
576     }
577   }
578 }
579 
580 
ProcessStoreElement(Node * node)581 void EscapeStatusAnalysis::ProcessStoreElement(Node* node) {
582   DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement);
583   Node* to = NodeProperties::GetValueInput(node, 0);
584   Node* val = NodeProperties::GetValueInput(node, 2);
585   if ((IsEscaped(to) || !IsAllocation(to)) && SetEscaped(val)) {
586     RevisitUses(val);
587     RevisitInputs(val);
588     if (FLAG_trace_turbo_escape) {
589       PrintF("Setting #%d (%s) to escaped because of store to field of #%d\n",
590              val->id(), val->op()->mnemonic(), to->id());
591     }
592   }
593 }
594 
595 
ProcessAllocate(Node * node)596 void EscapeStatusAnalysis::ProcessAllocate(Node* node) {
597   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
598   if (!HasEntry(node)) {
599     status_[node->id()] |= kTracked;
600     if (FLAG_trace_turbo_escape) {
601       PrintF("Created status entry for node #%d (%s)\n", node->id(),
602              node->op()->mnemonic());
603     }
604     NumberMatcher size(node->InputAt(0));
605     DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant &&
606            node->InputAt(0)->opcode() != IrOpcode::kInt64Constant &&
607            node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant &&
608            node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant);
609     if (!size.HasValue() && SetEscaped(node)) {
610       RevisitUses(node);
611       if (FLAG_trace_turbo_escape) {
612         PrintF("Setting #%d to escaped because of non-const alloc\n",
613                node->id());
614       }
615       // This node is known to escape, uses do not have to be checked.
616       return;
617     }
618   }
619   if (CheckUsesForEscape(node, true)) {
620     RevisitUses(node);
621   }
622 }
623 
624 
CheckUsesForEscape(Node * uses,Node * rep,bool phi_escaping)625 bool EscapeStatusAnalysis::CheckUsesForEscape(Node* uses, Node* rep,
626                                               bool phi_escaping) {
627   for (Edge edge : uses->use_edges()) {
628     Node* use = edge.from();
629     if (edge.index() >= use->op()->ValueInputCount() +
630                             OperatorProperties::GetContextInputCount(use->op()))
631       continue;
632     switch (use->opcode()) {
633       case IrOpcode::kPhi:
634         if (phi_escaping && SetEscaped(rep)) {
635           if (FLAG_trace_turbo_escape) {
636             PrintF(
637                 "Setting #%d (%s) to escaped because of use by phi node "
638                 "#%d (%s)\n",
639                 rep->id(), rep->op()->mnemonic(), use->id(),
640                 use->op()->mnemonic());
641           }
642           return true;
643         }
644       // Fallthrough.
645       case IrOpcode::kStoreField:
646       case IrOpcode::kLoadField:
647       case IrOpcode::kStoreElement:
648       case IrOpcode::kLoadElement:
649       case IrOpcode::kFrameState:
650       case IrOpcode::kStateValues:
651       case IrOpcode::kReferenceEqual:
652       case IrOpcode::kFinishRegion:
653         if (IsEscaped(use) && SetEscaped(rep)) {
654           if (FLAG_trace_turbo_escape) {
655             PrintF(
656                 "Setting #%d (%s) to escaped because of use by escaping node "
657                 "#%d (%s)\n",
658                 rep->id(), rep->op()->mnemonic(), use->id(),
659                 use->op()->mnemonic());
660           }
661           return true;
662         }
663         break;
664       case IrOpcode::kObjectIsSmi:
665         if (!IsAllocation(rep) && SetEscaped(rep)) {
666           PrintF("Setting #%d (%s) to escaped because of use by #%d (%s)\n",
667                  rep->id(), rep->op()->mnemonic(), use->id(),
668                  use->op()->mnemonic());
669           return true;
670         }
671         break;
672       default:
673         if (use->op()->EffectInputCount() == 0 &&
674             uses->op()->EffectInputCount() > 0) {
675           PrintF("Encountered unaccounted use by #%d (%s)\n", use->id(),
676                  use->op()->mnemonic());
677           UNREACHABLE();
678         }
679         if (SetEscaped(rep)) {
680           if (FLAG_trace_turbo_escape) {
681             PrintF("Setting #%d (%s) to escaped because of use by #%d (%s)\n",
682                    rep->id(), rep->op()->mnemonic(), use->id(),
683                    use->op()->mnemonic());
684           }
685           return true;
686         }
687     }
688   }
689   return false;
690 }
691 
692 
ProcessFinishRegion(Node * node)693 void EscapeStatusAnalysis::ProcessFinishRegion(Node* node) {
694   DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
695   if (!HasEntry(node)) {
696     status_[node->id()] |= kTracked;
697     RevisitUses(node);
698   }
699   if (CheckUsesForEscape(node, true)) {
700     RevisitInputs(node);
701   }
702 }
703 
704 
DebugPrint()705 void EscapeStatusAnalysis::DebugPrint() {
706   for (NodeId id = 0; id < status_.size(); id++) {
707     if (status_[id] & kTracked) {
708       PrintF("Node #%d is %s\n", id,
709              (status_[id] & kEscaped) ? "escaping" : "virtual");
710     }
711   }
712 }
713 
714 
EscapeAnalysis(Graph * graph,CommonOperatorBuilder * common,Zone * zone)715 EscapeAnalysis::EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common,
716                                Zone* zone)
717     : graph_(graph),
718       common_(common),
719       zone_(zone),
720       virtual_states_(zone),
721       replacements_(zone),
722       escape_status_(this, graph, zone),
723       cache_(new (zone) MergeCache(zone)),
724       aliases_(zone),
725       next_free_alias_(0) {}
726 
727 
~EscapeAnalysis()728 EscapeAnalysis::~EscapeAnalysis() {}
729 
730 
Run()731 void EscapeAnalysis::Run() {
732   replacements_.resize(graph()->NodeCount());
733   AssignAliases();
734   RunObjectAnalysis();
735   escape_status_.Run();
736 }
737 
738 
AssignAliases()739 void EscapeAnalysis::AssignAliases() {
740   ZoneVector<Node*> stack(zone());
741   stack.push_back(graph()->end());
742   CHECK_LT(graph()->NodeCount(), kUntrackable);
743   aliases_.resize(graph()->NodeCount(), kNotReachable);
744   aliases_[graph()->end()->id()] = kUntrackable;
745   while (!stack.empty()) {
746     Node* node = stack.back();
747     stack.pop_back();
748     switch (node->opcode()) {
749       case IrOpcode::kAllocate:
750         if (aliases_[node->id()] >= kUntrackable) {
751           aliases_[node->id()] = NextAlias();
752         }
753         break;
754       case IrOpcode::kFinishRegion: {
755         Node* allocate = NodeProperties::GetValueInput(node, 0);
756         if (allocate->opcode() == IrOpcode::kAllocate) {
757           if (aliases_[allocate->id()] >= kUntrackable) {
758             if (aliases_[allocate->id()] == kNotReachable) {
759               stack.push_back(allocate);
760             }
761             aliases_[allocate->id()] = NextAlias();
762           }
763           aliases_[node->id()] = aliases_[allocate->id()];
764         } else {
765           aliases_[node->id()] = NextAlias();
766         }
767         break;
768       }
769       default:
770         DCHECK_EQ(aliases_[node->id()], kUntrackable);
771         break;
772     }
773     for (Edge edge : node->input_edges()) {
774       Node* input = edge.to();
775       if (aliases_[input->id()] == kNotReachable) {
776         stack.push_back(input);
777         aliases_[input->id()] = kUntrackable;
778       }
779     }
780   }
781 
782   if (FLAG_trace_turbo_escape) {
783     PrintF("Discovered trackable nodes");
784     for (EscapeAnalysis::Alias id = 0; id < graph()->NodeCount(); ++id) {
785       if (aliases_[id] < kUntrackable) {
786         if (FLAG_trace_turbo_escape) {
787           PrintF(" #%u", id);
788         }
789       }
790     }
791     PrintF("\n");
792   }
793 }
794 
795 
RunObjectAnalysis()796 void EscapeAnalysis::RunObjectAnalysis() {
797   virtual_states_.resize(graph()->NodeCount());
798   ZoneVector<Node*> stack(zone());
799   stack.push_back(graph()->start());
800   while (!stack.empty()) {
801     Node* node = stack.back();
802     stack.pop_back();
803     if (aliases_[node->id()] != kNotReachable && Process(node)) {
804       for (Edge edge : node->use_edges()) {
805         if (NodeProperties::IsEffectEdge(edge)) {
806           Node* use = edge.from();
807           if ((use->opcode() != IrOpcode::kLoadField &&
808                use->opcode() != IrOpcode::kLoadElement) ||
809               !IsDanglingEffectNode(use)) {
810             stack.push_back(use);
811           }
812         }
813       }
814       // First process loads: dangling loads are a problem otherwise.
815       for (Edge edge : node->use_edges()) {
816         if (NodeProperties::IsEffectEdge(edge)) {
817           Node* use = edge.from();
818           if ((use->opcode() == IrOpcode::kLoadField ||
819                use->opcode() == IrOpcode::kLoadElement) &&
820               IsDanglingEffectNode(use)) {
821             stack.push_back(use);
822           }
823         }
824       }
825     }
826   }
827   if (FLAG_trace_turbo_escape) {
828     DebugPrint();
829   }
830 }
831 
832 
IsDanglingEffectNode(Node * node)833 bool EscapeAnalysis::IsDanglingEffectNode(Node* node) {
834   if (node->op()->EffectInputCount() == 0) return false;
835   if (node->op()->EffectOutputCount() == 0) return false;
836   if (node->op()->EffectInputCount() == 1 &&
837       NodeProperties::GetEffectInput(node)->opcode() == IrOpcode::kStart) {
838     // The start node is used as sentinel for nodes that are in general
839     // effectful, but of which an analysis has determined that they do not
840     // produce effects in this instance. We don't consider these nodes dangling.
841     return false;
842   }
843   for (Edge edge : node->use_edges()) {
844     if (NodeProperties::IsEffectEdge(edge)) {
845       return false;
846     }
847   }
848   return true;
849 }
850 
851 
Process(Node * node)852 bool EscapeAnalysis::Process(Node* node) {
853   switch (node->opcode()) {
854     case IrOpcode::kAllocate:
855       ProcessAllocation(node);
856       break;
857     case IrOpcode::kBeginRegion:
858       ForwardVirtualState(node);
859       break;
860     case IrOpcode::kFinishRegion:
861       ProcessFinishRegion(node);
862       break;
863     case IrOpcode::kStoreField:
864       ProcessStoreField(node);
865       break;
866     case IrOpcode::kLoadField:
867       ProcessLoadField(node);
868       break;
869     case IrOpcode::kStoreElement:
870       ProcessStoreElement(node);
871       break;
872     case IrOpcode::kLoadElement:
873       ProcessLoadElement(node);
874       break;
875     case IrOpcode::kStart:
876       ProcessStart(node);
877       break;
878     case IrOpcode::kEffectPhi:
879       return ProcessEffectPhi(node);
880       break;
881     default:
882       if (node->op()->EffectInputCount() > 0) {
883         ForwardVirtualState(node);
884       }
885       ProcessAllocationUsers(node);
886       break;
887   }
888   return true;
889 }
890 
891 
ProcessAllocationUsers(Node * node)892 void EscapeAnalysis::ProcessAllocationUsers(Node* node) {
893   for (Edge edge : node->input_edges()) {
894     Node* input = edge.to();
895     if (!NodeProperties::IsValueEdge(edge) &&
896         !NodeProperties::IsContextEdge(edge))
897       continue;
898     switch (node->opcode()) {
899       case IrOpcode::kStoreField:
900       case IrOpcode::kLoadField:
901       case IrOpcode::kStoreElement:
902       case IrOpcode::kLoadElement:
903       case IrOpcode::kFrameState:
904       case IrOpcode::kStateValues:
905       case IrOpcode::kReferenceEqual:
906       case IrOpcode::kFinishRegion:
907       case IrOpcode::kPhi:
908         break;
909       default:
910         VirtualState* state = virtual_states_[node->id()];
911         if (VirtualObject* obj = ResolveVirtualObject(state, input)) {
912           if (obj->ClearAllFields()) {
913             state->LastChangedAt(node);
914           }
915         }
916         break;
917     }
918   }
919 }
920 
921 
IsEffectBranchPoint(Node * node)922 bool EscapeAnalysis::IsEffectBranchPoint(Node* node) {
923   int count = 0;
924   for (Edge edge : node->use_edges()) {
925     if (NodeProperties::IsEffectEdge(edge)) {
926       if (++count > 1) {
927         return true;
928       }
929     }
930   }
931   return false;
932 }
933 
934 
ForwardVirtualState(Node * node)935 void EscapeAnalysis::ForwardVirtualState(Node* node) {
936   DCHECK_EQ(node->op()->EffectInputCount(), 1);
937   if (node->opcode() != IrOpcode::kLoadField &&
938       node->opcode() != IrOpcode::kLoadElement &&
939       node->opcode() != IrOpcode::kLoad && IsDanglingEffectNode(node)) {
940     PrintF("Dangeling effect node: #%d (%s)\n", node->id(),
941            node->op()->mnemonic());
942     UNREACHABLE();
943   }
944   Node* effect = NodeProperties::GetEffectInput(node);
945   // Break the cycle for effect phis.
946   if (effect->opcode() == IrOpcode::kEffectPhi) {
947     if (virtual_states_[effect->id()] == nullptr) {
948       virtual_states_[effect->id()] =
949           new (zone()) VirtualState(zone(), AliasCount());
950     }
951   }
952   DCHECK_NOT_NULL(virtual_states_[effect->id()]);
953   if (IsEffectBranchPoint(effect)) {
954     if (FLAG_trace_turbo_escape) {
955       PrintF("Copying object state %p from #%d (%s) to #%d (%s)\n",
956              static_cast<void*>(virtual_states_[effect->id()]), effect->id(),
957              effect->op()->mnemonic(), node->id(), node->op()->mnemonic());
958     }
959     if (!virtual_states_[node->id()]) {
960       virtual_states_[node->id()] =
961           new (zone()) VirtualState(*virtual_states_[effect->id()]);
962     } else {
963       virtual_states_[node->id()]->UpdateFrom(virtual_states_[effect->id()],
964                                               zone());
965     }
966   } else {
967     virtual_states_[node->id()] = virtual_states_[effect->id()];
968     if (FLAG_trace_turbo_escape) {
969       PrintF("Forwarding object state %p from #%d (%s) to #%d (%s)\n",
970              static_cast<void*>(virtual_states_[effect->id()]), effect->id(),
971              effect->op()->mnemonic(), node->id(), node->op()->mnemonic());
972     }
973   }
974 }
975 
976 
ProcessStart(Node * node)977 void EscapeAnalysis::ProcessStart(Node* node) {
978   DCHECK_EQ(node->opcode(), IrOpcode::kStart);
979   virtual_states_[node->id()] = new (zone()) VirtualState(zone(), AliasCount());
980 }
981 
982 
ProcessEffectPhi(Node * node)983 bool EscapeAnalysis::ProcessEffectPhi(Node* node) {
984   DCHECK_EQ(node->opcode(), IrOpcode::kEffectPhi);
985   bool changed = false;
986 
987   VirtualState* mergeState = virtual_states_[node->id()];
988   if (!mergeState) {
989     mergeState = new (zone()) VirtualState(zone(), AliasCount());
990     virtual_states_[node->id()] = mergeState;
991     changed = true;
992     if (FLAG_trace_turbo_escape) {
993       PrintF("Effect Phi #%d got new states map %p.\n", node->id(),
994              static_cast<void*>(mergeState));
995     }
996   } else if (mergeState->GetLastChanged() != node) {
997     changed = true;
998   }
999 
1000   cache_->Clear();
1001 
1002   if (FLAG_trace_turbo_escape) {
1003     PrintF("At Effect Phi #%d, merging states into %p:", node->id(),
1004            static_cast<void*>(mergeState));
1005   }
1006 
1007   for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
1008     Node* input = NodeProperties::GetEffectInput(node, i);
1009     VirtualState* state = virtual_states_[input->id()];
1010     if (state) {
1011       cache_->states().push_back(state);
1012     }
1013     if (FLAG_trace_turbo_escape) {
1014       PrintF(" %p (from %d %s)", static_cast<void*>(state), input->id(),
1015              input->op()->mnemonic());
1016     }
1017   }
1018   if (FLAG_trace_turbo_escape) {
1019     PrintF("\n");
1020   }
1021 
1022   if (cache_->states().size() == 0) {
1023     return changed;
1024   }
1025 
1026   changed = mergeState->MergeFrom(cache_, zone(), graph(), common(),
1027                                   NodeProperties::GetControlInput(node)) ||
1028             changed;
1029 
1030   if (FLAG_trace_turbo_escape) {
1031     PrintF("Merge %s the node.\n", changed ? "changed" : "did not change");
1032   }
1033 
1034   if (changed) {
1035     mergeState->LastChangedAt(node);
1036     escape_status_.Resize();
1037   }
1038   return changed;
1039 }
1040 
1041 
ProcessAllocation(Node * node)1042 void EscapeAnalysis::ProcessAllocation(Node* node) {
1043   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
1044   ForwardVirtualState(node);
1045 
1046   // Check if we have already processed this node.
1047   if (virtual_states_[node->id()]->VirtualObjectFromAlias(
1048           aliases_[node->id()])) {
1049     return;
1050   }
1051 
1052   NumberMatcher size(node->InputAt(0));
1053   DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant &&
1054          node->InputAt(0)->opcode() != IrOpcode::kInt64Constant &&
1055          node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant &&
1056          node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant);
1057   if (size.HasValue()) {
1058     virtual_states_[node->id()]->SetVirtualObject(
1059         aliases_[node->id()],
1060         new (zone())
1061             VirtualObject(node->id(), zone(), size.Value() / kPointerSize));
1062   } else {
1063     virtual_states_[node->id()]->SetVirtualObject(
1064         aliases_[node->id()], new (zone()) VirtualObject(node->id(), zone()));
1065   }
1066   virtual_states_[node->id()]->LastChangedAt(node);
1067 }
1068 
1069 
ProcessFinishRegion(Node * node)1070 void EscapeAnalysis::ProcessFinishRegion(Node* node) {
1071   DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
1072   ForwardVirtualState(node);
1073   Node* allocation = NodeProperties::GetValueInput(node, 0);
1074   if (allocation->opcode() == IrOpcode::kAllocate) {
1075     VirtualState* state = virtual_states_[node->id()];
1076     if (!state->VirtualObjectFromAlias(aliases_[node->id()])) {
1077       VirtualObject* vobj_alloc =
1078           state->VirtualObjectFromAlias(aliases_[allocation->id()]);
1079       DCHECK_NOT_NULL(vobj_alloc);
1080       state->SetVirtualObject(aliases_[node->id()], vobj_alloc);
1081       if (FLAG_trace_turbo_escape) {
1082         PrintF("Linked finish region node #%d to node #%d\n", node->id(),
1083                allocation->id());
1084       }
1085       state->LastChangedAt(node);
1086     }
1087   }
1088 }
1089 
1090 
replacement(NodeId id)1091 Node* EscapeAnalysis::replacement(NodeId id) {
1092   if (id >= replacements_.size()) return nullptr;
1093   return replacements_[id];
1094 }
1095 
1096 
replacement(Node * node)1097 Node* EscapeAnalysis::replacement(Node* node) {
1098   return replacement(node->id());
1099 }
1100 
1101 
SetReplacement(Node * node,Node * rep)1102 bool EscapeAnalysis::SetReplacement(Node* node, Node* rep) {
1103   bool changed = replacements_[node->id()] != rep;
1104   replacements_[node->id()] = rep;
1105   return changed;
1106 }
1107 
1108 
UpdateReplacement(VirtualState * state,Node * node,Node * rep)1109 bool EscapeAnalysis::UpdateReplacement(VirtualState* state, Node* node,
1110                                        Node* rep) {
1111   if (SetReplacement(node, rep)) {
1112     state->LastChangedAt(node);
1113     if (FLAG_trace_turbo_escape) {
1114       if (rep) {
1115         PrintF("Replacement of #%d is #%d (%s)\n", node->id(), rep->id(),
1116                rep->op()->mnemonic());
1117       } else {
1118         PrintF("Replacement of #%d cleared\n", node->id());
1119       }
1120     }
1121     return true;
1122   }
1123   return false;
1124 }
1125 
1126 
ResolveReplacement(Node * node)1127 Node* EscapeAnalysis::ResolveReplacement(Node* node) {
1128   while (replacement(node)) {
1129     node = replacement(node);
1130   }
1131   return node;
1132 }
1133 
1134 
GetReplacement(Node * node)1135 Node* EscapeAnalysis::GetReplacement(Node* node) {
1136   return GetReplacement(node->id());
1137 }
1138 
1139 
GetReplacement(NodeId id)1140 Node* EscapeAnalysis::GetReplacement(NodeId id) {
1141   Node* node = nullptr;
1142   while (replacement(id)) {
1143     node = replacement(id);
1144     id = node->id();
1145   }
1146   return node;
1147 }
1148 
1149 
IsVirtual(Node * node)1150 bool EscapeAnalysis::IsVirtual(Node* node) {
1151   if (node->id() >= escape_status_.size()) {
1152     return false;
1153   }
1154   return escape_status_.IsVirtual(node);
1155 }
1156 
1157 
IsEscaped(Node * node)1158 bool EscapeAnalysis::IsEscaped(Node* node) {
1159   if (node->id() >= escape_status_.size()) {
1160     return false;
1161   }
1162   return escape_status_.IsEscaped(node);
1163 }
1164 
1165 
SetEscaped(Node * node)1166 bool EscapeAnalysis::SetEscaped(Node* node) {
1167   return escape_status_.SetEscaped(node);
1168 }
1169 
1170 
GetVirtualObject(Node * at,NodeId id)1171 VirtualObject* EscapeAnalysis::GetVirtualObject(Node* at, NodeId id) {
1172   if (VirtualState* states = virtual_states_[at->id()]) {
1173     return states->VirtualObjectFromAlias(aliases_[id]);
1174   }
1175   return nullptr;
1176 }
1177 
1178 
ResolveVirtualObject(VirtualState * state,Node * node)1179 VirtualObject* EscapeAnalysis::ResolveVirtualObject(VirtualState* state,
1180                                                     Node* node) {
1181   VirtualObject* obj = GetVirtualObject(state, ResolveReplacement(node));
1182   while (obj && replacement(obj->id())) {
1183     if (VirtualObject* next = GetVirtualObject(state, replacement(obj->id()))) {
1184       obj = next;
1185     } else {
1186       break;
1187     }
1188   }
1189   return obj;
1190 }
1191 
1192 
CompareVirtualObjects(Node * left,Node * right)1193 bool EscapeAnalysis::CompareVirtualObjects(Node* left, Node* right) {
1194   DCHECK(IsVirtual(left) && IsVirtual(right));
1195   left = ResolveReplacement(left);
1196   right = ResolveReplacement(right);
1197   if (IsEquivalentPhi(left, right)) {
1198     return true;
1199   }
1200   return false;
1201 }
1202 
1203 
OffsetFromAccess(Node * node)1204 int EscapeAnalysis::OffsetFromAccess(Node* node) {
1205   DCHECK(OpParameter<FieldAccess>(node).offset % kPointerSize == 0);
1206   return OpParameter<FieldAccess>(node).offset / kPointerSize;
1207 }
1208 
1209 
ProcessLoadFromPhi(int offset,Node * from,Node * node,VirtualState * state)1210 void EscapeAnalysis::ProcessLoadFromPhi(int offset, Node* from, Node* node,
1211                                         VirtualState* state) {
1212   if (FLAG_trace_turbo_escape) {
1213     PrintF("Load #%d from phi #%d", node->id(), from->id());
1214   }
1215 
1216   cache_->fields().clear();
1217   for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
1218     Node* input = NodeProperties::GetValueInput(node, i);
1219     cache_->fields().push_back(input);
1220   }
1221 
1222   cache_->LoadVirtualObjectsForFieldsFrom(state, aliases_);
1223   if (cache_->objects().size() == cache_->fields().size()) {
1224     cache_->GetFields(offset);
1225     if (cache_->fields().size() == cache_->objects().size()) {
1226       Node* rep = replacement(node);
1227       if (!rep || !IsEquivalentPhi(rep, cache_->fields())) {
1228         int value_input_count = static_cast<int>(cache_->fields().size());
1229         cache_->fields().push_back(NodeProperties::GetControlInput(from));
1230         Node* phi = graph()->NewNode(
1231             common()->Phi(MachineRepresentation::kTagged, value_input_count),
1232             value_input_count + 1, &cache_->fields().front());
1233         escape_status_.Resize();
1234         SetReplacement(node, phi);
1235         state->LastChangedAt(node);
1236         if (FLAG_trace_turbo_escape) {
1237           PrintF(" got phi created.\n");
1238         }
1239       } else if (FLAG_trace_turbo_escape) {
1240         PrintF(" has already phi #%d.\n", rep->id());
1241       }
1242     } else if (FLAG_trace_turbo_escape) {
1243       PrintF(" has incomplete field info.\n");
1244     }
1245   } else if (FLAG_trace_turbo_escape) {
1246     PrintF(" has incomplete virtual object info.\n");
1247   }
1248 }
1249 
1250 
ProcessLoadField(Node * node)1251 void EscapeAnalysis::ProcessLoadField(Node* node) {
1252   DCHECK_EQ(node->opcode(), IrOpcode::kLoadField);
1253   ForwardVirtualState(node);
1254   Node* from = NodeProperties::GetValueInput(node, 0);
1255   VirtualState* state = virtual_states_[node->id()];
1256   if (VirtualObject* object = ResolveVirtualObject(state, from)) {
1257     int offset = OffsetFromAccess(node);
1258     if (!object->IsTracked()) return;
1259     Node* value = object->GetField(offset);
1260     if (value) {
1261       value = ResolveReplacement(value);
1262     }
1263     // Record that the load has this alias.
1264     UpdateReplacement(state, node, value);
1265   } else {
1266     if (from->opcode() == IrOpcode::kPhi &&
1267         OpParameter<FieldAccess>(node).offset % kPointerSize == 0) {
1268       int offset = OffsetFromAccess(node);
1269       // Only binary phis are supported for now.
1270       ProcessLoadFromPhi(offset, from, node, state);
1271     }
1272   }
1273 }
1274 
1275 
ProcessLoadElement(Node * node)1276 void EscapeAnalysis::ProcessLoadElement(Node* node) {
1277   DCHECK_EQ(node->opcode(), IrOpcode::kLoadElement);
1278   ForwardVirtualState(node);
1279   Node* from = NodeProperties::GetValueInput(node, 0);
1280   VirtualState* state = virtual_states_[node->id()];
1281   Node* index_node = node->InputAt(1);
1282   NumberMatcher index(index_node);
1283   DCHECK(index_node->opcode() != IrOpcode::kInt32Constant &&
1284          index_node->opcode() != IrOpcode::kInt64Constant &&
1285          index_node->opcode() != IrOpcode::kFloat32Constant &&
1286          index_node->opcode() != IrOpcode::kFloat64Constant);
1287   ElementAccess access = OpParameter<ElementAccess>(node);
1288   if (index.HasValue()) {
1289     int offset = index.Value() + access.header_size / kPointerSize;
1290     if (VirtualObject* object = ResolveVirtualObject(state, from)) {
1291       CHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
1292                kPointerSizeLog2);
1293       CHECK_EQ(access.header_size % kPointerSize, 0);
1294 
1295       if (!object->IsTracked()) return;
1296       Node* value = object->GetField(offset);
1297       if (value) {
1298         value = ResolveReplacement(value);
1299       }
1300       // Record that the load has this alias.
1301       UpdateReplacement(state, node, value);
1302     } else if (from->opcode() == IrOpcode::kPhi) {
1303       ElementAccess access = OpParameter<ElementAccess>(node);
1304       int offset = index.Value() + access.header_size / kPointerSize;
1305       ProcessLoadFromPhi(offset, from, node, state);
1306     }
1307   } else {
1308     // We have a load from a non-const index, cannot eliminate object.
1309     if (SetEscaped(from)) {
1310       if (FLAG_trace_turbo_escape) {
1311         PrintF(
1312             "Setting #%d (%s) to escaped because store element #%d to "
1313             "non-const "
1314             "index #%d (%s)\n",
1315             from->id(), from->op()->mnemonic(), node->id(), index_node->id(),
1316             index_node->op()->mnemonic());
1317       }
1318     }
1319   }
1320 }
1321 
1322 
ProcessStoreField(Node * node)1323 void EscapeAnalysis::ProcessStoreField(Node* node) {
1324   DCHECK_EQ(node->opcode(), IrOpcode::kStoreField);
1325   ForwardVirtualState(node);
1326   Node* to = NodeProperties::GetValueInput(node, 0);
1327   Node* val = NodeProperties::GetValueInput(node, 1);
1328   VirtualState* state = virtual_states_[node->id()];
1329   if (VirtualObject* obj = ResolveVirtualObject(state, to)) {
1330     if (!obj->IsTracked()) return;
1331     int offset = OffsetFromAccess(node);
1332     if (obj->SetField(offset, ResolveReplacement(val))) {
1333       state->LastChangedAt(node);
1334     }
1335   }
1336 }
1337 
1338 
ProcessStoreElement(Node * node)1339 void EscapeAnalysis::ProcessStoreElement(Node* node) {
1340   DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement);
1341   ForwardVirtualState(node);
1342   Node* to = NodeProperties::GetValueInput(node, 0);
1343   Node* index_node = node->InputAt(1);
1344   NumberMatcher index(index_node);
1345   DCHECK(index_node->opcode() != IrOpcode::kInt32Constant &&
1346          index_node->opcode() != IrOpcode::kInt64Constant &&
1347          index_node->opcode() != IrOpcode::kFloat32Constant &&
1348          index_node->opcode() != IrOpcode::kFloat64Constant);
1349   ElementAccess access = OpParameter<ElementAccess>(node);
1350   Node* val = NodeProperties::GetValueInput(node, 2);
1351   if (index.HasValue()) {
1352     int offset = index.Value() + access.header_size / kPointerSize;
1353     VirtualState* states = virtual_states_[node->id()];
1354     if (VirtualObject* obj = ResolveVirtualObject(states, to)) {
1355       if (!obj->IsTracked()) return;
1356       CHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
1357                kPointerSizeLog2);
1358       CHECK_EQ(access.header_size % kPointerSize, 0);
1359       if (obj->SetField(offset, ResolveReplacement(val))) {
1360         states->LastChangedAt(node);
1361       }
1362     }
1363   } else {
1364     // We have a store to a non-const index, cannot eliminate object.
1365     if (SetEscaped(to)) {
1366       if (FLAG_trace_turbo_escape) {
1367         PrintF(
1368             "Setting #%d (%s) to escaped because store element #%d to "
1369             "non-const "
1370             "index #%d (%s)\n",
1371             to->id(), to->op()->mnemonic(), node->id(), index_node->id(),
1372             index_node->op()->mnemonic());
1373       }
1374     }
1375   }
1376 }
1377 
1378 
GetOrCreateObjectState(Node * effect,Node * node)1379 Node* EscapeAnalysis::GetOrCreateObjectState(Node* effect, Node* node) {
1380   if ((node->opcode() == IrOpcode::kFinishRegion ||
1381        node->opcode() == IrOpcode::kAllocate) &&
1382       IsVirtual(node)) {
1383     if (VirtualObject* vobj =
1384             ResolveVirtualObject(virtual_states_[effect->id()], node)) {
1385       if (Node* object_state = vobj->GetObjectState()) {
1386         return object_state;
1387       } else {
1388         cache_->fields().clear();
1389         for (size_t i = 0; i < vobj->field_count(); ++i) {
1390           if (Node* field = vobj->GetField(i)) {
1391             cache_->fields().push_back(field);
1392           }
1393         }
1394         int input_count = static_cast<int>(cache_->fields().size());
1395         Node* new_object_state =
1396             graph()->NewNode(common()->ObjectState(input_count, vobj->id()),
1397                              input_count, &cache_->fields().front());
1398         vobj->SetObjectState(new_object_state);
1399         if (FLAG_trace_turbo_escape) {
1400           PrintF(
1401               "Creating object state #%d for vobj %p (from node #%d) at effect "
1402               "#%d\n",
1403               new_object_state->id(), static_cast<void*>(vobj), node->id(),
1404               effect->id());
1405         }
1406         // Now fix uses of other objects.
1407         for (size_t i = 0; i < vobj->field_count(); ++i) {
1408           if (Node* field = vobj->GetField(i)) {
1409             if (Node* field_object_state =
1410                     GetOrCreateObjectState(effect, field)) {
1411               NodeProperties::ReplaceValueInput(
1412                   new_object_state, field_object_state, static_cast<int>(i));
1413             }
1414           }
1415         }
1416         return new_object_state;
1417       }
1418     }
1419   }
1420   return nullptr;
1421 }
1422 
1423 
DebugPrintObject(VirtualObject * object,Alias alias)1424 void EscapeAnalysis::DebugPrintObject(VirtualObject* object, Alias alias) {
1425   PrintF("  Alias @%d: Object #%d with %zu fields\n", alias, object->id(),
1426          object->field_count());
1427   for (size_t i = 0; i < object->field_count(); ++i) {
1428     if (Node* f = object->GetField(i)) {
1429       PrintF("    Field %zu = #%d (%s)\n", i, f->id(), f->op()->mnemonic());
1430     }
1431   }
1432 }
1433 
1434 
DebugPrintState(VirtualState * state)1435 void EscapeAnalysis::DebugPrintState(VirtualState* state) {
1436   PrintF("Dumping object state %p\n", static_cast<void*>(state));
1437   for (Alias alias = 0; alias < AliasCount(); ++alias) {
1438     if (VirtualObject* object = state->VirtualObjectFromAlias(alias)) {
1439       DebugPrintObject(object, alias);
1440     }
1441   }
1442 }
1443 
1444 
DebugPrint()1445 void EscapeAnalysis::DebugPrint() {
1446   ZoneVector<VirtualState*> object_states(zone());
1447   for (NodeId id = 0; id < virtual_states_.size(); id++) {
1448     if (VirtualState* states = virtual_states_[id]) {
1449       if (std::find(object_states.begin(), object_states.end(), states) ==
1450           object_states.end()) {
1451         object_states.push_back(states);
1452       }
1453     }
1454   }
1455   for (size_t n = 0; n < object_states.size(); n++) {
1456     DebugPrintState(object_states[n]);
1457   }
1458 }
1459 
1460 
GetVirtualObject(VirtualState * state,Node * node)1461 VirtualObject* EscapeAnalysis::GetVirtualObject(VirtualState* state,
1462                                                 Node* node) {
1463   if (node->id() >= aliases_.size()) return nullptr;
1464   Alias alias = aliases_[node->id()];
1465   if (alias >= state->size()) return nullptr;
1466   return state->VirtualObjectFromAlias(alias);
1467 }
1468 
1469 }  // namespace compiler
1470 }  // namespace internal
1471 }  // namespace v8
1472