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