1 /* 2 * Copyright (C) 2011 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #ifndef DFGScoreBoard_h 27 #define DFGScoreBoard_h 28 29 #if ENABLE(DFG_JIT) 30 31 #include <dfg/DFGGraph.h> 32 #include <wtf/Vector.h> 33 34 namespace JSC { namespace DFG { 35 36 // === ScoreBoard === 37 // 38 // This class is used in performing a virtual register allocation over the graph. 39 // VirtualRegisters are allocated to nodes, with a used count for each virtual 40 // register tracking the lifespan of the value; after the final use of a node 41 // the VirtualRegister associated is freed such that it can be reused for 42 // another node. 43 class ScoreBoard { 44 public: ScoreBoard(Graph & graph,uint32_t firstTemporary)45 ScoreBoard(Graph& graph, uint32_t firstTemporary) 46 : m_graph(graph) 47 , m_firstTemporary(firstTemporary) 48 { 49 } 50 51 #if DFG_CONSISTENCY_CHECK ~ScoreBoard()52 ~ScoreBoard() 53 { 54 // Every VirtualRegister that was allocated should now be free. 55 ASSERT(m_used.size() == m_free.size()); 56 // For every entry in the free list, the use count of the virtual register should be zero. 57 // * By using the virtual register numbers from m_free, we are checking that all values 58 // in m_free are < m_used.size(), and correspond to an allocated VirtualRegsiter. 59 // * By setting m_used to a non-zero value after checking it, we are checking that all 60 // entries in m_free are unique (otherwise the second test of m_used will fail). 61 for (size_t i = 0; i < m_free.size(); ++i) { 62 uint32_t virtualRegister = m_free[i]; 63 ASSERT(!m_used[virtualRegister]); 64 m_used[virtualRegister] = 1; 65 } 66 } 67 #endif 68 allocate()69 VirtualRegister allocate() 70 { 71 // Do we have any VirtualRegsiters in the free list, that were used by 72 // prior nodes, but are now available? 73 if (!m_free.isEmpty()) { 74 uint32_t index = m_free.last(); 75 m_free.removeLast(); 76 // Use count must have hit zero for it to have been added to the free list! 77 ASSERT(!m_used[index]); 78 return (VirtualRegister)(m_firstTemporary + index); 79 } 80 81 // Allocate a new VirtualRegister, and add a corresponding entry to m_used. 82 size_t next = allocatedCount(); 83 m_used.append(0); 84 return (VirtualRegister)(m_firstTemporary + next); 85 } 86 87 // Increment the usecount for the VirtualRegsiter associated with 'child', 88 // if it reaches the node's refcount, free the VirtualRegsiter. use(NodeIndex child)89 void use(NodeIndex child) 90 { 91 if (child == NoNode) 92 return; 93 94 // Find the virtual register number for this child, increment its use count. 95 Node& node = m_graph[child]; 96 uint32_t index = node.virtualRegister - m_firstTemporary; 97 if (node.refCount == ++m_used[index]) { 98 // If the use count in the scoreboard reaches the use count for the node, 99 // then this was its last use; the virtual register is now free. 100 // Clear the use count & add to the free list. 101 m_used[index] = 0; 102 m_free.append(index); 103 } 104 } 105 allocatedCount()106 unsigned allocatedCount() 107 { 108 // m_used contains an entry for every allocated VirtualRegister. 109 return m_used.size(); 110 } 111 112 private: 113 // The graph, so we can get refCounts for nodes, to determine when values are dead. 114 Graph& m_graph; 115 // The first VirtualRegsiter to be used as a temporary. 116 uint32_t m_firstTemporary; 117 118 // For every virtual register that has been allocated (either currently alive, or in 119 // the free list), we keep a count of the number of remaining uses until it is dead 120 // (0, in the case of entries in the free list). Since there is an entry for every 121 // allocated VirtualRegister, the length of this array conveniently provides the 122 // next available VirtualRegister number. 123 Vector<uint32_t, 64> m_used; 124 // A free list of VirtualRegsiters no longer alive. 125 Vector<uint32_t, 64> m_free; 126 }; 127 128 } } // namespace JSC::DFG 129 130 #endif 131 #endif 132