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 "DFGArgumentPosition.h"
  33 #include "DFGAssemblyHelpers.h"
  34 #include "DFGBasicBlock.h"
  35 #include "DFGNode.h"
  36 #include "MethodOfGettingAValueProfile.h"
  37 #include "RegisterFile.h"
  38 #include <wtf/BitVector.h>
  39 #include <wtf/HashMap.h>
  40 #include <wtf/Vector.h>
  41 #include <wtf/StdLibExtras.h>
  42
  43 namespace JSC {
  44
  45 class CodeBlock;
  46 class ExecState;
  47
  48 namespace DFG {
  49
  50 struct StorageAccessData {
  51     size_t offset;
  52     unsigned identifierNumber;
  53
  54     // NOTE: the offset and identifierNumber do not by themselves
  55     // uniquely identify a property. The identifierNumber and a
  56     // Structure* do. If those two match, then the offset should
  57     // be the same, as well. For any Node that has a StorageAccessData,
  58     // it is possible to retrieve the Structure* by looking at the
  59     // first child. It should be a CheckStructure, which has the
  60     // Structure*.
  61 };
  62
  63 struct ResolveGlobalData {
  64     unsigned identifierNumber;
  65     unsigned resolveInfoIndex;
  66 };
  67
  68 //
  69 // === Graph ===
  70 //
  71 // The dataflow graph is an ordered vector of nodes.
  72 // The order may be significant for nodes with side-effects (property accesses, value conversions).
  73 // Nodes that are 'dead' remain in the vector with refCount 0.
  74 class Graph : public Vector<Node, 64> {
  75 public:
  76     Graph(JSGlobalData& globalData, CodeBlock* codeBlock)
  77         : m_globalData(globalData)
  78         , m_codeBlock(codeBlock)
  79         , m_profiledBlock(codeBlock->alternative())
  80     {
  81         ASSERT(m_profiledBlock);
  82     }
  83
  84     using Vector<Node, 64>::operator[];
  85     using Vector<Node, 64>::at;
  86
  87     Node& operator[](Edge nodeUse) { return at(nodeUse.index()); }
  88     const Node& operator[](Edge nodeUse) const { return at(nodeUse.index()); }
  89
  90     Node& at(Edge nodeUse) { return at(nodeUse.index()); }
  91     const Node& at(Edge nodeUse) const { return at(nodeUse.index()); }
  92
  93     // Mark a node as being referenced.
  94     void ref(NodeIndex nodeIndex)
  95     {
  96         Node& node = at(nodeIndex);
  97         // If the value (before incrementing) was at refCount zero then we need to ref its children.
  98         if (node.ref())
  99             refChildren(nodeIndex);
 100     }
 101     void ref(Edge nodeUse)
 102     {
 103         ref(nodeUse.index());
 104     }
 105
 106     void deref(NodeIndex nodeIndex)
 107     {
 108         if (at(nodeIndex).deref())
 109             derefChildren(nodeIndex);
 110     }
 111     void deref(Edge nodeUse)
 112     {
 113         deref(nodeUse.index());
 114     }
 115
 116     void clearAndDerefChild1(Node& node)
 117     {
 118         if (!node.child1())
 119             return;
 120         deref(node.child1());
 121         node.children.child1() = Edge();
 122     }
 123
 124     void clearAndDerefChild2(Node& node)
 125     {
 126         if (!node.child2())
 127             return;
 128         deref(node.child2());
 129         node.children.child2() = Edge();
 130     }
 131
 132     void clearAndDerefChild3(Node& node)
 133     {
 134         if (!node.child3())
 135             return;
 136         deref(node.child3());
 137         node.children.child3() = Edge();
 138     }
 139
 140     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
 141     void dump();
 142     void dump(NodeIndex);
 143
 144     // Dump the code origin of the given node as a diff from the code origin of the
 145     // preceding node.
 146     void dumpCodeOrigin(NodeIndex, NodeIndex);
 147
 148     BlockIndex blockIndexForBytecodeOffset(Vector<BlockIndex>& blocks, unsigned bytecodeBegin);
 149
 150     PredictedType getJSConstantPrediction(Node& node)
 151     {
 152         return predictionFromValue(node.valueOfJSConstant(m_codeBlock));
 153     }
 154
 155     bool addShouldSpeculateInteger(Node& add)
 156     {
 157         ASSERT(add.op() == ValueAdd || add.op() == ArithAdd || add.op() == ArithSub);
 158
 159         Node& left = at(add.child1());
 160         Node& right = at(add.child2());
 161
 162         if (left.hasConstant())
 163             return addImmediateShouldSpeculateInteger(add, right, left);
 164         if (right.hasConstant())
 165             return addImmediateShouldSpeculateInteger(add, left, right);
 166
 167         return Node::shouldSpeculateInteger(left, right) && add.canSpeculateInteger();
 168     }
 169
 170     bool negateShouldSpeculateInteger(Node& negate)
 171     {
 172         ASSERT(negate.op() == ArithNegate);
 173         return at(negate.child1()).shouldSpeculateInteger() && negate.canSpeculateInteger();
 174     }
 175
 176     bool addShouldSpeculateInteger(NodeIndex nodeIndex)
 177     {
 178         return addShouldSpeculateInteger(at(nodeIndex));
 179     }
 180
 181     // Helper methods to check nodes for constants.
 182     bool isConstant(NodeIndex nodeIndex)
 183     {
 184         return at(nodeIndex).hasConstant();
 185     }
 186     bool isJSConstant(NodeIndex nodeIndex)
 187     {
 188         return at(nodeIndex).hasConstant();
 189     }
 190     bool isInt32Constant(NodeIndex nodeIndex)
 191     {
 192         return at(nodeIndex).isInt32Constant(m_codeBlock);
 193     }
 194     bool isDoubleConstant(NodeIndex nodeIndex)
 195     {
 196         return at(nodeIndex).isDoubleConstant(m_codeBlock);
 197     }
 198     bool isNumberConstant(NodeIndex nodeIndex)
 199     {
 200         return at(nodeIndex).isNumberConstant(m_codeBlock);
 201     }
 202     bool isBooleanConstant(NodeIndex nodeIndex)
 203     {
 204         return at(nodeIndex).isBooleanConstant(m_codeBlock);
 205     }
 206     bool isFunctionConstant(NodeIndex nodeIndex)
 207     {
 208         if (!isJSConstant(nodeIndex))
 209             return false;
 210         if (!getJSFunction(valueOfJSConstant(nodeIndex)))
 211             return false;
 212         return true;
 213     }
 214     // Helper methods get constant values from nodes.
 215     JSValue valueOfJSConstant(NodeIndex nodeIndex)
 216     {
 217         return at(nodeIndex).valueOfJSConstant(m_codeBlock);
 218     }
 219     int32_t valueOfInt32Constant(NodeIndex nodeIndex)
 220     {
 221         return valueOfJSConstant(nodeIndex).asInt32();
 222     }
 223     double valueOfNumberConstant(NodeIndex nodeIndex)
 224     {
 225         return valueOfJSConstant(nodeIndex).asNumber();
 226     }
 227     bool valueOfBooleanConstant(NodeIndex nodeIndex)
 228     {
 229         return valueOfJSConstant(nodeIndex).asBoolean();
 230     }
 231     JSFunction* valueOfFunctionConstant(NodeIndex nodeIndex)
 232     {
 233         JSCell* function = getJSFunction(valueOfJSConstant(nodeIndex));
 234         ASSERT(function);
 235         return jsCast<JSFunction*>(function);
 236     }
 237
 238     static const char *opName(NodeType);
 239
 240     // This is O(n), and should only be used for verbose dumps.
 241     const char* nameOfVariableAccessData(VariableAccessData*);
 242
 243     void predictArgumentTypes();
 244
 245     StructureSet* addStructureSet(const StructureSet& structureSet)
 246     {
 247         ASSERT(structureSet.size());
 248         m_structureSet.append(structureSet);
 249         return &m_structureSet.last();
 250     }
 251
 252     StructureTransitionData* addStructureTransitionData(const StructureTransitionData& structureTransitionData)
 253     {
 254         m_structureTransitionData.append(structureTransitionData);
 255         return &m_structureTransitionData.last();
 256     }
 257
 258     CodeBlock* baselineCodeBlockFor(const CodeOrigin& codeOrigin)
 259     {
 260         return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
 261     }
 262
 263     ValueProfile* valueProfileFor(NodeIndex nodeIndex)
 264     {
 265         if (nodeIndex == NoNode)
 266             return 0;
 267
 268         Node& node = at(nodeIndex);
 269         CodeBlock* profiledBlock = baselineCodeBlockFor(node.codeOrigin);
 270
 271         if (node.hasLocal()) {
 272             if (!operandIsArgument(node.local()))
 273                 return 0;
 274             int argument = operandToArgument(node.local());
 275             if (node.variableAccessData() != at(m_arguments[argument]).variableAccessData())
 276                 return 0;
 277             return profiledBlock->valueProfileForArgument(argument);
 278         }
 279
 280         if (node.hasHeapPrediction())
 281             return profiledBlock->valueProfileForBytecodeOffset(node.codeOrigin.bytecodeIndexForValueProfile());
 282
 283         return 0;
 284     }
 285
 286     MethodOfGettingAValueProfile methodOfGettingAValueProfileFor(NodeIndex nodeIndex)
 287     {
 288         if (nodeIndex == NoNode)
 289             return MethodOfGettingAValueProfile();
 290
 291         Node& node = at(nodeIndex);
 292         CodeBlock* profiledBlock = baselineCodeBlockFor(node.codeOrigin);
 293
 294         if (node.op() == GetLocal) {
 295             return MethodOfGettingAValueProfile::fromLazyOperand(
 296                 profiledBlock,
 297                 LazyOperandValueProfileKey(
 298                     node.codeOrigin.bytecodeIndex, node.local()));
 299         }
 300
 301         return MethodOfGettingAValueProfile(valueProfileFor(nodeIndex));
 302     }
 303
 304     bool needsActivation() const
 305     {
 306 #if DFG_ENABLE(ALL_VARIABLES_CAPTURED)
 307         return true;
 308 #else
 309         return m_codeBlock->needsFullScopeChain() && m_codeBlock->codeType() != GlobalCode;
 310 #endif
 311     }
 312
 313     // Pass an argument index. Currently it's ignored, but that's somewhat
 314     // of a bug.
 315     bool argumentIsCaptured(int) const
 316     {
 317         return needsActivation();
 318     }
 319     bool localIsCaptured(int operand) const
 320     {
 321 #if DFG_ENABLE(ALL_VARIABLES_CAPTURED)
 322         return operand < m_codeBlock->m_numVars;
 323 #else
 324         return operand < m_codeBlock->m_numCapturedVars;
 325 #endif
 326     }
 327
 328     bool isCaptured(int operand) const
 329     {
 330         if (operandIsArgument(operand))
 331             return argumentIsCaptured(operandToArgument(operand));
 332         return localIsCaptured(operand);
 333     }
 334     bool isCaptured(VirtualRegister virtualRegister) const
 335     {
 336         return isCaptured(static_cast<int>(virtualRegister));
 337     }
 338
 339     JSGlobalData& m_globalData;
 340     CodeBlock* m_codeBlock;
 341     CodeBlock* m_profiledBlock;
 342
 343     Vector< OwnPtr<BasicBlock> , 8> m_blocks;
 344     Vector<Edge, 16> m_varArgChildren;
 345     Vector<StorageAccessData> m_storageAccessData;
 346     Vector<ResolveGlobalData> m_resolveGlobalData;
 347     Vector<NodeIndex, 8> m_arguments;
 348     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
 349     SegmentedVector<ArgumentPosition, 8> m_argumentPositions;
 350     SegmentedVector<StructureSet, 16> m_structureSet;
 351     SegmentedVector<StructureTransitionData, 8> m_structureTransitionData;
 352     BitVector m_preservedVars;
 353     unsigned m_localVars;
 354     unsigned m_parameterSlots;
 355 private:
 356
 357     bool addImmediateShouldSpeculateInteger(Node& add, Node& variable, Node& immediate)
 358     {
 359         ASSERT(immediate.hasConstant());
 360
 361         JSValue immediateValue = immediate.valueOfJSConstant(m_codeBlock);
 362         if (!immediateValue.isNumber())
 363             return false;
 364
 365         if (!variable.shouldSpeculateInteger())
 366             return false;
 367
 368         if (immediateValue.isInt32())
 369             return add.canSpeculateInteger();
 370
 371         double doubleImmediate = immediateValue.asDouble();
 372         const double twoToThe48 = 281474976710656.0;
 373         if (doubleImmediate < -twoToThe48 || doubleImmediate > twoToThe48)
 374             return false;
 375
 376         return nodeCanTruncateInteger(add.arithNodeFlags());
 377     }
 378
 379     // When a node's refCount goes from 0 to 1, it must (logically) recursively ref all of its children, and vice versa.
 380     void refChildren(NodeIndex);
 381     void derefChildren(NodeIndex);
 382 };
 383
 384 class GetBytecodeBeginForBlock {
 385 public:
 386     GetBytecodeBeginForBlock(Graph& graph)
 387         : m_graph(graph)
 388     {
 389     }
 390
 391     unsigned operator()(BlockIndex* blockIndex) const
 392     {
 393         return m_graph.m_blocks[*blockIndex]->bytecodeBegin;
 394     }
 395
 396 private:
 397     Graph& m_graph;
 398 };
 399
 400 inline BlockIndex Graph::blockIndexForBytecodeOffset(Vector<BlockIndex>& linkingTargets, unsigned bytecodeBegin)
 401 {
 402     return *WTF::binarySearchWithFunctor<BlockIndex, unsigned>(linkingTargets.begin(), linkingTargets.size(), bytecodeBegin, WTF::KeyMustBePresentInArray, GetBytecodeBeginForBlock(*this));
 403 }
 404
 405 } } // namespace JSC::DFG
 406
 407 #endif
 408 #endif