Rename dataLog() and dataLogV() to dataLogF() and dataLogFV()
[WebKit-https.git] / Source / JavaScriptCore / 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 Graph::Graph(JSGlobalData& globalData, CodeBlock* codeBlock, unsigned osrEntryBytecodeIndex, const Operands<JSValue>& mustHandleValues)
44     : m_globalData(globalData)
45     , m_codeBlock(codeBlock)
46     , m_profiledBlock(codeBlock->alternative())
47     , m_hasArguments(false)
48     , m_osrEntryBytecodeIndex(osrEntryBytecodeIndex)
49     , m_mustHandleValues(mustHandleValues)
50     , m_fixpointState(BeforeFixpoint)
51 {
52     ASSERT(m_profiledBlock);
53 }
54
55 const char *Graph::opName(NodeType op)
56 {
57     return dfgOpNames[op];
58 }
59
60 const char* Graph::nameOfVariableAccessData(VariableAccessData* variableAccessData)
61 {
62     // Variables are already numbered. For readability of IR dumps, this returns
63     // an alphabetic name for the variable access data, so that you don't have to
64     // reason about two numbers (variable number and live range number), but instead
65     // a number and a letter.
66     
67     unsigned index = std::numeric_limits<unsigned>::max();
68     for (unsigned i = 0; i < m_variableAccessData.size(); ++i) {
69         if (&m_variableAccessData[i] == variableAccessData) {
70             index = i;
71             break;
72         }
73     }
74     
75     ASSERT(index != std::numeric_limits<unsigned>::max());
76     
77     if (!index)
78         return "A";
79
80     static char buf[100];
81     BoundsCheckedPointer<char> ptr(buf, sizeof(buf));
82     
83     while (index) {
84         *ptr++ = 'A' + (index % 26);
85         index /= 26;
86     }
87     
88     if (variableAccessData->isCaptured())
89         *ptr++ = '*';
90     
91     ptr.strcat(speculationToAbbreviatedString(variableAccessData->prediction()));
92     
93     *ptr++ = 0;
94     
95     return buf;
96 }
97
98 static void printWhiteSpace(unsigned amount)
99 {
100     while (amount-- > 0)
101         dataLogF(" ");
102 }
103
104 void Graph::dumpCodeOrigin(const char* prefix, NodeIndex prevNodeIndex, NodeIndex nodeIndex)
105 {
106     if (prevNodeIndex == NoNode)
107         return;
108     
109     Node& currentNode = at(nodeIndex);
110     Node& previousNode = at(prevNodeIndex);
111     if (previousNode.codeOrigin.inlineCallFrame == currentNode.codeOrigin.inlineCallFrame)
112         return;
113     
114     Vector<CodeOrigin> previousInlineStack = previousNode.codeOrigin.inlineStack();
115     Vector<CodeOrigin> currentInlineStack = currentNode.codeOrigin.inlineStack();
116     unsigned commonSize = std::min(previousInlineStack.size(), currentInlineStack.size());
117     unsigned indexOfDivergence = commonSize;
118     for (unsigned i = 0; i < commonSize; ++i) {
119         if (previousInlineStack[i].inlineCallFrame != currentInlineStack[i].inlineCallFrame) {
120             indexOfDivergence = i;
121             break;
122         }
123     }
124     
125     // Print the pops.
126     for (unsigned i = previousInlineStack.size(); i-- > indexOfDivergence;) {
127         dataLogF("%s", prefix);
128         printWhiteSpace(i * 2);
129         dataLogF("<-- %p\n", previousInlineStack[i].inlineCallFrame->executable.get());
130     }
131     
132     // Print the pushes.
133     for (unsigned i = indexOfDivergence; i < currentInlineStack.size(); ++i) {
134         dataLogF("%s", prefix);
135         printWhiteSpace(i * 2);
136         dataLogF("--> %p\n", currentInlineStack[i].inlineCallFrame->executable.get());
137     }
138 }
139
140 int Graph::amountOfNodeWhiteSpace(Node& node)
141 {
142     return (node.codeOrigin.inlineDepth() - 1) * 2;
143 }
144
145 void Graph::printNodeWhiteSpace(Node& node)
146 {
147     printWhiteSpace(amountOfNodeWhiteSpace(node));
148 }
149
150 void Graph::dump(const char* prefix, NodeIndex nodeIndex)
151 {
152     Node& node = at(nodeIndex);
153     NodeType op = node.op();
154
155     unsigned refCount = node.refCount();
156     bool skipped = !refCount;
157     bool mustGenerate = node.mustGenerate();
158     if (mustGenerate)
159         --refCount;
160     
161     dataLogF("%s", prefix);
162     printNodeWhiteSpace(node);
163
164     // Example/explanation of dataflow dump output
165     //
166     //   14:   <!2:7>  GetByVal(@3, @13)
167     //   ^1     ^2 ^3     ^4       ^5
168     //
169     // (1) The nodeIndex of this operation.
170     // (2) The reference count. The number printed is the 'real' count,
171     //     not including the 'mustGenerate' ref. If the node is
172     //     'mustGenerate' then the count it prefixed with '!'.
173     // (3) The virtual register slot assigned to this node.
174     // (4) The name of the operation.
175     // (5) The arguments to the operation. The may be of the form:
176     //         @#   - a NodeIndex referencing a prior node in the graph.
177     //         arg# - an argument number.
178     //         $#   - the index in the CodeBlock of a constant { for numeric constants the value is displayed | for integers, in both decimal and hex }.
179     //         id#  - the index in the CodeBlock of an identifier { if codeBlock is passed to dump(), the string representation is displayed }.
180     //         var# - the index of a var on the global object, used by GetGlobalVar/PutGlobalVar operations.
181     dataLogF("% 4d:%s<%c%u:", (int)nodeIndex, skipped ? "  skipped  " : "           ", mustGenerate ? '!' : ' ', refCount);
182     if (node.hasResult() && !skipped && node.hasVirtualRegister())
183         dataLogF("%u", node.virtualRegister());
184     else
185         dataLogF("-");
186     dataLogF(">\t%s(", opName(op));
187     bool hasPrinted = false;
188     if (node.flags() & NodeHasVarArgs) {
189         for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++) {
190             if (hasPrinted)
191                 dataLogF(", ");
192             else
193                 hasPrinted = true;
194             if (!m_varArgChildren[childIdx])
195                 continue;
196             dataLogF("%s@%u%s",
197                     useKindToString(m_varArgChildren[childIdx].useKind()),
198                     m_varArgChildren[childIdx].index(),
199                     speculationToAbbreviatedString(
200                         at(m_varArgChildren[childIdx]).prediction()));
201         }
202     } else {
203         if (!!node.child1()) {
204             dataLogF("%s@%u%s",
205                     useKindToString(node.child1().useKind()),
206                     node.child1().index(),
207                     speculationToAbbreviatedString(at(node.child1()).prediction()));
208         }
209         if (!!node.child2()) {
210             dataLogF(", %s@%u%s",
211                     useKindToString(node.child2().useKind()),
212                     node.child2().index(),
213                     speculationToAbbreviatedString(at(node.child2()).prediction()));
214         }
215         if (!!node.child3()) {
216             dataLogF(", %s@%u%s",
217                     useKindToString(node.child3().useKind()),
218                     node.child3().index(),
219                     speculationToAbbreviatedString(at(node.child3()).prediction()));
220         }
221         hasPrinted = !!node.child1();
222     }
223
224     if (strlen(nodeFlagsAsString(node.flags()))) {
225         dataLogF("%s%s", hasPrinted ? ", " : "", nodeFlagsAsString(node.flags()));
226         hasPrinted = true;
227     }
228     if (node.hasArrayMode()) {
229         dataLogF("%s%s", hasPrinted ? ", " : "", node.arrayMode().toString());
230         hasPrinted = true;
231     }
232     if (node.hasVarNumber()) {
233         dataLogF("%svar%u", hasPrinted ? ", " : "", node.varNumber());
234         hasPrinted = true;
235     }
236     if (node.hasRegisterPointer()) {
237         dataLogF(
238             "%sglobal%u(%p)", hasPrinted ? ", " : "",
239             globalObjectFor(node.codeOrigin)->findRegisterIndex(node.registerPointer()),
240             node.registerPointer());
241         hasPrinted = true;
242     }
243     if (node.hasIdentifier()) {
244         dataLogF("%sid%u{%s}", hasPrinted ? ", " : "", node.identifierNumber(), m_codeBlock->identifier(node.identifierNumber()).string().utf8().data());
245         hasPrinted = true;
246     }
247     if (node.hasStructureSet()) {
248         for (size_t i = 0; i < node.structureSet().size(); ++i) {
249             dataLogF("%sstruct(%p: %s)", hasPrinted ? ", " : "", node.structureSet()[i], indexingTypeToString(node.structureSet()[i]->indexingType()));
250             hasPrinted = true;
251         }
252     }
253     if (node.hasStructure()) {
254         dataLogF("%sstruct(%p: %s)", hasPrinted ? ", " : "", node.structure(), indexingTypeToString(node.structure()->indexingType()));
255         hasPrinted = true;
256     }
257     if (node.hasStructureTransitionData()) {
258         dataLogF("%sstruct(%p -> %p)", hasPrinted ? ", " : "", node.structureTransitionData().previousStructure, node.structureTransitionData().newStructure);
259         hasPrinted = true;
260     }
261     if (node.hasFunction()) {
262         dataLogF("%s%p", hasPrinted ? ", " : "", node.function());
263         hasPrinted = true;
264     }
265     if (node.hasStorageAccessData()) {
266         StorageAccessData& storageAccessData = m_storageAccessData[node.storageAccessDataIndex()];
267         dataLogF("%sid%u{%s}", hasPrinted ? ", " : "", storageAccessData.identifierNumber, m_codeBlock->identifier(storageAccessData.identifierNumber).string().utf8().data());
268         
269         dataLogF(", %lu", static_cast<unsigned long>(storageAccessData.offset));
270         hasPrinted = true;
271     }
272     ASSERT(node.hasVariableAccessData() == node.hasLocal());
273     if (node.hasVariableAccessData()) {
274         VariableAccessData* variableAccessData = node.variableAccessData();
275         int operand = variableAccessData->operand();
276         if (operandIsArgument(operand))
277             dataLogF("%sarg%u(%s)", hasPrinted ? ", " : "", operandToArgument(operand), nameOfVariableAccessData(variableAccessData));
278         else
279             dataLogF("%sr%u(%s)", hasPrinted ? ", " : "", operand, nameOfVariableAccessData(variableAccessData));
280         hasPrinted = true;
281     }
282     if (node.hasConstantBuffer()) {
283         if (hasPrinted)
284             dataLogF(", ");
285         dataLogF("%u:[", node.startConstant());
286         for (unsigned i = 0; i < node.numConstants(); ++i) {
287             if (i)
288                 dataLogF(", ");
289             dataLogF("%s", m_codeBlock->constantBuffer(node.startConstant())[i].description());
290         }
291         dataLogF("]");
292         hasPrinted = true;
293     }
294     if (node.hasIndexingType()) {
295         if (hasPrinted)
296             dataLogF(", ");
297         dataLogF("%s", indexingTypeToString(node.indexingType()));
298     }
299     if (op == JSConstant) {
300         dataLogF("%s$%u", hasPrinted ? ", " : "", node.constantNumber());
301         JSValue value = valueOfJSConstant(nodeIndex);
302         dataLogF(" = %s", value.description());
303         hasPrinted = true;
304     }
305     if (op == WeakJSConstant) {
306         dataLogF("%s%p", hasPrinted ? ", " : "", node.weakConstant());
307         hasPrinted = true;
308     }
309     if  (node.isBranch() || node.isJump()) {
310         dataLogF("%sT:#%u", hasPrinted ? ", " : "", node.takenBlockIndex());
311         hasPrinted = true;
312     }
313     if  (node.isBranch()) {
314         dataLogF("%sF:#%u", hasPrinted ? ", " : "", node.notTakenBlockIndex());
315         hasPrinted = true;
316     }
317     dataLogF("%sbc#%u", hasPrinted ? ", " : "", node.codeOrigin.bytecodeIndex);
318     hasPrinted = true;
319     (void)hasPrinted;
320     
321     dataLogF(")");
322
323     if (!skipped) {
324         if (node.hasVariableAccessData())
325             dataLogF("  predicting %s%s", speculationToString(node.variableAccessData()->prediction()), node.variableAccessData()->shouldUseDoubleFormat() ? ", forcing double" : "");
326         else if (node.hasHeapPrediction())
327             dataLogF("  predicting %s", speculationToString(node.getHeapPrediction()));
328     }
329     
330     dataLogF("\n");
331 }
332
333 void Graph::dumpBlockHeader(const char* prefix, BlockIndex blockIndex, PhiNodeDumpMode phiNodeDumpMode)
334 {
335     BasicBlock* block = m_blocks[blockIndex].get();
336
337     dataLogF("%sBlock #%u (bc#%u): %s%s\n", prefix, (int)blockIndex, block->bytecodeBegin, block->isReachable ? "" : " (skipped)", block->isOSRTarget ? " (OSR target)" : "");
338     dataLogF("%s  Predecessors:", prefix);
339     for (size_t i = 0; i < block->m_predecessors.size(); ++i)
340         dataLogF(" #%u", block->m_predecessors[i]);
341     dataLogF("\n");
342     if (m_dominators.isValid()) {
343         dataLogF("%s  Dominated by:", prefix);
344         for (size_t i = 0; i < m_blocks.size(); ++i) {
345             if (!m_dominators.dominates(i, blockIndex))
346                 continue;
347             dataLogF(" #%lu", static_cast<unsigned long>(i));
348         }
349         dataLogF("\n");
350         dataLogF("%s  Dominates:", prefix);
351         for (size_t i = 0; i < m_blocks.size(); ++i) {
352             if (!m_dominators.dominates(blockIndex, i))
353                 continue;
354             dataLogF(" #%lu", static_cast<unsigned long>(i));
355         }
356         dataLogF("\n");
357     }
358     dataLogF("%s  Phi Nodes:", prefix);
359     for (size_t i = 0; i < block->phis.size(); ++i) {
360         NodeIndex phiNodeIndex = block->phis[i];
361         Node& phiNode = at(phiNodeIndex);
362         if (!phiNode.shouldGenerate() && phiNodeDumpMode == DumpLivePhisOnly)
363             continue;
364         dataLogF(" @%u->(", phiNodeIndex);
365         if (phiNode.child1()) {
366             dataLogF("@%u", phiNode.child1().index());
367             if (phiNode.child2()) {
368                 dataLogF(", @%u", phiNode.child2().index());
369                 if (phiNode.child3())
370                     dataLogF(", @%u", phiNode.child3().index());
371             }
372         }
373         dataLogF(")%s", i + 1 < block->phis.size() ? "," : "");
374     }
375     dataLogF("\n");
376 }
377
378 void Graph::dump()
379 {
380     NodeIndex lastNodeIndex = NoNode;
381     for (size_t b = 0; b < m_blocks.size(); ++b) {
382         BasicBlock* block = m_blocks[b].get();
383         if (!block)
384             continue;
385         dumpBlockHeader("", b, DumpAllPhis);
386         dataLogF("  vars before: ");
387         if (block->cfaHasVisited)
388             dumpOperands(block->valuesAtHead, WTF::dataFile());
389         else
390             dataLogF("<empty>");
391         dataLogF("\n");
392         dataLogF("  var links: ");
393         dumpOperands(block->variablesAtHead, WTF::dataFile());
394         dataLogF("\n");
395         for (size_t i = 0; i < block->size(); ++i) {
396             dumpCodeOrigin("", lastNodeIndex, block->at(i));
397             dump("", block->at(i));
398             lastNodeIndex = block->at(i);
399         }
400         dataLogF("  vars after: ");
401         if (block->cfaHasVisited)
402             dumpOperands(block->valuesAtTail, WTF::dataFile());
403         else
404             dataLogF("<empty>");
405         dataLogF("\n");
406         dataLogF("  var links: ");
407         dumpOperands(block->variablesAtTail, WTF::dataFile());
408         dataLogF("\n");
409     }
410 }
411
412 // FIXME: Convert this to be iterative, not recursive.
413 #define DO_TO_CHILDREN(node, thingToDo) do {                            \
414         Node& _node = (node);                                           \
415         if (_node.flags() & NodeHasVarArgs) {                           \
416             for (unsigned _childIdx = _node.firstChild();               \
417                  _childIdx < _node.firstChild() + _node.numChildren();  \
418                  _childIdx++) {                                         \
419                 if (!!m_varArgChildren[_childIdx])                      \
420                     thingToDo(m_varArgChildren[_childIdx]);             \
421             }                                                           \
422         } else {                                                        \
423             if (!_node.child1()) {                                      \
424                 ASSERT(!_node.child2()                                  \
425                        && !_node.child3());                             \
426                 break;                                                  \
427             }                                                           \
428             thingToDo(_node.child1());                                  \
429                                                                         \
430             if (!_node.child2()) {                                      \
431                 ASSERT(!_node.child3());                                \
432                 break;                                                  \
433             }                                                           \
434             thingToDo(_node.child2());                                  \
435                                                                         \
436             if (!_node.child3())                                        \
437                 break;                                                  \
438             thingToDo(_node.child3());                                  \
439         }                                                               \
440     } while (false)
441
442 void Graph::refChildren(NodeIndex op)
443 {
444     DO_TO_CHILDREN(at(op), ref);
445 }
446
447 void Graph::derefChildren(NodeIndex op)
448 {
449     DO_TO_CHILDREN(at(op), deref);
450 }
451
452 void Graph::predictArgumentTypes()
453 {
454     ASSERT(m_codeBlock->numParameters() >= 1);
455     for (size_t arg = 0; arg < static_cast<size_t>(m_codeBlock->numParameters()); ++arg) {
456         ValueProfile* profile = m_profiledBlock->valueProfileForArgument(arg);
457         if (!profile)
458             continue;
459         
460         at(m_arguments[arg]).variableAccessData()->predict(profile->computeUpdatedPrediction());
461         
462 #if DFG_ENABLE(DEBUG_VERBOSE)
463         dataLogF("Argument [%zu] prediction: %s\n", arg, speculationToString(at(m_arguments[arg]).variableAccessData()->prediction()));
464 #endif
465     }
466 }
467
468 void Graph::handleSuccessor(Vector<BlockIndex, 16>& worklist, BlockIndex blockIndex, BlockIndex successorIndex)
469 {
470     BasicBlock* successor = m_blocks[successorIndex].get();
471     if (!successor->isReachable) {
472         successor->isReachable = true;
473         worklist.append(successorIndex);
474     }
475     
476     successor->m_predecessors.append(blockIndex);
477 }
478
479 void Graph::collectGarbage()
480 {
481     // First reset the counts to 0 for all nodes.
482     for (unsigned i = size(); i--;)
483         at(i).setRefCount(0);
484     
485     // Now find the roots: the nodes that are must-generate. Set their ref counts to
486     // 1 and put them on the worklist.
487     Vector<NodeIndex, 128> worklist;
488     for (BlockIndex blockIndex = 0; blockIndex < m_blocks.size(); ++blockIndex) {
489         BasicBlock* block = m_blocks[blockIndex].get();
490         if (!block)
491             continue;
492         for (unsigned indexInBlock = block->size(); indexInBlock--;) {
493             NodeIndex nodeIndex = block->at(indexInBlock);
494             Node& node = at(nodeIndex);
495             if (!(node.flags() & NodeMustGenerate))
496                 continue;
497             node.setRefCount(1);
498             worklist.append(nodeIndex);
499         }
500     }
501     
502     while (!worklist.isEmpty()) {
503         NodeIndex nodeIndex = worklist.last();
504         worklist.removeLast();
505         Node& node = at(nodeIndex);
506         ASSERT(node.shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
507         if (node.flags() & NodeHasVarArgs) {
508             for (unsigned childIdx = node.firstChild();
509                  childIdx < node.firstChild() + node.numChildren();
510                  ++childIdx) {
511                 if (!m_varArgChildren[childIdx])
512                     continue;
513                 NodeIndex childNodeIndex = m_varArgChildren[childIdx].index();
514                 if (!at(childNodeIndex).ref())
515                     continue;
516                 worklist.append(childNodeIndex);
517             }
518         } else if (node.child1()) {
519             if (at(node.child1()).ref())
520                 worklist.append(node.child1().index());
521             if (node.child2()) {
522                 if (at(node.child2()).ref())
523                     worklist.append(node.child2().index());
524                 if (node.child3()) {
525                     if (at(node.child3()).ref())
526                         worklist.append(node.child3().index());
527                 }
528             }
529         }
530     }
531 }
532
533 void Graph::determineReachability()
534 {
535     Vector<BlockIndex, 16> worklist;
536     worklist.append(0);
537     m_blocks[0]->isReachable = true;
538     while (!worklist.isEmpty()) {
539         BlockIndex index = worklist.last();
540         worklist.removeLast();
541         
542         BasicBlock* block = m_blocks[index].get();
543         ASSERT(block->isLinked);
544         
545         Node& node = at(block->last());
546         ASSERT(node.isTerminal());
547         
548         if (node.isJump())
549             handleSuccessor(worklist, index, node.takenBlockIndex());
550         else if (node.isBranch()) {
551             handleSuccessor(worklist, index, node.takenBlockIndex());
552             handleSuccessor(worklist, index, node.notTakenBlockIndex());
553         }
554     }
555 }
556
557 void Graph::resetReachability()
558 {
559     for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) {
560         BasicBlock* block = m_blocks[blockIndex].get();
561         if (!block)
562             continue;
563         block->isReachable = false;
564         block->m_predecessors.clear();
565     }
566     
567     determineReachability();
568 }
569
570 void Graph::resetExitStates()
571 {
572     for (unsigned i = size(); i--;)
573         at(i).setCanExit(true);
574 }
575
576 } } // namespace JSC::DFG
577
578 #endif