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(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
 159 private:
 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