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 <wtf/BoundsCheckedPointer.h>
  31
  32 #if ENABLE(DFG_JIT)
  33
  34 namespace JSC { namespace DFG {
  35
  36 // Creates an array of stringized names.
  37 static const char* dfgOpNames[] = {
  38 #define STRINGIZE_DFG_OP_ENUM(opcode, flags) #opcode ,
  39     FOR_EACH_DFG_OP(STRINGIZE_DFG_OP_ENUM)
  40 #undef STRINGIZE_DFG_OP_ENUM
  41 };
  42
  43 const char *Graph::opName(NodeType op)
  44 {
  45     return dfgOpNames[op];
  46 }
  47
  48 const char* Graph::nameOfVariableAccessData(VariableAccessData* variableAccessData)
  49 {
  50     // Variables are already numbered. For readability of IR dumps, this returns
  51     // an alphabetic name for the variable access data, so that you don't have to
  52     // reason about two numbers (variable number and live range number), but instead
  53     // a number and a letter.
  54
  55     unsigned index = std::numeric_limits<unsigned>::max();
  56     for (unsigned i = 0; i < m_variableAccessData.size(); ++i) {
  57         if (&m_variableAccessData[i] == variableAccessData) {
  58             index = i;
  59             break;
  60         }
  61     }
  62
  63     ASSERT(index != std::numeric_limits<unsigned>::max());
  64
  65     if (!index)
  66         return "A";
  67
  68     static char buf[10];
  69     BoundsCheckedPointer<char> ptr(buf, sizeof(buf));
  70
  71     while (index) {
  72         *ptr++ = 'A' + (index % 26);
  73         index /= 26;
  74     }
  75
  76     *ptr++ = 0;
  77
  78     return buf;
  79 }
  80
  81 static void printWhiteSpace(unsigned amount)
  82 {
  83     while (amount-- > 0)
  84         dataLog(" ");
  85 }
  86
  87 void Graph::dumpCodeOrigin(NodeIndex prevNodeIndex, NodeIndex nodeIndex)
  88 {
  89     if (prevNodeIndex == NoNode)
  90         return;
  91
  92     Node& currentNode = at(nodeIndex);
  93     Node& previousNode = at(prevNodeIndex);
  94     if (previousNode.codeOrigin.inlineCallFrame == currentNode.codeOrigin.inlineCallFrame)
  95         return;
  96
  97     Vector<CodeOrigin> previousInlineStack = previousNode.codeOrigin.inlineStack();
  98     Vector<CodeOrigin> currentInlineStack = currentNode.codeOrigin.inlineStack();
  99     unsigned commonSize = std::min(previousInlineStack.size(), currentInlineStack.size());
 100     unsigned indexOfDivergence = commonSize;
 101     for (unsigned i = 0; i < commonSize; ++i) {
 102         if (previousInlineStack[i].inlineCallFrame != currentInlineStack[i].inlineCallFrame) {
 103             indexOfDivergence = i;
 104             break;
 105         }
 106     }
 107
 108     // Print the pops.
 109     for (unsigned i = previousInlineStack.size(); i-- > indexOfDivergence;) {
 110         printWhiteSpace(i * 2);
 111         dataLog("<-- %p\n", previousInlineStack[i].inlineCallFrame->executable.get());
 112     }
 113
 114     // Print the pushes.
 115     for (unsigned i = indexOfDivergence; i < currentInlineStack.size(); ++i) {
 116         printWhiteSpace(i * 2);
 117         dataLog("--> %p\n", currentInlineStack[i].inlineCallFrame->executable.get());
 118     }
 119 }
 120
 121 void Graph::dump(NodeIndex nodeIndex)
 122 {
 123     Node& node = at(nodeIndex);
 124     NodeType op = node.op();
 125
 126     unsigned refCount = node.refCount();
 127     bool skipped = !refCount;
 128     bool mustGenerate = node.mustGenerate();
 129     if (mustGenerate) {
 130         ASSERT(refCount);
 131         --refCount;
 132     }
 133
 134     printWhiteSpace((node.codeOrigin.inlineDepth() - 1) * 2);
 135
 136     // Example/explanation of dataflow dump output
 137     //
 138     //   14:   <!2:7>  GetByVal(@3, @13)
 139     //   ^1     ^2 ^3     ^4       ^5
 140     //
 141     // (1) The nodeIndex of this operation.
 142     // (2) The reference count. The number printed is the 'real' count,
 143     //     not including the 'mustGenerate' ref. If the node is
 144     //     'mustGenerate' then the count it prefixed with '!'.
 145     // (3) The virtual register slot assigned to this node.
 146     // (4) The name of the operation.
 147     // (5) The arguments to the operation. The may be of the form:
 148     //         @#   - a NodeIndex referencing a prior node in the graph.
 149     //         arg# - an argument number.
 150     //         $#   - the index in the CodeBlock of a constant { for numeric constants the value is displayed | for integers, in both decimal and hex }.
 151     //         id#  - the index in the CodeBlock of an identifier { if codeBlock is passed to dump(), the string representation is displayed }.
 152     //         var# - the index of a var on the global object, used by GetGlobalVar/PutGlobalVar operations.
 153     dataLog("% 4d:%s<%c%u:", (int)nodeIndex, skipped ? "  skipped  " : "           ", mustGenerate ? '!' : ' ', refCount);
 154     if (node.hasResult() && !skipped && node.hasVirtualRegister())
 155         dataLog("%u", node.virtualRegister());
 156     else
 157         dataLog("-");
 158     dataLog(">\t%s(", opName(op));
 159     bool hasPrinted = false;
 160     if (node.flags() & NodeHasVarArgs) {
 161         for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++) {
 162             if (hasPrinted)
 163                 dataLog(", ");
 164             else
 165                 hasPrinted = true;
 166             dataLog("%s@%u%s",
 167                     useKindToString(m_varArgChildren[childIdx].useKind()),
 168                     m_varArgChildren[childIdx].index(),
 169                     predictionToAbbreviatedString(at(childIdx).prediction()));
 170         }
 171     } else {
 172         if (!!node.child1()) {
 173             dataLog("%s@%u%s",
 174                     useKindToString(node.child1().useKind()),
 175                     node.child1().index(),
 176                     predictionToAbbreviatedString(at(node.child1()).prediction()));
 177         }
 178         if (!!node.child2()) {
 179             dataLog(", %s@%u%s",
 180                     useKindToString(node.child2().useKind()),
 181                     node.child2().index(),
 182                     predictionToAbbreviatedString(at(node.child2()).prediction()));
 183         }
 184         if (!!node.child3()) {
 185             dataLog(", %s@%u%s",
 186                     useKindToString(node.child3().useKind()),
 187                     node.child3().index(),
 188                     predictionToAbbreviatedString(at(node.child3()).prediction()));
 189         }
 190         hasPrinted = !!node.child1();
 191     }
 192
 193     if (node.flags()) {
 194         dataLog("%s%s", hasPrinted ? ", " : "", nodeFlagsAsString(node.flags()));
 195         hasPrinted = true;
 196     }
 197     if (node.hasVarNumber()) {
 198         dataLog("%svar%u", hasPrinted ? ", " : "", node.varNumber());
 199         hasPrinted = true;
 200     }
 201     if (node.hasIdentifier()) {
 202         dataLog("%sid%u{%s}", hasPrinted ? ", " : "", node.identifierNumber(), m_codeBlock->identifier(node.identifierNumber()).ustring().utf8().data());
 203         hasPrinted = true;
 204     }
 205     if (node.hasStructureSet()) {
 206         for (size_t i = 0; i < node.structureSet().size(); ++i) {
 207             dataLog("%sstruct(%p)", hasPrinted ? ", " : "", node.structureSet()[i]);
 208             hasPrinted = true;
 209         }
 210     }
 211     if (node.hasStructureTransitionData()) {
 212         dataLog("%sstruct(%p -> %p)", hasPrinted ? ", " : "", node.structureTransitionData().previousStructure, node.structureTransitionData().newStructure);
 213         hasPrinted = true;
 214     }
 215     if (node.hasStorageAccessData()) {
 216         StorageAccessData& storageAccessData = m_storageAccessData[node.storageAccessDataIndex()];
 217         dataLog("%sid%u{%s}", hasPrinted ? ", " : "", storageAccessData.identifierNumber, m_codeBlock->identifier(storageAccessData.identifierNumber).ustring().utf8().data());
 218
 219         dataLog(", %lu", static_cast<unsigned long>(storageAccessData.offset));
 220         hasPrinted = true;
 221     }
 222     ASSERT(node.hasVariableAccessData() == node.hasLocal());
 223     if (node.hasVariableAccessData()) {
 224         VariableAccessData* variableAccessData = node.variableAccessData();
 225         int operand = variableAccessData->operand();
 226         if (operandIsArgument(operand))
 227             dataLog("%sarg%u(%s)", hasPrinted ? ", " : "", operandToArgument(operand), nameOfVariableAccessData(variableAccessData));
 228         else
 229             dataLog("%sr%u(%s)", hasPrinted ? ", " : "", operand, nameOfVariableAccessData(variableAccessData));
 230         hasPrinted = true;
 231     }
 232     if (node.hasConstantBuffer()) {
 233         if (hasPrinted)
 234             dataLog(", ");
 235         dataLog("%u:[", node.startConstant());
 236         for (unsigned i = 0; i < node.numConstants(); ++i) {
 237             if (i)
 238                 dataLog(", ");
 239             dataLog("%s", m_codeBlock->constantBuffer(node.startConstant())[i].description());
 240         }
 241         dataLog("]");
 242         hasPrinted = true;
 243     }
 244     if (op == JSConstant) {
 245         dataLog("%s$%u", hasPrinted ? ", " : "", node.constantNumber());
 246         JSValue value = valueOfJSConstant(nodeIndex);
 247         dataLog(" = %s", value.description());
 248         hasPrinted = true;
 249     }
 250     if (op == WeakJSConstant) {
 251         dataLog("%s%p", hasPrinted ? ", " : "", node.weakConstant());
 252         hasPrinted = true;
 253     }
 254     if  (node.isBranch() || node.isJump()) {
 255         dataLog("%sT:#%u", hasPrinted ? ", " : "", node.takenBlockIndex());
 256         hasPrinted = true;
 257     }
 258     if  (node.isBranch()) {
 259         dataLog("%sF:#%u", hasPrinted ? ", " : "", node.notTakenBlockIndex());
 260         hasPrinted = true;
 261     }
 262     (void)hasPrinted;
 263
 264     dataLog(")");
 265
 266     if (!skipped) {
 267         if (node.hasVariableAccessData())
 268             dataLog("  predicting %s, double ratio %lf%s", predictionToString(node.variableAccessData()->prediction()), node.variableAccessData()->doubleVoteRatio(), node.variableAccessData()->shouldUseDoubleFormat() ? ", forcing double" : "");
 269         else if (node.hasHeapPrediction())
 270             dataLog("  predicting %s", predictionToString(node.getHeapPrediction()));
 271     }
 272
 273     dataLog("\n");
 274 }
 275
 276 void Graph::dump()
 277 {
 278     NodeIndex lastNodeIndex = NoNode;
 279     for (size_t b = 0; b < m_blocks.size(); ++b) {
 280         BasicBlock* block = m_blocks[b].get();
 281         dataLog("Block #%u (bc#%u): %s%s\n", (int)b, block->bytecodeBegin, block->isReachable ? "" : " (skipped)", block->isOSRTarget ? " (OSR target)" : "");
 282         dataLog("  Phi Nodes:\n");
 283         for (size_t i = 0; i < block->phis.size(); ++i) {
 284             // Dumping the dead Phi nodes is just annoying!
 285             if (at(block->phis[i]).refCount())
 286                 dump(block->phis[i]);
 287         }
 288         dataLog("  vars before: ");
 289         if (block->cfaHasVisited)
 290             dumpOperands(block->valuesAtHead, WTF::dataFile());
 291         else
 292             dataLog("<empty>");
 293         dataLog("\n");
 294         dataLog("  var links: ");
 295         dumpOperands(block->variablesAtHead, WTF::dataFile());
 296         dataLog("\n");
 297         for (size_t i = 0; i < block->size(); ++i) {
 298             dumpCodeOrigin(lastNodeIndex, block->at(i));
 299             dump(block->at(i));
 300             lastNodeIndex = block->at(i);
 301         }
 302         dataLog("  vars after: ");
 303         if (block->cfaHasVisited)
 304             dumpOperands(block->valuesAtTail, WTF::dataFile());
 305         else
 306             dataLog("<empty>");
 307         dataLog("\n");
 308     }
 309 }
 310
 311 // FIXME: Convert this to be iterative, not recursive.
 312 #define DO_TO_CHILDREN(node, thingToDo) do {                            \
 313         Node& _node = (node);                                           \
 314         if (_node.flags() & NodeHasVarArgs) {                           \
 315             for (unsigned _childIdx = _node.firstChild();               \
 316                  _childIdx < _node.firstChild() + _node.numChildren();  \
 317                  _childIdx++)                                           \
 318                 thingToDo(m_varArgChildren[_childIdx]);                 \
 319         } else {                                                        \
 320             if (!_node.child1()) {                                      \
 321                 ASSERT(!_node.child2()                                  \
 322                        && !_node.child3());                             \
 323                 break;                                                  \
 324             }                                                           \
 325             thingToDo(_node.child1());                                  \
 326                                                                         \
 327             if (!_node.child2()) {                                      \
 328                 ASSERT(!_node.child3());                                \
 329                 break;                                                  \
 330             }                                                           \
 331             thingToDo(_node.child2());                                  \
 332                                                                         \
 333             if (!_node.child3())                                        \
 334                 break;                                                  \
 335             thingToDo(_node.child3());                                  \
 336         }                                                               \
 337     } while (false)
 338
 339 void Graph::refChildren(NodeIndex op)
 340 {
 341     DO_TO_CHILDREN(at(op), ref);
 342 }
 343
 344 void Graph::derefChildren(NodeIndex op)
 345 {
 346     DO_TO_CHILDREN(at(op), deref);
 347 }
 348
 349 void Graph::predictArgumentTypes()
 350 {
 351     ASSERT(m_codeBlock->numParameters() >= 1);
 352     for (size_t arg = 0; arg < static_cast<size_t>(m_codeBlock->numParameters()); ++arg) {
 353         ValueProfile* profile = m_profiledBlock->valueProfileForArgument(arg);
 354         if (!profile)
 355             continue;
 356
 357         at(m_arguments[arg]).variableAccessData()->predict(profile->computeUpdatedPrediction());
 358
 359 #if DFG_ENABLE(DEBUG_VERBOSE)
 360         dataLog("Argument [%zu] prediction: %s\n", arg, predictionToString(at(m_arguments[arg]).variableAccessData()->prediction()));
 361 #endif
 362     }
 363 }
 364
 365 } } // namespace JSC::DFG
 366
 367 #endif