#include "config.h"
#include "DFGDominators.h"
#if ENABLE(DFG_JIT)
#include "DFGBlockMapInlines.h"
#include "DFGBlockWorklist.h"
#include "DFGGraph.h"
#include "DFGNaiveDominators.h"
#include "JSCInlines.h"
namespace JSC { namespace DFG {
Dominators::Dominators()
{
}
Dominators::~Dominators()
{
}
namespace {
class LengauerTarjan {
public:
LengauerTarjan(Graph& graph)
: m_graph(graph)
, m_data(graph)
{
for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
BasicBlock* block = m_graph.block(blockIndex);
if (!block)
continue;
m_data[block].label = block;
}
}
void compute()
{
computeDepthFirstPreNumbering(); computeSemiDominatorsAndImplicitImmediateDominators(); computeExplicitImmediateDominators(); }
BasicBlock* immediateDominator(BasicBlock* block)
{
return m_data[block].dom;
}
private:
void computeDepthFirstPreNumbering()
{
ExtendedBlockWorklist<unsigned> worklist;
worklist.push(m_graph.block(0), 0);
while (BlockWith<unsigned> item = worklist.pop()) {
BasicBlock* block = item.block;
unsigned successorIndex = item.data;
ASSERT(!successorIndex || successorIndex < block->numSuccessors());
if (!successorIndex) {
m_data[block].semiNumber = m_blockByPreNumber.size();
m_blockByPreNumber.append(block);
}
if (successorIndex < block->numSuccessors()) {
unsigned nextSuccessorIndex = successorIndex + 1;
if (nextSuccessorIndex < block->numSuccessors())
worklist.forcePush(block, nextSuccessorIndex);
BasicBlock* successorBlock = block->successor(successorIndex);
if (worklist.push(successorBlock, 0))
m_data[successorBlock].parent = block;
}
}
}
void computeSemiDominatorsAndImplicitImmediateDominators()
{
for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
BasicBlock* block = m_blockByPreNumber[currentPreNumber];
BlockData& blockData = m_data[block];
for (BasicBlock* predecessorBlock : block->predecessors) {
BasicBlock* 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);
for (BasicBlock* semiDominee : m_data[blockData.parent].bucket) {
BasicBlock* 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) {
BasicBlock* 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(BasicBlock* from, BasicBlock* to)
{
m_data[to].ancestor = from;
}
BasicBlock* eval(BasicBlock* block)
{
if (!m_data[block].ancestor)
return block;
compress(block);
return m_data[block].label;
}
void compress(BasicBlock* initialBlock)
{
BasicBlock* ancestor = m_data[initialBlock].ancestor;
ASSERT(ancestor);
if (!m_data[ancestor].ancestor)
return;
Vector<BasicBlock*, 16> stack;
for (BasicBlock* block = initialBlock; block; block = m_data[block].ancestor)
stack.append(block);
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--;) {
BasicBlock* block = stack[i];
BasicBlock*& labelOfBlock = m_data[block].label;
BasicBlock*& ancestorOfBlock = m_data[block].ancestor;
ASSERT(ancestorOfBlock);
ASSERT(m_data[ancestorOfBlock].ancestor);
BasicBlock* 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)
{
}
BasicBlock* parent;
unsigned preNumber;
unsigned semiNumber;
BasicBlock* ancestor;
BasicBlock* label;
Vector<BasicBlock*> bucket;
BasicBlock* dom;
};
Graph& m_graph;
BlockMap<BlockData> m_data;
Vector<BasicBlock*> m_blockByPreNumber;
};
struct ValidationContext {
ValidationContext(Graph& graph, Dominators& dominators)
: graph(graph)
, dominators(dominators)
{
}
void reportError(BasicBlock* from, BasicBlock* to, const char* message)
{
Error error;
error.from = from;
error.to = to;
error.message = message;
errors.append(error);
}
void handleErrors()
{
if (errors.isEmpty())
return;
startCrashing();
dataLog("DFG DOMINATOR VALIDATION FAILED:\n");
dataLog("\n");
dataLog("For block domination relationships:\n");
for (unsigned i = 0; i < errors.size(); ++i) {
dataLog(
" ", pointerDump(errors[i].from), " -> ", pointerDump(errors[i].to),
" (", errors[i].message, ")\n");
}
dataLog("\n");
dataLog("Control flow graph:\n");
for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
BasicBlock* block = graph.block(blockIndex);
if (!block)
continue;
dataLog(" Block #", blockIndex, ": successors = [");
CommaPrinter comma;
for (unsigned i = 0; i < block->numSuccessors(); ++i)
dataLog(comma, *block->successor(i));
dataLog("], predecessors = [");
comma = CommaPrinter();
for (unsigned i = 0; i < block->predecessors.size(); ++i)
dataLog(comma, *block->predecessors[i]);
dataLog("]\n");
}
dataLog("\n");
dataLog("Lengauer-Tarjan Dominators:\n");
dataLog(dominators);
dataLog("\n");
dataLog("Naive Dominators:\n");
naiveDominators.dump(graph, WTF::dataFile());
dataLog("\n");
dataLog("Graph at time of failure:\n");
graph.dump();
dataLog("\n");
dataLog("DFG DOMINATOR VALIDATION FAILIED!\n");
CRASH();
}
Graph& graph;
Dominators& dominators;
NaiveDominators naiveDominators;
struct Error {
BasicBlock* from;
BasicBlock* to;
const char* message;
};
Vector<Error> errors;
};
}
void Dominators::compute(Graph& graph)
{
LengauerTarjan lengauerTarjan(graph);
lengauerTarjan.compute();
m_data = BlockMap<BlockData>(graph);
for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
BasicBlock* block = graph.block(blockIndex);
if (!block)
continue;
BasicBlock* idomBlock = lengauerTarjan.immediateDominator(block);
m_data[block].idomParent = idomBlock;
if (idomBlock)
m_data[idomBlock].idomKids.append(block);
}
unsigned nextPreNumber = 0;
unsigned nextPostNumber = 0;
Vector<BlockWithOrder> worklist;
worklist.append(BlockWithOrder(graph.block(0), PreOrder));
while (!worklist.isEmpty()) {
BlockWithOrder item = worklist.takeLast();
switch (item.order) {
case PreOrder:
m_data[item.block].preNumber = nextPreNumber++;
worklist.append(BlockWithOrder(item.block, PostOrder));
for (BasicBlock* kid : m_data[item.block].idomKids)
worklist.append(BlockWithOrder(kid, PreOrder));
break;
case PostOrder:
m_data[item.block].postNumber = nextPostNumber++;
break;
}
}
if (validationEnabled()) {
ValidationContext context(graph, *this);
context.naiveDominators.compute(graph);
for (BlockIndex fromBlockIndex = graph.numBlocks(); fromBlockIndex--;) {
BasicBlock* fromBlock = graph.block(fromBlockIndex);
if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX)
continue;
for (BlockIndex toBlockIndex = graph.numBlocks(); toBlockIndex--;) {
BasicBlock* toBlock = graph.block(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();
}
}
BlockSet Dominators::strictDominatorsOf(BasicBlock* to) const
{
BlockSet result;
forAllStrictDominatorsOf(to, BlockAdder(result));
return result;
}
BlockSet Dominators::dominatorsOf(BasicBlock* to) const
{
BlockSet result;
forAllDominatorsOf(to, BlockAdder(result));
return result;
}
BlockSet Dominators::blocksStrictlyDominatedBy(BasicBlock* from) const
{
BlockSet result;
forAllBlocksStrictlyDominatedBy(from, BlockAdder(result));
return result;
}
BlockSet Dominators::blocksDominatedBy(BasicBlock* from) const
{
BlockSet result;
forAllBlocksDominatedBy(from, BlockAdder(result));
return result;
}
BlockSet Dominators::dominanceFrontierOf(BasicBlock* from) const
{
BlockSet result;
forAllBlocksInDominanceFrontierOfImpl(from, BlockAdder(result));
return result;
}
BlockSet Dominators::iteratedDominanceFrontierOf(const BlockList& from) const
{
BlockSet result;
forAllBlocksInIteratedDominanceFrontierOfImpl(from, BlockAdder(result));
return result;
}
bool Dominators::naiveDominates(BasicBlock* from, BasicBlock* to) const
{
for (BasicBlock* block = to; block; block = m_data[block].idomParent) {
if (block == from)
return true;
}
return false;
}
void Dominators::dump(PrintStream& out) const
{
if (!isValid()) {
out.print(" Not Valid.\n");
return;
}
for (BlockIndex blockIndex = 0; blockIndex < m_data.size(); ++blockIndex) {
if (m_data[blockIndex].preNumber == UINT_MAX)
continue;
out.print(" Block #", blockIndex, ": idom = ", pointerDump(m_data[blockIndex].idomParent), ", idomKids = [");
CommaPrinter comma;
for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
out.print(comma, *m_data[blockIndex].idomKids[i]);
out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
}
}
} }
#endif // ENABLE(DFG_JIT)