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