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-reducer.h"
6 :
7 : #include "src/compiler/all-nodes.h"
8 : #include "src/compiler/js-graph.h"
9 : #include "src/compiler/simplified-operator.h"
10 : #include "src/compiler/type-cache.h"
11 : #include "src/counters.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 : namespace compiler {
16 :
17 : #ifdef DEBUG
18 : #define TRACE(...) \
19 : do { \
20 : if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
21 : } while (false)
22 : #else
23 : #define TRACE(...)
24 : #endif // DEBUG
25 :
26 79538 : EscapeAnalysisReducer::EscapeAnalysisReducer(Editor* editor, JSGraph* jsgraph,
27 : EscapeAnalysis* escape_analysis,
28 : Zone* zone)
29 : : AdvancedReducer(editor),
30 : jsgraph_(jsgraph),
31 : escape_analysis_(escape_analysis),
32 : zone_(zone),
33 39769 : fully_reduced_(static_cast<int>(jsgraph->graph()->NodeCount() * 2), zone),
34 119307 : exists_virtual_allocate_(escape_analysis->ExistsVirtualAllocate()) {}
35 :
36 11008017 : Reduction EscapeAnalysisReducer::ReduceNode(Node* node) {
37 58267805 : if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
38 10389859 : fully_reduced_.Contains(node->id())) {
39 : return NoChange();
40 : }
41 :
42 10205134 : switch (node->opcode()) {
43 : case IrOpcode::kLoadField:
44 : case IrOpcode::kLoadElement:
45 446435 : return ReduceLoad(node);
46 : case IrOpcode::kStoreField:
47 : case IrOpcode::kStoreElement:
48 1106812 : return ReduceStore(node);
49 : case IrOpcode::kCheckMaps:
50 28169 : return ReduceCheckMaps(node);
51 : case IrOpcode::kAllocate:
52 115359 : return ReduceAllocate(node);
53 : case IrOpcode::kFinishRegion:
54 119622 : return ReduceFinishRegion(node);
55 : case IrOpcode::kReferenceEqual:
56 70363 : return ReduceReferenceEqual(node);
57 : case IrOpcode::kObjectIsSmi:
58 478 : return ReduceObjectIsSmi(node);
59 : // FrameStates and Value nodes are preprocessed here,
60 : // and visited via ReduceFrameStateUses from their user nodes.
61 : case IrOpcode::kFrameState:
62 : case IrOpcode::kStateValues: {
63 5452862 : if (node->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
64 2726431 : fully_reduced_.Contains(node->id())) {
65 : break;
66 : }
67 : bool depends_on_object_state = false;
68 30034549 : for (Node* input : node->inputs()) {
69 11508637 : switch (input->opcode()) {
70 : case IrOpcode::kAllocate:
71 : case IrOpcode::kFinishRegion:
72 : depends_on_object_state =
73 1240373 : depends_on_object_state || escape_analysis()->IsVirtual(input);
74 622216 : break;
75 : case IrOpcode::kFrameState:
76 : case IrOpcode::kStateValues:
77 : depends_on_object_state =
78 4290844 : depends_on_object_state ||
79 12892185 : input->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
80 4290844 : !fully_reduced_.Contains(input->id());
81 4310497 : break;
82 : default:
83 : break;
84 : }
85 : }
86 2726431 : if (!depends_on_object_state) {
87 5400248 : fully_reduced_.Add(node->id());
88 : }
89 : return NoChange();
90 : }
91 : case IrOpcode::kNewUnmappedArgumentsElements:
92 : arguments_elements_.insert(node);
93 : break;
94 : default:
95 : // TODO(sigurds): Change this to GetFrameStateInputCount once
96 : // it is working. For now we use EffectInputCount > 0 to determine
97 : // whether a node might have a frame state input.
98 7728644 : if (exists_virtual_allocate_ && node->op()->EffectInputCount() > 0) {
99 952610 : return ReduceFrameStateUses(node);
100 : }
101 : break;
102 : }
103 : return NoChange();
104 : }
105 :
106 10390253 : Reduction EscapeAnalysisReducer::Reduce(Node* node) {
107 10389859 : Reduction reduction = ReduceNode(node);
108 10389859 : if (reduction.Changed() && node != reduction.replacement()) {
109 394 : escape_analysis()->SetReplacement(node, reduction.replacement());
110 : }
111 10389859 : return reduction;
112 : }
113 :
114 : namespace {
115 :
116 482 : Node* MaybeGuard(JSGraph* jsgraph, Zone* zone, Node* original,
117 : Node* replacement) {
118 : // We might need to guard the replacement if the type of the {replacement}
119 : // node is not in a sub-type relation to the type of the the {original} node.
120 : Type* const replacement_type = NodeProperties::GetType(replacement);
121 : Type* const original_type = NodeProperties::GetType(original);
122 380 : if (!replacement_type->Is(original_type)) {
123 51 : Node* const control = NodeProperties::GetControlInput(original);
124 : replacement = jsgraph->graph()->NewNode(
125 51 : jsgraph->common()->TypeGuard(original_type), replacement, control);
126 : NodeProperties::SetType(replacement, original_type);
127 : }
128 380 : return replacement;
129 : }
130 :
131 1789808 : Node* SkipTypeGuards(Node* node) {
132 1789808 : while (node->opcode() == IrOpcode::kTypeGuard) {
133 775 : node = NodeProperties::GetValueInput(node, 0);
134 : }
135 : return node;
136 : }
137 :
138 : } // namespace
139 :
140 893630 : Reduction EscapeAnalysisReducer::ReduceLoad(Node* node) {
141 : DCHECK(node->opcode() == IrOpcode::kLoadField ||
142 : node->opcode() == IrOpcode::kLoadElement);
143 892870 : if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
144 446435 : fully_reduced_.Add(node->id());
145 : }
146 446435 : if (escape_analysis()->IsVirtual(
147 446435 : SkipTypeGuards(NodeProperties::GetValueInput(node, 0)))) {
148 380 : if (Node* rep = escape_analysis()->GetReplacement(node)) {
149 : TRACE("Replaced #%d (%s) with #%d (%s)\n", node->id(),
150 : node->op()->mnemonic(), rep->id(), rep->op()->mnemonic());
151 380 : rep = MaybeGuard(jsgraph(), zone(), node, rep);
152 380 : ReplaceWithValue(node, rep);
153 : return Replace(rep);
154 : }
155 : }
156 : return NoChange();
157 : }
158 :
159 :
160 2213624 : Reduction EscapeAnalysisReducer::ReduceStore(Node* node) {
161 : DCHECK(node->opcode() == IrOpcode::kStoreField ||
162 : node->opcode() == IrOpcode::kStoreElement);
163 2213624 : if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
164 1106812 : fully_reduced_.Add(node->id());
165 : }
166 1106812 : if (escape_analysis()->IsVirtual(
167 1106812 : SkipTypeGuards(NodeProperties::GetValueInput(node, 0)))) {
168 : TRACE("Removed #%d (%s) from effect chain\n", node->id(),
169 : node->op()->mnemonic());
170 : RelaxEffectsAndControls(node);
171 : return Changed(node);
172 : }
173 : return NoChange();
174 : }
175 :
176 56350 : Reduction EscapeAnalysisReducer::ReduceCheckMaps(Node* node) {
177 : DCHECK(node->opcode() == IrOpcode::kCheckMaps);
178 56338 : if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
179 28169 : fully_reduced_.Add(node->id());
180 : }
181 28169 : if (escape_analysis()->IsVirtual(
182 56350 : SkipTypeGuards(NodeProperties::GetValueInput(node, 0))) &&
183 12 : !escape_analysis()->IsEscaped(node)) {
184 : TRACE("Removed #%d (%s) from effect chain\n", node->id(),
185 : node->op()->mnemonic());
186 : RelaxEffectsAndControls(node);
187 : return Changed(node);
188 : }
189 : return NoChange();
190 : }
191 :
192 230718 : Reduction EscapeAnalysisReducer::ReduceAllocate(Node* node) {
193 : DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
194 230718 : if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
195 115359 : fully_reduced_.Add(node->id());
196 : }
197 115359 : if (escape_analysis()->IsVirtual(node)) {
198 : RelaxEffectsAndControls(node);
199 : TRACE("Removed allocate #%d from effect chain\n", node->id());
200 : return Changed(node);
201 : }
202 : return NoChange();
203 : }
204 :
205 :
206 145032 : Reduction EscapeAnalysisReducer::ReduceFinishRegion(Node* node) {
207 : DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
208 119622 : Node* effect = NodeProperties::GetEffectInput(node, 0);
209 119622 : if (effect->opcode() == IrOpcode::kBeginRegion) {
210 : // We only add it now to remove empty Begin/Finish region pairs
211 : // in the process.
212 50820 : if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
213 25410 : fully_reduced_.Add(node->id());
214 : }
215 : RelaxEffectsAndControls(effect);
216 : RelaxEffectsAndControls(node);
217 : #ifdef DEBUG
218 : if (FLAG_trace_turbo_escape) {
219 : PrintF("Removed region #%d / #%d from effect chain,", effect->id(),
220 : node->id());
221 : PrintF(" %d user(s) of #%d remain(s):", node->UseCount(), node->id());
222 : for (Edge edge : node->use_edges()) {
223 : PrintF(" #%d", edge.from()->id());
224 : }
225 : PrintF("\n");
226 : }
227 : #endif // DEBUG
228 : return Changed(node);
229 : }
230 : return NoChange();
231 : }
232 :
233 :
234 211124 : Reduction EscapeAnalysisReducer::ReduceReferenceEqual(Node* node) {
235 : DCHECK_EQ(node->opcode(), IrOpcode::kReferenceEqual);
236 70363 : Node* left = SkipTypeGuards(NodeProperties::GetValueInput(node, 0));
237 70363 : Node* right = SkipTypeGuards(NodeProperties::GetValueInput(node, 1));
238 70363 : if (escape_analysis()->IsVirtual(left)) {
239 21 : if (escape_analysis()->IsVirtual(right) &&
240 7 : escape_analysis()->CompareVirtualObjects(left, right)) {
241 14 : ReplaceWithValue(node, jsgraph()->TrueConstant());
242 : TRACE("Replaced ref eq #%d with true\n", node->id());
243 0 : return Replace(jsgraph()->TrueConstant());
244 : }
245 : // Right-hand side is not a virtual object, or a different one.
246 14 : ReplaceWithValue(node, jsgraph()->FalseConstant());
247 : TRACE("Replaced ref eq #%d with false\n", node->id());
248 14 : return Replace(jsgraph()->FalseConstant());
249 70349 : } else if (escape_analysis()->IsVirtual(right)) {
250 : // Left-hand side is not a virtual object.
251 0 : ReplaceWithValue(node, jsgraph()->FalseConstant());
252 : TRACE("Replaced ref eq #%d with false\n", node->id());
253 0 : return Replace(jsgraph()->FalseConstant());
254 : }
255 : return NoChange();
256 : }
257 :
258 :
259 956 : Reduction EscapeAnalysisReducer::ReduceObjectIsSmi(Node* node) {
260 : DCHECK_EQ(node->opcode(), IrOpcode::kObjectIsSmi);
261 478 : Node* input = SkipTypeGuards(NodeProperties::GetValueInput(node, 0));
262 478 : if (escape_analysis()->IsVirtual(input)) {
263 0 : ReplaceWithValue(node, jsgraph()->FalseConstant());
264 : TRACE("Replaced ObjectIsSmi #%d with false\n", node->id());
265 0 : return Replace(jsgraph()->FalseConstant());
266 : }
267 : return NoChange();
268 : }
269 :
270 :
271 952610 : Reduction EscapeAnalysisReducer::ReduceFrameStateUses(Node* node) {
272 : DCHECK_GE(node->op()->EffectInputCount(), 1);
273 1905220 : if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
274 952610 : fully_reduced_.Add(node->id());
275 : }
276 : bool changed = false;
277 8535288 : for (int i = 0; i < node->InputCount(); ++i) {
278 3791339 : Node* input = node->InputAt(i);
279 3791339 : if (input->opcode() == IrOpcode::kFrameState) {
280 545392 : if (Node* ret = ReduceDeoptState(input, node, false)) {
281 1131 : node->ReplaceInput(i, ret);
282 : changed = true;
283 : }
284 : }
285 : }
286 952610 : if (changed) {
287 : return Changed(node);
288 : }
289 : return NoChange();
290 : }
291 :
292 :
293 : // Returns the clone if it duplicated the node, and null otherwise.
294 778473 : Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
295 3043 : bool multiple_users) {
296 : DCHECK(node->opcode() == IrOpcode::kFrameState ||
297 : node->opcode() == IrOpcode::kStateValues);
298 1865468 : if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
299 602782 : fully_reduced_.Contains(node->id())) {
300 : return nullptr;
301 : }
302 : TRACE("Reducing %s %d\n", node->op()->mnemonic(), node->id());
303 : Node* clone = nullptr;
304 28561 : bool node_multiused = node->UseCount() > 1;
305 28561 : bool multiple_users_rec = multiple_users || node_multiused;
306 441390 : for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
307 118569 : Node* input = NodeProperties::GetValueInput(node, i);
308 118569 : if (input->opcode() == IrOpcode::kStateValues) {
309 52156 : if (Node* ret = ReduceDeoptState(input, effect, multiple_users_rec)) {
310 4001 : if (node_multiused || (multiple_users && !clone)) {
311 : TRACE(" Cloning #%d", node->id());
312 1940 : node = clone = jsgraph()->graph()->CloneNode(node);
313 : TRACE(" to #%d\n", node->id());
314 : node_multiused = false;
315 : }
316 4001 : NodeProperties::ReplaceValueInput(node, ret, i);
317 : }
318 : } else {
319 66413 : if (Node* ret = ReduceStateValueInput(node, i, effect, node_multiused,
320 66413 : clone, multiple_users)) {
321 : DCHECK_NULL(clone);
322 : node_multiused = false; // Don't clone anymore.
323 : node = clone = ret;
324 : }
325 : }
326 : }
327 28561 : if (node->opcode() == IrOpcode::kFrameState) {
328 16170 : Node* outer_frame_state = NodeProperties::GetFrameStateInput(node);
329 16170 : if (outer_frame_state->opcode() == IrOpcode::kFrameState) {
330 5234 : if (Node* ret =
331 5234 : ReduceDeoptState(outer_frame_state, effect, multiple_users_rec)) {
332 2179 : if (node_multiused || (multiple_users && !clone)) {
333 : TRACE(" Cloning #%d", node->id());
334 1103 : node = clone = jsgraph()->graph()->CloneNode(node);
335 : TRACE(" to #%d\n", node->id());
336 : }
337 2179 : NodeProperties::ReplaceFrameStateInput(node, ret);
338 : }
339 : }
340 : }
341 28561 : if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
342 28561 : fully_reduced_.Add(node->id());
343 : }
344 28561 : return clone;
345 : }
346 :
347 :
348 : // Returns the clone if it duplicated the node, and null otherwise.
349 132826 : Node* EscapeAnalysisReducer::ReduceStateValueInput(Node* node, int node_index,
350 : Node* effect,
351 : bool node_multiused,
352 : bool already_cloned,
353 44166 : bool multiple_users) {
354 66413 : Node* input = SkipTypeGuards(NodeProperties::GetValueInput(node, node_index));
355 199239 : if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
356 66413 : fully_reduced_.Contains(node->id())) {
357 : return nullptr;
358 : }
359 : TRACE("Reducing State Input #%d (%s)\n", input->id(),
360 : input->op()->mnemonic());
361 : Node* clone = nullptr;
362 66413 : if (input->opcode() == IrOpcode::kFinishRegion ||
363 : input->opcode() == IrOpcode::kAllocate) {
364 14106 : if (escape_analysis()->IsVirtual(input)) {
365 12896 : if (escape_analysis()->IsCyclicObjectState(effect, input)) {
366 : // TODO(mstarzinger): Represent cyclic object states differently to
367 : // ensure the scheduler can properly handle such object states.
368 0 : compilation_failed_ = true;
369 0 : return nullptr;
370 : }
371 12896 : if (Node* object_state =
372 12896 : escape_analysis()->GetOrCreateObjectState(effect, input)) {
373 12896 : if (node_multiused || (multiple_users && !already_cloned)) {
374 : TRACE("Cloning #%d", node->id());
375 4268 : node = clone = jsgraph()->graph()->CloneNode(node);
376 : TRACE(" to #%d\n", node->id());
377 : node_multiused = false;
378 : already_cloned = true;
379 : }
380 12896 : NodeProperties::ReplaceValueInput(node, object_state, node_index);
381 : TRACE("Replaced state #%d input #%d with object state #%d\n",
382 : node->id(), input->id(), object_state->id());
383 : } else {
384 : TRACE("No object state replacement for #%d at effect #%d available.\n",
385 : input->id(), effect->id());
386 0 : UNREACHABLE();
387 : }
388 : }
389 : }
390 66413 : return clone;
391 : }
392 :
393 :
394 39760 : void EscapeAnalysisReducer::VerifyReplacement() const {
395 : #ifdef DEBUG
396 : AllNodes all(zone(), jsgraph()->graph());
397 : for (Node* node : all.reachable) {
398 : if (node->opcode() == IrOpcode::kAllocate) {
399 : CHECK(!escape_analysis_->IsVirtual(node));
400 : }
401 : }
402 : #endif // DEBUG
403 39760 : }
404 :
405 50906 : void EscapeAnalysisReducer::Finalize() {
406 85799 : for (Node* node : arguments_elements_) {
407 : DCHECK(node->opcode() == IrOpcode::kNewUnmappedArgumentsElements);
408 :
409 5037 : Node* arguments_frame = NodeProperties::GetValueInput(node, 0);
410 5037 : if (arguments_frame->opcode() != IrOpcode::kArgumentsFrame) continue;
411 6869 : Node* arguments_length = NodeProperties::GetValueInput(node, 1);
412 5037 : if (arguments_length->opcode() != IrOpcode::kArgumentsLength) continue;
413 :
414 : Node* arguments_length_state = nullptr;
415 30129 : for (Edge edge : arguments_length->use_edges()) {
416 12546 : Node* use = edge.from();
417 12546 : switch (use->opcode()) {
418 : case IrOpcode::kObjectState:
419 : case IrOpcode::kTypedObjectState:
420 : case IrOpcode::kStateValues:
421 : case IrOpcode::kTypedStateValues:
422 800 : if (!arguments_length_state) {
423 : arguments_length_state = jsgraph()->graph()->NewNode(
424 : jsgraph()->common()->ArgumentsLengthState(
425 1824 : IsRestLengthOf(arguments_length->op())));
426 : NodeProperties::SetType(arguments_length_state,
427 : Type::OtherInternal());
428 : }
429 800 : edge.UpdateTo(arguments_length_state);
430 800 : break;
431 : default:
432 : break;
433 : }
434 : }
435 :
436 : bool escaping_use = false;
437 : ZoneVector<Node*> loads(zone());
438 23198 : for (Edge edge : node->use_edges()) {
439 10987 : Node* use = edge.from();
440 16672 : if (!NodeProperties::IsValueEdge(edge)) continue;
441 11216 : if (use->use_edges().empty()) {
442 : // A node without uses is dead, so we don't have to care about it.
443 : continue;
444 : }
445 10604 : switch (use->opcode()) {
446 : case IrOpcode::kStateValues:
447 : case IrOpcode::kTypedStateValues:
448 : case IrOpcode::kObjectState:
449 : case IrOpcode::kTypedObjectState:
450 : break;
451 : case IrOpcode::kLoadElement:
452 413 : loads.push_back(use);
453 413 : break;
454 : case IrOpcode::kLoadField:
455 300 : if (FieldAccessOf(use->op()).offset == FixedArray::kLengthOffset) {
456 300 : loads.push_back(use);
457 : } else {
458 : escaping_use = true;
459 : }
460 : break;
461 : default:
462 : // If the arguments elements node node is used by an unhandled node,
463 : // then we cannot remove this allocation.
464 : escaping_use = true;
465 3813 : break;
466 : }
467 5302 : if (escaping_use) break;
468 : }
469 5037 : if (!escaping_use) {
470 : Node* arguments_elements_state = jsgraph()->graph()->NewNode(
471 : jsgraph()->common()->ArgumentsElementsState(
472 3672 : IsRestLengthOf(arguments_length->op())));
473 : NodeProperties::SetType(arguments_elements_state, Type::OtherInternal());
474 1453 : ReplaceWithValue(node, arguments_elements_state);
475 :
476 : ElementAccess stack_access;
477 1224 : stack_access.base_is_tagged = BaseTaggedness::kUntaggedBase;
478 : // Reduce base address by {kPointerSize} such that (length - index)
479 : // resolves to the right position.
480 : stack_access.header_size =
481 1224 : CommonFrameConstants::kFixedFrameSizeAboveFp - kPointerSize;
482 1224 : stack_access.type = Type::NonInternal();
483 1224 : stack_access.machine_type = MachineType::AnyTagged();
484 1224 : stack_access.write_barrier_kind = WriteBarrierKind::kNoWriteBarrier;
485 : const Operator* load_stack_op =
486 1224 : jsgraph()->simplified()->LoadElement(stack_access);
487 :
488 2977 : for (Node* load : loads) {
489 529 : switch (load->opcode()) {
490 : case IrOpcode::kLoadElement: {
491 300 : Node* index = NodeProperties::GetValueInput(load, 1);
492 : // {offset} is a reverted index starting from 1. The base address is
493 : // adapted to allow offsets starting from 1.
494 : Node* offset = jsgraph()->graph()->NewNode(
495 : jsgraph()->simplified()->NumberSubtract(), arguments_length,
496 600 : index);
497 : NodeProperties::SetType(offset,
498 300 : TypeCache::Get().kArgumentsLengthType);
499 300 : NodeProperties::ReplaceValueInput(load, arguments_frame, 0);
500 300 : NodeProperties::ReplaceValueInput(load, offset, 1);
501 300 : NodeProperties::ChangeOp(load, load_stack_op);
502 300 : break;
503 : }
504 : case IrOpcode::kLoadField: {
505 : DCHECK_EQ(FieldAccessOf(load->op()).offset,
506 : FixedArray::kLengthOffset);
507 229 : Node* length = NodeProperties::GetValueInput(node, 1);
508 : ReplaceWithValue(load, length);
509 : break;
510 : }
511 : default:
512 0 : UNREACHABLE();
513 : }
514 : }
515 : }
516 : }
517 40381 : }
518 :
519 : } // namespace compiler
520 : } // namespace internal
521 : } // namespace v8
|
