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