CFGSimplificationPhase should de-dupe jettisonedBlocks
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGCFGSimplificationPhase.cpp
1 /*
2  * Copyright (C) 2012-2015 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 "DFGBasicBlockInlines.h"
32 #include "DFGGraph.h"
33 #include "DFGInsertionSet.h"
34 #include "DFGPhase.h"
35 #include "DFGValidate.h"
36 #include "JSCInlines.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 canMergeBlocks(BasicBlock* block, BasicBlock* targetBlock)
48     {
49         return targetBlock->predecessors.size() == 1 && targetBlock != block;
50     }
51     
52     bool run()
53     {
54         // FIXME: We should make this work in SSA. https://bugs.webkit.org/show_bug.cgi?id=148260
55         DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA);
56         
57         const bool extremeLogging = false;
58
59         bool outerChanged = false;
60         bool innerChanged;
61         
62         do {
63             innerChanged = false;
64             for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
65                 BasicBlock* block = m_graph.block(blockIndex);
66                 if (!block)
67                     continue;
68                 ASSERT(block->isReachable);
69
70                 auto canMergeWithBlock = [&] (BasicBlock* targetBlock) {
71                     return canMergeBlocks(block, targetBlock);
72                 };
73             
74                 switch (block->terminal()->op()) {
75                 case Jump: {
76                     // Successor with one predecessor -> merge.
77                     if (canMergeWithBlock(block->successor(0))) {
78                         ASSERT(block->successor(0)->predecessors[0] == block);
79                         if (extremeLogging)
80                             m_graph.dump();
81                         m_graph.dethread();
82                         mergeBlocks(block, block->successor(0), noBlocks());
83                         innerChanged = outerChanged = true;
84                         break;
85                     }
86                 
87                     // FIXME: Block only has a jump -> remove. This is tricky though because of
88                     // liveness. What we really want is to slam in a phantom at the end of the
89                     // block, after the terminal. But we can't right now. :-(
90                     // Idea: what if I slam the ghosties into my successor? Nope, that's
91                     // suboptimal, because if my successor has multiple predecessors then we'll
92                     // be keeping alive things on other predecessor edges unnecessarily.
93                     // What we really need is the notion of end-of-block ghosties!
94                     // FIXME: Allow putting phantoms after terminals.
95                     // https://bugs.webkit.org/show_bug.cgi?id=126778
96                     break;
97                 }
98                 
99                 case Branch: {
100                     // Branch on constant -> jettison the not-taken block and merge.
101                     if (isKnownDirection(block->cfaBranchDirection)) {
102                         bool condition = branchCondition(block->cfaBranchDirection);
103                         BasicBlock* targetBlock = block->successorForCondition(condition);
104                         BasicBlock* jettisonedBlock = block->successorForCondition(!condition);
105                         if (canMergeWithBlock(targetBlock)) {
106                             if (extremeLogging)
107                                 m_graph.dump();
108                             m_graph.dethread();
109                             mergeBlocks(block, targetBlock, oneBlock(jettisonedBlock));
110                         } else {
111                             if (extremeLogging)
112                                 m_graph.dump();
113                             m_graph.dethread();
114                             
115                             Node* terminal = block->terminal();
116                             ASSERT(terminal->isTerminal());
117                             NodeOrigin boundaryNodeOrigin = terminal->origin;
118
119                             jettisonBlock(block, jettisonedBlock, boundaryNodeOrigin);
120
121                             block->replaceTerminal(
122                                 m_graph, SpecNone, Jump, boundaryNodeOrigin,
123                                 OpInfo(targetBlock));
124                             
125                             ASSERT(block->terminal());
126                         
127                         }
128                         innerChanged = outerChanged = true;
129                         break;
130                     }
131                     
132                     if (block->successor(0) == block->successor(1)) {
133                         convertToJump(block, block->successor(0));
134                         innerChanged = outerChanged = true;
135                         break;
136                     }
137                     
138                     // Branch to same destination -> jump.
139                     // FIXME: this will currently not be hit because of the lack of jump-only
140                     // block simplification.
141                     
142                     break;
143                 }
144                     
145                 case Switch: {
146                     SwitchData* data = block->terminal()->switchData();
147                     
148                     // Prune out cases that end up jumping to default.
149                     for (unsigned i = 0; i < data->cases.size(); ++i) {
150                         if (data->cases[i].target.block == data->fallThrough.block) {
151                             data->fallThrough.count += data->cases[i].target.count;
152                             data->cases[i--] = data->cases.last();
153                             data->cases.removeLast();
154                         }
155                     }
156                     
157                     // If there are no cases other than default then this turns
158                     // into a jump.
159                     if (data->cases.isEmpty()) {
160                         convertToJump(block, data->fallThrough.block);
161                         innerChanged = outerChanged = true;
162                         break;
163                     }
164                     
165                     // Switch on constant -> jettison all other targets and merge.
166                     Node* terminal = block->terminal();
167                     if (terminal->child1()->hasConstant()) {
168                         FrozenValue* value = terminal->child1()->constant();
169                         TriState found = FalseTriState;
170                         BasicBlock* targetBlock = 0;
171                         for (unsigned i = data->cases.size(); found == FalseTriState && i--;) {
172                             found = data->cases[i].value.strictEqual(value);
173                             if (found == TrueTriState)
174                                 targetBlock = data->cases[i].target.block;
175                         }
176                         
177                         if (found == MixedTriState)
178                             break;
179                         if (found == FalseTriState)
180                             targetBlock = data->fallThrough.block;
181                         ASSERT(targetBlock);
182                         
183                         Vector<BasicBlock*, 1> jettisonedBlocks;
184                         for (BasicBlock* successor : terminal->successors()) {
185                             if (successor != targetBlock && !jettisonedBlocks.contains(successor))
186                                 jettisonedBlocks.append(successor);
187                         }
188                         
189                         if (canMergeWithBlock(targetBlock)) {
190                             if (extremeLogging)
191                                 m_graph.dump();
192                             m_graph.dethread();
193                             
194                             mergeBlocks(block, targetBlock, jettisonedBlocks);
195                         } else {
196                             if (extremeLogging)
197                                 m_graph.dump();
198                             m_graph.dethread();
199                             
200                             NodeOrigin boundaryNodeOrigin = terminal->origin;
201
202                             for (unsigned i = jettisonedBlocks.size(); i--;)
203                                 jettisonBlock(block, jettisonedBlocks[i], boundaryNodeOrigin);
204                             
205                             block->replaceTerminal(
206                                 m_graph, SpecNone, Jump, boundaryNodeOrigin, OpInfo(targetBlock));
207                         }
208                         innerChanged = outerChanged = true;
209                         break;
210                     }
211                     break;
212                 }
213                     
214                 default:
215                     break;
216                 }
217             }
218             
219             if (innerChanged) {
220                 // Here's the reason for this pass:
221                 // Blocks: A, B, C, D, E, F
222                 // A -> B, C
223                 // B -> F
224                 // C -> D, E
225                 // D -> F
226                 // E -> F
227                 //
228                 // Assume that A's branch is determined to go to B. Then the rest of this phase
229                 // is smart enough to simplify down to:
230                 // A -> B
231                 // B -> F
232                 // C -> D, E
233                 // D -> F
234                 // E -> F
235                 //
236                 // We will also merge A and B. But then we don't have any other mechanism to
237                 // remove D, E as predecessors for F. Worse, the rest of this phase does not
238                 // know how to fix the Phi functions of F to ensure that they no longer refer
239                 // to variables in D, E. In general, we need a way to handle Phi simplification
240                 // upon:
241                 // 1) Removal of a predecessor due to branch simplification. The branch
242                 //    simplifier already does that.
243                 // 2) Invalidation of a predecessor because said predecessor was rendered
244                 //    unreachable. We do this here.
245                 //
246                 // This implies that when a block is unreachable, we must inspect its
247                 // successors' Phi functions to remove any references from them into the
248                 // removed block.
249                 
250                 m_graph.invalidateCFG();
251                 m_graph.resetReachability();
252                 m_graph.killUnreachableBlocks();
253             }
254             
255             if (Options::validateGraphAtEachPhase())
256                 validate();
257         } while (innerChanged);
258         
259         return outerChanged;
260     }
261
262 private:
263     void convertToJump(BasicBlock* block, BasicBlock* targetBlock)
264     {
265         ASSERT(targetBlock);
266         ASSERT(targetBlock->isReachable);
267         if (canMergeBlocks(block, targetBlock)) {
268             m_graph.dethread();
269             mergeBlocks(block, targetBlock, noBlocks());
270         } else {
271             Node* branch = block->terminal();
272             ASSERT(branch->op() == Branch || branch->op() == Switch);
273
274             block->replaceTerminal(
275                 m_graph, SpecNone, Jump, branch->origin, OpInfo(targetBlock));
276         }
277     }
278     
279     void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, NodeOrigin nodeOrigin, VirtualRegister operand)
280     {
281         Node* livenessNode = jettisonedBlock->variablesAtHead.operand(operand);
282         if (!livenessNode)
283             return;
284         NodeType nodeType;
285         if (livenessNode->flags() & NodeIsFlushed)
286             nodeType = Flush;
287         else {
288             // This seems like it shouldn't be necessary because we could just rematerialize
289             // PhantomLocals or something similar using bytecode liveness. However, in ThreadedCPS, it's
290             // worth the sanity to maintain this eagerly. See
291             // https://bugs.webkit.org/show_bug.cgi?id=144086
292             nodeType = PhantomLocal;
293         }
294         block->appendNode(
295             m_graph, SpecNone, nodeType, nodeOrigin, 
296             OpInfo(livenessNode->variableAccessData()));
297     }
298     
299     void jettisonBlock(BasicBlock* block, BasicBlock* jettisonedBlock, NodeOrigin boundaryNodeOrigin)
300     {
301         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
302             keepOperandAlive(block, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForArgument(i));
303         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
304             keepOperandAlive(block, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForLocal(i));
305         
306         fixJettisonedPredecessors(block, jettisonedBlock);
307     }
308     
309     void fixJettisonedPredecessors(BasicBlock* block, BasicBlock* jettisonedBlock)
310     {
311         jettisonedBlock->removePredecessor(block);
312     }
313
314     Vector<BasicBlock*, 1> noBlocks()
315     {
316         return Vector<BasicBlock*, 1>();
317     }
318     
319     Vector<BasicBlock*, 1> oneBlock(BasicBlock* block)
320     {
321         Vector<BasicBlock*, 1> result;
322         result.append(block);
323         return result;
324     }
325     
326     void mergeBlocks(
327         BasicBlock* firstBlock, BasicBlock* secondBlock,
328         Vector<BasicBlock*, 1> jettisonedBlocks)
329     {
330         RELEASE_ASSERT(canMergeBlocks(firstBlock, secondBlock));
331         // This will add all of the nodes in secondBlock to firstBlock, but in so doing
332         // it will also ensure that any GetLocals from the second block that refer to
333         // SetLocals in the first block are relinked. If jettisonedBlock is not NoBlock,
334         // then Phantoms are inserted for anything that the jettisonedBlock would have
335         // kept alive.
336         
337         // Remove the terminal of firstBlock since we don't need it anymore. Well, we don't
338         // really remove it; we actually turn it into a check.
339         Node* terminal = firstBlock->terminal();
340         ASSERT(terminal->isTerminal());
341         NodeOrigin boundaryNodeOrigin = terminal->origin;
342         terminal->remove(m_graph);
343         ASSERT(terminal->refCount() == 1);
344         
345         for (unsigned i = jettisonedBlocks.size(); i--;) {
346             BasicBlock* jettisonedBlock = jettisonedBlocks[i];
347             
348             // Time to insert ghosties for things that need to be kept alive in case we OSR
349             // exit prior to hitting the firstBlock's terminal, and end up going down a
350             // different path than secondBlock.
351             
352             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
353                 keepOperandAlive(firstBlock, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForArgument(i));
354             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
355                 keepOperandAlive(firstBlock, jettisonedBlock, boundaryNodeOrigin, virtualRegisterForLocal(i));
356         }
357         
358         for (size_t i = 0; i < secondBlock->phis.size(); ++i)
359             firstBlock->phis.append(secondBlock->phis[i]);
360
361         for (size_t i = 0; i < secondBlock->size(); ++i)
362             firstBlock->append(secondBlock->at(i));
363         
364         ASSERT(firstBlock->terminal()->isTerminal());
365         
366         // Fix the predecessors of my new successors. This is tricky, since we are going to reset
367         // all predecessors anyway due to reachability analysis. But we need to fix the
368         // predecessors eagerly to ensure that we know what they are in case the next block we
369         // consider in this phase wishes to query the predecessors of one of the blocks we
370         // affected.
371         for (unsigned i = firstBlock->numSuccessors(); i--;) {
372             BasicBlock* successor = firstBlock->successor(i);
373             for (unsigned j = 0; j < successor->predecessors.size(); ++j) {
374                 if (successor->predecessors[j] == secondBlock)
375                     successor->predecessors[j] = firstBlock;
376             }
377         }
378         
379         // Fix the predecessors of my former successors. Again, we'd rather not do this, but it's
380         // an unfortunate necessity. See above comment.
381         for (unsigned i = jettisonedBlocks.size(); i--;)
382             fixJettisonedPredecessors(firstBlock, jettisonedBlocks[i]);
383         
384         firstBlock->valuesAtTail = secondBlock->valuesAtTail;
385         firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
386         
387         m_graph.killBlock(secondBlock);
388     }
389 };
390
391 bool performCFGSimplification(Graph& graph)
392 {
393     return runPhase<CFGSimplificationPhase>(graph);
394 }
395
396 } } // namespace JSC::DFG
397
398 #endif // ENABLE(DFG_JIT)
399
400