dfg/DFGGraph.cpp

   1 /*
   2  * Copyright (C) 2011, 2013, 2014 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 #include "config.h"
  27 #include "DFGGraph.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "BytecodeLivenessAnalysisInlines.h"
  32 #include "CodeBlock.h"
  33 #include "CodeBlockWithJITType.h"
  34 #include "DFGClobberSet.h"
  35 #include "DFGJITCode.h"
  36 #include "DFGVariableAccessDataDump.h"
  37 #include "FullBytecodeLiveness.h"
  38 #include "FunctionExecutableDump.h"
  39 #include "JIT.h"
  40 #include "JSActivation.h"
  41 #include "MaxFrameExtentForSlowPathCall.h"
  42 #include "OperandsInlines.h"
  43 #include "JSCInlines.h"
  44 #include "StackAlignment.h"
  45 #include <wtf/CommaPrinter.h>
  46 #include <wtf/ListDump.h>
  47
  48 namespace JSC { namespace DFG {
  49
  50 // Creates an array of stringized names.
  51 static const char* dfgOpNames[] = {
  52 #define STRINGIZE_DFG_OP_ENUM(opcode, flags) #opcode ,
  53     FOR_EACH_DFG_OP(STRINGIZE_DFG_OP_ENUM)
  54 #undef STRINGIZE_DFG_OP_ENUM
  55 };
  56
  57 Graph::Graph(VM& vm, Plan& plan, LongLivedState& longLivedState)
  58     : m_vm(vm)
  59     , m_plan(plan)
  60     , m_codeBlock(m_plan.codeBlock.get())
  61     , m_profiledBlock(m_codeBlock->alternative())
  62     , m_allocator(longLivedState.m_allocator)
  63     , m_mustHandleAbstractValues(OperandsLike, plan.mustHandleValues)
  64     , m_hasArguments(false)
  65     , m_nextMachineLocal(0)
  66     , m_machineCaptureStart(std::numeric_limits<int>::max())
  67     , m_fixpointState(BeforeFixpoint)
  68     , m_form(LoadStore)
  69     , m_unificationState(LocallyUnified)
  70     , m_refCountState(EverythingIsLive)
  71 {
  72     ASSERT(m_profiledBlock);
  73
  74     for (unsigned i = m_mustHandleAbstractValues.size(); i--;)
  75         m_mustHandleAbstractValues[i].setMostSpecific(*this, plan.mustHandleValues[i]);
  76 }
  77
  78 Graph::~Graph()
  79 {
  80     m_allocator.freeAll();
  81 }
  82
  83 const char *Graph::opName(NodeType op)
  84 {
  85     return dfgOpNames[op];
  86 }
  87
  88 static void printWhiteSpace(PrintStream& out, unsigned amount)
  89 {
  90     while (amount-- > 0)
  91         out.print(" ");
  92 }
  93
  94 bool Graph::dumpCodeOrigin(PrintStream& out, const char* prefix, Node* previousNode, Node* currentNode, DumpContext* context)
  95 {
  96     if (!previousNode)
  97         return false;
  98
  99     if (previousNode->origin.semantic.inlineCallFrame == currentNode->origin.semantic.inlineCallFrame)
 100         return false;
 101
 102     Vector<CodeOrigin> previousInlineStack = previousNode->origin.semantic.inlineStack();
 103     Vector<CodeOrigin> currentInlineStack = currentNode->origin.semantic.inlineStack();
 104     unsigned commonSize = std::min(previousInlineStack.size(), currentInlineStack.size());
 105     unsigned indexOfDivergence = commonSize;
 106     for (unsigned i = 0; i < commonSize; ++i) {
 107         if (previousInlineStack[i].inlineCallFrame != currentInlineStack[i].inlineCallFrame) {
 108             indexOfDivergence = i;
 109             break;
 110         }
 111     }
 112
 113     bool hasPrinted = false;
 114
 115     // Print the pops.
 116     for (unsigned i = previousInlineStack.size(); i-- > indexOfDivergence;) {
 117         out.print(prefix);
 118         printWhiteSpace(out, i * 2);
 119         out.print("<-- ", inContext(*previousInlineStack[i].inlineCallFrame, context), "\n");
 120         hasPrinted = true;
 121     }
 122
 123     // Print the pushes.
 124     for (unsigned i = indexOfDivergence; i < currentInlineStack.size(); ++i) {
 125         out.print(prefix);
 126         printWhiteSpace(out, i * 2);
 127         out.print("--> ", inContext(*currentInlineStack[i].inlineCallFrame, context), "\n");
 128         hasPrinted = true;
 129     }
 130
 131     return hasPrinted;
 132 }
 133
 134 int Graph::amountOfNodeWhiteSpace(Node* node)
 135 {
 136     return (node->origin.semantic.inlineDepth() - 1) * 2;
 137 }
 138
 139 void Graph::printNodeWhiteSpace(PrintStream& out, Node* node)
 140 {
 141     printWhiteSpace(out, amountOfNodeWhiteSpace(node));
 142 }
 143
 144 void Graph::dump(PrintStream& out, const char* prefix, Node* node, DumpContext* context)
 145 {
 146     NodeType op = node->op();
 147
 148     unsigned refCount = node->refCount();
 149     bool skipped = !refCount;
 150     bool mustGenerate = node->mustGenerate();
 151     if (mustGenerate)
 152         --refCount;
 153
 154     out.print(prefix);
 155     printNodeWhiteSpace(out, node);
 156
 157     // Example/explanation of dataflow dump output
 158     //
 159     //   14:   <!2:7>  GetByVal(@3, @13)
 160     //   ^1     ^2 ^3     ^4       ^5
 161     //
 162     // (1) The nodeIndex of this operation.
 163     // (2) The reference count. The number printed is the 'real' count,
 164     //     not including the 'mustGenerate' ref. If the node is
 165     //     'mustGenerate' then the count it prefixed with '!'.
 166     // (3) The virtual register slot assigned to this node.
 167     // (4) The name of the operation.
 168     // (5) The arguments to the operation. The may be of the form:
 169     //         @#   - a NodeIndex referencing a prior node in the graph.
 170     //         arg# - an argument number.
 171     //         $#   - the index in the CodeBlock of a constant { for numeric constants the value is displayed | for integers, in both decimal and hex }.
 172     //         id#  - the index in the CodeBlock of an identifier { if codeBlock is passed to dump(), the string representation is displayed }.
 173     //         var# - the index of a var on the global object, used by GetGlobalVar/PutGlobalVar operations.
 174     out.printf("% 4d:%s<%c%u:", (int)node->index(), skipped ? "  skipped  " : "           ", mustGenerate ? '!' : ' ', refCount);
 175     if (node->hasResult() && !skipped && node->hasVirtualRegister())
 176         out.print(node->virtualRegister());
 177     else
 178         out.print("-");
 179     out.print(">\t", opName(op), "(");
 180     CommaPrinter comma;
 181     if (node->flags() & NodeHasVarArgs) {
 182         for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
 183             if (!m_varArgChildren[childIdx])
 184                 continue;
 185             out.print(comma, m_varArgChildren[childIdx]);
 186         }
 187     } else {
 188         if (!!node->child1() || !!node->child2() || !!node->child3())
 189             out.print(comma, node->child1());
 190         if (!!node->child2() || !!node->child3())
 191             out.print(comma, node->child2());
 192         if (!!node->child3())
 193             out.print(comma, node->child3());
 194     }
 195
 196     if (toCString(NodeFlagsDump(node->flags())) != "<empty>")
 197         out.print(comma, NodeFlagsDump(node->flags()));
 198     if (node->prediction())
 199         out.print(comma, SpeculationDump(node->prediction()));
 200     if (node->hasArrayMode())
 201         out.print(comma, node->arrayMode());
 202     if (node->hasArithMode())
 203         out.print(comma, node->arithMode());
 204     if (node->hasVarNumber())
 205         out.print(comma, node->varNumber());
 206     if (node->hasRegisterPointer())
 207         out.print(comma, "global", globalObjectFor(node->origin.semantic)->findRegisterIndex(node->registerPointer()), "(", RawPointer(node->registerPointer()), ")");
 208     if (node->hasIdentifier())
 209         out.print(comma, "id", node->identifierNumber(), "{", identifiers()[node->identifierNumber()], "}");
 210     if (node->hasStructureSet())
 211         out.print(comma, inContext(node->structureSet(), context));
 212     if (node->hasStructure())
 213         out.print(comma, inContext(*node->structure(), context));
 214     if (node->hasStructureTransitionData())
 215         out.print(comma, inContext(*node->structureTransitionData().previousStructure, context), " -> ", inContext(*node->structureTransitionData().newStructure, context));
 216     if (node->hasFunction()) {
 217         out.print(comma, "function(", RawPointer(node->function()), ", ");
 218         if (node->function()->inherits(JSFunction::info())) {
 219             JSFunction* function = jsCast<JSFunction*>(node->function());
 220             if (function->isHostFunction())
 221                 out.print("<host function>");
 222             else
 223                 out.print(FunctionExecutableDump(function->jsExecutable()));
 224         } else
 225             out.print("<not JSFunction>");
 226         out.print(")");
 227     }
 228     if (node->hasExecutable()) {
 229         if (node->executable()->inherits(FunctionExecutable::info()))
 230             out.print(comma, "executable(", FunctionExecutableDump(jsCast<FunctionExecutable*>(node->executable())), ")");
 231         else
 232             out.print(comma, "executable(not function: ", RawPointer(node->executable()), ")");
 233     }
 234     if (node->hasFunctionDeclIndex()) {
 235         FunctionExecutable* executable = m_codeBlock->functionDecl(node->functionDeclIndex());
 236         out.print(comma, FunctionExecutableDump(executable));
 237     }
 238     if (node->hasFunctionExprIndex()) {
 239         FunctionExecutable* executable = m_codeBlock->functionExpr(node->functionExprIndex());
 240         out.print(comma, FunctionExecutableDump(executable));
 241     }
 242     if (node->hasStorageAccessData()) {
 243         StorageAccessData& storageAccessData = m_storageAccessData[node->storageAccessDataIndex()];
 244         out.print(comma, "id", storageAccessData.identifierNumber, "{", identifiers()[storageAccessData.identifierNumber], "}");
 245         out.print(", ", static_cast<ptrdiff_t>(storageAccessData.offset));
 246     }
 247     if (node->hasMultiGetByOffsetData()) {
 248         MultiGetByOffsetData& data = node->multiGetByOffsetData();
 249         out.print(comma, "id", data.identifierNumber, "{", identifiers()[data.identifierNumber], "}");
 250         for (unsigned i = 0; i < data.variants.size(); ++i)
 251             out.print(comma, inContext(data.variants[i], context));
 252     }
 253     if (node->hasMultiPutByOffsetData()) {
 254         MultiPutByOffsetData& data = node->multiPutByOffsetData();
 255         out.print(comma, "id", data.identifierNumber, "{", identifiers()[data.identifierNumber], "}");
 256         for (unsigned i = 0; i < data.variants.size(); ++i)
 257             out.print(comma, inContext(data.variants[i], context));
 258     }
 259     ASSERT(node->hasVariableAccessData(*this) == node->hasLocal(*this));
 260     if (node->hasVariableAccessData(*this)) {
 261         VariableAccessData* variableAccessData = node->tryGetVariableAccessData();
 262         if (variableAccessData) {
 263             VirtualRegister operand = variableAccessData->local();
 264             if (operand.isArgument())
 265                 out.print(comma, "arg", operand.toArgument(), "(", VariableAccessDataDump(*this, variableAccessData), ")");
 266             else
 267                 out.print(comma, "loc", operand.toLocal(), "(", VariableAccessDataDump(*this, variableAccessData), ")");
 268
 269             operand = variableAccessData->machineLocal();
 270             if (operand.isValid()) {
 271                 if (operand.isArgument())
 272                     out.print(comma, "machine:arg", operand.toArgument());
 273                 else
 274                     out.print(comma, "machine:loc", operand.toLocal());
 275             }
 276         }
 277     }
 278     if (node->hasUnlinkedLocal()) {
 279         VirtualRegister operand = node->unlinkedLocal();
 280         if (operand.isArgument())
 281             out.print(comma, "arg", operand.toArgument());
 282         else
 283             out.print(comma, "loc", operand.toLocal());
 284     }
 285     if (node->hasUnlinkedMachineLocal()) {
 286         VirtualRegister operand = node->unlinkedMachineLocal();
 287         if (operand.isValid()) {
 288             if (operand.isArgument())
 289                 out.print(comma, "machine:arg", operand.toArgument());
 290             else
 291                 out.print(comma, "machine:loc", operand.toLocal());
 292         }
 293     }
 294     if (node->hasConstantBuffer()) {
 295         out.print(comma);
 296         out.print(node->startConstant(), ":[");
 297         CommaPrinter anotherComma;
 298         for (unsigned i = 0; i < node->numConstants(); ++i)
 299             out.print(anotherComma, inContext(m_codeBlock->constantBuffer(node->startConstant())[i], context));
 300         out.print("]");
 301     }
 302     if (node->hasIndexingType())
 303         out.print(comma, IndexingTypeDump(node->indexingType()));
 304     if (node->hasTypedArrayType())
 305         out.print(comma, node->typedArrayType());
 306     if (node->hasPhi())
 307         out.print(comma, "^", node->phi()->index());
 308     if (node->hasExecutionCounter())
 309         out.print(comma, RawPointer(node->executionCounter()));
 310     if (node->hasVariableWatchpointSet())
 311         out.print(comma, RawPointer(node->variableWatchpointSet()));
 312     if (node->hasTypedArray())
 313         out.print(comma, inContext(JSValue(node->typedArray()), context));
 314     if (node->hasStoragePointer())
 315         out.print(comma, RawPointer(node->storagePointer()));
 316     if (node->isConstant()) {
 317         out.print(comma, "$", node->constantNumber());
 318         JSValue value = valueOfJSConstant(node);
 319         out.print(" = ", inContext(value, context));
 320     }
 321     if (op == WeakJSConstant)
 322         out.print(comma, RawPointer(node->weakConstant()), " (", inContext(*node->weakConstant()->structure(), context), ")");
 323     if (node->isJump())
 324         out.print(comma, "T:", *node->targetBlock());
 325     if (node->isBranch())
 326         out.print(comma, "T:", node->branchData()->taken, ", F:", node->branchData()->notTaken);
 327     if (node->isSwitch()) {
 328         SwitchData* data = node->switchData();
 329         out.print(comma, data->kind);
 330         for (unsigned i = 0; i < data->cases.size(); ++i)
 331             out.print(comma, inContext(data->cases[i].value, context), ":", data->cases[i].target);
 332         out.print(comma, "default:", data->fallThrough);
 333     }
 334     ClobberSet reads;
 335     ClobberSet writes;
 336     addReadsAndWrites(*this, node, reads, writes);
 337     if (!reads.isEmpty())
 338         out.print(comma, "R:", sortedListDump(reads.direct(), ","));
 339     if (!writes.isEmpty())
 340         out.print(comma, "W:", sortedListDump(writes.direct(), ","));
 341     out.print(comma, "bc#", node->origin.semantic.bytecodeIndex);
 342     if (node->origin.semantic != node->origin.forExit)
 343         out.print(comma, "exit: ", node->origin.forExit);
 344
 345     out.print(")");
 346
 347     if (!skipped) {
 348         if (node->hasVariableAccessData(*this) && node->tryGetVariableAccessData())
 349             out.print("  predicting ", SpeculationDump(node->tryGetVariableAccessData()->prediction()));
 350         else if (node->hasHeapPrediction())
 351             out.print("  predicting ", SpeculationDump(node->getHeapPrediction()));
 352     }
 353
 354     out.print("\n");
 355 }
 356
 357 void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* block, PhiNodeDumpMode phiNodeDumpMode, DumpContext* context)
 358 {
 359     out.print(prefix, "Block ", *block, " (", inContext(block->at(0)->origin.semantic, context), "): ", block->isReachable ? "" : "(skipped)", block->isOSRTarget ? " (OSR target)" : "", "\n");
 360     if (block->executionCount == block->executionCount)
 361         out.print(prefix, "  Execution count: ", block->executionCount, "\n");
 362     out.print(prefix, "  Predecessors:");
 363     for (size_t i = 0; i < block->predecessors.size(); ++i)
 364         out.print(" ", *block->predecessors[i]);
 365     out.print("\n");
 366     if (m_dominators.isValid()) {
 367         out.print(prefix, "  Dominated by:");
 368         for (size_t i = 0; i < m_blocks.size(); ++i) {
 369             if (!m_dominators.dominates(i, block->index))
 370                 continue;
 371             out.print(" #", i);
 372         }
 373         out.print("\n");
 374         out.print(prefix, "  Dominates:");
 375         for (size_t i = 0; i < m_blocks.size(); ++i) {
 376             if (!m_dominators.dominates(block->index, i))
 377                 continue;
 378             out.print(" #", i);
 379         }
 380         out.print("\n");
 381     }
 382     if (m_naturalLoops.isValid()) {
 383         if (const NaturalLoop* loop = m_naturalLoops.headerOf(block)) {
 384             out.print(prefix, "  Loop header, contains:");
 385             Vector<BlockIndex> sortedBlockList;
 386             for (unsigned i = 0; i < loop->size(); ++i)
 387                 sortedBlockList.append(loop->at(i)->index);
 388             std::sort(sortedBlockList.begin(), sortedBlockList.end());
 389             for (unsigned i = 0; i < sortedBlockList.size(); ++i)
 390                 out.print(" #", sortedBlockList[i]);
 391             out.print("\n");
 392         }
 393
 394         Vector<const NaturalLoop*> containingLoops =
 395             m_naturalLoops.loopsOf(block);
 396         if (!containingLoops.isEmpty()) {
 397             out.print(prefix, "  Containing loop headers:");
 398             for (unsigned i = 0; i < containingLoops.size(); ++i)
 399                 out.print(" ", *containingLoops[i]->header());
 400             out.print("\n");
 401         }
 402     }
 403     if (!block->phis.isEmpty()) {
 404         out.print(prefix, "  Phi Nodes:");
 405         for (size_t i = 0; i < block->phis.size(); ++i) {
 406             Node* phiNode = block->phis[i];
 407             if (!phiNode->shouldGenerate() && phiNodeDumpMode == DumpLivePhisOnly)
 408                 continue;
 409             out.print(" @", phiNode->index(), "<", phiNode->refCount(), ">->(");
 410             if (phiNode->child1()) {
 411                 out.print("@", phiNode->child1()->index());
 412                 if (phiNode->child2()) {
 413                     out.print(", @", phiNode->child2()->index());
 414                     if (phiNode->child3())
 415                         out.print(", @", phiNode->child3()->index());
 416                 }
 417             }
 418             out.print(")", i + 1 < block->phis.size() ? "," : "");
 419         }
 420         out.print("\n");
 421     }
 422 }
 423
 424 void Graph::dump(PrintStream& out, DumpContext* context)
 425 {
 426     DumpContext myContext;
 427     myContext.graph = this;
 428     if (!context)
 429         context = &myContext;
 430
 431     dataLog("\n");
 432     dataLog("DFG for ", CodeBlockWithJITType(m_codeBlock, JITCode::DFGJIT), ":\n");
 433     dataLog("  Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "; Ref count state: ", m_refCountState, "\n");
 434     dataLog("\n");
 435
 436     Node* lastNode = 0;
 437     for (size_t b = 0; b < m_blocks.size(); ++b) {
 438         BasicBlock* block = m_blocks[b].get();
 439         if (!block)
 440             continue;
 441         dumpBlockHeader(out, "", block, DumpAllPhis, context);
 442         switch (m_form) {
 443         case LoadStore:
 444         case ThreadedCPS: {
 445             out.print("  vars before: ");
 446             if (block->cfaHasVisited)
 447                 out.print(inContext(block->valuesAtHead, context));
 448             else
 449                 out.print("<empty>");
 450             out.print("\n");
 451             out.print("  var links: ", block->variablesAtHead, "\n");
 452             break;
 453         }
 454
 455         case SSA: {
 456             RELEASE_ASSERT(block->ssa);
 457             out.print("  Availability: ", block->ssa->availabilityAtHead, "\n");
 458             out.print("  Live: ", nodeListDump(block->ssa->liveAtHead), "\n");
 459             out.print("  Values: ", nodeMapDump(block->ssa->valuesAtHead, context), "\n");
 460             break;
 461         } }
 462         for (size_t i = 0; i < block->size(); ++i) {
 463             dumpCodeOrigin(out, "", lastNode, block->at(i), context);
 464             dump(out, "", block->at(i), context);
 465             lastNode = block->at(i);
 466         }
 467         switch (m_form) {
 468         case LoadStore:
 469         case ThreadedCPS: {
 470             out.print("  vars after: ");
 471             if (block->cfaHasVisited)
 472                 out.print(inContext(block->valuesAtTail, context));
 473             else
 474                 out.print("<empty>");
 475             out.print("\n");
 476             out.print("  var links: ", block->variablesAtTail, "\n");
 477             break;
 478         }
 479
 480         case SSA: {
 481             RELEASE_ASSERT(block->ssa);
 482             out.print("  Availability: ", block->ssa->availabilityAtTail, "\n");
 483             out.print("  Live: ", nodeListDump(block->ssa->liveAtTail), "\n");
 484             out.print("  Values: ", nodeMapDump(block->ssa->valuesAtTail, context), "\n");
 485             break;
 486         } }
 487         dataLog("\n");
 488     }
 489
 490     if (!myContext.isEmpty()) {
 491         myContext.dump(WTF::dataFile());
 492         dataLog("\n");
 493     }
 494 }
 495
 496 void Graph::dethread()
 497 {
 498     if (m_form == LoadStore || m_form == SSA)
 499         return;
 500
 501     if (logCompilationChanges())
 502         dataLog("Dethreading DFG graph.\n");
 503
 504     SamplingRegion samplingRegion("DFG Dethreading");
 505
 506     for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) {
 507         BasicBlock* block = m_blocks[blockIndex].get();
 508         if (!block)
 509             continue;
 510         for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
 511             Node* phi = block->phis[phiIndex];
 512             phi->children.reset();
 513         }
 514     }
 515
 516     m_form = LoadStore;
 517 }
 518
 519 void Graph::handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock* block, BasicBlock* successor)
 520 {
 521     if (!successor->isReachable) {
 522         successor->isReachable = true;
 523         worklist.append(successor);
 524     }
 525
 526     successor->predecessors.append(block);
 527 }
 528
 529 void Graph::determineReachability()
 530 {
 531     Vector<BasicBlock*, 16> worklist;
 532     worklist.append(block(0));
 533     block(0)->isReachable = true;
 534     while (!worklist.isEmpty()) {
 535         BasicBlock* block = worklist.takeLast();
 536         for (unsigned i = block->numSuccessors(); i--;)
 537             handleSuccessor(worklist, block, block->successor(i));
 538     }
 539 }
 540
 541 void Graph::resetReachability()
 542 {
 543     for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) {
 544         BasicBlock* block = m_blocks[blockIndex].get();
 545         if (!block)
 546             continue;
 547         block->isReachable = false;
 548         block->predecessors.clear();
 549     }
 550
 551     determineReachability();
 552 }
 553
 554 void Graph::killBlockAndItsContents(BasicBlock* block)
 555 {
 556     for (unsigned phiIndex = block->phis.size(); phiIndex--;)
 557         m_allocator.free(block->phis[phiIndex]);
 558     for (unsigned nodeIndex = block->size(); nodeIndex--;)
 559         m_allocator.free(block->at(nodeIndex));
 560
 561     killBlock(block);
 562 }
 563
 564 void Graph::killUnreachableBlocks()
 565 {
 566     for (BlockIndex blockIndex = 0; blockIndex < numBlocks(); ++blockIndex) {
 567         BasicBlock* block = this->block(blockIndex);
 568         if (!block)
 569             continue;
 570         if (block->isReachable)
 571             continue;
 572
 573         killBlockAndItsContents(block);
 574     }
 575 }
 576
 577 void Graph::resetExitStates()
 578 {
 579     for (BlockIndex blockIndex = 0; blockIndex < m_blocks.size(); ++blockIndex) {
 580         BasicBlock* block = m_blocks[blockIndex].get();
 581         if (!block)
 582             continue;
 583         for (unsigned indexInBlock = block->size(); indexInBlock--;)
 584             block->at(indexInBlock)->setCanExit(true);
 585     }
 586 }
 587
 588 void Graph::invalidateCFG()
 589 {
 590     m_dominators.invalidate();
 591     m_naturalLoops.invalidate();
 592 }
 593
 594 void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
 595 {
 596     if (variableAccessData->isCaptured()) {
 597         // Let CSE worry about this one.
 598         return;
 599     }
 600     for (unsigned indexInBlock = startIndexInBlock; indexInBlock < block.size(); ++indexInBlock) {
 601         Node* node = block[indexInBlock];
 602         bool shouldContinue = true;
 603         switch (node->op()) {
 604         case SetLocal: {
 605             if (node->local() == variableAccessData->local())
 606                 shouldContinue = false;
 607             break;
 608         }
 609
 610         case GetLocal: {
 611             if (node->variableAccessData() != variableAccessData)
 612                 continue;
 613             substitute(block, indexInBlock, node, newGetLocal);
 614             Node* oldTailNode = block.variablesAtTail.operand(variableAccessData->local());
 615             if (oldTailNode == node)
 616                 block.variablesAtTail.operand(variableAccessData->local()) = newGetLocal;
 617             shouldContinue = false;
 618             break;
 619         }
 620
 621         default:
 622             break;
 623         }
 624         if (!shouldContinue)
 625             break;
 626     }
 627 }
 628
 629 void Graph::addForDepthFirstSort(Vector<BasicBlock*>& result, Vector<BasicBlock*, 16>& worklist, HashSet<BasicBlock*>& seen, BasicBlock* block)
 630 {
 631     if (seen.contains(block))
 632         return;
 633
 634     result.append(block);
 635     worklist.append(block);
 636     seen.add(block);
 637 }
 638
 639 void Graph::getBlocksInDepthFirstOrder(Vector<BasicBlock*>& result)
 640 {
 641     Vector<BasicBlock*, 16> worklist;
 642     HashSet<BasicBlock*> seen;
 643     addForDepthFirstSort(result, worklist, seen, block(0));
 644     while (!worklist.isEmpty()) {
 645         BasicBlock* block = worklist.takeLast();
 646         for (unsigned i = block->numSuccessors(); i--;)
 647             addForDepthFirstSort(result, worklist, seen, block->successor(i));
 648     }
 649 }
 650
 651 void Graph::clearReplacements()
 652 {
 653     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
 654         BasicBlock* block = m_blocks[blockIndex].get();
 655         if (!block)
 656             continue;
 657         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
 658             block->phis[phiIndex]->misc.replacement = 0;
 659         for (unsigned nodeIndex = block->size(); nodeIndex--;)
 660             block->at(nodeIndex)->misc.replacement = 0;
 661     }
 662 }
 663
 664 void Graph::initializeNodeOwners()
 665 {
 666     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
 667         BasicBlock* block = m_blocks[blockIndex].get();
 668         if (!block)
 669             continue;
 670         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
 671             block->phis[phiIndex]->misc.owner = block;
 672         for (unsigned nodeIndex = block->size(); nodeIndex--;)
 673             block->at(nodeIndex)->misc.owner = block;
 674     }
 675 }
 676
 677 void Graph::clearFlagsOnAllNodes(NodeFlags flags)
 678 {
 679     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
 680         BasicBlock* block = m_blocks[blockIndex].get();
 681         if (!block)
 682             continue;
 683         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
 684             block->phis[phiIndex]->clearFlags(flags);
 685         for (unsigned nodeIndex = block->size(); nodeIndex--;)
 686             block->at(nodeIndex)->clearFlags(flags);
 687     }
 688 }
 689
 690 FullBytecodeLiveness& Graph::livenessFor(CodeBlock* codeBlock)
 691 {
 692     HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>>::iterator iter = m_bytecodeLiveness.find(codeBlock);
 693     if (iter != m_bytecodeLiveness.end())
 694         return *iter->value;
 695
 696     std::unique_ptr<FullBytecodeLiveness> liveness = std::make_unique<FullBytecodeLiveness>();
 697     codeBlock->livenessAnalysis().computeFullLiveness(*liveness);
 698     FullBytecodeLiveness& result = *liveness;
 699     m_bytecodeLiveness.add(codeBlock, WTF::move(liveness));
 700     return result;
 701 }
 702
 703 FullBytecodeLiveness& Graph::livenessFor(InlineCallFrame* inlineCallFrame)
 704 {
 705     return livenessFor(baselineCodeBlockFor(inlineCallFrame));
 706 }
 707
 708 bool Graph::isLiveInBytecode(VirtualRegister operand, CodeOrigin codeOrigin)
 709 {
 710     for (;;) {
 711         VirtualRegister reg = VirtualRegister(
 712             operand.offset() - codeOrigin.stackOffset());
 713
 714         if (operand.offset() < codeOrigin.stackOffset() + JSStack::CallFrameHeaderSize) {
 715             if (reg.isArgument()) {
 716                 RELEASE_ASSERT(reg.offset() < JSStack::CallFrameHeaderSize);
 717
 718                 if (!codeOrigin.inlineCallFrame->isClosureCall)
 719                     return false;
 720
 721                 if (reg.offset() == JSStack::Callee)
 722                     return true;
 723                 if (reg.offset() == JSStack::ScopeChain)
 724                     return true;
 725
 726                 return false;
 727             }
 728
 729             return livenessFor(codeOrigin.inlineCallFrame).operandIsLive(
 730                 reg.offset(), codeOrigin.bytecodeIndex);
 731         }
 732
 733         InlineCallFrame* inlineCallFrame = codeOrigin.inlineCallFrame;
 734         if (!inlineCallFrame)
 735             break;
 736
 737         // Arguments are always live. This would be redundant if it wasn't for our
 738         // op_call_varargs inlining.
 739         // FIXME: 'this' might not be live, but we don't have a way of knowing.
 740         // https://bugs.webkit.org/show_bug.cgi?id=128519
 741         if (reg.isArgument()
 742             && static_cast<size_t>(reg.toArgument()) < inlineCallFrame->arguments.size())
 743             return true;
 744
 745         codeOrigin = inlineCallFrame->caller;
 746     }
 747
 748     return true;
 749 }
 750
 751 unsigned Graph::frameRegisterCount()
 752 {
 753     unsigned result = m_nextMachineLocal + std::max(m_parameterSlots, static_cast<unsigned>(maxFrameExtentForSlowPathCallInRegisters));
 754     return roundLocalRegisterCountForFramePointerOffset(result);
 755 }
 756
 757 unsigned Graph::stackPointerOffset()
 758 {
 759     return virtualRegisterForLocal(frameRegisterCount() - 1).offset();
 760 }
 761
 762 unsigned Graph::requiredRegisterCountForExit()
 763 {
 764     unsigned count = JIT::frameRegisterCountFor(m_profiledBlock);
 765     for (InlineCallFrameSet::iterator iter = m_plan.inlineCallFrames->begin(); !!iter; ++iter) {
 766         InlineCallFrame* inlineCallFrame = *iter;
 767         CodeBlock* codeBlock = baselineCodeBlockForInlineCallFrame(inlineCallFrame);
 768         unsigned requiredCount = VirtualRegister(inlineCallFrame->stackOffset).toLocal() + 1 + JIT::frameRegisterCountFor(codeBlock);
 769         count = std::max(count, requiredCount);
 770     }
 771     return count;
 772 }
 773
 774 unsigned Graph::requiredRegisterCountForExecutionAndExit()
 775 {
 776     return std::max(frameRegisterCount(), requiredRegisterCountForExit());
 777 }
 778
 779 JSActivation* Graph::tryGetActivation(Node* node)
 780 {
 781     if (!node->hasConstant())
 782         return 0;
 783     return jsDynamicCast<JSActivation*>(valueOfJSConstant(node));
 784 }
 785
 786 WriteBarrierBase<Unknown>* Graph::tryGetRegisters(Node* node)
 787 {
 788     JSActivation* activation = tryGetActivation(node);
 789     if (!activation)
 790         return 0;
 791     if (!activation->isTornOff())
 792         return 0;
 793     return activation->registers();
 794 }
 795
 796 JSArrayBufferView* Graph::tryGetFoldableView(Node* node)
 797 {
 798     if (!node->hasConstant())
 799         return 0;
 800     JSArrayBufferView* view = jsDynamicCast<JSArrayBufferView*>(valueOfJSConstant(node));
 801     if (!view)
 802         return 0;
 803     if (!watchpoints().isStillValid(view))
 804         return 0;
 805     return view;
 806 }
 807
 808 JSArrayBufferView* Graph::tryGetFoldableView(Node* node, ArrayMode arrayMode)
 809 {
 810     if (arrayMode.typedArrayType() == NotTypedArray)
 811         return 0;
 812     return tryGetFoldableView(node);
 813 }
 814
 815 JSArrayBufferView* Graph::tryGetFoldableViewForChild1(Node* node)
 816 {
 817     return tryGetFoldableView(child(node, 0).node(), node->arrayMode());
 818 }
 819
 820 void Graph::visitChildren(SlotVisitor& visitor)
 821 {
 822     for (BlockIndex blockIndex = numBlocks(); blockIndex--;) {
 823         BasicBlock* block = this->block(blockIndex);
 824         if (!block)
 825             continue;
 826
 827         for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
 828             Node* node = block->at(nodeIndex);
 829
 830             switch (node->op()) {
 831             case JSConstant:
 832             case WeakJSConstant:
 833                 visitor.appendUnbarrieredReadOnlyValue(valueOfJSConstant(node));
 834                 break;
 835
 836             case CheckFunction:
 837                 visitor.appendUnbarrieredReadOnlyPointer(node->function());
 838                 break;
 839
 840             case CheckExecutable:
 841                 visitor.appendUnbarrieredReadOnlyPointer(node->executable());
 842                 break;
 843
 844             case CheckStructure:
 845                 for (unsigned i = node->structureSet().size(); i--;)
 846                     visitor.appendUnbarrieredReadOnlyPointer(node->structureSet()[i]);
 847                 break;
 848
 849             case StructureTransitionWatchpoint:
 850             case NewObject:
 851             case ArrayifyToStructure:
 852             case NewStringObject:
 853                 visitor.appendUnbarrieredReadOnlyPointer(node->structure());
 854                 break;
 855
 856             case PutStructure:
 857             case PhantomPutStructure:
 858             case AllocatePropertyStorage:
 859             case ReallocatePropertyStorage:
 860                 visitor.appendUnbarrieredReadOnlyPointer(
 861                     node->structureTransitionData().previousStructure);
 862                 visitor.appendUnbarrieredReadOnlyPointer(
 863                     node->structureTransitionData().newStructure);
 864                 break;
 865
 866             default:
 867                 break;
 868             }
 869         }
 870     }
 871 }
 872
 873 } } // namespace JSC::DFG
 874
 875 #endif // ENABLE(DFG_JIT)