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