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