Title: [157675] trunk/Source/_javascript_Core
- Revision
- 157675
- Author
- [email protected]
- Date
- 2013-10-19 13:11:36 -0700 (Sat, 19 Oct 2013)
Log Message
DFG dominators: document and rename stuff.
https://bugs.webkit.org/show_bug.cgi?id=123056
Patch by Nadav Rotem <[email protected]> on 2013-10-19
Reviewed by Filip Pizlo.
Documented the code and renamed some variables.
* dfg/DFGDominators.cpp:
(JSC::DFG::Dominators::compute):
(JSC::DFG::Dominators::pruneDominators):
* dfg/DFGDominators.h:
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (157674 => 157675)
--- trunk/Source/_javascript_Core/ChangeLog 2013-10-19 19:55:40 UTC (rev 157674)
+++ trunk/Source/_javascript_Core/ChangeLog 2013-10-19 20:11:36 UTC (rev 157675)
@@ -1,3 +1,17 @@
+2013-10-19 Nadav Rotem <[email protected]>
+
+ DFG dominators: document and rename stuff.
+ https://bugs.webkit.org/show_bug.cgi?id=123056
+
+ Reviewed by Filip Pizlo.
+
+ Documented the code and renamed some variables.
+
+ * dfg/DFGDominators.cpp:
+ (JSC::DFG::Dominators::compute):
+ (JSC::DFG::Dominators::pruneDominators):
+ * dfg/DFGDominators.h:
+
2013-10-19 Julien Brianceau <[email protected]>
Fix build failure for architectures with 4 argument registers.
Modified: trunk/Source/_javascript_Core/dfg/DFGDominators.cpp (157674 => 157675)
--- trunk/Source/_javascript_Core/dfg/DFGDominators.cpp 2013-10-19 19:55:40 UTC (rev 157674)
+++ trunk/Source/_javascript_Core/dfg/DFGDominators.cpp 2013-10-19 20:11:36 UTC (rev 157675)
@@ -48,16 +48,19 @@
unsigned numBlocks = graph.numBlocks();
+ // Allocate storage for the dense dominance matrix.
if (numBlocks > m_results.size()) {
m_results.grow(numBlocks);
for (unsigned i = numBlocks; i--;)
m_results[i].resize(numBlocks);
m_scratch.resize(numBlocks);
}
-
+
+ // We know that the entry block is only dominated by itself.
m_results[0].clearAll();
m_results[0].set(0);
-
+
+ // Find all of the valid blocks.
m_scratch.clearAll();
for (unsigned i = numBlocks; i--;) {
if (!graph.block(i))
@@ -65,39 +68,48 @@
m_scratch.set(i);
}
+ // Mark all nodes as dominated by everything.
for (unsigned i = numBlocks; i-- > 1;) {
if (!graph.block(i) || graph.block(i)->predecessors.isEmpty())
m_results[i].clearAll();
else
m_results[i].set(m_scratch);
}
-
+
+ // Iteratively eliminate nodes that are not dominator.
bool changed;
do {
changed = false;
+ // Prune dominators in all non entry blocks: forward scan.
for (unsigned i = 1; i < numBlocks; ++i)
- changed |= iterateForBlock(graph, i);
+ changed |= pruneDominators(graph, i);
+
if (!changed)
break;
-
+
+ // Prune dominators in all non entry blocks: backward scan.
changed = false;
for (unsigned i = numBlocks; i-- > 1;)
- changed |= iterateForBlock(graph, i);
+ changed |= pruneDominators(graph, i);
} while (changed);
}
-bool Dominators::iterateForBlock(Graph& graph, BlockIndex i)
+bool Dominators::pruneDominators(Graph& graph, BlockIndex idx)
{
- BasicBlock* block = graph.block(i);
- if (!block)
+ BasicBlock* block = graph.block(idx);
+
+ if (!block || block->predecessors.isEmpty())
return false;
- if (block->predecessors.isEmpty())
- return false;
+
+ // Find the intersection of dom(preds).
m_scratch.set(m_results[block->predecessors[0]->index]);
for (unsigned j = block->predecessors.size(); j-- > 1;)
m_scratch.filter(m_results[block->predecessors[j]->index]);
- m_scratch.set(i);
- return m_results[i].setAndCheck(m_scratch);
+
+ // The block is also dominated by itself.
+ m_scratch.set(idx);
+
+ return m_results[idx].setAndCheck(m_scratch);
}
void Dominators::dump(Graph& graph, PrintStream& out) const
Modified: trunk/Source/_javascript_Core/dfg/DFGDominators.h (157674 => 157675)
--- trunk/Source/_javascript_Core/dfg/DFGDominators.h 2013-10-19 19:55:40 UTC (rev 157674)
+++ trunk/Source/_javascript_Core/dfg/DFGDominators.h 2013-10-19 20:11:36 UTC (rev 157675)
@@ -60,10 +60,10 @@
void dump(Graph& graph, PrintStream&) const;
private:
- bool iterateForBlock(Graph& graph, BlockIndex);
+ bool pruneDominators(Graph&, BlockIndex);
Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
- FastBitVector m_scratch;
+ FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
};
} } // namespace JSC::DFG
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
