Source/JavaScriptCore/dfg/DFGRegisterBank.h - platform/external/webkit - Git at Google

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