1/*
2 * Copyright (C) 2015-2018 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 "DFGVarargsForwardingPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "ClonedArguments.h"
32#include "DFGArgumentsUtilities.h"
33#include "DFGClobberize.h"
34#include "DFGForAllKills.h"
35#include "DFGGraph.h"
36#include "DFGPhase.h"
37#include "JSCInlines.h"
38#include <wtf/ListDump.h>
39
40namespace JSC { namespace DFG {
41
42namespace {
43
44namespace DFGVarargsForwardingPhaseInternal {
45static const bool verbose = false;
46}
47
48class VarargsForwardingPhase : public Phase {
49public:
50 VarargsForwardingPhase(Graph& graph)
51 : Phase(graph, "varargs forwarding")
52 {
53 }
54
55 bool run()
56 {
57 DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA);
58
59 if (DFGVarargsForwardingPhaseInternal::verbose) {
60 dataLog("Graph before varargs forwarding:\n");
61 m_graph.dump();
62 }
63
64 m_changed = false;
65 for (BasicBlock* block : m_graph.blocksInNaturalOrder())
66 handleBlock(block);
67 return m_changed;
68 }
69
70private:
71 void handleBlock(BasicBlock* block)
72 {
73 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
74 Node* node = block->at(nodeIndex);
75 switch (node->op()) {
76 case CreateDirectArguments:
77 case CreateClonedArguments:
78 handleCandidate(block, nodeIndex);
79 break;
80 default:
81 break;
82 }
83 }
84 }
85
86 void handleCandidate(BasicBlock* block, unsigned candidateNodeIndex)
87 {
88 // We expect calls into this function to be rare. So, this is written in a simple O(n) manner.
89
90 Node* candidate = block->at(candidateNodeIndex);
91 if (DFGVarargsForwardingPhaseInternal::verbose)
92 dataLog("Handling candidate ", candidate, "\n");
93
94 // We eliminate GetButterfly over CreateClonedArguments if the butterfly is only
95 // used by a GetByOffset that loads the CreateClonedArguments's length. We also
96 // eliminate it if the GetButterfly node is totally unused.
97 Vector<Node*, 1> candidateButterflies;
98
99 // Find the index of the last node in this block to use the candidate, and look for escaping
100 // sites.
101 unsigned lastUserIndex = candidateNodeIndex;
102 Vector<VirtualRegister, 2> relevantLocals; // This is a set. We expect it to be a small set.
103 for (unsigned nodeIndex = candidateNodeIndex + 1; nodeIndex < block->size(); ++nodeIndex) {
104 Node* node = block->at(nodeIndex);
105
106 auto defaultEscape = [&] {
107 if (m_graph.uses(node, candidate)) {
108 if (DFGVarargsForwardingPhaseInternal::verbose)
109 dataLog(" Escape at ", node, "\n");
110 return true;
111 }
112 return false;
113 };
114
115 bool validGetByOffset = false;
116 switch (node->op()) {
117 case MovHint:
118 if (node->child1() != candidate)
119 break;
120 lastUserIndex = nodeIndex;
121 if (!relevantLocals.contains(node->unlinkedLocal()))
122 relevantLocals.append(node->unlinkedLocal());
123 break;
124
125 case CheckVarargs:
126 case Check: {
127 bool sawEscape = false;
128 m_graph.doToChildren(
129 node,
130 [&] (Edge edge) {
131 if (edge == candidate)
132 lastUserIndex = nodeIndex;
133
134 if (edge.willNotHaveCheck())
135 return;
136
137 if (alreadyChecked(edge.useKind(), SpecObject))
138 return;
139
140 sawEscape = true;
141 });
142 if (sawEscape) {
143 if (DFGVarargsForwardingPhaseInternal::verbose)
144 dataLog(" Escape at ", node, "\n");
145 return;
146 }
147 break;
148 }
149
150 case LoadVarargs:
151 if (m_graph.uses(node, candidate))
152 lastUserIndex = nodeIndex;
153 break;
154
155 case CallVarargs:
156 case ConstructVarargs:
157 case TailCallVarargs:
158 case TailCallVarargsInlinedCaller:
159 if (node->child1() == candidate || node->child2() == candidate) {
160 if (DFGVarargsForwardingPhaseInternal::verbose)
161 dataLog(" Escape at ", node, "\n");
162 return;
163 }
164 if (node->child2() == candidate)
165 lastUserIndex = nodeIndex;
166 break;
167
168 case SetLocal:
169 if (node->child1() == candidate && node->variableAccessData()->isLoadedFrom()) {
170 if (DFGVarargsForwardingPhaseInternal::verbose)
171 dataLog(" Escape at ", node, "\n");
172 return;
173 }
174 break;
175
176 case GetArrayLength: {
177 if (node->arrayMode().type() == Array::DirectArguments && node->child1() == candidate && node->child1()->op() == CreateDirectArguments) {
178 lastUserIndex = nodeIndex;
179 break;
180 }
181 if (defaultEscape())
182 return;
183 break;
184 }
185
186 case GetButterfly: {
187 if (node->child1() == candidate && candidate->op() == CreateClonedArguments) {
188 lastUserIndex = nodeIndex;
189 candidateButterflies.append(node);
190 break;
191 }
192 if (defaultEscape())
193 return;
194 break;
195 }
196
197 case FilterGetByIdStatus:
198 case FilterPutByIdStatus:
199 case FilterCallLinkStatus:
200 case FilterInByIdStatus:
201 break;
202
203 case GetByOffset: {
204 if (node->child1()->op() == GetButterfly
205 && candidateButterflies.contains(node->child1().node())
206 && node->child2() == candidate
207 && node->storageAccessData().offset == clonedArgumentsLengthPropertyOffset) {
208 ASSERT(node->child1()->child1() == candidate);
209 ASSERT(isOutOfLineOffset(clonedArgumentsLengthPropertyOffset));
210 // We're good to go. This is getting the length of the arguments.
211 lastUserIndex = nodeIndex;
212 validGetByOffset = true;
213 break;
214 }
215 if (defaultEscape())
216 return;
217 break;
218 }
219
220 default:
221 if (defaultEscape())
222 return;
223 break;
224 }
225
226 if (!validGetByOffset) {
227 for (Node* butterfly : candidateButterflies) {
228 if (m_graph.uses(node, butterfly)) {
229 if (DFGVarargsForwardingPhaseInternal::verbose)
230 dataLog(" Butterfly escaped at ", node, "\n");
231 return;
232 }
233 }
234 }
235
236 forAllKilledOperands(
237 m_graph, node, block->tryAt(nodeIndex + 1),
238 [&] (VirtualRegister reg) {
239 if (DFGVarargsForwardingPhaseInternal::verbose)
240 dataLog(" Killing ", reg, " while we are interested in ", listDump(relevantLocals), "\n");
241 for (unsigned i = 0; i < relevantLocals.size(); ++i) {
242 if (relevantLocals[i] == reg) {
243 relevantLocals[i--] = relevantLocals.last();
244 relevantLocals.removeLast();
245 lastUserIndex = nodeIndex;
246 }
247 }
248 });
249 }
250 if (DFGVarargsForwardingPhaseInternal::verbose)
251 dataLog("Selected lastUserIndex = ", lastUserIndex, ", ", block->at(lastUserIndex), "\n");
252
253 // We're still in business. Determine if between the candidate and the last user there is any
254 // effect that could interfere with sinking.
255 for (unsigned nodeIndex = candidateNodeIndex + 1; nodeIndex <= lastUserIndex; ++nodeIndex) {
256 Node* node = block->at(nodeIndex);
257
258 // We have our own custom switch to detect some interferences that clobberize() wouldn't know
259 // about, and also some of the common ones, too. In particular, clobberize() doesn't know
260 // that Flush, MovHint, ZombieHint, and KillStack are bad because it's not worried about
261 // what gets read on OSR exit.
262 switch (node->op()) {
263 case MovHint:
264 case ZombieHint:
265 case KillStack:
266 if (argumentsInvolveStackSlot(candidate, node->unlinkedLocal())) {
267 if (DFGVarargsForwardingPhaseInternal::verbose)
268 dataLog(" Interference at ", node, "\n");
269 return;
270 }
271 break;
272
273 case PutStack:
274 if (argumentsInvolveStackSlot(candidate, node->stackAccessData()->local)) {
275 if (DFGVarargsForwardingPhaseInternal::verbose)
276 dataLog(" Interference at ", node, "\n");
277 return;
278 }
279 break;
280
281 case SetLocal:
282 case Flush:
283 if (argumentsInvolveStackSlot(candidate, node->local())) {
284 if (DFGVarargsForwardingPhaseInternal::verbose)
285 dataLog(" Interference at ", node, "\n");
286 return;
287 }
288 break;
289
290 default: {
291 bool doesInterfere = false;
292 clobberize(
293 m_graph, node, NoOpClobberize(),
294 [&] (AbstractHeap heap) {
295 if (heap.kind() != Stack) {
296 ASSERT(!heap.overlaps(Stack));
297 return;
298 }
299 ASSERT(!heap.payload().isTop());
300 VirtualRegister reg(heap.payload().value32());
301 if (argumentsInvolveStackSlot(candidate, reg))
302 doesInterfere = true;
303 },
304 NoOpClobberize());
305 if (doesInterfere) {
306 if (DFGVarargsForwardingPhaseInternal::verbose)
307 dataLog(" Interference at ", node, "\n");
308 return;
309 }
310 } }
311 }
312
313 // We can make this work.
314 if (DFGVarargsForwardingPhaseInternal::verbose)
315 dataLog(" Will do forwarding!\n");
316 m_changed = true;
317
318 // Transform the program.
319 switch (candidate->op()) {
320 case CreateDirectArguments:
321 candidate->setOpAndDefaultFlags(PhantomDirectArguments);
322 break;
323
324 case CreateClonedArguments:
325 candidate->setOpAndDefaultFlags(PhantomClonedArguments);
326 break;
327
328 default:
329 DFG_CRASH(m_graph, candidate, "bad node type");
330 break;
331 }
332
333 InsertionSet insertionSet(m_graph);
334 for (unsigned nodeIndex = candidateNodeIndex + 1; nodeIndex <= lastUserIndex; ++nodeIndex) {
335 Node* node = block->at(nodeIndex);
336 switch (node->op()) {
337 case Check:
338 case CheckVarargs:
339 case MovHint:
340 case PutHint:
341 // We don't need to change anything with these.
342 break;
343
344 case LoadVarargs:
345 if (node->child1() != candidate)
346 break;
347 node->setOpAndDefaultFlags(ForwardVarargs);
348 break;
349
350 case CallVarargs:
351 if (node->child3() != candidate)
352 break;
353 node->setOpAndDefaultFlags(CallForwardVarargs);
354 break;
355
356 case ConstructVarargs:
357 if (node->child3() != candidate)
358 break;
359 node->setOpAndDefaultFlags(ConstructForwardVarargs);
360 break;
361
362 case TailCallVarargs:
363 if (node->child3() != candidate)
364 break;
365 node->setOpAndDefaultFlags(TailCallForwardVarargs);
366 break;
367
368 case TailCallVarargsInlinedCaller:
369 if (node->child3() != candidate)
370 break;
371 node->setOpAndDefaultFlags(TailCallForwardVarargsInlinedCaller);
372 break;
373
374 case SetLocal:
375 // This is super odd. We don't have to do anything here, since in DFG IR, the phantom
376 // arguments nodes do produce a JSValue. Also, we know that if this SetLocal referenecs a
377 // candidate then the SetLocal - along with all of its references - will die off pretty
378 // soon, since it has no real users. DCE will surely kill it. If we make it to SSA, then
379 // SSA conversion will kill it.
380 break;
381
382 case GetButterfly: {
383 if (node->child1().node() == candidate) {
384 ASSERT(candidateButterflies.contains(node));
385 node->child1() = Edge();
386 node->remove(m_graph);
387 }
388 break;
389 }
390
391 case FilterGetByIdStatus:
392 case FilterPutByIdStatus:
393 case FilterCallLinkStatus:
394 case FilterInByIdStatus:
395 if (node->child1().node() == candidate)
396 node->remove(m_graph);
397 break;
398
399 case GetByOffset: {
400 if (node->child2() == candidate) {
401 ASSERT(candidateButterflies.contains(node->child1().node())); // It's no longer a GetButterfly node, but it should've been a candidate butterfly.
402 ASSERT(node->storageAccessData().offset == clonedArgumentsLengthPropertyOffset);
403 node->convertToIdentityOn(
404 emitCodeToGetArgumentsArrayLength(insertionSet, candidate, nodeIndex, node->origin));
405 }
406 break;
407 }
408
409 case GetArrayLength:
410 if (node->arrayMode().type() == Array::DirectArguments && node->child1() == candidate) {
411 node->convertToIdentityOn(
412 emitCodeToGetArgumentsArrayLength(insertionSet, candidate, nodeIndex, node->origin));
413 }
414 break;
415
416 default:
417 if (ASSERT_DISABLED)
418 break;
419 m_graph.doToChildren(
420 node,
421 [&] (Edge edge) {
422 DFG_ASSERT(m_graph, node, edge != candidate);
423 });
424 break;
425 }
426 }
427
428 insertionSet.execute(block);
429 }
430
431 bool m_changed;
432};
433
434} // anonymous namespace
435
436bool performVarargsForwarding(Graph& graph)
437{
438 return runPhase<VarargsForwardingPhase>(graph);
439}
440
441} } // namespace JSC::DFG
442
443#endif // ENABLE(DFG_JIT)
444
445