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 "DFGGraph.h" 32#include <wtf/BitVector.h> 33#include <wtf/Vector.h> 34 35namespace JSC { namespace DFG { 36 37// === ScoreBoard === 38// 39// This class is used in performing a virtual register allocation over the graph. 40// VirtualRegisters are allocated to nodes, with a used count for each virtual 41// register tracking the lifespan of the value; after the final use of a node 42// the VirtualRegister associated is freed such that it can be reused for 43// another node. 44class ScoreBoard { 45public: 46 ScoreBoard(unsigned nextMachineLocal) 47 : m_highWatermark(nextMachineLocal + 1) 48 { 49 m_used.fill(max(), nextMachineLocal); 50 m_free.reserveCapacity(nextMachineLocal); 51 } 52 53 ~ScoreBoard() 54 { 55 assertClear(); 56 } 57 58 void assertClear() 59 { 60#if !ASSERT_DISABLED 61 // For every entry in the used list the use count of the virtual register should be zero, or max, due to it being a preserved local. 62 for (size_t i = 0; i < m_used.size(); ++i) 63 ASSERT(!m_used[i] || m_used[i] == max()); 64 // For every entry in the free list, the use count should be zero. 65 for (size_t i = 0; i < m_free.size(); ++i) 66 ASSERT(!m_used[m_free[i]]); 67 // There must not be duplicates in the free list. 68 for (size_t i = 0; i < m_free.size(); ++i) { 69 for (size_t j = i + 1; j < m_free.size(); ++j) 70 ASSERT(m_free[i] != m_free[j]); 71 } 72#endif 73 } 74 75 VirtualRegister allocate() 76 { 77 // Do we have any VirtualRegsiters in the free list, that were used by 78 // prior nodes, but are now available? 79 if (!m_free.isEmpty()) { 80 uint32_t index = m_free.last(); 81 m_free.removeLast(); 82 // Use count must have hit zero for it to have been added to the free list! 83 ASSERT(!m_used[index]); 84 m_highWatermark = std::max(m_highWatermark, static_cast<unsigned>(index) + 1); 85 return virtualRegisterForLocal(index); 86 } 87 88 // Allocate a new VirtualRegister, and add a corresponding entry to m_used. 89 size_t next = m_used.size(); 90 m_used.append(0); 91 m_highWatermark = std::max(m_highWatermark, static_cast<unsigned>(next) + 1); 92 return virtualRegisterForLocal(next); 93 } 94 95 // Increment the usecount for the VirtualRegister associated with 'child', 96 // if it reaches the node's refcount, free the VirtualRegister. 97 void use(Node* child) 98 { 99 if (!child) 100 return; 101 102 // Find the virtual register number for this child, increment its use count. 103 uint32_t index = child->virtualRegister().toLocal(); 104 ASSERT(m_used[index] != max()); 105 if (child->refCount() == ++m_used[index]) { 106 // If the use count in the scoreboard reaches the use count for the node, 107 // then this was its last use; the virtual register is now free. 108 // Clear the use count & add to the free list. 109 m_used[index] = 0; 110 m_free.append(index); 111 } 112 } 113 void use(Edge child) 114 { 115 use(child.node()); 116 } 117 118 void useIfHasResult(Edge child) 119 { 120 if (!child) 121 return; 122 if (!child->hasResult()) 123 return; 124 use(child); 125 } 126 127 unsigned highWatermark() 128 { 129 return m_highWatermark; 130 } 131 132#ifndef NDEBUG 133 void dump() 134 { 135 dataLogF(" USED: [ "); 136 for (unsigned i = 0; i < m_used.size(); ++i) { 137 if (!m_free.contains(i)) { 138 dataLogF("%d:", i); 139 if (m_used[i] == max()) 140 dataLogF("local "); 141 else 142 dataLogF("%d ", m_used[i]); 143 } 144 } 145 dataLogF("]\n"); 146 147 dataLogF(" FREE: [ "); 148 for (unsigned i = 0; i < m_used.size(); ++i) { 149 if (m_free.contains(i) && m_used[i] != max()) { 150 ASSERT(!m_used[i]); 151 dataLogF("%d ", i); 152 } 153 } 154 dataLogF("]\n"); 155 } 156 157#endif 158 159private: 160 static uint32_t max() { return std::numeric_limits<uint32_t>::max(); } 161 162 // The size of the span of virtual registers that this code block will use. 163 unsigned m_highWatermark; 164 165 // For every virtual register that has been allocated (either currently alive, or in 166 // the free list), we keep a count of the number of remaining uses until it is dead 167 // (0, in the case of entries in the free list). Since there is an entry for every 168 // allocated VirtualRegister, the length of this array conveniently provides the 169 // next available VirtualRegister number. 170 Vector<uint32_t, 64> m_used; 171 // A free list of VirtualRegsiters no longer alive. 172 Vector<uint32_t, 64> m_free; 173}; 174 175} } // namespace JSC::DFG 176 177#endif 178#endif 179