Imported WebKit commit 2ea9d364d0f6efa8fa64acf19f451504c59be0e4 (http://svn.webkit.org/repository/webkit/trunk@104285)

1 files changed, 383 insertions, 0 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGRegisterBank.h b/Source/JavaScriptCore/dfg/DFGRegisterBank.h
new file mode 100644
index 000000000..11cc70931
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGRegisterBank.h
@@ -0,0 +1,383 @@
+/*
+ * 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/DFGCommon.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<class BankInfo>
+class RegisterBank {
+    typedef typename BankInfo::RegisterType RegID;
+    static const size_t NUM_REGS = BankInfo::numberOfRegisters;
+
+    typedef uint32_t SpillHint;
+    static const SpillHint SpillHintInvalid = 0xffffffff;
+
+public:
+    RegisterBank()
+        : m_lastAllocated(NUM_REGS - 1)
+    {
+    }
+
+    // Attempt to allocate a register - this function finds an unlocked
+    // register, locks it, and returns it. If none can be found, this
+    // returns -1 (InvalidGPRReg or InvalidFPRReg).
+    RegID tryAllocate()
+    {
+        VirtualRegister ignored;
+        
+        for (uint32_t i = m_lastAllocated + 1; i < NUM_REGS; ++i) {
+            if (!m_data[i].lockCount && m_data[i].name == InvalidVirtualRegister)
+                return allocateInternal(i, ignored);
+        }
+        // Loop over the remaining entries.
+        for (uint32_t i = 0; i <= m_lastAllocated; ++i) {
+            if (!m_data[i].lockCount && m_data[i].name == InvalidVirtualRegister)
+                return allocateInternal(i, ignored);
+        }
+        
+        return (RegID)-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 = SpillHintInvalid;
+
+        // 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 == SpillHintInvalid)
+                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 == SpillHintInvalid)
+                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 != SpillHintInvalid);
+        // There were no available registers; currentLowest will need to be spilled.
+        return allocateInternal(currentLowest, spillMe);
+    }
+
+    // Allocates the given register, even if this will force a spill.
+    VirtualRegister allocateSpecific(RegID reg)
+    {
+        unsigned index = BankInfo::toIndex(reg);
+
+        ++m_data[index].lockCount;
+        VirtualRegister name = nameAtIndex(index);
+        if (name != InvalidVirtualRegister)
+            releaseAtIndex(index);
+        
+        return name;
+    }
+
+    // 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)
+    {
+        unsigned index = BankInfo::toIndex(reg);
+
+        // SpillHint must be valid.
+        ASSERT(spillOrder != SpillHintInvalid);
+        // 'index' must be a valid, locked register.
+        ASSERT(index < NUM_REGS);
+        ASSERT(m_data[index].lockCount);
+        // 'index' should not currently be named, the new name must be valid.
+        ASSERT(m_data[index].name == InvalidVirtualRegister);
+        ASSERT(name != InvalidVirtualRegister);
+        // 'index' should not currently have a spillOrder.
+        ASSERT(m_data[index].spillOrder == SpillHintInvalid);
+
+        m_data[index].name = name;
+        m_data[index].spillOrder = spillOrder;
+    }
+    void release(RegID reg)
+    {
+        releaseAtIndex(BankInfo::toIndex(reg));
+    }
+
+    // lock/unlock register, ensures that they are not spilled.
+    void lock(RegID reg)
+    {
+        unsigned index = BankInfo::toIndex(reg);
+
+        ASSERT(index < NUM_REGS);
+        ++m_data[index].lockCount;
+        ASSERT(m_data[index].lockCount);
+    }
+    void unlock(RegID reg)
+    {
+        unsigned index = BankInfo::toIndex(reg);
+
+        ASSERT(index < NUM_REGS);
+        ASSERT(m_data[index].lockCount);
+        --m_data[index].lockCount;
+    }
+    bool isLocked(RegID reg) const
+    {
+        return isLockedAtIndex(BankInfo::toIndex(reg));
+    }
+
+    // Get the name (VirtualRegister) associated with the
+    // given register (or InvalidVirtualRegister for none).
+    VirtualRegister name(RegID reg) const
+    {
+        return nameAtIndex(BankInfo::toIndex(reg));
+    }
+    
+#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
+
+    class iterator {
+    friend class RegisterBank<BankInfo>;
+    public:
+        VirtualRegister name() const
+        {
+            return m_bank->nameAtIndex(m_index);
+        }
+
+        bool isLocked() const
+        {
+            return m_bank->isLockedAtIndex(m_index);
+        }
+
+        void release() const
+        {
+            m_bank->releaseAtIndex(m_index);
+        }
+
+        RegID regID() const
+        {
+            return BankInfo::toRegister(m_index);
+        }
+
+#ifndef NDEBUG
+        const char* debugName() const
+        {
+            return BankInfo::debugName(regID());
+        }
+#endif
+
+        iterator& operator++()
+        {
+            ++m_index;
+            return *this;
+        }
+
+        bool operator!=(const iterator& other) const
+        {
+            ASSERT(m_bank == other.m_bank);
+            return m_index != other.m_index;
+        }
+
+        unsigned index() const
+        {
+            return m_index;
+        }
+
+    private:
+        iterator(RegisterBank<BankInfo>* bank, unsigned index)
+            : m_bank(bank)
+            , m_index(index)
+        {
+        }
+
+        RegisterBank<BankInfo>* m_bank;
+        unsigned m_index;
+    };
+
+    iterator begin()
+    {
+        return iterator(this, 0);
+    }
+
+    iterator end()
+    {
+        return iterator(this, NUM_REGS);
+    }
+
+private:
+    bool isLockedAtIndex(unsigned index) const
+    {
+        ASSERT(index < NUM_REGS);
+        return m_data[index].lockCount;
+    }
+
+    VirtualRegister nameAtIndex(unsigned index) const
+    {
+        ASSERT(index < NUM_REGS);
+        return m_data[index].name;
+    }
+
+    void releaseAtIndex(unsigned index)
+    {
+        // 'index' must be a valid register.
+        ASSERT(index < NUM_REGS);
+        // 'index' should currently be named.
+        ASSERT(m_data[index].name != InvalidVirtualRegister);
+        // 'index' should currently have a valid spill order.
+        ASSERT(m_data[index].spillOrder != SpillHintInvalid);
+
+        m_data[index].name = InvalidVirtualRegister;
+        m_data[index].spillOrder = SpillHintInvalid;
+    }
+
+    // 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();
+        // Mark the register as locked (with a lock count of 1).
+        m_data[i].lockCount = 1;
+
+        m_lastAllocated = i;
+        return BankInfo::toRegister(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(SpillHintInvalid)
+            , 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