2 * Copyright (C) 2011 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
31 #include "CodeBlock.h"
33 #include "PredictionTracker.h"
34 #include "RegisterFile.h"
35 #include <wtf/HashMap.h>
36 #include <wtf/Vector.h>
37 #include <wtf/StdLibExtras.h>
46 typedef uint32_t BlockIndex;
48 // For every local variable we track any existing get or set of the value.
49 // We track the get so that these may be shared, and we track the set to
50 // retrieve the current value, and to reference the final definition.
51 struct VariableRecord {
60 typedef Vector <BlockIndex, 2> PredecessorList;
63 BasicBlock(unsigned bytecodeBegin, NodeIndex begin, unsigned numArguments, unsigned numLocals)
64 : bytecodeBegin(bytecodeBegin)
68 , m_arguments(numArguments)
73 static inline BlockIndex getBytecodeBegin(OwnPtr<BasicBlock>* block)
75 return (*block)->bytecodeBegin;
78 unsigned bytecodeBegin;
83 PredecessorList m_predecessors;
84 Vector <VariableRecord, 8> m_arguments;
85 Vector <VariableRecord, 16> m_locals;
91 // The dataflow graph is an ordered vector of nodes.
92 // The order may be significant for nodes with side-effects (property accesses, value conversions).
93 // Nodes that are 'dead' remain in the vector with refCount 0.
94 class Graph : public Vector<Node, 64> {
96 Graph(unsigned numArguments, unsigned numVariables)
97 : m_predictions(numArguments, numVariables)
101 // Mark a node as being referenced.
102 void ref(NodeIndex nodeIndex)
104 Node& node = at(nodeIndex);
105 // If the value (before incrementing) was at refCount zero then we need to ref its children.
107 refChildren(nodeIndex);
111 // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
112 void dump(CodeBlock* = 0);
113 void dump(NodeIndex, CodeBlock* = 0);
116 BlockIndex blockIndexForBytecodeOffset(unsigned bytecodeBegin)
118 OwnPtr<BasicBlock>* begin = m_blocks.begin();
119 OwnPtr<BasicBlock>* block = binarySearch<OwnPtr<BasicBlock>, unsigned, BasicBlock::getBytecodeBegin>(begin, m_blocks.size(), bytecodeBegin);
120 ASSERT(block >= m_blocks.begin() && block < m_blocks.end());
121 return static_cast<BlockIndex>(block - begin);
124 BasicBlock& blockForBytecodeOffset(unsigned bytecodeBegin)
126 return *m_blocks[blockIndexForBytecodeOffset(bytecodeBegin)];
129 PredictionTracker& predictions()
131 return m_predictions;
134 bool predict(int operand, PredictedType prediction, PredictionSource source)
136 return m_predictions.predict(operand, prediction, source);
139 bool predictGlobalVar(unsigned varNumber, PredictedType prediction, PredictionSource source)
141 return m_predictions.predictGlobalVar(varNumber, prediction, source);
144 bool predict(Node& node, PredictedType prediction, PredictionSource source)
148 return predict(node.local(), prediction, source);
151 return predictGlobalVar(node.varNumber(), prediction, source);
158 return node.predict(prediction, source);
164 PredictedType getPrediction(int operand)
166 return m_predictions.getPrediction(operand);
169 PredictedType getGlobalVarPrediction(unsigned varNumber)
171 return m_predictions.getGlobalVarPrediction(varNumber);
174 PredictedType getPrediction(Node& node)
176 Node* nodePtr = &node;
178 if (nodePtr->op == ValueToNumber)
179 nodePtr = &(*this)[nodePtr->child1()];
181 if (nodePtr->op == ValueToInt32)
182 nodePtr = &(*this)[nodePtr->child1()];
184 switch (nodePtr->op) {
186 return getPrediction(nodePtr->local());
188 return getGlobalVarPrediction(nodePtr->varNumber());
194 return nodePtr->getPrediction();
200 // Helper methods to check nodes for constants.
201 bool isConstant(NodeIndex nodeIndex)
203 return at(nodeIndex).isConstant();
205 bool isJSConstant(NodeIndex nodeIndex)
207 return at(nodeIndex).isConstant();
209 bool isInt32Constant(CodeBlock* codeBlock, NodeIndex nodeIndex)
211 return at(nodeIndex).isInt32Constant(codeBlock);
213 bool isDoubleConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
215 return at(nodeIndex).isDoubleConstant(codeBlock);
217 bool isNumberConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
219 return at(nodeIndex).isNumberConstant(codeBlock);
221 bool isBooleanConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
223 return at(nodeIndex).isBooleanConstant(codeBlock);
225 // Helper methods get constant values from nodes.
226 JSValue valueOfJSConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
228 return at(nodeIndex).valueOfJSConstant(codeBlock);
230 int32_t valueOfInt32Constant(CodeBlock* codeBlock, NodeIndex nodeIndex)
232 return at(nodeIndex).valueOfInt32Constant(codeBlock);
234 double valueOfNumberConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
236 return at(nodeIndex).valueOfNumberConstant(codeBlock);
238 bool valueOfBooleanConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
240 return at(nodeIndex).valueOfBooleanConstant(codeBlock);
244 static const char *opName(NodeType);
247 void predictArgumentTypes(ExecState*, CodeBlock*);
249 Vector< OwnPtr<BasicBlock> , 8> m_blocks;
250 Vector<NodeIndex, 16> m_varArgChildren;
253 // When a node's refCount goes from 0 to 1, it must (logically) recursively ref all of its children, and vice versa.
254 void refChildren(NodeIndex);
256 PredictionTracker m_predictions;
259 } } // namespace JSC::DFG