MovHint should be a strong use
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGDCEPhase.cpp
1 /*
2  * Copyright (C) 2013-2015 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         m_graph.computeRefCounts();
52         
53         if (m_graph.m_form == SSA) {
54             for (BasicBlock* block : m_graph.blocksInPreOrder())
55                 fixupBlock(block);
56             
57             // This is like cleanVariables, but has a much simpler approach to GetLocal.
58             for (unsigned i = m_graph.m_arguments.size(); i--;) {
59                 Node* node = m_graph.m_arguments[i];
60                 if (!node)
61                     continue;
62                 if (node->op() != Phantom && node->op() != Check && node->shouldGenerate())
63                     continue;
64                 m_graph.m_arguments[i] = nullptr;
65             }
66         } else {
67             RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
68             
69             for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
70                 fixupBlock(m_graph.block(blockIndex));
71             cleanVariables(m_graph.m_arguments);
72         }
73         
74         // Just do a basic HardPhantom/Phantom/Check clean-up.
75         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
76             BasicBlock* block = m_graph.block(blockIndex);
77             if (!block)
78                 continue;
79             unsigned sourceIndex = 0;
80             unsigned targetIndex = 0;
81             while (sourceIndex < block->size()) {
82                 Node* node = block->at(sourceIndex++);
83                 switch (node->op()) {
84                 case Check:
85                 case HardPhantom:
86                 case Phantom:
87                     if (node->children.isEmpty())
88                         continue;
89                     break;
90                 default:
91                     break;
92                 }
93                 block->at(targetIndex++) = node;
94             }
95             block->resize(targetIndex);
96         }
97         
98         m_graph.m_refCountState = ExactRefCount;
99         
100         return true;
101     }
102
103 private:
104     void fixupBlock(BasicBlock* block)
105     {
106         if (!block)
107             return;
108         
109         switch (m_graph.m_form) {
110         case SSA:
111             break;
112             
113         case ThreadedCPS: {
114             // Clean up variable links for the block. We need to do this before the actual DCE
115             // because we need to see GetLocals, so we can bypass them in situations where the
116             // vars-at-tail point to a GetLocal, the GetLocal is dead, but the Phi it points
117             // to is alive.
118             
119             for (unsigned phiIndex = 0; phiIndex < block->phis.size(); ++phiIndex) {
120                 if (!block->phis[phiIndex]->shouldGenerate()) {
121                     // FIXME: We could actually free nodes here. Except that it probably
122                     // doesn't matter, since we don't add any nodes after this phase.
123                     // https://bugs.webkit.org/show_bug.cgi?id=126239
124                     block->phis[phiIndex--] = block->phis.last();
125                     block->phis.removeLast();
126                 }
127             }
128             
129             cleanVariables(block->variablesAtHead);
130             cleanVariables(block->variablesAtTail);
131             break;
132         }
133             
134         default:
135             RELEASE_ASSERT_NOT_REACHED();
136             return;
137         }
138
139         // This has to be a forward loop because we are using the insertion set.
140         for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
141             Node* node = block->at(indexInBlock);
142             if (node->shouldGenerate())
143                 continue;
144                 
145             switch (node->op()) {
146             case MovHint:
147             case ZombieHint:
148                 // These are not killable. (They once were.)
149                 RELEASE_ASSERT_NOT_REACHED();
150                 
151             default: {
152                 if (node->flags() & NodeHasVarArgs) {
153                     for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
154                         Edge edge = m_graph.m_varArgChildren[childIdx];
155
156                         if (!edge || edge.isProved() || edge.willNotHaveCheck())
157                             continue;
158
159                         m_insertionSet.insertNode(indexInBlock, SpecNone, Check, node->origin, edge);
160                     }
161
162                     node->convertToPhantom();
163                     node->children.reset();
164                     node->setRefCount(1);
165                     break;
166                 }
167
168                 node->convertToCheck();
169                 for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
170                     Edge edge = node->children.child(i);
171                     if (!edge)
172                         continue;
173                     if (edge.isProved() || edge.willNotHaveCheck())
174                         node->children.removeEdge(i--);
175                 }
176                 node->setRefCount(1);
177                 break;
178             } }
179         }
180
181         m_insertionSet.execute(block);
182     }
183     
184     template<typename VariablesVectorType>
185     void cleanVariables(VariablesVectorType& variables)
186     {
187         for (unsigned i = variables.size(); i--;) {
188             Node* node = variables[i];
189             if (!node)
190                 continue;
191             if (node->op() != Phantom && node->op() != Check && node->shouldGenerate())
192                 continue;
193             if (node->op() == GetLocal) {
194                 node = node->child1().node();
195                 
196                 ASSERT(node->op() == Phi || node->op() == SetArgument);
197                 
198                 if (node->shouldGenerate()) {
199                     variables[i] = node;
200                     continue;
201                 }
202             }
203             variables[i] = 0;
204         }
205     }
206     
207     InsertionSet m_insertionSet;
208 };
209
210 bool performDCE(Graph& graph)
211 {
212     SamplingRegion samplingRegion("DFG DCE Phase");
213     return runPhase<DCEPhase>(graph);
214 }
215
216 } } // namespace JSC::DFG
217
218 #endif // ENABLE(DFG_JIT)
219