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         if (hasExitSite(add, Int52Overflow))
 297             return false;
 298
 299         if (Node::shouldSpeculateAnyInt(left, right))
 300             return true;
 301
 302         auto shouldSpeculateAnyIntForAdd = [](Node* node) {
 303             auto isAnyIntSpeculationForAdd = [](SpeculatedType value) {
 304                 return !!value && (value & (SpecAnyInt | SpecAnyIntAsDouble)) == value;
 305             };
 306
 307             // When DoubleConstant node appears, it means that users explicitly write a constant in their code with double form instead of integer form (1.0 instead of 1).
 308             // In that case, we should honor this decision: using it as integer is not appropriate.
 309             if (node->op() == DoubleConstant)
 310                 return false;
 311             return isAnyIntSpeculationForAdd(node->prediction());
 312         };
 313
 314         // Allow AnyInt ArithAdd only when the one side of the binary operation should be speculated AnyInt. It is a bit conservative
 315         // decision. This is because Double to Int52 conversion is not so cheap. Frequent back-and-forth conversions between Double and Int52
 316         // rather hurt the performance. If the one side of the operation is already Int52, the cost for constructing ArithAdd becomes
 317         // cheap since only one Double to Int52 conversion could be required.
 318         // This recovers some regression in assorted tests while keeping kraken crypto improvements.
 319         if (!left->shouldSpeculateAnyInt() && !right->shouldSpeculateAnyInt())
 320             return false;
 321
 322         auto usesAsNumbers = [](Node* node) {
 323             NodeFlags flags = node->flags() & NodeBytecodeBackPropMask;
 324             if (!flags)
 325                 return false;
 326             return (flags & (NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex)) == flags;
 327         };
 328
 329         // Wrapping Int52 to Value is also not so cheap. Thus, we allow Int52 addition only when the node is used as number.
 330         if (!usesAsNumbers(add))
 331             return false;
 332
 333         return shouldSpeculateAnyIntForAdd(left) && shouldSpeculateAnyIntForAdd(right);
 334     }
 335
 336     bool binaryArithShouldSpeculateInt32(Node* node, PredictionPass pass)
 337     {
 338         Node* left = node->child1().node();
 339         Node* right = node->child2().node();
 340
 341         return Node::shouldSpeculateInt32OrBooleanForArithmetic(left, right)
 342             && node->canSpeculateInt32(node->sourceFor(pass));
 343     }
 344
 345     bool binaryArithShouldSpeculateAnyInt(Node* node, PredictionPass pass)
 346     {
 347         if (!enableInt52())
 348             return false;
 349
 350         Node* left = node->child1().node();
 351         Node* right = node->child2().node();
 352
 353         return Node::shouldSpeculateAnyInt(left, right)
 354             && node->canSpeculateInt52(pass)
 355             && !hasExitSite(node, Int52Overflow);
 356     }
 357
 358     bool unaryArithShouldSpeculateInt32(Node* node, PredictionPass pass)
 359     {
 360         return node->child1()->shouldSpeculateInt32OrBooleanForArithmetic()
 361             && node->canSpeculateInt32(pass);
 362     }
 363
 364     bool unaryArithShouldSpeculateAnyInt(Node* node, PredictionPass pass)
 365     {
 366         if (!enableInt52())
 367             return false;
 368         return node->child1()->shouldSpeculateAnyInt()
 369             && node->canSpeculateInt52(pass)
 370             && !hasExitSite(node, Int52Overflow);
 371     }
 372
 373     bool canOptimizeStringObjectAccess(const CodeOrigin&);
 374
 375     bool getRegExpPrototypeProperty(JSObject* regExpPrototype, Structure* regExpPrototypeStructure, UniquedStringImpl* uid, JSValue& returnJSValue);
 376
 377     bool roundShouldSpeculateInt32(Node* arithRound, PredictionPass pass)
 378     {
 379         ASSERT(arithRound->op() == ArithRound || arithRound->op() == ArithFloor || arithRound->op() == ArithCeil || arithRound->op() == ArithTrunc);
 380         return arithRound->canSpeculateInt32(pass) && !hasExitSite(arithRound->origin.semantic, Overflow) && !hasExitSite(arithRound->origin.semantic, NegativeZero);
 381     }
 382
 383     static const char *opName(NodeType);
 384
 385     RegisteredStructureSet* addStructureSet(const StructureSet& structureSet)
 386     {
 387         m_structureSets.append();
 388         RegisteredStructureSet* result = &m_structureSets.last();
 389
 390         for (Structure* structure : structureSet)
 391             result->add(registerStructure(structure));
 392
 393         return result;
 394     }
 395
 396     RegisteredStructureSet* addStructureSet(const RegisteredStructureSet& structureSet)
 397     {
 398         m_structureSets.append();
 399         RegisteredStructureSet* result = &m_structureSets.last();
 400
 401         for (RegisteredStructure structure : structureSet)
 402             result->add(structure);
 403
 404         return result;
 405     }
 406
 407     JSGlobalObject* globalObjectFor(CodeOrigin codeOrigin)
 408     {
 409         return m_codeBlock->globalObjectFor(codeOrigin);
 410     }
 411
 412     JSObject* globalThisObjectFor(CodeOrigin codeOrigin)
 413     {
 414         JSGlobalObject* object = globalObjectFor(codeOrigin);
 415         return jsCast<JSObject*>(object->methodTable()->toThis(object, object->globalExec(), NotStrictMode));
 416     }
 417
 418     ScriptExecutable* executableFor(InlineCallFrame* inlineCallFrame)
 419     {
 420         if (!inlineCallFrame)
 421             return m_codeBlock->ownerScriptExecutable();
 422
 423         return inlineCallFrame->baselineCodeBlock->ownerScriptExecutable();
 424     }
 425
 426     ScriptExecutable* executableFor(const CodeOrigin& codeOrigin)
 427     {
 428         return executableFor(codeOrigin.inlineCallFrame);
 429     }
 430
 431     CodeBlock* baselineCodeBlockFor(InlineCallFrame* inlineCallFrame)
 432     {
 433         if (!inlineCallFrame)
 434             return m_profiledBlock;
 435         return baselineCodeBlockForInlineCallFrame(inlineCallFrame);
 436     }
 437
 438     CodeBlock* baselineCodeBlockFor(const CodeOrigin& codeOrigin)
 439     {
 440         return baselineCodeBlockForOriginAndBaselineCodeBlock(codeOrigin, m_profiledBlock);
 441     }
 442
 443     bool isStrictModeFor(CodeOrigin codeOrigin)
 444     {
 445         if (!codeOrigin.inlineCallFrame)
 446             return m_codeBlock->isStrictMode();
 447         return codeOrigin.inlineCallFrame->isStrictMode();
 448     }
 449
 450     ECMAMode ecmaModeFor(CodeOrigin codeOrigin)
 451     {
 452         return isStrictModeFor(codeOrigin) ? StrictMode : NotStrictMode;
 453     }
 454
 455     bool masqueradesAsUndefinedWatchpointIsStillValid(const CodeOrigin& codeOrigin)
 456     {
 457         return globalObjectFor(codeOrigin)->masqueradesAsUndefinedWatchpoint()->isStillValid();
 458     }
 459
 460     bool hasGlobalExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
 461     {
 462         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(exitKind));
 463     }
 464
 465     bool hasExitSite(const CodeOrigin& codeOrigin, ExitKind exitKind)
 466     {
 467         return baselineCodeBlockFor(codeOrigin)->hasExitSite(FrequentExitSite(codeOrigin.bytecodeIndex, exitKind));
 468     }
 469
 470     bool hasExitSite(Node* node, ExitKind exitKind)
 471     {
 472         return hasExitSite(node->origin.semantic, exitKind);
 473     }
 474
 475     MethodOfGettingAValueProfile methodOfGettingAValueProfileFor(Node* currentNode, Node* operandNode);
 476
 477     BlockIndex numBlocks() const { return m_blocks.size(); }
 478     BasicBlock* block(BlockIndex blockIndex) const { return m_blocks[blockIndex].get(); }
 479     BasicBlock* lastBlock() const { return block(numBlocks() - 1); }
 480
 481     void appendBlock(Ref<BasicBlock>&& basicBlock)
 482     {
 483         basicBlock->index = m_blocks.size();
 484         m_blocks.append(WTFMove(basicBlock));
 485     }
 486
 487     void killBlock(BlockIndex blockIndex)
 488     {
 489         m_blocks[blockIndex] = nullptr;
 490     }
 491
 492     void killBlock(BasicBlock* basicBlock)
 493     {
 494         killBlock(basicBlock->index);
 495     }
 496
 497     void killBlockAndItsContents(BasicBlock*);
 498
 499     void killUnreachableBlocks();
 500
 501     void determineReachability();
 502     void resetReachability();
 503
 504     void computeRefCounts();
 505
 506     unsigned varArgNumChildren(Node* node)
 507     {
 508         ASSERT(node->flags() & NodeHasVarArgs);
 509         return node->numChildren();
 510     }
 511
 512     unsigned numChildren(Node* node)
 513     {
 514         if (node->flags() & NodeHasVarArgs)
 515             return varArgNumChildren(node);
 516         return AdjacencyList::Size;
 517     }
 518
 519     Edge& varArgChild(Node* node, unsigned index)
 520     {
 521         ASSERT(node->flags() & NodeHasVarArgs);
 522         return m_varArgChildren[node->firstChild() + index];
 523     }
 524
 525     Edge& child(Node* node, unsigned index)
 526     {
 527         if (node->flags() & NodeHasVarArgs)
 528             return varArgChild(node, index);
 529         return node->children.child(index);
 530     }
 531
 532     void voteNode(Node* node, unsigned ballot, float weight = 1)
 533     {
 534         switch (node->op()) {
 535         case ValueToInt32:
 536         case UInt32ToNumber:
 537             node = node->child1().node();
 538             break;
 539         default:
 540             break;
 541         }
 542
 543         if (node->op() == GetLocal)
 544             node->variableAccessData()->vote(ballot, weight);
 545     }
 546
 547     void voteNode(Edge edge, unsigned ballot, float weight = 1)
 548     {
 549         voteNode(edge.node(), ballot, weight);
 550     }
 551
 552     void voteChildren(Node* node, unsigned ballot, float weight = 1)
 553     {
 554         if (node->flags() & NodeHasVarArgs) {
 555             for (unsigned childIdx = node->firstChild();
 556                 childIdx < node->firstChild() + node->numChildren();
 557                 childIdx++) {
 558                 if (!!m_varArgChildren[childIdx])
 559                     voteNode(m_varArgChildren[childIdx], ballot, weight);
 560             }
 561             return;
 562         }
 563
 564         if (!node->child1())
 565             return;
 566         voteNode(node->child1(), ballot, weight);
 567         if (!node->child2())
 568             return;
 569         voteNode(node->child2(), ballot, weight);
 570         if (!node->child3())
 571             return;
 572         voteNode(node->child3(), ballot, weight);
 573     }
 574
 575     template<typename T> // T = Node* or Edge
 576     void substitute(BasicBlock& block, unsigned startIndexInBlock, T oldThing, T newThing)
 577     {
 578         for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
 579             Node* node = block[indexInBlock];
 580             if (node->flags() & NodeHasVarArgs) {
 581                 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); ++childIdx) {
 582                     if (!!m_varArgChildren[childIdx])
 583                         compareAndSwap(m_varArgChildren[childIdx], oldThing, newThing);
 584                 }
 585                 continue;
 586             }
 587             if (!node->child1())
 588                 continue;
 589             compareAndSwap(node->children.child1(), oldThing, newThing);
 590             if (!node->child2())
 591                 continue;
 592             compareAndSwap(node->children.child2(), oldThing, newThing);
 593             if (!node->child3())
 594                 continue;
 595             compareAndSwap(node->children.child3(), oldThing, newThing);
 596         }
 597     }
 598
 599     // Use this if you introduce a new GetLocal and you know that you introduced it *before*
 600     // any GetLocals in the basic block.
 601     // FIXME: it may be appropriate, in the future, to generalize this to handle GetLocals
 602     // introduced anywhere in the basic block.
 603     void substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal);
 604
 605     void invalidateCFG();
 606     void invalidateNodeLiveness();
 607
 608     void clearFlagsOnAllNodes(NodeFlags);
 609
 610     void clearReplacements();
 611     void clearEpochs();
 612     void initializeNodeOwners();
 613
 614     BlockList blocksInPreOrder();
 615     BlockList blocksInPostOrder();
 616
 617     class NaturalBlockIterable {
 618     public:
 619         NaturalBlockIterable()
 620             : m_graph(nullptr)
 621         {
 622         }
 623
 624         NaturalBlockIterable(Graph& graph)
 625             : m_graph(&graph)
 626         {
 627         }
 628
 629         class iterator {
 630         public:
 631             iterator()
 632                 : m_graph(nullptr)
 633                 , m_index(0)
 634             {
 635             }
 636
 637             iterator(Graph& graph, BlockIndex index)
 638                 : m_graph(&graph)
 639                 , m_index(findNext(index))
 640             {
 641             }
 642
 643             BasicBlock *operator*()
 644             {
 645                 return m_graph->block(m_index);
 646             }
 647
 648             iterator& operator++()
 649             {
 650                 m_index = findNext(m_index + 1);
 651                 return *this;
 652             }
 653
 654             bool operator==(const iterator& other) const
 655             {
 656                 return m_index == other.m_index;
 657             }
 658
 659             bool operator!=(const iterator& other) const
 660             {
 661                 return !(*this == other);
 662             }
 663
 664         private:
 665             BlockIndex findNext(BlockIndex index)
 666             {
 667                 while (index < m_graph->numBlocks() && !m_graph->block(index))
 668                     index++;
 669                 return index;
 670             }
 671
 672             Graph* m_graph;
 673             BlockIndex m_index;
 674         };
 675
 676         iterator begin()
 677         {
 678             return iterator(*m_graph, 0);
 679         }
 680
 681         iterator end()
 682         {
 683             return iterator(*m_graph, m_graph->numBlocks());
 684         }
 685
 686     private:
 687         Graph* m_graph;
 688     };
 689
 690     NaturalBlockIterable blocksInNaturalOrder()
 691     {
 692         return NaturalBlockIterable(*this);
 693     }
 694
 695     template<typename ChildFunctor>
 696     void doToChildrenWithNode(Node* node, const ChildFunctor& functor)
 697     {
 698         DFG_NODE_DO_TO_CHILDREN(*this, node, functor);
 699     }
 700
 701     template<typename ChildFunctor>
 702     void doToChildren(Node* node, const ChildFunctor& functor)
 703     {
 704         doToChildrenWithNode(
 705             node,
 706             [&functor] (Node*, Edge& edge) {
 707                 functor(edge);
 708             });
 709     }
 710
 711     bool uses(Node* node, Node* child)
 712     {
 713         bool result = false;
 714         doToChildren(node, [&] (Edge edge) { result |= edge == child; });
 715         return result;
 716     }
 717
 718     bool isWatchingHavingABadTimeWatchpoint(Node* node)
 719     {
 720         JSGlobalObject* globalObject = globalObjectFor(node->origin.semantic);
 721         return watchpoints().isWatched(globalObject->havingABadTimeWatchpoint());
 722     }
 723
 724     bool isWatchingArrayIteratorProtocolWatchpoint(Node* node)
 725     {
 726         JSGlobalObject* globalObject = globalObjectFor(node->origin.semantic);
 727         InlineWatchpointSet& set = globalObject->arrayIteratorProtocolWatchpoint();
 728         if (watchpoints().isWatched(set))
 729             return true;
 730
 731         if (set.isStillValid()) {
 732             // Since the global object owns this watchpoint, we make ourselves have a weak pointer to it.
 733             // If the global object got deallocated, it wouldn't fire the watchpoint. It's unlikely the
 734             // global object would get deallocated without this code ever getting thrown away, however,
 735             // it's more sound logically to depend on the global object lifetime weakly.
 736             freeze(globalObject);
 737             watchpoints().addLazily(set);
 738             return true;
 739         }
 740
 741         return false;
 742     }
 743
 744     Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
 745
 746     DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
 747     DesiredWatchpoints& watchpoints() { return m_plan.watchpoints; }
 748
 749     // Returns false if the key is already invalid or unwatchable. If this is a Presence condition,
 750     // this also makes it cheap to query if the condition holds. Also makes sure that the GC knows
 751     // what's going on.
 752     bool watchCondition(const ObjectPropertyCondition&);
 753     bool watchConditions(const ObjectPropertyConditionSet&);
 754
 755     // Checks if it's known that loading from the given object at the given offset is fine. This is
 756     // computed by tracking which conditions we track with watchCondition().
 757     bool isSafeToLoad(JSObject* base, PropertyOffset);
 758
 759     void registerInferredType(const InferredType::Descriptor& type)
 760     {
 761         if (type.structure())
 762             registerStructure(type.structure());
 763     }
 764
 765     // Tells us what inferred type we are able to prove the property to have now and in the future.
 766     InferredType::Descriptor inferredTypeFor(const PropertyTypeKey&);
 767     InferredType::Descriptor inferredTypeForProperty(Structure* structure, UniquedStringImpl* uid)
 768     {
 769         return inferredTypeFor(PropertyTypeKey(structure, uid));
 770     }
 771
 772     AbstractValue inferredValueForProperty(
 773         const RegisteredStructureSet& base, UniquedStringImpl* uid, StructureClobberState = StructuresAreWatched);
 774
 775     // This uses either constant property inference or property type inference to derive a good abstract
 776     // value for some property accessed with the given abstract value base.
 777     AbstractValue inferredValueForProperty(
 778         const AbstractValue& base, UniquedStringImpl* uid, PropertyOffset, StructureClobberState);
 779
 780     FullBytecodeLiveness& livenessFor(CodeBlock*);
 781     FullBytecodeLiveness& livenessFor(InlineCallFrame*);
 782
 783     // Quickly query if a single local is live at the given point. This is faster than calling
 784     // forAllLiveInBytecode() if you will only query one local. But, if you want to know all of the
 785     // locals live, then calling this for each local is much slower than forAllLiveInBytecode().
 786     bool isLiveInBytecode(VirtualRegister, CodeOrigin);
 787
 788     // Quickly get all of the non-argument locals live at the given point. This doesn't give you
 789     // any arguments because those are all presumed live. You can call forAllLiveInBytecode() to
 790     // also get the arguments. This is much faster than calling isLiveInBytecode() for each local.
 791     template<typename Functor>
 792     void forAllLocalsLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
 793     {
 794         // Support for not redundantly reporting arguments. Necessary because in case of a varargs
 795         // call, only the callee knows that arguments are live while in the case of a non-varargs
 796         // call, both callee and caller will see the variables live.
 797         VirtualRegister exclusionStart;
 798         VirtualRegister exclusionEnd;
 799
 800         CodeOrigin* codeOriginPtr = &codeOrigin;
 801
 802         for (;;) {
 803             InlineCallFrame* inlineCallFrame = codeOriginPtr->inlineCallFrame;
 804             VirtualRegister stackOffset(inlineCallFrame ? inlineCallFrame->stackOffset : 0);
 805
 806             if (inlineCallFrame) {
 807                 if (inlineCallFrame->isClosureCall)
 808                     functor(stackOffset + CallFrameSlot::callee);
 809                 if (inlineCallFrame->isVarargs())
 810                     functor(stackOffset + CallFrameSlot::argumentCount);
 811             }
 812
 813             CodeBlock* codeBlock = baselineCodeBlockFor(inlineCallFrame);
 814             FullBytecodeLiveness& fullLiveness = livenessFor(codeBlock);
 815             const FastBitVector& liveness = fullLiveness.getLiveness(codeOriginPtr->bytecodeIndex);
 816             for (unsigned relativeLocal = codeBlock->m_numCalleeLocals; relativeLocal--;) {
 817                 VirtualRegister reg = stackOffset + virtualRegisterForLocal(relativeLocal);
 818
 819                 // Don't report if our callee already reported.
 820                 if (reg >= exclusionStart && reg < exclusionEnd)
 821                     continue;
 822
 823                 if (liveness[relativeLocal])
 824                     functor(reg);
 825             }
 826
 827             if (!inlineCallFrame)
 828                 break;
 829
 830             // Arguments are always live. This would be redundant if it wasn't for our
 831             // op_call_varargs inlining. See the comment above.
 832             exclusionStart = stackOffset + CallFrame::argumentOffsetIncludingThis(0);
 833             exclusionEnd = stackOffset + CallFrame::argumentOffsetIncludingThis(inlineCallFrame->arguments.size());
 834
 835             // We will always have a "this" argument and exclusionStart should be a smaller stack
 836             // offset than exclusionEnd.
 837             ASSERT(exclusionStart < exclusionEnd);
 838
 839             for (VirtualRegister reg = exclusionStart; reg < exclusionEnd; reg += 1)
 840                 functor(reg);
 841
 842             codeOriginPtr = inlineCallFrame->getCallerSkippingTailCalls();
 843
 844             // The first inline call frame could be an inline tail call
 845             if (!codeOriginPtr)
 846                 break;
 847         }
 848     }
 849
 850     // Get a BitVector of all of the non-argument locals live right now. This is mostly useful if
 851     // you want to compare two sets of live locals from two different CodeOrigins.
 852     BitVector localsLiveInBytecode(CodeOrigin);
 853
 854     // Tells you all of the arguments and locals live at the given CodeOrigin. This is a small
 855     // extension to forAllLocalsLiveInBytecode(), since all arguments are always presumed live.
 856     template<typename Functor>
 857     void forAllLiveInBytecode(CodeOrigin codeOrigin, const Functor& functor)
 858     {
 859         forAllLocalsLiveInBytecode(codeOrigin, functor);
 860
 861         // Report all arguments as being live.
 862         for (unsigned argument = block(0)->variablesAtHead.numberOfArguments(); argument--;)
 863             functor(virtualRegisterForArgument(argument));
 864     }
 865
 866     BytecodeKills& killsFor(CodeBlock*);
 867     BytecodeKills& killsFor(InlineCallFrame*);
 868
 869     static unsigned parameterSlotsForArgCount(unsigned);
 870
 871     unsigned frameRegisterCount();
 872     unsigned stackPointerOffset();
 873     unsigned requiredRegisterCountForExit();
 874     unsigned requiredRegisterCountForExecutionAndExit();
 875
 876     JSValue tryGetConstantProperty(JSValue base, const RegisteredStructureSet&, PropertyOffset);
 877     JSValue tryGetConstantProperty(JSValue base, Structure*, PropertyOffset);
 878     JSValue tryGetConstantProperty(JSValue base, const StructureAbstractValue&, PropertyOffset);
 879     JSValue tryGetConstantProperty(const AbstractValue&, PropertyOffset);
 880
 881     JSValue tryGetConstantClosureVar(JSValue base, ScopeOffset);
 882     JSValue tryGetConstantClosureVar(const AbstractValue&, ScopeOffset);
 883     JSValue tryGetConstantClosureVar(Node*, ScopeOffset);
 884
 885     JSArrayBufferView* tryGetFoldableView(JSValue);
 886     JSArrayBufferView* tryGetFoldableView(JSValue, ArrayMode arrayMode);
 887
 888     void registerFrozenValues();
 889
 890     void visitChildren(SlotVisitor&) override;
 891
 892     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
 893         std::nullptr_t, const char* file, int line, const char* function,
 894         const char* assertion);
 895     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
 896         Node*, const char* file, int line, const char* function,
 897         const char* assertion);
 898     NO_RETURN_DUE_TO_CRASH void handleAssertionFailure(
 899         BasicBlock*, const char* file, int line, const char* function,
 900         const char* assertion);
 901
 902     bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
 903
 904     Dominators& ensureDominators();
 905     PrePostNumbering& ensurePrePostNumbering();
 906     NaturalLoops& ensureNaturalLoops();
 907     BackwardsCFG& ensureBackwardsCFG();
 908     BackwardsDominators& ensureBackwardsDominators();
 909     ControlEquivalenceAnalysis& ensureControlEquivalenceAnalysis();
 910
 911     // This function only makes sense to call after bytecode parsing
 912     // because it queries the m_hasExceptionHandlers boolean whose value
 913     // is only fully determined after bytcode parsing.
 914     bool willCatchExceptionInMachineFrame(CodeOrigin, CodeOrigin& opCatchOriginOut, HandlerInfo*& catchHandlerOut);
 915
 916     bool needsScopeRegister() const { return m_hasDebuggerEnabled || m_codeBlock->usesEval(); }
 917     bool needsFlushedThis() const { return m_codeBlock->usesEval(); }
 918
 919     VM& m_vm;
 920     Plan& m_plan;
 921     CodeBlock* m_codeBlock;
 922     CodeBlock* m_profiledBlock;
 923
 924     NodeAllocator& m_allocator;
 925
 926     Vector< RefPtr<BasicBlock> , 8> m_blocks;
 927     Vector<Edge, 16> m_varArgChildren;
 928
 929     HashMap<EncodedJSValue, FrozenValue*, EncodedJSValueHash, EncodedJSValueHashTraits> m_frozenValueMap;
 930     Bag<FrozenValue> m_frozenValues;
 931
 932     Vector<uint32_t> m_uint32ValuesInUse;
 933
 934     Bag<StorageAccessData> m_storageAccessData;
 935
 936     // In CPS, this is all of the SetArgument nodes for the arguments in the machine code block
 937     // that survived DCE. All of them except maybe "this" will survive DCE, because of the Flush
 938     // nodes.
 939     //
 940     // In SSA, this is all of the GetStack nodes for the arguments in the machine code block that
 941     // may have some speculation in the prologue and survived DCE. Note that to get the speculation
 942     // for an argument in SSA, you must use m_argumentFormats, since we still have to speculate
 943     // even if the argument got killed. For example:
 944     //
 945     //     function foo(x) {
 946     //        var tmp = x + 1;
 947     //     }
 948     //
 949     // Assume that x is always int during profiling. The ArithAdd for "x + 1" will be dead and will
 950     // have a proven check for the edge to "x". So, we will not insert a Check node and we will
 951     // kill the GetStack for "x". But, we must do the int check in the progolue, because that's the
 952     // thing we used to allow DCE of ArithAdd. Otherwise the add could be impure:
 953     //
 954     //     var o = {
 955     //         valueOf: function() { do side effects; }
 956     //     };
 957     //     foo(o);
 958     //
 959     // If we DCE the ArithAdd and we remove the int check on x, then this won't do the side
 960     // effects.
 961     Vector<Node*, 8> m_arguments;
 962
 963     // In CPS, this is meaningless. In SSA, this is the argument speculation that we've locked in.
 964     Vector<FlushFormat> m_argumentFormats;
 965
 966     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
 967     SegmentedVector<ArgumentPosition, 8> m_argumentPositions;
 968     Bag<Transition> m_transitions;
 969     SegmentedVector<NewArrayBufferData, 4> m_newArrayBufferData;
 970     Bag<BranchData> m_branchData;
 971     Bag<SwitchData> m_switchData;
 972     Bag<MultiGetByOffsetData> m_multiGetByOffsetData;
 973     Bag<MultiPutByOffsetData> m_multiPutByOffsetData;
 974     Bag<ObjectMaterializationData> m_objectMaterializationData;
 975     Bag<CallVarargsData> m_callVarargsData;
 976     Bag<LoadVarargsData> m_loadVarargsData;
 977     Bag<StackAccessData> m_stackAccessData;
 978     Bag<LazyJSValue> m_lazyJSValues;
 979     Bag<CallDOMGetterData> m_callDOMGetterData;
 980     Bag<BitVector> m_bitVectors;
 981     Vector<InlineVariableData, 4> m_inlineVariableData;
 982     HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
 983     HashMap<CodeBlock*, std::unique_ptr<BytecodeKills>> m_bytecodeKills;
 984     HashSet<std::pair<JSObject*, PropertyOffset>> m_safeToLoad;
 985     HashMap<PropertyTypeKey, InferredType::Descriptor> m_inferredTypes;
 986     Vector<RefPtr<DOMJIT::Patchpoint>> m_domJITPatchpoints;
 987     std::unique_ptr<Dominators> m_dominators;
 988     std::unique_ptr<PrePostNumbering> m_prePostNumbering;
 989     std::unique_ptr<NaturalLoops> m_naturalLoops;
 990     std::unique_ptr<CFG> m_cfg;
 991     std::unique_ptr<BackwardsCFG> m_backwardsCFG;
 992     std::unique_ptr<BackwardsDominators> m_backwardsDominators;
 993     std::unique_ptr<ControlEquivalenceAnalysis> m_controlEquivalenceAnalysis;
 994     unsigned m_localVars;
 995     unsigned m_nextMachineLocal;
 996     unsigned m_parameterSlots;
 997
 998     HashSet<String> m_localStrings;
 999     HashMap<const StringImpl*, String> m_copiedStrings;
1000
1001 #if USE(JSVALUE32_64)
1002     std::unordered_map<int64_t, double*> m_doubleConstantsMap;
1003     std::unique_ptr<Bag<double>> m_doubleConstants;
1004 #endif
1005
1006     OptimizationFixpointState m_fixpointState;
1007     StructureRegistrationState m_structureRegistrationState;
1008     GraphForm m_form;
1009     UnificationState m_unificationState;
1010     PlanStage m_planStage { PlanStage::Initial };
1011     RefCountState m_refCountState;
1012     bool m_hasDebuggerEnabled;
1013     bool m_hasExceptionHandlers { false };
1014     std::unique_ptr<FlowIndexing> m_indexingCache;
1015     std::unique_ptr<FlowMap<AbstractValue>> m_abstractValuesCache;
1016
1017     RegisteredStructure stringStructure;
1018     RegisteredStructure symbolStructure;
1019
1020 private:
1021     void addNodeToMapByIndex(Node*);
1022
1023     bool isStringPrototypeMethodSane(JSGlobalObject*, UniquedStringImpl*);
1024
1025     void handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock*, BasicBlock* successor);
1026
1027     AddSpeculationMode addImmediateShouldSpeculateInt32(Node* add, bool variableShouldSpeculateInt32, Node* operand, Node*immediate, RareCaseProfilingSource source)
1028     {
1029         ASSERT(immediate->hasConstant());
1030
1031         JSValue immediateValue = immediate->asJSValue();
1032         if (!immediateValue.isNumber() && !immediateValue.isBoolean())
1033             return DontSpeculateInt32;
1034
1035         if (!variableShouldSpeculateInt32)
1036             return DontSpeculateInt32;
1037
1038         // Integer constants can be typed Double if they are written like a double in the source code (e.g. 42.0).
1039         // In that case, we stay conservative unless the other operand was explicitly typed as integer.
1040         NodeFlags operandResultType = operand->result();
1041         if (operandResultType != NodeResultInt32 && immediateValue.isDouble())
1042             return DontSpeculateInt32;
1043
1044         if (immediateValue.isBoolean() || jsNumber(immediateValue.asNumber()).isInt32())
1045             return add->canSpeculateInt32(source) ? SpeculateInt32 : DontSpeculateInt32;
1046
1047         double doubleImmediate = immediateValue.asDouble();
1048         const double twoToThe48 = 281474976710656.0;
1049         if (doubleImmediate < -twoToThe48 || doubleImmediate > twoToThe48)
1050             return DontSpeculateInt32;
1051
1052         return bytecodeCanTruncateInteger(add->arithNodeFlags()) ? SpeculateInt32AndTruncateConstants : DontSpeculateInt32;
1053     }
1054
1055     Vector<Node*, 0, UnsafeVectorOverflow> m_nodesByIndex;
1056     Vector<unsigned, 0, UnsafeVectorOverflow> m_nodeIndexFreeList;
1057     SegmentedVector<RegisteredStructureSet, 16> m_structureSets;
1058 };
1059
1060 } } // namespace JSC::DFG
1061
1062 #endif