1/* 2 * Copyright (C) 2011, 2013, 2014 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 DFGBasicBlock_h 27#define DFGBasicBlock_h 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGAbstractValue.h" 32#include "DFGAvailability.h" 33#include "DFGBranchDirection.h" 34#include "DFGFlushedAt.h" 35#include "DFGNode.h" 36#include "Operands.h" 37#include <wtf/HashMap.h> 38#include <wtf/HashSet.h> 39#include <wtf/OwnPtr.h> 40#include <wtf/Vector.h> 41 42namespace JSC { namespace DFG { 43 44class Graph; 45class InsertionSet; 46 47typedef Vector<BasicBlock*, 2> PredecessorList; 48 49struct BasicBlock : RefCounted<BasicBlock> { 50 BasicBlock( 51 unsigned bytecodeBegin, unsigned numArguments, unsigned numLocals, 52 float executionCount); 53 ~BasicBlock(); 54 55 void ensureLocals(unsigned newNumLocals); 56 57 size_t size() const { return m_nodes.size(); } 58 bool isEmpty() const { return !size(); } 59 Node*& at(size_t i) { return m_nodes[i]; } 60 Node* at(size_t i) const { return m_nodes[i]; } 61 Node*& operator[](size_t i) { return at(i); } 62 Node* operator[](size_t i) const { return at(i); } 63 Node* last() const { return at(size() - 1); } 64 void resize(size_t size) { m_nodes.resize(size); } 65 void grow(size_t size) { m_nodes.grow(size); } 66 67 void append(Node* node) { m_nodes.append(node); } 68 void insertBeforeLast(Node* node) 69 { 70 append(last()); 71 at(size() - 2) = node; 72 } 73 74 size_t numNodes() const { return phis.size() + size(); } 75 Node* node(size_t i) const 76 { 77 if (i < phis.size()) 78 return phis[i]; 79 return at(i - phis.size()); 80 } 81 bool isPhiIndex(size_t i) const { return i < phis.size(); } 82 83 bool isInPhis(Node* node) const; 84 bool isInBlock(Node* myNode) const; 85 86 unsigned numSuccessors() { return last()->numSuccessors(); } 87 88 BasicBlock*& successor(unsigned index) 89 { 90 return last()->successor(index); 91 } 92 BasicBlock*& successorForCondition(bool condition) 93 { 94 return last()->successorForCondition(condition); 95 } 96 97 void removePredecessor(BasicBlock* block); 98 void replacePredecessor(BasicBlock* from, BasicBlock* to); 99 100 template<typename... Params> 101 Node* appendNode(Graph&, SpeculatedType, Params...); 102 103 template<typename... Params> 104 Node* appendNonTerminal(Graph&, SpeculatedType, Params...); 105 106 void dump(PrintStream& out) const; 107 108 // This value is used internally for block linking and OSR entry. It is mostly meaningless 109 // for other purposes due to inlining. 110 unsigned bytecodeBegin; 111 112 BlockIndex index; 113 114 bool isOSRTarget; 115 bool cfaHasVisited; 116 bool cfaShouldRevisit; 117 bool cfaFoundConstants; 118 bool cfaDidFinish; 119 BranchDirection cfaBranchDirection; 120#if !ASSERT_DISABLED 121 bool isLinked; 122#endif 123 bool isReachable; 124 125 Vector<Node*> phis; 126 PredecessorList predecessors; 127 128 Operands<Node*, NodePointerTraits> variablesAtHead; 129 Operands<Node*, NodePointerTraits> variablesAtTail; 130 131 Operands<AbstractValue> valuesAtHead; 132 Operands<AbstractValue> valuesAtTail; 133 134 float executionCount; 135 136 // These fields are reserved for NaturalLoops. 137 static const unsigned numberOfInnerMostLoopIndices = 2; 138 unsigned innerMostLoopIndices[numberOfInnerMostLoopIndices]; 139 140 struct SSAData { 141 Operands<Availability> availabilityAtHead; 142 Operands<Availability> availabilityAtTail; 143 HashSet<Node*> liveAtHead; 144 HashSet<Node*> liveAtTail; 145 HashMap<Node*, AbstractValue> valuesAtHead; 146 HashMap<Node*, AbstractValue> valuesAtTail; 147 148 SSAData(BasicBlock*); 149 ~SSAData(); 150 }; 151 OwnPtr<SSAData> ssa; 152 153private: 154 friend class InsertionSet; 155 Vector<Node*, 8> m_nodes; 156}; 157 158struct UnlinkedBlock { 159 BasicBlock* m_block; 160 bool m_needsNormalLinking; 161 bool m_needsEarlyReturnLinking; 162 163 UnlinkedBlock() { } 164 165 explicit UnlinkedBlock(BasicBlock* block) 166 : m_block(block) 167 , m_needsNormalLinking(true) 168 , m_needsEarlyReturnLinking(false) 169 { 170 } 171}; 172 173static inline unsigned getBytecodeBeginForBlock(BasicBlock** basicBlock) 174{ 175 return (*basicBlock)->bytecodeBegin; 176} 177 178static inline BasicBlock* blockForBytecodeOffset(Vector<BasicBlock*>& linkingTargets, unsigned bytecodeBegin) 179{ 180 return *binarySearch<BasicBlock*, unsigned>(linkingTargets, linkingTargets.size(), bytecodeBegin, getBytecodeBeginForBlock); 181} 182 183} } // namespace JSC::DFG 184 185#endif // ENABLE(DFG_JIT) 186 187#endif // DFGBasicBlock_h 188 189