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             dataLog(" 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         }
 124     }
 125     void use(Edge child)
 126     {
 127         use(child.indexUnchecked());
 128     }
 129
 130     unsigned highWatermark()
 131     {
 132         return m_highWatermark;
 133     }
 134
 135 #ifndef NDEBUG
 136     void dump()
 137     {
 138         dataLog("    USED: [ ");
 139         for (unsigned i = 0; i < m_used.size(); ++i) {
 140             if (!m_free.contains(i)) {
 141                 dataLog("%d:", i);
 142                 if (m_used[i] == max())
 143                     dataLog("local ");
 144                 else
 145                     dataLog("%d ", m_used[i]);
 146             }
 147         }
 148         dataLog("]\n");
 149
 150         dataLog("    FREE: [ ");
 151         for (unsigned i = 0; i < m_used.size(); ++i) {
 152             if (m_free.contains(i) && m_used[i] != max()) {
 153                 ASSERT(!m_used[i]);
 154                 dataLog("%d ", i);
 155             }
 156         }
 157         dataLog("]\n");
 158     }
 159
 160 #endif
 161
 162 private:
 163     static uint32_t max() { return std::numeric_limits<uint32_t>::max(); }
 164
 165     // The graph, so we can get refCounts for nodes, to determine when values are dead.
 166     Graph& m_graph;
 167
 168     // The size of the span of virtual registers that this code block will use.
 169     unsigned m_highWatermark;
 170
 171     // For every virtual register that has been allocated (either currently alive, or in
 172     // the free list), we keep a count of the number of remaining uses until it is dead
 173     // (0, in the case of entries in the free list). Since there is an entry for every
 174     // allocated VirtualRegister, the length of this array conveniently provides the
 175     // next available VirtualRegister number.
 176     Vector<uint32_t, 64> m_used;
 177     // A free list of VirtualRegsiters no longer alive.
 178     Vector<uint32_t, 64> m_free;
 179 };
 180
 181 } } // namespace JSC::DFG
 182
 183 #endif
 184 #endif