DFGNaturalLoops.cpp [plain text]
#include "config.h"
#include "DFGNaturalLoops.h"
#if ENABLE(DFG_JIT)
#include "DFGGraph.h"
#include "JSCInlines.h"
#include <wtf/CommaPrinter.h>
namespace JSC { namespace DFG {
void NaturalLoop::dump(PrintStream& out) const
{
out.print("[Header: ", *header(), ", Body:");
for (unsigned i = 0; i < m_body.size(); ++i)
out.print(" ", *m_body[i]);
out.print("]");
}
NaturalLoops::NaturalLoops() { }
NaturalLoops::~NaturalLoops() { }
void NaturalLoops::compute(Graph& graph)
{
static const bool verbose = false;
graph.m_dominators.computeIfNecessary(graph);
if (verbose) {
dataLog("Dominators:\n");
graph.m_dominators.dump(graph, WTF::dataFile());
}
m_loops.resize(0);
for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
BasicBlock* block = graph.block(blockIndex);
if (!block)
continue;
for (unsigned i = block->numSuccessors(); i--;) {
BasicBlock* successor = block->successor(i);
if (!graph.m_dominators.dominates(successor, block))
continue;
bool found = false;
for (unsigned j = m_loops.size(); j--;) {
if (m_loops[j].header() == successor) {
m_loops[j].addBlock(block);
found = true;
break;
}
}
if (found)
continue;
NaturalLoop loop(successor, m_loops.size());
loop.addBlock(block);
m_loops.append(loop);
}
}
if (verbose)
dataLog("After bootstrap: ", *this, "\n");
FastBitVector seenBlocks;
Vector<BasicBlock*, 4> blockWorklist;
seenBlocks.resize(graph.numBlocks());
for (unsigned i = m_loops.size(); i--;) {
NaturalLoop& loop = m_loops[i];
seenBlocks.clearAll();
ASSERT(blockWorklist.isEmpty());
if (verbose)
dataLog("Dealing with loop ", loop, "\n");
for (unsigned j = loop.size(); j--;) {
seenBlocks.set(loop[j]->index);
blockWorklist.append(loop[j]);
}
while (!blockWorklist.isEmpty()) {
BasicBlock* block = blockWorklist.takeLast();
if (verbose)
dataLog(" Dealing with ", *block, "\n");
if (block == loop.header())
continue;
for (unsigned j = block->predecessors.size(); j--;) {
BasicBlock* predecessor = block->predecessors[j];
if (seenBlocks.get(predecessor->index))
continue;
loop.addBlock(predecessor);
blockWorklist.append(predecessor);
seenBlocks.set(predecessor->index);
}
}
}
for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
BasicBlock* block = graph.block(blockIndex);
if (!block)
continue;
for (unsigned i = BasicBlock::numberOfInnerMostLoopIndices; i--;)
block->innerMostLoopIndices[i] = UINT_MAX;
}
for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
NaturalLoop& loop = m_loops[loopIndex];
for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
BasicBlock* block = loop[blockIndexInLoop];
for (unsigned i = 0; i < BasicBlock::numberOfInnerMostLoopIndices; ++i) {
unsigned thisIndex = block->innerMostLoopIndices[i];
if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
insertIntoBoundedVector(
block->innerMostLoopIndices, BasicBlock::numberOfInnerMostLoopIndices,
loopIndex, i);
break;
}
}
}
}
for (unsigned i = m_loops.size(); i--;) {
NaturalLoop& loop = m_loops[i];
RELEASE_ASSERT(loop.header()->innerMostLoopIndices[0] == i);
loop.m_outerLoopIndex = loop.header()->innerMostLoopIndices[1];
}
if (validationEnabled()) {
for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
BasicBlock* block = graph.block(blockIndex);
if (!block)
continue;
Vector<const NaturalLoop*> simpleLoopsOf;
for (unsigned i = m_loops.size(); i--;) {
if (m_loops[i].contains(block))
simpleLoopsOf.append(&m_loops[i]);
}
Vector<const NaturalLoop*> fancyLoopsOf = loopsOf(block);
std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
RELEASE_ASSERT(simpleLoopsOf == fancyLoopsOf);
}
}
if (verbose)
dataLog("Results: ", *this, "\n");
}
Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
{
Vector<const NaturalLoop*> result;
for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
result.append(loop);
return result;
}
void NaturalLoops::dump(PrintStream& out) const
{
out.print("NaturalLoops:{");
CommaPrinter comma;
for (unsigned i = 0; i < m_loops.size(); ++i)
out.print(comma, m_loops[i]);
out.print("}");
}
} }
#endif // ENABLE(DFG_JIT)