Inserting a node into the DFG graph should not require five lines of code
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGCFGSimplificationPhase.cpp
1 /*
2  * Copyright (C) 2012 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 "DFGCFGSimplificationPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractState.h"
32 #include "DFGBasicBlockInlines.h"
33 #include "DFGGraph.h"
34 #include "DFGInsertionSet.h"
35 #include "DFGPhase.h"
36 #include "DFGValidate.h"
37 #include "Operations.h"
38
39 namespace JSC { namespace DFG {
40
41 class CFGSimplificationPhase : public Phase {
42 public:
43     CFGSimplificationPhase(Graph& graph)
44         : Phase(graph, "CFG simplification")
45     {
46     }
47     
48     bool run()
49     {
50         const bool extremeLogging = false;
51
52         bool outerChanged = false;
53         bool innerChanged;
54         
55         do {
56             innerChanged = false;
57             for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
58                 BasicBlock* block = m_graph.m_blocks[blockIndex].get();
59                 if (!block)
60                     continue;
61                 ASSERT(block->isReachable);
62             
63                 switch (m_graph[block->last()].op()) {
64                 case Jump: {
65                     // Successor with one predecessor -> merge.
66                     if (m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors.size() == 1) {
67                         ASSERT(m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors[0]
68                                == blockIndex);
69 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
70                         dataLogF("CFGSimplify: Jump merge on Block #%u to Block #%u.\n",
71                                 blockIndex, m_graph.successor(block, 0));
72 #endif
73                         if (extremeLogging)
74                             m_graph.dump();
75                         mergeBlocks(blockIndex, m_graph.successor(block, 0), NoBlock);
76                         innerChanged = outerChanged = true;
77                         break;
78                     } else {
79 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
80                         dataLogF("Not jump merging on Block #%u to Block #%u because predecessors = ",
81                                 blockIndex, m_graph.successor(block, 0));
82                         for (unsigned i = 0; i < m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors.size(); ++i) {
83                             if (i)
84                                 dataLogF(", ");
85                             dataLogF("#%u", m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors[i]);
86                         }
87                         dataLogF(".\n");
88 #endif
89                     }
90                 
91                     // FIXME: Block only has a jump -> remove. This is tricky though because of
92                     // liveness. What we really want is to slam in a phantom at the end of the
93                     // block, after the terminal. But we can't right now. :-(
94                     // Idea: what if I slam the ghosties into my successor? Nope, that's
95                     // suboptimal, because if my successor has multiple predecessors then we'll
96                     // be keeping alive things on other predecessor edges unnecessarily.
97                     // What we really need is the notion of end-of-block ghosties!
98                     break;
99                 }
100                 
101                 case Branch: {
102                     // Branch on constant -> jettison the not-taken block and merge.
103                     if (isKnownDirection(block->cfaBranchDirection)) {
104                         bool condition = branchCondition(block->cfaBranchDirection);
105                         BasicBlock* targetBlock = m_graph.m_blocks[
106                             m_graph.successorForCondition(block, condition)].get();
107                         if (targetBlock->m_predecessors.size() == 1) {
108 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
109                             dataLogF("CFGSimplify: Known condition (%s) branch merge on Block #%u to Block #%u, jettisoning Block #%u.\n",
110                                     condition ? "true" : "false",
111                                     blockIndex, m_graph.successorForCondition(block, condition),
112                                     m_graph.successorForCondition(block, !condition));
113 #endif
114                             if (extremeLogging)
115                                 m_graph.dump();
116                             mergeBlocks(
117                                 blockIndex,
118                                 m_graph.successorForCondition(block, condition),
119                                 m_graph.successorForCondition(block, !condition));
120                         } else {
121 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
122                             dataLogF("CFGSimplify: Known condition (%s) branch->jump conversion on Block #%u to Block #%u, jettisoning Block #%u.\n",
123                                     condition ? "true" : "false",
124                                     blockIndex, m_graph.successorForCondition(block, condition),
125                                     m_graph.successorForCondition(block, !condition));
126 #endif
127                             if (extremeLogging)
128                                 m_graph.dump();
129                             BlockIndex takenBlockIndex = m_graph.successorForCondition(block, condition);
130                             BlockIndex notTakenBlockIndex = m_graph.successorForCondition(block, !condition);
131                         
132                             ASSERT(m_graph[block->last()].isTerminal());
133                             CodeOrigin boundaryCodeOrigin = m_graph[block->last()].codeOrigin;
134                             m_graph[block->last()].setOpAndDefaultFlags(Phantom);
135                             ASSERT(m_graph[block->last()].refCount() == 1);
136                         
137                             jettisonBlock(blockIndex, notTakenBlockIndex, boundaryCodeOrigin);
138                         
139                             block->appendNode(
140                                 m_graph, DontRefChildren, DontRefNode, SpecNone, Jump,
141                                 boundaryCodeOrigin, OpInfo(takenBlockIndex));
142                         }
143                         innerChanged = outerChanged = true;
144                         break;
145                     }
146                     
147                     if (m_graph.successor(block, 0) == m_graph.successor(block, 1)) {
148                         BlockIndex targetBlockIndex = m_graph.successor(block, 0);
149                         BasicBlock* targetBlock = m_graph.m_blocks[targetBlockIndex].get();
150                         ASSERT(targetBlock);
151                         ASSERT(targetBlock->isReachable);
152                         if (targetBlock->m_predecessors.size() == 1) {
153 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
154                             dataLogF("CFGSimplify: Branch to same successor merge on Block #%u to Block #%u.\n",
155                                     blockIndex, targetBlockIndex);
156 #endif
157                             mergeBlocks(blockIndex, targetBlockIndex, NoBlock);
158                         } else {
159 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
160                             dataLogF("CFGSimplify: Branch->jump conversion to same successor on Block #%u to Block #%u.\n",
161                                     blockIndex, targetBlockIndex);
162 #endif
163                             ASSERT(m_graph[block->last()].isTerminal());
164                             Node& branch = m_graph[block->last()];
165                             ASSERT(branch.isTerminal());
166                             ASSERT(branch.op() == Branch);
167                             branch.setOpAndDefaultFlags(Phantom);
168                             ASSERT(branch.refCount() == 1);
169                             
170                             block->appendNode(
171                                 m_graph, DontRefChildren, DontRefNode, SpecNone, Jump,
172                                 branch.codeOrigin, OpInfo(targetBlockIndex));
173                         }
174                         innerChanged = outerChanged = true;
175                         break;
176                     }
177                     
178 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
179                     dataLogF("Not branch simplifying on Block #%u because the successors differ and the condition is not known.\n",
180                             blockIndex);
181 #endif
182                 
183                     // Branch to same destination -> jump.
184                     // FIXME: this will currently not be hit because of the lack of jump-only
185                     // block simplification.
186                     
187                     break;
188                 }
189                 
190                 default:
191                     break;
192                 }
193             }
194             
195             if (innerChanged) {
196                 // Here's the reason for this pass:
197                 // Blocks: A, B, C, D, E, F
198                 // A -> B, C
199                 // B -> F
200                 // C -> D, E
201                 // D -> F
202                 // E -> F
203                 //
204                 // Assume that A's branch is determined to go to B. Then the rest of this phase
205                 // is smart enough to simplify down to:
206                 // A -> B
207                 // B -> F
208                 // C -> D, E
209                 // D -> F
210                 // E -> F
211                 //
212                 // We will also merge A and B. But then we don't have any other mechanism to
213                 // remove D, E as predecessors for F. Worse, the rest of this phase does not
214                 // know how to fix the Phi functions of F to ensure that they no longer refer
215                 // to variables in D, E. In general, we need a way to handle Phi simplification
216                 // upon:
217                 // 1) Removal of a predecessor due to branch simplification. The branch
218                 //    simplifier already does that.
219                 // 2) Invalidation of a predecessor because said predecessor was rendered
220                 //    unreachable. We do this here.
221                 //
222                 // This implies that when a block is unreachable, we must inspect its
223                 // successors' Phi functions to remove any references from them into the
224                 // removed block.
225                 
226                 m_graph.resetReachability();
227
228                 for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
229                     BasicBlock* block = m_graph.m_blocks[blockIndex].get();
230                     if (!block)
231                         continue;
232                     if (block->isReachable)
233                         continue;
234                     
235                     killUnreachable(blockIndex);
236                 }
237             }
238             
239             validate(m_graph);
240         } while (innerChanged);
241         
242         return outerChanged;
243     }
244
245 private:
246     void killUnreachable(BlockIndex blockIndex)
247     {
248         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
249         
250         ASSERT(block);
251         ASSERT(!block->isReachable);
252         
253         // 1) Remove references from other blocks to this block.
254         for (unsigned i = m_graph.numSuccessors(block); i--;)
255             fixPhis(blockIndex, m_graph.successor(block, i));
256         
257         // 2) Kill the block
258         m_graph.m_blocks[blockIndex].clear();
259     }
260     
261     void keepOperandAlive(BasicBlock* block, CodeOrigin codeOrigin, int operand)
262     {
263         NodeIndex nodeIndex = block->variablesAtTail.operand(operand);
264         if (nodeIndex == NoNode)
265             return;
266         if (m_graph[nodeIndex].variableAccessData()->isCaptured())
267             return;
268         if (m_graph[nodeIndex].op() == SetLocal)
269             nodeIndex = m_graph[nodeIndex].child1().index();
270         Node& node = m_graph[nodeIndex];
271         if (!node.shouldGenerate())
272             return;
273         ASSERT(m_graph[nodeIndex].op() != SetLocal);
274         block->appendNode(
275             m_graph, RefChildren, DontRefNode, SpecNone, Phantom, codeOrigin, nodeIndex);
276     }
277     
278     void fixPossibleGetLocal(BasicBlock* block, Edge& edge, bool changeRef)
279     {
280         Node& child = m_graph[edge];
281         if (child.op() != GetLocal)
282             return;
283 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
284         dataLogF("    Considering GetLocal at @%u, local r%d.\n", edge.index(), child.local());
285 #endif
286         if (child.variableAccessData()->isCaptured()) {
287 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
288             dataLogF("        It's captured.\n");
289 #endif
290             return;
291         }
292         NodeIndex originalNodeIndex = block->variablesAtTail.operand(child.local());
293 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
294         dataLogF("        Dealing with original @%u.\n", originalNodeIndex);
295 #endif
296         ASSERT(originalNodeIndex != NoNode);
297         Node* originalNode = &m_graph[originalNodeIndex];
298 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
299         dataLogF("        Original has local r%d.\n", originalNode->local());
300 #endif
301         ASSERT(child.local() == originalNode->local());
302         // Possibilities:
303         // SetLocal -> the secondBlock is getting the value of something that is immediately
304         //     available in the first block with a known NodeIndex.
305         // GetLocal -> the secondBlock is getting the value of something that the first
306         //     block also gets.
307         // Phi -> the secondBlock is asking for keep-alive on an operand that the first block
308         //     was also asking for keep-alive on.
309         // SetArgument -> the secondBlock is asking for keep-alive on an operand that the
310         //     first block was keeping alive by virtue of the firstBlock being the root and
311         //     the operand being an argument.
312         // Flush -> the secondBlock is asking for keep-alive on an operand that the first
313         //     block was forcing to be alive, so the second block should refer child of
314         //     the flush.
315         if (originalNode->op() == Flush) {
316             originalNodeIndex = originalNode->child1().index();
317             originalNode = &m_graph[originalNodeIndex];
318         }
319         switch (originalNode->op()) {
320         case SetLocal: {
321             if (changeRef)
322                 ASSERT(originalNode->shouldGenerate());
323 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
324             dataLogF("        It's a SetLocal.\n");
325 #endif
326             m_graph.changeIndex(edge, originalNode->child1().index(), changeRef);
327             break;
328         }
329         case GetLocal: {
330 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
331             dataLogF("        It's a GetLocal.\n");
332 #endif
333             if (originalNode->shouldGenerate())
334                 m_graph.changeIndex(edge, originalNodeIndex, changeRef);
335             // If we have a GetLocal that points to a child GetLocal that is dead, then
336             // we have no need to do anything: this original GetLocal is still valid.
337             break;
338         }
339         case Phi:
340         case SetArgument: {
341         if (changeRef)
342             ASSERT(originalNode->shouldGenerate());
343 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
344             dataLogF("        It's Phi/SetArgument.\n");
345 #endif
346             // Keep the GetLocal!
347             break;
348         }
349         default:
350             ASSERT_NOT_REACHED();
351             break;
352         }
353     }
354     
355     void jettisonBlock(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex, CodeOrigin boundaryCodeOrigin)
356     {
357         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
358         BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
359         
360         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
361             keepOperandAlive(block, boundaryCodeOrigin, argumentToOperand(i));
362         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
363             keepOperandAlive(block, boundaryCodeOrigin, i);
364         
365         fixJettisonedPredecessors(blockIndex, jettisonedBlockIndex);
366     }
367     
368     void fixPhis(BlockIndex sourceBlockIndex, BlockIndex destinationBlockIndex)
369     {
370         BasicBlock* sourceBlock = m_graph.m_blocks[sourceBlockIndex].get();
371         BasicBlock* destinationBlock = m_graph.m_blocks[destinationBlockIndex].get();
372         if (!destinationBlock) {
373             // If we're trying to kill off the source block and the destination block is already
374             // dead, then we're done!
375             return;
376         }
377         for (size_t i = 0; i < destinationBlock->phis.size(); ++i) {
378             NodeIndex phiNodeIndex = destinationBlock->phis[i];
379             Node& phiNode = m_graph[phiNodeIndex];
380             NodeIndex myNodeIndex = sourceBlock->variablesAtTail.operand(phiNode.local());
381 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
382             dataLogF("Considering removing reference from phi @%u to @%u on local r%d:",
383                     phiNodeIndex, myNodeIndex, phiNode.local());
384 #endif
385             if (myNodeIndex == NoNode) {
386                 // This will happen if there is a phi in the destination that refers into
387                 // the destination itself.
388                 continue;
389             }
390             Node& myNode = m_graph[myNodeIndex];
391             if (myNode.op() == GetLocal)
392                 myNodeIndex = myNode.child1().index();
393             for (unsigned j = 0; j < AdjacencyList::Size; ++j)
394                 removePotentiallyDeadPhiReference(myNodeIndex, phiNode, j, sourceBlock->isReachable);
395 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
396             dataLogF("\n");
397 #endif
398         }
399     }
400     
401     void fixJettisonedPredecessors(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex)
402     {
403 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
404         dataLogF("Fixing predecessors and phis due to jettison of Block #%u from Block #%u.\n",
405                 jettisonedBlockIndex, blockIndex);
406 #endif
407         BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
408         for (unsigned i = 0; i < jettisonedBlock->m_predecessors.size(); ++i) {
409             if (jettisonedBlock->m_predecessors[i] != blockIndex)
410                 continue;
411             jettisonedBlock->m_predecessors[i] = jettisonedBlock->m_predecessors.last();
412             jettisonedBlock->m_predecessors.removeLast();
413             break;
414         }
415         
416         fixPhis(blockIndex, jettisonedBlockIndex);
417     }
418     
419     void removePotentiallyDeadPhiReference(NodeIndex myNodeIndex, Node& phiNode, unsigned edgeIndex, bool changeRef)
420     {
421         if (phiNode.children.child(edgeIndex).indexUnchecked() != myNodeIndex)
422             return;
423 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
424         dataLogF(" Removing reference at child %u.", edgeIndex);
425 #endif
426         if (changeRef && phiNode.shouldGenerate())
427             m_graph.deref(myNodeIndex);
428         phiNode.children.removeEdgeFromBag(edgeIndex);
429     }
430     
431     struct OperandSubstitution {
432         OperandSubstitution()
433             : oldChild(NoNode)
434             , newChild(NoNode)
435         {
436         }
437         
438         explicit OperandSubstitution(NodeIndex oldChild)
439             : oldChild(oldChild)
440             , newChild(oldChild)
441         {
442         }
443         
444         OperandSubstitution(NodeIndex oldChild, NodeIndex newChild)
445             : oldChild(oldChild)
446             , newChild(newChild)
447         {
448             ASSERT((oldChild == NoNode) == (newChild == NoNode));
449         }
450         
451         void dump(FILE* out)
452         {
453             if (oldChild == NoNode)
454                 fprintf(out, "-");
455             else
456                 fprintf(out, "@%u -> @%u", oldChild, newChild);
457         }
458         
459         NodeIndex oldChild;
460         NodeIndex newChild;
461     };
462     
463     NodeIndex skipGetLocal(NodeIndex nodeIndex)
464     {
465         if (nodeIndex == NoNode)
466             return NoNode;
467         Node& node = m_graph[nodeIndex];
468         if (node.op() == GetLocal)
469             return node.child1().index();
470         return nodeIndex;
471     }
472     
473     void recordPossibleIncomingReference(
474         BasicBlock* secondBlock, Operands<OperandSubstitution>& substitutions, int operand)
475     {
476         substitutions.operand(operand) = OperandSubstitution(
477             skipGetLocal(secondBlock->variablesAtTail.operand(operand)));
478     }
479     
480     void recordNewTarget(Operands<OperandSubstitution>& substitutions, int operand, NodeIndex nodeIndex)
481     {
482         ASSERT(m_graph[nodeIndex].op() == SetLocal
483                || m_graph[nodeIndex].op() == SetArgument
484                || m_graph[nodeIndex].op() == Flush
485                || m_graph[nodeIndex].op() == Phi);
486         substitutions.operand(operand).newChild = nodeIndex;
487     }
488     
489     void fixTailOperand(
490         BasicBlock* firstBlock, BasicBlock* secondBlock, int operand,
491         Operands<OperandSubstitution>& substitutions)
492     {
493         NodeIndex atSecondTail = secondBlock->variablesAtTail.operand(operand);
494         
495         if (atSecondTail == NoNode) {
496             // If the variable is dead at the end of the second block, then do nothing; essentially
497             // this means that we want the tail state to reflect whatever the first block did.
498             return;
499         }
500
501         Node& secondNode = m_graph[atSecondTail];
502         
503         switch (secondNode.op()) {
504         case SetLocal:
505         case Flush: {
506             // The second block did interesting things to the variables, so update the tail
507             // accordingly.
508             firstBlock->variablesAtTail.operand(operand) = atSecondTail;
509             break;
510         }
511             
512         case Phi: {
513             // Keep what was in the first block.
514             ASSERT(firstBlock->variablesAtTail.operand(operand) != NoNode);
515             recordNewTarget(substitutions, operand, skipGetLocal(firstBlock->variablesAtTail.operand(operand)));
516             break;
517         }
518
519         case GetLocal: {
520             // If it's a GetLocal on a captured var, then definitely keep what was
521             // in the second block. In particular, it's possible that the first
522             // block doesn't even know about this variable.
523             if (secondNode.variableAccessData()->isCaptured()) {
524                 firstBlock->variablesAtTail.operand(operand) = atSecondTail;
525                 recordNewTarget(substitutions, operand, secondNode.child1().index());
526                 break;
527             }
528             
529             // It's possible that the second block had a GetLocal and the first block
530             // had a SetArgument or a Phi. Then update the tail. Otherwise keep what was in the
531             // first block.
532             NodeIndex atFirstTail = firstBlock->variablesAtTail.operand(operand);
533             ASSERT(atFirstTail != NoNode);
534             switch (m_graph[atFirstTail].op()) {
535             case SetArgument:
536             case Phi:
537                 firstBlock->variablesAtTail.operand(operand) = atSecondTail;
538                 recordNewTarget(substitutions, operand, secondNode.child1().index());
539                 break;
540
541             default:
542                 // Keep what was in the first block, and adjust the substitution to account for
543                 // the fact that successors will refer to the child of the GetLocal.
544                 ASSERT(firstBlock->variablesAtTail.operand(operand) != NoNode);
545                 recordNewTarget(substitutions, operand, skipGetLocal(firstBlock->variablesAtTail.operand(operand)));
546                 break;
547             }
548             break;
549         }
550             
551         default:
552             ASSERT_NOT_REACHED();
553         }
554     }
555     
556     void mergeBlocks(
557         BlockIndex firstBlockIndex, BlockIndex secondBlockIndex, BlockIndex jettisonedBlockIndex)
558     {
559         // This will add all of the nodes in secondBlock to firstBlock, but in so doing
560         // it will also ensure that any GetLocals from the second block that refer to
561         // SetLocals in the first block are relinked. If jettisonedBlock is not NoBlock,
562         // then Phantoms are inserted for anything that the jettisonedBlock would have
563         // kept alive.
564         
565         BasicBlock* firstBlock = m_graph.m_blocks[firstBlockIndex].get();
566         BasicBlock* secondBlock = m_graph.m_blocks[secondBlockIndex].get();
567         
568         // Remove the terminal of firstBlock since we don't need it anymore. Well, we don't
569         // really remove it; we actually turn it into a Phantom.
570         ASSERT(m_graph[firstBlock->last()].isTerminal());
571         CodeOrigin boundaryCodeOrigin = m_graph[firstBlock->last()].codeOrigin;
572         m_graph[firstBlock->last()].setOpAndDefaultFlags(Phantom);
573         ASSERT(m_graph[firstBlock->last()].refCount() == 1);
574         
575         if (jettisonedBlockIndex != NoBlock) {
576             BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
577             
578             // Time to insert ghosties for things that need to be kept alive in case we OSR
579             // exit prior to hitting the firstBlock's terminal, and end up going down a
580             // different path than secondBlock.
581             
582             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
583                 keepOperandAlive(firstBlock, boundaryCodeOrigin, argumentToOperand(i));
584             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
585                 keepOperandAlive(firstBlock, boundaryCodeOrigin, i);
586         }
587         
588         for (size_t i = 0; i < secondBlock->phis.size(); ++i)
589             firstBlock->phis.append(secondBlock->phis[i]);
590
591         // Before we start changing the second block's graph, record what nodes would
592         // be referenced by successors of the second block.
593         Operands<OperandSubstitution> substitutions(
594             secondBlock->variablesAtTail.numberOfArguments(),
595             secondBlock->variablesAtTail.numberOfLocals());
596         for (size_t i = 0; i < secondBlock->variablesAtTail.numberOfArguments(); ++i)
597             recordPossibleIncomingReference(secondBlock, substitutions, argumentToOperand(i));
598         for (size_t i = 0; i < secondBlock->variablesAtTail.numberOfLocals(); ++i)
599             recordPossibleIncomingReference(secondBlock, substitutions, i);
600
601         for (size_t i = 0; i < secondBlock->size(); ++i) {
602             NodeIndex nodeIndex = secondBlock->at(i);
603             Node& node = m_graph[nodeIndex];
604             
605             bool childrenAlreadyFixed = false;
606             
607             switch (node.op()) {
608             case Phantom: {
609                 if (!node.child1())
610                     break;
611                 
612                 ASSERT(node.shouldGenerate());
613                 Node& possibleLocalOp = m_graph[node.child1()];
614                 if (possibleLocalOp.op() != GetLocal
615                     && possibleLocalOp.hasLocal()
616                     && !possibleLocalOp.variableAccessData()->isCaptured()) {
617                     NodeIndex setLocalIndex =
618                         firstBlock->variablesAtTail.operand(possibleLocalOp.local());
619                     Node& setLocal = m_graph[setLocalIndex];
620                     if (setLocal.op() == SetLocal) {
621                         m_graph.changeEdge(node.children.child1(), setLocal.child1());
622                         ASSERT(!node.child2());
623                         ASSERT(!node.child3());
624                         childrenAlreadyFixed = true;
625                     }
626                 }
627                 break;
628             }
629                 
630             case Flush:
631             case GetLocal: {
632                 // A Flush could use a GetLocal, SetLocal, SetArgument, or a Phi.
633                 // If it uses a GetLocal, it'll be taken care of below. If it uses a
634                 // SetLocal or SetArgument, then it must be using a node from the
635                 // same block. But if it uses a Phi, then we should redirect it to
636                 // use whatever the first block advertised as a tail operand.
637                 // Similarly for GetLocal; it could use any of those except for
638                 // GetLocal. If it uses a Phi then it should be redirected to use a
639                 // Phi from the tail operand.
640                 if (m_graph[node.child1()].op() != Phi)
641                     break;
642                 
643                 NodeIndex atFirstIndex = firstBlock->variablesAtTail.operand(node.local());
644                 m_graph.changeEdge(node.children.child1(), Edge(skipGetLocal(atFirstIndex)), node.shouldGenerate());
645                 childrenAlreadyFixed = true;
646                 break;
647             }
648                 
649             default:
650                 break;
651             }
652             
653             if (!childrenAlreadyFixed) {
654                 bool changeRef = node.shouldGenerate();
655             
656                 // If the child is a GetLocal, then we might like to fix it.
657                 if (node.flags() & NodeHasVarArgs) {
658                     for (unsigned childIdx = node.firstChild();
659                          childIdx < node.firstChild() + node.numChildren();
660                          ++childIdx) {
661                         if (!!m_graph.m_varArgChildren[childIdx])
662                             fixPossibleGetLocal(firstBlock, m_graph.m_varArgChildren[childIdx], changeRef);
663                     }
664                 } else if (!!node.child1()) {
665                     fixPossibleGetLocal(firstBlock, node.children.child1(), changeRef);
666                     if (!!node.child2()) {
667                         fixPossibleGetLocal(firstBlock, node.children.child2(), changeRef);
668                         if (!!node.child3())
669                             fixPossibleGetLocal(firstBlock, node.children.child3(), changeRef);
670                     }
671                 }
672             }
673
674             firstBlock->append(nodeIndex);
675         }
676         
677         ASSERT(m_graph[firstBlock->last()].isTerminal());
678         
679         // Fix the predecessors of my new successors. This is tricky, since we are going to reset
680         // all predecessors anyway due to reachability analysis. But we need to fix the
681         // predecessors eagerly to ensure that we know what they are in case the next block we
682         // consider in this phase wishes to query the predecessors of one of the blocks we
683         // affected.
684         for (unsigned i = m_graph.numSuccessors(firstBlock); i--;) {
685             BasicBlock* successor = m_graph.m_blocks[m_graph.successor(firstBlock, i)].get();
686             for (unsigned j = 0; j < successor->m_predecessors.size(); ++j) {
687                 if (successor->m_predecessors[j] == secondBlockIndex)
688                     successor->m_predecessors[j] = firstBlockIndex;
689             }
690         }
691         
692         // Fix the predecessors of my former successors. Again, we'd rather not do this, but it's
693         // an unfortunate necessity. See above comment.
694         if (jettisonedBlockIndex != NoBlock)
695             fixJettisonedPredecessors(firstBlockIndex, jettisonedBlockIndex);
696         
697         // Fix up the variables at tail.
698         for (size_t i = 0; i < secondBlock->variablesAtHead.numberOfArguments(); ++i)
699             fixTailOperand(firstBlock, secondBlock, argumentToOperand(i), substitutions);
700         for (size_t i = 0; i < secondBlock->variablesAtHead.numberOfLocals(); ++i)
701             fixTailOperand(firstBlock, secondBlock, i, substitutions);
702         
703         // Fix up the references from our new successors.
704         for (unsigned i = m_graph.numSuccessors(firstBlock); i--;) {
705             BasicBlock* successor = m_graph.m_blocks[m_graph.successor(firstBlock, i)].get();
706             for (unsigned j = 0; j < successor->phis.size(); ++j) {
707                 NodeIndex phiNodeIndex = successor->phis[j];
708                 Node& phiNode = m_graph[phiNodeIndex];
709                 bool changeRef = phiNode.shouldGenerate();
710                 OperandSubstitution substitution = substitutions.operand(phiNode.local());
711 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
712                 dataLogF("    Performing operand substitution @%u -> @%u.\n",
713                         substitution.oldChild, substitution.newChild);
714 #endif
715                 if (!phiNode.child1())
716                     continue;
717                 if (phiNode.child1().index() == substitution.oldChild)
718                     m_graph.changeIndex(phiNode.children.child1(), substitution.newChild, changeRef);
719                 if (!phiNode.child2())
720                     continue;
721                 if (phiNode.child2().index() == substitution.oldChild)
722                     m_graph.changeIndex(phiNode.children.child2(), substitution.newChild, changeRef);
723                 if (!phiNode.child3())
724                     continue;
725                 if (phiNode.child3().index() == substitution.oldChild)
726                     m_graph.changeIndex(phiNode.children.child3(), substitution.newChild, changeRef);
727             }
728         }
729         
730         firstBlock->valuesAtTail = secondBlock->valuesAtTail;
731         firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
732         
733         m_graph.m_blocks[secondBlockIndex].clear();
734     }
735 };
736
737 bool performCFGSimplification(Graph& graph)
738 {
739     SamplingRegion samplingRegion("DFG CFG Simplification Phase");
740     return runPhase<CFGSimplificationPhase>(graph);
741 }
742
743 } } // namespace JSC::DFG
744
745 #endif // ENABLE(DFG_JIT)
746
747