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