762 lines
30 KiB
C++
762 lines
30 KiB
C++
/*
|
|
* Copyright (C) 2011-2017 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.
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include <wtf/CommaPrinter.h>
|
|
#include <wtf/FastBitVector.h>
|
|
#include <wtf/GraphNodeWorklist.h>
|
|
#include <wtf/Vector.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 {
|
|
WTF_MAKE_FAST_ALLOCATED;
|
|
public:
|
|
using List = typename Graph::List;
|
|
|
|
Dominators(Graph& graph, bool selfCheck = false)
|
|
: m_graph(graph)
|
|
, m_data(graph.template newMap<BlockData>())
|
|
{
|
|
LengauerTarjan lengauerTarjan(m_graph);
|
|
lengauerTarjan.compute();
|
|
|
|
// 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 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 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 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 {
|
|
WTF_MAKE_FAST_ALLOCATED;
|
|
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 {
|
|
WTF_MAKE_STRUCT_FAST_ALLOCATED;
|
|
|
|
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 {
|
|
WTF_MAKE_FAST_ALLOCATED;
|
|
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 {
|
|
WTF_MAKE_STRUCT_FAST_ALLOCATED;
|
|
|
|
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 {
|
|
WTF_MAKE_STRUCT_FAST_ALLOCATED;
|
|
|
|
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 List& from, const Functor& functor) const
|
|
{
|
|
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 {
|
|
WTF_MAKE_STRUCT_FAST_ALLOCATED;
|
|
|
|
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;
|