1/*
2 * Copyright (C) 2015-2019 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "DFGArgumentsEliminationPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "ArrayPrototype.h"
32#include "BytecodeLivenessAnalysisInlines.h"
33#include "ClonedArguments.h"
34#include "DFGArgumentsUtilities.h"
35#include "DFGBasicBlockInlines.h"
36#include "DFGBlockMapInlines.h"
37#include "DFGClobberize.h"
38#include "DFGCombinedLiveness.h"
39#include "DFGForAllKills.h"
40#include "DFGGraph.h"
41#include "DFGInsertionSet.h"
42#include "DFGLivenessAnalysisPhase.h"
43#include "DFGOSRAvailabilityAnalysisPhase.h"
44#include "DFGPhase.h"
45#include "JSCInlines.h"
46#include <wtf/HashSet.h>
47#include <wtf/ListDump.h>
48#include <wtf/RecursableLambda.h>
49
50namespace JSC { namespace DFG {
51
52namespace {
53
54namespace DFGArgumentsEliminationPhaseInternal {
55static const bool verbose = false;
56}
57
58class ArgumentsEliminationPhase : public Phase {
59public:
60 ArgumentsEliminationPhase(Graph& graph)
61 : Phase(graph, "arguments elimination")
62 {
63 }
64
65 bool run()
66 {
67 // For now this phase only works on SSA. This could be changed; we could have a block-local
68 // version over LoadStore.
69 DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
70
71 if (DFGArgumentsEliminationPhaseInternal::verbose) {
72 dataLog("Graph before arguments elimination:\n");
73 m_graph.dump();
74 }
75
76 identifyCandidates();
77 if (m_candidates.isEmpty())
78 return false;
79
80 eliminateCandidatesThatEscape();
81 if (m_candidates.isEmpty())
82 return false;
83
84 eliminateCandidatesThatInterfere();
85 if (m_candidates.isEmpty())
86 return false;
87
88 transform();
89
90 return true;
91 }
92
93private:
94 // Just finds nodes that we know how to work with.
95 void identifyCandidates()
96 {
97 for (BasicBlock* block : m_graph.blocksInPreOrder()) {
98 for (Node* node : *block) {
99 switch (node->op()) {
100 case CreateDirectArguments:
101 case CreateClonedArguments:
102 m_candidates.add(node);
103 break;
104
105 case CreateRest:
106 if (m_graph.isWatchingHavingABadTimeWatchpoint(node)) {
107 // If we're watching the HavingABadTime watchpoint it means that we will be invalidated
108 // when it fires (it may or may not have actually fired yet). We don't try to eliminate
109 // this allocation when we're not watching the watchpoint because it could entail calling
110 // indexed accessors (and probably more crazy things) on out of bound accesses to the
111 // rest parameter. It's also much easier to reason about this way.
112 m_candidates.add(node);
113 }
114 break;
115
116 case Spread:
117 if (m_graph.isWatchingHavingABadTimeWatchpoint(node)) {
118 // We check ArrayUse here because ArrayUse indicates that the iterator
119 // protocol for Arrays is non-observable by user code (e.g, it hasn't
120 // been changed).
121 if (node->child1().useKind() == ArrayUse) {
122 if ((node->child1()->op() == CreateRest || node->child1()->op() == NewArrayBuffer) && m_candidates.contains(node->child1().node()))
123 m_candidates.add(node);
124 }
125 }
126 break;
127
128 case NewArrayWithSpread: {
129 if (m_graph.isWatchingHavingABadTimeWatchpoint(node)) {
130 BitVector* bitVector = node->bitVector();
131 // We only allow for Spreads to be of CreateRest or NewArrayBuffer nodes for now.
132 bool isOK = true;
133 for (unsigned i = 0; i < node->numChildren(); i++) {
134 if (bitVector->get(i)) {
135 Node* child = m_graph.varArgChild(node, i).node();
136 isOK = child->op() == Spread && (child->child1()->op() == CreateRest || child->child1()->op() == NewArrayBuffer) && m_candidates.contains(child);
137 if (!isOK)
138 break;
139 }
140 }
141
142 if (!isOK)
143 break;
144
145 m_candidates.add(node);
146 }
147 break;
148 }
149
150 case NewArrayBuffer: {
151 if (m_graph.isWatchingHavingABadTimeWatchpoint(node) && !hasAnyArrayStorage(node->indexingMode()))
152 m_candidates.add(node);
153 break;
154 }
155
156 case CreateScopedArguments:
157 // FIXME: We could handle this if it wasn't for the fact that scoped arguments are
158 // always stored into the activation.
159 // https://bugs.webkit.org/show_bug.cgi?id=143072 and
160 // https://bugs.webkit.org/show_bug.cgi?id=143073
161 break;
162
163 default:
164 break;
165 }
166 if (node->isPseudoTerminal())
167 break;
168 }
169 }
170
171 if (DFGArgumentsEliminationPhaseInternal::verbose)
172 dataLog("Candidates: ", listDump(m_candidates), "\n");
173 }
174
175 bool isStillValidCandidate(Node* candidate)
176 {
177 switch (candidate->op()) {
178 case Spread:
179 return m_candidates.contains(candidate->child1().node());
180
181 case NewArrayWithSpread: {
182 BitVector* bitVector = candidate->bitVector();
183 for (unsigned i = 0; i < candidate->numChildren(); i++) {
184 if (bitVector->get(i)) {
185 if (!m_candidates.contains(m_graph.varArgChild(candidate, i).node()))
186 return false;
187 }
188 }
189 return true;
190 }
191
192 default:
193 return true;
194 }
195
196 RELEASE_ASSERT_NOT_REACHED();
197 return false;
198 }
199
200 void removeInvalidCandidates()
201 {
202 bool changed;
203 do {
204 changed = false;
205 Vector<Node*, 1> toRemove;
206
207 for (Node* candidate : m_candidates) {
208 if (!isStillValidCandidate(candidate))
209 toRemove.append(candidate);
210 }
211
212 if (toRemove.size()) {
213 changed = true;
214 for (Node* node : toRemove)
215 m_candidates.remove(node);
216 }
217
218 } while (changed);
219 }
220
221 void transitivelyRemoveCandidate(Node* node, Node* source = nullptr)
222 {
223 bool removed = m_candidates.remove(node);
224 if (removed && DFGArgumentsEliminationPhaseInternal::verbose && source)
225 dataLog("eliminating candidate: ", node, " because it escapes from: ", source, "\n");
226
227 if (removed)
228 removeInvalidCandidates();
229 }
230
231 // Look for escaping sites, and remove from the candidates set if we see an escape.
232 void eliminateCandidatesThatEscape()
233 {
234 auto escape = [&] (Edge edge, Node* source) {
235 if (!edge)
236 return;
237 transitivelyRemoveCandidate(edge.node(), source);
238 };
239
240 auto escapeBasedOnArrayMode = [&] (ArrayMode mode, Edge edge, Node* source) {
241 switch (mode.type()) {
242 case Array::DirectArguments: {
243 if (edge->op() != CreateDirectArguments) {
244 escape(edge, source);
245 break;
246 }
247
248 // Everything is fine if we're doing an in-bounds access.
249 if (mode.isInBounds())
250 break;
251
252 // If we're out-of-bounds then we proceed only if the prototype chain
253 // for the allocation is sane (i.e. doesn't have indexed properties).
254 JSGlobalObject* globalObject = m_graph.globalObjectFor(edge->origin.semantic);
255 Structure* objectPrototypeStructure = globalObject->objectPrototype()->structure(m_graph.m_vm);
256 if (objectPrototypeStructure->transitionWatchpointSetIsStillValid()
257 && globalObject->objectPrototypeIsSane()) {
258 m_graph.registerAndWatchStructureTransition(objectPrototypeStructure);
259 break;
260 }
261 escape(edge, source);
262 break;
263 }
264
265 case Array::Contiguous: {
266 if (edge->op() != CreateClonedArguments && edge->op() != CreateRest) {
267 escape(edge, source);
268 break;
269 }
270
271 // Everything is fine if we're doing an in-bounds access.
272 if (mode.isInBounds())
273 break;
274
275 // If we're out-of-bounds then we proceed only if the prototype chain
276 // for the allocation is sane (i.e. doesn't have indexed properties).
277 JSGlobalObject* globalObject = m_graph.globalObjectFor(edge->origin.semantic);
278 Structure* objectPrototypeStructure = globalObject->objectPrototype()->structure(m_graph.m_vm);
279 if (edge->op() == CreateRest) {
280 Structure* arrayPrototypeStructure = globalObject->arrayPrototype()->structure(m_graph.m_vm);
281 if (arrayPrototypeStructure->transitionWatchpointSetIsStillValid()
282 && objectPrototypeStructure->transitionWatchpointSetIsStillValid()
283 && globalObject->arrayPrototypeChainIsSane()) {
284 m_graph.registerAndWatchStructureTransition(arrayPrototypeStructure);
285 m_graph.registerAndWatchStructureTransition(objectPrototypeStructure);
286 break;
287 }
288 } else {
289 if (objectPrototypeStructure->transitionWatchpointSetIsStillValid()
290 && globalObject->objectPrototypeIsSane()) {
291 m_graph.registerAndWatchStructureTransition(objectPrototypeStructure);
292 break;
293 }
294 }
295 escape(edge, source);
296 break;
297 }
298
299 case Array::ForceExit:
300 break;
301
302 default:
303 escape(edge, source);
304 break;
305 }
306 };
307
308 removeInvalidCandidates();
309
310 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
311 for (Node* node : *block) {
312 switch (node->op()) {
313 case GetFromArguments:
314 break;
315
316 case GetByVal:
317 escapeBasedOnArrayMode(node->arrayMode(), m_graph.varArgChild(node, 0), node);
318 escape(m_graph.varArgChild(node, 1), node);
319 escape(m_graph.varArgChild(node, 2), node);
320 break;
321
322 case GetArrayLength:
323 escape(node->child2(), node);
324 // Computing the length of a NewArrayWithSpread can require some additions.
325 // These additions can overflow if the array is sufficiently enormous, and in that case we will need to exit.
326 if ((node->child1()->op() == NewArrayWithSpread) && !node->origin.exitOK)
327 escape(node->child1(), node);
328 break;
329
330 case NewArrayWithSpread: {
331 BitVector* bitVector = node->bitVector();
332 bool isWatchingHavingABadTimeWatchpoint = m_graph.isWatchingHavingABadTimeWatchpoint(node);
333 for (unsigned i = 0; i < node->numChildren(); i++) {
334 Edge child = m_graph.varArgChild(node, i);
335 bool dontEscape;
336 if (bitVector->get(i)) {
337 dontEscape = child->op() == Spread
338 && child->child1().useKind() == ArrayUse
339 && (child->child1()->op() == CreateRest || child->child1()->op() == NewArrayBuffer)
340 && isWatchingHavingABadTimeWatchpoint;
341 } else
342 dontEscape = false;
343
344 if (!dontEscape)
345 escape(child, node);
346 }
347
348 break;
349 }
350
351 case Spread: {
352 bool isOK = node->child1().useKind() == ArrayUse && (node->child1()->op() == CreateRest || node->child1()->op() == NewArrayBuffer);
353 if (!isOK)
354 escape(node->child1(), node);
355 break;
356 }
357
358 case NewArrayBuffer:
359 break;
360
361 case LoadVarargs:
362 if (node->loadVarargsData()->offset && (node->child1()->op() == NewArrayWithSpread || node->child1()->op() == Spread || node->child1()->op() == NewArrayBuffer))
363 escape(node->child1(), node);
364 break;
365
366 case CallVarargs:
367 case ConstructVarargs:
368 case TailCallVarargs:
369 case TailCallVarargsInlinedCaller:
370 escape(node->child1(), node);
371 escape(node->child2(), node);
372 if (node->callVarargsData()->firstVarArgOffset && (node->child3()->op() == NewArrayWithSpread || node->child3()->op() == Spread || node->child1()->op() == NewArrayBuffer))
373 escape(node->child3(), node);
374 break;
375
376 case Check:
377 case CheckVarargs:
378 m_graph.doToChildren(
379 node,
380 [&] (Edge edge) {
381 if (edge.willNotHaveCheck())
382 return;
383
384 if (alreadyChecked(edge.useKind(), SpecObject))
385 return;
386
387 escape(edge, node);
388 });
389 break;
390
391 case MovHint:
392 case PutHint:
393 break;
394
395 case GetButterfly:
396 // This barely works. The danger is that the GetButterfly is used by something that
397 // does something escaping to a candidate. Fortunately, the only butterfly-using ops
398 // that we exempt here also use the candidate directly. If there ever was a
399 // butterfly-using op that we wanted to exempt, then we'd have to look at the
400 // butterfly's child and check if it's a candidate.
401 break;
402
403 case FilterGetByIdStatus:
404 case FilterPutByIdStatus:
405 case FilterCallLinkStatus:
406 case FilterInByIdStatus:
407 break;
408
409 case CheckArray:
410 escapeBasedOnArrayMode(node->arrayMode(), node->child1(), node);
411 break;
412
413 case CheckStructureOrEmpty:
414 case CheckStructure: {
415 Node* target = node->child1().node();
416 if (!m_candidates.contains(target))
417 break;
418
419 Structure* structure = nullptr;
420 JSGlobalObject* globalObject = m_graph.globalObjectFor(target->origin.semantic);
421 switch (target->op()) {
422 case CreateDirectArguments:
423 structure = globalObject->directArgumentsStructure();
424 break;
425 case CreateClonedArguments:
426 structure = globalObject->clonedArgumentsStructure();
427 break;
428 case CreateRest:
429 ASSERT(m_graph.isWatchingHavingABadTimeWatchpoint(target));
430 structure = globalObject->restParameterStructure();
431 break;
432 case NewArrayWithSpread:
433 ASSERT(m_graph.isWatchingHavingABadTimeWatchpoint(target));
434 structure = globalObject->originalArrayStructureForIndexingType(ArrayWithContiguous);
435 break;
436 case NewArrayBuffer: {
437 ASSERT(m_graph.isWatchingHavingABadTimeWatchpoint(target));
438 IndexingType indexingMode = target->indexingMode();
439 ASSERT(!hasAnyArrayStorage(indexingMode));
440 structure = globalObject->originalArrayStructureForIndexingType(indexingMode);
441 break;
442 }
443 default:
444 RELEASE_ASSERT_NOT_REACHED();
445 }
446 ASSERT(structure);
447
448 if (!node->structureSet().contains(m_graph.registerStructure(structure)))
449 escape(node->child1(), node);
450 break;
451 }
452
453 // FIXME: We should be able to handle GetById/GetByOffset on callee.
454 // https://bugs.webkit.org/show_bug.cgi?id=143075
455
456 case GetByOffset:
457 if (node->child2()->op() == CreateClonedArguments && node->storageAccessData().offset == clonedArgumentsLengthPropertyOffset)
458 break;
459 FALLTHROUGH;
460 default:
461 m_graph.doToChildren(node, [&] (Edge edge) { return escape(edge, node); });
462 break;
463 }
464 if (node->isPseudoTerminal())
465 break;
466 }
467 }
468
469 if (DFGArgumentsEliminationPhaseInternal::verbose)
470 dataLog("After escape analysis: ", listDump(m_candidates), "\n");
471 }
472
473 // Anywhere that a candidate is live (in bytecode or in DFG), check if there is a chance of
474 // interference between the stack area that the arguments object copies from and the arguments
475 // object's payload. Conservatively this means that the stack region doesn't get stored to.
476 void eliminateCandidatesThatInterfere()
477 {
478 performLivenessAnalysis(m_graph);
479 performOSRAvailabilityAnalysis(m_graph);
480 m_graph.initializeNodeOwners();
481 CombinedLiveness combinedLiveness(m_graph);
482
483 BlockMap<Operands<bool>> clobberedByBlock(m_graph);
484 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
485 Operands<bool>& clobberedByThisBlock = clobberedByBlock[block];
486 clobberedByThisBlock = Operands<bool>(OperandsLike, m_graph.block(0)->variablesAtHead);
487 for (Node* node : *block) {
488 clobberize(
489 m_graph, node, NoOpClobberize(),
490 [&] (AbstractHeap heap) {
491 if (heap.kind() != Stack) {
492 ASSERT(!heap.overlaps(Stack));
493 return;
494 }
495 ASSERT(!heap.payload().isTop());
496 VirtualRegister reg(heap.payload().value32());
497 // The register may not point to an argument or local, for example if we are looking at SetArgumentCountIncludingThis.
498 if (!reg.isHeader())
499 clobberedByThisBlock.operand(reg) = true;
500 },
501 NoOpClobberize());
502 }
503 }
504
505 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
506 // Stop if we've already removed all candidates.
507 if (m_candidates.isEmpty())
508 return;
509
510 // Ignore blocks that don't write to the stack.
511 bool writesToStack = false;
512 for (unsigned i = clobberedByBlock[block].size(); i--;) {
513 if (clobberedByBlock[block][i]) {
514 writesToStack = true;
515 break;
516 }
517 }
518 if (!writesToStack)
519 continue;
520
521 forAllKillsInBlock(
522 m_graph, combinedLiveness, block,
523 [&] (unsigned nodeIndex, Node* candidate) {
524 if (!m_candidates.contains(candidate))
525 return;
526
527 // Check if this block has any clobbers that affect this candidate. This is a fairly
528 // fast check.
529 bool isClobberedByBlock = false;
530 Operands<bool>& clobberedByThisBlock = clobberedByBlock[block];
531
532 if (InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame()) {
533 if (inlineCallFrame->isVarargs()) {
534 isClobberedByBlock |= clobberedByThisBlock.operand(
535 inlineCallFrame->stackOffset + CallFrameSlot::argumentCount);
536 }
537
538 if (!isClobberedByBlock || inlineCallFrame->isClosureCall) {
539 isClobberedByBlock |= clobberedByThisBlock.operand(
540 inlineCallFrame->stackOffset + CallFrameSlot::callee);
541 }
542
543 if (!isClobberedByBlock) {
544 for (unsigned i = 0; i < inlineCallFrame->argumentCountIncludingThis - 1; ++i) {
545 VirtualRegister reg =
546 VirtualRegister(inlineCallFrame->stackOffset) +
547 CallFrame::argumentOffset(i);
548 if (clobberedByThisBlock.operand(reg)) {
549 isClobberedByBlock = true;
550 break;
551 }
552 }
553 }
554 } else {
555 // We don't include the ArgumentCount or Callee in this case because we can be
556 // damn sure that this won't be clobbered.
557 for (unsigned i = 1; i < static_cast<unsigned>(codeBlock()->numParameters()); ++i) {
558 if (clobberedByThisBlock.argument(i)) {
559 isClobberedByBlock = true;
560 break;
561 }
562 }
563 }
564
565 if (!isClobberedByBlock)
566 return;
567
568 // Check if we can immediately eliminate this candidate. If the block has a clobber
569 // for this arguments allocation, and we'd have to examine every node in the block,
570 // then we can just eliminate the candidate.
571 if (nodeIndex == block->size() && candidate->owner != block) {
572 if (DFGArgumentsEliminationPhaseInternal::verbose)
573 dataLog("eliminating candidate: ", candidate, " because it is clobbered by: ", block->at(nodeIndex), "\n");
574 transitivelyRemoveCandidate(candidate);
575 return;
576 }
577
578 // This loop considers all nodes up to the nodeIndex, excluding the nodeIndex.
579 while (nodeIndex--) {
580 Node* node = block->at(nodeIndex);
581 if (node == candidate)
582 break;
583
584 bool found = false;
585 clobberize(
586 m_graph, node, NoOpClobberize(),
587 [&] (AbstractHeap heap) {
588 if (heap.kind() == Stack && !heap.payload().isTop()) {
589 if (argumentsInvolveStackSlot(candidate, VirtualRegister(heap.payload().value32())))
590 found = true;
591 return;
592 }
593 if (heap.overlaps(Stack))
594 found = true;
595 },
596 NoOpClobberize());
597
598 if (found) {
599 if (DFGArgumentsEliminationPhaseInternal::verbose)
600 dataLog("eliminating candidate: ", candidate, " because it is clobbered by ", block->at(nodeIndex), "\n");
601 transitivelyRemoveCandidate(candidate);
602 return;
603 }
604 }
605 });
606 }
607
608 // Q: How do we handle OSR exit with a live PhantomArguments at a point where the inline call
609 // frame is dead? A: Naively we could say that PhantomArguments must escape the stack slots. But
610 // that would break PutStack sinking, which in turn would break object allocation sinking, in
611 // cases where we have a varargs call to an otherwise pure method. So, we need something smarter.
612 // For the outermost arguments, we just have a PhantomArguments that magically knows that it
613 // should load the arguments from the call frame. For the inline arguments, we have the heap map
614 // in the availabiltiy map track each possible inline argument as a promoted heap location. If the
615 // PutStacks for those arguments aren't sunk, those heap locations will map to very trivial
616 // availabilities (they will be flush availabilities). But if sinking happens then those
617 // availabilities may become whatever. OSR exit should be able to handle this quite naturally,
618 // since those availabilities speak of the stack before the optimizing compiler stack frame is
619 // torn down.
620
621 if (DFGArgumentsEliminationPhaseInternal::verbose)
622 dataLog("After interference analysis: ", listDump(m_candidates), "\n");
623 }
624
625 void transform()
626 {
627 bool modifiedCFG = false;
628
629 InsertionSet insertionSet(m_graph);
630
631 for (BasicBlock* block : m_graph.blocksInPreOrder()) {
632 Node* pseudoTerminal = nullptr;
633 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
634 Node* node = block->at(nodeIndex);
635
636 auto getArrayLength = [&] (Node* candidate) -> Node* {
637 return emitCodeToGetArgumentsArrayLength(
638 insertionSet, candidate, nodeIndex, node->origin);
639 };
640
641 auto isEliminatedAllocation = [&] (Node* candidate) -> bool {
642 if (!m_candidates.contains(candidate))
643 return false;
644 // We traverse in such a way that we are guaranteed to see a def before a use.
645 // Therefore, we should have already transformed the allocation before the use
646 // of an allocation.
647 ASSERT(candidate->op() == PhantomCreateRest || candidate->op() == PhantomDirectArguments || candidate->op() == PhantomClonedArguments
648 || candidate->op() == PhantomSpread || candidate->op() == PhantomNewArrayWithSpread || candidate->op() == PhantomNewArrayBuffer);
649 return true;
650 };
651
652 switch (node->op()) {
653 case CreateDirectArguments:
654 if (!m_candidates.contains(node))
655 break;
656
657 node->setOpAndDefaultFlags(PhantomDirectArguments);
658 break;
659
660 case CreateRest:
661 if (!m_candidates.contains(node))
662 break;
663
664 ASSERT(node->origin.exitOK);
665 ASSERT(node->child1().useKind() == Int32Use);
666 insertionSet.insertNode(
667 nodeIndex, SpecNone, Check, node->origin,
668 node->child1());
669
670 node->setOpAndDefaultFlags(PhantomCreateRest);
671 // We don't need this parameter for OSR exit, we can find out all the information
672 // we need via the static parameter count and the dynamic argument count.
673 node->child1() = Edge();
674 break;
675
676 case CreateClonedArguments:
677 if (!m_candidates.contains(node))
678 break;
679
680 node->setOpAndDefaultFlags(PhantomClonedArguments);
681 break;
682
683 case Spread:
684 if (!m_candidates.contains(node))
685 break;
686
687 node->setOpAndDefaultFlags(PhantomSpread);
688 break;
689
690 case NewArrayWithSpread:
691 if (!m_candidates.contains(node))
692 break;
693
694 node->setOpAndDefaultFlags(PhantomNewArrayWithSpread);
695 break;
696
697 case NewArrayBuffer:
698 if (!m_candidates.contains(node))
699 break;
700
701 node->setOpAndDefaultFlags(PhantomNewArrayBuffer);
702 node->child1() = Edge(insertionSet.insertConstant(nodeIndex, node->origin, node->cellOperand()));
703 break;
704
705 case GetFromArguments: {
706 Node* candidate = node->child1().node();
707 if (!isEliminatedAllocation(candidate))
708 break;
709
710 DFG_ASSERT(
711 m_graph, node, node->child1()->op() == PhantomDirectArguments, node->child1()->op());
712 VirtualRegister reg =
713 virtualRegisterForArgument(node->capturedArgumentsOffset().offset() + 1) +
714 node->origin.semantic.stackOffset();
715 StackAccessData* data = m_graph.m_stackAccessData.add(reg, FlushedJSValue);
716 node->convertToGetStack(data);
717 break;
718 }
719
720 case GetByOffset: {
721 Node* candidate = node->child2().node();
722 if (!isEliminatedAllocation(candidate))
723 break;
724
725 ASSERT(candidate->op() == PhantomClonedArguments);
726 ASSERT(node->storageAccessData().offset == clonedArgumentsLengthPropertyOffset);
727
728 // Meh, this is kind of hackish - we use an Identity so that we can reuse the
729 // getArrayLength() helper.
730 node->convertToIdentityOn(getArrayLength(candidate));
731 break;
732 }
733
734 case GetArrayLength: {
735 Node* candidate = node->child1().node();
736 if (!isEliminatedAllocation(candidate))
737 break;
738
739 node->convertToIdentityOn(getArrayLength(candidate));
740 break;
741 }
742
743 case GetByVal: {
744 // FIXME: For ClonedArguments, we would have already done a separate bounds check.
745 // This code will cause us to have two bounds checks - the original one that we
746 // already factored out in SSALoweringPhase, and the new one we insert here, which is
747 // often implicitly part of GetMyArgumentByVal. B3 will probably eliminate the
748 // second bounds check, but still - that's just silly.
749 // https://bugs.webkit.org/show_bug.cgi?id=143076
750
751 Node* candidate = m_graph.varArgChild(node, 0).node();
752 if (!isEliminatedAllocation(candidate))
753 break;
754
755 unsigned numberOfArgumentsToSkip = 0;
756 if (candidate->op() == PhantomCreateRest)
757 numberOfArgumentsToSkip = candidate->numberOfArgumentsToSkip();
758
759 Node* result = nullptr;
760 if (m_graph.varArgChild(node, 1)->isInt32Constant()) {
761 unsigned index = m_graph.varArgChild(node, 1)->asUInt32();
762 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame();
763 index += numberOfArgumentsToSkip;
764
765 bool safeToGetStack;
766 if (inlineCallFrame)
767 safeToGetStack = index < inlineCallFrame->argumentCountIncludingThis - 1;
768 else {
769 safeToGetStack =
770 index < static_cast<unsigned>(codeBlock()->numParameters()) - 1;
771 }
772 if (safeToGetStack) {
773 StackAccessData* data;
774 VirtualRegister arg = virtualRegisterForArgument(index + 1);
775 if (inlineCallFrame)
776 arg += inlineCallFrame->stackOffset;
777 data = m_graph.m_stackAccessData.add(arg, FlushedJSValue);
778
779 Node* check = nullptr;
780 if (!inlineCallFrame || inlineCallFrame->isVarargs()) {
781 check = insertionSet.insertNode(
782 nodeIndex, SpecNone, CheckInBounds, node->origin,
783 m_graph.varArgChild(node, 1), Edge(getArrayLength(candidate), Int32Use));
784 }
785
786 result = insertionSet.insertNode(
787 nodeIndex, node->prediction(), GetStack, node->origin, OpInfo(data), Edge(check, UntypedUse));
788 }
789 }
790
791 if (!result) {
792 NodeType op;
793 if (node->arrayMode().isInBounds())
794 op = GetMyArgumentByVal;
795 else
796 op = GetMyArgumentByValOutOfBounds;
797 result = insertionSet.insertNode(
798 nodeIndex, node->prediction(), op, node->origin, OpInfo(numberOfArgumentsToSkip),
799 m_graph.varArgChild(node, 0), m_graph.varArgChild(node, 1));
800 }
801
802 // Need to do this because we may have a data format conversion here.
803 node->convertToIdentityOn(result);
804 break;
805 }
806
807 case LoadVarargs: {
808 Node* candidate = node->child1().node();
809 if (!isEliminatedAllocation(candidate))
810 break;
811
812 // LoadVarargs can exit, so it better be exitOK.
813 DFG_ASSERT(m_graph, node, node->origin.exitOK);
814 bool canExit = true;
815 LoadVarargsData* varargsData = node->loadVarargsData();
816
817 auto storeArgumentCountIncludingThis = [&] (unsigned argumentCountIncludingThis) {
818 Node* argumentCountIncludingThisNode = insertionSet.insertConstant(
819 nodeIndex, node->origin.withExitOK(canExit),
820 jsNumber(argumentCountIncludingThis));
821 insertionSet.insertNode(
822 nodeIndex, SpecNone, MovHint, node->origin.takeValidExit(canExit),
823 OpInfo(varargsData->count.offset()), Edge(argumentCountIncludingThisNode));
824 insertionSet.insertNode(
825 nodeIndex, SpecNone, PutStack, node->origin.withExitOK(canExit),
826 OpInfo(m_graph.m_stackAccessData.add(varargsData->count, FlushedInt32)),
827 Edge(argumentCountIncludingThisNode, KnownInt32Use));
828 };
829
830 auto storeValue = [&] (Node* value, unsigned storeIndex) {
831 VirtualRegister reg = varargsData->start + storeIndex;
832 StackAccessData* data =
833 m_graph.m_stackAccessData.add(reg, FlushedJSValue);
834
835 insertionSet.insertNode(
836 nodeIndex, SpecNone, MovHint, node->origin.takeValidExit(canExit),
837 OpInfo(reg.offset()), Edge(value));
838 insertionSet.insertNode(
839 nodeIndex, SpecNone, PutStack, node->origin.withExitOK(canExit),
840 OpInfo(data), Edge(value));
841 };
842
843 if (candidate->op() == PhantomNewArrayWithSpread || candidate->op() == PhantomNewArrayBuffer || candidate->op() == PhantomSpread) {
844 auto canConvertToStaticLoadStores = recursableLambda([&] (auto self, Node* candidate) -> bool {
845 if (candidate->op() == PhantomSpread)
846 return self(candidate->child1().node());
847
848 if (candidate->op() == PhantomNewArrayWithSpread) {
849 BitVector* bitVector = candidate->bitVector();
850 for (unsigned i = 0; i < candidate->numChildren(); i++) {
851 if (bitVector->get(i)) {
852 if (!self(m_graph.varArgChild(candidate, i).node()))
853 return false;
854 }
855 }
856 return true;
857 }
858
859 // PhantomNewArrayBuffer only contains constants. It can always convert LoadVarargs to static load stores.
860 if (candidate->op() == PhantomNewArrayBuffer)
861 return true;
862
863 ASSERT(candidate->op() == PhantomCreateRest);
864 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame();
865 return inlineCallFrame && !inlineCallFrame->isVarargs();
866 });
867
868 if (canConvertToStaticLoadStores(candidate)) {
869 auto countNumberOfArguments = recursableLambda([&](auto self, Node* candidate) -> unsigned {
870 if (candidate->op() == PhantomSpread)
871 return self(candidate->child1().node());
872
873 if (candidate->op() == PhantomNewArrayWithSpread) {
874 BitVector* bitVector = candidate->bitVector();
875 unsigned result = 0;
876 for (unsigned i = 0; i < candidate->numChildren(); i++) {
877 if (bitVector->get(i))
878 result += self(m_graph.varArgChild(candidate, i).node());
879 else
880 ++result;
881 }
882 return result;
883 }
884
885 if (candidate->op() == PhantomNewArrayBuffer)
886 return candidate->castOperand<JSImmutableButterfly*>()->length();
887
888 ASSERT(candidate->op() == PhantomCreateRest);
889 unsigned numberOfArgumentsToSkip = candidate->numberOfArgumentsToSkip();
890 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame();
891 unsigned frameArgumentCount = inlineCallFrame->argumentCountIncludingThis - 1;
892 if (frameArgumentCount >= numberOfArgumentsToSkip)
893 return frameArgumentCount - numberOfArgumentsToSkip;
894 return 0;
895 });
896
897 unsigned argumentCountIncludingThis = 1 + countNumberOfArguments(candidate); // |this|
898 if (argumentCountIncludingThis <= varargsData->limit) {
899 storeArgumentCountIncludingThis(argumentCountIncludingThis);
900
901 DFG_ASSERT(m_graph, node, varargsData->limit - 1 >= varargsData->mandatoryMinimum, varargsData->limit, varargsData->mandatoryMinimum);
902 // Define our limit to exclude "this", since that's a bit easier to reason about.
903 unsigned limit = varargsData->limit - 1;
904
905 auto forwardNode = recursableLambda([&](auto self, Node* candidate, unsigned storeIndex) -> unsigned {
906 if (candidate->op() == PhantomSpread)
907 return self(candidate->child1().node(), storeIndex);
908
909 if (candidate->op() == PhantomNewArrayWithSpread) {
910 BitVector* bitVector = candidate->bitVector();
911 for (unsigned i = 0; i < candidate->numChildren(); i++) {
912 if (bitVector->get(i))
913 storeIndex = self(m_graph.varArgChild(candidate, i).node(), storeIndex);
914 else {
915 Node* value = m_graph.varArgChild(candidate, i).node();
916 storeValue(value, storeIndex++);
917 }
918 }
919 return storeIndex;
920 }
921
922 if (candidate->op() == PhantomNewArrayBuffer) {
923 auto* array = candidate->castOperand<JSImmutableButterfly*>();
924 for (unsigned index = 0; index < array->length(); ++index) {
925 JSValue constant;
926 if (candidate->indexingType() == ArrayWithDouble)
927 constant = jsDoubleNumber(array->get(index).asNumber());
928 else
929 constant = array->get(index);
930 Node* value = insertionSet.insertConstant(nodeIndex, node->origin.withExitOK(canExit), constant);
931 storeValue(value, storeIndex++);
932 }
933 return storeIndex;
934 }
935
936 ASSERT(candidate->op() == PhantomCreateRest);
937 unsigned numberOfArgumentsToSkip = candidate->numberOfArgumentsToSkip();
938 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame();
939 unsigned frameArgumentCount = inlineCallFrame->argumentCountIncludingThis - 1;
940 for (unsigned loadIndex = numberOfArgumentsToSkip; loadIndex < frameArgumentCount; ++loadIndex) {
941 VirtualRegister reg = virtualRegisterForArgument(loadIndex + 1) + inlineCallFrame->stackOffset;
942 StackAccessData* data = m_graph.m_stackAccessData.add(reg, FlushedJSValue);
943 Node* value = insertionSet.insertNode(
944 nodeIndex, SpecNone, GetStack, node->origin.withExitOK(canExit),
945 OpInfo(data));
946 storeValue(value, storeIndex++);
947 }
948 return storeIndex;
949 });
950
951 unsigned storeIndex = forwardNode(candidate, 0);
952 RELEASE_ASSERT(storeIndex <= limit);
953 Node* undefined = nullptr;
954 for (; storeIndex < limit; ++storeIndex) {
955 if (!undefined) {
956 undefined = insertionSet.insertConstant(
957 nodeIndex, node->origin.withExitOK(canExit), jsUndefined());
958 }
959 storeValue(undefined, storeIndex);
960 }
961
962 node->remove(m_graph);
963 node->origin.exitOK = canExit;
964 break;
965 }
966 }
967 } else {
968 unsigned numberOfArgumentsToSkip = 0;
969 if (candidate->op() == PhantomCreateRest)
970 numberOfArgumentsToSkip = candidate->numberOfArgumentsToSkip();
971 varargsData->offset += numberOfArgumentsToSkip;
972
973 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame();
974
975 if (inlineCallFrame
976 && !inlineCallFrame->isVarargs()) {
977
978 unsigned argumentCountIncludingThis = inlineCallFrame->argumentCountIncludingThis;
979 if (argumentCountIncludingThis > varargsData->offset)
980 argumentCountIncludingThis -= varargsData->offset;
981 else
982 argumentCountIncludingThis = 1;
983 RELEASE_ASSERT(argumentCountIncludingThis >= 1);
984
985 if (argumentCountIncludingThis <= varargsData->limit) {
986
987 storeArgumentCountIncludingThis(argumentCountIncludingThis);
988
989 DFG_ASSERT(m_graph, node, varargsData->limit - 1 >= varargsData->mandatoryMinimum, varargsData->limit, varargsData->mandatoryMinimum);
990 // Define our limit to exclude "this", since that's a bit easier to reason about.
991 unsigned limit = varargsData->limit - 1;
992 Node* undefined = nullptr;
993 for (unsigned storeIndex = 0; storeIndex < limit; ++storeIndex) {
994 // First determine if we have an element we can load, and load it if
995 // possible.
996
997 Node* value = nullptr;
998 unsigned loadIndex = storeIndex + varargsData->offset;
999
1000 if (loadIndex + 1 < inlineCallFrame->argumentCountIncludingThis) {
1001 VirtualRegister reg = virtualRegisterForArgument(loadIndex + 1) + inlineCallFrame->stackOffset;
1002 StackAccessData* data = m_graph.m_stackAccessData.add(
1003 reg, FlushedJSValue);
1004
1005 value = insertionSet.insertNode(
1006 nodeIndex, SpecNone, GetStack, node->origin.withExitOK(canExit),
1007 OpInfo(data));
1008 } else {
1009 // FIXME: We shouldn't have to store anything if
1010 // storeIndex >= varargsData->mandatoryMinimum, but we will still
1011 // have GetStacks in that range. So if we don't do the stores, we'll
1012 // have degenerate IR: we'll have GetStacks of something that didn't
1013 // have PutStacks.
1014 // https://bugs.webkit.org/show_bug.cgi?id=147434
1015
1016 if (!undefined) {
1017 undefined = insertionSet.insertConstant(
1018 nodeIndex, node->origin.withExitOK(canExit), jsUndefined());
1019 }
1020 value = undefined;
1021 }
1022
1023 // Now that we have a value, store it.
1024 storeValue(value, storeIndex);
1025 }
1026
1027 node->remove(m_graph);
1028 node->origin.exitOK = canExit;
1029 break;
1030 }
1031 }
1032 }
1033
1034 node->setOpAndDefaultFlags(ForwardVarargs);
1035 break;
1036 }
1037
1038 case CallVarargs:
1039 case ConstructVarargs:
1040 case TailCallVarargs:
1041 case TailCallVarargsInlinedCaller: {
1042 Node* candidate = node->child3().node();
1043 if (!isEliminatedAllocation(candidate))
1044 break;
1045
1046 auto convertToStaticArgumentCountCall = [&] (const Vector<Node*>& arguments) {
1047 unsigned firstChild = m_graph.m_varArgChildren.size();
1048 m_graph.m_varArgChildren.append(node->child1());
1049 m_graph.m_varArgChildren.append(node->child2());
1050 for (Node* argument : arguments)
1051 m_graph.m_varArgChildren.append(Edge(argument));
1052 switch (node->op()) {
1053 case CallVarargs:
1054 node->setOpAndDefaultFlags(Call);
1055 break;
1056 case ConstructVarargs:
1057 node->setOpAndDefaultFlags(Construct);
1058 break;
1059 case TailCallVarargs:
1060 node->setOpAndDefaultFlags(TailCall);
1061 break;
1062 case TailCallVarargsInlinedCaller:
1063 node->setOpAndDefaultFlags(TailCallInlinedCaller);
1064 break;
1065 default:
1066 RELEASE_ASSERT_NOT_REACHED();
1067 }
1068 node->children = AdjacencyList(
1069 AdjacencyList::Variable,
1070 firstChild, m_graph.m_varArgChildren.size() - firstChild);
1071 };
1072
1073 auto convertToForwardsCall = [&] () {
1074 switch (node->op()) {
1075 case CallVarargs:
1076 node->setOpAndDefaultFlags(CallForwardVarargs);
1077 break;
1078 case ConstructVarargs:
1079 node->setOpAndDefaultFlags(ConstructForwardVarargs);
1080 break;
1081 case TailCallVarargs:
1082 node->setOpAndDefaultFlags(TailCallForwardVarargs);
1083 break;
1084 case TailCallVarargsInlinedCaller:
1085 node->setOpAndDefaultFlags(TailCallForwardVarargsInlinedCaller);
1086 break;
1087 default:
1088 RELEASE_ASSERT_NOT_REACHED();
1089 }
1090 };
1091
1092 if (candidate->op() == PhantomNewArrayWithSpread || candidate->op() == PhantomNewArrayBuffer || candidate->op() == PhantomSpread) {
1093 auto canTransformToStaticArgumentCountCall = recursableLambda([&](auto self, Node* candidate) -> bool {
1094 if (candidate->op() == PhantomSpread)
1095 return self(candidate->child1().node());
1096
1097 if (candidate->op() == PhantomNewArrayWithSpread) {
1098 BitVector* bitVector = candidate->bitVector();
1099 for (unsigned i = 0; i < candidate->numChildren(); i++) {
1100 if (bitVector->get(i)) {
1101 Node* spread = m_graph.varArgChild(candidate, i).node();
1102 if (!self(spread))
1103 return false;
1104 }
1105 }
1106 return true;
1107 }
1108
1109 // PhantomNewArrayBuffer only contains constants. It can always convert LoadVarargs to static load stores.
1110 if (candidate->op() == PhantomNewArrayBuffer)
1111 return true;
1112
1113 ASSERT(candidate->op() == PhantomCreateRest);
1114 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame();
1115 return inlineCallFrame && !inlineCallFrame->isVarargs();
1116 });
1117
1118 if (canTransformToStaticArgumentCountCall(candidate)) {
1119 Vector<Node*> arguments;
1120 auto appendNode = recursableLambda([&](auto self, Node* candidate) -> void {
1121 if (candidate->op() == PhantomSpread) {
1122 self(candidate->child1().node());
1123 return;
1124 }
1125
1126 if (candidate->op() == PhantomNewArrayWithSpread) {
1127 BitVector* bitVector = candidate->bitVector();
1128 for (unsigned i = 0; i < candidate->numChildren(); i++) {
1129 Node* child = m_graph.varArgChild(candidate, i).node();
1130 if (bitVector->get(i))
1131 self(child);
1132 else
1133 arguments.append(child);
1134 }
1135 return;
1136 }
1137
1138 if (candidate->op() == PhantomNewArrayBuffer) {
1139 bool canExit = true;
1140 auto* array = candidate->castOperand<JSImmutableButterfly*>();
1141 for (unsigned index = 0; index < array->length(); ++index) {
1142 JSValue constant;
1143 if (candidate->indexingType() == ArrayWithDouble)
1144 constant = jsDoubleNumber(array->get(index).asNumber());
1145 else
1146 constant = array->get(index);
1147 arguments.append(insertionSet.insertConstant(nodeIndex, node->origin.withExitOK(canExit), constant));
1148 }
1149 return;
1150 }
1151
1152 ASSERT(candidate->op() == PhantomCreateRest);
1153 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame();
1154 unsigned numberOfArgumentsToSkip = candidate->numberOfArgumentsToSkip();
1155 for (unsigned i = 1 + numberOfArgumentsToSkip; i < inlineCallFrame->argumentCountIncludingThis; ++i) {
1156 StackAccessData* data = m_graph.m_stackAccessData.add(
1157 virtualRegisterForArgument(i) + inlineCallFrame->stackOffset,
1158 FlushedJSValue);
1159
1160 Node* value = insertionSet.insertNode(
1161 nodeIndex, SpecNone, GetStack, node->origin, OpInfo(data));
1162
1163 arguments.append(value);
1164 }
1165 });
1166
1167 appendNode(candidate);
1168 convertToStaticArgumentCountCall(arguments);
1169 } else
1170 convertToForwardsCall();
1171 } else {
1172 unsigned numberOfArgumentsToSkip = 0;
1173 if (candidate->op() == PhantomCreateRest)
1174 numberOfArgumentsToSkip = candidate->numberOfArgumentsToSkip();
1175 CallVarargsData* varargsData = node->callVarargsData();
1176 varargsData->firstVarArgOffset += numberOfArgumentsToSkip;
1177
1178 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame();
1179 if (inlineCallFrame && !inlineCallFrame->isVarargs()) {
1180 Vector<Node*> arguments;
1181 for (unsigned i = 1 + varargsData->firstVarArgOffset; i < inlineCallFrame->argumentCountIncludingThis; ++i) {
1182 StackAccessData* data = m_graph.m_stackAccessData.add(
1183 virtualRegisterForArgument(i) + inlineCallFrame->stackOffset,
1184 FlushedJSValue);
1185
1186 Node* value = insertionSet.insertNode(
1187 nodeIndex, SpecNone, GetStack, node->origin, OpInfo(data));
1188
1189 arguments.append(value);
1190 }
1191
1192 convertToStaticArgumentCountCall(arguments);
1193 } else
1194 convertToForwardsCall();
1195 }
1196
1197 break;
1198 }
1199
1200 case CheckArray:
1201 case GetButterfly:
1202 case FilterGetByIdStatus:
1203 case FilterPutByIdStatus:
1204 case FilterCallLinkStatus:
1205 case FilterInByIdStatus: {
1206 if (!isEliminatedAllocation(node->child1().node()))
1207 break;
1208 node->remove(m_graph);
1209 break;
1210 }
1211
1212 case CheckStructureOrEmpty:
1213 case CheckStructure:
1214 if (!isEliminatedAllocation(node->child1().node()))
1215 break;
1216 node->child1() = Edge(); // Remove the cell check since we've proven it's not needed and FTL lowering might botch this.
1217 node->remove(m_graph);
1218 break;
1219
1220 default:
1221 break;
1222 }
1223
1224 if (node->isPseudoTerminal()) {
1225 pseudoTerminal = node;
1226 break;
1227 }
1228 }
1229
1230 insertionSet.execute(block);
1231
1232 if (pseudoTerminal) {
1233 for (unsigned i = 0; i < block->size(); ++i) {
1234 Node* node = block->at(i);
1235 if (node != pseudoTerminal)
1236 continue;
1237 block->resize(i + 1);
1238 block->append(m_graph.addNode(SpecNone, Unreachable, node->origin));
1239 modifiedCFG = true;
1240 break;
1241 }
1242 }
1243 }
1244
1245 if (modifiedCFG) {
1246 m_graph.invalidateCFG();
1247 m_graph.resetReachability();
1248 m_graph.killUnreachableBlocks();
1249 }
1250 }
1251
1252 HashSet<Node*> m_candidates;
1253};
1254
1255} // anonymous namespace
1256
1257bool performArgumentsElimination(Graph& graph)
1258{
1259 return runPhase<ArgumentsEliminationPhase>(graph);
1260}
1261
1262} } // namespace JSC::DFG
1263
1264#endif // ENABLE(DFG_JIT)
1265
1266