1/* 2 * Copyright (C) 2011 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#include "CodeBlock.h" 30#include "CodeBlockWithJITType.h" 31#include "DFGVariableAccessDataDump.h" 32#include "FunctionExecutableDump.h" 33#include "Operations.h" 34#include <wtf/CommaPrinter.h> 35 36#if ENABLE(DFG_JIT) 37 38namespace JSC { namespace DFG { 39 40// Creates an array of stringized names. 41static const char* dfgOpNames[] = { 42#define STRINGIZE_DFG_OP_ENUM(opcode, flags) #opcode , 43 FOR_EACH_DFG_OP(STRINGIZE_DFG_OP_ENUM) 44#undef STRINGIZE_DFG_OP_ENUM 45}; 46 47Graph::Graph(VM& vm, CodeBlock* codeBlock, unsigned osrEntryBytecodeIndex, const Operands<JSValue>& mustHandleValues) 48 : m_vm(vm) 49 , m_codeBlock(codeBlock) 50 , m_compilation(vm.m_perBytecodeProfiler ? vm.m_perBytecodeProfiler->newCompilation(codeBlock, Profiler::DFG) : 0) 51 , m_profiledBlock(codeBlock->alternative()) 52 , m_allocator(vm.m_dfgState->m_allocator) 53 , m_hasArguments(false) 54 , m_osrEntryBytecodeIndex(osrEntryBytecodeIndex) 55 , m_mustHandleValues(mustHandleValues) 56 , m_fixpointState(BeforeFixpoint) 57 , m_form(LoadStore) 58 , m_unificationState(LocallyUnified) 59 , m_refCountState(EverythingIsLive) 60{ 61 ASSERT(m_profiledBlock); 62} 63 64Graph::~Graph() 65{ 66 m_allocator.freeAll(); 67} 68 69const char *Graph::opName(NodeType op) 70{ 71 return dfgOpNames[op]; 72} 73 74static void printWhiteSpace(PrintStream& out, unsigned amount) 75{ 76 while (amount-- > 0) 77 out.print(" "); 78} 79 80bool Graph::dumpCodeOrigin(PrintStream& out, const char* prefix, Node* previousNode, Node* currentNode) 81{ 82 if (!previousNode) 83 return false; 84 85 if (previousNode->codeOrigin.inlineCallFrame == currentNode->codeOrigin.inlineCallFrame) 86 return false; 87 88 Vector<CodeOrigin> previousInlineStack = previousNode->codeOrigin.inlineStack(); 89 Vector<CodeOrigin> currentInlineStack = currentNode->codeOrigin.inlineStack(); 90 unsigned commonSize = std::min(previousInlineStack.size(), currentInlineStack.size()); 91 unsigned indexOfDivergence = commonSize; 92 for (unsigned i = 0; i < commonSize; ++i) { 93 if (previousInlineStack[i].inlineCallFrame != currentInlineStack[i].inlineCallFrame) { 94 indexOfDivergence = i; 95 break; 96 } 97 } 98 99 bool hasPrinted = false; 100 101 // Print the pops. 102 for (unsigned i = previousInlineStack.size(); i-- > indexOfDivergence;) { 103 out.print(prefix); 104 printWhiteSpace(out, i * 2); 105 out.print("<-- ", *previousInlineStack[i].inlineCallFrame, "\n"); 106 hasPrinted = true; 107 } 108 109 // Print the pushes. 110 for (unsigned i = indexOfDivergence; i < currentInlineStack.size(); ++i) { 111 out.print(prefix); 112 printWhiteSpace(out, i * 2); 113 out.print("--> ", *currentInlineStack[i].inlineCallFrame, "\n"); 114 hasPrinted = true; 115 } 116 117 return hasPrinted; 118} 119 120int Graph::amountOfNodeWhiteSpace(Node* node) 121{ 122 return (node->codeOrigin.inlineDepth() - 1) * 2; 123} 124 125void Graph::printNodeWhiteSpace(PrintStream& out, Node* node) 126{ 127 printWhiteSpace(out, amountOfNodeWhiteSpace(node)); 128} 129 130void Graph::dump(PrintStream& out, const char* prefix, Node* node) 131{ 132 NodeType op = node->op(); 133 134 unsigned refCount = node->refCount(); 135 bool skipped = !refCount; 136 bool mustGenerate = node->mustGenerate(); 137 if (mustGenerate) 138 --refCount; 139 140 out.print(prefix); 141 printNodeWhiteSpace(out, node); 142 143 // Example/explanation of dataflow dump output 144 // 145 // 14: <!2:7> GetByVal(@3, @13) 146 // ^1 ^2 ^3 ^4 ^5 147 // 148 // (1) The nodeIndex of this operation. 149 // (2) The reference count. The number printed is the 'real' count, 150 // not including the 'mustGenerate' ref. If the node is 151 // 'mustGenerate' then the count it prefixed with '!'. 152 // (3) The virtual register slot assigned to this node. 153 // (4) The name of the operation. 154 // (5) The arguments to the operation. The may be of the form: 155 // @# - a NodeIndex referencing a prior node in the graph. 156 // arg# - an argument number. 157 // $# - the index in the CodeBlock of a constant { for numeric constants the value is displayed | for integers, in both decimal and hex }. 158 // id# - the index in the CodeBlock of an identifier { if codeBlock is passed to dump(), the string representation is displayed }. 159 // var# - the index of a var on the global object, used by GetGlobalVar/PutGlobalVar operations. 160 out.printf("% 4d:%s<%c%u:", (int)node->index(), skipped ? " skipped " : " ", mustGenerate ? '!' : ' ', refCount); 161 if (node->hasResult() && !skipped && node->hasVirtualRegister()) 162 out.print(node->virtualRegister()); 163 else 164 out.print("-"); 165 out.print(">\t", opName(op), "("); 166 CommaPrinter comma; 167 if (node->flags() & NodeHasVarArgs) { 168 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) { 169 if (!m_varArgChildren[childIdx]) 170 continue; 171 out.print(comma, m_varArgChildren[childIdx]); 172 } 173 } else { 174 if (!!node->child1() || !!node->child2() || !!node->child3()) 175 out.print(comma, node->child1()); 176 if (!!node->child2() || !!node->child3()) 177 out.print(comma, node->child2()); 178 if (!!node->child3()) 179 out.print(comma, node->child3()); 180 } 181 182 if (toCString(NodeFlagsDump(node->flags())) != "<empty>") 183 out.print(comma, NodeFlagsDump(node->flags())); 184 if (node->hasArrayMode()) 185 out.print(comma, node->arrayMode()); 186 if (node->hasVarNumber()) 187 out.print(comma, node->varNumber()); 188 if (node->hasRegisterPointer()) 189 out.print(comma, "global", globalObjectFor(node->codeOrigin)->findRegisterIndex(node->registerPointer()), "(", RawPointer(node->registerPointer()), ")"); 190 if (node->hasIdentifier()) 191 out.print(comma, "id", node->identifierNumber(), "{", m_codeBlock->identifier(node->identifierNumber()).string(), "}"); 192 if (node->hasStructureSet()) { 193 for (size_t i = 0; i < node->structureSet().size(); ++i) 194 out.print(comma, "struct(", RawPointer(node->structureSet()[i]), ": ", IndexingTypeDump(node->structureSet()[i]->indexingType()), ")"); 195 } 196 if (node->hasStructure()) 197 out.print(comma, "struct(", RawPointer(node->structure()), ": ", IndexingTypeDump(node->structure()->indexingType()), ")"); 198 if (node->hasStructureTransitionData()) 199 out.print(comma, "struct(", RawPointer(node->structureTransitionData().previousStructure), " -> ", RawPointer(node->structureTransitionData().newStructure), ")"); 200 if (node->hasFunction()) { 201 out.print(comma, "function(", RawPointer(node->function()), ", "); 202 if (node->function()->inherits(&JSFunction::s_info)) { 203 JSFunction* function = jsCast<JSFunction*>(node->function()); 204 if (function->isHostFunction()) 205 out.print("<host function>"); 206 else 207 out.print(FunctionExecutableDump(function->jsExecutable())); 208 } else 209 out.print("<not JSFunction>"); 210 out.print(")"); 211 } 212 if (node->hasExecutable()) { 213 if (node->executable()->inherits(&FunctionExecutable::s_info)) 214 out.print(comma, "executable(", FunctionExecutableDump(jsCast<FunctionExecutable*>(node->executable())), ")"); 215 else 216 out.print(comma, "executable(not function: ", RawPointer(node->executable()), ")"); 217 } 218 if (node->hasFunctionDeclIndex()) { 219 FunctionExecutable* executable = m_codeBlock->functionDecl(node->functionDeclIndex()); 220 out.print(comma, executable->inferredName().string(), "#", executable->hashFor(CodeForCall)); 221 } 222 if (node->hasFunctionExprIndex()) { 223 FunctionExecutable* executable = m_codeBlock->functionExpr(node->functionExprIndex()); 224 out.print(comma, executable->inferredName().string(), "#", executable->hashFor(CodeForCall)); 225 } 226 if (node->hasStorageAccessData()) { 227 StorageAccessData& storageAccessData = m_storageAccessData[node->storageAccessDataIndex()]; 228 out.print(comma, "id", storageAccessData.identifierNumber, "{", m_codeBlock->identifier(storageAccessData.identifierNumber).string(), "}"); 229 out.print(", ", static_cast<ptrdiff_t>(storageAccessData.offset)); 230 } 231 ASSERT(node->hasVariableAccessData() == node->hasLocal()); 232 if (node->hasVariableAccessData()) { 233 VariableAccessData* variableAccessData = node->variableAccessData(); 234 int operand = variableAccessData->operand(); 235 if (operandIsArgument(operand)) 236 out.print(comma, "arg", operandToArgument(operand), "(", VariableAccessDataDump(*this, variableAccessData), ")"); 237 else 238 out.print(comma, "r", operand, "(", VariableAccessDataDump(*this, variableAccessData), ")"); 239 } 240 if (node->hasConstantBuffer()) { 241 out.print(comma); 242 out.print(node->startConstant(), ":["); 243 CommaPrinter anotherComma; 244 for (unsigned i = 0; i < node->numConstants(); ++i) 245 out.print(anotherComma, m_codeBlock->constantBuffer(node->startConstant())[i]); 246 out.print("]"); 247 } 248 if (node->hasIndexingType()) 249 out.print(comma, IndexingTypeDump(node->indexingType())); 250 if (node->hasExecutionCounter()) 251 out.print(comma, RawPointer(node->executionCounter())); 252 if (op == JSConstant) { 253 out.print(comma, "$", node->constantNumber()); 254 JSValue value = valueOfJSConstant(node); 255 out.print(" = ", value); 256 } 257 if (op == WeakJSConstant) 258 out.print(comma, RawPointer(node->weakConstant())); 259 if (node->isBranch() || node->isJump()) 260 out.print(comma, "T:#", node->takenBlockIndex()); 261 if (node->isBranch()) 262 out.print(comma, "F:#", node->notTakenBlockIndex()); 263 out.print(comma, "bc#", node->codeOrigin.bytecodeIndex); 264 265 out.print(")"); 266 267 if (!skipped) { 268 if (node->hasVariableAccessData()) 269 out.print(" predicting ", SpeculationDump(node->variableAccessData()->prediction()), node->variableAccessData()->shouldUseDoubleFormat() ? ", forcing double" : ""); 270 else if (node->hasHeapPrediction()) 271 out.print(" predicting ", SpeculationDump(node->getHeapPrediction())); 272 } 273 274 out.print("\n"); 275} 276 277void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BlockIndex blockIndex, PhiNodeDumpMode phiNodeDumpMode) 278{ 279 BasicBlock* block = m_blocks[blockIndex].get(); 280 281 out.print(prefix, "Block #", blockIndex, " (", block->at(0)->codeOrigin, "): ", block->isReachable ? "" : "(skipped)", block->isOSRTarget ? " (OSR target)" : "", "\n"); 282 out.print(prefix, " Predecessors:"); 283 for (size_t i = 0; i < block->m_predecessors.size(); ++i) 284 out.print(" #", block->m_predecessors[i]); 285 out.print("\n"); 286 if (m_dominators.isValid()) { 287 out.print(prefix, " Dominated by:"); 288 for (size_t i = 0; i < m_blocks.size(); ++i) { 289 if (!m_dominators.dominates(i, blockIndex)) 290 continue; 291 out.print(" #", i); 292 } 293 out.print("\n"); 294 out.print(prefix, " Dominates:"); 295 for (size_t i = 0; i < m_blocks.size(); ++i) { 296 if (!m_dominators.dominates(blockIndex, i)) 297 continue; 298 out.print(" #", i); 299 } 300 out.print("\n"); 301 } 302 out.print(prefix, " Phi Nodes:"); 303 for (size_t i = 0; i < block->phis.size(); ++i) { 304 Node* phiNode = block->phis[i]; 305 if (!phiNode->shouldGenerate() && phiNodeDumpMode == DumpLivePhisOnly) 306 continue; 307 out.print(" @", phiNode->index(), "<", phiNode->refCount(), ">->("); 308 if (phiNode->child1()) { 309 out.print("@", phiNode->child1()->index()); 310 if (phiNode->child2()) { 311 out.print(", @", phiNode->child2()->index()); 312 if (phiNode->child3()) 313 out.print(", @", phiNode->child3()->index()); 314 } 315 } 316 out.print(")", i + 1 < block->phis.size() ? "," : ""); 317 } 318 out.print("\n"); 319} 320 321void Graph::dump(PrintStream& out) 322{ 323 dataLog("DFG for ", CodeBlockWithJITType(m_codeBlock, JITCode::DFGJIT), ":\n"); 324 dataLog(" Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "; Ref count state: ", m_refCountState, "\n"); 325 326 out.print(" ArgumentPosition size: ", m_argumentPositions.size(), "\n"); 327 for (size_t i = 0; i < m_argumentPositions.size(); ++i) { 328 out.print(" #", i, ": "); 329 ArgumentPosition& arguments = m_argumentPositions[i]; 330 arguments.dump(out, this); 331 } 332 333 Node* lastNode = 0; 334 for (size_t b = 0; b < m_blocks.size(); ++b) { 335 BasicBlock* block = m_blocks[b].get(); 336 if (!block) 337 continue; 338 dumpBlockHeader(out, "", b, DumpAllPhis); 339 out.print(" vars before: "); 340 if (block->cfaHasVisited) 341 dumpOperands(block->valuesAtHead, out); 342 else 343 out.print("<empty>"); 344 out.print("\n"); 345 out.print(" var links: "); 346 dumpOperands(block->variablesAtHead, out); 347 out.print("\n"); 348 for (size_t i = 0; i < block->size(); ++i) { 349 dumpCodeOrigin(out, "", lastNode, block->at(i)); 350 dump(out, "", block->at(i)); 351 lastNode = block->at(i); 352 } 353 out.print(" vars after: "); 354 if (block->cfaHasVisited) 355 dumpOperands(block->valuesAtTail, out); 356 else 357 out.print("<empty>"); 358 out.print("\n"); 359 out.print(" var links: "); 360 dumpOperands(block->variablesAtTail, out); 361 out.print("\n"); 362 } 363} 364 365void Graph::dethread() 366{ 367 if (m_form == LoadStore) 368 return; 369 370 if (logCompilationChanges()) 371 dataLog("Dethreading DFG graph.\n"); 372 373 SamplingRegion samplingRegion("DFG Dethreading"); 374 375 for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) { 376 BasicBlock* block = m_blocks[blockIndex].get(); 377 if (!block) 378 continue; 379 for (unsigned phiIndex = block->phis.size(); phiIndex--;) { 380 Node* phi = block->phis[phiIndex]; 381 phi->children.reset(); 382 } 383 } 384 385 m_form = LoadStore; 386} 387 388void Graph::handleSuccessor(Vector<BlockIndex, 16>& worklist, BlockIndex blockIndex, BlockIndex successorIndex) 389{ 390 BasicBlock* successor = m_blocks[successorIndex].get(); 391 if (!successor->isReachable) { 392 successor->isReachable = true; 393 worklist.append(successorIndex); 394 } 395 396 successor->m_predecessors.append(blockIndex); 397} 398 399void Graph::determineReachability() 400{ 401 Vector<BlockIndex, 16> worklist; 402 worklist.append(0); 403 m_blocks[0]->isReachable = true; 404 while (!worklist.isEmpty()) { 405 BlockIndex index = worklist.last(); 406 worklist.removeLast(); 407 408 BasicBlock* block = m_blocks[index].get(); 409 ASSERT(block->isLinked); 410 411 Node* node = block->last(); 412 ASSERT(node->isTerminal()); 413 414 if (node->isJump()) 415 handleSuccessor(worklist, index, node->takenBlockIndex()); 416 else if (node->isBranch()) { 417 handleSuccessor(worklist, index, node->takenBlockIndex()); 418 handleSuccessor(worklist, index, node->notTakenBlockIndex()); 419 } 420 } 421} 422 423void Graph::resetReachability() 424{ 425 for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) { 426 BasicBlock* block = m_blocks[blockIndex].get(); 427 if (!block) 428 continue; 429 block->isReachable = false; 430 block->m_predecessors.clear(); 431 } 432 433 determineReachability(); 434} 435 436void Graph::resetExitStates() 437{ 438 for (BlockIndex blockIndex = 0; blockIndex < m_blocks.size(); ++blockIndex) { 439 BasicBlock* block = m_blocks[blockIndex].get(); 440 if (!block) 441 continue; 442 for (unsigned indexInBlock = block->size(); indexInBlock--;) 443 block->at(indexInBlock)->setCanExit(true); 444 } 445} 446 447} } // namespace JSC::DFG 448 449#endif 450