Line data Source code
1 : // Copyright 2017 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 "src/bootstrapper.h"
8 : #include "src/compiler/linkage.h"
9 : #include "src/compiler/node-matchers.h"
10 : #include "src/compiler/operator-properties.h"
11 : #include "src/compiler/simplified-operator.h"
12 : #include "src/zone/zone-list-inl.h" // TODO(mstarzinger): Fix zone-handle-set.h instead!
13 :
14 : #ifdef DEBUG
15 : #define TRACE(...) \
16 : do { \
17 : if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
18 : } while (false)
19 : #else
20 : #define TRACE(...)
21 : #endif
22 :
23 : namespace v8 {
24 : namespace internal {
25 : namespace compiler {
26 :
27 : template <class T>
28 : class Sidetable {
29 : public:
30 : explicit Sidetable(Zone* zone) : map_(zone) {}
31 114209913 : T& operator[](const Node* node) {
32 : NodeId id = node->id();
33 342629743 : if (id >= map_.size()) {
34 2350347 : map_.resize(id + 1);
35 : }
36 114209917 : return map_[id];
37 : }
38 :
39 : private:
40 : ZoneVector<T> map_;
41 : };
42 :
43 : template <class T>
44 : class SparseSidetable {
45 : public:
46 : explicit SparseSidetable(Zone* zone, T def_value = T())
47 886719 : : def_value_(std::move(def_value)), map_(zone) {}
48 66229503 : void Set(const Node* node, T value) {
49 122805074 : auto iter = map_.find(node->id());
50 61402441 : if (iter != map_.end()) {
51 1865362 : iter->second = std::move(value);
52 59536904 : } else if (value != def_value_) {
53 5074831 : map_.insert(iter, std::make_pair(node->id(), std::move(value)));
54 : }
55 61402266 : }
56 155566910 : const T& Get(const Node* node) const {
57 311133963 : auto iter = map_.find(node->id());
58 155567053 : return iter != map_.end() ? iter->second : def_value_;
59 : }
60 :
61 : private:
62 : T def_value_;
63 : ZoneUnorderedMap<NodeId, T> map_;
64 : };
65 :
66 : // Keeps track of the changes to the current node during reduction.
67 : // Encapsulates the current state of the IR graph and the reducer state like
68 : // side-tables. All access to the IR and the reducer state should happen through
69 : // a ReduceScope to ensure that changes and dependencies are tracked and all
70 : // necessary node revisitations happen.
71 : class ReduceScope {
72 : public:
73 : typedef EffectGraphReducer::Reduction Reduction;
74 : explicit ReduceScope(Node* node, Reduction* reduction)
75 30701485 : : current_node_(node), reduction_(reduction) {}
76 :
77 : protected:
78 : Node* current_node() const { return current_node_; }
79 : Reduction* reduction() { return reduction_; }
80 :
81 : private:
82 : Node* current_node_;
83 : Reduction* reduction_;
84 : };
85 :
86 : // A VariableTracker object keeps track of the values of variables at all points
87 : // of the effect chain and introduces new phi nodes when necessary.
88 : // Initially and by default, variables are mapped to nullptr, which means that
89 : // the variable allocation point does not dominate the current point on the
90 : // effect chain. We map variables that represent uninitialized memory to the
91 : // Dead node to ensure it is not read.
92 : // Unmapped values are impossible by construction, it is indistinguishable if a
93 : // PersistentMap does not contain an element or maps it to the default element.
94 : class VariableTracker {
95 : private:
96 : // The state of all variables at one point in the effect chain.
97 : class State {
98 : typedef PersistentMap<Variable, Node*> Map;
99 :
100 : public:
101 : explicit State(Zone* zone) : map_(zone) {}
102 7767536 : Node* Get(Variable var) const {
103 7767536 : CHECK(var != Variable::Invalid());
104 7767536 : return map_.Get(var);
105 : }
106 5411911 : void Set(Variable var, Node* node) {
107 5411911 : CHECK(var != Variable::Invalid());
108 10823819 : return map_.Set(var, node);
109 : }
110 395297 : Map::iterator begin() const { return map_.begin(); }
111 395295 : Map::iterator end() const { return map_.end(); }
112 59792798 : bool operator!=(const State& other) const { return map_ != other.map_; }
113 :
114 : private:
115 : Map map_;
116 : };
117 :
118 : public:
119 : VariableTracker(JSGraph* graph, EffectGraphReducer* reducer, Zone* zone);
120 755065 : Variable NewVariable() { return Variable(next_variable_++); }
121 322621 : Node* Get(Variable var, Node* effect) { return table_.Get(effect).Get(var); }
122 : Zone* zone() { return zone_; }
123 :
124 : class Scope : public ReduceScope {
125 : public:
126 : Scope(VariableTracker* tracker, Node* node, Reduction* reduction);
127 : ~Scope();
128 22033 : Node* Get(Variable var) { return current_state_.Get(var); }
129 2563225 : void Set(Variable var, Node* node) { current_state_.Set(var, node); }
130 :
131 : private:
132 : VariableTracker* states_;
133 : State current_state_;
134 : };
135 :
136 : private:
137 : State MergeInputs(Node* effect_phi);
138 : Zone* zone_;
139 : JSGraph* graph_;
140 : SparseSidetable<State> table_;
141 : ZoneVector<Node*> buffer_;
142 : EffectGraphReducer* reducer_;
143 : int next_variable_ = 0;
144 :
145 : DISALLOW_COPY_AND_ASSIGN(VariableTracker);
146 : };
147 :
148 : // Encapsulates the current state of the escape analysis reducer to preserve
149 : // invariants regarding changes and re-visitation.
150 : class EscapeAnalysisTracker : public ZoneObject {
151 : public:
152 443360 : EscapeAnalysisTracker(JSGraph* jsgraph, EffectGraphReducer* reducer,
153 : Zone* zone)
154 : : virtual_objects_(zone),
155 : replacements_(zone),
156 : variable_states_(jsgraph, reducer, zone),
157 : jsgraph_(jsgraph),
158 443359 : zone_(zone) {}
159 :
160 : class Scope : public VariableTracker::Scope {
161 : public:
162 : Scope(EffectGraphReducer* reducer, EscapeAnalysisTracker* tracker,
163 : Node* node, Reduction* reduction)
164 : : VariableTracker::Scope(&tracker->variable_states_, node, reduction),
165 : tracker_(tracker),
166 30701370 : reducer_(reducer) {}
167 3983019 : const VirtualObject* GetVirtualObject(Node* node) {
168 3983019 : VirtualObject* vobject = tracker_->virtual_objects_.Get(node);
169 3983019 : if (vobject) vobject->AddDependency(current_node());
170 3983019 : return vobject;
171 : }
172 : // Create or retrieve a virtual object for the current node.
173 260110 : const VirtualObject* InitVirtualObject(int size) {
174 : DCHECK_EQ(IrOpcode::kAllocate, current_node()->opcode());
175 518708 : VirtualObject* vobject = tracker_->virtual_objects_.Get(current_node());
176 260110 : if (vobject) {
177 135398 : CHECK(vobject->size() == size);
178 : } else {
179 124712 : vobject = tracker_->NewVirtualObject(size);
180 : }
181 260110 : if (vobject) vobject->AddDependency(current_node());
182 260110 : vobject_ = vobject;
183 260110 : return vobject;
184 : }
185 :
186 : void SetVirtualObject(Node* object) {
187 267905 : vobject_ = tracker_->virtual_objects_.Get(object);
188 : }
189 :
190 20913288 : void SetEscaped(Node* node) {
191 20913288 : if (VirtualObject* object = tracker_->virtual_objects_.Get(node)) {
192 22501639 : if (object->HasEscaped()) return;
193 : TRACE("Setting %s#%d to escaped because of use by %s#%d\n",
194 : node->op()->mnemonic(), node->id(),
195 : current_node()->op()->mnemonic(), current_node()->id());
196 : object->SetEscaped();
197 93179 : object->RevisitDependants(reducer_);
198 : }
199 : }
200 : // The inputs of the current node have to be accessed through the scope to
201 : // ensure that they respect the node replacements.
202 20629393 : Node* ValueInput(int i) {
203 : return tracker_->ResolveReplacement(
204 41258789 : NodeProperties::GetValueInput(current_node(), i));
205 : }
206 3258255 : Node* ContextInput() {
207 : return tracker_->ResolveReplacement(
208 6516512 : NodeProperties::GetContextInput(current_node()));
209 : }
210 :
211 996354 : void SetReplacement(Node* replacement) {
212 996354 : replacement_ = replacement;
213 : vobject_ =
214 996354 : replacement ? tracker_->virtual_objects_.Get(replacement) : nullptr;
215 : TRACE("Set %s#%d as replacement.\n", replacement->op()->mnemonic(),
216 : replacement->id());
217 996354 : }
218 :
219 957675 : void MarkForDeletion() { SetReplacement(tracker_->jsgraph_->Dead()); }
220 :
221 61402503 : ~Scope() {
222 150374780 : if (replacement_ != tracker_->replacements_[current_node()] ||
223 58270918 : vobject_ != tracker_->virtual_objects_.Get(current_node())) {
224 : reduction()->set_value_changed();
225 : }
226 30701296 : tracker_->replacements_[current_node()] = replacement_;
227 61402580 : tracker_->virtual_objects_.Set(current_node(), vobject_);
228 30701158 : }
229 :
230 : private:
231 : EscapeAnalysisTracker* tracker_;
232 : EffectGraphReducer* reducer_;
233 : VirtualObject* vobject_ = nullptr;
234 : Node* replacement_ = nullptr;
235 : };
236 :
237 52813924 : Node* GetReplacementOf(Node* node) { return replacements_[node]; }
238 : Node* ResolveReplacement(Node* node) {
239 23887653 : if (Node* replacement = GetReplacementOf(node)) {
240 : // Replacements cannot have replacements. This is important to ensure
241 : // re-visitation: If a replacement is replaced, then all nodes accessing
242 : // the replacement have to be updated.
243 : DCHECK_NULL(GetReplacementOf(replacement));
244 : return replacement;
245 : }
246 : return node;
247 : }
248 :
249 : private:
250 : friend class EscapeAnalysisResult;
251 : static const size_t kMaxTrackedObjects = 100;
252 :
253 124712 : VirtualObject* NewVirtualObject(int size) {
254 124712 : if (next_object_id_ >= kMaxTrackedObjects) return nullptr;
255 : return new (zone_)
256 246400 : VirtualObject(&variable_states_, next_object_id_++, size);
257 : }
258 :
259 : SparseSidetable<VirtualObject*> virtual_objects_;
260 : Sidetable<Node*> replacements_;
261 : VariableTracker variable_states_;
262 : VirtualObject::Id next_object_id_ = 0;
263 : JSGraph* const jsgraph_;
264 : Zone* const zone_;
265 :
266 : DISALLOW_COPY_AND_ASSIGN(EscapeAnalysisTracker);
267 : };
268 :
269 443358 : EffectGraphReducer::EffectGraphReducer(
270 : Graph* graph, std::function<void(Node*, Reduction*)> reduce, Zone* zone)
271 : : graph_(graph),
272 : state_(graph, kNumStates),
273 : revisit_(zone),
274 : stack_(zone),
275 1330077 : reduce_(reduce) {}
276 :
277 443359 : void EffectGraphReducer::ReduceFrom(Node* node) {
278 : // Perform DFS and eagerly trigger revisitation as soon as possible.
279 : // A stack element {node, i} indicates that input i of node should be visited
280 : // next.
281 : DCHECK(stack_.empty());
282 886832 : stack_.push({node, 0});
283 127684090 : while (!stack_.empty()) {
284 126797257 : Node* current = stack_.top().node;
285 : int& input_index = stack_.top().input_index;
286 253594514 : if (input_index < current->InputCount()) {
287 : Node* input = current->InputAt(input_index);
288 96095898 : input_index++;
289 96095642 : switch (state_.Get(input)) {
290 : case State::kVisited:
291 : // The input is already reduced.
292 : break;
293 : case State::kOnStack:
294 : // The input is on the DFS stack right now, so it will be revisited
295 : // later anyway.
296 : break;
297 : case State::kUnvisited:
298 : case State::kRevisit: {
299 : state_.Set(input, State::kOnStack);
300 56767151 : stack_.push({input, 0});
301 28383700 : break;
302 : }
303 : }
304 : } else {
305 : stack_.pop();
306 30701359 : Reduction reduction;
307 30701359 : reduce_(current, &reduction);
308 219890885 : for (Edge edge : current->use_edges()) {
309 : // Mark uses for revisitation.
310 : Node* use = edge.from();
311 94594846 : if (NodeProperties::IsEffectEdge(edge)) {
312 13086957 : if (reduction.effect_changed()) Revisit(use);
313 : } else {
314 81508744 : if (reduction.value_changed()) Revisit(use);
315 : }
316 : }
317 : state_.Set(current, State::kVisited);
318 : // Process the revisitation buffer immediately. This improves performance
319 : // of escape analysis. Using a stack for {revisit_} reverses the order in
320 : // which the revisitation happens. This also seems to improve performance.
321 32576017 : while (!revisit_.empty()) {
322 1874794 : Node* revisit = revisit_.top();
323 1874794 : if (state_.Get(revisit) == State::kRevisit) {
324 : state_.Set(revisit, State::kOnStack);
325 3749588 : stack_.push({revisit, 0});
326 : }
327 : revisit_.pop();
328 : }
329 : }
330 : }
331 443360 : }
332 :
333 9479814 : void EffectGraphReducer::Revisit(Node* node) {
334 18959628 : if (state_.Get(node) == State::kVisited) {
335 : TRACE(" Queueing for revisit: %s#%d\n", node->op()->mnemonic(),
336 : node->id());
337 : state_.Set(node, State::kRevisit);
338 : revisit_.push(node);
339 : }
340 9479814 : }
341 :
342 0 : VariableTracker::VariableTracker(JSGraph* graph, EffectGraphReducer* reducer,
343 : Zone* zone)
344 : : zone_(zone),
345 : graph_(graph),
346 : table_(zone, State(zone)),
347 : buffer_(zone),
348 886718 : reducer_(reducer) {}
349 :
350 61402970 : VariableTracker::Scope::Scope(VariableTracker* states, Node* node,
351 : Reduction* reduction)
352 : : ReduceScope(node, reduction),
353 : states_(states),
354 30701485 : current_state_(states->zone_) {
355 30701485 : switch (node->opcode()) {
356 : case IrOpcode::kEffectPhi:
357 395296 : current_state_ = states_->MergeInputs(node);
358 395296 : break;
359 : default:
360 30306189 : int effect_inputs = node->op()->EffectInputCount();
361 30306189 : if (effect_inputs == 1) {
362 : current_state_ =
363 12095168 : states_->table_.Get(NodeProperties::GetEffectInput(node, 0));
364 : } else {
365 : DCHECK_EQ(0, effect_inputs);
366 : }
367 : }
368 30701504 : }
369 :
370 30701260 : VariableTracker::Scope::~Scope() {
371 92103915 : if (!reduction()->effect_changed() &&
372 30701277 : states_->table_.Get(current_node()) != current_state_) {
373 : reduction()->set_effect_changed();
374 : }
375 30701319 : states_->table_.Set(current_node(), current_state_);
376 30701146 : }
377 :
378 395296 : VariableTracker::State VariableTracker::MergeInputs(Node* effect_phi) {
379 : // A variable that is mapped to [nullptr] was not assigned a value on every
380 : // execution path to the current effect phi. Relying on the invariant that
381 : // every variable is initialized (at least with a sentinel like the Dead
382 : // node), this means that the variable initialization does not dominate the
383 : // current point. So for loop effect phis, we can keep nullptr for a variable
384 : // as long as the first input of the loop has nullptr for this variable. For
385 : // non-loop effect phis, we can even keep it nullptr as long as any input has
386 : // nullptr.
387 : DCHECK_EQ(IrOpcode::kEffectPhi, effect_phi->opcode());
388 395296 : int arity = effect_phi->op()->EffectInputCount();
389 395296 : Node* control = NodeProperties::GetControlInput(effect_phi, 0);
390 : TRACE("control: %s#%d\n", control->op()->mnemonic(), control->id());
391 790594 : bool is_loop = control->opcode() == IrOpcode::kLoop;
392 574651 : buffer_.reserve(arity + 1);
393 :
394 395297 : State first_input = table_.Get(NodeProperties::GetEffectInput(effect_phi, 0));
395 395297 : State result = first_input;
396 6093499 : for (std::pair<Variable, Node*> var_value : first_input) {
397 2849102 : if (Node* value = var_value.second) {
398 2848686 : Variable var = var_value.first;
399 : TRACE("var %i:\n", var.id_);
400 : buffer_.clear();
401 2848686 : buffer_.push_back(value);
402 : bool identical_inputs = true;
403 : int num_defined_inputs = 1;
404 : TRACE(" input 0: %s#%d\n", value->op()->mnemonic(), value->id());
405 7422882 : for (int i = 1; i < arity; ++i) {
406 : Node* next_value =
407 4574196 : table_.Get(NodeProperties::GetEffectInput(effect_phi, i)).Get(var);
408 4574196 : if (next_value != value) identical_inputs = false;
409 4574196 : if (next_value != nullptr) {
410 3702260 : num_defined_inputs++;
411 : TRACE(" input %i: %s#%d\n", i, next_value->op()->mnemonic(),
412 : next_value->id());
413 : } else {
414 : TRACE(" input %i: nullptr\n", i);
415 : }
416 4574196 : buffer_.push_back(next_value);
417 : }
418 :
419 3689484 : Node* old_value = table_.Get(effect_phi).Get(var);
420 : if (old_value) {
421 : TRACE(" old: %s#%d\n", old_value->op()->mnemonic(), old_value->id());
422 : } else {
423 : TRACE(" old: nullptr\n");
424 : }
425 : // Reuse a previously created phi node if possible.
426 3954861 : if (old_value && old_value->opcode() == IrOpcode::kPhi &&
427 265377 : NodeProperties::GetControlInput(old_value, 0) == control) {
428 : // Since a phi node can never dominate its control node,
429 : // [old_value] cannot originate from the inputs. Thus [old_value]
430 : // must have been created by a previous reduction of this [effect_phi].
431 179354 : for (int i = 0; i < arity; ++i) {
432 : NodeProperties::ReplaceValueInput(
433 475044 : old_value, buffer_[i] ? buffer_[i] : graph_->Dead(), i);
434 : // This change cannot affect the rest of the reducer, so there is no
435 : // need to trigger additional revisitations.
436 : }
437 73611 : result.Set(var, old_value);
438 : } else {
439 2775075 : if (num_defined_inputs == 1 && is_loop) {
440 : // For loop effect phis, the variable initialization dominates iff it
441 : // dominates the first input.
442 : DCHECK_EQ(2, arity);
443 : DCHECK_EQ(value, buffer_[0]);
444 202692 : result.Set(var, value);
445 2572383 : } else if (num_defined_inputs < arity) {
446 : // If the variable is undefined on some input of this non-loop effect
447 : // phi, then its initialization does not dominate this point.
448 143833 : result.Set(var, nullptr);
449 : } else {
450 : DCHECK_EQ(num_defined_inputs, arity);
451 : // We only create a phi if the values are different.
452 2428550 : if (identical_inputs) {
453 2370382 : result.Set(var, value);
454 : } else {
455 : TRACE("Creating new phi\n");
456 58168 : buffer_.push_back(control);
457 : Node* phi = graph_->graph()->NewNode(
458 : graph_->common()->Phi(MachineRepresentation::kTagged, arity),
459 174504 : arity + 1, &buffer_.front());
460 : // TODO(tebbi): Computing precise types here is tricky, because of
461 : // the necessary revisitations. If we really need this, we should
462 : // probably do it afterwards.
463 : NodeProperties::SetType(phi, Type::Any());
464 58168 : reducer_->AddRoot(phi);
465 58168 : result.Set(var, phi);
466 : }
467 : }
468 : }
469 : #ifdef DEBUG
470 : if (Node* result_node = result.Get(var)) {
471 : TRACE(" result: %s#%d\n", result_node->op()->mnemonic(),
472 : result_node->id());
473 : } else {
474 : TRACE(" result: nullptr\n");
475 : }
476 : #endif
477 : }
478 : }
479 395295 : return result;
480 : }
481 :
482 : namespace {
483 :
484 : int OffsetOfFieldAccess(const Operator* op) {
485 : DCHECK(op->opcode() == IrOpcode::kLoadField ||
486 : op->opcode() == IrOpcode::kStoreField);
487 928494 : FieldAccess access = FieldAccessOf(op);
488 : return access.offset;
489 : }
490 :
491 39069 : Maybe<int> OffsetOfElementsAccess(const Operator* op, Node* index_node) {
492 : DCHECK(op->opcode() == IrOpcode::kLoadElement ||
493 : op->opcode() == IrOpcode::kStoreElement);
494 : Type* index_type = NodeProperties::GetType(index_node);
495 39069 : if (!index_type->Is(Type::Number())) return Nothing<int>();
496 39069 : double max = index_type->Max();
497 39069 : double min = index_type->Min();
498 39069 : int index = static_cast<int>(min);
499 39069 : if (!(index == min && index == max)) return Nothing<int>();
500 38870 : ElementAccess access = ElementAccessOf(op);
501 : DCHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
502 : kPointerSizeLog2);
503 38870 : return Just(access.header_size + (index << ElementSizeLog2Of(
504 38870 : access.machine_type.representation())));
505 : }
506 :
507 731 : Node* LowerCompareMapsWithoutLoad(Node* checked_map,
508 : ZoneHandleSet<Map> const& checked_against,
509 1462 : JSGraph* jsgraph) {
510 731 : Node* true_node = jsgraph->TrueConstant();
511 731 : Node* false_node = jsgraph->FalseConstant();
512 : Node* replacement = false_node;
513 1462 : for (Handle<Map> map : checked_against) {
514 731 : Node* map_node = jsgraph->HeapConstant(map);
515 : // We cannot create a HeapConstant type here as we are off-thread.
516 : NodeProperties::SetType(map_node, Type::Internal());
517 : Node* comparison = jsgraph->graph()->NewNode(
518 731 : jsgraph->simplified()->ReferenceEqual(), checked_map, map_node);
519 : NodeProperties::SetType(comparison, Type::Boolean());
520 731 : if (replacement == false_node) {
521 : replacement = comparison;
522 : } else {
523 : replacement = jsgraph->graph()->NewNode(
524 : jsgraph->common()->Select(MachineRepresentation::kTaggedPointer),
525 0 : comparison, true_node, replacement);
526 : NodeProperties::SetType(replacement, Type::Boolean());
527 : }
528 : }
529 731 : return replacement;
530 : }
531 :
532 70409157 : void ReduceNode(const Operator* op, EscapeAnalysisTracker::Scope* current,
533 : JSGraph* jsgraph) {
534 30701267 : switch (op->opcode()) {
535 : case IrOpcode::kAllocate: {
536 260110 : NumberMatcher size(current->ValueInput(0));
537 260111 : if (!size.HasValue()) break;
538 260110 : int size_int = static_cast<int>(size.Value());
539 260110 : if (size_int != size.Value()) break;
540 260110 : if (const VirtualObject* vobject = current->InitVirtualObject(size_int)) {
541 : // Initialize with dead nodes as a sentinel for uninitialized memory.
542 2128252 : for (Variable field : *vobject) {
543 1611057 : current->Set(field, jsgraph->Dead());
544 : }
545 : }
546 : break;
547 : }
548 : case IrOpcode::kFinishRegion:
549 267905 : current->SetVirtualObject(current->ValueInput(0));
550 : break;
551 : case IrOpcode::kStoreField: {
552 2212020 : Node* object = current->ValueInput(0);
553 2212020 : Node* value = current->ValueInput(1);
554 3951376 : const VirtualObject* vobject = current->GetVirtualObject(object);
555 : Variable var;
556 8375425 : if (vobject && !vobject->HasEscaped() &&
557 4039421 : vobject->FieldAt(OffsetOfFieldAccess(op)).To(&var)) {
558 : current->Set(var, value);
559 913699 : current->MarkForDeletion();
560 : } else {
561 1298324 : current->SetEscaped(object);
562 1298324 : current->SetEscaped(value);
563 : }
564 : break;
565 : }
566 : case IrOpcode::kStoreElement: {
567 93471 : Node* object = current->ValueInput(0);
568 93471 : Node* index = current->ValueInput(1);
569 93471 : Node* value = current->ValueInput(2);
570 175075 : const VirtualObject* vobject = current->GetVirtualObject(object);
571 : int offset;
572 : Variable var;
573 268546 : if (vobject && !vobject->HasEscaped() &&
574 302379 : OffsetOfElementsAccess(op, index).To(&offset) &&
575 131940 : vobject->FieldAt(offset).To(&var)) {
576 : current->Set(var, value);
577 38469 : current->MarkForDeletion();
578 : } else {
579 55002 : current->SetEscaped(value);
580 55002 : current->SetEscaped(object);
581 : }
582 : break;
583 : }
584 : case IrOpcode::kLoadField: {
585 1191111 : Node* object = current->ValueInput(0);
586 1293917 : const VirtualObject* vobject = current->GetVirtualObject(object);
587 : Variable var;
588 3676141 : if (vobject && !vobject->HasEscaped() &&
589 1220702 : vobject->FieldAt(OffsetOfFieldAccess(op)).To(&var)) {
590 14770 : current->SetReplacement(current->Get(var));
591 : } else {
592 : // TODO(tebbi): At the moment, we mark objects as escaping if there
593 : // is a load from an invalid location to avoid dead nodes. This is a
594 : // workaround that should be removed once we can handle dead nodes
595 : // everywhere.
596 1176342 : current->SetEscaped(object);
597 : }
598 : break;
599 : }
600 : case IrOpcode::kLoadElement: {
601 28605 : Node* object = current->ValueInput(0);
602 28605 : Node* index = current->ValueInput(1);
603 30363 : const VirtualObject* vobject = current->GetVirtualObject(object);
604 : int offset;
605 : Variable var;
606 58968 : if (vobject && !vobject->HasEscaped() &&
607 58781 : OffsetOfElementsAccess(op, index).To(&offset) &&
608 29006 : vobject->FieldAt(offset).To(&var)) {
609 401 : current->SetReplacement(current->Get(var));
610 : } else {
611 28204 : current->SetEscaped(object);
612 : }
613 : break;
614 : }
615 : case IrOpcode::kTypeGuard: {
616 : // The type-guard is re-introduced in the final reducer if the types
617 : // don't match.
618 20638 : current->SetReplacement(current->ValueInput(0));
619 20638 : break;
620 : }
621 : case IrOpcode::kReferenceEqual: {
622 183556 : Node* left = current->ValueInput(0);
623 183556 : Node* right = current->ValueInput(1);
624 186755 : const VirtualObject* left_object = current->GetVirtualObject(left);
625 184717 : const VirtualObject* right_object = current->GetVirtualObject(right);
626 : Node* replacement = nullptr;
627 186521 : if (left_object && !left_object->HasEscaped()) {
628 1836 : if (right_object && !right_object->HasEscaped() &&
629 : left_object->id() == right_object->id()) {
630 11 : replacement = jsgraph->TrueConstant();
631 : } else {
632 1357 : replacement = jsgraph->FalseConstant();
633 : }
634 182881 : } else if (right_object && !right_object->HasEscaped()) {
635 314 : replacement = jsgraph->FalseConstant();
636 : }
637 183556 : if (replacement) {
638 : // TODO(tebbi) This is a workaround for uninhabited types. If we
639 : // replaced a value of uninhabited type with a constant, we would
640 : // widen the type of the node. This could produce inconsistent
641 : // types (which might confuse representation selection). We get
642 : // around this by refusing to constant-fold and escape-analyze
643 : // if the type is not inhabited.
644 3357 : if (NodeProperties::GetType(left)->IsInhabited() &&
645 : NodeProperties::GetType(right)->IsInhabited()) {
646 1675 : current->SetReplacement(replacement);
647 : } else {
648 7 : current->SetEscaped(left);
649 7 : current->SetEscaped(right);
650 : }
651 : }
652 : break;
653 : }
654 : case IrOpcode::kCheckMaps: {
655 70466 : CheckMapsParameters params = CheckMapsParametersOf(op);
656 70466 : Node* checked = current->ValueInput(0);
657 84133 : const VirtualObject* vobject = current->GetVirtualObject(checked);
658 : Variable map_field;
659 225065 : if (vobject && !vobject->HasEscaped() &&
660 82712 : vobject->FieldAt(HeapObject::kMapOffset).To(&map_field)) {
661 6123 : if (Node* map = current->Get(map_field)) {
662 : Type* const map_type = NodeProperties::GetType(map);
663 9721 : if (map_type->IsHeapConstant() &&
664 : params.maps().contains(
665 4849 : bit_cast<Handle<Map>>(map_type->AsHeapConstant()->Value()))) {
666 4769 : current->MarkForDeletion();
667 4769 : break;
668 : }
669 : } else {
670 : // If the variable has no value, we have not reached the fixed-point
671 : // yet.
672 : break;
673 : }
674 : }
675 64446 : current->SetEscaped(checked);
676 64446 : break;
677 : }
678 : case IrOpcode::kCompareMaps: {
679 10395 : Node* object = current->ValueInput(0);
680 11760 : const VirtualObject* vobject = current->GetVirtualObject(object);
681 : Variable map_field;
682 32550 : if (vobject && !vobject->HasEscaped() &&
683 11873 : vobject->FieldAt(HeapObject::kMapOffset).To(&map_field)) {
684 739 : if (Node* object_map = current->Get(map_field)) {
685 : current->SetReplacement(LowerCompareMapsWithoutLoad(
686 731 : object_map, CompareMapsParametersOf(op).maps(), jsgraph));
687 731 : break;
688 : } else {
689 : // If the variable has no value, we have not reached the fixed-point
690 : // yet.
691 : break;
692 : }
693 : }
694 9656 : current->SetEscaped(object);
695 9656 : break;
696 : }
697 : case IrOpcode::kCheckHeapObject: {
698 29826 : Node* checked = current->ValueInput(0);
699 29826 : switch (checked->opcode()) {
700 : case IrOpcode::kAllocate:
701 : case IrOpcode::kFinishRegion:
702 : case IrOpcode::kHeapConstant:
703 464 : current->SetReplacement(checked);
704 464 : break;
705 : default:
706 29362 : current->SetEscaped(checked);
707 29362 : break;
708 : }
709 : break;
710 : }
711 : case IrOpcode::kMapGuard: {
712 9841 : Node* object = current->ValueInput(0);
713 11205 : const VirtualObject* vobject = current->GetVirtualObject(object);
714 11205 : if (vobject && !vobject->HasEscaped()) {
715 738 : current->MarkForDeletion();
716 : }
717 : break;
718 : }
719 : case IrOpcode::kStateValues:
720 : case IrOpcode::kFrameState:
721 : // These uses are always safe.
722 : break;
723 : default: {
724 : // For unknown nodes, treat all value inputs as escaping.
725 : int value_input_count = op->ValueInputCount();
726 32167122 : for (int i = 0; i < value_input_count; ++i) {
727 13640385 : Node* input = current->ValueInput(i);
728 13640368 : current->SetEscaped(input);
729 : }
730 18526737 : if (OperatorProperties::HasContextInput(op)) {
731 6516515 : current->SetEscaped(current->ContextInput());
732 : }
733 : break;
734 : }
735 : }
736 30701305 : }
737 :
738 : } // namespace
739 :
740 61402603 : void EscapeAnalysis::Reduce(Node* node, Reduction* reduction) {
741 : const Operator* op = node->op();
742 : TRACE("Reducing %s#%d\n", op->mnemonic(), node->id());
743 :
744 30701370 : EscapeAnalysisTracker::Scope current(this, tracker_, node, reduction);
745 30701233 : ReduceNode(op, ¤t, jsgraph());
746 30701161 : }
747 :
748 886717 : EscapeAnalysis::EscapeAnalysis(JSGraph* jsgraph, Zone* zone)
749 : : EffectGraphReducer(
750 : jsgraph->graph(),
751 30701336 : [this](Node* node, Reduction* reduction) { Reduce(node, reduction); },
752 : zone),
753 443360 : tracker_(new (zone) EscapeAnalysisTracker(jsgraph, this, zone)),
754 1330077 : jsgraph_(jsgraph) {}
755 :
756 28926276 : Node* EscapeAnalysisResult::GetReplacementOf(Node* node) {
757 57852592 : return tracker_->GetReplacementOf(node);
758 : }
759 :
760 322621 : Node* EscapeAnalysisResult::GetVirtualObjectField(const VirtualObject* vobject,
761 : int field, Node* effect) {
762 : return tracker_->variable_states_.Get(vobject->FieldAt(field).FromJust(),
763 967863 : effect);
764 : }
765 :
766 49081781 : const VirtualObject* EscapeAnalysisResult::GetVirtualObject(Node* node) {
767 49081781 : return tracker_->virtual_objects_.Get(node);
768 : }
769 :
770 246400 : VirtualObject::VirtualObject(VariableTracker* var_states, VirtualObject::Id id,
771 : int size)
772 123200 : : Dependable(var_states->zone()), id_(id), fields_(var_states->zone()) {
773 : DCHECK_EQ(0, size % kPointerSize);
774 : TRACE("Creating VirtualObject id:%d size:%d\n", id, size);
775 123200 : int num_fields = size / kPointerSize;
776 123200 : fields_.reserve(num_fields);
777 878265 : for (int i = 0; i < num_fields; ++i) {
778 1510130 : fields_.push_back(var_states->NewVariable());
779 : }
780 123200 : }
781 :
782 : #undef TRACE
783 :
784 : } // namespace compiler
785 : } // namespace internal
786 : } // namespace v8
|
