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