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
37namespace JSC { namespace DFG {
38
39class DCEPhase : public Phase {
40public:
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 for (BasicBlock* block : m_graph.blocksInPreOrder())
54 fixupBlock(block);
55
56 for (auto& argumentsVector : m_graph.m_rootToArguments.values())
57 cleanVariables(argumentsVector);
58
59 // Just do a basic Phantom/Check clean-up.
60 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
61 BasicBlock* block = m_graph.block(blockIndex);
62 if (!block)
63 continue;
64 unsigned sourceIndex = 0;
65 unsigned targetIndex = 0;
66 while (sourceIndex < block->size()) {
67 Node* node = block->at(sourceIndex++);
68 switch (node->op()) {
69 case Check:
70 case Phantom:
71 if (node->children.isEmpty())
72 continue;
73 break;
74 case CheckVarargs: {
75 bool isEmpty = true;
76 m_graph.doToChildren(node, [&] (Edge edge) {
77 isEmpty &= !edge;
78 });
79 if (isEmpty)
80 continue;
81 break;
82 }
83 default:
84 break;
85 }
86 block->at(targetIndex++) = node;
87 }
88 block->resize(targetIndex);
89 }
90
91 m_graph.m_refCountState = ExactRefCount;
92
93 return true;
94 }
95
96private:
97 void fixupBlock(BasicBlock* block)
98 {
99 if (!block)
100 return;
101
102 if (m_graph.m_form == ThreadedCPS) {
103 for (unsigned phiIndex = 0; phiIndex < block->phis.size(); ++phiIndex) {
104 Node* phi = block->phis[phiIndex];
105 if (!phi->shouldGenerate()) {
106 m_graph.deleteNode(phi);
107 block->phis[phiIndex--] = block->phis.last();
108 block->phis.removeLast();
109 }
110 }
111
112 cleanVariables(block->variablesAtHead);
113 cleanVariables(block->variablesAtTail);
114 }
115
116 // This has to be a forward loop because we are using the insertion set.
117 for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
118 Node* node = block->at(indexInBlock);
119 if (node->shouldGenerate())
120 continue;
121
122 if (node->flags() & NodeHasVarArgs) {
123 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
124 Edge edge = m_graph.m_varArgChildren[childIdx];
125
126 if (!edge || edge.willNotHaveCheck())
127 continue;
128
129 m_insertionSet.insertNode(indexInBlock, SpecNone, Check, node->origin, edge);
130 }
131
132 node->setOpAndDefaultFlags(Check);
133 node->children.reset();
134 node->setRefCount(1);
135 continue;
136 }
137
138 node->remove(m_graph);
139 node->setRefCount(1);
140 }
141
142 m_insertionSet.execute(block);
143 }
144
145 template<typename VariablesVectorType>
146 void cleanVariables(VariablesVectorType& variables)
147 {
148 for (unsigned i = variables.size(); i--;) {
149 Node* node = variables[i];
150 if (!node)
151 continue;
152 if (node->op() != Check && node->shouldGenerate())
153 continue;
154 variables[i] = nullptr;
155 }
156 }
157
158 InsertionSet m_insertionSet;
159};
160
161bool performDCE(Graph& graph)
162{
163 return runPhase<DCEPhase>(graph);
164}
165
166} } // namespace JSC::DFG
167
168#endif // ENABLE(DFG_JIT)
169
170