dfg/DFGGraph.h

   1 /*
   2  * Copyright (C) 2011, 2012, 2013 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 #include <wtf/Platform.h>
  30
  31 #if ENABLE(DFG_JIT)
  32
  33 #include "CodeBlock.h"
  34 #include "DFGArgumentPosition.h"
  35 #include "DFGAssemblyHelpers.h"
  36 #include "DFGBasicBlock.h"
  37 #include "DFGDominators.h"
  38 #include "DFGLongLivedState.h"
  39 #include "DFGNode.h"
  40 #include "DFGNodeAllocator.h"
  41 #include "DFGVariadicFunction.h"
  42 #include "JSStack.h"
  43 #include "MethodOfGettingAValueProfile.h"
  44 #include <wtf/BitVector.h>
  45 #include <wtf/HashMap.h>
  46 #include <wtf/Vector.h>
  47 #include <wtf/StdLibExtras.h>
  48
  49 namespace JSC {
  50
  51 class CodeBlock;
  52 class ExecState;
  53
  54 namespace DFG {
  55
  56 struct StorageAccessData {
  57     size_t offset;
  58     unsigned identifierNumber;
  59 };
  60
  61 struct ResolveGlobalData {
  62     unsigned identifierNumber;
  63     ResolveOperations* resolveOperations;
  64     PutToBaseOperation* putToBaseOperation;
  65     unsigned resolvePropertyIndex;
  66 };
  67
  68 struct ResolveOperationData {
  69     unsigned identifierNumber;
  70     ResolveOperations* resolveOperations;
  71     PutToBaseOperation* putToBaseOperation;
  72 };
  73
  74 struct PutToBaseOperationData {
  75     PutToBaseOperation* putToBaseOperation;
  76 };
  77
  78 enum AddSpeculationMode {
  79     DontSpeculateInteger,
  80     SpeculateIntegerAndTruncateConstants,
  81     SpeculateInteger
  82 };
  83
  84
  85 //
  86 // === Graph ===
  87 //
  88 // The order may be significant for nodes with side-effects (property accesses, value conversions).
  89 // Nodes that are 'dead' remain in the vector with refCount 0.
  90 class Graph {
  91 public:
  92     Graph(VM&, CodeBlock*, unsigned osrEntryBytecodeIndex, const Operands<JSValue>& mustHandleValues);
  93     ~Graph();
  94
  95     void changeChild(Edge& edge, Node* newNode)
  96     {
  97         edge.setNode(newNode);
  98     }
  99
 100     void changeEdge(Edge& edge, Edge newEdge)
 101     {
 102         edge = newEdge;
 103     }
 104
 105     void compareAndSwap(Edge& edge, Node* oldNode, Node* newNode)
 106     {
 107         if (edge.node() != oldNode)
 108             return;
 109         changeChild(edge, newNode);
 110     }
 111
 112     void compareAndSwap(Edge& edge, Edge oldEdge, Edge newEdge)
 113     {
 114         if (edge != oldEdge)
 115             return;
 116         changeEdge(edge, newEdge);
 117     }
 118
 119     void clearAndDerefChild(Node* node, unsigned index)
 120     {
 121         if (!node->children.child(index))
 122             return;
 123         node->children.setChild(index, Edge());
 124     }
 125     void clearAndDerefChild1(Node* node) { clearAndDerefChild(node, 0); }
 126     void clearAndDerefChild2(Node* node) { clearAndDerefChild(node, 1); }
 127     void clearAndDerefChild3(Node* node) { clearAndDerefChild(node, 2); }
 128
 129     void performSubstitution(Node* node)
 130     {
 131         if (node->flags() & NodeHasVarArgs) {
 132             for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++)
 133                 performSubstitutionForEdge(m_varArgChildren[childIdx]);
 134         } else {
 135             performSubstitutionForEdge(node->child1());
 136             performSubstitutionForEdge(node->child2());
 137             performSubstitutionForEdge(node->child3());
 138         }
 139     }
 140
 141     void performSubstitutionForEdge(Edge& child)
 142     {
 143         // Check if this operand is actually unused.
 144         if (!child)
 145             return;
 146
 147         // Check if there is any replacement.
 148         Node* replacement = child->replacement;
 149         if (!replacement)
 150             return;
 151
 152         child.setNode(replacement);
 153
 154         // There is definitely a replacement. Assert that the replacement does not
 155         // have a replacement.
 156         ASSERT(!child->replacement);
 157     }
 158
 159 #define DFG_DEFINE_ADD_NODE(templatePre, templatePost, typeParams, valueParamsComma, valueParams, valueArgs) \
 160     templatePre typeParams templatePost Node* addNode(SpeculatedType type valueParamsComma valueParams) \
 161     { \
 162         Node* node = new (m_allocator) Node(valueArgs); \
 163         node->predict(type); \
 164         return node; \
 165     }
 166     DFG_VARIADIC_TEMPLATE_FUNCTION(DFG_DEFINE_ADD_NODE)
 167 #undef DFG_DEFINE_ADD_NODE
 168
 169     void dethread();
 170
 171     void convertToConstant(Node* node, unsigned constantNumber)
 172     {
 173         if (node->op() == GetLocal)
 174             dethread();
 175         else
 176             ASSERT(!node->hasVariableAccessData());
 177         node->convertToConstant(constantNumber);
 178     }
 179
 180     void convertToConstant(Node* node, JSValue value)
 181     {
 182         convertToConstant(node, m_codeBlock->addOrFindConstant(value));
 183     }
 184
 185     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
 186     void dump(PrintStream& = WTF::dataFile());
 187     enum PhiNodeDumpMode { DumpLivePhisOnly, DumpAllPhis };
 188     void dumpBlockHeader(PrintStream&, const char* prefix, BlockIndex, PhiNodeDumpMode);
 189     void dump(PrintStream&, Edge);
 190     void dump(PrintStream&, const char* prefix, Node*);
 191     static int amountOfNodeWhiteSpace(Node*);
 192     static void printNodeWhiteSpace(PrintStream&, Node*);
 193
 194     // Dump the code origin of the given node as a diff from the code origin of the
 195     // preceding node. Returns true if anything was printed.
 196     bool dumpCodeOrigin(PrintStream&, const char* prefix, Node* previousNode, Node* currentNode);
 197
 198     BlockIndex blockIndexForBytecodeOffset(Vector<BlockIndex>& blocks, unsigned bytecodeBegin);
 199
 200     SpeculatedType getJSConstantSpeculation(Node* node)
 201     {
 202         return speculationFromValue(node->valueOfJSConstant(m_codeBlock));
 203     }
 204
 205     AddSpeculationMode addSpeculationMode(Node* add, bool leftShouldSpeculateInteger, bool rightShouldSpeculateInteger)
 206     {
 207         ASSERT(add->op() == ValueAdd || add->op() == ArithAdd || add->op() == ArithSub);
 208
 209         Node* left = add->child1().node();
 210         Node* right = add->child2().node();
 211
 212         if (left->hasConstant())
 213             return addImmediateShouldSpeculateInteger(add, rightShouldSpeculateInteger, left);
 214         if (right->hasConstant())
 215             return addImmediateShouldSpeculateInteger(add, leftShouldSpeculateInteger, right);
 216
 217         return (leftShouldSpeculateInteger && rightShouldSpeculateInteger && add->canSpeculateInteger()) ? SpeculateInteger : DontSpeculateInteger;
 218     }
 219
 220     AddSpeculationMode valueAddSpeculationMode(Node* add)
 221     {
 222         return addSpeculationMode(add, add->child1()->shouldSpeculateIntegerExpectingDefined(), add->child2()->shouldSpeculateIntegerExpectingDefined());
 223     }
 224
 225     AddSpeculationMode arithAddSpeculationMode(Node* add)
 226     {
 227         return addSpeculationMode(add, add->child1()->shouldSpeculateIntegerForArithmetic(), add->child2()->shouldSpeculateIntegerForArithmetic());
 228     }
 229
 230     AddSpeculationMode addSpeculationMode(Node* add)
 231     {
 232         if (add->op() == ValueAdd)
 233             return valueAddSpeculationMode(add);
 234
 235         return arithAddSpeculationMode(add);
 236     }
 237
 238     bool addShouldSpeculateInteger(Node* add)
 239     {
 240         return addSpeculationMode(add) != DontSpeculateInteger;
 241     }
 242
 243     bool mulShouldSpeculateInteger(Node* mul)
 244     {
 245         ASSERT(mul->op() == ArithMul);
 246
 247         Node* left = mul->child1().node();
 248         Node* right = mul->child2().node();
 249
 250         return Node::shouldSpeculateIntegerForArithmetic(left, right) && mul->canSpeculateInteger();
 251     }
 252
 253     bool negateShouldSpeculateInteger(Node* negate)
 254     {
 255         ASSERT(negate->op() == ArithNegate);
 256         return negate->child1()->shouldSpeculateIntegerForArithmetic() && negate->canSpeculateInteger();
 257     }
 258
 259     // Helper methods to check nodes for constants.
 260     bool isConstant(Node* node)
 261     {
 262         return node->hasConstant();
 263     }
 264     bool isJSConstant(Node* node)
 265     {
 266         return node->hasConstant();
 267     }
 268     bool isInt32Constant(Node* node)
 269     {
 270         return node->isInt32Constant(m_codeBlock);
 271     }
 272     bool isDoubleConstant(Node* node)
 273     {
 274         return node->isDoubleConstant(m_codeBlock);
 275     }
 276     bool isNumberConstant(Node* node)
 277     {
 278         return node->isNumberConstant(m_codeBlock);
 279     }
 280     bool isBooleanConstant(Node* node)
 281     {
 282         return node->isBooleanConstant(m_codeBlock);
 283     }
 284     bool isCellConstant(Node* node)
 285     {
 286         if (!isJSConstant(node))
 287             return false;
 288         JSValue value = valueOfJSConstant(node);
 289         return value.isCell() && !!value;
 290     }
 291     bool isFunctionConstant(Node* node)
 292     {
 293         if (!isJSConstant(node))
 294             return false;
 295         if (!getJSFunction(valueOfJSConstant(node)))
 296             return false;
 297         return true;
 298     }
 299     bool isInternalFunctionConstant(Node* node)
 300     {
 301         if (!isJSConstant(node))
 302             return false;
 303         JSValue value = valueOfJSConstant(node);
 304         if (!value.isCell() || !value)
 305             return false;
 306         JSCell* cell = value.asCell();
 307         if (!cell->inherits(&InternalFunction::s_info))
 308             return false;
 309         return true;
 310     }
 311     // Helper methods get constant values from nodes.
 312     JSValue valueOfJSConstant(Node* node)
 313     {
 314         return node->valueOfJSConstant(m_codeBlock);
 315     }
 316     int32_t valueOfInt32Constant(Node* node)
 317     {
 318         return valueOfJSConstant(node).asInt32();
 319     }
 320     double valueOfNumberConstant(Node* node)
 321     {
 322         return valueOfJSConstant(node).asNumber();
 323     }
 324     bool valueOfBooleanConstant(Node* node)
 325     {
 326         return valueOfJSConstant(node).asBoolean();
 327     }
 328     JSFunction* valueOfFunctionConstant(Node* node)
 329     {
 330         JSCell* function = getJSFunction(valueOfJSConstant(node));
 331         ASSERT(function);
 332         return jsCast<JSFunction*>(function);
 333     }
 334
 335     static const char *opName(NodeType);
 336
 337     StructureSet* addStructureSet(const StructureSet& structureSet)
 338     {
 339         ASSERT(structureSet.size());
 340         m_structureSet.append(structureSet);
 341         return &m_structureSet.last();
 342     }
 343
 344     StructureTransitionData* addStructureTransitionData(const StructureTransitionData& structureTransitionData)
 345     {
 346         m_structureTransitionData.append(structureTransitionData);
 347         return &m_structureTransitionData.last();
 348     }
 349
 350     JSGlobalObject* globalObjectFor(CodeOrigin codeOrigin)
 351     {
 352         return m_codeBlock->globalObjectFor(codeOrigin);
 353     }
 354
 355     JSObject* globalThisObjectFor(CodeOrigin codeOrigin)
 356     {
 357         JSGlobalObject* object = globalObjectFor(codeOrigin);
 358         return object->methodTable()->toThisObject(object, 0);
 359     }
 360
 361     ExecutableBase* executableFor(InlineCallFrame* inlineCallFrame)
 362     {
 363         if (!inlineCallFrame)
 364             return m_codeBlock->ownerExecutable();
 365
 366         return inlineCallFrame->executable.get();
 367     }
 368
 369     ExecutableBase* executableFor(const CodeOrigin& codeOrigin)
 370     {
 371         return executableFor(codeOrigin.inlineCallFrame);
 372     }
 373
 374     CodeBlock* baselineCodeBlockFor(const CodeOrigin& codeOrigin)
 375     {
 376         return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
 377     }
 378
 379     bool hasGlobalExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
 380     {
 381         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(exitKind));
 382     }
 383
 384     bool hasExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
 385     {
 386         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(codeOrigin.bytecodeIndex, exitKind));
 387     }
 388
 389     int argumentsRegisterFor(const CodeOrigin& codeOrigin)
 390     {
 391         if (!codeOrigin.inlineCallFrame)
 392             return m_codeBlock->argumentsRegister();
 393
 394         return baselineCodeBlockForInlineCallFrame(
 395             codeOrigin.inlineCallFrame)->argumentsRegister() +
 396             codeOrigin.inlineCallFrame->stackOffset;
 397     }
 398
 399     int uncheckedArgumentsRegisterFor(const CodeOrigin& codeOrigin)
 400     {
 401         if (!codeOrigin.inlineCallFrame)
 402             return m_codeBlock->uncheckedArgumentsRegister();
 403
 404         CodeBlock* codeBlock = baselineCodeBlockForInlineCallFrame(
 405             codeOrigin.inlineCallFrame);
 406         if (!codeBlock->usesArguments())
 407             return InvalidVirtualRegister;
 408
 409         return codeBlock->argumentsRegister() +
 410             codeOrigin.inlineCallFrame->stackOffset;
 411     }
 412
 413     int uncheckedActivationRegisterFor(const CodeOrigin&)
 414     {
 415         // This will ignore CodeOrigin because we don't inline code that uses activations.
 416         // Hence for inlined call frames it will return the outermost code block's
 417         // activation register. This method is only used to compare the result to a local
 418         // to see if we're mucking with the activation register. Hence if we return the
 419         // "wrong" activation register for the frame then it will compare false, which is
 420         // what we wanted.
 421         return m_codeBlock->uncheckedActivationRegister();
 422     }
 423
 424     ValueProfile* valueProfileFor(Node* node)
 425     {
 426         if (!node)
 427             return 0;
 428
 429         CodeBlock* profiledBlock = baselineCodeBlockFor(node->codeOrigin);
 430
 431         if (node->hasLocal()) {
 432             if (!operandIsArgument(node->local()))
 433                 return 0;
 434             int argument = operandToArgument(node->local());
 435             if (node->variableAccessData() != m_arguments[argument]->variableAccessData())
 436                 return 0;
 437             return profiledBlock->valueProfileForArgument(argument);
 438         }
 439
 440         if (node->hasHeapPrediction())
 441             return profiledBlock->valueProfileForBytecodeOffset(node->codeOrigin.bytecodeIndexForValueProfile());
 442
 443         return 0;
 444     }
 445
 446     MethodOfGettingAValueProfile methodOfGettingAValueProfileFor(Node* node)
 447     {
 448         if (!node)
 449             return MethodOfGettingAValueProfile();
 450
 451         CodeBlock* profiledBlock = baselineCodeBlockFor(node->codeOrigin);
 452
 453         if (node->op() == GetLocal) {
 454             return MethodOfGettingAValueProfile::fromLazyOperand(
 455                 profiledBlock,
 456                 LazyOperandValueProfileKey(
 457                     node->codeOrigin.bytecodeIndex, node->local()));
 458         }
 459
 460         return MethodOfGettingAValueProfile(valueProfileFor(node));
 461     }
 462
 463     bool needsActivation() const
 464     {
 465         return m_codeBlock->needsFullScopeChain() && m_codeBlock->codeType() != GlobalCode;
 466     }
 467
 468     bool usesArguments() const
 469     {
 470         return m_codeBlock->usesArguments();
 471     }
 472
 473     unsigned numSuccessors(BasicBlock* block)
 474     {
 475         return block->last()->numSuccessors();
 476     }
 477     BlockIndex successor(BasicBlock* block, unsigned index)
 478     {
 479         return block->last()->successor(index);
 480     }
 481     BlockIndex successorForCondition(BasicBlock* block, bool condition)
 482     {
 483         return block->last()->successorForCondition(condition);
 484     }
 485
 486     bool isPredictedNumerical(Node* node)
 487     {
 488         return isNumerical(node->child1().useKind()) && isNumerical(node->child2().useKind());
 489     }
 490
 491     // Note that a 'true' return does not actually mean that the ByVal access clobbers nothing.
 492     // It really means that it will not clobber the entire world. It's still up to you to
 493     // carefully consider things like:
 494     // - PutByVal definitely changes the array it stores to, and may even change its length.
 495     // - PutByOffset definitely changes the object it stores to.
 496     // - and so on.
 497     bool byValIsPure(Node* node)
 498     {
 499         switch (node->arrayMode().type()) {
 500         case Array::Generic:
 501             return false;
 502         case Array::Int32:
 503         case Array::Double:
 504         case Array::Contiguous:
 505         case Array::ArrayStorage:
 506             return !node->arrayMode().isOutOfBounds();
 507         case Array::SlowPutArrayStorage:
 508             return !node->arrayMode().mayStoreToHole();
 509         case Array::String:
 510             return node->op() == GetByVal;
 511 #if USE(JSVALUE32_64)
 512         case Array::Arguments:
 513             if (node->op() == GetByVal)
 514                 return true;
 515             return false;
 516 #endif // USE(JSVALUE32_64)
 517         default:
 518             return true;
 519         }
 520     }
 521
 522     bool clobbersWorld(Node* node)
 523     {
 524         if (node->flags() & NodeClobbersWorld)
 525             return true;
 526         if (!(node->flags() & NodeMightClobber))
 527             return false;
 528         switch (node->op()) {
 529         case ValueAdd:
 530         case CompareLess:
 531         case CompareLessEq:
 532         case CompareGreater:
 533         case CompareGreaterEq:
 534         case CompareEq:
 535             return !isPredictedNumerical(node);
 536         case GetByVal:
 537         case PutByVal:
 538         case PutByValAlias:
 539             return !byValIsPure(node);
 540         case ToString:
 541             switch (node->child1().useKind()) {
 542             case StringObjectUse:
 543             case StringOrStringObjectUse:
 544                 return false;
 545             case CellUse:
 546             case UntypedUse:
 547                 return true;
 548             default:
 549                 RELEASE_ASSERT_NOT_REACHED();
 550                 return true;
 551             }
 552         default:
 553             RELEASE_ASSERT_NOT_REACHED();
 554             return true; // If by some oddity we hit this case in release build it's safer to have CSE assume the worst.
 555         }
 556     }
 557
 558     void determineReachability();
 559     void resetReachability();
 560
 561     void resetExitStates();
 562
 563     unsigned varArgNumChildren(Node* node)
 564     {
 565         ASSERT(node->flags() & NodeHasVarArgs);
 566         return node->numChildren();
 567     }
 568
 569     unsigned numChildren(Node* node)
 570     {
 571         if (node->flags() & NodeHasVarArgs)
 572             return varArgNumChildren(node);
 573         return AdjacencyList::Size;
 574     }
 575
 576     Edge& varArgChild(Node* node, unsigned index)
 577     {
 578         ASSERT(node->flags() & NodeHasVarArgs);
 579         return m_varArgChildren[node->firstChild() + index];
 580     }
 581
 582     Edge& child(Node* node, unsigned index)
 583     {
 584         if (node->flags() & NodeHasVarArgs)
 585             return varArgChild(node, index);
 586         return node->children.child(index);
 587     }
 588
 589     void voteNode(Node* node, unsigned ballot)
 590     {
 591         switch (node->op()) {
 592         case ValueToInt32:
 593         case UInt32ToNumber:
 594             node = node->child1().node();
 595             break;
 596         default:
 597             break;
 598         }
 599
 600         if (node->op() == GetLocal)
 601             node->variableAccessData()->vote(ballot);
 602     }
 603
 604     void voteNode(Edge edge, unsigned ballot)
 605     {
 606         voteNode(edge.node(), ballot);
 607     }
 608
 609     void voteChildren(Node* node, unsigned ballot)
 610     {
 611         if (node->flags() & NodeHasVarArgs) {
 612             for (unsigned childIdx = node->firstChild();
 613                 childIdx < node->firstChild() + node->numChildren();
 614                 childIdx++) {
 615                 if (!!m_varArgChildren[childIdx])
 616                     voteNode(m_varArgChildren[childIdx], ballot);
 617             }
 618             return;
 619         }
 620
 621         if (!node->child1())
 622             return;
 623         voteNode(node->child1(), ballot);
 624         if (!node->child2())
 625             return;
 626         voteNode(node->child2(), ballot);
 627         if (!node->child3())
 628             return;
 629         voteNode(node->child3(), ballot);
 630     }
 631
 632     template<typename T> // T = Node* or Edge
 633     void substitute(BasicBlock& block, unsigned startIndexInBlock, T oldThing, T newThing)
 634     {
 635         for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
 636             Node* node = block[indexInBlock];
 637             if (node->flags() & NodeHasVarArgs) {
 638                 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); ++childIdx) {
 639                     if (!!m_varArgChildren[childIdx])
 640                         compareAndSwap(m_varArgChildren[childIdx], oldThing, newThing);
 641                 }
 642                 continue;
 643             }
 644             if (!node->child1())
 645                 continue;
 646             compareAndSwap(node->children.child1(), oldThing, newThing);
 647             if (!node->child2())
 648                 continue;
 649             compareAndSwap(node->children.child2(), oldThing, newThing);
 650             if (!node->child3())
 651                 continue;
 652             compareAndSwap(node->children.child3(), oldThing, newThing);
 653         }
 654     }
 655
 656     // Use this if you introduce a new GetLocal and you know that you introduced it *before*
 657     // any GetLocals in the basic block.
 658     // FIXME: it may be appropriate, in the future, to generalize this to handle GetLocals
 659     // introduced anywhere in the basic block.
 660     void substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
 661     {
 662         if (variableAccessData->isCaptured()) {
 663             // Let CSE worry about this one.
 664             return;
 665         }
 666         for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
 667             Node* node = block[indexInBlock];
 668             bool shouldContinue = true;
 669             switch (node->op()) {
 670             case SetLocal: {
 671                 if (node->local() == variableAccessData->local())
 672                     shouldContinue = false;
 673                 break;
 674             }
 675
 676             case GetLocal: {
 677                 if (node->variableAccessData() != variableAccessData)
 678                     continue;
 679                 substitute(block, indexInBlock, node, newGetLocal);
 680                 Node* oldTailNode = block.variablesAtTail.operand(variableAccessData->local());
 681                 if (oldTailNode == node)
 682                     block.variablesAtTail.operand(variableAccessData->local()) = newGetLocal;
 683                 shouldContinue = false;
 684                 break;
 685             }
 686
 687             default:
 688                 break;
 689             }
 690             if (!shouldContinue)
 691                 break;
 692         }
 693     }
 694
 695     VM& m_vm;
 696     CodeBlock* m_codeBlock;
 697     RefPtr<Profiler::Compilation> m_compilation;
 698     CodeBlock* m_profiledBlock;
 699
 700     NodeAllocator& m_allocator;
 701
 702     Vector< OwnPtr<BasicBlock> , 8> m_blocks;
 703     Vector<Edge, 16> m_varArgChildren;
 704     Vector<StorageAccessData> m_storageAccessData;
 705     Vector<ResolveGlobalData> m_resolveGlobalData;
 706     Vector<ResolveOperationData> m_resolveOperationsData;
 707     Vector<PutToBaseOperationData> m_putToBaseOperationData;
 708     Vector<Node*, 8> m_arguments;
 709     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
 710     SegmentedVector<ArgumentPosition, 8> m_argumentPositions;
 711     SegmentedVector<StructureSet, 16> m_structureSet;
 712     SegmentedVector<StructureTransitionData, 8> m_structureTransitionData;
 713     SegmentedVector<NewArrayBufferData, 4> m_newArrayBufferData;
 714     bool m_hasArguments;
 715     HashSet<ExecutableBase*> m_executablesWhoseArgumentsEscaped;
 716     BitVector m_preservedVars;
 717     Dominators m_dominators;
 718     unsigned m_localVars;
 719     unsigned m_parameterSlots;
 720     unsigned m_osrEntryBytecodeIndex;
 721     Operands<JSValue> m_mustHandleValues;
 722
 723     OptimizationFixpointState m_fixpointState;
 724     GraphForm m_form;
 725     UnificationState m_unificationState;
 726     RefCountState m_refCountState;
 727 private:
 728
 729     void handleSuccessor(Vector<BlockIndex, 16>& worklist, BlockIndex blockIndex, BlockIndex successorIndex);
 730
 731     AddSpeculationMode addImmediateShouldSpeculateInteger(Node* add, bool variableShouldSpeculateInteger, Node* immediate)
 732     {
 733         ASSERT(immediate->hasConstant());
 734
 735         JSValue immediateValue = immediate->valueOfJSConstant(m_codeBlock);
 736         if (!immediateValue.isNumber())
 737             return DontSpeculateInteger;
 738
 739         if (!variableShouldSpeculateInteger)
 740             return DontSpeculateInteger;
 741
 742         if (immediateValue.isInt32())
 743             return add->canSpeculateInteger() ? SpeculateInteger : DontSpeculateInteger;
 744
 745         double doubleImmediate = immediateValue.asDouble();
 746         const double twoToThe48 = 281474976710656.0;
 747         if (doubleImmediate < -twoToThe48 || doubleImmediate > twoToThe48)
 748             return DontSpeculateInteger;
 749
 750         return nodeCanTruncateInteger(add->arithNodeFlags()) ? SpeculateIntegerAndTruncateConstants : DontSpeculateInteger;
 751     }
 752
 753     bool mulImmediateShouldSpeculateInteger(Node* mul, Node* variable, Node* immediate)
 754     {
 755         ASSERT(immediate->hasConstant());
 756
 757         JSValue immediateValue = immediate->valueOfJSConstant(m_codeBlock);
 758         if (!immediateValue.isInt32())
 759             return false;
 760
 761         if (!variable->shouldSpeculateIntegerForArithmetic())
 762             return false;
 763
 764         int32_t intImmediate = immediateValue.asInt32();
 765         // Doubles have a 53 bit mantissa so we expect a multiplication of 2^31 (the highest
 766         // magnitude possible int32 value) and any value less than 2^22 to not result in any
 767         // rounding in a double multiplication - hence it will be equivalent to an integer
 768         // multiplication, if we are doing int32 truncation afterwards (which is what
 769         // canSpeculateInteger() implies).
 770         const int32_t twoToThe22 = 1 << 22;
 771         if (intImmediate <= -twoToThe22 || intImmediate >= twoToThe22)
 772             return mul->canSpeculateInteger() && !nodeMayOverflow(mul->arithNodeFlags());
 773
 774         return mul->canSpeculateInteger();
 775     }
 776 };
 777
 778 class GetBytecodeBeginForBlock {
 779 public:
 780     GetBytecodeBeginForBlock(Graph& graph)
 781         : m_graph(graph)
 782     {
 783     }
 784
 785     unsigned operator()(BlockIndex* blockIndex) const
 786     {
 787         return m_graph.m_blocks[*blockIndex]->bytecodeBegin;
 788     }
 789
 790 private:
 791     Graph& m_graph;
 792 };
 793
 794 inline BlockIndex Graph::blockIndexForBytecodeOffset(Vector<BlockIndex>& linkingTargets, unsigned bytecodeBegin)
 795 {
 796     return *binarySearch<BlockIndex, unsigned>(linkingTargets, linkingTargets.size(), bytecodeBegin, GetBytecodeBeginForBlock(*this));
 797 }
 798
 799 #define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do {            \
 800         Node* _node = (node);                                           \
 801         if (_node->flags() & NodeHasVarArgs) {                          \
 802             for (unsigned _childIdx = _node->firstChild();              \
 803                 _childIdx < _node->firstChild() + _node->numChildren(); \
 804                 _childIdx++) {                                          \
 805                 if (!!(graph).m_varArgChildren[_childIdx])              \
 806                     thingToDo(_node, (graph).m_varArgChildren[_childIdx]); \
 807             }                                                           \
 808         } else {                                                        \
 809             if (!_node->child1()) {                                     \
 810                 ASSERT(                                                 \
 811                     !_node->child2()                                    \
 812                     && !_node->child3());                               \
 813                 break;                                                  \
 814             }                                                           \
 815             thingToDo(_node, _node->child1());                          \
 816                                                                         \
 817             if (!_node->child2()) {                                     \
 818                 ASSERT(!_node->child3());                               \
 819                 break;                                                  \
 820             }                                                           \
 821             thingToDo(_node, _node->child2());                          \
 822                                                                         \
 823             if (!_node->child3())                                       \
 824                 break;                                                  \
 825             thingToDo(_node, _node->child3());                          \
 826         }                                                               \
 827     } while (false)
 828
 829 } } // namespace JSC::DFG
 830
 831 #endif
 832 #endif