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 DFGGraph_h
     27 #define DFGGraph_h
     28 
     29 #if ENABLE(DFG_JIT)
     30 
     31 #include <dfg/DFGNode.h>
     32 #include <wtf/Vector.h>
     33 #include <wtf/StdLibExtras.h>
     34 
     35 namespace JSC {
     36 
     37 class CodeBlock;
     38 
     39 namespace DFG {
     40 
     41 typedef uint32_t BlockIndex;
     42 
     43 struct BasicBlock {
     44     BasicBlock(unsigned bytecodeBegin, NodeIndex begin, NodeIndex end)
     45         : bytecodeBegin(bytecodeBegin)
     46         , begin(begin)
     47         , end(end)
     48     {
     49     }
     50 
     51     static inline BlockIndex getBytecodeBegin(BasicBlock* block)
     52     {
     53         return block->bytecodeBegin;
     54     }
     55 
     56     unsigned bytecodeBegin;
     57     NodeIndex begin;
     58     NodeIndex end;
     59 };
     60 
     61 //
     62 // === Graph ===
     63 //
     64 // The dataflow graph is an ordered vector of nodes.
     65 // The order may be significant for nodes with side-effects (property accesses, value conversions).
     66 // Nodes that are 'dead' remain in the vector with refCount 0.
     67 class Graph : public Vector<Node, 64> {
     68 public:
     69     // Mark a node as being referenced.
     70     void ref(NodeIndex nodeIndex)
     71     {
     72         Node& node = at(nodeIndex);
     73         // If the value (before incrementing) was at refCount zero then we need to ref its children.
     74         if (!node.refCount++)
     75             refChildren(nodeIndex);
     76     }
     77     void deref(NodeIndex nodeIndex)
     78     {
     79         Node& node = at(nodeIndex);
     80         ASSERT(node.refCount);
     81         // If the value (after decrementing) becomes refCount zero then we need to deref its children.
     82         if (!--node.refCount)
     83             derefChildren(nodeIndex);
     84     }
     85 
     86 #ifndef NDEBUG
     87     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
     88     void dump(CodeBlock* = 0);
     89     void dump(NodeIndex, CodeBlock* = 0);
     90 #endif
     91 
     92     Vector<BasicBlock> m_blocks;
     93 
     94     BlockIndex blockIndexForBytecodeOffset(unsigned bytecodeBegin)
     95     {
     96         BasicBlock* begin = m_blocks.begin();
     97         BasicBlock* block = binarySearch<BasicBlock, unsigned, BasicBlock::getBytecodeBegin>(begin, m_blocks.size(), bytecodeBegin);
     98         ASSERT(block >= m_blocks.begin() && block < m_blocks.end());
     99         return static_cast<BlockIndex>(block - begin);
    100     }
    101 
    102 private:
    103     // When a node's refCount goes from 0 to 1, it must (logically) recursively ref all of its children, and vice versa.
    104     void refChildren(NodeIndex);
    105     void derefChildren(NodeIndex);
    106 };
    107 
    108 } } // namespace JSC::DFG
    109 
    110 #endif
    111 #endif
    112