/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
#pragma once

#if ENABLE(DFG_JIT)

#include "DFGBasicBlock.h"
#include "DFGCommon.h"
#include "DFGDominators.h"
#include <wtf/FastMalloc.h>
#include <wtf/Noncopyable.h>

namespace JSC { namespace DFG {

class NaturalLoops;

class NaturalLoop {
public:
    NaturalLoop()
        : m_header(0)
        , m_outerLoopIndex(UINT_MAX)
    {
    }
    
    NaturalLoop(BasicBlock* header, unsigned index)
        : m_header(header)
        , m_outerLoopIndex(UINT_MAX)
        , m_index(index)
    {
    }
    
    BasicBlock* header() const { return m_header; }
    
    unsigned size() const { return m_body.size(); }
    BasicBlock* at(unsigned i) const { return m_body[i]; }
    BasicBlock* 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(BasicBlock* 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&) const;
private:
    friend class NaturalLoops;
    
    void addBlock(BasicBlock* block) { m_body.append(block); }
    
    BasicBlock* m_header;
    Vector<BasicBlock*, 4> m_body;
    unsigned m_outerLoopIndex;
    unsigned m_index;
};

class NaturalLoops {
    WTF_MAKE_NONCOPYABLE(NaturalLoops);
    WTF_MAKE_FAST_ALLOCATED;
public:
    NaturalLoops(Graph&);
    ~NaturalLoops();
    
    unsigned numLoops() const
    {
        return m_loops.size();
    }
    const NaturalLoop& 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* headerOf(BasicBlock* block) const
    {
        const NaturalLoop* loop = innerMostLoopOf(block);
        if (!loop)
            return 0;
        if (loop->header() == block)
            return loop;
        if (!ASSERT_DISABLED) {
            for (; loop; loop = innerMostOuterLoop(*loop))
                ASSERT(loop->header() != block);
        }
        return 0;
    }
    
    const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
    {
        unsigned index = block->innerMostLoopIndices[0];
        if (index == UINT_MAX)
            return 0;
        return &m_loops[index];
    }
    
    const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const
    {
        if (loop.m_outerLoopIndex == UINT_MAX)
            return 0;
        return &m_loops[loop.m_outerLoopIndex];
    }
    
    bool belongsTo(BasicBlock* block, const NaturalLoop& 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* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
            if (loop == &candidateLoop)
                return true;
        }
        return false;
    }
    
    unsigned loopDepth(BasicBlock* block) const
    {
        unsigned depth = 0;
        for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
            depth++;
        return depth;
    }
    
    // Return the indices of all loops this belongs to.
    Vector<const NaturalLoop*> loopsOf(BasicBlock*) const;

    void dump(PrintStream&) const;
private:
    // 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, 4> m_loops;
};

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)