Source/JavaScriptCore/dfg/DFGGraph.h

   1 /*
   2  * Copyright (C) 2011-2016 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 #pragma once
  27
  28 #if ENABLE(DFG_JIT)
  29
  30 #include "AssemblyHelpers.h"
  31 #include "BytecodeLivenessAnalysisInlines.h"
  32 #include "CodeBlock.h"
  33 #include "DFGArgumentPosition.h"
  34 #include "DFGBasicBlock.h"
  35 #include "DFGFrozenValue.h"
  36 #include "DFGLongLivedState.h"
  37 #include "DFGNode.h"
  38 #include "DFGNodeAllocator.h"
  39 #include "DFGPlan.h"
  40 #include "DFGPropertyTypeKey.h"
  41 #include "DFGScannable.h"
  42 #include "FullBytecodeLiveness.h"
  43 #include "MethodOfGettingAValueProfile.h"
  44 #include <unordered_map>
  45 #include <wtf/BitVector.h>
  46 #include <wtf/HashMap.h>
  47 #include <wtf/Vector.h>
  48 #include <wtf/StdLibExtras.h>
  49
  50 namespace JSC {
  51
  52 class CodeBlock;
  53 class ExecState;
  54
  55 namespace DFG {
  56
  57 class BackwardsCFG;
  58 class BackwardsDominators;
  59 class CFG;
  60 class ControlEquivalenceAnalysis;
  61 class Dominators;
  62 class FlowIndexing;
  63 class NaturalLoops;
  64 class PrePostNumbering;
  65
  66 template<typename> class FlowMap;
  67
  68 #define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do {            \
  69         Node* _node = (node);                                           \
  70         if (_node->flags() & NodeHasVarArgs) {                          \
  71             for (unsigned _childIdx = _node->firstChild();              \
  72                 _childIdx < _node->firstChild() + _node->numChildren(); \
  73                 _childIdx++) {                                          \
  74                 if (!!(graph).m_varArgChildren[_childIdx])              \
  75                     thingToDo(_node, (graph).m_varArgChildren[_childIdx]); \
  76             }                                                           \
  77         } else {                                                        \
  78             if (!_node->child1()) {                                     \
  79                 ASSERT(                                                 \
  80                     !_node->child2()                                    \
  81                     && !_node->child3());                               \
  82                 break;                                                  \
  83             }                                                           \
  84             thingToDo(_node, _node->child1());                          \
  85                                                                         \
  86             if (!_node->child2()) {                                     \
  87                 ASSERT(!_node->child3());                               \
  88                 break;                                                  \
  89             }                                                           \
  90             thingToDo(_node, _node->child2());                          \
  91                                                                         \
  92             if (!_node->child3())                                       \
  93                 break;                                                  \
  94             thingToDo(_node, _node->child3());                          \
  95         }                                                               \
  96     } while (false)
  97
  98 #define DFG_ASSERT(graph, node, assertion) do {                         \
  99         if (!!(assertion))                                              \
 100             break;                                                      \
 101         (graph).handleAssertionFailure(                                 \
 102             (node), __FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
 103     } while (false)
 104
 105 #define DFG_CRASH(graph, node, reason) do {                             \
 106         (graph).handleAssertionFailure(                                 \
 107             (node), __FILE__, __LINE__, WTF_PRETTY_FUNCTION, (reason)); \
 108     } while (false)
 109
 110 struct InlineVariableData {
 111     InlineCallFrame* inlineCallFrame;
 112     unsigned argumentPositionStart;
 113     VariableAccessData* calleeVariable;
 114 };
 115
 116 enum AddSpeculationMode {
 117     DontSpeculateInt32,
 118     SpeculateInt32AndTruncateConstants,
 119     SpeculateInt32
 120 };
 121
 122 //
 123 // === Graph ===
 124 //
 125 // The order may be significant for nodes with side-effects (property accesses, value conversions).
 126 // Nodes that are 'dead' remain in the vector with refCount 0.
 127 class Graph : public virtual Scannable {
 128 public:
 129     Graph(VM&, Plan&, LongLivedState&);
 130     ~Graph();
 131
 132     void changeChild(Edge& edge, Node* newNode)
 133     {
 134         edge.setNode(newNode);
 135     }
 136
 137     void changeEdge(Edge& edge, Edge newEdge)
 138     {
 139         edge = newEdge;
 140     }
 141
 142     void compareAndSwap(Edge& edge, Node* oldNode, Node* newNode)
 143     {
 144         if (edge.node() != oldNode)
 145             return;
 146         changeChild(edge, newNode);
 147     }
 148
 149     void compareAndSwap(Edge& edge, Edge oldEdge, Edge newEdge)
 150     {
 151         if (edge != oldEdge)
 152             return;
 153         changeEdge(edge, newEdge);
 154     }
 155
 156     void performSubstitution(Node* node)
 157     {
 158         if (node->flags() & NodeHasVarArgs) {
 159             for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++)
 160                 performSubstitutionForEdge(m_varArgChildren[childIdx]);
 161         } else {
 162             performSubstitutionForEdge(node->child1());
 163             performSubstitutionForEdge(node->child2());
 164             performSubstitutionForEdge(node->child3());
 165         }
 166     }
 167
 168     void performSubstitutionForEdge(Edge& child)
 169     {
 170         // Check if this operand is actually unused.
 171         if (!child)
 172             return;
 173
 174         // Check if there is any replacement.
 175         Node* replacement = child->replacement();
 176         if (!replacement)
 177             return;
 178
 179         child.setNode(replacement);
 180
 181         // There is definitely a replacement. Assert that the replacement does not
 182         // have a replacement.
 183         ASSERT(!child->replacement());
 184     }
 185
 186     template<typename... Params>
 187     Node* addNode(Params... params)
 188     {
 189         Node* node = new (m_allocator) Node(params...);
 190         addNodeToMapByIndex(node);
 191         return node;
 192     }
 193     template<typename... Params>
 194     Node* addNode(SpeculatedType type, Params... params)
 195     {
 196         Node* node = new (m_allocator) Node(params...);
 197         node->predict(type);
 198         addNodeToMapByIndex(node);
 199         return node;
 200     }
 201
 202     void deleteNode(Node*);
 203     unsigned maxNodeCount() const { return m_nodesByIndex.size(); }
 204     Node* nodeAt(unsigned index) const { return m_nodesByIndex[index]; }
 205     void packNodeIndices();
 206
 207     void dethread();
 208
 209     FrozenValue* freeze(JSValue); // We use weak freezing by default.
 210     FrozenValue* freezeStrong(JSValue); // Shorthand for freeze(value)->strengthenTo(StrongValue).
 211
 212     void convertToConstant(Node* node, FrozenValue* value);
 213     void convertToConstant(Node* node, JSValue value);
 214     void convertToStrongConstant(Node* node, JSValue value);
 215
 216     RegisteredStructure registerStructure(Structure* structure)
 217     {
 218         StructureRegistrationResult ignored;
 219         return registerStructure(structure, ignored);
 220     }
 221     RegisteredStructure registerStructure(Structure*, StructureRegistrationResult&);
 222     void assertIsRegistered(Structure* structure);
 223
 224     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
 225     void dump(PrintStream& = WTF::dataFile(), DumpContext* = 0);
 226
 227     bool terminalsAreValid();
 228
 229     enum PhiNodeDumpMode { DumpLivePhisOnly, DumpAllPhis };
 230     void dumpBlockHeader(PrintStream&, const char* prefix, BasicBlock*, PhiNodeDumpMode, DumpContext*);
 231     void dump(PrintStream&, Edge);
 232     void dump(PrintStream&, const char* prefix, Node*, DumpContext* = 0);
 233     static int amountOfNodeWhiteSpace(Node*);
 234     static void printNodeWhiteSpace(PrintStream&, Node*);
 235
 236     // Dump the code origin of the given node as a diff from the code origin of the
 237     // preceding node. Returns true if anything was printed.
 238     bool dumpCodeOrigin(PrintStream&, const char* prefix, Node*& previousNode, Node* currentNode, DumpContext*);
 239
 240     AddSpeculationMode addSpeculationMode(Node* add, bool leftShouldSpeculateInt32, bool rightShouldSpeculateInt32, PredictionPass pass)
 241     {
 242         ASSERT(add->op() == ValueAdd || add->op() == ArithAdd || add->op() == ArithSub);
 243
 244         RareCaseProfilingSource source = add->sourceFor(pass);
 245
 246         Node* left = add->child1().node();
 247         Node* right = add->child2().node();
 248
 249         if (left->hasConstant())
 250             return addImmediateShouldSpeculateInt32(add, rightShouldSpeculateInt32, right, left, source);
 251         if (right->hasConstant())
 252             return addImmediateShouldSpeculateInt32(add, leftShouldSpeculateInt32, left, right, source);
 253
 254         return (leftShouldSpeculateInt32 && rightShouldSpeculateInt32 && add->canSpeculateInt32(source)) ? SpeculateInt32 : DontSpeculateInt32;
 255     }
 256
 257     AddSpeculationMode valueAddSpeculationMode(Node* add, PredictionPass pass)
 258     {
 259         return addSpeculationMode(
 260             add,
 261             add->child1()->shouldSpeculateInt32OrBooleanExpectingDefined(),
 262             add->child2()->shouldSpeculateInt32OrBooleanExpectingDefined(),
 263             pass);
 264     }
 265
 266     AddSpeculationMode arithAddSpeculationMode(Node* add, PredictionPass pass)
 267     {
 268         return addSpeculationMode(
 269             add,
 270             add->child1()->shouldSpeculateInt32OrBooleanForArithmetic(),
 271             add->child2()->shouldSpeculateInt32OrBooleanForArithmetic(),
 272             pass);
 273     }
 274
 275     AddSpeculationMode addSpeculationMode(Node* add, PredictionPass pass)
 276     {
 277         if (add->op() == ValueAdd)
 278             return valueAddSpeculationMode(add, pass);
 279
 280         return arithAddSpeculationMode(add, pass);
 281     }
 282
 283     bool addShouldSpeculateInt32(Node* add, PredictionPass pass)
 284     {
 285         return addSpeculationMode(add, pass) != DontSpeculateInt32;
 286     }
 287
 288     bool addShouldSpeculateAnyInt(Node* add)
 289     {
 290         if (!enableInt52())
 291             return false;
 292
 293         Node* left = add->child1().node();
 294         Node* right = add->child2().node();
 295
 296         auto isAnyIntSpeculationForAdd = [](SpeculatedType value) {
 297             return !!value && (value & (SpecAnyInt | SpecAnyIntAsDouble)) == value;
 298         };
 299
 300         return isAnyIntSpeculationForAdd(left->prediction())
 301             && isAnyIntSpeculationForAdd(right->prediction())
 302             && !hasExitSite(add, Int52Overflow);
 303     }
 304
 305     bool binaryArithShouldSpeculateInt32(Node* node, PredictionPass pass)
 306     {
 307         Node* left = node->child1().node();
 308         Node* right = node->child2().node();
 309
 310         return Node::shouldSpeculateInt32OrBooleanForArithmetic(left, right)
 311             && node->canSpeculateInt32(node->sourceFor(pass));
 312     }
 313
 314     bool binaryArithShouldSpeculateAnyInt(Node* node, PredictionPass pass)
 315     {
 316         if (!enableInt52())
 317             return false;
 318
 319         Node* left = node->child1().node();
 320         Node* right = node->child2().node();
 321
 322         return Node::shouldSpeculateAnyInt(left, right)
 323             && node->canSpeculateInt52(pass)
 324             && !hasExitSite(node, Int52Overflow);
 325     }
 326
 327     bool unaryArithShouldSpeculateInt32(Node* node, PredictionPass pass)
 328     {
 329         return node->child1()->shouldSpeculateInt32OrBooleanForArithmetic()
 330             && node->canSpeculateInt32(pass);
 331     }
 332
 333     bool unaryArithShouldSpeculateAnyInt(Node* node, PredictionPass pass)
 334     {
 335         if (!enableInt52())
 336             return false;
 337         return node->child1()->shouldSpeculateAnyInt()
 338             && node->canSpeculateInt52(pass)
 339             && !hasExitSite(node, Int52Overflow);
 340     }
 341
 342     bool canOptimizeStringObjectAccess(const CodeOrigin&);
 343
 344     bool getRegExpPrototypeProperty(JSObject* regExpPrototype, Structure* regExpPrototypeStructure, UniquedStringImpl* uid, JSValue& returnJSValue);
 345
 346     bool roundShouldSpeculateInt32(Node* arithRound, PredictionPass pass)
 347     {
 348         ASSERT(arithRound->op() == ArithRound || arithRound->op() == ArithFloor || arithRound->op() == ArithCeil || arithRound->op() == ArithTrunc);
 349         return arithRound->canSpeculateInt32(pass) && !hasExitSite(arithRound->origin.semantic, Overflow) && !hasExitSite(arithRound->origin.semantic, NegativeZero);
 350     }
 351
 352     static const char *opName(NodeType);
 353
 354     RegisteredStructureSet* addStructureSet(const StructureSet& structureSet)
 355     {
 356         m_structureSets.append();
 357         RegisteredStructureSet* result = &m_structureSets.last();
 358
 359         for (Structure* structure : structureSet)
 360             result->add(registerStructure(structure));
 361
 362         return result;
 363     }
 364
 365     RegisteredStructureSet* addStructureSet(const RegisteredStructureSet& structureSet)
 366     {
 367         m_structureSets.append();
 368         RegisteredStructureSet* result = &m_structureSets.last();
 369
 370         for (RegisteredStructure structure : structureSet)
 371             result->add(structure);
 372
 373         return result;
 374     }
 375
 376     JSGlobalObject* globalObjectFor(CodeOrigin codeOrigin)
 377     {
 378         return m_codeBlock->globalObjectFor(codeOrigin);
 379     }
 380
 381     JSObject* globalThisObjectFor(CodeOrigin codeOrigin)
 382     {
 383         JSGlobalObject* object = globalObjectFor(codeOrigin);
 384         return jsCast<JSObject*>(object->methodTable()->toThis(object, object->globalExec(), NotStrictMode));
 385     }
 386
 387     ScriptExecutable* executableFor(InlineCallFrame* inlineCallFrame)
 388     {
 389         if (!inlineCallFrame)
 390             return m_codeBlock->ownerScriptExecutable();
 391
 392         return inlineCallFrame->baselineCodeBlock->ownerScriptExecutable();
 393     }
 394
 395     ScriptExecutable* executableFor(const CodeOrigin& codeOrigin)
 396     {
 397         return executableFor(codeOrigin.inlineCallFrame);
 398     }
 399
 400     CodeBlock* baselineCodeBlockFor(InlineCallFrame* inlineCallFrame)
 401     {
 402         if (!inlineCallFrame)
 403             return m_profiledBlock;
 404         return baselineCodeBlockForInlineCallFrame(inlineCallFrame);
 405     }
 406
 407     CodeBlock* baselineCodeBlockFor(const CodeOrigin& codeOrigin)
 408     {
 409         return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
 410     }
 411
 412     bool isStrictModeFor(CodeOrigin codeOrigin)
 413     {
 414         if (!codeOrigin.inlineCallFrame)
 415             return m_codeBlock->isStrictMode();
 416         return codeOrigin.inlineCallFrame->isStrictMode();
 417     }
 418
 419     ECMAMode ecmaModeFor(CodeOrigin codeOrigin)
 420     {
 421         return isStrictModeFor(codeOrigin) ? StrictMode : NotStrictMode;
 422     }
 423
 424     bool masqueradesAsUndefinedWatchpointIsStillValid(const CodeOrigin& codeOrigin)
 425     {
 426         return globalObjectFor(codeOrigin)->masqueradesAsUndefinedWatchpoint()->isStillValid();
 427     }
 428
 429     bool hasGlobalExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
 430     {
 431         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(exitKind));
 432     }
 433
 434     bool hasExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
 435     {
 436         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(codeOrigin.bytecodeIndex, exitKind));
 437     }
 438
 439     bool hasExitSite(Node* node, ExitKind exitKind)
 440     {
 441         return hasExitSite(node->origin.semantic, exitKind);
 442     }
 443
 444     MethodOfGettingAValueProfile methodOfGettingAValueProfileFor(Node* currentNode, Node* operandNode);
 445
 446     BlockIndex numBlocks() const { return m_blocks.size(); }
 447     BasicBlock* block(BlockIndex blockIndex) const { return m_blocks[blockIndex].get(); }
 448     BasicBlock* lastBlock() const { return block(numBlocks() - 1); }
 449
 450     void appendBlock(Ref<BasicBlock>&& basicBlock)
 451     {
 452         basicBlock->index = m_blocks.size();
 453         m_blocks.append(WTFMove(basicBlock));
 454     }
 455
 456     void killBlock(BlockIndex blockIndex)
 457     {
 458         m_blocks[blockIndex] = nullptr;
 459     }
 460
 461     void killBlock(BasicBlock* basicBlock)
 462     {
 463         killBlock(basicBlock->index);
 464     }
 465
 466     void killBlockAndItsContents(BasicBlock*);
 467
 468     void killUnreachableBlocks();
 469
 470     void determineReachability();
 471     void resetReachability();
 472
 473     void computeRefCounts();
 474
 475     unsigned varArgNumChildren(Node* node)
 476     {
 477         ASSERT(node->flags() & NodeHasVarArgs);
 478         return node->numChildren();
 479     }
 480
 481     unsigned numChildren(Node* node)
 482     {
 483         if (node->flags() & NodeHasVarArgs)
 484             return varArgNumChildren(node);
 485         return AdjacencyList::Size;
 486     }
 487
 488     Edge& varArgChild(Node* node, unsigned index)
 489     {
 490         ASSERT(node->flags() & NodeHasVarArgs);
 491         return m_varArgChildren[node->firstChild() + index];
 492     }
 493
 494     Edge& child(Node* node, unsigned index)
 495     {
 496         if (node->flags() & NodeHasVarArgs)
 497             return varArgChild(node, index);
 498         return node->children.child(index);
 499     }
 500
 501     void voteNode(Node* node, unsigned ballot, float weight = 1)
 502     {
 503         switch (node->op()) {
 504         case ValueToInt32:
 505         case UInt32ToNumber:
 506             node = node->child1().node();
 507             break;
 508         default:
 509             break;
 510         }
 511
 512         if (node->op() == GetLocal)
 513             node->variableAccessData()->vote(ballot, weight);
 514     }
 515
 516     void voteNode(Edge edge, unsigned ballot, float weight = 1)
 517     {
 518         voteNode(edge.node(), ballot, weight);
 519     }
 520
 521     void voteChildren(Node* node, unsigned ballot, float weight = 1)
 522     {
 523         if (node->flags() & NodeHasVarArgs) {
 524             for (unsigned childIdx = node->firstChild();
 525                 childIdx < node->firstChild() + node->numChildren();
 526                 childIdx++) {
 527                 if (!!m_varArgChildren[childIdx])
 528                     voteNode(m_varArgChildren[childIdx], ballot, weight);
 529             }
 530             return;
 531         }
 532
 533         if (!node->child1())
 534             return;
 535         voteNode(node->child1(), ballot, weight);
 536         if (!node->child2())
 537             return;
 538         voteNode(node->child2(), ballot, weight);
 539         if (!node->child3())
 540             return;
 541         voteNode(node->child3(), ballot, weight);
 542     }
 543
 544     template<typename T> // T = Node* or Edge
 545     void substitute(BasicBlock& block, unsigned startIndexInBlock, T oldThing, T newThing)
 546     {
 547         for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
 548             Node* node = block[indexInBlock];
 549             if (node->flags() & NodeHasVarArgs) {
 550                 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); ++childIdx) {
 551                     if (!!m_varArgChildren[childIdx])
 552                         compareAndSwap(m_varArgChildren[childIdx], oldThing, newThing);
 553                 }
 554                 continue;
 555             }
 556             if (!node->child1())
 557                 continue;
 558             compareAndSwap(node->children.child1(), oldThing, newThing);
 559             if (!node->child2())
 560                 continue;
 561             compareAndSwap(node->children.child2(), oldThing, newThing);
 562             if (!node->child3())
 563                 continue;
 564             compareAndSwap(node->children.child3(), oldThing, newThing);
 565         }
 566     }
 567
 568     // Use this if you introduce a new GetLocal and you know that you introduced it *before*
 569     // any GetLocals in the basic block.
 570     // FIXME: it may be appropriate, in the future, to generalize this to handle GetLocals
 571     // introduced anywhere in the basic block.
 572     void substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal);
 573
 574     void invalidateCFG();
 575     void invalidateNodeLiveness();
 576
 577     void clearFlagsOnAllNodes(NodeFlags);
 578
 579     void clearReplacements();
 580     void clearEpochs();
 581     void initializeNodeOwners();
 582
 583     BlockList blocksInPreOrder();
 584     BlockList blocksInPostOrder();
 585
 586     class NaturalBlockIterable {
 587     public:
 588         NaturalBlockIterable()
 589             : m_graph(nullptr)
 590         {
 591         }
 592
 593         NaturalBlockIterable(Graph& graph)
 594             : m_graph(&graph)
 595         {
 596         }
 597
 598         class iterator {
 599         public:
 600             iterator()
 601                 : m_graph(nullptr)
 602                 , m_index(0)
 603             {
 604             }
 605
 606             iterator(Graph& graph, BlockIndex index)
 607                 : m_graph(&graph)
 608                 , m_index(findNext(index))
 609             {
 610             }
 611
 612             BasicBlock *operator*()
 613             {
 614                 return m_graph->block(m_index);
 615             }
 616
 617             iterator& operator++()
 618             {
 619                 m_index = findNext(m_index + 1);
 620                 return *this;
 621             }
 622
 623             bool operator==(const iterator& other) const
 624             {
 625                 return m_index == other.m_index;
 626             }
 627
 628             bool operator!=(const iterator& other) const
 629             {
 630                 return !(*this == other);
 631             }
 632
 633         private:
 634             BlockIndex findNext(BlockIndex index)
 635             {
 636                 while (index < m_graph->numBlocks() && !m_graph->block(index))
 637                     index++;
 638                 return index;
 639             }
 640
 641             Graph* m_graph;
 642             BlockIndex m_index;
 643         };
 644
 645         iterator begin()
 646         {
 647             return iterator(*m_graph, 0);
 648         }
 649
 650         iterator end()
 651         {
 652             return iterator(*m_graph, m_graph->numBlocks());
 653         }
 654
 655     private:
 656         Graph* m_graph;
 657     };
 658
 659     NaturalBlockIterable blocksInNaturalOrder()
 660     {
 661         return NaturalBlockIterable(*this);
 662     }
 663
 664     template<typename ChildFunctor>
 665     void doToChildrenWithNode(Node* node, const ChildFunctor& functor)
 666     {
 667         DFG_NODE_DO_TO_CHILDREN(*this, node, functor);
 668     }
 669
 670     template<typename ChildFunctor>
 671     void doToChildren(Node* node, const ChildFunctor& functor)
 672     {
 673         doToChildrenWithNode(
 674             node,
 675             [&functor] (Node*, Edge& edge) {
 676                 functor(edge);
 677             });
 678     }
 679
 680     bool uses(Node* node, Node* child)
 681     {
 682         bool result = false;
 683         doToChildren(node, [&] (Edge edge) { result |= edge == child; });
 684         return result;
 685     }
 686
 687     bool isWatchingHavingABadTimeWatchpoint(Node* node)
 688     {
 689         JSGlobalObject* globalObject = globalObjectFor(node->origin.semantic);
 690         return watchpoints().isWatched(globalObject->havingABadTimeWatchpoint());
 691     }
 692
 693     bool isWatchingArrayIteratorProtocolWatchpoint(Node* node)
 694     {
 695         JSGlobalObject* globalObject = globalObjectFor(node->origin.semantic);
 696         InlineWatchpointSet& set = globalObject->arrayIteratorProtocolWatchpoint();
 697         if (watchpoints().isWatched(set))
 698             return true;
 699
 700         if (set.isStillValid()) {
 701             // Since the global object owns this watchpoint, we make ourselves have a weak pointer to it.
 702             // If the global object got deallocated, it wouldn't fire the watchpoint. It's unlikely the
 703             // global object would get deallocated without this code ever getting thrown away, however,
 704             // it's more sound logically to depend on the global object lifetime weakly.
 705             freeze(globalObject);
 706             watchpoints().addLazily(set);
 707             return true;
 708         }
 709
 710         return false;
 711     }
 712
 713     Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
 714
 715     DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
 716     DesiredWatchpoints& watchpoints() { return m_plan.watchpoints; }
 717
 718     // Returns false if the key is already invalid or unwatchable. If this is a Presence condition,
 719     // this also makes it cheap to query if the condition holds. Also makes sure that the GC knows
 720     // what's going on.
 721     bool watchCondition(const ObjectPropertyCondition&);
 722     bool watchConditions(const ObjectPropertyConditionSet&);
 723
 724     // Checks if it's known that loading from the given object at the given offset is fine. This is
 725     // computed by tracking which conditions we track with watchCondition().
 726     bool isSafeToLoad(JSObject* base, PropertyOffset);
 727
 728     void registerInferredType(const InferredType::Descriptor& type)
 729     {
 730         if (type.structure())
 731             registerStructure(type.structure());
 732     }
 733
 734     // Tells us what inferred type we are able to prove the property to have now and in the future.
 735     InferredType::Descriptor inferredTypeFor(const PropertyTypeKey&);
 736     InferredType::Descriptor inferredTypeForProperty(Structure* structure, UniquedStringImpl* uid)
 737     {
 738         return inferredTypeFor(PropertyTypeKey(structure, uid));
 739     }
 740
 741     AbstractValue inferredValueForProperty(
 742         const RegisteredStructureSet& base, UniquedStringImpl* uid, StructureClobberState = StructuresAreWatched);
 743
 744     // This uses either constant property inference or property type inference to derive a good abstract
 745     // value for some property accessed with the given abstract value base.
 746     AbstractValue inferredValueForProperty(
 747         const AbstractValue& base, UniquedStringImpl* uid, PropertyOffset, StructureClobberState);
 748
 749     FullBytecodeLiveness& livenessFor(CodeBlock*);
 750     FullBytecodeLiveness& livenessFor(InlineCallFrame*);
 751
 752     // Quickly query if a single local is live at the given point. This is faster than calling
 753     // forAllLiveInBytecode() if you will only query one local. But, if you want to know all of the
 754     // locals live, then calling this for each local is much slower than forAllLiveInBytecode().
 755     bool isLiveInBytecode(VirtualRegister, CodeOrigin);
 756
 757     // Quickly get all of the non-argument locals live at the given point. This doesn't give you
 758     // any arguments because those are all presumed live. You can call forAllLiveInBytecode() to
 759     // also get the arguments. This is much faster than calling isLiveInBytecode() for each local.
 760     template<typename Functor>
 761     void forAllLocalsLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
 762     {
 763         // Support for not redundantly reporting arguments. Necessary because in case of a varargs
 764         // call, only the callee knows that arguments are live while in the case of a non-varargs
 765         // call, both callee and caller will see the variables live.
 766         VirtualRegister exclusionStart;
 767         VirtualRegister exclusionEnd;
 768
 769         CodeOrigin* codeOriginPtr = &codeOrigin;
 770
 771         for (;;) {
 772             InlineCallFrame* inlineCallFrame = codeOriginPtr->inlineCallFrame;
 773             VirtualRegister stackOffset(inlineCallFrame ? inlineCallFrame->stackOffset : 0);
 774
 775             if (inlineCallFrame) {
 776                 if (inlineCallFrame->isClosureCall)
 777                     functor(stackOffset + CallFrameSlot::callee);
 778                 if (inlineCallFrame->isVarargs())
 779                     functor(stackOffset + CallFrameSlot::argumentCount);
 780             }
 781
 782             CodeBlock* codeBlock = baselineCodeBlockFor(inlineCallFrame);
 783             FullBytecodeLiveness& fullLiveness = livenessFor(codeBlock);
 784             const FastBitVector& liveness = fullLiveness.getLiveness(codeOriginPtr->bytecodeIndex);
 785             for (unsigned relativeLocal = codeBlock->m_numCalleeLocals; relativeLocal--;) {
 786                 VirtualRegister reg = stackOffset + virtualRegisterForLocal(relativeLocal);
 787
 788                 // Don't report if our callee already reported.
 789                 if (reg >= exclusionStart && reg < exclusionEnd)
 790                     continue;
 791
 792                 if (liveness[relativeLocal])
 793                     functor(reg);
 794             }
 795
 796             if (!inlineCallFrame)
 797                 break;
 798
 799             // Arguments are always live. This would be redundant if it wasn't for our
 800             // op_call_varargs inlining. See the comment above.
 801             exclusionStart = stackOffset + CallFrame::argumentOffsetIncludingThis(0);
 802             exclusionEnd = stackOffset + CallFrame::argumentOffsetIncludingThis(inlineCallFrame->arguments.size());
 803
 804             // We will always have a "this" argument and exclusionStart should be a smaller stack
 805             // offset than exclusionEnd.
 806             ASSERT(exclusionStart < exclusionEnd);
 807
 808             for (VirtualRegister reg = exclusionStart; reg < exclusionEnd; reg += 1)
 809                 functor(reg);
 810
 811             codeOriginPtr = inlineCallFrame->getCallerSkippingTailCalls();
 812
 813             // The first inline call frame could be an inline tail call
 814             if (!codeOriginPtr)
 815                 break;
 816         }
 817     }
 818
 819     // Get a BitVector of all of the non-argument locals live right now. This is mostly useful if
 820     // you want to compare two sets of live locals from two different CodeOrigins.
 821     BitVector localsLiveInBytecode(CodeOrigin);
 822
 823     // Tells you all of the arguments and locals live at the given CodeOrigin. This is a small
 824     // extension to forAllLocalsLiveInBytecode(), since all arguments are always presumed live.
 825     template<typename Functor>
 826     void forAllLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
 827     {
 828         forAllLocalsLiveInBytecode(codeOrigin, functor);
 829
 830         // Report all arguments as being live.
 831         for (unsigned argument = block(0)->variablesAtHead.numberOfArguments(); argument--;)
 832             functor(virtualRegisterForArgument(argument));
 833     }
 834
 835     BytecodeKills& killsFor(CodeBlock*);
 836     BytecodeKills& killsFor(InlineCallFrame*);
 837
 838     static unsigned parameterSlotsForArgCount(unsigned);
 839
 840     unsigned frameRegisterCount();
 841     unsigned stackPointerOffset();
 842     unsigned requiredRegisterCountForExit();
 843     unsigned requiredRegisterCountForExecutionAndExit();
 844
 845     JSValue tryGetConstantProperty(JSValue base, const RegisteredStructureSet&, PropertyOffset);
 846     JSValue tryGetConstantProperty(JSValue base, Structure*, PropertyOffset);
 847     JSValue tryGetConstantProperty(JSValue base, const StructureAbstractValue&, PropertyOffset);
 848     JSValue tryGetConstantProperty(const AbstractValue&, PropertyOffset);
 849
 850     JSValue tryGetConstantClosureVar(JSValue base, ScopeOffset);
 851     JSValue tryGetConstantClosureVar(const AbstractValue&, ScopeOffset);
 852     JSValue tryGetConstantClosureVar(Node*, ScopeOffset);
 853
 854     JSArrayBufferView* tryGetFoldableView(JSValue);
 855     JSArrayBufferView* tryGetFoldableView(JSValue, ArrayMode arrayMode);
 856
 857     void registerFrozenValues();
 858
 859     void visitChildren(SlotVisitor&) override;
 860
 861     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
 862         std::nullptr_t, const char* file, int line, const char* function,
 863         const char* assertion);
 864     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
 865         Node*, const char* file, int line, const char* function,
 866         const char* assertion);
 867     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
 868         BasicBlock*, const char* file, int line, const char* function,
 869         const char* assertion);
 870
 871     bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
 872
 873     Dominators& ensureDominators();
 874     PrePostNumbering& ensurePrePostNumbering();
 875     NaturalLoops& ensureNaturalLoops();
 876     BackwardsCFG& ensureBackwardsCFG();
 877     BackwardsDominators& ensureBackwardsDominators();
 878     ControlEquivalenceAnalysis& ensureControlEquivalenceAnalysis();
 879
 880     // This function only makes sense to call after bytecode parsing
 881     // because it queries the m_hasExceptionHandlers boolean whose value
 882     // is only fully determined after bytcode parsing.
 883     bool willCatchExceptionInMachineFrame(CodeOrigin, CodeOrigin& opCatchOriginOut, HandlerInfo*& catchHandlerOut);
 884
 885     bool needsScopeRegister() const { return m_hasDebuggerEnabled || m_codeBlock->usesEval(); }
 886     bool needsFlushedThis() const { return m_codeBlock->usesEval(); }
 887
 888     VM& m_vm;
 889     Plan& m_plan;
 890     CodeBlock* m_codeBlock;
 891     CodeBlock* m_profiledBlock;
 892
 893     NodeAllocator& m_allocator;
 894
 895     Vector< RefPtr<BasicBlock> , 8> m_blocks;
 896     Vector<Edge, 16> m_varArgChildren;
 897
 898     HashMap<EncodedJSValue, FrozenValue*, EncodedJSValueHash, EncodedJSValueHashTraits> m_frozenValueMap;
 899     Bag<FrozenValue> m_frozenValues;
 900
 901     Vector<uint32_t> m_uint32ValuesInUse;
 902
 903     Bag<StorageAccessData> m_storageAccessData;
 904
 905     // In CPS, this is all of the SetArgument nodes for the arguments in the machine code block
 906     // that survived DCE. All of them except maybe "this" will survive DCE, because of the Flush
 907     // nodes.
 908     //
 909     // In SSA, this is all of the GetStack nodes for the arguments in the machine code block that
 910     // may have some speculation in the prologue and survived DCE. Note that to get the speculation
 911     // for an argument in SSA, you must use m_argumentFormats, since we still have to speculate
 912     // even if the argument got killed. For example:
 913     //
 914     //     function foo(x) {
 915     //        var tmp = x + 1;
 916     //     }
 917     //
 918     // Assume that x is always int during profiling. The ArithAdd for "x + 1" will be dead and will
 919     // have a proven check for the edge to "x". So, we will not insert a Check node and we will
 920     // kill the GetStack for "x". But, we must do the int check in the progolue, because that's the
 921     // thing we used to allow DCE of ArithAdd. Otherwise the add could be impure:
 922     //
 923     //     var o = {
 924     //         valueOf: function() { do side effects; }
 925     //     };
 926     //     foo(o);
 927     //
 928     // If we DCE the ArithAdd and we remove the int check on x, then this won't do the side
 929     // effects.
 930     Vector<Node*, 8> m_arguments;
 931
 932     // In CPS, this is meaningless. In SSA, this is the argument speculation that we've locked in.
 933     Vector<FlushFormat> m_argumentFormats;
 934
 935     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
 936     SegmentedVector<ArgumentPosition, 8> m_argumentPositions;
 937     Bag<Transition> m_transitions;
 938     SegmentedVector<NewArrayBufferData, 4> m_newArrayBufferData;
 939     Bag<BranchData> m_branchData;
 940     Bag<SwitchData> m_switchData;
 941     Bag<MultiGetByOffsetData> m_multiGetByOffsetData;
 942     Bag<MultiPutByOffsetData> m_multiPutByOffsetData;
 943     Bag<ObjectMaterializationData> m_objectMaterializationData;
 944     Bag<CallVarargsData> m_callVarargsData;
 945     Bag<LoadVarargsData> m_loadVarargsData;
 946     Bag<StackAccessData> m_stackAccessData;
 947     Bag<LazyJSValue> m_lazyJSValues;
 948     Bag<CallDOMGetterData> m_callDOMGetterData;
 949     Bag<BitVector> m_bitVectors;
 950     Vector<InlineVariableData, 4> m_inlineVariableData;
 951     HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
 952     HashMap<CodeBlock*, std::unique_ptr<BytecodeKills>> m_bytecodeKills;
 953     HashSet<std::pair<JSObject*, PropertyOffset>> m_safeToLoad;
 954     HashMap<PropertyTypeKey, InferredType::Descriptor> m_inferredTypes;
 955     Vector<RefPtr<DOMJIT::Patchpoint>> m_domJITPatchpoints;
 956     std::unique_ptr<Dominators> m_dominators;
 957     std::unique_ptr<PrePostNumbering> m_prePostNumbering;
 958     std::unique_ptr<NaturalLoops> m_naturalLoops;
 959     std::unique_ptr<CFG> m_cfg;
 960     std::unique_ptr<BackwardsCFG> m_backwardsCFG;
 961     std::unique_ptr<BackwardsDominators> m_backwardsDominators;
 962     std::unique_ptr<ControlEquivalenceAnalysis> m_controlEquivalenceAnalysis;
 963     unsigned m_localVars;
 964     unsigned m_nextMachineLocal;
 965     unsigned m_parameterSlots;
 966
 967     HashSet<String> m_localStrings;
 968     HashMap<const StringImpl*, String> m_copiedStrings;
 969
 970 #if USE(JSVALUE32_64)
 971     std::unordered_map<int64_t, double*> m_doubleConstantsMap;
 972     std::unique_ptr<Bag<double>> m_doubleConstants;
 973 #endif
 974
 975     OptimizationFixpointState m_fixpointState;
 976     StructureRegistrationState m_structureRegistrationState;
 977     GraphForm m_form;
 978     UnificationState m_unificationState;
 979     PlanStage m_planStage { PlanStage::Initial };
 980     RefCountState m_refCountState;
 981     bool m_hasDebuggerEnabled;
 982     bool m_hasExceptionHandlers { false };
 983     std::unique_ptr<FlowIndexing> m_indexingCache;
 984     std::unique_ptr<FlowMap<AbstractValue>> m_abstractValuesCache;
 985
 986     RegisteredStructure stringStructure;
 987     RegisteredStructure symbolStructure;
 988
 989 private:
 990     void addNodeToMapByIndex(Node*);
 991
 992     bool isStringPrototypeMethodSane(JSGlobalObject*, UniquedStringImpl*);
 993
 994     void handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock*, BasicBlock* successor);
 995
 996     AddSpeculationMode addImmediateShouldSpeculateInt32(Node* add, bool variableShouldSpeculateInt32, Node* operand, Node*immediate, RareCaseProfilingSource source)
 997     {
 998         ASSERT(immediate->hasConstant());
 999
1000         JSValue immediateValue = immediate->asJSValue();
1001         if (!immediateValue.isNumber() && !immediateValue.isBoolean())
1002             return DontSpeculateInt32;
1003
1004         if (!variableShouldSpeculateInt32)
1005             return DontSpeculateInt32;
1006
1007         // Integer constants can be typed Double if they are written like a double in the source code (e.g. 42.0).
1008         // In that case, we stay conservative unless the other operand was explicitly typed as integer.
1009         NodeFlags operandResultType = operand->result();
1010         if (operandResultType != NodeResultInt32 && immediateValue.isDouble())
1011             return DontSpeculateInt32;
1012
1013         if (immediateValue.isBoolean() || jsNumber(immediateValue.asNumber()).isInt32())
1014             return add->canSpeculateInt32(source) ? SpeculateInt32 : DontSpeculateInt32;
1015
1016         double doubleImmediate = immediateValue.asDouble();
1017         const double twoToThe48 = 281474976710656.0;
1018         if (doubleImmediate < -twoToThe48 || doubleImmediate > twoToThe48)
1019             return DontSpeculateInt32;
1020
1021         return bytecodeCanTruncateInteger(add->arithNodeFlags()) ? SpeculateInt32AndTruncateConstants : DontSpeculateInt32;
1022     }
1023
1024     Vector<Node*, 0, UnsafeVectorOverflow> m_nodesByIndex;
1025     Vector<unsigned, 0, UnsafeVectorOverflow> m_nodeIndexFreeList;
1026     SegmentedVector<RegisteredStructureSet, 16> m_structureSets;
1027 };
1028
1029 } } // namespace JSC::DFG
1030
1031 #endif