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

#if ENABLE(DFG_JIT)

#include "DFGBasicBlockInlines.h"
#include "DFGBlockInsertionSet.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGSSACalculator.h"
#include "DFGVariableAccessDataDump.h"
#include "JSCInlines.h"

#undef RELEASE_ASSERT
#define RELEASE_ASSERT(assertion) do { \
    if (!(assertion)) { \
        WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
        CRASH(); \
    } \
} while (0)

namespace JSC { namespace DFG {

class SSAConversionPhase : public Phase {
    static constexpr bool verbose = false;
    
public:
    SSAConversionPhase(Graph& graph)
        : Phase(graph, "SSA conversion")
        , m_insertionSet(graph)
    {
    }
    
    bool run()
    {
        RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
        RELEASE_ASSERT(!m_graph.m_isInSSAConversion);
        m_graph.m_isInSSAConversion = true;
        
        m_graph.clearReplacements();
        m_graph.clearCPSCFGData();

        HashMap<unsigned, BasicBlock*, WTF::IntHash<unsigned>, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> entrypointIndexToArgumentsBlock;

        m_graph.m_numberOfEntrypoints = m_graph.m_roots.size();
        m_graph.m_argumentFormats.resize(m_graph.m_numberOfEntrypoints);

        for (unsigned entrypointIndex = 0; entrypointIndex < m_graph.m_numberOfEntrypoints; ++entrypointIndex) {
            BasicBlock* oldRoot = m_graph.m_roots[entrypointIndex];
            entrypointIndexToArgumentsBlock.add(entrypointIndex, oldRoot);
            
            NodeOrigin origin = oldRoot->at(0)->origin;
            m_insertionSet.insertNode(
                0, SpecNone, InitializeEntrypointArguments, origin, OpInfo(entrypointIndex));
            m_insertionSet.insertNode(
                0, SpecNone, ExitOK, origin);
            m_insertionSet.execute(oldRoot);
        }

        if (m_graph.m_numberOfEntrypoints > 1) {
            BlockInsertionSet blockInsertionSet(m_graph);
            BasicBlock* newRoot = blockInsertionSet.insert(0, 1.0f);

            EntrySwitchData* entrySwitchData = m_graph.m_entrySwitchData.add();
            for (unsigned entrypointIndex = 0; entrypointIndex < m_graph.m_numberOfEntrypoints; ++entrypointIndex) {
                BasicBlock* oldRoot = m_graph.m_roots[entrypointIndex];
                entrySwitchData->cases.append(oldRoot);

                ASSERT(oldRoot->predecessors.isEmpty());
                oldRoot->predecessors.append(newRoot);

                if (oldRoot->isCatchEntrypoint) {
                    ASSERT(!!entrypointIndex);
                    m_graph.m_entrypointIndexToCatchBytecodeIndex.add(entrypointIndex, oldRoot->bytecodeBegin);
                }
            }

            RELEASE_ASSERT(entrySwitchData->cases[0] == m_graph.block(0)); // We strongly assume the normal call entrypoint is the first item in the list.

            const bool exitOK = false;
            NodeOrigin origin { CodeOrigin(BytecodeIndex(0)), CodeOrigin(BytecodeIndex(0)), exitOK };
            newRoot->appendNode(
                m_graph, SpecNone, EntrySwitch, origin, OpInfo(entrySwitchData));

            m_graph.m_roots.clear();
            m_graph.m_roots.append(newRoot);

            blockInsertionSet.execute();
        }
        
        SSACalculator calculator(m_graph);

        m_graph.ensureSSADominators();
        
        if (verbose) {
            dataLog("Graph before SSA transformation:\n");
            m_graph.dump();
        }

        // Create a SSACalculator::Variable for every root VariableAccessData.
        for (VariableAccessData& variable : m_graph.m_variableAccessData) {
            if (!variable.isRoot())
                continue;
            
            SSACalculator::Variable* ssaVariable = calculator.newVariable();
            ASSERT(ssaVariable->index() == m_variableForSSAIndex.size());
            m_variableForSSAIndex.append(&variable);
            m_ssaVariableForVariable.add(&variable, ssaVariable);
        }
        
        // Find all SetLocals and create Defs for them. We handle SetArgumentDefinitely by creating a
        // GetLocal, and recording the flush format.
        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            
            // Must process the block in forward direction because we want to see the last
            // assignment for every local.
            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                Node* node = block->at(nodeIndex);
                if (node->op() != SetLocal && node->op() != SetArgumentDefinitely)
                    continue;
                
                VariableAccessData* variable = node->variableAccessData();
                
                Node* childNode;
                if (node->op() == SetLocal)
                    childNode = node->child1().node();
                else {
                    ASSERT(node->op() == SetArgumentDefinitely);
                    childNode = m_insertionSet.insertNode(
                        nodeIndex, node->variableAccessData()->prediction(),
                        GetStack, node->origin,
                        OpInfo(m_graph.m_stackAccessData.add(variable->local(), variable->flushFormat())));
                    if (!ASSERT_DISABLED)
                        m_argumentGetters.add(childNode);
                    m_argumentMapping.add(node, childNode);
                }
                
                calculator.newDef(
                    m_ssaVariableForVariable.get(variable), block, childNode);
            }
            
            m_insertionSet.execute(block);
        }
        
        // Decide where Phis are to be inserted. This creates the Phi's but doesn't insert them
        // yet. We will later know where to insert based on where SSACalculator tells us to.
        calculator.computePhis(
            [&] (SSACalculator::Variable* ssaVariable, BasicBlock* block) -> Node* {
                VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
                
                // Prune by liveness. This doesn't buy us much other than compile times.
                Node* headNode = block->variablesAtHead.operand(variable->local());
                if (!headNode)
                    return nullptr;

                // There is the possibiltiy of "rebirths". The SSA calculator will already prune
                // rebirths for the same VariableAccessData. But it will not be able to prune
                // rebirths that arose from the same local variable number but a different
                // VariableAccessData. We do that pruning here.
                //
                // Here's an example of a rebirth that this would catch:
                //
                //     var x;
                //     if (foo) {
                //         if (bar) {
                //             x = 42;
                //         } else {
                //             x = 43;
                //         }
                //         print(x);
                //         x = 44;
                //     } else {
                //         x = 45;
                //     }
                //     print(x); // Without this check, we'd have a Phi for x = 42|43 here.
                //
                // FIXME: Consider feeding local variable numbers, not VariableAccessData*'s, as
                // the "variables" for SSACalculator. That would allow us to eliminate this
                // special case.
                // https://bugs.webkit.org/show_bug.cgi?id=136641
                if (headNode->variableAccessData() != variable)
                    return nullptr;
                
                Node* phiNode = m_graph.addNode(
                    variable->prediction(), Phi, block->at(0)->origin.withInvalidExit());
                FlushFormat format = variable->flushFormat();
                NodeFlags result = resultFor(format);
                phiNode->mergeFlags(result);
                return phiNode;
            });
        
        if (verbose) {
            dataLog("Computed Phis, about to transform the graph.\n");
            dataLog("\n");
            dataLog("Graph:\n");
            m_graph.dump();
            dataLog("\n");
            dataLog("Mappings:\n");
            for (unsigned i = 0; i < m_variableForSSAIndex.size(); ++i)
                dataLog("    ", i, ": ", VariableAccessDataDump(m_graph, m_variableForSSAIndex[i]), "\n");
            dataLog("\n");
            dataLog("SSA calculator: ", calculator, "\n");
        }
        
        // Do the bulk of the SSA conversion. For each block, this tracks the operand->Node
        // mapping based on a combination of what the SSACalculator tells us, and us walking over
        // the block in forward order. We use our own data structure, valueForOperand, for
        // determining the local mapping, but we rely on SSACalculator for the non-local mapping.
        //
        // This does three things at once:
        //
        // - Inserts the Phis in all of the places where they need to go. We've already created
        //   them and they are accounted for in the SSACalculator's data structures, but we
        //   haven't inserted them yet, mostly because we want to insert all of a block's Phis in
        //   one go to amortize the cost of node insertion.
        //
        // - Create and insert Upsilons.
        //
        // - Convert all of the preexisting SSA nodes (other than the old CPS Phi nodes) into SSA
        //   form by replacing as follows:
        //
        //   - MovHint has KillLocal prepended to it.
        //
        //   - GetLocal die and get replaced with references to the node specified by
        //     valueForOperand.
        //
        //   - SetLocal turns into PutStack if it's flushed, or turns into a Check otherwise.
        //
        //   - Flush is removed.
        //
        //   - PhantomLocal becomes Phantom, and its child is whatever is specified by
        //     valueForOperand.
        //
        //   - SetArgumentDefinitely is removed. Note that GetStack nodes have already been inserted.
        //
        //   - SetArgumentMaybe is removed. It should not have any data flow uses.
        Operands<Node*> valueForOperand(OperandsLike, m_graph.block(0)->variablesAtHead);
        for (BasicBlock* block : m_graph.blocksInPreOrder()) {
            valueForOperand.clear();
            
            // CPS will claim that the root block has all arguments live. But we have already done
            // the first step of SSA conversion: argument locals are no longer live at head;
            // instead we have GetStack nodes for extracting the values of arguments. So, we
            // skip the at-head available value calculation for the root block.
            if (block != m_graph.block(0)) {
                for (size_t i = valueForOperand.size(); i--;) {
                    Node* nodeAtHead = block->variablesAtHead[i];
                    if (!nodeAtHead)
                        continue;
                    
                    VariableAccessData* variable = nodeAtHead->variableAccessData();
                    
                    if (verbose)
                        dataLog("Considering live variable ", VariableAccessDataDump(m_graph, variable), " at head of block ", *block, "\n");
                    
                    SSACalculator::Variable* ssaVariable = m_ssaVariableForVariable.get(variable);
                    SSACalculator::Def* def = calculator.reachingDefAtHead(block, ssaVariable);
                    if (!def) {
                        // If we are required to insert a Phi, then we won't have a reaching def
                        // at head.
                        continue;
                    }
                    
                    Node* node = def->value();
                    if (node->replacement()) {
                        // This will occur when a SetLocal had a GetLocal as its source. The
                        // GetLocal would get replaced with an actual SSA value by the time we get
                        // here. Note that the SSA value with which the GetLocal got replaced
                        // would not in turn have a replacement.
                        node = node->replacement();
                        ASSERT(!node->replacement());
                    }
                    if (verbose)
                        dataLog("Mapping: ", VirtualRegister(valueForOperand.operandForIndex(i)), " -> ", node, "\n");
                    valueForOperand[i] = node;
                }
            }
            
            // Insert Phis by asking the calculator what phis there are in this block. Also update
            // valueForOperand with those Phis. For Phis associated with variables that are not
            // flushed, we also insert a MovHint.
            size_t phiInsertionPoint = 0;
            for (SSACalculator::Def* phiDef : calculator.phisForBlock(block)) {
                VariableAccessData* variable = m_variableForSSAIndex[phiDef->variable()->index()];
                
                m_insertionSet.insert(phiInsertionPoint, phiDef->value());
                valueForOperand.operand(variable->local()) = phiDef->value();
                
                m_insertionSet.insertNode(
                    phiInsertionPoint, SpecNone, MovHint, block->at(0)->origin.withInvalidExit(),
                    OpInfo(variable->local().offset()), phiDef->value()->defaultEdge());
            }

            if (block->at(0)->origin.exitOK)
                m_insertionSet.insertNode(phiInsertionPoint, SpecNone, ExitOK, block->at(0)->origin);
            
            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                Node* node = block->at(nodeIndex);
                
                if (verbose) {
                    dataLog("Processing node ", node, ":\n");
                    m_graph.dump(WTF::dataFile(), "    ", node);
                }
                
                m_graph.performSubstitution(node);
                
                switch (node->op()) {
                case MovHint: {
                    m_insertionSet.insertNode(
                        nodeIndex, SpecNone, KillStack, node->origin,
                        OpInfo(node->unlinkedLocal().offset()));
                    node->origin.exitOK = false; // KillStack clobbers exit.
                    break;
                }
                    
                case SetLocal: {
                    VariableAccessData* variable = node->variableAccessData();
                    Node* child = node->child1().node();
                    
                    if (!!(node->flags() & NodeIsFlushed)) {
                        node->convertToPutStack(
                            m_graph.m_stackAccessData.add(
                                variable->local(), variable->flushFormat()));
                    } else
                        node->remove(m_graph);
                    
                    if (verbose)
                        dataLog("Mapping: ", variable->local(), " -> ", child, "\n");
                    valueForOperand.operand(variable->local()) = child;
                    break;
                }
                    
                case GetStack: {
                    ASSERT(m_argumentGetters.contains(node));
                    valueForOperand.operand(node->stackAccessData()->local) = node;
                    break;
                }
                    
                case GetLocal: {
                    VariableAccessData* variable = node->variableAccessData();
                    node->children.reset();
                    
                    node->remove(m_graph);
                    if (verbose)
                        dataLog("Replacing node ", node, " with ", valueForOperand.operand(variable->local()), "\n");
                    node->setReplacement(valueForOperand.operand(variable->local()));
                    break;
                }
                    
                case Flush: {
                    node->children.reset();
                    node->remove(m_graph);
                    break;
                }
                    
                case PhantomLocal: {
                    ASSERT(node->child1().useKind() == UntypedUse);
                    VariableAccessData* variable = node->variableAccessData();
                    node->child1() = valueForOperand.operand(variable->local())->defaultEdge();
                    node->remove(m_graph);
                    break;
                }
                    
                case SetArgumentDefinitely: {
                    node->remove(m_graph);
                    break;
                }

                case SetArgumentMaybe: {
                    node->remove(m_graph);
                    break;
                }
                    
                default:
                    break;
                }
            }
            
            // We want to insert Upsilons just before the end of the block. On the surface this
            // seems dangerous because the Upsilon will have a checking UseKind. But, we will not
            // actually be performing the check at the point of the Upsilon; the check will
            // already have been performed at the point where the original SetLocal was.
            NodeAndIndex terminal = block->findTerminal();
            size_t upsilonInsertionPoint = terminal.index;
            NodeOrigin upsilonOrigin = terminal.node->origin;
            for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
                BasicBlock* successorBlock = block->successor(successorIndex);
                for (SSACalculator::Def* phiDef : calculator.phisForBlock(successorBlock)) {
                    Node* phiNode = phiDef->value();
                    SSACalculator::Variable* ssaVariable = phiDef->variable();
                    VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
                    FlushFormat format = variable->flushFormat();

                    // We can use an unchecked use kind because the SetLocal was turned into a Check.
                    // We have to use an unchecked use because at least sometimes, the end of the block
                    // is not exitOK.
                    UseKind useKind = uncheckedUseKindFor(format);

                    dataLogLnIf(verbose, "Inserting Upsilon for ", variable->local(), " propagating ", valueForOperand.operand(variable->local()), " to ", phiNode);
                    
                    m_insertionSet.insertNode(
                        upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
                        OpInfo(phiNode), Edge(
                            valueForOperand.operand(variable->local()),
                            useKind));
                }
            }
            
            m_insertionSet.execute(block);
        }
        
        // Free all CPS phis and reset variables vectors.
        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            for (unsigned phiIndex = block->phis.size(); phiIndex--;)
                m_graph.deleteNode(block->phis[phiIndex]);
            block->phis.clear();
            block->variablesAtHead.clear();
            block->variablesAtTail.clear();
            block->valuesAtHead.clear();
            block->valuesAtHead.clear();
            block->ssa = makeUnique<BasicBlock::SSAData>(block);
        }

        for (auto& pair : entrypointIndexToArgumentsBlock) {
            unsigned entrypointIndex = pair.key;
            BasicBlock* oldRoot = pair.value;
            ArgumentsVector& arguments = m_graph.m_rootToArguments.find(oldRoot)->value;
            Vector<FlushFormat> argumentFormats;
            argumentFormats.reserveInitialCapacity(arguments.size());
            for (unsigned i = 0; i < arguments.size(); ++i) {
                Node* node = m_argumentMapping.get(arguments[i]);
                RELEASE_ASSERT(node);
                argumentFormats.uncheckedAppend(node->stackAccessData()->format);
            }
            m_graph.m_argumentFormats[entrypointIndex] = WTFMove(argumentFormats);
        }

        m_graph.m_rootToArguments.clear();

        RELEASE_ASSERT(m_graph.m_isInSSAConversion);
        m_graph.m_isInSSAConversion = false;

        m_graph.m_form = SSA;

        if (verbose) {
            dataLog("Graph after SSA transformation:\n");
            m_graph.dump();
        }

        return true;
    }

private:
    InsertionSet m_insertionSet;
    HashMap<VariableAccessData*, SSACalculator::Variable*> m_ssaVariableForVariable;
    HashMap<Node*, Node*> m_argumentMapping;
    HashSet<Node*> m_argumentGetters;
    Vector<VariableAccessData*> m_variableForSSAIndex;
};

bool performSSAConversion(Graph& graph)
{
    bool result = runPhase<SSAConversionPhase>(graph);
    return result;
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)