DFG CFG simplification should correct the variables at the head of the predecessor...
[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.\n", edge.index());
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 (changeRef)
306             ASSERT(originalNode->shouldGenerate());
307         // Possibilities:
308         // SetLocal -> the secondBlock is getting the value of something that is immediately
309         //     available in the first block with a known NodeIndex.
310         // GetLocal -> the secondBlock is getting the value of something that the first
311         //     block also gets.
312         // Phi -> the secondBlock is asking for keep-alive on an operand that the first block
313         //     was also asking for keep-alive on.
314         // SetArgument -> the secondBlock is asking for keep-alive on an operand that the
315         //     first block was keeping alive by virtue of the firstBlock being the root and
316         //     the operand being an argument.
317         // Flush -> the secondBlock is asking for keep-alive on an operand that the first
318         //     block was forcing to be alive, so the second block should refer child of
319         //     the flush.
320         if (originalNode->op() == Flush) {
321             originalNodeIndex = originalNode->child1().index();
322             originalNode = &m_graph[originalNodeIndex];
323         }
324         switch (originalNode->op()) {
325         case SetLocal: {
326 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
327             dataLog("        It's a SetLocal.\n");
328 #endif
329             m_graph.changeIndex(edge, originalNode->child1().index(), changeRef);
330             break;
331         }
332         case GetLocal: {
333 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
334             dataLog("        It's a GetLocal.\n");
335 #endif
336             m_graph.changeIndex(edge, originalNodeIndex, changeRef);
337             break;
338         }
339         case Phi:
340         case SetArgument: {
341 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
342             dataLog("        It's Phi/SetArgument.\n");
343 #endif
344             // Keep the GetLocal!
345             break;
346         }
347         default:
348             ASSERT_NOT_REACHED();
349             break;
350         }
351     }
352     
353     void jettisonBlock(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex, CodeOrigin boundaryCodeOrigin)
354     {
355         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
356         BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
357         
358         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
359             keepOperandAlive(block, boundaryCodeOrigin, argumentToOperand(i));
360         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
361             keepOperandAlive(block, boundaryCodeOrigin, i);
362         
363         fixJettisonedPredecessors(blockIndex, jettisonedBlockIndex);
364     }
365     
366     void fixPhis(BlockIndex sourceBlockIndex, BlockIndex destinationBlockIndex)
367     {
368         BasicBlock* sourceBlock = m_graph.m_blocks[sourceBlockIndex].get();
369         BasicBlock* destinationBlock = m_graph.m_blocks[destinationBlockIndex].get();
370         if (!destinationBlock) {
371             // If we're trying to kill off the source block and the destination block is already
372             // dead, then we're done!
373             return;
374         }
375         for (size_t i = 0; i < destinationBlock->phis.size(); ++i) {
376             NodeIndex phiNodeIndex = destinationBlock->phis[i];
377             Node& phiNode = m_graph[phiNodeIndex];
378             NodeIndex myNodeIndex = sourceBlock->variablesAtTail.operand(phiNode.local());
379 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
380             dataLog("Considering removing reference from phi @%u to @%u on local r%d:",
381                     phiNodeIndex, myNodeIndex, phiNode.local());
382 #endif
383             if (myNodeIndex == NoNode) {
384                 // This will happen if there is a phi in the destination that refers into
385                 // the destination itself.
386                 continue;
387             }
388             Node& myNode = m_graph[myNodeIndex];
389             if (myNode.op() == GetLocal)
390                 myNodeIndex = myNode.child1().index();
391             for (unsigned j = 0; j < AdjacencyList::Size; ++j)
392                 removePotentiallyDeadPhiReference(myNodeIndex, phiNode, j);
393 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
394             dataLog("\n");
395 #endif
396         }
397     }
398     
399     void fixJettisonedPredecessors(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex)
400     {
401 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
402         dataLog("Fixing predecessors and phis due to jettison of Block #%u from Block #%u.\n",
403                 jettisonedBlockIndex, blockIndex);
404 #endif
405         BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
406         for (unsigned i = 0; i < jettisonedBlock->m_predecessors.size(); ++i) {
407             if (jettisonedBlock->m_predecessors[i] != blockIndex)
408                 continue;
409             jettisonedBlock->m_predecessors[i] = jettisonedBlock->m_predecessors.last();
410             jettisonedBlock->m_predecessors.removeLast();
411             break;
412         }
413         
414         fixPhis(blockIndex, jettisonedBlockIndex);
415     }
416     
417     void removePotentiallyDeadPhiReference(NodeIndex myNodeIndex, Node& phiNode, unsigned edgeIndex)
418     {
419         if (phiNode.children.child(edgeIndex).indexUnchecked() != myNodeIndex)
420             return;
421 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
422         dataLog(" Removing reference at child %u.", edgeIndex);
423 #endif
424         if (phiNode.shouldGenerate())
425             m_graph.deref(myNodeIndex);
426         phiNode.children.removeEdgeFromBag(edgeIndex);
427     }
428     
429     struct OperandSubstitution {
430         OperandSubstitution()
431             : oldChild(NoNode)
432             , newChild(NoNode)
433         {
434         }
435         
436         explicit OperandSubstitution(NodeIndex oldChild)
437             : oldChild(oldChild)
438             , newChild(oldChild)
439         {
440         }
441         
442         OperandSubstitution(NodeIndex oldChild, NodeIndex newChild)
443             : oldChild(oldChild)
444             , newChild(newChild)
445         {
446             ASSERT((oldChild == NoNode) == (newChild == NoNode));
447         }
448         
449         void dump(FILE* out)
450         {
451             if (oldChild == NoNode)
452                 fprintf(out, "-");
453             else
454                 fprintf(out, "@%u -> @%u", oldChild, newChild);
455         }
456         
457         NodeIndex oldChild;
458         NodeIndex newChild;
459     };
460     
461     NodeIndex skipGetLocal(NodeIndex nodeIndex)
462     {
463         if (nodeIndex == NoNode)
464             return NoNode;
465         Node& node = m_graph[nodeIndex];
466         if (node.op() == GetLocal)
467             return node.child1().index();
468         return nodeIndex;
469     }
470     
471     void recordPossibleIncomingReference(
472         BasicBlock* secondBlock, Operands<OperandSubstitution>& substitutions, int operand)
473     {
474         substitutions.operand(operand) = OperandSubstitution(
475             skipGetLocal(secondBlock->variablesAtTail.operand(operand)));
476     }
477     
478     void recordNewTarget(Operands<OperandSubstitution>& substitutions, int operand, NodeIndex nodeIndex)
479     {
480         ASSERT(m_graph[nodeIndex].op() == SetLocal
481                || m_graph[nodeIndex].op() == SetArgument
482                || m_graph[nodeIndex].op() == Flush
483                || m_graph[nodeIndex].op() == Phi);
484         substitutions.operand(operand).newChild = nodeIndex;
485     }
486     
487     void fixTailOperand(
488         BasicBlock* firstBlock, BasicBlock* secondBlock, int operand,
489         Operands<OperandSubstitution>& substitutions)
490     {
491         NodeIndex atSecondTail = secondBlock->variablesAtTail.operand(operand);
492         
493         if (atSecondTail == NoNode) {
494             // If the variable is dead at the end of the second block, then do nothing; essentially
495             // this means that we want the tail state to reflect whatever the first block did.
496             return;
497         }
498
499         Node& secondNode = m_graph[atSecondTail];
500         
501         switch (secondNode.op()) {
502         case SetLocal:
503         case Flush: {
504             // The second block did interesting things to the variables, so update the tail
505             // accordingly.
506             firstBlock->variablesAtTail.operand(operand) = atSecondTail;
507             break;
508         }
509             
510         case Phi: {
511             // Keep what was in the first block.
512             ASSERT(firstBlock->variablesAtTail.operand(operand) != NoNode);
513             recordNewTarget(substitutions, operand, skipGetLocal(firstBlock->variablesAtTail.operand(operand)));
514             break;
515         }
516
517         case GetLocal: {
518             // If it's a GetLocal on a captured var, then definitely keep what was
519             // in the second block. In particular, it's possible that the first
520             // block doesn't even know about this variable.
521             if (secondNode.variableAccessData()->isCaptured()) {
522                 firstBlock->variablesAtTail.operand(operand) = atSecondTail;
523                 recordNewTarget(substitutions, operand, secondNode.child1().index());
524                 break;
525             }
526             
527             // It's possible that the second block had a GetLocal and the first block
528             // had a SetArgument or a Phi. Then update the tail. Otherwise keep what was in the
529             // first block.
530             NodeIndex atFirstTail = firstBlock->variablesAtTail.operand(operand);
531             ASSERT(atFirstTail != NoNode);
532             switch (m_graph[atFirstTail].op()) {
533             case SetArgument:
534             case Phi:
535                 firstBlock->variablesAtTail.operand(operand) = atSecondTail;
536                 recordNewTarget(substitutions, operand, secondNode.child1().index());
537                 break;
538
539             default:
540                 // Keep what was in the first block, and adjust the substitution to account for
541                 // the fact that successors will refer to the child of the GetLocal.
542                 ASSERT(firstBlock->variablesAtTail.operand(operand) != NoNode);
543                 recordNewTarget(substitutions, operand, skipGetLocal(firstBlock->variablesAtTail.operand(operand)));
544                 break;
545             }
546             break;
547         }
548             
549         default:
550             ASSERT_NOT_REACHED();
551         }
552     }
553     
554     void mergeBlocks(
555         BlockIndex firstBlockIndex, BlockIndex secondBlockIndex, BlockIndex jettisonedBlockIndex)
556     {
557         // This will add all of the nodes in secondBlock to firstBlock, but in so doing
558         // it will also ensure that any GetLocals from the second block that refer to
559         // SetLocals in the first block are relinked. If jettisonedBlock is not NoBlock,
560         // then Phantoms are inserted for anything that the jettisonedBlock would have
561         // kept alive.
562         
563         BasicBlock* firstBlock = m_graph.m_blocks[firstBlockIndex].get();
564         BasicBlock* secondBlock = m_graph.m_blocks[secondBlockIndex].get();
565         
566         // Remove the terminal of firstBlock since we don't need it anymore. Well, we don't
567         // really remove it; we actually turn it into a Phantom.
568         ASSERT(m_graph[firstBlock->last()].isTerminal());
569         CodeOrigin boundaryCodeOrigin = m_graph[firstBlock->last()].codeOrigin;
570         m_graph[firstBlock->last()].setOpAndDefaultFlags(Phantom);
571         ASSERT(m_graph[firstBlock->last()].refCount() == 1);
572         
573         if (jettisonedBlockIndex != NoBlock) {
574             BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
575             
576             // Time to insert ghosties for things that need to be kept alive in case we OSR
577             // exit prior to hitting the firstBlock's terminal, and end up going down a
578             // different path than secondBlock.
579             
580             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
581                 keepOperandAlive(firstBlock, boundaryCodeOrigin, argumentToOperand(i));
582             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
583                 keepOperandAlive(firstBlock, boundaryCodeOrigin, i);
584         }
585         
586         for (size_t i = 0; i < secondBlock->phis.size(); ++i)
587             firstBlock->phis.append(secondBlock->phis[i]);
588
589         // Before we start changing the second block's graph, record what nodes would
590         // be referenced by successors of the second block.
591         Operands<OperandSubstitution> substitutions(
592             secondBlock->variablesAtTail.numberOfArguments(),
593             secondBlock->variablesAtTail.numberOfLocals());
594         for (size_t i = 0; i < secondBlock->variablesAtTail.numberOfArguments(); ++i)
595             recordPossibleIncomingReference(secondBlock, substitutions, argumentToOperand(i));
596         for (size_t i = 0; i < secondBlock->variablesAtTail.numberOfLocals(); ++i)
597             recordPossibleIncomingReference(secondBlock, substitutions, i);
598
599         for (size_t i = 0; i < secondBlock->size(); ++i) {
600             NodeIndex nodeIndex = secondBlock->at(i);
601             Node& node = m_graph[nodeIndex];
602             
603             switch (node.op()) {
604             case Phantom: {
605                 if (!node.child1())
606                     break;
607                 
608                 ASSERT(node.shouldGenerate());
609                 Node& possibleLocalOp = m_graph[node.child1()];
610                 if (possibleLocalOp.hasLocal()) {
611                     NodeIndex setLocalIndex =
612                         firstBlock->variablesAtTail.operand(possibleLocalOp.local());
613                     Node& setLocal = m_graph[setLocalIndex];
614                     if (setLocal.op() == SetLocal)
615                         m_graph.changeEdge(node.children.child1(), setLocal.child1());
616                 }
617                 break;
618             }
619                 
620             case Flush:
621             case GetLocal: {
622                 // A Flush could use a GetLocal, SetLocal, SetArgument, or a Phi.
623                 // If it uses a GetLocal, it'll be taken care of below. If it uses a
624                 // SetLocal or SetArgument, then it must be using a node from the
625                 // same block. But if it uses a Phi, then we should redirect it to
626                 // use whatever the first block advertised as a tail operand.
627                 // Similarly for GetLocal; it could use any of those except for
628                 // GetLocal. If it uses a Phi then it should be redirected to use a
629                 // Phi from the tail operand.
630                 if (m_graph[node.child1()].op() != Phi)
631                     break;
632                 
633                 NodeIndex atFirstIndex = firstBlock->variablesAtTail.operand(node.local());
634                 m_graph.changeEdge(node.children.child1(), Edge(skipGetLocal(atFirstIndex)), node.shouldGenerate());
635                 
636                 if (node.op() != GetLocal)
637                     break;
638                 
639                 NodeIndex atFirstHeadIndex = firstBlock->variablesAtHead.operand(node.local());
640                 if (atFirstHeadIndex == NoNode)
641                     break;
642                 
643                 if (m_graph[atFirstHeadIndex].op() != Phi)
644                     break;
645                 
646                 firstBlock->variablesAtHead.operand(node.local()) = nodeIndex;
647                 break;
648             }
649                 
650             default:
651                 break;
652             }
653             
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                     fixPossibleGetLocal(firstBlock, m_graph.m_varArgChildren[childIdx], changeRef);
662             } else if (!!node.child1()) {
663                 fixPossibleGetLocal(firstBlock, node.children.child1(), changeRef);
664                 if (!!node.child2()) {
665                     fixPossibleGetLocal(firstBlock, node.children.child2(), changeRef);
666                     if (!!node.child3())
667                         fixPossibleGetLocal(firstBlock, node.children.child3(), changeRef);
668                 }
669             }
670
671             firstBlock->append(nodeIndex);
672         }
673         
674         ASSERT(m_graph[firstBlock->last()].isTerminal());
675         
676         // Fix the predecessors of my new successors. This is tricky, since we are going to reset
677         // all predecessors anyway due to reachability analysis. But we need to fix the
678         // predecessors eagerly to ensure that we know what they are in case the next block we
679         // consider in this phase wishes to query the predecessors of one of the blocks we
680         // affected.
681         for (unsigned i = m_graph.numSuccessors(firstBlock); i--;) {
682             BasicBlock* successor = m_graph.m_blocks[m_graph.successor(firstBlock, i)].get();
683             for (unsigned j = 0; j < successor->m_predecessors.size(); ++j) {
684                 if (successor->m_predecessors[j] == secondBlockIndex)
685                     successor->m_predecessors[j] = firstBlockIndex;
686             }
687         }
688         
689         // Fix the predecessors of my former successors. Again, we'd rather not do this, but it's
690         // an unfortunate necessity. See above comment.
691         if (jettisonedBlockIndex != NoBlock)
692             fixJettisonedPredecessors(firstBlockIndex, jettisonedBlockIndex);
693         
694         // Fix up the variables at tail.
695         for (size_t i = 0; i < secondBlock->variablesAtHead.numberOfArguments(); ++i)
696             fixTailOperand(firstBlock, secondBlock, argumentToOperand(i), substitutions);
697         for (size_t i = 0; i < secondBlock->variablesAtHead.numberOfLocals(); ++i)
698             fixTailOperand(firstBlock, secondBlock, i, substitutions);
699         
700         // Fix up the references from our new successors.
701         for (unsigned i = m_graph.numSuccessors(firstBlock); i--;) {
702             BasicBlock* successor = m_graph.m_blocks[m_graph.successor(firstBlock, i)].get();
703             for (unsigned j = 0; j < successor->phis.size(); ++j) {
704                 NodeIndex phiNodeIndex = successor->phis[j];
705                 Node& phiNode = m_graph[phiNodeIndex];
706                 bool changeRef = phiNode.shouldGenerate();
707                 OperandSubstitution substitution = substitutions.operand(phiNode.local());
708 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
709                 dataLog("    Performing operand substitution @%u -> @%u.\n",
710                         substitution.oldChild, substitution.newChild);
711 #endif
712                 if (!phiNode.child1())
713                     continue;
714                 if (phiNode.child1().index() == substitution.oldChild)
715                     m_graph.changeIndex(phiNode.children.child1(), substitution.newChild, changeRef);
716                 if (!phiNode.child2())
717                     continue;
718                 if (phiNode.child2().index() == substitution.oldChild)
719                     m_graph.changeIndex(phiNode.children.child2(), substitution.newChild, changeRef);
720                 if (!phiNode.child3())
721                     continue;
722                 if (phiNode.child3().index() == substitution.oldChild)
723                     m_graph.changeIndex(phiNode.children.child3(), substitution.newChild, changeRef);
724             }
725         }
726         
727         firstBlock->valuesAtTail = secondBlock->valuesAtTail;
728         
729         m_graph.m_blocks[secondBlockIndex].clear();
730     }
731 };
732
733 bool performCFGSimplification(Graph& graph)
734 {
735     return runPhase<CFGSimplificationPhase>(graph);
736 }
737
738 } } // namespace JSC::DFG
739
740 #endif // ENABLE(DFG_JIT)
741
742