/*
 * Copyright (C) 2012-2018 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 "DFGTypeCheckHoistingPhase.h"

#if ENABLE(DFG_JIT)

#include "DFGBasicBlock.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGVariableAccessDataDump.h"
#include "JSCInlines.h"
#include <wtf/HashMap.h>

namespace JSC { namespace DFG {

enum CheckBallot { VoteOther, VoteStructureCheck = 1, VoteCheckArray = 1 };

struct ArrayTypeCheck;
struct StructureTypeCheck;

struct CheckData {
    Structure* m_structure;
    ArrayMode m_arrayMode;
    bool m_arrayModeIsValid;
    bool m_arrayModeHoistingOkay;
    
    CheckData()
        : m_structure(0)
        , m_arrayModeIsValid(false)
        , m_arrayModeHoistingOkay(false)
    {
    }
    
    CheckData(Structure* structure)
        : m_structure(structure)
        , m_arrayModeIsValid(false)
        , m_arrayModeHoistingOkay(true)
    {
    }

    CheckData(ArrayMode arrayMode)
        : m_structure(0)
        , m_arrayMode(arrayMode)
        , m_arrayModeIsValid(true)
        , m_arrayModeHoistingOkay(true)
    {
    }

    void disableCheckArrayHoisting()
    {
        m_arrayModeIsValid = false;
        m_arrayModeHoistingOkay = false;
    }
};
    
class TypeCheckHoistingPhase : public Phase {
public:
    TypeCheckHoistingPhase(Graph& graph)
        : Phase(graph, "structure check hoisting")
    {
    }
    
    bool run()
    {
        ASSERT(m_graph.m_form == ThreadedCPS);
        
        clearVariableVotes();
        identifyRedundantStructureChecks();
        disableHoistingForVariablesWithInsufficientVotes<StructureTypeCheck>();

        clearVariableVotes();
        identifyRedundantArrayChecks();
        disableHoistingForVariablesWithInsufficientVotes<ArrayTypeCheck>();

        disableHoistingAcrossOSREntries<StructureTypeCheck>();
        disableHoistingAcrossOSREntries<ArrayTypeCheck>();

        bool changed = false;

        // Place CheckStructure's at SetLocal sites.
        InsertionSet insertionSet(m_graph);
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            unsigned indexForChecks = UINT_MAX;
            NodeOrigin originForChecks;
            for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
                Node* node = block->at(indexInBlock);
                
                if (node->origin.exitOK) {
                    indexForChecks = indexInBlock;
                    originForChecks = node->origin;
                }
                
                // Be careful not to use 'node' after appending to the graph. In those switch
                // cases where we need to append, we first carefully extract everything we need
                // from the node, before doing any appending.
                switch (node->op()) {
                case SetArgumentDefinitely: {
                    // Insert a GetLocal and a CheckStructure immediately following this
                    // SetArgumentDefinitely, if the variable was a candidate for structure hoisting.
                    // If the basic block previously only had the SetArgumentDefinitely as its
                    // variable-at-tail, then replace it with this GetLocal.
                    VariableAccessData* variable = node->variableAccessData();
                    HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
                    if (iter == m_map.end())
                        break;
                    if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid)
                        break;

                    // Currently we should only be doing this hoisting for SetArguments at a CFG root.
                    ASSERT(m_graph.isRoot(block));

                    NodeOrigin origin = node->origin;
                    RELEASE_ASSERT(origin.exitOK);
                    
                    Node* getLocal = insertionSet.insertNode(
                        indexInBlock + 1, variable->prediction(), GetLocal, origin,
                        OpInfo(variable), Edge(node));
                    if (iter->value.m_structure) {
                        auto checkOp = CheckStructure;
                        if (SpecCellCheck & SpecEmpty) {
                            VirtualRegister local = node->variableAccessData()->local();
                            auto* inlineCallFrame = node->origin.semantic.inlineCallFrame();
                            if ((local - (inlineCallFrame ? inlineCallFrame->stackOffset : 0)) == virtualRegisterForArgument(0)) {
                                // |this| can be the TDZ value. The call entrypoint won't have |this| as TDZ,
                                // but a catch or a loop OSR entry may have |this| be TDZ.
                                checkOp = CheckStructureOrEmpty;
                            }
                        }

                        insertionSet.insertNode(
                            indexInBlock + 1, SpecNone, checkOp, origin,
                            OpInfo(m_graph.addStructureSet(iter->value.m_structure)),
                            Edge(getLocal, CellUse));
                    } else if (iter->value.m_arrayModeIsValid) {
                        ASSERT(iter->value.m_arrayModeHoistingOkay);
                        insertionSet.insertNode(
                            indexInBlock + 1, SpecNone, CheckArray, origin,
                            OpInfo(iter->value.m_arrayMode.asWord()),
                            Edge(getLocal, CellUse));
                    } else
                        RELEASE_ASSERT_NOT_REACHED();

                    if (block->variablesAtTail.operand(variable->local()) == node)
                        block->variablesAtTail.operand(variable->local()) = getLocal;
                    
                    m_graph.substituteGetLocal(*block, indexInBlock, variable, getLocal);
                    
                    changed = true;
                    break;
                }
                    
                case SetLocal: {
                    VariableAccessData* variable = node->variableAccessData();
                    HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
                    if (iter == m_map.end())
                        break;
                    if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid)
                        break;

                    NodeOrigin origin = node->origin;
                    Edge child1 = node->child1();
                    
                    if (iter->value.m_structure) {
                        // Note: On 64-bit platforms, cell checks allow the empty value to flow through.
                        // This means that this structure check may see the empty value as input. We need
                        // to emit a node that explicitly handles the empty value. Most of the time, CheckStructureOrEmpty
                        // will be folded to CheckStructure because AI proves that the incoming value is
                        // definitely not empty.
                        insertionSet.insertNode(
                            indexForChecks, SpecNone, (SpecCellCheck & SpecEmpty) ? CheckStructureOrEmpty : CheckStructure,
                            originForChecks.withSemantic(origin.semantic),
                            OpInfo(m_graph.addStructureSet(iter->value.m_structure)),
                            Edge(child1.node(), CellUse));
                    } else if (iter->value.m_arrayModeIsValid) {
                        ASSERT(iter->value.m_arrayModeHoistingOkay);
                        insertionSet.insertNode(
                            indexForChecks, SpecNone, CheckArray,
                            originForChecks.withSemantic(origin.semantic),
                            OpInfo(iter->value.m_arrayMode.asWord()),
                            Edge(child1.node(), CellUse));
                    } else
                        RELEASE_ASSERT_NOT_REACHED();
                    changed = true;
                    break;
                }
                    
                default:
                    break;
                }
            }
            insertionSet.execute(block);
        }
        
        return changed;
    }

private:
    void clearVariableVotes()
    { 
        for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
            VariableAccessData* variable = &m_graph.m_variableAccessData[i];
            if (!variable->isRoot())
                continue;
            variable->clearVotes();
        }
    }
        
    // Identify the set of variables that are always subject to the same structure
    // checks. For now, only consider monomorphic structure checks (one structure).
    void identifyRedundantStructureChecks()
    {    
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
                Node* node = block->at(indexInBlock);
                switch (node->op()) {
                case CheckStructure: {
                    Node* child = node->child1().node();
                    if (child->op() != GetLocal)
                        break;
                    VariableAccessData* variable = child->variableAccessData();
                    variable->vote(VoteStructureCheck);
                    if (!shouldConsiderForHoisting<StructureTypeCheck>(variable))
                        break;
                    noticeStructureCheck(variable, node->structureSet());
                    break;
                }

                case ArrayifyToStructure:
                case Arrayify:
                case GetByOffset:
                case PutByOffset:
                case PutStructure:
                case AllocatePropertyStorage:
                case ReallocatePropertyStorage:
                case NukeStructureAndSetButterfly:
                case GetButterfly:
                case GetByVal:
                case PutByValDirect:
                case PutByVal:
                case PutByValAlias:
                case GetArrayLength:
                case CheckArray:
                case GetIndexedPropertyStorage:
                case GetTypedArrayByteOffset:
                case Phantom:
                case MovHint:
                case MultiGetByOffset:
                case MultiPutByOffset:
                    // Don't count these uses.
                    break;
                    
                case SetLocal: {
                    // Find all uses of the source of the SetLocal. If any of them are a
                    // kind of CheckStructure, then we should notice them to ensure that
                    // we're not hoisting a check that would contravene checks that are
                    // already being performed.
                    VariableAccessData* variable = node->variableAccessData();
                    if (!shouldConsiderForHoisting<StructureTypeCheck>(variable))
                        break;
                    Node* source = node->child1().node();
                    for (auto* subNode : *block) {
                        switch (subNode->op()) {
                        case CheckStructure: {
                            if (subNode->child1() != source)
                                break;
                            
                            noticeStructureCheck(variable, subNode->structureSet());
                            break;
                        }
                        default:
                            break;
                        }
                    }
                    
                    m_graph.voteChildren(node, VoteOther);
                    break;
                }
                    
                default:
                    m_graph.voteChildren(node, VoteOther);
                    break;
                }
            }
        }
    }
        
    void identifyRedundantArrayChecks()
    {
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            for (auto* node : *block) {
                switch (node->op()) {
                case CheckArray: {
                    Node* child = node->child1().node();
                    if (child->op() != GetLocal)
                        break;
                    VariableAccessData* variable = child->variableAccessData();
                    variable->vote(VoteCheckArray);
                    if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
                        break;
                    noticeCheckArray(variable, node->arrayMode());
                    break;
                }

                case CheckStructure:
                case GetByOffset:
                case PutByOffset:
                case PutStructure:
                case ReallocatePropertyStorage:
                case GetButterfly:
                case GetByVal:
                case PutByValDirect:
                case PutByVal:
                case PutByValAlias:
                case GetArrayLength:
                case GetIndexedPropertyStorage:
                case Phantom:
                case MovHint:
                case MultiGetByOffset:
                case MultiPutByOffset:
                    // Don't count these uses.
                    break;
                    
                case AllocatePropertyStorage:
                case ArrayifyToStructure:
                case Arrayify: {
                    // Any Arrayify could change our indexing type, so disable
                    // all CheckArray hoisting.
                    Node* child = node->child1().node();
                    if (child->op() != GetLocal)
                        break;
                    VariableAccessData* variable = child->variableAccessData();
                    variable->vote(VoteOther);
                    if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
                        break;
                    disableCheckArrayHoisting(variable);
                    break;
                }
                    
                case SetLocal: {
                    // Find all uses of the source of the SetLocal. If any of them are a
                    // kind of CheckStructure, then we should notice them to ensure that
                    // we're not hoisting a check that would contravene checks that are
                    // already being performed.
                    VariableAccessData* variable = node->variableAccessData();
                    if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable))
                        break;
                    Node* source = node->child1().node();
                    for (auto subNode : *block) {
                        switch (subNode->op()) {
                        case CheckStructure: {
                            if (subNode->child1() != source)
                                break;
                            
                            noticeStructureCheckAccountingForArrayMode(variable, subNode->structureSet());
                            break;
                        }
                        case CheckArray: {
                            if (subNode->child1() != source)
                                break;
                            noticeCheckArray(variable, subNode->arrayMode());
                            break;
                        }
                        default:
                            break;
                        }
                    }
                    
                    m_graph.voteChildren(node, VoteOther);
                    break;
                }
                    
                default:
                    m_graph.voteChildren(node, VoteOther);
                    break;
                }
            }
        }
    }

    // Disable hoisting on variables that appear to mostly be used in
    // contexts where it doesn't make sense.
    template <typename TypeCheck>
    void disableHoistingForVariablesWithInsufficientVotes()
    {    
        for (unsigned i = m_graph.m_variableAccessData.size(); i--;) {
            VariableAccessData* variable = &m_graph.m_variableAccessData[i];
            if (!variable->isRoot())
                continue;
            if (TypeCheck::hasEnoughVotesToHoist(variable))
                continue;
            HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
            if (iter == m_map.end())
                continue;
            TypeCheck::disableHoisting(iter->value);
        }
    }

    // Disable check hoisting for variables that cross the OSR entry that
    // we're currently taking, and where the value currently does not have the
    // particular form we want (e.g. a contradictory ArrayMode or Struture).
    template <typename TypeCheck>
    void disableHoistingAcrossOSREntries()
    {
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
            BasicBlock* block = m_graph.block(blockIndex);
            if (!block)
                continue;
            ASSERT(block->isReachable);
            if (!block->isOSRTarget)
                continue;
            if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex())
                continue;
            const Operands<Optional<JSValue>>& mustHandleValues = m_graph.m_plan.mustHandleValues();
            for (size_t i = 0; i < mustHandleValues.size(); ++i) {
                int operand = mustHandleValues.operandForIndex(i);
                Node* node = block->variablesAtHead.operand(operand);
                if (!node)
                    continue;
                VariableAccessData* variable = node->variableAccessData();
                HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable);
                if (iter == m_map.end())
                    continue;
                if (!TypeCheck::isValidToHoist(iter->value))
                    continue;
                Optional<JSValue> value = mustHandleValues[i];
                if (!value || !value.value() || !value.value().isCell() || TypeCheck::isContravenedByValue(iter->value, value.value())) {
                    TypeCheck::disableHoisting(iter->value);
                    continue;
                }
            }
        }
    }

    void disableCheckArrayHoisting(VariableAccessData* variable)
    {
        HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData());
        result.iterator->value.disableCheckArrayHoisting();
    }

    template <typename TypeCheck>
    bool shouldConsiderForHoisting(VariableAccessData* variable)
    {
        if (!variable->shouldUnboxIfPossible())
            return false;
        if (TypeCheck::hoistingPreviouslyFailed(variable))
            return false;
        if (!isCellSpeculation(variable->prediction()))
            return false;
        return true;
    }
    
    void noticeStructureCheck(VariableAccessData* variable, RegisteredStructure structure)
    {
        HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(structure.get()));
        if (result.isNewEntry)
            return;
        if (result.iterator->value.m_structure == structure.get())
            return;
        result.iterator->value.m_structure = 0;
    }
    
    void noticeStructureCheck(VariableAccessData* variable, RegisteredStructureSet set)
    {
        if (set.size() != 1) {
            noticeStructureCheck(variable, RegisteredStructure());
            return;
        }
        noticeStructureCheck(variable, set.at(0));
    }

    void noticeCheckArray(VariableAccessData* variable, ArrayMode arrayMode)
    {
        HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(arrayMode));
        if (result.isNewEntry)
            return;
        if (!result.iterator->value.m_arrayModeHoistingOkay)
            return;
        if (result.iterator->value.m_arrayMode == arrayMode)
            return;
        if (!result.iterator->value.m_arrayModeIsValid) {
            result.iterator->value.m_arrayMode = arrayMode;
            result.iterator->value.m_arrayModeIsValid = true;
            return;
        }
        result.iterator->value.disableCheckArrayHoisting();
    }

    void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, RegisteredStructure structure)
    {
        HashMap<VariableAccessData*, CheckData>::iterator result = m_map.find(variable);
        if (result == m_map.end())
            return;
        if (!result->value.m_arrayModeHoistingOkay || !result->value.m_arrayModeIsValid)
            return;
        if (result->value.m_arrayMode.structureWouldPassArrayModeFiltering(structure.get()))
            return;
        result->value.disableCheckArrayHoisting();
    }

    void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, RegisteredStructureSet set)
    {
        for (unsigned i = 0; i < set.size(); i++)
            noticeStructureCheckAccountingForArrayMode(variable, set.at(i));
    }

    HashMap<VariableAccessData*, CheckData> m_map;
};

bool performTypeCheckHoisting(Graph& graph)
{
    return runPhase<TypeCheckHoistingPhase>(graph);
}

struct ArrayTypeCheck {
    static bool isValidToHoist(CheckData& checkData)
    {
        return checkData.m_arrayModeIsValid;
    }

    static void disableHoisting(CheckData& checkData)
    {
        checkData.disableCheckArrayHoisting();
    }

    static bool isContravenedByValue(CheckData& checkData, JSValue value)
    {
        ASSERT(value.isCell());
        return !checkData.m_arrayMode.structureWouldPassArrayModeFiltering(value.asCell()->structure());
    }

    static bool hasEnoughVotesToHoist(VariableAccessData* variable)
    {
        return variable->voteRatio() >= Options::checkArrayVoteRatioForHoisting();
    }

    static bool hoistingPreviouslyFailed(VariableAccessData* variable)
    {
        return variable->checkArrayHoistingFailed();
    }
};

struct StructureTypeCheck {
    static bool isValidToHoist(CheckData& checkData)
    {
        return checkData.m_structure;
    }

    static void disableHoisting(CheckData& checkData)
    {
        checkData.m_structure = 0;
    }

    static bool isContravenedByValue(CheckData& checkData, JSValue value)
    {
        ASSERT(value.isCell());
        return checkData.m_structure != value.asCell()->structure();
    }

    static bool hasEnoughVotesToHoist(VariableAccessData* variable)
    {
        return variable->voteRatio() >= Options::structureCheckVoteRatioForHoisting();
    }

    static bool hoistingPreviouslyFailed(VariableAccessData* variable)
    {
        return variable->structureCheckHoistingFailed();
    }
};

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)