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