/* * Copyright (C) 2013 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "config.h" #include "DFGDCEPhase.h" #if ENABLE(DFG_JIT) #include "DFGBasicBlockInlines.h" #include "DFGGraph.h" #include "DFGInsertionSet.h" #include "DFGPhase.h" #include "Operations.h" namespace JSC { namespace DFG { class DCEPhase : public Phase { public: DCEPhase(Graph& graph) : Phase(graph, "dead code elimination") , m_insertionSet(graph) { } bool run() { ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA); // First reset the counts to 0 for all nodes. for (BlockIndex blockIndex = 0; blockIndex size(); indexInBlock--;) block->at(indexInBlock)->setRefCount(0); for (unsigned phiIndex = block->phis.size(); phiIndex--;) block->phis[phiIndex]->setRefCount(0); } // Now find the roots: // - Nodes that are must-generate. // - Nodes that are reachable from type checks. // Set their ref counts to 1 and put them on the worklist. for (BlockIndex blockIndex = 0; blockIndex size(); indexInBlock--;) { Node* node = block->at(indexInBlock); DFG_NODE_DO_TO_CHILDREN(m_graph, node, findTypeCheckRoot); if (!(node->flags() & NodeMustGenerate)) continue; if (!node->postfixRef()) m_worklist.append(node); } } while (!m_worklist.isEmpty()) { while (!m_worklist.isEmpty()) { Node* node = m_worklist.last(); m_worklist.removeLast(); ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed. DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge); } if (m_graph.m_form == SSA) { // Find Phi->Upsilon edges, which are represented as meta-data in the // Upsilon. for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) { BasicBlock* block = m_graph.block(blockIndex); if (!block) continue; for (unsigned nodeIndex = block->size(); nodeIndex--;) { Node* node = block->at(nodeIndex); if (node->op() != Upsilon) continue; if (node->shouldGenerate()) continue; if (node->phi()->shouldGenerate()) countNode(node); } } } } if (m_graph.m_form == SSA) { // Need to process the graph in reverse DFS order, so that we get to the uses // of a node before we get to the node itself. Vector depthFirst; m_graph.getBlocksInDepthFirstOrder(depthFirst); for (unsigned i = depthFirst.size(); i--;) fixupBlock(depthFirst[i]); } else { RELEASE_ASSERT(m_graph.m_form == ThreadedCPS); for (BlockIndex blockIndex = 0; blockIndex postfixRef()) m_worklist.append(edge.node()); } void countNode(Node* node) { if (node->postfixRef()) return; m_worklist.append(node); } void countEdge(Node*, Edge edge) { // Don't count edges that are already counted for their type checks. if (edge.willHaveCheck()) return; countNode(edge.node()); } void fixupBlock(BasicBlock* block) { if (!block) return; switch (m_graph.m_form) { case SSA: break; case ThreadedCPS: { // Clean up variable links for the block. We need to do this before the actual DCE // because we need to see GetLocals, so we can bypass them in situations where the // vars-at-tail point to a GetLocal, the GetLocal is dead, but the Phi it points // to is alive. for (unsigned phiIndex = 0; phiIndex phis.size(); ++phiIndex) { if (!block->phis[phiIndex]->shouldGenerate()) { // FIXME: We could actually free nodes here. Except that it probably // doesn't matter, since we don't add any nodes after this phase. // https://bugs.webkit.org/show_bug.cgi?id=126239 block->phis[phiIndex--] = block->phis.last(); block->phis.removeLast(); } } cleanVariables(block->variablesAtHead); cleanVariables(block->variablesAtTail); break; } default: RELEASE_ASSERT_NOT_REACHED(); return; } for (unsigned indexInBlock = block->size(); indexInBlock--;) { Node* node = block->at(indexInBlock); if (node->shouldGenerate()) continue; switch (node->op()) { case MovHint: { ASSERT(node->child1().useKind() == UntypedUse); if (!node->child1()->shouldGenerate()) { node->setOpAndDefaultFlags(ZombieHint); node->child1() = Edge(); break; } node->setOpAndDefaultFlags(MovHint); break; } case ZombieHint: { // Currently we assume that DCE runs only once. RELEASE_ASSERT_NOT_REACHED(); break; } default: { if (node->flags() & NodeHasVarArgs) { for (unsigned childIdx = node->firstChild(); childIdx firstChild() + node->numChildren(); childIdx++) { Edge edge = m_graph.m_varArgChildren[childIdx]; if (!edge || edge.willNotHaveCheck()) continue; m_insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->codeOrigin, edge); } node->convertToPhantomUnchecked(); node->children.reset(); node->setRefCount(1); break; } node->convertToPhantom(); eliminateIrrelevantPhantomChildren(node); node->setRefCount(1); break; } } } m_insertionSet.execute(block); } void eliminateIrrelevantPhantomChildren(Node* node) { for (unsigned i = 0; i children.child(i); if (!edge) continue; if (edge.willNotHaveCheck()) node->children.removeEdge(i--); } } template void cleanVariables(VariablesVectorType& variables) { for (unsigned i = variables.size(); i--;) { Node* node = variables[i]; if (!node) continue; if (node->op() != Phantom && node->shouldGenerate()) continue; if (node->op() == GetLocal) { node = node->child1().node(); ASSERT(node->op() == Phi || node->op() == SetArgument); if (node->shouldGenerate()) { variables[i] = node; continue; } } variables[i] = 0; } } Vector m_worklist; InsertionSet m_insertionSet; }; bool performDCE(Graph& graph) { SamplingRegion samplingRegion("DFG DCE Phase"); return runPhase(graph); } } } // namespace JSC::DFG #endif // ENABLE(DFG_JIT)