[WTF] Add makeUnique<T>, which ensures T is fast-allocated, makeUnique / makeUniqueWi...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSSAConversionPhase.cpp
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
48 namespace JSC { namespace DFG {
49
50 class SSAConversionPhase : public Phase {
51     static const bool verbose = false;
52     
53 public:
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 = makeUnique<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
483 private:
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
491 bool 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