DFG DCE might eliminate checks unsoundly
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGCFGSimplificationPhase.cpp
1 /*
2  * Copyright (C) 2012, 2013 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "DFGCFGSimplificationPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractState.h"
32 #include "DFGBasicBlockInlines.h"
33 #include "DFGGraph.h"
34 #include "DFGInsertionSet.h"
35 #include "DFGPhase.h"
36 #include "DFGValidate.h"
37 #include "Operations.h"
38
39 namespace JSC { namespace DFG {
40
41 class CFGSimplificationPhase : public Phase {
42 public:
43     CFGSimplificationPhase(Graph& graph)
44         : Phase(graph, "CFG simplification")
45     {
46     }
47     
48     bool run()
49     {
50         const bool extremeLogging = false;
51
52         bool outerChanged = false;
53         bool innerChanged;
54         
55         do {
56             innerChanged = false;
57             for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
58                 BasicBlock* block = m_graph.m_blocks[blockIndex].get();
59                 if (!block)
60                     continue;
61                 ASSERT(block->isReachable);
62             
63                 switch (block->last()->op()) {
64                 case Jump: {
65                     // Successor with one predecessor -> merge.
66                     if (m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors.size() == 1) {
67                         ASSERT(m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors[0]
68                                == blockIndex);
69 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
70                         dataLogF("CFGSimplify: Jump merge on Block #%u to Block #%u.\n",
71                                 blockIndex, m_graph.successor(block, 0));
72 #endif
73                         if (extremeLogging)
74                             m_graph.dump();
75                         m_graph.dethread();
76                         mergeBlocks(blockIndex, m_graph.successor(block, 0), NoBlock);
77                         innerChanged = outerChanged = true;
78                         break;
79                     } else {
80 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
81                         dataLogF("Not jump merging on Block #%u to Block #%u because predecessors = ",
82                                 blockIndex, m_graph.successor(block, 0));
83                         for (unsigned i = 0; i < m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors.size(); ++i) {
84                             if (i)
85                                 dataLogF(", ");
86                             dataLogF("#%u", m_graph.m_blocks[m_graph.successor(block, 0)]->m_predecessors[i]);
87                         }
88                         dataLogF(".\n");
89 #endif
90                     }
91                 
92                     // FIXME: Block only has a jump -> remove. This is tricky though because of
93                     // liveness. What we really want is to slam in a phantom at the end of the
94                     // block, after the terminal. But we can't right now. :-(
95                     // Idea: what if I slam the ghosties into my successor? Nope, that's
96                     // suboptimal, because if my successor has multiple predecessors then we'll
97                     // be keeping alive things on other predecessor edges unnecessarily.
98                     // What we really need is the notion of end-of-block ghosties!
99                     break;
100                 }
101                 
102                 case Branch: {
103                     // Branch on constant -> jettison the not-taken block and merge.
104                     if (isKnownDirection(block->cfaBranchDirection)) {
105                         bool condition = branchCondition(block->cfaBranchDirection);
106                         BasicBlock* targetBlock = m_graph.m_blocks[
107                             m_graph.successorForCondition(block, condition)].get();
108                         if (targetBlock->m_predecessors.size() == 1) {
109 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
110                             dataLogF("CFGSimplify: Known condition (%s) branch merge on Block #%u to Block #%u, jettisoning Block #%u.\n",
111                                     condition ? "true" : "false",
112                                     blockIndex, m_graph.successorForCondition(block, condition),
113                                     m_graph.successorForCondition(block, !condition));
114 #endif
115                             if (extremeLogging)
116                                 m_graph.dump();
117                             m_graph.dethread();
118                             mergeBlocks(
119                                 blockIndex,
120                                 m_graph.successorForCondition(block, condition),
121                                 m_graph.successorForCondition(block, !condition));
122                         } else {
123 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
124                             dataLogF("CFGSimplify: Known condition (%s) branch->jump conversion on Block #%u to Block #%u, jettisoning Block #%u.\n",
125                                     condition ? "true" : "false",
126                                     blockIndex, m_graph.successorForCondition(block, condition),
127                                     m_graph.successorForCondition(block, !condition));
128 #endif
129                             if (extremeLogging)
130                                 m_graph.dump();
131                             m_graph.dethread();
132                             BlockIndex takenBlockIndex = m_graph.successorForCondition(block, condition);
133                             BlockIndex notTakenBlockIndex = m_graph.successorForCondition(block, !condition);
134                         
135                             ASSERT(block->last()->isTerminal());
136                             CodeOrigin boundaryCodeOrigin = block->last()->codeOrigin;
137                             block->last()->convertToPhantom();
138                             ASSERT(block->last()->refCount() == 1);
139                         
140                             jettisonBlock(blockIndex, notTakenBlockIndex, boundaryCodeOrigin);
141                         
142                             block->appendNode(
143                                 m_graph, SpecNone, Jump, boundaryCodeOrigin,
144                                 OpInfo(takenBlockIndex));
145                         }
146                         innerChanged = outerChanged = true;
147                         break;
148                     }
149                     
150                     if (m_graph.successor(block, 0) == m_graph.successor(block, 1)) {
151                         BlockIndex targetBlockIndex = m_graph.successor(block, 0);
152                         BasicBlock* targetBlock = m_graph.m_blocks[targetBlockIndex].get();
153                         ASSERT(targetBlock);
154                         ASSERT(targetBlock->isReachable);
155                         if (targetBlock->m_predecessors.size() == 1) {
156 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
157                             dataLogF("CFGSimplify: Branch to same successor merge on Block #%u to Block #%u.\n",
158                                     blockIndex, targetBlockIndex);
159 #endif
160                             m_graph.dethread();
161                             mergeBlocks(blockIndex, targetBlockIndex, NoBlock);
162                         } else {
163 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
164                             dataLogF("CFGSimplify: Branch->jump conversion to same successor on Block #%u to Block #%u.\n",
165                                     blockIndex, targetBlockIndex);
166 #endif
167                             Node* branch = block->last();
168                             ASSERT(branch->isTerminal());
169                             ASSERT(branch->op() == Branch);
170                             branch->convertToPhantom();
171                             ASSERT(branch->refCount() == 1);
172                             
173                             block->appendNode(
174                                 m_graph, SpecNone, Jump, branch->codeOrigin,
175                                 OpInfo(targetBlockIndex));
176                         }
177                         innerChanged = outerChanged = true;
178                         break;
179                     }
180                     
181 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
182                     dataLogF("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             if (Options::validateGraphAtEachPhase())
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         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
258             m_graph.m_allocator.free(block->phis[phiIndex]);
259         for (unsigned nodeIndex = block->size(); nodeIndex--;)
260             m_graph.m_allocator.free(block->at(nodeIndex));
261         
262         m_graph.m_blocks[blockIndex].clear();
263     }
264     
265     void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, CodeOrigin codeOrigin, int operand)
266     {
267         Node* livenessNode = jettisonedBlock->variablesAtHead.operand(operand);
268         if (!livenessNode)
269             return;
270         if (livenessNode->variableAccessData()->isCaptured())
271             return;
272         if (!livenessNode->shouldGenerate())
273             return;
274         block->appendNode(
275             m_graph, SpecNone, PhantomLocal, codeOrigin, 
276             OpInfo(livenessNode->variableAccessData()));
277     }
278     
279     void jettisonBlock(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex, CodeOrigin boundaryCodeOrigin)
280     {
281         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
282         BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
283         
284         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
285             keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, argumentToOperand(i));
286         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
287             keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, i);
288         
289         fixJettisonedPredecessors(blockIndex, jettisonedBlockIndex);
290     }
291     
292     void fixJettisonedPredecessors(BlockIndex blockIndex, BlockIndex jettisonedBlockIndex)
293     {
294 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
295         dataLogF("Fixing predecessors and phis due to jettison of Block #%u from Block #%u.\n",
296                 jettisonedBlockIndex, blockIndex);
297 #endif
298         BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
299         for (unsigned i = 0; i < jettisonedBlock->m_predecessors.size(); ++i) {
300             if (jettisonedBlock->m_predecessors[i] != blockIndex)
301                 continue;
302             jettisonedBlock->m_predecessors[i] = jettisonedBlock->m_predecessors.last();
303             jettisonedBlock->m_predecessors.removeLast();
304             break;
305         }
306     }
307     
308     void mergeBlocks(
309         BlockIndex firstBlockIndex, BlockIndex secondBlockIndex, BlockIndex jettisonedBlockIndex)
310     {
311         // This will add all of the nodes in secondBlock to firstBlock, but in so doing
312         // it will also ensure that any GetLocals from the second block that refer to
313         // SetLocals in the first block are relinked. If jettisonedBlock is not NoBlock,
314         // then Phantoms are inserted for anything that the jettisonedBlock would have
315         // kept alive.
316         
317         BasicBlock* firstBlock = m_graph.m_blocks[firstBlockIndex].get();
318         BasicBlock* secondBlock = m_graph.m_blocks[secondBlockIndex].get();
319         
320         // Remove the terminal of firstBlock since we don't need it anymore. Well, we don't
321         // really remove it; we actually turn it into a Phantom.
322         ASSERT(firstBlock->last()->isTerminal());
323         CodeOrigin boundaryCodeOrigin = firstBlock->last()->codeOrigin;
324         firstBlock->last()->convertToPhantom();
325         ASSERT(firstBlock->last()->refCount() == 1);
326         
327         if (jettisonedBlockIndex != NoBlock) {
328             BasicBlock* jettisonedBlock = m_graph.m_blocks[jettisonedBlockIndex].get();
329             
330             // Time to insert ghosties for things that need to be kept alive in case we OSR
331             // exit prior to hitting the firstBlock's terminal, and end up going down a
332             // different path than secondBlock.
333             
334             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
335                 keepOperandAlive(firstBlock, jettisonedBlock, boundaryCodeOrigin, argumentToOperand(i));
336             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
337                 keepOperandAlive(firstBlock, jettisonedBlock, boundaryCodeOrigin, i);
338         }
339         
340         for (size_t i = 0; i < secondBlock->phis.size(); ++i)
341             firstBlock->phis.append(secondBlock->phis[i]);
342
343         for (size_t i = 0; i < secondBlock->size(); ++i)
344             firstBlock->append(secondBlock->at(i));
345         
346         ASSERT(firstBlock->last()->isTerminal());
347         
348         // Fix the predecessors of my new successors. This is tricky, since we are going to reset
349         // all predecessors anyway due to reachability analysis. But we need to fix the
350         // predecessors eagerly to ensure that we know what they are in case the next block we
351         // consider in this phase wishes to query the predecessors of one of the blocks we
352         // affected.
353         for (unsigned i = m_graph.numSuccessors(firstBlock); i--;) {
354             BasicBlock* successor = m_graph.m_blocks[m_graph.successor(firstBlock, i)].get();
355             for (unsigned j = 0; j < successor->m_predecessors.size(); ++j) {
356                 if (successor->m_predecessors[j] == secondBlockIndex)
357                     successor->m_predecessors[j] = firstBlockIndex;
358             }
359         }
360         
361         // Fix the predecessors of my former successors. Again, we'd rather not do this, but it's
362         // an unfortunate necessity. See above comment.
363         if (jettisonedBlockIndex != NoBlock)
364             fixJettisonedPredecessors(firstBlockIndex, jettisonedBlockIndex);
365         
366         firstBlock->valuesAtTail = secondBlock->valuesAtTail;
367         firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
368         
369         m_graph.m_blocks[secondBlockIndex].clear();
370     }
371 };
372
373 bool performCFGSimplification(Graph& graph)
374 {
375     SamplingRegion samplingRegion("DFG CFG Simplification Phase");
376     return runPhase<CFGSimplificationPhase>(graph);
377 }
378
379 } } // namespace JSC::DFG
380
381 #endif // ENABLE(DFG_JIT)
382
383