Move back primary header includes next to config.h
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGDCEPhase.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 "DFGDCEPhase.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 DCEPhase : public Phase {
40 public:
41     DCEPhase(Graph& graph)
42         : Phase(graph, "dead code elimination")
43         , m_insertionSet(graph)
44     {
45     }
46     
47     bool run()
48     {
49         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
50         
51         // First reset the counts to 0 for all nodes.
52         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
53             BasicBlock* block = m_graph.block(blockIndex);
54             if (!block)
55                 continue;
56             for (unsigned indexInBlock = block->size(); indexInBlock--;)
57                 block->at(indexInBlock)->setRefCount(0);
58             for (unsigned phiIndex = block->phis.size(); phiIndex--;)
59                 block->phis[phiIndex]->setRefCount(0);
60         }
61     
62         // Now find the roots:
63         // - Nodes that are must-generate.
64         // - Nodes that are reachable from type checks.
65         // Set their ref counts to 1 and put them on the worklist.
66         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
67             BasicBlock* block = m_graph.block(blockIndex);
68             if (!block)
69                 continue;
70             for (unsigned indexInBlock = block->size(); indexInBlock--;) {
71                 Node* node = block->at(indexInBlock);
72                 DFG_NODE_DO_TO_CHILDREN(m_graph, node, findTypeCheckRoot);
73                 if (!(node->flags() & NodeMustGenerate))
74                     continue;
75                 if (!node->postfixRef())
76                     m_worklist.append(node);
77             }
78         }
79         
80         while (!m_worklist.isEmpty()) {
81             while (!m_worklist.isEmpty()) {
82                 Node* node = m_worklist.last();
83                 m_worklist.removeLast();
84                 ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
85                 DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
86             }
87             
88             if (m_graph.m_form == SSA) {
89                 // Find Phi->Upsilon edges, which are represented as meta-data in the
90                 // Upsilon.
91                 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
92                     BasicBlock* block = m_graph.block(blockIndex);
93                     if (!block)
94                         continue;
95                     for (unsigned nodeIndex = block->size(); nodeIndex--;) {
96                         Node* node = block->at(nodeIndex);
97                         if (node->op() != Upsilon)
98                             continue;
99                         if (node->shouldGenerate())
100                             continue;
101                         if (node->phi()->shouldGenerate())
102                             countNode(node);
103                     }
104                 }
105             }
106         }
107         
108         if (m_graph.m_form == SSA) {
109             // Need to process the graph in reverse DFS order, so that we get to the uses
110             // of a node before we get to the node itself.
111             Vector<BasicBlock*> depthFirst;
112             m_graph.getBlocksInDepthFirstOrder(depthFirst);
113             for (unsigned i = depthFirst.size(); i--;)
114                 fixupBlock(depthFirst[i]);
115         } else {
116             RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
117             
118             for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
119                 fixupBlock(m_graph.block(blockIndex));
120             
121             cleanVariables(m_graph.m_arguments);
122         }
123         
124         m_graph.m_refCountState = ExactRefCount;
125         
126         return true;
127     }
128
129 private:
130     void findTypeCheckRoot(Node*, Edge edge)
131     {
132         // We may have an "unproved" untyped use for code that is unreachable. The CFA
133         // will just not have gotten around to it.
134         if (edge.willNotHaveCheck())
135             return;
136         if (!edge->postfixRef())
137             m_worklist.append(edge.node());
138     }
139     
140     void countNode(Node* node)
141     {
142         if (node->postfixRef())
143             return;
144         m_worklist.append(node);
145     }
146     
147     void countEdge(Node*, Edge edge)
148     {
149         // Don't count edges that are already counted for their type checks.
150         if (edge.willHaveCheck())
151             return;
152         countNode(edge.node());
153     }
154     
155     void fixupBlock(BasicBlock* block)
156     {
157         if (!block)
158             return;
159         
160         switch (m_graph.m_form) {
161         case SSA:
162             break;
163             
164         case ThreadedCPS: {
165             // Clean up variable links for the block. We need to do this before the actual DCE
166             // because we need to see GetLocals, so we can bypass them in situations where the
167             // vars-at-tail point to a GetLocal, the GetLocal is dead, but the Phi it points
168             // to is alive.
169             
170             for (unsigned phiIndex = 0; phiIndex < block->phis.size(); ++phiIndex) {
171                 if (!block->phis[phiIndex]->shouldGenerate()) {
172                     // FIXME: We could actually free nodes here. Except that it probably
173                     // doesn't matter, since we don't add any nodes after this phase.
174                     // https://bugs.webkit.org/show_bug.cgi?id=126239
175                     block->phis[phiIndex--] = block->phis.last();
176                     block->phis.removeLast();
177                 }
178             }
179             
180             cleanVariables(block->variablesAtHead);
181             cleanVariables(block->variablesAtTail);
182             break;
183         }
184             
185         default:
186             RELEASE_ASSERT_NOT_REACHED();
187             return;
188         }
189
190         for (unsigned indexInBlock = block->size(); indexInBlock--;) {
191             Node* node = block->at(indexInBlock);
192             if (node->shouldGenerate())
193                 continue;
194                 
195             switch (node->op()) {
196             case MovHint: {
197                 ASSERT(node->child1().useKind() == UntypedUse);
198                 if (!node->child1()->shouldGenerate()) {
199                     node->setOpAndDefaultFlags(ZombieHint);
200                     node->child1() = Edge();
201                     break;
202                 }
203                 node->setOpAndDefaultFlags(MovHint);
204                 break;
205             }
206                 
207             case ZombieHint: {
208                 // Currently we assume that DCE runs only once.
209                 RELEASE_ASSERT_NOT_REACHED();
210                 break;
211             }
212             
213             default: {
214                 if (node->flags() & NodeHasVarArgs) {
215                     for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
216                         Edge edge = m_graph.m_varArgChildren[childIdx];
217
218                         if (!edge || edge.willNotHaveCheck())
219                             continue;
220
221                         m_insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->origin, edge);
222                     }
223
224                     node->convertToPhantomUnchecked();
225                     node->children.reset();
226                     node->setRefCount(1);
227                     break;
228                 }
229
230                 node->convertToPhantom();
231                 eliminateIrrelevantPhantomChildren(node);
232                 node->setRefCount(1);
233                 break;
234             } }
235         }
236
237         m_insertionSet.execute(block);
238     }
239     
240     void eliminateIrrelevantPhantomChildren(Node* node)
241     {
242         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
243             Edge edge = node->children.child(i);
244             if (!edge)
245                 continue;
246             if (edge.willNotHaveCheck())
247                 node->children.removeEdge(i--);
248         }
249     }
250     
251     template<typename VariablesVectorType>
252     void cleanVariables(VariablesVectorType& variables)
253     {
254         for (unsigned i = variables.size(); i--;) {
255             Node* node = variables[i];
256             if (!node)
257                 continue;
258             if (node->op() != Phantom && node->shouldGenerate())
259                 continue;
260             if (node->op() == GetLocal) {
261                 node = node->child1().node();
262                 ASSERT(node->op() == Phi || node->op() == SetArgument);
263                 if (node->shouldGenerate()) {
264                     variables[i] = node;
265                     continue;
266                 }
267             }
268             variables[i] = 0;
269         }
270     }
271     
272     Vector<Node*, 128> m_worklist;
273     InsertionSet m_insertionSet;
274 };
275
276 bool performDCE(Graph& graph)
277 {
278     SamplingRegion samplingRegion("DFG DCE Phase");
279     return runPhase<DCEPhase>(graph);
280 }
281
282 } } // namespace JSC::DFG
283
284 #endif // ENABLE(DFG_JIT)
285