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 48namespace JSC { namespace DFG { 49 50// Creates an array of stringized names. 51static 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 57Graph::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 78Graph::~Graph() 79{ 80 m_allocator.freeAll(); 81} 82 83const char *Graph::opName(NodeType op) 84{ 85 return dfgOpNames[op]; 86} 87 88static void printWhiteSpace(PrintStream& out, unsigned amount) 89{ 90 while (amount-- > 0) 91 out.print(" "); 92} 93 94bool 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 134int Graph::amountOfNodeWhiteSpace(Node* node) 135{ 136 return (node->origin.semantic.inlineDepth() - 1) * 2; 137} 138 139void Graph::printNodeWhiteSpace(PrintStream& out, Node* node) 140{ 141 printWhiteSpace(out, amountOfNodeWhiteSpace(node)); 142} 143 144void 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 357void 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 424void 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 496void 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 519void 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 529void 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 541void 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 554void 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 564void 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 577void 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 588void Graph::invalidateCFG() 589{ 590 m_dominators.invalidate(); 591 m_naturalLoops.invalidate(); 592} 593 594void 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 629void 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 639void 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 651void 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 664void 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 677void 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 690FullBytecodeLiveness& 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 703FullBytecodeLiveness& Graph::livenessFor(InlineCallFrame* inlineCallFrame) 704{ 705 return livenessFor(baselineCodeBlockFor(inlineCallFrame)); 706} 707 708bool 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 751unsigned Graph::frameRegisterCount() 752{ 753 unsigned result = m_nextMachineLocal + std::max(m_parameterSlots, static_cast<unsigned>(maxFrameExtentForSlowPathCallInRegisters)); 754 return roundLocalRegisterCountForFramePointerOffset(result); 755} 756 757unsigned Graph::stackPointerOffset() 758{ 759 return virtualRegisterForLocal(frameRegisterCount() - 1).offset(); 760} 761 762unsigned 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 774unsigned Graph::requiredRegisterCountForExecutionAndExit() 775{ 776 return std::max(frameRegisterCount(), requiredRegisterCountForExit()); 777} 778 779JSActivation* Graph::tryGetActivation(Node* node) 780{ 781 if (!node->hasConstant()) 782 return 0; 783 return jsDynamicCast<JSActivation*>(valueOfJSConstant(node)); 784} 785 786WriteBarrierBase<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 796JSArrayBufferView* 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 808JSArrayBufferView* Graph::tryGetFoldableView(Node* node, ArrayMode arrayMode) 809{ 810 if (arrayMode.typedArrayType() == NotTypedArray) 811 return 0; 812 return tryGetFoldableView(node); 813} 814 815JSArrayBufferView* Graph::tryGetFoldableViewForChild1(Node* node) 816{ 817 return tryGetFoldableView(child(node, 0).node(), node->arrayMode()); 818} 819 820void 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) 876