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 { BasicBlockBasicBlock44 BasicBlock(unsigned bytecodeBegin, NodeIndex begin, NodeIndex end) 45 : bytecodeBegin(bytecodeBegin) 46 , begin(begin) 47 , end(end) 48 { 49 } 50 getBytecodeBeginBasicBlock51 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. ref(NodeIndex nodeIndex)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 } deref(NodeIndex nodeIndex)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 blockIndexForBytecodeOffset(unsigned bytecodeBegin)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