Unreviewed, rolling out r145299.
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGCPSRethreadingPhase.cpp
1 /*
2  * Copyright (C) 2013 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 "DFGCPSRethreadingPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGBasicBlockInlines.h"
32 #include "DFGGraph.h"
33 #include "DFGPhase.h"
34 #include "Operations.h"
35
36 namespace JSC { namespace DFG {
37
38 class CPSRethreadingPhase : public Phase {
39 public:
40     CPSRethreadingPhase(Graph& graph)
41         : Phase(graph, "CPS rethreading")
42     {
43     }
44     
45     bool run()
46     {
47         if (m_graph.m_form == ThreadedCPS)
48             return false;
49         
50         freeUnnecessaryNodes();
51         canonicalizeLocalsInBlocks();
52         propagatePhis<LocalOperand>();
53         propagatePhis<ArgumentOperand>();
54         
55         m_graph.m_form = ThreadedCPS;
56         return true;
57     }
58
59 private:
60     
61     void freeUnnecessaryNodes()
62     {
63         SamplingRegion samplingRegion("DFG CPS Rethreading: freeUnnecessaryNodes");
64         
65         for (BlockIndex blockIndex = m_graph.m_blocks.size(); blockIndex--;) {
66             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
67             if (!block)
68                 continue;
69             ASSERT(block->isReachable);
70             
71             unsigned fromIndex = 0;
72             unsigned toIndex = 0;
73             while (fromIndex < block->size()) {
74                 Node* node = block->at(fromIndex++);
75                 switch (node->op()) {
76                 case GetLocal:
77                 case Flush:
78                 case PhantomLocal:
79                     node->children.setChild1(Edge());
80                     break;
81                 case Phantom:
82                     if (!node->child1())
83                         continue;
84                     switch (node->child1()->op()) {
85                     case Phi:
86                     case SetArgument:
87                     case SetLocal:
88                         node->convertToPhantomLocal();
89                         break;
90                     default:
91                         ASSERT(node->child1()->hasResult());
92                         break;
93                     }
94                     break;
95                 case Nop:
96                     continue;
97                 default:
98                     break;
99                 }
100                 node->replacement = 0; // Reset the replacement since the next phase will use it.
101                 block->at(toIndex++) = node;
102             }
103             block->resize(toIndex);
104             
105             for (unsigned phiIndex = block->phis.size(); phiIndex--;)
106                 m_graph.m_allocator.free(block->phis[phiIndex]);
107             block->phis.resize(0);
108         }
109     }
110     
111     template<OperandKind operandKind>
112     void clearVariablesAtHeadAndTail()
113     {
114         ASSERT(
115             m_block->variablesAtHead.sizeFor<operandKind>()
116             == m_block->variablesAtTail.sizeFor<operandKind>());
117         
118         for (unsigned i = m_block->variablesAtHead.sizeFor<operandKind>(); i--;) {
119             m_block->variablesAtHead.atFor<operandKind>(i) = 0;
120             m_block->variablesAtTail.atFor<operandKind>(i) = 0;
121         }
122     }
123     
124     ALWAYS_INLINE Node* addPhiSilently(BasicBlock* block, const CodeOrigin& codeOrigin, VariableAccessData* variable)
125     {
126         Node* result = m_graph.addNode(SpecNone, Phi, codeOrigin, OpInfo(variable));
127         block->phis.append(result);
128         return result;
129     }
130     
131     template<OperandKind operandKind>
132     ALWAYS_INLINE Node* addPhi(BasicBlock* block, const CodeOrigin& codeOrigin, VariableAccessData* variable, size_t index)
133     {
134         Node* result = addPhiSilently(block, codeOrigin, variable);
135         phiStackFor<operandKind>().append(PhiStackEntry(block, index, result));
136         return result;
137     }
138     
139     template<OperandKind operandKind>
140     ALWAYS_INLINE Node* addPhi(const CodeOrigin& codeOrigin, VariableAccessData* variable, size_t index)
141     {
142         return addPhi<operandKind>(m_block, codeOrigin, variable, index);
143     }
144     
145     template<OperandKind operandKind>
146     void canonicalizeGetLocalFor(Node* node, VariableAccessData* variable, size_t idx)
147     {
148         ASSERT(!node->child1());
149         
150         if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
151             ASSERT(otherNode->variableAccessData() == variable);
152             
153             switch (otherNode->op()) {
154             case Flush:
155             case PhantomLocal:
156                 otherNode = otherNode->child1().node();
157                 if (otherNode->op() == Phi) {
158                     // We need to have a GetLocal, so this might as well be the one.
159                     node->children.setChild1(Edge(otherNode));
160                     m_block->variablesAtTail.atFor<operandKind>(idx) = node;
161                     return;
162                 }
163                 ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
164                 break;
165             default:
166                 break;
167             }
168             
169             ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument || otherNode->op() == GetLocal);
170             ASSERT(otherNode->variableAccessData() == variable);
171             
172             if (otherNode->op() == SetArgument) {
173                 node->children.setChild1(Edge(otherNode));
174                 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
175                 return;
176             }
177             
178             if (variable->isCaptured()) {
179                 if (otherNode->op() == GetLocal)
180                     otherNode = otherNode->child1().node();
181                 else
182                     ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgument);
183                 
184                 ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
185                 
186                 // Keep this GetLocal but link it to the prior ones.
187                 node->children.setChild1(Edge(otherNode));
188                 m_block->variablesAtTail.atFor<operandKind>(idx) = node;
189                 return;
190             }
191             
192             if (otherNode->op() == GetLocal) {
193                 // Replace all references to this GetLocal with otherNode.
194                 node->replacement = otherNode;
195                 return;
196             }
197             
198             ASSERT(otherNode->op() == SetLocal);
199             node->replacement = otherNode->child1().node();
200             return;
201         }
202         
203         Node* phi = addPhi<operandKind>(node->codeOrigin, variable, idx);
204         node->children.setChild1(Edge(phi));
205         m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
206         m_block->variablesAtTail.atFor<operandKind>(idx) = node;
207     }
208     
209     void canonicalizeGetLocal(Node* node)
210     {
211         VariableAccessData* variable = node->variableAccessData();
212         if (operandIsArgument(variable->local()))
213             canonicalizeGetLocalFor<ArgumentOperand>(node, variable, operandToArgument(variable->local()));
214         else
215             canonicalizeGetLocalFor<LocalOperand>(node, variable, variable->local());
216     }
217     
218     void canonicalizeSetLocal(Node* node)
219     {
220         m_block->variablesAtTail.setOperand(node->local(), node);
221     }
222     
223     template<NodeType nodeType, OperandKind operandKind>
224     void canonicalizeFlushOrPhantomLocalFor(Node* node, VariableAccessData* variable, size_t idx)
225     {
226         ASSERT(!node->child1());
227         
228         if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
229             ASSERT(otherNode->variableAccessData() == variable);
230             
231             switch (otherNode->op()) {
232             case Flush:
233             case PhantomLocal:
234             case GetLocal:
235                 otherNode = otherNode->child1().node();
236                 break;
237             default:
238                 break;
239             }
240             
241             ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgument);
242             
243             if (nodeType == PhantomLocal && otherNode->op() == SetLocal) {
244                 // PhantomLocal(SetLocal) doesn't make sense. PhantomLocal means: at this
245                 // point I know I would have been interested in the value of this variable
246                 // for the purpose of OSR. PhantomLocal(SetLocal) means: at this point I
247                 // know that I would have read the value written by that SetLocal. This is
248                 // redundant and inefficient, since really it just means that we want to
249                 // be keeping the operand to the SetLocal alive. The SetLocal may die, and
250                 // we'll be fine because OSR tracks dead SetLocals.
251                 
252                 // So we turn this into a Phantom on the child of the SetLocal.
253                 
254                 node->convertToPhantom();
255                 node->children.setChild1(otherNode->child1());
256                 return;
257             }
258             
259             // There is nothing wrong with having redundant Flush's. It just needs to
260             // be linked appropriately. Note that if there had already been a previous
261             // use at tail then we don't override it. It's fine for variablesAtTail to
262             // omit Flushes and PhantomLocals. On the other hand, having it refer to a
263             // Flush or a PhantomLocal if just before it the last use was a GetLocal would
264             // seriously confuse the CFA.
265             node->children.setChild1(Edge(otherNode));
266             return;
267         }
268         
269         node->children.setChild1(Edge(addPhi<operandKind>(node->codeOrigin, variable, idx)));
270         m_block->variablesAtHead.atFor<operandKind>(idx) = node;
271         m_block->variablesAtTail.atFor<operandKind>(idx) = node;
272     }
273
274     template<NodeType nodeType>
275     void canonicalizeFlushOrPhantomLocal(Node* node)
276     {
277         VariableAccessData* variable = node->variableAccessData();
278         if (operandIsArgument(variable->local()))
279             canonicalizeFlushOrPhantomLocalFor<nodeType, ArgumentOperand>(node, variable, operandToArgument(variable->local()));
280         else
281             canonicalizeFlushOrPhantomLocalFor<nodeType, LocalOperand>(node, variable, variable->local());
282     }
283     
284     void canonicalizeSetArgument(Node* node)
285     {
286         int local = node->local();
287         ASSERT(operandIsArgument(local));
288         int argument = operandToArgument(local);
289         m_block->variablesAtHead.setArgumentFirstTime(argument, node);
290         m_block->variablesAtTail.setArgumentFirstTime(argument, node);
291     }
292     
293     void canonicalizeLocalsInBlock()
294     {
295         if (!m_block)
296             return;
297         ASSERT(m_block->isReachable);
298         
299         clearVariablesAtHeadAndTail<ArgumentOperand>();
300         clearVariablesAtHeadAndTail<LocalOperand>();
301         
302         // Assumes that all phi references have been removed. Assumes that things that
303         // should be live have a non-zero ref count, but doesn't assume that the ref
304         // counts are correct beyond that (more formally !!logicalRefCount == !!actualRefCount
305         // but not logicalRefCount == actualRefCount). Assumes that it can break ref
306         // counts.
307         
308         for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
309             Node* node = m_block->at(nodeIndex);
310             
311             m_graph.performSubstitution(node);
312             
313             // The rules for threaded CPS form:
314             // 
315             // Head variable: describes what is live at the head of the basic block.
316             // Head variable links may refer to Flush, PhantomLocal, Phi, or SetArgument.
317             // SetArgument may only appear in the root block.
318             //
319             // Tail variable: the last thing that happened to the variable in the block.
320             // It may be a Flush, PhantomLocal, GetLocal, SetLocal, or SetArgument.
321             // SetArgument may only appear in the root block. Note that if there ever
322             // was a GetLocal to the variable, and it was followed by PhantomLocals and
323             // Flushes but not SetLocals, then the tail variable will be the GetLocal.
324             // This reflects the fact that you only care that the tail variable is a
325             // Flush or PhantomLocal if nothing else interesting happened.
326             //
327             // Child of GetLocal: the operation that the GetLocal keeps alive. For
328             // uncaptured locals, it may be a Phi from the current block. For arguments,
329             // it may be a SetArgument. For captured locals and arguments it may also be
330             // a SetLocal.
331             //
332             // Child of SetLocal: must be a value producing node.
333             //
334             // Child of Flush: it may be a Phi from the current block or a SetLocal. For
335             // arguments it may also be a SetArgument.
336             //
337             // Child of PhantomLocal: it may be a Phi from the current block. For
338             // arguments it may also be a SetArgument.
339             //
340             // Children of Phi: other Phis in the same basic block, or any of the
341             // following from predecessor blocks: SetLocal, Phi, or SetArgument. These
342             // are computed by looking at the tail variables of the predecessor  blocks
343             // and either using it directly (if it's a SetLocal, Phi, or SetArgument) or
344             // loading that nodes child (if it's a GetLocal, PhanomLocal, or Flush - all
345             // of these will have children that are SetLocal, Phi, or SetArgument).
346             
347             switch (node->op()) {
348             case GetLocal:
349                 canonicalizeGetLocal(node);
350                 break;
351                 
352             case SetLocal:
353                 canonicalizeSetLocal(node);
354                 break;
355                 
356             case Flush:
357                 canonicalizeFlushOrPhantomLocal<Flush>(node);
358                 break;
359                 
360             case PhantomLocal:
361                 canonicalizeFlushOrPhantomLocal<PhantomLocal>(node);
362                 break;
363                 
364             case SetArgument:
365                 canonicalizeSetArgument(node);
366                 break;
367                 
368             default:
369                 break;
370             }
371         }
372     }
373     
374     void canonicalizeLocalsInBlocks()
375     {
376         SamplingRegion samplingRegion("DFG CPS Rethreading: canonicalizeLocalsInBlocks");
377         
378         for (m_blockIndex = m_graph.m_blocks.size(); m_blockIndex--;) {
379             m_block = m_graph.m_blocks[m_blockIndex].get();
380             canonicalizeLocalsInBlock();
381         }
382     }
383     
384     template<OperandKind operandKind>
385     void propagatePhis()
386     {
387         Vector<PhiStackEntry, 128>& phiStack = operandKind == ArgumentOperand ? m_argumentPhiStack : m_localPhiStack;
388         
389         SamplingRegion samplingRegion("DFG CPS Rethreading: propagatePhis");
390         
391         // Ensure that attempts to use this fail instantly.
392         m_block = 0;
393         m_blockIndex = NoBlock;
394         
395         while (!phiStack.isEmpty()) {
396             PhiStackEntry entry = phiStack.last();
397             phiStack.removeLast();
398             
399             BasicBlock* block = entry.m_block;
400             PredecessorList& predecessors = block->m_predecessors;
401             Node* currentPhi = entry.m_phi;
402             VariableAccessData* variable = currentPhi->variableAccessData();
403             size_t index = entry.m_index;
404             
405             for (size_t i = predecessors.size(); i--;) {
406                 BasicBlock* predecessorBlock = m_graph.m_blocks[predecessors[i]].get();
407                 
408                 Node* variableInPrevious = predecessorBlock->variablesAtTail.atFor<operandKind>(index);
409                 if (!variableInPrevious) {
410                     variableInPrevious = addPhi<operandKind>(predecessorBlock, currentPhi->codeOrigin, variable, index);
411                     predecessorBlock->variablesAtTail.atFor<operandKind>(index) = variableInPrevious;
412                     predecessorBlock->variablesAtHead.atFor<operandKind>(index) = variableInPrevious;
413                 } else {
414                     switch (variableInPrevious->op()) {
415                     case GetLocal:
416                     case PhantomLocal:
417                     case Flush:
418                         ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
419                         variableInPrevious = variableInPrevious->child1().node();
420                         break;
421                     default:
422                         break;
423                     }
424                 }
425                 
426                 ASSERT(
427                     variableInPrevious->op() == SetLocal
428                     || variableInPrevious->op() == Phi
429                     || variableInPrevious->op() == SetArgument);
430           
431                 if (!currentPhi->child1()) {
432                     currentPhi->children.setChild1(Edge(variableInPrevious));
433                     continue;
434                 }
435                 if (!currentPhi->child2()) {
436                     currentPhi->children.setChild2(Edge(variableInPrevious));
437                     continue;
438                 }
439                 if (!currentPhi->child3()) {
440                     currentPhi->children.setChild3(Edge(variableInPrevious));
441                     continue;
442                 }
443                 
444                 Node* newPhi = addPhiSilently(block, currentPhi->codeOrigin, variable);
445                 newPhi->children = currentPhi->children;
446                 currentPhi->children.initialize(newPhi, variableInPrevious, 0);
447             }
448         }
449     }
450     
451     struct PhiStackEntry {
452         PhiStackEntry(BasicBlock* block, size_t index, Node* phi)
453             : m_block(block)
454             , m_index(index)
455             , m_phi(phi)
456         {
457         }
458         
459         BasicBlock* m_block;
460         size_t m_index;
461         Node* m_phi;
462     };
463     
464     template<OperandKind operandKind>
465     Vector<PhiStackEntry, 128>& phiStackFor()
466     {
467         if (operandKind == ArgumentOperand)
468             return m_argumentPhiStack;
469         return m_localPhiStack;
470     }
471     
472     BlockIndex m_blockIndex;
473     BasicBlock* m_block;
474     Vector<PhiStackEntry, 128> m_argumentPhiStack;
475     Vector<PhiStackEntry, 128> m_localPhiStack;
476 };
477
478 bool performCPSRethreading(Graph& graph)
479 {
480     SamplingRegion samplingRegion("DFG CPS Rethreading Phase");
481     return runPhase<CPSRethreadingPhase>(graph);
482 }
483
484 } } // namespace JSC::DFG
485
486 #endif // ENABLE(DFG_JIT)
487