1/*
2 * Copyright (C) 2013-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 "DFGCPSRethreadingPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBasicBlockInlines.h"
32#include "DFGGraph.h"
33#include "DFGPhase.h"
34#include "JSCInlines.h"
35
36namespace JSC { namespace DFG {
37
38class CPSRethreadingPhase : public Phase {
39public:
40 CPSRethreadingPhase(Graph& graph)
41 : Phase(graph, "CPS rethreading")
42 {
43 }
44
45 bool run()
46 {
47 RELEASE_ASSERT(m_graph.m_refCountState == EverythingIsLive);
48
49 if (m_graph.m_form == ThreadedCPS)
50 return false;
51
52 clearIsLoadedFrom();
53 freeUnnecessaryNodes();
54 m_graph.clearReplacements();
55 canonicalizeLocalsInBlocks();
56 specialCaseArguments();
57 propagatePhis<LocalOperand>();
58 propagatePhis<ArgumentOperand>();
59 computeIsFlushed();
60
61 m_graph.m_form = ThreadedCPS;
62 return true;
63 }
64
65private:
66
67 void clearIsLoadedFrom()
68 {
69 for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
70 m_graph.m_variableAccessData[i].setIsLoadedFrom(false);
71 }
72
73 void freeUnnecessaryNodes()
74 {
75 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
76 BasicBlock* block = m_graph.block(blockIndex);
77 if (!block)
78 continue;
79 ASSERT(block->isReachable);
80
81 unsigned fromIndex = 0;
82 unsigned toIndex = 0;
83 while (fromIndex < block->size()) {
84 Node* node = block->at(fromIndex++);
85 switch (node->op()) {
86 case GetLocal:
87 case Flush:
88 case PhantomLocal:
89 node->children.setChild1(Edge());
90 break;
91 case Phantom:
92 if (!node->child1()) {
93 m_graph.deleteNode(node);
94 continue;
95 }
96 switch (node->child1()->op()) {
97 case SetArgumentMaybe:
98 DFG_CRASH(m_graph, node, "Invalid Phantom(@SetArgumentMaybe)");
99 break;
100 case Phi:
101 case SetArgumentDefinitely:
102 case SetLocal:
103 node->convertPhantomToPhantomLocal();
104 break;
105 default:
106 ASSERT(node->child1()->hasResult());
107 break;
108 }
109 break;
110 default:
111 break;
112 }
113 block->at(toIndex++) = node;
114 }
115 block->resize(toIndex);
116
117 for (unsigned phiIndex = block->phis.size(); phiIndex--;)
118 m_graph.deleteNode(block->phis[phiIndex]);
119 block->phis.resize(0);
120 }
121 }
122
123 template<OperandKind operandKind>
124 void clearVariables()
125 {
126 ASSERT(
127 m_block->variablesAtHead.sizeFor<operandKind>()
128 == m_block->variablesAtTail.sizeFor<operandKind>());
129
130 for (unsigned i = m_block->variablesAtHead.sizeFor<operandKind>(); i--;) {
131 m_block->variablesAtHead.atFor<operandKind>(i) = nullptr;
132 m_block->variablesAtTail.atFor<operandKind>(i) = nullptr;
133 }
134 }
135
136 ALWAYS_INLINE Node* addPhiSilently(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable)
137 {
138 Node* result = m_graph.addNode(Phi, origin, OpInfo(variable));
139 block->phis.append(result);
140 return result;
141 }
142
143 template<OperandKind operandKind>
144 ALWAYS_INLINE Node* addPhi(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable, size_t index)
145 {
146 Node* result = addPhiSilently(block, origin, variable);
147 phiStackFor<operandKind>().append(PhiStackEntry(block, index, result));
148 return result;
149 }
150
151 template<OperandKind operandKind>
152 ALWAYS_INLINE Node* addPhi(const NodeOrigin& origin, VariableAccessData* variable, size_t index)
153 {
154 return addPhi<operandKind>(m_block, origin, variable, index);
155 }
156
157 template<OperandKind operandKind>
158 void canonicalizeGetLocalFor(Node* node, VariableAccessData* variable, size_t idx)
159 {
160 ASSERT(!node->child1());
161
162 if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
163 ASSERT(otherNode->variableAccessData() == variable);
164
165 switch (otherNode->op()) {
166 case Flush:
167 case PhantomLocal:
168 otherNode = otherNode->child1().node();
169 if (otherNode->op() == Phi) {
170 // We need to have a GetLocal, so this might as well be the one.
171 node->children.setChild1(Edge(otherNode));
172 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
173 return;
174 }
175 ASSERT(otherNode->op() != SetArgumentMaybe);
176 ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely);
177 break;
178 default:
179 break;
180 }
181
182 ASSERT(otherNode->op() != SetArgumentMaybe);
183 ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely || otherNode->op() == GetLocal);
184 ASSERT(otherNode->variableAccessData() == variable);
185
186 if (otherNode->op() == SetArgumentDefinitely) {
187 variable->setIsLoadedFrom(true);
188 node->children.setChild1(Edge(otherNode));
189 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
190 return;
191 }
192
193 if (otherNode->op() == GetLocal) {
194 // Replace all references to this GetLocal with otherNode.
195 node->replaceWith(m_graph, otherNode);
196 return;
197 }
198
199 ASSERT(otherNode->op() == SetLocal);
200 node->replaceWith(m_graph, otherNode->child1().node());
201 return;
202 }
203
204 variable->setIsLoadedFrom(true);
205 Node* phi = addPhi<operandKind>(node->origin, variable, idx);
206 node->children.setChild1(Edge(phi));
207 m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
208 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
209 }
210
211 void canonicalizeGetLocal(Node* node)
212 {
213 VariableAccessData* variable = node->variableAccessData();
214 if (variable->local().isArgument())
215 canonicalizeGetLocalFor<ArgumentOperand>(node, variable, variable->local().toArgument());
216 else
217 canonicalizeGetLocalFor<LocalOperand>(node, variable, variable->local().toLocal());
218 }
219
220 template<NodeType nodeType, OperandKind operandKind>
221 void canonicalizeFlushOrPhantomLocalFor(Node* node, VariableAccessData* variable, size_t idx)
222 {
223 ASSERT(!node->child1());
224
225 if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
226 ASSERT(otherNode->variableAccessData() == variable);
227
228 switch (otherNode->op()) {
229 case Flush:
230 case PhantomLocal:
231 case GetLocal:
232 otherNode = otherNode->child1().node();
233 break;
234 default:
235 break;
236 }
237
238 ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely || otherNode->op() == SetArgumentMaybe);
239
240 if (nodeType == PhantomLocal && otherNode->op() == SetLocal) {
241 // PhantomLocal(SetLocal) doesn't make sense. PhantomLocal means: at this
242 // point I know I would have been interested in the value of this variable
243 // for the purpose of OSR. PhantomLocal(SetLocal) means: at this point I
244 // know that I would have read the value written by that SetLocal. This is
245 // redundant and inefficient, since really it just means that we want to
246 // keep the last MovHinted value of that local alive.
247
248 node->remove(m_graph);
249 return;
250 }
251
252 variable->setIsLoadedFrom(true);
253 // There is nothing wrong with having redundant Flush's. It just needs to
254 // be linked appropriately. Note that if there had already been a previous
255 // use at tail then we don't override it. It's fine for variablesAtTail to
256 // omit Flushes and PhantomLocals. On the other hand, having it refer to a
257 // Flush or a PhantomLocal if just before it the last use was a GetLocal would
258 // seriously confuse the CFA.
259 node->children.setChild1(Edge(otherNode));
260 return;
261 }
262
263 variable->setIsLoadedFrom(true);
264 node->children.setChild1(Edge(addPhi<operandKind>(node->origin, variable, idx)));
265 m_block->variablesAtHead.atFor<operandKind>(idx) = node;
266 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
267 }
268
269 template<NodeType nodeType>
270 void canonicalizeFlushOrPhantomLocal(Node* node)
271 {
272 VariableAccessData* variable = node->variableAccessData();
273 if (variable->local().isArgument())
274 canonicalizeFlushOrPhantomLocalFor<nodeType, ArgumentOperand>(node, variable, variable->local().toArgument());
275 else
276 canonicalizeFlushOrPhantomLocalFor<nodeType, LocalOperand>(node, variable, variable->local().toLocal());
277 }
278
279 void canonicalizeSet(Node* node)
280 {
281 m_block->variablesAtTail.setOperand(node->local(), node);
282 }
283
284 void canonicalizeLocalsInBlock()
285 {
286 if (!m_block)
287 return;
288 ASSERT(m_block->isReachable);
289
290 clearVariables<ArgumentOperand>();
291 clearVariables<LocalOperand>();
292
293 // Assumes that all phi references have been removed. Assumes that things that
294 // should be live have a non-zero ref count, but doesn't assume that the ref
295 // counts are correct beyond that (more formally !!logicalRefCount == !!actualRefCount
296 // but not logicalRefCount == actualRefCount). Assumes that it can break ref
297 // counts.
298
299 for (auto* node : *m_block) {
300 m_graph.performSubstitution(node);
301
302 // The rules for threaded CPS form:
303 //
304 // Head variable: describes what is live at the head of the basic block.
305 // Head variable links may refer to Flush, PhantomLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe.
306 // SetArgumentDefinitely/SetArgumentMaybe may only appear in the root block.
307 //
308 // Tail variable: the last thing that happened to the variable in the block.
309 // It may be a Flush, PhantomLocal, GetLocal, SetLocal, SetArgumentDefinitely/SetArgumentMaybe, or Phi.
310 // SetArgumentDefinitely/SetArgumentMaybe may only appear in the root block. Note that if there ever
311 // was a GetLocal to the variable, and it was followed by PhantomLocals and
312 // Flushes but not SetLocals, then the tail variable will be the GetLocal.
313 // This reflects the fact that you only care that the tail variable is a
314 // Flush or PhantomLocal if nothing else interesting happened. Likewise, if
315 // there ever was a SetLocal and it was followed by Flushes, then the tail
316 // variable will be a SetLocal and not those subsequent Flushes.
317 //
318 // Child of GetLocal: the operation that the GetLocal keeps alive. It may be
319 // a Phi from the current block. For arguments, it may be a SetArgumentDefinitely
320 // but it can't be a SetArgumentMaybe.
321 //
322 // Child of SetLocal: must be a value producing node.
323 //
324 // Child of Flush: it may be a Phi from the current block or a SetLocal. For
325 // arguments it may also be a SetArgumentDefinitely/SetArgumentMaybe.
326 //
327 // Child of PhantomLocal: it may be a Phi from the current block. For
328 // arguments it may also be a SetArgumentDefinitely/SetArgumentMaybe.
329 //
330 // Children of Phi: other Phis in the same basic block, or any of the
331 // following from predecessor blocks: SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe.
332 // These are computed by looking at the tail variables of the predecessor blocks
333 // and either using it directly (if it's a SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe) or
334 // loading that nodes child (if it's a GetLocal, PhanomLocal, or Flush - all
335 // of these will have children that are SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe).
336
337 switch (node->op()) {
338 case GetLocal:
339 canonicalizeGetLocal(node);
340 break;
341
342 case SetLocal:
343 canonicalizeSet(node);
344 break;
345
346 case Flush:
347 canonicalizeFlushOrPhantomLocal<Flush>(node);
348 break;
349
350 case PhantomLocal:
351 canonicalizeFlushOrPhantomLocal<PhantomLocal>(node);
352 break;
353
354 case SetArgumentDefinitely:
355 case SetArgumentMaybe:
356 canonicalizeSet(node);
357 break;
358
359 default:
360 break;
361 }
362 }
363 }
364
365 void canonicalizeLocalsInBlocks()
366 {
367 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
368 m_block = m_graph.block(blockIndex);
369 canonicalizeLocalsInBlock();
370 }
371 }
372
373 void specialCaseArguments()
374 {
375 // Normally, a SetArgumentDefinitely denotes the start of a live range for a local's value on the stack.
376 // But those SetArguments used for the actual arguments to the machine CodeBlock get
377 // special-cased. We could have instead used two different node types - one for the arguments
378 // at the prologue case, and another for the other uses. But this seemed like IR overkill.
379
380 for (auto& pair : m_graph.m_rootToArguments) {
381 BasicBlock* entrypoint = pair.key;
382 const ArgumentsVector& arguments = pair.value;
383 for (unsigned i = arguments.size(); i--;)
384 entrypoint->variablesAtHead.setArgumentFirstTime(i, arguments[i]);
385 }
386 }
387
388 template<OperandKind operandKind>
389 void propagatePhis()
390 {
391 Vector<PhiStackEntry, 128>& phiStack = operandKind == ArgumentOperand ? m_argumentPhiStack : m_localPhiStack;
392
393 // Ensure that attempts to use this fail instantly.
394 m_block = 0;
395
396 while (!phiStack.isEmpty()) {
397 PhiStackEntry entry = phiStack.last();
398 phiStack.removeLast();
399
400 BasicBlock* block = entry.m_block;
401 PredecessorList& predecessors = block->predecessors;
402 Node* currentPhi = entry.m_phi;
403 VariableAccessData* variable = currentPhi->variableAccessData();
404 size_t index = entry.m_index;
405
406 for (size_t i = predecessors.size(); i--;) {
407 BasicBlock* predecessorBlock = predecessors[i];
408
409 Node* variableInPrevious = predecessorBlock->variablesAtTail.atFor<operandKind>(index);
410 if (!variableInPrevious) {
411 variableInPrevious = addPhi<operandKind>(predecessorBlock, currentPhi->origin, variable, index);
412 predecessorBlock->variablesAtTail.atFor<operandKind>(index) = variableInPrevious;
413 predecessorBlock->variablesAtHead.atFor<operandKind>(index) = variableInPrevious;
414 } else {
415 switch (variableInPrevious->op()) {
416 case GetLocal:
417 case PhantomLocal:
418 case Flush:
419 ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
420 variableInPrevious = variableInPrevious->child1().node();
421 break;
422 default:
423 break;
424 }
425 }
426
427 ASSERT(
428 variableInPrevious->op() == SetLocal
429 || variableInPrevious->op() == Phi
430 || variableInPrevious->op() == SetArgumentDefinitely
431 || variableInPrevious->op() == SetArgumentMaybe);
432
433 if (!currentPhi->child1()) {
434 currentPhi->children.setChild1(Edge(variableInPrevious));
435 continue;
436 }
437 if (!currentPhi->child2()) {
438 currentPhi->children.setChild2(Edge(variableInPrevious));
439 continue;
440 }
441 if (!currentPhi->child3()) {
442 currentPhi->children.setChild3(Edge(variableInPrevious));
443 continue;
444 }
445
446 Node* newPhi = addPhiSilently(block, currentPhi->origin, variable);
447 newPhi->children = currentPhi->children;
448 currentPhi->children.initialize(newPhi, variableInPrevious, 0);
449 }
450 }
451 }
452
453 struct PhiStackEntry {
454 PhiStackEntry(BasicBlock* block, size_t index, Node* phi)
455 : m_block(block)
456 , m_index(index)
457 , m_phi(phi)
458 {
459 }
460
461 BasicBlock* m_block;
462 size_t m_index;
463 Node* m_phi;
464 };
465
466 template<OperandKind operandKind>
467 Vector<PhiStackEntry, 128>& phiStackFor()
468 {
469 if (operandKind == ArgumentOperand)
470 return m_argumentPhiStack;
471 return m_localPhiStack;
472 }
473
474 void computeIsFlushed()
475 {
476 m_graph.clearFlagsOnAllNodes(NodeIsFlushed);
477
478 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
479 BasicBlock* block = m_graph.block(blockIndex);
480 if (!block)
481 continue;
482 for (unsigned nodeIndex = block->size(); nodeIndex--;) {
483 Node* node = block->at(nodeIndex);
484 if (node->op() != Flush)
485 continue;
486 addFlushedLocalOp(node);
487 }
488 }
489 while (!m_flushedLocalOpWorklist.isEmpty()) {
490 Node* node = m_flushedLocalOpWorklist.takeLast();
491 switch (node->op()) {
492 case SetLocal:
493 case SetArgumentDefinitely:
494 case SetArgumentMaybe:
495 break;
496
497 case Flush:
498 case Phi:
499 ASSERT(node->flags() & NodeIsFlushed);
500 DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge);
501 break;
502
503 default:
504 DFG_CRASH(m_graph, node, "Invalid node in flush graph");
505 break;
506 }
507 }
508 }
509
510 void addFlushedLocalOp(Node* node)
511 {
512 if (node->mergeFlags(NodeIsFlushed))
513 m_flushedLocalOpWorklist.append(node);
514 }
515
516 void addFlushedLocalEdge(Node*, Edge edge)
517 {
518 addFlushedLocalOp(edge.node());
519 }
520
521 BasicBlock* m_block;
522 Vector<PhiStackEntry, 128> m_argumentPhiStack;
523 Vector<PhiStackEntry, 128> m_localPhiStack;
524 Vector<Node*, 128> m_flushedLocalOpWorklist;
525};
526
527bool performCPSRethreading(Graph& graph)
528{
529 return runPhase<CPSRethreadingPhase>(graph);
530}
531
532} } // namespace JSC::DFG
533
534#endif // ENABLE(DFG_JIT)
535
536