diff options
Diffstat (limited to 'Source/WTF/wtf/Dominators.h')
| -rw-r--r-- | Source/WTF/wtf/Dominators.h | 752 |
1 files changed, 752 insertions, 0 deletions
diff --git a/Source/WTF/wtf/Dominators.h b/Source/WTF/wtf/Dominators.h new file mode 100644 index 000000000..e7ab52f7e --- /dev/null +++ b/Source/WTF/wtf/Dominators.h @@ -0,0 +1,752 @@ +/* + * Copyright (C) 2011, 2014-2016 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. + */ + +#ifndef WTFDominators_h +#define WTFDominators_h + +#include <wtf/FastBitVector.h> +#include <wtf/GraphNodeWorklist.h> + +namespace WTF { + +// This is a utility for finding the dominators of a graph. Dominators are almost universally used +// for control flow graph analysis, so this code will refer to the graph's "nodes" as "blocks". In +// that regard this code is kind of specialized for the various JSC compilers, but you could use it +// for non-compiler things if you are OK with referring to your "nodes" as "blocks". + +template<typename Graph> +class Dominators { +public: + Dominators(Graph& graph, bool selfCheck = false) + : m_graph(graph) + , m_data(graph.template newMap<BlockData>()) + { + LengauerTarjan lengauerTarjan(m_graph); + lengauerTarjan.compute(); + + m_data = m_graph.template newMap<BlockData>(); + + // From here we want to build a spanning tree with both upward and downward links and we want + // to do a search over this tree to compute pre and post numbers that can be used for dominance + // tests. + + for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) { + typename Graph::Node block = m_graph.node(blockIndex); + if (!block) + continue; + + typename Graph::Node idomBlock = lengauerTarjan.immediateDominator(block); + m_data[block].idomParent = idomBlock; + if (idomBlock) + m_data[idomBlock].idomKids.append(block); + } + + unsigned nextPreNumber = 0; + unsigned nextPostNumber = 0; + + // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway. + Vector<GraphNodeWithOrder<typename Graph::Node>> worklist; + worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.root(), GraphVisitOrder::Pre)); + while (!worklist.isEmpty()) { + GraphNodeWithOrder<typename Graph::Node> item = worklist.takeLast(); + switch (item.order) { + case GraphVisitOrder::Pre: + m_data[item.node].preNumber = nextPreNumber++; + worklist.append(GraphNodeWithOrder<typename Graph::Node>(item.node, GraphVisitOrder::Post)); + for (typename Graph::Node kid : m_data[item.node].idomKids) + worklist.append(GraphNodeWithOrder<typename Graph::Node>(kid, GraphVisitOrder::Pre)); + break; + case GraphVisitOrder::Post: + m_data[item.node].postNumber = nextPostNumber++; + break; + } + } + + if (selfCheck) { + // Check our dominator calculation: + // 1) Check that our range-based ancestry test is the same as a naive ancestry test. + // 2) Check that our notion of who dominates whom is identical to a naive (not + // Lengauer-Tarjan) dominator calculation. + + ValidationContext context(m_graph, *this); + + for (unsigned fromBlockIndex = m_graph.numNodes(); fromBlockIndex--;) { + typename Graph::Node fromBlock = m_graph.node(fromBlockIndex); + if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX) + continue; + for (unsigned toBlockIndex = m_graph.numNodes(); toBlockIndex--;) { + typename Graph::Node toBlock = m_graph.node(toBlockIndex); + if (!toBlock || m_data[toBlock].preNumber == UINT_MAX) + continue; + + if (dominates(fromBlock, toBlock) != naiveDominates(fromBlock, toBlock)) + context.reportError(fromBlock, toBlock, "Range-based domination check is broken"); + if (dominates(fromBlock, toBlock) != context.naiveDominators.dominates(fromBlock, toBlock)) + context.reportError(fromBlock, toBlock, "Lengauer-Tarjan domination is broken"); + } + } + + context.handleErrors(); + } + } + + bool strictlyDominates(typename Graph::Node from, typename Graph::Node to) const + { + return m_data[to].preNumber > m_data[from].preNumber + && m_data[to].postNumber < m_data[from].postNumber; + } + + bool dominates(typename Graph::Node from, typename Graph::Node to) const + { + return from == to || strictlyDominates(from, to); + } + + // Returns the immediate dominator of this block. Returns null for the root block. + typename Graph::Node idom(typename Graph::Node block) const + { + return m_data[block].idomParent; + } + + template<typename Functor> + void forAllStrictDominatorsOf(typename Graph::Node to, const Functor& functor) const + { + for (typename Graph::Node block = m_data[to].idomParent; block; block = m_data[block].idomParent) + functor(block); + } + + // Note: This will visit the dominators starting with the 'to' node and moving up the idom tree + // until it gets to the root. Some clients of this function, like B3::moveConstants(), rely on this + // order. + template<typename Functor> + void forAllDominatorsOf(typename Graph::Node to, const Functor& functor) const + { + for (typename Graph::Node block = to; block; block = m_data[block].idomParent) + functor(block); + } + + template<typename Functor> + void forAllBlocksStrictlyDominatedBy(typename Graph::Node from, const Functor& functor) const + { + Vector<typename Graph::Node, 16> worklist; + worklist.appendVector(m_data[from].idomKids); + while (!worklist.isEmpty()) { + typename Graph::Node block = worklist.takeLast(); + functor(block); + worklist.appendVector(m_data[block].idomKids); + } + } + + template<typename Functor> + void forAllBlocksDominatedBy(typename Graph::Node from, const Functor& functor) const + { + Vector<typename Graph::Node, 16> worklist; + worklist.append(from); + while (!worklist.isEmpty()) { + typename Graph::Node block = worklist.takeLast(); + functor(block); + worklist.appendVector(m_data[block].idomKids); + } + } + + typename Graph::Set strictDominatorsOf(typename Graph::Node to) const + { + typename Graph::Set result; + forAllStrictDominatorsOf( + to, + [&] (typename Graph::Node node) { + result.add(node); + }); + return result; + } + + typename Graph::Set dominatorsOf(typename Graph::Node to) const + { + typename Graph::Set result; + forAllDominatorsOf( + to, + [&] (typename Graph::Node node) { + result.add(node); + }); + return result; + } + + typename Graph::Set blocksStrictlyDominatedBy(typename Graph::Node from) const + { + typename Graph::Set result; + forAllBlocksStrictlyDominatedBy( + from, + [&] (typename Graph::Node node) { + result.add(node); + }); + return result; + } + + typename Graph::Set blocksDominatedBy(typename Graph::Node from) const + { + typename Graph::Set result; + forAllBlocksDominatedBy( + from, + [&] (typename Graph::Node node) { + result.add(node); + }); + return result; + } + + template<typename Functor> + void forAllBlocksInDominanceFrontierOf( + typename Graph::Node from, const Functor& functor) const + { + typename Graph::Set set; + forAllBlocksInDominanceFrontierOfImpl( + from, + [&] (typename Graph::Node block) { + if (set.add(block)) + functor(block); + }); + } + + typename Graph::Set dominanceFrontierOf(typename Graph::Node from) const + { + typename Graph::Set result; + forAllBlocksInDominanceFrontierOf( + from, + [&] (typename Graph::Node node) { + result.add(node); + }); + return result; + } + + template<typename Functor> + void forAllBlocksInIteratedDominanceFrontierOf(const typename Graph::List& from, const Functor& functor) + { + forAllBlocksInPrunedIteratedDominanceFrontierOf( + from, + [&] (typename Graph::Node block) -> bool { + functor(block); + return true; + }); + } + + // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the + // given functor to return false to indicate that we don't wish to consider the given block. + // Useful for computing pruned SSA form. + template<typename Functor> + void forAllBlocksInPrunedIteratedDominanceFrontierOf( + const typename Graph::List& from, const Functor& functor) + { + typename Graph::Set set; + forAllBlocksInIteratedDominanceFrontierOfImpl( + from, + [&] (typename Graph::Node block) -> bool { + if (!set.add(block)) + return false; + return functor(block); + }); + } + + typename Graph::Set iteratedDominanceFrontierOf(const typename Graph::List& from) const + { + typename Graph::Set result; + forAllBlocksInIteratedDominanceFrontierOfImpl( + from, + [&] (typename Graph::Node node) -> bool { + return result.add(node); + }); + return result; + } + + void dump(PrintStream& out) const + { + for (unsigned blockIndex = 0; blockIndex < m_data.size(); ++blockIndex) { + if (m_data[blockIndex].preNumber == UINT_MAX) + continue; + + out.print(" Block #", blockIndex, ": idom = ", m_graph.dump(m_data[blockIndex].idomParent), ", idomKids = ["); + CommaPrinter comma; + for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i) + out.print(comma, m_graph.dump(m_data[blockIndex].idomKids[i])); + out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n"); + } + } + +private: + // This implements Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph" + // (TOPLAS 1979). It uses the "simple" implementation of LINK and EVAL, which yields an O(n log n) + // solution. The full paper is linked below; this code attempts to closely follow the algorithm as + // it is presented in the paper; in particular sections 3 and 4 as well as appendix B. + // https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf + // + // This code is very subtle. The Lengauer-Tarjan algorithm is incredibly deep to begin with. The + // goal of this code is to follow the code in the paper, however our implementation must deviate + // from the paper when it comes to recursion. The authors had used recursion to implement DFS, and + // also to implement the "simple" EVAL. We convert both of those into worklist-based solutions. + // Finally, once the algorithm gives us immediate dominators, we implement dominance tests by + // walking the dominator tree and computing pre and post numbers. We then use the range inclusion + // check trick that was first discovered by Paul F. Dietz in 1982 in "Maintaining order in a linked + // list" (see http://dl.acm.org/citation.cfm?id=802184). + + class LengauerTarjan { + public: + LengauerTarjan(Graph& graph) + : m_graph(graph) + , m_data(graph.template newMap<BlockData>()) + { + for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) { + typename Graph::Node block = m_graph.node(blockIndex); + if (!block) + continue; + m_data[block].label = block; + } + } + + void compute() + { + computeDepthFirstPreNumbering(); // Step 1. + computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3. + computeExplicitImmediateDominators(); // Step 4. + } + + typename Graph::Node immediateDominator(typename Graph::Node block) + { + return m_data[block].dom; + } + + private: + void computeDepthFirstPreNumbering() + { + // Use a block worklist that also tracks the index inside the successor list. This is + // necessary for ensuring that we don't attempt to visit a successor until the previous + // successors that we had visited are fully processed. This ends up being revealed in the + // output of this method because the first time we see an edge to a block, we set the + // block's parent. So, if we have: + // + // A -> B + // A -> C + // B -> C + // + // And we're processing A, then we want to ensure that if we see A->B first (and hence set + // B's prenumber before we set C's) then we also end up setting C's parent to B by virtue + // of not noticing A->C until we're done processing B. + + ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist; + worklist.push(m_graph.root(), 0); + + while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) { + typename Graph::Node block = item.node; + unsigned successorIndex = item.data; + + // We initially push with successorIndex = 0 regardless of whether or not we have any + // successors. This is so that we can assign our prenumber. Subsequently we get pushed + // with higher successorIndex values, but only if they are in range. + ASSERT(!successorIndex || successorIndex < m_graph.successors(block).size()); + + if (!successorIndex) { + m_data[block].semiNumber = m_blockByPreNumber.size(); + m_blockByPreNumber.append(block); + } + + if (successorIndex < m_graph.successors(block).size()) { + unsigned nextSuccessorIndex = successorIndex + 1; + if (nextSuccessorIndex < m_graph.successors(block).size()) + worklist.forcePush(block, nextSuccessorIndex); + + typename Graph::Node successorBlock = m_graph.successors(block)[successorIndex]; + if (worklist.push(successorBlock, 0)) + m_data[successorBlock].parent = block; + } + } + } + + void computeSemiDominatorsAndImplicitImmediateDominators() + { + for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) { + typename Graph::Node block = m_blockByPreNumber[currentPreNumber]; + BlockData& blockData = m_data[block]; + + // Step 2: + for (typename Graph::Node predecessorBlock : m_graph.predecessors(block)) { + typename Graph::Node intermediateBlock = eval(predecessorBlock); + blockData.semiNumber = std::min( + m_data[intermediateBlock].semiNumber, blockData.semiNumber); + } + unsigned bucketPreNumber = blockData.semiNumber; + ASSERT(bucketPreNumber <= currentPreNumber); + m_data[m_blockByPreNumber[bucketPreNumber]].bucket.append(block); + link(blockData.parent, block); + + // Step 3: + for (typename Graph::Node semiDominee : m_data[blockData.parent].bucket) { + typename Graph::Node possibleDominator = eval(semiDominee); + BlockData& semiDomineeData = m_data[semiDominee]; + ASSERT(m_blockByPreNumber[semiDomineeData.semiNumber] == blockData.parent); + BlockData& possibleDominatorData = m_data[possibleDominator]; + if (possibleDominatorData.semiNumber < semiDomineeData.semiNumber) + semiDomineeData.dom = possibleDominator; + else + semiDomineeData.dom = blockData.parent; + } + m_data[blockData.parent].bucket.clear(); + } + } + + void computeExplicitImmediateDominators() + { + for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) { + typename Graph::Node block = m_blockByPreNumber[currentPreNumber]; + BlockData& blockData = m_data[block]; + + if (blockData.dom != m_blockByPreNumber[blockData.semiNumber]) + blockData.dom = m_data[blockData.dom].dom; + } + } + + void link(typename Graph::Node from, typename Graph::Node to) + { + m_data[to].ancestor = from; + } + + typename Graph::Node eval(typename Graph::Node block) + { + if (!m_data[block].ancestor) + return block; + + compress(block); + return m_data[block].label; + } + + void compress(typename Graph::Node initialBlock) + { + // This was meant to be a recursive function, but we don't like recursion because we don't + // want to blow the stack. The original function will call compress() recursively on the + // ancestor of anything that has an ancestor. So, we populate our worklist with the + // recursive ancestors of initialBlock. Then we process the list starting from the block + // that is furthest up the ancestor chain. + + typename Graph::Node ancestor = m_data[initialBlock].ancestor; + ASSERT(ancestor); + if (!m_data[ancestor].ancestor) + return; + + Vector<typename Graph::Node, 16> stack; + for (typename Graph::Node block = initialBlock; block; block = m_data[block].ancestor) + stack.append(block); + + // We only care about blocks that have an ancestor that has an ancestor. The last two + // elements in the stack won't satisfy this property. + ASSERT(stack.size() >= 2); + ASSERT(!m_data[stack[stack.size() - 1]].ancestor); + ASSERT(!m_data[m_data[stack[stack.size() - 2]].ancestor].ancestor); + + for (unsigned i = stack.size() - 2; i--;) { + typename Graph::Node block = stack[i]; + typename Graph::Node& labelOfBlock = m_data[block].label; + typename Graph::Node& ancestorOfBlock = m_data[block].ancestor; + ASSERT(ancestorOfBlock); + ASSERT(m_data[ancestorOfBlock].ancestor); + + typename Graph::Node labelOfAncestorOfBlock = m_data[ancestorOfBlock].label; + + if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber) + labelOfBlock = labelOfAncestorOfBlock; + ancestorOfBlock = m_data[ancestorOfBlock].ancestor; + } + } + + struct BlockData { + BlockData() + : parent(nullptr) + , preNumber(UINT_MAX) + , semiNumber(UINT_MAX) + , ancestor(nullptr) + , label(nullptr) + , dom(nullptr) + { + } + + typename Graph::Node parent; + unsigned preNumber; + unsigned semiNumber; + typename Graph::Node ancestor; + typename Graph::Node label; + Vector<typename Graph::Node> bucket; + typename Graph::Node dom; + }; + + Graph& m_graph; + typename Graph::template Map<BlockData> m_data; + Vector<typename Graph::Node> m_blockByPreNumber; + }; + + class NaiveDominators { + public: + NaiveDominators(Graph& graph) + : m_graph(graph) + { + // This implements a naive dominator solver. + + ASSERT(!graph.predecessors(graph.root()).size()); + + unsigned numBlocks = graph.numNodes(); + + // Allocate storage for the dense dominance matrix. + 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][0] = true; + + // Find all of the valid blocks. + m_scratch.clearAll(); + for (unsigned i = numBlocks; i--;) { + if (!graph.node(i)) + continue; + m_scratch[i] = true; + } + + // Mark all nodes as dominated by everything. + for (unsigned i = numBlocks; i-- > 1;) { + if (!graph.node(i) || !graph.predecessors(graph.node(i)).size()) + m_results[i].clearAll(); + else + m_results[i] = 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 |= pruneDominators(i); + + if (!changed) + break; + + // Prune dominators in all non entry blocks: backward scan. + changed = false; + for (unsigned i = numBlocks; i-- > 1;) + changed |= pruneDominators(i); + } while (changed); + } + + bool dominates(unsigned from, unsigned to) const + { + return m_results[to][from]; + } + + bool dominates(typename Graph::Node from, typename Graph::Node to) const + { + return dominates(m_graph.index(from), m_graph.index(to)); + } + + void dump(PrintStream& out) const + { + for (unsigned blockIndex = 0; blockIndex < m_graph.numNodes(); ++blockIndex) { + typename Graph::Node block = m_graph.node(blockIndex); + if (!block) + continue; + out.print(" Block ", m_graph.dump(block), ":"); + for (unsigned otherIndex = 0; otherIndex < m_graph.numNodes(); ++otherIndex) { + if (!dominates(m_graph.index(block), otherIndex)) + continue; + out.print(" ", m_graph.dump(m_graph.node(otherIndex))); + } + out.print("\n"); + } + } + + private: + bool pruneDominators(unsigned idx) + { + typename Graph::Node block = m_graph.node(idx); + + if (!block || !m_graph.predecessors(block).size()) + return false; + + // Find the intersection of dom(preds). + m_scratch = m_results[m_graph.index(m_graph.predecessors(block)[0])]; + for (unsigned j = m_graph.predecessors(block).size(); j-- > 1;) + m_scratch &= m_results[m_graph.index(m_graph.predecessors(block)[j])]; + + // The block is also dominated by itself. + m_scratch[idx] = true; + + return m_results[idx].setAndCheck(m_scratch); + } + + Graph& m_graph; + Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it. + FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes. + }; + + struct ValidationContext { + ValidationContext(Graph& graph, Dominators& dominators) + : graph(graph) + , dominators(dominators) + , naiveDominators(graph) + { + } + + void reportError(typename Graph::Node from, typename Graph::Node to, const char* message) + { + Error error; + error.from = from; + error.to = to; + error.message = message; + errors.append(error); + } + + void handleErrors() + { + if (errors.isEmpty()) + return; + + dataLog("DFG DOMINATOR VALIDATION FAILED:\n"); + dataLog("\n"); + dataLog("For block domination relationships:\n"); + for (unsigned i = 0; i < errors.size(); ++i) { + dataLog( + " ", graph.dump(errors[i].from), " -> ", graph.dump(errors[i].to), + " (", errors[i].message, ")\n"); + } + dataLog("\n"); + dataLog("Control flow graph:\n"); + for (unsigned blockIndex = 0; blockIndex < graph.numNodes(); ++blockIndex) { + typename Graph::Node block = graph.node(blockIndex); + if (!block) + continue; + dataLog(" Block ", graph.dump(graph.node(blockIndex)), ": successors = ["); + CommaPrinter comma; + for (auto successor : graph.successors(block)) + dataLog(comma, graph.dump(successor)); + dataLog("], predecessors = ["); + comma = CommaPrinter(); + for (auto predecessor : graph.predecessors(block)) + dataLog(comma, graph.dump(predecessor)); + dataLog("]\n"); + } + dataLog("\n"); + dataLog("Lengauer-Tarjan Dominators:\n"); + dataLog(dominators); + dataLog("\n"); + dataLog("Naive Dominators:\n"); + naiveDominators.dump(WTF::dataFile()); + dataLog("\n"); + dataLog("Graph at time of failure:\n"); + dataLog(graph); + dataLog("\n"); + dataLog("DFG DOMINATOR VALIDATION FAILIED!\n"); + CRASH(); + } + + Graph& graph; + Dominators& dominators; + NaiveDominators naiveDominators; + + struct Error { + typename Graph::Node from; + typename Graph::Node to; + const char* message; + }; + + Vector<Error> errors; + }; + + bool naiveDominates(typename Graph::Node from, typename Graph::Node to) const + { + for (typename Graph::Node block = to; block; block = m_data[block].idomParent) { + if (block == from) + return true; + } + return false; + } + + template<typename Functor> + void forAllBlocksInDominanceFrontierOfImpl( + typename Graph::Node from, const Functor& functor) const + { + // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory): + // "The dominance frontier of a block 'from' is the set of all blocks 'to' such that + // 'from' dominates an immediate predecessor of 'to', but 'from' does not strictly + // dominate 'to'." + // + // A useful corner case to remember: a block may be in its own dominance frontier if it has + // a loop edge to itself, since it dominates itself and so it dominates its own immediate + // predecessor, and a block never strictly dominates itself. + + forAllBlocksDominatedBy( + from, + [&] (typename Graph::Node block) { + for (typename Graph::Node to : m_graph.successors(block)) { + if (!strictlyDominates(from, to)) + functor(to); + } + }); + } + + template<typename Functor> + void forAllBlocksInIteratedDominanceFrontierOfImpl( + const typename Graph::List& from, const Functor& functor) const + { + typename Graph::List worklist = from; + while (!worklist.isEmpty()) { + typename Graph::Node block = worklist.takeLast(); + forAllBlocksInDominanceFrontierOfImpl( + block, + [&] (typename Graph::Node otherBlock) { + if (functor(otherBlock)) + worklist.append(otherBlock); + }); + } + } + + struct BlockData { + BlockData() + : idomParent(nullptr) + , preNumber(UINT_MAX) + , postNumber(UINT_MAX) + { + } + + Vector<typename Graph::Node> idomKids; + typename Graph::Node idomParent; + + unsigned preNumber; + unsigned postNumber; + }; + + Graph& m_graph; + typename Graph::template Map<BlockData> m_data; +}; + +} // namespace WTF + +using WTF::Dominators; + +#endif // WTFDominators_h + |