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