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