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