12bde8e466a4451c7319e3a072d118917957d6554Steve Block/* 22bde8e466a4451c7319e3a072d118917957d6554Steve Block * Copyright (C) 2011 Apple Inc. All rights reserved. 32bde8e466a4451c7319e3a072d118917957d6554Steve Block * 42bde8e466a4451c7319e3a072d118917957d6554Steve Block * Redistribution and use in source and binary forms, with or without 52bde8e466a4451c7319e3a072d118917957d6554Steve Block * modification, are permitted provided that the following conditions 62bde8e466a4451c7319e3a072d118917957d6554Steve Block * are met: 72bde8e466a4451c7319e3a072d118917957d6554Steve Block * 1. Redistributions of source code must retain the above copyright 82bde8e466a4451c7319e3a072d118917957d6554Steve Block * notice, this list of conditions and the following disclaimer. 92bde8e466a4451c7319e3a072d118917957d6554Steve Block * 2. Redistributions in binary form must reproduce the above copyright 102bde8e466a4451c7319e3a072d118917957d6554Steve Block * notice, this list of conditions and the following disclaimer in the 112bde8e466a4451c7319e3a072d118917957d6554Steve Block * documentation and/or other materials provided with the distribution. 122bde8e466a4451c7319e3a072d118917957d6554Steve Block * 132bde8e466a4451c7319e3a072d118917957d6554Steve Block * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 142bde8e466a4451c7319e3a072d118917957d6554Steve Block * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 152bde8e466a4451c7319e3a072d118917957d6554Steve Block * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 162bde8e466a4451c7319e3a072d118917957d6554Steve Block * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 172bde8e466a4451c7319e3a072d118917957d6554Steve Block * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 182bde8e466a4451c7319e3a072d118917957d6554Steve Block * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 192bde8e466a4451c7319e3a072d118917957d6554Steve Block * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 202bde8e466a4451c7319e3a072d118917957d6554Steve Block * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 212bde8e466a4451c7319e3a072d118917957d6554Steve Block * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 222bde8e466a4451c7319e3a072d118917957d6554Steve Block * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 232bde8e466a4451c7319e3a072d118917957d6554Steve Block * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 242bde8e466a4451c7319e3a072d118917957d6554Steve Block */ 252bde8e466a4451c7319e3a072d118917957d6554Steve Block 262bde8e466a4451c7319e3a072d118917957d6554Steve Block#ifndef DFGScoreBoard_h 272bde8e466a4451c7319e3a072d118917957d6554Steve Block#define DFGScoreBoard_h 282bde8e466a4451c7319e3a072d118917957d6554Steve Block 292bde8e466a4451c7319e3a072d118917957d6554Steve Block#if ENABLE(DFG_JIT) 302bde8e466a4451c7319e3a072d118917957d6554Steve Block 312bde8e466a4451c7319e3a072d118917957d6554Steve Block#include <dfg/DFGGraph.h> 322bde8e466a4451c7319e3a072d118917957d6554Steve Block#include <wtf/Vector.h> 332bde8e466a4451c7319e3a072d118917957d6554Steve Block 342bde8e466a4451c7319e3a072d118917957d6554Steve Blocknamespace JSC { namespace DFG { 352bde8e466a4451c7319e3a072d118917957d6554Steve Block 362bde8e466a4451c7319e3a072d118917957d6554Steve Block// === ScoreBoard === 372bde8e466a4451c7319e3a072d118917957d6554Steve Block// 382bde8e466a4451c7319e3a072d118917957d6554Steve Block// This class is used in performing a virtual register allocation over the graph. 392bde8e466a4451c7319e3a072d118917957d6554Steve Block// VirtualRegisters are allocated to nodes, with a used count for each virtual 402bde8e466a4451c7319e3a072d118917957d6554Steve Block// register tracking the lifespan of the value; after the final use of a node 412bde8e466a4451c7319e3a072d118917957d6554Steve Block// the VirtualRegister associated is freed such that it can be reused for 422bde8e466a4451c7319e3a072d118917957d6554Steve Block// another node. 432bde8e466a4451c7319e3a072d118917957d6554Steve Blockclass ScoreBoard { 442bde8e466a4451c7319e3a072d118917957d6554Steve Blockpublic: 452daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch ScoreBoard(Graph& graph, uint32_t firstTemporary) 462bde8e466a4451c7319e3a072d118917957d6554Steve Block : m_graph(graph) 472daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch , m_firstTemporary(firstTemporary) 482bde8e466a4451c7319e3a072d118917957d6554Steve Block { 492bde8e466a4451c7319e3a072d118917957d6554Steve Block } 502bde8e466a4451c7319e3a072d118917957d6554Steve Block 512bde8e466a4451c7319e3a072d118917957d6554Steve Block#if DFG_CONSISTENCY_CHECK 522bde8e466a4451c7319e3a072d118917957d6554Steve Block ~ScoreBoard() 532bde8e466a4451c7319e3a072d118917957d6554Steve Block { 542bde8e466a4451c7319e3a072d118917957d6554Steve Block // Every VirtualRegister that was allocated should now be free. 552bde8e466a4451c7319e3a072d118917957d6554Steve Block ASSERT(m_used.size() == m_free.size()); 562bde8e466a4451c7319e3a072d118917957d6554Steve Block // For every entry in the free list, the use count of the virtual register should be zero. 572bde8e466a4451c7319e3a072d118917957d6554Steve Block // * By using the virtual register numbers from m_free, we are checking that all values 582bde8e466a4451c7319e3a072d118917957d6554Steve Block // in m_free are < m_used.size(), and correspond to an allocated VirtualRegsiter. 592bde8e466a4451c7319e3a072d118917957d6554Steve Block // * By setting m_used to a non-zero value after checking it, we are checking that all 602bde8e466a4451c7319e3a072d118917957d6554Steve Block // entries in m_free are unique (otherwise the second test of m_used will fail). 612bde8e466a4451c7319e3a072d118917957d6554Steve Block for (size_t i = 0; i < m_free.size(); ++i) { 622daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch uint32_t virtualRegister = m_free[i]; 632bde8e466a4451c7319e3a072d118917957d6554Steve Block ASSERT(!m_used[virtualRegister]); 642bde8e466a4451c7319e3a072d118917957d6554Steve Block m_used[virtualRegister] = 1; 652bde8e466a4451c7319e3a072d118917957d6554Steve Block } 662bde8e466a4451c7319e3a072d118917957d6554Steve Block } 672bde8e466a4451c7319e3a072d118917957d6554Steve Block#endif 682bde8e466a4451c7319e3a072d118917957d6554Steve Block 692bde8e466a4451c7319e3a072d118917957d6554Steve Block VirtualRegister allocate() 702bde8e466a4451c7319e3a072d118917957d6554Steve Block { 712bde8e466a4451c7319e3a072d118917957d6554Steve Block // Do we have any VirtualRegsiters in the free list, that were used by 722bde8e466a4451c7319e3a072d118917957d6554Steve Block // prior nodes, but are now available? 732bde8e466a4451c7319e3a072d118917957d6554Steve Block if (!m_free.isEmpty()) { 742daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch uint32_t index = m_free.last(); 752bde8e466a4451c7319e3a072d118917957d6554Steve Block m_free.removeLast(); 762bde8e466a4451c7319e3a072d118917957d6554Steve Block // Use count must have hit zero for it to have been added to the free list! 772daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch ASSERT(!m_used[index]); 782daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch return (VirtualRegister)(m_firstTemporary + index); 792bde8e466a4451c7319e3a072d118917957d6554Steve Block } 802bde8e466a4451c7319e3a072d118917957d6554Steve Block 812bde8e466a4451c7319e3a072d118917957d6554Steve Block // Allocate a new VirtualRegister, and add a corresponding entry to m_used. 822bde8e466a4451c7319e3a072d118917957d6554Steve Block size_t next = allocatedCount(); 832bde8e466a4451c7319e3a072d118917957d6554Steve Block m_used.append(0); 842daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch return (VirtualRegister)(m_firstTemporary + next); 852bde8e466a4451c7319e3a072d118917957d6554Steve Block } 862bde8e466a4451c7319e3a072d118917957d6554Steve Block 872bde8e466a4451c7319e3a072d118917957d6554Steve Block // Increment the usecount for the VirtualRegsiter associated with 'child', 882bde8e466a4451c7319e3a072d118917957d6554Steve Block // if it reaches the node's refcount, free the VirtualRegsiter. 892bde8e466a4451c7319e3a072d118917957d6554Steve Block void use(NodeIndex child) 902bde8e466a4451c7319e3a072d118917957d6554Steve Block { 912bde8e466a4451c7319e3a072d118917957d6554Steve Block if (child == NoNode) 922bde8e466a4451c7319e3a072d118917957d6554Steve Block return; 932bde8e466a4451c7319e3a072d118917957d6554Steve Block 942bde8e466a4451c7319e3a072d118917957d6554Steve Block // Find the virtual register number for this child, increment its use count. 952bde8e466a4451c7319e3a072d118917957d6554Steve Block Node& node = m_graph[child]; 962daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch uint32_t index = node.virtualRegister - m_firstTemporary; 972bde8e466a4451c7319e3a072d118917957d6554Steve Block if (node.refCount == ++m_used[index]) { 982bde8e466a4451c7319e3a072d118917957d6554Steve Block // If the use count in the scoreboard reaches the use count for the node, 992bde8e466a4451c7319e3a072d118917957d6554Steve Block // then this was its last use; the virtual register is now free. 1002bde8e466a4451c7319e3a072d118917957d6554Steve Block // Clear the use count & add to the free list. 1012bde8e466a4451c7319e3a072d118917957d6554Steve Block m_used[index] = 0; 1022bde8e466a4451c7319e3a072d118917957d6554Steve Block m_free.append(index); 1032bde8e466a4451c7319e3a072d118917957d6554Steve Block } 1042bde8e466a4451c7319e3a072d118917957d6554Steve Block } 1052bde8e466a4451c7319e3a072d118917957d6554Steve Block 1062bde8e466a4451c7319e3a072d118917957d6554Steve Block unsigned allocatedCount() 1072bde8e466a4451c7319e3a072d118917957d6554Steve Block { 1082bde8e466a4451c7319e3a072d118917957d6554Steve Block // m_used contains an entry for every allocated VirtualRegister. 1092bde8e466a4451c7319e3a072d118917957d6554Steve Block return m_used.size(); 1102bde8e466a4451c7319e3a072d118917957d6554Steve Block } 1112bde8e466a4451c7319e3a072d118917957d6554Steve Block 1122bde8e466a4451c7319e3a072d118917957d6554Steve Blockprivate: 1132bde8e466a4451c7319e3a072d118917957d6554Steve Block // The graph, so we can get refCounts for nodes, to determine when values are dead. 1142bde8e466a4451c7319e3a072d118917957d6554Steve Block Graph& m_graph; 1152daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch // The first VirtualRegsiter to be used as a temporary. 1162daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch uint32_t m_firstTemporary; 1172daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch 1182bde8e466a4451c7319e3a072d118917957d6554Steve Block // For every virtual register that has been allocated (either currently alive, or in 1192bde8e466a4451c7319e3a072d118917957d6554Steve Block // the free list), we keep a count of the number of remaining uses until it is dead 1202bde8e466a4451c7319e3a072d118917957d6554Steve Block // (0, in the case of entries in the free list). Since there is an entry for every 1212bde8e466a4451c7319e3a072d118917957d6554Steve Block // allocated VirtualRegister, the length of this array conveniently provides the 1222bde8e466a4451c7319e3a072d118917957d6554Steve Block // next available VirtualRegister number. 1232bde8e466a4451c7319e3a072d118917957d6554Steve Block Vector<uint32_t, 64> m_used; 1242bde8e466a4451c7319e3a072d118917957d6554Steve Block // A free list of VirtualRegsiters no longer alive. 1252daae5fd11344eaa88a0d92b0f6d65f8d2255c00Ben Murdoch Vector<uint32_t, 64> m_free; 1262bde8e466a4451c7319e3a072d118917957d6554Steve Block}; 1272bde8e466a4451c7319e3a072d118917957d6554Steve Block 1282bde8e466a4451c7319e3a072d118917957d6554Steve Block} } // namespace JSC::DFG 1292bde8e466a4451c7319e3a072d118917957d6554Steve Block 1302bde8e466a4451c7319e3a072d118917957d6554Steve Block#endif 1312bde8e466a4451c7319e3a072d118917957d6554Steve Block#endif 132