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
35namespace JSC {
36
37class CodeBlock;
38
39namespace DFG {
40
41typedef uint32_t BlockIndex;
42
43struct 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.
67class Graph : public Vector<Node, 64> {
68public:
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
102private:
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