JavaScriptCore/dfg/DFGRegisterBank.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 DFGRegisterBank_h
#define DFGRegisterBank_h

#if ENABLE(DFG_JIT)

#include <dfg/DFGJITCompiler.h>

namespace JSC { namespace DFG {

// === RegisterBank ===
//
// This class is used to implement the GPR and FPR register banks.
// All registers have two pieces of state associated with them:
// a lock count (used to indicate this register is already in use
// in code generation of the current node, and cannot be spilled or
// allocated as a temporary), and VirtualRegister 'name', recording
// which value (if any) a machine register currently holds.
// Either or both of these pieces of information may be valid for a
// given register. A register may be:
//
//  - unlocked, and unnamed: Available for allocation.
//  - locked, but unnamed:   Already allocated as a temporary or
//                           result for the current node.
//  - unlocked, but named:   Contains the result of a prior operation,
//                           not yet in use for this node,
//  - locked, but named:     Contains the result of a prior operation,
//                           already allocated as a operand to the
//                           current operation.
//
// For every named register we also record a hint value indicating
// the order in which registers should be selected to be spilled;
// registers that can be more cheaply spilled and/or filled should
// be selected first.
//
// Locking register is a strong retention mechanism; a locked register
// will never be reallocated (this is used to ensure the operands to
// the current node are in registers). Naming, conversely, in a weak
// retention mechanism - allocating a register may force a named value
// to be spilled.
//
// All named values must be given a hint that is greater than Min and
// less than Max.
template<typename RegID, size_t NUM_REGS, typename SpillHint, SpillHint SpillHintMin, SpillHint SpillHintMax>
class RegisterBank {
public:
    RegisterBank()
        : m_lastAllocated(NUM_REGS - 1)
    {
    }

    // Allocate a register - this function finds an unlocked register,
    // locks it, and returns it. If any named registers exist, one
    // of these should be selected to be allocated. If all unlocked
    // registers are named, then one of the named registers will need
    // to be spilled. In this case the register selected to be spilled
    // will be one of the registers that has the lowest 'spillOrder'
    // cost associated with it.
    //
    // This method select the register to be allocated, and calls the
    // private 'allocateInternal' method to update internal data
    // structures accordingly.
    RegID allocate(VirtualRegister &spillMe)
    {
        uint32_t currentLowest = NUM_REGS;
        SpillHint currentSpillOrder = SpillHintMax;

        // Scan through all register, starting at the last allocated & looping around.
        ASSERT(m_lastAllocated < NUM_REGS);

        // This loop is broken into two halves, looping from the last allocated
        // register (the register returned last time this method was called) to
        // the maximum register value, then from 0 to the last allocated.
        // This implements a simple round-robin like approach to try to reduce
        // thrash, and minimize time spent scanning locked registers in allocation.
        // If a unlocked and unnamed register is found return it immediately.
        // Otherwise, find the first unlocked register with the lowest spillOrder.
        for (uint32_t i = m_lastAllocated + 1; i < NUM_REGS; ++i) {
            // (1) If the current register is locked, it is not a candidate.
            if (m_data[i].lockCount)
                continue;
            // (2) If the current register's spill order is 0, pick this! – unassigned registers have spill order 0.
            SpillHint spillOrder = m_data[i].spillOrder;
            if (!spillOrder)
                return allocateInternal(i, spillMe);
            // If this register is better (has a lower spill order value) than any prior
            // candidate, then record it.
            if (spillOrder < currentSpillOrder) {
                currentSpillOrder = spillOrder;
                currentLowest = i;
            }
        }
        // Loop over the remaining entries.
        for (uint32_t i = 0; i <= m_lastAllocated; ++i) {
            if (m_data[i].lockCount)
                continue;
            SpillHint spillOrder = m_data[i].spillOrder;
            if (!spillOrder)
                return allocateInternal(i, spillMe);
            if (spillOrder < currentSpillOrder) {
                currentSpillOrder = spillOrder;
                currentLowest = i;
            }
        }

        // Deadlock check - this could only occur is all registers are locked!
        ASSERT(currentLowest != NUM_REGS && currentSpillOrder != SpillHintMax);
        // There were no available registers; currentLowest will need to be spilled.
        return allocateInternal(currentLowest, spillMe);
    }

    // retain/release - these methods are used to associate/disassociate names
    // with values in registers. retain should only be called on locked registers.
    void retain(RegID reg, VirtualRegister name, SpillHint spillOrder)
    {
        // 'reg' must be a valid, locked register.
        ASSERT(reg < NUM_REGS);
        ASSERT(m_data[reg].lockCount);
        // 'reg' should not currently be named, the new name must be valid.
        ASSERT(m_data[reg].name == InvalidVirtualRegister);
        ASSERT(name != InvalidVirtualRegister);
        // 'reg' should not currently have a spillOrder, the new spill order must be valid.
        ASSERT(spillOrder && spillOrder < SpillHintMax);
        ASSERT(m_data[reg].spillOrder == SpillHintMin);

        m_data[reg].name = name;
        m_data[reg].spillOrder = spillOrder;
    }
    void release(RegID reg)
    {
        // 'reg' must be a valid register.
        ASSERT(reg < NUM_REGS);
        // 'reg' should currently be named.
        ASSERT(m_data[reg].name != InvalidVirtualRegister);
        // 'reg' should currently have a valid spill order.
        ASSERT(m_data[reg].spillOrder > SpillHintMin && m_data[reg].spillOrder < SpillHintMax);

        m_data[reg].name = InvalidVirtualRegister;
        m_data[reg].spillOrder = SpillHintMin;
    }

    // lock/unlock register, ensures that they are not spilled.
    void lock(RegID reg)
    {
        ASSERT(reg < NUM_REGS);
        ++m_data[reg].lockCount;
        ASSERT(m_data[reg].lockCount);
    }
    void unlock(RegID reg)
    {
        ASSERT(reg < NUM_REGS);
        ASSERT(m_data[reg].lockCount);
        --m_data[reg].lockCount;
    }
    bool isLocked(RegID reg)
    {
        ASSERT(reg < NUM_REGS);
        return m_data[reg].lockCount;
    }

    // Get the name (VirtualRegister) associated with the
    // given register (or InvalidVirtualRegister for none).
    VirtualRegister name(RegID reg)
    {
        ASSERT(reg < NUM_REGS);
        return m_data[reg].name;
    }

#ifndef NDEBUG
    void dump()
    {
        // For each register, print the VirtualRegister 'name'.
        for (uint32_t i =0; i < NUM_REGS; ++i) {
            if (m_data[i].name != InvalidVirtualRegister)
                fprintf(stderr, "[%02d]", m_data[i].name);
            else
                fprintf(stderr, "[--]");
        }
        fprintf(stderr, "\n");
    }
#endif

private:
    // Used by 'allocate', above, to update inforamtion in the map.
    RegID allocateInternal(uint32_t i, VirtualRegister &spillMe)
    {
        // 'i' must be a valid, unlocked register.
        ASSERT(i < NUM_REGS && !m_data[i].lockCount);

        // Return the VirtualRegister of the named value currently stored in
        // the register being returned - or InvalidVirtualRegister if none.
        spillMe = m_data[i].name;

        // Clear any name/spillOrder currently associated with the register,
        m_data[i] = MapEntry();
        m_data[i].lockCount = 1;
        // Mark the register as locked (with a lock count of 1).
        m_lastAllocated = i;
        return (RegID)i;
    }

    // === MapEntry ===
    //
    // This structure provides information for an individual machine register
    // being managed by the RegisterBank. For each register we track a lock
    // count, name and spillOrder hint.
    struct MapEntry {
        MapEntry()
            : name(InvalidVirtualRegister)
            , spillOrder(SpillHintMin)
            , lockCount(0)
        {
        }

        VirtualRegister name;
        SpillHint spillOrder;
        uint32_t lockCount;
    };

    // Holds the current status of all registers.
    MapEntry m_data[NUM_REGS];
    // Used to to implement a simple round-robin like allocation scheme.
    uint32_t m_lastAllocated;
};

} } // namespace JSC::DFG

#endif
#endif