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