/*
 * Copyright (C) 2011 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "config.h"
#include "DFGGraph.h"

#include "CodeBlock.h"
#include "DFGVariableAccessDataDump.h"

#if ENABLE(DFG_JIT)

namespace JSC { namespace DFG {

// Creates an array of stringized names.
static const char* dfgOpNames[] = {
#define STRINGIZE_DFG_OP_ENUM(opcode, flags) #opcode ,
    FOR_EACH_DFG_OP(STRINGIZE_DFG_OP_ENUM)
#undef STRINGIZE_DFG_OP_ENUM
};

Graph::Graph(JSGlobalData& globalData, CodeBlock* codeBlock, unsigned osrEntryBytecodeIndex, const Operands<JSValue>& mustHandleValues)
    : m_globalData(globalData)
    , m_codeBlock(codeBlock)
    , m_profiledBlock(codeBlock->alternative())
    , m_hasArguments(false)
    , m_osrEntryBytecodeIndex(osrEntryBytecodeIndex)
    , m_mustHandleValues(mustHandleValues)
    , m_fixpointState(BeforeFixpoint)
{
    ASSERT(m_profiledBlock);
}

const char *Graph::opName(NodeType op)
{
    return dfgOpNames[op];
}

static void printWhiteSpace(PrintStream& out, unsigned amount)
{
    while (amount-- > 0)
        out.print(" ");
}

void Graph::dumpCodeOrigin(PrintStream& out, const char* prefix, NodeIndex prevNodeIndex, NodeIndex nodeIndex)
{
    if (prevNodeIndex == NoNode)
        return;
    
    Node& currentNode = at(nodeIndex);
    Node& previousNode = at(prevNodeIndex);
    if (previousNode.codeOrigin.inlineCallFrame == currentNode.codeOrigin.inlineCallFrame)
        return;
    
    Vector<CodeOrigin> previousInlineStack = previousNode.codeOrigin.inlineStack();
    Vector<CodeOrigin> currentInlineStack = currentNode.codeOrigin.inlineStack();
    unsigned commonSize = std::min(previousInlineStack.size(), currentInlineStack.size());
    unsigned indexOfDivergence = commonSize;
    for (unsigned i = 0; i < commonSize; ++i) {
        if (previousInlineStack[i].inlineCallFrame != currentInlineStack[i].inlineCallFrame) {
            indexOfDivergence = i;
            break;
        }
    }
    
    // Print the pops.
    for (unsigned i = previousInlineStack.size(); i-- > indexOfDivergence;) {
        out.print(prefix);
        printWhiteSpace(out, i * 2);
        out.print("<-- #", previousInlineStack[i].inlineCallFrame->hash(), "\n");
    }
    
    // Print the pushes.
    for (unsigned i = indexOfDivergence; i < currentInlineStack.size(); ++i) {
        out.print(prefix);
        printWhiteSpace(out, i * 2);
        out.print("--> #", currentInlineStack[i].inlineCallFrame->hash(), "\n");
    }
}

int Graph::amountOfNodeWhiteSpace(Node& node)
{
    return (node.codeOrigin.inlineDepth() - 1) * 2;
}

void Graph::printNodeWhiteSpace(PrintStream& out, Node& node)
{
    printWhiteSpace(out, amountOfNodeWhiteSpace(node));
}

void Graph::dump(PrintStream& out, Edge edge)
{
    out.print(
        useKindToString(edge.useKind()),
        "@", edge.index(),
        AbbreviatedSpeculationDump(at(edge).prediction()));
}

void Graph::dump(PrintStream& out, const char* prefix, NodeIndex nodeIndex)
{
    Node& node = at(nodeIndex);
    NodeType op = node.op();

    unsigned refCount = node.refCount();
    bool skipped = !refCount;
    bool mustGenerate = node.mustGenerate();
    if (mustGenerate)
        --refCount;

    out.print(prefix);
    printNodeWhiteSpace(out, node);

    // Example/explanation of dataflow dump output
    //
    //   14:   <!2:7>  GetByVal(@3, @13)
    //   ^1     ^2 ^3     ^4       ^5
    //
    // (1) The nodeIndex of this operation.
    // (2) The reference count. The number printed is the 'real' count,
    //     not including the 'mustGenerate' ref. If the node is
    //     'mustGenerate' then the count it prefixed with '!'.
    // (3) The virtual register slot assigned to this node.
    // (4) The name of the operation.
    // (5) The arguments to the operation. The may be of the form:
    //         @#   - a NodeIndex referencing a prior node in the graph.
    //         arg# - an argument number.
    //         $#   - the index in the CodeBlock of a constant { for numeric constants the value is displayed | for integers, in both decimal and hex }.
    //         id#  - the index in the CodeBlock of an identifier { if codeBlock is passed to dump(), the string representation is displayed }.
    //         var# - the index of a var on the global object, used by GetGlobalVar/PutGlobalVar operations.
    out.printf("% 4d:%s<%c%u:", (int)nodeIndex, skipped ? "  skipped  " : "           ", mustGenerate ? '!' : ' ', refCount);
    if (node.hasResult() && !skipped && node.hasVirtualRegister())
        out.print(node.virtualRegister());
    else
        out.print("-");
    out.print(">\t", opName(op), "(");
    bool hasPrinted = false;
    if (node.flags() & NodeHasVarArgs) {
        for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++) {
            if (hasPrinted)
                out.print(", ");
            else
                hasPrinted = true;
            if (!m_varArgChildren[childIdx])
                continue;
            dump(out, m_varArgChildren[childIdx]);
        }
    } else {
        if (!!node.child1()) {
            dump(out, node.child1());
            hasPrinted = true;
        }
        if (!!node.child2()) {
            out.print(", "); // Whether or not there is a first child, we print a comma to ensure that we see a blank entry if there wasn't one.
            dump(out, node.child2());
            hasPrinted = true;
        }
        if (!!node.child3()) {
            if (!node.child1() && !node.child2())
                out.print(", "); // If the third child is the first non-empty one then make sure we have two blanks preceding it.
            out.print(", ");
            dump(out, node.child3());
            hasPrinted = true;
        }
    }

    if (strlen(nodeFlagsAsString(node.flags()))) {
        out.print(hasPrinted ? ", " : "", nodeFlagsAsString(node.flags()));
        hasPrinted = true;
    }
    if (node.hasArrayMode()) {
        out.print(hasPrinted ? ", " : "", node.arrayMode().toString());
        hasPrinted = true;
    }
    if (node.hasVarNumber()) {
        out.print(hasPrinted ? ", " : "", "var", node.varNumber());
        hasPrinted = true;
    }
    if (node.hasRegisterPointer()) {
        out.print(hasPrinted ? ", " : "", "global", globalObjectFor(node.codeOrigin)->findRegisterIndex(node.registerPointer()), "(", RawPointer(node.registerPointer()), ")");
        hasPrinted = true;
    }
    if (node.hasIdentifier()) {
        out.print(hasPrinted ? ", " : "", "id", node.identifierNumber(), "{", m_codeBlock->identifier(node.identifierNumber()).string(), "}");
        hasPrinted = true;
    }
    if (node.hasStructureSet()) {
        for (size_t i = 0; i < node.structureSet().size(); ++i) {
            out.print(hasPrinted ? ", " : "", "struct(", RawPointer(node.structureSet()[i]), ": ", indexingTypeToString(node.structureSet()[i]->indexingType()), ")");
            hasPrinted = true;
        }
    }
    if (node.hasStructure()) {
        out.print(hasPrinted ? ", " : "", "struct(", RawPointer(node.structure()), ": ", indexingTypeToString(node.structure()->indexingType()), ")");
        hasPrinted = true;
    }
    if (node.hasStructureTransitionData()) {
        out.print(hasPrinted ? ", " : "", "struct(", RawPointer(node.structureTransitionData().previousStructure), " -> ", RawPointer(node.structureTransitionData().newStructure), ")");
        hasPrinted = true;
    }
    if (node.hasFunction()) {
        out.print(hasPrinted ? ", " : "", RawPointer(node.function()));
        hasPrinted = true;
    }
    if (node.hasStorageAccessData()) {
        StorageAccessData& storageAccessData = m_storageAccessData[node.storageAccessDataIndex()];
        out.print(hasPrinted ? ", " : "", "id", storageAccessData.identifierNumber, "{", m_codeBlock->identifier(storageAccessData.identifierNumber).string(), "}");
        out.print(", ", static_cast<ptrdiff_t>(storageAccessData.offset));
        hasPrinted = true;
    }
    ASSERT(node.hasVariableAccessData() == node.hasLocal());
    if (node.hasVariableAccessData()) {
        VariableAccessData* variableAccessData = node.variableAccessData();
        int operand = variableAccessData->operand();
        if (operandIsArgument(operand))
            out.print(hasPrinted ? ", " : "", "arg", operandToArgument(operand), "(", VariableAccessDataDump(*this, variableAccessData), ")");
        else
            out.print(hasPrinted ? ", " : "", "r", operand, "(", VariableAccessDataDump(*this, variableAccessData), ")");
        hasPrinted = true;
    }
    if (node.hasConstantBuffer()) {
        if (hasPrinted)
            out.print(", ");
        out.print(node.startConstant(), ":[");
        for (unsigned i = 0; i < node.numConstants(); ++i) {
            if (i)
                out.print(", ");
            out.print(m_codeBlock->constantBuffer(node.startConstant())[i].description());
        }
        out.print("]");
        hasPrinted = true;
    }
    if (node.hasIndexingType()) {
        if (hasPrinted)
            out.print(", ");
        out.print(indexingTypeToString(node.indexingType()));
    }
    if (op == JSConstant) {
        out.print(hasPrinted ? ", " : "", "$", node.constantNumber());
        JSValue value = valueOfJSConstant(nodeIndex);
        out.print(" = ", value.description());
        hasPrinted = true;
    }
    if (op == WeakJSConstant) {
        out.print(hasPrinted ? ", " : "", RawPointer(node.weakConstant()));
        hasPrinted = true;
    }
    if  (node.isBranch() || node.isJump()) {
        out.print(hasPrinted ? ", " : "", "T:#", node.takenBlockIndex());
        hasPrinted = true;
    }
    if  (node.isBranch()) {
        out.print(hasPrinted ? ", " : "", "F:#", node.notTakenBlockIndex());
        hasPrinted = true;
    }
    out.print(hasPrinted ? ", " : "", "bc#", node.codeOrigin.bytecodeIndex);
    hasPrinted = true;
    
    (void)hasPrinted;
    
    out.print(")");

    if (!skipped) {
        if (node.hasVariableAccessData())
            out.print("  predicting ", SpeculationDump(node.variableAccessData()->prediction()), node.variableAccessData()->shouldUseDoubleFormat() ? ", forcing double" : "");
        else if (node.hasHeapPrediction())
            out.print("  predicting ", SpeculationDump(node.getHeapPrediction()));
    }
    
    out.print("\n");
}

void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BlockIndex blockIndex, PhiNodeDumpMode phiNodeDumpMode)
{
    BasicBlock* block = m_blocks[blockIndex].get();

    out.print(prefix, "Block #", blockIndex, " (bc#", block->bytecodeBegin, "): ", block->isReachable ? "" : "(skipped)", block->isOSRTarget ? " (OSR target)" : "", "\n");
    out.print(prefix, "  Predecessors:");
    for (size_t i = 0; i < block->m_predecessors.size(); ++i)
        out.print(" #", block->m_predecessors[i]);
    out.print("\n");
    if (m_dominators.isValid()) {
        out.print(prefix, "  Dominated by:");
        for (size_t i = 0; i < m_blocks.size(); ++i) {
            if (!m_dominators.dominates(i, blockIndex))
                continue;
            out.print(" #", i);
        }
        out.print("\n");
        out.print(prefix, "  Dominates:");
        for (size_t i = 0; i < m_blocks.size(); ++i) {
            if (!m_dominators.dominates(blockIndex, i))
                continue;
            out.print(" #", i);
        }
        out.print("\n");
    }
    out.print(prefix, "  Phi Nodes:");
    for (size_t i = 0; i < block->phis.size(); ++i) {
        NodeIndex phiNodeIndex = block->phis[i];
        Node& phiNode = at(phiNodeIndex);
        if (!phiNode.shouldGenerate() && phiNodeDumpMode == DumpLivePhisOnly)
            continue;
        out.print(" @", phiNodeIndex, "->(");
        if (phiNode.child1()) {
            out.print("@", phiNode.child1().index());
            if (phiNode.child2()) {
                out.print(", @", phiNode.child2().index());
                if (phiNode.child3())
                    out.print(", @", phiNode.child3().index());
            }
        }
        out.print(")", i + 1 < block->phis.size() ? "," : "");
    }
    out.print("\n");
}

void Graph::dump(PrintStream& out)
{
    NodeIndex lastNodeIndex = NoNode;
    for (size_t b = 0; b < m_blocks.size(); ++b) {
        BasicBlock* block = m_blocks[b].get();
        if (!block)
            continue;
        dumpBlockHeader(out, "", b, DumpAllPhis);
        out.print("  vars before: ");
        if (block->cfaHasVisited)
            dumpOperands(block->valuesAtHead, out);
        else
            out.print("<empty>");
        out.print("\n");
        out.print("  var links: ");
        dumpOperands(block->variablesAtHead, out);
        out.print("\n");
        for (size_t i = 0; i < block->size(); ++i) {
            dumpCodeOrigin(out, "", lastNodeIndex, block->at(i));
            dump(out, "", block->at(i));
            lastNodeIndex = block->at(i);
        }
        out.print("  vars after: ");
        if (block->cfaHasVisited)
            dumpOperands(block->valuesAtTail, out);
        else
            out.print("<empty>");
        out.print("\n");
        out.print("  var links: ");
        dumpOperands(block->variablesAtTail, out);
        out.print("\n");
    }
}

// FIXME: Convert this to be iterative, not recursive.
#define DO_TO_CHILDREN(node, thingToDo) do {                            \
        Node& _node = (node);                                           \
        if (_node.flags() & NodeHasVarArgs) {                           \
            for (unsigned _childIdx = _node.firstChild();               \
                 _childIdx < _node.firstChild() + _node.numChildren();  \
                 _childIdx++) {                                         \
                if (!!m_varArgChildren[_childIdx])                      \
                    thingToDo(m_varArgChildren[_childIdx]);             \
            }                                                           \
        } else {                                                        \
            if (!_node.child1()) {                                      \
                ASSERT(!_node.child2()                                  \
                       && !_node.child3());                             \
                break;                                                  \
            }                                                           \
            thingToDo(_node.child1());                                  \
                                                                        \
            if (!_node.child2()) {                                      \
                ASSERT(!_node.child3());                                \
                break;                                                  \
            }                                                           \
            thingToDo(_node.child2());                                  \
                                                                        \
            if (!_node.child3())                                        \
                break;                                                  \
            thingToDo(_node.child3());                                  \
        }                                                               \
    } while (false)

void Graph::refChildren(NodeIndex op)
{
    DO_TO_CHILDREN(at(op), ref);
}

void Graph::derefChildren(NodeIndex op)
{
    DO_TO_CHILDREN(at(op), deref);
}

void Graph::predictArgumentTypes()
{
    ASSERT(m_codeBlock->numParameters() >= 1);
    for (size_t arg = 0; arg < static_cast<size_t>(m_codeBlock->numParameters()); ++arg) {
        ValueProfile* profile = m_profiledBlock->valueProfileForArgument(arg);
        if (!profile)
            continue;
        
        at(m_arguments[arg]).variableAccessData()->predict(profile->computeUpdatedPrediction());
        
#if DFG_ENABLE(DEBUG_VERBOSE)
        dataLog(
            "Argument [", arg, "] prediction: ",
            SpeculationDump(at(m_arguments[arg]).variableAccessData()->prediction()), "\n");
#endif
    }
}

void Graph::handleSuccessor(Vector<BlockIndex, 16>& worklist, BlockIndex blockIndex, BlockIndex successorIndex)
{
    BasicBlock* successor = m_blocks[successorIndex].get();
    if (!successor->isReachable) {
        successor->isReachable = true;
        worklist.append(successorIndex);
    }
    
    successor->m_predecessors.append(blockIndex);
}

void Graph::collectGarbage()
{
    // First reset the counts to 0 for all nodes.
    for (unsigned i = size(); i--;)
        at(i).setRefCount(0);
    
    // Now find the roots: the nodes that are must-generate. Set their ref counts to
    // 1 and put them on the worklist.
    Vector<NodeIndex, 128> worklist;
    for (BlockIndex blockIndex = 0; blockIndex < m_blocks.size(); ++blockIndex) {
        BasicBlock* block = m_blocks[blockIndex].get();
        if (!block)
            continue;
        for (unsigned indexInBlock = block->size(); indexInBlock--;) {
            NodeIndex nodeIndex = block->at(indexInBlock);
            Node& node = at(nodeIndex);
            if (!(node.flags() & NodeMustGenerate))
                continue;
            node.setRefCount(1);
            worklist.append(nodeIndex);
        }
    }
    
    while (!worklist.isEmpty()) {
        NodeIndex nodeIndex = worklist.last();
        worklist.removeLast();
        Node& node = at(nodeIndex);
        ASSERT(node.shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
        if (node.flags() & NodeHasVarArgs) {
            for (unsigned childIdx = node.firstChild();
                 childIdx < node.firstChild() + node.numChildren();
                 ++childIdx) {
                if (!m_varArgChildren[childIdx])
                    continue;
                NodeIndex childNodeIndex = m_varArgChildren[childIdx].index();
                if (!at(childNodeIndex).ref())
                    continue;
                worklist.append(childNodeIndex);
            }
        } else if (node.child1()) {
            if (at(node.child1()).ref())
                worklist.append(node.child1().index());
            if (node.child2()) {
                if (at(node.child2()).ref())
                    worklist.append(node.child2().index());
                if (node.child3()) {
                    if (at(node.child3()).ref())
                        worklist.append(node.child3().index());
                }
            }
        }
    }
}

void Graph::determineReachability()
{
    Vector<BlockIndex, 16> worklist;
    worklist.append(0);
    m_blocks[0]->isReachable = true;
    while (!worklist.isEmpty()) {
        BlockIndex index = worklist.last();
        worklist.removeLast();
        
        BasicBlock* block = m_blocks[index].get();
        ASSERT(block->isLinked);
        
        Node& node = at(block->last());
        ASSERT(node.isTerminal());
        
        if (node.isJump())
            handleSuccessor(worklist, index, node.takenBlockIndex());
        else if (node.isBranch()) {
            handleSuccessor(worklist, index, node.takenBlockIndex());
            handleSuccessor(worklist, index, node.notTakenBlockIndex());
        }
    }
}

void Graph::resetReachability()
{
    for (BlockIndex blockIndex = m_blocks.size(); blockIndex--;) {
        BasicBlock* block = m_blocks[blockIndex].get();
        if (!block)
            continue;
        block->isReachable = false;
        block->m_predecessors.clear();
    }
    
    determineReachability();
}

void Graph::resetExitStates()
{
    for (unsigned i = size(); i--;)
        at(i).setCanExit(true);
}

} } // namespace JSC::DFG

#endif