/*
 * Copyright (C) 2013-2015 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 "DFGCPSRethreadingPhase.h"

#if ENABLE(DFG_JIT)

#include "DFGGraph.h"
#include "DFGPhase.h"
#include "JSCJSValueInlines.h"

namespace JSC { namespace DFG {

class CPSRethreadingPhase : public Phase {
    static constexpr bool verbose = false;
public:
    CPSRethreadingPhase(Graph& graph)
        : Phase(graph, "CPS rethreading"_s)
    {
    }
    
    bool run()
    {
        RELEASE_ASSERT(m_graph.m_refCountState == EverythingIsLive);
        
        if (m_graph.m_form == ThreadedCPS)
            return false;
        
        clearIsLoadedFrom();
        freeUnnecessaryNodes();
        m_graph.clearReplacements();
        canonicalizeLocalsInBlocks();
        specialCaseArguments();
        propagatePhis<OperandKind::Local>();
        propagatePhis<OperandKind::Argument>();
        propagatePhis<OperandKind::Tmp>();
        computeIsFlushed();
        
        m_graph.m_form = ThreadedCPS;
        return true;
    }

private:
    
    void clearIsLoadedFrom()
    {
        for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
            m_graph.m_variableAccessData[i].setIsLoadedFrom(false);
    }
    
    void freeUnnecessaryNodes()
    {
        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            ASSERT(block->isReachable);
            
            unsigned fromIndex = 0;
            unsigned toIndex = 0;
            while (fromIndex < block->size()) {
                Node* node = block->at(fromIndex++);
                switch (node->op()) {
                case GetLocal:
                case Flush:
                case PhantomLocal:
                    node->children.setChild1(Edge());
                    break;
                case Phantom:
                    if (!node->child1()) {
                        m_graph.deleteNode(node);
                        continue;
                    }
                    switch (node->child1()->op()) {
                    case SetArgumentMaybe:
                        DFG_CRASH(m_graph, node, "Invalid Phantom(@SetArgumentMaybe)");
                        break;
                    case Phi:
                    case SetArgumentDefinitely:
                    case SetLocal:
                        node->convertPhantomToPhantomLocal();
                        break;
                    default:
                        ASSERT(node->child1()->hasResult());
                        break;
                    }
                    break;
                default:
                    break;
                }
                block->at(toIndex++) = node;
            }
            block->resize(toIndex);
            
            for (unsigned phiIndex = block->phis.size(); phiIndex--;)
                m_graph.deleteNode(block->phis[phiIndex]);
            block->phis.shrink(0);
        }
    }
    
    template<OperandKind operandKind>
    void clearVariables()
    {
        ASSERT(
            m_block->variablesAtHead.sizeFor<operandKind>()
            == m_block->variablesAtTail.sizeFor<operandKind>());
        
        for (unsigned i = m_block->variablesAtHead.sizeFor<operandKind>(); i--;) {
            m_block->variablesAtHead.atFor<operandKind>(i) = nullptr;
            m_block->variablesAtTail.atFor<operandKind>(i) = nullptr;
        }
    }
    
    ALWAYS_INLINE Node* addPhiSilently(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable)
    {
        Node* result = m_graph.addNode(Phi, origin, OpInfo(variable));
        block->phis.append(result);
        return result;
    }
    
    template<OperandKind operandKind>
    ALWAYS_INLINE Node* addPhi(BasicBlock* block, const NodeOrigin& origin, VariableAccessData* variable, size_t index)
    {
        Node* result = addPhiSilently(block, origin, variable);
        phiStackFor<operandKind>().append(PhiStackEntry(block, index, result));
        return result;
    }
    
    template<OperandKind operandKind>
    ALWAYS_INLINE Node* addPhi(const NodeOrigin& origin, VariableAccessData* variable, size_t index)
    {
        return addPhi<operandKind>(m_block, origin, variable, index);
    }
    
    template<OperandKind operandKind>
    void canonicalizeGetLocalFor(Node* node, VariableAccessData* variable, size_t idx)
    {
        ASSERT(!node->child1());
        
        if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
            ASSERT(otherNode->variableAccessData() == variable);
            
            switch (otherNode->op()) {
            case Flush:
            case PhantomLocal:
                otherNode = otherNode->child1().node();
                if (otherNode->op() == Phi) {
                    // We need to have a GetLocal, so this might as well be the one.
                    node->children.setChild1(Edge(otherNode));
                    m_block->variablesAtTail.atFor<operandKind>(idx) = node;
                    return;
                }
                ASSERT(otherNode->op() != SetArgumentMaybe);
                ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely);
                break;
            default:
                break;
            }
            
            ASSERT(otherNode->op() != SetArgumentMaybe);
            ASSERT(otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely || otherNode->op() == GetLocal);
            ASSERT(otherNode->variableAccessData() == variable);
            
            if (otherNode->op() == SetArgumentDefinitely) {
                variable->setIsLoadedFrom(true);
                node->children.setChild1(Edge(otherNode));
                m_block->variablesAtTail.atFor<operandKind>(idx) = node;
                return;
            }
            
            if (otherNode->op() == GetLocal) {
                // Replace all references to this GetLocal with otherNode.
                node->replaceWith(m_graph, otherNode);
                return;
            }
            
            ASSERT(otherNode->op() == SetLocal);
            node->replaceWith(m_graph, otherNode->child1().node());
            return;
        }
        
        variable->setIsLoadedFrom(true);
        Node* phi = addPhi<operandKind>(node->origin, variable, idx);
        node->children.setChild1(Edge(phi));
        m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
        m_block->variablesAtTail.atFor<operandKind>(idx) = node;
    }
    
    void canonicalizeGetLocal(Node* node)
    {
        VariableAccessData* variable = node->variableAccessData();
        switch (variable->operand().kind()) {
        case OperandKind::Argument: {
            canonicalizeGetLocalFor<OperandKind::Argument>(node, variable, variable->operand().toArgument());
            break;
        }
        case OperandKind::Local: {
            canonicalizeGetLocalFor<OperandKind::Local>(node, variable, variable->operand().toLocal());
            break;
        }
        case OperandKind::Tmp: {
            canonicalizeGetLocalFor<OperandKind::Tmp>(node, variable, variable->operand().value());
            break;
        }
        }
    }
    
    template<NodeType nodeType, OperandKind operandKind>
    void canonicalizeFlushOrPhantomLocalFor(Node* node, VariableAccessData* variable, size_t idx)
    {
        ASSERT(!node->child1());
        
        if (Node* otherNode = m_block->variablesAtTail.atFor<operandKind>(idx)) {
            ASSERT(otherNode->variableAccessData() == variable);
            
            switch (otherNode->op()) {
            case Flush:
            case PhantomLocal:
            case GetLocal:
                ASSERT(otherNode->child1().node());
                otherNode = otherNode->child1().node();
                break;
            default:
                break;
            }
            
            ASSERT(otherNode->op() == Phi || otherNode->op() == SetLocal || otherNode->op() == SetArgumentDefinitely || otherNode->op() == SetArgumentMaybe);
            
            if (nodeType == PhantomLocal && otherNode->op() == SetLocal) {
                // PhantomLocal(SetLocal) doesn't make sense. PhantomLocal means: at this
                // point I know I would have been interested in the value of this variable
                // for the purpose of OSR. PhantomLocal(SetLocal) means: at this point I
                // know that I would have read the value written by that SetLocal. This is
                // redundant and inefficient, since really it just means that we want to
                // keep the last MovHinted value of that local alive.
                
                node->remove(m_graph);
                return;
            }
            
            variable->setIsLoadedFrom(true);
            // There is nothing wrong with having redundant Flush's. It just needs to
            // be linked appropriately. Note that if there had already been a previous
            // use at tail then we don't override it. It's fine for variablesAtTail to
            // omit Flushes and PhantomLocals. On the other hand, having it refer to a
            // Flush or a PhantomLocal if just before it the last use was a GetLocal would
            // seriously confuse the CFA.
            node->children.setChild1(Edge(otherNode));
            return;
        }
        
        variable->setIsLoadedFrom(true);
        Node* phi = addPhi<operandKind>(node->origin, variable, idx);
        node->children.setChild1(Edge(phi));
        m_block->variablesAtHead.atFor<operandKind>(idx) = phi;
        m_block->variablesAtTail.atFor<operandKind>(idx) = node;
    }

    template<NodeType nodeType>
    void canonicalizeFlushOrPhantomLocal(Node* node)
    {
        VariableAccessData* variable = node->variableAccessData();
        switch (variable->operand().kind()) {
        case OperandKind::Argument: {
            canonicalizeFlushOrPhantomLocalFor<nodeType, OperandKind::Argument>(node, variable, variable->operand().toArgument());
            break;
        }
        case OperandKind::Local: {
            canonicalizeFlushOrPhantomLocalFor<nodeType, OperandKind::Local>(node, variable, variable->operand().toLocal());
            break;
        }
        case OperandKind::Tmp: {
            canonicalizeFlushOrPhantomLocalFor<nodeType, OperandKind::Tmp>(node, variable, variable->operand().value());
            break;
        }
        }
    }
    
    void canonicalizeSet(Node* node)
    {
        m_block->variablesAtTail.setOperand(node->operand(), node);
    }
    
    void canonicalizeLocalsInBlock()
    {
        if (!m_block)
            return;
        ASSERT(m_block->isReachable);
        
        clearVariables<OperandKind::Argument>();
        clearVariables<OperandKind::Local>();
        clearVariables<OperandKind::Tmp>();
        
        // Assumes that all phi references have been removed. Assumes that things that
        // should be live have a non-zero ref count, but doesn't assume that the ref
        // counts are correct beyond that (more formally !!logicalRefCount == !!actualRefCount
        // but not logicalRefCount == actualRefCount). Assumes that it can break ref
        // counts.
        
        for (auto* node : *m_block) {
            m_graph.performSubstitution(node);
            
            // The rules for threaded CPS form:
            // 
            // Head variable: describes what is live at the head of the basic block.
            // Head variable links may refer to Phi or SetArgumentDefinitely/SetArgumentMaybe.
            // SetArgumentDefinitely/SetArgumentMaybe may only appear in the root block.
            //
            // Tail variable: the last thing that happened to the variable in the block.
            // It may be a Flush, PhantomLocal, GetLocal, SetLocal, SetArgumentDefinitely/SetArgumentMaybe, or Phi.
            // SetArgumentDefinitely/SetArgumentMaybe may only appear in the root block. Note that if there ever
            // was a GetLocal to the variable, and it was followed by PhantomLocals and
            // Flushes but not SetLocals, then the tail variable will be the GetLocal.
            // This reflects the fact that you only care that the tail variable is a
            // Flush or PhantomLocal if nothing else interesting happened. Likewise, if
            // there ever was a SetLocal and it was followed by Flushes, then the tail
            // variable will be a SetLocal and not those subsequent Flushes.
            //
            // Child of GetLocal: the operation that the GetLocal keeps alive. It may be
            // a Phi from the current block. For arguments, it may be a SetArgumentDefinitely
            // but it can't be a SetArgumentMaybe.
            //
            // Child of SetLocal: must be a value producing node.
            //
            // Child of Flush: it may be a Phi from the current block or a SetLocal. For
            // arguments it may also be a SetArgumentDefinitely/SetArgumentMaybe.
            //
            // Child of PhantomLocal: it may be a Phi from the current block. For
            // arguments it may also be a SetArgumentDefinitely/SetArgumentMaybe.
            //
            // Children of Phi: other Phis in the same basic block, or any of the
            // following from predecessor blocks: SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe.
            // These are computed by looking at the tail variables of the predecessor blocks
            // and either using it directly (if it's a SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe) or
            // loading that nodes child (if it's a GetLocal, PhanomLocal, or Flush - all
            // of these will have children that are SetLocal, Phi, or SetArgumentDefinitely/SetArgumentMaybe).
            
            switch (node->op()) {
            case GetLocal:
                canonicalizeGetLocal(node);
                break;
                
            case SetLocal:
                canonicalizeSet(node);
                break;
                
            case Flush:
                canonicalizeFlushOrPhantomLocal<Flush>(node);
                break;
                
            case PhantomLocal:
                canonicalizeFlushOrPhantomLocal<PhantomLocal>(node);
                break;
                
            case SetArgumentDefinitely:
            case SetArgumentMaybe:
                canonicalizeSet(node);
                break;
                
            default:
                break;
            }
        }
    }
    
    void canonicalizeLocalsInBlocks()
    {
        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
            m_block = m_graph.block(blockIndex);
            canonicalizeLocalsInBlock();
        }
    }
    
    void specialCaseArguments()
    {
        // Normally, a SetArgumentDefinitely denotes the start of a live range for a local's value on the stack.
        // But those SetArguments used for the actual arguments to the machine CodeBlock get
        // special-cased. We could have instead used two different node types - one for the arguments
        // at the prologue case, and another for the other uses. But this seemed like IR overkill.

        for (auto& pair : m_graph.m_rootToArguments) {
            BasicBlock* entrypoint = pair.key;
            const ArgumentsVector& arguments = pair.value;
            for (unsigned i = arguments.size(); i--;)
                entrypoint->variablesAtHead.setArgumentFirstTime(i, arguments[i]);
        }
    }
    
    template<OperandKind operandKind>
    void propagatePhis()
    {
        Vector<PhiStackEntry, 128>& phiStack = phiStackFor<operandKind>();
        
        // Ensure that attempts to use this fail instantly.
        m_block = nullptr;
        
        while (!phiStack.isEmpty()) {
            PhiStackEntry entry = phiStack.last();
            phiStack.removeLast();
            
            BasicBlock* block = entry.m_block;
            PredecessorList& predecessors = block->predecessors;
            Node* currentPhi = entry.m_phi;
            VariableAccessData* variable = currentPhi->variableAccessData();
            size_t index = entry.m_index;
            
            if (verbose) {
                WTF::dataFile().atomically([&](auto&) {
                    dataLog(" Iterating on phi from block ", block, " ");
                    m_graph.dump(WTF::dataFile(), "", currentPhi);
                });
            }

            for (size_t i = predecessors.size(); i--;) {
                BasicBlock* predecessorBlock = predecessors[i];
                
                Node* variableInPrevious = predecessorBlock->variablesAtTail.atFor<operandKind>(index);
                if (!variableInPrevious) {
                    variableInPrevious = addPhi<operandKind>(predecessorBlock, currentPhi->origin, variable, index);
                    predecessorBlock->variablesAtTail.atFor<operandKind>(index) = variableInPrevious;
                    predecessorBlock->variablesAtHead.atFor<operandKind>(index) = variableInPrevious;
                    dataLogLnIf(verbose, "    No variable in predecessor ", predecessorBlock, " creating a new phi: ", variableInPrevious);
                } else {
                    switch (variableInPrevious->op()) {
                    case GetLocal:
                    case PhantomLocal:
                    case Flush:
                        dataLogLnIf(verbose, "    Variable in predecessor ", predecessorBlock, " ", variableInPrevious, " needs to be forwarded to first child ", variableInPrevious->child1().node());
                        ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
                        variableInPrevious = variableInPrevious->child1().node();
                        break;
                    default:
                        break;
                    }
                }
                
                ASSERT(
                    variableInPrevious->op() == SetLocal
                    || variableInPrevious->op() == Phi
                    || variableInPrevious->op() == SetArgumentDefinitely
                    || variableInPrevious->op() == SetArgumentMaybe);
          
                if (verbose) {
                    WTF::dataFile().atomically([&](auto& out) {
                        m_graph.dump(out, "    Adding new variable from predecessor ", variableInPrevious);
                    });
                }

                if (!currentPhi->child1()) {
                    currentPhi->children.setChild1(Edge(variableInPrevious));
                    continue;
                }
                if (!currentPhi->child2()) {
                    currentPhi->children.setChild2(Edge(variableInPrevious));
                    continue;
                }
                if (!currentPhi->child3()) {
                    currentPhi->children.setChild3(Edge(variableInPrevious));
                    continue;
                }
                
                Node* newPhi = addPhiSilently(block, currentPhi->origin, variable);
                newPhi->children = currentPhi->children;
                currentPhi->children.initialize(newPhi, variableInPrevious, nullptr);
            }
        }
    }
    
    struct PhiStackEntry {
        PhiStackEntry(BasicBlock* block, size_t index, Node* phi)
            : m_block(block)
            , m_index(index)
            , m_phi(phi)
        {
        }
        
        BasicBlock* m_block;
        size_t m_index;
        Node* m_phi;
    };
    
    template<OperandKind operandKind>
    Vector<PhiStackEntry, 128>& phiStackFor()
    {
        switch (operandKind) {
        case OperandKind::Argument: return m_argumentPhiStack;
        case OperandKind::Local: return m_localPhiStack;
        case OperandKind::Tmp: return m_tmpPhiStack;
        }
        RELEASE_ASSERT_NOT_REACHED();
    }
    
    void computeIsFlushed()
    {
        m_graph.clearFlagsOnAllNodes(NodeIsFlushed);
        
        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            for (unsigned nodeIndex = block->size(); nodeIndex--;) {
                Node* node = block->at(nodeIndex);
                if (node->op() != Flush)
                    continue;
                addFlushedLocalOp(node);
            }
        }
        while (!m_flushedLocalOpWorklist.isEmpty()) {
            Node* node = m_flushedLocalOpWorklist.takeLast();
            switch (node->op()) {
            case SetLocal:
            case SetArgumentDefinitely:
            case SetArgumentMaybe:
                break;
                
            case Flush:
            case Phi:
                ASSERT(node->flags() & NodeIsFlushed);
                DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge);
                break;

            default:
                DFG_CRASH(m_graph, node, "Invalid node in flush graph");
                break;
            }
        }
    }
    
    void addFlushedLocalOp(Node* node)
    {
        if (node->mergeFlags(NodeIsFlushed))
            m_flushedLocalOpWorklist.append(node);
    }

    void addFlushedLocalEdge(Node*, Edge edge)
    {
        addFlushedLocalOp(edge.node());
    }

    BasicBlock* m_block;
    Vector<PhiStackEntry, 128> m_argumentPhiStack;
    Vector<PhiStackEntry, 128> m_localPhiStack;
    Vector<PhiStackEntry, 128> m_tmpPhiStack;
    Vector<Node*, 128> m_flushedLocalOpWorklist;
};

bool performCPSRethreading(Graph& graph)
{
    return runPhase<CPSRethreadingPhase>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)