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