DFGScoreBoard.h

/*
 * Copyright (C) 2011 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. 
 */

#ifndef DFGScoreBoard_h
#define DFGScoreBoard_h

#if ENABLE(DFG_JIT)

#include <dfg/DFGGraph.h>
#include <wtf/Vector.h>

namespace JSC { namespace DFG {

// === ScoreBoard ===
//
// This class is used in performing a virtual register allocation over the graph.
// VirtualRegisters are allocated to nodes, with a used count for each virtual
// register tracking the lifespan of the value; after the final use of a node
// the VirtualRegister associated is freed such that it can be reused for
// another node.
class ScoreBoard {
public:
    ScoreBoard(Graph& graph, uint32_t firstTemporary)
        : m_graph(graph)
        , m_firstTemporary(firstTemporary)
    {
    }

#if DFG_CONSISTENCY_CHECK
    ~ScoreBoard()
    {
        // Every VirtualRegister that was allocated should now be free.
        ASSERT(m_used.size() == m_free.size());
        // Every entry in the used list should be available in the free list.
        for (size_t i = 0; i < m_used.size(); ++i)
            ASSERT(m_free.contains(i));
        // For every entry in the used list the use count of the virtual register should be zero.
        for (size_t i = 0; i < m_free.size(); ++i)
            ASSERT(!m_used[i]);
    }
#endif

    VirtualRegister allocate()
    {
        // Do we have any VirtualRegsiters in the free list, that were used by
        // prior nodes, but are now available?
        if (!m_free.isEmpty()) {
            uint32_t index = m_free.last();
            m_free.removeLast();
            // Use count must have hit zero for it to have been added to the free list!
            ASSERT(!m_used[index]);
            return (VirtualRegister)(m_firstTemporary + index);
        }

        // Allocate a new VirtualRegister, and add a corresponding entry to m_used.
        size_t next = allocatedCount();
        m_used.append(0);
        return (VirtualRegister)(m_firstTemporary + next);
    }

    // Increment the usecount for the VirtualRegsiter associated with 'child',
    // if it reaches the node's refcount, free the VirtualRegsiter.
    void use(NodeIndex child)
    {
        if (child == NoNode)
            return;

        // Find the virtual register number for this child, increment its use count.
        Node& node = m_graph[child];
        uint32_t index = node.virtualRegister() - m_firstTemporary;
        if (node.refCount() == ++m_used[index]) {
            // If the use count in the scoreboard reaches the use count for the node,
            // then this was its last use; the virtual register is now free.
            // Clear the use count & add to the free list.
            m_used[index] = 0;
            m_free.append(index);
        }
    }

    unsigned allocatedCount()
    {
        // m_used contains an entry for every allocated VirtualRegister.
        return m_used.size();
    }

#ifndef NDEBUG
    void dump()
    {
        printf("    USED: [ ");
        for (unsigned i = 0; i < m_used.size(); ++i) {
            if (!m_free.contains(i))
                printf("%d:%d ", m_firstTemporary + i, m_used[i]);
        }
        printf("]\n");

        printf("    FREE: [ ");
        for (unsigned i = 0; i < m_used.size(); ++i) {
            if (m_free.contains(i)) {
                ASSERT(!m_used[i]);
                printf("%d ", m_firstTemporary + i);
            }
        }
        printf("]\n");
    }

#endif

private:
    // The graph, so we can get refCounts for nodes, to determine when values are dead.
    Graph& m_graph;
    // The first VirtualRegsiter to be used as a temporary.
    uint32_t m_firstTemporary;
    
    // For every virtual register that has been allocated (either currently alive, or in
    // the free list), we keep a count of the number of remaining uses until it is dead
    // (0, in the case of entries in the free list). Since there is an entry for every
    // allocated VirtualRegister, the length of this array conveniently provides the
    // next available VirtualRegister number.
    Vector<uint32_t, 64> m_used;
    // A free list of VirtualRegsiters no longer alive.
    Vector<uint32_t, 64> m_free;
};

} } // namespace JSC::DFG

#endif
#endif