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