]> git.saurik.com Git - apple/javascriptcore.git/blob - dfg/DFGArgumentsEliminationPhase.cpp
JavaScriptCore-7601.1.46.3.tar.gz
[apple/javascriptcore.git] / dfg / DFGArgumentsEliminationPhase.cpp
1 /*
2 * Copyright (C) 2015 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 "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"
38 #include "DFGGraph.h"
39 #include "DFGInsertionSet.h"
40 #include "DFGLivenessAnalysisPhase.h"
41 #include "DFGOSRAvailabilityAnalysisPhase.h"
42 #include "DFGPhase.h"
43 #include "JSCInlines.h"
44 #include <wtf/HashMap.h>
45 #include <wtf/HashSet.h>
46 #include <wtf/ListDump.h>
47
48 namespace JSC { namespace DFG {
49
50 namespace {
51
52 bool verbose = false;
53
54 class ArgumentsEliminationPhase : public Phase {
55 public:
56 ArgumentsEliminationPhase(Graph& graph)
57 : Phase(graph, "arguments elimination")
58 {
59 }
60
61 bool run()
62 {
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);
66
67 if (verbose) {
68 dataLog("Graph before arguments elimination:\n");
69 m_graph.dump();
70 }
71
72 identifyCandidates();
73 if (m_candidates.isEmpty())
74 return false;
75
76 eliminateCandidatesThatEscape();
77 if (m_candidates.isEmpty())
78 return false;
79
80 eliminateCandidatesThatInterfere();
81 if (m_candidates.isEmpty())
82 return false;
83
84 transform();
85
86 return true;
87 }
88
89 private:
90 // Just finds nodes that we know how to work with.
91 void identifyCandidates()
92 {
93 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
94 for (Node* node : *block) {
95 switch (node->op()) {
96 case CreateDirectArguments:
97 case CreateClonedArguments:
98 m_candidates.add(node);
99 break;
100
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
106 break;
107
108 default:
109 break;
110 }
111 }
112 }
113
114 if (verbose)
115 dataLog("Candidates: ", listDump(m_candidates), "\n");
116 }
117
118 // Look for escaping sites, and remove from the candidates set if we see an escape.
119 void eliminateCandidatesThatEscape()
120 {
121 auto escape = [&] (Edge edge) {
122 if (!edge)
123 return;
124 m_candidates.remove(edge.node());
125 };
126
127 auto escapeBasedOnArrayMode = [&] (ArrayMode mode, Edge edge) {
128 switch (mode.type()) {
129 case Array::DirectArguments:
130 if (edge->op() != CreateDirectArguments)
131 escape(edge);
132 break;
133
134 case Array::Int32:
135 case Array::Double:
136 case Array::Contiguous:
137 if (edge->op() != CreateClonedArguments)
138 escape(edge);
139 break;
140
141 default:
142 escape(edge);
143 break;
144 }
145 };
146
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);
152 break;
153
154 case GetByVal:
155 escapeBasedOnArrayMode(node->arrayMode(), node->child1());
156 escape(node->child2());
157 escape(node->child3());
158 break;
159
160 case GetArrayLength:
161 escapeBasedOnArrayMode(node->arrayMode(), node->child1());
162 escape(node->child2());
163 break;
164
165 case LoadVarargs:
166 break;
167
168 case CallVarargs:
169 case ConstructVarargs:
170 escape(node->child1());
171 escape(node->child3());
172 break;
173
174 case Check:
175 m_graph.doToChildren(
176 node,
177 [&] (Edge edge) {
178 if (edge.willNotHaveCheck())
179 return;
180
181 if (alreadyChecked(edge.useKind(), SpecObject))
182 return;
183
184 escape(edge);
185 });
186 break;
187
188 case MovHint:
189 case PutHint:
190 break;
191
192 case GetButterfly:
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.
198 break;
199
200 case CheckArray:
201 escapeBasedOnArrayMode(node->arrayMode(), node->child1());
202 break;
203
204 // FIXME: For cloned arguments, we'd like to allow GetByOffset on length to not be
205 // an escape.
206 // https://bugs.webkit.org/show_bug.cgi?id=143074
207
208 // FIXME: We should be able to handle GetById/GetByOffset on callee.
209 // https://bugs.webkit.org/show_bug.cgi?id=143075
210
211 default:
212 m_graph.doToChildren(node, escape);
213 break;
214 }
215 }
216 }
217
218 if (verbose)
219 dataLog("After escape analysis: ", listDump(m_candidates), "\n");
220 }
221
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()
226 {
227 performLivenessAnalysis(m_graph);
228 performOSRAvailabilityAnalysis(m_graph);
229 m_graph.initializeNodeOwners();
230 CombinedLiveness combinedLiveness(m_graph);
231
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) {
237 clobberize(
238 m_graph, node, NoOpClobberize(),
239 [&] (AbstractHeap heap) {
240 if (heap.kind() != Stack) {
241 ASSERT(!heap.overlaps(Stack));
242 return;
243 }
244 ASSERT(!heap.payload().isTop());
245 VirtualRegister reg(heap.payload().value32());
246 clobberedByThisBlock.operand(reg) = true;
247 },
248 NoOpClobberize());
249 }
250 }
251
252 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
253 // Stop if we've already removed all candidates.
254 if (m_candidates.isEmpty())
255 return;
256
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;
262 break;
263 }
264 }
265 if (!writesToStack)
266 continue;
267
268 forAllKillsInBlock(
269 m_graph, combinedLiveness, block,
270 [&] (unsigned nodeIndex, Node* candidate) {
271 if (!m_candidates.contains(candidate))
272 return;
273
274 // Check if this block has any clobbers that affect this candidate. This is a fairly
275 // fast check.
276 bool isClobberedByBlock = false;
277 Operands<bool>& clobberedByThisBlock = clobberedByBlock[block];
278
279 if (InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame) {
280 if (inlineCallFrame->isVarargs()) {
281 isClobberedByBlock |= clobberedByThisBlock.operand(
282 inlineCallFrame->stackOffset + JSStack::ArgumentCount);
283 }
284
285 if (!isClobberedByBlock || inlineCallFrame->isClosureCall) {
286 isClobberedByBlock |= clobberedByThisBlock.operand(
287 inlineCallFrame->stackOffset + JSStack::Callee);
288 }
289
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;
297 break;
298 }
299 }
300 }
301 } else {
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;
307 break;
308 }
309 }
310 }
311
312 if (!isClobberedByBlock)
313 return;
314
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);
320 return;
321 }
322
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)
327 break;
328
329 bool found = false;
330 clobberize(
331 m_graph, node, NoOpClobberize(),
332 [&] (AbstractHeap heap) {
333 if (heap.kind() == Stack && !heap.payload().isTop()) {
334 if (argumentsInvolveStackSlot(candidate, VirtualRegister(heap.payload().value32())))
335 found = true;
336 return;
337 }
338 if (heap.overlaps(Stack))
339 found = true;
340 },
341 NoOpClobberize());
342
343 if (found) {
344 m_candidates.remove(candidate);
345 return;
346 }
347 }
348 });
349 }
350
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
362 // torn down.
363
364 if (verbose)
365 dataLog("After interference analysis: ", listDump(m_candidates), "\n");
366 }
367
368 void transform()
369 {
370 InsertionSet insertionSet(m_graph);
371
372 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
373 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
374 Node* node = block->at(nodeIndex);
375
376 auto getArrayLength = [&] (Node* candidate) -> Node* {
377 return emitCodeToGetArgumentsArrayLength(
378 insertionSet, candidate, nodeIndex, node->origin);
379 };
380
381 switch (node->op()) {
382 case CreateDirectArguments:
383 if (!m_candidates.contains(node))
384 break;
385
386 node->setOpAndDefaultFlags(PhantomDirectArguments);
387 break;
388
389 case CreateClonedArguments:
390 if (!m_candidates.contains(node))
391 break;
392
393 node->setOpAndDefaultFlags(PhantomClonedArguments);
394 break;
395
396 case GetFromArguments: {
397 Node* candidate = node->child1().node();
398 if (!m_candidates.contains(candidate))
399 break;
400
401 DFG_ASSERT(
402 m_graph, node,
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);
410 break;
411 }
412
413 case GetArrayLength: {
414 Node* candidate = node->child1().node();
415 if (!m_candidates.contains(candidate))
416 break;
417
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));
421 break;
422 }
423
424 case GetByVal: {
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
431
432 Node* candidate = node->child1().node();
433 if (!m_candidates.contains(candidate))
434 break;
435
436 Node* result = nullptr;
437 if (node->child2()->isInt32Constant()) {
438 unsigned index = node->child2()->asUInt32();
439 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame;
440
441 bool safeToGetStack;
442 if (inlineCallFrame)
443 safeToGetStack = index < inlineCallFrame->arguments.size() - 1;
444 else {
445 safeToGetStack =
446 index < static_cast<unsigned>(codeBlock()->numParameters()) - 1;
447 }
448 if (safeToGetStack) {
449 StackAccessData* data;
450 VirtualRegister arg = virtualRegisterForArgument(index + 1);
451 if (inlineCallFrame)
452 arg += inlineCallFrame->stackOffset;
453 data = m_graph.m_stackAccessData.add(arg, FlushedJSValue);
454
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));
460 }
461
462 result = insertionSet.insertNode(
463 nodeIndex, node->prediction(), GetStack, node->origin, OpInfo(data));
464 }
465 }
466
467 if (!result) {
468 result = insertionSet.insertNode(
469 nodeIndex, node->prediction(), GetMyArgumentByVal, node->origin,
470 node->child1(), node->child2());
471 }
472
473 // Need to do this because we may have a data format conversion here.
474 node->convertToIdentityOn(result);
475 break;
476 }
477
478 case LoadVarargs: {
479 Node* candidate = node->child1().node();
480 if (!m_candidates.contains(candidate))
481 break;
482
483 LoadVarargsData* varargsData = node->loadVarargsData();
484 InlineCallFrame* inlineCallFrame = candidate->origin.semantic.inlineCallFrame;
485 if (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));
498
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
505 // possible.
506
507 unsigned loadIndex = storeIndex + varargsData->offset;
508
509 Node* value;
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);
516
517 value = insertionSet.insertNode(
518 nodeIndex, SpecNone, GetStack, node->origin, OpInfo(data));
519 } else {
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
524 // have PutStacks.
525 // https://bugs.webkit.org/show_bug.cgi?id=147434
526
527 if (!undefined) {
528 undefined = insertionSet.insertConstant(
529 nodeIndex, node->origin, jsUndefined());
530 }
531 value = undefined;
532 }
533
534 // Now that we have a value, store it.
535
536 VirtualRegister reg = varargsData->start + storeIndex;
537 StackAccessData* data =
538 m_graph.m_stackAccessData.add(reg, FlushedJSValue);
539
540 insertionSet.insertNode(
541 nodeIndex, SpecNone, MovHint, node->origin, OpInfo(reg.offset()),
542 Edge(value));
543 insertionSet.insertNode(
544 nodeIndex, SpecNone, PutStack, node->origin, OpInfo(data),
545 Edge(value));
546 }
547
548 node->remove();
549 break;
550 }
551
552 node->setOpAndDefaultFlags(ForwardVarargs);
553 break;
554 }
555
556 case CallVarargs:
557 case ConstructVarargs: {
558 Node* candidate = node->child2().node();
559 if (!m_candidates.contains(candidate))
560 break;
561
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,
569 FlushedJSValue);
570
571 Node* value = insertionSet.insertNode(
572 nodeIndex, SpecNone, GetStack, node->origin, OpInfo(data));
573
574 arguments.append(value);
575 }
576
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);
587 break;
588 }
589
590 node->setOpAndDefaultFlags(
591 node->op() == CallVarargs ? CallForwardVarargs : ConstructForwardVarargs);
592 break;
593 }
594
595 case CheckArray:
596 case GetButterfly: {
597 if (!m_candidates.contains(node->child1().node()))
598 break;
599 node->remove();
600 break;
601 }
602
603 default:
604 break;
605 }
606 }
607
608 insertionSet.execute(block);
609 }
610 }
611
612 HashSet<Node*> m_candidates;
613 };
614
615 } // anonymous namespace
616
617 bool performArgumentsElimination(Graph& graph)
618 {
619 SamplingRegion samplingRegion("DFG Arguments Elimination Phase");
620 return runPhase<ArgumentsEliminationPhase>(graph);
621 }
622
623 } } // namespace JSC::DFG
624
625 #endif // ENABLE(DFG_JIT)
626