blob: 7da0f8458644d2f8c8ea6c602a5072ad186b1c3c [file] [log] [blame]
/*
* Copyright (C) 2013-2019 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/Dominators.h>
namespace WTF {
template<typename Graph>
class NaturalLoops;
template<typename Graph>
class NaturalLoop {
WTF_MAKE_FAST_ALLOCATED;
public:
NaturalLoop()
: m_graph(nullptr)
, m_header(nullptr)
, m_outerLoopIndex(UINT_MAX)
{
}
NaturalLoop(Graph& graph, typename Graph::Node header, unsigned index)
: m_graph(&graph)
, m_header(header)
, m_outerLoopIndex(UINT_MAX)
, m_index(index)
{
}
Graph* graph() const { return m_graph; }
typename Graph::Node header() const { return m_header; }
unsigned size() const { return m_body.size(); }
typename Graph::Node at(unsigned i) const { return m_body[i]; }
typename Graph::Node operator[](unsigned i) const { return at(i); }
// This is the slower, but simpler, way of asking if a block belongs to
// a natural loop. It's faster to call NaturalLoops::belongsTo(), which
// tries to be O(loop depth) rather than O(loop size). Loop depth is
// almost always smaller than loop size. A *lot* smaller.
bool contains(typename Graph::Node block) const
{
for (unsigned i = m_body.size(); i--;) {
if (m_body[i] == block)
return true;
}
ASSERT(block != header()); // Header should be contained.
return false;
}
// The index of this loop in NaturalLoops.
unsigned index() const { return m_index; }
bool isOuterMostLoop() const { return m_outerLoopIndex == UINT_MAX; }
void dump(PrintStream& out) const
{
if (!m_graph) {
out.print("<null>");
return;
}
out.print("[Header: ", m_graph->dump(header()), ", Body:");
for (unsigned i = 0; i < m_body.size(); ++i)
out.print(" ", m_graph->dump(m_body[i]));
out.print("]");
}
private:
template<typename>
friend class NaturalLoops;
void addBlock(typename Graph::Node block)
{
ASSERT(!m_body.contains(block)); // The NaturalLoops algorithm relies on blocks being unique in this vector.
m_body.append(block);
}
Graph* m_graph;
typename Graph::Node m_header;
Vector<typename Graph::Node, 4> m_body;
unsigned m_outerLoopIndex;
unsigned m_index;
};
template<typename Graph>
class NaturalLoops {
WTF_MAKE_FAST_ALLOCATED;
public:
typedef std::array<unsigned, 2> InnerMostLoopIndices;
NaturalLoops(Graph& graph, Dominators<Graph>& dominators, bool selfCheck = false)
: m_graph(graph)
, m_innerMostLoopIndices(graph.template newMap<InnerMostLoopIndices>())
{
// Implement the classic dominator-based natural loop finder. The first
// step is to find all control flow edges A -> B where B dominates A.
// Then B is a loop header and A is a backward branching block. We will
// then accumulate, for each loop header, multiple backward branching
// blocks. Then we backwards graph search from the backward branching
// blocks to their loop headers, which gives us all of the blocks in the
// loop body.
static constexpr bool verbose = false;
if (verbose) {
dataLog("Dominators:\n");
dominators.dump(WTF::dataFile());
}
m_loops.shrink(0);
for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
typename Graph::Node header = graph.node(blockIndex);
if (!header)
continue;
for (unsigned i = graph.predecessors(header).size(); i--;) {
typename Graph::Node footer = graph.predecessors(header)[i];
if (!dominators.dominates(header, footer))
continue;
// At this point, we've proven 'header' is actually a loop header and
// that 'footer' is a loop footer.
bool found = false;
for (unsigned j = m_loops.size(); j--;) {
if (m_loops[j].header() == header) {
m_loops[j].addBlock(footer);
found = true;
break;
}
}
if (found)
continue;
NaturalLoop<Graph> loop(graph, header, m_loops.size());
loop.addBlock(footer);
m_loops.append(loop);
}
}
if (verbose)
dataLog("After bootstrap: ", *this, "\n");
FastBitVector seenBlocks;
Vector<typename Graph::Node, 4> blockWorklist;
seenBlocks.resize(graph.numNodes());
for (unsigned i = m_loops.size(); i--;) {
NaturalLoop<Graph>& loop = m_loops[i];
seenBlocks.clearAll();
ASSERT(blockWorklist.isEmpty());
if (verbose)
dataLog("Dealing with loop ", loop, "\n");
for (unsigned j = loop.size(); j--;) {
seenBlocks[graph.index(loop[j])] = true;
blockWorklist.append(loop[j]);
}
while (!blockWorklist.isEmpty()) {
typename Graph::Node block = blockWorklist.takeLast();
if (verbose)
dataLog(" Dealing with ", graph.dump(block), "\n");
if (block == loop.header())
continue;
for (unsigned j = graph.predecessors(block).size(); j--;) {
typename Graph::Node predecessor = graph.predecessors(block)[j];
if (seenBlocks[graph.index(predecessor)])
continue;
loop.addBlock(predecessor);
blockWorklist.append(predecessor);
seenBlocks[graph.index(predecessor)] = true;
}
}
}
// Figure out reverse mapping from blocks to loops.
for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
typename Graph::Node block = graph.node(blockIndex);
if (!block)
continue;
for (unsigned i = std::tuple_size<InnerMostLoopIndices>::value; i--;)
m_innerMostLoopIndices[block][i] = UINT_MAX;
}
for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
NaturalLoop<Graph>& loop = m_loops[loopIndex];
for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
typename Graph::Node block = loop[blockIndexInLoop];
for (unsigned i = 0; i < std::tuple_size<InnerMostLoopIndices>::value; ++i) {
unsigned thisIndex = m_innerMostLoopIndices[block][i];
if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
insertIntoBoundedVector(
m_innerMostLoopIndices[block], std::tuple_size<InnerMostLoopIndices>::value,
loopIndex, i);
break;
}
}
}
}
// Now each block knows its inner-most loop and its next-to-inner-most loop. Use
// this to figure out loop parenting.
for (unsigned i = m_loops.size(); i--;) {
NaturalLoop<Graph>& loop = m_loops[i];
RELEASE_ASSERT(m_innerMostLoopIndices[loop.header()][0] == i);
loop.m_outerLoopIndex = m_innerMostLoopIndices[loop.header()][1];
}
if (selfCheck) {
// Do some self-verification that we've done some of this correctly.
for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
typename Graph::Node block = graph.node(blockIndex);
if (!block)
continue;
Vector<const NaturalLoop<Graph>*> simpleLoopsOf;
for (unsigned i = m_loops.size(); i--;) {
if (m_loops[i].contains(block))
simpleLoopsOf.append(&m_loops[i]);
}
Vector<const NaturalLoop<Graph>*> 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");
}
Graph& graph() { return m_graph; }
unsigned numLoops() const
{
return m_loops.size();
}
const NaturalLoop<Graph>& loop(unsigned i) const
{
return m_loops[i];
}
// Return either null if the block isn't a loop header, or the
// loop it belongs to.
const NaturalLoop<Graph>* headerOf(typename Graph::Node block) const
{
const NaturalLoop<Graph>* loop = innerMostLoopOf(block);
if (!loop)
return nullptr;
if (loop->header() == block)
return loop;
if (!ASSERT_DISABLED) {
for (; loop; loop = innerMostOuterLoop(*loop))
ASSERT(loop->header() != block);
}
return nullptr;
}
const NaturalLoop<Graph>* innerMostLoopOf(typename Graph::Node block) const
{
unsigned index = m_innerMostLoopIndices[block][0];
if (index == UINT_MAX)
return nullptr;
return &m_loops[index];
}
const NaturalLoop<Graph>* innerMostOuterLoop(const NaturalLoop<Graph>& loop) const
{
if (loop.m_outerLoopIndex == UINT_MAX)
return nullptr;
return &m_loops[loop.m_outerLoopIndex];
}
bool belongsTo(typename Graph::Node block, const NaturalLoop<Graph>& candidateLoop) const
{
// It's faster to do this test using the loop itself, if it's small.
if (candidateLoop.size() < 4)
return candidateLoop.contains(block);
for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
if (loop == &candidateLoop)
return true;
}
return false;
}
unsigned loopDepth(typename Graph::Node block) const
{
unsigned depth = 0;
for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
depth++;
return depth;
}
// Return all loops this belongs to. The first entry in the vector is the innermost loop. The last is the
// outermost loop.
Vector<const NaturalLoop<Graph>*> loopsOf(typename Graph::Node block) const
{
Vector<const NaturalLoop<Graph>*> result;
for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
result.append(loop);
return result;
}
void 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("}");
}
private:
Graph& m_graph;
// If we ever had a scalability problem in our natural loop finder, we could
// use some HashMap's here. But it just feels a heck of a lot less convenient.
Vector<NaturalLoop<Graph>, 4> m_loops;
typename Graph::template Map<InnerMostLoopIndices> m_innerMostLoopIndices;
};
} // namespace WTF
using WTF::NaturalLoop;
using WTF::NaturalLoops;