2 * Copyright (C) 2015 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
27 #include "DFGArgumentsEliminationPhase.h"
31 #include "BytecodeLivenessAnalysisInlines.h"
32 #include "DFGArgumentsUtilities.h"
33 #include "DFGBasicBlockInlines.h"
34 #include "DFGBlockMapInlines.h"
35 #include "DFGClobberize.h"
36 #include "DFGCombinedLiveness.h"
37 #include "DFGForAllKills.h"
39 #include "DFGInsertionSet.h"
40 #include "DFGLivenessAnalysisPhase.h"
41 #include "DFGOSRAvailabilityAnalysisPhase.h"
43 #include "JSCInlines.h"
44 #include <wtf/HashMap.h>
45 #include <wtf/HashSet.h>
46 #include <wtf/ListDump.h>
48 namespace JSC
{ namespace DFG
{
54 class ArgumentsEliminationPhase
: public Phase
{
56 ArgumentsEliminationPhase(Graph
& graph
)
57 : Phase(graph
, "arguments elimination")
63 // For now this phase only works on SSA. This could be changed; we could have a block-local
64 // version over LoadStore.
65 DFG_ASSERT(m_graph
, nullptr, m_graph
.m_form
== SSA
);
68 dataLog("Graph before arguments elimination:\n");
73 if (m_candidates
.isEmpty())
76 eliminateCandidatesThatEscape();
77 if (m_candidates
.isEmpty())
80 eliminateCandidatesThatInterfere();
81 if (m_candidates
.isEmpty())
90 // Just finds nodes that we know how to work with.
91 void identifyCandidates()
93 for (BasicBlock
* block
: m_graph
.blocksInNaturalOrder()) {
94 for (Node
* node
: *block
) {
96 case CreateDirectArguments
:
97 case CreateClonedArguments
:
98 m_candidates
.add(node
);
101 case CreateScopedArguments
:
102 // FIXME: We could handle this if it wasn't for the fact that scoped arguments are
103 // always stored into the activation.
104 // https://bugs.webkit.org/show_bug.cgi?id=143072 and
105 // https://bugs.webkit.org/show_bug.cgi?id=143073
115 dataLog("Candidates: ", listDump(m_candidates
), "\n");
118 // Look for escaping sites, and remove from the candidates set if we see an escape.
119 void eliminateCandidatesThatEscape()
121 auto escape
= [&] (Edge edge
) {
124 m_candidates
.remove(edge
.node());
127 auto escapeBasedOnArrayMode
= [&] (ArrayMode mode
, Edge edge
) {
128 switch (mode
.type()) {
129 case Array::DirectArguments
:
130 if (edge
->op() != CreateDirectArguments
)
136 case Array::Contiguous
:
137 if (edge
->op() != CreateClonedArguments
)
147 for (BasicBlock
* block
: m_graph
.blocksInNaturalOrder()) {
148 for (Node
* node
: *block
) {
149 switch (node
->op()) {
150 case GetFromArguments
:
151 DFG_ASSERT(m_graph
, node
, node
->child1()->op() == CreateDirectArguments
);
155 escapeBasedOnArrayMode(node
->arrayMode(), node
->child1());
156 escape(node
->child2());
157 escape(node
->child3());
161 escapeBasedOnArrayMode(node
->arrayMode(), node
->child1());
162 escape(node
->child2());
169 case ConstructVarargs
:
170 escape(node
->child1());
171 escape(node
->child3());
175 m_graph
.doToChildren(
178 if (edge
.willNotHaveCheck())
181 if (alreadyChecked(edge
.useKind(), SpecObject
))
193 // This barely works. The danger is that the GetButterfly is used by something that
194 // does something escaping to a candidate. Fortunately, the only butterfly-using ops
195 // that we exempt here also use the candidate directly. If there ever was a
196 // butterfly-using op that we wanted to exempt, then we'd have to look at the
197 // butterfly's child and check if it's a candidate.
201 escapeBasedOnArrayMode(node
->arrayMode(), node
->child1());
204 // FIXME: For cloned arguments, we'd like to allow GetByOffset on length to not be
206 // https://bugs.webkit.org/show_bug.cgi?id=143074
208 // FIXME: We should be able to handle GetById/GetByOffset on callee.
209 // https://bugs.webkit.org/show_bug.cgi?id=143075
212 m_graph
.doToChildren(node
, escape
);
219 dataLog("After escape analysis: ", listDump(m_candidates
), "\n");
222 // Anywhere that a candidate is live (in bytecode or in DFG), check if there is a chance of
223 // interference between the stack area that the arguments object copies from and the arguments
224 // object's payload. Conservatively this means that the stack region doesn't get stored to.
225 void eliminateCandidatesThatInterfere()
227 performLivenessAnalysis(m_graph
);
228 performOSRAvailabilityAnalysis(m_graph
);
229 m_graph
.initializeNodeOwners();
230 CombinedLiveness
combinedLiveness(m_graph
);
232 BlockMap
<Operands
<bool>> clobberedByBlock(m_graph
);
233 for (BasicBlock
* block
: m_graph
.blocksInNaturalOrder()) {
234 Operands
<bool>& clobberedByThisBlock
= clobberedByBlock
[block
];
235 clobberedByThisBlock
= Operands
<bool>(OperandsLike
, m_graph
.block(0)->variablesAtHead
);
236 for (Node
* node
: *block
) {
238 m_graph
, node
, NoOpClobberize(),
239 [&] (AbstractHeap heap
) {
240 if (heap
.kind() != Stack
) {
241 ASSERT(!heap
.overlaps(Stack
));
244 ASSERT(!heap
.payload().isTop());
245 VirtualRegister
reg(heap
.payload().value32());
246 clobberedByThisBlock
.operand(reg
) = true;
252 for (BasicBlock
* block
: m_graph
.blocksInNaturalOrder()) {
253 // Stop if we've already removed all candidates.
254 if (m_candidates
.isEmpty())
257 // Ignore blocks that don't write to the stack.
258 bool writesToStack
= false;
259 for (unsigned i
= clobberedByBlock
[block
].size(); i
--;) {
260 if (clobberedByBlock
[block
][i
]) {
261 writesToStack
= true;
269 m_graph
, combinedLiveness
, block
,
270 [&] (unsigned nodeIndex
, Node
* candidate
) {
271 if (!m_candidates
.contains(candidate
))
274 // Check if this block has any clobbers that affect this candidate. This is a fairly
276 bool isClobberedByBlock
= false;
277 Operands
<bool>& clobberedByThisBlock
= clobberedByBlock
[block
];
279 if (InlineCallFrame
* inlineCallFrame
= candidate
->origin
.semantic
.inlineCallFrame
) {
280 if (inlineCallFrame
->isVarargs()) {
281 isClobberedByBlock
|= clobberedByThisBlock
.operand(
282 inlineCallFrame
->stackOffset
+ JSStack::ArgumentCount
);
285 if (!isClobberedByBlock
|| inlineCallFrame
->isClosureCall
) {
286 isClobberedByBlock
|= clobberedByThisBlock
.operand(
287 inlineCallFrame
->stackOffset
+ JSStack::Callee
);
290 if (!isClobberedByBlock
) {
291 for (unsigned i
= 0; i
< inlineCallFrame
->arguments
.size() - 1; ++i
) {
292 VirtualRegister reg
=
293 VirtualRegister(inlineCallFrame
->stackOffset
) +
294 CallFrame::argumentOffset(i
);
295 if (clobberedByThisBlock
.operand(reg
)) {
296 isClobberedByBlock
= true;
302 // We don't include the ArgumentCount or Callee in this case because we can be
303 // damn sure that this won't be clobbered.
304 for (unsigned i
= 1; i
< static_cast<unsigned>(codeBlock()->numParameters()); ++i
) {
305 if (clobberedByThisBlock
.argument(i
)) {
306 isClobberedByBlock
= true;
312 if (!isClobberedByBlock
)
315 // Check if we can immediately eliminate this candidate. If the block has a clobber
316 // for this arguments allocation, and we'd have to examine every node in the block,
317 // then we can just eliminate the candidate.
318 if (nodeIndex
== block
->size() && candidate
->owner
!= block
) {
319 m_candidates
.remove(candidate
);
323 // This loop considers all nodes up to the nodeIndex, excluding the nodeIndex.
324 while (nodeIndex
--) {
325 Node
* node
= block
->at(nodeIndex
);
326 if (node
== candidate
)
331 m_graph
, node
, NoOpClobberize(),
332 [&] (AbstractHeap heap
) {
333 if (heap
.kind() == Stack
&& !heap
.payload().isTop()) {
334 if (argumentsInvolveStackSlot(candidate
, VirtualRegister(heap
.payload().value32())))
338 if (heap
.overlaps(Stack
))
344 m_candidates
.remove(candidate
);
351 // Q: How do we handle OSR exit with a live PhantomArguments at a point where the inline call
352 // frame is dead? A: Naively we could say that PhantomArguments must escape the stack slots. But
353 // that would break PutStack sinking, which in turn would break object allocation sinking, in
354 // cases where we have a varargs call to an otherwise pure method. So, we need something smarter.
355 // For the outermost arguments, we just have a PhantomArguments that magically knows that it
356 // should load the arguments from the call frame. For the inline arguments, we have the heap map
357 // in the availabiltiy map track each possible inline argument as a promoted heap location. If the
358 // PutStacks for those arguments aren't sunk, those heap locations will map to very trivial
359 // availabilities (they will be flush availabilities). But if sinking happens then those
360 // availabilities may become whatever. OSR exit should be able to handle this quite naturally,
361 // since those availabilities speak of the stack before the optimizing compiler stack frame is
365 dataLog("After interference analysis: ", listDump(m_candidates
), "\n");
370 InsertionSet
insertionSet(m_graph
);
372 for (BasicBlock
* block
: m_graph
.blocksInNaturalOrder()) {
373 for (unsigned nodeIndex
= 0; nodeIndex
< block
->size(); ++nodeIndex
) {
374 Node
* node
= block
->at(nodeIndex
);
376 auto getArrayLength
= [&] (Node
* candidate
) -> Node
* {
377 return emitCodeToGetArgumentsArrayLength(
378 insertionSet
, candidate
, nodeIndex
, node
->origin
);
381 switch (node
->op()) {
382 case CreateDirectArguments
:
383 if (!m_candidates
.contains(node
))
386 node
->setOpAndDefaultFlags(PhantomDirectArguments
);
389 case CreateClonedArguments
:
390 if (!m_candidates
.contains(node
))
393 node
->setOpAndDefaultFlags(PhantomClonedArguments
);
396 case GetFromArguments
: {
397 Node
* candidate
= node
->child1().node();
398 if (!m_candidates
.contains(candidate
))
403 node
->child1()->op() == CreateDirectArguments
404 || node
->child1()->op() == PhantomDirectArguments
);
405 VirtualRegister reg
=
406 virtualRegisterForArgument(node
->capturedArgumentsOffset().offset() + 1) +
407 node
->origin
.semantic
.stackOffset();
408 StackAccessData
* data
= m_graph
.m_stackAccessData
.add(reg
, FlushedJSValue
);
409 node
->convertToGetStack(data
);
413 case GetArrayLength
: {
414 Node
* candidate
= node
->child1().node();
415 if (!m_candidates
.contains(candidate
))
418 // Meh, this is kind of hackish - we use an Identity so that we can reuse the
419 // getArrayLength() helper.
420 node
->convertToIdentityOn(getArrayLength(candidate
));
425 // FIXME: For ClonedArguments, we would have already done a separate bounds check.
426 // This code will cause us to have two bounds checks - the original one that we
427 // already factored out in SSALoweringPhase, and the new one we insert here, which is
428 // often implicitly part of GetMyArgumentByVal. LLVM will probably eliminate the
429 // second bounds check, but still - that's just silly.
430 // https://bugs.webkit.org/show_bug.cgi?id=143076
432 Node
* candidate
= node
->child1().node();
433 if (!m_candidates
.contains(candidate
))
436 Node
* result
= nullptr;
437 if (node
->child2()->isInt32Constant()) {
438 unsigned index
= node
->child2()->asUInt32();
439 InlineCallFrame
* inlineCallFrame
= candidate
->origin
.semantic
.inlineCallFrame
;
443 safeToGetStack
= index
< inlineCallFrame
->arguments
.size() - 1;
446 index
< static_cast<unsigned>(codeBlock()->numParameters()) - 1;
448 if (safeToGetStack
) {
449 StackAccessData
* data
;
450 VirtualRegister arg
= virtualRegisterForArgument(index
+ 1);
452 arg
+= inlineCallFrame
->stackOffset
;
453 data
= m_graph
.m_stackAccessData
.add(arg
, FlushedJSValue
);
455 if (!inlineCallFrame
|| inlineCallFrame
->isVarargs()
456 || index
>= inlineCallFrame
->arguments
.size() - 1) {
457 insertionSet
.insertNode(
458 nodeIndex
, SpecNone
, CheckInBounds
, node
->origin
,
459 node
->child2(), Edge(getArrayLength(candidate
), Int32Use
));
462 result
= insertionSet
.insertNode(
463 nodeIndex
, node
->prediction(), GetStack
, node
->origin
, OpInfo(data
));
468 result
= insertionSet
.insertNode(
469 nodeIndex
, node
->prediction(), GetMyArgumentByVal
, node
->origin
,
470 node
->child1(), node
->child2());
473 // Need to do this because we may have a data format conversion here.
474 node
->convertToIdentityOn(result
);
479 Node
* candidate
= node
->child1().node();
480 if (!m_candidates
.contains(candidate
))
483 LoadVarargsData
* varargsData
= node
->loadVarargsData();
484 InlineCallFrame
* inlineCallFrame
= candidate
->origin
.semantic
.inlineCallFrame
;
486 && !inlineCallFrame
->isVarargs()
487 && inlineCallFrame
->arguments
.size() - varargsData
->offset
<= varargsData
->limit
) {
488 Node
* argumentCount
= insertionSet
.insertConstant(
489 nodeIndex
, node
->origin
,
490 jsNumber(inlineCallFrame
->arguments
.size() - varargsData
->offset
));
491 insertionSet
.insertNode(
492 nodeIndex
, SpecNone
, MovHint
, node
->origin
,
493 OpInfo(varargsData
->count
.offset()), Edge(argumentCount
));
494 insertionSet
.insertNode(
495 nodeIndex
, SpecNone
, PutStack
, node
->origin
,
496 OpInfo(m_graph
.m_stackAccessData
.add(varargsData
->count
, FlushedInt32
)),
497 Edge(argumentCount
, Int32Use
));
499 DFG_ASSERT(m_graph
, node
, varargsData
->limit
- 1 >= varargsData
->mandatoryMinimum
);
500 // Define our limit to not include "this", since that's a bit easier to reason about.
501 unsigned limit
= varargsData
->limit
- 1;
502 Node
* undefined
= nullptr;
503 for (unsigned storeIndex
= 0; storeIndex
< limit
; ++storeIndex
) {
504 // First determine if we have an element we can load, and load it if
507 unsigned loadIndex
= storeIndex
+ varargsData
->offset
;
510 if (loadIndex
+ 1 < inlineCallFrame
->arguments
.size()) {
511 VirtualRegister reg
=
512 virtualRegisterForArgument(loadIndex
+ 1) +
513 inlineCallFrame
->stackOffset
;
514 StackAccessData
* data
= m_graph
.m_stackAccessData
.add(
515 reg
, FlushedJSValue
);
517 value
= insertionSet
.insertNode(
518 nodeIndex
, SpecNone
, GetStack
, node
->origin
, OpInfo(data
));
520 // FIXME: We shouldn't have to store anything if
521 // storeIndex >= varargsData->mandatoryMinimum, but we will still
522 // have GetStacks in that range. So if we don't do the stores, we'll
523 // have degenerate IR: we'll have GetStacks of something that didn't
525 // https://bugs.webkit.org/show_bug.cgi?id=147434
528 undefined
= insertionSet
.insertConstant(
529 nodeIndex
, node
->origin
, jsUndefined());
534 // Now that we have a value, store it.
536 VirtualRegister reg
= varargsData
->start
+ storeIndex
;
537 StackAccessData
* data
=
538 m_graph
.m_stackAccessData
.add(reg
, FlushedJSValue
);
540 insertionSet
.insertNode(
541 nodeIndex
, SpecNone
, MovHint
, node
->origin
, OpInfo(reg
.offset()),
543 insertionSet
.insertNode(
544 nodeIndex
, SpecNone
, PutStack
, node
->origin
, OpInfo(data
),
552 node
->setOpAndDefaultFlags(ForwardVarargs
);
557 case ConstructVarargs
: {
558 Node
* candidate
= node
->child2().node();
559 if (!m_candidates
.contains(candidate
))
562 CallVarargsData
* varargsData
= node
->callVarargsData();
563 InlineCallFrame
* inlineCallFrame
= candidate
->origin
.semantic
.inlineCallFrame
;
564 if (inlineCallFrame
&& !inlineCallFrame
->isVarargs()) {
565 Vector
<Node
*> arguments
;
566 for (unsigned i
= 1 + varargsData
->firstVarArgOffset
; i
< inlineCallFrame
->arguments
.size(); ++i
) {
567 StackAccessData
* data
= m_graph
.m_stackAccessData
.add(
568 virtualRegisterForArgument(i
) + inlineCallFrame
->stackOffset
,
571 Node
* value
= insertionSet
.insertNode(
572 nodeIndex
, SpecNone
, GetStack
, node
->origin
, OpInfo(data
));
574 arguments
.append(value
);
577 unsigned firstChild
= m_graph
.m_varArgChildren
.size();
578 m_graph
.m_varArgChildren
.append(node
->child1());
579 m_graph
.m_varArgChildren
.append(node
->child3());
580 for (Node
* argument
: arguments
)
581 m_graph
.m_varArgChildren
.append(Edge(argument
));
582 node
->setOpAndDefaultFlags(
583 node
->op() == CallVarargs
? Call
: Construct
);
584 node
->children
= AdjacencyList(
585 AdjacencyList::Variable
,
586 firstChild
, m_graph
.m_varArgChildren
.size() - firstChild
);
590 node
->setOpAndDefaultFlags(
591 node
->op() == CallVarargs
? CallForwardVarargs
: ConstructForwardVarargs
);
597 if (!m_candidates
.contains(node
->child1().node()))
608 insertionSet
.execute(block
);
612 HashSet
<Node
*> m_candidates
;
615 } // anonymous namespace
617 bool performArgumentsElimination(Graph
& graph
)
619 SamplingRegion
samplingRegion("DFG Arguments Elimination Phase");
620 return runPhase
<ArgumentsEliminationPhase
>(graph
);
623 } } // namespace JSC::DFG
625 #endif // ENABLE(DFG_JIT)