code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/dfg/DFGGraph.h

   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 "CodeBlock.h"
  32 #include "DFGNode.h"
  33 #include "PredictionTracker.h"
  34 #include "RegisterFile.h"
  35 #include <wtf/HashMap.h>
  36 #include <wtf/Vector.h>
  37 #include <wtf/StdLibExtras.h>
  38
  39 namespace JSC {
  40
  41 class CodeBlock;
  42 class ExecState;
  43
  44 namespace DFG {
  45
  46 typedef uint32_t BlockIndex;
  47
  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 {
  52     VariableRecord()
  53         : value(NoNode)
  54     {
  55     }
  56
  57     NodeIndex value;
  58 };
  59
  60 struct MethodCheckData {
  61     // It is safe to refer to these directly because they are shadowed by
  62     // the old JIT's CodeBlock's MethodCallLinkInfo.
  63     Structure* structure;
  64     Structure* prototypeStructure;
  65     JSObject* function;
  66     JSObject* prototype;
  67
  68     bool operator==(const MethodCheckData& other) const
  69     {
  70         if (structure != other.structure)
  71             return false;
  72         if (prototypeStructure != other.prototypeStructure)
  73             return false;
  74         if (function != other.function)
  75             return false;
  76         if (prototype != other.prototype)
  77             return false;
  78         return true;
  79     }
  80
  81     bool operator!=(const MethodCheckData& other) const
  82     {
  83         return !(*this == other);
  84     }
  85 };
  86
  87 typedef Vector <BlockIndex, 2> PredecessorList;
  88
  89 struct BasicBlock {
  90     BasicBlock(unsigned bytecodeBegin, NodeIndex begin, unsigned numArguments, unsigned numLocals)
  91         : bytecodeBegin(bytecodeBegin)
  92         , begin(begin)
  93         , end(NoNode)
  94         , isOSRTarget(false)
  95         , m_arguments(numArguments)
  96         , m_locals(numLocals)
  97     {
  98     }
  99
 100     static inline BlockIndex getBytecodeBegin(OwnPtr<BasicBlock>* block)
 101     {
 102         return (*block)->bytecodeBegin;
 103     }
 104
 105     unsigned bytecodeBegin;
 106     NodeIndex begin;
 107     NodeIndex end;
 108     bool isOSRTarget;
 109
 110     PredecessorList m_predecessors;
 111     Vector <VariableRecord, 8> m_arguments;
 112     Vector <VariableRecord, 16> m_locals;
 113 };
 114
 115 //
 116 // === Graph ===
 117 //
 118 // The dataflow graph is an ordered vector of nodes.
 119 // The order may be significant for nodes with side-effects (property accesses, value conversions).
 120 // Nodes that are 'dead' remain in the vector with refCount 0.
 121 class Graph : public Vector<Node, 64> {
 122 public:
 123     Graph(unsigned numArguments, unsigned numVariables)
 124         : m_predictions(numArguments, numVariables)
 125     {
 126     }
 127
 128     // Mark a node as being referenced.
 129     void ref(NodeIndex nodeIndex)
 130     {
 131         Node& node = at(nodeIndex);
 132         // If the value (before incrementing) was at refCount zero then we need to ref its children.
 133         if (node.ref())
 134             refChildren(nodeIndex);
 135     }
 136
 137 #ifndef NDEBUG
 138     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
 139     void dump(CodeBlock* = 0);
 140     void dump(NodeIndex, CodeBlock* = 0);
 141 #endif
 142
 143     BlockIndex blockIndexForBytecodeOffset(unsigned bytecodeBegin)
 144     {
 145         OwnPtr<BasicBlock>* begin = m_blocks.begin();
 146         OwnPtr<BasicBlock>* block = binarySearch<OwnPtr<BasicBlock>, unsigned, BasicBlock::getBytecodeBegin>(begin, m_blocks.size(), bytecodeBegin);
 147         ASSERT(block >= m_blocks.begin() && block < m_blocks.end());
 148         return static_cast<BlockIndex>(block - begin);
 149     }
 150
 151     BasicBlock& blockForBytecodeOffset(unsigned bytecodeBegin)
 152     {
 153         return *m_blocks[blockIndexForBytecodeOffset(bytecodeBegin)];
 154     }
 155
 156     PredictionTracker& predictions()
 157     {
 158         return m_predictions;
 159     }
 160
 161     bool predict(int operand, PredictedType prediction, PredictionSource source)
 162     {
 163         return m_predictions.predict(operand, prediction, source);
 164     }
 165
 166     bool predictGlobalVar(unsigned varNumber, PredictedType prediction, PredictionSource source)
 167     {
 168         return m_predictions.predictGlobalVar(varNumber, prediction, source);
 169     }
 170
 171     bool predict(Node& node, PredictedType prediction, PredictionSource source)
 172     {
 173         switch (node.op) {
 174         case GetLocal:
 175             return predict(node.local(), prediction, source);
 176             break;
 177         case GetGlobalVar:
 178             return predictGlobalVar(node.varNumber(), prediction, source);
 179             break;
 180         case GetById:
 181         case GetMethod:
 182         case GetByVal:
 183         case Call:
 184         case Construct:
 185             return node.predict(prediction, source);
 186         default:
 187             return false;
 188         }
 189     }
 190
 191     PredictedType getPrediction(int operand)
 192     {
 193         return m_predictions.getPrediction(operand);
 194     }
 195
 196     PredictedType getGlobalVarPrediction(unsigned varNumber)
 197     {
 198         return m_predictions.getGlobalVarPrediction(varNumber);
 199     }
 200
 201     PredictedType getMethodCheckPrediction(Node& node)
 202     {
 203         return makePrediction(predictionFromCell(m_methodCheckData[node.methodCheckDataIndex()].function), StrongPrediction);
 204     }
 205
 206     PredictedType getPrediction(Node& node)
 207     {
 208         Node* nodePtr = &node;
 209
 210         if (nodePtr->op == ValueToNumber)
 211             nodePtr = &(*this)[nodePtr->child1()];
 212
 213         if (nodePtr->op == ValueToInt32)
 214             nodePtr = &(*this)[nodePtr->child1()];
 215
 216         switch (nodePtr->op) {
 217         case GetLocal:
 218             return getPrediction(nodePtr->local());
 219         case GetGlobalVar:
 220             return getGlobalVarPrediction(nodePtr->varNumber());
 221         case GetById:
 222         case GetMethod:
 223         case GetByVal:
 224         case Call:
 225         case Construct:
 226             return nodePtr->getPrediction();
 227         case CheckMethod:
 228             return getMethodCheckPrediction(*nodePtr);
 229         default:
 230             return PredictNone;
 231         }
 232     }
 233
 234     // Helper methods to check nodes for constants.
 235     bool isConstant(NodeIndex nodeIndex)
 236     {
 237         return at(nodeIndex).hasConstant();
 238     }
 239     bool isJSConstant(NodeIndex nodeIndex)
 240     {
 241         return at(nodeIndex).hasConstant();
 242     }
 243     bool isInt32Constant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 244     {
 245         return at(nodeIndex).isInt32Constant(codeBlock);
 246     }
 247     bool isDoubleConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 248     {
 249         return at(nodeIndex).isDoubleConstant(codeBlock);
 250     }
 251     bool isNumberConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 252     {
 253         return at(nodeIndex).isNumberConstant(codeBlock);
 254     }
 255     bool isBooleanConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 256     {
 257         return at(nodeIndex).isBooleanConstant(codeBlock);
 258     }
 259     bool isFunctionConstant(CodeBlock* codeBlock, JSGlobalData& globalData, NodeIndex nodeIndex)
 260     {
 261         if (!isJSConstant(nodeIndex))
 262             return false;
 263         if (!getJSFunction(globalData, valueOfJSConstant(codeBlock, nodeIndex)))
 264             return false;
 265         return true;
 266     }
 267     // Helper methods get constant values from nodes.
 268     JSValue valueOfJSConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 269     {
 270         if (at(nodeIndex).hasMethodCheckData())
 271             return JSValue(m_methodCheckData[at(nodeIndex).methodCheckDataIndex()].function);
 272         return valueOfJSConstantNode(codeBlock, nodeIndex);
 273     }
 274     int32_t valueOfInt32Constant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 275     {
 276         return valueOfJSConstantNode(codeBlock, nodeIndex).asInt32();
 277     }
 278     double valueOfNumberConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 279     {
 280         return valueOfJSConstantNode(codeBlock, nodeIndex).uncheckedGetNumber();
 281     }
 282     bool valueOfBooleanConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 283     {
 284         return valueOfJSConstantNode(codeBlock, nodeIndex).getBoolean();
 285     }
 286     JSFunction* valueOfFunctionConstant(CodeBlock* codeBlock, JSGlobalData& globalData, NodeIndex nodeIndex)
 287     {
 288         JSCell* function = getJSFunction(globalData, valueOfJSConstant(codeBlock, nodeIndex));
 289         ASSERT(function);
 290         return asFunction(function);
 291     }
 292
 293 #ifndef NDEBUG
 294     static const char *opName(NodeType);
 295 #endif
 296
 297     void predictArgumentTypes(ExecState*, CodeBlock*);
 298
 299     Vector< OwnPtr<BasicBlock> , 8> m_blocks;
 300     Vector<NodeIndex, 16> m_varArgChildren;
 301     Vector<MethodCheckData> m_methodCheckData;
 302     unsigned m_preservedVars;
 303     unsigned m_parameterSlots;
 304 private:
 305
 306     JSValue valueOfJSConstantNode(CodeBlock* codeBlock, NodeIndex nodeIndex)
 307     {
 308         return codeBlock->constantRegister(FirstConstantRegisterIndex + at(nodeIndex).constantNumber()).get();
 309     }
 310
 311     // When a node's refCount goes from 0 to 1, it must (logically) recursively ref all of its children, and vice versa.
 312     void refChildren(NodeIndex);
 313
 314     PredictionTracker m_predictions;
 315 };
 316
 317 } } // namespace JSC::DFG
 318
 319 #endif
 320 #endif