X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/2d39b0e377c0896910ee49ae70082ba665faf986..refs/heads/master:/dfg/DFGDCEPhase.cpp diff --git a/dfg/DFGDCEPhase.cpp b/dfg/DFGDCEPhase.cpp index e8cf933..5290f24 100644 --- a/dfg/DFGDCEPhase.cpp +++ b/dfg/DFGDCEPhase.cpp @@ -1,5 +1,5 @@ /* - * Copyright (C) 2013, 2014 Apple Inc. All rights reserved. + * Copyright (C) 2013-2015 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -48,75 +48,34 @@ public: { 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 < m_graph.numBlocks(); ++blockIndex) { - BasicBlock* block = m_graph.block(blockIndex); - if (!block) - continue; - for (unsigned indexInBlock = block->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 < m_graph.numBlocks(); ++blockIndex) { + m_graph.computeRefCounts(); + + for (BasicBlock* block : m_graph.blocksInPreOrder()) + fixupBlock(block); + + cleanVariables(m_graph.m_arguments); + + // Just do a basic Phantom/Check clean-up. + for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) { BasicBlock* block = m_graph.block(blockIndex); if (!block) continue; - for (unsigned indexInBlock = block->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) + unsigned sourceIndex = 0; + unsigned targetIndex = 0; + while (sourceIndex < block->size()) { + Node* node = block->at(sourceIndex++); + switch (node->op()) { + case Check: + case Phantom: + if (node->children.isEmpty()) 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); - } + break; + default: + break; } + block->at(targetIndex++) = node; } - } - - if (m_graph.m_form == SSA) { - Vector depthFirst; - m_graph.getBlocksInDepthFirstOrder(depthFirst); - for (unsigned i = 0; i < depthFirst.size(); ++i) - fixupBlock(depthFirst[i]); - } else { - RELEASE_ASSERT(m_graph.m_form == ThreadedCPS); - - for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) - fixupBlock(m_graph.block(blockIndex)); - - cleanVariables(m_graph.m_arguments); + block->resize(targetIndex); } m_graph.m_refCountState = ExactRefCount; @@ -125,51 +84,16 @@ public: } private: - void findTypeCheckRoot(Node*, Edge edge) - { - // We may have an "unproved" untyped use for code that is unreachable. The CFA - // will just not have gotten around to it. - if (edge.willNotHaveCheck()) - return; - if (!edge->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. - + + if (m_graph.m_form == ThreadedCPS) { for (unsigned phiIndex = 0; phiIndex < block->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 + Node* phi = block->phis[phiIndex]; + if (!phi->shouldGenerate()) { + m_graph.m_allocator.free(phi); block->phis[phiIndex--] = block->phis.last(); block->phis.removeLast(); } @@ -177,12 +101,6 @@ private: cleanVariables(block->variablesAtHead); cleanVariables(block->variablesAtTail); - break; - } - - default: - RELEASE_ASSERT_NOT_REACHED(); - return; } // This has to be a forward loop because we are using the insertion set. @@ -191,62 +109,29 @@ private: if (node->shouldGenerate()) continue; - switch (node->op()) { - case MovHint: { - // Check if the child is dead. MovHint's child would only be a Phantom - // if we had just killed it. - if (node->child1()->op() == Phantom) { - node->setOpAndDefaultFlags(ZombieHint); - node->child1() = Edge(); - break; + if (node->flags() & NodeHasVarArgs) { + for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) { + Edge edge = m_graph.m_varArgChildren[childIdx]; + + if (!edge || edge.willNotHaveCheck()) + continue; + + m_insertionSet.insertNode(indexInBlock, SpecNone, Check, node->origin, edge); } - break; - } - case ZombieHint: { - // Currently we assume that DCE runs only once. - RELEASE_ASSERT_NOT_REACHED(); - break; + node->setOpAndDefaultFlags(Check); + node->children.reset(); + node->setRefCount(1); + continue; } - default: { - if (node->flags() & NodeHasVarArgs) { - for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) { - Edge edge = m_graph.m_varArgChildren[childIdx]; - - if (!edge || edge.willNotHaveCheck()) - continue; - - m_insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->origin, edge); - } - - node->convertToPhantomUnchecked(); - node->children.reset(); - node->setRefCount(1); - break; - } - - node->convertToPhantom(); - eliminateIrrelevantPhantomChildren(node); - node->setRefCount(1); - break; - } } + node->remove(); + node->setRefCount(1); } m_insertionSet.execute(block); } - void eliminateIrrelevantPhantomChildren(Node* node) - { - for (unsigned i = 0; i < AdjacencyList::Size; ++i) { - Edge edge = node->children.child(i); - if (!edge) - continue; - if (edge.willNotHaveCheck()) - node->children.removeEdge(i--); - } - } - template void cleanVariables(VariablesVectorType& variables) { @@ -254,53 +139,12 @@ private: Node* node = variables[i]; if (!node) continue; - if (node->op() != Phantom && node->shouldGenerate()) + if (node->op() != Check && node->shouldGenerate()) continue; - if (node->op() == GetLocal) { - node = node->child1().node(); - - // FIXME: In the case that the variable is captured, we really want to be able - // to replace the variable-at-tail with the last use of the variable in the same - // way that CPS rethreading would do. The child of the GetLocal isn't necessarily - // the same as what CPS rethreading would do. For example, we may have: - // - // a: SetLocal(...) // live - // b: GetLocal(@a) // live - // c: GetLocal(@a) // dead - // - // When killing @c, the code below will set the variable-at-tail to @a, while CPS - // rethreading would have set @b. This is a benign bug, since all clients of CPS - // only use the variable-at-tail of captured variables to get the - // VariableAccessData and observe that it is in fact captured. But, this feels - // like it could cause bugs in the future. - // - // It's tempting to just dethread and then invoke CPS rethreading, but CPS - // rethreading fails to preserve exact ref-counts. So we would need a fixpoint. - // It's probably the case that this fixpoint will be guaranteed to converge after - // the second iteration (i.e. the second run of DCE will not kill anything and so - // will not need to dethread), but for now the safest approach is probably just to - // allow for this tiny bit of sloppiness. - // - // Another possible solution would be to simply say that DCE dethreads but then - // we never rethread before going to the backend. That feels intuitively right - // because it's unlikely that any of the phases after DCE in the backend rely on - // ThreadedCPS. - // - // https://bugs.webkit.org/show_bug.cgi?id=130115 - ASSERT( - node->op() == Phi || node->op() == SetArgument - || node->variableAccessData()->isCaptured()); - - if (node->shouldGenerate()) { - variables[i] = node; - continue; - } - } - variables[i] = 0; + variables[i] = nullptr; } } - Vector m_worklist; InsertionSet m_insertionSet; };