/*
 * Copyright (C) 2011-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 "DFGCFAPhase.h"

#if ENABLE(DFG_JIT)

#include "DFGAbstractInterpreterInlines.h"
#include "DFGBlockSet.h"
#include "DFGClobberSet.h"
#include "DFGClobberize.h"
#include "DFGGraph.h"
#include "DFGInPlaceAbstractState.h"
#include "DFGPhase.h"
#include "DFGSafeToExecute.h"
#include "OperandsInlines.h"
#include "JSCInlines.h"

namespace JSC { namespace DFG {

class CFAPhase : public Phase {
public:
    CFAPhase(Graph& graph)
        : Phase(graph, "control flow analysis")
        , m_state(graph)
        , m_interpreter(graph, m_state)
        , m_verbose(Options::verboseCFA())
    {
    }
    
    bool run()
    {
        ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
        ASSERT(m_graph.m_unificationState == GloballyUnified);
        ASSERT(m_graph.m_refCountState == EverythingIsLive);
        
        m_count = 0;

        if (m_verbose && !shouldDumpGraphAtEachPhase(m_graph.m_plan.mode())) {
            dataLog("Graph before CFA:\n");
            m_graph.dump();
        }
        
        // This implements a pseudo-worklist-based forward CFA, except that the visit order
        // of blocks is the bytecode program order (which is nearly topological), and
        // instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit
        // is set to true. This is likely to balance the efficiency properties of both
        // worklist-based and forward fixpoint-based approaches. Like a worklist-based
        // approach, it won't visit code if it's meaningless to do so (nothing changed at
        // the head of the block or the predecessors have not been visited). Like a forward
        // fixpoint-based approach, it has a high probability of only visiting a block
        // after all predecessors have been visited. Only loops will cause this analysis to
        // revisit blocks, and the amount of revisiting is proportional to loop depth.
        
        m_state.initialize();
        
        if (m_graph.m_form != SSA) {
            if (m_verbose)
                dataLog("   Widening state at OSR entry block.\n");
            
            // Widen the abstract values at the block that serves as the must-handle OSR entry.
            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
                BasicBlock* block = m_graph.block(blockIndex);
                if (!block)
                    continue;
                
                if (!block->isOSRTarget)
                    continue;
                if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex())
                    continue;
                
                // We record that the block needs some OSR stuff, but we don't do that yet. We want to
                // handle OSR entry data at the right time in order to get the best compile times. If we
                // simply injected OSR data right now, then we'd potentially cause a loop body to be
                // interpreted with just the constants we feed it, which is more expensive than if we
                // interpreted it with non-constant values. If we always injected this data after the
                // main pass of CFA ran, then we would potentially spend a bunch of time rerunning CFA
                // after convergence. So, we try very hard to inject OSR data for a block when we first
                // naturally come to see it - see the m_blocksWithOSR check in performBlockCFA(). This
                // way, we:
                //
                // - Reduce the likelihood of interpreting the block with constants, since we will inject
                //   the OSR entry constants on top of whatever abstract values we got for that block on
                //   the first pass. The mix of those two things is likely to not be constant.
                //
                // - Reduce the total number of CFA reexecutions since we inject the OSR data as part of
                //   the normal flow of CFA instead of having to do a second fixpoint. We may still have
                //   to do a second fixpoint if we don't even reach the OSR entry block during the main
                //   run of CFA, but in that case at least we're not being redundant.
                m_blocksWithOSR.add(block);
            }
        }

        do {
            m_changed = false;
            performForwardCFA();
        } while (m_changed);
        
        if (m_graph.m_form != SSA) {
            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
                BasicBlock* block = m_graph.block(blockIndex);
                if (!block)
                    continue;
                
                if (m_blocksWithOSR.remove(block))
                    m_changed |= injectOSR(block);
            }
            
            while (m_changed) {
                m_changed = false;
                performForwardCFA();
            }
        
            // Make sure we record the intersection of all proofs that we ever allowed the
            // compiler to rely upon.
            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
                BasicBlock* block = m_graph.block(blockIndex);
                if (!block)
                    continue;
                
                block->intersectionOfCFAHasVisited &= block->cfaHasVisited;
                for (unsigned i = block->intersectionOfPastValuesAtHead.size(); i--;) {
                    AbstractValue value = block->valuesAtHead[i];
                    // We need to guarantee that when we do an OSR entry, we validate the incoming
                    // value as if it could be live past an invalidation point. Otherwise, we may
                    // OSR enter with a value with the wrong structure, and an InvalidationPoint's
                    // promise of filtering the structure set of certain values is no longer upheld.
                    value.m_structure.observeInvalidationPoint();
                    block->intersectionOfPastValuesAtHead[i].filter(value);
                }
            }
        }
        
        return true;
    }
    
private:
    bool injectOSR(BasicBlock* block)
    {
        if (m_verbose)
            dataLog("   Found must-handle block: ", *block, "\n");
        
        // This merges snapshot of stack values while CFA phase want to have proven types and values. This is somewhat tricky.
        // But this is OK as long as DFG OSR entry validates the inputs with *proven* AbstracValue values. And it turns out that this
        // type widening is critical to navier-stokes. Without it, navier-stokes has more strict constraint on OSR entry and
        // fails OSR entry repeatedly.
        bool changed = false;
        const Operands<Optional<JSValue>>& mustHandleValues = m_graph.m_plan.mustHandleValues();
        for (size_t i = mustHandleValues.size(); i--;) {
            int operand = mustHandleValues.operandForIndex(i);
            Optional<JSValue> value = mustHandleValues[i];
            if (!value) {
                if (m_verbose)
                    dataLog("   Not live in bytecode: ", VirtualRegister(operand), "\n");
                continue;
            }
            Node* node = block->variablesAtHead.operand(operand);
            if (!node) {
                if (m_verbose)
                    dataLog("   Not live: ", VirtualRegister(operand), "\n");
                continue;
            }
            
            if (m_verbose)
                dataLog("   Widening ", VirtualRegister(operand), " with ", value.value(), "\n");
            
            AbstractValue& target = block->valuesAtHead.operand(operand);
            changed |= target.mergeOSREntryValue(m_graph, value.value(), node->variableAccessData(), node);
        }
        
        if (changed || !block->cfaHasVisited) {
            block->cfaShouldRevisit = true;
            return true;
        }
        
        return false;
    }
    
    void performBlockCFA(BasicBlock* block)
    {
        if (!block)
            return;
        if (!block->cfaShouldRevisit)
            return;
        if (m_verbose)
            dataLog("   Block ", *block, ":\n");
        
        if (m_blocksWithOSR.remove(block))
            injectOSR(block);
        
        m_state.beginBasicBlock(block);
        if (m_verbose) {
            dataLog("      head vars: ", block->valuesAtHead, "\n");
            if (m_graph.m_form == SSA)
                dataLog("      head regs: ", nodeValuePairListDump(block->ssa->valuesAtHead), "\n");
        }
        for (unsigned i = 0; i < block->size(); ++i) {
            Node* node = block->at(i);
            if (m_verbose) {
                dataLogF("      %s @%u: ", Graph::opName(node->op()), node->index());
                
                if (!safeToExecute(m_state, m_graph, node))
                    dataLog("(UNSAFE) ");
                
                dataLog(m_state.variablesForDebugging(), " ", m_interpreter);
                
                dataLogF("\n");
            }
            if (!m_interpreter.execute(i)) {
                if (m_verbose)
                    dataLogF("         Expect OSR exit.\n");
                break;
            }
            
            if (ASSERT_ENABLED
                && m_state.didClobberOrFolded() != writesOverlap(m_graph, node, JSCell_structureID))
                DFG_CRASH(m_graph, node, toCString("AI-clobberize disagreement; AI says ", m_state.clobberState(), " while clobberize says ", writeSet(m_graph, node)).data());
        }
        if (m_verbose) {
            dataLogF("      tail regs: ");
            m_interpreter.dump(WTF::dataFile());
            dataLogF("\n");
        }
        m_changed |= m_state.endBasicBlock();
        
        if (m_verbose) {
            dataLog("      tail vars: ", block->valuesAtTail, "\n");
            if (m_graph.m_form == SSA)
                dataLog("      head regs: ", nodeValuePairListDump(block->ssa->valuesAtTail), "\n");
        }
    }
    
    void performForwardCFA()
    {
        ++m_count;
        if (m_verbose)
            dataLogF("CFA [%u]\n", m_count);
        
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
            performBlockCFA(m_graph.block(blockIndex));
    }

private:
    InPlaceAbstractState m_state;
    AbstractInterpreter<InPlaceAbstractState> m_interpreter;
    BlockSet m_blocksWithOSR;
    
    const bool m_verbose;
    
    bool m_changed;
    unsigned m_count;
};

bool performCFA(Graph& graph)
{
    return runPhase<CFAPhase>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)