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