diff options
Diffstat (limited to 'Source/JavaScriptCore/dfg/DFGRegisterBank.h')
-rw-r--r-- | Source/JavaScriptCore/dfg/DFGRegisterBank.h | 253 |
1 files changed, 253 insertions, 0 deletions
diff --git a/Source/JavaScriptCore/dfg/DFGRegisterBank.h b/Source/JavaScriptCore/dfg/DFGRegisterBank.h new file mode 100644 index 0000000..575e6b7 --- /dev/null +++ b/Source/JavaScriptCore/dfg/DFGRegisterBank.h @@ -0,0 +1,253 @@ +/* + * 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 |