Home | History | Annotate | Download | only in dfg 
      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         // For every entry in the free list, the use count of the virtual register should be zero.
     57         // * By using the virtual register numbers from m_free, we are checking that all values
     58         //   in m_free are < m_used.size(), and correspond to an allocated VirtualRegsiter.
     59         // * By setting m_used to a non-zero value after checking it, we are checking that all
     60         //   entries in m_free are unique (otherwise the second test of m_used will fail).
     61         for (size_t i = 0; i < m_free.size(); ++i) {
     62             uint32_t virtualRegister = m_free[i];
     63             ASSERT(!m_used[virtualRegister]);
     64             m_used[virtualRegister] = 1;
     65         }
     66     }
     67 #endif
     68 
     69     VirtualRegister allocate()
     70     {
     71         // Do we have any VirtualRegsiters in the free list, that were used by
     72         // prior nodes, but are now available?
     73         if (!m_free.isEmpty()) {
     74             uint32_t index = m_free.last();
     75             m_free.removeLast();
     76             // Use count must have hit zero for it to have been added to the free list!
     77             ASSERT(!m_used[index]);
     78             return (VirtualRegister)(m_firstTemporary + index);
     79         }
     80 
     81         // Allocate a new VirtualRegister, and add a corresponding entry to m_used.
     82         size_t next = allocatedCount();
     83         m_used.append(0);
     84         return (VirtualRegister)(m_firstTemporary + next);
     85     }
     86 
     87     // Increment the usecount for the VirtualRegsiter associated with 'child',
     88     // if it reaches the node's refcount, free the VirtualRegsiter.
     89     void use(NodeIndex child)
     90     {
     91         if (child == NoNode)
     92             return;
     93 
     94         // Find the virtual register number for this child, increment its use count.
     95         Node& node = m_graph[child];
     96         uint32_t index = node.virtualRegister - m_firstTemporary;
     97         if (node.refCount == ++m_used[index]) {
     98             // If the use count in the scoreboard reaches the use count for the node,
     99             // then this was its last use; the virtual register is now free.
    100             // Clear the use count & add to the free list.
    101             m_used[index] = 0;
    102             m_free.append(index);
    103         }
    104     }
    105 
    106     unsigned allocatedCount()
    107     {
    108         // m_used contains an entry for every allocated VirtualRegister.
    109         return m_used.size();
    110     }
    111 
    112 private:
    113     // The graph, so we can get refCounts for nodes, to determine when values are dead.
    114     Graph& m_graph;
    115     // The first VirtualRegsiter to be used as a temporary.
    116     uint32_t m_firstTemporary;
    117 
    118     // For every virtual register that has been allocated (either currently alive, or in
    119     // the free list), we keep a count of the number of remaining uses until it is dead
    120     // (0, in the case of entries in the free list). Since there is an entry for every
    121     // allocated VirtualRegister, the length of this array conveniently provides the
    122     // next available VirtualRegister number.
    123     Vector<uint32_t, 64> m_used;
    124     // A free list of VirtualRegsiters no longer alive.
    125     Vector<uint32_t, 64> m_free;
    126 };
    127 
    128 } } // namespace JSC::DFG
    129 
    130 #endif
    131 #endif
    132