Line data Source code
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/linkage.h"
16 : #include "src/compiler/node-matchers.h"
17 : #include "src/compiler/node-properties.h"
18 : #include "src/compiler/node.h"
19 : #include "src/compiler/operator-properties.h"
20 : #include "src/compiler/simplified-operator.h"
21 : #include "src/compiler/type-cache.h"
22 : #include "src/objects-inl.h"
23 :
24 : namespace v8 {
25 : namespace internal {
26 : namespace compiler {
27 :
28 : typedef NodeId Alias;
29 :
30 : #ifdef DEBUG
31 : #define TRACE(...) \
32 : do { \
33 : if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
34 : } while (false)
35 : #else
36 : #define TRACE(...)
37 : #endif
38 :
39 : // EscapeStatusAnalysis determines for each allocation whether it escapes.
40 : class EscapeStatusAnalysis : public ZoneObject {
41 : public:
42 : enum Status {
43 : kUnknown = 0u,
44 : kTracked = 1u << 0,
45 : kEscaped = 1u << 1,
46 : kOnStack = 1u << 2,
47 : kVisited = 1u << 3,
48 : // A node is dangling, if it is a load of some kind, and does not have
49 : // an effect successor.
50 : kDanglingComputed = 1u << 4,
51 : kDangling = 1u << 5,
52 : // A node is is an effect branch point, if it has more than 2 non-dangling
53 : // effect successors.
54 : kBranchPointComputed = 1u << 6,
55 : kBranchPoint = 1u << 7,
56 : kInQueue = 1u << 8
57 : };
58 : typedef base::Flags<Status, uint16_t> StatusFlags;
59 :
60 : void RunStatusAnalysis();
61 :
62 : bool IsVirtual(Node* node);
63 : bool IsEscaped(Node* node);
64 : bool IsAllocation(Node* node);
65 :
66 : bool IsInQueue(NodeId id);
67 : void SetInQueue(NodeId id, bool on_stack);
68 :
69 : void DebugPrint();
70 :
71 : EscapeStatusAnalysis(EscapeAnalysis* object_analysis, Graph* graph,
72 : Zone* zone);
73 : void EnqueueForStatusAnalysis(Node* node);
74 : bool SetEscaped(Node* node);
75 : bool IsEffectBranchPoint(Node* node);
76 : bool IsDanglingEffectNode(Node* node);
77 : void ResizeStatusVector();
78 : size_t GetStatusVectorSize();
79 : bool IsVirtual(NodeId id);
80 :
81 : Graph* graph() const { return graph_; }
82 : void AssignAliases();
83 35392408 : Alias GetAlias(NodeId id) const { return aliases_[id]; }
84 : const ZoneVector<Alias>& GetAliasMap() const { return aliases_; }
85 : Alias AliasCount() const { return next_free_alias_; }
86 : static const Alias kNotReachable;
87 : static const Alias kUntrackable;
88 :
89 : bool IsNotReachable(Node* node);
90 :
91 : private:
92 : void Process(Node* node);
93 : void ProcessAllocate(Node* node);
94 : void ProcessFinishRegion(Node* node);
95 : void ProcessStoreField(Node* node);
96 : void ProcessStoreElement(Node* node);
97 : bool CheckUsesForEscape(Node* node, bool phi_escaping = false) {
98 697329 : return CheckUsesForEscape(node, node, phi_escaping);
99 : }
100 : bool CheckUsesForEscape(Node* node, Node* rep, bool phi_escaping = false);
101 : void RevisitUses(Node* node);
102 : void RevisitInputs(Node* node);
103 :
104 115359 : Alias NextAlias() { return next_free_alias_++; }
105 :
106 : bool HasEntry(Node* node);
107 :
108 : bool IsAllocationPhi(Node* node);
109 :
110 : ZoneVector<Node*> stack_;
111 : EscapeAnalysis* object_analysis_;
112 : Graph* const graph_;
113 : ZoneVector<StatusFlags> status_;
114 : Alias next_free_alias_;
115 : ZoneVector<Node*> status_stack_;
116 : ZoneVector<Alias> aliases_;
117 :
118 : DISALLOW_COPY_AND_ASSIGN(EscapeStatusAnalysis);
119 : };
120 :
121 : DEFINE_OPERATORS_FOR_FLAGS(EscapeStatusAnalysis::StatusFlags)
122 :
123 : const Alias EscapeStatusAnalysis::kNotReachable =
124 : std::numeric_limits<Alias>::max();
125 : const Alias EscapeStatusAnalysis::kUntrackable =
126 : std::numeric_limits<Alias>::max() - 1;
127 :
128 : class VirtualObject : public ZoneObject {
129 : public:
130 : enum Status {
131 : kInitial = 0,
132 : kTracked = 1u << 0,
133 : kInitialized = 1u << 1,
134 : kCopyRequired = 1u << 2,
135 : };
136 : typedef base::Flags<Status, unsigned char> StatusFlags;
137 :
138 : VirtualObject(NodeId id, VirtualState* owner, Zone* zone)
139 : : id_(id),
140 : status_(kInitial),
141 : fields_(zone),
142 : phi_(zone),
143 : object_state_(nullptr),
144 0 : owner_(owner) {}
145 :
146 272802 : VirtualObject(VirtualState* owner, const VirtualObject& other)
147 : : id_(other.id_),
148 : status_(other.status_ & ~kCopyRequired),
149 : fields_(other.fields_),
150 : phi_(other.phi_),
151 : object_state_(other.object_state_),
152 818406 : owner_(owner) {}
153 :
154 476067 : VirtualObject(NodeId id, VirtualState* owner, Zone* zone, size_t field_number,
155 : bool initialized)
156 : : id_(id),
157 : status_(kTracked | (initialized ? kInitialized : kInitial)),
158 : fields_(zone),
159 : phi_(zone),
160 : object_state_(nullptr),
161 952134 : owner_(owner) {
162 476067 : fields_.resize(field_number);
163 476067 : phi_.resize(field_number, false);
164 476067 : }
165 :
166 1062419665 : Node* GetField(size_t offset) { return fields_[offset]; }
167 :
168 1861859 : bool IsCreatedPhi(size_t offset) { return phi_[offset]; }
169 :
170 4190266 : void SetField(size_t offset, Node* node, bool created_phi = false) {
171 8380532 : fields_[offset] = node;
172 4190266 : phi_[offset] = created_phi;
173 4190266 : }
174 : bool IsTracked() const { return status_ & kTracked; }
175 360708 : bool IsInitialized() const { return status_ & kInitialized; }
176 : bool SetInitialized() { return status_ |= kInitialized; }
177 : VirtualState* owner() const { return owner_; }
178 :
179 : Node** fields_array() { return &fields_.front(); }
180 24123522 : size_t field_count() { return fields_.size(); }
181 339013 : bool ResizeFields(size_t field_count) {
182 678026 : if (field_count > fields_.size()) {
183 0 : fields_.resize(field_count);
184 0 : phi_.resize(field_count);
185 0 : return true;
186 : }
187 : return false;
188 : }
189 81244 : void ClearAllFields() {
190 1507456 : for (size_t i = 0; i < fields_.size(); ++i) {
191 1426212 : fields_[i] = nullptr;
192 672484 : phi_[i] = false;
193 : }
194 81244 : }
195 : bool AllFieldsClear() {
196 29029704 : for (size_t i = 0; i < fields_.size(); ++i) {
197 32657228 : if (fields_[i] != nullptr) {
198 : return false;
199 : }
200 : }
201 : return true;
202 : }
203 : bool UpdateFrom(const VirtualObject& other);
204 : bool MergeFrom(MergeCache* cache, Node* at, Graph* graph,
205 : CommonOperatorBuilder* common, bool initialMerge);
206 8835 : void SetObjectState(Node* node) { object_state_ = node; }
207 : Node* GetObjectState() const { return object_state_; }
208 : bool IsCopyRequired() const { return status_ & kCopyRequired; }
209 : void SetCopyRequired() { status_ |= kCopyRequired; }
210 : bool NeedCopyForModification() {
211 1529465 : if (!IsCopyRequired() || !IsInitialized()) {
212 : return false;
213 : }
214 : return true;
215 : }
216 :
217 : NodeId id() const { return id_; }
218 : void id(NodeId id) { id_ = id; }
219 :
220 : private:
221 : bool MergeFields(size_t i, Node* at, MergeCache* cache, Graph* graph,
222 : CommonOperatorBuilder* common);
223 :
224 : NodeId id_;
225 : StatusFlags status_;
226 : ZoneVector<Node*> fields_;
227 : ZoneVector<bool> phi_;
228 : Node* object_state_;
229 : VirtualState* owner_;
230 :
231 : DISALLOW_COPY_AND_ASSIGN(VirtualObject);
232 : };
233 :
234 : DEFINE_OPERATORS_FOR_FLAGS(VirtualObject::StatusFlags)
235 :
236 89668 : bool VirtualObject::UpdateFrom(const VirtualObject& other) {
237 89668 : bool changed = status_ != other.status_;
238 89668 : status_ = other.status_;
239 : phi_ = other.phi_;
240 1373010 : if (fields_.size() != other.fields_.size()) {
241 : fields_ = other.fields_;
242 0 : return true;
243 : }
244 1104006 : for (size_t i = 0; i < fields_.size(); ++i) {
245 1014338 : if (fields_[i] != other.fields_[i]) {
246 : changed = true;
247 45498 : fields_[i] = other.fields_[i];
248 : }
249 : }
250 : return changed;
251 : }
252 :
253 : class VirtualState : public ZoneObject {
254 : public:
255 267427 : VirtualState(Node* owner, Zone* zone, size_t size)
256 : : info_(size, nullptr, zone),
257 : initialized_(static_cast<int>(size), zone),
258 267427 : owner_(owner) {}
259 :
260 126519 : VirtualState(Node* owner, const VirtualState& state)
261 : : info_(state.info_.size(), nullptr, state.info_.get_allocator().zone()),
262 : initialized_(state.initialized_.length(),
263 : state.info_.get_allocator().zone()),
264 3035756 : owner_(owner) {
265 5818474 : for (size_t i = 0; i < info_.size(); ++i) {
266 2782718 : if (state.info_[i]) {
267 3244282 : info_[i] = state.info_[i];
268 : }
269 : }
270 126519 : }
271 :
272 : VirtualObject* VirtualObjectFromAlias(size_t alias);
273 : void SetVirtualObject(Alias alias, VirtualObject* state);
274 : bool UpdateFrom(VirtualState* state, Zone* zone);
275 : bool MergeFrom(MergeCache* cache, Zone* zone, Graph* graph,
276 : CommonOperatorBuilder* common, Node* at);
277 72833684 : size_t size() const { return info_.size(); }
278 : Node* owner() const { return owner_; }
279 : VirtualObject* Copy(VirtualObject* obj, Alias alias);
280 : void SetCopyRequired() {
281 77040842 : for (VirtualObject* obj : info_) {
282 37347270 : if (obj) obj->SetCopyRequired();
283 : }
284 : }
285 :
286 : private:
287 : ZoneVector<VirtualObject*> info_;
288 : BitVector initialized_;
289 : Node* owner_;
290 :
291 : DISALLOW_COPY_AND_ASSIGN(VirtualState);
292 : };
293 :
294 : class MergeCache : public ZoneObject {
295 : public:
296 39769 : explicit MergeCache(Zone* zone)
297 : : states_(zone), objects_(zone), fields_(zone) {
298 39769 : states_.reserve(5);
299 39769 : objects_.reserve(5);
300 39769 : fields_.reserve(5);
301 39769 : }
302 : ZoneVector<VirtualState*>& states() { return states_; }
303 : ZoneVector<VirtualObject*>& objects() { return objects_; }
304 : ZoneVector<Node*>& fields() { return fields_; }
305 : void Clear() {
306 : states_.clear();
307 : objects_.clear();
308 : fields_.clear();
309 : }
310 : size_t LoadVirtualObjectsFromStatesFor(Alias alias);
311 : void LoadVirtualObjectsForFieldsFrom(VirtualState* state,
312 : const ZoneVector<Alias>& aliases);
313 : Node* GetFields(size_t pos);
314 :
315 : private:
316 : ZoneVector<VirtualState*> states_;
317 : ZoneVector<VirtualObject*> objects_;
318 : ZoneVector<Node*> fields_;
319 :
320 : DISALLOW_COPY_AND_ASSIGN(MergeCache);
321 : };
322 :
323 0 : size_t MergeCache::LoadVirtualObjectsFromStatesFor(Alias alias) {
324 : objects_.clear();
325 : DCHECK_GT(states_.size(), 0u);
326 0 : size_t min = std::numeric_limits<size_t>::max();
327 0 : for (VirtualState* state : states_) {
328 0 : if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) {
329 0 : objects_.push_back(obj);
330 0 : min = std::min(obj->field_count(), min);
331 : }
332 : }
333 0 : return min;
334 : }
335 :
336 15964 : void MergeCache::LoadVirtualObjectsForFieldsFrom(
337 : VirtualState* state, const ZoneVector<Alias>& aliases) {
338 : objects_.clear();
339 : size_t max_alias = state->size();
340 47892 : for (Node* field : fields_) {
341 31928 : Alias alias = aliases[field->id()];
342 15964 : if (alias >= max_alias) continue;
343 0 : if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) {
344 0 : objects_.push_back(obj);
345 : }
346 : }
347 15964 : }
348 :
349 3318215 : Node* MergeCache::GetFields(size_t pos) {
350 : fields_.clear();
351 3318215 : Node* rep = pos >= objects_.front()->field_count()
352 : ? nullptr
353 3318215 : : objects_.front()->GetField(pos);
354 18339934 : for (VirtualObject* obj : objects_) {
355 11703504 : if (pos >= obj->field_count()) continue;
356 11703504 : Node* field = obj->GetField(pos);
357 11703504 : if (field) {
358 7263236 : fields_.push_back(field);
359 : }
360 11703504 : if (field != rep) {
361 : rep = nullptr;
362 : }
363 : }
364 3318215 : return rep;
365 : }
366 :
367 321597 : VirtualObject* VirtualState::Copy(VirtualObject* obj, Alias alias) {
368 321597 : if (obj->owner() == this) return obj;
369 : VirtualObject* new_obj =
370 272380 : new (info_.get_allocator().zone()) VirtualObject(this, *obj);
371 : TRACE("At state %p, alias @%d (#%d), copying virtual object from %p to %p\n",
372 : static_cast<void*>(this), alias, obj->id(), static_cast<void*>(obj),
373 : static_cast<void*>(new_obj));
374 544760 : info_[alias] = new_obj;
375 272380 : return new_obj;
376 : }
377 :
378 0 : VirtualObject* VirtualState::VirtualObjectFromAlias(size_t alias) {
379 110626468 : return info_[alias];
380 : }
381 :
382 0 : void VirtualState::SetVirtualObject(Alias alias, VirtualObject* obj) {
383 14580192 : info_[alias] = obj;
384 476489 : if (obj) initialized_.Add(alias);
385 0 : }
386 :
387 689904 : bool VirtualState::UpdateFrom(VirtualState* from, Zone* zone) {
388 689904 : if (from == this) return false;
389 : bool changed = false;
390 800826 : for (Alias alias = 0; alias < size(); ++alias) {
391 : VirtualObject* ls = VirtualObjectFromAlias(alias);
392 : VirtualObject* rs = from->VirtualObjectFromAlias(alias);
393 :
394 382855 : if (ls == rs || rs == nullptr) continue;
395 :
396 89668 : if (ls == nullptr) {
397 0 : ls = new (zone) VirtualObject(this, *rs);
398 : SetVirtualObject(alias, ls);
399 : changed = true;
400 : continue;
401 : }
402 :
403 : TRACE(" Updating fields of @%d\n", alias);
404 :
405 89668 : changed = ls->UpdateFrom(*rs) || changed;
406 : }
407 : return false;
408 : }
409 :
410 : namespace {
411 :
412 14 : bool IsEquivalentPhi(Node* node1, Node* node2) {
413 7 : if (node1 == node2) return true;
414 7 : if (node1->opcode() != IrOpcode::kPhi || node2->opcode() != IrOpcode::kPhi ||
415 0 : node1->op()->ValueInputCount() != node2->op()->ValueInputCount()) {
416 : return false;
417 : }
418 0 : for (int i = 0; i < node1->op()->ValueInputCount(); ++i) {
419 0 : Node* input1 = NodeProperties::GetValueInput(node1, i);
420 0 : Node* input2 = NodeProperties::GetValueInput(node2, i);
421 0 : if (!IsEquivalentPhi(input1, input2)) {
422 : return false;
423 : }
424 : }
425 : return true;
426 : }
427 :
428 0 : bool IsEquivalentPhi(Node* phi, ZoneVector<Node*>& inputs) {
429 0 : if (phi->opcode() != IrOpcode::kPhi) return false;
430 0 : if (static_cast<size_t>(phi->op()->ValueInputCount()) != inputs.size()) {
431 : return false;
432 : }
433 0 : for (size_t i = 0; i < inputs.size(); ++i) {
434 0 : Node* input = NodeProperties::GetValueInput(phi, static_cast<int>(i));
435 0 : if (!IsEquivalentPhi(input, inputs[i])) {
436 : return false;
437 : }
438 : }
439 : return true;
440 : }
441 : } // namespace
442 :
443 55848 : bool VirtualObject::MergeFields(size_t i, Node* at, MergeCache* cache,
444 63318 : Graph* graph, CommonOperatorBuilder* common) {
445 : bool changed = false;
446 111696 : int value_input_count = static_cast<int>(cache->fields().size());
447 : Node* rep = GetField(i);
448 108631 : if (!rep || !IsCreatedPhi(i)) {
449 : Type* phi_type = Type::None();
450 150279 : for (Node* input : cache->fields()) {
451 63318 : CHECK_NOT_NULL(input);
452 63318 : CHECK(!input->IsDead());
453 : Type* input_type = NodeProperties::GetType(input);
454 63318 : phi_type = Type::Union(phi_type, input_type, graph->zone());
455 : }
456 23643 : Node* control = NodeProperties::GetControlInput(at);
457 23643 : cache->fields().push_back(control);
458 : Node* phi = graph->NewNode(
459 : common->Phi(MachineRepresentation::kTagged, value_input_count),
460 23643 : value_input_count + 1, &cache->fields().front());
461 : NodeProperties::SetType(phi, phi_type);
462 23643 : SetField(i, phi, true);
463 :
464 : #ifdef DEBUG
465 : if (FLAG_trace_turbo_escape) {
466 : PrintF(" Creating Phi #%d as merge of", phi->id());
467 : for (int i = 0; i < value_input_count; i++) {
468 : PrintF(" #%d (%s)", cache->fields()[i]->id(),
469 : cache->fields()[i]->op()->mnemonic());
470 : }
471 : PrintF("\n");
472 : }
473 : #endif
474 : changed = true;
475 : } else {
476 : DCHECK(rep->opcode() == IrOpcode::kPhi);
477 91510 : for (int n = 0; n < value_input_count; ++n) {
478 91510 : Node* old = NodeProperties::GetValueInput(rep, n);
479 183020 : if (old != cache->fields()[n]) {
480 : changed = true;
481 21079 : NodeProperties::ReplaceValueInput(rep, cache->fields()[n], n);
482 : }
483 : }
484 : }
485 55848 : return changed;
486 : }
487 :
488 2214706 : bool VirtualObject::MergeFrom(MergeCache* cache, Node* at, Graph* graph,
489 : CommonOperatorBuilder* common,
490 : bool initialMerge) {
491 : DCHECK(at->opcode() == IrOpcode::kEffectPhi ||
492 : at->opcode() == IrOpcode::kPhi);
493 : bool changed = false;
494 9787536 : for (size_t i = 0; i < field_count(); ++i) {
495 6125299 : if (!initialMerge && GetField(i) == nullptr) continue;
496 3318215 : Node* field = cache->GetFields(i);
497 5127291 : if (field && !IsCreatedPhi(i)) {
498 2908210 : changed = changed || GetField(i) != field;
499 1803652 : SetField(i, field);
500 : TRACE(" Field %zu agree on rep #%d\n", i, field->id());
501 : } else {
502 : size_t arity = at->opcode() == IrOpcode::kEffectPhi
503 1514563 : ? at->op()->EffectInputCount()
504 3029126 : : at->op()->ValueInputCount();
505 3029126 : if (cache->fields().size() == arity) {
506 55848 : changed = MergeFields(i, at, cache, graph, common) || changed;
507 : } else {
508 1458715 : if (GetField(i) != nullptr) {
509 : TRACE(" Field %zu cleared\n", i);
510 : changed = true;
511 : }
512 1458715 : SetField(i, nullptr);
513 : }
514 : }
515 : }
516 700143 : return changed;
517 : }
518 :
519 421631 : bool VirtualState::MergeFrom(MergeCache* cache, Zone* zone, Graph* graph,
520 : CommonOperatorBuilder* common, Node* at) {
521 : DCHECK_GT(cache->states().size(), 0u);
522 : bool changed = false;
523 15870762 : for (Alias alias = 0; alias < size(); ++alias) {
524 : cache->objects().clear();
525 : VirtualObject* mergeObject = VirtualObjectFromAlias(alias);
526 : bool copy_merge_object = false;
527 7513750 : size_t fields = std::numeric_limits<size_t>::max();
528 33563502 : for (VirtualState* state : cache->states()) {
529 18536002 : if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) {
530 2872787 : cache->objects().push_back(obj);
531 2872787 : if (mergeObject == obj) {
532 : copy_merge_object = true;
533 : }
534 5745574 : fields = std::min(obj->field_count(), fields);
535 : }
536 : }
537 30055000 : if (cache->objects().size() == cache->states().size() &&
538 721416 : (mergeObject || !initialized_.Contains(alias))) {
539 : bool initialMerge = false;
540 700143 : if (!mergeObject) {
541 : initialMerge = true;
542 : VirtualObject* obj = new (zone)
543 360708 : VirtualObject(cache->objects().front()->id(), this, zone, fields,
544 721416 : cache->objects().front()->IsInitialized());
545 : SetVirtualObject(alias, obj);
546 : mergeObject = obj;
547 : changed = true;
548 339435 : } else if (copy_merge_object) {
549 422 : VirtualObject* obj = new (zone) VirtualObject(this, *mergeObject);
550 : SetVirtualObject(alias, obj);
551 : mergeObject = obj;
552 : changed = true;
553 : } else {
554 339013 : changed = mergeObject->ResizeFields(fields) || changed;
555 : }
556 : #ifdef DEBUG
557 : if (FLAG_trace_turbo_escape) {
558 : PrintF(" Alias @%d, merging into %p virtual objects", alias,
559 : static_cast<void*>(mergeObject));
560 : for (size_t i = 0; i < cache->objects().size(); i++) {
561 : PrintF(" %p", static_cast<void*>(cache->objects()[i]));
562 : }
563 : PrintF("\n");
564 : }
565 : #endif // DEBUG
566 : changed =
567 700143 : mergeObject->MergeFrom(cache, at, graph, common, initialMerge) ||
568 : changed;
569 : } else {
570 6813607 : if (mergeObject) {
571 : TRACE(" Alias %d, virtual object removed\n", alias);
572 : changed = true;
573 : }
574 : SetVirtualObject(alias, nullptr);
575 : }
576 : }
577 421631 : return changed;
578 : }
579 :
580 0 : EscapeStatusAnalysis::EscapeStatusAnalysis(EscapeAnalysis* object_analysis,
581 : Graph* graph, Zone* zone)
582 : : stack_(zone),
583 : object_analysis_(object_analysis),
584 : graph_(graph),
585 : status_(zone),
586 : next_free_alias_(0),
587 : status_stack_(zone),
588 786404 : aliases_(zone) {}
589 :
590 697329 : bool EscapeStatusAnalysis::HasEntry(Node* node) {
591 697329 : return status_[node->id()] & (kTracked | kEscaped);
592 : }
593 :
594 0 : bool EscapeStatusAnalysis::IsVirtual(Node* node) {
595 0 : return IsVirtual(node->id());
596 : }
597 :
598 0 : bool EscapeStatusAnalysis::IsVirtual(NodeId id) {
599 5213428 : return (status_[id] & kTracked) && !(status_[id] & kEscaped);
600 : }
601 :
602 6050294 : bool EscapeStatusAnalysis::IsEscaped(Node* node) {
603 6050312 : return status_[node->id()] & kEscaped;
604 : }
605 :
606 1022210 : bool EscapeStatusAnalysis::IsAllocation(Node* node) {
607 1597824 : return node->opcode() == IrOpcode::kAllocate ||
608 0 : node->opcode() == IrOpcode::kFinishRegion;
609 : }
610 :
611 5047975 : bool EscapeStatusAnalysis::SetEscaped(Node* node) {
612 5047975 : bool changed = !(status_[node->id()] & kEscaped);
613 : status_[node->id()] |= kEscaped | kTracked;
614 0 : return changed;
615 : }
616 :
617 0 : bool EscapeStatusAnalysis::IsInQueue(NodeId id) {
618 5416518 : return status_[id] & kInQueue;
619 : }
620 :
621 0 : void EscapeStatusAnalysis::SetInQueue(NodeId id, bool on_stack) {
622 0 : if (on_stack) {
623 5048293 : status_[id] |= kInQueue;
624 : } else {
625 5048293 : status_[id] &= ~kInQueue;
626 : }
627 0 : }
628 :
629 1534540 : void EscapeStatusAnalysis::ResizeStatusVector() {
630 2301810 : if (status_.size() <= graph()->NodeCount()) {
631 393202 : status_.resize(graph()->NodeCount() * 1.1, kUnknown);
632 : }
633 767270 : }
634 :
635 2503200 : size_t EscapeStatusAnalysis::GetStatusVectorSize() { return status_.size(); }
636 :
637 39769 : void EscapeStatusAnalysis::RunStatusAnalysis() {
638 : // TODO(tebbi): This checks for faulty VirtualObject states, which can happen
639 : // due to bug https://bugs.chromium.org/p/v8/issues/detail?id=6302. As a
640 : // workaround, we set everything to escaped if such a faulty state was
641 : // detected.
642 39769 : bool all_objects_complete = object_analysis_->AllObjectsComplete();
643 39769 : ResizeStatusVector();
644 9209655 : while (!status_stack_.empty()) {
645 27390351 : Node* node = status_stack_.back();
646 : status_stack_.pop_back();
647 18260234 : status_[node->id()] &= ~kOnStack;
648 9130117 : Process(node);
649 9130117 : status_[node->id()] |= kVisited;
650 9130117 : if (!all_objects_complete) SetEscaped(node);
651 : }
652 39769 : }
653 :
654 115359 : void EscapeStatusAnalysis::EnqueueForStatusAnalysis(Node* node) {
655 : DCHECK_NOT_NULL(node);
656 576795 : if (!(status_[node->id()] & kOnStack)) {
657 115359 : status_stack_.push_back(node);
658 230718 : status_[node->id()] |= kOnStack;
659 : }
660 115359 : }
661 :
662 785757 : void EscapeStatusAnalysis::RevisitInputs(Node* node) {
663 1882273 : for (Edge edge : node->input_edges()) {
664 1096516 : Node* input = edge.to();
665 5070840 : if (!(status_[input->id()] & kOnStack)) {
666 890646 : status_stack_.push_back(input);
667 1781292 : status_[input->id()] |= kOnStack;
668 : }
669 : }
670 785757 : }
671 :
672 1756328 : void EscapeStatusAnalysis::RevisitUses(Node* node) {
673 13101724 : for (Edge edge : node->use_edges()) {
674 11345395 : Node* use = edge.from();
675 58419801 : if (!(status_[use->id()] & kOnStack) && !IsNotReachable(use)) {
676 8124149 : status_stack_.push_back(use);
677 16248300 : status_[use->id()] |= kOnStack;
678 : }
679 : }
680 1756329 : }
681 :
682 9130125 : void EscapeStatusAnalysis::Process(Node* node) {
683 9130125 : switch (node->opcode()) {
684 : case IrOpcode::kAllocate:
685 182775 : ProcessAllocate(node);
686 182775 : break;
687 : case IrOpcode::kFinishRegion:
688 176389 : ProcessFinishRegion(node);
689 176389 : break;
690 : case IrOpcode::kStoreField:
691 2315081 : ProcessStoreField(node);
692 2315077 : break;
693 : case IrOpcode::kStoreElement:
694 435438 : ProcessStoreElement(node);
695 435438 : break;
696 : case IrOpcode::kLoadField:
697 : case IrOpcode::kLoadElement: {
698 549333 : if (Node* rep = object_analysis_->GetReplacement(node)) {
699 17162 : if (IsAllocation(rep) && CheckUsesForEscape(node, rep)) {
700 1 : RevisitInputs(rep);
701 1 : RevisitUses(rep);
702 : }
703 : } else {
704 532171 : Node* from = NodeProperties::GetValueInput(node, 0);
705 532171 : from = object_analysis_->ResolveReplacement(from);
706 532171 : if (SetEscaped(from)) {
707 : TRACE("Setting #%d (%s) to escaped because of unresolved load #%i\n",
708 : from->id(), from->op()->mnemonic(), node->id());
709 44659 : RevisitInputs(from);
710 44659 : RevisitUses(from);
711 : }
712 : }
713 549333 : RevisitUses(node);
714 549333 : break;
715 : }
716 : case IrOpcode::kPhi:
717 338165 : if (!HasEntry(node)) {
718 : status_[node->id()] |= kTracked;
719 125847 : RevisitUses(node);
720 : }
721 676330 : if (!IsAllocationPhi(node) && SetEscaped(node)) {
722 125847 : RevisitInputs(node);
723 125847 : RevisitUses(node);
724 : }
725 : CheckUsesForEscape(node);
726 : default:
727 : break;
728 : }
729 9130121 : }
730 :
731 338165 : bool EscapeStatusAnalysis::IsAllocationPhi(Node* node) {
732 624757 : for (Edge edge : node->input_edges()) {
733 624757 : Node* input = edge.to();
734 767658 : if (input->opcode() == IrOpcode::kPhi && !IsEscaped(input)) continue;
735 575614 : if (IsAllocation(input)) continue;
736 : return false;
737 : }
738 0 : return true;
739 : }
740 :
741 2315080 : void EscapeStatusAnalysis::ProcessStoreField(Node* node) {
742 : DCHECK_EQ(node->opcode(), IrOpcode::kStoreField);
743 2315080 : Node* to = NodeProperties::GetValueInput(node, 0);
744 2315080 : Node* val = NodeProperties::GetValueInput(node, 1);
745 4856832 : if ((IsEscaped(to) || !IsAllocation(to)) && SetEscaped(val)) {
746 423206 : RevisitUses(val);
747 423206 : RevisitInputs(val);
748 : TRACE("Setting #%d (%s) to escaped because of store to field of #%d\n",
749 : val->id(), val->op()->mnemonic(), to->id());
750 : }
751 2315077 : }
752 :
753 435438 : void EscapeStatusAnalysis::ProcessStoreElement(Node* node) {
754 : DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement);
755 435438 : Node* to = NodeProperties::GetValueInput(node, 0);
756 435438 : Node* val = NodeProperties::GetValueInput(node, 2);
757 872325 : if ((IsEscaped(to) || !IsAllocation(to)) && SetEscaped(val)) {
758 136193 : RevisitUses(val);
759 136193 : RevisitInputs(val);
760 : TRACE("Setting #%d (%s) to escaped because of store to field of #%d\n",
761 : val->id(), val->op()->mnemonic(), to->id());
762 : }
763 435438 : }
764 :
765 182775 : void EscapeStatusAnalysis::ProcessAllocate(Node* node) {
766 : DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
767 182775 : if (!HasEntry(node)) {
768 : status_[node->id()] |= kTracked;
769 : TRACE("Created status entry for node #%d (%s)\n", node->id(),
770 : node->op()->mnemonic());
771 : NumberMatcher size(node->InputAt(0));
772 : DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant &&
773 : node->InputAt(0)->opcode() != IrOpcode::kInt64Constant &&
774 : node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant &&
775 : node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant);
776 115356 : RevisitUses(node);
777 115356 : if (!size.HasValue() && SetEscaped(node)) {
778 : TRACE("Setting #%d to escaped because of non-const alloc\n", node->id());
779 : // This node is already known to escape, uses do not have to be checked
780 : // for escape.
781 182775 : return;
782 : }
783 : }
784 182775 : if (CheckUsesForEscape(node, true)) {
785 72235 : RevisitUses(node);
786 : }
787 : }
788 :
789 754143 : bool EscapeStatusAnalysis::CheckUsesForEscape(Node* uses, Node* rep,
790 : bool phi_escaping) {
791 4694132 : for (Edge edge : uses->use_edges()) {
792 7995562 : Node* use = edge.from();
793 4122514 : if (IsNotReachable(use)) continue;
794 8238649 : if (edge.index() >= use->op()->ValueInputCount() +
795 : OperatorProperties::GetContextInputCount(use->op()))
796 : continue;
797 3876237 : switch (use->opcode()) {
798 : case IrOpcode::kPhi:
799 638715 : if (phi_escaping && SetEscaped(rep)) {
800 : TRACE(
801 : "Setting #%d (%s) to escaped because of use by phi node "
802 : "#%d (%s)\n",
803 : rep->id(), rep->op()->mnemonic(), use->id(),
804 : use->op()->mnemonic());
805 : return true;
806 : }
807 : // Fallthrough.
808 : case IrOpcode::kStoreField:
809 : case IrOpcode::kLoadField:
810 : case IrOpcode::kStoreElement:
811 : case IrOpcode::kLoadElement:
812 : case IrOpcode::kFrameState:
813 : case IrOpcode::kStateValues:
814 : case IrOpcode::kReferenceEqual:
815 : case IrOpcode::kFinishRegion:
816 : case IrOpcode::kCheckMaps:
817 4543556 : if (IsEscaped(use) && SetEscaped(rep)) {
818 : TRACE(
819 : "Setting #%d (%s) to escaped because of use by escaping node "
820 : "#%d (%s)\n",
821 : rep->id(), rep->op()->mnemonic(), use->id(),
822 : use->op()->mnemonic());
823 : return true;
824 : }
825 : break;
826 : case IrOpcode::kObjectIsSmi:
827 152 : if (!IsAllocation(rep) && SetEscaped(rep)) {
828 : TRACE("Setting #%d (%s) to escaped because of use by #%d (%s)\n",
829 : rep->id(), rep->op()->mnemonic(), use->id(),
830 : use->op()->mnemonic());
831 : return true;
832 : }
833 : break;
834 : case IrOpcode::kSelect:
835 : // TODO(mstarzinger): The following list of operators will eventually be
836 : // handled by the EscapeAnalysisReducer (similar to ObjectIsSmi).
837 : case IrOpcode::kConvertTaggedHoleToUndefined:
838 : case IrOpcode::kStringEqual:
839 : case IrOpcode::kStringLessThan:
840 : case IrOpcode::kStringLessThanOrEqual:
841 : case IrOpcode::kTypeGuard:
842 : case IrOpcode::kPlainPrimitiveToNumber:
843 : case IrOpcode::kPlainPrimitiveToWord32:
844 : case IrOpcode::kPlainPrimitiveToFloat64:
845 : case IrOpcode::kStringCharAt:
846 : case IrOpcode::kStringCharCodeAt:
847 : case IrOpcode::kStringIndexOf:
848 : case IrOpcode::kObjectIsDetectableCallable:
849 : case IrOpcode::kObjectIsNaN:
850 : case IrOpcode::kObjectIsNonCallable:
851 : case IrOpcode::kObjectIsNumber:
852 : case IrOpcode::kObjectIsReceiver:
853 : case IrOpcode::kObjectIsString:
854 : case IrOpcode::kObjectIsSymbol:
855 : case IrOpcode::kObjectIsUndetectable:
856 1155 : if (SetEscaped(rep)) {
857 : TRACE("Setting #%d (%s) to escaped because of use by #%d (%s)\n",
858 : rep->id(), rep->op()->mnemonic(), use->id(),
859 : use->op()->mnemonic());
860 : return true;
861 : }
862 : break;
863 : default:
864 1472095 : if (use->op()->EffectInputCount() == 0 &&
865 783325 : uses->op()->EffectInputCount() > 0 &&
866 : !IrOpcode::IsJsOpcode(use->opcode())) {
867 : V8_Fatal(__FILE__, __LINE__,
868 : "Encountered unaccounted use by #%d (%s)\n", use->id(),
869 0 : use->op()->mnemonic());
870 : }
871 708829 : if (SetEscaped(rep)) {
872 : TRACE("Setting #%d (%s) to escaped because of use by #%d (%s)\n",
873 : rep->id(), rep->op()->mnemonic(), use->id(),
874 : use->op()->mnemonic());
875 : return true;
876 : }
877 : }
878 : }
879 571618 : return false;
880 : }
881 :
882 176389 : void EscapeStatusAnalysis::ProcessFinishRegion(Node* node) {
883 : DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
884 176389 : if (!HasEntry(node)) {
885 : status_[node->id()] |= kTracked;
886 107805 : RevisitUses(node);
887 : }
888 176389 : if (CheckUsesForEscape(node, true)) {
889 55851 : RevisitInputs(node);
890 55851 : RevisitUses(node);
891 : }
892 176389 : }
893 :
894 0 : void EscapeStatusAnalysis::DebugPrint() {
895 0 : for (NodeId id = 0; id < status_.size(); id++) {
896 0 : if (status_[id] & kTracked) {
897 : PrintF("Node #%d is %s\n", id,
898 0 : (status_[id] & kEscaped) ? "escaping" : "virtual");
899 : }
900 : }
901 0 : }
902 :
903 393202 : EscapeAnalysis::EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common,
904 : Zone* zone)
905 : : zone_(zone),
906 393202 : slot_not_analyzed_(graph->NewNode(common->NumberConstant(0x1c0debad))),
907 : common_(common),
908 : status_analysis_(new (zone) EscapeStatusAnalysis(this, graph, zone)),
909 : virtual_states_(zone),
910 : replacements_(zone),
911 : cycle_detection_(zone),
912 1572808 : cache_(nullptr) {
913 : // Type slot_not_analyzed_ manually.
914 786404 : double v = OpParameter<double>(slot_not_analyzed_);
915 393202 : NodeProperties::SetType(slot_not_analyzed_, Type::Range(v, v, zone));
916 393202 : }
917 :
918 786403 : EscapeAnalysis::~EscapeAnalysis() {}
919 :
920 432971 : bool EscapeAnalysis::Run() {
921 786404 : replacements_.resize(graph()->NodeCount());
922 786404 : status_analysis_->AssignAliases();
923 786404 : if (status_analysis_->AliasCount() > 0) {
924 39769 : cache_ = new (zone()) MergeCache(zone());
925 79538 : replacements_.resize(graph()->NodeCount());
926 39769 : status_analysis_->ResizeStatusVector();
927 39769 : RunObjectAnalysis();
928 39769 : status_analysis_->RunStatusAnalysis();
929 39769 : return true;
930 : } else {
931 : return false;
932 : }
933 : }
934 :
935 1966010 : void EscapeStatusAnalysis::AssignAliases() {
936 393202 : size_t max_size = 1024;
937 393202 : size_t min_size = 32;
938 : size_t stack_size =
939 1179606 : std::min(std::max(graph()->NodeCount() / 5, min_size), max_size);
940 393202 : stack_.reserve(stack_size);
941 393202 : ResizeStatusVector();
942 786404 : stack_.push_back(graph()->end());
943 393202 : CHECK_LT(graph()->NodeCount(), kUntrackable);
944 112984293 : aliases_.resize(graph()->NodeCount(), kNotReachable);
945 1179606 : aliases_[graph()->end()->id()] = kUntrackable;
946 393202 : status_stack_.reserve(8);
947 : TRACE("Discovering trackable nodes");
948 29521869 : while (!stack_.empty()) {
949 57701633 : Node* node = stack_.back();
950 : stack_.pop_back();
951 28735458 : switch (node->opcode()) {
952 : case IrOpcode::kAllocate:
953 230718 : if (aliases_[node->id()] >= kUntrackable) {
954 2 : aliases_[node->id()] = NextAlias();
955 : TRACE(" @%d:%s#%u", aliases_[node->id()], node->op()->mnemonic(),
956 : node->id());
957 2 : EnqueueForStatusAnalysis(node);
958 : }
959 : break;
960 : case IrOpcode::kFinishRegion: {
961 120066 : Node* allocate = NodeProperties::GetValueInput(node, 0);
962 : DCHECK_NOT_NULL(allocate);
963 470847 : if (allocate->opcode() == IrOpcode::kAllocate) {
964 230716 : if (aliases_[allocate->id()] >= kUntrackable) {
965 115357 : if (aliases_[allocate->id()] == kNotReachable) {
966 115353 : stack_.push_back(allocate);
967 : }
968 346071 : aliases_[allocate->id()] = NextAlias();
969 : TRACE(" @%d:%s#%u", aliases_[allocate->id()],
970 : allocate->op()->mnemonic(), allocate->id());
971 115357 : EnqueueForStatusAnalysis(allocate);
972 : }
973 461432 : aliases_[node->id()] = aliases_[allocate->id()];
974 : TRACE(" @%d:%s#%u", aliases_[node->id()], node->op()->mnemonic(),
975 : node->id());
976 : }
977 : break;
978 : }
979 : default:
980 : DCHECK_EQ(aliases_[node->id()], kUntrackable);
981 : break;
982 : }
983 112244898 : for (Edge edge : node->input_edges()) {
984 83509447 : Node* input = edge.to();
985 278755351 : if (aliases_[input->id()] == kNotReachable) {
986 28227029 : stack_.push_back(input);
987 84681030 : aliases_[input->id()] = kUntrackable;
988 : }
989 : }
990 : }
991 : TRACE("\n");
992 393202 : }
993 :
994 20231586 : bool EscapeStatusAnalysis::IsNotReachable(Node* node) {
995 56733804 : if (node->id() >= aliases_.size()) {
996 : return false;
997 : }
998 28074693 : return aliases_[node->id()] == kNotReachable;
999 : }
1000 :
1001 39769 : bool EscapeAnalysis::AllObjectsComplete() {
1002 12113949 : for (VirtualState* state : virtual_states_) {
1003 12049898 : if (state) {
1004 110765760 : for (size_t i = 0; i < state->size(); ++i) {
1005 54034320 : if (VirtualObject* object = state->VirtualObjectFromAlias(i)) {
1006 5150528 : if (!object->AllFieldsClear()) {
1007 1037904080 : for (size_t i = 0; i < object->field_count(); ++i) {
1008 1037919567 : if (object->GetField(i) == nullptr) {
1009 : return false;
1010 : }
1011 : }
1012 : }
1013 : }
1014 : }
1015 : }
1016 : }
1017 : return true;
1018 : }
1019 :
1020 119307 : void EscapeAnalysis::RunObjectAnalysis() {
1021 79538 : virtual_states_.resize(graph()->NodeCount());
1022 : ZoneDeque<Node*> queue(zone());
1023 79538 : queue.push_back(graph()->start());
1024 : ZoneVector<Node*> danglers(zone());
1025 5088059 : while (!queue.empty()) {
1026 10096583 : Node* node = queue.back();
1027 : queue.pop_back();
1028 5048293 : status_analysis_->SetInQueue(node->id(), false);
1029 5048293 : if (Process(node)) {
1030 37139318 : for (Edge edge : node->use_edges()) {
1031 16109072 : Node* use = edge.from();
1032 43051286 : if (status_analysis_->IsNotReachable(use)) {
1033 9941 : continue;
1034 : }
1035 16099131 : if (NodeProperties::IsEffectEdge(edge)) {
1036 : // Iteration order: depth first, but delay phis.
1037 : // We need DFS do avoid some duplication of VirtualStates and
1038 : // VirtualObjects, and we want to delay phis to improve performance.
1039 10833248 : if (use->opcode() == IrOpcode::kEffectPhi) {
1040 1659482 : if (!status_analysis_->IsInQueue(use->id())) {
1041 : status_analysis_->SetInQueue(use->id(), true);
1042 421631 : queue.push_front(use);
1043 : }
1044 8638168 : } else if ((use->opcode() != IrOpcode::kLoadField &&
1045 5139815 : use->opcode() != IrOpcode::kLoadElement) ||
1046 552932 : !status_analysis_->IsDanglingEffectNode(use)) {
1047 13760331 : if (!status_analysis_->IsInQueue(use->id())) {
1048 : status_analysis_->SetInQueue(use->id(), true);
1049 4586777 : queue.push_back(use);
1050 : }
1051 : } else {
1052 106 : danglers.push_back(use);
1053 : }
1054 : }
1055 : }
1056 : // Danglers need to be processed immediately, even if they are
1057 : // on the stack. Since they do not have effect outputs,
1058 : // we don't have to track whether they are on the stack.
1059 4921174 : queue.insert(queue.end(), danglers.begin(), danglers.end());
1060 : danglers.clear();
1061 : }
1062 : }
1063 :
1064 : #ifdef DEBUG
1065 : if (FLAG_trace_turbo_escape) {
1066 : DebugPrint();
1067 : }
1068 : #endif
1069 39769 : }
1070 :
1071 1886660 : bool EscapeStatusAnalysis::IsDanglingEffectNode(Node* node) {
1072 2434019 : if (status_[node->id()] & kDanglingComputed) {
1073 547359 : return status_[node->id()] & kDangling;
1074 : }
1075 1339300 : if (node->op()->EffectInputCount() == 0 ||
1076 892867 : node->op()->EffectOutputCount() == 0 ||
1077 446434 : (node->op()->EffectInputCount() == 1 &&
1078 446434 : NodeProperties::GetEffectInput(node)->opcode() == IrOpcode::kStart)) {
1079 : // The start node is used as sentinel for nodes that are in general
1080 : // effectful, but of which an analysis has determined that they do not
1081 : // produce effects in this instance. We don't consider these nodes dangling.
1082 0 : status_[node->id()] |= kDanglingComputed;
1083 0 : return false;
1084 : }
1085 2156828 : for (Edge edge : node->use_edges()) {
1086 1078361 : Node* use = edge.from();
1087 2156722 : if (aliases_[use->id()] == kNotReachable) continue;
1088 1078353 : if (NodeProperties::IsEffectEdge(edge)) {
1089 446329 : status_[node->id()] |= kDanglingComputed;
1090 446329 : return false;
1091 : }
1092 : }
1093 106 : status_[node->id()] |= kDanglingComputed | kDangling;
1094 106 : return true;
1095 : }
1096 :
1097 7487958 : bool EscapeStatusAnalysis::IsEffectBranchPoint(Node* node) {
1098 11384950 : if (status_[node->id()] & kBranchPointComputed) {
1099 306027 : return status_[node->id()] & kBranchPoint;
1100 : }
1101 : int count = 0;
1102 28101374 : for (Edge edge : node->use_edges()) {
1103 16499608 : Node* use = edge.from();
1104 24946020 : if (aliases_[use->id()] == kNotReachable) continue;
1105 12463864 : if (NodeProperties::IsEffectEdge(edge)) {
1106 7624144 : if ((use->opcode() == IrOpcode::kLoadField ||
1107 3585736 : use->opcode() == IrOpcode::kLoadElement ||
1108 4467461 : use->opcode() == IrOpcode::kLoad) &&
1109 440863 : IsDanglingEffectNode(use))
1110 : continue;
1111 4026577 : if (++count > 1) {
1112 435612 : status_[node->id()] |= kBranchPointComputed | kBranchPoint;
1113 435612 : return true;
1114 : }
1115 : }
1116 : }
1117 3155354 : status_[node->id()] |= kBranchPointComputed;
1118 3155354 : return false;
1119 : }
1120 :
1121 : namespace {
1122 :
1123 4626654 : bool HasFrameStateInput(const Operator* op) {
1124 4626654 : if (op->opcode() == IrOpcode::kCall || op->opcode() == IrOpcode::kTailCall) {
1125 277600 : const CallDescriptor* d = CallDescriptorOf(op);
1126 277600 : return d->NeedsFrameState();
1127 : } else {
1128 4349054 : return OperatorProperties::HasFrameStateInput(op);
1129 : }
1130 : }
1131 :
1132 : } // namespace
1133 :
1134 11279636 : bool EscapeAnalysis::Process(Node* node) {
1135 5048298 : switch (node->opcode()) {
1136 : case IrOpcode::kAllocate:
1137 136036 : ProcessAllocation(node);
1138 136036 : break;
1139 : case IrOpcode::kBeginRegion:
1140 140515 : ForwardVirtualState(node);
1141 140515 : break;
1142 : case IrOpcode::kFinishRegion:
1143 140515 : ProcessFinishRegion(node);
1144 140515 : break;
1145 : case IrOpcode::kStoreField:
1146 1090966 : ProcessStoreField(node);
1147 1090962 : break;
1148 : case IrOpcode::kLoadField:
1149 535601 : ProcessLoadField(node);
1150 535601 : break;
1151 : case IrOpcode::kStoreElement:
1152 156038 : ProcessStoreElement(node);
1153 156038 : break;
1154 : case IrOpcode::kLoadElement:
1155 17331 : ProcessLoadElement(node);
1156 17331 : break;
1157 : case IrOpcode::kCheckMaps:
1158 41445 : ProcessCheckMaps(node);
1159 41445 : break;
1160 : case IrOpcode::kStart:
1161 39769 : ProcessStart(node);
1162 39769 : break;
1163 : case IrOpcode::kEffectPhi:
1164 421631 : return ProcessEffectPhi(node);
1165 : break;
1166 : default:
1167 4656902 : if (node->op()->EffectInputCount() > 0) {
1168 2328451 : ForwardVirtualState(node);
1169 : }
1170 2328452 : ProcessAllocationUsers(node);
1171 2328445 : break;
1172 : }
1173 4626657 : if (HasFrameStateInput(node->op())) {
1174 3209362 : virtual_states_[node->id()]->SetCopyRequired();
1175 : }
1176 : return true;
1177 : }
1178 :
1179 10608889 : void EscapeAnalysis::ProcessAllocationUsers(Node* node) {
1180 12448219 : for (Edge edge : node->input_edges()) {
1181 : Node* input = edge.to();
1182 10119774 : Node* use = edge.from();
1183 20239547 : if (edge.index() >= use->op()->ValueInputCount() +
1184 : OperatorProperties::GetContextInputCount(use->op()))
1185 : continue;
1186 4140220 : switch (node->opcode()) {
1187 : case IrOpcode::kStoreField:
1188 : case IrOpcode::kLoadField:
1189 : case IrOpcode::kStoreElement:
1190 : case IrOpcode::kLoadElement:
1191 : case IrOpcode::kFrameState:
1192 : case IrOpcode::kStateValues:
1193 : case IrOpcode::kReferenceEqual:
1194 : case IrOpcode::kFinishRegion:
1195 : case IrOpcode::kObjectIsSmi:
1196 : break;
1197 : case IrOpcode::kCheckMaps: {
1198 0 : CheckMapsParameters params = CheckMapsParametersOf(node->op());
1199 0 : if (params.flags() == CheckMapsFlag::kNone) break;
1200 : } // Fallthrough.
1201 : default:
1202 8280442 : VirtualState* state = virtual_states_[node->id()];
1203 4140219 : if (VirtualObject* obj =
1204 4140221 : GetVirtualObject(state, ResolveReplacement(input))) {
1205 346051 : if (!obj->AllFieldsClear()) {
1206 79129 : obj = CopyForModificationAt(obj, state, node);
1207 79129 : obj->ClearAllFields();
1208 : TRACE("Cleared all fields of @%d:#%d\n",
1209 : status_analysis_->GetAlias(obj->id()), obj->id());
1210 : }
1211 : }
1212 : break;
1213 : }
1214 : }
1215 2328445 : }
1216 :
1217 136253 : VirtualState* EscapeAnalysis::CopyForModificationAt(VirtualState* state,
1218 253038 : Node* node) {
1219 136253 : if (state->owner() != node) {
1220 126519 : VirtualState* new_state = new (zone()) VirtualState(node, *state);
1221 253038 : virtual_states_[node->id()] = new_state;
1222 : TRACE("Copying virtual state %p to new state %p at node %s#%d\n",
1223 : static_cast<void*>(state), static_cast<void*>(new_state),
1224 : node->op()->mnemonic(), node->id());
1225 126519 : return new_state;
1226 : }
1227 : return state;
1228 : }
1229 :
1230 1085247 : VirtualObject* EscapeAnalysis::CopyForModificationAt(VirtualObject* obj,
1231 : VirtualState* state,
1232 : Node* node) {
1233 985500 : if (obj->NeedCopyForModification()) {
1234 99747 : state = CopyForModificationAt(state, node);
1235 : // TODO(tebbi): this copies the complete virtual state. Replace with a more
1236 : // precise analysis of which objects are actually affected by the change.
1237 99747 : Alias changed_alias = status_analysis_->GetAlias(obj->id());
1238 3531430 : for (Alias alias = 0; alias < state->size(); ++alias) {
1239 1665968 : if (VirtualObject* next_obj = state->VirtualObjectFromAlias(alias)) {
1240 544483 : if (alias != changed_alias && next_obj->NeedCopyForModification()) {
1241 221850 : state->Copy(next_obj, alias);
1242 : }
1243 : }
1244 : }
1245 99747 : return state->Copy(obj, changed_alias);
1246 : }
1247 : return obj;
1248 : }
1249 :
1250 10605313 : void EscapeAnalysis::ForwardVirtualState(Node* node) {
1251 : DCHECK_EQ(node->op()->EffectInputCount(), 1);
1252 : #ifdef DEBUG
1253 : if (node->opcode() != IrOpcode::kLoadField &&
1254 : node->opcode() != IrOpcode::kLoadElement &&
1255 : node->opcode() != IrOpcode::kLoad &&
1256 : status_analysis_->IsDanglingEffectNode(node)) {
1257 : PrintF("Dangeling effect node: #%d (%s)\n", node->id(),
1258 : node->op()->mnemonic());
1259 : UNREACHABLE();
1260 : }
1261 : #endif // DEBUG
1262 9173788 : Node* effect = NodeProperties::GetEffectInput(node);
1263 : DCHECK_NOT_NULL(virtual_states_[effect->id()]);
1264 9915409 : if (virtual_states_[node->id()]) {
1265 689904 : virtual_states_[node->id()]->UpdateFrom(virtual_states_[effect->id()],
1266 689904 : zone());
1267 : } else {
1268 7793980 : virtual_states_[node->id()] = virtual_states_[effect->id()];
1269 : TRACE("Forwarding object state %p from %s#%d to %s#%d",
1270 : static_cast<void*>(virtual_states_[effect->id()]),
1271 : effect->op()->mnemonic(), effect->id(), node->op()->mnemonic(),
1272 : node->id());
1273 3896990 : if (status_analysis_->IsEffectBranchPoint(effect)) {
1274 1483242 : virtual_states_[node->id()]->SetCopyRequired();
1275 : TRACE(", effect input %s#%d is branch point", effect->op()->mnemonic(),
1276 : effect->id());
1277 : }
1278 : TRACE("\n");
1279 : }
1280 4586895 : }
1281 :
1282 79538 : void EscapeAnalysis::ProcessStart(Node* node) {
1283 : DCHECK_EQ(node->opcode(), IrOpcode::kStart);
1284 39769 : virtual_states_[node->id()] =
1285 119307 : new (zone()) VirtualState(node, zone(), status_analysis_->AliasCount());
1286 39769 : }
1287 :
1288 3641860 : bool EscapeAnalysis::ProcessEffectPhi(Node* node) {
1289 : DCHECK_EQ(node->opcode(), IrOpcode::kEffectPhi);
1290 : bool changed = false;
1291 :
1292 2570940 : VirtualState* mergeState = virtual_states_[node->id()];
1293 421631 : if (!mergeState) {
1294 : mergeState =
1295 450088 : new (zone()) VirtualState(node, zone(), status_analysis_->AliasCount());
1296 444860 : virtual_states_[node->id()] = mergeState;
1297 : changed = true;
1298 : TRACE("Effect Phi #%d got new virtual state %p.\n", node->id(),
1299 : static_cast<void*>(mergeState));
1300 : }
1301 :
1302 421631 : cache_->Clear();
1303 :
1304 : TRACE("At Effect Phi #%d, merging states into %p:", node->id(),
1305 : static_cast<void*>(mergeState));
1306 :
1307 5764953 : for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
1308 1500020 : Node* input = NodeProperties::GetEffectInput(node, i);
1309 3000040 : VirtualState* state = virtual_states_[input->id()];
1310 1500020 : if (state) {
1311 1206250 : cache_->states().push_back(state);
1312 1206250 : if (state == mergeState) {
1313 : mergeState = new (zone())
1314 15684 : VirtualState(node, zone(), status_analysis_->AliasCount());
1315 10456 : virtual_states_[node->id()] = mergeState;
1316 : changed = true;
1317 : }
1318 : }
1319 : TRACE(" %p (from %d %s)", static_cast<void*>(state), input->id(),
1320 : input->op()->mnemonic());
1321 : }
1322 : TRACE("\n");
1323 :
1324 843262 : if (cache_->states().size() == 0) {
1325 : return changed;
1326 : }
1327 :
1328 : changed =
1329 421631 : mergeState->MergeFrom(cache_, zone(), graph(), common(), node) || changed;
1330 :
1331 : TRACE("Merge %s the node.\n", changed ? "changed" : "did not change");
1332 :
1333 421631 : if (changed) {
1334 294530 : status_analysis_->ResizeStatusVector();
1335 : }
1336 421631 : return changed;
1337 : }
1338 :
1339 387431 : void EscapeAnalysis::ProcessAllocation(Node* node) {
1340 : DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
1341 136036 : ForwardVirtualState(node);
1342 387431 : VirtualState* state = virtual_states_[node->id()];
1343 136036 : Alias alias = status_analysis_->GetAlias(node->id());
1344 :
1345 : // Check if we have already processed this node.
1346 272072 : if (state->VirtualObjectFromAlias(alias)) {
1347 136036 : return;
1348 : }
1349 :
1350 230718 : if (state->owner()->opcode() == IrOpcode::kEffectPhi) {
1351 36506 : state = CopyForModificationAt(state, node);
1352 : }
1353 :
1354 : NumberMatcher size(node->InputAt(0));
1355 : DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant &&
1356 : node->InputAt(0)->opcode() != IrOpcode::kInt64Constant &&
1357 : node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant &&
1358 : node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant);
1359 115359 : if (size.HasValue()) {
1360 : VirtualObject* obj = new (zone()) VirtualObject(
1361 230718 : node->id(), state, zone(), size.Value() / kPointerSize, false);
1362 : state->SetVirtualObject(alias, obj);
1363 : } else {
1364 : state->SetVirtualObject(
1365 : alias, new (zone()) VirtualObject(node->id(), state, zone()));
1366 : }
1367 : }
1368 :
1369 276550 : void EscapeAnalysis::ProcessFinishRegion(Node* node) {
1370 : DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
1371 140515 : ForwardVirtualState(node);
1372 140515 : Node* allocation = NodeProperties::GetValueInput(node, 0);
1373 140515 : if (allocation->opcode() == IrOpcode::kAllocate) {
1374 272070 : VirtualState* state = virtual_states_[node->id()];
1375 : VirtualObject* obj =
1376 272070 : state->VirtualObjectFromAlias(status_analysis_->GetAlias(node->id()));
1377 : DCHECK_NOT_NULL(obj);
1378 : obj->SetInitialized();
1379 : }
1380 140515 : }
1381 :
1382 8222296 : Node* EscapeAnalysis::replacement(Node* node) {
1383 16497446 : if (node->id() >= replacements_.size()) return nullptr;
1384 8262110 : return replacements_[node->id()];
1385 : }
1386 :
1387 520037 : bool EscapeAnalysis::SetReplacement(Node* node, Node* rep) {
1388 521642 : bool changed = replacements_[node->id()] != rep;
1389 521248 : replacements_[node->id()] = rep;
1390 394 : return changed;
1391 : }
1392 :
1393 0 : bool EscapeAnalysis::UpdateReplacement(VirtualState* state, Node* node,
1394 : Node* rep) {
1395 0 : if (SetReplacement(node, rep)) {
1396 : if (rep) {
1397 : TRACE("Replacement of #%d is #%d (%s)\n", node->id(), rep->id(),
1398 : rep->op()->mnemonic());
1399 : } else {
1400 : TRACE("Replacement of #%d cleared\n", node->id());
1401 : }
1402 : return true;
1403 : }
1404 0 : return false;
1405 : }
1406 :
1407 7619718 : Node* EscapeAnalysis::ResolveReplacement(Node* node) {
1408 15274740 : while (replacement(node)) {
1409 : node = replacement(node);
1410 : }
1411 7619718 : return node;
1412 : }
1413 :
1414 549724 : Node* EscapeAnalysis::GetReplacement(Node* node) {
1415 : Node* result = nullptr;
1416 1116998 : while (replacement(node)) {
1417 : node = result = replacement(node);
1418 : }
1419 549724 : return result;
1420 : }
1421 :
1422 2503182 : bool EscapeAnalysis::IsVirtual(Node* node) {
1423 5006364 : if (node->id() >= status_analysis_->GetStatusVectorSize()) {
1424 : return false;
1425 : }
1426 2503182 : return status_analysis_->IsVirtual(node);
1427 : }
1428 :
1429 18 : bool EscapeAnalysis::IsEscaped(Node* node) {
1430 36 : if (node->id() >= status_analysis_->GetStatusVectorSize()) {
1431 : return false;
1432 : }
1433 18 : return status_analysis_->IsEscaped(node);
1434 : }
1435 :
1436 7 : bool EscapeAnalysis::CompareVirtualObjects(Node* left, Node* right) {
1437 : DCHECK(IsVirtual(left) && IsVirtual(right));
1438 7 : left = ResolveReplacement(left);
1439 7 : right = ResolveReplacement(right);
1440 7 : if (IsEquivalentPhi(left, right)) {
1441 : return true;
1442 : }
1443 7 : return false;
1444 : }
1445 :
1446 : namespace {
1447 :
1448 : bool IsOffsetForFieldAccessCorrect(const FieldAccess& access) {
1449 : #if V8_TARGET_LITTLE_ENDIAN
1450 15964 : return (access.offset % kPointerSize) == 0;
1451 : #else
1452 : return ((access.offset +
1453 : (1 << ElementSizeLog2Of(access.machine_type.representation()))) %
1454 : kPointerSize) == 0;
1455 : #endif
1456 : }
1457 :
1458 1001069 : int OffsetForFieldAccess(Node* node) {
1459 1001069 : FieldAccess access = FieldAccessOf(node->op());
1460 : DCHECK(IsOffsetForFieldAccessCorrect(access));
1461 1001069 : return access.offset / kPointerSize;
1462 : }
1463 :
1464 148680 : int OffsetForElementAccess(Node* node, int index) {
1465 148680 : ElementAccess access = ElementAccessOf(node->op());
1466 : DCHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
1467 : kPointerSizeLog2);
1468 : DCHECK_EQ(access.header_size % kPointerSize, 0);
1469 148680 : return access.header_size / kPointerSize + index;
1470 : }
1471 :
1472 : } // namespace
1473 :
1474 47892 : void EscapeAnalysis::ProcessLoadFromPhi(int offset, Node* from, Node* load,
1475 0 : VirtualState* state) {
1476 : TRACE("Load #%d from phi #%d", load->id(), from->id());
1477 :
1478 15964 : cache_->fields().clear();
1479 95784 : for (int i = 0; i < load->op()->ValueInputCount(); ++i) {
1480 15964 : Node* input = NodeProperties::GetValueInput(load, i);
1481 15964 : cache_->fields().push_back(input);
1482 : }
1483 :
1484 : cache_->LoadVirtualObjectsForFieldsFrom(state,
1485 15964 : status_analysis_->GetAliasMap());
1486 47892 : if (cache_->objects().size() == cache_->fields().size()) {
1487 0 : cache_->GetFields(offset);
1488 0 : if (cache_->fields().size() == cache_->objects().size()) {
1489 : Node* rep = replacement(load);
1490 0 : if (!rep || !IsEquivalentPhi(rep, cache_->fields())) {
1491 0 : int value_input_count = static_cast<int>(cache_->fields().size());
1492 : Type* phi_type = Type::None();
1493 0 : for (Node* input : cache_->fields()) {
1494 : Type* input_type = NodeProperties::GetType(input);
1495 0 : phi_type = Type::Union(phi_type, input_type, graph()->zone());
1496 : }
1497 0 : cache_->fields().push_back(NodeProperties::GetControlInput(from));
1498 : Node* phi = graph()->NewNode(
1499 : common()->Phi(MachineRepresentation::kTagged, value_input_count),
1500 0 : value_input_count + 1, &cache_->fields().front());
1501 : NodeProperties::SetType(phi, phi_type);
1502 0 : status_analysis_->ResizeStatusVector();
1503 : SetReplacement(load, phi);
1504 : TRACE(" got phi created.\n");
1505 : } else {
1506 : TRACE(" has already phi #%d.\n", rep->id());
1507 : }
1508 : } else {
1509 : TRACE(" has incomplete field info.\n");
1510 : }
1511 : } else {
1512 : TRACE(" has incomplete virtual object info.\n");
1513 : }
1514 15964 : }
1515 :
1516 1087166 : void EscapeAnalysis::ProcessLoadField(Node* node) {
1517 : DCHECK_EQ(node->opcode(), IrOpcode::kLoadField);
1518 535601 : ForwardVirtualState(node);
1519 945395 : Node* from = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1520 1071202 : VirtualState* state = virtual_states_[node->id()];
1521 535601 : if (VirtualObject* object = GetVirtualObject(state, from)) {
1522 125807 : if (!object->IsTracked()) return;
1523 : int offset = OffsetForFieldAccess(node);
1524 251614 : if (static_cast<size_t>(offset) >= object->field_count()) {
1525 : // We have a load from a field that is not inside the {object}. This
1526 : // can only happen with conflicting type feedback and for dead {node}s.
1527 : // For now, we just mark the {object} as escaping.
1528 : // TODO(turbofan): Consider introducing an Undefined or None operator
1529 : // that we can replace this load with, since we know it's dead code.
1530 17 : if (status_analysis_->SetEscaped(from)) {
1531 : TRACE(
1532 : "Setting #%d (%s) to escaped because load field #%d from "
1533 : "offset %d outside of object\n",
1534 : from->id(), from->op()->mnemonic(), node->id(), offset);
1535 : }
1536 : return;
1537 : }
1538 : Node* value = object->GetField(offset);
1539 125790 : if (value) {
1540 23054 : value = ResolveReplacement(value);
1541 : }
1542 : // Record that the load has this alias.
1543 : UpdateReplacement(state, node, value);
1544 425758 : } else if (from->opcode() == IrOpcode::kPhi &&
1545 15964 : IsOffsetForFieldAccessCorrect(FieldAccessOf(node->op()))) {
1546 : int offset = OffsetForFieldAccess(node);
1547 : // Only binary phis are supported for now.
1548 15964 : ProcessLoadFromPhi(offset, from, node, state);
1549 : } else {
1550 : UpdateReplacement(state, node, nullptr);
1551 : }
1552 : }
1553 :
1554 41565 : void EscapeAnalysis::ProcessCheckMaps(Node* node) {
1555 : DCHECK_EQ(node->opcode(), IrOpcode::kCheckMaps);
1556 41445 : ForwardVirtualState(node);
1557 41445 : Node* checked = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1558 41445 : if (FLAG_turbo_experimental) {
1559 120 : VirtualState* state = virtual_states_[node->id()];
1560 60 : if (VirtualObject* object = GetVirtualObject(state, checked)) {
1561 60 : if (!object->IsTracked()) {
1562 0 : if (status_analysis_->SetEscaped(node)) {
1563 : TRACE(
1564 : "Setting #%d (%s) to escaped because checked object #%i is not "
1565 : "tracked\n",
1566 : node->id(), node->op()->mnemonic(), object->id());
1567 : }
1568 60 : return;
1569 : }
1570 60 : CheckMapsParameters params = CheckMapsParametersOf(node->op());
1571 :
1572 60 : Node* value = object->GetField(HeapObject::kMapOffset / kPointerSize);
1573 60 : if (value) {
1574 60 : value = ResolveReplacement(value);
1575 : // TODO(tebbi): We want to extend this beyond constant folding with a
1576 : // CheckMapsValue operator that takes the load-eliminated map value as
1577 : // input.
1578 180 : if (value->opcode() == IrOpcode::kHeapConstant &&
1579 : params.maps().contains(ZoneHandleSet<Map>(
1580 180 : Handle<Map>::cast(OpParameter<Handle<HeapObject>>(value))))) {
1581 : TRACE("CheckMaps #%i seems to be redundant (until now).\n",
1582 : node->id());
1583 : return;
1584 : }
1585 : }
1586 : }
1587 : }
1588 41385 : if (status_analysis_->SetEscaped(node)) {
1589 : TRACE("Setting #%d (%s) to escaped (checking #%i)\n", node->id(),
1590 : node->op()->mnemonic(), checked->id());
1591 : }
1592 : }
1593 :
1594 34662 : void EscapeAnalysis::ProcessLoadElement(Node* node) {
1595 : DCHECK_EQ(node->opcode(), IrOpcode::kLoadElement);
1596 17331 : ForwardVirtualState(node);
1597 18542 : Node* from = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1598 34662 : VirtualState* state = virtual_states_[node->id()];
1599 : Node* index_node = node->InputAt(1);
1600 : NumberMatcher index(index_node);
1601 : DCHECK(index_node->opcode() != IrOpcode::kInt32Constant &&
1602 : index_node->opcode() != IrOpcode::kInt64Constant &&
1603 : index_node->opcode() != IrOpcode::kFloat32Constant &&
1604 : index_node->opcode() != IrOpcode::kFloat64Constant);
1605 17331 : if (index.HasValue()) {
1606 1234 : if (VirtualObject* object = GetVirtualObject(state, from)) {
1607 23 : if (!object->IsTracked()) return;
1608 23 : int offset = OffsetForElementAccess(node, index.Value());
1609 46 : if (static_cast<size_t>(offset) >= object->field_count()) return;
1610 : Node* value = object->GetField(offset);
1611 23 : if (value) {
1612 0 : value = ResolveReplacement(value);
1613 : }
1614 : // Record that the load has this alias.
1615 : UpdateReplacement(state, node, value);
1616 1211 : } else if (from->opcode() == IrOpcode::kPhi) {
1617 0 : int offset = OffsetForElementAccess(node, index.Value());
1618 0 : ProcessLoadFromPhi(offset, from, node, state);
1619 : } else {
1620 : UpdateReplacement(state, node, nullptr);
1621 : }
1622 : } else {
1623 : // We have a load from a non-const index, cannot eliminate object.
1624 16097 : if (status_analysis_->SetEscaped(from)) {
1625 : TRACE(
1626 : "Setting #%d (%s) to escaped because load element #%d from non-const "
1627 : "index #%d (%s)\n",
1628 : from->id(), from->op()->mnemonic(), node->id(), index_node->id(),
1629 : index_node->op()->mnemonic());
1630 : }
1631 : }
1632 : }
1633 :
1634 2181932 : void EscapeAnalysis::ProcessStoreField(Node* node) {
1635 : DCHECK_EQ(node->opcode(), IrOpcode::kStoreField);
1636 1090966 : ForwardVirtualState(node);
1637 1090966 : Node* to = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1638 2181932 : VirtualState* state = virtual_states_[node->id()];
1639 1090966 : if (VirtualObject* object = GetVirtualObject(state, to)) {
1640 859298 : if (!object->IsTracked()) return;
1641 : int offset = OffsetForFieldAccess(node);
1642 1718596 : if (static_cast<size_t>(offset) >= object->field_count()) {
1643 : // We have a store to a field that is not inside the {object}. This
1644 : // can only happen with conflicting type feedback and for dead {node}s.
1645 : // For now, we just mark the {object} as escaping.
1646 : // TODO(turbofan): Consider just eliminating the store in the reducer
1647 : // pass, as it's dead code anyways.
1648 0 : if (status_analysis_->SetEscaped(to)) {
1649 : TRACE(
1650 : "Setting #%d (%s) to escaped because store field #%d to "
1651 : "offset %d outside of object\n",
1652 : to->id(), to->op()->mnemonic(), node->id(), offset);
1653 : }
1654 : return;
1655 : }
1656 859298 : Node* val = ResolveReplacement(NodeProperties::GetValueInput(node, 1));
1657 : // TODO(mstarzinger): The following is a workaround to not track some well
1658 : // known raw fields. We only ever store default initial values into these
1659 : // fields which are hard-coded in {TranslatedState::MaterializeAt} as well.
1660 859298 : if (val->opcode() == IrOpcode::kInt32Constant ||
1661 : val->opcode() == IrOpcode::kInt64Constant) {
1662 : DCHECK(FieldAccessOf(node->op()).offset == JSFunction::kCodeEntryOffset ||
1663 : FieldAccessOf(node->op()).offset == Name::kHashFieldOffset);
1664 0 : val = slot_not_analyzed_;
1665 : }
1666 859298 : if (object->GetField(offset) != val) {
1667 756135 : object = CopyForModificationAt(object, state, node);
1668 756135 : object->SetField(offset, val);
1669 : }
1670 : }
1671 : }
1672 :
1673 156038 : void EscapeAnalysis::ProcessStoreElement(Node* node) {
1674 : DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement);
1675 156038 : ForwardVirtualState(node);
1676 156038 : Node* to = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
1677 : Node* index_node = node->InputAt(1);
1678 : NumberMatcher index(index_node);
1679 : DCHECK(index_node->opcode() != IrOpcode::kInt32Constant &&
1680 : index_node->opcode() != IrOpcode::kInt64Constant &&
1681 : index_node->opcode() != IrOpcode::kFloat32Constant &&
1682 : index_node->opcode() != IrOpcode::kFloat64Constant);
1683 312076 : VirtualState* state = virtual_states_[node->id()];
1684 156038 : if (index.HasValue()) {
1685 148706 : if (VirtualObject* object = GetVirtualObject(state, to)) {
1686 148657 : if (!object->IsTracked()) return;
1687 148657 : int offset = OffsetForElementAccess(node, index.Value());
1688 297314 : if (static_cast<size_t>(offset) >= object->field_count()) return;
1689 148657 : Node* val = ResolveReplacement(NodeProperties::GetValueInput(node, 2));
1690 148657 : if (object->GetField(offset) != val) {
1691 148121 : object = CopyForModificationAt(object, state, node);
1692 148121 : object->SetField(offset, val);
1693 : }
1694 : }
1695 : } else {
1696 : // We have a store to a non-const index, cannot eliminate object.
1697 7332 : if (status_analysis_->SetEscaped(to)) {
1698 : TRACE(
1699 : "Setting #%d (%s) to escaped because store element #%d to non-const "
1700 : "index #%d (%s)\n",
1701 : to->id(), to->op()->mnemonic(), node->id(), index_node->id(),
1702 : index_node->op()->mnemonic());
1703 : }
1704 7332 : if (VirtualObject* object = GetVirtualObject(state, to)) {
1705 4773 : if (!object->IsTracked()) return;
1706 4773 : if (!object->AllFieldsClear()) {
1707 2115 : object = CopyForModificationAt(object, state, node);
1708 2115 : object->ClearAllFields();
1709 : TRACE("Cleared all fields of @%d:#%d\n",
1710 : status_analysis_->GetAlias(object->id()), object->id());
1711 : }
1712 : }
1713 : }
1714 : }
1715 :
1716 79500 : Node* EscapeAnalysis::GetOrCreateObjectState(Node* effect, Node* node) {
1717 95897 : if ((node->opcode() == IrOpcode::kFinishRegion ||
1718 70972 : node->opcode() == IrOpcode::kAllocate) &&
1719 15349 : IsVirtual(node)) {
1720 30084 : if (VirtualObject* vobj = GetVirtualObject(virtual_states_[effect->id()],
1721 30084 : ResolveReplacement(node))) {
1722 15042 : if (Node* object_state = vobj->GetObjectState()) {
1723 : return object_state;
1724 : } else {
1725 8835 : cache_->fields().clear();
1726 103124 : for (size_t i = 0; i < vobj->field_count(); ++i) {
1727 42727 : if (Node* field = vobj->GetField(i)) {
1728 85454 : cache_->fields().push_back(ResolveReplacement(field));
1729 : } else {
1730 : return nullptr;
1731 : }
1732 : }
1733 17670 : int input_count = static_cast<int>(cache_->fields().size());
1734 : Node* new_object_state =
1735 : graph()->NewNode(common()->ObjectState(input_count), input_count,
1736 17670 : &cache_->fields().front());
1737 : NodeProperties::SetType(new_object_state, Type::OtherInternal());
1738 : vobj->SetObjectState(new_object_state);
1739 : TRACE(
1740 : "Creating object state #%d for vobj %p (from node #%d) at effect "
1741 : "#%d\n",
1742 : new_object_state->id(), static_cast<void*>(vobj), node->id(),
1743 : effect->id());
1744 : // Now fix uses of other objects.
1745 103124 : for (size_t i = 0; i < vobj->field_count(); ++i) {
1746 42727 : if (Node* field = vobj->GetField(i)) {
1747 42727 : if (Node* field_object_state =
1748 42727 : GetOrCreateObjectState(effect, field)) {
1749 : NodeProperties::ReplaceValueInput(
1750 2146 : new_object_state, field_object_state, static_cast<int>(i));
1751 : }
1752 : }
1753 : }
1754 : return new_object_state;
1755 : }
1756 : }
1757 : }
1758 : return nullptr;
1759 : }
1760 :
1761 111235 : bool EscapeAnalysis::IsCyclicObjectState(Node* effect, Node* node) {
1762 170658 : if ((node->opcode() == IrOpcode::kFinishRegion ||
1763 111708 : node->opcode() == IrOpcode::kAllocate) &&
1764 17586 : IsVirtual(node)) {
1765 34226 : if (VirtualObject* vobj = GetVirtualObject(virtual_states_[effect->id()],
1766 34226 : ResolveReplacement(node))) {
1767 34226 : if (cycle_detection_.find(vobj) != cycle_detection_.end()) return true;
1768 : cycle_detection_.insert(vobj);
1769 : bool cycle_detected = false;
1770 196678 : for (size_t i = 0; i < vobj->field_count(); ++i) {
1771 81226 : if (Node* field = vobj->GetField(i)) {
1772 81226 : if (IsCyclicObjectState(effect, field)) cycle_detected = true;
1773 : }
1774 : }
1775 : cycle_detection_.erase(vobj);
1776 17113 : return cycle_detected;
1777 : }
1778 : }
1779 : return false;
1780 : }
1781 :
1782 0 : void EscapeAnalysis::DebugPrintState(VirtualState* state) {
1783 0 : PrintF("Dumping virtual state %p\n", static_cast<void*>(state));
1784 0 : for (Alias alias = 0; alias < status_analysis_->AliasCount(); ++alias) {
1785 0 : if (VirtualObject* object = state->VirtualObjectFromAlias(alias)) {
1786 : PrintF(" Alias @%d: Object #%d with %zu fields\n", alias, object->id(),
1787 0 : object->field_count());
1788 0 : for (size_t i = 0; i < object->field_count(); ++i) {
1789 0 : if (Node* f = object->GetField(i)) {
1790 0 : PrintF(" Field %zu = #%d (%s)\n", i, f->id(), f->op()->mnemonic());
1791 : }
1792 : }
1793 : }
1794 : }
1795 0 : }
1796 :
1797 0 : void EscapeAnalysis::DebugPrint() {
1798 : ZoneVector<VirtualState*> object_states(zone());
1799 0 : for (NodeId id = 0; id < virtual_states_.size(); id++) {
1800 0 : if (VirtualState* states = virtual_states_[id]) {
1801 0 : if (std::find(object_states.begin(), object_states.end(), states) ==
1802 : object_states.end()) {
1803 0 : object_states.push_back(states);
1804 : }
1805 : }
1806 : }
1807 0 : for (size_t n = 0; n < object_states.size(); n++) {
1808 0 : DebugPrintState(object_states[n]);
1809 : }
1810 0 : }
1811 :
1812 5956265 : VirtualObject* EscapeAnalysis::GetVirtualObject(VirtualState* state,
1813 5956265 : Node* node) {
1814 11912530 : if (node->id() >= status_analysis_->GetAliasMap().size()) return nullptr;
1815 : Alias alias = status_analysis_->GetAlias(node->id());
1816 11903452 : if (alias >= state->size()) return nullptr;
1817 1516824 : return state->VirtualObjectFromAlias(alias);
1818 : }
1819 :
1820 39769 : bool EscapeAnalysis::ExistsVirtualAllocate() {
1821 28756374 : for (size_t id = 0; id < status_analysis_->GetAliasMap().size(); ++id) {
1822 : Alias alias = status_analysis_->GetAlias(static_cast<NodeId>(id));
1823 14348523 : if (alias < EscapeStatusAnalysis::kUntrackable) {
1824 166059 : if (status_analysis_->IsVirtual(static_cast<int>(id))) {
1825 : return true;
1826 : }
1827 : }
1828 : }
1829 : return false;
1830 : }
1831 :
1832 942975 : Graph* EscapeAnalysis::graph() const { return status_analysis_->graph(); }
1833 :
1834 : } // namespace compiler
1835 : } // namespace internal
1836 : } // namespace v8
|
