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