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