1/*
2 * Copyright (C) 2013-2017 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 "DFGSSAConversionPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBasicBlockInlines.h"
32#include "DFGBlockInsertionSet.h"
33#include "DFGGraph.h"
34#include "DFGInsertionSet.h"
35#include "DFGPhase.h"
36#include "DFGSSACalculator.h"
37#include "DFGVariableAccessDataDump.h"
38#include "JSCInlines.h"
39
40#undef RELEASE_ASSERT
41#define RELEASE_ASSERT(assertion) do { \
42 if (!(assertion)) { \
43 WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
44 CRASH(); \
45 } \
46} while (0)
47
48namespace JSC { namespace DFG {
49
50class SSAConversionPhase : public Phase {
51 static const bool verbose = false;
52
53public:
54 SSAConversionPhase(Graph& graph)
55 : Phase(graph, "SSA conversion")
56 , m_insertionSet(graph)
57 {
58 }
59
60 bool run()
61 {
62 RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
63 RELEASE_ASSERT(!m_graph.m_isInSSAConversion);
64 m_graph.m_isInSSAConversion = true;
65
66 m_graph.clearReplacements();
67 m_graph.clearCPSCFGData();
68
69 HashMap<unsigned, BasicBlock*, WTF::IntHash<unsigned>, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> entrypointIndexToArgumentsBlock;
70
71 m_graph.m_numberOfEntrypoints = m_graph.m_roots.size();
72 m_graph.m_argumentFormats.resize(m_graph.m_numberOfEntrypoints);
73
74 for (unsigned entrypointIndex = 0; entrypointIndex < m_graph.m_numberOfEntrypoints; ++entrypointIndex) {
75 BasicBlock* oldRoot = m_graph.m_roots[entrypointIndex];
76 entrypointIndexToArgumentsBlock.add(entrypointIndex, oldRoot);
77
78 NodeOrigin origin = oldRoot->at(0)->origin;
79 m_insertionSet.insertNode(
80 0, SpecNone, InitializeEntrypointArguments, origin, OpInfo(entrypointIndex));
81 m_insertionSet.insertNode(
82 0, SpecNone, ExitOK, origin);
83 m_insertionSet.execute(oldRoot);
84 }
85
86 if (m_graph.m_numberOfEntrypoints > 1) {
87 BlockInsertionSet blockInsertionSet(m_graph);
88 BasicBlock* newRoot = blockInsertionSet.insert(0, 1.0f);
89
90 EntrySwitchData* entrySwitchData = m_graph.m_entrySwitchData.add();
91 for (unsigned entrypointIndex = 0; entrypointIndex < m_graph.m_numberOfEntrypoints; ++entrypointIndex) {
92 BasicBlock* oldRoot = m_graph.m_roots[entrypointIndex];
93 entrySwitchData->cases.append(oldRoot);
94
95 ASSERT(oldRoot->predecessors.isEmpty());
96 oldRoot->predecessors.append(newRoot);
97
98 if (oldRoot->isCatchEntrypoint) {
99 ASSERT(!!entrypointIndex);
100 m_graph.m_entrypointIndexToCatchBytecodeOffset.add(entrypointIndex, oldRoot->bytecodeBegin);
101 }
102 }
103
104 RELEASE_ASSERT(entrySwitchData->cases[0] == m_graph.block(0)); // We strongly assume the normal call entrypoint is the first item in the list.
105
106 const bool exitOK = false;
107 NodeOrigin origin { CodeOrigin(0), CodeOrigin(0), exitOK };
108 newRoot->appendNode(
109 m_graph, SpecNone, EntrySwitch, origin, OpInfo(entrySwitchData));
110
111 m_graph.m_roots.clear();
112 m_graph.m_roots.append(newRoot);
113
114 blockInsertionSet.execute();
115 }
116
117 SSACalculator calculator(m_graph);
118
119 m_graph.ensureSSADominators();
120
121 if (verbose) {
122 dataLog("Graph before SSA transformation:\n");
123 m_graph.dump();
124 }
125
126 // Create a SSACalculator::Variable for every root VariableAccessData.
127 for (VariableAccessData& variable : m_graph.m_variableAccessData) {
128 if (!variable.isRoot())
129 continue;
130
131 SSACalculator::Variable* ssaVariable = calculator.newVariable();
132 ASSERT(ssaVariable->index() == m_variableForSSAIndex.size());
133 m_variableForSSAIndex.append(&variable);
134 m_ssaVariableForVariable.add(&variable, ssaVariable);
135 }
136
137 // Find all SetLocals and create Defs for them. We handle SetArgumentDefinitely by creating a
138 // GetLocal, and recording the flush format.
139 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
140 BasicBlock* block = m_graph.block(blockIndex);
141 if (!block)
142 continue;
143
144 // Must process the block in forward direction because we want to see the last
145 // assignment for every local.
146 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
147 Node* node = block->at(nodeIndex);
148 if (node->op() != SetLocal && node->op() != SetArgumentDefinitely)
149 continue;
150
151 VariableAccessData* variable = node->variableAccessData();
152
153 Node* childNode;
154 if (node->op() == SetLocal)
155 childNode = node->child1().node();
156 else {
157 ASSERT(node->op() == SetArgumentDefinitely);
158 childNode = m_insertionSet.insertNode(
159 nodeIndex, node->variableAccessData()->prediction(),
160 GetStack, node->origin,
161 OpInfo(m_graph.m_stackAccessData.add(variable->local(), variable->flushFormat())));
162 if (!ASSERT_DISABLED)
163 m_argumentGetters.add(childNode);
164 m_argumentMapping.add(node, childNode);
165 }
166
167 calculator.newDef(
168 m_ssaVariableForVariable.get(variable), block, childNode);
169 }
170
171 m_insertionSet.execute(block);
172 }
173
174 // Decide where Phis are to be inserted. This creates the Phi's but doesn't insert them
175 // yet. We will later know where to insert based on where SSACalculator tells us to.
176 calculator.computePhis(
177 [&] (SSACalculator::Variable* ssaVariable, BasicBlock* block) -> Node* {
178 VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
179
180 // Prune by liveness. This doesn't buy us much other than compile times.
181 Node* headNode = block->variablesAtHead.operand(variable->local());
182 if (!headNode)
183 return nullptr;
184
185 // There is the possibiltiy of "rebirths". The SSA calculator will already prune
186 // rebirths for the same VariableAccessData. But it will not be able to prune
187 // rebirths that arose from the same local variable number but a different
188 // VariableAccessData. We do that pruning here.
189 //
190 // Here's an example of a rebirth that this would catch:
191 //
192 // var x;
193 // if (foo) {
194 // if (bar) {
195 // x = 42;
196 // } else {
197 // x = 43;
198 // }
199 // print(x);
200 // x = 44;
201 // } else {
202 // x = 45;
203 // }
204 // print(x); // Without this check, we'd have a Phi for x = 42|43 here.
205 //
206 // FIXME: Consider feeding local variable numbers, not VariableAccessData*'s, as
207 // the "variables" for SSACalculator. That would allow us to eliminate this
208 // special case.
209 // https://bugs.webkit.org/show_bug.cgi?id=136641
210 if (headNode->variableAccessData() != variable)
211 return nullptr;
212
213 Node* phiNode = m_graph.addNode(
214 variable->prediction(), Phi, block->at(0)->origin.withInvalidExit());
215 FlushFormat format = variable->flushFormat();
216 NodeFlags result = resultFor(format);
217 phiNode->mergeFlags(result);
218 return phiNode;
219 });
220
221 if (verbose) {
222 dataLog("Computed Phis, about to transform the graph.\n");
223 dataLog("\n");
224 dataLog("Graph:\n");
225 m_graph.dump();
226 dataLog("\n");
227 dataLog("Mappings:\n");
228 for (unsigned i = 0; i < m_variableForSSAIndex.size(); ++i)
229 dataLog(" ", i, ": ", VariableAccessDataDump(m_graph, m_variableForSSAIndex[i]), "\n");
230 dataLog("\n");
231 dataLog("SSA calculator: ", calculator, "\n");
232 }
233
234 // Do the bulk of the SSA conversion. For each block, this tracks the operand->Node
235 // mapping based on a combination of what the SSACalculator tells us, and us walking over
236 // the block in forward order. We use our own data structure, valueForOperand, for
237 // determining the local mapping, but we rely on SSACalculator for the non-local mapping.
238 //
239 // This does three things at once:
240 //
241 // - Inserts the Phis in all of the places where they need to go. We've already created
242 // them and they are accounted for in the SSACalculator's data structures, but we
243 // haven't inserted them yet, mostly because we want to insert all of a block's Phis in
244 // one go to amortize the cost of node insertion.
245 //
246 // - Create and insert Upsilons.
247 //
248 // - Convert all of the preexisting SSA nodes (other than the old CPS Phi nodes) into SSA
249 // form by replacing as follows:
250 //
251 // - MovHint has KillLocal prepended to it.
252 //
253 // - GetLocal die and get replaced with references to the node specified by
254 // valueForOperand.
255 //
256 // - SetLocal turns into PutStack if it's flushed, or turns into a Check otherwise.
257 //
258 // - Flush is removed.
259 //
260 // - PhantomLocal becomes Phantom, and its child is whatever is specified by
261 // valueForOperand.
262 //
263 // - SetArgumentDefinitely is removed. Note that GetStack nodes have already been inserted.
264 //
265 // - SetArgumentMaybe is removed. It should not have any data flow uses.
266 Operands<Node*> valueForOperand(OperandsLike, m_graph.block(0)->variablesAtHead);
267 for (BasicBlock* block : m_graph.blocksInPreOrder()) {
268 valueForOperand.clear();
269
270 // CPS will claim that the root block has all arguments live. But we have already done
271 // the first step of SSA conversion: argument locals are no longer live at head;
272 // instead we have GetStack nodes for extracting the values of arguments. So, we
273 // skip the at-head available value calculation for the root block.
274 if (block != m_graph.block(0)) {
275 for (size_t i = valueForOperand.size(); i--;) {
276 Node* nodeAtHead = block->variablesAtHead[i];
277 if (!nodeAtHead)
278 continue;
279
280 VariableAccessData* variable = nodeAtHead->variableAccessData();
281
282 if (verbose)
283 dataLog("Considering live variable ", VariableAccessDataDump(m_graph, variable), " at head of block ", *block, "\n");
284
285 SSACalculator::Variable* ssaVariable = m_ssaVariableForVariable.get(variable);
286 SSACalculator::Def* def = calculator.reachingDefAtHead(block, ssaVariable);
287 if (!def) {
288 // If we are required to insert a Phi, then we won't have a reaching def
289 // at head.
290 continue;
291 }
292
293 Node* node = def->value();
294 if (node->replacement()) {
295 // This will occur when a SetLocal had a GetLocal as its source. The
296 // GetLocal would get replaced with an actual SSA value by the time we get
297 // here. Note that the SSA value with which the GetLocal got replaced
298 // would not in turn have a replacement.
299 node = node->replacement();
300 ASSERT(!node->replacement());
301 }
302 if (verbose)
303 dataLog("Mapping: ", VirtualRegister(valueForOperand.operandForIndex(i)), " -> ", node, "\n");
304 valueForOperand[i] = node;
305 }
306 }
307
308 // Insert Phis by asking the calculator what phis there are in this block. Also update
309 // valueForOperand with those Phis. For Phis associated with variables that are not
310 // flushed, we also insert a MovHint.
311 size_t phiInsertionPoint = 0;
312 for (SSACalculator::Def* phiDef : calculator.phisForBlock(block)) {
313 VariableAccessData* variable = m_variableForSSAIndex[phiDef->variable()->index()];
314
315 m_insertionSet.insert(phiInsertionPoint, phiDef->value());
316 valueForOperand.operand(variable->local()) = phiDef->value();
317
318 m_insertionSet.insertNode(
319 phiInsertionPoint, SpecNone, MovHint, block->at(0)->origin.withInvalidExit(),
320 OpInfo(variable->local().offset()), phiDef->value()->defaultEdge());
321 }
322
323 if (block->at(0)->origin.exitOK)
324 m_insertionSet.insertNode(phiInsertionPoint, SpecNone, ExitOK, block->at(0)->origin);
325
326 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
327 Node* node = block->at(nodeIndex);
328
329 if (verbose) {
330 dataLog("Processing node ", node, ":\n");
331 m_graph.dump(WTF::dataFile(), " ", node);
332 }
333
334 m_graph.performSubstitution(node);
335
336 switch (node->op()) {
337 case MovHint: {
338 m_insertionSet.insertNode(
339 nodeIndex, SpecNone, KillStack, node->origin,
340 OpInfo(node->unlinkedLocal().offset()));
341 node->origin.exitOK = false; // KillStack clobbers exit.
342 break;
343 }
344
345 case SetLocal: {
346 VariableAccessData* variable = node->variableAccessData();
347 Node* child = node->child1().node();
348
349 if (!!(node->flags() & NodeIsFlushed)) {
350 node->convertToPutStack(
351 m_graph.m_stackAccessData.add(
352 variable->local(), variable->flushFormat()));
353 } else
354 node->remove(m_graph);
355
356 if (verbose)
357 dataLog("Mapping: ", variable->local(), " -> ", child, "\n");
358 valueForOperand.operand(variable->local()) = child;
359 break;
360 }
361
362 case GetStack: {
363 ASSERT(m_argumentGetters.contains(node));
364 valueForOperand.operand(node->stackAccessData()->local) = node;
365 break;
366 }
367
368 case GetLocal: {
369 VariableAccessData* variable = node->variableAccessData();
370 node->children.reset();
371
372 node->remove(m_graph);
373 if (verbose)
374 dataLog("Replacing node ", node, " with ", valueForOperand.operand(variable->local()), "\n");
375 node->setReplacement(valueForOperand.operand(variable->local()));
376 break;
377 }
378
379 case Flush: {
380 node->children.reset();
381 node->remove(m_graph);
382 break;
383 }
384
385 case PhantomLocal: {
386 ASSERT(node->child1().useKind() == UntypedUse);
387 VariableAccessData* variable = node->variableAccessData();
388 node->child1() = valueForOperand.operand(variable->local())->defaultEdge();
389 node->remove(m_graph);
390 break;
391 }
392
393 case SetArgumentDefinitely: {
394 node->remove(m_graph);
395 break;
396 }
397
398 case SetArgumentMaybe: {
399 node->remove(m_graph);
400 break;
401 }
402
403 default:
404 break;
405 }
406 }
407
408 // We want to insert Upsilons just before the end of the block. On the surface this
409 // seems dangerous because the Upsilon will have a checking UseKind. But, we will not
410 // actually be performing the check at the point of the Upsilon; the check will
411 // already have been performed at the point where the original SetLocal was.
412 NodeAndIndex terminal = block->findTerminal();
413 size_t upsilonInsertionPoint = terminal.index;
414 NodeOrigin upsilonOrigin = terminal.node->origin;
415 for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
416 BasicBlock* successorBlock = block->successor(successorIndex);
417 for (SSACalculator::Def* phiDef : calculator.phisForBlock(successorBlock)) {
418 Node* phiNode = phiDef->value();
419 SSACalculator::Variable* ssaVariable = phiDef->variable();
420 VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
421 FlushFormat format = variable->flushFormat();
422
423 // We can use an unchecked use kind because the SetLocal was turned into a Check.
424 // We have to use an unchecked use because at least sometimes, the end of the block
425 // is not exitOK.
426 UseKind useKind = uncheckedUseKindFor(format);
427
428 m_insertionSet.insertNode(
429 upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
430 OpInfo(phiNode), Edge(
431 valueForOperand.operand(variable->local()),
432 useKind));
433 }
434 }
435
436 m_insertionSet.execute(block);
437 }
438
439 // Free all CPS phis and reset variables vectors.
440 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
441 BasicBlock* block = m_graph.block(blockIndex);
442 if (!block)
443 continue;
444 for (unsigned phiIndex = block->phis.size(); phiIndex--;)
445 m_graph.deleteNode(block->phis[phiIndex]);
446 block->phis.clear();
447 block->variablesAtHead.clear();
448 block->variablesAtTail.clear();
449 block->valuesAtHead.clear();
450 block->valuesAtHead.clear();
451 block->ssa = std::make_unique<BasicBlock::SSAData>(block);
452 }
453
454 for (auto& pair : entrypointIndexToArgumentsBlock) {
455 unsigned entrypointIndex = pair.key;
456 BasicBlock* oldRoot = pair.value;
457 ArgumentsVector& arguments = m_graph.m_rootToArguments.find(oldRoot)->value;
458 Vector<FlushFormat> argumentFormats;
459 argumentFormats.reserveInitialCapacity(arguments.size());
460 for (unsigned i = 0; i < arguments.size(); ++i) {
461 Node* node = m_argumentMapping.get(arguments[i]);
462 RELEASE_ASSERT(node);
463 argumentFormats.uncheckedAppend(node->stackAccessData()->format);
464 }
465 m_graph.m_argumentFormats[entrypointIndex] = WTFMove(argumentFormats);
466 }
467
468 m_graph.m_rootToArguments.clear();
469
470 RELEASE_ASSERT(m_graph.m_isInSSAConversion);
471 m_graph.m_isInSSAConversion = false;
472
473 m_graph.m_form = SSA;
474
475 if (verbose) {
476 dataLog("Graph after SSA transformation:\n");
477 m_graph.dump();
478 }
479
480 return true;
481 }
482
483private:
484 InsertionSet m_insertionSet;
485 HashMap<VariableAccessData*, SSACalculator::Variable*> m_ssaVariableForVariable;
486 HashMap<Node*, Node*> m_argumentMapping;
487 HashSet<Node*> m_argumentGetters;
488 Vector<VariableAccessData*> m_variableForSSAIndex;
489};
490
491bool performSSAConversion(Graph& graph)
492{
493 bool result = runPhase<SSAConversionPhase>(graph);
494 return result;
495}
496
497} } // namespace JSC::DFG
498
499#endif // ENABLE(DFG_JIT)
500
501