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 "Operations.h"
36
37namespace JSC { namespace DFG {
38
39class DCEPhase : public Phase {
40public:
41    DCEPhase(Graph& graph)
42        : Phase(graph, "dead code elimination")
43    {
44    }
45
46    bool run()
47    {
48        // First reset the counts to 0 for all nodes.
49        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
50            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
51            if (!block)
52                continue;
53            for (unsigned indexInBlock = block->size(); indexInBlock--;)
54                block->at(indexInBlock)->setRefCount(0);
55            for (unsigned phiIndex = block->phis.size(); phiIndex--;)
56                block->phis[phiIndex]->setRefCount(0);
57        }
58
59        // Now find the roots:
60        // - Nodes that are must-generate.
61        // - Nodes that are reachable from type checks.
62        // Set their ref counts to 1 and put them on the worklist.
63        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
64            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
65            if (!block)
66                continue;
67            for (unsigned indexInBlock = block->size(); indexInBlock--;) {
68                Node* node = block->at(indexInBlock);
69                DFG_NODE_DO_TO_CHILDREN(m_graph, node, findTypeCheckRoot);
70                if (!(node->flags() & NodeMustGenerate))
71                    continue;
72                if (!node->postfixRef())
73                    m_worklist.append(node);
74            }
75        }
76
77        while (!m_worklist.isEmpty()) {
78            Node* node = m_worklist.last();
79            m_worklist.removeLast();
80            ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
81            DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
82        }
83
84        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
85            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
86            if (!block)
87                continue;
88
89            InsertionSet insertionSet(m_graph);
90
91            for (unsigned indexInBlock = block->size(); indexInBlock--;) {
92                Node* node = block->at(indexInBlock);
93                if (node->shouldGenerate())
94                    continue;
95
96                switch (node->op()) {
97                case SetLocal: {
98                    if (node->child1().isProved() || node->child1().useKind() == UntypedUse) {
99                        // Consider the possibility that UInt32ToNumber is dead but its
100                        // child isn't; if so then we should MovHint the child.
101                        if (!node->child1()->shouldGenerate()
102                            && node->child1()->op() == UInt32ToNumber)
103                            node->child1() = node->child1()->child1();
104
105                        if (!node->child1()->shouldGenerate()) {
106                            node->setOpAndDefaultFlags(ZombieHint);
107                            node->child1() = Edge();
108                            break;
109                        }
110                        node->setOpAndDefaultFlags(MovHint);
111                        break;
112                    }
113                    node->setOpAndDefaultFlags(MovHintAndCheck);
114                    node->setRefCount(1);
115                    break;
116                }
117
118                case GetLocal:
119                case SetArgument: {
120                    // Leave them as not shouldGenerate.
121                    break;
122                }
123
124                default: {
125                    if (node->flags() & NodeHasVarArgs) {
126                        for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
127                            Edge edge = m_graph.m_varArgChildren[childIdx];
128
129                            if (!edge || edge.isProved() || edge.useKind() == UntypedUse)
130                                continue;
131
132                            insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->codeOrigin, edge);
133                        }
134
135                        node->convertToPhantomUnchecked();
136                        node->children.reset();
137                        node->setRefCount(1);
138                        break;
139                    }
140
141                    node->convertToPhantom();
142                    eliminateIrrelevantPhantomChildren(node);
143                    node->setRefCount(1);
144                    break;
145                } }
146            }
147
148            insertionSet.execute(block);
149        }
150
151        m_graph.m_refCountState = ExactRefCount;
152
153        return true;
154    }
155
156private:
157    void findTypeCheckRoot(Node*, Edge edge)
158    {
159        // We may have an "unproved" untyped use for code that is unreachable. The CFA
160        // will just not have gotten around to it.
161        if (edge.isProved() || edge.useKind() == UntypedUse)
162            return;
163        if (!edge->postfixRef())
164            m_worklist.append(edge.node());
165    }
166
167    void countEdge(Node*, Edge edge)
168    {
169        // Don't count edges that are already counted for their type checks.
170        if (!(edge.isProved() || edge.useKind() == UntypedUse))
171            return;
172
173        if (edge->postfixRef())
174            return;
175        m_worklist.append(edge.node());
176    }
177
178    void eliminateIrrelevantPhantomChildren(Node* node)
179    {
180        for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
181            Edge edge = node->children.child(i);
182            if (!edge)
183                continue;
184            if (edge.isProved() || edge.useKind() == UntypedUse)
185                node->children.removeEdge(i--);
186        }
187    }
188
189    Vector<Node*, 128> m_worklist;
190};
191
192bool performDCE(Graph& graph)
193{
194    SamplingRegion samplingRegion("DFG DCE Phase");
195    return runPhase<DCEPhase>(graph);
196}
197
198} } // namespace JSC::DFG
199
200#endif // ENABLE(DFG_JIT)
201
202