/*
- * 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
{
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<BasicBlock*> 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;
}
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();
}
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.
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<typename VariablesVectorType>
void cleanVariables(VariablesVectorType& variables)
{
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<Node*, 128> m_worklist;
InsertionSet m_insertionSet;
};
projects / apple / javascriptcore.git / blobdiff