Source/WTF/wtf/NaturalLoops.h

/*
 * 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_ENABLED) {
            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;