dfg/DFGGraph.cpp

   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
  38 namespace JSC { namespace DFG {
  39
  40 // Creates an array of stringized names.
  41 static 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
  47 Graph::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
  64 Graph::~Graph()
  65 {
  66     m_allocator.freeAll();
  67 }
  68
  69 const char *Graph::opName(NodeType op)
  70 {
  71     return dfgOpNames[op];
  72 }
  73
  74 static void printWhiteSpace(PrintStream& out, unsigned amount)
  75 {
  76     while (amount-- > 0)
  77         out.print(" ");
  78 }
  79
  80 bool 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
 120 int Graph::amountOfNodeWhiteSpace(Node* node)
 121 {
 122     return (node->codeOrigin.inlineDepth() - 1) * 2;
 123 }
 124
 125 void Graph::printNodeWhiteSpace(PrintStream& out, Node* node)
 126 {
 127     printWhiteSpace(out, amountOfNodeWhiteSpace(node));
 128 }
 129
 130 void 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
 277 void 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
 321 void 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
 365 void 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
 388 void 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
 399 void 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
 423 void 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
 436 void 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