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