Source/WTF/wtf/NaturalLoops.h - WebKit - Git at Google

 /*
  * 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;
	/*
	* 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;