Move back primary header includes next to config.h
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSSAConversionPhase.cpp
1 /*
2  * Copyright (C) 2013, 2014 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 "JSCInlines.h"
36
37 namespace JSC { namespace DFG {
38
39 class SSAConversionPhase : public Phase {
40     static const bool verbose = false;
41     static const bool dumpGraph = false;
42     
43 public:
44     SSAConversionPhase(Graph& graph)
45         : Phase(graph, "SSA conversion")
46         , m_insertionSet(graph)
47         , m_changed(false)
48     {
49     }
50     
51     bool run()
52     {
53         RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
54         
55         if (dumpGraph) {
56             dataLog("Graph dump at top of SSA conversion:\n");
57             m_graph.dump();
58         }
59         
60         // Figure out which SetLocal's need flushing. Need to do this while the
61         // Phi graph is still intact.
62         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
63             BasicBlock* block = m_graph.block(blockIndex);
64             if (!block)
65                 continue;
66             for (unsigned nodeIndex = block->size(); nodeIndex--;) {
67                 Node* node = block->at(nodeIndex);
68                 if (node->op() != Flush)
69                     continue;
70                 addFlushedLocalOp(node);
71             }
72         }
73         while (!m_flushedLocalOpWorklist.isEmpty()) {
74             Node* node = m_flushedLocalOpWorklist.takeLast();
75             ASSERT(m_flushedLocalOps.contains(node));
76             DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge);
77         }
78         
79         // Eliminate all duplicate or self-pointing Phi edges. This means that
80         // we transform:
81         //
82         // p: Phi(@n1, @n2, @n3)
83         //
84         // into:
85         //
86         // p: Phi(@x)
87         //
88         // if each @ni in {@n1, @n2, @n3} is either equal to @p to is equal
89         // to @x, for exactly one other @x. Additionally, trivial Phis (i.e.
90         // p: Phi(@x)) are forwarded, so that if have an edge to such @p, we
91         // replace it with @x. This loop does this for Phis only; later we do
92         // such forwarding for Phi references found in other nodes.
93         //
94         // See Aycock and Horspool in CC'00 for a better description of what
95         // we're doing here.
96         do {
97             m_changed = false;
98             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
99                 BasicBlock* block = m_graph.block(blockIndex);
100                 if (!block)
101                     continue;
102                 for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
103                     Node* phi = block->phis[phiIndex];
104                     if (phi->variableAccessData()->isCaptured())
105                         continue;
106                     forwardPhiChildren(phi);
107                     deduplicateChildren(phi);
108                 }
109             }
110         } while (m_changed);
111         
112         // For each basic block, for each local live at the head of that block,
113         // figure out what node we should be referring to instead of that local.
114         // If it turns out to be a non-trivial Phi, make sure that we create an
115         // SSA Phi and Upsilons in predecessor blocks. We reuse
116         // BasicBlock::variablesAtHead for tracking which nodes to refer to.
117         Operands<bool> nonTrivialPhis(OperandsLike, m_graph.block(0)->variablesAtHead);
118         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
119             BasicBlock* block = m_graph.block(blockIndex);
120             if (!block)
121                 continue;
122
123             nonTrivialPhis.fill(false);
124             for (unsigned i = block->phis.size(); i--;) {
125                 Node* phi = block->phis[i];
126                 if (!phi->children.justOneChild())
127                     nonTrivialPhis.operand(phi->local()) = true;
128             }
129                 
130             for (unsigned i = block->variablesAtHead.size(); i--;) {
131                 Node* node = block->variablesAtHead[i];
132                 if (!node)
133                     continue;
134                 
135                 if (verbose)
136                     dataLog("At block #", blockIndex, " for operand r", block->variablesAtHead.operandForIndex(i), " have node ", node, "\n");
137                 
138                 VariableAccessData* variable = node->variableAccessData();
139                 if (variable->isCaptured()) {
140                     // Poison this entry in variablesAtHead because we don't
141                     // want anyone to try to refer to it, if the variable is
142                     // captured.
143                     block->variablesAtHead[i] = 0;
144                     continue;
145                 }
146                 
147                 switch (node->op()) {
148                 case Phi:
149                 case SetArgument:
150                     break;
151                 case Flush:
152                 case GetLocal:
153                 case PhantomLocal:
154                     node = node->child1().node();
155                     break;
156                 default:
157                     RELEASE_ASSERT_NOT_REACHED();
158                 }
159                 RELEASE_ASSERT(node->op() == Phi || node->op() == SetArgument);
160                 
161                 bool isFlushed = m_flushedLocalOps.contains(node);
162                 
163                 if (node->op() == Phi) {
164                     if (!nonTrivialPhis.operand(node->local())) {
165                         Edge edge = node->children.justOneChild();
166                         ASSERT(edge);
167                         if (verbose)
168                             dataLog("    One child: ", edge, ", ", RawPointer(edge.node()), "\n");
169                         node = edge.node(); // It's something from a different basic block.
170                     } else {
171                         if (verbose)
172                             dataLog("    Non-trivial.\n");
173                         // It's a non-trivial Phi.
174                         FlushFormat format = variable->flushFormat();
175                         NodeFlags result = resultFor(format);
176                         UseKind useKind = useKindFor(format);
177                         
178                         node = m_insertionSet.insertNode(0, SpecNone, Phi, NodeOrigin());
179                         if (verbose)
180                             dataLog("    Inserted new node: ", node, "\n");
181                         node->mergeFlags(result);
182                         RELEASE_ASSERT((node->flags() & NodeResultMask) == result);
183                         
184                         for (unsigned j = block->predecessors.size(); j--;) {
185                             BasicBlock* predecessor = block->predecessors[j];
186                             predecessor->appendNonTerminal(
187                                 m_graph, SpecNone, Upsilon, predecessor->last()->origin,
188                                 OpInfo(node), Edge(predecessor->variablesAtTail[i], useKind));
189                         }
190                         
191                         if (isFlushed) {
192                             // Do nothing. For multiple reasons.
193                             
194                             // Reason #1: If the local is flushed then we don't need to bother
195                             // with a MovHint since every path to this point in the code will
196                             // have flushed the bytecode variable using a SetLocal and hence
197                             // the Availability::flushedAt() will agree, and that will be
198                             // sufficient for figuring out how to recover the variable's value.
199                             
200                             // Reason #2: If we had inserted a MovHint and the Phi function had
201                             // died (because the only user of the value was the "flush" - i.e.
202                             // some asynchronous runtime thingy) then the MovHint would turn
203                             // into a ZombieHint, which would fool us into thinking that the
204                             // variable is dead.
205                             
206                             // Reason #3: If we had inserted a MovHint then even if the Phi
207                             // stayed alive, we would still end up generating inefficient code
208                             // since we would be telling the OSR exit compiler to use some SSA
209                             // value for the bytecode variable rather than just telling it that
210                             // the value was already on the stack.
211                         } else {
212                             m_insertionSet.insertNode(
213                                 0, SpecNone, MovHint, NodeOrigin(),
214                                 OpInfo(variable->local().offset()), Edge(node));
215                         }
216                     }
217                 }
218                 
219                 block->variablesAtHead[i] = node;
220             }
221
222             m_insertionSet.execute(block);
223         }
224         
225         if (verbose) {
226             dataLog("Variables at head after SSA Phi insertion:\n");
227             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
228                 BasicBlock* block = m_graph.block(blockIndex);
229                 if (!block)
230                     continue;
231                 dataLog("    ", *block, ": ", block->variablesAtHead, "\n");
232             }
233         }
234         
235         // At this point variablesAtHead in each block refers to either:
236         //
237         // 1) A new SSA phi in the current block.
238         // 2) A SetArgument, which will soon get converted into a GetArgument.
239         // 3) An old CPS phi in a different block.
240         //
241         // We don't have to do anything for (1) and (2), but we do need to
242         // do a replacement for (3).
243         
244         // Clear all replacements, since other phases may have used them.
245         m_graph.clearReplacements();
246         
247         if (dumpGraph) {
248             dataLog("Graph just before identifying replacements:\n");
249             m_graph.dump();
250         }
251         
252         // For all of the old CPS Phis, figure out what they correspond to in SSA.
253         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
254             BasicBlock* block = m_graph.block(blockIndex);
255             if (!block)
256                 continue;
257             if (verbose)
258                 dataLog("Dealing with block #", blockIndex, "\n");
259             for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
260                 Node* phi = block->phis[phiIndex];
261                 if (verbose) {
262                     dataLog(
263                         "Considering ", phi, " (", RawPointer(phi), "), for r",
264                         phi->local(), ", and its replacement in ", *block, ", ",
265                         block->variablesAtHead.operand(phi->local()), "\n");
266                 }
267                 ASSERT(phi != block->variablesAtHead.operand(phi->local()));
268                 phi->misc.replacement = block->variablesAtHead.operand(phi->local());
269             }
270         }
271         
272         // Now make sure that all variablesAtHead in each block points to the
273         // canonical SSA value. Prior to this, variablesAtHead[local] may point to
274         // an old CPS Phi in a different block.
275         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
276             BasicBlock* block = m_graph.block(blockIndex);
277             if (!block)
278                 continue;
279             for (size_t i = block->variablesAtHead.size(); i--;) {
280                 Node* node = block->variablesAtHead[i];
281                 if (!node)
282                     continue;
283                 while (node->misc.replacement) {
284                     ASSERT(node != node->misc.replacement);
285                     node = node->misc.replacement;
286                 }
287                 block->variablesAtHead[i] = node;
288             }
289         }
290         
291         if (verbose) {
292             dataLog("Variables at head after convergence:\n");
293             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
294                 BasicBlock* block = m_graph.block(blockIndex);
295                 if (!block)
296                     continue;
297                 dataLog("    ", *block, ": ", block->variablesAtHead, "\n");
298             }
299         }
300         
301         // Convert operations over locals into operations over SSA nodes.
302         // - GetLocal over captured variables lose their phis.
303         // - GetLocal over uncaptured variables die and get replaced with references
304         //   to the node specified by variablesAtHead.
305         // - SetLocal gets NodeMustGenerate if it's flushed, or turns into a
306         //   Check otherwise.
307         // - Flush loses its children but remains, because we want to know when a
308         //   flushed SetLocal's value is no longer needed. This also makes it simpler
309         //   to reason about the format of a local, since we can just do a backwards
310         //   analysis (see FlushLivenessAnalysisPhase). As part of the backwards
311         //   analysis, we say that the type of a local can be either int32, double,
312         //   value, or dead.
313         // - PhantomLocal becomes Phantom, and its child is whatever is specified
314         //   by variablesAtHead.
315         // - SetArgument turns into GetArgument unless it's a captured variable.
316         // - Upsilons get their children fixed to refer to the true value of that local
317         //   at the end of the block. Prior to this loop, Upsilons will refer to
318         //   variableAtTail[operand], which may be any of Flush, PhantomLocal, GetLocal,
319         //   SetLocal, SetArgument, or Phi. We accomplish this by setting the
320         //   replacement pointers of all of those nodes to refer to either
321         //   variablesAtHead[operand], or the child of the SetLocal.
322         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
323             BasicBlock* block = m_graph.block(blockIndex);
324             if (!block)
325                 continue;
326             
327             for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
328                 block->phis[phiIndex]->misc.replacement =
329                     block->variablesAtHead.operand(block->phis[phiIndex]->local());
330             }
331             for (unsigned nodeIndex = block->size(); nodeIndex--;)
332                 ASSERT(!block->at(nodeIndex)->misc.replacement);
333             
334             for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
335                 Node* node = block->at(nodeIndex);
336                 
337                 m_graph.performSubstitution(node);
338                 
339                 switch (node->op()) {
340                 case SetLocal: {
341                     VariableAccessData* variable = node->variableAccessData();
342                     if (variable->isCaptured() || m_flushedLocalOps.contains(node))
343                         node->mergeFlags(NodeMustGenerate);
344                     else
345                         node->setOpAndDefaultFlags(Check);
346                     node->misc.replacement = node->child1().node(); // Only for Upsilons.
347                     break;
348                 }
349                     
350                 case GetLocal: {
351                     // It seems tempting to just do forwardPhi(GetLocal), except that we
352                     // could have created a new (SSA) Phi, and the GetLocal could still be
353                     // referring to an old (CPS) Phi. Uses variablesAtHead to tell us what
354                     // to refer to.
355                     node->children.reset();
356                     VariableAccessData* variable = node->variableAccessData();
357                     if (variable->isCaptured())
358                         break;
359                     node->convertToPhantom();
360                     node->misc.replacement = block->variablesAtHead.operand(variable->local());
361                     break;
362                 }
363                     
364                 case Flush: {
365                     node->children.reset();
366                     // This is only for Upsilons. An Upsilon will only refer to a Flush if
367                     // there were no SetLocals or GetLocals in the block.
368                     node->misc.replacement = block->variablesAtHead.operand(node->local());
369                     break;
370                 }
371                     
372                 case PhantomLocal: {
373                     VariableAccessData* variable = node->variableAccessData();
374                     if (variable->isCaptured())
375                         break;
376                     node->child1().setNode(block->variablesAtHead.operand(variable->local()));
377                     node->convertToPhantom();
378                     // This is only for Upsilons. An Upsilon will only refer to a
379                     // PhantomLocal if there were no SetLocals or GetLocals in the block.
380                     node->misc.replacement = block->variablesAtHead.operand(variable->local());
381                     break;
382                 }
383                     
384                 case SetArgument: {
385                     VariableAccessData* variable = node->variableAccessData();
386                     if (variable->isCaptured())
387                         break;
388                     node->setOpAndDefaultFlags(GetArgument);
389                     node->mergeFlags(resultFor(node->variableAccessData()->flushFormat()));
390                     break;
391                 }
392
393                 default:
394                     break;
395                 }
396             }
397         }
398         
399         // Free all CPS phis and reset variables vectors.
400         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
401             BasicBlock* block = m_graph.block(blockIndex);
402             if (!block)
403                 continue;
404             for (unsigned phiIndex = block->phis.size(); phiIndex--;)
405                 m_graph.m_allocator.free(block->phis[phiIndex]);
406             block->phis.clear();
407             block->variablesAtHead.clear();
408             block->variablesAtTail.clear();
409             block->valuesAtHead.clear();
410             block->valuesAtHead.clear();
411             block->ssa = adoptPtr(new BasicBlock::SSAData(block));
412         }
413         
414         m_graph.m_arguments.clear();
415         
416         m_graph.m_form = SSA;
417         return true;
418     }
419
420 private:
421     void forwardPhiChildren(Node* node)
422     {
423         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
424             Edge& edge = node->children.child(i);
425             if (!edge)
426                 break;
427             m_changed |= forwardPhiEdge(edge);
428         }
429     }
430     
431     Node* forwardPhi(Node* node)
432     {
433         for (;;) {
434             switch (node->op()) {
435             case Phi: {
436                 Edge edge = node->children.justOneChild();
437                 if (!edge)
438                     return node;
439                 node = edge.node();
440                 break;
441             }
442             case GetLocal:
443             case SetLocal:
444                 if (node->variableAccessData()->isCaptured())
445                     return node;
446                 node = node->child1().node();
447                 break;
448             default:
449                 return node;
450             }
451         }
452     }
453     
454     bool forwardPhiEdge(Edge& edge)
455     {
456         Node* newNode = forwardPhi(edge.node());
457         if (newNode == edge.node())
458             return false;
459         edge.setNode(newNode);
460         return true;
461     }
462     
463     void deduplicateChildren(Node* node)
464     {
465         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
466             Edge edge = node->children.child(i);
467             if (!edge)
468                 break;
469             if (edge == node) {
470                 node->children.removeEdge(i--);
471                 m_changed = true;
472                 continue;
473             }
474             for (unsigned j = i + 1; j < AdjacencyList::Size; ++j) {
475                 if (node->children.child(j) == edge) {
476                     node->children.removeEdge(j--);
477                     m_changed = true;
478                 }
479             }
480         }
481     }
482     
483     void addFlushedLocalOp(Node* node)
484     {
485         if (m_flushedLocalOps.contains(node))
486             return;
487         m_flushedLocalOps.add(node);
488         m_flushedLocalOpWorklist.append(node);
489     }
490
491     void addFlushedLocalEdge(Node*, Edge edge)
492     {
493         addFlushedLocalOp(edge.node());
494     }
495     
496     InsertionSet m_insertionSet;
497     HashSet<Node*> m_flushedLocalOps;
498     Vector<Node*> m_flushedLocalOpWorklist;
499     bool m_changed;
500 };
501
502 bool performSSAConversion(Graph& graph)
503 {
504     SamplingRegion samplingRegion("DFG SSA Conversion Phase");
505     return runPhase<SSAConversionPhase>(graph);
506 }
507
508 } } // namespace JSC::DFG
509
510 #endif // ENABLE(DFG_JIT)
511