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 "DFGBasicBlock.h"
  33 #include "DFGNode.h"
  34 #include "PredictionTracker.h"
  35 #include "RegisterFile.h"
  36 #include <wtf/BitVector.h>
  37 #include <wtf/HashMap.h>
  38 #include <wtf/Vector.h>
  39 #include <wtf/StdLibExtras.h>
  40
  41 namespace JSC {
  42
  43 class CodeBlock;
  44 class ExecState;
  45
  46 namespace DFG {
  47
  48 struct StorageAccessData {
  49     size_t offset;
  50     unsigned identifierNumber;
  51
  52     // NOTE: the offset and identifierNumber do not by themselves
  53     // uniquely identify a property. The identifierNumber and a
  54     // Structure* do. If those two match, then the offset should
  55     // be the same, as well. For any Node that has a StorageAccessData,
  56     // it is possible to retrieve the Structure* by looking at the
  57     // first child. It should be a CheckStructure, which has the
  58     // Structure*.
  59 };
  60
  61 struct ResolveGlobalData {
  62     unsigned identifierNumber;
  63     unsigned resolveInfoIndex;
  64 };
  65
  66 //
  67 // === Graph ===
  68 //
  69 // The dataflow graph is an ordered vector of nodes.
  70 // The order may be significant for nodes with side-effects (property accesses, value conversions).
  71 // Nodes that are 'dead' remain in the vector with refCount 0.
  72 class Graph : public Vector<Node, 64> {
  73 public:
  74     // Mark a node as being referenced.
  75     void ref(NodeIndex nodeIndex)
  76     {
  77         Node& node = at(nodeIndex);
  78         // If the value (before incrementing) was at refCount zero then we need to ref its children.
  79         if (node.ref())
  80             refChildren(nodeIndex);
  81     }
  82
  83 #ifndef NDEBUG
  84     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
  85     void dump(CodeBlock* = 0);
  86     void dump(NodeIndex, CodeBlock* = 0);
  87
  88     // Dump the code origin of the given node as a diff from the code origin of the
  89     // preceding node.
  90     void dumpCodeOrigin(NodeIndex);
  91 #endif
  92
  93     BlockIndex blockIndexForBytecodeOffset(Vector<BlockIndex>& blocks, unsigned bytecodeBegin);
  94
  95     bool predictGlobalVar(unsigned varNumber, PredictedType prediction)
  96     {
  97         return m_predictions.predictGlobalVar(varNumber, prediction);
  98     }
  99
 100     PredictedType getGlobalVarPrediction(unsigned varNumber)
 101     {
 102         return m_predictions.getGlobalVarPrediction(varNumber);
 103     }
 104
 105     PredictedType getJSConstantPrediction(Node& node, CodeBlock* codeBlock)
 106     {
 107         return predictionFromValue(node.valueOfJSConstant(codeBlock));
 108     }
 109
 110     // Helper methods to check nodes for constants.
 111     bool isConstant(NodeIndex nodeIndex)
 112     {
 113         return at(nodeIndex).hasConstant();
 114     }
 115     bool isJSConstant(NodeIndex nodeIndex)
 116     {
 117         return at(nodeIndex).hasConstant();
 118     }
 119     bool isInt32Constant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 120     {
 121         return at(nodeIndex).isInt32Constant(codeBlock);
 122     }
 123     bool isDoubleConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 124     {
 125         return at(nodeIndex).isDoubleConstant(codeBlock);
 126     }
 127     bool isNumberConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 128     {
 129         return at(nodeIndex).isNumberConstant(codeBlock);
 130     }
 131     bool isBooleanConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 132     {
 133         return at(nodeIndex).isBooleanConstant(codeBlock);
 134     }
 135     bool isFunctionConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 136     {
 137         if (!isJSConstant(nodeIndex))
 138             return false;
 139         if (!getJSFunction(valueOfJSConstant(codeBlock, nodeIndex)))
 140             return false;
 141         return true;
 142     }
 143     // Helper methods get constant values from nodes.
 144     JSValue valueOfJSConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 145     {
 146         return at(nodeIndex).valueOfJSConstant(codeBlock);
 147     }
 148     int32_t valueOfInt32Constant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 149     {
 150         return valueOfJSConstant(codeBlock, nodeIndex).asInt32();
 151     }
 152     double valueOfNumberConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 153     {
 154         return valueOfJSConstant(codeBlock, nodeIndex).asNumber();
 155     }
 156     bool valueOfBooleanConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 157     {
 158         return valueOfJSConstant(codeBlock, nodeIndex).asBoolean();
 159     }
 160     JSFunction* valueOfFunctionConstant(CodeBlock* codeBlock, NodeIndex nodeIndex)
 161     {
 162         JSCell* function = getJSFunction(valueOfJSConstant(codeBlock, nodeIndex));
 163         ASSERT(function);
 164         return asFunction(function);
 165     }
 166
 167 #ifndef NDEBUG
 168     static const char *opName(NodeType);
 169
 170     // This is O(n), and should only be used for verbose dumps.
 171     const char* nameOfVariableAccessData(VariableAccessData*);
 172 #endif
 173
 174     void predictArgumentTypes(CodeBlock*);
 175
 176     StructureSet* addStructureSet(const StructureSet& structureSet)
 177     {
 178         ASSERT(structureSet.size());
 179         m_structureSet.append(structureSet);
 180         return &m_structureSet.last();
 181     }
 182
 183     StructureTransitionData* addStructureTransitionData(const StructureTransitionData& structureTransitionData)
 184     {
 185         m_structureTransitionData.append(structureTransitionData);
 186         return &m_structureTransitionData.last();
 187     }
 188
 189     ValueProfile* valueProfileFor(NodeIndex nodeIndex, CodeBlock* profiledBlock)
 190     {
 191         if (nodeIndex == NoNode)
 192             return 0;
 193
 194         Node& node = at(nodeIndex);
 195
 196         switch (node.op) {
 197         case GetLocal: {
 198             if (!operandIsArgument(node.local()))
 199                 return 0;
 200             int argument = node.local() + m_arguments.size() + RegisterFile::CallFrameHeaderSize;
 201             if (node.variableAccessData() != at(m_arguments[argument]).variableAccessData())
 202                 return 0;
 203             return profiledBlock->valueProfileForArgument(argument);
 204         }
 205
 206         // Nodes derives from calls need special handling because the value profile is
 207         // associated with the op_call_put_result instruction.
 208         case Call:
 209         case Construct:
 210         case ArrayPop:
 211         case ArrayPush: {
 212             ASSERT(OPCODE_LENGTH(op_call) == OPCODE_LENGTH(op_construct));
 213             return profiledBlock->valueProfileForBytecodeOffset(node.codeOrigin.bytecodeIndex + OPCODE_LENGTH(op_call));
 214         }
 215
 216         default:
 217             if (node.hasHeapPrediction())
 218                 return profiledBlock->valueProfileForBytecodeOffset(node.codeOrigin.bytecodeIndex);
 219             return 0;
 220         }
 221     }
 222
 223     Vector< OwnPtr<BasicBlock> , 8> m_blocks;
 224     Vector<NodeIndex, 16> m_varArgChildren;
 225     Vector<StorageAccessData> m_storageAccessData;
 226     Vector<ResolveGlobalData> m_resolveGlobalData;
 227     Vector<NodeIndex, 8> m_arguments;
 228     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
 229     SegmentedVector<StructureSet, 16> m_structureSet;
 230     SegmentedVector<StructureTransitionData, 8> m_structureTransitionData;
 231     BitVector m_preservedVars;
 232     unsigned m_localVars;
 233     unsigned m_parameterSlots;
 234 private:
 235
 236     // When a node's refCount goes from 0 to 1, it must (logically) recursively ref all of its children, and vice versa.
 237     void refChildren(NodeIndex);
 238
 239     PredictionTracker m_predictions;
 240 };
 241
 242 class GetBytecodeBeginForBlock {
 243 public:
 244     GetBytecodeBeginForBlock(Graph& graph)
 245         : m_graph(graph)
 246     {
 247     }
 248
 249     unsigned operator()(BlockIndex* blockIndex) const
 250     {
 251         return m_graph.m_blocks[*blockIndex]->bytecodeBegin;
 252     }
 253
 254 private:
 255     Graph& m_graph;
 256 };
 257
 258 inline BlockIndex Graph::blockIndexForBytecodeOffset(Vector<BlockIndex>& linkingTargets, unsigned bytecodeBegin)
 259 {
 260     return *WTF::binarySearchWithFunctor<BlockIndex, unsigned>(linkingTargets.begin(), linkingTargets.size(), bytecodeBegin, WTF::KeyMustBePresentInArray, GetBytecodeBeginForBlock(*this));
 261 }
 262
 263 } } // namespace JSC::DFG
 264
 265 #endif
 266 #endif