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/handles-inl.h"
13 : #include "src/objects/map-inl.h"
14 :
15 : #ifdef DEBUG
16 : #define TRACE(...) \
17 : do { \
18 : if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
19 : } while (false)
20 : #else
21 : #define TRACE(...)
22 : #endif
23 :
24 : namespace v8 {
25 : namespace internal {
26 : namespace compiler {
27 :
28 : template <class T>
29 : class Sidetable {
30 : public:
31 : explicit Sidetable(Zone* zone) : map_(zone) {}
32 112620069 : T& operator[](const Node* node) {
33 : NodeId id = node->id();
34 337860241 : if (id >= map_.size()) {
35 2607648 : map_.resize(id + 1);
36 : }
37 112620103 : return map_[id];
38 : }
39 :
40 : private:
41 : ZoneVector<T> map_;
42 : };
43 :
44 : template <class T>
45 : class SparseSidetable {
46 : public:
47 : explicit SparseSidetable(Zone* zone, T def_value = T())
48 912191 : : def_value_(std::move(def_value)), map_(zone) {}
49 65120975 : void Set(const Node* node, T value) {
50 121956039 : auto iter = map_.find(node->id());
51 60977961 : if (iter != map_.end()) {
52 2281698 : iter->second = std::move(value);
53 58696256 : } else if (value != def_value_) {
54 4367045 : map_.insert(iter, std::make_pair(node->id(), std::move(value)));
55 : }
56 60977952 : }
57 160531629 : const T& Get(const Node* node) const {
58 321052144 : auto iter = map_.find(node->id());
59 160520515 : return iter != map_.end() ? iter->second : def_value_;
60 : }
61 :
62 : private:
63 : T def_value_;
64 : ZoneUnorderedMap<NodeId, T> map_;
65 : };
66 :
67 : // Keeps track of the changes to the current node during reduction.
68 : // Encapsulates the current state of the IR graph and the reducer state like
69 : // side-tables. All access to the IR and the reducer state should happen through
70 : // a ReduceScope to ensure that changes and dependencies are tracked and all
71 : // necessary node revisitations happen.
72 : class ReduceScope {
73 : public:
74 : typedef EffectGraphReducer::Reduction Reduction;
75 : explicit ReduceScope(Node* node, Reduction* reduction)
76 30489652 : : current_node_(node), reduction_(reduction) {}
77 :
78 : protected:
79 : Node* current_node() const { return current_node_; }
80 : Reduction* reduction() { return reduction_; }
81 :
82 : private:
83 : Node* current_node_;
84 : Reduction* reduction_;
85 : };
86 :
87 : // A VariableTracker object keeps track of the values of variables at all points
88 : // of the effect chain and introduces new phi nodes when necessary.
89 : // Initially and by default, variables are mapped to nullptr, which means that
90 : // the variable allocation point does not dominate the current point on the
91 : // effect chain. We map variables that represent uninitialized memory to the
92 : // Dead node to ensure it is not read.
93 : // Unmapped values are impossible by construction, it is indistinguishable if a
94 : // PersistentMap does not contain an element or maps it to the default element.
95 : class VariableTracker {
96 : private:
97 : // The state of all variables at one point in the effect chain.
98 : class State {
99 : typedef PersistentMap<Variable, Node*> Map;
100 :
101 : public:
102 : explicit State(Zone* zone) : map_(zone) {}
103 13891817 : Node* Get(Variable var) const {
104 13891817 : CHECK(var != Variable::Invalid());
105 13891817 : return map_.Get(var);
106 : }
107 7442588 : void Set(Variable var, Node* node) {
108 7442588 : CHECK(var != Variable::Invalid());
109 7442588 : return map_.Set(var, node);
110 : }
111 387156 : Map::iterator begin() const { return map_.begin(); }
112 387176 : Map::iterator end() const { return map_.end(); }
113 58951078 : bool operator!=(const State& other) const { return map_ != other.map_; }
114 :
115 : private:
116 : Map map_;
117 : };
118 :
119 : public:
120 : VariableTracker(JSGraph* graph, EffectGraphReducer* reducer, Zone* zone);
121 760345 : Variable NewVariable() { return Variable(next_variable_++); }
122 658995 : Node* Get(Variable var, Node* effect) { return table_.Get(effect).Get(var); }
123 : Zone* zone() { return zone_; }
124 :
125 : class Scope : public ReduceScope {
126 : public:
127 : Scope(VariableTracker* tracker, Node* node, Reduction* reduction);
128 : ~Scope();
129 26882 : Maybe<Node*> Get(Variable var) {
130 26882 : Node* node = current_state_.Get(var);
131 46381 : if (node && node->opcode() == IrOpcode::kDead) {
132 : // TODO(tebbi): We use {Dead} as a sentinel for uninitialized memory.
133 : // Reading uninitialized memory can only happen in unreachable code. In
134 : // this case, we have to mark the object as escaping to avoid dead nodes
135 : // in the graph. This is a workaround that should be removed once we can
136 : // handle dead nodes everywhere.
137 : return Nothing<Node*>();
138 : }
139 : return Just(node);
140 : }
141 2650582 : void Set(Variable var, Node* node) { current_state_.Set(var, node); }
142 :
143 : private:
144 : VariableTracker* states_;
145 : State current_state_;
146 : };
147 :
148 : private:
149 : State MergeInputs(Node* effect_phi);
150 : Zone* zone_;
151 : JSGraph* graph_;
152 : SparseSidetable<State> table_;
153 : ZoneVector<Node*> buffer_;
154 : EffectGraphReducer* reducer_;
155 : int next_variable_ = 0;
156 :
157 : DISALLOW_COPY_AND_ASSIGN(VariableTracker);
158 : };
159 :
160 : // Encapsulates the current state of the escape analysis reducer to preserve
161 : // invariants regarding changes and re-visitation.
162 : class EscapeAnalysisTracker : public ZoneObject {
163 : public:
164 456097 : EscapeAnalysisTracker(JSGraph* jsgraph, EffectGraphReducer* reducer,
165 : Zone* zone)
166 : : virtual_objects_(zone),
167 : replacements_(zone),
168 : variable_states_(jsgraph, reducer, zone),
169 : jsgraph_(jsgraph),
170 456098 : zone_(zone) {}
171 :
172 : class Scope : public VariableTracker::Scope {
173 : public:
174 : Scope(EffectGraphReducer* reducer, EscapeAnalysisTracker* tracker,
175 : Node* node, Reduction* reduction)
176 : : VariableTracker::Scope(&tracker->variable_states_, node, reduction),
177 : tracker_(tracker),
178 30489331 : reducer_(reducer) {}
179 4152763 : const VirtualObject* GetVirtualObject(Node* node) {
180 4152763 : VirtualObject* vobject = tracker_->virtual_objects_.Get(node);
181 4152763 : if (vobject) vobject->AddDependency(current_node());
182 4152763 : return vobject;
183 : }
184 : // Create or retrieve a virtual object for the current node.
185 298003 : const VirtualObject* InitVirtualObject(int size) {
186 : DCHECK_EQ(IrOpcode::kAllocate, current_node()->opcode());
187 541346 : VirtualObject* vobject = tracker_->virtual_objects_.Get(current_node());
188 298003 : if (vobject) {
189 132378 : CHECK(vobject->size() == size);
190 : } else {
191 165625 : vobject = tracker_->NewVirtualObject(size);
192 : }
193 298004 : if (vobject) vobject->AddDependency(current_node());
194 298004 : vobject_ = vobject;
195 298004 : return vobject;
196 : }
197 :
198 : void SetVirtualObject(Node* object) {
199 337652 : vobject_ = tracker_->virtual_objects_.Get(object);
200 : }
201 :
202 20305735 : void SetEscaped(Node* node) {
203 20305735 : if (VirtualObject* object = tracker_->virtual_objects_.Get(node)) {
204 21697356 : if (object->HasEscaped()) return;
205 : TRACE("Setting %s#%d to escaped because of use by %s#%d\n",
206 : node->op()->mnemonic(), node->id(),
207 : current_node()->op()->mnemonic(), current_node()->id());
208 : object->SetEscaped();
209 84098 : object->RevisitDependants(reducer_);
210 : }
211 : }
212 : // The inputs of the current node have to be accessed through the scope to
213 : // ensure that they respect the node replacements.
214 20469256 : Node* ValueInput(int i) {
215 : return tracker_->ResolveReplacement(
216 40938573 : NodeProperties::GetValueInput(current_node(), i));
217 : }
218 3038828 : Node* ContextInput() {
219 : return tracker_->ResolveReplacement(
220 6077685 : NodeProperties::GetContextInput(current_node()));
221 : }
222 :
223 1034324 : void SetReplacement(Node* replacement) {
224 1034324 : replacement_ = replacement;
225 : vobject_ =
226 1034324 : replacement ? tracker_->virtual_objects_.Get(replacement) : nullptr;
227 : if (replacement) {
228 : TRACE("Set %s#%d as replacement.\n", replacement->op()->mnemonic(),
229 : replacement->id());
230 : } else {
231 : TRACE("Set nullptr as replacement.\n");
232 : }
233 1034319 : }
234 :
235 1013118 : void MarkForDeletion() { SetReplacement(tracker_->jsgraph_->Dead()); }
236 :
237 60978034 : ~Scope() {
238 149361761 : if (replacement_ != tracker_->replacements_[current_node()] ||
239 57895168 : vobject_ != tracker_->virtual_objects_.Get(current_node())) {
240 : reduction()->set_value_changed();
241 : }
242 30488839 : tracker_->replacements_[current_node()] = replacement_;
243 60977878 : tracker_->virtual_objects_.Set(current_node(), vobject_);
244 30488812 : }
245 :
246 : private:
247 : EscapeAnalysisTracker* tracker_;
248 : EffectGraphReducer* reducer_;
249 : VirtualObject* vobject_ = nullptr;
250 : Node* replacement_ = nullptr;
251 : };
252 :
253 51652267 : Node* GetReplacementOf(Node* node) { return replacements_[node]; }
254 : Node* ResolveReplacement(Node* node) {
255 23508174 : if (Node* replacement = GetReplacementOf(node)) {
256 : return replacement;
257 : }
258 : return node;
259 : }
260 :
261 : private:
262 : friend class EscapeAnalysisResult;
263 : static const size_t kMaxTrackedObjects = 100;
264 :
265 165625 : VirtualObject* NewVirtualObject(int size) {
266 165625 : if (next_object_id_ >= kMaxTrackedObjects) return nullptr;
267 : return new (zone_)
268 221930 : VirtualObject(&variable_states_, next_object_id_++, size);
269 : }
270 :
271 : SparseSidetable<VirtualObject*> virtual_objects_;
272 : Sidetable<Node*> replacements_;
273 : VariableTracker variable_states_;
274 : VirtualObject::Id next_object_id_ = 0;
275 : JSGraph* const jsgraph_;
276 : Zone* const zone_;
277 :
278 : DISALLOW_COPY_AND_ASSIGN(EscapeAnalysisTracker);
279 : };
280 :
281 456102 : EffectGraphReducer::EffectGraphReducer(
282 : Graph* graph, std::function<void(Node*, Reduction*)> reduce, Zone* zone)
283 : : graph_(graph),
284 : state_(graph, kNumStates),
285 : revisit_(zone),
286 : stack_(zone),
287 912216 : reduce_(std::move(reduce)) {}
288 :
289 456081 : void EffectGraphReducer::ReduceFrom(Node* node) {
290 : // Perform DFS and eagerly trigger revisitation as soon as possible.
291 : // A stack element {node, i} indicates that input i of node should be visited
292 : // next.
293 : DCHECK(stack_.empty());
294 912560 : stack_.push({node, 0});
295 126860921 : while (!stack_.empty()) {
296 125948326 : Node* current = stack_.top().node;
297 : int& input_index = stack_.top().input_index;
298 251896652 : if (input_index < current->InputCount()) {
299 : Node* input = current->InputAt(input_index);
300 95458928 : input_index++;
301 95458225 : switch (state_.Get(input)) {
302 : case State::kVisited:
303 : // The input is already reduced.
304 : break;
305 : case State::kOnStack:
306 : // The input is on the DFS stack right now, so it will be revisited
307 : // later anyway.
308 : break;
309 : case State::kUnvisited:
310 : case State::kRevisit: {
311 : state_.Set(input, State::kOnStack);
312 55245817 : stack_.push({input, 0});
313 27623043 : break;
314 : }
315 : }
316 : } else {
317 : stack_.pop();
318 30489398 : Reduction reduction;
319 30489398 : reduce_(current, &reduction);
320 246514396 : for (Edge edge : current->use_edges()) {
321 : // Mark uses for revisitation.
322 : Node* use = edge.from();
323 92767904 : if (NodeProperties::IsEffectEdge(edge)) {
324 13208580 : if (reduction.effect_changed()) Revisit(use);
325 : } else {
326 79561765 : if (reduction.value_changed()) Revisit(use);
327 : }
328 : }
329 : state_.Set(current, State::kVisited);
330 : // Process the revisitation buffer immediately. This improves performance
331 : // of escape analysis. Using a stack for {revisit_} reverses the order in
332 : // which the revisitation happens. This also seems to improve performance.
333 32900606 : while (!revisit_.empty()) {
334 2411231 : Node* revisit = revisit_.top();
335 2411239 : if (state_.Get(revisit) == State::kRevisit) {
336 : state_.Set(revisit, State::kOnStack);
337 4822608 : stack_.push({revisit, 0});
338 : }
339 : revisit_.pop();
340 : }
341 : }
342 : }
343 456116 : }
344 :
345 8948977 : void EffectGraphReducer::Revisit(Node* node) {
346 17897936 : if (state_.Get(node) == State::kVisited) {
347 : TRACE(" Queueing for revisit: %s#%d\n", node->op()->mnemonic(),
348 : node->id());
349 : state_.Set(node, State::kRevisit);
350 : revisit_.push(node);
351 : }
352 8948935 : }
353 :
354 0 : VariableTracker::VariableTracker(JSGraph* graph, EffectGraphReducer* reducer,
355 : Zone* zone)
356 : : zone_(zone),
357 : graph_(graph),
358 : table_(zone, State(zone)),
359 : buffer_(zone),
360 912192 : reducer_(reducer) {}
361 :
362 60979304 : VariableTracker::Scope::Scope(VariableTracker* states, Node* node,
363 : Reduction* reduction)
364 : : ReduceScope(node, reduction),
365 : states_(states),
366 30489652 : current_state_(states->zone_) {
367 30489652 : switch (node->opcode()) {
368 : case IrOpcode::kEffectPhi:
369 387172 : current_state_ = states_->MergeInputs(node);
370 387181 : break;
371 : default:
372 30102480 : int effect_inputs = node->op()->EffectInputCount();
373 30102480 : if (effect_inputs == 1) {
374 : current_state_ =
375 12197339 : states_->table_.Get(NodeProperties::GetEffectInput(node, 0));
376 : } else {
377 : DCHECK_EQ(0, effect_inputs);
378 : }
379 : }
380 30489493 : }
381 :
382 30488873 : VariableTracker::Scope::~Scope() {
383 91467038 : if (!reduction()->effect_changed() &&
384 30488930 : states_->table_.Get(current_node()) != current_state_) {
385 : reduction()->set_effect_changed();
386 : }
387 30489054 : states_->table_.Set(current_node(), current_state_);
388 30488808 : }
389 :
390 387169 : VariableTracker::State VariableTracker::MergeInputs(Node* effect_phi) {
391 : // A variable that is mapped to [nullptr] was not assigned a value on every
392 : // execution path to the current effect phi. Relying on the invariant that
393 : // every variable is initialized (at least with a sentinel like the Dead
394 : // node), this means that the variable initialization does not dominate the
395 : // current point. So for loop effect phis, we can keep nullptr for a variable
396 : // as long as the first input of the loop has nullptr for this variable. For
397 : // non-loop effect phis, we can even keep it nullptr as long as any input has
398 : // nullptr.
399 : DCHECK_EQ(IrOpcode::kEffectPhi, effect_phi->opcode());
400 387169 : int arity = effect_phi->op()->EffectInputCount();
401 387169 : Node* control = NodeProperties::GetControlInput(effect_phi, 0);
402 : TRACE("control: %s#%d\n", control->op()->mnemonic(), control->id());
403 774340 : bool is_loop = control->opcode() == IrOpcode::kLoop;
404 848691 : buffer_.reserve(arity + 1);
405 :
406 387167 : State first_input = table_.Get(NodeProperties::GetEffectInput(effect_phi, 0));
407 387156 : State result = first_input;
408 10007144 : for (std::pair<Variable, Node*> var_value : first_input) {
409 4808336 : if (Node* value = var_value.second) {
410 4807227 : Variable var = var_value.first;
411 : TRACE("var %i:\n", var.id_);
412 : buffer_.clear();
413 4807227 : buffer_.push_back(value);
414 : bool identical_inputs = true;
415 : int num_defined_inputs = 1;
416 : TRACE(" input 0: %s#%d\n", value->op()->mnemonic(), value->id());
417 13333832 : for (int i = 1; i < arity; ++i) {
418 : Node* next_value =
419 8540145 : table_.Get(NodeProperties::GetEffectInput(effect_phi, i)).Get(var);
420 8489688 : if (next_value != value) identical_inputs = false;
421 8489688 : if (next_value != nullptr) {
422 7342108 : num_defined_inputs++;
423 : TRACE(" input %i: %s#%d\n", i, next_value->op()->mnemonic(),
424 : next_value->id());
425 : } else {
426 : TRACE(" input %i: nullptr\n", i);
427 : }
428 8489688 : buffer_.push_back(next_value);
429 : }
430 :
431 6749266 : Node* old_value = table_.Get(effect_phi).Get(var);
432 : if (old_value) {
433 : TRACE(" old: %s#%d\n", old_value->op()->mnemonic(), old_value->id());
434 : } else {
435 : TRACE(" old: nullptr\n");
436 : }
437 : // Reuse a previously created phi node if possible.
438 7194886 : if (old_value && old_value->opcode() == IrOpcode::kPhi &&
439 443870 : NodeProperties::GetControlInput(old_value, 0) == control) {
440 : // Since a phi node can never dominate its control node,
441 : // [old_value] cannot originate from the inputs. Thus [old_value]
442 : // must have been created by a previous reduction of this [effect_phi].
443 461521 : for (int i = 0; i < arity; ++i) {
444 : NodeProperties::ReplaceValueInput(
445 1330237 : old_value, buffer_[i] ? buffer_[i] : graph_->Dead(), i);
446 : // This change cannot affect the rest of the reducer, so there is no
447 : // need to trigger additional revisitations.
448 : }
449 171733 : result.Set(var, old_value);
450 : } else {
451 4623704 : if (num_defined_inputs == 1 && is_loop) {
452 : // For loop effect phis, the variable initialization dominates iff it
453 : // dominates the first input.
454 : DCHECK_EQ(2, arity);
455 : DCHECK_EQ(value, buffer_[0]);
456 331880 : result.Set(var, value);
457 4291824 : } else if (num_defined_inputs < arity) {
458 : // If the variable is undefined on some input of this non-loop effect
459 : // phi, then its initialization does not dominate this point.
460 244306 : result.Set(var, nullptr);
461 : } else {
462 : DCHECK_EQ(num_defined_inputs, arity);
463 : // We only create a phi if the values are different.
464 4047518 : if (identical_inputs) {
465 3843921 : result.Set(var, value);
466 : } else {
467 : TRACE("Creating new phi\n");
468 203597 : buffer_.push_back(control);
469 : Node* phi = graph_->graph()->NewNode(
470 : graph_->common()->Phi(MachineRepresentation::kTagged, arity),
471 610793 : arity + 1, &buffer_.front());
472 : // TODO(tebbi): Computing precise types here is tricky, because of
473 : // the necessary revisitations. If we really need this, we should
474 : // probably do it afterwards.
475 : NodeProperties::SetType(phi, Type::Any());
476 203598 : reducer_->AddRoot(phi);
477 203598 : result.Set(var, phi);
478 : }
479 : }
480 : }
481 : #ifdef DEBUG
482 : if (Node* result_node = result.Get(var)) {
483 : TRACE(" result: %s#%d\n", result_node->op()->mnemonic(),
484 : result_node->id());
485 : } else {
486 : TRACE(" result: nullptr\n");
487 : }
488 : #endif
489 : }
490 : }
491 387180 : return result;
492 : }
493 :
494 : namespace {
495 :
496 : int OffsetOfFieldAccess(const Operator* op) {
497 : DCHECK(op->opcode() == IrOpcode::kLoadField ||
498 : op->opcode() == IrOpcode::kStoreField);
499 980180 : FieldAccess access = FieldAccessOf(op);
500 : return access.offset;
501 : }
502 :
503 : int OffsetOfElementAt(ElementAccess const& access, int index) {
504 : DCHECK_GE(index, 0);
505 : DCHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
506 : kTaggedSizeLog2);
507 49632 : return access.header_size +
508 49750 : (index << ElementSizeLog2Of(access.machine_type.representation()));
509 : }
510 :
511 49101 : Maybe<int> OffsetOfElementsAccess(const Operator* op, Node* index_node) {
512 : DCHECK(op->opcode() == IrOpcode::kLoadElement ||
513 : op->opcode() == IrOpcode::kStoreElement);
514 49101 : Type index_type = NodeProperties::GetType(index_node);
515 49101 : if (!index_type.Is(Type::OrderedNumber())) return Nothing<int>();
516 49101 : double max = index_type.Max();
517 49101 : double min = index_type.Min();
518 49101 : int index = static_cast<int>(min);
519 49101 : if (index < 0 || index != min || index != max) return Nothing<int>();
520 48113 : return Just(OffsetOfElementAt(ElementAccessOf(op), index));
521 : }
522 :
523 125 : Node* LowerCompareMapsWithoutLoad(Node* checked_map,
524 : ZoneHandleSet<Map> const& checked_against,
525 125 : JSGraph* jsgraph) {
526 125 : Node* true_node = jsgraph->TrueConstant();
527 125 : Node* false_node = jsgraph->FalseConstant();
528 : Node* replacement = false_node;
529 250 : for (Handle<Map> map : checked_against) {
530 125 : Node* map_node = jsgraph->HeapConstant(map);
531 : // We cannot create a HeapConstant type here as we are off-thread.
532 : NodeProperties::SetType(map_node, Type::Internal());
533 : Node* comparison = jsgraph->graph()->NewNode(
534 125 : jsgraph->simplified()->ReferenceEqual(), checked_map, map_node);
535 : NodeProperties::SetType(comparison, Type::Boolean());
536 125 : if (replacement == false_node) {
537 : replacement = comparison;
538 : } else {
539 : replacement = jsgraph->graph()->NewNode(
540 : jsgraph->common()->Select(MachineRepresentation::kTaggedPointer),
541 0 : comparison, true_node, replacement);
542 : NodeProperties::SetType(replacement, Type::Boolean());
543 : }
544 : }
545 125 : return replacement;
546 : }
547 :
548 69650563 : void ReduceNode(const Operator* op, EscapeAnalysisTracker::Scope* current,
549 449 : JSGraph* jsgraph) {
550 30489120 : switch (op->opcode()) {
551 : case IrOpcode::kAllocate: {
552 298004 : NumberMatcher size(current->ValueInput(0));
553 298003 : if (!size.HasValue()) break;
554 298003 : int size_int = static_cast<int>(size.Value());
555 298003 : if (size_int != size.Value()) break;
556 298003 : if (const VirtualObject* vobject = current->InitVirtualObject(size_int)) {
557 : // Initialize with dead nodes as a sentinel for uninitialized memory.
558 2128587 : for (Variable field : *vobject) {
559 1643248 : current->Set(field, jsgraph->Dead());
560 : }
561 : }
562 : break;
563 : }
564 : case IrOpcode::kFinishRegion:
565 307344 : current->SetVirtualObject(current->ValueInput(0));
566 : break;
567 : case IrOpcode::kStoreField: {
568 2675535 : Node* object = current->ValueInput(0);
569 2675532 : Node* value = current->ValueInput(1);
570 4431235 : const VirtualObject* vobject = current->GetVirtualObject(object);
571 : Variable var;
572 9782311 : if (vobject && !vobject->HasEscaped() &&
573 4597287 : vobject->FieldAt(OffsetOfFieldAccess(op)).To(&var)) {
574 : current->Set(var, value);
575 960874 : current->MarkForDeletion();
576 : } else {
577 1714662 : current->SetEscaped(object);
578 1714662 : current->SetEscaped(value);
579 : }
580 : break;
581 : }
582 : case IrOpcode::kStoreElement: {
583 107593 : Node* object = current->ValueInput(0);
584 107593 : Node* index = current->ValueInput(1);
585 107593 : Node* value = current->ValueInput(2);
586 203522 : const VirtualObject* vobject = current->GetVirtualObject(object);
587 : int offset;
588 : Variable var;
589 311115 : if (vobject && !vobject->HasEscaped() &&
590 358634 : OffsetOfElementsAccess(op, index).To(&offset) &&
591 155399 : vobject->FieldAt(offset).To(&var)) {
592 : current->Set(var, value);
593 47806 : current->MarkForDeletion();
594 : } else {
595 59787 : current->SetEscaped(value);
596 59787 : current->SetEscaped(object);
597 : }
598 : break;
599 : }
600 : case IrOpcode::kLoadField: {
601 868105 : Node* object = current->ValueInput(0);
602 979940 : const VirtualObject* vobject = current->GetVirtualObject(object);
603 : Variable var;
604 : Node* value;
605 1848047 : if (vobject && !vobject->HasEscaped() &&
606 1794107 : vobject->FieldAt(OffsetOfFieldAccess(op)).To(&var) &&
607 887390 : current->Get(var).To(&value)) {
608 19284 : current->SetReplacement(value);
609 : } else {
610 848822 : current->SetEscaped(object);
611 : }
612 : break;
613 : }
614 : case IrOpcode::kLoadElement: {
615 29422 : Node* object = current->ValueInput(0);
616 29422 : Node* index = current->ValueInput(1);
617 33431 : const VirtualObject* vobject = current->GetVirtualObject(object);
618 : int offset;
619 : Variable var;
620 : Node* value;
621 60996 : if (vobject && !vobject->HasEscaped() &&
622 32288 : OffsetOfElementsAccess(op, index).To(&offset) &&
623 30326 : vobject->FieldAt(offset).To(&var) && current->Get(var).To(&value)) {
624 299 : current->SetReplacement(value);
625 30977 : } else if (vobject && !vobject->HasEscaped()) {
626 : // Compute the known length (aka the number of elements) of {object}
627 : // based on the virtual object information.
628 981 : ElementAccess const& access = ElementAccessOf(op);
629 : int const length =
630 981 : (vobject->size() - access.header_size) >>
631 1430 : ElementSizeLog2Of(access.machine_type.representation());
632 : Variable var0, var1;
633 : Node* value0;
634 : Node* value1;
635 1962 : if (length == 1 &&
636 1335 : vobject->FieldAt(OffsetOfElementAt(access, 0)).To(&var) &&
637 2198 : current->Get(var).To(&value) &&
638 81 : (value == nullptr ||
639 1062 : NodeProperties::GetType(value).Is(access.type))) {
640 : // The {object} has no elements, and we know that the LoadElement
641 : // {index} must be within bounds, thus it must always yield this
642 : // one element of {object}.
643 118 : current->SetReplacement(value);
644 118 : break;
645 1726 : } else if (length == 2 &&
646 3152 : vobject->FieldAt(OffsetOfElementAt(access, 0)).To(&var0) &&
647 2389 : current->Get(var0).To(&value0) &&
648 456 : (value0 == nullptr ||
649 2075 : NodeProperties::GetType(value0).Is(access.type)) &&
650 2375 : vobject->FieldAt(OffsetOfElementAt(access, 1)).To(&var1) &&
651 3238 : current->Get(var1).To(&value1) &&
652 449 : (value1 == nullptr ||
653 1312 : NodeProperties::GetType(value1).Is(access.type))) {
654 756 : if (value0 && value1) {
655 : // The {object} has exactly two elements, so the LoadElement
656 : // must return one of them (i.e. either the element at index
657 : // 0 or the one at index 1). So we can turn the LoadElement
658 : // into a Select operation instead (still allowing the {object}
659 : // to be scalar replaced). We must however mark the elements
660 : // of the {object} itself as escaping.
661 : Node* check =
662 : jsgraph->graph()->NewNode(jsgraph->simplified()->NumberEqual(),
663 898 : index, jsgraph->ZeroConstant());
664 : NodeProperties::SetType(check, Type::Boolean());
665 : Node* select = jsgraph->graph()->NewNode(
666 : jsgraph->common()->Select(access.machine_type.representation()),
667 449 : check, value0, value1);
668 : NodeProperties::SetType(select, access.type);
669 449 : current->SetReplacement(select);
670 449 : current->SetEscaped(value0);
671 449 : current->SetEscaped(value1);
672 449 : break;
673 : } else {
674 : // If the variables have no values, we have
675 : // not reached the fixed-point yet.
676 : break;
677 : }
678 : }
679 : }
680 28547 : current->SetEscaped(object);
681 28547 : break;
682 : }
683 : case IrOpcode::kTypeGuard: {
684 30309 : current->SetVirtualObject(current->ValueInput(0));
685 : break;
686 : }
687 : case IrOpcode::kReferenceEqual: {
688 190521 : Node* left = current->ValueInput(0);
689 190521 : Node* right = current->ValueInput(1);
690 191576 : const VirtualObject* left_object = current->GetVirtualObject(left);
691 191990 : const VirtualObject* right_object = current->GetVirtualObject(right);
692 : Node* replacement = nullptr;
693 191342 : if (left_object && !left_object->HasEscaped()) {
694 730 : if (right_object && !right_object->HasEscaped() &&
695 : left_object->id() == right_object->id()) {
696 4 : replacement = jsgraph->TrueConstant();
697 : } else {
698 258 : replacement = jsgraph->FalseConstant();
699 : }
700 191260 : } else if (right_object && !right_object->HasEscaped()) {
701 470 : replacement = jsgraph->FalseConstant();
702 : }
703 190521 : if (replacement) {
704 : // TODO(tebbi) This is a workaround for uninhabited types. If we
705 : // replaced a value of uninhabited type with a constant, we would
706 : // widen the type of the node. This could produce inconsistent
707 : // types (which might confuse representation selection). We get
708 : // around this by refusing to constant-fold and escape-analyze
709 : // if the type is not inhabited.
710 732 : if (!NodeProperties::GetType(left).IsNone() &&
711 : !NodeProperties::GetType(right).IsNone()) {
712 732 : current->SetReplacement(replacement);
713 : } else {
714 0 : current->SetEscaped(left);
715 0 : current->SetEscaped(right);
716 : }
717 : }
718 : break;
719 : }
720 : case IrOpcode::kCheckMaps: {
721 77007 : CheckMapsParameters params = CheckMapsParametersOf(op);
722 77006 : Node* checked = current->ValueInput(0);
723 93311 : const VirtualObject* vobject = current->GetVirtualObject(checked);
724 : Variable map_field;
725 : Node* map;
726 170317 : if (vobject && !vobject->HasEscaped() &&
727 170581 : vobject->FieldAt(HeapObject::kMapOffset).To(&map_field) &&
728 82529 : current->Get(map_field).To(&map)) {
729 5523 : if (map) {
730 4412 : Type const map_type = NodeProperties::GetType(map);
731 : AllowHandleDereference handle_dereference;
732 8813 : if (map_type.IsHeapConstant() &&
733 : params.maps().contains(
734 4401 : Handle<Map>::cast(map_type.AsHeapConstant()->Value()))) {
735 4300 : current->MarkForDeletion();
736 4300 : break;
737 : }
738 : } else {
739 : // If the variable has no value, we have not reached the fixed-point
740 : // yet.
741 : break;
742 : }
743 : }
744 71595 : current->SetEscaped(checked);
745 71595 : break;
746 : }
747 : case IrOpcode::kCompareMaps: {
748 7638 : Node* object = current->ValueInput(0);
749 8008 : const VirtualObject* vobject = current->GetVirtualObject(object);
750 : Variable map_field;
751 : Node* object_map;
752 15646 : if (vobject && !vobject->HasEscaped() &&
753 15693 : vobject->FieldAt(HeapObject::kMapOffset).To(&map_field) &&
754 7777 : current->Get(map_field).To(&object_map)) {
755 139 : if (object_map) {
756 : current->SetReplacement(LowerCompareMapsWithoutLoad(
757 125 : object_map, CompareMapsParametersOf(op).maps(), jsgraph));
758 125 : break;
759 : } else {
760 : // If the variable has no value, we have not reached the fixed-point
761 : // yet.
762 : break;
763 : }
764 : }
765 7499 : current->SetEscaped(object);
766 7499 : break;
767 : }
768 : case IrOpcode::kCheckHeapObject: {
769 34872 : Node* checked = current->ValueInput(0);
770 34873 : switch (checked->opcode()) {
771 : case IrOpcode::kAllocate:
772 : case IrOpcode::kFinishRegion:
773 : case IrOpcode::kHeapConstant:
774 199 : current->SetReplacement(checked);
775 199 : break;
776 : default:
777 34674 : current->SetEscaped(checked);
778 34674 : break;
779 : }
780 : break;
781 : }
782 : case IrOpcode::kMapGuard: {
783 6449 : Node* object = current->ValueInput(0);
784 6825 : const VirtualObject* vobject = current->GetVirtualObject(object);
785 6825 : if (vobject && !vobject->HasEscaped()) {
786 138 : current->MarkForDeletion();
787 : }
788 : break;
789 : }
790 : case IrOpcode::kStateValues:
791 : case IrOpcode::kFrameState:
792 : // These uses are always safe.
793 : break;
794 : default: {
795 : // For unknown nodes, treat all value inputs as escaping.
796 : int value_input_count = op->ValueInputCount();
797 31243861 : for (int i = 0; i < value_input_count; ++i) {
798 12726128 : Node* input = current->ValueInput(i);
799 12726116 : current->SetEscaped(input);
800 : }
801 18517733 : if (OperatorProperties::HasContextInput(op)) {
802 6077680 : current->SetEscaped(current->ContextInput());
803 : }
804 : break;
805 : }
806 : }
807 30488992 : }
808 :
809 : } // namespace
810 :
811 60978507 : void EscapeAnalysis::Reduce(Node* node, Reduction* reduction) {
812 : const Operator* op = node->op();
813 : TRACE("Reducing %s#%d\n", op->mnemonic(), node->id());
814 :
815 30489331 : EscapeAnalysisTracker::Scope current(this, tracker_, node, reduction);
816 30489176 : ReduceNode(op, ¤t, jsgraph());
817 30488804 : }
818 :
819 456077 : EscapeAnalysis::EscapeAnalysis(JSGraph* jsgraph, Zone* zone)
820 : : EffectGraphReducer(
821 : jsgraph->graph(),
822 30489280 : [this](Node* node, Reduction* reduction) { Reduce(node, reduction); },
823 : zone),
824 456097 : tracker_(new (zone) EscapeAnalysisTracker(jsgraph, this, zone)),
825 1368326 : jsgraph_(jsgraph) {}
826 :
827 28144135 : Node* EscapeAnalysisResult::GetReplacementOf(Node* node) {
828 28144135 : Node* replacement = tracker_->GetReplacementOf(node);
829 : // Replacements cannot have replacements. This is important to ensure
830 : // re-visitation: If a replacement is replaced, then all nodes accessing
831 : // the replacement have to be updated.
832 : if (replacement) DCHECK_NULL(tracker_->GetReplacementOf(replacement));
833 28144347 : return replacement;
834 : }
835 :
836 658995 : Node* EscapeAnalysisResult::GetVirtualObjectField(const VirtualObject* vobject,
837 : int field, Node* effect) {
838 : return tracker_->variable_states_.Get(vobject->FieldAt(field).FromJust(),
839 1976986 : effect);
840 : }
841 :
842 48531912 : const VirtualObject* EscapeAnalysisResult::GetVirtualObject(Node* node) {
843 48531912 : return tracker_->virtual_objects_.Get(node);
844 : }
845 :
846 221928 : VirtualObject::VirtualObject(VariableTracker* var_states, VirtualObject::Id id,
847 : int size)
848 110964 : : Dependable(var_states->zone()), id_(id), fields_(var_states->zone()) {
849 : DCHECK(IsAligned(size, kTaggedSize));
850 : TRACE("Creating VirtualObject id:%d size:%d\n", id, size);
851 110964 : int num_fields = size / kTaggedSize;
852 110964 : fields_.reserve(num_fields);
853 871310 : for (int i = 0; i < num_fields; ++i) {
854 1520688 : fields_.push_back(var_states->NewVariable());
855 : }
856 110965 : }
857 :
858 : #undef TRACE
859 :
860 : } // namespace compiler
861 : } // namespace internal
862 183867 : } // namespace v8
|
