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 <dfg/DFGGraph.h>
  32 #include <wtf/Vector.h>
  33
  34 namespace JSC { namespace DFG {
  35
  36 // === ScoreBoard ===
  37 //
  38 // This class is used in performing a virtual register allocation over the graph.
  39 // VirtualRegisters are allocated to nodes, with a used count for each virtual
  40 // register tracking the lifespan of the value; after the final use of a node
  41 // the VirtualRegister associated is freed such that it can be reused for
  42 // another node.
  43 class ScoreBoard {
  44 public:
  45     ScoreBoard(Graph& graph, uint32_t firstTemporary)
  46         : m_graph(graph)
  47         , m_firstTemporary(firstTemporary)
  48     {
  49     }
  50
  51 #if DFG_CONSISTENCY_CHECK
  52     ~ScoreBoard()
  53     {
  54         // Every VirtualRegister that was allocated should now be free.
  55         ASSERT(m_used.size() == m_free.size());
  56         // Every entry in the used list should be available in the free list.
  57         for (size_t i = 0; i < m_used.size(); ++i)
  58             ASSERT(m_free.contains(i));
  59         // For every entry in the used list the use count of the virtual register should be zero.
  60         for (size_t i = 0; i < m_free.size(); ++i)
  61             ASSERT(!m_used[i]);
  62     }
  63 #endif
  64
  65     VirtualRegister allocate()
  66     {
  67         // Do we have any VirtualRegsiters in the free list, that were used by
  68         // prior nodes, but are now available?
  69         if (!m_free.isEmpty()) {
  70             uint32_t index = m_free.last();
  71             m_free.removeLast();
  72             // Use count must have hit zero for it to have been added to the free list!
  73             ASSERT(!m_used[index]);
  74             return (VirtualRegister)(m_firstTemporary + index);
  75         }
  76
  77         // Allocate a new VirtualRegister, and add a corresponding entry to m_used.
  78         size_t next = allocatedCount();
  79         m_used.append(0);
  80         return (VirtualRegister)(m_firstTemporary + next);
  81     }
  82
  83     // Increment the usecount for the VirtualRegsiter associated with 'child',
  84     // if it reaches the node's refcount, free the VirtualRegsiter.
  85     void use(NodeIndex child)
  86     {
  87         if (child == NoNode)
  88             return;
  89
  90         // Find the virtual register number for this child, increment its use count.
  91         Node& node = m_graph[child];
  92         uint32_t index = node.virtualRegister() - m_firstTemporary;
  93         if (node.refCount() == ++m_used[index]) {
  94             // If the use count in the scoreboard reaches the use count for the node,
  95             // then this was its last use; the virtual register is now free.
  96             // Clear the use count & add to the free list.
  97             m_used[index] = 0;
  98             m_free.append(index);
  99         }
 100     }
 101
 102     unsigned allocatedCount()
 103     {
 104         // m_used contains an entry for every allocated VirtualRegister.
 105         return m_used.size();
 106     }
 107
 108 #ifndef NDEBUG
 109     void dump()
 110     {
 111         printf("    USED: [ ");
 112         for (unsigned i = 0; i < m_used.size(); ++i) {
 113             if (!m_free.contains(i))
 114                 printf("%d:%d ", m_firstTemporary + i, m_used[i]);
 115         }
 116         printf("]\n");
 117
 118         printf("    FREE: [ ");
 119         for (unsigned i = 0; i < m_used.size(); ++i) {
 120             if (m_free.contains(i)) {
 121                 ASSERT(!m_used[i]);
 122                 printf("%d ", m_firstTemporary + i);
 123             }
 124         }
 125         printf("]\n");
 126     }
 127
 128 #endif
 129
 130 private:
 131     // The graph, so we can get refCounts for nodes, to determine when values are dead.
 132     Graph& m_graph;
 133     // The first VirtualRegsiter to be used as a temporary.
 134     uint32_t m_firstTemporary;
 135
 136     // For every virtual register that has been allocated (either currently alive, or in
 137     // the free list), we keep a count of the number of remaining uses until it is dead
 138     // (0, in the case of entries in the free list). Since there is an entry for every
 139     // allocated VirtualRegister, the length of this array conveniently provides the
 140     // next available VirtualRegister number.
 141     Vector<uint32_t, 64> m_used;
 142     // A free list of VirtualRegsiters no longer alive.
 143     Vector<uint32_t, 64> m_free;
 144 };
 145
 146 } } // namespace JSC::DFG
 147
 148 #endif
 149 #endif