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